通过调和分析揭示多指标模型的统计-计算权衡机制
Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis
- 基于正交群对称性，构建调和分解下的学习复杂度刻画
- 在球面对称输入下，首次获得统计与计算下界，并可逼近
- 适用于追求样本效率与运行时平衡的研究者
我们研究多指标模型（MIMs）的学习问题，其中标签仅依赖于输入向量 $\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 下界。根据调和阶数序列的选择，这类估计器可在样本复杂度与运行时间之间实现广泛的权衡。技术上，结果建立在 $\mathcal{O}_d$ 在 $L^2(\mathbb{S}^{d-1})$ 上作用的半单分解，以及球谐函数与无迹对称张量间的交织同构之上。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。