Robust Regression of General ReLUs with Queries
Authors: Ilias Diakonikolas
Daniel Kane
Mingchen Ma
Venue: NeurIPS 2025 poster ()
Keywords: Learning Theory
Active Learning
ReLU Regression
Agnostic Learning
Primary area: theory
TL;DR: We design the first efficient algorithm that solves the general agnostic ReLU regression with optimal query complexity

Abstract: We study the task of 
agnostically learning general 
(as opposed to homogeneous) ReLUs 
under the Gaussian distribution with respect 
to the squared loss. In the passive learning setting, 
recent work gave a computationally efficient algorithm 
that uses $poly(d,1/\epsilon)$ labeled examples 
and outputs a hypothesis with error $O(opt)+\epsilon$, 
where $opt$ is the squared loss of the best fit ReLU.
Here we focus on 
the interactive setting, where the learner 
has some form of query access to the labels of unlabeled 
examples. 
Our main result is the first computationally 
efficient learner  
that uses 
$d polylog(1/\epsilon)+\tilde{O}(\min\{1/p, 1/\epsilon\})$ 
black-box label queries, 
where $p$ is the bias of the target function, and achieves error $O(opt)+\epsilon$.
We complement our algorithmic result by showing 
that its query complexity 
bound is qualitatively near-optimal, 
even ignoring computational constraints. 
Finally, we establish that query access 
is essentially necessary 
to improve on the label complexity of passive learning. Specifically, for pool-based active learning, 
any active learner 
requires $\tilde{\Omega}(d/\epsilon)$ labels, 
unless it draws a super-polynomial
 number of unlabeled examples.

Robust Regression of General ReLUs with Queries
Ilias Diakonikolas" University of Misconsin-Madisoee ilias$cs. wisc.edu
Daniel M. Kane"
University of California, San Diego dakane@cs. ucsd.edu
Mingchen Ma*
University of Wisconsin-Madison mingchen&cs. wisc.edu
Abstract
We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. the passive learning setting, recent work gave computationally efficient algorithm that uses poly(d, (d, 1/e) labeled examples and outputs hypothesis with error ((opt) + where opt is the squared loss of the best fit ReLU. Here we focus the interactive setting, where the learner has some form of query access to the labels unlabeled examples. Our main result is the first computationally efficient learner that uses dpolylog(1/e) (1/e) (min ( 1/p, 1/c]) black-box label queries, where is the bias of the target function, and achieves error ((opt)+<.. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires (dd/e) labels, unless it draws a super-polynomial number of unlabeled examples.
Introduction
ReLU activations play central role the design of modern neural networks. ReLU function aW 1) max - f, 03 is specified by pair of parameters (W, (), where W E Rd and t TR. ReLU regression the following basic problem: given some form of access to a distribution D over Rdd x R. output a ReLU with loss that can compete with opt-the loss of the best-fit ReLU with respect to D. This fundamental task has been extensively studied the past decades; see, e.g., IKKSKIL, FCG20, DGK+20. VYS21, DKTZ22b, WZDD23, ATV22, GV24] and references therein. Prior algorithmic work has focused on learning from random examples (passive learning) and has obtained efficient learners with error (optt) + e, under the assumption that the marginal distribution D. is well- well-behaved; in most cases, a standard Gaussian or a structured distribution with similar properties. Such benchmark is motivated by known computational hardness results for this problem. On the one hand, without any assumption on D.. is computationally intractable to achieve error C opt for any constant C > [DKMR22]. On the other hand, even under the standard Gaussian, it computationally hard to achieve loss opt + [DKZ20, DKR23].
Despite the aforementioned long line of work on this problem, the number of labeled examples needed to achieve the desired error guarantee remains poorly understood. For the special case that the target ReLU has negative threshold (i.e., t < 0) [DKTZ22a, WZDD23] design efficient PAC learning algorithms achieving error (opt) e with a nearly optimal sample complexity of dpolylog(1/e The problem becomes much more challenging for general ReLUs (with arbitrary bias t) and in
Equal Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

particular for t > 0. Recently, [GV24, ZWDD25] gave the first efficient PAC learning algorithms that achieve ((opt) + e error for general t. using poly(d, 1/e) labeled examples. In fact, to learn an arbitrary ReLU to error e, even with clean labels, one needs ((d/e) labeled examples in the passive PAC setting (see, e.g., from Theorem 1.3). Hence, to obtain improved label complexity, one needs to consider stronger data access models that allow some form of adaptive (query) access to the labels.
Learning with queries and reduce the number of labeled examples needed for various learning tasks. Such models capture the ability to perform experiments. or the availability of expert advice, and are well-motivated by real-worlds applications where unlabeled examples are cheap. A long line of work has shown that in such interactive settings one can significantly reduce the number of labeled examples needed for learning in variety of settings [BBZ07, DKM05, BL13, ABL17, YZ17, She21, DMRT24, DKM24, KMT24a, GTX+ TTX++4, 24, LT25J.
active learning are powerful models that can be used to
The focus of this paper is on agnostic learning with black-box query access the labels. Specifically, for I E IRd, we can make a black-box query for its label y(z), where y(z) is generated adversarially,
In the context of ReLU regression, in the noiseless setting, the examples we actually using those with non-zero zero labels. This implies that we have one example with non-zer label, then we only need to make (d) queries in its neighborhood to collect d examples with non-zero labels. This lead to algorithm with label complexity of O(1/p + d--beating the label complexity of passive learning. If p 12)1), existing agnostic learning algorithms robustify the above ideas and nearly match such label complexity, even in the passive setting. However, if p is small (corresponding to large > 0) our understanding of the label complexity is limited. Specifically, there is a large gap in the label complexity of known algorithms for >> 0 versus 0. This discussion motivates the following question:
What the label complexity of the general agnostic ReLU regression problem?
Our main result is the first efficient learning algorithm that solves the general agnostic ReLU regression problem with near-optimal label complexity (see Theorem 3.1 for the formal statement).
Theorem 1.1. Consider the problem of general agnostic ReLU regression with Gaussian marginals. (1min(1/pp
There is an algorithm that makes M = dpolylog( R2 jc) + Ómin (1/p, R2 /ct) queries, runs in Poly(M) time, and outputs a ReLU function o oW t) such that with high probability, h has error (opt) + c. Here, p is the fraction of examples that are labeled non-zero by the optimal ReLU and is the upper bound for [W
Notably, our algorithmic approach solves not only the ReLU regression problem, but also develops new techniques that can be used to analyze a variety of generalized linear models.
Unlike pool-based active learning, where an algorithm first selects a pool of unlabeled examples S from the marginal distribution Dr and is allowed to query y(r) for x E S,S our algorithm makes use of a stronger oracle that is allowed to query any desired point in Rdd.
To complement our upper bound, we show that the query complexity of our algorithm is information- theoretically nearly optimal (see Theorem 4.1 for the formal statement).
Theorem 1.2. Consider the problem of general agnostic ReLU regression with Gaussian marginals. Suppose that the optimal ReLU has bias p and [[*I| = 1. Any learning algorithm that learns a hypothesis h with error Öpp) and succeeds with probability 1/3 must make $2(1/p² + d) queries, even opt < p.
Our final lower bound shows that unless the unlabeled dataset is extremely large, no pool-based active learning algorithm is able to achieve the label complexity of our algorithm, even in the realizable setting. This establishes sharp separation between pool-based active regression and query learning, and resolves the label complexity of ReLU regression (see Theorem 4.2 for the formal statement).
Theorem 1.3. Consider the problem of general (realizable) ReLU regression with Gaussian marginal. Suppose the optimal ReLU has bias p. Any pool-based active learning algorithm that learns hypothesis h with error Ö(p) from a pool of m unlabled examples drawn from N T) and succeeds with probability 1/3 must make (ddd (p log(m))) queries.
Preliminaries and Notation
Here we record the problem definition and basic notation.

---

Definition 1.4 (Agnostic ReLU Regression with Queries), Let Ø(2) = max Of be the ReLU
function. A labeling function y(æ) IRd + R is a random function that maps each x E TRd to an unknown real-valued random variable. For each h. : R + R, denote by crr(h) = E (h(z)-v(zz) y(z))² /2, opt == miD:: err(a(W - -)) and o" o'(x)= o -
x-) be any ReLU with entor opt. A query takes z E R as input and returns label y ~ y(x). We say that a learning algorithm A is a constant-factor approximate learner for every labeling function y(z), and for every e, E (0, 1), it outputs some hypothesis h : R + IR by adaptively making queries, such that with probability at least 1 -- err(h) I (opt)) +e. The query complexity of A is the total number of queries it uses during the learning process.
Furthermore, we will without loss of generality assume opt S since the final error guarantee is Ooopt + +e). We remark that in some parts the paper, we will also consider the case where a not ReLU but a general function and W E gd-1 In that case, we call the problem agnostic learning (spherical) generalized linear model (GLM) and for hypothesis a - .r), we use err(w) to denote its error accordingly. For a vector W in IR,, we use [|W|| to denote it &2 norm and use the lower case w to denote its direction W/ [[W]] For one-dimensional standard normal
N NO, 1) and 2 we denote by (() := (2 >> 1) and (t) the value of the density function of z at t. For a ReLU activation (2 t), we denote by ((t) == Ez-N(0,1) o² - t) its second moment and call p = o(t) its bias. For realevalued function f R > I. we denote by Il.ll == Es-N(0,1) f² its squared L2 norm in Gaussian space and for a E [0, 1]. denote by fz) == E f(az + vI-a2s)
Organization of the Paper In Section 2, we consider a special case of the problem where t* is given and the optimal vector W is restricted over Sd-1 We propose framework showing that a simple projected gradient-descent method converges to a desired solution for learning spherical GLMs, provided warm-start. As application, we give an efficient algorithm with optimal query complexity for ReLU regression when ||W'|,, tt" are given. In Section 3, we tackle the general ReLÚ regression problem, by discussing the technical difficulties and presenting key components of the problem, combining with the framework of Section 2. In Section 4, we establish our query complexity lower bounds. Due to space limitations, we defer several proofs the supplementary material.
2 Warm Up: Robustly Learning Spherical GLM
As a warm up, we consider the special setting where ||W*|| 1 and t" > are known. Prior works in the passive setting, such as [GV24, ZWDD25), reduce the problem to this case by guessing [I]W*I,, t²) brute force way. There are two motivations for studying such a setting. First, as we will discuss in Section 3, although such special case does not capture the main difficulty of obtaining query-optimal algorithms, it provides important technical components to achieve this goal. Second, when (I]W*I f²)) are known, the problem becomes a special case of agnostic learning of spherical GLMs, where a a general activation function and is known precisely to the learner. In this section, we start by analyzing the task of agnostic learning spherical GL.Ms in the passive learning setting. We presenting several technical tools that we develop to solve the ReLU regression problem in this special case with an optimal query complexity. Unlike prior works, such as [GV24], which designed complicated update rule for w (the current direction), we instead focus on the following simple projected gradient descent method:
w +- projge-1 (w - puproj,, Vuerr(w))
We summarize our main technical contribution in this section informally as follows.
Theorem 2.1. Let a: : + R be any activation function such that 110'1 L, <> O. Let D be any distribution over RRd x R such that D2 = (O, T) and crr(w") (("))=) S e, where w* gd-1 is direction that achieves the optimal loss. For a > 1, suppose we are given any unit vector wd E gd-1 such that [ 11 Z ||0'112/ /a, where Gg = 0(w,, w²). Starting from wo, the update rule (1) gives direction i with error (()²e).
Roughly speaking, we show that the update rule (1) has an initialization- error guarantee, which holds for even very complicated activation functions that are non-monotone. The quality of the initialization is measured by the ratio a := ||o'11// / I|T o "I22- As we will show later, for general ReLU activations, we are able to efficiently get w" with O(1), which implies solution
3

---

with error O(e) if we can implement (1) with high accuracy. Due to space limitations, we defer the technical details and proofs of this section to Appendix B. To analyze the error guarantee, we start with the following simple observation:
err(w)) (w) < E (or(w x) o(w" x))² + E (a(w" z) v)) = 2opt + E (a x) - o(w" z))²
at
So, the central part of the analysis relies on characterizing the noiseless enror of o(w x), l(w)
Eg~N((.)) (a(w x) - or (wo =x))² /2. Prior works usually analyzed f(w) via the angle ((w, w"). For example, for the problem of learning homogeneous halfspaces, f(w) 0 /r. However, in general, f(w) does not have such a simple closed-form. In the following lemma, we give an integral expression for ((w) over the unit sphere by drawing connection with the Omstein -uleenn-Uhheneekk semi-group.
Lemma 2.2 (Noiseless Error Estimation over the Sphere). Let R - R be any activation function such that a' E (0, I)) and let w E 5d-1 be any unit vector such that @ = Aww, w") ) < π 8/2 Then E(w) = S sin ||T /oo / ds S (m/2) 0 1
To relate Lemma 2.2 with the update rule (1), we use the following two structural lemmas that characterize the progress as well as the noise level during the update in each round.
Lemma 2.3. Let a: IR- + R be any activation function such that a' E (2 1)) and let w E g be any unil vector such that
0(w, w²) 7/2, where err(a )) = opt. Write w" -ww + bu, where u E Sd-1 u 1 w, a, b 2 0, a² + - = 1, then, proju- Vwl(w) = -b -b
Lemma 2.4. Leto : IR-- + R be any activation function such that o' E LO, I)) and let w E Sd-1 be any unit vector such that E gd-1 and u 1 w, ppro eVeerr(w) - V (w)) vl ve ||0'
0(w, w²) 7/2, where err(a(w")) opt S Then for any
The intuition here is that in each update round, if the length of the gradient ||T 11 is larger than the noise level /C ||a')l2-- then the projected gradient descent approach able to improve the angle between w and w². We summarize this as Lemma 2.5.
Lemma 2.5 (Angle Contraction). Let w", w(() E gd-1 such that w" = awll) + bu, where u E gd-1, u I. v0(() a, 2 0, a² + 12 = 1. Let 0, = =(w("),'' Let G E Rd be a random vector such that with probability 1, G I (6) Let be the mean of G and 9 E Rd_ Suppose there is some e > O such that g 2 cb/10, |lll| I cb, 11g Qll S bc/40, 40, then by setting p c/20, the update rule
w(i- = p + ng) satisfies sin S V1- (20)² 2 (2)/2))
However, the length of the signal sin 9 ||T o' ||2 in general is not an increasing function of 9. If Oo is not small enough, the noise level could be too high to make the gradient point in the correct direction, making it impossible to reach desirable error guarantee. On the other hand, by Lemma 2.2, if E(w) 2 l(a²c), Since (T ('oose go'll is decreasing in 0, this implies that, as long as we have good initialization, we can make progress and reach a good solution. We summarize this property as Lemma 2.6.
cc) then the noise level |proj (Vwwer((w) V (w)) v| is at most sin 6a: ||o'
Lemma 2.6. Let a R + R be any activation function such that a' E [,2(N(0, T))- Let a > and 0- < 0o 7/2 such thut [ /' 1|2 2 1|0'112 /// Let w E sd--1 be any unit vector such that 0- = 0(w, w²) < Oo. where err(a(w"))
opt S e. If'sin 2 0 1lo'112 2 20a2e/m,, then for any E gd-1 and v I w. |!rroj.' (V (rw(wr( - -V [(w)) < [|projw V.(((w)] /20. Furthermore, if |proj... eVrerr w) V (=((l)) > [[proj.. Vul(w)]] /20, then err(w) < O(a²e).
2.1 Application: Query Complexity of Agnostic Learning Spherical ReLU with Known Bias
As a direct application of the above framework, we show when w* E S and t* is given, how to solve the general ReLU regression problem with optimal query complexity. As discussed above, to ensure we get a solution with error O(e), we need some w with ||o'1l2/ |T 1112 O(1).
To characterize such a Og. we present the following structural lemma.
Lemma 2.7. Let a be an activation function funcctioo of the form (2) = Relu(= - 1*), where to > 0. If
sin 0/2 < 1/t", then ||T Joos go" |1 2 ||o'112// /50.

---

This implies that 8, = ((1/t)) is sufficient for us to reach some w with O(e) error. But to obtain such a w0) is also a challenging problem. Our initialization is motivated by the following lemma.
Lemma 2.8. Let a be an activation the form ((2) = Relu(z - ))", where t > O. Let y(x) be any labeling function such that opt I E. Let 0 be suitably small constant. V+*) > Ce,, for some large constant C, then Pr (7(x:) F sign( (w" x - t²)) S /(C) for some large constant C² > O, where ū(x) := 1 [u(x) > cf(()))
That is to say, as long as t" is not too large to make / = 0 have error O(e), the truncated label 8(x) := 1 {v(x) > c/t") } can be seen as a labeling generated by the halfspace h(x)) = sign( (w* -x:--------- -x- corrupted with 17lleel adversarial label noise, such that 1/ /t(*)) < 1/CC for some sufficiently large constant C. Such an observation is useful, as it allows us to make use of the recent technique developed in [DKM24] to obtain the warm-stan start using only Ó(L/p + d) queries.
Lemma 2.9. [Halfspace Initialization via Queries (Theorem 3.8. Theorem F.1 [DKM24])] Let h (x) sign(w" xz -t),,, where to < O( ([Voog(//e) and y(x) : _ - =1 be any fabeling,uunction function such that Pro=)((.1) (h (x) + y(z)) I o(t")/(' for some large enough constant C². There is an algorithm such that given some E with It -t1 S 1/log(L/e), it makes M ((1/((t) +
d (lo{(L/e) queries, runs in poly (d, M) time, and with probability at least 1/ //////////////// outputs
some (0) such that sin(!(w!") w²) w²)/2) S min 1/2].
However, obtaining such a (0) is not enough for us to solve the problem with a small label complexity for the following reason: Lemma 2.6 does not bound the number of iterations and the number of labeled examples needed to reach a good solution. Specifically, by Lemma 2.5, the progress made in each round is characterized by the length of the signal g u. g u R c csin 0, then the angle decreases by factor of (1 c) in each round. If t" O, prior works have shown that labeled examples are enough to get a good estimation of g. The landscape changes dramatically when t" becomes large. As indicated by Lemma 2.3, for large 1",, the length of the gradient is a most ||a'|1 which can be as small as poly(c). This implies that, unless we estimate the gradient to very high accuracy and rescale the gradient to a constant length, the progress made in each round is too small. Unfortunately, as the variance of the gradient is much larger than the accuracy we need, this blows up the total query complexity. To overcome this difficulty, we show that for the problem of ReLU regression, the initialization guarantee 0g- S O(1/t*) not only lets us make progress in each round, but it also allows us to use queries to boost the length of the gradient while maintain small variance. Intuitively, every time we estimate the gradient, examples with wn x >> t' contribute most of the gradient. When our current (i( is close to w", the regions (ar (+()) x > )²) and {ar w= x > }*} have significant intersection. Thus, we can boost the length of the gradient by querying examples in {o ((() x > }²}. Furthermore, due to the Lipschitz continuity of Relu, we can maintain small variance for the gradient; and thus (dd examples suffice for us to accurately estimate the gradient.
(2(1) and Ö(d)
Lemma 2.10. Let a=z) = Relu(z - (*), with 1x > O. Let u(x) be any labeling function such that opt S e. Let w E sd-1 be any vector such that sin(0/2) Σ 1/t". Denote by G E Idd the random vector (a(w -x--- t*) ow x -x- t*)) proj and G the random vec- tor (a(w- -t) -v(z)) proje I, where ((, 1) ||//!>>>11 Then the following holds: (1)
EG = 6 b1T oo (t)) (2) [EG* - EG) el S Vello'Il, / (3) If sin? (+0(t)) > e, then EGG < O(P), VrE
The structural results we obtained so far are almost all we need to get query-optimal algorithm for the spherical case. We refer the reader to Appendix B for the detailed proof. A remaining caveat is that the initialization algorithm for halfspace learning used in [DKM24] only succeeds with 1/ /loo((/c) probability in the worst case. This implies that to succeed with a good probability, list of poly log(1/e)
need to run the same algorithm poly log(1 (1/c) times, which will give candidate hypotheses. The usual way to find a desired hypothesis from the list is to check their empirical errors via labeled examples. However, this approach will take ((1/e²) labeled examples, blowing up the query complexity we have achieved so far. To avoid this, we design a new active testing procedure that only takes poly log(1/4 /c) queries and selects hypothesis with error Oe)). Our procedure not only works for selecting ReI.U activations, but also applies for much general settings.
Lemma 2.11 (Hypothesis Selection with Queries). Let D be a distribution over I&d x R and let D2 be the marginal distribution of D.,. There is an algorithm that, input list of hypotheses
5

---

hi.....hh such that for i E [k], h3s R + R, E (x) exists, it makes poly(k) queries and returns hypothesis h such that crr(h)= I (minnee()) ((xa)~D(y h,())))
The intuition of our hypothesis selection algorithm is as follows. To simplify the intuition, we assume || ll = || For each pair (i.j), we would like to check whether lly - hall2 S lly 1lyy// 1ly--yll 1 which is equivalent to checking the sign of the correlation Ely((,(xx)) -x)(x))] Naively, this can be done by randomly querying x ~ Dz; but since the variance of y(h((z) - (x)) can be very large, this can blow up the query complexity of the algorithm. Instead, we reweight D2 according to (h,(x) - (1))² and use j((x)) x (/( h2 (x))² as our query value. Such a modification keeps the mean we interested in, but reduces its variance, allowing us use ((1) queries to solve the task. We defer details of the hypothesis selection algorithm to Appendix B.9.
3 Ag ggnottic Learning an Arbitrary ReLU with Optimal Query Complexity
To handle the general case, where || || and t"' are unknown, we need to overcome several conceptual and technical difficulties. Prior works in the passive setting solve the general version of the problem by reducing it to the spherical case, by guessing ||W*| and t" up to poly(e/ ( R) additive error, running the same algorithm poly(R/C times and doing a hypothesis testing. Unfortunately, this simple approach is prohibitive in our context because completely ruins the query complexity (even though we are able to solve the spherical setting with optimal query complexity). To achieve an optimal query complexity for the general problem, there are two main obstacles overcome.
The first one is to find the correct way to update parameters.
the case where 1" S 0, prior works avoid guessing [I*|| by replacing the update rule (1) by standard gradient descent W <- W werr (W), and showing that when ||W - W is large enough to make the noiseless error larger than (e)). Vwerr(W)) (W - W') 2 MII - w=1 ); this leads to a constant factor of decay in || |I. However, when there is large threshold, I|W WI|| is not the correct quantity that characterizes the noiseless error. Consider the optimal hypothesis ht = oww I (*)) and two other hypotheses h1 a(v- 1--0------ --) ) h2 = (t { + 1w x t²). where & >> 0 and sin ((v, w*) = &. When t* is large, the parameter distance of h2 is much larger than that of hy; however, it can be checked that the two functions have the same noiseless error, and thus adding the same level of noise can make the two functions indistinguishabl.. The implication of this phenomenon is that even if the parameter distance | || is large, we are not able to guarantee the noise rate is small enough to make the fast decay happen.
The second obstacle is how to implement the correct update with a small query complexity. In the spherical setting, we make use of the fact that (w . t*) y(z) is small for most queries x to make the variance of the gradient as small as sin? 0, (which matches the length of the gradient). The small variance is the key that makes Ö(d) queries sufficient to improve w!), However, since r", (" are not part of the input, an inaccurate learned parameter (r-(0) f(0)) could make h(x)) - v(x) very large, making it impossible to estimate the gradient accurately with few queries. So, when we do the parameter update, the statistics we rely must have small variance throughout the learning process.
We will require the following notation. For r > O, w sd-1, f > 0, we define hypothesis (r,, w,t) = (rw x - t). In particular, we write the optimal hypothesis as h² = "rr'"" z - -.)). We denote by == t/r the normalized threshold of a ReLU and define the noiseless error of h(r, w. t) as ((r, t.t) = 1/2 Er-N(O.1)) (a( x - t) - o(r"w" x
-=))) Our main algorithmic result is an efficient learning algorithm with optimal query complexity. Due to space limitations, we defer some technical details and proofs from this section to Appendix C.
Theorem 3.1. Consider the problem of agnostic general ReLU regression with queries under the Gaussian distribution. There is an algorithm such that for every labeling function y(z) for every 6 E (0, 1), it makes M = Oğ (minç1/p. R2 /c] + d polylog (R²/c) /c)) queries, runs in poly (d, M) time, where p = ((*) is the bias of the optimal activation function, and outputs an h such that with high probability at least 1 - 8. err(A) < O(opt) c
We remark that the dependence on R²2 is due to the natural of rescaling of the error parameter. Similar to the spherical setting, we still need a warm start in order to converge to a good solution. To maintain truncated label to implement Lemma 2.9, some information about (r", (") is needed. Here, we will grid r E [0, R] and i E j0, (Tooo /R))))), the normalized threshold, to get the initial information. However, instead of using grid of size poly(R/e) we maintain grid of

