A Practical Online Method for Distributionally Deep Robust Optimization

Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, Tianbao Yang

Introduction

Training deep neural networks that are robust to noisy data or class imbalances remains a significant challenge. While Empirical Risk Minimization (ERM) is the standard paradigm, it assumes that the training distribution perfectly reflects the test environment. When this assumption fails—due to label noise or long-tailed data distributions—model performance degrades. Distributionally Robust Optimization (DRO) addresses this by optimizing for the worst-case distribution within a neighborhood of the empirical distribution. However, traditional DRO methods often suffer from high computational costs and memory overhead, making them impractical for large-scale deep learning.

In this work, researchers introduce COVER and RECOVER, the first practical online, "duality-free" methods for solving KL-regularized DRO. These methods achieve state-of-the-art convergence rates and significant training speedups by transforming the complex min-max DRO problem into a simpler stochastic compositional minimization problem.

The Compositional Shortcut

The core innovation lies in the mathematical reformulation of KL-regularized DRO. Traditionally, DRO is framed as a primal-dual min-max problem that requires maintaining a dual variable for every data point, leading to a memory cost of $O(n+d)$. For massive datasets or online streaming scenarios where $n$ is unknown or very large, this is prohibitive.

The authors demonstrate that this problem is equivalent to a stochastic compositional minimization problem: $\min_w f(\mathbb{E}[g(w)])$. This "duality-free" approach eliminates the need to store per-sample weights, reducing the memory cost to $O(d)$, identical to standard SGD.

Algorithms: COVER and RECOVER

To solve the resulting compositional problem, the authors propose two algorithms:

  1. COVER (Compositional Optimal VariancE Reduction): An online method utilizing a sophisticated variance reduction technique inspired by the STORM algorithm. It handles the inner and outer functions of the composition simultaneously using a polynomially decreasing step size.
  2. RECOVER: A practical, "restarted" version of COVER designed for deep learning workflows. It employs stagewise training, where the learning rate is decreased geometrically at specific intervals. This mirrors the standard training schedules used for models like ResNets.
The RECOVER algorithm, featuring a stagewise training approach.

Theoretical Comparison

The proposed methods offer significant theoretical advantages over existing baselines. As shown in the table below, COVER and RECOVER achieve optimal sample complexities while maintaining a memory cost independent of the dataset size $n$.

Comparison of COVER and RECOVER with existing DRO and compositional optimization algorithms.

Under the Polyak-Łojasiewicz (PL) condition—a common assumption in deep learning theory—RECOVER achieves a convergence rate of $O(1/\mu\epsilon)$, which is superior to previous primal-dual methods that scale with $1/\mu^2\epsilon$.

Empirical Results

The researchers evaluated COVER and RECOVER on several computer vision benchmarks, including artificially imbalanced versions of STL10, CIFAR10, and CIFAR100, as well as the naturally imbalanced iNaturalist2019 dataset (~265,000 images).

  • Efficiency: On iNaturalist, RECOVER was more than 2x faster than traditional primal-dual baselines, saving days of GPU training time.
  • Performance: DRO via RECOVER consistently outperformed standard ERM on imbalanced datasets. For instance, on highly imbalanced CIFAR10, RECOVER achieved higher test accuracy with significantly lower variance.
  • Stability: Unlike some compositional baselines (e.g., ASC-PG) that exhibited unstable convergence, RECOVER remained robust throughout the training process.

Conclusion

By bypassing the need for high-dimensional dual variables, COVER and RECOVER make Distributionally Robust Optimization a viable tool for modern, large-scale deep learning. The transition from a primal-dual framework to a duality-free compositional framework allows for significant gains in both memory efficiency and training speed without sacrificing theoretical guarantees. Future work aims to extend these duality-free techniques to DRO problems with hard constraints beyond KL-regularization.

Summary updated

BibTeX
@inproceedings{qi2021practical,
  author = {Qi Qi and Zhishuai Guo and Yi Xu and Rong Jin and Tianbao Yang},
  title = {{A Practical Online Method for Distributionally Deep Robust Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=VlQNa6n479n},
}
Figure