# Zeroth-order Stochastic Compositional Algorithms for Risk-Aware Learning

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

## Key facts

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

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

- [Risk-Averse No-Regret Learning in Online Convex Games](https://mlsanity.com/paper/2203.08957/) (2022)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)

## Abstract (arXiv)

We present textitFree-MESSAGEp, 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 textitFree-MESSAGEp 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 textitFree-MESSAGEp 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.