Mean–semideviation–based distributionally robust learning with weakly convex losses: convergence rates and finite-sample guarantees
将均值-半偏差风险度量的分布鲁棒优化转化为两层随机优化问题，提出单时间尺度算法，证明样本复杂度为O(ε^{-3})，并通过深度学习与非光滑回归示例验证性能。
Abstract We consider a distributionally robust stochastic optimization problem where the ambiguity sets are implicitly defined by the dual representation of the mean–semideviation risk measure. Utilizing the specific form of this risk measure, we reformulate the problem as a stochastic two-level composition optimization problem. In this setting, we consider a single time-scale algorithm, involving two versions of the inner function value tracking: linearized tracking of a continuously differentiable loss function with Lipschitz gradients, and SPIDER tracking of a weakly convex loss function. We adopt the squared norm of the gradient of the Moreau envelope as our measure of stationarity and show that the sample complexity of $$\mathscr {O}(\varepsilon ^{-3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is possible in both cases, with only the constant larger in the second case. Finally, we demonstrate the performance of our algorithm with a deep learning example and a weakly convex, non-smooth regression example.