mlsanityData to 7 Oct 2026

Efficient Continual Finite-Sum Minimization

arXiv 2406.04731 ↗First posted 7 Jun 2024math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Given a sequence of functions f1,ldots,fn with fi:Dmapsto ℝ, finite-sum minimization seeks a point x^star ∈ D minimizing sumj=1n fj(x)/n. In this work, we propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization, that asks for a sequence of points x1^star,ldots,xn^star ∈ D such that each x^stari ∈ D minimizes the prefix-sum sumj=1ifj(x)/i. Assuming that each prefix-sum is strongly convex, we develop a first-order continual stochastic variance reduction gradient method (CSVRG) producing an ε-optimal sequence with mathcaltildeO(n/ε1/3 + 1/√ε) overall first-order oracles (FO). An FO corresponds to the computation of a single gradient nabla fj(x) at a given x ∈ D for some j ∈ [n]. Our approach significantly improves upon the O(n/ε) FOs that StochasticGradientDescent requires and the O(n2 log (1/ε)) FOs that state-of-the-art variance reduction methods such as Katyusha require. We also prove that there is no natural first-order method with Oleft(n/εαright) gradient complexity for α < 1/4, establishing that the first-order complexity of our method is nearly tight.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 34 of its 55 references that are in the map. First posted on arXiv 7 Jun 2024.

Builds on

34 of 55 references.

References · 34

  1. 2016Overcoming catastrophic forgetting in neural networkscited by 4,718
  2. 2021Convex optimizationcited by 2,479
  3. 2017Gradient Episodic Memory for Continual Learningcited by 1,871
  4. 2013An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networkscited by 711
  5. 2017Lifelong Learning with Dynamically Expandable Networkscited by 689
  6. 2018End-to-End Incremental Learningcited by 596
  7. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  8. 2017Variational Continual Learningcited by 335
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  11. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  12. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
22 more
  1. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  2. 2017Incremental Learning Through Deep Adaptationcited by 108
  3. 2022Constrained Few-shot Class-incremental Learningcited by 93
  4. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  5. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  6. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  7. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  8. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  9. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  10. 2018A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimizationcited by 33
  11. 2015An optimal randomized incremental gradient methodcited by 32
  12. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  13. 2019A Stochastic Composite Gradient Method with Incremental Variance Reductioncited by 26
  14. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 23
  15. 2020Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimizationcited by 18
  16. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17
  17. 2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
  18. 2018Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimizationcited by 15
  19. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  20. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  21. 2022An Introduction to Lifelong Supervised Learningcited by 12
  22. 2013Accelerated Mini-Batch Stochastic Dual Coordinate Ascentcited by 11

Built on by

Not cited yet.