Accelerated stochastic algorithms for convex-concave saddle-point problems
From MaRDI portal
Publication:5085148
DOI10.1287/MOOR.2021.1175zbMATH Open1489.90130arXiv1903.01687OpenAlexW3164209919MaRDI QIDQ5085148FDOQ5085148
Authors: Renbo Zhao 
Publication date: 27 June 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1903.01687
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
stochastic approximationconvex-concave saddle-point problemsprimal-dual first-order methodprimal-dual hybrid gradient framework
Convex programming (90C25) Stochastic programming (90C15) Minimax problems in mathematical programming (90C47)
Cites Work
- CVXPY: a Python-embedded modeling language for convex optimization
- Title not available (Why is that?)
- Elements of Information Theory
- Regularization and Variable Selection Via the Elastic Net
- Smooth minimization of non-smooth functions
- Gradient methods for minimizing composite functions
- High-dimensional probability. An introduction with applications in data science
- A Stochastic Approximation Method
- Primal-dual subgradient methods for convex problems
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- The ordered subsets mirror descent optimization method with applications to tomography
- Robust Stochastic Approximation Approach to Stochastic Programming
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Subgradient methods for saddle-point problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Title not available (Why is that?)
- Non-Euclidean restricted memory level method for large-scale convex optimization
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- Learning the kernel matrix with semidefinite programming
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- An optimal method for stochastic composite optimization
- 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
- On general minimax theorems
- Solving variational inequalities with stochastic mirror-prox algorithm
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Convex optimization in normed spaces. Theory, methods and examples
- Smoothing technique and its applications in semidefinite optimization
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Optimal primal-dual methods for a class of saddle point problems
- Title not available (Why is that?)
- Information-Based Complexity, Feedback and Dynamics in Convex Programming
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- 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
- Accelerated schemes for a class of variational inequalities
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- Title not available (Why is that?)
Cited In (20)
- 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
- Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- Stochastic Saddle Point Problems with Decision-Dependent Distributions
- Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
- Optimal primal-dual methods for a class of saddle point problems
- Practical acceleration of the Condat-Vũ algorithm
- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
Uses Software
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)
