論文の概要: Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
- arxiv url: http://arxiv.org/abs/2505.21430v1
- Date: Tue, 27 May 2025 17:02:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-28 17:05:58.816288
- Title: Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
- Title（参考訳）: 定悪雑音率をもつスパースハーフ空間の属性効率の良いPAC学習
- Authors: Shiwei Zeng, Jie Shen,
- Abstract要約: スパースハーフスペースの属性効率の学習は、機械学習理論における根本的な問題である。
本稿では,データ内に一定の量の悪意のあるノイズが存在することを考察し,基礎となる$s$スパースハーフスペースを学習することを目的とする。
このような条件下では、既存のヒンジ損失最小化プログラムの単純な変種により、属性効率が達成可能であることを示す。
- 参考スコア（独自算出の注目度）: 10.550885570889527
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Attribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory. In recent years, machine learning algorithms are faced with prevalent data corruptions or even adversarial attacks. It is of central interest to design efficient algorithms that are robust to noise corruptions. In this paper, we consider that there exists a constant amount of malicious noise in the data and the goal is to learn an underlying $s$-sparse halfspace $w^* \in \mathbb{R}^d$ with $\text{poly}(s,\log d)$ samples. Specifically, we follow a recent line of works and assume that the underlying distribution satisfies a certain concentration condition and a margin condition at the same time. Under such conditions, we show that attribute-efficiency can be achieved by simple variants to existing hinge loss minimization programs. Our key contribution includes: 1) an attribute-efficient PAC learning algorithm that works under constant malicious noise rate; 2) a new gradient analysis that carefully handles the sparsity constraint in hinge loss minimization.
- Abstract（参考訳）: スパースハーフスペースの属性効率の学習は、機械学習理論における根本的な問題である。
近年、機械学習アルゴリズムは、一般的なデータ破損や、敵対的な攻撃に直面している。
ノイズの破損に対して堅牢な効率的なアルゴリズムを設計することは、中心的な関心事である。
本稿では、データ内に一定の量の悪意のあるノイズが存在すると考え、その目標は、$s$-sparseハーフスペース$w^* \in \mathbb{R}^d$を$\text{poly}(s,\log d)$サンプルで学習することである。
具体的には、最近の研究の行に続き、基礎となる分布が特定の濃度条件とマージン条件を同時に満たすと仮定する。
このような条件下では、既存のヒンジ損失最小化プログラムの単純な変種により、属性効率が達成可能であることを示す。
私たちの重要な貢献は以下のとおりです。
1) 一定の雑音率で機能する属性効率の高いPAC学習アルゴリズム
2) ヒンジ損失最小化において, 空間的制約を慎重に処理する新たな勾配解析を行った。
関連論文リスト
- Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate [6.209600119671225]
本研究では,悪質な雑音の存在下でのハーフスペースの計算効率の高いPAC学習の問題について検討する。
再重み付きヒンジ損失を最小化することにより、一定の耐雑音性を実現することができることを示す。
論文 参考訳（メタデータ） (2024-10-02T02:38:33Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - 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) - Attribute-Efficient Learning of Halfspaces with Malicious Noise:
Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
本稿では,雑音下でのmathbbRd$における等質スパース半空間の計算的学習について述べる。
サンプルの複雑さは$tildeObig(frac 1 epsilon s2 log5 d big)$であり、属性効率も楽しめます。
論文 参考訳（メタデータ） (2020-06-06T04:57:39Z) - Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
本研究では,分布に依存しない環境下で,逆向きに頑健なハーフスペースを学習する問題について検討する。
実現可能な設定では、ハーフ空間が効果的に学習可能な対向摂動集合に対して必要かつ十分な条件を提供する。
論文 参考訳（メタデータ） (2020-05-15T17:13:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。