Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds

Introduction

It is well known that artificial neural networks (NNs) can approximate any real-valued function. Fundamental results show that a NN with a single hidden layer provides a universal representation up to arbitrary approximation, with the number of hidden units needed depending on the function being approximated and the desired accuracy.

Besides their generality, an important feature of NNs is the ease of training them — gradient descent (GD) is used to minimize the error of the network, measured by a loss function of the current weights. This seems to work across a range of labeled data sets. Yet despite its tremendous success, there is no satisfactory explanation for the efficiency or effectiveness of this generic training algorithmIndeed, one might consider this a miraculous feat of engineering and even ask, is there anything to explain rigorously? We are not entirely comfortable with this view and optimistic of some life beyond convexity..

The difficulty is that even for highly restricted classes of NNs, natural loss functions such as the mean squared loss have a highly non-convex landscape with many nonoptimal local minima. However, when data is generated from a model with random weights, GD (the stochastic version with a small batch size) seems to consistently learn a network with error close to zero. This raises the prospect of a provable guarantee, but there are two complicating experimental observations. First, the randomness of the initialization appears essential (standard in practice) as in experiments it is possible to remain stuck at higher error. Second, we observe smaller error (and it decreases more quickly) when the model size used for training is made larger; in particular, for the realizable case (when the data is itself labeled by a NN), we train using many more units than the original. This aspect is also commonly encountered in the training of large NNs on real data — even with huge amounts of data, the size of the model used can be larger.

In this paper we give nearly matching upper and lower bounds that help explain the phenomena seen in practice when training NNs. The upper bounds are for GD and the lower bounds are for all statistical query algorithms. We summarize them here, and present them formally in the next section.

Our algorithmic result is an agnostic upper bound on the approximation error and time and sample complexity of GD with the standard mean squared loss function. Despite training only the output layer weights, our novel proof techniques avoid using any convexity in the problem. Since our analysis does not rely on reaching a global minimum, there is reason to hope the techniques will extend to nonconvex settings where we can in general expect only to find a local minimum. Prior results along this line were either for more complicated algorithms or more restricted settings; the closest is the work of Andoni et al. where they assume the target function is a bounded degree polynomial. A detailed comparison of results is given in Section 1.3. As a corollary of our convergence analaysis, we obtain a rigorous proof of the “spectral bias” of gradient descent observed experimentally in .

The upper bound shows that to get close to the best possible degree $k$ polynomial approximation of the data, it suffices to run GD on a NN with $n^{O(k)}$ units, using the same number of samples. It suffices to train the output layer weights alone. This is an agnostic guarantee. We prove a matching lower bound for solving this polynomial learning problem over the uniform distribution on the unit sphere, for any statistical query algorithm that uses tolerance inversely proportional to $n^{\Omega(k)}$. Thus, for this general agnostic learning problem, GD is as good as it gets.

We initialize our NNs by choosing the vectors $u\in W$ independently from $D$, and setting each $b_{u}$ to .

Our first theorem is for training networks of sigmoid gates. The same statement holds for ReLU activation units and even functions $g$.

Next we state a more general theorem. This will apply to a large class of activation functions. The main property we need of the activation function is that it should not be a low-degree polynomial. We first introduce additional notation. (See Section 2 for related definitions and background.) We denote by $\mathcal{H}_{n,k}$ the set of spherical harmonics of degree $k$ on the sphere $S^{n-1}$.

Since the dimension $n$ is uniform throughout this paper, we will abbreviate our notation and refer to $(S,\alpha)$-activations. The set $S$ will not generally depend on $n$, but the quantity $\alpha=\alpha(n)$ generally will (see, e.g., Lemma 2.6).

For example, the commonly used sigmoid gate $\sigma_{\textrm{sig}}(x)=1/(1+e^{-x})$ is an $(S,\alpha)$-activation function for $S$ the odd integers less than $k$ and $\alpha=n^{-O(k)}$. Similarly, ReLU gates are $(S,\alpha)$-activation functions for subsets $S$ of the even integers.

This general theorem has the following corollary in the realizable case, when data is generated by a one-hidden-layer NN. In this case, the function can be approximated by a low-degree polynomial. In order to allow for this approximation guarantee, and to side-step previous statistical query lower bounds , we guarantee some degree on nondegeneracy by focusing on unbiased NNs, i.e., networks without additive bias terms (as in Eq. (1)).

