Agnostic Learning of General ReLU Activation Using Gradient Descent
Authors: Pranjal Awasthi
Alex Tang
Aravindan Vijayaraghavan
Venue: ICLR 2023 poster (2023)
Keywords: agnostic learning
learning ReLU
global convergence
learning theory

Abstract: We provide a convergence analysis of gradient descent for the problem of agnostically learning a single ReLU function under Gaussian distributions. Unlike prior work that studies the setting of zero bias, we consider the more challenging scenario when the bias of the ReLU function is non-zero. Our main result establishes that starting from random initialization, in a polynomial number of iterations gradient descent outputs, with high probability, a ReLU function that achieves an error that is within a constant factor of the optimal i.e., it is guaranteed to achieve an error of $O(OPT)$, where $OPT$ is the error of the best ReLU function. This is a significant improvement over existing guarantees for gradient descent, which only guarantee  error of $O(\sqrt{d \cdot OPT})$ even in the zero-bias case  (Frei et al., 2020). We also provide finite sample guarantees, and obtain similar guarantees for a broader class of marginal distributions beyond Gaussians. 

Published as a conference paper at ICLR 2023
AGNOSTIC LEARNING OF GENERAL RELU ACTIVATION USING GRADIENT DESCENT
Pranjal Awasthi
Alex Tang' Northwestern University
Aravindan Vijayaraghavan'
Google Research
Northwestern University
pranjalawasthie @ google.com
aravindv Soaiindv@nnttwwsttm...eee
ABSTRACT
We provide convergence analysis of gradient descent for the problem of agnosti- cally learning single ReLU function under Gaussian distributions. Unlike prior work that studies the setting of zero bias, consider the more challenging scenario when the bias of the ReLU function is non-zero. Our main result establishes that starting from random initialization, in a polynomial number of iterations gradient descent outputs, with high probability, ReLU function that achieves an error that is within a constant factor of the optimal i.e., it is guaranteed to achieve an error of O(T,T), where OPT is the error of the best ReLU function. This is a significant improvement over existing guarantees for gradient descent, which only guarantee error of O(vd. OPT) even in the zero-bias case (Frei et al. 2020p. We also provide finite sample guarantees, and obtain similar guarantees for broader class marginal distributions beyond Gaussians.
INTRODUCTION
Gradient descent forms the bedrock of modern optimization algorithms for machine learning. Despite a long line of work understanding and analyzing the gradient descent iterates, there remain several outstanding questions
whether they can provably learn important classes of problems. In this work we study one of the simplest learning problems where the properties of gradient descent are not well understood, namely agnostic learning of single ReLU function.
More formally, let D be distribution over Ed x RR A ReLU function is parameterized by (w. b where v E IRd and bw E IR. For notational convenience, we will consider the points to be IR++1 by appending z with fixed coordinate 1 as (z. 1). Let D be the distribution over Rd+1 x IR induced by D. We define the loss incurred at (Ø, bw) be
E [a(w I ++ b..)) y)² = 2 (x.N)~ [(w)= = 2 (Z.g)=D
[oo x:) y)²
Here (xx) max(x, 0) is the standard rectified linear unit popularly used in deep learning. The goal in agnostic learning of a ReLU function (or agnostic ReLU regression) to design a polynomial time learning algorithm that takes as input i.i.d. samples from D and outputs (w. bw) such that L(w) compares favorably with OPT that is given by
1
OPT = min w=( 2 (N (o x)) y)
E.
Here the hypothesis set that algorithm competes with is the set of ReLU units with parameters (w, bw) with the relative bias |bwl/[|[@] la being bounded. This is non-trivial and interesting regime; when the bias is too large in magnitude the optimal ReLUU function fitting the data is either the constant function almost everywhere,
linear function almost everywhere.
This agnostic learning problem has been extensively studied and polynomial time learning algorithms exists for variety of settings. This includes the noisy teacher setting where Ely [x] is given by
"The last two authors are supported by the National Science Foundation (NSF) under Grant No. CCF-1652491 and CCF 1934931. The last author also funded by a Google Research Scholar award.

---

Published as a conference paper at ICLR 2023
ReLU function Kakade et al. (2011) Mukherjee & Muthukumar (2020) and the fully agnostic setting where no assumption on y is made (Goel & Klivans, 2019 Diakomikolas et all, 2020). In recent work (Frei et al., 2020) analyzed the properties of gradient descent for the above agnostic learning problem when the bias term is assumed to be zero. The gradient descent based learning algorithm corresponds to the following sequence of updates starting from suitable initializer wo:
Wr+1 = Wt: - L The work of Frei et al. (2020) proved that starting from zero initialization and for distributions where the marginal of satisties some mild assumptions gradient descent iterates produce, in polynomial time, a point wr such that L(wr) = O(VOPT) when the domain for x is bounded (it is instructive for this bound to think of OPT < 1; the general expression is more complicated with some additive terms and dependencies on
quantities).
While the above provides the first non-trivial learning guarantees for gradient descent in the case of ag- nostic ReLU learning. it suffers from a few key limitations. The result of Frei al. (2020) only applies in the setting when the distribution has a bounded domain and when the bias terms are zero. When the distribution is not bounded, the error of OVOPPT) also includes some dimension-dependene terms; e.g., when the marginal of E is a standard Gaussian (0, Laxa), it gives a O(Vd- OPT) error. Moreover, there is natural question of improving the bound of O(VOPT) on the error of gradient descent (since the most interesting regime of parameters is when OPT & 1). This is particularly intriguing given the recent result of Diakonikolas et al. (2020) that shows that, assuming zero bias, gradient descent on a convex surrogate for L( (w) achieves O(OPT') error. This raises the question of whether the same holds for gradient descent on L(w) itself. In another recent work, the authors in Vardi et al. 2202] are able to provide convergence guarantees for gradient descent in the presence of bias terms, but under the strong realizability assumption, i.e, assuming that OPT
To summarize the existing guarantees, to the best of our knowledge. (i) there are no existing guarantees for any polynomial time algorithm (including gradient descent) for agnostic learning of ReLU function with bias, and (ii) even in the zero bias case, there is no existing guarantee for gradient descent (on the standard squared loss) that achieves O(OPT) error.
1.1 OUR RESULTS
In this work we make progress on both these fronts, by improving the state of the art of guarantees for gradient descent for agnostic ReLU regression. In particular, we show that when the marginal of x is a Gaussian, gradient descent on L(w) achieves an error of O(OPT), even under the presence of bias terms that are bounded. The (OPP)) guarantee that get even in the zero bias answers an open question raised in the work of Frei et al. 2020). There are also no additional dependencies on the dimension. Given the recent statistical query lower bound of Goel & Klivans (019) that rules out an additive guarantee of OPT + & for agnostic ReLU regression, our result shows that vanilla gradient descent on the target loss already achieves near optimal error guarantees. Below we state our main theorem. For convenience we assume that ||ō|| (the optimal weight, i.e. v = (τ, b,)) E H such that L(u)= = -OTT, is constant; A shows why this without loss of generality.
Theorem 1.1. Les C1 2 I, C2 > 0, C3 > 0 be absolute constants. Let D be a distribution over (Z, E Rd x I where the marginal over ã is the standard Gaussian (0, Let H = {w (w, bw)) || E [1/C1, C1), |bطl I }2). and consider population gradient descent iterates: W++1 = wi 1) (Lw.)) For suitable constant learning rate n,, when starting from wp (wa, 0) where ün is randomly initialized from a radially symmetric distribution, with at least constant probability C3 > 0 one of the iterates wr of gradient descent after poly(d, { steps satisfies L(WT) = O(OPT) +
Please see Section for the more formal statement and proof. Note that the above guarantee applies to one of the intermediate iterates produced by gradient descent within the first poly(d, 1/e) iterations. This is consistent with other convergence guarantees for gradient descent in non-realizable settings where last iterate guarantees typically do not exist Frei et al. (202)). One can always pick the iterate among the first (oly 1/E) steps that has the smallest loss on an independent sample from the distribution D.
The above theorem proves that gradient descent obtains a bound of O(OPT) when the relative bias of the optimal ReLU function is bounded (recall that ||00| (1) for the optimal classifier without loss of generality from Proposition C.T). Note that we do not constrain the gradient updates to remain in the set H. This result significantly improves upon the existing state-of-the--rt guarantees (rei et al.
2

---

Published as a conference paper at ICLR 2023
(2000) of O(vd OPT) for gradient descent even when specialized to the case of ReLU activations with no bias. Further this gives the first provable guarantees in the setting with non-zero bias. Our improved bound of O(OPT) enror even with non-zero bias involves several new ideas. At high level there are two main ingredients that allow us to do beyond the previous work: (1) an improved analysis for gradient descent in the agnostic case that in particular avoids any dimension-dependenn factors, and (2) a new "multiscale" random initialization scheme with a stronger guarantee for the initializer. We outline these in more detail Section and Section respectively.
We remark that some of the assumptions in Theorem are made with a view towards a clearer exposition, and similar guarantees hold more general settings. While the above theorem gives guarantees for gradient descent on the population loss function L(w) (as in Vardi et al. (202T)) we also prove guarantees for the empirical loss function in Section [ Moreover while the above Theorem I.J Jasumess Gaussian marginals (as this already illustrates the improvements guarantees in a basic and well-studied setting), these techniques extend broader class of distributions that we describe next.
1.2 GUARANTEES BEYOND GAUSSIAN MARGINALS
The above algorithmic result can be generalized to broader class of marginals than Gaussians, that we call O(l)rrea marginals.
((1) marginals: Assumptions about the marginals over ă We make the following assumptions about the marginal distribution D over ž E Id:; there exists absolute constants 31, 3/2 82, B3, B1, As > and Bo : RR + Rt, such that
(i) Approximate isotropicity and bounded fourth moments: for every unit vector u Rd. E BW (),, E [1/8g, 32], and ER [(u, 3) S $4.
(ii) Anti-concentration: there exists an absolute constant B3 > such that for every unit vector u E Rd and 8 0,
sup P (ū, FER TND
5, + 8)] < min minn (B36, 1}-
(iii) Spread out: there exists 30 : R4 + R4 such that Bo ((b))) > 0 is constant when [6,] is constant, and
Ve S
E
a bb) 2 (o((b..))
I-D.
(iv) 2-D projections: In every 2-dimensional subspace of TRd spanned by orthonormal unit vectors ú1, Ug E Rd, we have set Gü
C R such that,
P
j1g
ã E Güynüz]
= 1 o(1,, and
(I)
RND.
Vt E G Nar
E Dr
o (
x)
2 Bs
E DnD
[a })
(2)
In other words, the conditional expectation of o F) is not much smaller after conditioning
on the projection in an orthogonal direction 0g for most values of ūz x. Note that for Gaussian (0. 7), the r.v.s ü, ū J. are independent, so this condition holds with B3 = and Gāy ,2 Te.
We remark that Gaussian distribution (O, I) is (re)-regular i.e., all the constants B1, 32, 32 As 1, ,333 < 2, and Ba (b..) = E (((.1. [g + b.)] > 0 for all b, E (-o0, oo); in fact 8o is an increasing function that is 0 only at - oc. We also note that assumptions of this flavor have also been used in prior works including Vardi al. (2021), which inspired parts of our analysis. In particular, Vardi al. (202T) assume a lower- bound on the density for any 2-dimensional marginal; our assumption (4) the 2-dimensional marginals is qualitatively weaker (it is potentially satisfied by even discrete distributions), and morcover we only need the condition to be satisfied for a large fraction of values of ū J (and not all). See Section B for the generalized version of our main theorem.
3

---

Published as a conference paper at ICLR 2023
2 RELATED WORK
The agnostic ReLU regression problem that we consider has been studied in a variety of settings. In the realizable setting or when the noise is stochastic with zero mean, i.e., Ely[æ] is ReLU function, the learning problem is known as isotonic regression and can be solved efficiently via the GLM-tron algorithm (Kakade et al. 2011 Kalai & Sastry 2009). Distributions generated by a 1-layer ReLU neural network under the realizable setting can also be learned efficiently (Wu et al. 2019). In the absence of any assumptions on the distribution of y|a, the work Goel & Klivans (019) provided
an efficient algorithm that achieves O(OPT2/3) + E error under Gaussian and log-concave marginals in the zero-bias setting. The authors also show that it is hard to achieve an additive bound of OPT + via statistical query (SQ) algorithms Kearns & Valiant (1994). For the case of zero bias and any marginal over the unit sphere, the work of Goel et al. (017)) provides agnostic learning algorithms for the ReLU regression problem that run in time exponential in 1/e and achieve an error bound of OPT The recent work of Diakonikolas et al. (020)) improved the upper bound of Goel & Klivans (219 to O(OPT) + E via designing an efficient algorithm that performs gradient descent on convex surrogate for the loss L. (w)); very recently they also obtained near optimal sample complexity with a regularized loss Diakonikolas et al.) 2022). Note that all of the above works that study the fully agnostic setting consider the setting where the bias terms are not present.
Recent works of Frei et al. (2020); Vardi et al. (202T) consider analyzing gradient descent for the ReL.U regression problem. Frei et al. (2020) provides an O O(VOPT) guarantee (along with some additional problem-dependent terms) for the case of zero bias and bounded distributions. When considering distributions such as the standard Gaussian (0, I) the bound of Frei et al. (2020) incurs a dimension dependent term of the form O(Vd- - vOPT) in the error bound. Vardi et al. (021) provides a tighter analysis that also extends to the case of non-zero bias. However the analysis only applies in the realizable setting, i.e., when OPT is zero. Our main result provides improved bounds over these works by providing a dimension independent error bound that applies to the case of non-zero bias well.
There is also a long line of work analyzing gradient descent for broader settings. The works of Ge et al. 2015 2018); Jin et al. (2017); Anandkumar & Ge (016)); (Soltanolkotabi (2017) show convergence of gradient descent updates to approximate stationary points in non-convex settings under suitable assumptions on the function being optimized. Another line of work considers the global convergence properties of gradient descent. These works establish that gradient descent on highly overparameterized neural networks converges the global optimum of the empirical loss over a finite set of data points (AllenZZhu et al., 2019 Du et al., 2019
Jacot et al., 2021 Zhong
al. 2017 Chizat & Bach 2018: Lee et al.) 2019 Arora et al., 2019). Yet another line of work
considers the realizable setting where data is generated from an unknown small depth and width
neural network. These works analyze the local convergence properties of gradient descent when
starting from suitably close initial point (Bartlett et al. 2018 Zou et al. 2020).
3 PRELIMINARIES
We consider agnostically learning a single ReLU neuron with bias through gradient descent under the supervised learning setting. We assume we are given data (x,y), where x E RR++1 follows the standard Gaussian distribution (0, 7) in the first d dimensions and the d + I'th dimension being constant 1. We also assume the labels E RR are arbitrarily correlated with æ and o x).
Note that throughout the paper, we will use w. 0, H to denote the first d dimensions of W. U, respectively, with the last dimension of u being bm E IR (similarly for b, E R). Therefore, w x is in fact w bw-
In the analysis, we will compare the current iterate w to any optimizer of the loss L(w).
E == arg min L(w), where L(w) (x.0)~D WEH
[oo x)) - w/²
and the hypothesis set H = {w = (w, bw) || E ltf CiJ, bul S C2)), where C₁ and C2 are absolute constants. This is to ensure that the relative bias |b, /b,0l/1|/@ll is bounded; as described earlier Appendix Clllows to assume ||تر||| E (2f G1 without loss of generality.
4

---

Published as a conference paper at ICLR 2023
As in the agnostic setting, there may be that achieves zero loss. We can split the loss function L ((w) into two components, one of which is F(w) defined by
_ د (o(w" (x) x) 10)--((0) a(v' -ov''(())))) 2)){. VF(w) = E [orw T x) -o(oo' -ov'=)))o''' x)o]
F(w) =
(4)
We will often refer to F(w) as the realizuble loss, since it captures the difference between w and v; in the realizable setting L(w) F(w). Note that F(v) O.
Gradient of the Loss. The gradient of L(w) with respect to w is
V((w) = E (o(w x) y) (w x)x
(5)
where o'(-) is the derivative of a()), defined as (z) = 1f > 0}. Note that the ReLU function (z) differentiable everywhere except
O. Following standard convention in this literature, we define o' o0) = 1. Note that the exact value of o' d0()) will have no effect on our results.
We can also decompose V((w) as
VL(w) (o(w) x) - olu x))a (w x)x) + E (o(u y)o x))
(6)
Therefore, VL(w) = VF(w) + E (o(u x) - v)o x)
(7)
Gradient Descent. Finally, our paper focuses on the standard gradient descent algorithm with ge
fixed learning rate 17 > O. We initialize at some point wp IR+1), and at each iteration E N we have 1 = W/ F(we). We do not optimize the iteration count in this paper; hence it will be instructive to think of
non-negligible parameter that can be set to be sufficiently small (e.g.. an inverse polynomial for polynomial time guarantees).
Simplification. For sake of exposition we will assume that | through when ||ā]|a E [1/O], Ci] as well. Moreover Proposition C. shows that assuming that |o]|2 normalized without loss of generality. Note that we cannot make such simplifying assumption about the vectors wA= = (w,, bw) in the intermediate iterations.
the same analysis goes
Finally, please see Section B for the weaker distributional guarantees and guarantees.
OVERVIEW OF THE ANALYSIS (PROOF OF THEOREM 1.1)
We now provide an overview of our analysis. For complete proofs of the lemmas and propositions, please refer to the supplementary material (Appendix Recall that our goal throughout the learning process is to find E Rd+1 such that L(w) achieves comparable performance to OPT L(v). In order to accomplish this, we aim to find w such that it is close to v, i.e. ||w - ell is small. Note that approximating suffices to achieve an error close to OPT, since we can upper-bound L(w) as
L(w)= = うタ
1
= B (T
1
oo (() w)²]
[ - o =))²² + [[o((TTT) -) v)2 = (F) + 20PT
$ 2
2
2
through Young's inequality. The realizable portion of the loss F(w) becomes O(OPT) when || -vl < O(VOPT) (see Lemma 4.4 for proof), and consequence we will get O(OPT) error in total.
To formalize intuition above, adopt similar proof strategy used in Frei et al. (020h. Namely, we argue that when optimizing with respect to the agnostic loss L(w;), we are always making some non-trivial progress due to decrease in l|w, e|l and due to decrease in F(w,) (which is just the realizable portion of the loss). Moreover, whenever we stop making progress, we will argue that at
this point either lw; el < O(VOPT) or [V:)):) < O(VOPT); in both cases, this iterate already achieves an error of ((PPT) due to Lemma 4.4 and Lemma
5

---

Published as a conference paper at ICLR 2023
Challenges in arguing progress. At a high-level the analysis of gradient descent follows similar approach to FoeF et al. (020) which only handles zero bias. Yet there are several new ideas needed to obtain the stronger ((PP)) guarantee even for the zero-bias case. Morcover, allowing non-zero bias terms imposes extra technical challenges. For example, the probability measure of {wTx 2 0, 2 0f under Gaussian distributions, which is vital to deriving the gain in each gradient descent step, does not have a closed-form expression when bias is present. Furthermore we cannot afford to lose any dimension dependent factors assume boundedness. Thus, address these difficulties, more detailed analyses (e.g. Lemma
are needed to facilitate our argument.
Moreover tackling non-zero bias terms requires additional assumptions when initializing wo as well. The initializer finds a wh such that F(wo) is strictly less than F(O) by constant amount 5 > 0 (this inspired by Vardi et al. (2021), however in their case can have an inverse-polynome dependence on the dimension In fact our multiscale random initialization and the improved analysis is crucial to obtaining
bound on the error. The high-level intuition behind why this property is useful is that it ensures that gradient descent does not get trapped around highly non-smooth region (e.g. when w = 0) by making it start at somewhere better than it, so that w keeps Moreover, in our
comeenioon-inependeen
moving closer Vardi et al. ) because of the agnostic setting. This is because Vardi et al. (202T) heavily relies on the realizability assumption to simplify its analysis.
the analysis is more challenging implement compared to
We also highlight our improvements on the dependency of the dimension d. In previous works, the guarantees of the algorithm has dependence d either explicitly or implicitly. For instance, in Frei al. 2020 the O(vOPT) guarantee for ReLU neurons includes coefficient in terms of 8 (the upper-bourd for | [), which for Gaussian inputs is in fact vd: or for example in Vardi al. 202 the gain for each gradient descent iteration comes with a dependency on (the upper-bound bound for ||=|]) of e-8, which for Gaussian is d-4, In contrast, we avoid such dependencies on the dimension d in order to obtain our guarantees.
We first establish two important lemmas we will later utilize in proving progress in each iteration. As stated in the preliminaries, we assume in the rest of the section that | = 1. The first lemma gives lower bound on the measure of the region where both ou 2) and (w) x)) are non-zero. Our inductive hypotheses will ensure that this lower bound is constant (if 16 is a constant).
Lemma 4.1 (Lower bound on the measure of the intersection). Suppose the marginal distribution Dr over T. is 0(1) There exists an absolute constant > such that for all 8 > 0, if F(w)= < F0) then
82
Plw 2 0,0
0J
(8)
+ bb, 12)2
With Lemma the following lemma allows to get improvement on the realizable portion of the loss function as long as the gradient is non-negligible. We state and prove this lemma for the general case of ((1)-regllar marginal distributions.
Lemma 4.2 (Improvement from the first order term). Suppose the marginal over T. is ((1)--egulaa
There exists absolute constants C1, 02 > such that for any 8 > 0, if |1]|2, |1l| l2 S B and
F(w) < F F(0) ö, then (VF(w), w v) 2 ?|l vll2, where y 13
6
The constants C1, C1 depend on the constants $1, 32, 84 etc. in the regularity assumption of D.. We remark that for our setting of parameters (1(1) and = O(1), and hence we will conclude that (VF, w v) 2 Q(Ilw v1l2). Please refer to Appendix A for all the complete proofs.
4.1 MAIN PROOF STRATEGY
With these two key lemmas, are now ready discuss the proof overview of the main theorem (Theorem L.I. We inductively maintain two invariants in every iteration of the algorithm:
(A) || u||2 S 0(), and (B) F(0)- - F(w,) = 2((1)
These two invariants are true at t = 0 due to our initialization Wn- Lemma B.3 guarantees with at least constant probability 2(1), both the invariants hold for wo- The proof that both the invariants

---

Published as a conference paper at ICLR 2023
continue to hold follows from the progress made by the algorithm due to decrease in both ||a, e/12 and F(we) (note that we only need to show they do not increase to maintain the invariant).
The argument consists of two parts. First, assuming F(w)) F(0) 8 holds (for some constant > 0), we establish that whenever wwy - 0 > 7OPT for some constant y > 0, gradient descent always makes progress i.e. || -012 || e1I² is lower bounded. Next, we argue that if wo is initialized such that F F(w)) _ F(0) 5 for some constant > O, then throughout gradient descent F(w)) always decreases, i.e. the inequality F(wx)= - F(wo) S F(0) - ô always holds.
However, unlike Vardi et al. (2021 where they focus on the realizable setting, analyzing gradient descent on the agnostic loss ((w) is more challenging, since the update depends on V (I(w)) and not FFw)). In fact, the additional term from the "non-realizable" portion of the loss L(w) can overwhelm the contribution from the realizable loss when either F/ S O(VOPT) or ||wl, - ull2 I ((VOPT). The following two lemmas argue that in both of these cases, the current iterate already achieves (OOPT) error (and this iterate will be the T that satisfies the guarantee of Theorem I.1
Lemma 4.3 (Success if |[F]| & ((VOPT)). Suppose B,5 > O are constants such that |1ll2, |wll2 S B and F(w) I F(0) 8. Then there exists a constant Cg such that if [V)(w)] S CGVOPT then || - ell2 S O(VOPT).
Proof. We can first apply Lemma 4.2 to conclude that (VF(w). w o) 2 >|l w u1 for some constant 7 > 0 (since B,6 > 0 are constants), hence we have /VF(())ll - (VF(w), v) 2 7| - u1I?. Thus | - 2112 = ((VOPT) which implics the lemma.
We now argue that if || - -il < this is stated and proven for ((1)-regula distributions.
O(VOPT), then F(w)) - O(OPT) through the following lemma;
Lemma 4.4 (Small ||mo, w|l implies small F(w:)). Assume D2 is ((1)-regular with parameters defined above. If ||u, - ul12 s 0(VOPT + for some & > 0, then F(w,)= I 0OPPT + +))
Proof. Since ReLU function is 1-Lipschitz (i.e. la(z) o(2') s 1/2 1--- - z1),
F(w:) = E [o(w]] x)) a(v x=))² -
1 E
[w, x v [x)²]] |/0 - u112
(n T 2)²
2 E
2
where we defined u get
Wi Iw--ell
hence the last equation. Now, notice by using Young's inequality, we
E
[[ xxT)
E
( ā + bun)
+b,) < 2E (
x)p] + 20 S 2,32 + 20 < 0(1)
due to the regularity assumption on D.. Hence
||w; - =
F(we)= S
0(1) < O1I -013) < 0(OPT +s)
2
which concludes the proof.
Proving progress in ||w, ull and F(w:). To show ||, uil decreases, we establish the following lemma.
Lemma 4.5 (Decrease in [|we-vl] - el). Assume at time t, F(w:) S F(0) - 8 where 5 >> 0 is a constant
and D= is Oel)-rrgllar For constants n
0.05->
dāg Cp = //[ 10082/ 7-90
+ +10
B2 )
92/7
19.8 B2 where yy is defined as in Lemma 4.2 for some
Ill w112
> - C +c),
then [w - u1|2 < ||1. - u1|2 - n/C (OPT +e).
As direct consequence of Lemma 4.5 we obtain the following inductive statement: for every t,
either (a) |wu - - || v
nC(OPT + =) is true for some constant C 0 or (b) - (OPT + +)) holds. Observe that when (b) holds Lemma (.4 implies the loss is O(OPT); ;; hence we need only assume at time (b) does not hold yet, thus suffices focusing on
I|w, r||2 < 0(
showing (a) is true. Additionally, note at each timestep i,
ww 0112 ||w+41
2112 2n [(we), wi v) - - (
7

---

Published as a conference paper at ICLR 2023
Therefore, dower-bounde 1 - - we will give lower bound for (VL(wr), We -) and an upper bound for || VL(w))]l To show that F(w)) decreases we show that at time t, if gradient descent continues to make progress towards v, then (( I F(w,) S F(0) 8. The progress in
F(w) follows crucially relies on Lemma 4.2 Please see Appendix A in the supplementary material
for the detailed proofs.
RANDOM INITIALIZATION
We now prove the initialization lemma assuming weak conditions on the marginal distribution over I E Rd which is Dz (recall that the standard Gaussian N(0 7) also satisfies all of the properties). We will initialize w (t², bw) with b.. 0 and ū drawn from spherical symmetric distribution Dw. The length is chosen from the distribution D, so that it has non-negligible probability in any constant length interval (a) ||2 02 (g]|=[l2) where 02 > 01 > 0 are constants: our specific choice picks the correct length scale with non-negligible probability, and is reasonably spread out.
Our new random initialization and the improved analysis are crucial in obtaining the O(OPT) guarantee even with non-zero bias. Our multiscale random initialization scheme tries out different length scales and ensures that with non-negligible probability we get an initializer that satisfies the required property. For the correct guess of length scale of ||l|| (up to factor of 2), our improved analysis (see (TO) shows that the random spherically symmetric initialization with constant probability produces an initializer with F(w)= - F()) )1) When we have unknown length scale || E [1/M, M). the random initialization can try out the different length scales in geometric progression i.e., the length scale is chosen uniformly at random from {2 1 : E Z, log M S S log M).
Multiscale random initialization We are given a parameter M such that ||v||2 E [2- log M. 2 MM (note that M can have large dependencies on d and other parameters; our guarantees will be polyno- mial in log M). A random initializer w = (18, 0) is drawn from D Panknown (M) as follows:
1. Pick j uniformly at random from { [log M1, [log M + L. ...., 1,, 1, ...,, [log M1}.
2. P E Ry is drawn according to Dp as follows: we first pick g ~ NO,, 1) and set = 2 [g]-
3. A uniformly random unit vector à E Rd is drawn and output w pro The initializer is (17, 0).
We prove the following claim about the multiscale random initializer.
Lemma 5.1. There exists ci (v), ca(v), es(v) > O which only depend on b / (and not on the dimension), and are both absolute constants when [bal/|/Í|| 0(1), such that the following holds. When w (w, by = O) is drawn according to the distribution Dunkuowo (M) described above for some given M 2 satisfying [|l||2 E [L/M, M). Then with probability at least 02(v)/ log M,
F(w) < (0) - (1) and ||w -ll S ca(v)11611
In the above lemma, if Dr is a standard Gaussian (0 I), the descriptions of these above constants become much simpler, as described in Section B33 The guarantees for the multiscale random initialization scheme follows from the analysis of random initialization when the length scale of ||اح| is known. Without loss of generality (see Section we can assume that ||ō||2 1 (or (1))) ). For convenience, we will set D, to be the absolute value of a standard Gaussian NO, 1) (or N (0, 82) with 3 E [1,2]. In this setting, we can show for constants eı (v), c2(v), ca(v) >> 0 (these are constants when [bul/ |/ll
2 is bounded), we have with probability at least c2(v)
F(w) < F(0) (1) and ||w - ull & co(1)]|0|12
(10)
We remark that for random initialization to work, we only need the probability of success 2 (2(v) > be non-negligible (e.g.. at least an inverse polynomial). We can try 0(1/n) many random initializers, and amplify the success probability to be very close to 1.
One can pick many other spread distributions in place of the absolute value of Gaussian.
8

---

Published as a conference paper at ICLR 2023
Overview of the proof of Lemma 5.1
We now outline the argument of Lemma 5.1 Please refer to Section B.3 B.3and and Section B.4 the full proofs. For convenience we define b, == / = w/|lō la so they are normalized w.r.t. the length of U. The conditions of the lemma assume that lbel O1)). The multiscale random initialization finds the correct length scale with probability at least 1/ //oo M).. For the rest of the overview we assume that the length ||0||2 = 1 known; without assume that ||ö|| 1. By definition, the distribution of
loss of generality (see Section Cp.
W E IR" is spherically symmetric.
F(w) F(0) = (o( oiū b,))
- 2 o x x+ b.))
1
2 x
1ا E ( w>] 11 o x)a(8" x bo))).
where ú = 1| with @ being the unit vector along For a fixed p R. @ (and hence ()) picked along uniformly random direction i.e., w ~y gd-1 Hence for x ~v Dz.
[F( 0)) F(O)] 10110112
[o 2)²
E Wro
E
E DD
(11)
2
-||0|1
E DND
T) x 8,0) = =100BB(ppp -
@-p
where d' > O is a universal constant based on our assumptions about Dr (c' = 0.5 for x (O, 7)). One technical portion of the argument derive an expression for (z(2), and prove that it is a constant independent of the dimension. This forms the bulk of the argument and requires symmetrization and careful use of anti-concentration bounds. Once we establish this, we need to prove that the first part 10 holds with non-negligible probability. From III
we note that for any
p
(a(v) (x(v)
we have that
2
[F((00 0)}1 < F(0) ||0||2 || C3(
E Badgy
2c
Moreover p is distributed as the absolute value of a standard normal with variance in [1, 4]; so we get from anti-concentration bounds that is in the right interval with probability at least Cs (v) > 0,
which is constant when bu] is constant. Now we condition on this event that p E
(ca()) ca(w) For
2e
fixed p in this interval, let Z be r.v. that captures the distribution of F((p [ 00
0)) F(0) as w
is drawn uniformly from the unit sphere gd-1 Note that E| [Z] I -1
Varlz| < [[F((p] ū w 0)) < O(1) ||ह||| ( +b))
Further for - F[Z we have from the Cantelli-Chebyyele one-sided tail inequality we have for some absolute constant eg 0
E
PP i 2 S[
min (occa())/((4+
co(o), =o(o),
Var [Z]
E|ZJ2
where co(v) is a constant when by is a constant. This allows us to conclude that F(w) F()) 2(( with probability at least cu(v) cg(v) which is a constant when b, is a constant. Finally w|w 0l12 < ||l||2 |/|| is upper bounded just because of our choice of and ||ōح| being upper bounded by assumption. See Sections B.3 and B.4 for the full proofs.
CONCLUSION
In this paper, we provided a convergence analysis of gradient descent for learning a single neuron with general ReLU activations (with non-zero bias terms) and gave improved guarantees under comparable assumptions also made in previous works. We addressed multiple challenges for analyzing general ReLU activations with non-zero bias terms throughout our analyses that may lead to better understanding of the dynamics of gradient descent when learning ReLU neurons. However, our analysis does not apply to modern neural networks that have multiple nodes and layers. The major open direction is to generalize current performance guarantees for networks of multiple neurons and higher depth.

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning. pp. 242-252. PMLR, 2019.
Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. In Conference on learning theory. pp. 81-102. PMLR, 2016.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332. PMLR, 2019.
Peter Bartlett, Dave Helmbold, and Philip Long. Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks. In International conference on machine learning, pp. 521-530. PMLR, 2018.
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- weer-araaeterizer models using optimal transport. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 3040-3050, Red Hook, NY, USA, 2018. Curran Associates Inc.
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one- eee-hidden-laye relu networks. In Conference on Learning Theory, pp. 1514-1539. PMLR, 2020.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning single neuron with adversarial label noise via gradient descent, 2022. URL httpp:://axxiv.rrr
2206. 08918
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes averpparameterized neural networks. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA. May 6-9, 2019. OpenReview.net, 2019. URL https
/ooeerrvveww.oo net. forum 1d=$1ek3109y0
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-54255 2020.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points points-online stochastic gradient for tensor decomposition. In Conference on learning theory, pp- 797-842. PMLR, 2015.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In International Conference on Learning Representations, 2018. URL https://
openreview www.eeet/oooo forum (icrrumiidBBBwwoboaea
Surbhi Goel and Adam Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference on Learning Theory, pp. 1470-1499. PMLR, 2019.
Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in polynomial time. In Conference on Learning Theory, pp. (004-1042, PMLR, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks (invited paper). In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 6, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 0781450380533 doi: 10.1 N0.114573403325.46533
URL 0ttp://66...00100..1111511133333 1143331443513315555111 3465355
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724-1732. PMLR, 2017.
Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2.
10

---

Published as a conference paper at ICLR 2023
Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT. Citeseer, 2009.
Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994.
Samuel Kutin. Extensions to mediarmid's inequality when differences are bounded with high probability. 05 2002.
Jachoon Lec, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bur E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL
Anirbit Mukherjee and Ramchandran Muthukumar. A study of neural training with non-gradient and noise assisted gradient methods. 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Mahdi Soltanolkotabi. Learning relus via gradient descent. In NIPS, 2017.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning single neuron with bias using gradient descent. Advances in Neural Information Processing Systems, 34, 2021.
Shanshan Wu, Alexandros G. Dimakis, and Sujay Sanghavi. Learning distributions gener- ated by one-layer relu networks. Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8105-8115, 2019. URL 84d41b834ea 90352633993333333 73a 9a as a aew.caeeeeee-ee. Abst wwcbbrracc.... htm
nwwrips https//pppppppe/////aaaaaaa
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 4140-4145 JMLR.org, 2017.
Difan Zou, Philip M Long, and Quanquan Gu. On the global convergence of training deep linear resnets. arXiv preprint vrXiv:2003.0109: 2020.


Reviews:
[{"review_id": "qgPYmAEels", "reviewer": "Reviewer_DGFB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the behavior of a single ReLU neuron in the gradient descent training process. The main results include that first, a new class of distributions (called O(1)-regular marginals) is proposed to characterize the regularity of the input space distributions. This class includes multivariate Gaussian distributions, and does not require compact support. Second, under the proposed O(1)-regularity, and with constant step-size, Theorem 1.1 claims that in polynomial (of the input space dimension, and the error threshold) number of iterations, the expected loss converges to the optimal value subject to a small error threshold.\n\n======================\n\nupdate after the discussion session: we find that most of our concerns have been resolved. We are therefore happy to recommend acceptance of this paper.", "summary_of_the_review": "There are some mathematical mistakes. Appendix is claimed but missing.", "strength_and_weaknesses": "Strength:\n1. the introduction of O(1) regularity\n2. the better convergence results\n\nWeakness:\n1. For Lemma 4.3, please specify the limit process for the big-O notation.\n2. When we read Section 1.2, a natural question is whether the O(1) regular marginal conditions can be induced from a sufficient condition: the distribution Dx has a continuous and compactly supported density function, which takes a positive value at the origin? Whether, subject to scaling x|-> ax for a specific a>0 because of (iii), this density condition is also necessary? If not, would the O(1) regularity contain any meaningful application scenario that is excluded from the C0 density assumption?\n3. For the simplification right before Section 4, would the analysis be different if the optimizer \\tilde{v} appears at the boundary of H?\n4. Please provide the Appendix as cited in the paper. For the time being, we are using the arXiv version of this paper to review the Appendix, and the comments are made accordingly.\n5. Please specify the limit process for the notations \\Omega(1) and O(1), below Equation (9). The same problem is in (1), and at the beginning of Section 4.1.\n6. Since in the proof Lemma 4.2 is cited, please add the O(1) regularity assumption to Lemma 4.3\n7. The constant c2 plays no role in Lemma 4.2. I guess this constant can be removed.\n8. For the arXiv version (dated August 04, 2022, same as below). The last inequality of (11) of the arXiv version: the O(1) distribution is replaced by the Normal distribution. The same mistake is observed in Equation (20) of the arXiv version.\n10. The O(1) regularity assumption just assumes beta_4 is positive, which could be very small. So, in the last two paragraphs, from beta<q^(1/4)/beta_4 one can not derive |b_u|>1/2.\n11. The claim (page 10 of the arXiv version) \"Observe that when (b) holds Lemma 4.4 implies the loss is O(OPT)\" requires the specification of the definition of \"O(OPT)\", to be further checked. Also, why would this lead to Lemma 4.5?\n12. Lemma 4.6 (the arXiv version) is different from the cited source. In Lemma d.4 in [VYS21], the underlying distribution is assumed compactly supported, and the bound c of the distribution support is changed to the square root of d (space dimension) in Lemma 4.6. In this paper, the O(1) regularity does not guarantee compact support. I guess that such a difference may not affect the conclusion, but then the new lemma should be proved separately.\n13. The O(1) regularity should be assumed for Lemma 4.5, since in the proof Lemma 4.2 is employed. Also, the boundedness of w_t and v should either be proved or assumed.\n14. Line -3 on page 11 of the arXiv version: according to Assumption (i) in O(1) regularity, the bound should be beta_2, not 2.\n15. Line 9 on page 12 of the arXiv version: there should be a factor $\\sqrt{beta_2}$ on the right-hand side.\n16. Line -4 of page 12 of the arXiv version: if C_2 is larger than C_1 C_p^2, then C' is negative.\n17. Line 3 of page 15 of the arXiv version: C_G is not elsewhere claimed to be greater than sqrt(2).\n18. Line -5 of page 6 of the ICLR version: the existence of such w_t (in particular, w_0) should be assumed. In particular, if v=0, such existence is violated.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kfQ-uLz5l6Z", "reviewer": "Reviewer_iUj1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the convergence of gradient descent in the regime of learning ReLU activations agnostically for a class of distributions that contains the standard high dimensional normal distribution. In contrast with previous results, they consider the case where bias exists and apply gradient descent on the weight vector+bias. Their approach essentially connects the analysis of [1] and [2].\n\n[1]: Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent.\n[2]: Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning a single neuron with bias using gradient descent", "summary_of_the_review": "I think the contributions of this work are not sufficient for acceptance in ICRL. ", "strength_and_weaknesses": "Pros:\n1. This is an important problem. Previous results have focused on the unbiased case, so this is somehow the first result for biased ReLU activations.\n2. The gradient descent happens in bias and the weight vector, which means that the naive idea of extending the dimension works\n\nCons:\n1.  The authors state in the abstract that this is the first algorithm based on gradient descent that achieves these guarantees when the bias is zero. But [3,4] apply gradient descent and achieve $O(OPT)$. The first work does gradient descent on a surrogate loss which differs from this work, where the gradient descent is applied to the standard objective. Meanwhile, the second work uses gradient descent on the same objective and achieves $O(OPT)$. So, I believe this sentence should be removed from the abstract. \n2.  This work considers the case where the ratio between $||w||_2$ and $b_w$ is bounded by a constant. The title and the abstract leave the impression that this work provides a theorem for any value of bias which is not the case. One of the main difficulties of learning ReLU activations is to sample enough points so that $\\sigma'(w^Tx+b)>0$  and $\\sigma(u^Tx+b')>>0$ ($u,b'$ are the best parameters for this instance) for a large portion of the points (see [5] theorem 4.2 for the intuition); with these assumptions, this is somehow easily satisfied (for standard Gaussian) with a good initialization (Section 5) because the mean and variance of the RV $u^Tx+b'$ is bounded by constants. \n\n\n\n\n[3]: Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, Mahdi Soltanolkotabi. Approximation Schemes for ReLU Regression\n[4]: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning a single neuron with adversarial label noise via gradient descent\n[5]: Gilad Yehudai, and Ohad Shamir. Learning a Single Neuron with Gradient Methods\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jwvgNCODob", "reviewer": "Reviewer_na9i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of agnostically learning a ReLU function via gradient descent using samples drawn from Gaussian (or even a more general class of) distributions.  The main result states that under a suitable random initialization, if gradient descent is run for sufficiently many iterations on the population risk loss function, then it outputs a ReLU function the error for which is within a constant factor of the optimal error, i.e., the minimum value of the population risk (referred to as: OPT). This result does not necessarily need the bias of the ReLU to be zero and improves existing guarantees for gradient descent (Frei et al. 2020).", "summary_of_the_review": "I think the contributions of the paper are decent and improve upon the analysis of (Frei et al. 2020) for learning ReLUs. The paper is also written cleanly and is easy to follow. As mentioned under \"weaknesses\" and in \"further comments\", I do have some comments regarding some closely related work and other technical aspects which need clarification.  ", "strength_and_weaknesses": "Pros: The paper has the following strengths.\n\n1. The exposition is in general clear and easy to follow. The problem setup and related work are detailed nicely that makes it convenient for the reader.\n\n2. The analysis is an improvement over that of (Frei et al. 2020) since this latter work assumes zero-bias ReLU's and achieves an error bound of $O(\\sqrt{d \\ OPT})$ when the samples are drawn from a Gaussian distribution.\n\nCons: \n\n1. I believe that the related work is incomplete for gradient descent learning of ReLU functions. The work of Soltanolkotabi [1] considers this problem in the realizable setting (with zero-bias) with the inputs drawn from a Gaussian and derives error bounds for recovering the unknown parameter. It is not clear to me how easy it is to extend this analysis to the noisy teacher setting. Since [1] is well cited, it would be good to check other related works that cite [1] in order to be more complete in the literature review. \n\n2. I find it is a bit restrictive to analyze gradient descent on the population risk. While this is natural to do as a first step in the analysis and certainly non-trivial, I believe the main theoretical result should ultimately be the one for the finite sample setting and should ideally be presented in the main text. This analysis is currently relegated to Appendix D as Theorem D.1. I also have a question regarding Theorem D.1 later below.\n\n[1] M. Soltanolkotabi, Learning relus via gradient descent, NeurIPS 2017.\n\nFurther comments:\n\n1. In the statement of Theorem D.1, it is not clear to me how $|y| \\leq B_Y$ can be assumed since the input $\\tilde{x}$ is generated from a Gaussian. For instance, isn't this violated in the realizable setting where y is defined as a ReLU?\n\n2. I was trying to understand whether in the special case of the \"noisy teacher\" setting (or \"realizable\" setting) the analysis says something about the convergence of the gradient descent iterates to the ground truth parameter. However from Section 4.1, it seems to me that this is not the case since it is only mentioned that the iterates lie within a ball of radius $O(\\sqrt{OPT})$ around the ground truth parameter. But we know from [1] that iterates of projected gradient descent (on the empirical loss) converge linearly to the ground truth in the realizable setting.  Some more explanation in this regard would be helpful.\n\n3. In Section 1.1 just above Theorem 1.1, $\\tilde{v}$ is introduced but has not been defined till then. There is a small typo towards the bottom of page 3 in \"Vardi et al.\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LtkdxOeQKa5", "reviewer": "Reviewer_4WPP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a convergence analysis of gradient descent for learning a single ReLU function under Gaussian feature distributions. The paper focuses on the mean squared loss between the single ReLU function the label, but allows updating both the weight vector and the bias parameter of the ReLU function.\n\nThe main contribution is proving that the gradient descent algorithm starting from a random initialization converges to within a constant factor of the global minimum of the loss within polynomial (in input dimension) number of iterations.\n\nBesides the case of Gaussian feature distributions, the analysis can also be generalized to the O(1)-regular marginals.", "summary_of_the_review": "Overall I think this is a solid paper that contributes to the learning of nonlinear ReLU functions. It expands prior result and clearly states the limitations too (i.e., limited to one node) for future work. As noted above there is some concerns related to missing several related works in the literature.", "strength_and_weaknesses": "Strength:\n- The result of this paper improves upon a previous result for learning a single ReLU function by additionally incorporating the bias in the analysis. Further, the analysis shows that the convergent iterate is within a constant factor of the optimum, whereas prior result requires an additional factor of d (i.e., input dimension).\n\nWeakness:\n- The feature distribution is assumed to be drawn from a Gaussian distribution. While this can be relaxed to the case of (1)-regular marginals, generalizing further seems challenging (e.g., does the condition hold for mixture of Gaussians or anisotropic Gaussians?)\n- There are related works that consider the realizable setting of learning ReLU networks, which should perhaps also be discussed in the related work, e.g., here’s one:\n\n“Learning Distributions Generated by One-Layer ReLU Networks.” Shanshan Wu, Alexandros G. Dimakis, Sujay Sanghavi. 2019.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster