Zeroth-order stochastic compositional algorithms for risk-aware learning

DOI10.1137/20M1315403MaRDI QIDQ5071109zbMATH OpenFDO

Authors Dionysios S. Kalogerias, Warren Powell

Publication date 20 April 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.09484

zbMATH Keywords

compositional optimizationmean-upper-semideviationrisk measuresrisk-averse optimizationrisk-aware learningstochastic gradient methodszeroth-order methods

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Stochastic programming (90C15) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We present $extit{Free-MESSAGE}^p$, the first zeroth-order algorithm for (weakly-)convex mean-semideviation-based risk-aware learning, which is also the first three-level zeroth-order compositional stochastic optimization algorithm whatsoever. Using a non-trivial extension of Nesterov's classical results on Gaussian smoothing, we develop the $extit{Free-MESSAGE}^p$ algorithm from first principles, and show that it essentially solves a smoothed surrogate to the original problem, the former being a uniform approximation of the latter, in a useful, convenient sense. We then present a complete analysis of the $extit{Free-MESSAGE}^p$ algorithm, which establishes convergence in a user-tunable neighborhood of the optimal solutions of the original problem for convex costs, as well as explicit convergence rates for convex, weakly convex, and strongly convex costs, and in a unified way. Orderwise, and for fixed problem parameters, our results demonstrate no sacrifice in convergence speed as compared to existing first-order methods, while striking a certain balance among the condition of the problem, its dimensionality, as well as the accuracy of the obtained results, naturally extending previous results in zeroth-order risk-neutral learning.

Recommendations

• A zeroth order method for stochastic weakly convex optimization
• Zeroth-order algorithms for stochastic distributed nonconvex optimization
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Zeroth-order optimization with orthogonal random directions
• Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points

Cites work

• Approximate Value Iteration for Risk-Aware Markov Decision Processes
• Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks
• Cash flow matching with risks controlled by buffered probability of exceedance and conditional value-at-risk
• Coherent risk measures in inventory problems
• Deep learning
• Dual Stochastic Dominance and Related Mean-Risk Models
• From stochastic dominance to mean-risk models: Semideviations as risk measures
• Generalized deviations in risk analysis
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 1324223 (Why is no real title available?)
• scientific article; zbMATH DE number 1391397 (Why is no real title available?)
• scientific article; zbMATH DE number 1416652 (Why is no real title available?)
• Introduction to Derivative-Free Optimization
• Introduction to Stochastic Search and Optimization
• Lectures on stochastic programming. Modeling and theory.
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Multilevel stochastic gradient methods for nested composition optimization
• Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
• Optimality conditions in portfolio analysis with general deviation measures
• Parallel Nonstationary Direct Policy Search for Risk-Averse Stochastic Optimization
• Proximité et dualité dans un espace hilbertien
• Random gradient-free minimization of convex functions
• Risk neutral and risk averse approaches to multistage renewable investment planning under uncertainty
• Risk-Averse Access Point Selection in Wireless Communication Networks
• Risk-averse approximate dynamic programming with quantile-based risk measures
• Sequential Decision Making With Coherent Risk
• Soft margin support vector classification as buffered probability minimization
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Stochastic model-based minimization of weakly convex functions
• Support vector machines based on convex risk functions and general norms

Cited in

(5)

• A Zeroth-Order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization
• Zeroth-order proximal clipped gradient method with shifts for distributed stochastic composite optimization problems with infinite variance
• Risk-adaptive approaches to stochastic optimization: a survey
• Title not available (Why is no real title available?)
• A proximal Newton-type algorithm for zeroth-order stochastic composite optimization with a new norm test for sample size selection

This page was built for publication: Zeroth-order stochastic compositional algorithms for risk-aware learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5071109)