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
- 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
- A Stochastic Approximation Method
- 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
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Convex optimization in normed spaces. Theory, methods and examples
- CVXPY: a Python-embedded modeling language for convex optimization
- 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
- 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?)
- 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 primal-dual methods for a class of saddle point problems
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- 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
(23)- An accelerated directional derivative method for smooth stochastic convex optimization
- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming 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
- Accelerated stochastic variance reduction for a class of convex optimization problems
- 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
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- Optimal primal-dual methods for a class of saddle point problems
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- Accelerated variance-reduced methods for saddle-point problems
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
- Decentralized saddle-point problems with different constants of strong convexity and strong concavity
- Stochastic Saddle Point Problems with Decision-Dependent Distributions
- Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
- General procedure to provide high-probability guarantees for stochastic saddle point problems
- Practical acceleration of the Condat-Vũ algorithm
- A practical and optimal first-order method for large-scale convex quadratic programming
- A stochastic primal-dual splitting algorithm with variance reduction for composite optimization problems
- Stochastic-constrained stochastic optimization with Markovian data
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)
