Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis

Jikai Jin, Bohang Zhang, Haiyang Wang, Liwei Wang

Executive Summary

Distributionally Robust Optimization (DRO) is a powerful tool for building machine learning models that resist distribution shifts. However, it is notoriously difficult to optimize when using non-convex models like deep neural networks. This paper provides the first non-asymptotic convergence analysis for non-convex DRO, proving that a specific algorithm—mini-batch normalized SGD with momentum—can find stationary points with the same $\mathcal{O}(\epsilon^{-4})$ complexity as standard smooth optimization, even when the objective is non-smooth and exhibits unbounded gradient noise.

The Challenge of Non-Convex DRO

In classical machine learning, a core assumption is that training and test data are drawn from the same distribution. In real-world deployments, this assumption frequently fails due to distribution shifts, class imbalances, or adversarial attacks. Distributionally Robust Optimization (DRO) addresses this vulnerability by minimizing the "worst-case" loss over a set of potential distributions situated near the training data.

Despite its utility, a major theoretical gap exists. While DRO is well-understood for convex problems, most modern AI applications rely on non-convex loss functions (e.g., deep learning). In these scenarios, the DRO objective becomes a mathematical nightmare: it is often non-convex, non-smooth, and its stochastic gradients can exhibit "exploding" variance (unbounded noise). Consequently, standard optimization tools like vanilla Stochastic Gradient Descent (SGD) often struggle or fail to converge entirely.

Methodology: Taming the DRO Objective

To bridge this gap, the authors analyze the penalized DRO problem using $\psi$-divergence, a general family of distance measures between probability distributions.

Common $\psi$-divergences and their conjugate functions used in the DRO framework.

The primary contribution of this work is the rigorous analysis of Mini-batch Normalized SGD with Momentum. The authors identify two critical properties of the DRO objective that this algorithm successfully navigates:

  1. Generalized Smoothness: While the objective isn't "smooth" in the traditional sense, its smoothness can be bounded by the norm of its own gradient.
  2. Gradient-Dependent Noise: The variance of the stochastic gradient is not constant; rather, it grows proportionally as the gradient itself grows.

To solve these issues, the algorithm employs normalization (dividing the update step by its norm) to prevent the optimizer from overshooting in non-smooth regions. It pairs this with momentum and mini-batches to effectively suppress the massive gradient noise.

Furthermore, for the popular but non-differentiable Conditional Value-at-Risk (CVaR) metric, the authors propose a new smoothed CVaR divergence. This innovation allows for simpler optimization while maintaining the desired robustness.

Empirical Evaluation

The authors evaluated their approach on two main tasks designed to highlight the need for robustness:

  • AFAD-Full: A facial image dataset used for age regression. It is naturally imbalanced (most faces are between ages 18 and 30), making it a prime candidate for DRO.
  • Imbalanced CIFAR-10: The standard image classification dataset, modified by randomly sub-sampling categories at different ratios to create artificial class imbalance.

Key Insights and Main Results

  • Theoretical Parity: The authors proved that their algorithm achieves a gradient complexity of $\mathcal{O}(\epsilon^{-4})$. This is a significant milestone because it matches the best possible rate for standard smooth non-convex optimization, demonstrating that DRO does not have to be theoretically "slower" than standard training.
  • The "Adam" Connection: The proposed algorithm (normalization + momentum) is structurally similar to popular adaptive optimizers like Adam. This research provides a theoretical hint as to why Adam performs so well on complex, ill-conditioned landscapes where vanilla SGD fails.
  • Faster Convergence: In regression tests on the AFAD dataset, vanilla SGD failed to converge even after 100 epochs. In contrast, the normalized momentum algorithm converged in roughly 25 epochs.
  • Improved Fairness: On the imbalanced CIFAR-10 task, the proposed method significantly boosted the accuracy of the "worst-performing" class (the minority group) from 44.8% to 49.8% compared to standard momentum SGD.

Limitations and Future Directions

While groundbreaking, the study notes a few limitations. The complexity bounds still depend on constants like the Lipschitz constant ($G$) and the penalty coefficient ($\lambda$). Future work could explore how to make these bounds tighter or more independent of problem-specific parameters.

Additionally, the current analysis focuses on divergences with smooth "conjugate functions." Some popular choices, like standard KL-divergence, do not perfectly fit this mold or may be non-continuous, leaving room for broader theoretical generalizations. Finally, testing these specialized DRO algorithms on massive-scale models, such as Transformers, remains an open area for empirical validation.

Summary updated

Abstract

Distributionally robust optimization (DRO) is a widely-used approach to learn models that are robust against distribution shift. Compared with the standard optimization setting, the objective function in DRO is more difficult to optimize, and most of the existing theoretical results make strong assumptions on the loss function. In this work we bridge the gap by studying DRO algorithms for general smooth non-convex losses. By carefully exploiting the specific form of the DRO objective, we are able to provide non-asymptotic convergence guarantees even though the objective function is possibly non-convex, non-smooth and has unbounded gradient noise. In particular, we prove that a special algorithm called the mini-batch normalized gradient descent with momentum, can find an $\epsilon$-first-order stationary point within $\mathcal O(\epsilon^{-4})$ gradient complexity. We also discuss the conditional value-at-risk (CVaR) setting, where we propose a penalized DRO objective based on a smoothed version of the CVaR that allows us to obtain a similar convergence guarantee. We finally verify our theoretical results in a number of tasks and find that the proposed algorithm can consistently achieve prominent acceleration.
BibTeX
@inproceedings{jin2021non,
  author = {Jikai Jin and Bohang Zhang and Haiyang Wang and Liwei Wang},
  title = {{Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Vf205Ib19Vk},
}
Figure