論文の概要: Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games
- arxiv url: http://arxiv.org/abs/2304.12768v1
- Date: Tue, 25 Apr 2023 12:42:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 20:43:00.842477
- Title: Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games
- Title（参考訳）: ゼロサム行列ゲームにおける学習の1次クエリ複雑度(近似)ナッシュ平衡のキャラクタリゼーション
- Authors: H\'edi Hadiji, Sarah Sachs (UvA), Tim van Erven (UvA), Wouter M.
Koolen (CWI)
- Abstract要約: 正確な平衡を学習するには、線形化$K$のクエリが多数必要であることを示す。
エプシロン > 0$ の場合、現在のクエリ複雑性上限上限は$O(min(K) / epsilon, K))$である。
我々は下界の新しい手法を導入し、$tildeOmega(log (1 / (Kepsilon))$ for any $epsilon leq1 / cK4$ ここで$c$は一定の独立性を持つ。
- 参考スコア（独自算出の注目度）: 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,
playersobserve the expected pay-offs for all their possible actions under
therandomized action played by their opponent. This is a classical model,which
has received renewed interest after the discoveryby Rakhlin and Sridharan that
$\epsilon$-approximate Nash equilibria can be computedefficiently from $O(\ln K
/ \epsilon) $ instead of $O( \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 linearin $K$, which
means that it is essentially as hard as querying the wholematrix, which can
also be done with $K$ queries. Second, for $\epsilon > 0$, the currentquery
complexity upper bound stands at $O(\min(\ln(K) / \epsilon , K))$. We argue
that, unfortunately, obtaining matchinglower bound is not possible with
existing techniques: we prove that nolower bound can be derived by constructing
hard matrices whose entriestake values in a known countable set, because such
matrices can be fullyidentified by a single query. This rules out, for
instance, reducing toa submodular optimization problem over the hypercube by
encoding itas a binary matrix. We then introduce a new technique for lower
bounds,which allows us to obtain lower bounds of order$\tilde\Omega(\log(1 /
(K\epsilon)))$ for any $\epsilon \leq1 / cK^4$, where $c$ is a constant
independent of $K$. We furtherdiscuss possible future directions to improve on
our techniques in orderto close the gap with the upper bounds.
- Abstract（参考訳）: 0-sum $K\times K$Matrixゲームに対する1次クエリモデルでは、プレイヤーは、相手がプレイするランダム化アクションの下で、可能なすべてのアクションに対する期待された支払いを観測する。
これは古典的なモデルであり、rakhlinとsridharanによって、$\epsilon$-approximate nash equilibriaが$o(\ln k / \epsilon)$の代わりに$o(\ln k / \epsilon^2)$クエリから効率的に計算できることが発見された後、新たな関心を集めている。
まず、厳密な平衡値(\epsilon=0$)を学習するクエリの複雑さを、線形の$k$という多くのクエリを必要とすることを示すことによって、完全に特徴付けします。
第二に、$\epsilon > 0$ の場合、電流の複雑さの上界は$O(\min(\ln(K) / \epsilon , K))$である。
そのような行列は単一の問合せで完全同定できるので、既知の可算集合において入出力値を持つハード行列を構築することによって、ノローバウンドが導出可能であることを証明できる。
これにより、例えば、ハイパーキューブ上のtoa部分モジュラー最適化問題をバイナリ行列としてエンコードすることで減らすことができる。
次に、下界に対する新しい手法を導入し、$\tilde\Omega(\log(1 / (K\epsilon))$を任意の$\epsilon \leq1 / cK^4$に対して、$c$は$K$の一定の独立性を持つ。
我々は,このギャップを上界で縮めるために,我々の技術を改善するための今後の方向性をさらに明らかにする。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。