The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms
- URL: http://arxiv.org/abs/2310.08066v1
- Date: Thu, 12 Oct 2023 06:30:12 GMT
- Title: The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms
- Authors: Xiaotie Deng, Dongchen Li, Hanyu Li
- Abstract summary: This work provides an automatic method for approximation analysis on a well-studied problem in theoretical computer science.
We observe that such algorithms can be reformulated into a search-and-mix paradigm.
By doing so, we are able to fully automate the procedure of designing and analyzing the mixing phase.
- Score: 9.037333651025351
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: AI in Math deals with mathematics in a constructive manner so that reasoning
becomes automated, less laborious, and less error-prone. For algorithms, the
question becomes how to automate analyses for specific problems. For the first
time, this work provides an automatic method for approximation analysis on a
well-studied problem in theoretical computer science: computing approximate
Nash equilibria in two-player games. We observe that such algorithms can be
reformulated into a search-and-mix paradigm, which involves a search phase
followed by a mixing phase. By doing so, we are able to fully automate the
procedure of designing and analyzing the mixing phase. For example, we
illustrate how to perform our method with a program to analyze the
approximation bounds of all the algorithms in the literature. Same
approximation bounds are computed without any hand-written proof. Our automatic
method heavily relies on the LP-relaxation structure in approximate Nash
equilibria. Since many approximation algorithms and online algorithms adopt the
LP relaxation, our approach may be extended to automate the analysis of other
algorithms.
Related papers
- EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
We present EKM: a novel algorithm for solving this problem exactly with worst-case $Oleft(NK+1right)$ complexity.
EKM is developed according to recent advances in transformational programming and generation, using formal program steps.
We show that the wall-clock run time of our algorithm matches the worst-case time complexity analysis on synthetic datasets.
arXiv Detail & Related papers (2024-05-16T15:11:37Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards.
For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
arXiv Detail & Related papers (2023-08-23T08:38:53Z) - Dual Algorithmic Reasoning [9.701208207491879]
We propose to learn algorithms by exploiting duality of the underlying algorithmic problem.
We demonstrate that simultaneously learning the dual definition of these optimisation problems in algorithmic learning allows for better learning.
We then validate the real-world utility of our dual algorithmic reasoner by deploying it on a challenging brain vessel classification task.
arXiv Detail & Related papers (2023-02-09T08:46:23Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs)
Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method.
We provide nonasymptotic theoretical guarantees for these algorithms.
arXiv Detail & Related papers (2022-04-07T00:11:05Z) - Towards algorithm-free physical equilibrium model of computing [0.0]
A new model of computing is proposed to replace the sequential paradigm of algorithms with inherent parallelism of physical processes.
We construct physical systems whose equilibrium states correspond to the desired solutions and let them evolve to search for the solutions.
The main requirements of the model are identified and quantum circuits are proposed for its potential implementation.
arXiv Detail & Related papers (2021-11-30T09:48:39Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification.
We design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors.
arXiv Detail & Related papers (2021-11-09T02:33:36Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric.
We show that in practice, automated search can find substantial improvements to the initial program.
arXiv Detail & Related papers (2021-09-14T20:52:55Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
Dynamic programming (DP) is an algorithmic design paradigm for the efficient, exact solution of intractable, problems.
This paper presents a rigorous algebraic formalism for systematically deriving DP algorithms, based on semiring.
arXiv Detail & Related papers (2021-07-05T00:51:02Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
We propose two single-timescale single-loop algorithms that require only one data point each step.
Our results are expressed in a form of simultaneous primal and dual side convergence.
arXiv Detail & Related papers (2020-08-23T20:36:49Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.