mlsanityData to 14 Oct 2026

Stochastic Constrained DRO with a Complexity Independent of Sample Size

arXiv 2210.05740 ↗First posted 11 Oct 2022cs.LG cs.AI math.OCcited by 16

Not on the map. Why?

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.

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

37 of 75 references.

References · 37

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  2. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 12,049
  3. 2015Distilling the Knowledge in a Neural Networkcited by 10,324
  4. 2021Convex optimizationcited by 2,515
  5. 2021Align before Fuse: Vision and Language Representation Learning with Momentum Distillationcited by 1,619
  6. 2019Decoupling Representation and Classifier for Long-Tailed Recognitioncited by 809
  7. 2019Large-Scale Long-Tailed Recognition in an Open Worldcited by 705
  8. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  9. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  10. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  11. 2016Statistics of Robust Optimization: A Generalized Empirical Likelihood Approachcited by 183
  12. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
25 more
  1. 2016Variance-based regularization with convex objectivescited by 155
  2. 2022CyCLIP: Cyclic Contrastive Language-Image Pretrainingcited by 127
  3. 2020Tilted Empirical Risk Minimizationcited by 106
  4. 2021Distributionally Robust Federated Averagingcited by 104
  5. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 95
  6. 2013Data-Driven Robust Optimizationcited by 85
  7. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  8. 2019Distributionally Robust Optimization and Generalization in Kernel Methodscited by 73
  9. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  10. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  11. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
  12. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 43
  13. 2022Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performancecited by 43
  14. 2020An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectivescited by 42
  15. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
  16. 2021Sinkhorn Distributionally Robust Optimizationcited by 38
  17. 2019A Stochastic Composite Gradient Method with Incremental Variance Reductioncited by 26
  18. 2020Optimal Algorithms for Convex Nested Stochastic Composite Optimizationcited by 20
  19. 2019Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structurecited by 15
  20. 2019Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problemscited by 14
  21. 2019A Simple and Effective Framework for Pairwise Deep Metric Learningcited by 13
  22. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  23. 2014Convex Optimization in Juliacited by 9
  24. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6
  25. 2019Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 4; 2026: 3.

16 papers.

Sort:

By area:

  1. 2023Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualizationcited by 25
  2. 2024Adaptive Preference Scaling for Reinforcement Learning with Human Feedbackcited by 20
  3. 2024Take the Bull by the Horns: Hard Sample-Reweighted Continual Training Improves LLM Generalizationcited by 12
  4. 2024To Cool or not to Cool? Temperature Network Meets Large Foundation Models via DROcited by 11
  5. 2023Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimizationcited by 6
  6. 2024Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oraclescited by 5
  7. 2025Improved Stochastic Optimization of LogSumExpcited by 4
  8. 2024Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimizationcited by 3
  9. 2024Communication-Efficient Federated Group Distributionally Robust Optimizationcited by 3
  10. 2025Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimizationcited by 3
  11. 2023FedDRO: Federated Compositional Optimization for Distributionally Robust Learningcited by 1
  12. 2025Model Steering: Learning with a Reference Model Improves Generalization Bounds and Scaling Lawscited by 1
4 more
  1. 2025Understanding temperature tuning in energy-based modelscited by 1
  2. 2026A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimizationcited by 1
  3. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  4. 2026From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimizationcited by 0