The use of sigmoid units in Corollary 1.4 is not essential, but the bounds on network size and training time will depend on the specific activation function chosen.

Spectral bias.

As a consequence of our techniques, we give a proof of the “spectral bias” phenomenon observed experimentally in . The experiments of showed that neural networks trained via gradient descent learned low Fourier frequencies more quickly than higher frequencies, which the authors propose as a mechanism to explain generalization performance of deep learning. We prove that low frequencies are indeed learned more quickly than high frequencies, where “low frequencies” and “high frequencies” are understood as low and high degree harmonic components of a function.

To quantify the relative speed of learning, we introduce additional notation.

Lower bounds.

The bound is the standard deviation of $t$ independent Bernoulli coins with desired expectation, i.e., the error that even a random sample of size $t$ would yield. The SQ complexity of an algorithm is given by the number of queries and the batch size $t$. The remaining computation is unrestricted and can use randomization. We will also give lower bounds against the $\operatorname{1-STAT}$ oracle, which responds to queries with a single honest bit. Given a distribution $D$ over $X$ and a query function $h:X\to\{0,1\}$, the $\operatorname{1-STAT}$ oracle responds with a single value $h(x)$, where $x\sim D$ .

Choosing a useful SQ model for regression problems is nontrivial. We discuss some of the pitfalls in Section 4. Our lower bounds concern three query models.

Let $\varepsilon>0$. For all $k,\lambda>0$ and all sufficiently large $n$ and $d<\exp(n^{1/2-\varepsilon})$, there exists a family $\mathcal{C}$ of degree-$k$ polynomials on $S^{n}$ with $|\mathcal{C}|=d$ such that if a randomized SQ algorithm learns $\mathcal{C}$ to regression error less than any fixed constant with probability at least $1/2$:

it requires at least $\Omega(d)$ queries, if the queries are inner product queries to $\operatorname{VSTAT}(n^{\Omega(k)})$;

it requires at least $\Omega(d)$ queries, if the queries are $L^{\infty}$-normalized $\lambda$-Lipschitz queries to $\operatorname{VSTAT}(n^{\Omega(k)}/\lambda)$;

for $d=n^{\Omega(k)}$, it requires at least $n^{\Omega(k)}/\lambda$ queries, if the queries are $L^{\infty}$-normalized queries to $\operatorname{1-STAT}$ with Gaussian noise of variance $1/\lambda^{2}$

where all the hidden constants depend on $\varepsilon$ only.

2 Approach and techniques

The gradient of the loss function with respect to any outer layer weight can be viewed as a spherical transform of the current residual error. More precisely, if the current function $f$ is computed by an unbiased single hidden-layer NN with output-layer weights $b_{u}$, as in Eq. (1), and the residual error with respect to the target function $g$ is $H=g-f$, then for any $u$,

The latter expectation is quite special when the domain of integration is the unit sphere. Different choices of the function $\phi$ correspond to different spherical transformations. For example, $\phi(u\cdot x)$ being the indicator of $u\cdot x\geq 0$ is the hemispherical transform, while $\phi(u\cdot x)=1$ iff $u\cdot x=0$ is the Radon transform, etc. This type of transformation

In particular, the harmonic polynomials are eigenfunctions of the operator $\mathcal{J}_{\phi}$. Moreover, since there exists an orthonormal basis of harmonic polynomials for $L^{2}$ functions over the unit sphere, any function (in our case the residual $H$) has zero norm iff the corresponding transform has zero norm (assuming the function $\phi$ has nonzero coefficients $\alpha_{n,k}(\phi)$).

Thus, if the current residual error is given by some function $H$, then the empirical gradient of the mean-squared loss with respect to a set $X$ of labeled examples is $T_{X}(H)$ (see Section 3).

Show that, with a large enough set $X$ of samples, the empirical gradient operator $T_{X}$ approximates the Funk transform $\mathcal{J}_{\phi}$ as an operator on the space of residual error functions (Lemmas 3.5 and 3.6)

Bound the rate at which error from the approximation of $T_{X}$ by $\mathcal{J}_{\phi}$ accumulates over multiple rounds of GD (Lemmas 3.7 and 3.8)

