# Recursive Optimization of Convex Risk Measures: Mean-Semideviation Models

arXiv: https://arxiv.org/abs/1804.00636 · HTML: https://mlsanity.com/paper/1804.00636/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2018.

## Built on by (most cited first, 2 of 2)

- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Strong Duality Relations in Nonconvex Risk-Constrained Learning](https://mlsanity.com/paper/2312.01110/) (2023)

## Abstract (arXiv)

We develop recursive, data-driven, stochastic subgradient methods for optimizing a new, versatile, and application-driven class of convex risk measures, termed here as mean-semideviations, strictly generalizing the well-known and popular mean-upper-semideviation. We introduce the MESSAGEp algorithm, which is an efficient compositional subgradient procedure for iteratively solving convex mean-semideviation risk-averse problems to optimality. We analyze the asymptotic behavior of the MESSAGEp algorithm under a flexible and structure-exploiting set of problem assumptions. In particular: 1) Under appropriate stepsize rules, we establish pathwise convergence of the MESSAGEp algorithm in a strong technical sense, confirming its asymptotic consistency. 2) Assuming a strongly convex cost, we show that, for fixed semideviation order p>1 and for ε∈left[0,1right), the MESSAGEp algorithm achieves a squared-cal L2 solution suboptimality rate of the order of cal O(n-left(1-εright)/2) iterations, where, for ε>0, pathwise convergence is simultaneously guaranteed. This result establishes a rate of order arbitrarily close to cal O(n-1/2), while ensuring strongly stable pathwise operation. For pequiv1, the rate order improves to cal O(n-2/3), which also suffices for pathwise convergence, and matches previous results. 3) Likewise, in the general case of a convex cost, we show that, for any ε∈left[0,1right), the MESSAGEp algorithm with iterate smoothing achieves an cal L1 objective suboptimality rate of the order of cal O(n^-left(1-εright)/left(4bf1_left p>1right +4right)) iterations. This result provides maximal rates of cal O(n-1/4), if pequiv1, and cal O(n-1/8), if p>1, matching the state of the art, as well.