Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
This work addresses efficiency and scalability issues for researchers and practitioners in machine learning dealing with large-scale matrix optimization problems like matrix completion.
The paper tackles the computational challenge of nuclear norm regularization in matrix optimization by developing a stochastic subgradient descent method with cheap iterations using low-rank stochastic subgradients and incremental SVD updates. The result is a practical algorithm that maintains low-rank factorizations for efficient memory use and prediction, showing competitive performance with state-of-the-art solvers in empirical comparisons.
We describe novel subgradient methods for a broad class of matrix optimization problems involving nuclear norm regularization. Unlike existing approaches, our method executes very cheap iterations by combining low-rank stochastic subgradients with efficient incremental SVD updates, made possible by highly optimized and parallelizable dense linear algebra operations on small matrices. Our practical algorithms always maintain a low-rank factorization of iterates that can be conveniently held in memory and efficiently multiplied to generate predictions in matrix completion settings. Empirical comparisons confirm that our approach is highly competitive with several recently proposed state-of-the-art solvers for such problems.