Research map / Optimization / Nonconvex and smooth optimization
Efficient Continual Finite-Sum Minimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces continual finite-sum minimization (solving each prefix-sum problem to epsilon accuracy) and CSVRG, a variance-reduced method with Õ(n/eps^{1/3} + 1/sqrt(eps)) first-order oracle complexity, plus lower bounds for "natural" first-order methods.
Problem
Maintaining epsilon-accurate minimizers of every prefix-sum of a growing sequence of strongly convex functions while keeping first-order oracle (gradient) cost low as n grows.
Approach
A variance-reduced SGD where the full prefix gradient is recomputed only sparsely (geometrically spaced stages), and at other stages a running average of past gradients is updated with one new FO; the inner estimator uses 3 FOs per step and is unbiased with bounded variance.
Key results
- CSVRG achieves Õ(n/eps^{1/3} + 1/sqrt(eps)) first-order oracle complexity for continual finite-sum minimization versus O(n/eps) for SGD and O(n^2 log(1/eps)) for variance-reduction methods.
- Lower bound: no natural first-order method achieves O(n^{2-alpha} log(1/eps)) for any alpha>0, and none achieves O(n/eps^alpha) for alpha<1/4.
- On ridge regression, CSVRG matches SGD's FO count with smaller suboptimality gap and reaches comparable error to Katyusha/SVRG using roughly 4% of their FOs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CSVRG instead of SGD | Continual finite-sum minimization · Continual finite-sum minimization (strongly convex) | FO complexity: \mathcal{O}(n/\epsilon) -> \tilde{\mathcal{O}}(n/\epsilon^{1/3} + 1/\sqrt{\epsilon}) | Helped |
| Use CSVRG instead of variance-reduction methods such as Katyusha | Continual finite-sum minimization · Continual finite-sum minimization (strongly convex) | FO complexity: \mathcal{O}(n^2 \log(1/\epsilon)) -> \tilde{\mathcal{O}}(n/\epsilon^{1/3} + 1/\sqrt{\epsilon}) | Helped |
| Use CSVRG instead of SGD-sparse | Continual finite-sum minimization · Continual finite-sum minimization (strongly convex) | FO complexity: \mathcal{O}(\log n/\epsilon^2) -> \tilde{\mathcal{O}}(n/\epsilon^{1/3} + \log n/\sqrt{\epsilon}) | Mixed |
| Use CSVRG instead of SGD or SGD-sparse at matched FO calls | Ridge regression methods · Ridge regression on LIBSVM datasets, prefix sums | optimality gap | Helped |
| Use CSVRG instead of Katyusha or SVRG | Ridge regression methods · Ridge regression on LIBSVM datasets, prefix sums | optimality gap | No clear effect |
Limitations
- Theoretical guarantees restricted to the strongly convex case.
- Lower bound gap remains between n^{4/3} upper and n^{5/4} lower bound at epsilon=1/n.
- Experiments limited to ridge regression on LIBSVM.
Experimental setup
Datasets: LIBSVM datasets
Benchmarks: LIBSVM ridge regression
Metrics: optimality gap number of first-order oracles
Baselines: SGD SGD-sparse Katyusha SVRG
Builds on: SVRG Katyusha SGD
Closest papers by meaning
- Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure (NeurIPS 2017 · similarity 0.90)
- Limitations on Variance-Reduction and Acceleration Schemes for Finite Sums Optimization (NeurIPS 2017 · similarity 0.89)
- Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization (NeurIPS 2022 · similarity 0.88)
- Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems (ICML 2020 · similarity 0.88)
- Proximal Stochastic Methods for Nonsmooth Nonconvex Finite-Sum Optimization (NeurIPS 2016 · similarity 0.88)
- A unified variance-reduced accelerated gradient method for convex optimization (NeurIPS 2019 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.