論文の概要: A New Approach to Drifting Games, Based on Asymptotically Optimal Potentials

• arxiv url: http://arxiv.org/abs/2207.11405v1
• Date: Sat, 23 Jul 2022 03:55:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-26 15:46:34.728216
• Title: A New Approach to Drifting Games, Based on Asymptotically Optimal Potentials
• Title（参考訳）: 漸近的最適ポテンシャルに基づくドリフトゲームに対する新しいアプローチ
• Authors: Zhilei Wang and Robert V. Kohn
• Abstract要約: 我々は,エキスパートアドバイザによる予測やヘッジゲームなど,多種多様な応用を持つ2人ゲームの開発を行っている。 我々のアプローチは、関連する偏微分方程式(PDE)を解くことによって、肛門の最適電位を推定することを伴う。 我々は、時間ステップの数の負のパワーのような差がスケールする最終時間損失に対して、上限と下限を証明した。
• 参考スコア（独自算出の注目度）: 1.9798034349981162
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a new approach to drifting games, a class of two-person games with many applications to boosting and online learning settings, including Prediction with Expert Advice and the Hedge game. Our approach involves (a) guessing an asymptotically optimal potential by solving an associated partial differential equation (PDE); then (b) justifying the guess, by proving upper and lower bounds on the final-time loss whose difference scales like a negative power of the number of time steps. The proofs of our potential-based upper bounds are elementary, using little more than Taylor expansion. The proofs of our potential-based lower bounds are also rather elementary, combining Taylor expansion with probabilistic or combinatorial arguments. Most previous work on asymptotically optimal strategies has used potentials obtained by solving a discrete dynamic programming principle; the arguments are complicated by their discrete nature. Our approach is facilitated by the fact that the potentials we use are explicit solutions of PDEs; the arguments are based on basic calculus. Not only is our approach more elementary, but we give new potentials and derive corresponding upper and lower bounds that match each other in the asymptotic regime.
• Abstract（参考訳）: 我々は,エキスパートアドバイスによる予測やヘッジゲームなど,学習環境の強化やオンライン化に多くの応用を施した2人制ゲームであるドリフトゲームに対する新しいアプローチを開発した。 我々のアプローチは (a)関連する偏微分方程式(PDE)を解くことで漸近的最適ポテンシャルを推定する。 (b)時間ステップ数の負の力のように差がスケールする最終時間損失の上限と下限を証明し、推測を正当化すること。 ポテンシャルベースの上界の証明は、テイラー展開をほとんど使用せずに、初等的である。 我々のポテンシャルに基づく下限の証明はむしろ初等的であり、テイラー展開と確率的あるいは組合せ的議論を組み合わせる。 漸近的最適戦略に関するこれまでのほとんどの研究は、離散動的プログラミングの原理を解くことによって得られるポテンシャルを用いてきた。 我々のアプローチは、私たちが使っているポテンシャルがPDEの明示的な解であるという事実によって促進される。 我々のアプローチはより初等的であるだけでなく、新しいポテンシャルを与え、漸近的体制において互いに一致する対応する上下境界を導出する。

関連論文リスト

• Asymptotic and Non-Asymptotic Convergence of AdaGrad for Non-Convex Optimization via Novel Stopping Time-based Analysis [17.34603953600226]
  我々はAdaの革新的な包括的分析を導入し、文献の既存のギャップを埋める。 AdaGradの期待は、ほぼ確実に、平均的にもたらされます。 また,既存の結果と無関係に予測された平均非a-bpt-d勾配を実証した。
  論文  参考訳（メタデータ） (2024-09-08T08:29:51Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples [1.0650780147044159]
  スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。 本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
  論文  参考訳（メタデータ） (2022-03-25T20:56:07Z)
• PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
  部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。 我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。 これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
  論文  参考訳（メタデータ） (2022-01-19T22:21:21Z)
• Learning a Single Neuron with Bias Using Gradient Descent [53.15475693468925]
  単一ニューロンをバイアス項で学習する基本的な問題について検討する。 これはバイアスのないケースとは大きく異なり、より難しい問題であることを示す。
  論文  参考訳（メタデータ） (2021-06-02T12:09:55Z)
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality [25.627939043735683]
  我々は後悔を最小限に抑えるために構造化された包帯について研究する。 本稿では,有限仮説に焦点をあて,有界後悔を楽しみながら最適性を達成できるかを問う。
  論文  参考訳（メタデータ） (2020-06-15T20:46:52Z)
• Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method [10.819408603463426]
  ミニマックスサドル点降下器は、機械の傾きと信号処理において幅広い用途に現れる。 単純な多段階LA-Ascentアルゴリズムは文献上の既存アルゴリズムよりも強いことを示す。
  論文  参考訳（メタデータ） (2020-03-18T08:38:34Z)

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

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