論文の概要: Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models

• arxiv url: http://arxiv.org/abs/2505.21475v1
• Date: Tue, 27 May 2025 17:47:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:58.842257
• Title: Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
• Title（参考訳）: 実数値マルチインデックスモデルのロバスト学習のためのアルゴリズムとSQ下界
• Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Lisheng Ren,
• Abstract要約: ガウス分布に基づく実数値マルチインデックスモデル(MIM)の学習の複雑さについて検討する。 K$-MIM は関数 $f:mathbbRdto mathbbR$ であり、入力の$K$-次元部分空間への射影のみに依存する。 逆ラベルノイズが存在する場合でも, 正方形損失に対して幅広いMIMを学習するための一般アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 34.196233651364615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A $K$-MIM is a function $f:\mathbb{R}^d\to \mathbb{R}$ that depends only on the projection of its input onto a $K$-dimensional subspace. We give a general algorithm for PAC learning a broad class of MIMs with respect to the square loss, even in the presence of adversarial label noise. Moreover, we establish a nearly matching Statistical Query (SQ) lower bound, providing evidence that the complexity of our algorithm is qualitatively optimal as a function of the dimension. Specifically, we consider the class of bounded variation MIMs with the property that degree at most $m$ distinguishing moments exist with respect to projections onto any subspace. In the presence of adversarial label noise, the complexity of our learning algorithm is $d^{O(m)}2^{\mathrm{poly}(K/\epsilon)}$. For the realizable and independent noise settings, our algorithm incurs complexity $d^{O(m)}2^{\mathrm{poly}(K)}(1/\epsilon)^{O(K)}$. To complement our upper bound, we show that if for some subspace degree-$m$ distinguishing moments do not exist, then any SQ learner for the corresponding class of MIMs requires complexity $d^{\Omega(m)}$. As an application, we give the first efficient learner for the class of positive-homogeneous $L$-Lipschitz $K$-MIMs. The resulting algorithm has complexity $\mathrm{poly}(d) 2^{\mathrm{poly}(KL/\epsilon)}$. This gives a new PAC learning algorithm for Lipschitz homogeneous ReLU networks with complexity independent of the network size, removing the exponential dependence incurred in prior work.
• Abstract（参考訳）: ガウス分布に基づく実数値マルチインデックスモデル(MIM)の学習の複雑さについて検討する。 K$-MIM は函数 $f:\mathbb{R}^d\to \mathbb{R}$ であり、$K$-次元部分空間への入力の射影にのみ依存する。 逆ラベルノイズが存在する場合でも, 正方形損失に対して幅広いMIMを学習するための一般アルゴリズムを提案する。 さらに、ほぼ一致する統計的クエリ(SQ)の下限を確立し、このアルゴリズムの複雑さが次元の関数として質的に最適であることを示す。 具体的には、任意の部分空間への射影に関して、少なくとも$m$の微分モーメントを持つような性質を持つ有界変分MIMのクラスを考える。 逆ラベルノイズが存在する場合、学習アルゴリズムの複雑さは$d^{O(m)}2^{\mathrm{poly}(K/\epsilon)}$である。 実現可能かつ独立なノイズ設定に対して、我々のアルゴリズムは複雑さを$d^{O(m)}2^{\mathrm{poly}(K)}(1/\epsilon)^{O(K)}$に導く。 上界を補完するために、ある部分空間次数-$m$ のモーメントが存在しない場合、対応する MIM のクラスに対する任意の SQ 学習者は、複雑性$d^{\Omega(m)}$ を必要とする。 アプリケーションとして、正ホモジニアス$L$-Lipschitz$K$-MIMのクラスに対して、最初の効率的な学習者を与える。 結果として得られるアルゴリズムは複雑さ$\mathrm{poly}(d) 2^{\mathrm{poly}(KL/\epsilon)}$である。 これにより、ネットワークサイズに依存しない複雑性を持つリプシッツ均質ReLUネットワークに対して、新しいPAC学習アルゴリズムが提供される。

関連論文リスト

• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
  論文  参考訳（メタデータ） (2025-02-13T17:37:42Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58: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)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• 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)
• 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)

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

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