提出首个针对非单调非线性模型的鲁棒恢复算法,可在对抗污染下高效收敛。
Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption
- 通过结构化分析损失曲面,发现全局最优解附近存在不变维数的凸盆地。
- 在污染率ε下实现$O(σ√ε)$的估计误差,样本与时间复杂度接近线性。
- 适用于现代神经网络中的GeLU、Swish等非单调激活函数,填补理论空白。
研究在重尾噪声和恒定比例对抗污染的协变量与响应下,鲁棒学习高斯单指标模型(SIMs)的问题。已有工作仅覆盖线性回归、严格单调链接函数及相位重构,但无法处理如GeLU、Swish等现代神经网络中常见的非单调非对称链接函数。本文首次提出具有近线性样本与时间复杂度的鲁棒恢复算法,为一类广泛存在的非线性SIMs建立了首个理论保证。核心贡献在于揭示:在对抗污染下,对于一大类非单调非线性SIMs,其高斯平方损失曲面存在一个维度无关、半径恒定的凸盆地,且可通过鲁棒谱初始化有效抵达。该结构保证了鲁棒梯度下降的可靠初值,可在$ ilde{O}(nd)$时间内以$ ilde{O}(d)$样本完成优化,最终达到$O(σegin{sqrt}εegin{sqrt})$的估计误差,其中ε为污染比例。
原文摘要 · Abstract (English)
We study the problem of robustly learning Gaussian Single Index Models (SIMs) in the presence of heavy-tailed noise and a constant fraction of adversarially corrupted covariates and responses. Prior work on robust recovery has considered settings such as linear regression (Pensia et al., JASA 2024), strictly monotonic link functions (Awasthi et al., NeurIPS 2022), and phase retrieval (Buna and Rebeschini, AISTATS 2025). However, these techniques do not extend to generic asymmetric non-monotonic link functions such as \textsc{GeLU} and \textsc{Swish}, which arise naturally as scalar primitives in modern gated neural architectures. We close this gap by giving the first robust recovery algorithm with near-linear sample and time complexity for generic non-monotonic link functions, thereby establishing the first robust recovery guarantees for a broad family of nonlinear SIMs for which \textit{no guarantees were previously known}. Our central contribution is a new structural understanding of the Gaussian squared-loss landscape under adversarial contamination. Crucially, we prove that for a broad class of nonlinear non-monotonic SIMs, a dimension-independent, constant-radius convex basin exists around the ground truth and is efficiently reachable via robust spectral initialization even under adversarial contamination. Prior works fail to establish both guarantees simultaneously, thereby either breaking down under adversarial contamination or failing to handle generic non-monotonic link functions. Together, these structural insights yield a principled warm start for robust gradient descent that provably converges to a final estimation error of $O(σ\sqrtε)$ in $\tilde{O}(nd)$ time with $\tilde{O}(d)$ samples, where $ε$ is the contamination fraction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。