提出一种鲁棒学习多指标模型的新算法，高效处理标签噪声下的高维数据。
Robust Learning of Multi-index Models via Iterative Subspace Approximation
- 通过迭代计算条件低阶矩，逐步逼近函数依赖的低维子空间。
- 在随机分类噪声下，样本复杂度为 $O(d^2)2^{\mathrm{poly}(K/ε)}$，计算复杂度为多项式级。
- 适用于多类线性分类器和半空间交集，首次实现常数因子近似与多项式复杂度。
研究在高斯分布下带标签噪声的多指标模型（MIM）学习问题。$K$-MIM 是仅依赖于 $K$ 维子空间的函数。针对具有良好性质、值域有界的 MIM，提出一种在统计查询（SQ）模型中近乎最优的鲁棒学习算法。该算法通过计算当前子空间投影上的低阶矩条件，识别具有显著经验矩的方向并迭代更新子空间逼近。最终找到一个子空间 $V$，使得 $f(\mathbf{x})$ 接近 $\mathbf{x}$ 在 $V$ 上投影的函数。对于条件矩无帮助的函数，证明了存在不可逾越的 SQ 下界，表明无高效学习器存在。应用方面：对多类线性分类器，给出常数因子近似抗噪学习器，样本复杂度 $N = O(d) 2^{\mathrm{poly}(K/ε)}$，计算复杂度 $\mathrm{poly}(N,d)$；对半空间交集类，实现 0-1 误差 $K \tilde{O}(\mathrm{OPT}) + ε$，样本复杂度 $N=O(d^2) 2^{\mathrm{poly}(K/ε)}$，且计算复杂度为固定次数多项式。此外，在随机分类噪声下，算法复杂度关于 $1/ε$ 多项式增长。
原文摘要 · Abstract (English)
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/ε)}$ 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}) + ε$ with sample complexity $N=O(d^2) 2^{\mathrm{poly}(K/ε)}$ 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/ε$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。