A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
arXiv:2003.04375
Abstract
We propose a primal-dual smoothing framework for finding a near-stationary point of a class of non-smooth non-convex optimization problems with max-structure. We analyze the primal and dual gradient complexities of the framework via two approaches, i.e., the dual-then-primal and primal-the-dual smoothing approaches. Our framework improves the best-known oracle complexities of the existing method, even in the restricted problem setting. As an important part of our framework, we propose a first-order method for solving a class of (strongly) convex-concave saddle-point problems, which is based on a newly developed non-Hilbertian inexact accelerated proximal gradient algorithm for strongly convex composite minimization that enjoys duality-gap convergence guarantees. Some variants and extensions of our framework are also discussed.
arXiv comment46 pages
References in corpus (9)
- Certifying Some Distributional Robustness with Principled Adversarial Training
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
- Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
- Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
- Near-Optimal Algorithms for Minimax Optimization
- Regularizing with Bregman-Moreau envelopes
- Efficient Algorithms for Smooth Minimax Optimization
- An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
Cited by in corpus (5)
- Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
- The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
- Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
- Minimax Optimization with Smooth Algorithmic Adversaries
- Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems