A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization

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.

46 pages

References in corpus (2)

• Near-Optimal Algorithms for Minimax Optimization
• Efficient Algorithms for Smooth Minimax Optimization

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