Publications related to Learning Generalized Nash Equilibria in a Class of Convex Games

A first-order primal-dual method with adaptivity to local smoothness

We consider the problem of finding a saddle point for the convex-concave objective

\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)

, where

f

is a convex function with locally Lipschitz gradient and

g

is convex and possibly non-smooth. We propose an ...

2021

Bandit Online Learning of Nash Equilibria in Monotone Games

Maryam Kamgarpour

We address online bandit learning of Nash equilibria in multi-agent convex games. We propose an algorithm whereby each agent uses only obtained values of her cost function at each joint played action, lacking any information of the functional form of her c ...

2021

Fast Projection Onto Convex Smooth Constraints

Maryam Kamgarpour, Andreas Krause, Ilnura Usmanova

The Euclidean projection onto a convex set is an important problem that arises in numerous constrained optimization tasks. Unfortunately, in many cases, computing projections is computationally demanding. In this work, we focus on projection problems where ...

PMLR2021

Mixed Nash Equilibria in the Adversarial Examples Game

Rafaël Benjamin Pinot

This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually al ...

2021

Forward-reflected-backward method with variance reduction

Volkan Cevher, Ahmet Alacaoglu

We propose a variance reduced algorithm for solving monotone variational inequalities. Without assuming strong monotonicity, cocoercivity, or boundedness of the domain, we prove almost sure convergence of the iterates generated by the algorithm to a soluti ...

2021

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Ali H. Sayed, Kun Yuan

This paper introduces a new algorithm for consensus optimization in a multi-agent network, where all agents collaboratively find a minimizer for the sum of their private functions. All decentralized algorithms rely on communications between adjacent nodes. ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

On the asymptotic behavior of the solutions to parabolic variational inequalities

Maria Colombo

We consider various versions of the obstacle and thin-obstacle problems, we interpret them as variational inequalities, with non-smooth constraint, and prove that they satisfy a new constrained Lojasiewicz inequality. The difficulty lies in the fact that, ...

2020

Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

Shaul Nadav Hallak

This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to t ...

SPRINGER/PLENUM PUBLISHERS2020

Convergence without Convexity: Sampling, Optimization, and Games

Ya-Ping Hsieh

Many important problems in contemporary machine learning involve solving highly non- convex problems in sampling, optimization, or games. The absence of convexity poses significant challenges to convergence analysis of most training algorithms, and in some ...

EPFL2020

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Justin Dean Ward

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local ...

SIAM PUBLICATIONS2020

Learning Generalized Nash Equilibria in a Class of Convex Games

Graph Chatbot

Chat with Graph Search

A first-order primal-dual method with adaptivity to local smoothness

Bandit Online Learning of Nash Equilibria in Monotone Games

Fast Projection Onto Convex Smooth Constraints

Mixed Nash Equilibria in the Adversarial Examples Game

Forward-reflected-backward method with variance reduction

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

On the asymptotic behavior of the solutions to parabolic variational inequalities

Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

Convergence without Convexity: Sampling, Optimization, and Games

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

A first-order primal-dual method with adaptivity to local smoothness

Bandit Online Learning of Nash Equilibria in Monotone Games

Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

Mixed Nash Equilibria in the Adversarial Examples Game

On the asymptotic behavior of the solutions to parabolic variational inequalities

Convergence without Convexity: Sampling, Optimization, and Games

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Fast Projection Onto Convex Smooth Constraints

Forward-reflected-backward method with variance reduction

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization