Scalable Robust Matrix Factorization with Nonconvex Loss
Matrix factorization (MF), which uses the 2 -loss, and robust matrix factorization (RMF), which uses the 1 -loss, are sometimes not robust enough for outliers. Moreover, even the state-of-the-art RMF solver (RMF-MM) is slow and cannot utilize data sparsity. In this paper, we propose to improve robustness by using nonconvex loss functions. The resultant optimization problem is difficult. To improve efficiency and scalability, we use majorization-minimization (MM) and optimize the MM surrogate by using the accelerated proximal gradient algorithm on its dual problem. Data sparsity can also be exploited. The resultant algorithm has low time and space complexities, and is guaranteed to converge to a critical point. Extensive experiments show that it outperforms the state-of-the-art in terms of both accuracy and speed.
RMF solvers cannot be used. As in RMF-MM, we rely on the more flexible MM optimization technique, and a new MM surrogate is proposed. To improve scalability, we transform the surrogate to its dual and then solve it with the accelerated proximal gradient (APG) algorithm [2,32]. Data sparsity can also be exploited in the design of the APG algorithm. As for its convergence analysis, proof techniques in RMF-MM cannot be used as the loss is no longer convex. Instead, we develop new proof techniques based on the Clarke subdifferential [10], and show that convergence to a critical point can be guaranteed. Extensive experiments on both synthetic and real-world data sets demonstrate superiority of the proposed algorithm over the state-of-the-art in terms of both accuracy and scalability.
Notation. For scalar x, sign (x) = 1 if x > 0, 0 if x = 0, and −1 otherwise. For a vector x, Diag(x) constructs a diagonal matrix X with X ii = x i . For a matrix X, X F = ( i,j X 2 ij ) 1/2 is its Frobenius norm, X 1 = i,j |X ij | is its 1 -norm, and nnz(X) is the number of nonzero elements in X. For a square matrix X, tr(X) = i X ii is its trace. For two matrices X, Y , X Y denotes their element-wise product. For a smooth function f , ∇f is its gradient. For a convex f , G ∈ ∂f (X) = {U : f (Y ) ≥ f (X) + tr(U (Y − X))} is a subgradient.
In this paper, an algorithm for matrix factorization (MF) is proposed, which provide better robustness to outlier’s behavior compared to state of the art algorithms for Robust MF (RMF). Another nice property of the new algorithm is that it is suitable for sparse data matrices which is a clear advantage when it is compared against previous approaches to RMF. Basically, the authors propose to replace the l1 penalty with a nonconvex regularizer and provide results for various selections of regularizers. Since the optimization in this case is not simple, the authors propose to use a Majorization Minimization (MM) optimization approach with a definition of a new MM surrogate. The paper provides a nice introduction to the problem of robust matrix factorization, providing a complete overview of the state of the art and giving good motivations for the development of a new algorithm. I found the paper well written, technically sounded and having a nice structure. The theoretical treatment of the results is adequate giving guarantees of convergence. The paper includes a rich experimental section with useful comparisons with previously proposed algorithms and evaluating several options for regularizers. I definitively recommend the acceptance of this submission for presentation in NIPS. However, I found few minor issues which need attention for the final submission. Issues: • Font sizes in all figures are too small. Please consider resizing figures. • In section 4.1 Synthetic Data, outliers are generated by using constant values {+5, -5} in the 5% of the entries. I think, it would be very useful to analyze the effect of varying the percentage of affected entries (instead of a fixed 5%) and also to consider other values for outliers with some probabilistic distribution. I think that, by adding these new analysis the applicability of the algorithm would be better assessed. The authors agreed to add these additional results to the final version.