We propose and analyze algorithms for distributionally robust optimization of
convex losses with conditional value at risk (CVaR) and $\chi^2$ divergence
uncertainty sets. We prove that our algorithms require a number of gradient
evaluations independent of training set size and number of parameters, making
them suitable for large-scale applications. For $\chi^2$ uncertainty sets these
are the first such guarantees in the literature, and for CVaR our guarantees
scale linearly in the uncertainty level rather than quadratically as in
previous work. We also provide lower bounds proving the worst-case optimality
of our algorithms for CVaR and a penalized version of the $\chi^2$ problem. Our
primary technical contributions are novel bounds on the bias of batch robust
risk estimation and the variance of a multilevel Monte Carlo gradient estimator
due to [Blanchet & Glynn, 2015]. Experiments on MNIST and ImageNet confirm the
theoretical scaling of our algorithms, which are 9--36 times more efficient
than full-batch methods.

该文主要研究了基于 CVaR 和 chi-squared 分布的鲁棒优化问题，并提出了一种新的算法以及相应的优化方案。研究结果表明，该算法不仅适用于大规模应用，而且在实验中的效率比全样本方法高 9~36 倍。

分布鲁棒优化的大规模方法

Large-Scale Methods for Distributionally Robust Optimization

We study sampling from a target distribution $\nu_* = e^{-f}$ using the
unadjusted Langevin Monte Carlo (LMC) algorithm when the potential $f$
satisfies a strong dissipativity condition and it is first-order smooth with a
Lipschitz gradient. We prove that, initialized with a Gaussian random vector
that has sufficiently small variance, iterating the LMC algorithm for
$\widetilde{\mathcal{O}}(\lambda^2 d\epsilon^{-1})$ steps is sufficient to
reach $\epsilon$-neighborhood of the target in both Chi-squared and Renyi
divergence, where $\lambda$ is the logarithmic Sobolev constant of $\nu_*$. Our
results do not require warm-start to deal with the exponential dimension
dependency in Chi-squared divergence at initialization. In particular, for
strongly convex and first-order smooth potentials, we show that the LMC
algorithm achieves the rate estimate $\widetilde{\mathcal{O}}(d\epsilon^{-1})$
which improves the previously known rates in both of these metrics, under the
same assumptions. Translating this rate to other metrics, our results also
recover the state-of-the-art rate estimates in KL divergence, total variation
and $2$-Wasserstein distance in the same setup. Finally, as we rely on the
logarithmic Sobolev inequality, our framework covers a range of non-convex
potentials that are first-order smooth and exhibit strong convexity outside of
a compact region.

研究采用未校准 Langevin Monte Carlo 算法从目标分布采样当势能满足强弛散条件、具有 Lipschitz 梯度和首阶平滑性，证明其在 Chi-squared divergence 和 Renyi divergence 下，迭代一定步数后可保证达到目标的 ε 邻域。

Langevin 蒙特卡罗在 Chi-Squared 和 Renyi 分歧中的收敛

Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence

Stein Variational Gradient Descent (SVGD), a popular sampling algorithm, is
often described as the kernelized gradient flow for the Kullback-Leibler
divergence in the geometry of optimal transport. We introduce a new perspective
on SVGD that instead views SVGD as the (kernelized) gradient flow of the
chi-squared divergence which, we show, exhibits a strong form of uniform
exponential ergodicity under conditions as weak as a Poincar\'e inequality.
This perspective leads us to propose an alternative to SVGD, called Laplacian
Adjusted Wasserstein Gradient Descent (LAWGD), that can be implemented from the
spectral decomposition of the Laplacian operator associated with the target
density. We show that LAWGD exhibits strong convergence guarantees and good
practical performance.

本论文介绍了 Stein Variational Gradient Descent (SVGD) 算法的一种新视角，将 SVGD 视为卡方散度的（核化）梯度流，提出了一种基于目标密度关联的拉普拉斯算子的谱分解实现的替代方法，称为 Laplacian Adjusted Wasserstein Gradient Descent (LAWGD)，这种方法表现出强大的收敛保证和良好的实际性能。