論文の概要: Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

• arxiv url: http://arxiv.org/abs/2605.18662v1
• Date: Mon, 18 May 2026 17:09:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 17:57:50.120284
• Title: Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
• Title（参考訳）: 多クラス線形分類器の高能率・耐雑音性PAC学習
• Authors: Rita Adhikari, Shiwei Zeng,
• Abstract要約: 線形モデルの耐雑音性PAC学習は、前世紀から機械学習コミュニティにおいて中心的な関心を集めてきた。 PAC がマルチクラス線形分類器 $h_w:xmapsto argmax_yin[k]w_ycdot x, xin mathbbRd, winmathbbRkd$ を少なくとも$O(k2cdot (dlog d+log k))$サンプルを用いて学習する計算効率のよいアルゴリズムが存在することを示す。
• 参考スコア（独自算出の注目度）: 4.812718493682454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes $k$ is at least $3$, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers $\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\}$ using at most $O(k^2\cdot (d\log d+\log k))$ samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e. $k=2$, our result is strictly stronger than all prior works.
• Abstract（参考訳）: 線形モデルの耐雑音性PAC学習は、前世紀から機械学習コミュニティにおいて中心的な関心を集めてきた。 近年,複数の雑音モデルの下で線形しきい値関数を学習する問題に対して,多くの計算効率のよいアルゴリズムが提案されている。 しかし、クラス数$k$が少なくとも$$$3の場合には、データセットが悪用された場合、計算効率のよいPAC学習アルゴリズムが存在するかどうかは不明である。 本稿では,境界分布は有界分散分布の混合であり,データセットはマージン条件を同時に満たすと考えられる。 PAC がマルチクラス線形分類器 $\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\} を学習する計算効率のよいアルゴリズムが存在することを示す。 本アルゴリズムは,クラスタベースプルーニング方式と標準マルチクラスヒンジ損失最小化プログラムの2つの主成分からなる。 特別なバイナリ設定の場合、すなわち$k=2$であっても、我々の結果は以前のすべての作業よりも強くなる。

関連論文リスト

• Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models [34.196233651364615]
  ガウス分布に基づく実数値マルチインデックスモデル(MIM)の学習の複雑さについて検討する。 K$-MIM は関数 $f:mathbbRdto mathbbR$ であり、入力の$K$-次元部分空間への射影のみに依存する。 逆ラベルノイズが存在する場合でも, 正方形損失に対して幅広いMIMを学習するための一般アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-27T17:47:26Z)
• Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate [10.550885570889527]
  スパースハーフスペースの属性効率の学習は、機械学習理論における根本的な問題である。 本稿では,データ内に一定の量の悪意のあるノイズが存在することを考察し,基礎となる$s$スパースハーフスペースを学習することを目的とする。 このような条件下では、既存のヒンジ損失最小化プログラムの単純な変種により、属性効率が達成可能であることを示す。
  論文  参考訳（メタデータ） (2025-05-27T17:02:28Z)
• 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)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• 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)

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

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