# Screening for Sparse Online Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 18 Jan 2021.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Fast OSCAR and OWL Regression via Safe Screening Rules](https://mlsanity.com/paper/2006.16433/) (2020)
- [GAP Safe screening rules for sparse multi-task and multi-class models](https://mlsanity.com/paper/1506.03736/) (2015)
- [Screening Tests for Lasso Problems](https://mlsanity.com/paper/1405.4897/) (2014)
- [A Safe Screening Rule for Sparse Logistic Regression](https://mlsanity.com/paper/1307.4145/) (2013)
- [Safe Screening With Variational Inequalities and Its Application to LASSO](https://mlsanity.com/paper/1307.7577/) (2013)
- [Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso](https://mlsanity.com/paper/1412.4080/) (2014)
- [GAP Safe Screening Rules for Sparse-Group-Lasso](https://mlsanity.com/paper/1602.06225/) (2016)
- [Local Convergence Properties of SAGA/Prox-SVRG and Acceleration](https://mlsanity.com/paper/1802.02554/) (2018)
- [Model identification and local linear convergence of coordinate descent](https://mlsanity.com/paper/2010.11825/) (2020)
- [Model Selection with Low Complexity Priors](https://mlsanity.com/paper/1307.2342/) (2013)
- [Safe Screening for the Generalized Conditional Gradient Method](https://mlsanity.com/paper/2002.09718/) (2020)

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

- [An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification](https://mlsanity.com/paper/2208.06058/) (2022)
- [Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling](https://mlsanity.com/paper/2410.23601/) (2024)

## Abstract (arXiv)

Sparsity promoting regularizers are widely used to impose low-complexity structure (e.g. l1-norm for sparsity) to the regression coefficients of supervised learning. In the realm of deterministic optimization, the sequence generated by iterative algorithms (such as proximal gradient descent) exhibit "finite activity identification", namely, they can identify the low-complexity structure in a finite number of iterations. However, most online algorithms (such as proximal stochastic gradient descent) do not have the property owing to the vanishing step-size and non-vanishing variance. In this paper, by combining with a screening rule, we show how to eliminate useless features of the iterates generated by online algorithms, and thereby enforce finite activity identification. One consequence is that when combined with any convergent online algorithm, sparsity properties imposed by the regularizer can be exploited for computational gains. Numerically, significant acceleration can be obtained.