Robustly Learning Monotone Single-Index Models
Authors: Puqian Wang
Nikos Zarifis
Ilias Diakonikolas
Jelena Diakonikolas
Venue: NeurIPS 2025 poster ()
Keywords: agnostic learning
PAC Learning
single-index models
Primary area: theory

Abstract: We consider the basic problem of learning Single-Index Models 
with respect to the square loss under the Gaussian distribution 
in the presence of adversarial label 
noise. Our main contribution is the first computationally 
efficient  algorithm for this learning task, achieving a constant 
factor approximation,
that succeeds for the class of {\em all} monotone activations with bounded moment of order $2 + \zeta,$ for $\zeta > 0.$ This class in particular includes all monotone Lipschitz functions and even discontinuous functions like (possibly biased) halfspaces. 
Prior work for the case of unknown activation either does not attain constant factor approximation or succeeds for a substantially smaller family of activations. The main conceptual novelty of our approach lies in developing an optimization framework that steps outside the boundaries of usual gradient methods and instead identifies a useful vector field to guide the algorithm updates by directly leveraging the problem structure, properties of Gaussian spaces, and regularity of monotone functions.

Robustly Learning Monotone Single-Index Models
Puqian Wang
Nikos Zarifis UW Madison zarifis@risc.edu
Ilias Diakonikolas UW Madison ilias@cs wisc edu
UW Madison
pwang333@wisc.oo edu
Jelena Diakonikolas
UW Madison
j jelena@cs wisc edu
Abstract
We consider the basic problem of learning Single-Index Models with respect to the square loss under the Gaussian distribution in the presence of adversarial label noise. Our main contribution the first computationally efficient algorithm for this learning task, achieving constant factor approximation, that succeeds for the class of all monotone activations with bounded moment of order + Ç, for < 0. This class in particular includes all monotone Lipschitz functions and even discontinuous functions like (possibly biased) halfspaces. Prior work for the case of unknown activation either does not attain constant factor approximation or succeeds for a substantially smaller family of activations. The main conceptual novelty of our approach lies in developing an optimization framework that steps outside the boundaries of usual gradient methods and instead identifies a useful vector field guide the algorithm updates by directly leveraging the problem structure, properties of Gaussian spaces, and regularity of monotone functions.
Introduction
Single-index models (SIMs) [Ich93, HJS01, HMS+04, DIS08, KS09, KKSK11, DH18] represent fundamental class of supervised learning models, widely used and studied in machine learning and statistics. The SIM framework captures scenarios where the output value depends solely on a one-dimensional projection of the input, i.e., it contains functions of form f(x) = a x), R is an unknown activation (or link) function, and E Rd an unknown parameter vector. While the activation function is generally unknown, it is often assumed to lie in a "well- behaved" family, e.g., is monotone and/or Lipschitz. addition to being well-motivated from the aspect of applications, such regularity assumptions are also necessary for ensuring statistical and computational tractability of the underlying learning task. Indeed, without such assumptions, learning SIMs can be information-theorette the.reetcoraallyyy impossible (see, e.g., (ZWDD25)) or computationally for Gaussian data. Classical works [KS09, KKSK11) 1] demonstrated that SIMs with monotone and Lipschitz activations can be learned efficiently in the realizable case (i.e., with clean labels) or zero-mean label noise, under any distribution on the unit ball.
where
intractable [SZB21]-ene
In this paper, we consider the task of learning SIMs in the (more challenging) agnostic model [Hau92, KSS94], which the labels may be arbitrarily corrupted and structural assumptions are made on the noise. The goal of an agnostic learner for target class C is to find a predictor that is competitive with the best function C. More concretely, D denote distribution over labeled pairs (x, 3) Rd x R. and let the squared loss of predictor f IRd - IR be given by L2())
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

D(xx))-D((((x)-- -. Given access to i..dd samples from D, the learner aims to output hypothesis with error close to the minimum loss OPT := jec C2()) attainable by any function in the class C.
In our context, the target class C' will refer to the class of SIMs with unknown activation and parameter vector, namely functions of the form f(x) = (w x). The only assumptions we make are that the norm of the parameter (weight) vector is bounded, i.e., ||w]2 S W for some W 0, and that the activation function belongs to a known family of structured monotone functions. For a pair (w, o) defining the SIM fxx = a (w- x), we write L2(W; r)) E E(x.))>D((r((w x) y) to denote the squared error of ʃ. We now formally define our learning task.
Problem 1.1 (Robustly Learning SIMs). Fix a family F of univariate activations. Let DD be distribution of (x, y) E &R x IK such that its x-marginal DDx is the slandard normul. We say that an algorithm is C-approximate proper SIM learner, for some C 2 1, if given > 0, W > O, and i.d. samples from D, the algorithm outputs activation ō E F and a vector W E IRd such that with high probubility it holds L2(W; T) S C OPT + c, where OPT _ mi (a(w))
The focus of this work is on developing polynomial-time algorithms that achieve a constant factor approximation to the optimal
((1)-independenn) of the dimension or any other problem parameters. Achieving = (for the case of Gaussian marginals studied here) is ruled out by computational hardness results [DKZ20, GGK20, DKPZ21, DKR23J. Moreover, even for constant- factor approximation, strong distributional assumptions are required [DKMR22, GGKS23J.
i.e., C
Motivated by the pioneering work of [KKSKI1], central open question in the algorithmic theory of SIMs has been to design an efficient constant-facte factor approximate SIM learner that succeeds for the class of monotone and Lipschitz, activations. While significant algorithmic progress has been made on natural special cases of this task [DGK xxx+20 20, DKTZ22b, DKTZ22a, ATV23, WZDD23, GGKS23, ZWDD24, GV24, ZWDD25], the general question has remained open:
Does there exist an efficient constant-factor approximation algorithm for learning monotone & Lipschiizz SIMS under Gaussian inputs?
As our main contribution, we resolve this question in the affirmative.
Theorem 1.2 (Robustly Learning Monotone & Lipschitz SIMs). There exists a universal constant
C > 1 such that the following holds. Let C be the class of all SIMs on Rd with monotone and L-Lipschitz activation. There is an algorithm that, given e > O and W >> 0, draws N d' polyy(1ee, W, L) samples, rums in Poly(N) time, and returns a predictor (ō, W) such that, with high probability, L2(W;;) S COPT+C.
We reiterate that the approximation ratio of our algorithm is universal constant monstant--ideppedeen of the dimension, the desired accuracy, the Lipschitz constant, and the radius of the space.
worth noting that our algorithm does not require the Lipschitz assumption on the unknown activation. In fact, it applies for the broader class of monotone activations with bounded (2 + () moment, for any C >> (Corollary 2.4). This in particular implies that the case of Linear Threshold Functions (LTFs) fits in our class. As pointed out in [ZWDD25], the bounded moment assumption on top of monotonicity is essentially information-tteorrticall theoretically necessary (in particular, bounded second moment alone does not suffice).
Comparison to Prior Work The most directly related prior work is [ZWDD25], which gave an efficient constant-factor approximate learner for the known activation version of our problem (i.e., for a known monotone activation with bounded (2 + () moment). Independently, [GV24] developed an efficient constant-factor learner for the special case of general (biased) ReLU. Interestingly, even for the special case of known activation (c.g., a general LTF or ReLU), obtaining an efficient constant- factor approximation for more general structured distributions (beyond the Gaussian) remains open. The special case of LTFs, where the first such constant factor approximation was obtained in [DKS18], appears to be a significant bottleneck to go beyond the Gaussian case.
Regarding the SIM version of the problem, prior work either did not achieve a constant- factor approx- imation or succeeded for significantly smaller class of activations. Specifically. [GGKS23] gave an efficient SIM learner for monotone 1-Lipschitz activations, for any distribution with bounded second moment, with error guarantee O( (OPT) + (under the technical assumption that the labels are bounded in [0, ID.. In addition to the sub-optimal dependence OPT, the multiplicative factor inside

---

the big-O O scales with the radius W of the space. Subsequently, [ZWDD24] developed an efficient constant-factor SIM learner under structured distributions (including the Gaussian), albeit for a much smaller family of activations. Specifically, for parameters b >> O, the activation family considered in [ZWDD24] contains all functions a + IR such that o²()) S b everywhere and o d' 2 a > 0 for 2 2 0. The final error bound of the algorithm in [ZWDD24] is (pooy(b/a))
+ This guarantee is vacuous as + 0, i.e., for the class of monotone b- L-pischiiz functions.
1.1 Technical Overview
Before getting the details of our algorithm and its analysis, first provide "the big picture" of the conceptual novelty of our approach. Prior work on agnostic learning of GLMs and SIMs has as one of its main components gradient-based algorithm applied to either the square loss [DKTZ22a], its smoothing [ZWDD25], or a suitable surrogate [GGKS23, WZDD23, WZDD24, ZWDD24). Such approaches are reasonable, considering the long history of gradient-based optimization methods and their applications in learning. However, the considered problems are not black-box, and if we think about optimization algorithms as choosing vector fields guide the algorithm updates, then the "negative gradient" appearing in gradient-based methods is but one possible choice that could work.
On conceptual level, our work makes the case for stepping outside the usual boundaries of gradient- based methods and instead looking to directly design a vector field that can be computed from the information given to the algorithm and that carries useful information about the location of target solutions. In the spirit of prior work such as [WZDD23, WZDD24, ZWDD24, ZWDD25), this useful information is captured by the alignment of the chosen vector field and a target parameter vector w
We point out here that this a rather nontrivial goal: even the case of GLMs (known activation), the negative gradient of the square loss (as used in e.g., [DKTZ22al) a standard surrogate loss (as used in e.g., [WZDD23]) can "point in the wrong direction" " on some monotone Lipschitz functions (see the discussion in [ZWDD25]). This issue was addressed in the recent work [ZWDD25] by demonstrating that the negative (Riemannian) gradient of the squared loss with Gaussian-smoothee activation, L.p (: or) (1/(2p)) E(x.))>DD -ly-Tpar (w x))?), correlates with w" for an appropriate choice of the smoothing parameter o E (0, 1). Here po, E (0. 1), is the smoothed activation using the Ornstein-Uhlenbeeck semi-group; see Section 1.2 and Appendix A for details.
Briefly, [ZWDD25] shows that when w is still far away from the target w", the Riemannian gradient WV o) E(x,))>=l(y- (p x))T,ot (w- - x)x w] = (x p p (w x)x w] possesses the 'gradient alignment' property, that (denoting = 0 w ))
-VwCp(W;o)) w 2 0
(Tecs (w x)T (w x)] v /OPT sin T X
E
Then, by carefully and adaptively updating the smoothing parameter p that p RS cos (for simplicity, we take & = cos f below), we have - Looo
w" 2 sin @l| 2o' 1|2 VOPT sin 0 | p which implies that - W ol (W: w 2 sin? 2 Te Too |3 when sin 0 Σ v VPPT/ITTC. cos 8o' وواا in other words, -V woos (W; (w) aligns well with the target direction w" when 8(( (w, w*) ) is large. Consequently, [ZWDD25] proved that the algorithm linearly converges to w" until w is too close to w" (and the alignment condition fails), in which case COPT + e eπror solution is found.
critical issue arises, however, when trying to adapt the methods from [ZWDD25) to the SIM setting: the correlation between w* and the Riemannian gradient V Lues o (w; u) becomes uncontrollable, even if we choose u as the "best-fit" activation given w. To see this, a simple calculation shows that
V Leus o (: u) w =
[VT oul (w x)x w ww] (x.v)>D
E
2 sin 0
E [Toos eo' (w- x)Teos ou'(w x)] VOPT sin 0l 112 x
Even though it is possible to control the L3 distance between u(2) and (2) by 0(w, w*) following similar steps as in [ZWDD24), it is unclear how to show that Teus oud (z) is close to Teae 00 (2)
"x' w here denotes the projection of x on the orthogonal complement of w w = (I ww )xx Note that -w is independent of w x (as x is standard Gaussian), hence Ex [T (w-x)T, T) (w-x)x-- = O.
Here, A 2 B means that there exists universal positive constant C' so that A > CB.
3

---

u) w" 2 O co and the arguments of [ZWDD25] can go through. Intuitively, the smoothing operator Tos 9 filters out the high-order components of the derivative of the activation o' in the Hermite basis while keeping only the low-order components. Thus, to ensure || (TTcsoo' T oo I| is small, necessitates approximating the low degree coefficients of o' (under adversarial noise and without the knowledge of Ø), imposing formidable technical challenges. In partieular, it is unclear whether prior SIM learning frameworks [KKSKII, ZWDD24, - alternating between the "best-fit" updates for activation and gradient-style updates for w-can resolve this issue. Hence, our work represents a departure from this seemingly natural approach.
that -V
Alignment with a New Vector Field Our method deviates from prior works in that we no longer cling to the gradient field of a particular loss function, but rather, we identify a vector field that aligns with w" without the need to estimate the targer function a on the run. Revisiting the correlation between the gradient of the smoothed L loss and the target vector w - o (W:o)) ww = ((x.))>D [/T cos cos
oa' (w x x)x-_W w"). we observe that the right-hand side of the equation consists of three parts: the label y, random variable x x-w w" that is independent of w x, and a function Toss no' (w- x) of w x that is not available when a is unknown. Critically, we replace the unknown function Tens @o (z) with any function h=z) such that [[b(=)][ı, 1, and ask: which function h- (2) maximizes the correlation (hh := (xx,))=D _yx w xx] w*? Let ho(z) = Toos oa' (z)/ cos o0' Ing. By maximality of h", we know that the correlation K(h") is at least as large as K (ho) = - w Woos el o) w" /IlT so' L.g. indicating the vector field H. == ((x,)) yyx "ht "h" (w x)] is at least as good as the gradient V ( o) of the smoothed loss with respect to the target activation 0, after normalization.
In fact, letting V
(w /ll( ///[[[W"=/)/ ) 1/2 and w' -cos cos@w + sin Ov we can write K(h) as: (yh(w (w- x)w* x _w] = sin Q
((h)-
E (x.
E x~
E (x.))=D
[VVV x) w x]][(w x)] (1)
Consider the L2 space of the standard Gaussian random variable w x equipped with the inner product (a, b) = Ew-x~.rle (aa 6]; it is known from duality that (a, b) < ||||ا,||اl with equality if a a= b almost surely. Hence, the choice h" h"(w x) Elyy x w - x Elyv x w x]]laa maximizes Equation (1). Having access to such h" would guarantee that the corresponding update rule using H. (xx,))>Dlyx - Whh" (w- - x)] performs at least as well as the gradient descent on the smoothed loss Loce (w; ow: is precisely the update of [ZWDD25] used in the case of known a. Note that by the definition of K(h), we have K K(h") sin fy H
There are two obstacles in finding such an h²: 1) the learner does not have knowledge of w", and 2) even if the learner knew w", it would not be possible to estimate h (2) = Elyy X w x (as the probability of observing single point twice is zero). For this reason, we need to consider a different way of finding an update rule.
=1/ll Elyv", x x1Il Lg on any desired point
The Spectral Subroutine For the first obstacle, our critical observation is that instead of estimating ht,, we can approximate the vector H directly via spectral methods. Let us define g²(x) (z) == w
E(x,))~DD [yx
W x =x= 2] and consider the matrix M Ex-NN [gw (g (z)get (z)T], T]. Observe that
( M = E
[(
E JUX
-wx-
V W -
[xxx)) x]) = (V H E Elyv X | /wwwxxx w-x]llma
x=Dx
(x.I)~D
K(ht)
K KTTooo
E Elyv
X
W
x 11 sin T| cos 60"
Elyv
x w x x|]11
sin 0
Lbg
where in the last inequality we used the maximality of K(hi), The first equality above also implies V M v Elyv x w x]]22 therefore, we have (v M vw) 1/2 we know that H. is least as aligned with w' as the gradient vector - o (w; 0) and we know from [ZWDD25] that K (TTooa ga") = - WW o)- w 2 sin? 0J oooesoo 12, > 0 since the gradient alignment condition holds, we get that both v V, and v H are far away from O. This implies that much of the information on H. is contained in v and, in addition, vi is contained in the eigenspace of the large eigenvectors of M Furthermore, we show that for any direction u that is orthogonal to v both u M & OPT and H; u S vOPT are small. In other words, H. is almost completely captured by v and v is effectively contained in the space of the highest eigenvalues. Consequently, H; is approximated by the top eigenvectors of M
v H Since

---

