提出新型嵌套随机算法，高效求解带广义Sinkhorn距离的鲁棒优化问题。
Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimization
- 将复杂优化转化为嵌套随机学习形式，双层变量依赖数据样本。
- 收敛速度多项式，迭代与采样复杂度与数据规模无关。
- 适合大规模分布外鲁棒训练，尤其适用于支持集不同的分布场景。
分布鲁棒优化（DRO）是应对数据分布偏移的有效方法。本文针对一类正则化的非凸DRO问题展开研究，其中不确定性集合由广义Sinkhorn距离建模，损失函数为非凸且可能无界。该距离能刻画具有不同概率支撑和散度函数的分布间的不确定性。针对此类问题，我们推导出一种新颖的对偶形式，表现为嵌套随机优化，其对偶变量依赖于数据样本。为求解该对偶问题，我们提供理论依据，设计了一种嵌套随机梯度下降（SGD）算法，利用随机近似估计嵌套梯度。我们分析了嵌套SGD的收敛速率，建立了与数据规模和参数维度无关的多项式迭代与样本复杂度，表明其在求解大规模DRO问题上的潜力。数值实验验证了所提算法的效率与鲁棒性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。