Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis

Abstract

Distributionally robust optimization (DRO) is a widely-used approach to learn models that are robust against distribution shift. Compared with the standard optimization setting, the objective function in DRO is more difficult to optimize, and most of the existing theoretical results make strong assumptions on the loss function. In this work we bridge the gap by studying DRO algorithms for general smooth non-convex losses. By carefully exploiting the specific form of the DRO objective, we are able to provide non-asymptotic convergence guarantees even though the objective function is possibly non-convex, non-smooth and has unbounded gradient noise. In particular, we prove that a special algorithm called the mini-batch normalized gradient descent with momentum, can find an $\epsilon$ first-order stationary point within $O({\epsilon }^{-4})$ gradient complexity. We also discuss the conditional value-at-risk (CVaR) setting, where we propose a penalized DRO objective based on a smoothed version of the CVaR that allows us to obtain a similar convergence guarantee. We finally verify our theoretical results in a number of tasks and find that the proposed algorithm can consistently achieve prominent acceleration.

arXiv comment25 pages; to appear in NeurIPS 2021

References in corpus (6)

• Does Distributionally Robust Supervised Learning Give Robust Classifiers?
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Remix: Rebalanced Mixup
• Statistical Learning with Conditional Value at Risk
• A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning
• Noisy Linear Convergence of Stochastic Gradient Descent for CV@R Statistical Learning under Polyak-Łojasiewicz Conditions