Optimal Smooth Approximation for Quantile Matrix Factorization

Matrix Factorization (MF) is a critical technique in many applications. Most existing MF methods minimize the $L_2$ loss between observations and their dependent matrix measurement variables. Under certain conditions, linear convergence to global optimality can be established for $L_2$ loss, while $L_1$ loss and check loss are widely used to deal with data that are contaminated with outliers, there lacks of efficient and theoretically proven algorithms specifically designed for MF with non-smooth losses. In this paper, we study Quantile Matrix Factorization (QMF) that adopts a tunable check loss and can introduce robustness to matrix estimation under possibly skewed and heavy-tailed observations, which are prevalent in reality. To deal with the non-smooth loss, we propose Nesterov-smoothed QMF (NsQMF), extending Nesterov's optimal smooth approximation technique to MF. We then present an alternating minimization algorithm to solve NsQMF efficiently while handling non-convexity. We prove that solving the smoothed NsQMF is equivalent to solving the original non-smooth QMF problem and that our algorithm achieves linear convergence to the global optimality of QMF. Extensive evaluations verify our theoretical findings and demonstrate that NsQMF significantly outperforms commonly used Least Squares Matrix Factorization (LSMF) and prior rough smoothing techniques for QMF under various noise distributions.