Optimal Methods for Convex Risk-Averse Distributed Optimization
From MaRDI portal
Abstract: 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 . We observe that the number of -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.
Recommendations
- Optimal convergence rates for convex distributed optimization in networks
- Communication-efficient algorithms for decentralized and stochastic optimization
- A dual approach for optimal algorithms in distributed optimization over networks
- Distributed communication-sliding mirror-descent algorithm for nonsmooth resource allocation problem
- A primal-dual algorithm for risk minimization
Cites work
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Advances and Open Problems in Federated Learning
- An optimal randomized incremental gradient method
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
- Efficient algorithms for distributionally robust stochastic optimization with discrete scenario support
- First-order and stochastic optimization methods for machine learning
- First-order methods in optimization
- Gradient sliding for composite optimization
- Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 477581 (Why is no real title available?)
- scientific article; zbMATH DE number 6253954 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Lectures on stochastic programming. Modeling and theory.
- Likelihood robust optimization for data-driven problems
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- New variants of bundle methods
- Nonlinear total variation based noise removal algorithms
- Optimal convergence rates for convex distributed optimization in networks
- Smooth minimization of non-smooth functions
- Sparsity and Smoothness Via the Fused Lasso
- Tensor Decompositions and Applications
Cited in
(2)
This page was built for publication: Optimal Methods for Convex Risk-Averse Distributed Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116242)
