Provable Computational and Statistical Guarantees for Efficient Learning of Continuous-Action Graphical Games
In this paper, we study the problem of learning the set of pure strategy Nash equilibria and the exact structure of a continuous-action graphical game with quadratic payoffs by observing a small set of perturbed equilibria. A continuous-action graphical game can possibly have an uncountable set of Nash euqilibria. We propose a $\ell_{12}-$ block regularized method which recovers a graphical game, whose Nash equilibria are the $\epsilon$-Nash equilibria of the game from which the data was generated (true game). Under a slightly stringent condition on the parameters of the true game, our method recovers the exact structure of the graphical game. Our method has a logarithmic sample complexity with respect to the number of players. It also runs in polynomial time.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Provable Sample Complexity Guarantees for Learning of Continuous-Action Graphical Games with Nonparametric Utilities
In this paper, we study the problem of learning the exact structure of continuous-action games with non-parametric utility functions. We propose an $\ell_1$ regularized method which encourages sparsity of the coefficient…
Fair Classification with Noisy Protected Attributes: A Framework with Provable Guarantees
We present an optimization framework for learning a fair classifier in the presence of noisy perturbations in the protected attributes. Compared to prior work, our framework can be employed with a very general class of l…
FairnessGeneral ClassificationTighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time
We provide statistical and computational analysis of sparse Principal Component Analysis (PCA) in high dimensions. The sparse PCA problem is highly nonconvex in nature. Consequently, though its global solution attains th…
Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees
*Automated circuit discovery* is a central tool in mechanistic interpretability for identifying the internal components of neural networks responsible for specific behaviors. While prior methods have made significant pro…
What, Indeed, is an Achievable Provable Guarantee for Learning-Enabled Safety Critical Systems
Machine learning has made remarkable advancements, but confidently utilising learning-enabled components in safety-critical domains still poses challenges. Among the challenges, it is known that a rigorous, yet practical…