# Efficient Continual Finite-Sum Minimization

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

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks](https://mlsanity.com/paper/1312.6211/) (2013)
- [Lifelong Learning with Dynamically Expandable Networks](https://mlsanity.com/paper/1708.01547/) (2017)
- [End-to-End Incremental Learning](https://mlsanity.com/paper/1807.09536/) (2018)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Variational Continual Learning](https://mlsanity.com/paper/1710.10628/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Incremental Learning Through Deep Adaptation](https://mlsanity.com/paper/1705.04228/) (2017)
- [Constrained Few-shot Class-incremental Learning](https://mlsanity.com/paper/2203.16588/) (2022)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1802.04477/) (2018)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)

## 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.