論文の概要: Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis

• arxiv url: http://arxiv.org/abs/2602.09959v1
• Date: Tue, 10 Feb 2026 16:46:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-11 20:17:43.689389
• Title: Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis
• Title（参考訳）: 高調波解析による多次元モデル学習における統計的計算トレードオフ
• Authors: Hugo Latourelle-Vigeant, Theodor Misiakiewicz,
• Abstract要約: マルチインデックスモデル(MIM)の学習問題について検討する。 球対称入力を持つMIMの学習複雑性の鋭い調和解析特性を得る。
• 参考スコア（独自算出の注目度）: 5.7652356955571085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning multi-index models (MIMs), where the label depends on the input $\boldsymbol{x} \in \mathbb{R}^d$ only through an unknown $\mathsf{s}$-dimensional projection $\boldsymbol{W}_*^\mathsf{T} \boldsymbol{x} \in \mathbb{R}^\mathsf{s}$. Exploiting the equivariance of this problem under the orthogonal group $\mathcal{O}_d$, we obtain a sharp harmonic-analytic characterization of the learning complexity for MIMs with spherically symmetric inputs -- which refines and generalizes previous Gaussian-specific analyses. Specifically, we derive statistical and computational complexity lower bounds within the Statistical Query (SQ) and Low-Degree Polynomial (LDP) frameworks. These bounds decompose naturally across spherical harmonic subspaces. Guided by this decomposition, we construct a family of spectral algorithms based on harmonic tensor unfolding that sequentially recover the latent directions and (nearly) achieve these SQ and LDP lower bounds. Depending on the choice of harmonic degree sequence, these estimators can realize a broad range of trade-offs between sample and runtime complexity. From a technical standpoint, our results build on the semisimple decomposition of the $\mathcal{O}_d$-action on $L^2 (\mathbb{S}^{d-1})$ and the intertwining isomorphism between spherical harmonics and traceless symmetric tensors.
• Abstract（参考訳）: ラベルは入力 $\boldsymbol{x} \in \mathbb{R}^d$ にのみ依存し、未知の $\mathsf{s}$-次元射影 $\boldsymbol{W}_*^\mathsf{T} \boldsymbol{x} \in \mathbb{R}^\mathsf{s}$ にのみ依存する。 この問題の等式を直交群 $\mathcal{O}_d$ の下で展開し、球対称な入力を持つMIMの学習複雑性の鋭い調和解析的特徴を得る。 具体的には,統計クエリ (SQ) と低次多項式 (LDP) フレームワークにおける統計的・計算的複雑性の低い境界を導出する。 これらの境界は自然に球面調和部分空間に分解される。 この分解で導かれたスペクトルアルゴリズム群は、継続方向を逐次的に復元し、(ほぼ)これらのSQおよびLDPの下界を達成する調和テンソル展開に基づくスペクトルアルゴリズム群を構築する。 調和次数列の選択により、これらの推定器はサンプルと実行時の複雑さの間の幅広いトレードオフを実現することができる。 技術的観点から、我々の結果は、$L^2 (\mathbb{S}^{d-1})$上の$\mathcal{O}_d$-反応の半単純分解と、球面調和とトレーレス対称テンソルの間の交叉同型の上に構築される。

関連論文リスト

• Learning single-index models via harmonic decomposition [21.065469907392643]
  そこで, mathbbRd$ のラベル $y は 1次元の未知射影を通してのみ mathbbRd$ の入力 $boldsymbolx に依存する。 テンソル展開とオンラインSGDに基づく2種類の推定器を導入し、それぞれが最適なサンプル複雑性または最適なランタイムを達成する。
  論文  参考訳（メタデータ） (2025-06-11T15:59:53Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• A Unified View of Stochastic Hamiltonian Sampling [18.300078015845262]
  この研究は、後続サンプリングのためのハミルトン微分方程式(SDE)の理論的性質を再考する。 数値SDEシミュレーションから生じる2種類の誤差について検討し, 離散化誤差と雑音勾配推定による誤差について検討した。
  論文  参考訳（メタデータ） (2021-06-30T16:50:11Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。 本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-28T18:52:37Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Information-Theoretic Limits for the Matrix Tensor Product [8.206394018475708]
  本稿では,ランダム行列の行列テンソル積を含む高次元推論問題について検討する。 本稿では,高次元行列保存信号の解析のための新しい手法を紹介する。
  論文  参考訳（メタデータ） (2020-05-22T17:03:48Z)

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

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