Research map / Learning theory and algorithms / Sample complexity
Robustly Learning Single-Index Models via Alignment Sharpness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first efficient constant-factor approximate agnostic learner for single-index models with unknown monotone Lipschitz (unbounded) link functions under well-behaved (e.g., Gaussian, log-concave) marginals, via a new "alignment sharpness" property of the surrogate loss.
Problem
Agnostic (adversarial label noise) learning of single-index models under L2^2 loss with unknown link function; prior efficient agnostic results only achieved error O(sqrt(OPT))-type or W-dependent factors, and constant-factor results required known link.
Approach
Shows the empirical gradient of a convex surrogate loss, evaluated at the best-fit (empirically optimal) link function, correlates with w - w* with strength proportional to the component of w* orthogonal to w (alignment sharpness), independent of scale; alternates Riemannian gradient descent on the sphere for w with best-fit link updates, over a grid of norm guesses and with a test-based selection
Key results
- Achieves L2^2 error O(OPT)+eps with O(1) approximation factor for well-behaved marginals (including Gaussian and log-concave) and (a,b)-unbounded link functions with b/a=O(1).
- Sample complexity N = poly(W) Õ(d/eps^2) with poly(N,d) runtime; success probability 2/3 in the main theorem.
- Prior agnostic SIM result (Gopalan et al.) achieved O(W sqrt(lambda) sqrt(OPT))+eps, with error depending on sqrt(OPT) and linearly on W.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Alignment Sharpness learner instead of the prior unknown-link learner | Agnostic SIM learning · Agnostic SIM learning on (L,R)-well-behaved distributions | L2^2 loss: O(W \sqrt{\lambda}\sqrt{\opt}) +\eps -> O_{1/L,1/R,b/a}(\opt) + \eps | Helped |
Surprising findings
- The gradient of the surrogate loss can be negatively correlated with w - w* even when the L2 error is Omega(1), so standard sharpness fails for unknown link functions.
Limitations
- Requires b/a bounded by a constant, so general b-Lipschitz (a=0) links are not covered.
- Assumes well-behaved marginals with sub-exponential tails; the W-dependence in sample complexity is polynomial.
Experimental setup
Metrics: L2^2 loss approximation factor relative to OPT
Baselines: Wang et al. 2017 style omnipredictor learner (Gopalan et al.) known-link agnostic SIM learners
Builds on: surrogate loss of Frei et al. (2020) / Yehudai & Shamir sharpness well-behaved distribution class of Diakonikolas et al. unbounded activation class
Closest papers by meaning
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.91)
- Robustly Learning Monotone Single-Index Models (NeurIPS 2025 · similarity 0.90)
- Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.87)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.86)
- Zeroth-Order Sharpness-Aware Learning with Exponential Tilting (NeurIPS 2026 · similarity 0.85)
- Towards Robust Out-of-Distribution Generalization Bounds via Sharpness (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.