# Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 74 references that are in the map.
- First posted on arXiv 29 Mar 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (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)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [Recovering Best Statistical Guarantees via the Empirical Divergence-based Distributionally Robust Optimization](https://mlsanity.com/paper/1605.09349/) (2016)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Understanding Contrastive Learning via Distributionally Robust Optimization](https://mlsanity.com/paper/2310.11048/) (2023)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)

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

- [Distributionally Robust Optimization via Diffusion Ambiguity Modeling](https://mlsanity.com/paper/2510.22757/) (2025)
- [Distributionally Robust Optimization via Generative Ambiguity Modeling](https://mlsanity.com/paper/2602.08976/) (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) is a powerful technique to train robust models against data distribution shift. This paper aims to solve regularized nonconvex DRO problems, where the uncertainty set is modeled by a so-called generalized Sinkhorn distance and the loss function is nonconvex and possibly unbounded. Such a distance allows to model uncertainty of distributions with different probability supports and divergence functions. For this class of regularized DRO problems, we derive a novel dual formulation taking the form of nested stochastic optimization, where the dual variable depends on the data sample. To solve the dual problem, we provide theoretical evidence to design a nested stochastic gradient descent (SGD) algorithm, which leverages stochastic approximation to estimate the nested stochastic gradients. We study the convergence rate of nested SGD and establish polynomial iteration and sample complexities that are independent of the data size and parameter dimension, indicating its potential for solving large-scale DRO problems. We conduct numerical experiments to demonstrate the efficiency and robustness of the proposed algorithm.