# Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2015.

## Built on by (most cited first, 30 of 45)

- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Particle-based Variational Inference with Preconditioned Functional Gradient Flow](https://mlsanity.com/paper/2211.13954/) (2022)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [Faster Deep Reinforcement Learning with Slower Online Network](https://mlsanity.com/paper/2112.05848/) (2021)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)
- [Federated Learning with Server Learning: Enhancing Performance for Non-IID Data](https://mlsanity.com/paper/2210.02614/) (2022)
- [Linear Speedup of Incremental Aggregated Gradient Methods on Streaming Data](https://mlsanity.com/paper/2309.04980/) (2023)
- [Personalized Federated Learning with Attention-based Client Selection](https://mlsanity.com/paper/2312.15148/) (2023)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [FedMCSA: Personalized Federated Learning via Model Components Self-Attention](https://mlsanity.com/paper/2208.10731/) (2022)
- [Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networks](https://mlsanity.com/paper/2304.09221/) (2023)
- [Generalized Low-Rank Update: Model Parameter Bounds for Low-Rank Training Data Modifications](https://mlsanity.com/paper/2306.12670/) (2023)
- [The Diversity Bonus: Learning from Dissimilar Distributed Clients in Personalized Federated Learning](https://mlsanity.com/paper/2407.15464/) (2024)
- [Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers](https://mlsanity.com/paper/2110.07029/) (2021)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regime](https://mlsanity.com/paper/2305.10294/) (2023)
- [Understanding the Training Speedup from Sampling with Approximate Losses](https://mlsanity.com/paper/2402.07052/) (2024)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [On the Convergence of Federated Learning Algorithms without Data Similarity](https://mlsanity.com/paper/2403.02347/) (2024)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Single-shot Star-convex Polygon-based Instance Segmentation for Spatially-correlated Biomedical Objects](https://mlsanity.com/paper/2504.12078/) (2025)
- [Deep Neural Network Based Accelerated Failure Time Models using Rank Loss](https://mlsanity.com/paper/2206.05974/) (2022)
- [Proximal Mean Field Learning in Shallow Neural Networks](https://mlsanity.com/paper/2210.13879/) (2022)
- [FedSR: A Semi-Decentralized Federated Learning Algorithm for Non-IIDness in IoT System](https://mlsanity.com/paper/2403.14718/) (2024)
- [Artificial Intelligence for the Internal Democracy of Political Parties](https://mlsanity.com/paper/2405.09529/) (2024)

## Abstract (arXiv)

We survey incremental methods for minimizing a sum sumi=1mfi(x) consisting of a large number of convex component functions fi. Our methods consist of iterations applied to single components, and have proved very effective in practice. We introduce a unified algorithmic framework for a variety of such methods, some involving gradient and subgradient iterations, which are known, and some involving combinations of subgradient and proximal methods, which are new and offer greater flexibility in exploiting the special structure of fi. We provide an analysis of the convergence and rate of convergence properties of these methods, including the advantages offered by randomization in the selection of components. We also survey applications in inference/machine learning, signal processing, and large-scale and distributed optimization.