# Stochastic Constrained DRO with a Complexity Independent of Sample Size

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 75 references that are in the map.
- First posted on arXiv 11 Oct 2022.

## Builds on (most cited first, 30 of 37)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Align before Fuse: Vision and Language Representation Learning with Momentum Distillation](https://mlsanity.com/paper/2107.07651/) (2021)
- [Decoupling Representation and Classifier for Long-Tailed Recognition](https://mlsanity.com/paper/1910.09217/) (2019)
- [Large-Scale Long-Tailed Recognition in an Open World](https://mlsanity.com/paper/1904.05160/) (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)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [CyCLIP: Cyclic Contrastive Language-Image Pretraining](https://mlsanity.com/paper/2205.14459/) (2022)
- [Tilted Empirical Risk Minimization](https://mlsanity.com/paper/2007.01162/) (2020)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance](https://mlsanity.com/paper/2202.12387/) (2022)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)

## Built on by (most cited first, 16 of 16)

- [Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization](https://mlsanity.com/paper/2305.11965/) (2023)
- [Adaptive Preference Scaling for Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2406.02764/) (2024)
- [Take the Bull by the Horns: Hard Sample-Reweighted Continual Training Improves LLM Generalization](https://mlsanity.com/paper/2402.14270/) (2024)
- [To Cool or not to Cool? Temperature Network Meets Large Foundation Models via DRO](https://mlsanity.com/paper/2404.04575/) (2024)
- [Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimization](https://mlsanity.com/paper/2306.09222/) (2023)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Improved Stochastic Optimization of LogSumExp](https://mlsanity.com/paper/2509.24894/) (2025)
- [Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization](https://mlsanity.com/paper/2404.01200/) (2024)
- [Communication-Efficient Federated Group Distributionally Robust Optimization](https://mlsanity.com/paper/2410.06369/) (2024)
- [Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimization](https://mlsanity.com/paper/2503.22923/) (2025)
- [FedDRO: Federated Compositional Optimization for Distributionally Robust Learning](https://mlsanity.com/paper/2311.12652/) (2023)
- [Model Steering: Learning with a Reference Model Improves Generalization Bounds and Scaling Laws](https://mlsanity.com/paper/2505.06699/) (2025)
- [Understanding temperature tuning in energy-based models](https://mlsanity.com/paper/2512.09152/) (2025)
- [A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization](https://mlsanity.com/paper/2602.02877/) (2026)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)
- [From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization](https://mlsanity.com/paper/2605.05660/) (2026)

## Abstract (arXiv)

Distributionally Robust Optimization (DRO), as a popular method to train robust models against distribution shift between training and test sets, has received tremendous attention in recent years. In this paper, we propose and analyze stochastic algorithms that apply to both non-convex and convex losses for solving Kullback Leibler divergence constrained DRO problem. Compared with existing methods solving this problem, our stochastic algorithms not only enjoy competitive if not better complexity independent of sample size but also just require a constant batch size at every iteration, which is more practical for broad applications. We establish a nearly optimal complexity bound for finding an ε stationary solution for non-convex losses and an optimal complexity for finding an ε optimal solution for convex losses. Empirical studies demonstrate the effectiveness of the proposed algorithms for solving non-convex and convex constrained DRO problems.