2018/04/02 by Dionysios S. Kalogerias, Kalogerias, Dionysios S., Warren B. Powell +1 · 1 citation
Decision Sciences · Engineering · Mathematics · #Applications (stat.AP) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Methodology (stat.ME) #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #math.OC #stat.AP #stat.ME #stat.ML
paper · pdf · doi:10.48550/arxiv.1804.00636
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!
openalex publication_date 2018/04/02 · openalex created_date 2018/04/13 · arxiv created 2018/10/29 · arxiv updated 2018/10/30 · openalex updated_date 2026/07/28
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 ε∈[0,1), the MESSAGEp algorithm achieves a squared-\cal L2 solution suboptimality rate of the order of \cal O(n-(1-ε)/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 p≡1, 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 ε∈[0,1), the MESSAGEp algorithm with iterate smoothing achieves an \cal L1 objective suboptimality rate of the order of \cal O(n^-(1-ε)/(4\bf1_\ p>1\ +4)) iterations. This result provides maximal rates of \cal O(n-1/4), if p≡1, and \cal O(n-1/8), if p>1, matching the state of the art, as well.