Distributionally Robust Optimization via Ball Oracle Acceleration

Yair Carmon, Danielle Hausler

Introduction

Most machine learning models are trained using Empirical Risk Minimization (ERM), which minimizes the average loss across a dataset. While effective on average, ERM can fail spectacularly on minority groups or under "domain shift" (when test data differs from training data).

Distributionally Robust Optimization (DRO) offers a solution by minimizing the worst-case expected loss over a set of possible data distributions, known as the "uncertainty set." This approach yields models that are more robust and fair, but it comes with a heavy computational price. The "worst-case" requirement involves a "max" operator that makes the optimization objective non-smooth and difficult for standard algorithms to handle efficiently. For a dataset of size $N$, standard methods often require $O(N\epsilon^{-2})$ operations to find an $\epsilon$-accurate solution, which becomes prohibitively slow for high-precision demands.

This paper introduces a significantly faster way to solve DRO problems by combining a "ball optimization oracle" with advanced sampling techniques, achieving a theoretical speedup of up to $\epsilon^{-4/3}$ over previous state-of-the-art methods.

Methodology: Ball Oracle Acceleration

The authors tackle the computational complexity of DRO by leveraging Ball Oracle Acceleration. Instead of attempting to solve the global optimization problem all at once, the algorithm breaks it down into a series of smaller sub-problems: minimizing the objective within a small Euclidean ball around a query point.

The core technical innovations enabling this approach include:

  • Efficient Ball Oracles for Group DRO: Group DRO minimizes the maximum loss across $M$ pre-defined groups. To avoid the $O(M)$ cost of checking every group at every step, the authors utilize Multilevel Monte Carlo (MLMC). This acts as a "free" smoother, allowing the algorithm to produce an unbiased estimate of a smoothed "softmax" version of the objective in $O(1)$ time while keeping variance low.
  • Dual Stability for $f$-divergence DRO: For DRO where the uncertainty set is defined by $f$-divergences (such as KL-divergence or $\chi^2$), the authors work with the dual formulation. They introduce a small amount of entropy regularization to stabilize the gradient estimators, ensuring they do not explode when the optimization approaches the boundaries of the uncertainty set.
  • Acceleration Framework: These efficient local "ball" solvers are plugged into an acceleration framework—similar to Monteiro-Svaiter acceleration—that translates local progress into global convergence at a much faster rate. The "ball" itself acts as a crucial variance-control tool, restricting the optimization to a small radius so that stochastic gradient estimators remain stable.

Key Results and Complexity Improvements

As a purely theoretical paper focused on algorithmic complexity, the results are presented as mathematical bounds on the number of function evaluations required rather than empirical benchmarks. The primary achievement is a massive reduction in the theoretical iteration complexity for finding an $\epsilon$-suboptimal solution.

Comparison of iteration complexities for finding an $\epsilon$-accurate solution in DRO.

As shown in the complexity table above, the proposed method yields substantial improvements:

  • Non-smooth Losses: The authors achieve a complexity of $\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-2})$. Compared to the previous standard of $O(N\epsilon^{-2})$, this represents a massive speedup when $\epsilon$ is small. For instance, if $\epsilon = 0.01$, the improvement factor can be as large as 10,000x.
  • Weakly Smooth Losses: If the loss functions exhibit some degree of smoothness, the complexity improves even further to $\tilde{O}(N\epsilon^{-2/3} + \sqrt{N}\epsilon^{-1})$.

Furthermore, the authors argue that their rates are nearly optimal (up to logarithmic factors) for certain classes of DRO problems, suggesting it is unlikely that significantly faster algorithms exist for these specific formulations.

Limitations and Future Work

While theoretically groundbreaking, the paper outlines several challenges and avenues for future research:

  • Practical Implementation: The "bisection" procedure required by the acceleration framework is notoriously difficult to implement efficiently in practice. Making these algorithms "production-ready" remains a significant engineering challenge.
  • Parameter Tuning: The method relies on several hyperparameters, such as the ball radius and smoothing level, which are not known in advance and may require extensive tuning.
  • Unstructured Uncertainty: The current approach relies heavily on the specific mathematical structures of Group and $f$-divergence DRO. Extending these speedups to arbitrary or unstructured uncertainty sets is an open question.
  • Non-convexity: The theoretical guarantees assume convex loss functions. Extending these high-performance bounds to non-convex models, such as deep neural networks, represents a major frontier for future robust optimization research.

Summary updated

Abstract

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 $\epsilon$-accurate solution with $\widetilde{O}\left(N\epsilon^{-2/3} + \epsilon^{-2}\right)$ first-order oracle queries to individual loss functions. Compared to existing algorithms for this problem, we improve complexity by a factor of up to $\epsilon^{-4/3}$.
BibTeX
@inproceedings{carmon2022distributionally,
  author = {Yair Carmon and Danielle Hausler},
  title = {{Distributionally Robust Optimization via Ball Oracle Acceleration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=0ZKyTHwF5V1},
}
Figure