SVD-free Approaches For Nuclear Norm Regularization

Many applications in machine learning,such as marix completion,collaborative filtering,multi-task learning and so on,aim to recover a low-rank matrix.These prob-lems can be solved by minimizing a convex function of matrices regularized by the nuclear norm.However,the non-smoothness,as well as the expensive gradient oper-ations of the nuclear norm,poses a series of challenges to the design of optimization algorithms.In this situation,the paper focuses on the problem of minimizing a convex function of matrices regularized by the nuclear norm under high-dimensional data and studies the following aspects.When the size of the data matrix,denoted by m×n,is very large,existing optimization methods are inefficient because in each iteration,they need to perform a singular value decomposition(SVD)which takes O(m2n)time.To reduce the computation cost,we exploit the dual characterization of the nuclear norm to intro-duce a convex-concave optimization problem and design a subgradient-based algorithm without performing SVD.In each iteration,the proposed algorithm only computes the largest singular vector,reducing the time complexity from O(m2n)to O(mn).To the best of our knowledge,this is the first SVD-free convex optimization approach for nuclear-norm regularized problems that does not rely on the smoothness assumption.Theoretical analysis shows that the proposed algorithm converges at an optimal O(1/(?))rate where T is the number of iterations.We also extend our algorithm to the stochastic case where only stochastic subgradients of the convex function are avail-able and a special case that contains an additional non-smooth regularizer(e.g.,l1 norm regularizer).In both extensions,we prove that.both the computation complexity and convergence rates are the same as the one of the basic algorithm.Finally,we conduct experiments on robust low-rank matrix approximation and link prediction to demon-strate the efficiency of our algorithms.