Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA relaxed-inertial forward-backward-forward algorithm for Stochastic Generalized Nash equilibrium seeking
235
0
0.0
(
0
)
Added by
Mathias Staudigl
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we propose a new operator splitting algorithm for distributed Nash equilibrium seeking under stochastic uncertainty, featuring relaxation and inertial effects. Our work is inspired by recent deterministic operator splitting methods, designed for solving structured monotone inclusion problems. The algorithm is derived from a forward-backward-forward scheme for solving structured monotone inclusion problems featuring a Lipschitz continuous and monotone game operator. To the best of our knowledge, this is the first distributed (generalized) Nash equilibrium seeking algorithm featuring acceleration techniques in stochastic Nash games without assuming cocoercivity. Numerical examples illustrate the effect of inertia and relaxation on the performance of our proposed algorithm.
rate research
Read More
We consider monotone inclusions defined on a Hilbert space where the operator is given by the sum of a maximal monotone operator $T$ and a single-valued monotone, Lipschitz continuous, and expectation-valued operator $V$. We draw motivation from the seminal work by Attouch and Cabot on relaxed inertial methods for monotone inclusions and present a stochastic extension of the relaxed inertial forward-backward-forward (RISFBF) method. Facilitated by an online variance reduction strategy via a mini-batch approach, we show that (RISFBF) produces a sequence that weakly converges to the solution set. Moreover, it is possible to estimate the rate at which the discrete velocity of the stochastic process vanishes. Under strong monotonicity, we demonstrate strong convergence, and give a detailed assessment of the iteration and oracle complexity of the scheme. When the mini-batch is raised at a geometric (polynomial) rate, the rate statement can be strengthened to a linear (suitable polynomial) rate while the oracle complexity of computing an $epsilon$-solution improves to $O(1/epsilon)$. Importantly, the latter claim allows for possibly biased oracles, a key theoretical advancement allowing for far broader applicability. By defining a restricted gap function based on the Fitzpatrick function, we prove that the expected gap of an averaged sequence diminishes at a sublinear rate of $O(1/k)$ while the oracle complexity of computing a suitably defined $epsilon$-solution is $O(1/epsilon^{1+a})$ where $a>1$. Numerical results on two-stage games and an overlapping group Lasso problem illustrate the advantages of our method compared to stochastic forward-backward-forward (SFBF) and SA schemes.
We introduce a relaxed inertial forward-backward-forward (RIFBF) splitting algorithm for approaching the set of zeros of the sum of a maximally monotone operator and a single-valued monotone and Lipschitz continuous operator. This work aims to extend Tsengs forward-backward-forward method by both using inertial effects as well as relaxation parameters. We formulate first a second order dynamical system which approaches the solution set of the monotone inclusion problem to be solved and provide an asymptotic analysis for its trajectories. We provide for RIFBF, which follows by explicit time discretization, a convergence analysis in the general monotone case as well as when applied to the solving of pseudo-monotone variational inequalities. We illustrate the proposed method by applications to a bilinear saddle point problem, in the context of which we also emphasize the interplay between the inertial and the relaxation parameters, and to the training of Generative Adversarial Networks (GANs).
We propose and analyze the convergence of a novel stochastic algorithm for solving monotone inclusions that are the sum of a maximal monotone operator and a monotone, Lipschitzian operator. The propose algorithm requires only unbiased estimations of the Lipschitzian operator. We obtain the rate $mathcal{O}(log(n)/n)$ in expectation for the strongly monotone case, as well as almost sure convergence for the general case. Furthermore, in the context of application to convex-concave saddle point problems, we derive the rate of the primal-dual gap. In particular, we also obtain $mathcal{O}(1/n)$ rate convergence of the primal-dual gap in the deterministic setting.
In this paper, we aim to develop distributed continuous-time algorithms under directed graphs to seek the Nash equilibrium of a noncooperative game. Motivated by the existing consensus-based designs in Gadjov and Pavel (2019), we present a distributed algorithm with a proportional gain for weight-balanced directed graphs. By further embedding a distributed estimator of the left eigenvector associated with zero eigenvalue of the graph Laplacian, we extend it to the case with arbitrary strongly connected directed graphs having possible unbalanced weights. In both cases, the Nash equilibrium is proven to be exactly reached with an exponential convergence rate.
In this paper, we consider a generalized forward-backward splitting (G-FBS) operator for solving the monotone inclusions, and analyze its nonexpansive properties in a context of arbitrary variable metric. Then, for the associated fixed-point iterations (i.e. the G-FBS algorithms), the global ergodic and pointwise convergence rates of metric distance are obtained from the nonexpansiveness. The convergence in terms of objective function value is also investigated, when the G-FBS operator is applied to a minimization problem. A main contribution of this paper is to show that the G-FBS operator provides a simplifying and unifying framework to model and analyze a great variety of operator splitting algorithms, where the convergence behaviours can be easily described by the fixed-point construction of this simple operator.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
