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

In this paper, we tackle a fundamental problem in high-dimensional statistics, namely, learning Single Index Models (SIMs) robustly in the presence of heavy-tailed noise and an adversary that can corrupt a constant fraction of both covariates and responses. Prior research on efficient robust recovery only focuses on monotonic link functions or only limit themselves to Phase Retrieval. Provable efficient robust recovery guarantees for generic nonlinear link functions have remained elusive. In this paper, we obtain the first near-linear time, optimal-sample-complexity robust recovery algorithm for a wide class of nonlinear non-monotonic link functions. Critical to our result is an improved understanding of the squared-loss landscape: we identify a sufficient condition under which a broad class of non linear link functions admit a dimension-independent constant-radius convex basin around the ground truth, establishing statistical identifiability beyond previously known cases. We also leverage second-order Stein's identities to identify a structural condition, that we term Expected Squared Convexity (ESC), that acts as a sufficient condition for spectral initialization techniques to obtain an estimator within the convex basin with error $O(\epsilon^{1/4})$, even under heavy-tailed noise and strong adversarial contamination. This robust initialization technique can be combined with a robust gradient descent phase to break the spectral error barrier, achieving an improved estimation error of $O(\sigma\sqrt{\epsilon})$. Our non-convex optimization framework gives the first efficient sample and time complexity robust recovery results for activation functions such as GeLU and Swish that act as building blocks of modern deep-learning architectures.