# Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 33 references that are in the map.
- First posted on arXiv 24 Oct 2021.

## Builds on (most cited first, 21 of 21)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Remix: Rebalanced Mixup](https://mlsanity.com/paper/2007.03943/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Coping with Label Shift via Distributionally Robust Optimisation](https://mlsanity.com/paper/2010.12230/) (2020)
- [Why are Adaptive Methods Good for Attention Models?](https://mlsanity.com/paper/1912.03194/) (2019)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [Statistical Learning with Conditional Value at Risk](https://mlsanity.com/paper/2002.05826/) (2020)
- [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020)
- [Noisy Linear Convergence of Stochastic Gradient Descent for CV@R Statistical Learning under Polyak-Lojasiewicz Conditions](https://mlsanity.com/paper/2012.07785/) (2020)
- [A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning](https://mlsanity.com/paper/2006.04873/) (2020)

## Built on by (most cited first, 30 of 39)

- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [CAGroup3D: Class-Aware Grouping for 3D Object Detection on Point Clouds](https://mlsanity.com/paper/2210.04264/) (2022)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [RBGNet: Ray-based Grouping for 3D Object Detection](https://mlsanity.com/paper/2204.02251/) (2022)
- [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022)
- [Provable Adaptivity of Adam under Non-uniform Smoothness](https://mlsanity.com/paper/2208.09900/) (2022)
- [Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization](https://mlsanity.com/paper/2305.11965/) (2023)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Distributionally Robust Bayesian Optimization with varphi-divergences](https://mlsanity.com/paper/2203.02128/) (2022)
- [Stochastic Constrained DRO with a Complexity Independent of Sample Size](https://mlsanity.com/paper/2210.05740/) (2022)
- [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond](https://mlsanity.com/paper/2403.15146/) (2024)
- [Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance](https://mlsanity.com/paper/2404.01436/) (2024)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2302.07155/) (2023)
- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)
- [MGDA Converges under Generalized Smoothness, Provably](https://mlsanity.com/paper/2405.19440/) (2024)
- [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Non-Uniform Smoothness for Gradient Descent](https://mlsanity.com/paper/2311.08615/) (2023)
- [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization](https://mlsanity.com/paper/2410.14054/) (2024)
- [Error Feedback under (L0,L1)-Smoothness: Normalization and Momentum](https://mlsanity.com/paper/2410.16871/) (2024)
- [Simple Convergence Proof of Adam From a Sign-like Descent Perspective](https://mlsanity.com/paper/2507.05966/) (2025)
- [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022)

## Abstract (arXiv)

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 ε first-order stationary point within O( ε-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.