An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
From MaRDI portal
(Redirected from Publication:6182323)
Abstract: We develop an inexact primal-dual first-order smoothing framework to solve a class of non-bilinear saddle point problems with primal strong convexity. Compared with existing methods, our framework yields a significant improvement over the primal oracle complexity, while it has competitive dual oracle complexity. In addition, we consider the situation where the primal-dual coupling term has a large number of component functions. To efficiently handle this situation, we develop a randomized version of our smoothing framework, which allows the primal and dual sub-problems in each iteration to be solved by randomized algorithms inexactly in expectation. The convergence of this framework is analyzed both in expectation and with high probability. In terms of the primal and dual oracle complexities, this framework significantly improves over its deterministic counterpart. As an important application, we adapt both frameworks for solving convex optimization problems with many functional constraints. To obtain an -optimal and -feasible solution, both frameworks achieve the best-known oracle complexities (in terms of their dependence on ).
Recommendations
- A primal-dual smoothing framework for max-structured non-convex optimization
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- Optimal primal-dual methods for a class of saddle point problems
- A primal-dual algorithm framework for convex saddle-point optimization
- First-order primal-dual methods for nonsmooth non-convex optimization
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A level-set method for convex optimization with a feasible solution path
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- A proximal stochastic gradient method with progressive variance reduction
- A simplified view of first order methods for optimization
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization
- Accelerated schemes for a class of variational inequalities
- Affine-invariant contracting-point methods for convex optimization
- An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex-concave saddle-point problems
- An optimal randomized incremental gradient method
- Contracting proximal methods for smooth convex optimization
- ESSENTIAL SMOOTHNESS, ESSENTIAL STRICT CONVEXITY, AND LEGENDRE FUNCTIONS IN BANACH SPACES
- Excessive Gap Technique in Nonsmooth Convex Minimization
- First-order methods in optimization
- Gradient methods for minimizing composite functions
- Inexact and accelerated proximal point algorithms
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
- On the ergodic convergence rates of a first-order primal-dual algorithm
- 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
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- Smooth minimization of non-smooth functions
- Solving variational inequalities with stochastic mirror-prox algorithm
- Subgradient methods for saddle-point problems
Cited in
(2)
This page was built for publication: An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182323)
