mlsanityData to 7 Oct 2026

Distributionally Robust Optimization via Ball Oracle Acceleration

arXiv 2203.13225 ↗First posted 24 Mar 2022math.OC cs.DS cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We develop and analyze algorithms for distributionally robust optimization (DRO) of convex losses. In particular, we consider group-structured and bounded f-divergence uncertainty sets. Our approach relies on an accelerated method that queries a ball optimization oracle, i.e., a subroutine that minimizes the objective within a small ball around the query point. Our main contribution is efficient implementations of this oracle for DRO objectives. For DRO with N non-smooth loss functions, the resulting algorithms find an ε-accurate solution with widetildeOleft(Nε-2/3 + ε-2right) first-order oracle queries to individual loss functions. Compared to existing algorithms for this problem, we improve complexity by a factor of up to ε-4/3.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 32 of its 67 references that are in the map. First posted on arXiv 24 Mar 2022.

Builds on

32 of 67 references.

References · 32

  1. 2020WILDS: A Benchmark of in-the-Wild Distribution Shiftscited by 1,366
  2. 2018Fairness Without Demographics in Repeated Loss Minimizationcited by 363
  3. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  4. 2015Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulationscited by 285
  5. 2019Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imagingcited by 215
  6. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  7. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  8. 2015Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approachcited by 162
  9. 2016Variance-based regularization with convex objectivescited by 153
  10. 2019Distributionally Robust Language Modelingcited by 142
  11. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  12. 2020Robust Optimization for Fairness with Noisy Protected Groupscited by 78
20 more
  1. 2021Risk-Averse Offline Reinforcement Learningcited by 65
  2. 2021DORO: Distributional and Outlier Robust Optimizationcited by 54
  3. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  4. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  5. 2019Adaptive Sampling for Stochastic Risk-Averse Learningcited by 39
  6. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
  7. 2016Geometric Median in Nearly Linear Timecited by 38
  8. 2020Acceleration with a Ball Optimization Oraclecited by 31
  9. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  10. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 23
  11. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 19
  12. 2021Is Importance Weighting Incompatible with Interpolating Classifiers?cited by 19
  13. 2021Distributionally Robust Multilingual Machine Translationcited by 18
  14. 2019Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applicationscited by 17
  15. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  16. 2018Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimizationcited by 15
  17. 2020Coordinate Methods for Matrix Gamescited by 15
  18. 2021Boosted CVaR Classificationcited by 12
  19. 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
  20. 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: 2023: 5; 2024: 1; 2025: 2; 2026: 6.

14 papers.

Sort:

  1. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  2. 2023Optimal Multi-Distribution Learningcited by 13
  3. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  4. 2023Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyondcited by 4
  5. 2023Efficient Stochastic Approximation of Minimax Excess Risk Optimizationcited by 4
  6. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  7. 2025Group Distributionally Robust Optimization with Flexible Sample Queriescited by 2
  8. 2026Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noisecited by 1
  9. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  10. 2026From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimizationcited by 0
  11. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0
  12. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 0
2 more
  1. 2026Optimal High-Order Methods for Solving Monotone Variational Inequalitiescited by 0
  2. 2026Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compressioncited by 0