Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis
This work addresses the problem of robust model learning under distribution shift for machine learning practitioners, offering theoretical guarantees for non-convex settings, though it is incremental as it builds on existing DRO methods.
The paper tackles the challenge of optimizing distributionally robust objectives for general smooth non-convex losses, proving that a mini-batch normalized gradient descent with momentum algorithm finds an ε first-order stationary point within O(ε^{-4}) gradient complexity.
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 $ε$ first-order stationary point within $O( ε^{-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.