Research map / Optimization / Nonconvex and smooth optimization
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
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 adaptive selection of component functions with combined cutting-plane and interior-point updates | Decomposable convex optimization · Decomposable convex optimization | gradient oracle calls: O(nd \log(1/\epsilon)) -> O(m\log(m/\epsilon)) | Helped |
| Apply the proposed decomposable optimization algorithm to decomposable submodular minimization | Decomposable submodular minimization · Decomposable submodular minimization | evaluation oracle calls: \widetilde{O}(n k^6 \log (1/\epsilon)) -> O(n k^2 \log(nk/\epsilon)) | Helped |
Closest papers by meaning
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.90)
- The Complexity of Finding Stationary Points with Stochastic Gradient Descent (ICML 2020 · similarity 0.89)
- Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization (ICML 2023 · similarity 0.89)
- Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.89)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.89)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · 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.