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.

Imagine trying to learn the nonlinear rule that relates property features to house prices by aggregating thousands of listings. Two kinds of corruption make this hard. - First, every homeowner has personal idiosyncrasies (one prizes a bay view, another a large kitchen) that add random, occasionally extreme noise to their asking price; a single eccentric seller might list at ten times the market rate, skewing any naive estimate. - Second, a coordinated price-fixing cartel can strategically falsify both the property details and the asking prices of a fraction of listings, no matter how the learning algorithm works. We give the first provably efficient algorithm for nonlinear regression that handles both corruptions simultaneously, recovering the nonlinear pricing rule and the relevant combination of property features even when the relationship between features and price is non-monotone (for example, an extra bedroom may help in a small flat but barely matter in a mansion), the idiosyncratic noise is occasionally extreme, and the cartel corrupts a constant fraction of both features and prices. Computational guarantees for nonlinear regression under both corruptions were previously known only for monotone and/or highly structured pricing rules. Our framework applies directly to a large class of activation functions that include GeLU and Swish which are the scalar primitives in Transformers. Therefore, we provide the first theoretical guarantee that these building blocks can be learned reliably under adversarial data poisoning. This is particularly relevant for large language models, which are trained on vast web-scraped datasets that inevitably contain strategically corrupted or manipulated content.