論文の概要: Statistically Near-Optimal Hypothesis Selection
- arxiv url: http://arxiv.org/abs/2108.07880v1
- Date: Tue, 17 Aug 2021 21:11:20 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-19 14:46:45.232045
- Title: Statistically Near-Optimal Hypothesis Selection
- Title（参考訳）: 統計的に近似した仮説選択
- Authors: Olivier Bousquet and Mark Braverman and Klim Efremenko and Gillat Kol
and Shay Moran
- Abstract要約: 仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 33.83129262033921
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Hypothesis Selection is a fundamental distribution learning problem where
given a comparator-class $Q=\{q_1,\ldots, q_n\}$ of distributions, and a
sampling access to an unknown target distribution $p$, the goal is to output a
distribution $q$ such that $\mathsf{TV}(p,q)$ is close to $opt$, where $opt =
\min_i\{\mathsf{TV}(p,q_i)\}$ and $\mathsf{TV}(\cdot, \cdot)$ denotes the
total-variation distance. Despite the fact that this problem has been studied
since the 19th century, its complexity in terms of basic resources, such as
number of samples and approximation guarantees, remains unsettled (this is
discussed, e.g., in the charming book by Devroye and Lugosi `00). This is in
stark contrast with other (younger) learning settings, such as PAC learning,
for which these complexities are well understood.
We derive an optimal $2$-approximation learning strategy for the Hypothesis
Selection problem, outputting $q$ such that $\mathsf{TV}(p,q) \leq2 \cdot opt +
\eps$, with a (nearly) optimal sample complexity of~$\tilde O(\log
n/\epsilon^2)$. This is the first algorithm that simultaneously achieves the
best approximation factor and sample complexity: previously, Bousquet, Kane,
and Moran (COLT `19) gave a learner achieving the optimal $2$-approximation,
but with an exponentially worse sample complexity of $\tilde
O(\sqrt{n}/\epsilon^{2.5})$, and Yatracos~(Annals of Statistics `85) gave a
learner with optimal sample complexity of $O(\log n /\epsilon^2)$ but with a
sub-optimal approximation factor of $3$.
- Abstract（参考訳）: 仮説選択は、コンパレータクラス $q=\{q_1,\ldots, q_n\}$ と未知の目標分布 $p$ へのサンプリングアクセスが与えられた場合の基本的な分布学習問題であり、その目的は、$\mathsf{tv}(p,q)$ が$opt$に近いような分布 $q$ を出力することであり、ここでは$opt = \min_i\{\mathsf{tv}(p,q_i)\}$ と $\mathsf{tv}(\cdot, \cdot)$ が全変動距離を表す。
この問題は19世紀から研究されているにもかかわらず、サンプルの数や近似保証といった基本的な資源の複雑さは未解決のままである(例えば、Devroye と Lugosi `00" の魅力的な本で論じられている)。
これは、これらの複雑さがよく理解されているPAC学習のような他の(若い)学習環境とは対照的である。
仮説選択問題に対して最適な2ドル近似学習戦略を導出し、$$$q$を$\mathsf{TV}(p,q) \leq2 \cdot opt + \eps$とし、(ほぼ)最適サンプル複雑性~$$\tilde O(\log n/\epsilon^2)$とする。
以前、Bousquet, Kane, and Moran (COLT `19)は、最適な2$-approximationを達成する学習者を与えたが、指数関数的に悪いサンプルの複雑さは$\tilde O(\sqrt{n}/\epsilon^{2.5})$, and Yatracos~(Annals of Statistics `85)は、最適なサンプルの複雑さを持つ学習者に対して$O(\log n /\epsilon^2)$を与えられた。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳（メタデータ） (2024-11-08T17:10:38Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。
具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。
本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
論文 参考訳（メタデータ） (2023-11-22T04:34:09Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。