論文の概要: Robust Learning of Multi-index Models via Iterative Subspace Approximation

• arxiv url: http://arxiv.org/abs/2502.09525v1
• Date: Thu, 13 Feb 2025 17:37:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:49:23.937801
• Title: Robust Learning of Multi-index Models via Iterative Subspace Approximation
• Title（参考訳）: 反復部分空間近似によるマルチインデックスモデルのロバスト学習
• Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Nikos Zarifis,
• Abstract要約: ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
• 参考スコア（独自算出の注目度）: 36.138661719725626
• License:
• Abstract: We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution. A $K$-MIM is any function $f$ that only depends on a $K$-dimensional subspace. We focus on well-behaved MIMs with finite ranges that satisfy certain regularity properties. Our main contribution is a general robust learner that is qualitatively optimal in the Statistical Query (SQ) model. Our algorithm iteratively constructs better approximations to the defining subspace by computing low-degree moments conditional on the projection to the subspace computed thus far, and adding directions with relatively large empirical moments. This procedure efficiently finds a subspace $V$ so that $f(\mathbf{x})$ is close to a function of the projection of $\mathbf{x}$ onto $V$. Conversely, for functions for which these conditional moments do not help, we prove an SQ lower bound suggesting that no efficient learner exists. As applications, we provide faster robust learners for the following concept classes: * {\bf Multiclass Linear Classifiers} We give a constant-factor approximate agnostic learner with sample complexity $N = O(d) 2^{\mathrm{poly}(K/\epsilon)}$ and computational complexity $\mathrm{poly}(N ,d)$. This is the first constant-factor agnostic learner for this class whose complexity is a fixed-degree polynomial in $d$. * {\bf Intersections of Halfspaces} We give an approximate agnostic learner for this class achieving 0-1 error $K \tilde{O}(\mathrm{OPT}) + \epsilon$ with sample complexity $N=O(d^2) 2^{\mathrm{poly}(K/\epsilon)}$ and computational complexity $\mathrm{poly}(N ,d)$. This is the first agnostic learner for this class with near-linear error dependence and complexity a fixed-degree polynomial in $d$. Furthermore, we show that in the presence of random classification noise, the complexity of our algorithm scales polynomially with $1/\epsilon$.
• Abstract（参考訳）: ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 K$-MIM は任意の函数 $f$ であり、これは K$-次元部分空間にのみ依存する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 我々の主な貢献は、統計的クエリ(SQ)モデルにおいて定性的に最適である一般的な頑健な学習者である。 提案アルゴリズムは,これまで計算された部分空間への射影条件付き低次モーメントを計算し,比較的大きな経験的モーメントを付加することにより,定義部分空間に対するより良い近似を反復的に構築する。 この手順は、$f(\mathbf{x})$ が$V$ への射影の関数に近いような部分空間 $V$ を効率的に見つける。 逆に、これらの条件モーメントが役に立たない関数に対しては、効率的な学習者が存在しないことを示すSQ下界を証明する。 アプリケーションとして、我々は以下の概念クラスに対してより高速な堅牢な学習者を提供する。 * {\bf Multiclass Linear Classifiers} サンプル複雑性$N = O(d) 2^{\mathrm{poly}(K/\epsilon)}$と計算複雑性$\mathrm{poly}(N ,d)$。 これは、複雑性が$d$の固定次多項式であるこのクラスにとって、最初の定数要素非依存の学習者である。 * {\bf Intersections of Halfspaces} このクラスに対する近似非依存的な学習者には、0-1エラーを達成できる$K \tilde{O}(\mathrm{OPT}) + \epsilon$とサンプル複雑性$N=O(d^2) 2^{\mathrm{poly}(K/\epsilon)}$と計算複雑性$\mathrm{poly}(N ,d)$を与える。 これは、ほぼ線形の誤差依存と、$d$の固定次多項式の複雑さを持つこのクラスで最初の非依存的な学習者である。 さらに、ランダムな分類ノイズの存在下では、アルゴリズムの複雑さは1/\epsilon$で多項式的にスケールすることを示した。

関連論文リスト

• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• 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)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)

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

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