論文の概要: Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs

• arxiv url: http://arxiv.org/abs/2404.00529v1
• Date: Sun, 31 Mar 2024 02:03:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 03:10:31.589228
• Title: Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
• Title（参考訳）: 多項式の超非特異分解とロバスト学習低次PTFへの応用
• Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis,
• Abstract要約: 低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。 提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
• 参考スコア（独自算出の注目度）: 39.468324211376505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic result is a polynomial-time PAC learning algorithm for this concept class in the strong contamination model under the Gaussian distribution with error guarantee $O_{d, c}(\text{opt}^{1-c})$, for any desired constant $c>0$, where $\text{opt}$ is the fraction of corruptions. In the strong contamination model, an omniscient adversary can arbitrarily corrupt an $\text{opt}$-fraction of the data points and their labels. This model generalizes the malicious noise model and the adversarial label noise model. Prior to our work, known polynomial-time algorithms in this corruption model (or even in the weaker adversarial label noise model) achieved error $\tilde{O}_d(\text{opt}^{1/(d+1)})$, which deteriorates significantly as a function of the degree $d$. Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions. Specifically, we use a robust perceptron algorithm to compute a good partial classifier and then iterate on the unclassified points. In order to achieve this, we need to take a set defined by a number of polynomial inequalities and partition it into several well-behaved subsets. To this end, we develop new polynomial decomposition techniques that may be of independent interest.
• Abstract（参考訳）: 低次多項式しきい値関数 (PTF) の対向汚職の一定割合の存在下での効率的な学習性について検討した。 我々のアルゴリズムの主なアルゴリズムは、ガウス分布の下での強い汚染モデルにおけるこの概念クラスの多項式時間PAC学習アルゴリズムであり、任意の定数$c>0$に対して$O_{d, c}(\text{opt}^{1-c})$である。 強い汚染モデルでは、全能な敵は、データポイントとそのラベルの$\text{opt}$-fractionを任意に破壊することができる。 このモデルは、悪質なノイズモデルと敵対的なラベルノイズモデルを一般化する。 我々の研究に先立ち、この汚職モデルにおける既知の多項式時間アルゴリズム(あるいはより弱い逆ラベルノイズモデルでさえも)は誤差$\tilde{O}_d(\text{opt}^{1/(d+1)})$を達成し、次数$d$の関数として著しく劣化する。 提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。 具体的には、ロバストなパーセプトロンアルゴリズムを用いて、優れた部分分類器を計算し、未分類の点を反復する。 これを達成するために、多くの多項式の不等式で定義される集合をいくつかのよく定義された部分集合に分割する必要がある。 この目的のために、我々は独立した関心を持つかもしれない新しい多項式分解手法を開発した。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。 我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
  論文  参考訳（メタデータ） (2023-10-23T04:07:26Z)
• 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)
• Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise [10.550885570889527]
  我々は、$mathbbRn$で$K$sparse degree-$d$ PTFsのPAC学習を研究する。 私たちの主な貢献は、時間$(nd/epsilon)O(d)$で実行される新しいアルゴリズムです。 PACは$eta leq O(epsilond)であっても$O(fracK4depsilon2d cdot log5d n)$でエラー率$epsilon$までクラスを学習する
  論文  参考訳（メタデータ） (2023-06-01T13:49:22Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy [26.69391745812235]
  本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。 これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
  論文  参考訳（メタデータ） (2020-11-11T17:48:00Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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