mlsanityData to 7 Oct 2026

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

arXiv 2105.01778 ↗First posted 4 May 2021math.OC cs.DS cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

We characterize the complexity of minimizing maxi∈[N] fi(x) for convex, Lipschitz functions f1,ldots, fN. For non-smooth functions, existing methods require O(Nε-2) queries to a first-order oracle to compute an ε-suboptimal point and tildeO(Nε-1) queries if the fi are O(1/ε)-smooth. We develop methods with improved complexity bounds of tildeO(Nε-2/3 + ε-8/3) in the non-smooth case and tildeO(Nε-2/3 + √Nε-1) in the O(1/ε)-smooth case. Our methods consist of a recently proposed ball optimization oracle acceleration algorithm (which we refine) and a careful implementation of said oracle for the softmax function. We also prove an oracle complexity lower bound scaling as Omega(Nε-2/3), showing that our dependence on N is optimal up to polylogarithmic factors.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 4 May 2021.

Builds on

17 of 39 references.

References · 17

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  5. 2017Lower Bounds for Finding Stationary Points Icited by 125
  6. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  7. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  8. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  9. 2019Variance Reduction for Matrix Gamescited by 37
  10. 2020Acceleration with a Ball Optimization Oraclecited by 31
  11. 2016Minimizing the Maximal Loss: How and Why?cited by 30
  12. 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
5 more
  1. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  2. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 21
  3. 2018Lower Bounds for Parallel and Randomized Convex Optimizationcited by 17
  4. 2015Efficient Inverse Maintenance and Faster Algorithms for Linear Programmingcited by 13
  5. 2019Unified Acceleration of High-Order Algorithms under H"older Continuity and Uniform Convexitycited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 3; 2024: 2; 2025: 3; 2026: 1.

17 papers.

Sort:

  1. 2022Rank-based Decomposable Losses in Machine Learning: A Surveycited by 26
  2. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  3. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 19
  4. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  5. 2022Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyondcited by 16
  6. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  7. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  8. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  9. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  10. 2023Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Banditscited by 9
  11. 2021Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimizationcited by 4
  12. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
5 more
  1. 2025The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applicationscited by 3
  2. 2025Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimizationcited by 3
  3. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  4. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  5. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0