# An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

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

- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022)
- [Stochastic Constrained DRO with a Complexity Independent of Sample Size](https://mlsanity.com/paper/2210.05740/) (2022)
- [Upweighting Easy Samples in Fine-Tuning Mitigates Forgetting](https://mlsanity.com/paper/2502.02797/) (2025)
- [Dynamic Loss-Based Sample Reweighting for Improved Large Language Model Pretraining](https://mlsanity.com/paper/2502.06733/) (2025)
- [Distributed Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2210.07588/) (2022)
- [Take the Bull by the Horns: Hard Sample-Reweighted Continual Training Improves LLM Generalization](https://mlsanity.com/paper/2402.14270/) (2024)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [On the Benefits of Over-parameterization for Out-of-Distribution Generalization](https://mlsanity.com/paper/2403.17592/) (2024)
- [Learning Unnormalized Statistical Models via Compositional Optimization](https://mlsanity.com/paper/2306.07485/) (2023)
- [Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimization](https://mlsanity.com/paper/2306.09222/) (2023)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)
- [Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2302.09267/) (2023)
- [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023)
- [GRAPE: Optimize Data Mixture for Group Robust Multi-target Adaptive Pretraining](https://mlsanity.com/paper/2505.20380/) (2025)
- [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)
- [Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees](https://mlsanity.com/paper/2205.15624/) (2022)
- [Doubly Robust Instance-Reweighted Adversarial Training](https://mlsanity.com/paper/2308.00311/) (2023)
- [Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization](https://mlsanity.com/paper/2308.09604/) (2023)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024)
- [Towards Fair Class-wise Robustness: Class Optimal Distribution Adversarial Training](https://mlsanity.com/paper/2501.04527/) (2025)
- [Safe Collaborative Filtering](https://mlsanity.com/paper/2306.05292/) (2023)

## Abstract (arXiv)

In this paper, we propose a practical online method for solving a class of distributionally robust optimization (DRO) with non-convex objectives, which has important applications in machine learning for improving the robustness of neural networks. In the literature, most methods for solving DRO are based on stochastic primal-dual methods. However, primal-dual methods for DRO suffer from several drawbacks: (1) manipulating a high-dimensional dual variable corresponding to the size of data is time expensive; (2) they are not friendly to online learning where data is coming sequentially. To address these issues, we consider a class of DRO with an KL divergence regularization on the dual variables, transform the min-max problem into a compositional minimization problem, and propose practical duality-free online stochastic methods without requiring a large mini-batch size. We establish the state-of-the-art complexities of the proposed methods with and without a Polyak-L ojasiewicz (PL) condition of the objective. Empirical studies on large-scale deep learning tasks (i) demonstrate that our method can speed up the training by more than 2 times than baseline methods and save days of training time on a large-scale dataset with ~ 265K images, and (ii) verify the supreme performance of DRO over Empirical Risk Minimization (ERM) on imbalanced datasets. Of independent interest, the proposed method can be also used for solving a family of stochastic compositional problems with state-of-the-art complexities.