mlsanityData to 14 Oct 2026

Acceleration with a Ball Optimization Oracle

arXiv 2003.08078 ↗First posted 18 Mar 2020math.OC cs.DScited by 31

Not on the map. Why?

Abstract (arXiv)

Consider an oracle which takes a point x and returns the minimizer of a convex function f in an ℓ2 ball of radius r around x. It is straightforward to show that roughly r-1logfrac1ε calls to the oracle suffice to find an ε-approximate minimizer of f in an ℓ2 unit ball. Perhaps surprisingly, this is not optimal: we design an accelerated algorithm which attains an ε-approximate minimizer with roughly r-2/3 log frac1ε oracle queries, and give a matching lower bound. Further, we implement ball optimization oracles for functions with locally stable Hessians using a variant of Newton's method. The resulting algorithm applies to a number of problems of practical and theoretical import, improving upon previous results for logistic and ℓ_∞ regression and achieving guarantees comparable to the state-of-the-art for ℓp regression.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 5; 2024: 7; 2025: 4; 2026: 2.

31 papers.

Sort:

  1. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  2. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  3. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 20
  4. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  5. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  6. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  7. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  8. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  9. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  10. 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
  11. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 8
  12. 2023Smoothed f-Divergence Distributionally Robust Optimizationcited by 7
19 more
  1. 2023Gradient Descent Converges Linearly for Logistic Regression on Separable Datacited by 7
  2. 2023Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Methodcited by 7
  3. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  4. 2025The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applicationscited by 5
  5. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  6. 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4
  7. 2025Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimizationcited by 4
  8. 2021Understanding Riemannian Acceleration via a Proximal Extragradient Frameworkcited by 3
  9. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  10. 2024Regularized Gauss-Newton for Optimizing Overparameterized Neural Networkscited by 3
  11. 2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimizationcited by 3
  12. 2024Non-Euclidean High-Order Smooth Convex Optimizationcited by 3
  13. 2025Gradient-Normalized Smoothness for Optimization with Approximate Hessianscited by 3
  14. 2021Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularizationcited by 1
  15. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  16. 2024Faster Acceleration for Steepest Descentcited by 1
  17. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  18. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0
  19. 2026Primal Acceleration of Newton's Methodcited by 0