Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning
From MaRDI portal
Abstract: Min-max problems have broad applications in machine learning, including learning with non-decomposable loss and learning with robustness to data distribution. Convex-concave min-max problem is an active topic of research with efficient algorithms and sound theoretical foundations developed. However, it remains a challenge to design provably efficient algorithms for non-convex min-max problems with or without smoothness. In this paper, we study a family of non-convex min-max problems, whose objective function is weakly convex in the variables of minimization and is concave in the variables of maximization. We propose a proximally guided stochastic subgradient method and a proximally guided stochastic variance-reduced method for the non-smooth and smooth instances, respectively, in this family of problems. We analyze the time complexities of the proposed methods for finding a nearly stationary point of the outer minimization problem corresponding to the min-max problem.
Recommendations
- The landscape of the proximal point method for nonconvex-nonconcave minimax optimization
- Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- Optimality Conditions for Nonsmooth Nonconvex-Nonconcave Min-Max Problems and Generative Adversarial Networks
- A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems
Cites work
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Efficiency of minimizing compositions of convex functions and smooth maps
- Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
- Monotone Operators and the Proximal Point Algorithm
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- scientific article; zbMATH DE number 192914 (Why is no real title available?)
- Robust Stochastic Approximation Approach to Stochastic Programming
- Statistical consistency and asymptotic normality for high-dimensional robust \(M\)-estimators
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic model-based minimization of weakly convex functions
- Variance-based regularization with convex objectives
Cited in
(30)- An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispersion problem
- scientific article; zbMATH DE number 7625189 (Why is no real title available?)
- First-order convergence theory for weakly-convex-weakly-concave min-max problems
- An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems
- Zeroth-order single-loop algorithms for nonconvex-linear minimax problems
- Zeroth-order algorithms for nonconvex-strongly-concave minimax problems with improved complexities
- Adaptively weighted difference model of anisotropic and isotropic total variation for image denoising
- The landscape of the proximal point method for nonconvex-nonconcave minimax optimization
- A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems
- Decentralized Gradient Descent Maximization Method for Composite Nonconvex Strongly-Concave Minimax Problems
- Optimality Conditions for Nonsmooth Nonconvex-Nonconcave Min-Max Problems and Generative Adversarial Networks
- On Proximal Algorithms with Inertial Effects Beyond Monotonicity
- Conservative parametric optimality and the ridge method for tame min-max problems
- Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems
- Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
- An approximation proximal gradient algorithm for nonconvex-linear minimax problems with nonconvex nonsmooth terms
- Stochastic nested primal-dual method for nonconvex constrained composition optimization
- A quasi-Newton subspace trust region algorithm for nonmonotone variational inequalities in adversarial learning over box constraints
- Convergence properties of gradient-based methods for minimax problems with nonlinear constraints
- Adaptive method for saddle point problems with a generalization of smoothness property
- Nonsmooth nonconvex-nonconcave minimax optimization: primal-dual balancing and iteration complexity analysis
- Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
- A consensus-based algorithm for non-convex multiplayer games
- Unified convergence analysis for adaptive optimization with moving average estimator
- An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems
- Outer approximation scheme for weakly convex constrained optimization problems
- A minimization approach for minimax optimization with coupled constraints
- An alternating proximal gradient algorithm for nonsmooth nonconvex-linear minimax problems with coupled linear constraints
- An alternating gradient projection algorithm with momentum for nonconvex-concave minimax problems
- Primal-dual algorithm for weakly convex functions under sharpness conditions
This page was built for publication: Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043854)