The second obstacle is to estimate the function gw (z) -(xxa)>-Dlxx " w.wxx 2] that constructs the matrix M This is not trivial task even in the noiseless setting because we are conditioning on hyperplane that has measure zero in the space. One would hope that conditioning on small bands suffices for this purpose; namely, that if w x E (a, b) with bb - al = poly(c), then for all E (a, b) it would be Elyx-w w x w.x. x E (a, b)]. Unfortunately, since the labels are adversarially corrupted, the
Approximation and Regularity of Monotone Functions
2] ~ Elyx adversary could corrupt y for each value of w xx- 2 in which case such an approximation would not yield an accurate estimate. Instead, we proceed as follows: consider restricting h(z) to be a pecewise-constan function on a fixed set of small bands & = [a, 1,+1), E [4]. We show that the argument about maximizing K (h) on continuous functions h can be carried out similarly to piecewise constants, Let h" be the piecewise constant function that maximizes K (hh) We further show that Toosed can be approximated by fixed value on each band & Hence, using a piecewise-constant approximate function T To 80', we have that 0 & ( mono RJ ((Tcos00') < K K(h"), and thus the argument that large eigenvectors of M = E2- ((w (z)g (z) contain information about H. can be extended to M = E (ow-v//w())))) (z) (2) where gw is the piecewise constant version of gw (z), which can now be efficiently estimated.
Optimization via Random Walk A final obstacle this approach is that both u and uu are eigenvectors that correspond to the maximum eigenvalue and we cannot determine whether u or -u correlates positively with w To address this issue, at each iteration, we pick the direction from {u, - at random. Consequently, with probability 1/2, the algorithm will decrease the angle with w Consider the random variable Ze ((w(t), w w the angle between w, and w*. Let O" be the largest angle such that if Z, S 0" then (2(w 5 ((OPT) - e. Furthermore, let 8o = ((w((), w*). Assume without loss of generality that the initialized vector w( is not constant approximate vector, hence 8g 2 = Now let T = infe(t 2 1 Z, S 0*) i... Ti is the first iteration that has Zr, < 00," and let 72 inf 1| Ze 2 0o). Pr < <T2 2 > 0, then repeating the process O(1/a) times guarantees that with high probability the event Tı < T2 happens, Note that: Pr(m < r2 Pr[chooses the correct direction for all the T steps until Z, S 6*) 2 We will show that T & log(BL/c). Thus, we have Pr[m < Tg. 2 1/2" poly(c, 1/B, 1/L). Therefore, repeating the algorithm 2n poly(1/c, B, L) times suffices.
1.2 Notation and Preliminaries
For n E Z,, let [n] == f1,.... .n... We use bold lowercase letters to denote vectors and bold uppercase letters for matrices. For x E Rd, ||x||2 denotes the f2-norm of x. For a matrix M E Rdxd, |M]]2 denotes the operator norm of M. We use x y for the dot product of x, y E Rd and (xx, y) for the angle between x, y. We use 1 (A) to denote the characteristic function of the set A. For unit vectors u, we use u-v to denote the component of u that is orthogonal to i.e., u-v (I vv )u. gd gd-1 denotes the unit sphere in Rd and IB denotes the unit ball. For (x, y) distributed according to D, denote by D the marginal distribution of x. We use D'N denote the empirical distribution constructed by N i.i.d. samples from D. We use the standard (.)),
2(-) asymptotic notation and Ō(-) to omit polylogarithiic factors in the argument. We write F. 2 F for two negative expressions F. and F to denote that there exists some positive universal constant c > 0 such that E 1 F. E S F is defined similarly. We write E ~ F if S F and E 2 F. We write E > F if there exists large universal constant > 0 such that E 2 CF. E &
similarly defined.
Let (0, I) denote the standard d-dimensional normal distribution. The L2 norm of a function with respect to the standard normal is || = (lx)) while ||9]|... is the essential supremum of the absolute value of g. We denote by L L2(N) the vector space of all functions Rdd IR such that |lf oc. An important tool for our work is the Crnstin-UUhlenber semigroup, defined below.
Definition 1.3 denoted by Tp, is linear operator that maps a function E L2(N) to the function Tpg defined as: (x)))()= = El~N v1-p²z)).
Semigroup). Let p E (0, 1). The
semigroup.
5

---

2 Robustly Learning SIMs
We consider distributions D over (x. y) I2 x R with x (O, I), and predictors of the form (x) = (w (x), where ||w|] - W and a is monotone. We assume that the target activation o is c-close (B, L.-Regular function, that satisfies the following conditions:
Definition 2.1 ((B,L) L)-eull Monotone Activations). Given parameters B.L we define the class of [B, L)-Regular activations, denoted by H.BB, L). as the class containing all functions : R + E. such that 1) || S B and 2) |o'll < L. Given > O, we define the class of e-Extended (B, J.)Regular activations, denoted by (B, L.,, as the class containing all activations
01 : -> for which there exists d2 E H(B L) such that [0] - 0221222 100121
S.
Remark 2.2. Instead of directly enforcing norm bound |/w]| W. one can assume that H. L) that we compete against is chosen so that it contains all the activations 0(2) + (A2)) for all S W. This lets us focus on the core statistical challenge without separately tracking norm constraint on w.
Learning with respect to the class of activations H. (B, L) allows us to make the following simplifying assumption that comes at no loss of generality. We can assume that the labels y are truncated in the interval [ B, B), and, as result, we assume that ly| < B (see Fact A.9). Our main result is that Algorithm efficiently generates solution pair that achieves COPT + error:
Algorithm 1 Main algorithm
1: Input: Parameters B, L, e, 6; Data access (x, y) D, empty set Stol
2: gini & Initialziation [B, c] (Algorithm 2), Sthol <- Sini
3: Sample N i.i.d. samples ((x(), y from D and construct Dy
4: for w0 E
Çini do
5: for 0 E θ = tke /I: : k [ do
6: Run SpectralOptimizzaioon/ [8, w( DN] (Algorithm 3) and get S.
7: Stol < Sool U.S
8: (w, ū) = [est[S (Algorithm 5).
9: Return: (w, ū).
Theorem 2.3 (Main Result). Lete O let B, L > O. Let be a distribution over (x. y) E Rd x R with x (O, Ia). Lei (w", E TRd x (B, L) be a pair of vector and monotone activation such that Lo [w" :a) = OPT. Then Algorithm I draws N = de popyyBBB (B, L, 1/e) samples, it runs at most poolyNN, d) time, and it returns a vector w and a monotone and Lipschitz activation i : RR + IR such that with probability at least 2/3, it holds that L2(W; ū) S O(PPT) +
Using the fact that any monotone function a with bounded 2 + moment (=- S B. is an e-Extended (B, Re-Rgul with B, L = poly((B./e) 1/e) (see Fact A.7), we have:
Corollary 2.4. Let e, > O. Let (x, D with Dx = (O, Let w E Rdd be a unit vector and let be a monotone function with bounded (2 + () moment, i.e., B2>N(la(()))1 Ca(w"; σ) OPT. Then, Algorithm I draws N = dt (oly((B,,, ////e)//,, 1/c) samples, runs in at most poly d) time, and returns a vector w and a monotone and Lipschitz activation ā R + IR, such that with probability least 2/3, it holds that L2 û) O(OPT) + c.
S Ba, such that
Note further that monotone L-Lipschitz functions belong H.,B,, with B O(L see Fact A.7.
The body of the section is organized as follows: in Section 2.1 we prove the correctness of the initialization subroutine; in Section 2.2 we present the main component of our algorithm, the spectral subroutine and show that it generates pair of solution achieving small error; Section 2.3 presents the proof of the main theorem (Thcorem 2.3).
2.1 Initialization
In this section, we present the initialization algorithm. The goal of our initialization is to find a vector (0) such that ((w( (0), w*) < 1/M, where M is the smallest threshold such that
E ([o(z) (M) > MI < C(OPT+e)

---

for some large absolute constant C; in other words, we can truncate the activation a(2) after |a| M M without inducing much error. To find such a vector w("), we design a label transformation Tτy) = 1y 2 t) for a carefully chosen threshold and transform the regression problem to a robust halfspace learning problem, following the same procedure as in [ZWDD25] (see Section 4.3 of [ZWDD25]). Since (unlike in [2WDD25]) a unknown, neither this threshold nor the parameter M are known to the learner. Our workaround is construct a grid of possible thresholds I, (we argue at most B/Ve of values the grid suffice) and argue that with high probability there exists threshold 1" such that the initialization succeeds. We store all the vectors generated by the initialization algorithm, based on all these thresholds. We find the correct parameter vector in the final testing stage of the main algorithm. The proof of the following lemma is deferred to Appendix B.
Lemma 2.5 (Initialization). Lei ( x) be hypothesis that satisfies Pix.))~llly-o(( (ww x)) <
O E, where a a noc-deccgg e- Extended (B, L) -Regulr function. functiionn Suppose that no constans hypothesis, i.e., function of the form (=) for any E R. is constant- approximate solution. Let C > 1 be a large absolute constant and let M >> be the smallest parameter such that (z~N((o(z)) a { 2 MY] S C(OPT + c). Then Algorithum 2, using Odd/ log ()) samples, with probability at least 99%, returns a list Sini of O /c) vectors that contains a vector
w(0) such that 0( ((w()) w*) v
Algorithm 2 Initialization
1: Input: Parameters B, e; Data access (x, 3) ~ D; S +0. 0.
2: for i = I, I,..., [B/vE]] do
3: 4; = ivE, transform the data to D, = (x, T(y; (:)) where T(y = 1(y 2 4J.
4: Run the Robust Halfspace Learning algorithm from Fact B.2, get parameter (0,6)
5: S -SU (w(0.))
6: Return: S.
2.2
The Spectral Subroutine
In this section, we present our main structural result (Proposition 2.6). We show that-even though the target activation a is unknown-we can identify vector that has a strong correlation with an 'ideal descent direction' v. : (w')_w/]] /I| [[/][("""))) (w*) I12 It is not hard to see that V. can be used to rotate w towards w". The vector that we identify is a top eigenvector of matrix Mw that can be efficiently estimated using sample access to labeled data. We can only identify such target vector
up to its sign; however, as we argue later, this is sufficient for our argument to go through.
To build up this result, we need the following technical pieces: (1) the spectrum of the matrix Mw contains information on v i.e., V -Mw V is large (Lemma 2.7); (2) All the other directions that are orthogonal to v have small quadratic form value compared to v i.e., u n- & v M v and therefore, the direction v stands out in the spectrum of the matrix Mw (Lemma 2.8); (3) finally, we argue that the top eigenvector Vw of Mw correlates strongly with v. (Lemma 2.9).
Algorithm 3 Spectral Optimization
1: Input: Parameter 0o: Initialization vector w (0); Empirical Distribution Dx:
2: Sool <- 0, Φi < 0(1 - 1/ 118)) th +- sin oi / K < poly(1/e, L) and T - ((log(1(eeL))
3: for k 1...., K do
4: for t-=- = 0......7 T do
5: Let Bw(()
(0)
E (x [yx! 1 (w((t) E Ej1l, j E [M].
6: Compute the empirical matrix M Mwie <- Σソ Wi wes) /Pres/oo. E Eg).
7: Find the top eigenvector u of Mwco, then randomly pick (()) from {tu).
8: (k+1) +- projga (w(() - -nv())).
9: Sool_ S U (11).
10: Return: Sool.
Proposition 2.6 (Spectral Alignment). Fix parameters B,L 0 and 6 O. Let D be a distribution over (x, y) E Rd x IR with Dx (N( Ia). Let (w", 0) E Rd (B, L) be pair of vector
7

---

and monotone activation such that Co(w":o) = OPT. If 2 d L, L.1/e). then with probability at least 99% the following holds: for any unit vector w E TR satisfying sin ((w, (") 2 40VOPT/II| cos (( w 0 o'|l L2 the top eigenvector
I of the empirical matrix Mw returned by Algorithm 3 satisfies u w = and |u- w"1 Z (22/2) sin ((),
The rest of this subsection develops the machinery required to prove the proposition above. Further details and complete proof' are deferred to Appendix C.
[ZWDD25] showed that (Proposition 2.2, [ZWDD25]) given the target activation o, the gradient vector of the smoothed L loss correlates strongly with w": when sin 0 2 3 3/OPT/ || 80 L2 Wo e (w; w = Exx.))>=Dl/ clt.cllloocccooyi (w.x)x+"*> -x)--xxxxw-w>>- w 2 (2/3)][Tcos eo'1 sin However, the structural result above requires the knowledge of which is not applicable to our setting. Instead, we argue that using the vector (z) defined below, the top eigenvector of the matrix Mw = E Eg Bw (=) correlates with the "ideal" update direction v = (W")-w /lww//(ww>)))) 1|2:
((x 1yx [( x E E,11 1f2 12EEE) &,,
gw(z)= =
Pr(w x Ej]
(Grad)
where {
&, = 01:1 I- 11 M + + A= 2
M' = O( OlV/oo(BB/)))) -
We first show that the target direction v lies in the space of eigenvectors of large eigenvalues.
Lemma 2.7. Let gw (=(z) be the vector defined in (Grad), let Mw Ez~N/Bww gw (z) and
V (w - L /Il ( Suppose e S OPT and sin 0 2 AvOPT/|| g (2)ll(2. Then, Mw V 2 (1/16) sin OoTTos 60'0
(ve)
Proof Sketch of Lemma 2.7. Define the correltation K K(h(w - x)) = E ((x.>-Dlyv x x)]
where h(z) H' = {h: h(z) E/=1 h,1 E E,}, |||||| L2 1}. and =,i== I,...,4, are the same intervals as in the definition of gw (2). (Grad), One can show that (h) can be written as: K(h(w- sin (h(22,, va gw (2)) La Lo (N)) where (:,') (z('(..))) is the inner product defined on the L2 space with respect to the standard Gaussian measure. Therefore, by the duality of norms in the Hilbert spaces, we have h" h2) = =V gw (z)/llv "g gm()))le, maximizes K K(h). Next, observe that by the definition of Mw and gw (2), holds (vw) "MM V. = (llv 'g (=)]lez/ sin 0) K (h" (h"(w- Ei T Teosee @o (a:)1(z E E where & = [a;, 04+1) as defined in cos oo loll,, E H' and by the maximality of h" we have (vr) MM 2 (llv: (=)())l sin 0) (ho x)). One can show that it holds K K(ho(w x)) 2 sin? 2 [oos o0'll L, and that V Sw (3)]le, = ((vi)) ( Mwvx))? 1/2 Thus, we obtain that (v&) Mw v 2 sin? 2 Tol 112,.
x)). Now define Too)
(Grad). Then, ho(z) = T Toos)o'(=))
The next lemma shows that any vector that is orthogonal to vi has a small quadratic form. Lemma 2.8. For any unit vector E Rd orthogonal to vw, we have u M u & 20PT.
Then we show that the top eigenvector v of Mw correlates strongly with the target direction ww- Lemma 2.9. Let vw be the top eigenvector of Mw. If 0 2 40/OPT//|T..odd [| then Vw V v3/2.
What remains is to determine the required number of samples so that we can have an accurate approximation of Mw, which is characterized in the following lemma:
Lemma 2.10 (Sample Complexity). Draw N 2 d c, B, L) i.i.d. samples from D, and let Mw be constructed as in Algorithm 3. Then, with probubility at least 99% for all w E 3d-1, it holds ||M Mw || S
We can now proceed to the proof sketch of the main structural result (Proposition 2.6).
Proof Sketch of Proposition 2.6. Let 0 = 0(w, w*) and assume that sin 0 2 40/OPT/ cas go r.g. In Lemma 2.9 we proved that for any unit vector w, one of the top cigenvectors Vw of My correlates
8

---

with :w: 0(v Vw) S T/6. Next, in Lemma 2.10, we proved that using N = O(d (olyy(//e, samples, for any unit vector w, the empirical matrix Mw satisfies || Mw S e. Further- more, one can show that the eigengap of Mw is greater than 60c (Lemma C.8). Therefore, using Wedin's 's theorem (Fact C.7), we know that for any vector w, the top eigenvector Vw of Mw satisfies (V., Tw) I 1/59, indicating 0(Tw, vw) & V(Vw. Vw) + @Vv.. V.w) S 7/44. Therefore, let u be such eigenvector V of Mw that correlates positively with v Note that by defimition of Mw. it must hold u 1. w. Thus we have u u-w" = (-(cos(0)w (eollw/-sss(((/ + = (in(0)uvvz. 2 (V2/2) sin(O). L
2.3 Proof Sketch of Main Theorem (Theorem 2.3)
Full details are deferred to Appendix D. In this proof sketch, we assume that are initialized at
the correct w() that satisfies 0( ((w(() w*) S 1/M, where M is the minimum value that satisfies
[z~r((((==) - (MM) {12] 2 M) I C(OPT + c). In other words, according to Fact A0 for any vector w such that ((w I 8(w (0) (w)),,""), it holds Exx,))DDK - o(w x)) I COPT + sin 0
112.. Denote the angle between w((t) and w² by 0g = f(w((), ,
Furthermore, let the = 0(1 - /3)3 and T = esin di/4 where e = 1/4 S 22/2. We can assume without loss of generality that e S OPT. According to Proposition 2.6, as long as sin 0. 2 /0OOPT/IIT.om cos o,
with probability at least 99% the vector v(t) returned at Line (7) of Algorithm 3 satisfies /v(() . w"1 2 esin Og and v(() w(() 0. We de- note by Pe the event that v(t) negatively correlates with w*. We consider the following event R2 = fsin 0: 2 /OOPP///Teoo,0 } where C >> 0 is an absolute constant.
We show that conditioning on the events R,, Pr, E [T'. for all & T, it holds that Φ. O.. We use induction. By assumption, we have that do 2 Oo. Next, we assume that d, 2 Oz. Let us study the distance between (()) and w" after one iteration from t to + 1. Since v(t) is orthogonal to w(t), must be [] - 7/c v'1 1/2 2 1, therefore, ((+1)) = projs (w (1) - (v)())). By the non-expansiveness of the projection operator, we have
||w(+1)] w' 1 prrjj (w(1) ()(( w11 < Il m)((() -w"1l
= =/|w(0 (1) w 12 + n v (1) | 21% (1) (w) - -w") = (t) w 12 + ne + 2n. (t)
w", (2)
Note that [/w(()) w 1 || || 13 1/3 = 2(cos 0c+1 - cos 0.) and using the identity about the sum of cosines, we have 4 sin (0++1 - 02) sin( 1 + 0,)/2) S ni + 2np(!)) ww.
First, consider the case where 28, 2 0i 2 0t. From Proposition 2.6, we have that v(9) -w" S - -csin where e > is an absolute constant. Hence, since we chose 1)- = csin / it holds no + v() w" < -c² sin Φi sin 0,/4. Therefore, in this case, 0,+1 I 6,, hence sin( (0,41 + 22) I 0i Using the inequality x/4 4 S sin x S x for x E 7/2). we have 0.+1 S 0, (1-11-0 2 /32) S dr+1-
For the next case where s; 2 20,, if 0z+1 S O2 then 0z+1 S S1+1, so we need to consider the case where 41+1 2 9r. We need to bound the maximum increase of 6.+1. By the triangle inequality and the non cannexpansiveness of the projection operator, it holds
2 sin (0.+1 /2) = || [(+1) w 1l2 = I (w(() - ()
w'lla S || n.v(1) - w'll
(w(() (t) w 1l2 + 17: || ||2 = (in + csin 02/4.
From the assumption we have 0, < 01/ therefore, choosing S 1 1/4 and since sin(x) S x for E
(0, n x/2) we have that (fn( S sin /4) + csin dx/8 S 9 Therefore, since (5/8),r x S
sin x when x E (0, 722 we have sin(0. 2 (5/16)6,41 and thus, 6,41 S (9/10)ø: I (1
e² e2/22)o: < Φ1+1. This completes the induction argument that 0,+1 S Φc+1.
Conditioning on the event that all P,'s are satisfied for t E [T]. one can show that due to the contraction of 92, i.e. 0 < (1 2² /32) do 5 21-22/32) fp. the algorithm will arrive at a vector w such that 0 = 0( W, w*) satisfies sin 0 < / VOPT/ eos @o'll [h in at most T₁ < T = C' Cogo (Lc) iterations, for some large absolute value C". This implies that w satisfies E Bixw))p((y-off (ww-lllyywwwwooooooo P]
COPT + Let Ti T be the first time that R, is not satisfied.
Next, we need to bound the probability that all P, (correct direction choices) are satisfied. The events Pt are independent, and each occurs with probability at least 1/2. The probability of Ti such events

---

occurring is at least (1/2) Since Ti = this probability is bounded below by 8' = (1/2)" = poly(e, If we rerun the algorithm K (((1/")) (1/)) times (Line 3 of Algorithm 3), by standard Chernoff bounds, with probability at least 6, there will be at least one run where all P. are satisfied for all E [7i].
Next, we show that given all the constructed candidate solutions, the testing subroutine (Algorithm 5) with high probability returns an activation and direction pair that achieves O(OPT) + error.
Lemma 2.11 (Learning the Predictor and Testing). Algorithm 5 given n poly (B, L, L/e) samples and set Stol of poly(B. L, 1/c) vectors, with probability at least 99% returns solution pair (ww, W), with New being Lipschitz and monotone, and w E S such that B(x.y)~D (T ( x)
))²] I C' Ceminwesu B(x.))>D((o((w x) y) + for some universal constant C.
Using Lemma 2.11 and the fact that there exists w E S that satisfies E(x,)>D((y o(w x - COPT + 6, Algorithm with n = poly [B, L, 1/e) new samples returns with probability least 99% a solution pair (ww, W where Uh Lipschitz and monotone and w Sool such that E -x (0 (w- x) y) COPT + This completes the proof.
3 Conclusions and Future Directions
This work resolves recognized open problem in the algorithmic theory of learning SIMs, by devel- oping the first polynomial-time constant-factor robust SIM learner for monotone activations under Gaussian inputs. At the technical level, alignment-based spectral framework bypasses the limita- tions of gradient-basee of dimension, radius of optimization, noise level. An interesting direction for future work is to generalize our algorithmic guarantees beyond Gaussian marginals, e.g., to all isotropic log-concave distributions. This question is open even for agnostic learning of general (i.e., with arbitrary bias) halfspace or ReLU, where all known efficient constant- factor learners critically leverage Gaussianity.
methods and leads to a constant-facto approximation ratio- independen
Acknowledgments and Disclosure of Funding
PW was supported in part by NSF Award DMS-202322 and by the Air Force Office of Scientific Research under award number 1-955002241-000 NZ was supported in part by NSF Medium Award CCF-2107079 and ONR award number N00014-25-1-225 122668. ID was supported in part by NSF Medium Award CCF-2107079, ONR award number N00014-25-1-2265 and an H.I. Romnes Faculty Fellowship. JD supported in part by the Air Force Office of Scientific Research under award number FA9550-244 1-0076. by the U.S. Office of Naval Research under contract number N00014-22-1-233 and by the NSF CAREER Award CCF-2440563. Any opinions, findings and conclusions or recommendation expressed in this material are those of the author(s) and do not necessarily reflect the views of the U.S. Department of Defense.
References
[ATV23] P. Awasthi, A. Tang, and A. Vijayaraghavan. Agnostic learning of general ReLU activation using gradient descent. In The Eleventh International Conference Learning Representations, ICLR, 2023.
[Bog98] V. Bogachev. Gaussian measures. Mathematical surveys and monographs, vol. 62, 1998.
[DGK 20] Diakonikolas, S. Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi. Ap- proximation schemes for ReLU regression. In Conference Learning Theory, COLT, volume 125 of Proceedings of Machine Learning Research, pages 1452-1485. PMLR, 2020.
[DH18] R. Dudeja and D. Hsu. Learning single-index models in Gaussian space. In Conference on Learning Theory, COLT, volume 75 of Proceedings of Machine Learning Research, pages 1887-1930. PMLR, 2018.
10

---

[DIS08] A. S. Dalalyan, A. Juditsky, and V. Spokoiny, A new algorithm for estimating the effective dimension-reductiee reduction subspace. The Journal of Machine Learning Research, 9: 9:1647-1678, 2008
[DKMR22] I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren. Hardness of learning a single neuron with adversarial label noise. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[DKPZ21] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polyno- mial regression for agnostic learning under Gaussian marginals in the SQ model. In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.
[DKR23] Diakonikolas, D. M. Kane, and L.. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginals. In ICML, 2023.
[DKS18] Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1061-1073, 2018.
[DKTZ22a]
Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning a single neuron with adversarial label noise via gradient descent. In Conference Learning Theory (COLT), pages 4313-4361, 2022.
[DKTZ22b] Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaccs with adversarial label noise via online gradient descent. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5118-5141. PMLR, 17-23 Jul 2022.
[DKZ20] Diakonikolas, D. M. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[GGK20] S. Goel, A. Gollakota, and A. R. Klivans. Statistical-query lower bounds via functional gradients. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[GGKS23] A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[GV24] A. Guo and A. Vijayaraghavan. Agnostic learning of arbitrary ReLU activation under Gaussian marginals. arXiv preprint 21t.:2441..14499 2024.
[Hau92] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78-150, 1992.
[HJS01] M. Hristache, A. Juditsky, and V. Spokoiny. Direct estimation of the index coefficient in single-index model. Annals of Statistics, pages 595-623, 2001.
[HMS+04] W. Härdle, M. Müller, S. Sperlich, A. Werwatz, et al. Nonparametric and semiparamet- ric models, volume 1. Springer, 2004.
[HTY25) L. Hu, K. Tian, and C. Yang. Omnipredicting single-index models with multi-index models. 57th Annual ACM Symposium on Theory of Computing, 2025.
[Ich93] H. Ichimura. Semiparametric least squares (SLS) and weighted SLS estimation of single-index models. Journal of econometrics, 58(1 (1(-2)):7--120, 1993.
[KKSKI]] S. M. Kakade, V. Kanade, O. Shamir, and A. Kalai. Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011.
[KS09] A. T. Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT, 2009.

---

[KSS94] M. Kearns, R. Schapire, and L. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2/3):115-141, 1994.
[O'D14] R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[SSTIO] N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010.
[SZB21] M. J. Song. Zadik, and J. Bruna. On the cryptographic hardness of learning single periodic neurons. In Advances in Neural Information Processing Systems, NeurIPS, 2021.
[WZDD23] Wang, N. Zarifis, I. Diakonikolas, and Diakonikolas. Robustly learning a single neuron via sharpness. 40th International Conference on Machine Learning, 2023.
[WZDD24] P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Sample and computationally efficient robust learning of gaussian single-index models. The Thirty-Eighth Annual Conference Neural Information Processing Systems, 2024.
[ZWDD24] N. Zarifis, P. Wang. I. Diakonikolas, and J. Diakonikolas. Robustly learning single-index models via alignment sharpness. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 58197-58243. PMLR, 21-27 Jul 2024.
[ZWDD25] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning monotone generalized linear models via data augmentation. arXiv preprint arXiv:2502.086/1, 2025.
12

---

Appendix
Organization The appendix is organized as follows: in Appendix we present basic properties of the Seeeen--Uhlenbbec-seniig
and discuss the (e-Extended) (B, L)- L--Rlar activation class; in Appendix we provide omitted details and proofs of Section 2.1; Appendix C we provide the the full version of Section 2.2 on the spectral subroutine; in Appendix D we complete the details omitted from Section 2.3 on the proof of the main theorem Theorem 2.3.
A Technical Backgroound
A.1 Ornstein-Uhlenbet Semigroup
The MeistiinUUhlenbekk semigroup is extensively used in our work. Let first give formal definition of the Cemstein-Uhlenbee semigroup and then record the properties that will be used frequently throughout this paper.
Definition A.1 Ceastein-Uhlenbeck Semigroup). Let p (0,1), 9 L2(N). The Orn- stein-Uhlenbeck semigroup, denoted by Tp, is a linear operator that maps 9 L2(N) to the function T 2 defined as:
[o(ox + vI - v1=))z) (x)9)(x)= = 2-N
For simplicity of notation, write T T2)(x) instead of (x)
The following fact summarizes useful properties of the Omstein-Uhlenbeck semigroup. Fact A.2 (see, e.g., [Bog98, O'D14J.. Let f,g E (z(N).
For any f.g Le and any > Ex-N(((T
2. For any Rd > IR, E Lz all of the following statements hold.
(a) For any t, > 0, T,T.g Tesg.
(b) For any p (0, 1). Txg(x) is differentiable every point Rd
(c) For any E (0, 1), Txg(x) is /11 (0tp://(1111)1_111111 10)) i.e., [[VT,
<
|19|| (1 p²)3//, Vx E Rd.
(d) For any p e (0, 1). Tøg(x) C
(e) For any p 2 1, T, is nonexpansive with respect to the norm || Il Lee. [T S ligllz,
( [x)pl())l is non-decreasing w.r.f. p.
(g) If g is, in addition, a differentiable function, then for all p e (0, holds that: VxTpo(x) Vxg()))), for any Rd..
The Ornstein-Uhlenbeck semigroup induces an operator L applying to functions f E L2(N), defined below.
Definition A.3 (Definition 11.24 [O'D14]). The -hhstein-Ullenbeck operator is linear operator that applies to functions f E T2()), defined by T.f dT,f
dp 1-=1, provided that T.f exists.
Fact A.4 ((O'D14)), Let f.g E L2(N), p (0, 1). Then:
1. ((Proposition 11.27])
aT.f 1 LT pf f = T.L.
dp
2. ((Proposition 11.28]) ExON (x) (xx) Ex (Vf(x)VT,
The following fact from [ZWDD25] shows that the error incurred by smoothing is controlled by the smoothing parameter and the L3 norm the gradient:
Fact A.5 (Lemma B.5 in [ZWDD251). Let f E Iz(N) be a continuous and (almost everywhere)
differentiable function. Then (T,f - f(x)) < 3(1 p) fx))
13

---

A.2 Regular Activations
Our main algorithm robustly learns SIMs whose activations are monotone and approximately regular. The definition of regularity and approximate regularity is given below.
Definition A.6 (B, Le-guula Activations, Definition 3.1 of (ZWDD25]). Given parameters
B, L > O, define the class of (B, L)- -Regular activations, denoted by H(B, L), as the class containing all functions a : R + such that 1) ||oll=> I B and 2) || Le S L. Given O, define the class of c-Extended (B, Lig-Ruullar activations, denoted by He L), as the class containing all activations 01 I - R for which there exists 02 E H(B, L) such that ||01 o2ll2 S.
Examples of Monotone Regular Activations The class of Monotone e-extended (B, ---regular activations is a broad family of functions, with illustrative examples provided in the fact below.
Fact A.7 (Examples of e-Extended Regular Functions (Lemmas C.9 and C. in [ZWDD25])). The following function classes are c-Extended Regular:
1. If satisfies (s [ I B, for some Ç > 0 and is monotone, then He De where D (Ba/4e) and C1, 02 are absolute constants.
2. If a b-Lipschitz and recentered so that (0) = 0, then (c(ccllo')(((/b)) b), where c
is absolute constant.
3. If = 01 + C where on E (B, L., [+(2) S A, and
((=)
A1 24) Ao Ao E ERER: 0, (m): < oo
2=1
then HB + A, L max (ETT.
In particular, using Fact A.7, it follows that
1. General ReLUs (z) max + f}. R are regular; namely, a
H. (1)og)
2. General Halfspaces a (2) 1[2 + + 0). E R, are regular; namely, E 1/c1
In the next lemma, we show that, in fact, all monotone functioon L2(N) are e-Extenned (B, L)- Regular. However, the parameters B(e), L(e) depend on f and which might not be a polynomial of 1/c. Therefore, the lemma below does not violate the netrmattio-thhoreed lower bound in [ZWDD25).
Lemma A.8. Let f be monotone activation in L2(N). Then, for any 0. there exists C(e) 0 so that f E (ooy)s/))))))))))po((((()))))
Proof of Lemma A.8. Using the assumption that f E L2(N), we have that Ilfll,, S c < oo for some 0. Therefore, have that
Iflli, = / Pr(f(()) 2
t 2
Note that the function (+] 2 t] is nonnegative function of t. Therefore the sequence an = f"" Pr(f((z) 2 tjdt is non-decreasing for any n E N and by assumption the limit of the sequence an + oo exists. Therefore from the definition of the convergence of the limits, for any E (0, 1) there exists n. E N so that for any n 2 ne, we have
(x) 2 tjdt= = /
00
Pr(f((x) tldt - I Prif(()) tjdt SE'
14

---

Furthermore, note that for f2 = sign(f) min (m ))) we have that
I/ f2l Pr[1/(=) /2(=)] 2 ljdl
Pr[[[(=) /2=)1 2 4,11 2 ll
- Prif(=) 2 tjdt s
By applying Part 1 of Fact 7.7 to fz and choose c' == c/2, we get the result for C(c) (f2(n))) 0
Truncation of Regular Activations For a target activation a E HB, L), we can make simplifying assumptions that come at no loss of generality. The first assumption is that there exists finite parameter M such that outside the interval zero. In this case, we call the interval [-M, -M, , .M] the support of a' and say the support of o' is bounded by M. Another way of viewing this assumption is as saying that is "capped" (or truncated) at (M). It turns out that such truncation ensures all ((PPT) solutions are unaffected. Similarly, the labels can be truncated in the interval [-B, B), and, as result, we can assume w.l.o.g. that lyl S B. formal statement is provided below.
-MMMM, the derivative o' of the target activation o is
Fact A.9 (Lemma C.6, C.7 in [ZWDD25]). Suppose that the target activation E H. L). Ler sygn(y) min B). Then, E(x,)~Dl( - o(w" x)) < OPT + and for any W such that E E(x.))-Dl(g- o ( x} O(OPT) + E. have ((x,y) [yy - ow x)) O(PPT) +
Moreover, there exists ē E H(B,L) L) such that l|ō 1 olii, S c, with support of o' bounded by log log( 4B² If satisfies E(x,)>-D(y
M S /22lo((4B2 then also ((x,)>=D( (1y - ( x}}² S ((PT)) + Thus, one can replace a with ā and y by Us and assume w.l.o.g. that the support of of is bounded by M and lyl S B.
ā(w x)) S (OPT)) +
Error Bound In the next fact, we show that for any function o E He (B, L), we can bound the L3 loss o)) at vector w by sin Tl]Tccoe ao Il2,.. where = 0(w, w").
Fact A.10 (Error Bound, Lemma D.8 Proposition 4.5 in [ZWDD25]). Suppose that ((x.)>>l(a((" x) y) OPT holds for monotone activation
unit vector w² Rdd and suppose the support of d' is bounded by M H. and Given any unit vector w E Rd, let = O(w, w*). Then, if 0 < c/M for an absolute constant a, we have ((xx))D((((W x) y) & COPT + sin" @ cos 22, for a universal constant > 1.
B Omitted Proofs and Details from Section 2.1
Note that the methodology of our initialization algorithm is to find threshold t such that after transforming the labels y to T t) = 1fy 2 f}, we can reduce the regression problem to a robust halfspacc learning problem and find a vector (0) satisfying (ww()) w) < 1/M via the robust halfspace learning algorithm from [DKTZ22b], where M > 0 is the smallest parameter such that Eg~ (a(()) - 2 [1 2 My] < C(OPT + c). The following fact guarantees the existence of target threshold that ensures the desired initialization.
Fact B.1 (Proposition F.19 and Lemma F.21 in [ZWDD25]). Let L x) be optimal hypothesis that satisfies E(x,y)~Dly o( x S 6o for En == OPT+ 0, where a is a non-decreasing
Extended (B, L)-regular function. Suppose the constant hypothesis o(2) = c not constant factor approximate solution for any R. Let C1 0 be sufficiently large absolute constant. Then there exists a minimum M > that satisfies [[(T(z) ( 2 M)12 & Ci6o. such that [r[1 2 (M)) + 1( 2 MJ} < Pr(w" 2 MI/C2, where C2 = C1/5.
Suppose we given the threshold / a (M) with M being the minimum value satisfying Fact B. After transforming the labels to ÿ T(y:)) l Z 1). we can apply the algorithm from [DKTZ22b, ZWDD25] to find vector w" such that O(w" w") ) 1/M.
15

---

= Fact B.2 (Proposition F.19, Fact F:20 in (ZWDD25). (x) 1[ 2 M] be target Gaus-
sian halfspace, i.e., x ~ Dx and x a standard Gaussian distribution. Let (x. 9) ~ 'D be distribu- tion of labeled samples with OPT' adversarial label with the noise rate satisfying OPT' S (1/ (1/C2)eep((MM / R (1/Ca) Pr lh* (x) = 11, where
meaning that Pr [ ş h (x) < OPT,
C2 is large absolute constant. Then, there is an algorithm that uses (dde log 1 /o)) samples and
returns with probability at least 1 å a vector w such that ((w, w-) S min(m (066,, 1/M).
Therefore, what remains is to find such threshold t. Since the target activation is unknown, it is not possible to find M and calculate Pr(z = 2 M] and estimate Pr[1 (y 2 (()) * 1 2 My] Our strategy is to show that can discretize the labels y and the target activation so that they only take small number of values, which then implies that the target threshold / = (M) must be an element of a small set. Then, can brute force iterates through all the possible values (we show there are polynomially many), and run the robust halfspace learning algorithm from Fact B.2 on each of the label transformations T T(y: t.), t = ive. Formally, we have:
Claim B.3. Suppose |ly ow" x) x)122 S eo for some eg > O. Define the truncation operator
trunc(-) by trunc(z) = B + iv if 2 live, + 1)ve), i E [2B/Ve]. Then |ttruncly)
trunc(o (w* - x))] S 9(0 +e).
Proof. Since is (B, L--rull (thus || S B) and since w.l.o.g. [u| S B (Fact A.9), we have [[trunc[y)) - 2l S Veo and l|a(w* x) - trunclo (ow" x S VeD. Direct calculation yields: ||trunc(y) - trunc(o(w" x))]l2, = -|ttunccy)) - y + y o(w" x) + o(w" x) - trunc(o(w' x)) S $2VE+ + Veo-
Thus, we have ||trunc(y) - (runc(o((w) (w" -x))xx S 9(E co).
Now we prove Lemma 2.5, restated below.
Lemma 2.5 (Initialization). Let o xx be hypothesis that satisfies Bix.))-D(l--((( ~x) S
O where is a non-decreasing e-Extended (B, Reegglla functiur Suppose that no constant hypothesis, i.e., function of the form (z) c for any c E R. is a constant-facto approximate solution. Let C > 1 be a large absolute constant and let M >> O be the smallest parameter such that Ez~N (a)))) - (M)) {2 2 M]] S C(OPT c). Then Algorithm 2, using (dd log( ()))) samples, with probability at least 99%, returns a list Sini of O(B/vt) vectors that contains a vector w(O) such that ((w((), w²) < min m1/, (MMM./166 T/16).
P Proof of Lemma 2.5. By Claim B.3, we can discretize the labels and the target activation o so that it only takes a finite number of values: i i/C, i E [[2B/ /cc + 1). while only inducing a small error.
By Fact B.I, there exits threshold t E (ivE,// B/v² so that (=- (0(2) > {}] <
C(OPT + e) and Pr[1 2 t} + 1( x) 2 [J] S Pr(a(w" x) 2 fJ/C,, where C, are large absolute constants. Then by Fact B.2 we know that using the algorithm from [DKTZ22b]
will obtain a vector w such that 6(w, w*) < 1/M where M = o (t). The algorithm requires Odd/e² log(1/8") samples to return such vector with probability 1- - 8'. Since we run the algorithm B/ times, let 8' = vēo/ B. and after a union bound we get that with O(d/e² log(B/(<o)) samples, the algorithm succeeds with probability 1 8 for all the iterations. Setting 5 = 0.01 completes the proof.
C Full Version of Section 2.2
In this section, we present and prove our main structural result (Proposition C. We show that-even though the target activation is unknown- we can identify a vector that has strong correlation with an 'ideal descent direction' v :=
/I]("") L 2- It is not hard to see that v can be used to rotate w towards w'. The vector that we identify is top eigenvector of matrix M,, that can be efficiently estimated using sample access to labeled data. We can only identify such a target vector up to its sign; however,
argue later, this is sufficient for our argument to go through.
To build up this result, we need the following technical pieces: (1) the spectrum of the matrix M. contains information on v i.c. V. -M v is large (Lemma C.3); (2) All the other directions u that
16

---

are orthogonal to v have small quadratic form value compared to Vw. i... u u-M & V Mw and therefore, the direction V. stands out in the spectrum of the matrix Mw (Lemma C.5); (3) finally, we argue that the top eigenvector Vw of Mw correlates strongly with Vw (Lemma C.6).
Algorithm 4 Spectral Optimization
1: Input: Parameter 0o: Initialization vector w (0); Empirical Distribution DN;
2: S f- 0, Φ - 0(1 - 1/ 128)*, T/ sin /8, K t poly(1/e, L) and T t ((log(L((e)))).
3: for = 1..... K do
4: for = O..... T do
Let Letgll w
E (x.))-Bx [yx (w(l) x E E
5:
6: Compute the empirical matrix Mw(t)- t
Ej Bi (B w(t)) PPr E En].
7: Find the top eigenvector of Mw then randomly pick v(t) from {Lu}.
8: ((++1) + projga(((() - 1) (()).
9: Stol <- Sool U (w(++1).
10:
Return: Sool.
Proposition C.1 (Spectral Aligmment). Fix parameters B, L > 0 and 0. Let D be distribution over (x.y) E R. x R with Dx = ( Lt). Let (w" o) E gd-1 x (. L) be a pair of unit vector and monotone activation such that (2(w";o) OPT. If N 2 d poly B, L, 1/e), then with probability at least 99% the following holds: for any unit vector w E IR satisfying sin 8(w, w*) (eeeT////ccoeee returned by Algorithm 4 satisfies u w = and Iu w"| 2 (v2/2) sin 0(w, w").
40/OPT) Feess(www / the top (unit) eigenvector u Rd of the empirical matrix Mw
The rest of this subsection is follows: Appendix C.I develops the machinery required to prove Proposition C.I. We prove Proposition C. in Appendix C.2. In Appendix C.3, we determine the sample complexity for the spectral subroutine.
C.1 Technical Machinery for Proposition C.1
We start with the following fact from [ZWDD25] showing that given the target activation a, the gradient vector of the smoothed L2 loss correlates strongly with w":
Fact C.2 (Proposition 2.2, [ZWDD25]). Fix an activation R + IR. Fix vectors w", w E
gd-1 such that E(x.y)~D((y o oww x]) = OPT and let = O(w", w). If sin 2
3v 3/OPT/ cas oo 1 then:
[yT (yTTosoo' x)x+"1 w' 2 (2/3) 11, sin 8. (x.y)>/D
E
The structural result above relies heavily on the knowledge of the target activation a and is thus not applicable setting. Instead, argue (Lemma C.6) that using the vector (2) defined below, the top eigenvector of the matrix Mw Ex~A(1,II)) [gw (w z)gw(w 2) J], correlates with the "ideal" update direction v (w*) /Il(ww) 112:
E E(x yxx 1( x E Ed}]
gw gw(2) =
Pr(w x &
E, = a1+1) = |-M + (i 1)4, -M + +iA), A= 2/ (Grad)
where
M' = Oly (lVllg(BB/e)) satisfies Pre-i[22] 2 M' S 2/1B213))
I=
=(BBL))))
X E = E Plyx [(w x x & Pr(w x E Ej), so that gw (2) can be written gw(2) = E, (xxx))-D(xx fyx w- E { E E.). We note that for any in interval &,, (z) (xx,)) flyx_ Lw w E Ei), i.e., it is a fixed vector that only depends
Denote E(x,)) Ly w
w.
First, we show that the quadratic form (v:) MMw v with respect to the target vector v is large.
17

---

(2) be the vector defined in (Grad), let Mw = E (aw.N//w(2) (2) (2)] 1. and Suppose e S OPT and sin 4v 4vOPT/|| 80 (z) Then, (vi) MM V 2 (1/16) sin c
Lemma C.3. Let gw
Vw (w*) ////////// /
Proof. Observe that ve sin 0 (w*)
Consider the following quantity:
K(h(w- x))
E (x.y)>
low --wwh(w xx)]
Define the function class H by
H'' = h R hh:R<RING h(2) E (0 =1}
where & =1, 1,.... I, are the same intervals as in the definition of gw (2).), (Grad). Our goal is to find h E Ht that maximizes K (h(ww x)). Observe that for h E H', K(h(w x)) can be written as
K(h(w- x)) =
E
yw" w Σ hellw (eelwwxxe x E.
(x,))~D
h4 sin 0
E (x.W)DD
(vw x)
h4 sin 0
Ve
E
lyx |..xEE)
Pr(w &l]
(xx1)
hy sin 0
1yx !w
w.w.E Eil Pr(zeE &l
(3)
(x.y)~
(126)
h,1fz (M.1ZEEEtt (vo.
E wuxt / )
sin
2
(x.))D
[v=) Bm(()) = sin / 1(22), v (B(())))))) Lo(N((0,1))
sin
0 E 2
where (i) is by w __ = (w*)-w x-w = v x (ii) is by the definition of (xx,)))D byyx yyx w e Eg). (ii) is by Priz E = [1f2 E E = EI~N[(1(2 E E and appropriate grouping of terms, and the remaining inequalities product and that w ~ NN0 1). Because K (h((wxx) is an inner product in the space of L2(N) func- tions, from the Le norm (self-)duality this is maximized for l(2)) (gw(3) v ///ll [w) v La-
the definition of the inner
Now we study ) TM Using the result that K (h(ww x)) is maximized at h (2) = V gw (2)//(lz gww (2)ll) from the discussion above, and recalling that PIx-Dx [w x E,] Pra-N(2 E E₁] (since x follows the standard Gaussian distribution), we have that
= E zm
(gw
(2)
E [u(v x) (.xEE))(=EE))) )
E
2
(x (x,I)~~D
( x) (ixxe))
2
E
E (
(x,g)<
20N
Vw
E
[xx lw
(w-XEE)) [
Pr(ze
(x.y)D
=l
v
gw (2)lle (hh"(w x)).
(5)
sin 0
18

---

where in the last equality we used (3) and that h = v E Exx.)) w wwwx E 8.1/Iv gw Bw(2))lza by the definition of h" (z). Let us define
T Teosoo' (z) - oa:)
(6)
Recall that we have defined as the left endpoint of the interval & = (aa, ai+1) in (Grad), We show that Toos pwww x) is close
no' wo'(w x) pointwise.
Claim C.4. Suppose sin Toce eo' llz Z VOPT and e S OPT. Consider the piecewise constant function eo' defined in Equation (6), with the intervals & i E [1], and parameter M' following the construction in (Grad). Then,
[T coos00' go' (z) Teos
MT) <cBB;
- || f cos Se.
Proof of Claim C.4. By Fact A.2 part (c), we know that for any p E (0,1), Il ((Ta(()))ll I ///lli...// p². In addition, by Fact A.2 part (a) we have Tens 00 (()=((())==)))))) = T Veos ( Voose (z)) Therefore we claim that T (0))) is a Lipschitz function:
IT Voos Veos (=)1l r. (6) Voos
V 0 (z))
[I cos oo (z)) = II(T Vooa 0 Voos (z))))
E
v1 cos
v2 cos 9 sin (8/2)
(8)
B
22 cos 0 sin (00))/00/II1-111 8
s 2sin2(0/22) (1//2\/oo$@)
where in (t) we applied Fact A.2 part (g) and the fact that cos 0 2 s (0/2) and in (ii) we used the fact that ||o < B since is e-Extended (B, reeegul... Furthermore, note that by assumption that sin 0 VOPT/ [ eo'll2. have sin 2 > Toos eo'll Using the fact that /| is an non-decreasing function with respect to p (Fact A.2, (D), we have [TT o0' IIZ, $ 1100112 I L2, again by the assumption that o e-Extended (B, Leeggular. Hence sin" 0 2 OPT/L2, Finally, our initialization subroutine guarantees that cos 0 2 c for some small absolute constant >> O. Therefore, in summary, obtain that [| ([Tcosso' 6=)) l._. x BL2/OPT.
Now for any E [T). let z E [a,; d+-1) ) be any value in the interval E,. Since we have proved in the last paragraph that Teos so (z) is O(BL² Lipshii,,,,,,, we have that there exists sufficiently large absolute constant C" such that
[Toos so' (2) T To (a:) S C" BLL///PPT= ail S (C" (CPBL//PT))//(CCB))) S Se/B.
Note that in the last inequality we used (by the definition of & [a,, ai+1) in (Grad)) that di+1 -a; S 2 2/(CB² 1.2). where C 2 C' is sufficiently large absolute constant. Therefore, we conclude that (Toos 60' (z) - Toos ga' (=) [ E [-M', MJ S B, proving the first part of the claim.
For the second part of the claim, note first that
||T cus g0 (2) Teus o (z)ll<a S [I(T Cos 00 (2) T coss 00 (z)) E [-M' M')
+ I| 0 (z)11(z12 M'Hle
Using the first part of the claim, we obtain [[(T'coso'll - Toos (=)) M'M', S. Now applying Fact A.2(c) again we have [T 00 1 S B/(cos sin 0). We have argued in the previous paragraph that sin 2 VOPT/T. /, 2 L and cos 0 2 e for some small absolute constant e under our assumptions. Therefore, ooToos e S BL/VE. Since M' = =(vTogi (L/e)) is chosen such that Pr[[z| 2 M'] < /C((C for a large absolute constant C, where = is a standard Gaussian random variable, have
E [[T (z)) 2 MY S 1B Pr[[2| M Sc.
Therefore, it holds T| ( (z)]lz, To (z)]l < 2e.
19

---

Now observe that since T (2)/ E H', we have that
K(h" (w (w.x)) K (Tocosoo (w (l)))))
which implies (from Equation (4))
V (w(2)]l22
Vw
Mw Viw
K (Tcos
eo' (w x)/ [ cos c
sin 0
ll Bw 00'0 Lg sin 1
ly(w" x " I cas 00 00' xx (x & (7)
(x.D)
Note that by the definition of Mw. we have (vw) Mw w - Ez-Nl(vi gw 8w(2)) = [w(
v 112. Furthermore, as we have shown in Claim C.4, it holds [lT S 11'T 1l,, + E; and note that we have 3/ s 3/OPT < I|Tece (since have assumed 1 sin 2 Thus, for small e holds vē S "lTTooseo'lla and we obtain ||Toos S
/ (o eo'll 2||T ooo''ooseo 1l Using that [lg(z) , Wwll (v Mw and | I 2/ e 2 into Equation (7) yields
(v MV
[y(w"" x - po') &d]l (x
E
sin 0|l 20'(00))(())) (=)
E luww" x lx'")( (T eo (w x))[[[w X &
2 sin 01 90' (z)(
(x
(Q1)
E (x.))=D
(u(vw x) no (a((a))
Tens (w [w) &i).
T cos 00 100 (2)lleg
(Q2)
(8)
For the term (Q1), we apply Fact C.2 and obtain
(Q1) = E [ w x W Teoe a (w x) {/w x/ S MM))
(x
2 (2/3) sin T Toos oo' li.
E
[u( (w" x W no'(w x)1 x| > M']]
(x,1)
2 (2/3) sin 0 cos o
12.
B
E llv x|]
E x~D
[| OT oo (w x)| [|w x 2 My],
x~
where in the second inequality we used inequality further yields
lul < B and
v/ sin = (W*) Using the Sauchy-Schwarz
x, || sin oo ao'oao'wwwwo x)/xx)/l/Wwww x 2 M'H S sin
E (TTos Pr[[w x 2 M']
xnDD
I sin 0
Teos o0 (clll,,
where used the fact that M' satisfies Pr[[e] 2 M' e/CBL) for some large absolute constant C; the definition of M' in (Grad). When sin 0|| cos oa' l|,, 2 3/OPT > 3/e, since C' a large absolute constant and T. a constant larger than 1, we have c/(CBL) S (1/24B) sin 0l|Toos cos e Therefore, it holds
(Q1) 2 (2/3) sin T cos 90' 112 B E llvi. x1](1/2AB) sin 60'1 x
2 (7/12) sin 2 T 00 112..
20

---

For the term (Q2), using Claim C.4 again we have
1(Q2)) -
E (x.y)DD
x
Teus (o'o0o)a))) (a:)
Teos Coosoo (wxx) x E &HHl
B E
x|
E
| oo' (a;) T Teas (w (w x 6 &
X-DDx
Xx
==1
Pr
Since S OPT S (1/12) sin² 01 ens 80 I12., we obtain that ((Q2) (1/12) sin T| cas o0' 12..
Plugging (Q1), (Q2) back into Equation (8) yields:
1
1 sin 0| 00 1|ng-
(V Mw v 1/2 Z sin 0| cos N0 pa'11 24
sin 2 01
1012 2 4 oo
24
Thus, we have ww Mw v (1/16) sin 01 0o' Il?
The next lemma shows that any unit vector that is orthogonal to v has a small quadratic form. Lemma C.5. Let u be any unit vector that is orthogonal to v. Then u Mwu S 2OPT.
Proof. First, if u = w, then since gw (2) w = 0, we have w M = 0 < OPT. Now consider L Since w, ve and since w cos Ow + sin Oyw have that u x is independent of w" x. Direct calculation gives (noting again that PrxwD, /W x Eg] Pr E εg] since Dx
the standard Gaussian):
u J Mw u
[u E x=
gw (=)))
E lu(u- x) (xxe)))
E sMN
(x,g)
y(u y(u-xx) (w)(Wwwww))) (ww.xxxE)) (w Pr/p: (Pr &
E (x/9)>
E (x.I)D
1y o(w" xx)(u x]l(W. x XEEH]
Pr(z E Ei]
E [o(w" x) x) xx []][w-xE]]]]]
+
xx
E (v o(w" x))( x ())(..x)(())) xx 2
Pr[z E E,]
(x.))>
1=1 where in the last inequality we used that u is orthogonal to w, w". Furthermore, holds:
2
[VV - o(w" x)) x) (x.0))D
E [ly o(w" x)) x x E xnD,
E
[uu x) x E &H]
(x.))>D
(
2
E
(Iv oow" ( x & E Ei),
(x,y)>
where in (i) we applied Cauchy-Schwae Schwarz and in (ii) we used the independence between u x and w since w. Therefore,
u Mw u S
Σ
(1 oww- x)) x XE 1=1 (x.1)
< 2 E
[lo(w" x) ( l M 20PT.
(x.1)>
21

---

Then we can show that the top eigenvector Vw of Mw correlates strongly with the target direction Vw
Lemma C.6. Let Vw be the top eigenvector of Mw. Suppose sin 0 /0/OPT///ooss I2 Then Vw
V. 2 33/2.
Proof. Since Vw is the top eigenvector of Mw. by Lemma C.3, it holds V Mw Vw 2 (vw) "M (vw)
2 (4/9) sin Tos l| > 0. Since Mw = 0, must hold Vw w O, otherwise we would be able to find another eigenvector that has larger eigenvalue. Suppose that Vw = av + bu, where u W, w and a² + 1. Then, we obtain
d²(vw) MM v + u T Mw + 2abu Mw = Mw 2 (vi) "M By Lemma C.5 we have Mw u OPT. Furthermore, note that by Cauchy-Schiie Schwwrz
u MM = E lu gw (2)) Bw(2))] & zmnV
E 2~N E~N-
I(u Bw(2)) E 20
[. gw (z))
=Vu'Mwu Mw I VOPT (vw) Mw
Since a² + = we get
(1-a²)vi Mw = b2v Mw 2ab VW MM V
which implies that
M OPT
Vw V'v =a VOPT V Mw
w
Recall that (vw) Mw V 2 (1/16) sin 0 oo li..- Since we have assumed
sin 0 0 cos p 11 40v OPT, it holds (v:) Mw 2 1000PT. Thus, obtain
V cos((0 (Vw vw)) sin (0ww.w )))) 2 ssin(O(V vw)),
hence tan(0(vw, ))) S 1/3 and therefore Vw V v3/2.
C.2 Proof of Proposition C.1
Let (2) be the vector defined in (Grad) and Mw /Bw (B:
In Lemma C.6
we proved that for any vector w, whenever sin(0 w²)) 2 40vOPT| Teos olw o'Ilz one of the top eigenvector
of Mw correlates with v Vw v 2 v3/2. i.e., O(v w: Vw) I π /6. Next, in Lemma C.9, we proved that using N = (d2 B12 / /c10 Log(dBL/(BBe)
samples, for any vector w, the empirical matrix Mw satisfies || Mw wwll2 I Therefore, using Wedin's Theorem (Fact C.7), know that for any vector w. the top eigenvector V. of Mw satisfies sin sin(Ow Vw)) S <p(ppi - P2 e). Since in Lemma C.8 we showed that when sin(O (w, w²)) > /PTTl// w-)oww || it holds 1/59, indicating B(V vw) Σ B(Vw: vw) + 0(Vw: vw) I 1/59 + T/6 S T T/4. Therefore, let be such eigenvector Vw of Mw that correlates positively with v Note that by definition of Mw. it must hold u 1 w. Thus we have w (cos(6(w, w, w")) + sin sin(B(w, w")) sin (0(w, w"))u V 2 (V2/2) sin(O(w, w*)). Letting 0.01 finishes the proof.
P2 2 60OPT 2 60c, we then have that 0(vw. Vw) S
C.3 Determining the Sample Complexity
Since we only have access to the empirical estimate Mw. we will use the following Wedin's theorem to bound the error between the empirical top eigenvector V. and the population top eigenvector ww: Fact C.7 (Wedin's 's theorem). Let 0(vw, vw) be the angle between the top eigenvectors Vw Rd and & E Rdd of Mw and My, respectively. Let pr and pz be the first eigenvalues of Mw. Then, holds that:
|M Mw
sin(0(Vw, vw)) 5
P2
M
Mw
22

---

Next, we bound the eigengap between the top eigenvalue and the rest.
Lemma C.8. Suppose sin 0 T 00' |L, 2 OPT. Let p be any eigenvector of Mw orthogonal to Vw. Then, V Vw P Mwp 2 (1/24) sin 01l e 2 60OPT.
Proof. In Lemma C.6, we showed that Vw av + bu with u w- 2 v3/2, a² + + Assume that == V + +b where u' is a vector orthogonal to both V. and u and a + 1 Since p Vw 0, we have 0a, 6bj
which implies that a²aq 6b62 I (1 (1-
Rearranging the terms, it yields of I 1 - a² < 1/4, and therefore we have 0i S 1/2. Denote bru + u' v', and we have p = a1 v + v' and | I 1. Since v' T v.. by Lemma C.5 we have (v') "M < 2OPT]| S 2OPT. Then the eigenvalue of p is bounded above by
D'M = V.v. V + aiv Mw + +v' MWw
S (1/4)v Mw + (1/2) 20PT(v Mw + 20PT,
where in the last inequality we applied 40/OP, then Lemma C.3 implies that V MM V 2 (1/16) sin? ol 112, 1000PT, therefore we obtain p MM S (1/3)v MM v. Thus, the eigengap between Vw Mw Vw and MwP can be bounded above by
Schwarz. Since we have assumed sin 0|| cos 00 0''1L,, 2
v M. P 2'MMP 2 (2/3)v Mw (1/24) sin" Teoss 00 I1,, (200/3)OPT.
By Lemma C.8 we immediately get that p1 - P2 2 csin 8 cos 112, therefore, to guarantee that sin sin(O(v (V Vw)) < 1, if suffices to ensure that ||Mw Mw ll2 S c S OPT 2 sin 0J| o0' oo'l...
Lemma C.9 (Sample Complexity). Draw N = O( 18 samples from D. Let
log(dBL((6e)) (ogg
independent
N
w "I(w x EE
gw Bw 1 Pr(z E E,
gw 1( ' Pr(z E Eg]]
Mw = Pr(z
E IMN
Eg]
j=1
Then, with probability at least 8, for any |w|l2 = 1, we have M Mwll25c.
Proof. Since gw (=()) is piecewise constant function on the intervals E₁ = (uj,aj+1) where aj- -M' + +. and A = 2² ((L as defined in (Grad), it suffices to approximate the (vector) value of (2) on each interval. First, for any j E [7]. we observe that r, == _ wwww- x E E } is a sub-Gause Sab-Gaussian random variable with parameter B. To see this, it suffices show that for any unit vector u it holds ||u - ryylı,, I B.PP for any p 2 1. Since w ry = O, we only need to consider u that is orthogonal to w. Direct calculation yields:
g(x u) x x x |]
Iu r,11 = E (x,y)>
(x.g)>D
< B x-D
[lu x x Priz E & s (c/p)))
Thus, ||u rylle, & ByD for any unit vector u and hence r, is B-sub-Gaussian.
Now sample N independent samples from D, ((x(1),
| creating N independent vectors = (0) (x (1) Tw {w (0) E &
Then we know that (1/N) Ee (r))) E (r,]) is sub-Gaussian random vector with param-
eter B/ Then, using standard sub- Gabb-Ga vector concentration inequality, we obtain
1 N
N
cs2
Pr
E
1r,)
2 s
S exp
(x.9)~
2
B2d
23

---

We let = c/(CB\(e/BL). Observe that Pr(z E Eg] 2 (as+1 - az) exp( exp((=a3+112 = A Aexp(-a)+112) where A e² e/LL)) Since las+1l M' for all E - 11, we have exp(-o)+112) Z exp(-(MM')22) 2 Prile 2 M'] 2/(B)) Thus, we have Priz Ejl 2 (e/BL)4 and hence & & (e/(CB)) Pr(z E & for all j E [4]. Therefore choosing
N = - /eal/////ll log(1/))), we have that with probability at least 6.
1
Prr( E Ej] CB
1r (X.))~D
E
S
N
where C' is large absolute constant. However, since there are T= (((BL/(()) pieces of intervals &j (by the definition of (Grad)), to guarantee that (1/N) Σ ry is close to E(x,))= [ry] on every interval, setting +- 8e2 (BL)2 and applying a union bound, we obtain that using N
L(dB L/ (&e))) samples, with probability at least 1 - 8 it holds [I11/N) Ei=1 Fj
E E(x.))>D/r,lll S c/(CB) Pr[= E,] for every j E [T]. Thus, letting
N
1 (x W {w x00 EE - N
we have that with probability at least 1 5, it holds e Pr(z E E,I/ for any j E [1].
[|@ Dyxx
lyxx W E EjHll12 s
Now define
2 gw ( Priz E,]
200 gw E
)
Mw Σ
gw (gw
E NaN
Pr(z E Eg]
Pr(z
Oberve that since gw I we have w Mw W 0. Similarly we have Mww 0. Now consider any unit vector u that is orthogonal to w. Then, by the definition of gw gw(2) and that
Mw Ezww(gw(=)e) (=)gw( (z) T) we have
MMw - Mw u
n M u1 un
E 2
Bw
Bw (z)gw(z))
(u g
(u E(x,)
Dlyx lyx
[( . E EE,))²
Pr(s Eg]
Pr
u. (@W)
E (xy))D
1yx
w 1(W x E EjHl) u. (eW
+
E (x.y)D
lyx
L "1fw x E EjHD
Pr lz E Eg]
j=1
gw
E
[yx
- w W x EgHl
gw
E
lyx
L WwwWw x XE EgHl
Pr[z E Eg]
(x.)
(x.V>D
j=1
2
Note that we have therefore,
& S Pr[2 E E,I((CB), for any j E [1]
M Mw)u
ePr2a E &
(ePl2 Eg]
| (w x E EE,3]
+2
E (x.1)DD
Pr|2 E Eg1
CB
CB
1=1
>> CB
(ePr E Eg] CB
+2
E
[yx 1f (/W-XEEEN)
(x.1)/D
Observe that E(x,)) (os.)w/llyxxw
Elll S Brr E Eg] since
|| [yxx L "1(W x E E = sup
|||=== (x.j) [y(u x [
(x.))D
S sup
| (u X &,11 BPr/2 E &,}, | (x,a)>D
E
(9)
24

---

where we used the assumption that |v| I B and the facts that u x-x !w and w x are independent and that Ex [u. x-*]| & 2. Thus, in summary, we have
u (Mw Mw)u
BB)
E&J S
CB
This implies that MM - Mwlla S.
Finally, we show that ((e")) -net of w's covers all the functions gw (z) and consequently covers all the matrices Mw.
Claim C.10. Given unit vector w, let w' be a vector such that || 1 and ||w' w|12 S 2/(CB4L2 /lg BL/() for some large absolute constant C. Then, for all E R, holds that (z) gw (z)lla S (CB).
Proof. For any unit vector w' such that |/w' S é. (//(CBAT (oggB//O)) S ( @//(C/TTM and any unit vector u. we have
- = Σ (kx))ol(((u-xxM)11 x Ej} (u (u-x-w1( 1( x E E,1) {
u (Bw(2))BB((33 (x)
Pr(2 E EEg]
1=1
Let w' = + q such that ||ll2 S <²/ ((oCC=LL//og(BBEE)) Then, ||u- -u-'l ll(w.
u)w u)w'll S St St/(CBL) Furthermore, note that
E xe x~
(w/ x [a,)
= E x2 x~D,
x a,} (1/w x a3+13 - 1(w', x
1/////x///. az+1111
S E [w x~Dx
xl 0z) 1 ((w x ولارل
E
[| (w- x aj+11 1(w' x x
xーDx
is well-known that Pr[l 1 + 11 fwww
x 2 f)} S f(w, w exp(-(2) (2 (see Fact C.11
from [DKT722b)). Therefore, since (., w/) I |w w/ S M/(C for small have
E [[([-xe x E,} - 1(w' x E BLL (exp( (aa+11 - 2)2/2) + exxp( (a((-()+//2)
xnDx
2 exp(-a2+1
6 Pr[z E Eg).
S B² aj+1
S
B
Thus, suppose E Ej, we have
Iu (gw(2) (2) gw (2))] =
1
E
- -ww)) "WW'-xl(W x E1ll
Pr[z
(x.g)
1
+ Pr(z
E
lyu Iw x(I(f-xXE8) - 1(w E E,3I
(x.1))
n-w -
Pr[z E Eg]
x
E
B
||u Iw u wwll2 ||ll//u
x
Pr(z E - l|2
B
E
[lu- x|]
E [[[ Eg} [[[w' x -1w E
Pr(z E Eg]
xxDx
xxDx
</B
Thus, this implies [[gw - gw (z)ll2 S B/B.
Note that when [gw(2) Sw (2)]l 1| 2 c/B, we have (recall that in Equation (9) we showed
E (xxx "1(w- E E Pr|z Ed1l12 < B hence by the definition of gw (2)2) we have
25

---

(B S B):
Vust | = 1:
Iu T gw (z)gw (z) "u]]uu- u u gw Bw(2)gw (2) (=
I (gw (z) - gw (gw (2) + gw(()))
(Bw((z) [w()))lll|sw((
Bw (=)2)]l2
x CB (2 (2)112 c/B) s
indicating that
|M Mw sup E Iu (Bw (2)gw(2x)) - gw (=)g)ww(() ()) Se. | z~N
Thus, constructing Ō(c²) / [B3) cover S on the unit sphere and requiring [I(1/n) Σ M Mw ||2 I e on all w' E s suffices. Since O (B) S on the unit sphere contain [S| (O(e) ((+))() vectors, applying union bound we obtain that using N Odd B /ea" log(dBL/
samples, we guarantee that with probability at least 1 - 6, for any unit vector w, it holds |M Mwl125c
D Proof of Main Theorem (Theorem 2.3)
We state and prove a more detailed version of the main theorem (Theorem 2.3) below:
Theorem D.1 (Main Result). Let > O. Fix parameters B, > Let be distribution over (0, La). Suppose there is unit vector w Rd and monotone
(x. E R I with activation a E H.(B, L) such that E(xp)~D((a(w> x) - y) I OPT. Then Algorithm runs for at most poly(B, B, L. 1/c) iterations. draws Odd 112 /c log(dBL/e)) samples, and returns a vector w and Lipschitz and monotone activation R R, such that with probability at least 99%, it holds that (xx.))>D((u(W x) - y) -) < O(OPT) +
Proof of Theorem D.I. We first show that if we appropriately choose the step size and the number of iterations in Algorithm 4, then for any initialization w-()), Algorithm with high probability returns vector with 0- 0(w, w*) so that sin 0 < O(VOPT)/IIT cos go'lla, and 0 = ((w(()) w").
Proposition D.2. Let > O. Fix parameters B, L 0 and 8 E (0, Let D be distribution over (x,y) E IRd x I with x ~ (N(O, Suppose there is unit vector w E Rd and an activation a E (B, I.) such that E(x,))=D (a(w" x) y) S OPT. Then Algorithm 4, given initialization vector (O) so that ((w()), ww) < and T 2 (loo(L/ee)) with probability at least 1 - returns a list of vectors Stal with size | = poly(1/e, (1g() such that: there exists w E 5ool so that: i < 0 and sin 0 O(VOPT)/IT go" II,, where θ = B(W w").
Proof of Proposition D.2. In the proof, we denote the angle between (t) and w by O, 0 ((w(1), w"). Furthermore, the algorithm uses the following parameters: Ø; = 8(1 2 2/32)' and nhe csin d where 1/4 22/2. Note that if COPT, then with é' = c/ (2C') and assume that we have more noise of order OPT' = 2c'. In this case, the final error bound will be COPT' < c/2 OPT + So, without loss of generality, we can assume that e < ОPT. According to Proposition C.1 as long as sin 0, 2 JO/OPT//|TTC 0f with proba- bility at least 1/2, the vector (t) returned Line (7) of Algorithm 4 satisties ((t)) ww" <-csin 0, and (t) (() O. We denote P, the event that (!) negatively correlates with w*. We consider the following event
the algorithm
CVOPT
R₂ = sin O2 > T 6 o'
where C' > 0 is an absolute constant.
First, we show that conditioning the events R., Pt, for all ( E T, it holds that de 2 O.. Claim D.3. Suppose the events R,, Pe, E [Ti), all hold for some T₁ 2 Then for all E [Ti),
holds that or 2 0r.
26

---

Proof of Claim D.3. We use induction for this proof. By assumption, we have that du 2 80. Next, we assume that or 2 0₁. We need to show that Φt+1 2 O--1. We study the distance between w(() and w after one iteration from t to + 1. Since v(t) is orthogonal to w("), it must be ||w(() ne 2| 2 1, therefore, ((++1) = proja ( (w 1/8 vl)). By the non-expansiveness of the projection operator, we have
||w([-1)
wo1 112 = prroj (w(1) - 7/2 /)((() w0 - ||w( 1/. -1/v(()) w011
-n/v()--'13
(1) -(w(1) -w" ||w(() w l1 u + 2n v w".
l/w(1) w 1/2 (0 2m
(10)
Note that |lw(()
cos f,) and using the identity about the w |/w((-11) w01 2(cos 0
sum of cosines, we have
ssin 0.+1 - O2
ac+1 + 0z S n 21t w'.
sin
2
2
First, consider the case where 20, 2 de 2 0,. From Proposition C.I, we have that v(() -w" < -esin 0g where с > is an absolute constant. Hence, since we chose T/t = esin Φz/4, 4 it holds v S -c² sin the sin 0./4. Therefore, in this case, 0c+1 S 0g hence (in(((++1(( S sin f,, and we have that
01 0
16
2 o² sin Φt.
2
Using the inequality x/4 S sin S x for 72,) we get that
Oc+1 S 0,(1 - 2² /32).
and using that Φi+1 = Φc - 2 /32), we have that 0c+1 1e+1.
Consider the remaining case where d; 2 20, In this case, if fc+1 S 6i, then pc+1 S 61+1 so we need to consider the case where Oc+1 2 0.. We need to bound the maximum increase of ot+1 Applying the triangle inequality and the non- non-expansiveness of the projection operator, it holds
2 sin( /2) = ||w (1+1) w* ||2 I|proja (w (1) - 7/ (1 (w ())) wIll2 S [|w(() (t) n mv w")
S [w(() - w w + |v
(*) ||2 = 2 (0n + csin csin
From the assumption, we have 02 s 02 therefore, choosing 1/4 and since sin(x) x for & E (0, 1/2), we have that
sin(0(+1/2) S sin + csii /: < 96:/32.
Therefore, since (5/8)x < sin x when (0,m/2) we have sin(Or4 1/ 2 (5/16)0,+1 and thus, O.+1 S (9/10)ør < (1- c2 2² 0 I 2z+1. This completes the proof.
Next, we condition on the event that all P. are satisfied for E [T]. According Claim D.3, as long as R, is satisfied, we have 6; 2 6.. Assume R2 is satisfied for all t E [2]. If T > C" log(L/e) for sufficiently large constant C², then ΦT S VELL. This would imply OT S Ve/L. If RT was satisfied, sin 0r 2 CVOPT/ TT By of d'll I.2. So 0T 2 sin 2 CVOPT/L (since |TTaee IL < Ia < L, by Fact Af)( Then ve/L 2 CVOPT/L, which means ve 2 CVOPT. If c < OPT, this is a contradiction for C > 1. This means that our assumption that R, are satisfied for all t [T] must be false. Therefore, there must exist some T₁ E [T] (we take Ti to be the smallest one) such that RT, is not satisfied. For all < Tı, Rr was satisfied (otherwise Ti would be smaller), and thus di O, for 1 Ti. At t = Ti, Rr, is false, meaning sin OT, < C/OPT/|[T... ozz a' o'lln and we also have Or, S Φπ. S 0. This gives us the desired vector W = (T)) such that 0 < CVOPT/IILL /Il 00'1...
To conclude, we need to bound the probability that all P. (correct direction choices) are satisfied.
The events Pe are independent, and each occurs with probability at least 1/2. The probability of T
such events occurring is at least (1/2)T3, Since Ti S T = Ollog L/e)), this probability bounded
below by 8'= (1/2)² poly(e, 1/L.. If we rerun the algorithm K = ((1
(1)))) times (
Line 3 of Algorithm 4), by standard Chernoff bounds, with probability at least 5, there will be at
least one where all P. are satisfied for t E [Ti]. This completes the proof of Proposition D.2. D
27

---

In Lemma 2.5, we showed that the initialization algorithm (Algorithm 2) uses Ood B)/e²) samples and returns a list of vectors Simi | < B/ve that contains a vector w(() such that ((w(O), w") < 1/M and M is the threshold we can truncate such that (x~w((o(2) (M)) 1 2 MH S C(OPT + e), i.e., we can truncate o at M and the overall error increased by C(OPT + c). By Fact A.10 (with the absolute constant = 2 in Fact A.10), this initialized vector (()) ensures that for any unit vector w(() such that 0, == 0(w(1), w') - 20( ([ww() w"), ) it holds
E (x.9) (w x) y) - COPT sin? 0g [| o 0'112.2
(11)
Therefore, any unit vector w(!) such that 0, - 28 (0), w*) and sin² a constant factor approximate solution (i.c., it holds ((xx))=(((((((()) x) y) S COPT + e). Since are iterating through this list Simi it is guaranteed we will encounter the correct w( If (0) is an approximate solution, it will be tested and output by our testing subroutine (Algorithm 5). Now assume in the following that w(O) is not target solution.
0. o'Ili, I COPT is
It remains to show that we can choose the correct stepsize in Algorithm 4. If choose 0 from the list θ {t/L....,kee kc/L} for k (/e2)//e, it is guaranteed that for the correct w-(0) in the initialization list, there exists an initial stepsize 0 θ so that ((w!"), w*) ) E (0 L/L, 0) (see (5) of Algorithm 1). Our claim is that we are guaranteed to have 0 S 20 (w() w*). That means according to Proposition D.2, setting = 0.01, with probability at least 99% we have that there exist w in the list S returned by Algorithm 4, that satisfies that = 0(w, w ) S 0 S (0(w(0) (0), w") and sin 0 I O(VOPT)/II
o0''lol indicating that E(x.g)->l((t) (a x) y) S COPT + by (11). Now we prove the claim that 0 < 20(w(0) w*). To show this, suffices to prove that ((w(0), w*) 2 E/L because we choose θ ke/ L for k [(T/2)L/c].
Claim D.4. Suppose o(w(O))x) not a constant factor approximate solution. Then, it must hold that 0l (0), w") 2 e/L.
Proof. Assuming that 0, S c/ I, we have
E (x.))
[(a(w( xx) -1 s 2 E
[(a .x)
x) - o(w" x)) (x.y)>
E [aa(w" x) y)
x-Dx
<
E (o()
E (a 00z1 + sin 0 (012) 2OPT.
=1.22"00"
By the definition of O Uhlenbeck seweeenbee--semii--e seek--ssmiiioorree and using the tower rule of expectation, we have that -2,, (orrwao(o(ccsss (cr(cos 21 + sin (022) the error can be bounded from above by
(o)())))))))) = E (co)) o,
0 (21)), which yields that
(w (0) x) vIli, S
E o
OPT.
Z~N
Note that by the fundamental formula of calculus, the term in the parenthesis above can be written as
[. a (2)) -
E [o E N~N 2 of (2)o
E (z)o(((( 2
Teos 0, 02))]
E
zmn
cos fo
E (()))
dp T (2)
cos Og 2>A
where in the last equation, we used Fubini's theorem. Now applying Fact A.4, we have dT (TTa(z)) dp = (1T (()) (Fact A.4 part 1), and using Fact A.4 part 2 we further obtain
E [o x~~
dp)] = (1/p) 2~N (o())) (x))== (1/p) E (o'
Bringing in Fact A.2 part (g), it finally yields
( = [
E (o < l
E [o())] E zn znN
(o
cas 0g znd a
< cos 0o) 00)L² 2= 2 sin (0on L2
Therefore, if sin 0u S L,L, we have (la(w(0) x) yll?, < OPT + c, contradicting the assumption that (0) is not constant-factor approximate solution.
28

---

Next, we show that given all the constructed candidate solutions, Algorithm 5 with high probability returns an activation and direction pair that achieves O(OPT) e error. The proof of Lemma D.5 can be found in Appendix D.1.
Lemma D.5 (Learning the Predictor and Testing). Algorithm 5 given n n and a set Sool of poly(B: B, L, 1/c) vectors, with probability at least 99% returns a solution puir (uw, W), with uw being Lipschitz and monotone, and w Srool such that
= poly [B L, L/c) samples
E (x.y)>D
(Tw (w .x) 1-y) S wES (x.y)~
min E
[oo x) - te.
for some universal constant
Algorithm 5 Testing
I: Input: Parameters B, L, e; Data access (x, v) ~ D; gool, empty set S
2: Draw samples {(x(1, (xx(0,y()) )0 and construct the empirical distribution D,.-
3: for w Sual do
4: Find Uw = arrgmin E (x.)) [[u(w x) 10-1)- 8)
5: S 5 SU [(w,, w)}
6: Return: (Uw, W) = argmin (ww: w) S E (x,)) (lsx)>>,,[lu((( x) - -))
Finally, using Lemma D.5, we know that drawing at most n O(log(BL/cc)
new samples,
with probability at least 99%, the testing algorithm (Algorithm 5) returns a solution pair (u w) where Uw E H(B, L) and w E gool such that ((Tx x) - y) < COPT+e This completes the proof of Theorem D.1.
D.1 Proof of the Testing Lemma (Lemma D.5)
Algorithm generates a list of possible parameters Sool = {w((0)
(m M=1 where m = poly(1/e, L).
and we know that there exists vector w E Sool such that sin 0 S /OPT/I/Tcstte oo where 0 = ((w, w*). ). To complete the task of learning SIMs, we need to: (I) find an activation E H(B, L)
that is close to the target activation σ; (2) find the target vector w E S50l
First, we note that given any vector w and n samples ((x(), )0) there exists an efficient algorithm that computes a best fitting monotone and B-Lipschitz function on the sample set {(x(() (0)) via solving the following constrained optimization problem:
c - 202 ((()
min
(Iso)
s.l. 0 S 0++1 S 3(w ( (i+1) w. x()())..
We remark that (s)ss are sorted so that w (0)ss are increasing order.
We use the following fact:
Fact D.6 (Proposition [HTY25]), Given a sample set ((x(1), y1)) there exists an algorithm that exactly solves (Iso) in On log" (n)) time.
Observe that given the solution { of (Iso), we can construct a function T (2) by linearly interpolating the points {(2, } where 2; w- x,. Then, the function Tw (z) is guaranteed to be a monotone and 3-Lipschitz function. In the following claim, we show that the function class H(B, L) is covered by Lipschitz-continuuus functions.
Claim D.7. It is without loss of generality to assume that ő E He L) is BL/ BL/Ve-Lipe V--ipschirz.
Proof. Let a H(B, L) such that ||o 0122, S c. By Fact A.5, we have that for any (0,1) it holds ||T o 11 < (1 |o''l, < (1 L²) Therefore, choosing p² 1 - c/L2
have that for any function e H(B, L), there exists function Tho E H(B, L) such that
29

---

- I and hence I|T - I 2c. Furthermore, the function T T2)(2) is BL/Ve.
Lipschitz since according to Fact A.2 part (c) we have (I S Iallr~//11 p² < BL/Ve. Therefore, the function class H. (B, L) is covered by Ve-Lipchtt functions and hence it is without loss of generality to assume that a E HB L) VE-LVishhhii..
We now ready to prove the sample complexity and the correctness of the testing algorithm. We restate and prove Lemma D.5.
Lemma D.5 (Learning the Predictor and Testing). Algorithm 5 given n = poly (B, L, 1/e) samples and a set Sool of poly(B. B, L, 1/c) vectors, with probability at least 99% returns a solution pair (ūw. W), with üw being Lipschitz and monotone, and w Stoo, succh that
E (x.))D
(Tw (w x) - 1-0) S
min E (x.y)~
[(o(w x) - -y) te.
wE
for some universal constant
Proof. Let 3 BL/VE VE (if we know that the target activation is b-Lipschitz, let 3 b). Let {xx(0, 1] be set of samples and let (z) be solution of (Iso) (via linear interpolation),
i...
Tw (2) E
argmin
(1/m)
Σ (u(w x()) - 00
w:B Lip--ipphictz,, 2220
t=1
Note that in Claim D.7 we showed that all the functions in He,,, T.) are 3-Lipschitz functions, hence we have
n (1/m)
n
> Tow (w. - 200
argmin
(1/m) Σ (u(w (a(w-x(9)) x(0) - y)2
W ,EH(B,L),
Let us denote Pu.w (x) ; == u(w x) and let = (Pu. u B-Lipschitz, u' 2 0, w E S } be the family of all such Pu,w. Let [((Fu,w) == E B(x.)~D((PP,.) - 3) Denote the empirical distribu- tion on (0))) by Dn, we define [(ppu,) E (xx))) ((/uu,((x) y) Furthermore, let
argmin [(w)) L == min L(p). yeu
Fell
Then, since we know there exist an activation E H.,B, L) and a vector w E Sool such that (okw)>>((<<((e x) - -) < COPT holds that L S COPT + Furthermore, by definition we have
argmin
E [[v u(w x)) [(p(x)) - y) = Lipehipp 20, weStol (x.y)~ (x.
E
argmin
PEu
indicating that 6- is solution of the problem (Iso) with respect to some vector w E Sool, i.c., (x)) Pū & (x) = Uw (wr x) for some 3-Lipschitz function üي and w gool
We use the following fact to show that (() are close to L(Pu,,) for all Pa,w E U:
Fact D.8 (Theorem 1, [SSTIO]) Suppose there exists constant b > such that for any up U, and any (x,y) y) D it holds (y(() - y)² < b. Let RR,(I) be the empirical Rademacher complexity of function class U with respect some sample set (x(1),... ,...,,"", (,..,,x(*)) and let Ru,( (uP(x())...xxm) Rr, (l1). We have that with probability at least size n, for any E Ud holds for some universal constant C' > 0 that
over the random sample set of
(VESO)
log (x) blog(1/8)
(n) blog(1/8)
((p)) < -C
n
and
b (1/8)
+ loog Iog((m)R2 blog(1/8)
[((") < L" +C¹
VC.
log 1.5 (n) +
n
30

---

Note first that since u E 2 by definition we have |u| I B and since lu S B as well, it holds [Ø(x)] < and (ip(x) y)² X B for any yp U.
Fact D.8 implies that if is large enough such that (2, I v log2/2 (n) and B (lg(1//)/// I c, then are guaranteed that: (1) for any activation and any vector B(x.s)-D((u())) x) - =) I (x.g)> [(u(w x) =);; (2) for the solution pair (0 w) that achieves the minimal empirical loss among all the vectors w from S and all B-Lipschitz activations, Le., Ø² Pā w argminpeu (x.)) [(p(x) y)²) we have L(ppa,.) ((x.)))D[(u> (w x) - v) & (C' + 1)C* & CC'PP + c. Therefore, by solving (Iso) and finding the besting fitting activation uw for each w E Stol and outputting the solution pair (u w) with the smallest empirical error, we are ensured that us (w x) a constant factor approximate solution such that E(x,))~ (ww (w x) - y) I COPT +
S it holds
Thus, it remains to bound the Rademacher complexity of the function class U and choose such that (U) S VE/ (/gg(((()) (n) and B log(1/6)/n S e. To this aim, we use the following fact:
Fact D.9 (Lemma A.3, [SSTIO]). For any function class Ut let N2(e,U, n) be the e-cover of u with respect to E2 norm sample set (x("),,..,,)))),, Let Dn be the empirical distribution .()),...,x()),, Then,
(2) S inf 4a + 10 puupeerr B BALD, [x]]
(o, m)l) de}
azu
n
Let F. be the family of monotone and B-Lipschitz functions that maps (- M M to BB (recall that for all o==) E H. L) we can truncate the domain of a1z) to [-M, Mj where M S (lo)(B/e), as shown in Fact A.9, therefore. it is sufficient to consider the function class of monotone B-Lipschitz functions u that maps from [-M, MM to [-B, B] that contains the target activation r). Then, standard results showed that [,, n)] < [N m)] (B/e)2 (one can show this via constructing grid of width </3 on the domain [-M, M and another grid of width e on the codomain, see e.g., Lemma 6, [KKSKI1]). Hence, since F o S we have [N, U, n)l I (e, n) S (B/e)2M//<((5m) Then, choosing a 1/n in Fact D.9, and noting that v BBxDD (x2(x)) < 11pl|r.. I
B, we obtain
l B 1/n
1,) x n
+
/og(((><o1) + (M) log(B/e) de
+ B (log((S>ol))
1
B (MBBe) de + V 11/n
x n
Vlog(B/e)de
n
n
1/m
log Sool
M3B
M3B² log( Stol)
< + B
Thus, Ru, S M log( St0l )/n. Recall that we have |S = poly(1/e, B, L). M <
L).
/ (log(B/e] and 8 = BL/ Ve (Claim D.7), therefore to guarantee that (2) < v log 2/((2))) and
B² log(1 (1/5)/ < e, it suffices to choose n @(lo((BI/ee)on ( completes the proof.
Letting 8 0.01
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, main claims made the abstract and introduction accurately reflect the paper's contributions and scope. The main contribution is summarised in the main theorem.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we discussed the limitation in the introduction section and the final conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification: Yes we provided the full set of assumptions for each theoretical result. Each theorem statement states all the assumptions. We provide complete proof for all statements in the supplementary material. Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
33

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wtips.cc/ppblccc//eccccccpcppppp gewic//gugee....e CoodeSummii www.nnoolicciooeooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: :tttpss:/nnuurt http///nurrrppppeeee hctpppplccc/tchccccccciieeeeeeed
Answer: [Yes]
Justification: Our paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper theoretical work and not tied any particular applications, and we do not see any major or immediate implications on society.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is a theoretical work and contains no data set.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
37

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : ht/pa/rrps.cccoooeeeeeeeeeeeeeee / for what should or should be described.
38


Reviews:
[{"review_id": "5t7GYnLaE5", "reviewer": "Reviewer_Be7r", "summary": "This paper provides the first computationally efficient algorithm for robustly learning a Single-Index Model (SIM) of the form $f(x) = \\sigma(w \\cdot x)$ when the activation function $\\sigma$ is unknown but belongs to a broad class of monotone functions, the input distribution is Gaussian, and the labels are subject to adversarial noise. The algorithm achieves a constant-factor approximation to the optimal squared loss, resolving a significant open problem in the algorithmic theory of SIMs. The main technical innovation is a novel optimisation framework that moves beyond gradient-based methods, instead using a carefully constructed vector field, identified via spectral methods, to guide the search for the optimal parameter vector.", "questions": "- Your spectral method relies on constructing a moment matrix $M_w$. To what extent are the key properties required for your analysis (specifically, the spectral gap between the top eigenvalue and the rest of the spectrum) tied to the Gaussianity of the input distribution? Could this spectral alignment framework be extended to other distributions, such as isotropic log-concave distributions?\n\n- The algorithm's final stage relies on a random walk to overcome the sign ambiguity of the identified eigenvector, requiring $poly(1/\\epsilon, B, L)$ repetitions to guarantee success with high probability. Could you comment on the practical magnitude of this number of repetitions? Furthermore, is there a potential path to \"de-randomise\" this component?\n\n- What are the primary obstacles to extending this spectral alignment approach to robustly learning a multi-index model? Would the top eigenvectors of a similarly constructed moment matrix still capture the subspace of interest, or would the interactions between different index directions fundamentally complicate the spectral picture?\n\n- Given the work is purely theoretical, what specific insights do you believe an empirical study would provide? For example, how might the constants hidden in your asymptotic analysis behave in a finite-sample setting, and what is your hypothesis on the algorithm's robustness to minor deviations from the Gaussian data assumption?", "limitations": "The primary limitations of this work are threefold. First, its theoretical guarantees are confined to the standard Gaussian input distribution, which restricts its direct applicability. Second, the algorithm's high polynomial complexity and multi-stage, randomised nature raise questions about its practical feasibility despite its theoretical efficiency. Finally, the work is entirely theoretical, with no empirical validation provided in either the main paper or the supplementary material. The absence of experiments means there is no insight into the algorithm's finite-sample performance, the practical values of the constants in the bounds, or its robustness to even minor deviations from the strict distributional assumptions.", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "*Disclaimer: I am not an expert of the field and the proofs in the SM have not been checked.*\n\n# Strengths\n\n- It successfully provides the first polynomial-time, constant-factor approximation algorithm for agnostically learning SIMs with a very general class of monotone activations. This class includes all monotone Lipschitz functions and discontinuous ones, which covers many cases of practical and theoretical interest.\n\n- The main technical idea is novel. The authors' departure from standard gradient-based optimisation and designed a custom moment matrix $M_w$ that can be analysed with spectral methods to guide the gradient.\n\n- For a paper with high technical density, the exposition is remarkably clear.\n\n# Weaknesses\n\n- The entire analysis is contingent on the assumption that the input data $x$ follows a standard multivariate Gaussian distribution. This is a strong limitation, as the analytical tools used (e.g., properties of the Ornstein-Uhlenbeck semigroup, Gaussian integration by parts) are highly specific to this setting. The authors rightly note that generalising beyond Gaussian marginals is a major open question, even for simpler models. As it stands, the algorithm's direct applicability to non-Gaussian, real-world data is limited.\n\n- While the algorithm is proven to be \"efficient\" in the theoretical sense (i.e., runs in polynomial time), its complexity appears prohibitive for practical use. The sample complexity is $N=d^{2}poly(B,L,1/\\epsilon)$, and the overall algorithm involves multiple nested subroutines, including an initialisation procedure that grids over a parameter space and a main loop that performs a random walk, requiring the core routine to be repeated many times to ensure success. \n\n- The work is entirely theoretical and lacks any experimental validation. This absence prevents an assessment of the algorithm's finite-sample performance, the practical magnitude of the constants hidden in the theoretical bounds, and its robustness to even minor deviations from the strict Gaussian assumption.", "was_revised": true, "final_justification": "I have read the authors' rebuttal and the other reviews. My assessment of the paper remains unchanged.\n\n​This paper makes a significant theoretical contribution by providing the first polynomial-time algorithm for robustly learning single-index models with unknown monotone activations, a long-standing open problem. The technical approach is novel and the exposition is clear.\n\n​The authors have satisfactorily addressed my main concerns. Their justification for focusing on the Gaussian distribution is reasonable, it tackles a known open problem, and extensions are non-trivial even for much simpler cases. While I maintain that the lack of experiments is a limitation, I agree with the authors that it is not a prerequisite for acceptance for a purely theoretical work of this caliber.", "rebuttal": "We thank the reviewer for their effort in evaluating our submission and for their insightful questions. We are  encouraged by the reviewer’s positive assessment, particularly on the **significance** of the paper, the **novelty** of the techniques, and the **clarity** of our presentation. Below, we respond to the reviewer’s comments and questions.\n\n**Gaussian Assumption**: \n- Response: The reviewer is correct that our algorithmic result makes essential use of the Gaussian distribution. As pointed out in the submission, the question we resolve (robustly learning monotone SIMs under Gaussian marginals within a constant factor) has been a recognized open problem in the field (see, e.g., the prior works [WZDD23], [WZDD24], [ZWDD24], [ZWDD25] all cited from the main body). As the reviewer noted and is stated in our paper, to achieve a constant-factor approximate learner beyond Gaussian data, one would first need to make progress on (very) special cases of the problem when the activation is known (e.g., for a general Linear Threshold Function or a general, potentially biased, ReLU). \n\n**Practicality and Experimental Evaluation** \n- Response: As the reviewer notes, our work is in the area of learning theory. The primary focus was to provide the first polynomial (in the dimension $d$ and $1/\\epsilon$) sample and time algorithm for our learning task. As such, we did not optimize the absolute constants or the constant powers of $1/\\epsilon$ in the resulting complexity bounds. That said, we are confident that a more careful analysis may yield a significantly improved upper bound.  While experimental evaluation of our algorithm would be interesting, we note that the NeurIPS call for papers invites purely theoretical works (for which experimental evaluation is not required). \n\n**(Question 1): To what extent are the key properties required for your analysis tied to the Gaussianity of the input distribution?**\n- Response: Our work crucially relies on the Gaussianity of the feature vectors in two main aspects:\n\n1. **Spectral Subroutine:** To derive our main structural result—that the top eigenvector of our designed matrix aligns with the target direction—we relied on Stein’s lemma and the properties of the Ornstein-Uhlenbeck (OU) semi-group. It is not immediately clear how to extend this result to non-Gaussian distributions.\n\n2. **Initialization Subroutine:** This part of our algorithm transforms our learning problem into the task of agnostically learning halfspaces under Gaussian marginals. Unfortunately, even for this special case, there is no known efficient algorithm that achieves a constant-factor approximation beyond the Gaussian case; see the conclusion section, line 391-393.\n\nWe are hopeful that similar ideas might be adapted to non-Gaussian distributions and leave this as an important direction for future work.\n\n**(Question 2): Practical magnitude of number of repetitions in random walk and potential derandomization.**\n- Response: The total number of iterations incurred by this step is on the order of $(L/\\epsilon)^c$ for some universal constant c, which we did not optimize. The upper bound in our analysis relies on the worst case (monotone) function in the class. That said, for natural subsets of activations (e.g., activations with heavy tails or exponential tails) it is possible to obtain faster convergence rates. Regarding de-randomization, it is currently unclear to us how to circumvent the random walk approach. One potential approach would be to determine the correct sign of the eigenvector by testing which direction yields a smaller error. However, obtaining such an accurate estimate for a general monotone function under agnostic noise is a significant challenge in itself.\n\n**(Question 3): What are the primary obstacles to extending this spectral alignment approach to robustly learning a multi-index model?**\n- Response: Extending our approach to multi-index models (MIMs) is challenging for a number of reasons. The primary obstacle is that the interactions between different index directions would fundamentally complicate the spectral field of the moment matrix. For the case of SIMs that we study, it turns out that second moment information suffices for our purposes. For the more general setting of MIMs, the second moment matrix would likely no longer suffice to capture the subspace of interest, and leveraging higher-order moment information would become necessary. Very recent work has provided some theoretical justification of this observation for learning MIMs, via SQ and low-degree polynomial lower bounds; see, e.g., [DIKZ25]. \n\n\n**(Question 4): Potential Insights of Empirical Study**\n- Response:  In an empirical study, we expect (1) better performance than what is predicted by the theoretical bounds, as our focus was on getting a polynomial time algorithm and constant factor approximation, which was the primary open question we were aiming to address. In particular, we expect the algorithm to perform well even with a smaller sample size and to have a reasonably small constant approximation ratio. (2) The algorithm should remain robust to minor deviations from Gaussian data, as the data augmentation itself should have a \"correcting effect\" for such deviations, making the data \"look and behave more Gaussian.\" (3) Furthermore, an empirical study could investigate the algorithm's performance on certain classes of non-monotone activations. While our theoretical guarantees for key components like the initialization and the error analysis crucially rely on the monotonicity assumption, the core optimization routine itself is more general. Observing strong empirical performance even on some non-monotone functions would be a compelling result, potentially motivating future theoretical work to relax this assumption.\n\n\n[WZDD23] P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Robustly learning a single neuron via sharpness. 40th International Conference on Machine Learning, 2023.\n\n[WZDD24] P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Sample and computationally efficient robust learning of gaussian single-index models. The Thirty-Eighth Annual Conference on Neural Information Processing Systems, 2024.\n\n[ZWDD24] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning single-index models via alignment sharpness. In Proceedings of the 41st International Conference on Machine Learning, 2024.\n\n[ZWDD25] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning monotone generalized linear models via data augmentation. COLT 2025\n\n[DIKZ25] Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, and Nikos Zarifis \nRobust Learning of Multi-index Models via Iterative Subspace Approximation 2025, arXiv:2505.21475"}, {"review_id": "UEgVungCV7", "reviewer": "Reviewer_vBoH", "summary": "This paper tackles the problem of learning generalized linear models with Gaussian inputs $x$ where both the parameters and the activation/link function are unknown. The parameters are assumed to be bounded and $\\sigma$ is assumed to belong to the class of monotone, Lipschitz functions (or monotone functions with bounded $2 + \\delta$-moment). The goal is to jointly learn both the activation and parameters. The core contribution of this is the development and analysis of an algorithm for learning $(\\sigma, w)$. The algorithm is based on the spectrum of a matrix constructed from the data whose eigenvectors are supposed to strongly correlate with the optimal parameters $w^\\star$. The algorithm is shown to achieve a constant factor approximation of the optimum from a polynomial number of samples (with respect to the input dimension).", "questions": "1. Line 126 : \"Thus, to ensure $\\|T_{cos \\theta} u' - T_{cos \\theta} \\sigma'\\|$  small, it necessitates approximating the low degree coefficients of $\\sigma'$ (under adversarial noise and without the knowledge of $\\sigma$), imposing formidable technical challenges.\" Could the authors elaborate on these challenges?\n2. On line 174, the author argues that because the labels are adversarially corrupted, estimating $g^\\star_w(z)$ as $E[yx^{\\perp w} | w \\cdot x \\in (a,b)]$ is not possible. Could the authors elaborate on why this is the case?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\nThe main contribution of this work is the core construction of the update direction. It involves two non-trivial steps: posing the choice of update direction as a \"correlation maximization problem\" and estimating the solution of this problem from the spectrum of a matrix that can be constructed from data.\n\n\n## Weaknesses\n\nThe manuscript is difficult to read and at times informal or unclear. This makes it very difficult to parse the exact contributions of the work and assess their correctness. For instance, the main text contains several instances of notation that are either used before being defined or not defined at all. For instance, Section 1.1 refers to $T_{\\rho}$, $x^{\\perp w}$, and $\\gtrsim$ only defined later in Sec 1.2. This makes the section (which is almost 1/3 of the paper) almost impossible before having read through the full paper (with appendices). These issues are compounded with the continuous use of inline math, including to introduce proof sketches (e.g., line 190-197, which do not even point to a specific result later in the paper). This makes the section virtually unreadable. While I understands that conference papers have space constraints, I do not believe it is an excuse to jeopardize clarity.\n\nThe manuscript (and appendices) also repeatedly refer to results in the literature without explicit references, which makes them impossible to assess. This is particularly critical with respect to [ZWDD25] (which contains a plethora of results), e.g., \n    - Line 122-125 : \"Even though it is possible to control the L2 distance between $u(z)$ and $\\sigma(z)$ by $\\theta(w, w^{\\star})$ following **similar steps as in [ZWDD24]**, it is unclear how to show that $T_{cos \\theta}u'(z)$ is close to $T_{cos \\theta}$ \\sigma'(z)$ so that [...] and **the arguments of [ZWDD25] can go through**.\" (which steps/arguments?)\n    - Line 162 : \"and we **know from [ZWDD25]** that ...\" (specific proposition? theorem? proof?)\n    - Line 258 : \"and transform the regression problem to a robust halfspace learning problem, following **the same procedure** as in [ZWDD25]\" (which procedure?)\nIt is difficult to understand these references without knowing the specific results the manuscript is aluding to.\n\nThe comparisons to other works are also not very clear. For instance, this work extends [ZWDD25], which also assumes Gaussian inputs, but only mentions [GGKS23] which works with similar assumptions on the activation function, but *no distributional assumptions* (while labels are confined to [0,1], the labels in the current manuscript are also bounded given the that f is uniformly bounded). It is not straightforward, from the discussions in the paper, to see how the results are considerably weaker in this setting, seen as the sample complexity look comparable and the proportionality constants of the optimality factor are not clearly described. While [GGKS23] does depend on $W$, the radius of the space, it is not clear that this is worst than the constants for Algorithms 1-4. Particularly, since the bound on $\\|w\\|$ in [GGKS23] is replaced here by a uniform bound $B$ on the activation/link function (I believe that is in fact part of the argument in Remark 2.2 leveraging the homogeneity of $\\sigma$). Again, it is hard to adjudicate these matters from the presentations in the manuscript.\n\nOn a minor point, it is not clear to which extent the labels are per se \"adversarial.\" Though the agnostic learning setting can be seen as incorporating a form of \"adversarial label noise\" (as in, e.g., [DKMR22]), the setting of this paper is not fully agnostic since $x$ is assumed to be Gaussian. I imagine that what is meant by adversarial label noise is the fact that no assumptions are made on the conditional $y|x$, but this point should be explicitly addressed in the manuscript.\n\nWhile the paper might have relevant contributions, it requires considerable improvement in its presentation for the novelty and correctness of the contributions to be evaluated. I therefore cannot recommend the manuscript be published in its current form.", "was_revised": true, "final_justification": "It is not clear from the manuscript that the contributions of this work (in terms of results or techniques) warrant a publication at this stage. I believe it is interesting and of interest, but it would require additional work that is too substantial for a minor camera-ready revision. I don't feel strongly enough to recommend it for acceptance, but I also would not stand in its way.", "rebuttal": "We thank the reviewer for their time and effort in reviewing our paper. We address the reviewer’s points below.\n\n**(Weaknesses 1 & 2): Presentation** \n- Response: In the introductory section (Section 1), we intentionally adopted a degree of informality to avoid introducing too many technical details (while focusing on the key novel ideas of our approach). We believe this enhances readability. Regarding the notation pointed out by the reviewer: First we note that this notation is fairly standard in this subfield of theoretical machine learning and specific definitions (such as $T_\\rho$, for which a forward reference is provided the first time it is mentioned) are not crucial to explaining the intuition, which is the purpose of Section 1.1. Importantly, we provide all required definitions and notation in Section 1.2 (see page 5). That said, we will revise this section to ensure forward references are included for all the utilized notation. \nRegarding references to prior work: We must respectfully but firmly push back on this assessment.  While in the introduction our goal was to provide high-level context, we provided full technical details and references to all needed results in the supplementary material (see Facts A.8, A.9, B.1, B.2, C.2).\n\n**(Weakness 3 & 4): Comparison to Prior Work**\n- Response: A detailed summary of prior work is given in lines 71-87, where we provide a comparison to [ZWDD25], [GV24], [ZWDD24], and [GGKS23], which are closest to our work. Specifically, regarding the comparison with the work of [GGKS23], we reiterate the point made in our submission: Our algorithm achieves an error of **$C \\cdot OPT + \\epsilon$**, where $C$ is a **universal constant–independent of any problem parameters**–in the case where the activation function is **unknown**.  This answers a recognized open problem in the literature. For example, this precise question was posed as the main open problem in both [ZWDD24] and [ZWDD25] (see the “Conclusion” section of  [ZWDD24] and the “Conclusions and Open Problems” section of [ZWDD25]).\n\nThe prior work of [GGKS23] obtains an error of $O(W) \\sqrt{OPT} + \\epsilon$, where $W$ is the diameter of the space. The parameter $W$ can depend polynomially on the dimension $d$ and cannot be viewed as a “constant”. Additionally, their error guarantee is also sub-optimal as a function of the parameter $OPT$. We want to emphasize here that this distinction (constant vs non-constant approximation ratio) is not new. A number of prior published works in this field make this distinction clear and pose the question of obtaining a constant factor approximation as an open question. Concrete recent examples include lines 78-82 and page 2 of [ZWDD24] and Appendix A of [ZWDD25]. Earlier references include [DGK+20] and [DKTZ22a], cited in our work. \n\nA point of confusion from the reviewer may be the notion of “boundedness” for the labels. In our setting, even though the labels are bounded (and this is w.l.o.g., as discussed in the paper), the upper bound is not necessarily an absolute constant: instead, the upper bound can scale polynomially with the diameter of the space (hence, also the dimension) and also depend on the desired accuracy. Specifically, for the basic case of a ReLU activation, the effective bound on the magnitude is roughly $W\\sqrt{\\log(1/\\epsilon)}$, where W is the radius of the space and $\\epsilon$ an accuracy parameter. In summary, there is a major qualitative difference with the prior work [GGKS23]. It is essential here that our approximation ratio in the error is *independent* of this quantity—and any other problem scaling (i.e., possibly rescaling the labels or the problem space via a change of variable has no impact on the multiplicative approximation guarantee and this is in contrast to prior work).\n\n**(Weakness 4): Regarding adversarial label noise/agnostic noise**\n- Response: While this point was deemed minor by the reviewer, we have the following comments. The terminology we use (i.e., interchangeably using the terms “distribution-specific agnostic learning” and “learning with adversarial label noise”) is standard in the literature; see, e.g., [KKMS05], [ABL17] for the task of learning Linear Threshold Functions and [DKTZ22a] for the task of robustly learning GLMs (a special case of our task). Recall that we work in the distribution-specific setting where the feature vectors are assumed to be drawn from the standard normal (this is a standard and extensively studied regime in the literature). Importantly, no assumptions are made on the labels and our goal is to compete against the best-fit function in the class. An essentially equivalent phrasing is that we start from clean labels (i.e., consistent with the target function in the class) and then an adversary is allowed to arbitrarily corrupt them, subject to the constraint that the total misspecification (with respect to the $L_2$ loss) is bounded above by OPT. See for example lines 28-34 for a brief explanation.\n\n**(Question 1) Approximation of $\\sigma’$:**\n- Response: The challenge in approximating the derivative $\\sigma'$ is significant because this task is equivalent to learning the polynomial approximation of $\\sigma$. The latter task requires sample complexity $d^{m/2}$, where $m$ is the degree of the polynomial approximation (which may be large). (We note here that learning with respect to the $L_2$-norm is equivalent to finding a function that has a closely approximating polynomial expansion.) On the other hand, the sample complexity of our algorithm is $O(d^2)$, which does not depend on the degree of the polynomial expansion of the unknown activation.\n\n**(Question 2) Estimation of** $g_w^* (z)$\n- Response: The core challenge is that an adversary can manipulate labels at specific (individual) points without affecting the overall loss, which makes naive estimation impossible. Since we cannot efficiently sample at an exact point $w \\cdot x = z$ (as this is an event with probability measure zero), a natural choice would be to sample from a small band or interval. This approach would indeed work (efficiently) in the realizable case, when the labels $y$ are equal to $\\sigma(w^{\\ast} \\cdot x)$, for a monotone activation $\\sigma$. Unfortunately, this fails in the agnostic/adversarial label noise setting we consider for the following reason: an adversary can place extreme noise at one point $z$. As this is a single point, the measure is zero, and this manipulation does not actually change the overall loss. However, if we try to estimate the value of $ g_w^* (z) $ by averaging $yx$ over the interval containing $z$, we will never sample this specific point $z$ and we will never observe the extreme value. This makes our local estimate of $g_w^*(z)$  inaccurate (with error we can make arbitrarily high by increasing the magnitude of the noise).\n\nInstead of trying to estimate the corrupted function directly, our approach is to find a function that performs at least as well as the unknown activation, specifically $T_{\\cos\\theta}\\sigma'$. A key property of the Ornstein-Uhlenbeck semi-group is that it is a **smoothing operator**. This means that the function $T_{\\cos\\theta}\\sigma'$ is smooth and, therefore, nearly constant within small intervals. This property justifies approximating it with a **piecewise-constant function**, as the error introduced will be controllably small. By estimating the average value over a band, we thus obtain a piecewise-constant estimate. Our analysis shows that this approach is sufficient because this approximation is good enough to effectively compete with the smooth target, successfully overcoming the adversary's potential manipulations.\n\n[KKMS05] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. FOCS 2005\n\n[ABL17] Awasthi, P., Balcan, M. F., and Long, P. M. The power of localization for eﬃciently learning linear separators with noise. Journal of the ACM, 2017\n\n[DKTZ22a] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning a single neuron with adversarial label noise via gradient descent. COLT 2022\n\n[GGKS23] A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. NeurIPS 2023\n\n[ZWDD24] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning single-index models via alignment sharpness. In Proceedings of the 41st International Conference on Machine Learning, 2024.\n\n[ZWDD25] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning monotone generalized linear models via data augmentation. COLT 2025\n\n[GV24] A. Guo and A. Vijayaraghavan. Agnostic learning of arbitrary ReLU activation under\nGaussian marginals. COLT 2025"}, {"review_id": "JwByd7Ac0t", "reviewer": "Reviewer_Kf2k", "summary": "The paper makes progress for the problem on agnostically learning monotone single index model.", "questions": "I feel like some ingredients in the new algorithm including the alignment part, the spectral subroutine and the approximation part have all been used for related problems. Can the authors comment on such related work or (boldly) claim these are novel.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper shows technical competency in improving on a natural problem.\nHowever, both in terms of the proofs and in terms of the results there is a concern about how incremental the result is.\n\nObtaining a *constant-factor* approximation for learning *monotone* single-index model for an *unknown* activation was indeed unknown before. But removing any of the highlighted conditions either makes the results invalid or known. So the progress is for a somewhat narrow problem. Also the case where the activation has slightly stronger assumption is studied in ZWDD24.", "was_revised": true, "final_justification": "The paper seems to contain nice technical contributions but the questions studies is a bit too specific.", "rebuttal": "We thank the reviewer for their time and effort in reviewing our paper. We address the reviewer’s points below.\n\n\n**Significance**\n- Response: While the problem setting we consider is specific, it resolves a well-known open question (see, e.g., prior works [WZDD23], [WZDD24], [ZWDD24], [ZWDD25] cited in the main body). This is common in learning theory papers (as ours), that are within the scope of the conference (as per the call for papers). Our work provides the first constant-factor approximation algorithm for agnostically learning SIMs under the Gaussian distribution, where the only assumption on the activation is that it is monotone. Prior work either required significantly stronger assumptions or achieved qualitatively weaker error guarantees (see lines 71-87 and [GGSK23, ZWDD24]). In particular, the [ZWDD24] paper that the reviewer referred to required significantly stronger assumptions on the activation class—that excludes basic activations like biased ReLUs, sigmoids, Linear Threshold Functions, etc.-- whereas our algorithm can deal with *any monotone* activation, a class that includes the activation class considered in [ZWDD24] as a mere subset. Furthermore, the error guarantee obtained in [ZWDD24] is considerably weaker than ours: in [ZWDD24] the final error is $O((\\max_{z\\geq 0}\\sigma’(z))/(\\min_{z\\geq 0}\\sigma’(z)))^4\\cdot OPT$ (infinite for activations like the Linear Threshold Function and exponentially large for activations like sigmoid), whereas ours scales as $C\\cdot OPT$ with $C$ being an *absolute constant,* independent of *any* problem parameters. Obtaining our result (which, we reiterate, was posed as an open problem in these prior works) requires new algorithmic and analytic insights, as we have illustrated in Section 1.1 of our submission.  \n\n**Overlap with “concurrent work” [ZWDD25]**\n- Response: We note that [ZWDD25] is a **prior work**. It appeared on arxiv in February and its conference version recently appeared in COLT 2025. We reiterate that [ZWDD25] posed as an open question the problem we solve (among other prior works, please see our first response bullet above). At the technical level, our algorithm utilizes two key ingredients from that work (the initialization and the error-angle connection). We emphasize that these components alone are by no means sufficient to solve the problem with an unknown activation function, which is the core technical challenge we solve. As we have thoroughly discussed in the manuscript (see e.g., lines 119-131), the gradient alignment property that is crucial to [ZWDD25] no longer holds in our setting, due to the fact that the activation $\\sigma$ is no longer a prior known to the learner. Further, a high-accuracy estimate of $\\sigma$ is also unavailable due to the agnostic noise. The gradient alignment property is the main structural result in [ZWDD25] that established the convergence guarantee of their algorithm. Regarding the novelty of our techniques, please see below. \n\n**(Question): Novelty of Techniques**\n- Response: We provide a summary in the following paragraphs. A more detailed description is given in our submission (see references to specific lines below).\n\n1. Our **spectral subroutine**, based on a duality argument, is **novel** and of independent interest. In particular, the spectral subroutine identifies an optimal vector field for the gradient descent steps that is substantially different from prior works, as noted in our manuscript (lines 97-100): ’On a conceptual level, our work makes the case for stepping outside the usual boundaries of gradient based methods and instead looking to directly design a vector field that can be computed from the information given to the algorithm and that carries useful information about the location of target solutions.’ The overview of the spectral subroutine is presented in lines 156-168.\n\n2. Our optimization method is fundamentally different from prior approaches. Our algorithm **does not need to estimate the activation function** at each step. This is yet another major difference from prior works, which required an alternating approach to estimate the best-fitting activation $u$ on each update and then update the parameter $w$. This is another novel feature of our algorithm, as we have clearly stated in lines 129-131, that ‘...it is unclear whether prior SIM learning frameworks [KKSK11, ZWDD24, HTY25]— alternating between the “best-fit” updates for activation u and gradient-style updates for w—can resolve this issue [of creating alignment between the gradient and the optimal parameter w*]. Hence, our work represents a departure from this seemingly natural approach.’\n\n3. We are not aware of any prior work that uses a **random walk-based optimization procedure** in a similar context and that is proven to converge in polynomial time (lines 185-197). \n\n[WZDD23] P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Robustly learning a single neuron via sharpness. 40th International Conference on Machine Learning, 2023.\n\n[WZDD24] P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Sample and computationally efficient robust learning of Gaussian single-index models. The Thirty-Eighth Annual Conference on Neural Information Processing Systems, 2024.\n\n[ZWDD24] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning single-index models via alignment sharpness. In Proceedings of the 41st International Conference on Machine Learning, 2024.\n\n[ZWDD25] N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning monotone generalized linear models via data augmentation. COLT 2025.\n\n[GGSK23] A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. In Thirty-seventh Conference on Neural Information Processing Systems, 2023."}]

Author rebuttal:

Meta-review: This paper proposes a computationally efficient algorithm to learn single index models $f(x)=\sigma(w\cdot x)$, where both the activation function $\sigma:\mathbb{R}\to \mathbb{R}$ and $w\in \mathbb{R}^d$ are learned from data with adversarial label noises. The primary contribution of the paper is the development of the first polynomial-time, constant-factor approximation algorithm for agnostically learning SIMs with a broad class of monotone Lipschitz activation functions, addressing an open problem in the literature. Additionally, the paper introduces several novel techniques, including the use of a spectral subroutine to identify an optimal vector field for gradient descent steps and a random walk-based optimization procedure.

Meanwhile, the paper has some limitations: it assumes the input data follow a Gaussian distribution, the algorithm's complexity may be high for practical applications, and it lacks empirical validation. Reviewers also suggest improvements in the presentation for enhanced clarity. Overall, the reviewers are generally satisfied with the authors' responses, acknowledging that while the results are interesting, substantial efforts are needed to improve the clarity of the presentation and the articulation of the main contributions.
Decision: Accept (poster)