Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis

2021/10/24 by Jikai Jin, Jin, Jikai, Bohang Zhang +5 · 6 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.2110.12459

25 pages; to appear in NeurIPS 2021

openalex publication_date 2021/10/24 · arxiv created 2021/10/26 · arxiv updated 2021/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ε 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.

Citations

• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

Cited by

• Multi-Task GRPO: Reliable LLM Reasoning Across Tasks
• Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis
• Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
• Simple Convergence Proof of Adam From a Sign-like Descent Perspective
• Decentralized Min-Max Optimization with Gradient Tracking
• An Efficient Stochastic First-Order Algorithm for Nonconvex--Strongly Concave Minimax Optimization beyond Lipschitz Smoothness

Related

• Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization
• Distributionally Robust Learning with Weakly Convex Losses: Convergence Rates and Finite-Sample Guarantees
• Large-Scale Methods for Distributionally Robust Optimization
• Distributionally Robust Optimization with Bias and Variance Reduction
• Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees