An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems

DOI10.1007/S10957-023-02351-9arXiv1711.03669OpenAlexW2883470300MaRDI QIDQ6182323FDOQ6182323

Renbo Zhao, William B. Haskell, Le Thi Khanh Hien

Publication date: 25 January 2024

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

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 $varepsilon$-optimal and $varepsilon$-feasible solution, both frameworks achieve the best-known oracle complexities (in terms of their dependence on $varepsilon$).

Full work available at URL: https://arxiv.org/abs/1711.03669

zbMATH Keywords

stochastic optimizationconvex optimization with functional constraintsinexact primal-dual smoothingnon-bilinear saddle point problems

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Nonsmooth analysis (49J52)

Cites Work

• Title not available (Why is that?)
• Smooth minimization of non-smooth functions
• Gradient methods for minimizing composite functions
• First-Order Methods in Optimization
• 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
• Excessive Gap Technique in Nonsmooth Convex Minimization
• ESSENTIAL SMOOTHNESS, ESSENTIAL STRICT CONVEXITY, AND LEGENDRE FUNCTIONS IN BANACH SPACES
• Subgradient methods for saddle-point problems
• Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
• Title not available (Why is that?)
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• Title not available (Why is that?)
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
• An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems
• An optimal randomized incremental gradient method
• A simplified view of first order methods for optimization
• Accelerated schemes for a class of variational inequalities
• A Level-Set Method for Convex Optimization with a Feasible Solution Path
• Contracting Proximal Methods for Smooth Convex Optimization
• A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
• Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization
• Affine-invariant contracting-point methods for convex optimization

Cited In (1)

• Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems

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)