Two new algorithms solve nonconvex-strongly concave problems efficiently.
problem Solving nonconvex-strongly concave minimax problems.
method Proposed MINIMAX-TR and MINIMAX-TRACE algorithms.
result Find ( ε , ε ) (ε, \sqrtε) ( ε , ε ) -second order stationary points within O ( ε − 1.5 ) \mathcal{O}(ε^{-1.5}) O ( ε − 1.5 ) iterations. Develops shuffling gradient-based methods for nonconvex-concave minimax optimization.
problem Nonconvex-concave minimax optimization problems.
method Two shuffling gradient-based algorithms for nonconvex-linear and nonconvex-strongly concave settings.
result Achieves state-of-the-art oracle complexity in nonconvex optimization and best-known complexity bounds for nonconvex-strongly concave setting.
Paper proposes an algorithm to solve complex minimax problems efficiently.
problem Stochastic nonconvex-concave minimax problems in various fields.
method Accelerated first-order regularized momentum descent ascent algorithm (FORMDA).
result Achieves best-known complexity bound of i l d e O ( ε − 6.5 ) ilde{\mathcal{O}}(\varepsilon ^{-6.5}) i l d e O ( ε − 6.5 ) for single-loop algorithms. TiAda adapts adaptive gradient methods for nonconvex minimax optimization.
problem Nonconvex minimax optimization challenges in achieving convergence.
method TiAda is a time-scale adaptive GDA algorithm for nonconvex minimax optimization.
result TiAda achieves near-optimal complexities in deterministic and stochastic settings.
Two algorithms solve nonconvex minimax problems with linear constraints, achieving complexity guarantees.
problem Nonconvex minimax problems with coupled linear constraints.
method Zeroth-order primal-dual alternating projected gradient (ZO-PDAPG) and zeroth-order regularized momentum primal-dual projected gradient (ZO-RMPDPG) algorithms.
result Iteration complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints.
This paper analyzes OGDA and EG methods for nonconvex minimax problems.
problem Theoretical guarantees of OGDA and EG methods in nonconvex settings.
method Unified analysis through single-call extra-gradient methods.
result Established convergence of OGDA and EG methods under NC-SC and NC-C settings.
New algorithms solve nonconvex-concave minimax problems without parameter knowledge.
problem Solving nonconvex-concave minimax problems efficiently.
method Three completely parameter-free single-loop algorithms.
result Achieve optimal iteration complexity for nonconvex-concave minimax problems.
New algorithms solve complex minimax problems without needing derivatives.
problem Solving nonconvex-concave minimax problems efficiently.
method Zeroth-order alternating and proximal gradient algorithms.
result Iteration complexity and function value estimation bounds established.
A new method solves a complex optimization problem efficiently.
problem Nonconvex-strongly-concave constrained minimax optimization.
method First-order augmented Lagrangian method with a first-order subproblem solver.
result Achieves improved operation complexity for finding solutions.
New algorithm solves nonconvex-convex minimax problems efficiently.
problem Solving nonconvex-convex minimax problems with nonsmooth, nonconvex, and nonlinearity.
method Hybrid variance-reduced SGD algorithm combining smoothing and biased techniques.
result Achieves O(T^(-2/3)) convergence rate and best oracle complexity.
New algorithm solves minimax games with linear constraints.
problem Nonconvex minimax games with coupled linear constraints.
method Primal-dual alternating proximal gradient (PDAPG) algorithm.
result Achieves ε-stationary solution within O(ε^(-2)) iterations for strongly concave settings.
Two-stage nonconvex algorithm and convex relaxation both achieve optimal accuracy in noisy blind deconvolution.
problem Solving bilinear systems of equations with random noise under different designs.
method Two-stage nonconvex algorithm and convex relaxation.
result Both methods achieve minimax-optimal accuracy in the presence of random noise.
AGDA and variance-reduced methods solve nonconvex-nonconcave minimax problems globally and faster.
problem Solving nonconvex-nonconcave minimax problems in machine learning.
method Global convergence of AGDA and variance-reduced algorithms.
result AGDA and variance-reduced methods achieve global convergence and faster rates.
Paper proposes algorithms for solving nonconvex-nonconcave problems with complexity guarantees.
problem Nonconvex-nonconcave minimax problems with PL condition.
method Zeroth-order AGDA and VRAGDA algorithms.
result Iteration complexities for obtaining ε-stationary points.
New SGDA method speeds up nonconvex minimax optimization.
problem Improving convergence of nonconvex minimax optimization.
method SGDA with random reshuffling for nonconvex-PŁ objectives.
result Convergence rates faster than with-replacement SGDA.
The paper analyzes PPM for nonconvex-nonconcave problems, identifying three regions with varying convergence guarantees.
problem Challenges in nonconvex-nonconcave minimax optimization.
method Classic proximal point method with insights from the Moreau envelope.
result Identification of three regions with varying convergence guarantees for PPM.
NeAda solves nonconvex minimax optimization by balancing primal and dual variables adaptively.
problem Nonconvex minimax optimization challenges with parameter-agnostic adaptive algorithms.
method Nested Adaptive (NeAda) framework with inner and outer loops for primal and dual variables.
result Achieves near-optimal convergence rates for nonconvex-strongly-concave problems.
Improved zeroth-order algorithms tackle nonconvex minimax problems with reduced complexity.
problem Nonconvex minimax optimization problems in machine learning.
method Design and analysis of Zeroth-Order Gradient Descent Ascent ( exttt{ZO-GDA}) and Zeroth-Order Gradient Descent Multi-Step Ascent ( exttt{ZO-GDMSA}) algorithms.
result Oracle complexity improvements for minimax optimization problems.
Paper proves Sion's theorem in geodesic spaces and develops a Riemannian extragradient method.
problem Understanding saddle points in nonconvex-nonconcave minimax problems.
method Geodesic metric space version of Sion's theorem and Riemannian extragradient method.
result Developed a Riemannian extragradient algorithm for smooth minimax problems.
Paper analyzes nonconvex bandit problems with improved adaptive methods.
problem Continuous armed bandit problems for nonconvex cost functions.
method Simple and adaptive bin splitting methods.
result Adaptive method achieves locally minimax optimal expected cumulative regret.
New method solves complex constrained optimization problems.
problem Constrained nonconvex-nonconcave minimax optimization problems.
method Inexact proximal gradient method using sequential convex programming.
result Established complexity guarantees for approximate stationary points.
The paper analyzes generalization bounds for NC-SC/NC-C stochastic minimax optimization.
problem Generalization analysis of nonconvex-(strongly)-concave stochastic minimax optimization.
method Established algorithm-agnostic and algorithm-dependent generalization bounds via uniform convergence and stability arguments.
result Sample complexities and generalization bounds for NC-SC and NC-C settings.
New algorithms solve nonconvex-nonconcave minimax optimization problems.
problem Solving minimax optimization problems in machine learning.
method Two novel Newton-type algorithms for nonconvex-nonconcave minimax optimization.
result Proved local convergence at strict local minimax points.
A novel decentralized algorithm improves minimax optimization in federated learning.
problem Minimax optimization in federated learning with data heterogeneity.
method Decentralized Gradient Tracking (K-GT-Minimax) for nonconvex-strongly-concave optimization.
result Demonstrates superior convergence rate for NC-SC minimax optimization.
Paper improves risk bounds for nonconvex-strongly-concave minimax problems.
problem Achieving sharper risk bounds for nonconvex-strongly-concave minimax problems.
method Using uniform localized convergence to derive high probability generalization error bounds.
result Derives n times faster excess primal risk bounds for popular algorithms.
New method tackles nonconvex-nonconcave problems with local KL condition.
problem Nonconvex-nonconcave minimax problems under varying KL conditions.
method Inexact proximal gradient method for KL-structured subproblems.
result Complexity guarantees for approximate stationary points.
DS-GDA solves nonconvex-nonconcave problems without regularity conditions.
problem Nonconvex-nonconcave minimax optimization challenges.
method Doubly smoothed gradient descent ascent method (DS-GDA).
result Achieves convergence on various nonconvex-nonconcave problems.
Minimax optimization has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training and multi-agent reinforcement learning. As most of these applications involve continuous nonconvex-nonconcave formulations, a very basic question arises---"w…
This paper studies first order methods for solving smooth minimax optimization problems min x max y g ( x , y ) \min_x \max_y g(x,y) min x max y g ( x , y ) where g ( ⋅ , ⋅ ) g(\cdot,\cdot) g ( ⋅ , ⋅ ) is smooth and g ( x , ⋅ ) g(x,\cdot) g ( x , ⋅ ) is concave for each x x x . In terms of g ( ⋅ , y ) g(\cdot,y) g ( ⋅ , y ) , we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. …
We consider nonconvex-concave minimax problems, min x max y ∈ Y f ( x , y ) \min_{\mathbf{x}} \max_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y}) min x max y ∈ Y f ( x , y ) , where f f f is nonconvex in x \mathbf{x} x but concave in y \mathbf{y} y and Y \mathcal{Y} Y is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated…
New algorithms solve complex minimax problems efficiently.
problem Nonconvex-strongly concave minimax problems in machine learning.
method Gradient norm regularized trust-region (GRTR) and Levenberg-Marquardt (LMNegCur) algorithms.
result Proved iteration complexities matching best known results.
Paper analyzes complexity of solving nonconvex-strongly-concave problems.
problem Finding approximate stationary points of nonconvex-strongly-concave minimax problems.
method Introduces a generic acceleration scheme to solve crafted subproblems.
result Algorithm nearly matches lower complexity bounds in general setting.
A federated minimax framework for heterogeneous clients.
problem Training with edge devices having different datasets and capabilities.
method Proposes a federated minimax optimization framework with normalized updates.
result Improves convergence and communication complexity for nonconvex functions.
Two new methods improve block-sparse signal recovery from noisy data.
problem Recovering block-sparse signals with unknown partitions.
method LogLOP-l2/l1 and AdaLOP-l2/l1 methods using log-sum penalty and MCP.
result Our methods outperform existing techniques in estimation accuracy.
Paper analyzes convergence of GDA for nonconvex-nonconcave minimax problems.
problem Understanding convergence of GDA for nonconvex-nonconcave minimax problems.
method Local convergence analysis of GDA with stepsize ratio Θ(κ).
result Stepsize ratio of Θ(κ) is necessary and sufficient for local convergence of GDA to a Stackelberg Equilibrium.
SREDA optimizes complex machine learning problems with fewer evaluations.
problem Finding an optimal point in nonconvex-strongly-concave minimax problems.
method Stochastic Recursive Gradient Descent Ascent (SREDA) with variance reduction.
result Achieves optimal stochastic gradient complexity of O(κ^3ε^-3).
A fast sketching algorithm solves regularized least squares problems efficiently.
problem Solving large-scale optimization problems with convex or nonconvex regularization.
method Sketching for Regularized Optimization (SRO) algorithm that generates a sketch of the original data matrix and solves the sketched problem.
result General theoretical results for the approximation error between the original and sketched problems, including minimax rates for sparse signal estimation.
We consider compressed sensing formulated as a minimization problem of nonconvex sparse penalties, Smoothly Clipped Absolute deviation (SCAD) and Minimax Concave Penalty (MCP). The nonconvexity of these penalties is controlled by nonconvexity parameters, and L1 penalty is contained as a limit with respect to these para…
Support vector machines (SVMs) with sparsity-inducing nonconvex penalties have received considerable attentions for the characteristics of automatic classification and variable selection. However, it is quite challenging to solve the nonconvex penalized SVMs due to their nondifferentiability, nonsmoothness and nonconve…
New theorem guarantees approximate equilibrium in non-convex games.
problem No guarantee of equilibrium in non-convex games.
method Introduced a minimax theorem for non-convex games involving neural networks.
result Provided an approximate minimax theorem for non-convex games.
Paper tackles gradient-free minimax optimization with variance reduction for faster convergence.
problem Gradient-free minimax optimization problems in machine learning.
method Variance reduction technique to design a novel zeroth-order gradient descent ascent algorithm.
result Achieves the best known query complexity of O(κ(d₁ + d₂)ε⁻³), outperforming previous methods.
Paper solves minimax optimization gap with near-optimal algorithms.
problem Designing efficient algorithms for smooth and strongly-convex-strongly-concave minimax problems.
method Accelerated proximal point method and accelerated solver for minimax proximal steps.
result First algorithm with gradient complexity matching the lower bound up to logarithmic factors.
Method solves nonconvex constrained optimization problems with a new augmented Lagrangian approach.
problem Nonconvex composite functional constraints with inequality constraints.
method First-order augmented Lagrangian method with smoothed prox-linear reformulation.
result Explicit convergence rates for the proposed method in terms of KKT residual.
New algorithm solves federated minimax optimization problems.
problem Federated minimax optimization challenges.
method Federated Stochastic Smoothed Gradient Descent Ascent (FESS-GDA).
result FESS-GDA uniformly solves federated minimax problems.
Sparse principal component analysis (PCA) involves nonconvex optimization for which the global solution is hard to obtain. To address this issue, one popular approach is convex relaxation. However, such an approach may produce suboptimal estimators due to the relaxation effect. To optimally estimate sparse principal su…
A new decentralized method solves minimax problems with reduced communication and sample complexity.
problem Solving minimax optimization problems in a distributed setting.
method Decentralized stochastic gradient descent ascent with variance reduction.
result Achieved optimal sample and communication complexities for nonconvex-strongly-concave problems.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) accuracy. Sign information is the key to overcoming the inevitable saturation error in compressive sensing systems, which causes information loss and results in bias. For sparse signal recovery from saturation, we propose to use a linear loss to improve the effectiveness from existing methods that utilize hard constraints/hinge …