Drago optimizes DRO problems with faster convergence.
problem Distributionally robust optimization with closed, convex uncertainty sets.
method Primal-dual coupled variance reduction algorithm with cyclic and randomized updates.
result Achieves state-of-the-art linear convergence rate on strongly convex-strongly concave problems.
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.
PURE-CD algorithm proves complexity bounds for convex-concave problems.
problem Solving convex-concave min-max problems with bilinear coupling.
method Primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD).
result Complexity bounds match or improve existing results for dense and sparse problems.
In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving…
A generalized optimistic method for saddle point problems with improved complexity.
problem Solving convex-concave saddle point problems efficiently.
method Proposes a generalized optimistic method that includes the optimistic gradient method as a special case, handling constrained saddle point problems with composite objective functions and arbitrary norms.
result Best-known global iteration complexity bounds for first-, second-, and higher-order methods.
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.
Negative momentum accelerates convergence in minimax games but at a suboptimal rate.
problem The convergence rate of negative momentum in minimax games is suboptimal.
method Extending variational inequality formulation, connecting momentum method with Chebyshev polynomials.
result Negative momentum accelerates convergence locally but at a suboptimal rate.
Random extrapolation speeds up coordinate descent for sparse and dense data.
problem Efficiently solving primal-dual coordinate descent for sparse and dense data.
method Adapts to sparsity and uses large step sizes for dense data, proving linear convergence under metric subregularity.
result Linear convergence under metric subregularity and optimal sublinear convergence rates in general convex-concave problems.
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.
GenFlow optimizes faster, avoiding saddle points in fixed time.
problem Designing efficient optimization algorithms for convex and non-convex functions.
method Introduces GenFlow and momentum variants with fixed-time convergence guarantees.
result GenFlow and momentum variants converge to optimal solutions in fixed time for PL functions and evade saddle points uniformly.
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
problem Minimax optimization convergence rate comparison
method Alternating Gradient Descent-Ascent (Alt-GDA) vs. Simultaneous Gradient Descent-Ascent (Sim-GDA)
result Alt-GDA achieves near-optimal local convergence rate for strongly convex-strongly concave problems, while Sim-GDA converges slower.
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.
Study on convergence of Langevin dynamics for zero-sum games in probability distributions.
problem Analyzing convergence of Langevin dynamics for zero-sum games in probability distributions.
method Proved exponential and biased convergence guarantees for mean-field and finite-particle min-max Langevin dynamics.
result Explicit iteration complexity for finite-particle algorithms to approximate equilibrium distributions.
Sampling without replacement speeds up optimization in minimax problems.
problem Optimizing minimax problems with faster convergence rates.
method Analysis of gradient descent ascent and proximal point method with two sampling strategies.
result Sampling without replacement leads to faster convergence rates in minimax optimization.
New algorithm reduces communication in federated learning.
problem Communication inefficiency in distributed federated learning.
method Distributionally Robust Federated Averaging (DRFA) with snapshotting scheme.
result DRFA achieves efficient convergence in various settings.
Optimal multistage method solves noisy minimax problems.
problem Minimizing/maximizing in noisy conditions with smooth and strongly convex-strongly concave settings.
method Multistage Stochastic Gradient Descent Ascent (M-GDA) and Optimistic Gradient Descent Ascent (M-OGDA).
result Achieves optimal linear decay rate with respect to initial error and condition number.
Improved convergence rates for saddle-point optimization algorithms.
problem Understanding last-iterate convergence rates for saddle-point optimization algorithms in constrained settings.
method Expanding the understanding of last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) in the constrained setting.
result Linear last-iterate convergence achieved with a universal constant learning rate for OMWU in bilinear games over the simplex.
New framework for DP-SMO with near-optimal privacy-loss trade-off.
problem Optimal trade-off between privacy and population loss in DP-SMO.
method General framework using Phased-ERM method and black-box optimization.
result Near-linear time algorithms with near-optimal guarantees.
Epoch-GDA achieves optimal convergence rate for SCSC min-max problems.
problem Solving stochastic min-max problems with strong convexity and strong concavity.
method Epoch-wise stochastic gradient descent ascent method (Epoch-GDA) without additional assumptions.
result Achieves the optimal rate of O(1/T) for the duality gap of general SCSC min-max problems.