# Distributionally Robust Optimization via Ball Oracle Acceleration

arXiv: https://arxiv.org/abs/2203.13225 · HTML: https://mlsanity.com/paper/2203.13225/

## Key facts

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

## Builds on (most cited first, 30 of 32)

- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imaging](https://mlsanity.com/paper/1909.12475/) (2019)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Distributionally Robust Language Modeling](https://mlsanity.com/paper/1909.02060/) (2019)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Robust Optimization for Fairness with Noisy Protected Groups](https://mlsanity.com/paper/2002.09343/) (2020)
- [Risk-Averse Offline Reinforcement Learning](https://mlsanity.com/paper/2102.05371/) (2021)
- [DORO: Distributional and Outlier Robust Optimization](https://mlsanity.com/paper/2106.06142/) (2021)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [Adaptive Sampling for Stochastic Risk-Averse Learning](https://mlsanity.com/paper/1910.12511/) (2019)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)
- [Is Importance Weighting Incompatible with Interpolating Classifiers?](https://mlsanity.com/paper/2112.12986/) (2021)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)
- [Distributionally Robust Multilingual Machine Translation](https://mlsanity.com/paper/2109.04020/) (2021)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [Boosted CVaR Classification](https://mlsanity.com/paper/2110.13948/) (2021)

## Built on by (most cited first, 14 of 14)

- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2302.09267/) (2023)
- [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise](https://mlsanity.com/paper/2602.21039/) (2026)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization](https://mlsanity.com/paper/2605.05660/) (2026)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)
- [Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression](https://mlsanity.com/paper/2609.36610/) (2026)

## 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.