Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems

Abstract

We develop a novel and single-loop variance-reduced algorithm to solve a class of stochastic nonconvex-convex minimax problems involving a nonconvex-linear objective function, which has various applications in different fields such as machine learning and robust optimization. This problem class has several computational challenges due to its nonsmoothness, nonconvexity, nonlinearity, and non-separability of the objective functions. Our approach relies on a new combination of recent ideas, including smoothing and hybrid biased variance-reduced techniques. Our algorithm and its variants can achieve $\mathcal{O}(T^{-2/3})$-convergence rate and the best known oracle complexity under standard assumptions, where $T$ is the iteration counter. They have several computational advantages compared to existing methods such as simple to implement and less parameter tuning requirements. They can also work with both single sample or mini-batch on derivative estimators, and with constant or diminishing step-sizes. We demonstrate the benefits of our algorithms over existing methods through two numerical examples, including a nonsmooth and nonconvex-non-strongly concave minimax model.

arXiv comment30 pages and 6 figures

References in corpus (13)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Stochastic Hamiltonian Gradient Methods for Smooth Games
• Variance Reduced methods for Non-convex Composition Optimization
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Proximal methods for minimizing the sum of a convex function and a composite function
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization

Cited by in corpus (4)

• Learning from History for Byzantine Robust Optimization
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction