8,218 research outputs found
Stochastic Generalized Nash Equilibrium-Seeking in Merely Monotone Games
Full text linkWe solve the stochastic generalized Nash equilibrium (SGNE) problem in merely monotone games with expected value cost functions. Specifically, we present the first distributed SGNE-seeking algorithm for monotone games that require one proximal computation (e.g., one projection step) and one pseudogradient evaluation per iteration. Our main contribution is to extend the relaxed forward–backward operator splitting by the Malitsky (Mathematical Programming, 2019) to the stochastic case and in turn to show almost sure convergence to an SGNE when the expected value of the pseudogradient is approximated by the average over a number of random samples.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Team Sergio GrammaticoTeam Bart De Schutte
A distributed forward-backward algorithm for stochastic generalized Nash equilibrium seeking
No full textWe consider the stochastic generalized Nash equilibrium problem (SGNEP) with expected-value cost functions. Inspired by Yi and Pavel (2019), we propose a distributed generalized Nash equilibrium seeking algorithm based on the preconditioned forward-backward operator splitting for SGNEPs, where, at each iteration, the expected value of the pseudogradient is approximated via a number of random samples. Our main contribution is to show almost sure convergence of the proposed algorithm if the pseudogradient mapping is restricted (monotone and) cocoercive.Accepted Author ManuscriptTeam Bart De Schutte
Stochastic generalized Nash equilibrium seeking under partial-decision information
Full text linkWe consider for the first time a stochastic generalized Nash equilibrium problem, i.e., with expected-value cost functions and joint feasibility constraints, under partial-decision information, meaning that the agents communicate only with some trusted neighbors. We propose several distributed algorithms for network games and aggregative games that we show being special instances of a preconditioned forward–backward splitting method. We prove that the algorithms converge to a generalized Nash equilibrium when the forward operator is restricted cocoercive by using the stochastic approximation scheme with variance reduction to estimate the expected value of the pseudogradient.Team Sergio GrammaticoTeam Bart De Schutte
Training Generative Adversarial Networks via Stochastic Nash Games
No full textGenerative adversarial networks (GANs) are a class of generative models with two antagonistic neural networks: a generator and a discriminator. These two neural networks compete against each other through an adversarial process that can be modeled as a stochastic Nash equilibrium problem. Since the associated training process is challenging, it is fundamental to design reliable algorithms to compute an equilibrium. In this article, we propose a stochastic relaxed forward-backward (SRFB) algorithm for GANs, and we show convergence to an exact solution when an increasing number of data is available. We also show convergence of an averaged variant of the SRFB algorithm to a neighborhood of the solution when only a few samples are available. In both cases, convergence is guaranteed when the pseudogradient mapping of the game is monotone. This assumption is among the weakest known in the literature. Moreover, we apply our algorithm to the image generation problem.</p
On Variance-Reduced Extragradient Methods for Stochastic Generalized Nash Equilibrium Problems
Full text linkWe study variance reduction schemes for stochastic generalized Nash equilibrium problems. Specifically, we consider two instances of the extragradient algorithm to find a Nash equilibrium and show their convergence under weaker assumptions than the literature. In the particular case where we can write the cost function as a finite sum, we also propose a novel approximation scheme that sensibly lowers the computational burden. Numerical simulations suggest that the performance of the new approximation scheme can improve the computations also in the fully stochastic (infinite) case
On Distributionally Robust Generalized Nash Games Defined over the Wasserstein Ball
Full text linkIn this paper we propose an exact, deterministic, and fully continuous reformulation of generalized Nash games characterized by the presence of soft coupling constraints in the form of distributionally robust (DR) joint chance-constraints (CCs). We first rewrite the underlying uncertain game introducing mixed-integer variables to cope with DR–CCs, where the integer restriction actually amounts to a binary decision vector only, and then extend it to an equivalent deterministic problem with one additional agent handling all those introduced variables. Successively we show that, by means of a careful choice of tailored penalty functions, the extended deterministic game with additional agent can be equivalently recast in a fully continuous setting
A damped forward–backward algorithm for stochastic generalized Nash equilibrium seeking
Full text linkWe consider a stochastic generalized Nash equilibrium problem (GNEP) with expected-value cost functions. Inspired by Yi and Pavel (Automatica, 2019), we propose a distributed GNE seeking algorithm by exploiting the forward- backward operator splitting and a suitable preconditioning matrix. Specifically, we apply this method to the stochastic GNEP, where, at each iteration, the expected value of the pseudo-gradient is approximated via a number of random samples. Our main contribution is to show almost sure convergence of our proposed algorithm if the sample size grows large enough
Forward–Backward algorithms for stochastic Nash equilibrium seeking in restricted strongly and strictly monotone games
Full text linkWe study stochastic Nash equilibrium problems with expected valued cost functions whose pseudogradient satisfies restricted monotonicity properties which hold only with respect to the solution. We propose a forward-backward algorithm and prove its convergence under restricted strong monotonicity, restricted strict monotonicity and restricted cocoercivity of the pseudogradient mapping. To approximate the expected value, we use either a finite number of samples and a vanishing step size or an increasing number of samples with a constant step. Numerical simulations show that our proposed algorithm might be faster than the available algorithms
A game–theoretic approach for Generative Adversarial Networks
No full textGenerative adversarial networks (GANs) are a class of generative models, known for producing accurate samples. The key feature of GANs is that there are two antagonistic neural networks: the generator and the discriminator. The main bottleneck for their implementation is that the neural networks are very hard to train. One way to improve their performance is to design reliable algorithms for the adversarial process. Since the training can be cast as a stochastic Nash equilibrium problem, we rewrite it as a variational inequality and introduce an algorithm to compute an approximate solution. Specifically, we propose a stochastic relaxed forward-backward algorithm for GANs. We prove that when the pseudogradient mapping of the game is monotone, we have convergence to an exact solution or in a neighbourhood of it
Distributed projected–reflected–gradient algorithms for stochastic generalized Nash equilibrium problems
Full text linkWe consider the stochastic generalized Nash equilibrium problem (SGNEP) with joint feasibility constraints and expected-value cost functions. We propose a distributed stochastic projected reflected gradient algorithm and show its almost sure convergence when the pseudogradient mapping is monotone and the solution is unique. The algorithm is based on monotone operator splitting methods tailored for SGNEPs when the expected-value pseudogradient mapping is approximated at each iteration via an increasing number of samples of the random variable. Finally, we show that a preconditioned variant of our proposed algorithm has convergence guarantees when the pseudogradient mapping is cocoercive
- …
