論文の概要: Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold
Functions with Nasty Noise
- arxiv url: http://arxiv.org/abs/2306.00673v1
- Date: Thu, 1 Jun 2023 13:49:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 15:53:33.857924
- Title: Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold
Functions with Nasty Noise
- Title(参考訳): 雑音を考慮した低次多項式閾値関数の属性効率PAC学習
- Authors: Shiwei Zeng and Jie Shen
- Abstract要約: 我々は、$mathbbRn$で$K$sparse degree-$d$ PTFsのPAC学習を研究する。
私たちの主な貢献は、時間$(nd/epsilon)O(d)$で実行される新しいアルゴリズムです。
PACは$eta leq O(epsilond)であっても$O(fracK4depsilon2d cdot log5d n)$でエラー率$epsilon$までクラスを学習する
- 参考スコア(独自算出の注目度): 7.594050968868919
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The concept class of low-degree polynomial threshold functions (PTFs) plays a
fundamental role in machine learning. In this paper, we study PAC learning of
$K$-sparse degree-$d$ PTFs on $\mathbb{R}^n$, where any such concept depends
only on $K$ out of $n$ attributes of the input. Our main contribution is a new
algorithm that runs in time $({nd}/{\epsilon})^{O(d)}$ and under the Gaussian
marginal distribution, PAC learns the class up to error rate $\epsilon$ with
$O(\frac{K^{4d}}{\epsilon^{2d}} \cdot \log^{5d} n)$ samples even when an $\eta
\leq O(\epsilon^d)$ fraction of them are corrupted by the nasty noise of
Bshouty et al. (2002), possibly the strongest corruption model. Prior to this
work, attribute-efficient robust algorithms are established only for the
special case of sparse homogeneous halfspaces. Our key ingredients are: 1) a
structural result that translates the attribute sparsity to a sparsity pattern
of the Chow vector under the basis of Hermite polynomials, and 2) a novel
attribute-efficient robust Chow vector estimation algorithm which uses
exclusively a restricted Frobenius norm to either certify a good approximation
or to validate a sparsity-induced degree-$2d$ polynomial as a filter to detect
corrupted samples.
- Abstract(参考訳): 低次多項式しきい値関数(PTF)の概念クラスは、機械学習において基本的な役割を果たす。
本稿では,$K$-sparse degree-$d$ PTFs on $\mathbb{R}^n$のPAC学習について検討する。
私たちの主な貢献は、時間$({nd}/{\epsilon})^{o(d)}$で実行され、ガウス境界分布の下で、pacはエラーレート$\epsilon$のクラスを学習し、$o(\frac{k^{4d}}{\epsilon^{2d}} \cdot \log^{5d} n)$サンプルは$\eta \leq o(\epsilon^d)$がbshouty et al. (2002)の厄介なノイズによって損なわれる場合であっても、おそらく最も強力な腐敗モデルである。
この研究に先立って、属性効率のよいロバストアルゴリズムは、疎均質な半空間の特別な場合のみ確立される。
私たちの主な材料は
1) ハーマイト多項式に基づくChowベクトルのスパーシティパターンに属性のスパーシティを変換する構造的結果、及び
2) 制限されたフロベニウスノルムのみを用いて,良好な近似を証明したり, 破損したサンプルを検出するフィルタとして, 疎度誘起次数-$2d$多項式の検証を行う新しい属性効率の強いChowベクトル推定アルゴリズム。
関連論文リスト
- 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) - 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) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳(メタデータ) (2022-05-28T05:13:45Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳(メタデータ) (2020-10-04T22:19:06Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳(メタデータ) (2020-06-22T17:53:54Z) - Robust Sub-Gaussian Principal Component Analysis and Width-Independent
Schatten Packing [22.337756118270217]
基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。
最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。
私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
論文 参考訳(メタデータ) (2020-06-12T07:45:38Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。