Session: Deterministic and Stochastic Methods for Optimization and Games- Part I
Chair: Gesualdo Scutari
Cluster: Multi-agent Optimization and Games
Talk 1: On the computation of quasi-Nash equilibria under uncertainty
Speaker: Zhuoyu Xiao
Abstract: Motivated by applications in network congestion games and Cournot games, we consider the computation of either Nash or quasi-Nash equilibria in static stochastic noncooperative games afflicted by either non convexity or non-monotonicity. We consider sampled variants of gradient and best-response and show that under specified conditions, both schemes generate sequences which converge to quasi-Nash equilibria almost surely. We also provide non-asymptotic rate statements in some cases. Time permitting, we briefly discuss distributed extensions in networked settings of both schemes. Numerical experiments are also provided to support our theoretical results.
Talk 2: Iteratively Regularized Gradient Tracking Methods for Distributed Optimal Equilibrium Seeking
Speaker: Farzad Yousefian
Abstract: We consider a class of distributed constrained optimization problems where the constraint set is characterized by the solution set of a distributed monotone variational inequality problem. This problem is motivated by the need for estimation of the efficiency of equilibria in Nash games. First, we consider solving this problem over directed networks. We develop an iteratively regularized distributed gradient tracking method where the agents employ a push-pull protocol to communicate over the network. Second, we consider a stochastic variant of this problem over undirected networks and develop an iteratively regularized distributed stochastic gradient tracking method. For both algorithms, we establish the convergence of the generated iterates by the agents to the optimal equilibrium and derive new convergence rate statements. We validate the two proposed methods and present preliminary numerical results for computing the optimal equilibrium in a Cournot competition.
Talk 3: Clipped-Stochastic Methods for Generalized Smooth Stochastic Variational Inequalities
Speaker: Angelia Nedich
Abstract: We focus on solving a stochastic variational inequality (SVI) problem under relaxed smoothness assumption for a class of structured non-monotone operators. The SVI problem has attracted significant interest in the machine learning community due to its immediate application to adversarial training and multi-agent reinforcement learning. In many such applications, the resulting operators do not satisfy the smoothness assumption. To address this issue, we focus on the generalized smoothness assumption and consider two well-known stochastic methods with clipping, namely, projection and Korpelevich. For these clipped methods, we provide the first almost-sure convergence results without making any assumptions on the boundedness of either the stochastic operator or the stochastic samples. Furthermore, we provide the first almost-sure convergence results and in-expectation convergence rate results for these methods under a relaxed smoothness assumption.
