Abstract
Conditional Value-at-Risk ($\mathrm{CV@R}$) is one of the most popularmeasures of risk, which has been recently considered as a performance criterionin supervised statistical learning, as it is related to desirable operationalfeatures in modern applications, such as safety, fairness, distributionalrobustness, and prediction error stability. However, due to its variationaldefinition, $\mathrm{CV@R}$ is commonly believed to result in difficultoptimization problems, even for smooth and strongly convex loss functions. Wedisprove this statement by establishing noisy (i.e., fixed-accuracy) linearconvergence of stochastic gradient descent for sequential $\mathrm{CV@R}$learning, for a large class of not necessarily strongly-convex (or even convex)loss functions satisfying a set-restricted Polyak-Lojasiewicz inequality. Thisclass contains all smooth and strongly convex losses, confirming that classicalproblems, such as linear least squares regression, can be solved efficientlyunder the $\mathrm{CV@R}$ criterion, just as their risk-neutral versions. Ourresults are illustrated numerically on such a risk-aware ridge regression task,also verifying their validity in practice.