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. 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.
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.
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…
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.
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.
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 algorithm computes optimal transport barycenter efficiently.
problem Computing optimal transport barycenter for high-dimensional probability distributions.
method Wasserstein-Descent H ˙ 1 \dot{\mathbb{H}}^1 H ˙ 1 -Ascent (WDHA) algorithm. result Exact barycenter computation in nearly linear time and linear space 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.
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 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.
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.
Paper explores generalization of minimax learners, proposing a new metric.
problem Understanding how minimax learners perform on unseen data.
method Proposes a new metric, the primal gap, to study generalization of minimax learners.
result Derives generalization error bounds for the primal gap in nonconvex-concave settings.
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.
Wasserstein framework solves mixed linear regression problems.
problem Mixed linear regression with multi-modal distributions.
method Wasserstein distance minimization for nonconvex-concave minimax optimization.
result WMLR achieves global convergence and generalization guarantees for two linear models.
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).
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.
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.
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. 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.
We investigate the use of Minimax distances to extract in a nonparametric way the features that capture the unknown underlying patterns and structures in the data. We develop a general-purpose and computationally efficient framework to employ Minimax distances with many machine learning methods that perform on numerica…
Many tasks in modern machine learning can be formulated as finding equilibria in \emph{sequential} games. In particular, two-player zero-sum sequential games, also known as minimax optimization, have received growing interest. It is tempting to apply gradient descent to solve minimax optimization given its popularity a…
This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
A new method solves complex constrained minimax problems.
problem Solving constrained minimax optimization problems.
method First-order augmented Lagrangian method.
result Established an operation complexity of O ( ε − 4 log ε − 1 ) O(\varepsilon^{-4}\log\varepsilon^{-1}) O ( ε − 4 log ε − 1 ) . 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.
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.
Efficient sampling reduces memory usage for Minimax distance analysis.
problem Quadratic memory requirement for existing Minimax distance methods.
method Proposes a novel sampling technique with linear space complexity.
result Demonstrates significant reduction in memory usage for Minimax distances.
Study on estimating invertible functions with minimax analysis.
problem Minimizing risk of estimating invertible functions on a plane.
method Introduce two types of L 2 L^2 L 2 -risks, derive lower and upper rates for minimax values, develop an asymptotically almost everywhere invertible estimator. result Invertibility does not reduce the complexity of the estimation problem in terms of the rate.
Minimax defense improves neural network security against gradient-based attacks.
problem Gradient-based adversarial attacks on neural networks.
method Minimax optimization in a GAN framework to create a discriminator that plays a minimax game with the generator.
result Minimax defense significantly reduces adversarial attack success rates compared to standard classifiers.
Minimax linkage was first introduced by Ao et al. [3] in 2004, as an alternative to standard linkage methods used in hierarchical clustering. Minimax linkage relies on distances to a prototype for each cluster; this prototype can be thought of as a representative object in the cluster, hence improving the interpretabil…
New bounds on minimax regret for sequential probability assignment using logarithmic loss.
problem Minimizing regret in sequential probability assignment against arbitrary experts.
method Using self-concordance property of logarithmic loss to derive tight bounds.
result Tight bounds on minimax regret for various expert classes.
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 algorithm AG-OG optimizes separable convex-concave problems efficiently.
problem Efficiently solving separable convex-concave minimax optimization problems.
method Leverages Nesterov acceleration and optimistic gradient on component and coupling parts of the problem.
result Achieves optimal convergence rate for various settings including bilinearly coupled problems.
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.
Optimally estimate distances on surfaces using reconstructed meshes.
problem Estimating intrinsic distances on smooth submanifolds.
method Reconstruction of the surface using a tangential Delaunay complex, and Isomap variant.
result Minimax optimality achieved for distance estimation.
Study minimax linear regression under quantile risk, improving existing bounds and providing new results.
problem Designing minimax procedures in linear regression under quantile risk.
method Analyzes realizable setting with Gaussian noise, extends to all p-th power error functions, develops new lower and upper bounds.
result Proves minimaxity of a variant of the min-max regression procedure for all p-th power error functions.
This paper analyzes how machine learning models resist adversarial attacks in nonparametric regression.
problem Adversarial attacks on machine learning models in nonparametric regression.
method Theoretical analysis of minimax rates of convergence under adversarial sup-norm.
result The minimax rate under adversarial attacks is the sum of two terms: standard rate and deviation of true function.
Develops high-probability minimax quantile bounds for statistical problems.
problem Statistical procedures often lose information about tail behavior when reduced to expectations.
method Introduces minimax quantiles, develops high-probability variants of minimax methods, and converts risk lower bounds to quantile lower bounds.
result Obtains high-probability minimax quantile lower bounds for various statistical problems.
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.
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.
New estimator achieves minimax optimal risk in transfer learning.
problem Nonparametric regression with transfer learning.
method Confidence thresholding estimator and data-driven adaptive algorithm.
result Adaptive algorithm achieves minimax risk up to a logarithmic factor.
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine th…
Minimax solutions are weak solutions to Cauchy problems involving Hamilton--Jacobi equations, constructed from generating families quadratic at infinity of their geometric solutions. We give a complete description of minimax solutions and we classify their generic singularities of codimension not greater than 2.
This paper tackles convex-submodular minimax problems in mixed continuous-discrete domains.
problem Convex-submodular minimax problems in mixed continuous-discrete domains.
method Introduces new notions of optimality and proposes iterative algorithms combining discrete and continuous optimization.
result Characterizes convergence rates, computational complexity, and quality of solutions for convex and monotone-submodular minimax 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.
Adversarial meta-learning computes Gamma-minimax estimators for vague prior knowledge.
problem Estimating parameters with vague prior knowledge.
method Adversarial meta-learning algorithms for Gamma-minimax estimators.
result Convergence guarantees and neural network class for selection.
The paper analyzes how optimization algorithms affect the generalization of minimax models.
problem The generalization performance of minimax models trained with different optimization algorithms.
method Analysis of gradient descent ascent (GDA) and proximal point method (PPM) algorithms under convex concave and non-convex non-concave settings.
result The PPM algorithm ensures a bounded excess risk in convex concave problems, while GDA's generalization depends on solving subproblems simultaneously.
New analysis improves understanding of bilevel optimization stability and generalization.
problem Understanding how well bilevel optimization algorithms generalize.
method Algorithmic stability arguments and generalization bounds for three bilevel minimax solvers.
result Precise trade-off between algorithmic stability, generalization gaps, and practical settings.