論文の概要: Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games
- arxiv url: http://arxiv.org/abs/2304.12768v2
- Date: Thu, 2 Nov 2023 09:02:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-03 17:58:06.122832
- Title: Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games
- Title（参考訳）: ゼロサム行列ゲームにおける学習の1次クエリ複雑度(近似)ナッシュ平衡のキャラクタリゼーション
- Authors: H\'edi Hadiji (L2S), Sarah Sachs (UvA), Tim van Erven (UvA), Wouter M.
Koolen (CWI)
- Abstract要約: 正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。
我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the first-order query model for zero-sum $K\times K$ matrix games, players
observe the expected pay-offs for all their possible actions under the
randomized action played by their opponent. This classical model has received
renewed interest after the discovery by Rakhlin and Sridharan that
$\epsilon$-approximate Nash equilibria can be computed efficiently from
$O(\frac{\ln K}{\epsilon})$ instead of $O(\frac{\ln K}{\epsilon^2})$ queries.
Surprisingly, the optimal number of such queries, as a function of both
$\epsilon$ and $K$, is not known. We make progress on this question on two
fronts. First, we fully characterise the query complexity of learning exact
equilibria ($\epsilon=0$), by showing that they require a number of queries
that is linear in $K$, which means that it is essentially as hard as querying
the whole matrix, which can also be done with $K$ queries. Second, for
$\epsilon > 0$, the current query complexity upper bound stands at
$O(\min(\frac{\ln(K)}{\epsilon} , K))$. We argue that, unfortunately, obtaining
a matching lower bound is not possible with existing techniques: we prove that
no lower bound can be derived by constructing hard matrices whose entries take
values in a known countable set, because such matrices can be fully identified
by a single query. This rules out, for instance, reducing to an optimization
problem over the hypercube by encoding it as a binary payoff matrix. We then
introduce a new technique for lower bounds, which allows us to obtain lower
bounds of order $\tilde\Omega(\log(\frac{1}{K\epsilon})$ for any $\epsilon \leq
1 / (cK^4)$, where $c$ is a constant independent of $K$. We further discuss
possible future directions to improve on our techniques in order to close the
gap with the upper bounds.
- Abstract（参考訳）: 0-sum$K\times K$Matrixゲームに対する1次クエリモデルでは、プレイヤーは、対戦相手のランダム化アクションの下で、可能なすべてのアクションに対する期待された支払いを観察する。
この古典的モデルは、RakhlinとSridharanが発見して、$O(\frac{\ln K}{\epsilon})$から$O(\frac{\ln K}{\epsilon^2})$クエリに代えて、$\epsilon$-approximate Nash equilibriaを効率的に計算できることに新たな関心を寄せている。
驚いたことに、$\epsilon$と$K$の両方の関数として、そのようなクエリの最適数は不明である。
この質問は2つの点で進展している。
まず、厳密な平衡値(\epsilon=0$)を学習するクエリの複雑さを完全に特徴付けます。これは、$k$で線形なクエリをいくつも必要としていることを示します。
第二に、$\epsilon > 0$ の場合、現在のクエリの複雑性上限は $o(\min(\frac{\ln(k)}{\epsilon} , k))$ である。
我々は、これらの行列が単一のクエリによって完全に識別できるので、既知の可算集合の要素が値を取るハード行列を構築することによって下限が導出できないことを証明している。
これにより、例えば、ハイパーキューブ上の最適化問題をバイナリペイオフ行列としてエンコードすることで減らすことができる。
次に、下界に対する新しい手法を導入し、$\tilde\Omega(\log(\frac{1}{K\epsilon})$を任意の$\epsilon \leq 1 / (cK^4)$に対して得ることができる。
さらに,このギャップを上界で縮めるため,技術の改善に向けた今後の方向性についても検討する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳（メタデータ） (2023-11-13T00:45:41Z) - Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。
我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
論文 参考訳（メタデータ） (2023-04-06T16:15:19Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。
これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
論文 参考訳（メタデータ） (2021-11-05T00:04:29Z) - Semi-supervised Active Regression [21.51757844385258]
本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。
学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
論文 参考訳（メタデータ） (2021-06-12T03:28:43Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳（メタデータ） (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。