論文の概要: Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

• arxiv url: http://arxiv.org/abs/2605.21428v1
• Date: Wed, 20 May 2026 17:19:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.808773
• Title: Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals
• Title（参考訳）: ガウス行列に基づく多項式時間ロバスト多クラス線形分類
• Authors: Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma,
• Abstract要約: 標準的なマルチクラスパーセプトロンは,クリーンなラベルやガウスの限界を持つ場合でも,スーパーポリノミカルな多くのサンプルと更新を必要とすることを示す。 そこで我々は,誤差$O(mathrmopt)+$ for $k=3,エラー$mathrmpoly(k)mathrmopt+$ for geometryally regulark-class linear classifiersを開発した。
• 参考スコア（独自算出の注目度）: 38.241216472571786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples $(x, y)$ from a distribution over $\mathbb{R}^d \times [k]$, with Gaussian $x$-marginal, the goal is to output a hypothesis whose error is comparable to that of the best $k$-class linear classifier. While the binary case $k=2$ has a well-developed algorithmic theory, much less is known for $k \ge 3$. Even for $k=3$, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error $\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε$ for general $k$. Additionally, we develop a sharper localization-based framework which leads to error $O(\mathrm{opt})+ε$ for $k=3$, and error $\mathrm{poly}(k)\mathrm{opt}+ε$ for geometrically regular $k$-class linear classifiers.
• Abstract（参考訳）: ガウス分布下での多クラス線形分類器の非依存学習の課題について検討する。 a distribution over $\mathbb{R}^d \times [k]$, with Gaussian $x$-marginal のラベル付き例 $(x, y)$ が与えられた場合、ゴールは、最良の$k$クラスの線形分類器のエラーに匹敵する仮説を出力することである。 バイナリの場合、$k=2$ はよく発達したアルゴリズム理論を持つが、$k \ge 3$ ではあまり知られていない。 k=3$であっても、前の頑健なアルゴリズムは複雑さと表現サイズの両方において所望の精度の逆に指数関数的依存を生じさせる。 本研究では,マルチクラス線形分類器のための新しい構造解析結果を開発し,次元に依存しない誤り保証を持つ完全多項式時間頑健な学習者の設計に利用する。 最初の結果は、標準的なマルチクラスパーセプトロンアルゴリズムは、クリーンなラベルやガウスの限界を持つ場合でも、超ポリノミカルな多くのサンプルと更新を必要としており、バイナリケースに欠落する基本的な障害が明らかであることを示している。 我々の主な肯定的な結果は、ペアワイドな不適切な学習フレームワークで、エラーを$\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε$ for general $k$で効率的に学習する。 さらに, 誤差$O(\mathrm{opt})+ε$ for $k=3$, and error $\mathrm{poly}(k)\mathrm{opt}+ε$ for geometryally regular $k$-class linear classifiers。

関連論文リスト

• Universality of max-margin classifiers [10.797131009370219]
  非ガウス的特徴に対する誤分類誤差の高次元普遍性と大域化写像の役割について検討する。 特に、オーバーパラメトリゼーションしきい値と一般化誤差はより単純なモデルで計算できる。
  論文  参考訳（メタデータ） (2023-09-29T22:45:56Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• 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)
• 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)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime [11.252856459394854]
  現代の機械学習分類器は、トレーニングセットに消滅する分類誤差を示すことが多い。 これらの現象に触発され、線形分離可能なデータに対する高次元の最大マージン分類を再検討する。
  論文  参考訳（メタデータ） (2019-11-05T00:15:27Z)

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

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