arXiv research

The extragradient method accelerates convergence in complex game dynamics.

The extragradient method fails for hypomonotone variational inequalities.

This paper advances extragradient methods for solving inclusions under co-hypomonotonicity.

Improved analysis of extragradient methods for structured VIPs.

We analyze Riemannian accelerated methods using a new framework.

Paper improves a method for fast global and local convergence in optimization.

Survey on extragradient methods for solving nonlinear equations and inclusions.

Two accelerated extragradient methods converge at $O(1/k)$ rate for co-hypomonotone inclusions.

Paper develops fast method for computing optimal transport.

Paper generalizes extragradient methods for solving equations and inclusions with improved convergence rates.

Paper proves Sion's theorem in geodesic spaces and develops a Riemannian extragradient method.

Improved convergence for VIPs with SEG-RR, a variant of SEG with random reshuffling.

Improved SEG method converges to Nash equilibrium in bilinear games.

New method solves nonsmooth low-rank matrix optimization problems efficiently.

We study the effect of the stochastic gradient noise on the training of generative adversarial networks (GANs) and show that it can prevent the convergence of standard game optimization methods, while the batch version converges. We address this issue with a novel stochastic variance-reduced extragradient (SVRE) optimi…

Paper proposes a quasi-Newton method for nonlinear equations with global convergence guarantees.

New method solves convex optimization faster than NAG.

In this paper we propose a primal-dual proximal extragradient algorithm to solve the generalized Dantzig selector (GDS) estimation problem, based on a new convex-concave saddle-point (SP) reformulation. Our new formulation makes it possible to adopt recent developments in saddle-point optimization, to achieve the optim…

ARBITER learns SPX-VIX term structures without arbitrage constraints.

Riemannian algorithms converge at Euclidean rates for geodesically convex-concave problems.

In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processi…

New algorithm solves structured nonconvex-nonconcave min-max problems.

We consider a wide range of regularized stochastic minimization problems with two regularization terms, one of which is composed with a linear function. This optimization model abstracts a number of important applications in artificial intelligence and machine learning, such as fused Lasso, fused logistic regression, a…

New algorithms reduce variance in solving complex mathematical problems.

Data-driven modeling increasingly requires to find a Nash equilibrium in multi-player games, e.g. when training GANs. In this paper, we analyse a new extra-gradient method for Nash equilibrium finding, that performs gradient extrapolations and updates on a random subset of players at each iteration. This approach prova…

Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available for saddle-point optimization has focused on the offline setting. In this paper, we study nonstationar…

We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimi…

In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last…

This paper analyzes OGDA and EG methods for nonconvex minimax problems.

Two new algorithms solve privacy-constrained SVI and SSP problems.

We consider differentiable games where the goal is to find a Nash equilibrium. The machine learning community has recently started using variants of the gradient method (GD). Prime examples are extragradient (EG), the optimistic gradient method (OG) and consensus optimization (CO), which enjoy linear convergence in cas…

Optimal transportation, or computing the Wasserstein or ``earth mover's'' distance between two distributions, is a fundamental primitive which arises in many learning and statistical settings. We give an algorithm which solves this problem to additive $ε$ with $\tilde{O}(1/ε)$ parallel depth, and $\tilde{O}\left(n^2/ε\…

A new algorithm improves GAN training stability and performance.

New quasi-Newton method guarantees global superlinear convergence.

New insights into stochastic methods for solving variational inequalities.

A new method uses extrapolation to train deep learning models with larger batch sizes.

New tensor recovery method improves efficiency under strict complementarity.