Nested Stochastic Gradient Descent for Sinkhorn Distance-Regularized Distributionally Robust Optimization
Yufeng Yang, Yi Zhou, Zhaosong Lu · 2025
Read Nested Stochastic Gradient Descent for Sinkhorn Distance-Regularized Distributionally Robust Optimization by Yufeng Yang, Yi Zhou, Zhaosong Lu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22923.txt.
Introduction
Yang, Zhou, and Lu present an algorithm for robust optimization under data shift in twenty twenty-five. Robust optimization trains models that hold up when data patterns change. The uncertainty set here is defined by a generalized Sinkhorn distance between distributions. The loss can be nonconvex and even unbounded, which makes the problem hard.
The authors derive a dual form of the problem as nested stochastic optimization. In that form, the dual variable depends on each data sample. Their nested stochastic gradient method estimates the nested gradients by stochastic approximation. They prove polynomial bounds on iterations and samples that do not grow with data size or dimension. Numeric tests show the method is efficient and robust. The work targets large scale robust learning problems.
Catalog record
| CREATOR | Yufeng Yang, Yi Zhou, Zhaosong Lu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22923
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nested Stochastic Gradient Descent for Sinkhorn Distance-Regularized Distributionally Robust Optimization Yufeng Yang, Yi Zhou, Zhaosong Lu Abstract 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 programming, 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. 1 Introduction In classic machine learning, the primary goal is to achieve good predictive performance in the test set after training the model on a designated training set. The training problem is typically formulated as an empirical risk minimization (ERM) problem. However, empirical risk minimization assumes that the training set and the test set follow the same underlying data distribution, which is often unrealistic and may result in poor test performance when data distribution shift exists. Data distribution shift is prevalent in real-world scenarios. It can be caused by many factors such as sampling bias, presence of anomalies, data merging and change of measurements, etc. To tackle this challenge, distributionally robust optimization (DRO) ( Herbert 1957 ) was proposed, which formulates the objective function as a min-max problem. DRO aims to learn a robust model by minimizing the expected risk over the worst-case data distribution within a predefined ambiguity set. This formulation offers a principled framework to learn the optimal resilient solution in the face of distribution uncertainty. One key factor in DRO is the selection of an appropriate divergence measure for modeling the ambiguity set. Specifically, the divergence measure should not only be computationally tractable but also yield a solution that avoids excessive conservatism. In the existing literature, various divergence-based ambiguity sets have been studied. In ( Pflug & Wozabal 2007 ; Wozabal 2012 ; Shafieezadeh Abadeh et al. 2015 ; Esfahani & Kuhn 2018 ; Gao & Kleywegt 2023 ; Luo & Mehrotra 2019 ) , the authors focused on reformulating the expressions of loss functions under the worst-case distributions into a tractable form and exploring possible algorithms to tackle DRO problems under Wasserstein-type ambiguity sets. For more information, we refer the readers to ( Kuhn et al. 2019 ) for a comprehensive survey on Wasserstein DRO. In ( Hu & Hong 2013 ; Bayraksan & Love 2015 ; Levy et al. 2020 ; Duchi & Namkoong 2020 ) , the authors analyzed alternative expressions of loss functions under the worst-case distribution and developed algorithms to solve DRO problems under Kullback–Leibler (KL) divergence-based and f -divergence-based ambiguity sets. However, the aforementioned divergence measures have certain limitations. For example, it is known that DRO with Wasserstein distance requires high computational complexity ( Pele & Werman 2009 ; Ba et al. 2010 ) . Also, both KL and f -divergence are not symmetric when assessing distributions. Furthermore, these two divergence measures require that the distributions share the same probability support, a strong condition that may fail to capture extreme distributions at certain points. See the Examples 3.1 and 3.2 for some concrete application examples. The Sinkhorn distance, first introduced in ( Cuturi 2013 ) , was designed to address the aforementioned limitations. Sinkhorn distance is symmetric and allows distributions from the same sample space to have different probability support. Furthermore, Sinkhorn distance is a convex function with respect to distributions, ensuring computation tractability and efficiency for large-scale problems. In ( Wang et al. 2023 ) , constrained Sinkhorn DRO was initially investigated. Specifically, they derived the equivalent formulation of constrained Sinkhorn DRO problem, which can be solved by the stochastic mirror descent algorithm. However, the convergence analysis conducted in their work assumed that the loss function is convex and bounded, which may not hold in practical modern machine learning applications. In this work, we develop and study dual formulations of Sinkhorn-distance regularized DRO problems (see formulation ( 1 )). The problem becomes nested contextual stochastic programming. Unlike traditional stochastic programming, our formulation makes dual decision variable dependent on data sample following distribution \mathbb{P} . Previous works ( Hu et al. 2023 ; Hu et al. 2024 ) treat such problem as contextual bi-level optimization problem and utilize multi-level monte-carlo (MLMC) methods to estimate objective’s hyper-gradient. However, we notice that such framework encounters significant limitations in our derived formulation ( 3 ). To elaborate, their contextual stochastic bi-level programming requires hessian information and inner loop to estimate inner objective’s minimizer using epoch SGD ( Hazan & Kale 2011 ) . The computing of hessian and MLMC significantly increase algorithmic complexity for our DRO problem especially when model parameters are high dimension. Additionally, the convergence analysis for solving contextual bi-level programming is established on strong-convexity of inner function, which is impractical for most scenarios. To tackle this challenge, we found the special relationship between outer problem’s gradient and inner problem’s gradient. (see Lemma 4.3 and Theorem 4.1 ). This enables us to use sample-average approximation (SAA) to estimate gradients, solve dual problem efficiently via Nested SGD algorithm (See Algorithm 2 ) and establish convergence analysis without additional assumptions including bounded, convex loss assumed in ( Wang et al. 2023 ) and strong convexity of inner function used in ( Hu et al. 2023 ) . Finally, we train several models including logistic regression and neural network over large-scale dataset, and conduct experiments to compare test performance of Sinkhorn DRO formulation with other baseline methods over perturbated test dataset. Our results demonstrate Sinkhorn DRO formulation ( 3 ) and proposed nested algorithm 2 successfully improve machine learning models’ robustness against distribution shift. 1.1 Summary of Contributions • We introduce a generalized Sinkhorn distance based on the class of f -divergence measures. This generalized notion not only retains the advantages of the original Sinkhorn distance but also allows to use a broader range of divergences to model the ambiguity set. • We derive an equivalent dual formulation of the regularized Sinkhorn DRO problem with strong duality guarantee. The dual problem takes the novel form of contextual nested stochastic programming, where the variable for inner stochastic programming is dependent on the data sample. • To solve the contextual nested stochastic problem with nonconvex and unbounded loss, we design a practical Nested-SGD algorithm with convergence guarantee under relaxed assumptions. Our Nested-SGD is specifically tailored for solving large-scale regularized Sinkhorn DRO problems. Experiments over large-scale dataset demonstrate our proposed formulation and algorithm improve various machine learning models’ robustness against distribution shift. 2 Related Work DRO. The DRO framework shares strong connections with contrastive learning ( Wu et al. 2023 ) , multiple instance learning