論文の概要: 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ベクトル推定アルゴリズム。

関連論文リスト

• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
  論文  参考訳（メタデータ） (2024-12-30T18:59:46Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
  低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。 提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
  論文  参考訳（メタデータ） (2024-03-31T02:03:35Z)
• 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)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。