Research map / Optimization / Nonconvex and smooth optimization
Limitations on Variance-Reduction and Acceleration Schemes for Finite Sums Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Hide the identity of the sampled individual function | Finite sum optimization with a stochastic oracle · Smooth and strongly convex finite sums | oracle calls: n^2/2 | Hurt |
| Require the strong convexity parameter to be unknown to the algorithm | Oblivious finite sum algorithms with first-order and coordinate-descent oracles · Smooth and strongly convex finite sums | iteration complexity: tildeOmega(n+ kappa ln(1/epsilon)) | Hurt |
| Restrict the algorithm to stationary update rules | Oblivious finite sum algorithms with first-order and coordinate-descent oracles · Smooth and convex finite sums | iteration complexity: Omega(n+L/epsilon) | Hurt |
| Use an oblivious algorithm without restricting it to stationary updates | Finite sum algorithms with first-order and coordinate-descent oracles · Smooth and convex finite sums | iteration complexity: Omega(n+sqrt(nL/epsilon)) | Hurt |
Closest papers by meaning
- A Simple Practical Accelerated Method for Finite Sums (NeurIPS 2016 · similarity 0.91)
- Efficient Continual Finite-Sum Minimization (ICLR 2024 · similarity 0.89)
- Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions (ICLR 2024 · similarity 0.86)
- On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition (ICML 2024 · similarity 0.86)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.85)
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · similarity 0.85)
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.