Research map / Optimization / Nonconvex and smooth optimization
Tight Complexity Bounds for Optimizing Composite Objectives
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 |
|---|---|---|---|
| use prox oracle to smooth non-smooth Lipschitz components (Moreau envelope) and run AGD | non-smooth composite sums · L-Lipschitz convex components | oracle complexity | Helped |
| use randomized accelerated SVRG (KATYUSHA-style) on smoothed components instead of gradient-only access | non-smooth composite sums · L-Lipschitz convex components | oracle complexity | Helped |
| deterministic algorithms vs randomized algorithms on finite sums | smooth finite-sum problems · smooth convex components | dependence on number of components m: linear in m (deterministic) vs √m (randomized) | Helped |
Closest papers by meaning
- Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems (ICML 2020 · similarity 0.90)
- The Complexity of Finding Stationary Points with Stochastic Gradient Descent (ICML 2020 · similarity 0.90)
- Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness (NeurIPS 2021 · similarity 0.90)
- Complexity of Highly Parallel Non-Smooth Convex Optimization (NeurIPS 2019 · similarity 0.89)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.88)
- A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle (ICML 2024 · similarity 0.88)
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.