Learning a Single Neuron with Bias Using Gradient Descent

Abstract:
We theoretically study the fundamental problem of learning a single neuron with a bias term (x 7→ σ(〈w,x〉+ 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.

text: We theoretically study the fundamental problem of learning a single neuron with a bias term (x 7→ σ(〈w,x〉+ 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.

heading: 1 Introduction
text: Learning a single ReLU neuron with gradient descent is a fundamental primitive in the theory of deep learning, and has been extensively studied in recent years. Indeed, in order to understand the success of gradient descent on complicated neural networks, it seems reasonable to expect a satisfying analysis of convergence on a single neuron. Although many previous works studied the problem of learning a 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 a distribution D on Rd+1, and are labeled by a single target neuron of the form x 7→ σ(〈v,x〉), where σ : R → R is some non-linear activation function. To capture the bias term, we assume that the distribution D 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 x can be decomposed as (x̃, 1) with x̃ ∼ D̃, the vector v can be decomposed as (ṽ, bv), where ṽ ∈ Rd and bv ∈ R, and the target neuron computes a function of the form x 7→ σ(〈ṽ, x̃〉+ bv). Similarly, we can define the learned neuron as x 7→ σ(〈w̃, x̃〉+ bw), where w = (w̃, bw). Overall, we can write the objective function we wish to
∗Equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
optimize as follows:
F (w) := E x∼D
[ 1
2
( σ(w>x)− σ(v>x) )2] (1)
= E x̃∼D̃
[ 1
2
( σ(w̃>x̃ + bw)− σ(ṽ>x̃ + bv) )2] . (2)
Throughout the paper we consider the commonly used ReLU activation function: σ(x) = max{0, x}. Although the problem of learning a single neuron is well studied (e.g. Soltanolkotabi [2017], Yehudai and Shamir [2020], Frei et al. [2020], Du et al. [2017], Kalan et al. [2019], Tan and Vershynin [2019], Mei et al. [2018], Oymak and Soltanolkotabi [2018]), none of the previous works considered the problem with an additional bias term. Moreover, previous works on learning a single neuron with gradient methods have certain assumptions on the input distribution D, which do not apply when dealing with a 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 a 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 is 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 3 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 flow2 can sometimes fail with probability close to half over the initialization, even when the input distribution is uniform over a ball. In contrast, Yehudai and Shamir [2020] show that without a bias term, for the same input distribution, gradient flow converges to the global minimum with probability 1.
• In Section 4 we give a 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]) it 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 = 0. We prove that when we have a bias term, the set of critical points has a positive measure, and that there is a cone of local minima where the loss function is flat.
• In Sections 5 and 6 we show that gradient descent converges to the global minimum at a linear rate, under some assumptions on the input distribution and on 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 6 follows from some geometric arguments and extends the technique from Yehudai and Shamir [2020], Frei et al. [2020]. The analysis in Section 5 introduces a novel technique, not used in previous works on learning a single neuron, and has a more algebraic nature. Moreover, that analysis implies that under mild assumptions, gradient descent with random initialization converges to the global minimum with probability 1− eΩ(d).
• The best known result for learning a single neuron without bias using gradient descent for an input distribution that is not spherically symmetric, establishes convergence to the global minimum with probability close to 12 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 1− e−Ω(d) (see Remark 5.7).
Related work
Although there are no previous works on learning a 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 a single neuron can be solved under minimal assumptions using algorithms which are not gradient-based (such as gradient descent or SGD). These
2I.e., gradient descent with infinitesimal step size.
algorithms include the Isotron proposed by Kalai and Sastry [2009] and the GLMtron proposed by Kakade et al. [2011]. The GLMtron algorithm is also analyzed in Diakonikolas et 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 = Ω(1/ 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 in 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 a 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 a standard Gaussian distribution, without a bias term. Du et al. [2017] showed that under a certain subspace eigenvalue assumption a 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" in all directions, which does not allow for a bias term (since that requires an input distribution supported on {1} in the last coordinate). Yehudai and Shamir [2020] showed a convergence result under the realizable setting, while Frei et al. [2020] considered the agnostic and noisy settings. In Tan and Vershynin [2019] convergence guarantees are given for the absolute value activation, and a specific distribution which does not allow a 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 et 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 a single neuron with bias is also learnable using gradient descent (under certain assumptions). Agnostically learning a single neuron with non gradient-based algorithms and hardness of a agnostically learning a single neuron were studied in Diakonikolas et al. [2020], Goel et al. [2019, 2020].

heading: 2 Preliminaries
text: Notations. We use bold-faced letters to denote vectors, e.g., x = (x1, . . . , xd). For u ∈ Rd we denote by ‖u‖ the Euclidean norm. We denote ū = u‖u‖ , namely, the unit vector in the direction of u. For 1 ≤ i ≤ j ≤ d we denote ui:j = (ui, . . . , uj) ∈ Rj−i+1. We denote by 1(·) the indicator function, for example 1(t ≥ 5) equals 1 if t ≥ 5 and 0 otherwise. We denote by U([−r, r]) the uniform distribution over the interval [−r, r] in R, and byN (0,Σ) the multivariate normal distribution with mean 0 and covariance matrix Σ. Given two vectors w,v we let θ(w,v) = arccos ( 〈w,v〉 ‖w‖‖v‖ ) = arccos(〈w̄, v̄〉) ∈ [0, π]. For a vector u ∈ Rd+1 we often denote by ũ ∈ Rd the first d components of u, and denote by bu ∈ R 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. (2):
• Gradient descent: We initialize at some w0 ∈ Rd+1, and set a fixed learning rate η > 0. At each iteration t ≥ 0 we have: wt+1 = wt − η∇F (wt).
• Gradient Flow: We initialize at some w(0) ∈ Rd+1, and for every time t ≥ 0, we set w(t) to be the solution of the differential equation ẇ = −∇F (w(t)). This can be thought of as a continuous form of gradient descent, where the learning rate is infinitesimally small.
The gradient of the objective in Eq. (1) is:
∇F (w) = E x∼D
[( σ(w>x)− σ(v>x) ) · σ′(w>x)x ] . (3)
Since σ is the ReLU function, it is differentiable everywhere except for 0. Practical implementations of gradient methods define σ′(0) to be some constant in [0, 1]. Following this convention, the gradient
used by these methods still correspond to Eq. (3). We note that the exact value of σ′(0) has no effect on our results.

heading: 3 Negative results
text: In this section we demonstrate that adding bias to the problem of learning a 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 et al. [2017], Tan and Vershynin [2019]) considered assumptions on the input distribution, which require enough "spread" in all directions (for example, a 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 a ball around the origin. We note that due to Theorem 6.4 from Yehudai and Shamir [2020], we know that gradient flow on a 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 w0 is initialized in the exact direction −v, which happens with probability 0 with standard random initializations.

heading: 3.1 Initialization in a flat region
text: If we initialize the bias term in the same manner as the other coordinates, then we 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 w0 (including the bias) according to U([−1, 1]). Let > 0 and let D̃ be the uniform distribution supported on a ball around the origin in Rd of radius . Then, w.p > 1/2− √ d, gradient descent on the objective in Eq. (2) satisfies wt = w0 for all t (namely, it gets stuck at its initial point w0).
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 1 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 is applicable when is sufficiently small, e.g. 1/ √ d.

heading: 3.2 Targets with negative bias
text: Theorem 3.1 shows a difference between learning with and without the bias term. A 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 if we initialize the bias term to be exactly zero, and the input distribution is uniform over an arbitrary origin-centered ball, we might fail to converge to the global minimum for certain target neurons:
Theorem 3.2. Let D̃ be the uniform distribution on B = {x̃ ∈ Rd : ‖x̃‖ ≤ r} for some r > 0. Let v ∈ Rd+1 such that ṽ = (1, 0, . . . , 0)> and bv = − ( r − r2d2 ) . Let w0 ∈ Rd+1 such that bw0 = 0 and w̃0 is drawn from the uniform distribution on a sphere of radius ρ > 0. Then, with probability at least 12 − od(1) over the choice of w0, 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 12 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 a global minimum when bv is negative, instead it converges to a local minimum with a loss of F (0). However, the loss F (0) is determined by the input distribution. Take v = ( 1, 0, . . . , 0,− ( r − r2d2 ))> 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) = 1
2 · E x
[( σ(v>x) )2] = 1
2 · E x
[ 1(v>x ≥ 0) ( v>x )2] = 1
2 · E x
[ 1 ( x1 ≥ r − r
2d2
)( x1 − ( r − r
2d2 ))2] ≤ 1
2 · r
2
4d4 · Pr x
[ x1 ≥ r ( 1− 1
2d2
)] ≤ r2e−Ω(d) .
Thus, for any reasonable r, a local minimum with loss F (0) is almost as good as the global minimum. On the other hand, take a distribution D̃ with a support bounded in a ball of radius r, such that half of its mass is uniformly distributed in A := { x̃ ∈ Rd : x1 > r − r4d2 } , and the other half is uniformly distributed in B \A. In this case, it 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 (0) = Ω ( r d2 ) , which is arbitrarily large if r is large enough.
Although in the example given in Theorem 3.2 the objective at w = 0 is almost as good as the objective at w = v, we emphasize that w.p almost 12 gradient flow cannot reach the global minimum even asymptotically. On the other hand, in the bias-less case by Theorem 6.4 in Yehudai and Shamir [2020] gradient flow on the same input distribution will reach the global minimum w.p 1. Also note that the scale of the initialization of w0 has no effect on the result.

heading: 4 Characterization of the critical points
text: 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:
Assumption 4.1. The distribution D̃ on Rd has a density function p(x̃), and there are β, c > 0, such that D̃ is supported on {x̃ : ‖x̃‖ ≤ c}, and for every x̃ in the support we have p(x̃) ≥ β.
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], Frei et al. [2020]). We note that in Yehudai and Shamir [2020] it 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 v 6= 0, and assume that the distribution D̃ on the first d coordinates satisfies Assumption 4.1. Then w 6= 0 is a critical point of F (i.e., is a root of Eq. (3)) if and only if it satisfies one of the following:
• w = v, in which case w is a global minimum.
• w = (w̃, bw) where w̃ = 0 and bw < 0.
• w̃ 6= 0 and − bw‖w̃‖ ≥ c.
In the latter two cases, F (w) = F (0). Hence, if 0 is not a global minimum, then w is not a global minimum.
We note that F (0) = 12 Ex[σ(v >x)2], so 0 is a global minimum only if the target neuron returns 0 with probability 1.
Remark 4.3 (The case w = 0). We intentionally avoided characterizing the point w = 0, since the objective is not differentiable there (this is the only point of non-differentiability), and the gradient there is determined by the value of the ReLU activation at 0. For σ′(0) = 0 the gradient at w = 0 is zero, and this is a non-differentiable saddle point. For σ′(0) = 1 (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 σ′(0) = 1, and use a symmetric distribution, in which case the gradient at w = 0 points exactly at the direction of the target v. This is a crucial part of their convergence analysis.
We emphasize that with a bias term, there is a non-zero measure manifold of critical points (corresponding to 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 w = 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 a distribution with exponentially bounded tail, e.g. standard Gaussian. In this case, some of the critical points will instead have a 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) shows that if we do not initialize the bias of w to zero, then there is a 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 a positive probability to converge to a critical point which is not the global minimum. Hence, in order to guarantee convergence we need to have more assumptions on either the input distribution, the target v or the initialization. In the next section, we show that adding such assumptions are indeed sufficient to get positive convergence guarantees.

heading: 5 Convergence for initialization with loss slightly better than trivial
text: In this section, we show that under some assumptions on the input distribution, if gradient descent is initialized such that F (w0) < F (0) then it is guaranteed to converge to the global minimum. In Subsection 5.2, we study under what conditions this is likely to occur with standard random initialization.
5.1 Convergence if F (w0) < F (0)
To state our results, we need the following assumption: Assumption 5.1.
1. The distribution D is supported on {x ∈ Rd+1 : ‖x‖ ≤ c} for some c ≥ 1.
2. The distribution D̃ over the first d coordinates is bounded in all directions: there is c′ > 0 such that for every ũ with ‖ũ‖ = 1 and every a ∈ R and b ≥ 0, we have Prx̃∼D̃ [ ũ>x̃ ∈ [a, a+ b] ] ≤ b ·c′.
3. We assume w.l.o.g. that ‖v‖ = 1 and c′ ≥ 1.
Assumption (3) helps simplifying some expressions in our convergence result, and is not necessary. Assumption (2) requires that the distribution is not too concentrated in a short interval. For example, if 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.1 we have the following. Let δ > 0 and let w0 ∈ Rd+1 such that F (w0) ≤ F (0)− δ. Let γ = δ 3
3·122(‖w0‖+2)3c8c′2 . Assume that gradient descent runs starting from w0 with step size η ≤ γc4 . Then, for every t we have
‖wt − v‖2 ≤ ‖w0 − v‖2 (1− γη)t .
The formal proof appears in Appendix D, but we provide the main ideas below. First, note that ‖wt+1 − v‖2 = ‖wt − η∇F (wt)− v‖2
= ‖wt − v‖2 − 2η〈∇F (wt),wt − v〉+ η2‖∇F (wt)‖2 .
Hence, in order to show that ‖wt+1 − v‖2 ≤ ‖wt − v‖2 (1− γη) we need to obtain an upper bound for ‖∇F (wt)‖ and a lower bound for 〈∇F (wt),wt − v〉. Achieving the lower bound for 〈∇F (wt),wt − 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 [ w>t x ≥ 0,v>x ≥ 0 ] . We prove that if F (wt) ≤ F (0)− δ
then Prx [ w>t x ≥ 0,v>x ≥ 0 ] ≥ δc2‖wt‖ . Hence, if F (wt) remains at most F (0)− δ for every t, then a lower bound for 〈∇F (wt),wt − v〉 can be achieved, which completes the proof. However, it is not obvious that F (wt) remains at most F (0)− δ 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∇F (w) is unbounded. We show that if F (wt) ≤ F (0)− δ then wt is sufficiently far from 0, and hence the smoothness of F around wt can be bounded, which allows us to choose a small step size that ensures that F (wt+1) ≤ F (wt) ≤ F (0)− δ. Hence, it follows that F (wt) remains at most F (0)− δ for every t. As an aside, recall that in Section 4 we showed that other than w = v all critical points of F (w) are in a flat region where F (w) = F (0). Hence, the fact that F (wt) remains at most F (0)− δ for every t implies that wt 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.

heading: 5.2 Convergence for Random Initialization
text: In Theorem 5.2 we showed that if F (w0) < F (0) then gradient descent converges to the global minimum. We now show that under mild assumptions on the input distribution, a random initialization of w0 near zero satisfies this requirement. We will need the following assumption, also used in Yehudai and Shamir [2020], Frei et al. [2020]: Assumption 5.3. There are α, β > 0 s.t the distribution D̃ satisfies the following: For any vector w̃ 6= ṽ, let D̃w̃,ṽ denote the marginal distribution of D̃ on the subspace spanned by w̃, ṽ (as a distribution over R2). Then any such distribution has a density function pw̃,ṽ(x̂) over R2 such that inf x̂:‖x̂‖≤α pw̃,ṽ(x̂) ≥ β.
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‖ ≤ c} for some c ≥ 1, and Assumption 5.3 holds. Let v ∈ Rd+1 such that ‖v‖ = 1 and − bv‖ṽ‖ ≤ α · sin(π8 ) 4 . Let M = α4β sin3(π8 )
256c . Let w ∈ R d+1 such that bw = 0, θ(w̃, ṽ) ≤ 3π4 and ‖w‖ < 2M c2 . Then,
F (w) ≤ F (0) + ‖w‖2 · c 2
2 − ‖w‖ ·M < F (0).
We prove the theorem in Appendix D.1. The main idea is that since
F (w) = E x
[ 1
2
( σ(w>x)− σ(v>x) )2] = F (0) + 1
2 E x
[( σ(w>x) )2]− E x [ σ(w>x)σ(v>x) ] ≤ F (0) + ‖w‖2 · c 2
2 − ‖w‖ · E x
[ σ(w̄>x)σ(v>x) ] ,
then it suffices to obtain a lower bound for Ex [ σ(w̄>x)σ(v>x) ] . In the proof we show that such a bound can be achieved if the conditions of the theorem hold.
Suppose that w0 is such that w̃0 is drawn from a spherically symmetric distribution and bw0 = 0. By standard concentration of measure arguments, it holds w.p. at least 1 − eΩ(d) that θ(w̃0, ṽ) ≤ 3π4 (where the notation Ω(d) hides only numerical constants, namely, it does not depend on other parameters of the problem). Therefore, if w̃0 is drawn from the uniform distribution on a sphere of radius ρ < 2Mc2 , then the theorem implies that w.h.p. we have F (w0) < F (0). For such initialization Theorem 5.2 implies that gradient descent converges to the global minimum. For example, for ρ = Mc2
we have w.h.p. that F (w0) ≤ F (0) + ρ 2c2 2 − ρM = F (0)− M2
2c2 , and thus Theorem 5.2 applies with δ = M 2
2c2 . Thus, we have the following corollary:
Corollary 5.5. Under Assumption 5.1 and Assumption 5.3 we have the following. Let M = α4β sin3(π8 )
256c , let ρ = M c2 , let δ =
M2 2c2 , and let γ = δ3 3·122(ρ+2)3c8c′2 . Suppose that − bv ‖ṽ‖ ≤ α · sin(π8 ) 4 ,
and w0 is such that bw0 = 0 and w̃0 is drawn from the uniform distribution on a sphere of radius ρ. Consider gradient descent with step size η ≤ γc4 . Then, with probability at least 1− e
Ω(d) over the choice of w0 we have for every t: ‖wt − v‖2 ≤ ‖w0 − v‖2 (1− γη)t .
We note that a similar result holds also if w̃0 is drawn from a normal distribution N (0, ρ 2
d I).
Remark 5.6 (The assumption on bv). The assumption − bv‖ṽ‖ ≤ α · sin(π8 )
4 implies that the bias term bv may be either positive or negative, but in case it is negative then it cannot be too large. This assumption is indeed crucial for the proof, but for "well-behaved" distributions, if this assumption is not satisfied (for a large enough α), then the loss at F (0) is already good enough. For example, for a standard Gaussian distribution and for every > 0, we can choose α large enough such that for any bias term (positive or negative) we either: (1) converge to the global minimum with a loss of zero, or; (2) converge to a local minimum with a loss of F (0), which is smaller then . Moreover, we can show that by choosing α appropriately, and using the example in Theorem 3.2, if − bv‖ṽ‖ ≥ 2α then gradient flow will converge to a non-global minimum with loss of F (0). This means that our bound on α is tight up to a constant factor. For a further discussion on the assumption on bv, and how to choose α see Appendix E.
Previous papers have shown separation between random features (or kernel) methods and neural networks in terms of their approximation power (see Yehudai and Shamir [2019], Kamath et al. [2020], and the discussion in Malach et al. [2021]). These works show that under a standard Gaussian distribution, random features cannot even approximate a single ReLU neuron, unless the number of features is exponential in the input dimension. That analysis crucially relies on the single neuron having a non-zero bias term. In this work we complete the picture by showing that gradient descent can indeed find a near-optimal neuron with non-zero bias. Thus, we see there is 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 a 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 12 − od(1). 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− eΩ(d). Moreover, our proof technique can be easily adapted to the setting of learning a single neuron without bias using gradient descent on a single neuron without bias, namely, the setting studied in Yehudai and Shamir [2020]. It can be shown that in this setting gradient descent converges w.h.p to the global minimum. Thus, our technique allows us to improve the result of Yehudai and Shamir [2020] from probability 1 2 − od(1) to probability 1− e Ω(d).

heading: 6 Convergence for spread and symmetric distributions
text: In this section we show that under a certain set of assumptions, different from the assumptions in Section 5, 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 target vector v satisfies that bv ≥ 0 and ‖ṽ‖ = 1.
2. The distribution D̃ over the first d coordinates is spherically symmetric.
3. Assumption 5.3 holds, and denoting by τ := Ex̃∼D̃[|x̃1x̃2|] Ex̃∼D̃[x̃21]
, then α ≥ 2.5 √ 2 ·max {
1, 1√ τ
} where
α is from Assumption 5.3. 4. Denote by c := Ex̃∼D̃ [ ‖x̃‖4 ] , then c <∞.
We note that item (3) considers x1, x2, but due to the assumption on the symmetry of the distribution (item (2)), the assumption in item (3) holds for every xi, xj . Under these assumptions, we prove the following theorem:
Theorem 6.2. Assume we initialize w0 such that ‖w0 − v‖2 < 1, bw0 ≥ 0 and that Assumption 6.1 holds. Then, there is a universal constant C, such that using gradient descent on F (w) with step size η < C · βcα2 min{1, τ} yields that for every t we have ‖wt − v‖
2 ≤ (1− ηλ)t‖w0 − v‖2 , for λ = C · βcα2 .
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 (bv ≥ 0) and spherically symmetric distributions D̃. Also we require a certain technical assumption on the the distribution, as specified by τ , which are satisfied for standard spherically symmetric distributions, but is a bit non-trivial3. Finally, the assumption on the initialization (‖w0 − v‖2 < 1 and bw0 ≥ 0) is much more restrictive (although see Remark 6.3 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 w0 such that ‖w0 − v‖2 < 1 and bw0 ≥ 0, we get a convergence rate that only depends on the input distribution. On the other hand, in Theorem 5.2, the convergence rate depends on the parameter δ which depends on the initialization. Also, the distribution is not necessarily bounded – we only require its fourth moment to be bounded.
Remark 6.3 (Random initialization). For bv = 0 the initialization assumption (‖w0 − v‖2 < 1) is satisfied with probability close to 1/2 with standard initializations, see Lemma 5.1 from Yehudai and Shamir [2020]). For bv > 0, a similar argument applies if bw is initialized close enough to bv.
The proof of the theorem is quite different from the proofs 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 [2020] to the case of adding a bias term. Specifically, we show a lower bound on 〈∇F (w),w − v〉, which depends on both the angle between w̃ and ṽ, and the bias terms bw and bv (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 − bw‖w̃‖ does not get too large. Note that due to Theorem 4.2, we know that keeping this term small 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.

heading: 7 Discussion
text: 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 a bias term makes the problem more difficult than without a bias term. Next, we gave a characterization of the critical points of the problem under some assumptions on the input distribution, showing that there is a manifold of 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 a single neuron either considered nonstandard algorithms (e.g. Isotron), or required assumptions on the input distribution which do not
3For example, for standard Gaussian distribution, we have that τ = 2 π ≈ 0.63, hence we can take α = 4.5, and β = 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 a single neuron with a bias term using gradient methods.
In this work we focused on the gradient descent algorithm. We believe that our results can also be extended to the commonly used SGD algorithm, using similar techniques to 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 a bias term. These settings can include convolutional networks, two layers neural networks, and agnostic learning of a single neuron.

heading: Acknowledgements
text: This research is supported in part by European Research Council (ERC) grant 754705.

Review summaries:
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).   --- after rebuttal ---  I am satisfied with the authors response. I am keeping the same rating.

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.   First, 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.