Estimate the final loss in terms of the distance of the target function from the space of low-degree harmonic polynomials — i.e., the distance from the most significant eigenspaces of $\mathcal{J}_{\phi}$ (see proof of Lemma 3.3)

Our analysis does not use the fact that the optimization produces an approximate global minimum; hence, there is a greater hope of generalizing to nonconvex regimes where we expect to instead only reach a local minimum in general. Another pleasant feature of our analysis is that we need not directly prove a “representation theorem” showing that the hypothesis minimizing the population loss is a good approximation to the target function; instead, we can derive such a result for free, as a corollary to our analysis. That is, since we prove directly that GD on the output layer weights of a single-layer NN with randomly-initialized gates results in small loss, it follows that any low-degree harmonic polynomial is in fact approximated by such a network. Our hope is that this new approach offers an interesting possibility for understanding GD in more difficult settings.

A practical consequence of our method of analysis is that we can easily prove a “spectral bias” result, showing the lower degrees are learned more quickly than higher degrees, as was suggested experimentally in (see Theorem 1.6).

The upper bound guarantees hold for the agnostic learning problem of minimizing the least squares error, and the bound is with respect to the best degree $k$ polynomial approximation. The size of the network needed grows as $n^{\Omega(k)}$, as does the time and sample complexity. We show that this unavoidable for any SQ algorithm, including GD and its variants on arbitrary network architectures. The “hard” functions used for the lower bound will be generated by spherical harmonic polynomials. Specifically, we use the univariate Legendre polynomial of degree $k$ in dimension $n$, denoted as $P_{n,k}$, and also called the Gegenbauer polynomial (see Section 2 for more background). We pick a set of unit vectors $u$ and for each one we get a polynomial $f_{u}(x)=P_{n,k}(u\cdot x)$. We choose the vectors randomly so that most have a small pairwise inner product. Then querying one of these polynomials gives little information about the others (on the same input $x$), and forces an algorithm to make many queries. As in the work on SQ regression algorithms of , it is essential not only to bound the pairwise correlations of the “hard” functions themselves, but also of arbitary “smoothed” indicator functions composed with the hard family. This is accomplished by using a concentration of measure inequality on the sphere to avoid regions where these indicators are in fact correlated. In contrast to those earlier SQ regression lower bounds, we obtain bounds on the sensitivity parameter $t$ for the $\operatorname{VSTAT}(t)$ oracle that scales with the number of queries $d$ and the degree $k$.

3 Related work

Explaining the success of deep NNs and GD for training NNs has been a challenge for several years. The trade-off between depth and size for the purpose of representation has been rigorously demonstrated . Moreover, there are strong complexity-theoretic and cryptographic-assumption based lower bounds to contend with . These lower bounds are typically based on Boolean functions and “hard” input distributions. More recent lower bounds hold even for specific distributions and smooth functions, for basic GD , and even realizable smooth functions for any SQ algorithm and any product logconcave input distribution . These earlier lower bound constructs are degenerate in the sense that they rely on data generated by networks whose bias and weight vectors have unbounded Euclidean norm as the dimension increases. In contrast, the constructions used in this paper match a corresponding upper bound almost exactly by making use of generic harmonic polynomials in the construction, apply to a significantly broader family of functions, and achieve a much stronger bound on the sensitivity parameter $t$.

Upper bounds have been hard to come by. Standard loss functions, even for one-hidden-layer networks with an output sum gate, are not convex and have multiple disconnected local minima. One body of work shows how to learn more restricted functions, e.g., polynomials and restricted convolutional networks . Another line of work investigates classes of such networks that can be learned in polynomial time, notably using tensor methods and polynomial kernels , more direct methods with assumptions on the structure of the network and a combination of tensor initialization followed by GD . A recent paper shows that the tensor method can be emulated by GD by adding a sufficiently sophisticated penalty to the objective function . Earlier work gave combinatorial methods to learn random networks , guarantees for learning linear dynamical systems by GD and ReLU networks with more restrictive assumptions . Representation theorems analogous to our own were also proved in , and a very general analysis of GD is given in .

Our analysis is reminiscent of the well-known random kitchen sinks paper , which showed that GD using a hard upper bound on the magnitude of coefficients (in practice, an $L_{1}$ penalty term) with many random features from some distribution achieves error that converges to the best possible error among functions whose coefficients are not much higher than those of the corresponding densities of the sampling distribution. While this approach has been quite insightful (and effective in practice), it (a) does not give a bound for standard GD (with no penalty) and (b) does not address functions that have very different support than the sampling distribution. Our bounds compare with the best possible polynomial approximations and are essentially the best possible in that generality for randomly chosen features.

The work of Andoni et al. shows that GD applied to learn a bounded degree polynomial, using a 1-hidden-layer network of exponential gates, converges with roughly the same number of gates (and a higher iteration count, $\mbox{poly}(1/\varepsilon)$ instead of $\log(1/\varepsilon)$ to achieve error $\varepsilon$). A crucial difference is that our analysis is agnostic and we show that GD converges to the error of the best degree $k$ approximation of the target function given sufficient many gates. We also state our results for general and commonly-used activation functions, rather than the $e^{z}$ gate analyzed in , and obtain explicit sample complexity bounds. Of course, the proof technique is also novel; we obtain our representation theorem as a side effect of our direct analysis of GD, rather than the other way around.

Spherical Harmonics

We now recall the basic theorems of spherical harmonics we will require. A more detailed treatment can be found in .

The following proposition is immediate from Cauchy-Schwarz.

We have $\|\mathcal{J}_{\phi}(G)\|_{\infty}\leq\|\phi\|_{2}\|G\|_{2}$.

By Proposition 2.3, $\mathcal{J}_{\phi}$ has bounded norm as an operator on $L^{2}(S^{n-1})$ and so by Theorem 2.2,

We first prove a general lemma describing the harmonic spectrum of a wide class of functions, and then derive estimates of the spectra for commonly used activation functions.

By Rodrigues’ formula (see [18, Proposition 3.3.7]),

Hence, by the bounded convergence theorem,

where $B(a,b)$ is the Euler beta function. Indeed, integrating by parts, we see that if $i<k$ the expression is , and otherwise

After a change of variables $u=t^{2}$, this latter integral is by definition $B((i-k+1)/2,(n-3)/2+k+1)$.

Now for any $i>j\geq k$ of the same parity $\bmod 2$, if $a_{j}\neq 0$ we estimate

In particular, whenever $a_{k}\neq 0$ we have

Let $\phi(t)=1/(1+e^{-t})$ be the standard sigmoid function. Then for any positive integer $d$, $\phi$ is an $(S,n^{-d-O(1)})$-activation function, where $S$ contains and all odd integers less than $d$.

Let $\phi(t)=\log(e^{t}+1)$ be the “softplus” function. Then for any positive integer $d$, $\phi$ is an $(S,n^{-d-O(1)})$-activation function, where $S$ contains $1$ and all even integers less than $d$.

The statement follows from Lemma 2.6 by computing the relevant Taylor series. ∎

We can also perform a similar computation for ReLU activations. (A more general estimate is given in [3, Appendix D.2].)

Let $\phi(t)=\max\{t,0\}$ be the ReLU function. Then for any positive integer $d$, $\phi$ is an $(S,n^{-d-O(1)})$-activation function, where $S$ contains $1$ and all even integers less than $d$.

Analysis of Gradient Descent

We now define notation that will be used throughout the rest of this section.

We fix $\varepsilon>0$, the approximation error we will achieve over the projection of $g$ to harmonics of degrees in $S$. We define quantities $t$, $\delta$, and $m$ as follows, using absolute constants $c_{t}$, $c_{\delta}$, and $c_{m}$ to be defined later in the proof. The maximum number of iterations of gradient descent will be

We define $\delta$ to be an error tolerance used in certain estimates in the proof,

Finally, we define $m$ to be the number of hidden units (so $|W|=m$), as well as the number of samples,

We recall the definition in Eq. (3) of the operator

We denote by $H_{i}=g-f_{i}$ the $i$th residual. We define $a_{0}(u)=0$ and, for $i\geq 1$, set $a_{i}(u)=a_{i-1}(u)+(1/m)T_{X}H_{i}(u)$.

We therefore have the following two propositions which describe how the neural network evolves over multiple iterations of gradient descent.

Thus, a single iteration of gradient descent with learning rate $1/(2m)$ will update the weight $b_{u}$ by adding $(1/m)T_{X}(g-f)(u)$. The proposition now follows by induction on $i$. ∎

