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

• URL: http://arxiv.org/abs/2605.29497v1
• Date: Thu, 28 May 2026 07:21:04 GMT
• Title: Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption
• Abstract summary: We study the problem of robustly learning Gaussian Single Index Models (SIMs) in the presence of heavy-tailed noise.<n>We give the first robust recovery algorithm with near-linear sample and time complexity for generic non-monotonic link functions.
• Score: 4.52430575477004
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Stability and Generalization of Straight-Through Estimators for Training Two-Layer Quantized Neural Networks [16.84694273405234]
  We study the identity straight-through estimator (STE) for training a two-layer binary-activation network with hinge loss.<n>Our central question is whether algorithmic stability can explain the statistical generalization of the estimator produced by the discontinuous STE training rule.
  arXiv  Detail & Related papers  (2026-09-06T07:12:16Z)
• Gradient-Based Latent Decomposition Reveals Mechanisms of Feature Degradation in Weakly Supervised Mammography [0.0]
  Weakly supervised hierarchical models exhibit a persistent asymmetry.<n> coarse lesion-type features are preserved under reconstruction while fine-grained malignancy cues degrade.<n>In high-dimensional spaces, a single coarse supervisory signal isolates only a 1D latent direction, forcing critical fine-grained features into the vulnerable residual subspace.
  arXiv  Detail & Related papers  (2026-07-24T01:04:07Z)
• On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity [3.9945187423832507]
  We cast sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set.<n>We show that neither can be removed: an minimax lower bound of $big((eLT/r)nbig)$ holds for every estimator.<n>Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.
  arXiv  Detail & Related papers  (2026-07-21T00:54:27Z)
• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition.<n>We propose a regularization-based framework combining a Huberized data fidelity with generalized folded-concave penalties.<n>We derive estimation error bounds of order $sqrtslog(n)/m$ that hold at emphevery localized stationary point.
  arXiv  Detail & Related papers  (2026-07-12T07:29:39Z)
• Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
  We study mean estimation of a random vector $X$ in a distributed parameter-server-worker setup.<n>Key challenges are adversarial measurements and asynchrony.<n>Results provide a unified finite-time characterization of robustness, identifiability, and statistical efficiency in distributed linear estimation with adversarial workers.
  arXiv  Detail & Related papers  (2026-04-07T11:45:55Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Identifiable Convex-Concave Regression via Sub-gradient Regularised Least Squares [1.9580473532948397]
  We propose a novel nonparametric regression method that models complex input-relationships as the sum of convex and concave components.<n>The method-ICCNLS-decomposes sub-constrained shape-constrained additive decomposition.
  arXiv  Detail & Related papers  (2025-06-22T15:53:12Z)
• Federated Learning Resilient to Byzantine Attacks and Data Heterogeneity [59.17297282373628]
  This paper addresses Gradient learning (FL) in the context of malicious attacks on data.<n>We introduce a novel Average Robust Algorithm (RAGA) which uses the median for both convergence analysis and loss functions.
  arXiv  Detail & Related papers  (2024-03-20T08:15:08Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
  We make the assumption of sub-Gaussian measurements, which is satisfied by a wide range of measurement models. We show that our result can be extended to the uniform recovery guarantee under the assumption of a so-called local embedding property.
  arXiv  Detail & Related papers  (2020-06-22T16:43:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.