# An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification

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

## Key facts

- Cited by 14 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 11 Aug 2022.

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

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [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)
- [FairPrune: Achieving Fairness Through Pruning for Dermatological Disease Diagnosis](https://mlsanity.com/paper/2203.02110/) (2022)
- [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)
- [Fast OSCAR and OWL Regression via Safe Screening Rules](https://mlsanity.com/paper/2006.16433/) (2020)
- [Enabling On-Device CNN Training by Self-Supervised Instance Filtering and Error Map Pruning](https://mlsanity.com/paper/2007.03213/) (2020)
- [Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction](https://mlsanity.com/paper/2205.01608/) (2022)
- [Intermittent Inference with Nonuniformly Compressed Multi-Exit Neural Network for Energy Harvesting Powered Devices](https://mlsanity.com/paper/2004.11293/) (2020)
- [An Optimization-Based Meta-Learning Model for MRI Reconstruction with Diverse Dataset](https://mlsanity.com/paper/2110.00715/) (2021)
- [Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction](https://mlsanity.com/paper/2007.11245/) (2020)
- [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013)
- [Screening Rules for Lasso with Non-Convex Sparse Regularizers](https://mlsanity.com/paper/1902.06125/) (2019)
- [Local Convergence Properties of SAGA/Prox-SVRG and Acceleration](https://mlsanity.com/paper/1802.02554/) (2018)
- [Screening Rules and its Complexity for Active Set Identification](https://mlsanity.com/paper/2009.02709/) (2020)
- [Randomized Block Coordinate Descent for Online and Stochastic Optimization](https://mlsanity.com/paper/1407.0107/) (2014)
- [Primal-Dual Rates and Certificates](https://mlsanity.com/paper/1602.05205/) (2016)
- [Screening for Sparse Online Learning](https://mlsanity.com/paper/2101.06982/) (2021)
- [PSGR: Pixel-wise Sparse Graph Reasoning for COVID-19 Pneumonia Segmentation in CT Images](https://mlsanity.com/paper/2108.03809/) (2021)

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

- [AutoReP: Automatic ReLU Replacement for Fast Private Network Inference](https://mlsanity.com/paper/2308.10134/) (2023)
- [LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference](https://mlsanity.com/paper/2309.14331/) (2023)
- [Unlocking Memorization in Large Language Models with Dynamic Soft Prompting](https://mlsanity.com/paper/2409.13853/) (2024)
- [Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratch](https://mlsanity.com/paper/2403.14729/) (2024)
- [RRNet: Towards ReLU-Reduced Neural Network for Two-party Computation Based Private Inference](https://mlsanity.com/paper/2302.02292/) (2023)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [QuMoS: A Framework for Preserving Security of Quantum Machine Learning Model](https://mlsanity.com/paper/2304.11511/) (2023)
- [Federated Conditional Stochastic Optimization](https://mlsanity.com/paper/2310.02524/) (2023)
- [All-in-One Tuning and Structural Pruning for Domain-Specific LLMs](https://mlsanity.com/paper/2412.14426/) (2024)
- [ALTER: All-in-One Layer Pruning and Temporal Expert Routing for Efficient Diffusion Generation](https://mlsanity.com/paper/2505.21817/) (2025)
- [Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruning](https://mlsanity.com/paper/2306.13561/) (2023)
- [Edge-InversionNet: Enabling Efficient Inference of InversionNet on Edge Devices](https://mlsanity.com/paper/2310.09667/) (2023)
- [Safe Screening Rules for Group OWL Models](https://mlsanity.com/paper/2504.03152/) (2025)
- [Safe Screening Rules for Group SLOPE](https://mlsanity.com/paper/2506.09451/) (2025)

## Abstract (arXiv)

Sparsity regularized loss minimization problems play an important role in various fields including machine learning, data mining, and modern statistics. Proximal gradient descent method and coordinate descent method are the most popular approaches to solving the minimization problem. Although existing methods can achieve implicit model identification, aka support set identification, in a finite number of iterations, these methods still suffer from huge computational costs and memory burdens in high-dimensional scenarios. The reason is that the support set identification in these methods is implicit and thus cannot explicitly identify the low-complexity structure in practice, namely, they cannot discard useless coefficients of the associated features to achieve algorithmic acceleration via dimension reduction. To address this challenge, we propose a novel accelerated doubly stochastic gradient descent (ADSGD) method for sparsity regularized loss minimization problems, which can reduce the number of block iterations by eliminating inactive coefficients during the optimization process and eventually achieve faster explicit model identification and improve the algorithm efficiency. Theoretically, we first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity. More importantly, we prove that ADSGD can achieve a linear rate of explicit model identification. Numerically, experimental results on benchmark datasets confirm the efficiency of our proposed method.