mlsanityData to 14 Oct 2026

Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption

arXiv 2605.29497 ↗First posted 28 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 textscGeLU and textscSwish, 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 textitno 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(σ√ε) in tildeO(nd) time with tildeO(d) samples, where ε is the contamination fraction.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 30 of its 55 references that are in the map. First posted on arXiv 28 May 2026.

Builds on

30 of 55 references.

References · 30

  1. 2020GLU Variants Improve Transformercited by 1,804
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  4. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  5. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  6. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  7. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  8. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  9. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  10. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  11. 2013Phase Retrieval using Alternating Minimizationcited by 58
  12. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
18 more
  1. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
  2. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  3. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 32
  4. 2025Emergence and scaling laws in SGD learning of shallow neural networkscited by 32
  5. 2013Phase Retrieval from Coded Diffraction Patternscited by 26
  6. 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
  7. 2025Learning quadratic neural networks in high dimensions: SGD dynamics and scaling lawscited by 25
  8. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  9. 2023On Single Index Models beyond Gaussian Datacited by 17
  10. 2025Survey on Algorithms for multi-index modelscited by 15
  11. 2016Homotopy Analysis for Tensor PCAcited by 12
  12. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  13. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  14. 2025Learning single-index models via harmonic decompositioncited by 7
  15. 2022Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Modelscited by 6
  16. 2016Median-Truncated Nonconvex Approach for Phase Retrieval with Outlierscited by 4
  17. 2024Robust Gradient Descent for Phase Retrievalcited by 2
  18. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1

Built on by

Not cited yet.