Fast Stochastic Algorithms for Lowrank and Nonsmooth Matrix Problems
[edit]
Proceedings of Machine Learning Research, PMLR 89:286294, 2019.
Abstract
Composite convex optimization problems which include both a nonsmooth term and a lowrank promoting term have important applications in machine learning and signal processing, such as when one wishes to recover an unknown matrix that is simultaneously lowrank and sparse. However, such problems are highly challenging to solve in largescale: the lowrank promoting term prohibits efficient implementations of proximal methods for composite optimization and even simple subgradient methods. On the other hand, methods which are tailored for lowrank optimization, such as conditional gradienttype methods, which are often applied to a smooth approximation of the nonsmooth objective, are slow since their runtime scales with both the large Lipchitz parameter of the smoothed gradient vector and with $1/\epsilon$, where $\epsilon$ is the target accuracy. In this paper we develop efficient algorithms for \textit{stochastic} optimization of a stronglyconvex objective which includes both a nonsmooth term and a lowrank promoting term. In particular, to the best of our knowledge, we present the first algorithm that enjoys all following critical properties for largescale problems: i) (nearly) optimal sample complexity, ii) each iteration requires only a single \textit{lowrank} SVD computation, and iii) overall number of thinSVD computations scales only with $\log{1/\epsilon}$ (as opposed to $\textrm{poly}(1/\epsilon)$ in previous methods). We also give an algorithm for the closelyrelated finitesum setting. We empirically demonstrate our results on the problem of recovering a simultaneously lowrank and sparse matrix.
Related Material