For all $i\geq 0$, $f_{i+1}=f_{i}+T_{W}T_{X}H_{i}$.

By the definitions of $f_{i}$ and $a_{i}$, we have

Having introduced and explained the necessary notation, we now state our main technical estimate, the following Lemma 3.3, which will be proved at the end of this section. For the rest of Section 3, we write $\Delta H_{i}=H_{i+1}-H_{i}=f_{i+1}-f_{i}$ for the change in the residual at step $i$, and we abbreviate $\mathcal{J}=\mathcal{J}_{\phi}$.

Suppose $i\leq t$ and $\|H_{j}^{(S)}\|_{2}\geq\varepsilon$ for all $j\leq i$. Then with high probability

Given Lemma 3.3, proved in the following Section 3.2, the main results stated in Section 1.1 are straightforward.

By Lemma 3.3, as long as $\|H_{i}\|_{2}^{2}$ remains larger than $\varepsilon$ and $i\leq t$, we have $\|\Delta H_{i}-\mathcal{J}^{2}H_{i}\|_{2}\leq O(\delta\|g\|_{2}t^{2})$. Now $(\Delta H_{i}-\mathcal{J}^{2}H_{i})^{(S)}$ and $(\Delta H_{i}-\mathcal{J}^{2}H_{i})^{(\overline{S})}$ are orthogonal, so also $\|(\Delta H_{i}-\mathcal{J}^{2}H_{i})^{(S)}\|_{2}\leq O(\delta\|g\|_{2}t^{2})$. Therefore, rewriting $\Delta H_{i}=H_{i+1}-H_{i}$, we have

For a sufficiently small choice of the constant $c_{\delta}$ defining $\delta$ (Eq. (6)), under the assumption that $\|H_{i}^{(S)}\|_{2}^{2}\geq\varepsilon$, we can take the $O(\delta\|g\|_{2}^{2}t^{2})$ term to be at most $(\alpha^{4}/2)\|H_{i}^{(S)}\|_{2}^{2}$. Therefore,

Since $\|H_{0}^{(S)}\|_{2}\leq\|H_{0}\|_{2}=\|g\|_{2}$, for some $s=O(\alpha^{-4}\log(\|g\|/\varepsilon))<t$ we have $\|H_{s}^{(S)}\|_{2}^{2}<\varepsilon$ (assuming a sufficiently large choice of the constant $c_{t}$ defining $t$ in Eq. (5)). Then

Theorem 1.1 now follows from Theorem 1.3, in view of Lemma 2.7.

To prove Corollary 1.4, we first recall an approximation lemma of Livni et al. [25, Lemma 2]:

Let $\phi(t)=1/(1+e^{-t})$ denote the sigmoid function. For every $\varepsilon>0$, there is a polynomial $p$ of degree $d=O(L\log(L/\varepsilon))$ such that $|p(t)-\phi(t)|<\varepsilon$ for all $t\in[-L,L]$.

2 Proof of Lemma 3.3

We now prove Lemma 3.3. Essentially, the lemma states that the operator $T_{Z}$ approximates $\mathcal{J}$ for sufficiently large sets $Z$. We will prove Lemma 3.3 via a sequence of gradually improving estimates of the approximation of $\mathcal{J}$ by $T_{Z}$. Lemma 3.5 gives a very general approximation, which we use to prove the finer approximation described in Lemma 3.6.

In particular, the second inequality of the present lemma holds.

We now complete the proof of the first inequality. For all choices of $Z$ and $u$, using Proposition 2.3, we have

In the following Lemma 3.6 we prove a finer-tuned approximation of the operator $\mathcal{J}$ by both $T_{X}$ and $T_{W}$. Since Lemma 3.5 doesn’t give a sufficiently tight approximation between the operators simultaneously for every $L^{2}$-function on $S^{n-1}$, we restrict our attention to the subspace we care about, namely, the functions spanned by the $\phi_{x}$ for $x\in W\cup X$.

With probability $1-1/m$ over the choice of $W$ and $X$, the following statements are all true:

For all $u\in W$, we have $\|T_{X}\phi_{u}-\mathcal{J}\phi_{u}\|_{2}\leq\delta$;

