# Distributed Dynamic Safe Screening Algorithms for Sparse Regularization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 23 Apr 2022.

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

- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient](https://mlsanity.com/paper/1803.06573/) (2018)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Mind the duality gap: safer rules for the Lasso](https://mlsanity.com/paper/1505.03410/) (2015)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)
- [Fast OSCAR and OWL Regression via Safe Screening Rules](https://mlsanity.com/paper/2006.16433/) (2020)
- [On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants](https://mlsanity.com/paper/1506.06840/) (2015)
- [Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling](https://mlsanity.com/paper/1602.02485/) (2016)
- [ASAGA: Asynchronous Parallel SAGA](https://mlsanity.com/paper/1606.04809/) (2016)
- [An Optimization-Based Meta-Learning Model for MRI Reconstruction with Diverse Dataset](https://mlsanity.com/paper/2110.00715/) (2021)
- [GAP Safe screening rules for sparse multi-task and multi-class models](https://mlsanity.com/paper/1506.03736/) (2015)
- [Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction](https://mlsanity.com/paper/2007.11245/) (2020)
- [A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates](https://mlsanity.com/paper/1806.11027/) (2018)
- [Screening Rules for Lasso with Non-Convex Sparse Regularizers](https://mlsanity.com/paper/1902.06125/) (2019)
- [GAP Safe Screening Rules for Sparse-Group-Lasso](https://mlsanity.com/paper/1602.06225/) (2016)
- [Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization](https://mlsanity.com/paper/1707.06468/) (2017)
- [Asynchronous Stochastic Proximal Optimization Algorithms with Variance Reduction](https://mlsanity.com/paper/1609.08435/) (2016)
- [Make Workers Work Harder: Decoupled Asynchronous Proximal Stochastic Gradient Descent](https://mlsanity.com/paper/1605.06619/) (2016)

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

- [Communication-Efficient Robust Federated Learning with Noisy Labels](https://mlsanity.com/paper/2206.05558/) (2022)

## Abstract (arXiv)

Distributed optimization has been widely used as one of the most efficient approaches for model training with massive samples. However, large-scale learning problems with both massive samples and high-dimensional features widely exist in the era of big data. Safe screening is a popular technique to speed up high-dimensional models by discarding the inactive features with zero coefficients. Nevertheless, existing safe screening methods are limited to the sequential setting. In this paper, we propose a new distributed dynamic safe screening (DDSS) method for sparsity regularized models and apply it on shared-memory and distributed-memory architecture respectively, which can achieve significant speedup without any loss of accuracy by simultaneously enjoying the sparsity of the model and dataset. To the best of our knowledge, this is the first work of distributed safe dynamic screening method. Theoretically, we prove that the proposed method achieves the linear convergence rate with lower overall complexity and can eliminate almost all the inactive features in a finite number of iterations almost surely. Finally, extensive experimental results on benchmark datasets confirm the superiority of our proposed method.