論文の概要: A New Minimax Theorem for Randomized Algorithms
- arxiv url: http://arxiv.org/abs/2002.10802v2
- Date: Thu, 17 Sep 2020 22:20:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 00:06:40.468207
- Title: A New Minimax Theorem for Randomized Algorithms
- Title（参考訳）: ランダム化アルゴリズムのための新しいミニマックス理論
- Authors: Shalev Ben-David, Eric Blais
- Abstract要約: 新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。
ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。
また、Impagliazzoのハードコアの改良版も証明した。
- 参考スコア（独自算出の注目度）: 1.2284934135116514
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The celebrated minimax principle of Yao (1977) says that for any
Boolean-valued function $f$ with finite domain, there is a distribution $\mu$
over the domain of $f$ such that computing $f$ to error $\epsilon$ against
inputs from $\mu$ is just as hard as computing $f$ to error $\epsilon$ on
worst-case inputs. Notably, however, the distribution $\mu$ depends on the
target error level $\epsilon$: the hard distribution which is tight for bounded
error might be trivial to solve to small bias, and the hard distribution which
is tight for a small bias level might be far from tight for bounded error
levels.
In this work, we introduce a new type of minimax theorem which can provide a
hard distribution $\mu$ that works for all bias levels at once. We show that
this works for randomized query complexity, randomized communication
complexity, some randomized circuit models, quantum query and communication
complexities, approximate polynomial degree, and approximate logrank. We also
prove an improved version of Impagliazzo's hardcore lemma.
Our proofs rely on two innovations over the classical approach of using Von
Neumann's minimax theorem or linear programming duality. First, we use Sion's
minimax theorem to prove a minimax theorem for ratios of bilinear functions
representing the cost and score of algorithms.
Second, we introduce a new way to analyze low-bias randomized algorithms by
viewing them as "forecasting algorithms" evaluated by a proper scoring rule.
The expected score of the forecasting version of a randomized algorithm appears
to be a more fine-grained way of analyzing the bias of the algorithm. We show
that such expected scores have many elegant mathematical properties: for
example, they can be amplified linearly instead of quadratically. We anticipate
forecasting algorithms will find use in future work in which a fine-grained
analysis of small-bias algorithms is required.
- Abstract（参考訳）: Yao (1977) の有名なミニマックスの原理は、有限領域を持つブール値関数 $f$ に対して、$f$の領域上の分布 $\mu$ が存在して、$\mu$ の入力に対する計算 $f$ の誤差 $\epsilon$ は、最悪のケース入力に対する計算 $f$ の誤差 $\epsilon$ と同程度に難しいということである。
しかし、分布 $\mu$ は対象の誤差レベル $\epsilon$ に依存する: 有界誤差に対して厳密な硬分布は小さなバイアスに難解であり、小さなバイアスレベルで厳密な硬分布は、有界誤差レベルでは厳密ではないかもしれない。
本研究では,すべてのバイアスレベルに対して同時に作用するハード分布$\mu$を提供する,新しいタイプのミニマックス定理を導入する。
本研究では,ランダム化クエリの複雑性,ランダム化通信の複雑性,ランダム化回路モデル,量子クエリと通信の複雑さ,近似多項式次数,近似logrankに対して有効であることを示す。
また、Impagliazzoのハードコア補題の改良版も証明した。
我々の証明は、フォン・ノイマンのミニマックス定理や線型計画双対性を用いる古典的なアプローチに対する2つの革新に依存している。
まず、アルゴリズムのコストとスコアを表す双線型関数の比に対するミニマックス定理をシオンのミニマックス定理を用いて証明する。
第2に、適切なスコアリングルールにより評価された「予測アルゴリズム」とみなして、低バイアスランダム化アルゴリズムを解析する新しい方法を提案する。
ランダム化アルゴリズムの予測バージョンの期待スコアは、アルゴリズムのバイアスを分析するためのよりきめ細かい方法であるように見える。
このような期待値には多くのエレガントな数学的性質があり、例えば二次数の代わりに線形に増幅することができる。
予測アルゴリズムは,小バイアスアルゴリズムのきめ細かな解析が必要となる今後の研究での利用を見込んでいる。
関連論文リスト
- Binary Search with Distributional Predictions [26.193119064206304]
本研究では,予測自体が分布である分布予測を用いたアルゴリズムについて検討する。
従来の予測に基づくアルゴリズムを1つの予測で使用すると、予測が不十分な単純な分布が存在することを示す。
これはまた、二分探索木を最適に計算する古典的な問題に対する最初の分散ロバストアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2024-11-25T01:15:31Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions [2.2940141855172036]
我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。
$delta$-correctアルゴリズムの下位境界はよく知られている。
我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
論文 参考訳（メタデータ） (2019-08-24T05:31:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。