Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences

Hongseok Namkoong, John C. DuchiNeurIPS 2016 · OpenReview

TL;DR

This paper introduces a highly efficient way to solve Distributionally Robust Optimization (DRO) problems using stochastic gradient methods. By framing the problem as a two-player game and utilizing clever data structures, the authors achieve a per-iteration complexity of $O(\log n)$, making robust optimization nearly as computationally cheap as standard Stochastic Gradient Descent (SGD).

The Fragility of Standard ERM

In standard Empirical Risk Minimization (ERM), models are trained to perform well on the average of the training data. However, this approach can be fragile: it fails to account for potential shifts in data distribution or the inherent variance of the loss.

Distributionally Robust Optimization (DRO) offers a solution by considering a "worst-case" scenario. Instead of minimizing average loss, it minimizes the maximum loss over a set of distributions (an "uncertainty set") near the observed empirical distribution. While DRO provides better statistical guarantees and "calibrated" confidence intervals, it has historically been much harder to solve than ERM. Previous attempts to use standard SGD on the dual form of these problems often failed because the gradients became too volatile, leading to exploding variance.

A Minimax Approach to Robustness

The authors treat the DRO problem as a two-player minimax game:

  1. The $x$-player (the model) tries to minimize the loss.
  2. The $p$-player (the adversary) tries to maximize the loss by reweighting the importance of training samples, staying within a certain "distance" (defined by $f$-divergences) from the uniform distribution.

Key Innovations

  • Bandit Mirror Descent: The authors propose a "Bandit Mirror Descent" algorithm. Instead of updating all $n$ weights for the $p$-player every time, they use a stochastic estimate based on a single sampled index.
  • Efficient $p$-updates via BSTs: For the specific case of $\chi^2$-divergence, the projection step for the adversary would normally take $O(n)$ time. The authors developed a specialized Balanced Binary Search Tree (BST) data structure that stores sums of weights and their powers, allowing this update to happen in just $O(\log n)$ time.
  • Cressie-Read Divergences: They provide a unified theoretical framework for a broad family of divergences (including KL-divergence and $\chi^2$), proving that their method achieves "sublinear regret"—meaning it converges to the optimal robust solution quickly.

Key Insights and Results

The authors evaluated their method on three primary benchmarks: a controlled synthetic dataset ($n=2000$), the Adult dataset ($n \approx 32k$), and the large-scale Reuters RCV1 Corpus ($n \approx 724k$).

Speed and Scalability

The most significant takeaway is that robustness doesn't have to be computationally prohibitive. With the $O(\log n)$ update, the overhead of being "distributionally robust" is negligible compared to standard training.

Convergence comparison on Synthetic and Reuters datasets

On the Reuters dataset, the proposed "bandit-minimax" algorithm reached a near-optimal solution significantly faster than standard Gradient Descent (GD). Furthermore, while Interior Point Methods (IPM) provide very accurate solutions on small datasets, they fail to scale to the hundreds of thousands of examples found in the Reuters dataset. The proposed method handled these scales easily.

Statistical Validity and Variance Regularization

The paper reinforces the idea that DRO is essentially a form of variance-based regularization. By focusing on the "worst-case" distribution, the model naturally penalizes solutions with high variance across samples, leading to more stable performance.

Loss and error comparisons showing the robust upper bound

Experiments confirmed that the robust objective provides a valid upper bound (a "certificate") on the true test-set risk. As seen in the loss and error plots above, the supremum bound (green line) reliably upper-bounds the test performance, whereas standard ERM often underestimates the risk.

Limitations and Future Work

  • Specific Divergences: While the theory covers many $f$-divergences, the highly optimized $O(\log n)$ data structure is specifically tailored for the $\chi^2$-divergence. Other divergences might require different specialized structures to achieve the same efficiency.
  • Compact Convex Sets: The theory assumes the parameter space $\mathcal{X}$ is a compact convex set. Extending this efficiently to non-convex settings (like deep neural networks) is a natural next step, though the theoretical guarantees would change.
  • Hyperparameter Sensitivity: The robustness parameter $\rho$ (the size of the uncertainty set) still needs to be chosen. While the paper links it to confidence levels, in practice, tuning $\rho$ remains a critical step for optimal performance.

Summary updated

Abstract

We develop efficient solution methods for a robust empirical risk minimization problem designed to give calibrated confidence intervals on performance and provide optimal tradeoffs between bias and variance. Our methods apply to distributionally robust optimization problems proposed by Ben-Tal et al., which put more weight on observations inducing high loss via a worst-case approach over a non-parametric uncertainty set on the underlying data distribution. Our algorithm solves the resulting minimax problems with nearly the same computational cost of stochastic gradient descent through the use of several carefully designed data structures. For a sample of size n, the per-iteration cost of our method scales as O(log n), which allows us to give optimality certificates that distributionally robust optimization provides at little extra cost compared to empirical risk minimization and stochastic gradient methods.
BibTeX
@inproceedings{namkoong2016stochastic,
  author = {Hongseok Namkoong and John C. Duchi},
  title = {{Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=S1ELgFWuWr},
}
Figure