Research map / Optimization / Nonconvex and smooth optimization
Acceleration with a Ball Optimization Oracle
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 ball optimization with the Monteiro-Svaiter framework | Smooth convex minimization with a radius-r ball optimization oracle · Smooth convex minimization | ball oracle queries: O\left(\frac{R}{r}\log\frac{\epsilon_0}{\epsilon}\right) -> O\left({{\left(\frac{R}{r}\right)^{2/3}\log\bigg(\frac{\epsi | Improved |
| Implement an accelerated MS algorithm with a ball optimization oracle | Ball-oracle convex optimization · Smooth convex minimization | query complexity exponent in R/r: (R/r)^{2/3} lower bound | No clear effect |
| Use Hessian stability to implement ball optimization with accelerated Newton steps | Hessian-stable functions · Ball-constrained function minimization | linear system solves: c^2 -> \widetilde{O}(c) | Improved |
| Apply accelerated ball optimization rather than the prior trust-region Newton method | Logistic regression · Logistic regression | linear system solves dependence on R: \widetilde{O}(R) -> O\left(R^{2/3}\log\left(\frac{\epsilon_0}{\epsilon}\right)\log^3\left(\frac{R^2}{\epsilon}(1 + R)\ri | Improved |
| Use accelerated ball optimization on a softmax approximation | ℓ∞ regression · ℓ∞ regression | linear system solves dependence on R/ε: \widetilde{O}((R/\epsilon)^{4/5}) -> O\left(\left(\frac{R\log n}{\epsilon}\right)^{2/3}\log\left(\frac{\epsilon_0}{\epsi | Improved |
Closest papers by meaning
- Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values (NeurIPS 2024 · similarity 0.84)
- Smooth Convex Optimization Using Sub-Zeroth-Order Oracles (AAAI 2021 · similarity 0.81)
- Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm (JMLR 2024 · similarity 0.81)
- Distributionally Robust Optimization via Ball Oracle Acceleration (NeurIPS 2022 · similarity 0.81)
- A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles (ICML 2024 · similarity 0.79)
- Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization (ICLR 2025 · similarity 0.79)
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.