---

size poly log(R/c)) R/c), exponentially smaller than the grid-size used in all prior works. In particular, for parameter t, we will set {(t) = (i - httpolylog(R////// (R/e), i = l...., (p Rfe)), while for parameter r, we build a two-level non-uniform grid as follows. The first level of the grid is defined as r; = 2.-1c.i = =.....,ooo R² /c) For each interval [r2, ri we grid it uniformly into riy = r + (j - http:/ooooog//).....
1, I..... polylog(R/e) Such grid can ensure that one of the grid points (r, t) satisfies r S r* S 2r and It- 21 polylog(R/e) We show in Lemma 3.2 that such pair rf) suffices for us to get an initial direction (0))) as a warm start.
Lemma 3.2 (Initialization with Raw Knowledge). Let r" ". be the optimal hypothesis. Assuming that (t*)) 2 [((),, there is an algorithm such that given parameters r, > 0 with r S r* I 2r and |t- - 0 I 1/log(P) R2² fe), it makes M = ((1pp + d dllog( R²² /e)) queries, runs in poly(d, M) time, and with probability at least 1/ log(1/p) outputs some wll) E Sd-1 such that sin (((((w))) "=w""") w/2)) S min(1/0", 1/23.
Although the first-level grid r; is enough for us to get warm start w(O) for technical reasons, to obtain an algorithm with an optimal query complexity, it turns out that we need better knowledge about r*. This is the reason why we use two-level partition. In the rest of the proof, we assume that we have (ro, w((), to) such that (ro- r"1 S r* r /polyllo R22 /e), sin(6)/2) - 1/2" and 1 8*1 < polylog( (aayloo(((//e),)))) We next provide overview of our algorithm based on this warm start (Tu, w((), to). As we mentioned earlier, since IW - | is not the correct measure for the noiseless error, the noise rate could be large even if W W+ is large. To overcome this issue, in each round of the algorithm, we modify the standard gradient descent by decomposing the update into two directions; along direction (f and orthogonal to w(()) In other words, we use different statistics to update (r..t)) and (+() separately in a careful way. The motivation for using such a strategy due to the following noiseless error decomposition, Lemma 3.3, which implies that the noiseless error can be decomposed into two terms that are independent of each other. Importantly, as long as one of the two terms is suboptimal, we are able to improve it despite the noise from the other direction.
Lemma 3.3. Let r
0 E
g6-1,t t
0. Then [(r; w,t)
S
(r*)2 1o sin 8 l'T.a - 10 ds Ez-N(0.1)
(o(rz- t) - orr==-
Furthermore, the errors from (ra, fx), (+)) can be entangled with each other, which makes the analysis subtle. particular, the error from one term can make the statistics we use for updating the other terms have a large variance, which could blow-up the query complexity we need. The second motivation of such a strategy is that provides clean way to analyze the error entanglement between the two terms. We list the algorithm below Algorithm I and describe the update methods we use. We defer the details of analysis to Appendix C.3.
Angle Update: Similar to the spherical setting, we construct the gradient by boosting proj..- (werr(w) via a rejection sampling approach. Given a ReLU activation, A(r,, w(f,, tt), define random vectors G; := (h(r,, w0(), t+)(z) - h (x)) proj (x) and its noisy version G = (M(ri, (f(r,, (z)()) v(x) proj (z), where N(O, I) lui0.
To begin with, we present the following lemma that quantifies G,.
Lemma 3.4. Let h(r, w(()t,))) Write w" = awls) + bu, where a.b > 0,a² + b² 1, E gd-1, u 1 w(() Then the following holds: (1) If l4, F- s A/log(()) R22 /c) and < 1/f
then EG; = -abr" I[ - -+))l (t,),, where 1/2 < a < 2. (2) (EG - EG) ul S
Vello'(z - t,)lla (b, Yo E Sd w())
Lemma 3.4 implics that the error from (Ta,t4) does not affect the direction of the update E G. Combining Lemma 2.2 and Lemma 2.7, it follows that as long as 0; is large and contributes Q(E) to the noiseless error, the gradient G, we construct can improve the angle. However, this does not imply that E G can be estimated with only few queries. To that end, use the following lemma that quantifies the variance of G..
Lemma 3.5. Let h(r,, t0(t) t.) be ReLU activation. Write w- -a(()) + bu, where a, > 0, 12 = 1, E gd-1, u L ml)) If - 1-| < l/oog((R)))) Ce/((r") S 12 < 1/1. then E(G. v) < Ô (E.-No.) (a(r2= (4) - -))=4)==))===0--00000)---)--))-- 13)² /T()) + (rt)2(2)
Unlike the spherical setting, the variance of G; depends on the accuracy of (r,, 4).. In particular, by Lemma 3.3, the contribution to the variance from (ra, is proportional to its contribution to
7

---

Algorithm QUERYLEAARNING(L.C. optimal ReLU with a warm start)
1: Input: w(() E gd-1 unit vector such that 0g I 1/polylog( R2 R2/c)- ro > such that
|r" -ro- S /r" /polyloy R2 /c), to lio 1*1 S pooyyoog(2)))) (c))).
2: Output: h : RR + R. such that err(h) I Oc)) with non-trivial probability.
3: Bn == r6/ :=10/ (1o/polylg((R2
4: i
do
5: Generate polylog(R /c) samples x(6) N(O, (wll) xx > 4.). Query y(x(,)) and use them to get an estimate 9; for (E UU EU,,EFF FF,)
6:
if |لx1|| (1polylog(It*/e then
7:
Set (rio, 40) = (ri, ()) and update (ray,4s) (rag-1), 1)-4)))))) (os))/polyog(((/// until |لر,ةا| - B.polylog(HP'
8:
(rit1, 1-) (riy (ty) for j = I,.... ((d) do
9:
10:
Generate x00ر NO, 1) (w(++1) x > 4++1 and query y(a())
11:
Estimate E G. via median of mean and get G;
w(++1) = projga-1 (w)))) pCi))
12:
Bi+1 (1-p)B,
14: á = (T)
15: Build unit grid of size 1/ (/poyloo([e/// over the ball centered (rr,lr) and randomly select pair (f, I) from the grid.
16: return h(f,, dē f)
the noiseless error. When (ri, 4)) contributes more noiseless error than w(), w(() might be updated incorrectly due to the estimation error.
To overcome this difficulty, we make use of potential analysis by maintaining suitably small upper bound for (r*)² sin? 0, and reduce the upper bound in each round of our algorithm by considering the update (é+1) projge-1 (w(++1) μGt) for some suitably small μ4, where G is an estimation for EG, with (d) queries. We will show that long as the error from (rx, t,) is within a polylog (R² /e) factor of B, dpolylog( R2/ /e) queries are enough to estimate E G2 and decrease the angle 0,. So, the key to obatin the correct query complexity is to update (r),,t) correctly, that it introduces small error throughout the implementation of Algorithm 1.
(r, t) Update We will next describe the way we update tr. To begin with, we briefly explain the technical difficulty that needs to be handled. To simplify the intuition, we consider a simple one-dimensional setting where the optimal hypothesis is r of= t²), and want to learn (r",t"). An immediate observation is that if we know to good high accuracy, then applying a binary search over via querying examples with > 1", we can learn r* efficiently. However, learning t" with few queries with an inaccurate learned parameter r is challenging, because even estimating the bias of the target ReLU needs many samples. In halfspace learning, [DKM24] overcomes the difficulty by querying examples for which |z fl < B < 1. Such a method can zoom the error from (f - {*) and (?-i)), /) B, which allows us make binary search find 7 with very few queries. Unfortunately, this method is not robust to label noise in la loss. Intuitively, queries are more sensitive when the labels are real-valued instead of binary. For the l2 loss, the noise rate could be very high within any small region, making this approach fail.
To bypass this difficulty, for given ReLU activation h(r, (+)) tx), we consider the following two quantities: U. (h(r,, w((), t.) h² h=)(w(()) F). == -(h(r,, w(() t.) ). and their noisy version U,, F;. Here we consider ~ (0, I) (w > f.). Intuitively, if (r,,t, are close to (r",t"), the task for optimizing them can be approximately seen as optimizing the following quadratie function t(r, = Ez-,N(o.1) ((re - t) (r* )+)) 1(2 E*). Such a quantity nearly characterizes the contribution of (r., f:) to the noiseless error as well as the contribution of (ri, 4:) to the variance of the gradient we use for updating (0) Furthermore, if 0; has already been updated in reasonable range, then (E U., E F.) is very close to the gradient of Z(r;, 4)). This gives the intuition to estimate (E U., E F)) and run standard gradient descent update to improve (ri, f.). To formalize
8

---

this intuition, we need to overcome two technical challenges. First, unlike the angle update, where the error from (ri, fa) does not affect the update direction E G the mismatch of w(t), w" does affect E EU;, E F.,, even if we ignore the noise and estimation error. This is because the mismatch between w(() and w= also contributes to Us, F,, which could vanish or even reverse the gradient for updating (Tr, t,). We defer the quantitative evaluation for the noise level and variance for U, F; to Appendix C. Fortunately, such forms of eπror are only O(r" sin 0z), which means that as long as w()) is updated to a reasonable range, we are safe to update (ri, 4i). So, we will simultaneously maintain w(() within a reasonable region and only update (ra, 42), when the angle is within reasonable accuracy. The second technique issue is because when the true threshold is large, (r, is an ill-conditioned function. Due to the presence of noise, the ill-condition of (r, t) implies that even if w!') has already been updated
desirable accuracy, the gradient descent update can only guarantee that (rr, (r) is Occpolylog( R², /c/ (f())) close to (r", (t", in terms of squared norm. Fortunately, there are only two parameters we need to worry about and they are already very close to (r",t") randomly
selecting a pair of parameters from their neighborhoods gives us a good hypothesis with enough probability.
Label Complexity Lower Bounds And the Necessity of Using Queries
Here we present our label complexity lower bounds. We defer the detailed proofs in this section to Appendix D. We start with an information-
lower bound in the query setting.
Theorem 4.1 (Query Complexity Lower Bound). Consider the problem of agnostic ReLU regression with queries with a restriction that the optimal ReLU satisfies ||*|| S 1 and has bias least p. Any learning algorithm that outputs a hypothesis with error less than Opp log" (p)( with probability 1 1/3, must make at least 50(1/p'=00 (=o(()) + d) queries. Furthermore, this holds even if opt < 2- 2-2 p.
The proof of Theorem 4.1 can be broken down into two parts. We first consider the lower bound of (d). Such a lower bound even holds for an easier problem, which is the standard linear regression problem in the realizable setting. Suppose that we have made r queries x ..... x(()).... so far, and denote by I. the subspace spanned by them. Consider a Bayesian setting, where w" ~ gd-1. Suppose we know w then for new example x, by symmetry, no hypothesis will have better error than the hypothesis wž= x. In particular, if ( I), this implies that no hypothesis has error better than - || 1/- For any possible subspace L. with dimension r, in expectation [lprojy w= 11 = r r/d, which implies that unless ((d)) queries are made, algorithm must incur 22(1) error. On the other hand, consider a hypothesis ow=" x 2--t) t*) with bias We want to tell whether the hypothesis is O or not. Notice that in the realizable setting, if we make query x and find y(z) = then by making another query in the opposite direction (but very far) we can easily verify whether h = O. However, with only a tiny fraction of adversarial label noise, we can corrupt all examples far from to have 0 label. Now if w" gd-1, then only examples in small cap with volume p²-o(2) have non-zero label; thus, unless 1/p² 1/() queries are made, we are not able to solve the distinguishing problem.
Our next lower bound shows that no pool-based active learner can achieve the query complexity of our query learner, even in the realizable setting.
Theorem 4.2 (Label Complexity Lower Bound, Active Learning). Consider the problem of realizable bast- active ReLU regression with a restriction that the optimal ReLU has bias p. Any active learning algorithm A that makes less than Ö(d/ (p log(m))) label queries over S. set of m i.i.d. points drawn from N (0, 1), will with probability at least 2/3 output a hypothesis h with error Mpp).
While a number of prior works [Das04, HY15, KMT24b, DKM24] established query complexity lower bounds for active classification problems, few techniques could be directly applied to the regression setting. An immediate obstacle is that the behavior of an adaptive algorithm can be much more complicated when the label is changed from binary continuous. An observation, inspired by prior works for proving label complexity lower bounds for learning Salfspaces[Das04, DKM224), that given a pool of m unlabeled examples, learning a hypothesis with queries is not harder than using queries to find d examples with non-zero labels. So we will focus on the hardness of this easier problem. By Yao's minimax principle, we consider a deterministic algorithm that solves the problem, while w² ~ gd-1 for large enough d. Suppose that deterministic algorithm wants to use queries to find examples with non-zero labels from a pool of m unlabeled examples drawn from (O, 7). Given set of m unlabeled examples, and any fixed w", the behavior of A can be uniquely described
9

---

as a path P successfully finds & examples with non-zero responses, then there exist & indices 81...... dy at which the responses are y² ..... y²x > O. Since there are (?) such tuples, to argue that the algorithm has a large probability of failure, it suffices to argue that for a fixed tuple the probability of realization is very small. Proving such statement turns out to be challenging, due to the rich behavior of the algorithm. In the binary classification setting, for each fixed tuple, the corresponding unlabeled 1). That is, to prove a lower bound for classification problem, we only need to argue that the probability these examples are all positive is small. Such a whether the previous
((x',y'), y....... ........... .²)) according to its responses. In particular, if the algorithm
examples (zt ..... x²') are unique, since y E {0.1).
strategy does not work for regression,
the next example not only depends example is positive, but also depends on the full value of y. This results in many possible realizations of ((x"1, y (x**, yy*)) ,y*,,"* )). So we need to bound the integral of their density function over all
possible outcomes. Consider a realization of the event ((x'), y"),, "....,.. (x**, yy*h )), with y's > O. Such realization completely characterizes vector WT T., where T. ís the subspace spanned by
these & queries. One observation is that if we change the basis of L by defining bJ = 2(11) / [|a()))]]]
and by- projr., ,a(ts)/ / proir.. ,2((1) ||. where -,-1 = span (zz(11), (1) 1)), then wr can be v v(w))=
bb). Importantly, the value of the density function of the event is exactly the density of the event that the first & coordinates of a random unit random vector equal to v(wz). On the other hand, due to the tree- stresstructure of the algorithm, given any possible d ((WL), we can decode it to reconstruct the corresponding ((#" yy.).................. 1r'*,8") Denote by Sw the set of all possible v(w)). This means the probability we interested in is exactly equal to the probability that projr., (w*) E S. where Lo is the span of the first & standard basis vectors. To derive an upper bound for this probability, it is sufficient to find superset of S.c. Our observation is that if z²' ,..., x are orthogonal, then | 2 > k(t*)2, which also implies that [[ [o((w))ll )|1" 2 k.( Furthermore, as long as m not as large as 20(d), for A chosen to be slightly
described as a k-dimensional vector
(wy 61, ......, Wt.
smaller than d, every k-tuple of examples from the pool are nearly orthogonal. This implies that the norm of v(wz) can be lower bounded uniformly, which suffices to bound above the target probability
by OOp l Since there are most (x) tuples we care about and & slightly smaller than a carefully chosen concludes the proof.
Acknowledgement
Ilias Diakonikolas was supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER),. Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant. Daniel M. Kane was supported by NSF Medium Award CCF-2107547 and NSF Award CCF-1553288 (CAREER). Mingehen Ma was supported by NSF Award CCF-2144298
References
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6))1-27, 2017.
[ATV22] Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. Agnostic learning of general relu activation using gradient descent. arXiv preprint arXiv:2208.02711 2022.
[BBZ07] Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International Conference on Computational Learning Theory, pages 35-50. Springer, 2007.
[BL13] Maria-Florin Balcan and Phil Long, Active and passive learning of linear separators under log- concave distributions. In Conference on Learning Theory, pages 288-33 316. PMLR, 2013.
[Das04] Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.
[DG03] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60-65 2003.
10

---

[DGK*200 Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. Conference on Learning Theory, pages 1452-1485, PMLR, 2020.
[DKM05] Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron- based active learning. In Learning Theory: 18th Annual Conference on Learning Theory, COLT 2005, Berlinoro, Italy, June 27-30, 2005. Proceedings 18, pages 249-263. Springer, 2005.
[DKM24] Ilias Diakonikolas, Daniel Kane, and Mingchen Ma. Active learning of general halfs- paces: Label queries vs membership queries. Advances in Neural Information Process- ing Systems, 17:49980-49911. 2024.
[DKMR22] Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. Hardness of learning single neuron with adversarial label noise. In International Conference Artificial Intelligence and Statistics, pages 8199-8213. PMLR, 2022.
[DKR23] Diakonikolas, D. M. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. CoRR, abs/2302.06511 2023.
[DKTZ22a] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning single neuron with adversarial label noise via gradient descent. In Conference learning theory, pages 4313-4361. PMLR, 2022.
[DKTZ22b] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning gen- eral halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning, pages 51 1811114. PMLR, 2022.
[DK220] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 33: 1 13586-13596 2020.
[DMRT24] Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, and Christos Tzamos. Fast co-training under weak dependence via stream-based active learning. In Forty-first International Conference on Machine Learning, 2024.
(FCG20) Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in neural information processing systems, 33:5417-5428, 2020.
[GTX+24] Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco, and Yi Li. Agnostic active learning of single index models with linear sample complexity. In The Thirty Seventh Annual Conference on Learning Theory, pages 1715-1754, PMLR, 2024.
[GV24] Anxin Guo and Aravindan Vijayaraghavan. Agnostic learning of arbitrary relu activation under gaussian marginals. arXiv preprint 24t.:2491..1444, 2024.
[HY15] Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1):3487-3600 2015.
[KSKII] S. Kakade, 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.
[KMT24a] Vasilis Kontonis, Mingchen Ma, and Christos Tzamos. Active classification with few queries under misspecification. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[KMT24b] Vasilis Kontonis, Mingchen Ma, and Christos Tzamos. Active learning with simple questions. In The Thirly Seventh Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pages 3064-3098. PMLR, 2024.

---

[KMT24c] Vasilis Kontonis, Mingchen Ma, and Christos Tzamos. The gain from ordering in online learning. Advances Neural Information Processing Systems, 36, 2024.
[LT25] Yi Li and Wai Ming Tai. Near-optimal active regression of single-index models. The Thirteenth International Conference Learning Representations, 2025.
[O'D14] Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
[She21] Jie Shen. On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In International Conference on Machine Learning, pages 9503- 9514. PMLR, 2021.
[VYS21] Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning a single neuron with bias using gradient descent. Advances in Neural Information Processing Systems, 34:28690-28700 2021.
[WZDD23] Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning single neuron via sharpness. In International conference machine learning, pages 36541-36577. PMLR, 2023.
[YZ17] Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.
[WDD255] Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning monotone generalized linear models via data augmentation. arXiv preprint arXiv:2502.08611 2025.
12

---

Supplementary Material
Structure of Supplementary Material The supplementary material is organized as follows. In Appendix A, we record the notation and mathematical background required for our technical sections. In Appendix B, we present omitted details from Section 2. In Appendix C, we provide a full version of Section 3, including a detailed discussion on the update rule for w and (r; (), missing technical lemmas and proofs. and the proof of Theorem 3.1. Finally, in Appendix D, we give the detailed proofs of our lower bound results from Section 4.
A Preliminaries and Related Background
A.1 Problem Definitions and Notation
We first define the task of Agnostic Learning with queries and the corresponding task in the active learning setting.
Definition A.1 (Agnostic ReLU Regression with Queries). Let d(2) max be the ReLU function. A labeling function y(z) : B" - R is random function that maps each E Rd to unknown real-valued random variable. For each h Rd + R, denote by err(h) E2.,(0.1) (((x)-y(x)) /2, opt: == |s5 err(a wZW -)) and o" (x) o(W* x 13) be any ReLU with error opt. A query takes E Rd as an input and returns label ~ y(1). We say that a learning algorithm A is a constant-fuctor approximate learner of every labeling function y(z), and for every c, 6 E (0, 1), it outputs some hypothesis h Rd - R by adaptively making queries, such that with probability at least 1- 6, err(h) S ((pt)) + The query complexity of A is the total number of queries it uses during the learning process.
Definition A.2 (Pool- -asee Active Learning for Agnostic ReLU Regression). Let a - R be known activation function and w² E Sd-1 be unit vector. Let D be distribution over RRd x {+1} such that Dz, the marginal distribution over x, is the standard Gaussian distribution (0, 1). For
each h. IRd - RR denote by crr(h) = Ei (h(x) y)² /2, opt == min will crr(o(w x)) t*) ) be any ReLU with error opt. Let S be a set of m i.i.d. labeled examples drawn from D. An active learning algorithm (with label query access) is given S but with hidden labels and is allowed to make a label query for each x E S and observe its label y(z). We say that learning algorithu A is a constant-factor approximate learner if for every distribution D and for every c,6 (0, 1), it outputs some h H by adaptively making label queries over a of m examples drawn i.i.d. from D, such that with probability at least 1 - 6, err(h) S O(opt) + e. The label complexity of A is the total number label queries made over S during the learning process.
and o² (x) = o (W" I -x-tt -x-+")
We will without loss of generality assume opt S e, since the final error guarantee is Ooppt + +). We remark that in some parts of the paper, we will also consider the case where a is not a ReLU but a general function and W* E Sd-1, In that case, we call the problem agnostic learning (spherical) generalized linear model (GLM) and for hypothesis a (ww z), we use err(w) to denote its error accordingly. For a vector W in Rd, we use ||W]| to denote it &g norm and use the lower case w to denote its direction W/ [|] For a one-dimensional standard random variable 2 ~ N(0 1) and t. 2 O, we denote by (() == (r >> 1) and (t) the value of the density function of = at L. For ReL.U activation (= - f), we denote by (I)) == Ez=,((.11) a² t) its second moment and call p its bias. For real valued function ʃ IR + R, we denote by ||/ == E (=) its squared
L2 norm in Gaussian space and for a E [0, 1). denote by (2) := E.-N(O.)) f(az + v1 d²s).
A.2 Background on Ornstein Semigroup
Here provide basic background on the [O'D14] for additional background.
Semigroup. We refer the readers to
Definition A.3 -Ornstein-Uhlenbeckk Semigroup). Let p E (0. 1). The Ornstinn-Ulenneen semi- group T L2 > La is linear mapping that maps a function f to a function T defined as
Tzf(2)= = E f(pz + vI p2s).
s.N(0.11)
13

