Recursive Optimization of Convex Risk Measures: Mean-Semideviation Models

Abstract

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 $\epsilon \in \left[0,1\right)$, the MESSAGEp algorithm achieves a squared-${\mathcal{L}}_2$ solution suboptimality rate of the order of $\mathcal{O}(n^{-\left(1-\epsilon \right)/2})$ iterations, where, for $\epsilon >0$, pathwise convergence is simultaneously guaranteed. This result establishes a rate of order arbitrarily close to $\mathcal{O}(n^{-1/2})$, while ensuring strongly stable pathwise operation. For $p\equiv 1$, the rate order improves to $\mathcal{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 $\epsilon \in \left[0,1\right)$, the MESSAGEp algorithm with iterate smoothing achieves an ${\mathcal{L}}_1$ objective suboptimality rate of the order of $\mathcal{O}(n^{-\left(1-\epsilon \right)/\left(41_{\left\{\mathbf{p}>1\right\}}+4\right)})$ iterations. This result provides maximal rates of $\mathcal{O}(n^{-1/4})$, if $p\equiv 1$, and $\mathcal{O}(n^{-1/8})$, if $p>1$, matching the state of the art, as well.

90 pages, 3 figures. Update: Substantial revision of the technical content, with an additional fully detailed analysis in regard to the rate of convergence of the MESSAGEp algorithm. NOTE: Please open in browser to see the math in the abstract!