Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtragradient with player sampling for faster Nash equilibrium finding
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 provably exhibits a better rate of convergence than full extra-gradient for non-smooth convex games with noisy gradient oracle. We propose an additional variance reduction mechanism to obtain speed-ups in smooth convex games. Our approach makes extrapolation amenable to massive multiplayer settings, and brings empirical speed-ups, in particular when using a heuristic cyclic sampling scheme. Most importantly, it allows to train faster and better GANs and mixtures of GANs.
rate research
Read More
Optimization algorithms and Monte Carlo sampling algorithms have provided the computational foundations for the rapid growth in applications of statistical machine learning in recent years. There is, however, limited theoretical understanding of the relationships between these two kinds of methodology, and limited understanding of relative strengths and weaknesses. Moreover, existing results have been obtained primarily in the setting of convex functions (for optimization) and log-concave functions (for sampling). In this setting, where local properties determine global properties, optimization algorithms are unsurprisingly more efficient computationally than sampling algorithms. We instead examine a class of nonconvex objective functions that arise in mixture modeling and multi-stable systems. In this nonconvex setting, we find that the computational complexity of sampling algorithms scales linearly with the model dimension while that of optimization algorithms scales exponentially.
We present a direct reduction from k-player games to 2-player games that preserves approximate Nash equilibrium. Previously, the computational equivalence of computing approximate Nash equilibrium in k-player and 2-player games was established via an indirect reduction. This included a sequence of works defining the complexity class PPAD, identifying complete problems for this class, showing that computing approximate Nash equilibrium for k-player games is in PPAD, and reducing a PPAD-complete problem to computing approximate Nash equilibrium for 2-player games. Our direct reduction makes no use of the concept of PPAD, thus eliminating some of the difficulties involved in following the known indirect reduction.
Tensors are widely used to represent multiway arrays of data. The recovery of missing entries in a tensor has been extensively studied, generally under the assumption that entries are missing completely at random (MCAR). However, in most practical settings, observations are missing not at random (MNAR): the probability that a given entry is observed (also called the propensity) may depend on other entries in the tensor or even on the value of the missing entry. In this paper, we study the problem of completing a partially observed tensor with MNAR observations, without prior information about the propensities. To complete the tensor, we assume that both the original tensor and the tensor of propensities have low multilinear rank. The algorithm first estimates the propensities using a convex relaxation and then predicts missing values using a higher-order SVD approach, reweighting the observed tensor by the inverse propensities. We provide finite-sample error bounds on the resulting complete tensor. Numerical experiments demonstrate the effectiveness of our approach.
In this paper, we consider a Nash equilibrium seeking problem for a class of high-order multi-agent systems with unknown dynamics. Different from existing results for single integrators, we aim to steer the outputs of this class of uncertain high-order agents to the Nash equilibrium of some noncooperative game in a distributed manner. To overcome the difficulties brought by the high-order structure, unknown nonlinearities, and the regulation requirement, we first introduce a virtual player for each agent and solve an auxiliary noncooperative game for them. Then, we develop a distributed adaptive protocol by embedding this auxiliary game dynamics into some proper tracking controller for the original agent to resolve this problem. We also discuss the parameter convergence problem under certain persistence of excitation condition. The efficacy of our algorithms is verified by numerical examples.
In this paper we consider the problem of finding a Nash equilibrium (NE) via zeroth-order feedback information in games with merely monotone pseudogradient mapping. Based on hybrid system theory, we propose a novel extremum seeking algorithm which converges to the set of Nash equilibria in a semi-global practical sense. Finally, we present two simulation examples. The first shows that the standard extremum seeking algorithm fails, while ours succeeds in reaching NE. In the second, we simulate an allocation problem with fixed demand.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