For all $x\in X$ we have $\|T_{W}\phi_{x}-\mathcal{J}\phi_{x}\|_{2}\leq\delta$

For all $x\neq y\in X$, we have $|T_{W}(\phi_{x})(y)-\mathcal{J}(\phi_{x})(y)|\leq\delta/2$;

We will use Markov’s inequality to bound the probability that $T_{W}(\phi_{x})$ is far from $\mathcal{J}(\phi_{x})$ at a random input, followed by a union bound over the choice of $W$ and the choice of $X$. We require the constant $c_{m}$ to be sufficiently large.

In detail, we have $m\geq c_{m}\log(\|g\|_{\infty}/\delta)(\|g\|_{\infty}/\delta^{2})$, so for any fixed $k,c_{0}>0$, we can set $c_{m}$ sufficiently large that there is some $p<1/m^{k}$ also satisfying

Therefore, by Markov’s inequality, with probability $1-1/(2m)$ over the choice of $W$, Eqs. (10) and (11) both hold for a random $x\sim D$ with probability $1-1/(8m^{2})$.

Similar to Eq. (10), with $X$ in place of $W$ and $g$ in place of $\phi_{x}$, statement (1) of the present lemma holds with probability $1-1/(16m^{3})>1-1/(8m)$ over the choice of $X$. Furthermore, for any fixed $X$, taking a union bound over $W$, we have with probability $1-m/(16m^{3})>1-1/(8m)$ that statement (2) holds.

Now suppose $W$ is such that Eq. (10) holds for a random $x\sim D$ with probability at least $1-1/(8m^{2})$; as we have already observed, this is the case with probability at least $1-1/(2m)$ over the choice of $W$. Then by a union bound over $X$, it then follows that with probability $1-1/(8m)$ over the choice of $X$, statement (3) holds. Finally, suppose similarly that $W$ is such that Eq. (11) holds for a random $x\sim D$ with probability at least $1-1/(8m^{2})$. By a union bound, we with probability at least $1-1/(8m)$ that for all $x\in X$,

Now, fixing such an $x\in X$, a union bound over all $y\in X$ with $y\neq x$ gives that

with probability $1-1/(16m^{2})$. Taking another union bound over all $x\in X$, we get statement (4) with probability $1-1/(16m)$ as well. Overall, statements (1)–(4) hold with probability at least $1-1/m$. ∎

For the remainder of this section, we use the notation $\alpha_{i}=\max_{u\in W}|a_{i}(u)|$ and $\beta_{i}=\max_{x\in X}|H_{i}(x)|$.

We focus on the second step of our analysis, as outlined in Section 1.2, bounding the rate at which error from the approximations of $\mathcal{J}$ described above accumulates over multiple iterations of GD. More precisely, we control the norm of $f$, measured via $\alpha_{i}$ and $\beta_{i}$. The statements are given in the following two lemmas.

By Lemma 3.6 (3), since $T_{W}$ and $\mathcal{J}$ are linear operators,

By Proposition 3.2, we have $\Delta H_{i}=T_{W}T_{X}H_{i}$. Therefore, since $\|\mathcal{J}(h)\|_{2}\leq\|h\|_{2}$ for all functions $h$, we have altogether that

For all $i\geq 0$, we have $\alpha_{i+1}\leq\alpha_{i}+\beta_{i}/m$. Furthermore, if statement (4) of Lemma 3.6 holds, then for all $i\geq 0$, we have

For the first inequality, we have by definition that for all $u\in W$

For the second inequality, fix $y\in X$. Using statement (4) of Lemma 3.6 we compute

By Proposition 2.3 and the first statement of Lemma 3.7,

$\|\Delta H_{i}-\mathcal{J}^{2}(H_{i})\|_{2}\leq O(\delta\|g\|_{2}(i+1)^{2})$

(So the statement of the lemma follows from estimate (3) and $i\leq t$.)

Since $f_{0}=0$, $a_{0}=0$, and $H_{0}=g$, the base cases are all trivial. Fix $0<i\leq t$ and assume estimates (1)–(4) hold for all $j<i$. We first prove that estimate (1) holds for $i$. Indeed, using the second statement of Lemma 3.8, and then simplifying using the inductive hypothesis for estimates (1), (2) and (4), we have

This latter expression is at most $\beta_{i-1}+\|g\|_{2}+O(\|g\|_{2}/t)$, using the fact that $i<t$ and the definitions of $t$, $\delta$, and $m$ in Eqs. (5), (6), and (7). Estimate (1) now follows by induction.

Similarly, from the first statement of Lemma 3.8 and from estimate (1), we have

By the second statement of Lemma 3.7, and using estimates (1) and (2), we have

giving estimate (3) by induction. Rewriting $\Delta H_{i}=H_{i+1}-H_{i}$, we have $\|H_{i+1}\|_{2}\leq\|H_{i}\|+O(\delta\|g\|_{2}(i+1)^{2})$. Now by estimate (4), $\|H_{i}-\mathcal{J}^{2}H_{i}\|_{2}\leq\|g\|_{2}$, and so

For a sufficiently small choice of the constant $c_{\delta}$ defining $\delta$ (Eq. (6)), under the assumption that $\|H_{i}^{(S)}\|_{2}^{2}\geq\varepsilon$, we can take the $O(\delta\|g\|_{2}^{2}(i+1)^{2})$ term to be at most $(\alpha^{4}/2)\|H_{i}^{(S)}\|_{2}^{2}$. Therefore,

The norm $\|H_{i}\|_{2}$ of the residual is therefore monotonically decreasing in $i$, giving estimate (4). ∎

Statistical query models

In particular, with a constant error tolerance $\tau$, such a family $\mathcal{C}$ can be learned using $\log|\mathcal{C}|$ statistical queries.

In particular, a statistical query model allowing arbitary measurable and bounded queries would allow efficiently learning any finite class of real-valued functions, perhaps perturbed slightly to ensure the functions disagree pairwise almost everywhere.

Furthermore, arbitrary measurable query functions don’t have concise descriptions anyway. So it is reasonable to require “well-behaved” query functions. We now describe three “well-behaved” statistical query settings, and prove strong lower bounds against algorithms learning degree-$k$ polynomials on $S^{n-1}$ in each setting.

We recall the definition of statistical dimension, denoting by $\rho_{D}(\mathcal{C})$ the average correlation among the functions of $\mathcal{C}$, i.e.,

where $\rho_{D}(f,g)=\operatorname*{Cov}_{D}(f,g)/\sqrt{\operatorname*{Var}(f)\operatorname*{Var}(g)}$.

The following theorem can be proved in a manner almost identical to the proof of [12, Theorem 2.7].

Let $u,v\in S^{n}$ be such that $|u\cdot v|=t$. Then

By the Funk–Hecke theorem, $\|f^{(k)}_{u}\|_{2}=1$ We therefore have, again by the Funk–Hecke theorem,

Since $P_{n,0}(t)=1$ and $P_{n,1}(t)=t$ (by [18, Proposition 3.3.7]), the result follows. ∎

We can now prove the SQ lower bound for this class of queries.

Taking a random (uniform) set $B$ of $d$ vectors $u\in S^{n}$, let $\mathcal{C}=\{f_{u}^{(k)}:u\in B\}$. For any pair of distinct vectors $u,v\in B$, we have with probability $1/d^{2}$ that $t_{uv}=|u\cdot v|=O(\sqrt{(\log d)/n})$. Thus, with positive probability, we have $t_{uv}=O(\sqrt{(\log d)/n})$ for all distinct $u,v\in B$. Then by Lemma 4.4, we have

for all $u,v\in B$. The theorem now follows from Theorem 4.3. ∎

2 Lipschitz queries

We now recall the Lipschitz query model introduced in . The functions learned in that paper were already bounded, so no $L^{\infty}$ normalization is performed. We state an $L^{\infty}$-normalized version of the relationship between statistical dimension and statistical query complexity, which are an immediate consequence of those proved in .

So $\chi_{y}$ is $(1/\varepsilon)^{2}$-Lipschitz, is supported on $(y-\varepsilon,y+\varepsilon)$, and has norm $\|\chi_{y}\|_{1}=1$.

We can now prove the lower bound for this query model. We use the same family of functions as for the inner product query model, but we must now also estimate the covariances of the soft indicators of these functions, as in the following lemma. We recall our notation $f^{(k)}_{u}(x)=\sqrt{N(n,k)}P_{n,k}(u\cdot x)$.

