論文の概要: Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise
- arxiv url: http://arxiv.org/abs/2306.16352v1
- Date: Wed, 28 Jun 2023 16:33:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-29 13:37:33.567474
- Title: Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise
- Title（参考訳）: ランダム分類雑音をもつ辺縁半空間学習のための情報計算トレードオフ
- Authors: Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang,
Nikos Zarifis
- Abstract要約: ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
- 参考スコア（独自算出の注目度）: 50.64137465792738
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of PAC learning $\gamma$-margin halfspaces with Random
Classification Noise. We establish an information-computation tradeoff
suggesting an inherent gap between the sample complexity of the problem and the
sample complexity of computationally efficient algorithms. Concretely, the
sample complexity of the problem is $\widetilde{\Theta}(1/(\gamma^2
\epsilon))$. We start by giving a simple efficient algorithm with sample
complexity $\widetilde{O}(1/(\gamma^2 \epsilon^2))$. Our main result is a lower
bound for Statistical Query (SQ) algorithms and low-degree polynomial tests
suggesting that the quadratic dependence on $1/\epsilon$ in the sample
complexity is inherent for computationally efficient algorithms. Specifically,
our results imply a lower bound of $\widetilde{\Omega}(1/(\gamma^{1/2}
\epsilon^2))$ on the sample complexity of any efficient SQ learner or
low-degree test.
- Abstract（参考訳）: ランダムな分類雑音を伴うpac学習問題である\gamma$-margin半空間について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
具体的には、問題のサンプル複雑性は$\widetilde{\Theta}(1/(\gamma^2 \epsilon)$である。
まず、サンプル複雑性 $\widetilde{O}(1/(\gamma^2 \epsilon^2))$ の単純な効率的なアルゴリズムを与える。
我々の主な結果は統計クエリ(sq)アルゴリズムと低次多項式テストに対する下限であり、サンプル複雑性における1/\epsilon$の二次依存は計算効率の高いアルゴリズムに固有のものであることを示唆している。
具体的には、効率的なSQ学習者や低次テストのサンプル複雑さについて、より低い値の$\widetilde{\Omega}(1/(\gamma^{1/2} \epsilon^2)を示唆する。
関連論文リスト
- 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) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳（メタデータ） (2023-03-03T18:03:49Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文 参考訳（メタデータ） (2020-07-30T04:18:51Z) - 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) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。