Research map / Optimization / Nonconvex and smooth optimization
A Generic Acceleration Framework for Stochastic Composite 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 |
|---|---|---|---|
| Accelerate prox-SGD using Catalyst with a strongly convex surrogate and optimality gaps | prox-SGD · Strongly convex stochastic composite optimization | iteration complexity: \tilde{O}\left(\sqrt{\frac{L}{\mu}}\log\left(\frac{F_0}{\varepsilon}\right) + \frac{\sigma^2}{\mu \varepsilon} \right) | Helped |
| Accelerate SAGA/MISO/SVRG using Catalyst with a strongly convex surrogate and optimality gaps | SAGA/MISO/SVRG · Strongly convex stochastic finite-sum optimization | iteration complexity: \tilde{O}\left( \sqrt{n\frac{L}{\mu}}\log\left(\frac{F_0}{\varepsilon} \right) + \frac{{\sigma}^2}{\mu\varepsilon} \righ | Helped |
| Use ordinary stochastic Catalyst with bias reduction by mini-batching or decreasing step sizes | Catalyst stochastic subproblems · Strongly convex stochastic optimization | noise-dependent iteration complexity: \frac{{B\sigma^2}}{{q^{3/2} \tau}\varepsilon} | Hurt |
| Use a method that provides a closed-form strongly convex surrogate alongside approximate minimization | Stochastic Catalyst · Strongly convex stochastic optimization | noise-dependent iteration complexity: \frac{{B\sigma^2}}{{q} \tau\varepsilon} | Helped |
| Use accelerated stochastic proximal gradient with an unbiased noisy gradient and exact prox | proximal stochastic gradient · Strongly convex stochastic composite optimization | expected objective error: \left( 1- \sqrt{\frac{\mu}{L}} \right)^k (F(x_0)-F^\star) + \frac{\sigma^2}{\sqrt{\mu L}} | Helped |
| Use accelerated stochastic proximal gradient with a finite horizon when the objective is convex | proximal stochastic gradient · Convex stochastic composite optimization | expected objective error: \frac{2L\|x_0-x^\star\|^2}{(K+1)^2} + \frac{3\sigma \|x_0-x^\star\|}{\sqrt{K+1}} | Helped |
| Use Catalyst with ISTA-like stochastic inner optimization instead of a surrogate that exploits optimality gaps | ISTA · Strongly convex stochastic optimization | noise-dependent iteration complexity: \tilde{O}((\sqrt{L/\mu}) {\sigma^2}/{\mu\varepsilon}) | Hurt |
| Use acceleration for very ill-conditioned cases with μ=1/1000n | acceleration methods · Logistic regression experiments, μ=1/1000n | objective convergence | Hurt |
| Use inexact proximal operators in the accelerated stochastic proximal method | accelerated stochastic proximal gradient · Strongly convex stochastic composite optimization | noise-dependent error contribution: \delta_k = 2 \varepsilon_k + {3\sigma^2}/({2(\kappa+\mu))} | Mixed |
| Use decreasing step sizes for SVRG and SAGA when perturbation noise is nonzero | SVRG and SAGA · Stochastic finite-sum experiments | convergence | Helped |
| Apply acceleration in stochastic optimization outside the very ill-conditioned setting | acceleration methods · Stochastic finite-sum experiments | objective convergence | Helped |
Closest papers by meaning
- A Universally Optimal Multistage Accelerated Stochastic Gradient Method (NeurIPS 2019 · similarity 0.91)
- Almost surely constrained convex optimization (ICML 2019 · similarity 0.91)
- Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping (NeurIPS 2020 · similarity 0.91)
- Estimate Sequences for Variance-Reduced Stochastic Composite Optimization (ICML 2019 · similarity 0.91)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · similarity 0.90)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.90)
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.