mlsanityData to 14 Oct 2026

Last Iterate Convergence of Incremental Methods and Applications in Continual Learning

arXiv 2403.06873 ↗First posted 11 Mar 2024math.OC cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Incremental gradient and incremental proximal methods are a fundamental class of optimization algorithms used for solving finite sum problems, broadly studied in the literature. Yet, without strong convexity, their convergence guarantees have primarily been established for the ergodic (average) iterate. Motivated by applications in continual learning, we obtain the first convergence guarantees for the last iterate of both incremental gradient and incremental proximal methods, in general convex smooth (for both) and convex Lipschitz (for the proximal variants) settings. Our oracle complexity bounds for the last iterate nearly match (i.e., match up to a square-root-log or a log factor) the best known oracle complexity bounds for the average iterate, for both classes of methods. We further obtain generalizations of our results to weighted averaging of the iterates with increasing weights and for randomly permuted ordering of updates. We study incremental proximal methods as a model of continual learning with generalization and argue that large amount of regularization is crucial to preventing catastrophic forgetting. Our results generalize last iterate guarantees for incremental methods compared to state of the art, as such results were previously known only for overparameterized linear models, which correspond to convex quadratic problems with infinitely many solutions.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 48 of its 67 references that are in the map. First posted on arXiv 11 Mar 2024.

Builds on

48 of 67 references.

References · 48

  1. 2016Overcoming catastrophic forgetting in neural networkscited by 4,787
  2. 2017Gradient Episodic Memory for Continual Learningcited by 1,898
  3. 2016Progressive Neural Networkscited by 1,361
  4. 2018Continual Lifelong Learning with Neural Networks: A Reviewcited by 1,330
  5. 2018Experience Replay for Continual Learningcited by 1,095
  6. 2013An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networkscited by 722
  7. 2017Lifelong Learning with Dynamically Expandable Networkscited by 694
  8. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  9. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  10. 2020A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrixcited by 103
  11. 2021Continual Learning in the Teacher-Student Setup: Impact of Task Similaritycited by 88
  12. 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 81
36 more
  1. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
  2. 2023Theory on Forgetting and Generalization of Continual Learningcited by 72
  3. 2020Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descentcited by 68
  4. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  5. 2019How Good is SGD with Random Shuffling?cited by 64
  6. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  7. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  8. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  9. 2020Closing the convergence gap of SGD without replacementcited by 57
  10. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 45
  11. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  12. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
  13. 2023The Ideal Continual Learner: An Agent That Never Forgetscited by 35
  14. 2023Continual Learning in Linear Classification on Separable Datacited by 34
  15. 2021Proximal and Federated Random Reshufflingcited by 33
  16. 2022Analysis of Catastrophic Forgetting for Random Orthogonal Transformation Tasks in the Overparameterized Regimecited by 29
  17. 2024The Joint Effect of Task Similarity and Overparameterization on Catastrophic Forgetting -- An Analytical Modelcited by 26
  18. 2023Exact convergence rate of the last iterate in subgradient methodscited by 25
  19. 2023Fixed Design Analysis of Regularization-Based Continual Learningcited by 24
  20. 2014Efficient Representations for Life-Long Learning and Autoencodingcited by 23
  21. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  22. 2021Statistical Mechanical Analysis of Catastrophic Forgetting in Continual Learning with Teacher and Student Networkscited by 22
  23. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 22
  24. 2022Memory Bounds for Continual Learningcited by 19
  25. 2021Provable Lifelong Learning of Representationscited by 15
  26. 2021Provable Continual Learning via Sketched Jacobian Approximationscited by 15
  27. 2022Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructionscited by 11
  28. 2020Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machinecited by 10
  29. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  30. 2022Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimizationcited by 9
  31. 2019Incremental Methods for Weakly Convex Optimizationcited by 7
  32. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  33. 2023High Probability Guarantees for Random Reshufflingcited by 5
  34. 2021Cyclic Coordinate Dual Averaging with Extrapolationcited by 3
  35. 2023Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimizationcited by 3
  36. 2015Incremental Aggregated Proximal and Augmented Lagrangian Algorithmscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 4.

10 papers.

  1. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 12
  2. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  3. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  4. 2024LoRanPAC: Low-rank Random Features and Pre-trained Models for Bridging Theory and Practice in Continual Learningcited by 8
  5. 2025Optimal Rates in Continual Linear Regression via Increasing Regularizationcited by 8
  6. 2024Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite lossescited by 6
  7. 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 4
  8. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  9. 2026From Order to Distribution: An Exact Operator Framework for Forgetting in Continual Learningcited by 0
  10. 2026The Sequential Price of Continual Learningcited by 0