Accelerated stochastic algorithms for convex-concave saddle-point problems
From MaRDI portal
Publication:5085148
Abstract: We develop stochastic first-order primal-dual algorithms to solve a class of convex-concave saddle-point problems. When the saddle function is strongly convex in the primal variable, we develop the first stochastic restart scheme for this problem. When the gradient noises obey sub-Gaussian distributions, the oracle complexity of our restart scheme is strictly better than any of the existing methods, even in the deterministic case. Furthermore, for each problem parameter of interest, whenever the lower bound exists, the oracle complexity of our restart scheme is either optimal or nearly optimal (up to a log factor). The subroutine used in this scheme is itself a new stochastic algorithm developed for the problem where the saddle function is non-strongly convex in the primal variable. This new algorithm, which is based on the primal-dual hybrid gradient framework, achieves the state-of-the-art oracle complexity and may be of independent interest.
Recommendations
- Optimal primal-dual methods for a class of saddle point problems
- Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- Accelerated methods for saddle-point problem
- A primal-dual algorithm with line search for general convex-concave saddle point problems
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 5135703 (Why is no real title available?)
- scientific article; zbMATH DE number 3695967 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Stochastic Approximation Method
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- Accelerated schemes for a class of variational inequalities
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex-concave saddle-point problems
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- An optimal method for stochastic composite optimization
- CVXPY: a Python-embedded modeling language for convex optimization
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Convex optimization in normed spaces. Theory, methods and examples
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Elements of Information Theory
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Gradient methods for minimizing composite functions
- High-dimensional probability. An introduction with applications in data science
- Information-Based Complexity, Feedback and Dynamics in Convex Programming
- Learning the kernel matrix with semidefinite programming
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Non-Euclidean restricted memory level method for large-scale convex optimization
- On general minimax theorems
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Optimal primal-dual methods for a class of saddle point problems
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Regularization and Variable Selection Via the Elastic Net
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of non-smooth functions
- Smoothing technique and its applications in semidefinite optimization
- Solving variational inequalities with stochastic mirror-prox algorithm
- Subgradient methods for saddle-point problems
- The ordered subsets mirror descent optimization method with applications to tomography
Cited in
(20)- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- General procedure to provide high-probability guarantees for stochastic saddle point problems
- Decentralized saddle-point problems with different constants of strong convexity and strong concavity
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- An accelerated directional derivative method for smooth stochastic convex optimization
- Accelerated stochastic variance reduction for a class of convex optimization problems
- On lower iteration complexity bounds for the convex concave saddle point problems
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- Accelerated variance-reduced methods for saddle-point problems
- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
- Stochastic Saddle Point Problems with Decision-Dependent Distributions
- Optimal primal-dual methods for a class of saddle point problems
- Practical acceleration of the Condat-Vũ algorithm
This page was built for publication: Accelerated stochastic algorithms for convex-concave saddle-point problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085148)
