Noisy Linear Convergence of Stochastic Gradient Descent for CV@R Statistical Learning under Polyak-Łojasiewicz Conditions

Abstract

Conditional Value-at-Risk ($CV@R$) is one of the most popular measures of risk, which has been recently considered as a performance criterion in supervised statistical learning, as it is related to desirable operational features in modern applications, such as safety, fairness, distributional robustness, and prediction error stability. However, due to its variational definition, $CV@R$ is commonly believed to result in difficult optimization problems, even for smooth and strongly convex loss functions. We disprove this statement by establishing noisy (i.e., fixed-accuracy) linear convergence of stochastic gradient descent for sequential $CV@R$ learning, for a large class of not necessarily strongly-convex (or even convex) loss functions satisfying a set-restricted Polyak-Lojasiewicz inequality. This class contains all smooth and strongly convex losses, confirming that classical problems, such as linear least squares regression, can be solved efficiently under the $CV@R$ criterion, just as their risk-neutral versions. Our results are illustrated numerically on such a risk-aware ridge regression task, also verifying their validity in practice.

arXiv comment17 pages, 2 figures. From v2 onwards: Significant updates to the technical content, fixed some errors/nonsense in the results and their proofs

References in corpus (10)

• Fairness risk measures
• Statistical Learning with Conditional Value at Risk
• Risk-Averse Stochastic Convex Bandit
• An Approximation Algorithm for Risk-averse Submodular Optimization
• Recursive Optimization of Convex Risk Measures: Mean-Semideviation Models
• Learning Bounds for Risk-sensitive Learning
• PAC-Bayesian Bound for the Conditional Value at Risk
• Adaptive Sampling for Stochastic Risk-Averse Learning
• Bi-directional Value Learning for Risk-aware Planning Under Uncertainty: Extended Version
• A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning

Cited by in corpus (1)

• Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis