Learning a Single Neuron with Bias Using Gradient Descent
Authors: Gal Vardi
Gilad Yehudai
Ohad Shamir
Venue: NeurIPS 2021 Poster (2021)
Keywords: Non-convex optimization
single neuron
gradient descent

Abstract: We theoretically study the fundamental problem of learning a single neuron with a bias term ($\mathbf{x}\mapsto \sigma(\langle\mathbf{w},\mathbf{x}\rangle + b)$) in the realizable setting with the ReLU activation, using gradient descent. Perhaps surprisingly, we show that this is a significantly different and more challenging problem than the bias-less case (which was the focus of previous works on single neurons), both in terms of the optimization geometry as well as the ability of gradient methods to succeed in some scenarios. We provide a detailed study of this problem, characterizing the critical points of the objective, demonstrating failure cases, and providing positive convergence guarantees under different sets of assumptions. To prove our results, we develop some tools which may be of independent interest, and improve previous results on learning single neurons. 

Learning a Single Neuron with Bias Using Gradient Descent
Gal Vardi'
Gilad Yehudai"
Weizmann Institute of Science gal. vardi@weizmann. ac. 11
Weizmann Institute of Science g yehudai @weizmann ac
Ohad Shamir
Weizmann Institute of Science ohad. shamir@wei zmann. ac il
Abstract
We theoretically study the fundamental problem of learning single neuron with bias term (x + ((W,x) + b)) in the realizable setting with the ReLU activation, using gradient descent. Perhaps surprisingly, different and more challenging problem than the bias-less case (which was the focus of previous works single neurons), both in terms of the optimization geometry as well as the ability of gradient methods to succeed in some scenarios. We provide detailed study of this problem, characterizing the critical points of the objective, demonstrating failure cases, and providing positive convergence guarantees under different of assumptions. To prove our results, we develop some tools which may be of independent interest, and improve previous results on learning single neurons.
show that this is significantly
1 Introduction
Learning a single ReLU neuron with gradient descent is fundamental primitive in the theory of deep learning, and has been extensively studied recent years. Indeed, in order to understand the success of gradient descent on complicated neural networks, it seems reasonable to expect satisfying analysis of convergence on a single neuron. Although many previous works studied the problem of learning single neuron with gradient descent, none of them considered this problem with an explicit bias term
In this work, we study the common setting of learning a single neuron with respect to the squared loss, using gradient descent. We focus on the realizable setting, where the inputs are drawn from distribution D on Rd+1, and are labeled by single target neuron of the form x + a((v, x)). where R + IR some non- non-linear activation function. To capture the bias term, we assume that the distribution is such that its first d components are drawn from some distribution D on Rd and the last component is a constant 1. Thus, the input can be decomposed as (x, 1) with x D, the vector v can be decomposed as (V, by), where V E I and by E R. and the target neuron computes a function of the form x + a (V, x) + by). Similarly, we can define the learned neuron as + a (w, x) + b.). where = (w, bww Overall, we can write the objective function we wish to
Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

optimize as follows:
F(w) = E x~D
(a(w x) - oov x))²
(1)
(o(w x + bw) -ooioo bx))
R
(2)
X~D
Throughout the paper consider the commonly used ReLU activation function: (z) max (0, 0, x)
Although the problem of learning a single neuron well studied (e.g. Soltanolkotabi [2017] Yehudai
and Shamir [2020] Frei et al. (020)_ Duu et al. [017]] Kalan et al. 2019). [lan and Vershynin 2019].
Mei et al. 2018]. Oymak and Soltanolkotabi (018 ) none of the previous works considered the problem with an additional bias term. Moreover, previous works on learning single neuron with gradient methods have certain assumptions on the input distribution D, which do not apply when dealing with bias term (for example, a certain "spread" in all directions, which does not apply when D is supported on {1} in the last coordinate).
Since neural networks with bias terms are the common practice, it is natural to ask how adding bias term affects the optimization landscape and the convergence of gradient descent. Although one might conjecture that this is just a small modification to the problem, we in fact show that the effect of adding a bias term very significant, both in terms of the optimization landscape and in terms of which gradient descent strategies can or cannot work. Our main contributions are as follows:
We start in Section with some negative results, which demonstrate how adding a bias term makes the problem more difficult. In particular, we show that with a bias term, gradient descent or gradient flowe) can sometimes fail with probability close to half over the initialization, even when the input distribution is uniform bias term, for the same input distribution, gradient flow converges to the global minimum with probability 1.
a ball. In contrast, Yehudai and Shamir [020] show that without
In Section 4 we give full characterization of the critical points of the loss function. We show that adding a bias term changes the optimization landscape significantly: In previous works (cf. Yehudai and Shamir 2020 has been shown that under mild assumptions on the input distribution, the only critical points are w = v (i.e., the global minimum) and w = O. We prove that when we have bias term, the set of critical points has positive measure, and that there is cone of local minima where the loss function is flat.
Sections and O we show that gradient descent converges to the global minimum at a lincar rate, under some assumptions the input distribution and the initialization. We give two positive convergence results, where each result is under different assumptions, and thus the results complement each other. We also use different techniques for proving each of the results: The analysis in Section 66 follows from some geometric arguments and extends the technique from Yehudai and Shamir [2020], Frei et al. [2020). The analysis in Section 5 introduces novel technique, not used in previous works on learning a single neuron, and has more algebraic nature. Moreover, that analysis implies that under mild assumptions, gradient descent with random initialization converges to the global minimum with probability (d())
The best known result for learning single neuron without bias using gradient descent for input distribution that is not spherically symmetric, establishes convergence to the global minimum with probability close to over the random initialization Yehudai and Shamir 2020 Frei et al. 2020) With our novel proof technique presented in Section 5 this result can be improved to probability at least -od) (see Remark 5.7
Related work
Although there are no previous works on learning single neuron with an explicit bias term, there are many works that consider the problem of a single neuron under different settings and assumptions.
Several papers showed that the problem of learning single neuron be solved under minimal assumptions using algorithms which are not gradient-based (such as gradient descent or SGD). These
Le.., gradient descent with infinitesimal step size.

---

algorithms include the Isotron proposed by Kalai and Sastry [2099] and the GLMtron proposed by Kakade al. (20TT) The GLMuron algorithm is also analyzed in Diakonikolas al. [2020]. These algorithms allow learning a single neuron with bias. We note that these are non-standard algorithms, whereas we focus on the standard gradient descent algorithm. An efficient algorithm for learning a single neuron with error parameter
S log(d)) was also obtained in Goel et al. 2017
In Mei et al. 2018 the authors study the empirical risk of the single neuron problem. However, their analysis does not include the ReLU activation, or adding a bias term. A related analysis is also given
Oymak and Soltanolkotabi (2018), where the ReLU activation is not considered.
Several papers showed convergence guarantees for the single neuron problem with ReLU activation under certain distributional assumptions, although none of these assumptions allows for bias term. Notably, Tian 2017], Soltanolkotabi] [2017]. Kalan et al. 2019). Brutzkus and Globerson 2017] showed convergence guarantees for gradient methods when the inputs have standard Gaussian distribution, without bias term. Du et al. [2017) showed that under a certain subspace eigenvalue assumption single neuron can be learned with SGD, although this assumption does not allow adding a bias term. Yehudai and Shamir [2020), Frei et al. [2020] use an assumption about the input distribution being sufficiently "spread" all directions, which does allow for bias term (since that requires an input distribution supported on {1} in the last coordinate). Yehudai and Shamir (020)] showed a convergence result under the realizable setting, while Frei et al. [2020] considered the agnostic and noisy settings. In Tan and Vershynin [2099] convergence guarantees are given for the absolute value activation, and a specific distribution which does not allow bias term.
Less directly related, Vardi and Shamir 2020) studied the problem of implicit regularization in the single neuron setting. In Yehudai and Shamir (2019), Kamath al.. [2020] it is shown that approximating a single neuron using random features (or kernel methods) is not tractable in high dimensions. We note that these results explicitly require that the single neuron which is being approximated will have a bias term. Thus, our work complements these works by showing that the problem of learning single neuron with bias is also learnable using gradient descent (under certain assumptions). Agnostically learning single neuron with non gradient- based algorithms and hardness of a agnostically learning a single neuron were studied Diakonikolas et al. [2020). Goel al. [2019 2020).
2 Preliminaries
Notations. We use bold-faced letters to denote vectors, e.g., x (xi,..., sa)- For u E Rd we denote by ||u|| the Fuclidean norm. We denote i = π namely, the unit vector in the direction of u. For 1 < i i j S d we denote U:y = (u,.... Uy) E Ri-i+1 We denote by 1--) the indicator function, for example (t 2 5) equals if 1. 2 5 and otherwise. We denote by U([-r,)) the uniform distribution over the interval [-r, r] in IR, and by N0 Σ) the multivariate normal distribution
with mean 0 and covariance matrix Σ. Given two vectors w, v we let 0 (w, v) = arccos
(w.v) 1w |w
arccos( (w, v)) E [0. r.. For a vector u E Rd+1 we often denote by ú E RRd the first d components of u, and denote by bu TR. its last component.
Gradient methods. In this paper we focus on the following two standard gradient methods for optimizing our objective F(w) from Eq. (
Gradient descent: We initialize at some Wo Rd+1 and set fixed learning rate 17 > 0. At each iteration 2 0 we have: Wi+1 = w. v/FF(w,) (w.).
Gradient Flow: We initialize at some w (0) E RRd+1, and for every time / 2 O, we set w(1) to be
the solution of the differential equation w V (t)). This can be thought of as continuous form of gradient descent, where the learning rate is infinitesimally small.
The gradient of the objective in Eq. ! is:
VF(w)= = E [(a(w olv' x)) o'(w' d'(TT)xx x)x] x~D
Since a is the ReLUU function, is differentiable everywhere except for 0. Practical implementations of gradient methods define o' d'(0) to be some constant in [0, 1]. Following this convention, the gradient
3

---

used by these methods still correspond to Eq. 33. We note that the exact value of o0) has no effect on our results.
3 Negative results
In this section demonstrate that adding bias to the problem of learning single neuron with gradient descent can make the problem significantly harder.
First, on an intuitive level, previous results (e.g.. Yehudai and Shamir 2020 Frei et al. 2020]]
Soltanolkotabi [2017]. Du al. 2017]. Tan and Vershynin| (2099] considered assumptions on the input distribution, which require enough "spread" in all directions (for example, strictly positive density in some neighborhood around the origin). Adding a bias term, even if the first d coordinates of the distribution satisfy a "spread" assumption, will give rise to a direction without "spread", since in this direction the distribution is concentrated on 1, hence the previous results do not apply.
Next, we show two negative results where the input distribution is uniform on ball around the origin. We note that due Theorem 6.4 from Yehudai and Shamir [2020), we know that gradient flow on single neuron without bias will converge to the global minimum with probability 1 over the random initialization. The only case where it will fail to converge is when Wo is initialized in the exact direction -v, which happens with probability 0 with standard random initializations.
3.1 Initialization in flat region
If initialize the bias term in the manner as the other coordinates, then can show that gradient descent will fail with probability close to half, even if the input distribution is uniform over a (certain) origin-centered ball:
Theorem 3.1. Suppose we initialize each coordinate of wo (including the bias) according to
U[[-1,1]), I]). Let E 0 and let DD be the uniform distribution supported ball around the
origin in Rd of radius Then, w.p > 1/2 1 1/2-ev/d, gradient descent the objective in Eq. 2 satisfies W, for all I (namely, it gets stuck al its inilial point wo).
Note that by Theorem 6.4 in Yehudai and Shamir 2020], if there is no bias term in the objective, then gradient descent will converge to the global minimum w.p using this random initialization scheme and this input distribution. The intuition for the proof is that with constant probability over the initialization, bw is small enough so that ((w x + bw) = 0 almost surely. If this happens, then the gradient will be 0 and gradient descent will never move. The full proof can be found in Appendix B.1 We note that Theorem 3.1 applicable when e sufficiently small, e.g. 1/vd.
3.2 Targets with negative bias
Theorem 3.1 shows a difference between learning with and without the bias term. main caveat of this example is the requirement that the bias is initialized in the same manner as the other parameters. Standard deep learning libraries (e.g. Pytorch (Paszke et al. 2019) often initialize the bias term to zero by default, while using random initialization schemes for the other parameters.
Alas, we now show that even we initialize the bias term to be exactly zero, and the input distribution is uniform over arbitrary origin- iegnereentered ball, we might fail to converge the global minimum for certain target neurons:
Theorem 3.2. Let DD be the uniform distribution on B {x E Rd: |||||| S <T) for some >> 0. Let v E pd+1 such that v = O1.,,..., and by (r- 3e Let wo E Rd+1 such that bw. = 0 and wo is drawn from the uniform distribution on a sphere of radius p 0. Then, with probability at least _ - o1(1) over the choice of Wo, gradient flow does not converge to the global minimum.
We prove the theorem in Appendix B.2 The intuition behind the proof is the following: The target neuron has a large negative bias, so that only a small (but positive) measure of input points are labelled as non-zero. By randomly initializing w. with probability close to & there are no inputs that both v and w label positively. Since the gradient is affected only by inputs that w labels positively, then during the optimization process the gradient will be independent of the direction of v, and w will not converge to the global minimum.

---

Remark 3.3. Theorem 3.2 shows that gradient flow is not guaranteed to converge to global mini- mum when by is negative, instead it converges to a local minimum with loss of F(O). However, the
loss O() is determined by the input distribution, Take (1. (1.0....) ..... 0, (r 2 considered in the theorem. On one hand, for a uniform distribution on a ball of radius r as in the theorem we have:
F(0) = E
[o(v
x))
=
1
E
1(v T x 2 0) (v x 21
2 x
2
(r- 2412)
E
1 [1)
rr-
2
2d
2d
,2
Pr
æ 2
[
S <r²
4d
2d
Thus, for any reasonable local minimum with loss F(O) is almost as good as the global minimum. On the other hand, take distribution D with support bounded in a ball of radius v, such that half of its mass is uniformly distributed in A == & E IR # > r 4 }. and the other half is uniformly distributed in B A. this case, is not hard to see that the same proof as in Theorem 3.2 works, and gradient flow will converge to a local minimum with loss F(O) = 9 (#) which is arbitvarily large if r is large enough.
Although in the example given in Theorem 3.2 the objective w is almost as good as the objective at w = v, we emphasize that w.p almost gradient flow cannot reach the global minimum even asymptotically. On the other hand, in the bias-less case by Theorem 6.4 Yehudai and Shamir (2200 gradient flow on the same input distribution will reach the global minimum w.p 1. Also note that the scale of the initialization of We has no effect on the result.
Characterization of the critical points
In the previous section we have shown two examples where gradient methods on the problem of a single neuron with bias will either get stuck in a flat region, or converge to a local minimum. In this section we delve deeper into the examples presented in the previous section, and give a full characterization of the critical points of the objective. We will use the following assumption on the input distribution:
The distribution D on Rdd has density function pl p(X), and there are 3, >> such that D is supported on {x: || S c), and for every the support we have p(x) 2 B.
Assumption 4.1.
The assumption essentially states that the distribution over the first d coordinates (without the bias term) has enough "spread" in all directions, and covers standard distributions such as uniform over a ball of radius c. Other similar assumptions are made in previous works (e.g. Yehudai and Shamir (2020), (rei et al.] (2020). We note that in Yehudai and Shamir (2020) is shown that without any assumption on the distribution, it is impossible to ensure convergence, hence we must have some kind of assumption for this problem to be learnable with gradient methods. Under this assumption we can characterize the critical points of the objective.
Theorem 4.2. Consider the objective in Eq. (2) with + O, and assume that the distribution D on the first d coordinates satisfies A Assumption 4.1 Then w + O is a critical point of F (Le., is a root of Eq. 3 if and only if it satisfies one of the following:
= v, in which case w is global minimum.
w (w, bw)
where w = 0 and bw < O.
+ 0 and
W
In the latter two cases, F(w)= = F(O). Hence, if is not a global minimum, then w is not global minimum.
We note that F(O)= 2 [x [x)]], so is global minimum only if the target neuron returns with probability 1.
5

---

Remark 4.3 (The case w = 0). We intentionally avoided characterizing the point w O. since the objective is not differentiable there (this is the only point of non- non-differentiabiity), and the gradient there is determined by the value of the ReLU activation al O. For a' (D) O the gradient at w 0 is zero, and this is non-differentiable saddle point. For o' (0) = (or any other positive value), the gradient at w 0 is non-zero, and it will point at a direction which depends on the distribution. We note that in Soltanolkotabi (2017) the authors define d0) = 1, and use a symmetric distribution, in O points exactly the direction of the target This is crucial part
which case the gradient of their convergence analysis.
We emphasize that with a bias term, there is a non-zero measure manifold of critical points (corre- sponding the third bullet in the theorem). On the other hand, without a bias term the only critical point besides the global minimum (under mild assumptions on the input distribution) is at the origin 0 (cf. Yehudai and Shamir (2020]). The full proof is in Appendix C
The assumption on the support of D is made for simplicity. It can be relaxed to having distribution with exponentially bounded tail, e.g. standard Gaussian. In this case, some of the critical points will instead have non-zero gradient which is exponentially small. We emphasize that when running optimization algorithms on finite-precision machines, which are used in practice, these "almost" critical points behave essentially like critical points since the gradient is extremely small.
Revisiting the negative examples from Section 3 the first example (Theorem 3.1 not initialize the bias of w to zero, then there is positive probability to initialize at a critical point which is not the global minimum. The second example (Theorem 3.2) shows that even if we initialize the bias of w to be zero, there is still positive probability to converge to critical point which is not the global minimum. Hence, in order to guarantce convergence we need to have more assumptions on either the imput distribution. the target or the initialization. In the next section, we show that adding such assumptions are indeed sufficient get positive convergence guarantees.
shows that if we do
5 Convergence for initialization with loss slightly better than trivial
In this section, we show that under some assumptions on the input distribution, gradient descent is initialized such that F(wo) < F(O) then it is guaranteed to converge to the global minimum. In Subsection 5.2. we study under what conditions this likely occur with standard random initialization.
5.1 Convergence if F(wo) < F())
To state results, need the following assumption:
Assumption 5.1.
1. The distribution 'D is supported on (x E Rd+1 +|x|| S c} for some 2 1.
The distribution over the first d coordinates bounded in all directions: there is e' > such that for every u with |ūl|| and every a E IK and b 2 0, we have Pr PraND [ x (a, a + bl S b.c.
3. We assume w.L..g. that ||v|| and c' >
Assumption (3) helps simplifying some expressions in convergence result, and is not necessary. Assumption (2) requires that the distribution is not too concentrated in a short interval. For example, D is spherically symmetric then the marginal density of the first (or any other) coordinate is bounded by c'. Note that we do not assume that D is spherically symmetric.
Theorem 5.2. Under Assumption 5.7 we have the following. Let ō > 0 and let wo E Rd+1 such that
F(wu) < F(0) 8. Let 3-12%(|wa [|wwllllllta +2) Assume that gradient descent runs starting from Wo with step size n S 2. Then, for every t we have
ga
||,, v/12 S || v/I2 (1 (1-
The formal proof appears in Appendix D but we provide the main ideas below. First, note that || - v = || 17 7 - v/l
= ||W, - - 2n V F F(w)) w. v) VVW,))1

---

Hence, in order to show that | -vl2 < W: v/1 (1-mm) we need to obtain an upper bound for (W;)ll and lower bound for (VF(w,). Wt -v- v). Achieving the lower bound for (VF((:); W, v) is the challenging part, and we show that in order to establish such a bound it suffices to obtain a lower bound for Prx [
x 2 0, v 2 0j. We prove that if F(w:)) S F(0) - 2 0 2 T|w Hence, if F F(we) remains at most F(0) for every t, then lower bound for (VF(W:), W. -v-v) v) can be achieved, which completes the proof. However, is not obvious that ((w,) remains at most F(O) 5 throughout the training process. When running gradient descent on a smooth loss function we can choose a sufficiently small step size such that the loss decreases in each step, but here the function F(w) is highly non-smooth around w 0. That is, the Lipschitz constant of V F(w) is unbounded. We show that if F F(we) I F(O) - then w, is sufficiently far from O, and hence the smoothness of F around W. can be bounded, which allows us to choose a small step size that ensures that F ((w++))= & F F(w)) S F(O) 6. Hence, follows that F F(w;) remains at most (() 5 for every t.
then Prx [ x 2 0, v
As an aside, recall that in Section we showed that other than w = v all critical points of F(w) are in flat region where F [(w) TO). Hence, the fact that F(w;) remains at most F(0) ô for every implies that w, does not reach the region of bad critical points, which explains the asymptotic convergence to the global minimum.
We also note that although we assume that the distribution has a bounded support, this assumption is mainly made for simplicity, and can be relaxed to have sub-Gaussian distributions with bounded moments, These distributions include, e.g. Gaussian distributions.
5.2 Convergence for Random Initialization
In Theorem 5.2 we showed that if F(wo) < F(O) then gradient descent converges to the global minimum. We now show that under mild assumptions on the input distribution, random initialization of Wp near zero satisfies this requirement. We will need the following assumption, also used in Yehudai and Shamir (000). |Frei al. (2020)
Assumption 5.3. There are a, B > O s.t the distribution D satisfies the following: For any vector w + v, let Da denote the marginal distribution of DD on the subspace spanned by w, v (as distribution over R.2). Then any such distribution has a density function (w,x(x) over IR? such that inf k: S Pw, & (x) 2 3.
The main technical tool for proving convergence under random initialization is the following:
Theorem 5.4. Assume that the input distribution 'D is supported on (x Rd+1 ||x|| S c) for
some c 2 1, and Assumption 5.3 holds. Let v E gd+1 such that ||v|| = and by S a M
sin (9)
Let M = sin Let w E RRd+1 such that bw = O. 0(w, v) S 3x and /wl < 2M Then,
256c
4
F(w) < F(O) + w/
|/| M < F(0).
We prove the theorem in Appendix D.I The main idea is that since
F(w) J x
( (a(w x) olv x))²
2
= =((0)
+ E
(o(w)) xx))
- [[[ [[[owooooov (x)o)
-E
2 x
c²
< F(0) + ||w]|
|| -E oo(w x)o(vV
then it suffices to obtain a lower bound for Ex [o(w Tx xv)(vVxx) In the proof we show that such a bound can be achieved if the conditions of the theorem hold.
Suppose that Wn such that Wo is drawn from spherically symmetric distribution and bwo 0. By
standard concentration of measure arguments, it holds w.p. least 1 - A(d) that 0(wo, v) 3
(where the notation ((d) hides only numerical constants, namely, it does not depend on other parameters of the problem). Therefore, if wo drawn from the uniform distribution on a sphere of radius/ p < _
2M then the theorem implies that w.h.p. we have F(wo) < F(O). For such initialization
Theorem 5.2 implies that gradient descent converges to the global minimum. For example, for p az
M
7

---

we have w.h.p. that F(wo) S F(0) + 2' pM = F(0)
M²
and thus Theorem 5.2 applies with
2.3+
5
2G Thus, we have the following corollary:
M²
Corollary 5.5. Under Assumption 5.7 and Assumption 5.3 have the following. Let M sin (#)
M² a (() let p= <2, let 5 2et and 7 3-12 Suppose that by
83
[ a a.
200e
and Wo is such that bwo = and Wo is drawn from the uniform distribution on a sphere of radius
Consider gradient descent with step size S 2.. Then, with probability at least (l(d) over the
choice of Wo we have for every L: |[ v < Wo vll (1 7m)
We note that a similar result holds also if wo is drawn from normal distribution NN E
sin(g)
By S a Remark 5.6 (The assumption on by). The assumption - [ by may be either positive negative, but in case it is negative then it cannot be too large. This assumption is indeed crucial for the proof, but for "well-behaeed distributions, ift assumption is not satisfied (for large enough a.), then the loss at F(O) is already good enough. For example. for standard Gaussian distribution and for every E >> 0, we can choose a large enough such that for any bias term (positive
implies that the bias term
either: (1) converge to the global minimam with loss of zero, or; (2) converge to a local minimum with a loss of F(O), which is smaller then e. Moreover, we can by
negative)
show that by choosing a appropriately, and using the example in Theorem 3.2 if |M|| 2 2a then
non-global minimum with loss of F().. This means that our bound on a tight up to a constant factor. For a further discussion on the assumption on by. and how to choose a see Appendix L
gradient flow will converge
Previous papers have shown separation between random features (or kernel) methods and neural networks in terms of their approximation power (see Yehudai and Shamir (019)) I9. Kamath et al. 2020], and the discussion Malach et al. (202T). These works show that under a standard Gaussian distribution, random features cannot even approximate single ReLU neuron, unless the number of features is exponential in the input dimension. That analysis crucially relies on the single neuron having non-zero bias term. In this work we complete the picture by showing that gradient descent can indeed find near-optimal neuron with non-zero bias. Thus, we see there indeed essentially a separation between what can be learned using random features and using gradient descent over neural networks.
Remark 5.7 (Learning a neuron without bias). Yehudai and Shamir [2020] studied the problem of learning a single ReLU neuron without bias using gradient descent on single neuron without bias. For input distributions that are not spherically symmetric they showed that gradient descent with random initialization near zero converges to the global minimum w.p. at least & - Their result is also under Assumption] 5.3] An immediate corollary from the discussion above is that if we learn a single neuron without bias using gradient descent with random initialization on a single neuron with bias, then the algorithm converges to the global minimum w.p. at least 1 ((d) Moreover, our proof technique can be easily adapted to the setting of learning a single neuron without bias using gradient descent on single neuron without bias, namely, the setting studied in Yehudai and Shamir 22020]. It can be shown that in this setting gradient descent converges w.h.p to the global minimum. Thus, our technique allows to improve the result of Yehudai and Shamir [2020] from probability (1) to probability S(d)
0a(1),
6 Convergence for spread and symmetric distributions
In this section we show that under a certain set of assumptions, different from the assumptions in Section it is possible to show linear convergence of gradient descent to the global minimum. The assumptions we make for this theorem are as follows:
Assumption 6.1.
1. The larget vector satisfes that by 2 0 and || 1.
2. The distribution D over the first d coordinates is spherically symmetric.

---

Assumption 5.3 holds, and denoting by -= Be 521 then a 2 2.522 max {1, /イ) where
or is from Assumption 5.3
4. Denote by == B [[] then < co.
We note that item (3) considers T1, 222 but due to the assumption on the symmetry of the distribution (item (2)), the assumption in item (3) holds for every 24, zzj. Under these assumptions, prove the following theorem:
Theorem 6.2. Assume we initialize wo such that || vII < 1, bwo 2 0 and that Assumption 6.1
holds. Then, there is universal constant C, such that using gradient descent F(w) with step
size 17 < C- 3 ca min 7} yields that for every we have l|,, vl|² $ (1 m7> v|1² for
A C ca
This result has several advantages and disadvantages compared to those of the previous section. The main disadvantage is that the assumptions are generally more stringent: We focus only on positive target biases (by 2 0) and spherically symmetric distributions D. Also require certain technical assumption on the the distribution, as specified by т. which are satisfied for standard spherically symmetric distributions, but is bit non-trivia Finally, the assumption the initialization (l]wo- - v/2 < and bwo 2 0) is much more restrictive (although see Remark 6.. below). In contrast, the initialization assumption in the previous section holds with probability close to 1 with random initialization. On the positive side, the convergence rate does not depend on the initialization, i.e., here by initializing with any wo such that || Wo v < 1 and bwg 2 we get a convergence rate that only depends on the input distribution. On the other hand, in Theorem [5.2] the convergence rate depends the parameter ō which depends the initialization. Also, the distribution is not necessarily bounded - we only require its fourth moment to be bounded.
Remark 6.3 (Random initialization). For by = 0 the initialization assumption ( (l[oo - v11 1) is satisfied with probability close to 1/2 with standard initializations, see Lemma 5. from Yehudai and Shamir (0201). For by > 0, a similar argument applies if bw is initialized close enough to by-
The proof of the theorem is quite different from the proof's in Section 5 and is more geometrical in nature, extending previously used techniques from Yehudai and Shamir 2020 Frei et al. (2020)
It contains two major parts: The first part is an extension of the methods from Yehudai and Shamir [2200] to the case of adding a bias term. Specifically, we show lower bound on (VF(w), w v which depends on both the angle between w and v, and the bias terms bw and by (see Theorem A.2) This result implies that for suitable values of w, gradient descent will decrease the distance from v. The second part of the proof is showing that throughout the optimization process, w will stay in an area where we can apply the result above. Specifically, the intricate part is showing that the term by does not get too large. Note that due to Theorem 4.2 we know that keeping this term small Wil
means that w stays away from the cone of bad critical points which are not the global minimum. The full proof can be found in Appendix F
7 Discussion
In this work we studied the problem of learning a single neuron with a bias term using gradient descent. We showed several negative results, indicating that adding bias term makes the problem more difficult than without a bias term. Next, we gave characterization of the critical points of the input distribution, showing that there is manifold of
the problem under some assumptions critical points which are not the global minimum. We proved two convergence results using different techniques and under different assumptions. Finally, we showed that under mild assumptions on the input distribution, reaching the global minimum can be achieved by standard random initialization.
We emphasize that previous works studying the problem of single neuron either considered non- standard algorithms (e.g. Isotron), or required assumptions on the input distribution which do not
è For example, for standard Gaussian distribution, we have that _ z 0.63, hence we can take = 4.5. and 3 = O(1). Since the distribution D is symmetric, we present the assumption w.l.o.g with respect to the first 2 coordinates.

---

allow a bias term. Hence, this is the first work we are aware of which gives positive and negative results on the problem of learning single neuron with bias term using gradient methods.
In this work we focused on the gradient descent algorithm. We believe that our results can also be extended the commonly used SGD algorithm, using similar techniques Yehudai and Shamir [2020), |Shamir [2015), and leave it for future work. Another interesting future direction is analyzing other previously studied settings, but with the addition of bias term. These settings can include convolutional networks, two layers neural networks, and agnostic learning of a single neuron.
Acknowledgements
This research is supported in part by European Research Council (ERC) grant 754705.
References
[1] A. Brutzkus and A. Globerson. Globally optimal gradient descent for convnet with gaussian inputs. Proceedings of the 34th International Conference on Machine Learning- Volume 70. JMLR. org, 2017.
[2] S. Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint 1005:4440,,4980 2014.
[3] Diakonikolas, S. Goel, Karmalkar, A. R. Klivans, and M. Soltanolkotabi. Approximation schemes for relu regression. In Conference on Learning Theory, pages 1452-1485 PMLR, 2020.
[4] S. S. Du, D. Lee, and Tian, When is a convolutional filter easy to learn? arXiv preprint arXiv: 1709.06/2,, 2017.
[5] S. Frei, Y. Cao, and Q. Gu. Agnostic learning of single neuron with gradient descent. arXiv preprint arXiv:2005. 14426, 2020.
[6] Goel, V. Kanade, A. Klivans, and Thaler. Reliably learning the relu in polynomial time. In Conference on Learning Theory, pages 1004-1042. PMLR, 2017.
[7] S. Goel, S. Karmalkar, and A. Klivans. Time/accuracy tradeoffs for learning relu with respect to gaussian marginals. arXiv preprint 19/ 2019.
[8] S. Goel, A. Klivans, P. Manurangsi, and D. Reichman. Tight hardness results for training depth-2 relu networks. arXiv preprint arXiv:2011 135500, 2020.
[9] S. M. Kakade, V. Kanade, O. Shamir, and A. Kalai. Efficient learning of generalized linear and single index models with isotonic regression. In Advances in Neural Information Processing Syslems, pages 927-935, 2011.
[10] A. T. Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT. Citeseer, 2009.
[11] M. M. Kalan, M. Soltanolkotabi, and A. S. Avestimehr, Fitting relus via sgd and quantized sgd. In 2019 IEEE International Symposium Information Theory (ISIT), pages 2469-2475 IEEE, 2019.
[12] Kamath, O. Montasser, and Srebro. Approximate good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Leurning Theory, pages 2236-2262. PMLR, 2020.
[13] E. Malach, P. Kamath, E. Abbe, and N. Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. arXiv preprint arXiv:2103.01210, 2021.
[14] S. Mei, Y. Bai, and A. Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018
[15] S. Oymak and M. Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? arXiv preprint arXiv:1812. 2018.
10

---

[16] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, al. Pytorch: An imperative style, perfopaaformance deep learning library. arXiv preprint 1rXiv:1912.017000 2019.
[17] O. Shamir. A stochastic pea and svd algorithm with an exponential convergence rate. In International Conference on Machine Learning, pages 144-152, 2015.
[18] M. Soltanolkotabi. Learning relus via gradient descent. Advances in Neural Information Processing Systems, pages 2007-2017, 2017.
[19] Y. Tan and R. Vershynin. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. arXiv preprint 1rXiv:1910.12837 2019.
[20] Y. Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 3404-3413, JMLR. org, 2017.
[21] G. Vardi and O. Shamir. Implicit regularization in relu networks with the square loss. arXiv preprint arXiv:2012.05156,, 2020.
[22] G. Yehudai and O. Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv:1904 00687, 2019.
[23] G. Yehudai and O. Shamir. Learning single neuron with gradient methods. arXiv preprint arXiv:2001.05205, 2020.
NeurIPS Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Yes
(b) Have you read the ethics review guidelines and ensured that your paper conforms to them? Yes
(c) Did you discuss any potential negative societal impacts of your work? n/a, the paper is theoretical in nature
(d) Did you describe the limitations of your work? Yes
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? Yes
(b) Did you include complete proofs of all theoretical results? Yes
3. If you ran experiments... n/a
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
n/a
5. If you used crowdsourcing or conducted research with human subjects... n/a


Reviews:
[{"review_id": "u_KpBQHKXa2", "reviewer": "Reviewer_9NfA", "summary": "In this paper, the authors consider the task of learning a single ReLu neuron with bias using gradient descent, which has a significantly different behavior than the unbiased case. For example, adding a bias leads to examples where gradient descent fails to find the global minimum with probability $1/2$, whereas GD succeeds wp 1 with no bias. This is explain by GD getting stuck at critical points which are characterized in Section 4. The authors then show that if the GD is initialized at a point with loss better than the trivial loss, then it converges to the global minimum. This good start happens with high probability for standard symmetric initialization (and 0 bias initialization), and can be shown to converge at linear rate. Finally, in section 6, they provide an alternative set of assumptions that leads to linear convergence, with rate that do not depend on initialization (but with lower probability on initialization).\n\n\n--- after rebuttal ---\n\nI am satisfied with the authors response. I am keeping the same rating.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well written and very pleasant to read. Each idea is introduced carefully and well explained. Plenty of intuition is provided on the proofs and the assumptions. Despite its simplicity, the problem addressed is fundamental and can provide some building block intuition on learning a single neuron. For these reasons, I recommend the paper to be accepted. \n\nSome comments:\n- The proofs and intuitions depend highly on the choice of the ReLu activation. While this is indeed the most standard non-linearity, I expect a lot of the results to break down when choosing an other activation. I wonder what happens in this case.\n\n- Some of the previous work consider gradient descent on the empirical loss (or SGD), instead of the population loss. This would also lead to a quite different analysis. I wonder if some concentration of landscape type analysis, similar to Mei et al. 2016 (this reference should be updated), could work, and if not what would break down in the analysis? \n\n- The negative results seem also to break down if several neurons are used.\n\nTo the best of my knowledge, this is indeed the first work that considers the case with non-zero bias and I think it would be of interest to the NeurIPS community.\n\nTypo: the standard notation is $g = \\Omega (f)$ if $g \\geq c \\cdot f$ for some $c>0$. I think you should add a minus in $e^{\\Omega (d)}$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "sBRYUffFOAc", "reviewer": "Reviewer_K5Jf", "summary": "The paper considers the task of learning ReLU with a bias term and shows that gradient descent converges to global minimum under reasonable data and initialization assumptions. Moreover, they also prove a two \"hardness\" theorems showing that having the bias makes the landscape more complicated, and this justifies the problem deserves further research. ", "questions": "", "limitations": "", "rating": 7, "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": "Update \n----\nI have read the author(s)' response to my review and maintain my rating. \n\nOriginality\n---\nLearning a single ReLU is a classic task. The paper considers the task of learning ReLU with a bias term, using GD method, which has not been studied before in the literature. \n\nSome proof techniques in the paper are not new, as they largely follow from similar paradigm from Yehudai and Shamir [2020]. \n\nThe paper discusses related work in sufficient depth. A missing reference might be an early work on learning single ReLU (with non GD method): [Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. \"Reliably learning the ReLU in polynomial time.\" In Conference on Learning Theory, 2017]. \n\nQuality\n----\nI've read the main paper and some proofs in appendix. I do not see any major issue. \n\nFor Theorem 3.1: based on the statement and its proof, the parameter $\\varepsilon$ needs to be sufficiently small, say, $\\varepsilon \\ll 1/\\sqrt{d}$. The authors may want to clarify any condition on $\\varepsilon$ here.\n\nFor Theorem 6.1, item 3 of Assumption 6.1 looks a bit confusing. Is it the case that only $x_1, x_2$ need to satisfy the bound?  \n\nClarity\n----\nOverall, I find the paper well-structured and well-written. The theorem statements are motivated and supported by intuitive explanations. \n\nSome minor points:\n1. Line 194: \"note that in Yehudai and Shamir [2020] it is shown that without any assumption on the distribution, it is impossible to ensure convergence\".  Here the work [Surbhi Goel, Adam Klivans, Pasin Manurangsi, Daniel Reichman. \"Tight Hardness Results for Training Depth-2 ReLU Networks\", In ITCS 2021] also gives worst-case hardness result (under no data assumption). It makes sense to refer to this paper as well. \n\n2. Line 269: maybe make a further comment that this is done by bounding the norm of all the training data whp, which is guaranteed by sub-gaussian distributions. \n\nSignificance \n----\nThe paper builds upon and extends an established line of work, the most closely related one being Yehudai and Shamir [2020]. I believe this work takes a good step along this line. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper addresses some limitations of their work throughout their paper. \n\nI believe the paper will not lead to any potential negative societal impact, due to its theoretical nature.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HXIC2kLn7Zn", "reviewer": "Reviewer_ahWe", "summary": "The paper studies the problem of learning a single neuron with a bias term in the realizable setting with the ReLU activation using gradient descent. The authors showed the behavior is significantly different from the case without bias both in terms of the optimization landscape and the ability of gradient methods to succeed.", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well written in general and has made concrete contribution to the fundamental problem in deep learning. The authors studied learning a single neuron with a bias term with the ReLU activation via gradient methods, which is of central interest in the theory of deep learning. They provided some failure cases to demonstrate the differences from the non-bias case. They also characterized all the critical points of the objective function and provided positive convergence results under several different assumptions.\n\nMy major concerns are as follows: Given the results from the previous work Yehudai and Shamir (2020), the results in this paper are not that surprising and less inspiring. The theoretical contribution is limited in this sense and the analysis can be seen as extension of Yehudai and Shamir (2020). The analysis has less insight compared to the previous work. The authors may analyze more complex network structure, which may give more fundamentally different optimization geometry.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors considered learning a single neuron with a bias term using gradient methods. Given the results in Yehudai and Shamir (2020), the theoretical contribution is limited. The authors may consider more complex network architecture.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "BCXtquGCF5b", "reviewer": "Reviewer_mnNc", "summary": "The work considers learning a single ReLU with the bias term using gradient based methods (and more specifically with gradient flow and gradient descent - which falls in the infinite data regime). Whereas previous works mostly considered this problem without the bias term, it (the bias term) is essential in a lot of practical applications. The paper considers gradient descent/flow with respect to standard squared error, which is practically relevant. \n\nFirst, it is shown (Section 3) that learning a single ReLU with bias via. gradient based methods is much harder than without by constructing specific negative examples. Then, under natural assumptions on the data distribution, the stationary points of the loss function is characterized and it is shown that it is a cone in Section 4 (rather than a finite set as is the case when there is no bias). The  subsequent sections explore several assumptions under which convergence can be guaranteed with high probability and with random initialization. \n\n", "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": "I believe that the paper is well written and easily accessible. \n\nThe proof techniques for the lower bounds involves construction rather artificial scenarios with negative bias where no non-trivial information can be extracted. This is easy to see since ReLU(t) = 0 whenever t < 0 and hence it is easy to construct scenarios when <w_0,x> < 0 almost surely x and w.p >= const. wrt initialization w_0 which ensures that gradient based methods don't move at all from the initialization (Theorem 3.1). Theorem 3.2 constructs a slightly less artificial examples which ensures that no movement is possible because of mismatch between labeling between w and v (i.e, they do not label any point positively at the same time). \n\nA concern which is addressed in Remark 3.3 here is that one can obtain a good enough prediction error even when w = 0 and we do not have to recover the exact vector v.  All these concerns seem to disappear when a uniformly expansive function like Leaky ReLU is used instead of ReLU, where it is not possible to hide the `'information' about v outside the support of the activation function. I feel that the authors have to note this fact in the manuscript. \n\nI believe that the non-trivial version of the problem occurs when <v,x> + b_v > 0 with some constant probability, which is partly addressed by Theorem 3.2 . \n\nThe characterization of the critical points is crisp and useful, which is then used to provide practical conditions for convergence of gradient descent under natural assumptions on the input x. One such assumption is that of positive bias which makes the problem fairly easy. I believe that the most notable contribution of the paper is Theorem 5.2 which along with Theorem 5.4 shows that when the initialization is close to 0, then we can expect global convergence with high probability.\n\nOther comments:\n1. Theorems 5.2 and 5.4 use various constants like b,c, c' etc. It would be useful to explicitly write out these constants for simple distributions like the uniform distribution on the sphere.\n2. Typo: 1-exp(\\Omega(d)) instead of 1-exp(-\\Omega(d)). \n3. The authors mention that GLMtron is not gradient based - which I believe is incorrect. It is indeed gradient based but with the convex proxy loss instead of the square loss. \n4. The notation in Assumption 5.3 is a bit confusing since w and v are also used for the iterate and actual parameter respectively. I understand that this choice is natural since this is exactly the subspace where this assumption is used in the proofs, but I urge the authors to reconsider.\n5. In Theorem 3.1, epsilon needs to be chosen to be very small (1/sqrt{d}) which seems artificial.\n6. In Theorem 3.2, the probability of failure is 1/2 - o_d(1). How does o_d(1)  depend on the radius parameters r and rho? In theorem 3.1, the radius had to be chosen as 1/sqrt{d} to obtain non-trivial lower bounds. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am satisfied with the limitations mentioned in Remark 3.3 and discussion following Theorem 6.2. I would add that the lower bounds are with respect to artificial distributions which are not interesting in practice and that the problems with convergence disappear when we consider activations like LeakyReLU instead of ReLU. It would also be useful to expand on Remark 3.3 and/or consider prediction error bounds.\n\nDiscussion on societal impact not applicable since this is a purely theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally find the paper to be a valuable addition to the neurips proceeding, despite some concerns on the originality (i.e., the paper seems to be a direct extension of prior works in terms of the problem setup and proof techniques.) The AC recommends the authors to discuss the relationship with prior works (on a both conceptual level and low-level technical level) more prominently. 

Decision: Accept (Poster)