# Optimal Methods for Convex Risk Averse Distributed Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 10 Mar 2022.

## Builds on (most cited first, 11 of 11)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Likelihood Robust Optimization for Data-driven Problems](https://mlsanity.com/paper/1307.6279/) (2013)
- [Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization](https://mlsanity.com/paper/2101.00143/) (2021)
- [Efficient Algorithms for Distributionally Robust Stochastic Optimization with Discrete Scenario Support](https://mlsanity.com/paper/1909.11216/) (2019)

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

- [Communication-Efficient Federated Group Distributionally Robust Optimization](https://mlsanity.com/paper/2410.06369/) (2024)
- [Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions](https://mlsanity.com/paper/2507.19465/) (2025)

## Abstract (arXiv)

This paper studies the communication complexity of convex risk-averse optimization over a network. The problem generalizes the well-studied risk-neutral finite-sum distributed optimization problem and its importance stems from the need to handle risk in an uncertain environment. For algorithms in the literature, there exists a gap in communication complexities for solving risk-averse and risk-neutral problems. We propose two distributed algorithms, namely the distributed risk averse optimization (DRAO) method and the distributed risk averse optimization with sliding (DRAO-S) method, to close the gap. Specifically, the DRAO method achieves the optimal communication complexity by assuming a certain saddle point subproblem can be easily solved in the server node. The DRAO-S method removes the strong assumption by introducing a novel saddle point sliding subroutine which only requires the projection over the ambiguity set P. We observe that the number of P-projections performed by DRAO-S is optimal. Moreover, we develop matching lower complexity bounds to show the communication complexities of both DRAO and DRAO-S to be improvable. Numerical experiments are conducted to demonstrate the encouraging empirical performance of the DRAO-S method.