---

Definition A.4 (Omstein-Uhlenbed) Uhlenbeck Operator). The Trmstein-Uhlenbee operator L L2 - L2 is linear mapping that maps a function a function Lf defined as
Lf(z) = dT dp
1==1(2) (z)
We list several facts about the Ornstein-Uhlenbee semigroup and Omstein-UUllnbbed operator. Fact A.5 ([O'D14)). Let f,9 L2(N). The follows statements hold.
1. For [0, 1}. ||T is non-decreasing function with respect to p.
For aob E [0,1], EzeN(,,) (aeNoo.))a,((azz.ff ( (
3. If f is difierentiae function, then for E (0, (Taf(=))' pT (z).
d7, = pf
dp
E E (f(=)LT,g(2)) E (f())((T=()))))
A.3 Background on Gaussian Integral
In this section, provide background Gaussian Integral. Let NN0 be the standard normal random variable. For t 2 0, we denote by ((t) == (r.(= > t) and (f()) the value of the density function of For ReLU activation o(= t), denote by (tt) = Ez~N(0.1) o² t) its second moment. We provide detailed characterization for o(t), (t),, V(t). First, provide the following fact that characterizes (t)).
Fact A.6 (Komatsu's Inequality). For any 2 0, (tt) can be bounded as
2 exp((
2 exp(-(1/2
n P < +(1) S a 1 +2
Next, we provide the following fact calculated by [GV24] that relates V(I,, 2(1), (b)). Fact A.7 (see, e.g., Appendix A, [GV24]). For any 2 0, the following fact holds.
E =1 1) = vi(1)
z~1(0.1)
E
2(2--)1((2 = (tt)
N
>11(2> t) *(() tt)(t) (1+ (1)) N~.10
E
V(t) (t + 1) te(()) (2+ (z))
For large > it is useful to mention the following asymptotic relation between (tt) and (t),,
(1) 1
3
(t) t 3 4
The following useful Stein's 's lemma will also be frequently used in our proofs. Fact A.8 (Stein's 's Lemma). Let N(u, o2, be a Gaussian vector in Rd Let g : Rd - IR such that Em..N g(z)æ and Ez-N(u.021) gg(z) exist. Then the following fact holds
E
g(x)(xx 11) x(N(11111
E
Vg(x).
Np..ar)
B Omitted Details from Section 2
Here provide the full details omitted from Section 2.
14

---

B.1 Proof of Lemma 2.2
We provide the proof of Lemma 2.2 and its restatement Lemma B.1.
Lemma B.1 (Restatement of Lemma 2.2). Let R IR be any activation function such that o' (N) and let w E gd-1 be any unit vector such that = 0(w, w²) < 7/2, then
[(w) = L/ 0
sin 8 Joos
Voons o'1 ds -
π sin 0 110'112
2
Proof of Lemma 2.2. We write w² = aw + bu, where a, b b>0000.0 2 = and E Sd-1 Notice that if x N (0, I), then w x and u x are independent standard one dimensional normal random variables.
_,,,,,, 1 w.
1
((w) 2 (u.((
E (a(w- a(w" (())=)))²== =~N(U,1)
E
(
E x~N(0,11)
a(w x)o(w* - x)
(2(2)-
o(w 1o)oowo . x + xx)
N0,1)
(0.1
(²(2)
a(2)o(az + bs) = E
(0)) - TT)(2))
z~N(0.1)
(0.1)
dl,o((z) ds
[[ (TToo())ds= [(
1
1
E d(2)
ds
E ((2)
E
a(z) LT, (z)ds
z~N(0.1)
z~011111
z~N(0,1)
(2)
d'()) 1 (Tao)())) S( z~N(0.1)
E d'()),oo'())d
(3)
N0.1) 8
11 ds
sin ( Jons o0 ds.
Here, (2) follows Item and (3) holds because of Item and Item 5. The last equation follows
change of variable. By the monotone property of ||T, and 0 S a/2 sin @ for 0 E (0, 2/2), we obtain that
[ S π sin" 0 1 ((w)= = //" sin o
2
B.2 Proof of Lemma 2.3
Here we provide the proof of Lemma 2.3 and its restatement Lemma B.2. Lemma B.2. Let + ER be any activation function such that of L2 (N (0, I)) and let E Sd-1 be any unit vector such that = 0(w, w²) < 7/2, where (rr(a(w") )) = opt. Write w" = aw + bu, where u Sd-1 1 w, a, 0, 6² 1, then, proj vw((ww) b ||T /
Proof of Lemma 2.3. By Fact A.5 and Fact A.8, we have the following calculation
proj. [w((w) = proj
(a(w- x) - ow - x)) (w x)x
*~N((,
= -proj
aw x:)o' x)x proj E
ow - x)o'(w-w)))
(0,))
N
-proj
E aww" x)o'(w x)x -projw+
E V. (a (z)
N(.J)
N~N(0,1)
=-projpet
E
(o'(w" x)00 (w x)w" + o(w" x) x))" r)w)
N
E
d'(w" 200 (w x r)bu = 2.00((0.11
d' + (z)bbu
(0,(
E
(2) -b u.
2~N(0.1)
15

---

B.3 Proof of Lemma 2.4
We next give the proof for Lemma 2.4 and its restatement as Lemma B.3.
Lemma B.3. Let a R + R be any activation function functionn such that o' E (o, 1)) and let w E S be any unit vector such that ((1,, u²) π //22, where err(a(w")) opt S Then for any E gd-1 and u L [pro eVrerr( [w((w)) v ve ||''122-
Proof of Lemma 2.4. We notice that
proju= (V wer((w)) - V vwl(ww) = projut
(a(w" x) - y) d'w x)a. N(0.)
E
For every u E gd-1 and v 1 1o, we have
pproj (Vwerr(w) V Vool(w)) w/
E (a(w" .x) v) o' (x xx)xx
N(0,1)
S
E (o,)
(a(w" x) - y)²
E
(o'(w -
z~N((,1)
opl
E N.3
(o'(z)8)² S Ve 10'12
Here, in the first inequality, we use Holder's inequality and in the last inequality, we use the fact that 2, 8 are independent.
B.4 Proof of Lemma 2.5
We next give the proof of the angle contraction lemma as follows.
Lemma B.4 (Angle Contraction). Let w" w(() g such that w= aw + bu, where u 8d-1, u L. w(t) a, b 2 0, a² + 12 = 1. Let 0: = 0ww(1) w²)) Lei G E Rd be random vector such that with probability 1, G 1. (1) Let be the mean of G and E Rd. Suppose there is some e > O bc/40, 40, then by setting P = c/20, the update rule ((--)) (w + μف) satisfies sin(0.+1/2) S / 2 sin(0./2).
such that g u 2 cb/10, |igl| I cb, 1|g - øl I bc/
Proof of Lemma 2.5.
w0 1|2 projja- =g) projge-i(w')) 5 [w() + ug =
10 (++1)
It remains to upper bound || + +4g w' 11
We have
( + pg- w"
(1)
+ 2μg (w w²) ) + μ²² 1
2pg w" 41² $1011
24g w- + 24(g - 9) w" + p. |
20
2/g w + 2p(g - 9) bu + μ.² |||
( w/
2ug w" 2pb ||g 9| n²² ||@|1
10 w/
2ubg + 2pb ||g انو μ²² ||
Here, in the second equality, the fact that ğ 1 w and in the fourth equality, use the fact (g g) (1) (g 9) bu (g 9) bu.
that (g - 9) ="
16

---

Notice that
|2(*) w01 || sin & and b = sin 8, By choosing μ = 1/C - c/20
We have
0 01+1 )² < (2sin
8:
(2sin
2 )) )² ueb² 15 + μcb? 20 + 1²2
2
$ sn
0
) )² μc sin? 15 = 4(1
uC
sin 2 02
4(1
( C
2
sin"
0g 2
2
20
2
=
20
This implies sin(0,-1/2) - /
C 20
sin (i/))
B.5 Proof of Lemma 2.6
For convenience, we restate the lemma below.
Lemma B.5. Let a : R - R be any activation function such that a' E L2, I]). Lel a > 1 and 0 0o 7/2 such that /' 1|2 z 1 fa. Let w Sd-1 be any unit vector such that 0 (ww, w²) ) < Go. where err(a((w)) opt S.. E. If 0 ||a'l12 20a²e/z, then for any E S and 1 I[proj.
1 (Veerr(w) [((w))) S !|rroj.! V Vw((w)] /20. Furthermore, if
|proj..' (V err(w) V vul(w))) ||proj.. [we(w)ll /20, then err(w) () S O(a?e).
Proof of Lemma 2.6, Since sin 0 1|0'112 2 20a²e, e, we know that Ve S sin loo 1l2//Vee /V2002 By Lemma 2.4, know that
||proj (Vmerr(w> vnl(ww) w/l S ve ||0|01 sin 0 |1'11 /o/'ll//2200/ 2002
< 0 ||T||I /oo 0 1| //20 llproj Vwl(())] /v20.
Here, the last inequality holds by the monotone property of [T On the other hand, if |proj..' (Vwerr(w) w) [+(()))|| > ||proj.. vel(w)]| / /v20, by Lemma 2.2, we know that
eir(w)= s E (a(w z) - ow" x))² + E (o x) - y)² s 2opt + E (a(w- x) - aww" . x))²
s 2opt + π sin 11o'11 s O(a²e).
Combining Lemma 2.2, Lemma 2.3, Lemma 2.4, Lemma 2.6, we know that the update rule (1) satisfies the following property. Suppose we are given a warm start w(() such that [TTvas 0, 212 2 ||o'll /o. As long as the current w has large angle, and thus has large noiseless error, the noise rate is much smaller than the length of the gradient used in the update and the angle can be improved. On the other hand, once the length of the gradient is small and the noise level is large, it must be the case that the angle is small enough so that the error of the current hypothesis is as small as O(a²e). We next use this property to show that when ||W**| = =1 and t* > 0 is given, we are able to solve the ReLU regression problem with label complexity Ö(1/p + dpolylogg1/e)).
B.6 Proof of Lemma 2.8
We start by proving that using method of label truncation, we are able to reduce the initialization for ReLU regression to the initialization for agnostic learning of halfspaces. We present the proof of Lemma 2.8 and its restatement Lemma B.6.
Lemma B.6. Let a be an activation f the form o Relu(2 10---" t²), where t > O. Let y(x) be any labeling function such that opt I c. Let c > 0 be suitably small constant. Vft)) > Cc, for some large constant C, then Pra-N(( (g(z) # sign (w" x - +))) < (tt) for some large constant
C² > O, where gzz) == 1 [g(x) > ctt)))
The idea of the proof as follows. Since the labels are continuous, for those examples with ground truth labels very close to the threshold c/(t*), we are not able to control their behavior. But on the other hand, for those examples with ground truth labels that are far from the threshold, to change their pseudo-label ((x), the adversary must add high-level noise to them. We will show that as long as h = does not have error O(e), we can reduce the problem halfspace learning by carefully choosing c.
17

---

Proof of Lemma 2.8. We partition F into three regions I1 = for w0. > t + 20/(t' +
1)). 1 fo w² x } and J := for
w t 2c/ (t* + 1)}. Since
opt = E (a(w0 x--'""x--" x--x) - -))² /2 < e, we have
< E (o(w" 11)
- -))²
x~N(0.1)
E
((rh (o(wo -1)) -))² 12
1(x
x~N().1)
E
< c//t"/ + 1l E I2.0(x) > (o(u"" --- ---)- /2
(0.1)
2
Pr
(I 1 U 1,, ((2) # (()))
2(t + 1)2 x0,().1)
Since E(,)( (w* x - -² 2 Ce, we obtain that
2(t + +1²
2(t + 1)2
Eo au" x -t12
Pr (o teEuUk 12 y(z) + [(z)) v (0.1)
c
S {tt()//2,
c²
Cc²
for some large enough C > O.
On the other hand,
2c 1
(t*)²
Pr (x E J,y(z) 4 G(x)) S Pr (x (x N=,1)
exp
10cx((().
a~N((.1)
(1" 1) 22T
Thus,
Pr (0(x) # sign(w" xx- x = Pr (x (.y()) f(x)) + Pr z>N(0,1)
(x h U v()) + m(x))
(0.1)
x~N(
I +0(t)/(c++0c0(()) (( /C"
for some large enough C" > O.
B.7 Proof of Lemma 2.7
Using the initialization technique recently developed in [DKM24), with label complexity Ö(1/p dpolylog(L/e)), we are able to get a w(() with 0 < O(1/t). We next show that such an angle satisfies Lemma 2.6 for a = 0(1). We provide the proof of Lemma 2.7 and its restatement as Lemma B.7.
Lemma B.7. Let a = o be the optimal activation function of the form a (wo x - (*), where o is the ReLU function, w* E gd-1 and 1* > 0 is known. If sfi(/()) S 1/t", then ||To
||o'112 /50. /500
Proof of Lemma 2.7. Let E 1d-1 be any direction such that sin(0/2) S 1/t". Write w = aw+bu.
where u E Sd-1 1 w. a, b 2 0, + 6²2 = 1. By Lemma 2.5, we know that
E ow x (ow" x (x) u) = 6 b oo
(0,1)
To show ||T /oo o 11 2 ||0'11 /50, is sufficient show that E x to xx- x-- t" (x- 2 6 ||o' /50. Write w- u. Notice that 2, are independent one-dimensional normal random variables. We have
oww" x - N(..)
" (w x tz) - u) = E oaa + bs - t') t*)s
2,8
= Eo (z t*) Eo Eo + bs t')s
= bE (z 1*) E (az + bs - 1*).
18

---

Notice that 02 f*) = 1[2 > t*). We have
d' + bs 1²)
b OEo (2- tn Eo' (az + bs - ==)==
= b
(o -)) 4(2) E
dz
o'(2 -t) t*
(d (²) d' [-22)
6
d'(z 1*) E" ]2
b
(d'(: -t)) 21(2) E Eo
al*
2 b (o'(z (3)) (x2=) Eo'
)dz
b
= b [_ (o'(s +)) (x)ddz
12
Pr N
(s>
b(1 + +a)
Since sin() < 1/t", we know that < 2/1", which implies that Pro-N(o.11($ >
b²+²
2
b(++0)
(r, 2) 2 0.02. Thus, obtain that
oww" a - -t0'0'(w" x - (x)(x u) 2 b1l0'112 /50.
z~,)
B.8 Proof of Lemma 2.10
Here we show how use queries to boost the gradient used by (1). The idea behind our proof is that if we consider the random vector G (a(w- x - =²) y(x)) proj where ((, I) [= then with the warm-start we have that the expectation of such ran- dom vector plays the same role as the gradient V err((w), but has larger length and small variance. This allows us to estimate it to desired accuracy with few queries. We provide the proof of Lemma 2.10 and its restatement Lemma B.8.
Lemma B.8. Let o==) Relu(z (*), with t" O. Let y(x) be any labeling function such that opt S Let w E Sd-1 be any vector such that sin(0/2) < 1/t". Denote by G E & the random vector (a(w x - tx) o(w" x t*)) proj x and G the random vector (o(w x t*) y(x)) projw-I, I, where (0, [[]/=>>)>> Then the following holds:
1. EG b b 1/ 1//())
(EG - EG) of - v 11 /011 ((tr).
3. sin" ($((") > then E(G v)2 < Vo
Proof of Lemma 2.10. We first prove the first item.
EG
E
(o(w t*) oow" x -t")) proje
x~ N..
E
1w {²] (o(w -- 11)- o(w" t')) proje-x/00/
N(01)
E
(ww
oww" 1*)) proj x (()
x~N(0,1)
- =bbl Vo _/2 /t(")u
Here, the last equation follows from Lemma 2.3.
19

---

We next prove the second item.
E(G - G) 0| =
E ((, wos)))
(y(x) - olw0
x x -x)) (z 21))
E I)))
1w x > 1-3 (v(z)= - alw- (*)) (I f)) (0(1))
E o'ww.x- -t- t') - aw x - (z. (1688) (0.))
S ||10o|112//(1
Here the last inequality follows from Lemma 2.4. Finally, we control the variance of G. We have
E(G- v)² < 2 B GC*) + (()(C-GG))))+2E((C +2E("" 0)}.
We bound the two terms separately.
E(G v)²
E
(a(w x 100-2-t)) t*) - oww0 xz x )² (x 1p.00 e)2
N00 wast)
E 1w. 1-) (o x olw x - ()) (x. ())0)/)(()))
No0,)
<
E 1( x> [wwxx>t) ( ((w- w)/
0,0 Recall that w² = aw + bu, where u E gd-1 w_w,ab22,,0++ 6² = 1. We have
E(G w)² S E
1 1w. r ((1 () 2)² 12 x) (x ((())((")))))))))))))))()))))0
(0,))
E fw x> f' (1-1a) a) (w
+ 1( x > 1r) (b((u=x)) 0))
=
-(.))
E f < O(b*)
> t
+
E 1 1 (t)) s O(b²)
2,8,7
In the second last inequality above, we use the fact that - cos 0 < 0(sin 0) and E, 1 1( > 1=)=² O((1") (+)( and b (1/tt).
We next bound the first term. We have
E(GG" - U)
=
E
(y(x) - olw" - xx- )²) (o v)3)
- No.
E NoN().1)
(y(x) alw" x - t²))² (z v) - x <> x+()/((t))
Let M > 0 be a threshold such that (2,)) 2²1||2| > M] S e. Notice that if we set y' sign(y) min(lyl. .M, then we will only introduce most c error. So, we can without loss of generality, assume ly] S M. In particular, for ReLU activation, M I [og((/)))) Based on this, we obtain that
E ((G' - G) (2).w)² w)²
E (u(x)) - o(w" x - -x))) (x I (w x > ('](((x w) (M))00())))) (o,(
+
E (U(z) - <(ww' t3)) (I 0) x ff(c- v) > M1/((t)
z(,(0,1)
< optM /Dttt)/D(t") + 4M2 E
(x 1) '1 w A> 11 v) > M1
z~N(0,1)
S <cM2/((L) + 2 S sin² 0M 0(12)
20

---

B.9 Proof of Lemma 2.11
In this section, we present the proof of Lemma 2.11 and the corresponding hypothesis selection algorithm. For convenience, we first state formal version of Lemma 2.11 as follows.
Lemma B.9 (Hypothesis Selection with Queries), Let D be a distribution over Rd x B and let D₂ be the marginal distribution of Dz. There is algorithm that, input a list of hypotheses hi..... hi such that for i E [k], h2 E + R. Ez~D (x) exists, it makes poly (k) queries and returns a hypothesis h such that crr(h) S (minng[[M) ((aa)-D(y -,,)))))(())))))
As subroutine, we will use later, we present the following well-known median-of-ment estimator.
Lemma B.10 (Median of Means Estimation). Let G E Ed be random vector such that for every i E [d], E(G-I,)² < B Then there is an estimator that takes M = Olog 1 dm)). i.i.d. samples from G and computes a vector g E I&d such that with probability at least 1 - ö, llg - E Gl| - B/ /mm
In this hypothesis selection problem, we only need to use the version for d = 1. Roughly speaking, if a random variable has a bounded variance, then very few samples suffice to estimate its mean. We present the following algorithm.
Algorithm/ 2 HYVOTHESUSSLLLCTIOONSSSCd a good hypothesis from a list of hypothesis)
1: Input: f.y..... hgg such that for i E [kj, h2 _ R,, Dr marginal distribution over Idd
2: Output: h Fd R. such that err (h) < ((minge(s] (( hx()))) with non-trivial
probability.
3: Let d(xx) be the density function of Da at
4: Create an empty graph G with set of node [R:]
5: for each (i, i + E [k] do
6: For each pair of (i, create hypothesis (2) = (,,))
7: Denote by Diy the distribution over æ with density proportional to z (x)d(2) Aoth 9i (z)){ with
8: Use the median of mean method estimate EggDD,, (g(z)
poly(k) samples
9: If the estimated result is more than ||/, hylls draw an edge from i to j
10: Return any h4 such that is in a source strongly connected component of G
Proof of Lemma 2.11. We first observe that
(y h; + hi [hh - ha),
err(hu) err(h;) = 2 E y(h; - h:) + ||A.|12 - ||by]|2 a>
E
x~1
which means to compare the error of hi, hj, it is sufficient check the sign of E (v heth
2 [h, - h.). And this is equivalent to check the sign of E,WD, hethhe )g.j. We remark that by construction, 119: = 1. Notice that
Nothy
h + hj 19.5 (z)
h + hj (v
E (y D-
E g1)(x)
gz)(0)
E
)9:s (z)
z>Da
(x)
z
Furthermore, consider the variance of the above quantity, have
E (y Dr
+ hy 2 (z)/91((2)
E D.D
(y
h; h of (z)
22 (z) = (y
h1 + hg
2
2
2
By Lemma 10 we know that with (kly(k) samples we are able to estimate E D. (V hoth )g:7 (r), with error ( /poly(k). We consider a fixed pair of (hi, hz). Assume
(yr hethi
2 ||A - hyll. then we have
h4 + 12g
11(h
h1)ll
3 (1IA, a1 + 114, =1l)
||4 vll <
(yr
<
2
2
4
21

---

which implies ||,, yll - 3 111 yll. By symmetry, we have ||b, yll - 3 3 yll- This implies
if ||A, - -31²= 2 10 | v/l. then we must have [(v A - ||/, h2l1- We next prove that
if |/A, - -l1 2 10 ||h 2|| then there must be an edge from j to but no edge from to j. Recall that
h4 + his (hg - -h:)= = E anDz
u(h; - h4) - | 1/b.l1
E (y D=
2
2
1 (11b: y11 11 y1l² + +11hs112 - [11,13) |1:/11 - || 1
9
2
11:
-y1
2
Since
|1: - hUll 11 2 ||4, - =l - |1/e - wll 2 (V10- 111 - -1
we have 11A, - -11 s ||,e h₂1l 2.. This gives
hs + hy [hg
E (y-
- h:)
2 8
144 - -hsll
x~ D.
2
Thus, when [|+ - y/1² 2 10 [|, y1( we have EDNDD (v hith )g 2 9 llh, hyll and the
estimation of this is larger than 1/+ hلlll with high probability. Thus, there must be an edge from to and no edge from to j.
On the other hand, if
(y
hethy
2 k2 ||4 h1ll. then we have
h4 + h2
/||
11(h; h2)ll
1 (1 2
|/4 - 3/1 S
(y
462 (1lhs - vll + 11, - yll).
2
2
which implies ||:- yl1
(1 + 1/2k² |/1 yll- By symmetry, we have 1| yll > (1
1 1/2x²) ||: yll. If 1/4 - y/1 1 |1h - y/l then we have E yg S 0. Since we have estimated E yggs up to error | h /k2.. this implies unless | - y/l and || yll are within factor of 1 + 1/2k² of each other, there will be no edge from j to Thus, if there is an edge from j to i,
then it must be the case that [h. b/1 2 11 - vl (1 1/2k²).
Now, we consider any source strongly connected S in G. For every pair of (i. in S. there is cycle C' that contains (). Without loss of generality. we write C- = (1 + 2,..., m - 1). where m & k. We will show that every h; E C has similar error. We prove this via contradiction. Assuming there a pair of (i.j) in the cycle such that lyy -h1l2 2 25 |y h.ll² then there must be an edge from i to j. Without loss of generality, we assume i = m and j = 1. otherwise we can prove the same statement over smaller cycle. Since for every S m I, there is an edge from i to + this implies
11-m1-- - vll 2
1
|/1
v 2 h1 - w/1 /2
2 11/m - vll
2
which implies that there should not be an edge from m to m. Thus, for each pair of (i.j) in cycle C. ||4 - y/1² < 25 l1h, - y112 This implies that any source strongly connected component S cannot contain a vertex j such that lly - h 2 25 min,e(M] E(z.))) h. To see why this is true, we consider two cases. Let i* be the vertex such that |/45- - y/ = min E E(z,))=D(V - {. If S contains i", since S is a strongly connected component, each pair of (i, (*) is contained within some cycle and their error must be within factor of 25. On the other hand, if 1" S and 5 contains some j such that I1y - h 1|2 > 25 min E(Ew)~ (yy - hz(z))), which implies that there must be an edge from i" to j and S cannot be a source strongly connected component. Notice that every time we make a comparison between hi; hy. we only use poly(k) samples. thus the total number of queries we make is pk)y(k).
Since for every pair of nodes (i,j), there is cycle such that (i.j) are both in the cycle. In this case, || - hall and [/, - y/l are within a factor. Let i" be the index such that l// - yll is minimized. We claim that C' does not contain some such that h, - y > 10 ||4,- vl If so, then there must be an edge from i" to j. Since C' is a source strongly connected component, then 1" E C, which implies that (i, i*) must be in the same cycle, which gives a contradiction.
D
22

---

B.10 Proof of Theorem B.11
Finally, we give a query-optimal learning algorithm that solves the general ReLU regression problem for the special case where ||W*|| || = 1 and 1* 0 is given.
Theorem B.11 (Query Learning for Spherical ReLU). Consider the problem of agnostic PAC learning GLM with membership queries under the Gaussian distribution. Suppose the optimal activation function a = oi- is of the form a a(w" - ),),, where
the ReLU function, w² Sdd11 and t" E IR is known, there is an algorithm such that for every labeling function y(2) and for every é, E (0, 1), it makes M
(0(iin(1/p 1/e] + d polylog(1/e /e)) memberships queries, runs in poly(d, M) time, where p = ((*) is the bias of the optimal activation function o², and outputs an = oi x- t*), i E Sd-1, such that with probability at least 1 - 6, err(h) S O(opt) + e.
Algorithm 3 SPHERICALL w" over the unit sphere)
1: Input: error parameter E (0, 1), confidence parameter d E (0,
2: Output: ì Ted + R. such that err(h) S (c)) with non-trivial probability.
3: Call INITIALIZZTION((t) to get (0()) and return h(z) = 0 if no w(() is returned.
4: for i = T - do
5: for jorj= L..., (dd) do
6:
Generate 200 > 0 with probability @0t" + /(()/(((t) and 2()i 1 ww() ~ N(O, I)
7: Query vzx(0), where 200) (0))) + +2(1)
8: Estimate E m Σ (o(w)) x(6) t²) y(x(1)) u(d via median of mean and get g())
9:
w(++1) -projga-i (w(+) + (g)
return (T)
11: procedure INITIALIZATION(iiNN
warm start w0()) given 1**)
12:
Input: t" > 0
13:
Output: (0) E su-h such that (ww(0)) w²) S 11((2t) or assert err(O) S O(c).
14:
if (tt")((t < (e)) then
15:
Assert 00 < O(e).
16:
else
17:
Run the initialization algorithm for query learning halfspaces (Algorithm 2/Algorithm 5 in [DKM24]) by simulating binary membership query with y := 1 > c/(t")} for small
constant e > 0 and denote the return of the algorithm by (o).
Proof of Theorem B.11. In each round of Algorithm 3, we use 0, to denote (wll) (e0)),")))) and we denote by Gi Rd the random vector be the random vec- tor (a(w() xx- -x) - (w II- -I- t")) proj and G, be the random vector (a(w(() x -)) v(x)) (ro) where x ~ I) (a/16992221))
By Lemma 2.8 and Lemma 2.9, know that the subroutine INITIALIZATION takes 0(1/p dlog()/))) queries and output a unit vector u(()) such that with probability least log(1/(((*) )) sin (0o/2) < 1/t". In the rest of the proof, we assume INITIALIZATION succeeds. Let a 50.
By Lemma 2.7, let a 50, we know that if 0: S 0o. then | || 2 |10 12 a. Let
6² (0, 7/2) such that sin² x- 20a2e/(T [|a'112). Lemma 2.6 implies that if 8, S d², then err(w) O()²e) O(e), since O(1).
Recall that for activation function o=2) ReLU(== ('), we have ||o' $(1)). We will show
that for if 0, S Og and 02 2 Φ², then with high probability, 0,1 S (1 (1- 11/C00 for some constant
C >
Write w" = (t) + bu, where u E sd-1 a.b 2 0, +02 = 1. By Lemma 2010, we known
that
EG proj (we(ww))) = | v w//((tt)))
(E G - EG]I = [projj. (V (ITw) - V (n (b()t) s Vello'/l,//(
23

---

By Lemma 2.6, we know that if 0- < <0, S to. then (EG' E EG]| - E | This implies that
19
EG EG. u-= EG; u E(G; G3) u 20
| G. 2 19ba //20.
Furthermore, since |EC]
21 E Gill, Lemma 2.5, we know that by estimating G upto error
20
||E /40, then 0.+1 - (1-1 17 for some large constant C > O. By Lemma 2.10, know that E(G u)² I O(b² log(1/c)), Ve gi-!. By Lemma B.10, we know that in each round of update, only need (dd queries. Since only need (log(1//) rounds make 0, I 0", the query complexity of Algorithm 3 is (() + dpoly log( (1))).
C Omitted Proofs from Section 3
In this section, we provide the missing details for solving the general ReLU regression problem.
C.1 Proof of Lemma 3.2
We start with the initialization algorithm. We provide the proof of Lemma 3.2 and its restatement Lemma C.I as follows. The key point of the lemma is that if we have a reasonable initial knowledge about r" t", we are still able to do the initialization.
Lemma C.1 (Initialization with Raw Knowledge). Let a be the ReLU activation function. Let 1n) be the optimal hypothesis. Suppose that (r" (V"))(((*) 2 (e)), there is an algorithm such that given parameter r, >> 0 such that r S rr S and [t -t- 11 S 1/ 1/log((8 (og(Re/e)) /c). makes M = Ó(1/p + dlog(R2 R2² (c)). runs in poly(d, M) time, and with probability at least 1/ log(1/p), outputs some (0) E gd-1 such that sin sin()((()) w.'") )/2) I min 1/2].
ht = =<"o(w"
Proof of Lemma 3.2. We consider the truncated label 7(z) [v(x) > et/t], for suitably small constant с > We will show that the truncated label Ø(x) can be seen as generated from the halfspace ht (x) sign(w"
(*) corrupted with adversarial label noise with level at most /CC for some large enough constant C. By the assumption that (V(() 2 Q(c). we have (t)))) otherwise, (x)) = 0 has error O(e). On the other hand, we can assume F" 2 1, otherwise, estimating Ez~N(o,1) y(z)z with constant error is enough to get w( such that sin ((w(()) w²) I 1/C. With these assumptions, we use similar argument of Lemma 2.8 but with more careful analysis.
F S
did for the proof
We partition Rd into three regions /1 {x wn x > 8' + 2c/t3,12 12 == tx w== .x < 8 and J = (x 7 w < E. 2c/1). Since opt E (r'a(w" (') - 1/2 6,
have
e a~N()111)
E ((EEUU1) (r' -- - -)²² /2
(1f E (1,(())))))) (00()))<<(/))))) <r/ + 1 1x E I2, 12,0(0) > orl1)) (F'(("" .r xx- -1) -y)² -²² /2
a0N()11)
2,2
Pr (rELU U T2, ((x) + ((z))
2t
z~((11)
Since (r
(r
1 ---- 8- > Cc, we obtain that
212 21 Ex (1*))o"""""" xx x0 -
Pr (o (0.1)
v(x) + [(x)) <
22 1
S ((F))/C.
Ce²
for some large enough C 0. Here, we use the fact that r S < 2r, F' < 01 Tog (2) and
It f- -- < 1/ (Ree). On the other hand,
2c 1
(1-)²)
Pr (x E J.u(z)+ (())) < Pr (x EJ (o.)
exp
s 10cD(F).
N0,(
t 2n
2
24

---

Thus,
Pr (0(x) # sign(w" x x)) x
Pr E J.y()) + ((z)) + Pr (x T 12, + ;(x)) z=N(0.1)
(0.1)
I {fff)/Cr + 10c0(t)) = D /fC
for some large enough C > 0. By Lemma 2.9, we are able to efficiently obtain a direction wo that satisfies the statement of Lemma 3.2.
C.2 Proof of Lemma 3.3
We next present the proof of Lemma 3.3 and its restatement Lemma C.2 to decompose the noiseless error for the general ReLU regression problem.
Lemma C.2. Consider the problem of agnostic ReLU regression with queries. Let > 0, w
gd Sd-1 t > 0 and (ww, (w,ww)=>" = 0. If S O( ((vlog((*)/e) and t*1 S 1/ log( /e), then
[(r, w. t) S (r*)² / sin T 80)122 ds ds+
E
(o(rz - t) -(r==-t))
xo.((.11
Proof of Lemma 3.3. To simplify the notation, we denote by // = -l(r"1 w. t*). Notice that ((r, w.
E N001()
(h
E am0.()
(h- - +h' 1²²)²²
E
(h- 11'22 + 11)
No,((
On the one hand, we have
E (h h²)²²
E (o(rw x -) -or")-o(rw-xxt") M~N().1)
E
(o(rz - t) - a(r-2 -11)²²
(0.I)
x~N(0.1)
On the other hand, we have
E 2~NN(0,1)
(h- - 1-=
E (o(r'wxx-- o(r'"" w-= 1²))²
z~N(0.1)
(r²)²
E (a(w- x 1*) - o ow"" x 1²)
zwN(0,1)
(r=))² / sin T /oos o' 11
Here, the last equation follows Lemma 2.2. This implies
wr,, w, S (rr) J sin |iT o' 2)] ds +
E N
(o(rz -t) t) -0(r2= -)))
C.3 Overview of Query Learning Algorithm
In this section, we present the analysis for the algorithm corresponding to Theorem 3.1. For convenience, we present Algorithm 4 as follows and give brief overview of it.
Theorem C.3. Consider the problem of agnostic general ReLU regression with queries under the Gaussian distribution. There is an algorithm such that for every labeling function y(x) and for every poly (d, M)
6, (0, 1), it makes M Ös (mmin /p. R2 /e/ d polylog( R22 /c)) queries, time, where p (FF)) is the bias of the optimal activation function, and outputs an h such that with high probability at least 1 - 5. err(h) < O(ptt) + e.
We remark that the dependence R² /e due the natural scaling of the squared &a loss. If want to learn Ro(w" x 1²) up to error e, this is equivalent to learning a (w" x - t*) to error c/ R?.
Given a ReLU activation, Ar(r,, w 44), define random vectors
G = (M(r,, 9 (4(()) h1" 1x(()) proj (xx
25

---

and its noisy version
G == (((r,, (0), tz)(z) - y(x)) proj (x)
where I 1) w... Define random variables follows
U == (h(r;, ( (4) h² (w r), F. == - (h(ri, w() ()))),)))))))))))() 11);;
and denote by U2, F3, their noisy version, namely
U = (h(r,, ,,) f.) v) x2, F; = (h((r;, wt)) tz)) v)
Algorithm 4 QUERYLEARNING(LEnn optimal ReLU with warm start)
1: Input: (0) E gd-1, unit vector such that 9, s 1/polylog(H2) (RaeloggR///))) > 0 such that In--rol <r² /rr//po /polyloogR /e), to fto t-1 S polyyog(HH/e))
2: Output: h RR + R. such that err(h) I Occ) with non-trivial probability.
3: Bu : r htolploogyRR
4: for fori=0.....
do
5: Generate polylog(R /2/c) samples x(6) 7) | (wi - x> t.). Query y(x(i)) and use them to get estimate 9: for UE, F.).
6: if |0:11 2 B:polylog(R*/e) then
7:
Set (rio, 40) - (ri, (4) and update (rij,4i)) (ray-1)) (1)-1))) (ols)/pllllog((// until |ل S (.
8:
(ri41, + (rij, 4ij)
9:
for j-rj=1o (d) do Generate rlii ~ ((, I) fw(++)), x > f and query y(((5))
10:
Estimate E EG; via median of mean and get G₁
12:
w(++1)= projor (t( mG;))
13:
Bi+1= = B,
14: á (T)
15: Build unit grid of size 1/polylog(H') (aayylog(R/// /c//c) over the ball centered at (rr,tz) and randomly select pair (f, E) from the grid.
16: return (i,,, w,
We now proceed with intuitive explanation of Algorithm 4 and its analysis. The detailed analysis is carried out in the rest of the section. We are given tuple of initial parameters (ro- w(()), (o) such that each of them are close to the true parameters up to a a11 + 1 1/polylog(FF (R2/ /c) factor. We remark that by Lemma 3.2, we are only able to get some (o) such that 0, S 1/8*, but as we will show in Appendix C.4, since the other parameters are close enough, by updating w(()) for log (o2 /e) rounds, we are able to achieve this guarantee. We will maintain an upper bound Bß for (r*)² sin? and reduce this upper bound stably in each round of the algorithm. In our analysis, we will show that as long as the error from (ri, tx) is within a polylog (1²2 /e) factor of B?, we are able to make roughly dpolylog( [t2 /e) queries to safely improve w(() and decrease the angle 0, by a small constant factor.
Regarding the parameters (rs, ta), since they are close to (r",t"), the task for optimizing them can be approximately seen as optimizing the following quadratic function (r,,t) E ((rz-1) - (r'2- +²) 11 > E*). Such a quantity nearly characterizes the contribution of (r,,t)) the noiseless error as well as the contribution of (r;, t.) to the variance of the gradient we use for updating (.) As we will show in Appendix C.5, if B² o (F*) S Z(r,, (4)444)/) 44)/polylog/ R2 /c), i.e. 0 has already been updated in a reasonable range, then (EU, E F:) is very close to the gradient of Z (r., f.). Thus, we are able to tell whether (rr t.) desirable by checking the norm of (E U, F,) due to the nature of quadratic minimization. When Z(r.,t.) is large, we use a standard gradient descent to update these parameters such that Z(r;, 4) is controlled by B within polylogorithmic
factor. This allows us to safely update (((() via gradient descent. When Z(re, 4)) is already close to B,4 we do not update it. We remark that due to the noise and the ill-condition of Z for large t", the
26

---

step size we choose is 1/polylog(R//6 instead of a constant. After at most polylog (ooylog(2//55 R2/c) rounds, w(T) is updated to desirable accuracy. However, due to the presence of noise, we are only able to guarantee that (rr, br) is O(cpolylog(A) R2 / /c) (f)) close (r",, t*) in terms of squared norm. Fortunately, there are only two parameters we need to worry about and they are already very close to
(r",t"); ); randomly selecting a pair of parameters from their neighborhoods gives us good hypothesis with enough probability.
C.4 Omitted Details Regarding Angle Update
In this section, we provide the full details the subroutine for updating the direction w(() Specifi- cally, we will consider the following random vectors in Rd. Given ReLU activation, h(ra, w()) tt). define random vectors G :- (h(ri, w(), (z)(x) - h- (x)) ( (x) and its noisy version G = (h(r,, w(),, (z) y(z)) pr)] (z), where x ~ NN(0 I) ls0.
C.4.1 Proof of Lemma 3.4
We first give an evaluation of the mean and the noise analysis of G. We provide the proof of Lemma 3,4 and its restatment Lemma C.4.
Lemma C.4. Consider the problem of agnostic ReLU regression with queries. Let h(ri, w6 t.).
Write w² = aw(l) + bu, where a, >> 0,a² + 1 = 1, u E gd-1 L w((), Then the following statements hold.
If - 1 log( /e) and S 1/t,, then
EG = -abr" I|Tao' - [,]]] [i)ll"//bl/ w/b(T.)
where 1/2 < a <
(EG - EG) ol S Vello'(=
Weesr w()
Proof of Lemma 3.4. We first consider the mean of G.. By Fact A.5 and Fact A.8, we have
(h(ri, (1)(())))))))))))))()))))) - (x)) proj
E EG a~ N0 (
E
E x>> { (1(Tt, ( (z)(z)
((
- -h((x) (t)(()))
proj( x/ (t.)
z~N(1
-pro
E
1w x>> (1)"(r)x/((()
z~N(0,1)
E z~N(0,1)
(w
<> 1, (w" <>> 1 //rrn/
E
1( .x> 1,]((w( .> br ((.))
z>N(0.1)
+
E
1 (1 xx> x>>T] (1 x > [ 1/ x 1- Hbbr"
-~N(0,1)
-br T - T4]1 u/ ((,,)
E
(1 [1 x >> <>4}
fl x x (2))brr
[0N()
By Lemma 2.7, we know that | [2 - E)]l (1)) Furthermore, we have
E (1) x 1.)(1 x> [.) (w x>> Fリ) [0.
E I~N(0,1)
(1 x [.) 11 x>> (3)) = =o{((T))
We conclude that E G -abr" |T (z {) u/ ((.) where 1/2<055
27

---

We next analyze the noise term. For every v E gd-1
and v 1 ww( by Holder's 's inequality, we have
E G4) r/
E
(v(z) (z) u))
x~N(O.D) (1(0)24)))
E
1(w(()) x>>>>> (,} (v(x)) h1" (x)) (or 8)) (2((,)
z~,((,11)
(1(x) - (x)
1( x > tiflz v)²
e~N().1)
(0N()
S ve (1o (8(T))
C.4.2 Proof of Lemma 3.5
We next provide the evaluation for the variance of G. We provide the proof of Lemma 3.5 and its restatement Lemma C.5.
Lemma C.5. Ler h(r, w(,t, t.) be a ReLU activation. Write w" = aw + bu, where a,b > 0, a² + 12 = 1, u E gd-1,u wlf) If 11] S 1/1og(Be//)) Ce/(())((((1)) S b² < 1/2. then
E(G: .)² S
E (o(riz- - (:) - -1)) ( (1990)))
(~N(0,))
for every u E gd-1, v w((
Proof of Lemma 3.5. For every E gd-1, 1 w(() we have
E(G; -)2² < 2EE(G Gt) u)² + +2E(G; v)²
We bound the two terms separately.
E s0.N(0.)) (uxtt) a22) (M(r, (2) n1) 2 (xr .))²
B(G v)²
E
1(w x > Est (h(ra w())
((), .ti - h1) (x- ()2
x0,((011)
We next expand (h(r,, w(()) (t)) (4)--10 h²²²² as follows:
(h(ri, (x) - n²)²
= =(h(ri, (0), ,tt)) h(r", (0) (²) + h(r", ()))tt))-(("
-h(r,, w0, tt))"
52 <2((( (h(rs,
(,,,)) (i) h(r,, w()) 13)) + 2 [1(r", w0)) - h1rr,,, w(t) (0))
For the first term, have
(t) - h(r", w()) r3)) ? <>> Eit (b(ri, w
E ((
(x ((),)((E)))))))))
(o.1)
E 1 (0.1)
x > fi (a(rzz t() a(r"= +²) (E.)
For the second term, notice that
(o(w x -x)) - a aww" 33))² 5 <((11a))w
a)w - bu)
x) x) )2 < 2(1 a) +z)+2662 (v/uuxx² x)2
28

---

Since a) 0(b)) and b = =(4,,, this gives
E l)w x > { (o(w!)) x -F) --P)-o(w' x - -)) 2 (x 0))
)>N(1,1)
E 1/ x x>>4 (2(1 a) a)((w(() -x)0 26 m){) 2 (o 100008//00/
m~N(0,1)
s 50 b² 0(b²)
This gives
B(G : u)² So
(a(r2z- - (i) - -o(r== -1))²² (b())) + (17)807)
Next, we bound the variance of the noisy term.
E((G" - u) =
E (u(z) - h" (x)) (x. 1)9)
E (0.1)
(x))) (x- 11 (1/((1))
Let M > be a threshold such that (0 1|=1 M] S e/RR. Notice that if we set sign(y) min(lyl, rr,M,, then will only introduce at most error since |r, - rr1 S r" log( R/c). So, we can without loss of generality, assume |y| < M. In particular, for ReLU activation, M <
Based on this, we obtain that
E [(G] - G.).,)² u)²
E (v(x) - h²)))) 2 ()
w~N(0,1)
E (u(x) - )x)) (x 1 .>> >> > M)/((t)
z~N(0.1)
opt.M///((() 4M E
(x v) 21 (w x 1(( v) (TA)(T))
z~N().1)
S <cM² /cM²//(FF) 4c / sin AM 0(0) log lR /c)
Thus, conclude that
E(G; b(G
E (*~N(..T)
(o(riz - (.) - -(r"= - (²))² (0()) + (1+)882)) (1))))))(
C.4.3 Progress on Angle Update
In this section, we analyze the progress made over the update of w(,, We present the following lemma for measuring the progress on w(()
Lemma C.6. Consider the problem of agnostic ReLU regression with queries. Let h(ri, w(()) (4) be
ReLU activation function. finctiono Write w* = aw! + bu, where a, b > 0, 0² +12 = =1, 1.u. E sd-1 1,,1, 1 (i) Suppose [6: E$| < 1/ log[R2 /e), b < 1/1, and |r; r"1 S r* /polylog(112 /e). Let B, > 0 be
parameter that satisfies the following property:
1. Es-N(O,)) (o(ri - tt) -0(r-= 1--=--"))
BB
B2 2(c).
Define Bi=1= (1-101111/1))) B,C for some universal constant C O. If (r+)) sin? 8, S B,33. 0 < 3 < 1/10, then the update w((++) = projga-1 (w) - p,G.)) satisfies (r*)² sin? 0.+1 S 12 where M4 is a small constant and G. is estimation of E G4 with 0(d/32) samples.
29

---

Proof of Lemma C.6. Write x- am + bu, where b > 0, a² + b² = 1. u E S u 1 7
Since sin 8, < 1/f It; - 1 - 1/ log [2 /e) and rn - -r r*
/polylog [R /e), by Lemma 3.5
and Lemma 10, we know that with ((d) samples of G. have [ E.; - BB:/1000. We consider two cases for (r*)) 0,. In the first case, we assume that (3 /2 /2 < (r*)² sin 0, S 3 B². By Lemma 3.4, we know that G. - EC. S 3 ||E for some large enough constant C1 > 0. By Lemma 2.5, we know that there is a small constant C2 > 0 such that sin 01+1 S (1 - 02) sin O; which implies that (r*)² sin" 0.+1 S B²+++
In the second case, we have (r*)² sin? 2 0, - B32B2/2. Notice that
2(sin(
0
0 2) = || | - o- - ( - w+ 1 sin(
10 S (1()) - m.Gi - w(())
|
2
Then we have
0it1
= -BBB+1 -r" **sinn 0 _ - rsin(
Bit1
sin B 2
3B - r" sin(
2
2
2
2 Bi+ - -BBe/2 rr |m.c.
>0
Thus, in both cases, we have (r*)² sin2 0,+1 S 3B2B2²+
We discuss the implication of Lemma C.6 before providing the details for updating the pa-
rameters (r, (). In our application, we will choose 3 = 1/polylog(FF) Raaillo((///// /t//)) As we discussed in Section 3, we have initial parameters ro. such that Iro- r"1 S r" r"/polylogRR? (R² /e) and F - 1 < 1/polylog( /e). This implies that
E (a(roz to) - -())=
N(,))
<
E ((ro- - -r")a(= - -oo))² + E
(r*) (r()) (.) o(= - -)))
I~
z~N(0,1)
<0((ro- - - + (To ()) S (")))((()))))))))))
R² /t).
If E is large enough such that for 0 1/polylog( R2 /c), (r*)² sin (T) S Ce, then by Lemma C.6, starting from w( and updating w())) at most log log( R2 /c) steps, obtain hy- pothesis with error O(e). Thus, in the rest of the section, we will assume that w()) satisfies sin 0g < 1/polylog(PP) R2/ /c).
C.5 Omitted Details in (r,)) Updates
Here we provide the details for updating the parameters (r, t). For a given ReLU activation H(TT, wii) fs), we define the following random variables:
U = (h(r,, ( (,) h² (w F) = - -h((r, w0,4) h1)),
and denote by Us, F2, their noisy version, namely
U := (h(r,, w tx) - (w x), Fi = - -(h(r,, w()) (t)) -1)
Here, x (0, 100
When the direction w is fixed, we will also use U(r, t). F(r, t) defined as follows for convenience:
U(r 1) == (M(r, w) ww - x), F(r, t) == -(h(r, w. 1) - y)-
We give quantitative characterizations for these random variables. We write w' = aw ( + bu, where a. b > 0, a² + b² = 1. u E gdd1 u 1 w(( We furthermore assume that the parameters lirr, w(()) 4,) are close to (r","", (()) That is to say 0, == 0(w,, wn()) S (() Ira - r*1 S r" //ooyyllo R² Re),),))) [ f'l < 1/polylog(RR2/)) /e)...
30

---

Evaluation of E E and E F
We first evaluate the expectation of U To do this, we first expand
Mir,, w(t) (.) - h² as follows
h(ri, (0) ()) - -1=-== - ,0,4 - , + , w²) - -h²
Since
E
E (M((r,, 10001,1,, (4) 11" (w) x) 1 (0) 1,)/ w())t))) E (h(ri, ( 4)) - h(r", w t)) + fe(r", 0 t*) h (w) x) x > (())(())
a~N(0,1)
x~N(0,1)
we evaluate the two components separately. For the first term, we have (h(re, (+)) .t:) - h(r", (0) t²) (w) x) x2> x> E (a(r - 12) - -r(r== x²)) = ((T,)
x=N()
(0,(
We next consider the second term. By Fact A.5, we have
E (h(r", w0 t*) - 1t" (w x) (w x > (())
= -(r)/((())
E N
(o(2- - Taa F)) 21 21 (3>1.) 1.}
(%." dT (f ds d'(z - -1)z = (r*/0(f")
dT,o(2 -8) 0'(z
-f) - +.)
= =(r))((())
E
E
xNN(0.11
ds
((,11
ds
-(-1/(()) J.
1 (LT (')) +,))'s ds
E -LT,0(= -1 [.))ds (r (r'/)(F))
E
N0N(0,1)
2~N
[ N0.1)
-(r))(()))
Too - (o) (o'(2 - (4) + =0(= - [:)) ds
-(r'/((()) L sin
E
T o d' (z- (o' (= (4) =0(= [T)) ds.
N0010
We notice that
E
Teos (z 8 jo - (2
E
Te,o Toosso (z - (o - -8)-
E
-4))
x~N(0,1)
z~0(0,1)
E N0,1
T oo (3 - -1) s
E
Toos
o - b) = Roll//oos000 (2 - 1)1,
when sin < 1/7 and F P1 S O(log(R/e)) (R/e)). This implies
/ sin s
(r*/0(())
E N(.1)
Toos o o0 (0)
ds = 0( ooogdo -2-))11)))
On the other hand,
E Tecs o - 8*) )=0(2= - [,) = Tooes o't - )t(((() = Pr (cos st, + sin sin -8" > (t). p~N10.11)
x01)(
This implies that
(r//((1))) { sins 20N(0.1)
Teanso - 1))z((z - I.)ds
-r" 1- sins Pr (cos s7, + sin 83 - > ()Teo((T))ds B-.10.1)
(L)))))) = O(r'))
Putting everything together, we get
EU
E (o(riz - f,) o(r"z - x²)) 21 ()) + b z0.()
31

---

for some suitable constant e >> O.
We next evaluate E F in similar way.
E
E (h(ri, (0 4) h1" ( x > [:)/
a~N(0,1)
= E (N(ri, (0) ,1,44) - h(r" w0) ,1) + Mir" w
- -1) (w x (1)/((())))))))))()))))))))))(
x~N((,,)
E (o(r,2 -4) -r("z2 (²)) ((()) + E (h(r w() (0) 11" 11) x -x> (3)((E))
z~,((,1)
z~N(0,1)
For the second component in E F,, we have
E (h(r",
w0)) t²) - h0)1 ( (1) x > (ff,
xNN().1)
= -(r)/((F)
E (o(z- -1) - Too - 12) 1 > 4
xNN(0.1)
(L."
[= ds d'(z d'(z- (:) (r'/0(F))
[
dT,o(z- -P))
o 02) [.)ds
= (r'/)(P)) M(.1)
E
E
ds
(
ds
J N0.1)
1
=(r'/((T))
E
- (o''(z (t) = - (r'))
E
-t))dds
20.1
-(r'/((²))
E
T - 8) (6(z E() ds
(0.1)
/ sin S
(rr/
E N0,1)
Tems o Pz- (5(z - f,)) ds s ((100 (()) s (()')
This gives E E = E N(..) (a(r,-- - 1,) a(r"z - t*)) 1l 0 x > (f,) + cbr for some
suitably small constant
As summary, we have the following:
Proposition C.7. There exist small constants C2 > 0 such that,
E E
E 10,1)
(o(riz - (1) - o(r" 2 -))=)() (*)) =1 =1 > (t)) + Harrb
EF =
E NO))
(a(riz - t4) -
x > (t,) + cbr".
Evaluation for Noise Terms
We next evaluate the noise terms. For the noise term in Ug we have
E(U, - -U,]=
E ((,I)
(y-h")
- h2) (w (w) x > (())
E N(0,1)
(u(x) - (x)))
E a>.((.))
1 (wii)) x > [.]( (()))
S
Ve
E >²1( > &)) zoN11.1)
/0((1) = +
Here, in the last equation, we use the fact that E E 221(22 > [x)()) Similarly, for the noise term in F, we have
E(F: -F7)
E 1w- 1(w(() x (l.)
((,))
E (u(x) - hx)))²
E
1(w(() .I> > (T.,)
N
x~N(1.0))
<
E 1(2 > E.) s0,1(0.11
/ = VeV
As summary, we have established the following:
32

---

Proposition C.8.
EIU - U,} (01)/00))) C(FF-E)) (tt)(tt)/(tt))
We remark that when iq is close to f², the noise rate of Ug is larger than that of F, by factor of 8". This is one of the central reasons why we need a small step size to update (r, t), and can only guarantee that (rr, (t) is O(epolylog(R') (R//e)////// (e)//((())))) )) close to (r", with gradient descent only.
Evaluation for Variance Finally, we examine the variance of U2 and F,. We start with U.. Notice that E EU?- s E( + 2 - 2.)
Let M > be a threshold such that Eg=,(0.1) [1=] > M] S </RR. Notice that if we set y/ sign(y) min(ly] rr then we will only introduce at most e error, since |r; - r-1 <r/ (g()))). So, we can, without loss of generality, assume that |y| s M. In particular, for the ReLU activation.
M S O( (looo)(R//)) Based on this, we obtain that:
E(U; - U,)²= = E (u(x) - h-" (x))² (x w 11w ( .z> f.11((z w() S Mf/((E.)
z~N(0.1)
+ E (v(x) - (=)) (x w 10) xx 11]1((00 w(t) > M)/
=~N(0,1)
S (1) + 4M
E
(x w) 1 111((2 > M)/0(1.)
a~ (0.1)
S <M² (f.) - 4eM² / (t.)) = ((e/
We next consider the variance of 2 We have
E (h(rs, w( 11) h(r,, ( (0'))))) (1)) 11 x ((44(())
((.J)
+ I0,
E (h(r", w x*) - ho (w 2) fw) x ((4)
We separately evaluate the two terms above. First, we have
E
(h(r,, (() tt) h(r", w (t,),))) (w)) () x x ff/4(E)
E 2~N(0.1) [.) - - ( 21 (1>1)>>0000 (E))
For the second term, recall that we decompose wt = aw + bu. Notice that
(o(w(). x -- alw" xx xx- (x))))² s (ww() - =²) = ((1 a) .x)))a)))))))) + b(u x))) 2
< 2(1 (w x)² + 26² (u x)²
This implies
E (h(r", (h(r", (0(0)t))))) " x) 3 10.. (
E (2(1- a)²(w x) 28 x)
2) x>> (((')//((()
I
E
()) 25
(0.1)
<o(
E b-211(2 > ()67)/0(())
E 03, ()00)//(())))
(0110.11)
We evaluate F in a similar way. First, we have
B -
33

---

Next, we have
E(F,)
2 2 E
(h(ri, w(), (1:1)-)0 - li(r", w ,0) x x=> 22>1,//(00) (.)/((G))
am ((,
+ 2
E (M(r", , .1)) - 111) (w (0) x (G))
The first term can be evaluated as
E
(h(ri, w() .t)) h(r", x0) 21)) (w) x> f>f(f((f)
(0,10
E
(m/a(2 - [,) - -r-a(== 11) (1)((())
(0,1)
For the second term, have
E (>,((
(h(r", w(() ,t) - h- 11 x x >> ((E)((E))
E
a)² [2(1 (2(1-))(ub)) (0 2)²² 26 (u.
1 1(w x (1)(7))/((()))
E (2(1 (=)²
(1)()))/((1))
(0,1((0.1)
<0(
E ba 21 ()(r))/((())
E 8112> -)))))/(()))
(011
As summary, we have established: Proposition C.9.
EU? c
E Z
EF, < Ô
E (=~N(0.1)
(rio(z - +))
C.5.1 Progress on (r, Updates
In this section, we describe how to update the parameters (r, f) that we are able to make the term 1io.) (a(rzz 44) a(r"= 1²) stably drop every time we choose update the parameters. For convenience, in this section, we define the following 2-dimensional vector:
((riz - -4) 14)-((1' -1=- -0) T
g())
((ri2 (.) (r'=-t))==1z=> (0.1)
E
E =~N(U,1) (1: --))((()))))
-((r r (0(")) (4 - (r))))(),-
and function
t(r, E
((rz 1) - (r 13)) 1( 1(3>8)
z~N(0,1)
=(r - (-)-)))8((7)
t* ())((()) 2(r ())(F)
tr,,t) =
E so.11
(o - t) -0('2-
To simplify the notation, we define
8(1*) (i((t)
Q
and define tr,,t) = ((-- rr), T))T. By definition, t(r,t) = ATQA. In particular, the largest eigenvalue of Q is ((EE)) while the smallest eigenvalue of Q is ((((E))) Thus, the ratio of the largest and smallest cigenvalues of Q is at most lo? /e). Furthermore, we want to mention that, when 1 becomes large, Q becomes ill-conditioned; this is the reason why in Algorithm 4, update (r;,4) with much smaller rate of 1 l/polylog( gradient descent stage can only guarantee that (rr, tr) is cpolylog R22/)) //) close to the optimal parameters (r" .t").
R2 /c) and the
We remark that (L)) is exactly the gradient of Z at point (ri, 42). The motivation of using this notation that when (v, t) is close to (r",""), Z(r, 1) and W(r, L), the quantities we want to control, are different by a negligible factor. We give the following proposition.
34

---

Proposition C.10. Suppose 8* < Vlog( R2 /e/c) and r' - R. given a pair of parameter (r, t) such that | r" rr polyloo R²² EE) and { t s 1/polylog( R² /e), we have
(w t) Z(r, oZ t)).
Proof. Since (r; 1) and ((r, 1) are only different at region {= [1 > 4, 1 1(= > 0}. when (r,1) 1) are close to (r", we have
( - (rr,0) S ((r )² + (1 11-1% (2))) Pr(z E {= [=
1(: M1 0})
- ((r r-) + (t ()) ((r)) //olyloo(lll (R2))))((///))))))))))))))() /c) < Z(r
/e).
Here, in the last inequality, we use the fact that the smallest eigenvalue of Q is 0! 1 (f* ( 1)
and
thus (rr,t) () 2 (r) (//(rr))/poolloo/ ppolyoog R2 /c))
Such proposition can also be generalized to the gradient of F and W. We next give the following proposition.
Proposition C.111 Suppose 8* < Vlog( It2 /e) and r' S R, given pair of parameter (r, t) such that r - r'I S /polylog( R² /c) and { t s 1/polylog( R2 /e), we have
[r, ( (r, < A(, (()).
Proof of Proposition C.I1. We notice that
v,W(r, t) = 2
E
(o(rz - t) -0ororr22 1²) [1
=~N(0.1)
v,W(r,))= -22 E z~N(0.11
- (t) -o(' - 1¹) 1(2 >)
Since Wrr, t) and Z(r,t) are only different at region fz [1 > & - 1(x > M) > 0}. when (r,t) are close to (r*,')), when
(V VW (r) ((r -)-- 17) Pr(z {z [1 > 4 122> 8) 03)²
$ ppo(()//olyylog((
Before formally presenting the analysis for updating the parameters (r, t), present the following standard gradient descent analysis for analyzing quadratic minimization.
Proposition C.12. Let Q E 2x2 be a positive definite matrix and let L,, p be the largest eigenvalue
and smallest eigenvalue of Q. For x E IR,, define F(x) x Qz. For 0
(//L)/C, for
large constant C, given g' E IR² such that I|g - -VF < c CIIFF Fll, let 0 < S 011L), then the update x' x pug' satisfies Fxx') < (1 ((d) and xx (1 ((m)) |0|||
Proof of Proposition C2 The proof of Proposition C.12 follows the standard gradient descent analysis for L smooth functions that satisfy the Lojasieeo condition with parameter μ.. We have
|VFI > 2xF(x)
F(x') < F(x) - -VV()) Laj 1101111122
Since
VF(2) 2 |VF(()) - |F VF(x)] 21
and
llg'll (1+
35

---

we have
F(x') S F(x) 17(1 c)||2 + Ln² (1 (1+c)
2
1-2p 2p ((( c) Lup (1 x)²) F(x).
This implies that by choosing ア O(1LL), we have F(x') (1 (m)))
We next show that the update also contracts the parameter distance
| | ng'1 | FZ) + (VV((z) g')ll S || + I'll S | - (=(")) + nc|lF(x)] & (1 - -np) ||>|| | on ||||| S (1 0(n))) |||||
Here, the last inequality follows the fact that S (n/L)/C.
In our setting, we have that the parameters μs, L for Q are 2 (((())((()) and ((7))
Thus, ((11(t()) and I= =()))))) By choosing the step size = 1 /ppolylo( RR2/ /c), we are able to drop Z(r; 1), and thus (r, f), by factor of 1 1/polylog( R /e) ) in each round of update. Furthermore, after the update (r, f), is still close to (r",t") ). So far, we have already stated all ingredients for analyzing the update for parameters (r. t). We present the following lemma conclude this section.
after zooming in to the region (( f). the rescaled parameters become
Lemma C.13. Consider the problem of agnostic ReLU regression with queries. Let h(ri, w()), (o((),t))) be (+) + bu, where a, O, a² + 1, u E 8d -u (t) Suppose that [4 - 11 < 1 1/polylog( R22 RR/e), b S 1/1, and [r; r*1 < r² polllogg( (R//e)) Let
ReLU activation function. Write w" (t)
B, > O and define B++1 = - 11-1/C) (CC,), B, for some universal constant C. Suppose Bi, Bi41 satisfy
the following properties:
1. ((r)) sin2 0, B2+
2. BTT((T) 2 (()).
3. (rr;,t)) - B polyyog
If (r,,t) 2 b² (E polylog((H /c), then there is an algorithm that makes polylog /e) queries, rans in polylog( R2 /E) time, and outputs a pair of (r+41,t441) such that W (ri+1, t++1)= S B2 ((F") polyyoog R2 /e).
Proof of Lemma C.13. For a parameter (r, (). if (r,,)) > B2 D( )olylog((R//e) by Proposition C.10, it must be the case that ((r,t) 2 B4+1810 (oly)poollogg R (e)e), which im- plies that []V Ol1 z ((+ poolyooo) /e). By Proposition C.11, this implies that (r, !)l > that when (r*)² 0. I *BL (.Fr,)) implies that (r, t), E((rt)) (2(r,t)/(((") < (r, (t II). By Proposi- tion C.9, with polylog(R') (R/cc) queries, we are able to estimate (EU(r, t). E ((r,t)) with er- RR3/c;; /c); and thus this is different from (Z(r,t)/((F) /polylog(B)))) RR/ /c). By Proposition C.12, we know that by running gradi-
(((F')olylog((")
On the other hand, by Proposition C.7, we know
(W f)ll oWI (r; ()I)) This
(r,U((, t). E F(r, f))ll /oolylog R²
by
IV ((r t)/ descent with step size O(1/polylog RR2 /e)), we are able to drop Z(r,1) be factor of (1- 1/polylog(Pe/or (T))e)) in each round; and thus after polylog(R2 R2/e) rounds of iterations, we have Z(re41,44)
BL_ (D(T") R2 (Re))))RR.........)))) Therefore, by Proposition C.10, we have W(r++1, (411 S B2 2(* polylog
C.6 Proof of Theorem 3.1
In this section, we give the proof of Theorem 3.1.
Proof of Theorem 3.1. We first notice that p < </2R,, otherwise the function has error O(e). Thus, by Lemma 3.2, with min(1/2 RP/e) queries, we obtain a warm start (())) such that 0 S 0(1 Furthermore, by the construction of the grid (r, t), if we randomly chose parameter (ro, to) from
36

---

the grid, with non-trivial probabliiyy(//poyygggR"" (R2))logg((R)))))))) RR)))), we have Iro - -rr1 S r" htplylloolg'' (R/e)
and [8o 1 < 1/polylog
With the pair of (ro: u to), we Algorithm 4. We prove by induction that in each round of the update (r) I B (olayfo)) R2 /e) and (r*)² sin 0g f B Notice that for i 0 this holds automatically by the property of (ro, w(()), to as a warm start.
Now suppose that this holds in the ith round. We will show this holds for the i + 1th round. By induction, we have (r*)² sin" 0.41 I B2+1- By Proposition C.7 and Proposition C.11, we must have [I t.), E (rr,,t)))
I ofI Z t) (I) By Propo- sition C.9, with polylog(R') /e) samples, we are able to estimate (EU(r, t.). (F.,,t)) up to error [| (ri, t.), E F(ri, t.))l /polylog(( /e), Since (rr ((()(()))))))))))))))))))))))( 2 [V (()) this implies if W (ri, (4) > Bi+1 +((* (ooyy)o) (It /e), we are able verify this by looking at the length of the gradient; and thus by Lemma C.13, after making polylog /e) queries, we get ((s+11, 14+1) S 2 ppolylog(R2) /c)/c). After this by Lemma C.6, by making O(d) queries, we have (r*) S B2+2-
(llog(112/e) /e)) rounds, we have (+)))+)(())) I O(e), while (rr,,tr) I O(epolylog(RP) (R2 /e). By Proposition C.10, this implies [|((,, trl ((t)) Z(rT, tr ppolylog( /e) S O O(epolylog( (tt))/og(((///)).) Notice that if a pair of (r, t) satisfies || | (r, Oll [t /e)), then W (r, S O(e). This implies that if we consider the ball B C IR cen- tered at (T) with radius O epoellly R22 /e)//((()))))))))))()))))))))))) then ("" E B. In particular, we grid B with a net N of size polylog( /e), there must be some (r',') that is (oolo(() [e)) close to (r',00 ()). By uniformly sampling from the grid, with probability at least 1 1/polylog( /e), we get such (r', f') with W 1') S O(). By Lemma 3.3, we know that hrr', (,(") ,/') has noiseless error at most (c), and thus err(h(r', w(()) ((t)tt))) t²)) )- = Oc).. Furthermore, the total number of queries we use is Ö₂ (min (1 1/p. R2/C) + d -polyoog R22 /e)). We remark that the current algorithm has a probability of success of 1/polylog(HH// /e). Thus, by running it polylog( [t2 /e) times, we get a list of polylog [t2 /e) hypothesis, one of which has error O(t). By doing hypothesis selection procedure using Lemma 1. we are able select hypothesis with O(e) error with high probability, which will only cost another polylog RR/)) queries.
Now after T
e/ (ollyl)o)
D Omitted Proofs from Section 4
D.1 Proof of Theorem 4.1
For convenience, we restate the theorem below. Theorem D.1. Consider the problem of agnostic ReLU regression with queries with a restriction that the optimal ReLU satisfies [|W*|| S and has bias at least p. Any learning algorithm that outputs a hypothesis with error less than Opp log² (p)) with probability 1/3, must make at least (01/p2-oa(1) + d) queries. Furthermore, this holds even if opt < 2- 2-((aa/')pp
Proof. We break down the proof into two parts. First, we show a lower bound of (1(1p)). Consider two hypotheses h1 (z) = oww" x - t²), where w" is drawn uniformly from gá-1 and h2(x)) = 0. Notice that
E N(0,)
(h1(x) - h²(x))² V(t*) (F)) ((t)) 2 ((t')((t)² #(p))
Thus, any learning algorithm that can learn a hypothesis with error Ö(p) can distinguish whether the target hypothesis is h or h2. We construct adversarial label noise as follows, when yy is the underlying hypothesis. For every example such that || > d + A, where A = d", 0 < a < 1, and d large enough, the adversary changes its label by y(z) O. We first show that the noise level is small. We have
E soN( (h1(z)) - y) E hf(x)1(w" . x x > t", ||]|| > d+
M0.
s Ō(pexp(-50) - 2
37

---

where in the last inequality, we use the tail bound for -d-distribttion. Here, we choose a = 5/8 to make 2a
1/4.
This implies that by querying examples with norm larger than vd+ A, learner will get informa- tion. Now we consider deterministic learner that makes r queries over the ball with radius vd + A. Since w" drawn uniformly from the unit sphere, we know that for each realization of w", only examples in R == {ar w" >> t*) have non-zero labels. This implies that the number of queries that fall into this region is
(t')² 2(1 + da-iy ((p''
Pr (0) 2 (7) (0) Ō exp( (v
for a E (0, 1). Thus, unless r 2 ((1/p)-o(1)) no query will have a non-zero response, and thus is impossible distinguish whether the ground truth is h h2.
We next establish the lower bound on d. We show that this even holds for learning a homogeneous ReLU with error (2(1) in the realizable setting. We consider even simpler model in the realizable setting, where w" E gd-1 and t" = O. Furthermore, for every query made by the learner, we additionally provide the information w* x. Denote by L the subspace spanned by x((1), r((),...,, ,x(), the queries made by the learner. We assume that S d log(d). Denote by wi projr (w*). Since w" gi-11 given wi, we know that the orthogonal component " is random vector drawn from the ball in L with radius /I hypothesis h, consider the expected error of h when w²,, D. We have
|| 2 Let D be the distribution of wi,, Now for any fixed
E (h(x) - o (w x + + 1 ~ N(0.)
N wn -D (h(x) o(wi x + w)
E Var Varw;r~-loo ~plolwt + wi,- x))
N0,1)
E Var Dlla(w] xT + w xz=))) x0N((
To simplify the notation, we denote by T wT, 2r. the threshold of the ReLU, owwi
"zz .. Notice that since S d/ log(d), with probability at least 2/3, | S log(())
and [T] I 1/ ///o)(1/d). Denote by D' the uniform distribution over the ball in I with radius
r - ||=
| []. For every fixed F we have
Var __ ( + w/ xx,))) = VaI + x)),
where é is the first standard basis vector in I.-. Since T. has dimension d(1 - (1/ /lg(()))) we know that when ||æ 2 S2( ((vd), and thus > ((vd). Varz~ (a +ei 2 22(1). Since x and Fr are independent, we know that with probability at least 2/3, || 2 ((vd). Thus, for every learning algorithm, if makes fewer than d/ log(d) queries, with probability at least 2/3, the expected
error of the output hypothesis is at least E,, ~D Eu~N(0,)) (h(x)) (w + w ))² 2 2(1). L
D.2 Proof of Theorem 4.2
We restate the theorem below.
Theorem D.2. For any active learning algorithm A, there is activation function h² that labels S with bias p such that if A makes less than O(dd(plog(m)) label queries over S. a set m i..dd. points drawn from N (0, then with probability least 2/3 the hypothesis h output by A has error more than Öpp) with respect to h
To begin with, we establish the following lemma that reduces the learning problem to slightly easier problem of finding examples with zon-zero labels from a pool of unlabeled examples.
Lemma D.3. Suppose there is an active learning algorithm that can make label queries over pool S of m 2 poly(d/p) examples drawn from N I) and learn any ReLU activation function
h" (x) oww" t*) with bias p up to error ((p) with probability at least 2/3. Then there is
38

---

an algorithm such that given pool of 2m random examples S drawn frow the standard Gaussian
distribution with hidden labels by some ReLU activation function h² (2) = a(w" -r- it makes + O(d) queries and finds d examples with non-zero labels. from S with probability 1 1/2.
----t) -*) with bias
Proof of Lemma D.3. Let A be such a learning algorithm. We select a random set of m exam- ples S1 and give it to A. We know that with probability 1/2, we learn a hypothesis h such that E..,((.)) (h(z)) ht (z))² < Ö(p). We first show that if x No,, then with probability at least (2()), h(x) > 1/ 12t.). This is because otherwise
E (h(x) - h²xx)) 1(h(2) < 1/(2)) h2 > 1/t)
x~N10.1)
20(1/P) (0,)
Pr (M(x) < 1/((2),, (x)) > 1/1) = 2tp)-
On the other hand, i NN I) and h(z)= (1/2t). then with probability least 1/2, h (x) > O. Suppose this is not correct, we have
E
(h(x) h²(x)) (1(x)) > 1/(20), (x) s 0}}
x-N(),1)
2 2(1(() z0.()
Pr (h(x) 1/(21), s 0) ((p)).
Since m is at least poly(d. (d. 1/p), we know that with enough high probability, least (2(d)) examples
will satisfy h(x) > 1/t(2) and at least a constant fraction of these examples will satisfy h (x) > 0. Thus, given such h with probability at least 3/4 4, we can find d examples with non-zero label in S by randomly querying (d) examples with prediction (xx) > 1/(21).
Based on this, we can give the proof of Theorem 4.2.
Proof of Theorem 4.2. Consider the problem where an algorithm wants to find & examples with non-zero labels from unlabeled examples by making queries. By Lemma D.3, it is sufficient for us to prove the hardness of such a problem by finding suitable parameters k,
Consider any deterministic learning algorithm A. Given a pool of unlabeled examples, we describe A in the following way. For every w", the implementation of can be described as a path P ((x(11, ( (x<(1, successfully finds k examples with (...,,((a)) f(fe)). Next, we consider fixed tuple of l: indices i1,..., ix and the corresponding label (1)()) : .....
())))), with length most In particular, path, along which A
can be uniquely represented as the indices i <... < is
and denote by S. the set of all (a (o(i))y()))) y(i)),.... (x((i), g g(t) that make algorithm .A succeed at positions i <... < dg. By choosing w* ~ gd-1 uniformly, we will show that the probability of S. very small. Notice that for any (2rl1), (alh))gr ) ,,.,, (x((t), ((()) E Se, it corresponds to a w" (06) for E [k], since Yiy > 0 and 4- = + Wij. We denote the marginal density on this event as [(xx()), (bx))),
unique event (2.61), ((t)))..... (zo(te), (((k)))())))) (9))), where g(a))
(++)))
Notice that Pr(S.) = S Wa se Se- bound this integral.
((((()) g(i))..... (((l)),(i)))) g(i)))). So, it is sufficient to upper
Denote by L the subspace spanned by ( ..... (in)). We consider a basis tbi...., b2 of L as follows. b = a(ii) |||=<>>)]]| and by = proje,_,
=(0)),,, where L = span(z((u) ...... (((6)=))), We know that there is unique u1 == projr, (w=) such that we z(1)) g(tz) for j E [K]. This implies that events (z((1), g g())),... (1((t), g(t)) can be precisely described as k-dimensional vector v(wr) == (Wr, bi...., wt - bb). Denote by Lo = spon(E)...... et). We have
f((z((1), g(1))) ..., (o(()), (ol)).((()) (())))) = p(proj,, (w") wv.) = p(projr, (w") = v(wr.)
where p(projr(w (w*) wI) is the density function of the event that proj (w²) = W'. w" gd-1 Consider the set Sn of all possible v(wz) such that wi corresponds to a realization ((((i)) (efli)gg(.)))))))))))) g(ft)),... f....,,.ti (z(we), g((e))). We notice that, given any v(wz) E Sn, we can uniquely recover the corresponding (z)(1), (())), (x ((+)) E So via A. This implies
Pr (Sc) = 1 Seg ((( ..., (wl , ((wn))) / s_ p(projz,(w") = o(wL)) Pr(S.)..
39

---

To upper bound (r(Sw). it is sufficient to upper bound the probability of super-set of S.. Since w x(1ا5 = g( > t" for j E [k]] we know that
(w² (x(11) W (((())T
je (a()))2 2 ) This implies that, for every realization, the square of the norm of the projection of uz onto the subspace, ||w,,,1" is
satisfies | =
B (w") A (AAT)-' Aw" =u (AAAA) | ||
2 k(t ||
where A Rxd the matrix with row vectors (61), (fx),
We next make use of the following structural lemma from [DKM24].
Lemma D.A. Let S S Rd be a m examples drawn i.i.d. from N(0, 1). Let > C 0 foror a sufficiently large constant C and = O(d/ log(m)((*))) Then, with probability at least 2/3, for every k-tuple of examples ( F& C S, || AA dl 1| S dd(()), where A E Rxd be matrix with vectors 31y-.-33i Fk-
That is to say, we are able to bound || ||, by d(1 + (t)) and thus every vector v(wz) has squared norm at least (k(t))//d() [1 + ((I/(tt))))) Since w² is uniformly chosen from the unit sphere, by Lemma B. in [KMT24c], the square norm of w* projected onto fixed k-dimensional subspace is random variable drawn from Beta distribution B -=²). By Lemma 2.2 in [DG03], have
d(t))²
d(t²)²
Pr (Iwizol 2 k(O)//0 -0/(())))) < exp (-2 d(1 + 0(1((M))) 1 - log(
d(1 + ((1/((())
(tr)dd
d(tr)2
V d(L ((1((+))))) exp( d(1 + ((L((t))))) 1))
(O((1)) exp( (t')²
2 (1- (1-0011(()31) &
(O((F)22 1 exp( - tz
2 (101119)) - (O(plog(1/))))
This implies that by choosing k: O(d/ log (tg(m) for every k tuple of indices, the probability of success for most (O(plog(1/p))) Since there are most (x) such tuples, by the union bound,
x (i)ot - cer ( (6 $ 2/3
s O(k/plog(1/p) = Old hogh (/p)). This implies that we make less than < Okk/plog( l/p)) 0(d/pplog(m/ppoyooo([111 queries, then it is hard find k Od/ log(m)(t*))
40

---

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: The abstract summarizes the results in this paper, which are thoroughly proven in the main body and supplementary material.
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 in 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 as long it 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:
The limitations are clearly stated in the statements of each theorem and are discussed in the introduction of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 few datasets 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 is low or images are taken in low lighting. Or speech-to-texx system might not be used reliably 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 fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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?
41

---

Answer: [Yes]
Justification: 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 not 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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper is theoretical in nature and 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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be 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 reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
42

---

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' is theoretical in nature and does not include code, data or experi- ments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public/gute gwwidee/Coeeeuueigeeeeeeee
cetminisssooooooooiioioooioooioi cesssonooliooo olicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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: / //nips. cc/ wwcp/bllc///aeeeccceeeceecceelee http//uudee//eeeee CCtees//ooSSubmmeecc cessinnoolcyy for more details.
The authors should provide instructions 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 are 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical in nature and 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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification: The paper is theoretical in nature and 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, statistical significance tests, 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 with given experimental conditions).
43

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out of range (c.g. negative emror 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and 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 runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / //nuurrrrsp.. oc cc/public////cccccccccoccccccccl wtw.iihiiieeeeeeeeettt
Answer: [Yes]
Justification: Our research conforms in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure 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 work is theoretical and we do not see any major or immediate implications
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.
44

---

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 work is theoretical and does not use data or models.
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: This work does not use any assets.
Guidelines:
The answer NA means that the paper does 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.
45

---

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: This work does not use any 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: This work does not involve any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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:
This work does not involve 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
46

---

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: LLMs where used only for writing assistance such as conrecting grammar errors and typos
Guidelines:
The answer NA means 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 htt/e//ips.ccc/ooeeeeeeeeeeeeeee / for what should or should be described.
47


Reviews:
[{"review_id": "lqShhGlRFP", "reviewer": "Reviewer_Jem3", "summary": "This paper studies the problem of agnostically learning general (non-homogeneous) ReLU functions under the Gaussian distribution with respect to squared loss. While recent work has shown that, in the passive learning setting, one can learn with error O(opt) + ε using a polynomial number of labeled examples, this paper focuses on the interactive setting, where the learner can query labels of selected unlabeled examples.\n\nThe main contribution is a computationally efficient algorithm that achieves error O(opt) + ε using roughly d·polylog(1/ε) + O(min{1/p, 1/ε}) black-box label queries, where p is the bias of the target function.", "questions": "Can this technique be generalized for learning more than one neuron?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The main strength of the paper is to show a sample complexity upper bound (Theorem 3.1) and an almost matching information theoretic lower bound (theorem 4.1). They also provide a separation between pool-based active learning and query learning in this setting.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in providing feedback, and we are encouraged by the positive assessment. We next address the reviewer’s question.\n\n\n>Question: Can this technique be generalized for learning more than one neuron?\n\nThe main contribution of this paper is to develop a computationally efficient, robust learning algorithm for learning general ReLU activations with optimal label complexity.\n\nThe problem of learning a linear combination of multiple ReLUs with queries is also of interest and has been studied by some of the prior works, such as [MSDH19,CKM21,DG21] under certain additional assumptions---importantly, in the realizable (aka noiseless) setting. Roughly speaking, these works first use queries to find a point where only one neuron is active and use queries to recover that neuron. While there exist some potential connections between our work and these prior works (in particular, some of our techniques could possibly be leveraged to solve the problem with more than one neuron), we want to remark that the aforementioned algorithms heavily rely on the realizable assumption and are not even robust to Gaussian random noise. So, these works on learning a sum of ReLUs in the realizable setting are not comparable to our work. We believe that developing an efficient, robust learning algorithm for more than one neuron with queries is an interesting open question that would also require significant effort and new ideas.\n\n>[CKM21] Chen, Sitan, Adam R. Klivans, and Raghu Meka. \"Efficiently learning any one hidden layer relu network from queries, 2021.\" URL https://arxiv. org/abs/2111.04727.\n\n>[DG21] Daniely A, Granot E. An exact poly-time membership-queries algorithm for extraction a three-layer relu network. arXiv preprint arXiv:2105.09673. 2021 May 20.\n\n>[MSDH19] Milli S, Schmidt L, Dragan AD, Hardt M. Model reconstruction from model explanations. InProceedings of the Conference on Fairness, Accountability, and Transparency 2019 Jan 29 (pp. 1-9)."}, {"review_id": "tQdJHa1R8w", "reviewer": "Reviewer_ezZp", "summary": "This paper addresses problem of agnostically learning a general ReLU function under the Gaussian distribution with respect to the squared loss. The authors focus on the interactive learning setting, where the learner has black-box query access to labels. The main contribution is a computationally efficient algorithm that achieves an error of O(opt) + ε with a query complexity of d*polylog(1/ε) + Õ(min{1/p, 1/ε}), where p is the bias of the optimal ReLU.  The authors complement their algorithm with a nearly-matching information-theoretic lower bound, demonstrating the near-optimality of their approach. Furthermore, they establish a strong separation result, proving that the weaker pool-based active learning model cannot achieve similar query improvements, thus justifying their use of a stronger membership query oracle.", "questions": "- How can the results be generalized to general sub-gaussian distributions over the input space Dx?\n- What are the challenges in obtaining an optimality guarantee on $opt +\\epsilon$ rather than O(opt) + \\epsilon?\n- Optimality Gap (Theorems 1.1 & 1.2): There is a small gap between the upper bound's Õ(1/p) and the lower bound's Ω(1/p^(1-o_d(1))) complexity. Do you believe this gap is an artifact of the analysis, or could there be a fundamental reason for the p^(-o_d(1)) factor?\n- What is the dependence on $\\delta$ on the sample complexity?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The paper presents near optimal sample complexity in the interactive learning setting, along with an almost matching lower bound.\n- The paper also shows the importance of the interactive setup showing a lower bound on pool-based active learning algorithm.\n- The authors start off with the simpler of setup of learning a spherical GLM and generalize to the ReLU setup later.\n\nWeaknesses:\n- The bias p, defined on line 101, is used extensively in the introduction  to showcase the main results. It would be better to define it earlier in the introduction. Also, the term ‘bias’ is used confusingly to denote both p and t in the paper.\n- Despite the simpler setup, the overall presentation is a bit too dense and it is challenging to verify the correctness of each of the claims. \n- The oracle model with the interactive querying can be a pretty strong. Would a slightly stronger pool based membership query work? For example, a local pool based membership oracle which allows the learner to query in a neighborhood of the points sampled from the input distribution Dx?", "was_revised": true, "final_justification": "I would like to keep my score and recommend this paper for acceptance.", "rebuttal": "We thank the reviewer for the constructive feedback. We will incorporate the reviewer’s suggestions regarding presentation and be more explicit about the use of notations in the future version of this manuscript. We next address the comments and questions by the reviewer separately.\n\n>Question: The oracle model with interactive querying can be pretty strong. Would a slightly stronger pool based membership query work? For example, a local pool based membership oracle which allows the learner to query in a neighborhood of the points sampled from the input distribution $D_x$?\n\nWe first want to point out that although the membership query model is a strong model in the realizable setting, in the agnostic setting, the response to a query could be arbitrary and thus captures many interesting practical applications. We also want to mention that the reviewer’s question on learning under the pool-based membership query model makes a very interesting point.  The model of local membership queries is related to the high-level idea behind our algorithm. Specifically, given a warm start, our algorithm can be implemented in the standard pool-based active learning setting. The use of the membership query oracle is only required in the stage of finding a warm-start. Intuitively, finding such a warm-start requires at least $d$ examples with non-zero labels, which in turn requires many unlabeled examples (as demonstrated in our lower bound). Using membership queries, given a random example with non-zero labels, by querying within a small neighborhood of this example, we can efficiently find the other $d-1$ examples with non-zero labels. (Such an intuition is also mentioned in the introduction of our paper for realizable ReLU regression as a motivation for our robust algorithm.) That said, a formal analysis in this setting would depend on the precise definition of the local query model. Specifically, if we are only able to query an extremely small neighborhood of a point in the pool, this would not make much difference from the pool-based active learning setting (for which we have already obtained a lower bound). It would be an interesting direction to understand the tradeoff between the query complexity and the size of the neighborhood we are allowed to query.\n\n>Question: How can the results be generalized to general sub-gaussian distributions over the input space $D_x$?\n\nTo properly answer this question, we provide the relevant context.\n\nThe goal of this paper is to get an efficient algorithm that achieves $O(opt)+\\epsilon$ error under adversarial label noise with an optimal label complexity under the Gaussian distribution. This is a fundamental problem, even if we ignore the label complexity requirement, and a line of work has focused on it in the standard passive setting. In particular, the passive learning version of the problem has been studied in several prior works, such as [ATV23,GV24,DKTZ22]. Perhaps surprisingly, it was only very recently that a (passive) polynomial-time algorithm for a general ReLU with $O(opt)$ error under adversarial label noise was developed. To date, there is no known polynomial-time algorithm  that achieves $O(opt)$ error beyond the case of the Gaussian distribution. One of the technical obstacles is that for a more general distribution $D_x$, we do not have a clean way to precisely characterize the distance between the current hypothesis and the target hypothesis when a large threshold exists in the target hypothesis. This makes it challenging to analyze the connection between the gradient in each round and the error of the current hypothesis. \n\nOn the other hand, if we are willing to relax the final error guarantee, to say $O(\\sqrt{opt})$, then it is plausible that we could design a polynomial-time algorithm for more general distribution families. In fact, prior work [DKS18] developed a polynomial time passive learner for general halfspaces (a closely related class of single-index models) under log-concave distributions to error $O(\\sqrt{opt})$. Developing a query-optimal algorithm for general ReLUs in the log-concave setting with similar error guarantees is an interesting question for future work. \nFinally, regarding the case of arbitrary sub-Gaussian distributions, we believe that robust learning with queries to error $O(opt)+\\epsilon$ with the optimal label complexity is challenging, in part due to the fact that an interactive learner usually needs to take advantage of prior knowledge of the marginal distribution.\n\n>Question: What are the challenges in obtaining an optimality guarantee on opt+\\epsilon  rather than O(opt) + \\epsilon?\n\n As mentioned in the introduction of our paper (line 28), prior work such as [DKZ20, DKR23] have shown that even for the task of agnostically learning a homogeneous ReLU, achieving $opt+\\epsilon$ error is computationally hard (specifically, it requires time exponential in $1/\\epsilon$). Furthermore, more recent work [DKKTZ24] shows that even in the membership query model, achieving $opt+\\epsilon$ error is computationally hard for proper learning (recall that our algorithm is proper). In summary, there are fundamental computational limitations to obtaining error $opt+\\epsilon$.\nIntuitively, for the task of ReLU regression, directions $w$ that give a hypothesis with $O(opt)$ error all fall in a small cone around $w^*$. So, as long as we detect this cone, we can solve the learning task. But within this cone, due to the adversarial label noise, the structure can be quite complicated and finding a direction within the cone with the smallest error can be computationally hard.\n\n>Question: Optimality Gap (Theorems 1.1 & 1.2): There is a small gap between the upper bound's Õ(1/p) and the lower bound's Ω(1/p^(1-o_d(1))) complexity. Do you believe this gap is an artifact of the analysis, or could there be a fundamental reason for the p^(-o_d(1)) factor?\n\nWe provide a high-level intuition explaining why there is a $p^{-o_{d(1)}}$ factor in our statement. Intuitively, we want to prevent an algorithm from querying examples that are too far from the origin.\nIn the realizable setting, an algorithm may only need $2$ queries to find an example with a non-zero label by querying points that are very far from the origin. To avoid this, we add a tiny fraction of noise so that examples with large norm must have $0$ labels, so that only queries within a ball with a bounded radius may have non-zero response. However, truncated within this ball, the fraction of examples with non-zero labels becomes slightly larger—since within the ball, the probability measure is slightly different from a Gaussian, and this is why we have a lower bound of $1/p^{1-o(1)}$. For large $d$, such a lower bound suffices to show the optimality of our query complexity.\n\n>Question: What is the dependence on $\\delta$ the sample complexity?\n\n It is $log(1/\\delta)$\n\n>[DKZ20] Diakonikolas I, Kane D, Zarifis N. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems. 2020;33:13586-96.\n\n>[DKTZ22] Diakonikolas I, Kontonis V, Tzamos C, Zarifis N. Learning a single neuron with adversarial label noise via gradient descent. InConference on learning theory 2022 Jun 28 (pp. 4313-4361). PMLR.\n\n>[ATV23] Awasthi P, Tang A, Vijayaraghavan A. Agnostic learning of general relu activation using gradient descent. arXiv preprint arXiv:2208.02711. 2022 Aug 4.\n\n>[GV24] Guo A, Vijayaraghavan A. Agnostic learning of arbitrary ReLU activation under Gaussian marginals. arXiv preprint arXiv:2411.14349. 2024 Nov 21.\n\n>[DKKTZ24]Diakonikolas I, Kane DM, Kontonis V, Tzamos C, Zarifis N. Agnostically learning multi-index models with queries. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 2024 Oct 27 (pp. 1931-1952). IEEE.\n\n>[DKS18]Diakonikolas I, Kane DM, Stewart A. Learning geometric concepts with nasty noise. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 2018 Jun 20 (pp. 1061-1073).\n\n>[DKR23]Diakonikolas I, Kane D, Ren L. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. InInternational Conference on Machine Learning 2023 Jul 3 (pp. 7922-7938). PMLR."}, {"review_id": "J8EsvT7Xxz", "reviewer": "Reviewer_6Jjm", "summary": "The paper studies the problem of agnostically learning ReLUs (with arbitrary biases) under the Gaussian distribution. They work in the label query model, where the learner can query an oracle for the (possibly noisy) value $y(x)$ at a datapoint $x$. The aim is to find a ReLU hypothesis $\\hat{h}$, such that the squared loss of $\\hat{h}$ is at most $O(OPT) +\\epsilon$ where $OPT$ is the squared loss of the best ReLU hypothesis. They solve this problem by designing a projected gradient descent (with warm start) based algorithm that uses $M= d\\text{poly}\\log (1/\\epsilon)+\\min (1/p,1/\\epsilon)$ queries, and runs in time $\\text{poly}(M)$ This was previously only known for the case where the ground truth ReLU was $\\max (w^* \\cdot x- t)$ with threshold $t\\leq 0$. In this work, they handle arbitrary thresholds. Here $p= Pr_{X\\sim \\mathcal{N}(0,I)}[w^*\\cdot x \\geq t]$. This is in contrast to the setting of learning with samples, where the best algorithms draw $\\text{poly}( d/\\epsilon)$ samples. Here, the authors leverage the query access model to obtain poly log sample complexity in the error parameter.\n\nThey support their upper bound with an information theoretic lower bound on the query complexity. They also show that any pool based active learner (algorithm first selects a pool of unlabelled samples and is allowed to query labels only for examples in this set) that doesnt draw a large number of unlabelled samples needs more query complexity than the learner equipped with label queries. This shows a separation in the power of the two model.", "questions": "See Weaknesses", "limitations": "This is a theoretical paper. I don't see any negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper's main algorithm (other than the initialization/ warm start) is projected gradient descent. This is a practically successful algorithm and this paper adds to the theoretical evidence supporting the empirical success of gradient descent. \n- The analysis is highly non-trivial and cleverly employs various techniques from the analysis of Gaussian space and gradient descent.\n- Achieving polylog query complexity requires a lot of fine grained work, for instance, even hypothesis selection is non-trivial (see Lemma 2.11)\n- The question of learning ReLU activations is a fundamental question in learning theory, and this paper makes progress on it.\n\n## Weaknesses\n- The analysis only works in Gaussian space and uses many sophisticated tricks from Gaussian integration. \n- The technical proofs in the appendix are very heavy in equations. I suggest adding supporting text whenever possible. \n- Section 2 contains many structural lemmas (Lemma 2.2-2.5) . Are all of these novel to this paper, or have similar analyses appeared before? For instance Lemma 2.2 seems to be a natural statement linking the loss function to the angle between the vectors  with a natural Gaussian integration based proof.\n- The use of the term \"bias\" for $p$ seems a bit confusing (as it usually refers to the threshold of the relu, or even the expectation of the function). Is this terminology standard?", "was_revised": true, "final_justification": "I should like to keep my score. The responses of the authors were satisfactory.", "rebuttal": "We thank the reviewer for their constructive feedback. We will incorporate the reviewer’s suggestions regarding presentation in the future version of this manuscript. We next address the comments and questions by the reviewer separately.\n\n>Question: The analysis only works in Gaussian space and uses many sophisticated tricks from Gaussian integration\n\nWe acknowledge that the Gaussian assumption is a strong distributional assumption. On the other hand, we note that it is one of the prototypical assumptions in our setting that has been extensively studied in prior work. Specifically, the task of designing efficient and robust algorithms for robust ReLU regression under the Gaussian distribution has been studied in a sequence of recent works in the passive setting; see, e.g., [ATV23,GV24,DKTZ22]. In fact, it was only very recently that a (passive) polynomial time learner for a general ReLU with $O(opt)$ error under adversarial label noise was developed—without label complexity constraints. Moreover, to date, there is no known polynomial time algorithm known with  $O(opt)$ error beyond the Gaussian distribution. \n\nTechnically, for a more general distribution $D_x$, we do not have a clean way to characterize the distance between the current hypothesis and the target hypothesis when a large threshold exists in the target hypothesis. This makes it hard to analyze the connection between the gradient in each round and the error of the current hypothesis.\n\n\nOn the other hand, if we are willing to relax the final error guarantee, to say $O(\\sqrt{opt})$, then it is plausible that we could design a polynomial-time algorithm for more general distribution families. In fact, prior work [DKS18] developed a polynomial time passive learner for general halfspaces (a closely related class of single-index models) under log-concave distributions to error $O(\\sqrt{opt})$. Developing a query-optimal algorithm for general ReLUs in the log-concave setting with similar error guarantees is an interesting question for future work. \n\n>Question: Section 2 contains many structural lemmas (Lemma 2.2-2.5) . Are all of these novel to this paper, or have similar analyses appeared before? For instance Lemma 2.2 seems to be a natural statement linking the loss function to the angle between the vectors with a natural Gaussian integration based proof.\n\nWhile Lemma 2.5 follows a standard analysis of projected gradient descent, Lemmas 2.2-2.4 are novel. For example, for Lemma 2.2, although prior works on learning other Gaussian single index models (such as halfspaces or homogeneous ReLUs) derived relations between the angle and error, their analysis heavily relies on the specific activation functions. On the other hand, we make use of the OU-operations to give a closed form analysis between the angle, error, and the gradient, for general activation functions. \n\n\n>[DKZ20] Diakonikolas I, Kane D, Zarifis N. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems. 2020;33:13586-96.\n\n>[DKTZ22] Diakonikolas I, Kontonis V, Tzamos C, Zarifis N. Learning a single neuron with adversarial label noise via gradient descent. InConference on learning theory 2022 Jun 28 (pp. 4313-4361). PMLR.\n\n>[ATV23] Awasthi P, Tang A, Vijayaraghavan A. Agnostic learning of general relu activation using gradient descent. arXiv preprint arXiv:2208.02711. 2022 Aug 4.\n\n>[GV24] Guo A, Vijayaraghavan A. Agnostic learning of arbitrary ReLU activation under Gaussian marginals. arXiv preprint arXiv:2411.14349. 2024 Nov 21.\n\n>[DKKTZ24]Diakonikolas I, Kane DM, Kontonis V, Tzamos C, Zarifis N. Agnostically learning multi-index models with queries. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 2024 Oct 27 (pp. 1931-1952). IEEE.\n\n>[DKS18]Diakonikolas I, Kane DM, Stewart A. Learning geometric concepts with nasty noise. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 2018 Jun 20 (pp. 1061-1073).\n\n>[DKR23]Diakonikolas I, Kane D, Ren L. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. InInternational Conference on Machine Learning 2023 Jul 3 (pp. 7922-7938). PMLR."}, {"review_id": "qrpwFlV5al", "reviewer": "Reviewer_huHJ", "summary": "This paper considers active learning, where an algorithm can query for the label corresponding to any data instance. This is a stronger oracle model than pool-based active learning where the unlabeled dataset is fixed. \n\nThe main contribution is a computationally-efficient algorithm that achieves a label complexity that nearly matches the lower bound. The authors show that this label complexity is lower than what is required for pool-based active learning, establishing the benefit of the stronger oracle model.", "questions": "* Could the authors describe the intuitions underlying the proofs? It seems that each step of the algorithm could be explained/motivated separately, and how they contribute to the overall complexity can be described in isolation. \n\n* What are the main bottlenecks in generalizing to more general marginal distributions? What is it about the Gaussian distribution that makes the analysis possible? Is there a natural extension to log-concave distributions, exponential families or some other classes of marginal distributions? While the analysis' being focused on Gaussian marginals is understandable, this would help better understand the intuition behind the improved label complexity that arises in the considered setting.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n* This paper identifies a clear gap in the literature and closes this gap. I especially value how the authors demonstrate improved label complexity that comes with the stronger oracle than pool-based active learning. \n\n**Weaknesses**\n* The paper is very dense. The introduction is a summary of the main results and a comparison with prior work, and there is no separate related works section. \n\n* The techniques used in this paper are specific to a Gaussian marginal distribution. The proofs rely heavily on the fact that they are Gaussian, e.g., relating to the Ornstein–Uhlenbeck semigroup. The proofs are very technical, with limited insights into how the arguments used in the paper extend to different marginals. It would be nice if the authors could describe some intuition on what the Gaussian marginals entail - is it expected that the problem becomes harder or easier for other marginal distributions?\n\n**Some Comments**\nThis paper solves a technically involved and important problem, and so it is understandable that the analysis is not too easy to follow. However, I find the Appendix to be a better description of the ideas underlying the algorithm and proof. I believe the paper presentation can be improved by modifying Section 3. For example, the authors could first clearly write out the main steps and then describe each step in detail in different subsections.", "was_revised": true, "final_justification": "I assign high weight to the paper's technical novelty. The paper presents a novel and interesting result. \n\nMy primary concern was the lack of intuition behind the main proof, which is significant for a theory paper. The authors' rebuttal successfully addressed this by providing a high-level summary. Because the authors have shown that they are able to provide the needed intuition, I recommend acceptance with the expectation that this will be integrated into the camera-ready version.", "rebuttal": "We thank the reviewer for the positive evaluation of our work and constructive suggestions. Due to the space limitations, we were not able to provide a detailed description of the algorithm in Section 3 but only the key ideas and high-level intuition. We will provide a more detailed description in the revised version of the manuscript.\n\n>Question:Could the authors describe the intuitions underlying the proofs? It seems that each step of the algorithm could be explained/motivated separately, and how they contribute to the overall complexity can be described in isolation.\n\nHere, we give a brief summary of the intuition behind our main algorithm; the detailed descriptions can be found in Section 3 and Appendix C.3. \n\nOur algorithm proceeds in a sequence of rounds, improving parameters $(r,t)$ and the direction w separately in each round of update. To start with, we will guess a pair of $(r_0,t_0)$ that is non-trivially close to $(r*,t*)$.\nSince the guessing step has a probability of success at least $1/polylog(R/\\epsilon)$, we can run the same algorithm poly-logarithmically times to boost the probability of success. So, we can assume that we start with a good $(r_0,t_0)$, and we use it to get a warm start $w_0$ by making at most $1/p + d polylog(R/\\epsilon)$ queries. \n\nWith a good warm start $(r_0,t_0)$ and $w_0$, we improve these parameters via a gradient method in each round. Specifically, in each round, we maintain a pair of $(r_i,t_i)$ and $w_i$ and assume that $(r*)^2\\theta_i^2 \\le B_i^2$, where $B_i$ is some suitable constant used for measuring the quality of $w_i$. \n\nThe intuition here is that if the current $(r_i,t_i)$ is not good enough, then the gradient of $w_i$ will not point in the wrong direction, but only have large variance. So, if $(r_i,t_i)$ is suitably good, we can use $d polylog(R/\\epsilon)$ queries to get a relatively good estimation of the gradient of $w_i$ and improve it so that $(r*)^2(\\theta_{i+1}^2) \\le B_{i+1}^2$, for some $B_{i+1}<B_i$. On the other hand, if $w_i$ has already been improved well enough, we are able to estimate the gradient $(r_i,t_i)$ using $polylog(R/\\epsilon)$ queries. By comparing the length of the gradient of $(r_i,t_i)$ with $B_i$, we are able to tell if the current $(r_i,t_i)$ meets the requirement for updating $w_i$. If it meets the requirement, we do not update $(r_i,t_i)$; otherwise, we run a gradient step for polylogarithmically many rounds to improve $(r_i,t_i)$ so that it meets the requirement for updating $w_i$. In summary, in each round of update we make $d polylog(R/\\epsilon)$ queries. \n\nAfter polylogarithmically many rounds, we improve $w$ to the desired accuracy. But due to noise, if $t*$ is large, we are only able to get some $(r,t)$ so that it is within the $\\epsilon polylog(R/\\epsilon)$ neighborhood of $(r*,t*)$. Since there are only two parameters, by using a brute-force approach, we can find polylogarithmically many hypotheses such that one of them is guaranteed to be good enough. Finally, by a hypothesis selection procedure over the candidate hypotheses, we find a good hypothesis. This gives the final query complexity.\n\n>Question:The techniques used in this paper are specific to a Gaussian marginal distribution. The proofs rely heavily on the fact that they are Gaussian, e.g., relating to the Ornstein–Uhlenbeck semigroup. \nWhat are the main bottlenecks in generalizing to more general marginal distributions? What is it about the Gaussian distribution that makes the analysis possible? Is there a natural extension to log-concave distributions, exponential families or some other classes of marginal distributions?\n\nWe acknowledge that the Gaussian assumption is a strong distributional assumption. On the other hand, we note that it is one of the prototypical assumptions in our setting that has been extensively studied in prior work. Specifically, the task of designing efficient and robust algorithms for robust ReLU regression under the Gaussian distribution has been studied in a sequence of recent works in the passive setting; see, e.g., [ATV23,GV24,DKTZ22]. In fact, it was only very recently that a (passive) polynomial time learner for a general ReLU with $O(opt)$ error under adversarial label noise was developed—without label complexity constraints. Moreover, to date, there is no known polynomial time algorithm known with  $O(opt)$ error beyond the Gaussian distribution. \n\nTechnically, for a more general distribution $D_x$, we do not have a clean way to characterize the distance between the current hypothesis and the target hypothesis when a large threshold exists in the target hypothesis. This makes it hard to analyze the connection between the gradient in each round and the error of the current hypothesis.\n\n\nOn the other hand, if we are willing to relax the final error guarantee, to say $O(\\sqrt{opt})$, then it is plausible that we could design a polynomial-time algorithm for more general distribution families. In fact, prior work [DKS18] developed a polynomial time passive learner for general halfspaces (a closely related class of single-index models) under log-concave distributions to error $O(\\sqrt{opt})$. Developing a query-optimal algorithm for general ReLUs in the log-concave setting with similar error guarantees is an interesting question for future work.\n\n\n>[DKZ20] Diakonikolas I, Kane D, Zarifis N. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems. 2020;33:13586-96.\n\n>[DKTZ22] Diakonikolas I, Kontonis V, Tzamos C, Zarifis N. Learning a single neuron with adversarial label noise via gradient descent. InConference on learning theory 2022 Jun 28 (pp. 4313-4361). PMLR.\n\n>[ATV23] Awasthi P, Tang A, Vijayaraghavan A. Agnostic learning of general relu activation using gradient descent. arXiv preprint arXiv:2208.02711. 2022 Aug 4.\n\n>[GV24] Guo A, Vijayaraghavan A. Agnostic learning of arbitrary ReLU activation under Gaussian marginals. arXiv preprint arXiv:2411.14349. 2024 Nov 21.\n\n>[DKKTZ24]Diakonikolas I, Kane DM, Kontonis V, Tzamos C, Zarifis N. Agnostically learning multi-index models with queries. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 2024 Oct 27 (pp. 1931-1952). IEEE.\n\n>[DKS18]Diakonikolas I, Kane DM, Stewart A. Learning geometric concepts with nasty noise. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 2018 Jun 20 (pp. 1061-1073).\n\n>[DKR23]Diakonikolas I, Kane D, Ren L. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. InInternational Conference on Machine Learning 2023 Jul 3 (pp. 7922-7938). PMLR."}]

Author rebuttal:

Meta-review: The paper presents query-based algorithms for learning ReLUs, and provide matching lower bounds. All reviewers acknowledge the technical novelty of this paper, and the intuition of the proof was explained in the rebuttal stage. The authors are encouraged to include the explanations in the final version.
Decision: Accept (poster)