論文の概要: Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise

• arxiv url: http://arxiv.org/abs/2306.00673v2
• Date: Tue, 19 Mar 2024 15:01:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 01:20:39.235133
• Title: Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
• Title（参考訳）: 雑音を考慮した低次多項式閾値関数の属性効率PAC学習
• Authors: Shiwei Zeng, 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$までクラスを学習する
• 参考スコア（独自算出の注目度）: 10.550885570889527
• 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はクラスを$O(\frac{K^{4d}}{\epsilon^{2d}} \cdot \log^{5d} n)$サンプルで学習する。 この研究に先立ち、属性効率の良いロバストアルゴリズムはスパースホモジニアス半空間の特別なケースに対してのみ確立される。 主な材料は以下の通り。 1) ハーマイト多項式に基づくChowベクトルのスパーシティパターンに属性のスパーシティを変換する構造的結果、及び 2) 制限されたフロベニウスノルムのみを用いて良好な近似を証明するか, あるいは, 破損したサンプルを検出するフィルタとして, 疎度誘起次数-$2d$多項式の検証を行う新しい属性効率の強いChowベクトル推定アルゴリズムを提案する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• 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)
• 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)
• 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)

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

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