論文の概要: The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms

• arxiv url: http://arxiv.org/abs/2310.08066v1
• Date: Thu, 12 Oct 2023 06:30:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-15 11:09:35.441738
• Title: The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms
• Title（参考訳）: 近似nash平衡アルゴリズムにおける探索・混合パラダイム
• Authors: Xiaotie Deng, Dongchen Li, Hanyu Li
• Abstract要約: この研究は、理論計算機科学におけるよく研究された問題に対する近似解析の自動手法を提供する。 我々は,このようなアルゴリズムを探索・混合パラダイムに再構成できることを観察する。 これにより、混合相を設計・解析する手順を完全に自動化することができる。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 数学におけるAIは、推論が自動化され、手間がかかり、エラーが発生しにくいように、構成的な方法で数学を扱う。 アルゴリズムでは、特定の問題に対する分析を自動化する方法が問題となる。 本研究は, 理論計算機科学におけるよく研究された問題の近似解析手法である2人プレイゲームにおける近似ナッシュ平衡の計算法を初めて提供する。 このようなアルゴリズムを探索・混合パラダイムに再構成し,探索相と混合相を伴い得ることを観察した。 これにより、混合相を設計・解析する手順を完全に自動化することができる。 例えば、文献中の全てのアルゴリズムの近似境界を分析するプログラムを用いて、この手法をどのように実行するかを示す。 同じ近似境界は手書きの証明なしで計算される。 我々の自動手法は近似ナッシュ平衡におけるLP緩和構造に大きく依存している。 多くの近似アルゴリズムとオンラインアルゴリズムはLP緩和を採用するため、他のアルゴリズムの分析を自動化するために我々のアプローチを拡張することができる。

関連論文リスト

• EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
  EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。 EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。 我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
  論文  参考訳（メタデータ） (2024-05-16T15:11:37Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Dual Algorithmic Reasoning [9.701208207491879]
  本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。 アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。 次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
  論文  参考訳（メタデータ） (2023-02-09T08:46:23Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Towards algorithm-free physical equilibrium model of computing [0.0]
  新しい計算モデルが提案され、アルゴリズムの逐次パラダイムを物理プロセスの固有の並列性に置き換える。 平衡状態が所望の解に対応する物理系を構築し、解を探すためにそれらを進化させる。 モデルの主な要件は特定され、潜在的な実装のために量子回路が提案される。
  論文  参考訳（メタデータ） (2021-11-30T09:48:39Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-09-14T20:52:55Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。