For $w,x\in S^{n}$, we write $z_{w}(x)=\chi_{y}^{(\varepsilon)}(f^{(k)}_{w}(x))$.

Let $\zeta(t)=\chi_{y}^{(\varepsilon)}(\sqrt{N(n,k)}P_{n,k}(t))$, so $z_{w}(x)=\zeta(w\cdot x)$. Then

Now substituting $w=\sqrt{1-\alpha^{2}}x_{2}+\alpha x_{1}$, we have

Next we note that in our range of $x_{1},w$,

Taking a random (uniform) set $B$ of $d$ vectors $u\in S^{n}$, let $\mathcal{C}=\{f_{u}^{(k)}:u\in B\}$. As seen in the proof of Theorem 1.7 (1), we can take every pair $u,v\in B$ to satisfy $u\cdot v=O(\sqrt{(\log d)/n})$. By Lemma 4.4, we have

We therefore have $\operatorname{SDA}(\mathcal{C},S^{n},n^{-\Omega(k)})=d$. The result now follows by Theorem 4.6. ∎

3 Queries with Gaussian noise

We conclude this section with our lower bounds against $\operatorname{1-STAT}$. These lower bounds rely on the simulation of $\operatorname{1-STAT}$ using $\operatorname{VSTAT}$ proved in [12, Theorem 3.13].

In order to give our lower bounds against $\operatorname{1-STAT}$ oracles, we first give the following lower bounds for queries to $\operatorname{VSTAT}$ in the presence of Gaussian noise, which by Lemma 4.9 are in effect a special case of those proved in Section 4.2 for Lipschitz queries.

Let $\varepsilon>0$. For all $k,\lambda>0$ and all sufficiently large $n$ and $d<\exp(n^{1/2-\varepsilon})$, there exists a family $\mathcal{C}$ of degree-$k$ polynomials on $S^{n}$ with $|\mathcal{C}|=d$ such that if a randomized SQ algorithm learns $\mathcal{C}$ to regression error less than any fixed constant with probability at least $1/2$, it requires at least $\Omega(d)$ queries, if the queries are $L^{\infty}$-normalized queries to $\operatorname{VSTAT}(n^{\Omega(k)}/\lambda)$ in the presence of Gaussian noise of variance $1/\lambda^{2}$. (All the hidden constants depend on $\varepsilon$ only.)

where $D_{\textrm{TV}}$ denotes the total variation distance. This distance is bounded above by $|y_{1}-y_{2}|/(2\sigma)$ (see, e.g., ). ∎

By [12, Theorem 3.13], if there is an algorithm solving the problem using $m$ queries to $\operatorname{1-STAT}$, there is an algorithm solving the problem using $m$ queries to $\operatorname{VSTAT}(O(m))$. By Lemma 4.8, at least $\Omega(d)$ queries to $\operatorname{VSTAT}(n^{\Omega(k)}/\lambda)$ are required. Hence, at least $n^{\Omega(k)}/\lambda$ queries to $\operatorname{1-STAT}$ are also required in the presence of Gaussian noise of variance $1/\lambda^{2}$, as long as the number $d$ of polynomials in $\mathcal{C}$ is at least $n^{\Omega(k)}$. ∎

Discussion

We have given a polynomial-time analysis of gradient descent for training a neural network in an agnostic setting. In particular, we show that functions that are approximated by polynomials can be learned by gradient descent, as well as functions computed by single-hidden-layer neural networks. These results build on a long line of work by many authors studying the power of random initialization combined with output-layer training.

We show that our analysis is essentially tight, in the sense that no statistical query algorithm can have significantly better time complexity.

Extending the training to hidden-layer weights cannot offer an asymptotic improvement in the number of gates needed to achieve small error in the general setting we consider. However, experiments suggest that training hidden-layer weights might allow for tighter bounds in the realizable case. In particular, it would be interesting to give a fully polynomial analysis of gradient descent for learning data labeled by a single-hidden layer neural network with $m$ neurons. An extension for networks with bounded bias parameters, rather than unbiased networks, would also be interesting.

The authors are grateful to Adam Kalai and Le Song for helpful discussions. The authors also thank Joël Bellaïche and the anonymous referees for careful reading and many suggestions that improved the presentation. This work was supported in part by NSF grants CCF-1563838, CCF-1717349 and E2CDA-1640081.

References