# Fast Stochastic Algorithms for Low-rank and Nonsmooth Matrix Problems

arXiv: https://arxiv.org/abs/1809.10477 · HTML: https://mlsanity.com/paper/1809.10477/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2018.

## Built on by (most cited first, 5 of 5)

- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)
- [First-Order Sparse Convex Optimization: Better Rates with Sparse Updates](https://mlsanity.com/paper/2506.19075/) (2025)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

Composite convex optimization problems which include both a nonsmooth term and a low-rank promoting term have important applications in machine learning and signal processing, such as when one wishes to recover an unknown matrix that is simultaneously low-rank and sparse. However, such problems are highly challenging to solve in large-scale: the low-rank 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 low-rank optimization, such as conditional gradient-type methods, which are often applied to a smooth approximation of the nonsmooth objective, are slow since their runtime scales with both the large Lipshitz parameter of the smoothed gradient vector and with 1/ε. In this paper we develop efficient algorithms for textitstochastic optimization of a strongly-convex objective which includes both a nonsmooth term and a low-rank promoting term. In particular, to the best of our knowledge, we present the first algorithm that enjoys all following critical properties for large-scale problems: i) (nearly) optimal sample complexity, ii) each iteration requires only a single textitlow-rank SVD computation, and iii) overall number of thin-SVD computations scales only with log1/ε (as opposed to textrmpoly(1/ε) in previous methods). We also give an algorithm for the closely-related finite-sum setting. At the heart of our results lie a novel combination of a variance-reduction technique and the use of a textitweak-proximal oracle which is key to obtaining all above three properties simultaneously.