論文の概要: A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
- arxiv url: http://arxiv.org/abs/2511.07244v1
- Date: Mon, 10 Nov 2025 15:58:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-11 21:18:45.351562
- Title: A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
- Title（参考訳）: ハイパーキューブ上のロバスト学習半空間に対する完全多項式時間アルゴリズム
- Authors: Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
- Abstract要約: ハイパーキューブ上の一様分布に関して、ハーフスペースを学習するための最初のフルタイムアルゴリズムを与える。
誤り保証は$etaO(1)+epsilon$で、$eta$はノイズレートです。
より一般的に、我々のフレームワークは、個別分布に関する教師あり学習が以前考えられていたほど難しくないことを示している。
- 参考スコア（独自算出の注目度）: 26.777025730534756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in the presence of contamination, where an adversary may corrupt some fraction of examples and labels arbitrarily. We achieve an error guarantee of $\eta^{O(1)}+\epsilon$ where $\eta$ is the noise rate. Such a result was not known even in the agnostic setting, where only labels can be adversarially corrupted. All prior work over the last two decades has a superpolynomial dependence in $1/\epsilon$ or succeeds only with respect to continuous marginals (such as log-concave densities). Previous analyses rely heavily on various structural properties of continuous distributions such as anti-concentration. Our approach avoids these requirements and makes use of a new algorithm for learning Generalized Linear Models (GLMs) with only a polylogarithmic dependence on the activation function's Lipschitz constant. More generally, our framework shows that supervised learning with respect to discrete distributions is not as difficult as previously thought.
- Abstract（参考訳）: 汚染が存在する場合のハイパーキューブ上の均一分布に関して、ハーフスペースを学習するための最初の完全多項式時間アルゴリズムを与える。
誤差保証は$\eta^{O(1)}+\epsilon$で、$\eta$はノイズ率である。
このような結果は、ラベルのみを逆向きに破損させるような、不可知的な設定でも知られていなかった。
過去20年間の全ての先行研究は1/\epsilon$のスーパーポリノミカル依存を持つか、あるいは(対数凹凸密度のような)連続的な限界に対してのみ成功する。
以前の分析は、アンチ集中のような連続分布の様々な構造的特性に大きく依存していた。
提案手法はこれらの要求を回避し,アクティベーション関数のリプシッツ定数に依存した一般化線形モデル(GLM)を学習するための新しいアルゴリズムを利用する。
より一般的に、我々のフレームワークは、個別分布に関する教師あり学習が以前考えられていたほど難しくないことを示している。
関連論文リスト
- Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。
学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。
時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-07-01T04:58:36Z) - Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。
我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。
超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
論文 参考訳（メタデータ） (2023-11-02T17:51:10Z) - 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) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。