# Learning Large Scale Sparse Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 26 Jan 2023.

## Builds on (most cited first, 7 of 7)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization](https://mlsanity.com/paper/1310.7991/) (2013)
- [New Algorithms for Learning Incoherent and Overcomplete Dictionaries](https://mlsanity.com/paper/1308.6273/) (2013)
- [Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization](https://mlsanity.com/paper/1309.2375/) (2013)
- [On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants](https://mlsanity.com/paper/1506.06840/) (2015)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)

## Abstract (arXiv)

In this work, we consider learning sparse models in large scale settings, where the number of samples and the feature dimension can grow as large as millions or billions. Two immediate issues occur under such challenging scenario: (i) computational cost; (ii) memory overhead. In particular, the memory issue precludes a large volume of prior algorithms that are based on batch optimization technique. To remedy the problem, we propose to learn sparse models such as Lasso in an online manner where in each iteration, only one randomly chosen sample is revealed to update a sparse iterate. Thereby, the memory cost is independent of the sample size and gradient evaluation for one sample is efficient. Perhaps amazingly, we find that with the same parameter, sparsity promoted by batch methods is not preserved in online fashion. We analyze such interesting phenomenon and illustrate some effective variants including mini-batch methods and a hard thresholding based stochastic gradient algorithm. Extensive experiments are carried out on a public dataset which supports our findings and algorithms.