Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent

Introduction

A major challenge in the theory of deep learning is to understand when gradient descent can efficiently learn simple families of neural networks. The associated optimization problem is nonconvex and well known to be computationally intractable in the worst case. For example, cyphertexts from public-key cryptosystems can be encoded into a training set labeled by simple neural networks [KS09], implying that the corresponding learning problem is as hard as breaking cryptographic primitives. These hardness results, however, rely on discrete representations and produce relatively unrealistic joint distributions.

In this paper we give the first superpolynomial lower bounds for learning neural networks using gradient descent in arguably the simplest possible setting: we assume the marginal distribution is a spherical Gaussian, the labels are noiseless and are exactly equal to the output of a one-layer neural network (a linear combination of say ReLU or sigmoid activations), and the goal is to output a classifier whose test error (measured by square-loss) is small. We prove—unconditionally—that gradient descent fails to produce a classifier with small square-loss if it is required to run in polynomial time in the dimension. Our lower bound depends only on the algorithm used (gradient descent) and not on the architecture of the underlying classifier. That is, our results imply that current popular heuristics such as running gradient descent on an overparameterized network (for example, working in the NTK regime [JHG18]) will require superpolynomial time to achieve small test error.

Statistical Queries.

Since the convergence analysis of gradient descent holds given sufficiently strong approximations of the gradient, lower bounds for learning in the SQ model [Kea98, BFJ+94, Szö09, Fel12, Fel17] directly imply unconditional lower bounds on the running time for gradient descent to achieve small error. We give the first superpolynomial lower bounds for learning one-layer networks with respect to any Gaussian distribution for any SQ algorithm that uses inner product queries:

Let ${\mathcal{C}}$ be a class of real-valued concepts defined by one-layer single-output neural networks with input dimension $n$ and $m$ hidden units (ReLU or sigmoid); i.e., functions of the form $f(x)=\sum_{i=1}^{m}a_{i}\sigma(w_{i}\cdot x)$. Then learning ${\mathcal{C}}$ under the standard Gaussian $\mathcal{N}(0,I_{n})$ in the SQ model with inner-product queries requires $n^{\Omega(\log m)}$ queries for any tolerance $\tau=n^{-\Omega(\log m)}$.

In particular, this rules out any approach for learning one-layer neural networks in polynomial-time that performs gradient descent on any polynomial-size classifier with respect to square-loss or logistic loss. For classification, we obtain significantly stronger results and rule out general SQ algorithms that run in polynomial-time (e.g., gradient descent with respect to any polynomial-size classifier and any polynomial-time computable loss). In this setting, our labels are $\{\pm 1\}$ and correspond to the softmax of an unknown one-layer neural network. We prove the following:

The above lower bound for classification rules out the commonly used approach of training a polynomial-size, real-valued neural network using gradient descent (with respect to any polynomial-time computable loss) and then taking the sign of the output of the resulting network.

Our techniques.

At the core of all SQ lower bounds is the construction of a family of functions that are pairwise approximately orthogonal with respect to the underlying marginal distribution. Typically, these constructions embed $2^{n}$ parity functions over the discrete hypercube $\{-1,1\}^{n}$. Since parity functions are perfectly orthogonal, the resulting lower bound can be quite strong. Here we wish to give lower bounds for more natural families of distributions, namely Gaussians, and it is unclear how to embed parity.

Enumerating over every $S\subseteq[n]$ of size $k$ gives a family of functions of size $n^{O(k)}$. Here $x_{S}$ denotes the vector of $x_{i}$ for $i\in S$ (typically we choose $k=\log m$ to produce a family of one-layer neural networks with $m$ hidden units). Each of the $2^{k}=m$ inner weight vectors are all of unit norm, and all of the $m$ outer weights have absolute value one. Note also that our construction uses activations with zero bias term.

We give a complete characterization of the class of nonlinear activations for which these functions are orthogonal. In particular, the family is orthogonal for any activation with a nonzero Hermite coefficient of degree $k$ or higher.

Apart from showing orthogonality, we must also prove that functions in these classes are nontrivial (i.e., are not exponentially close to the constant zero function). This reduces to proving certain lower bounds on the norms of one-layer neural networks. The analysis requires tools from Hermite and complex analysis.

SQ Lower Bounds for Real-Valued Functions.

Another major challenge is that our function family is real-valued as opposed to boolean. Given an orthogonal family of (deterministic) boolean functions, it is straightforward to apply known results and obtain general SQ lower bounds for learning with respect to $0/1$ loss. For the case of real-valued functions, the situation is considerably more complicated. For example, the class of orthogonal Hermite polynomials on $n$ variables of degree $d$ has size $n^{O(d)}$, yet there is an SQ algorithm due to [APVZ14] that learns this class with respect to the Gaussian distribution in time $2^{O(d)}$. More recent work due to [ADHV19] shows that Hermite polynomials can be learned by an SQ algorithm in time polynomial in $n$ and $\log d$.

As such, it is impossible to rule out general polynomial-time SQ algorithms for learning real-valued functions based solely on orthogonal function families. Fortunately, it is not difficult to see that the SQ reductions due to [Szö09] hold in the real-valued setting as long as the learning algorithm uses only inner-product queries (and the norms of the functions are sufficiently large). Since performing gradient descent with respect to square-loss or logistic loss can be implemented using inner-product queries, we obtain our first set of desired resultsThe algorithms of [APVZ14] and [ADHV19] do not use inner-product queries..

We give superpolynomial lower bounds for both of these problems in the general SQ model by making a new connection to probabilistic concepts, a learning model due to [KS94]. Our key theorem gives a superpolynomial SQ lower bound for the problem of distinguishing probabilistic concepts induced by our one-layer neural networks from truly random labels. A final complication we overcome is that we must prove orthogonality and norm bounds on one-layer neural networks that have been composed with a nonlinear activation (e.g., tanh).

SGD and Gradient Descent Plus Noise.

It is easy to see that our results also imply lower bounds for algorithms where the learner adds noise to the estimate of the gradient (e.g., Langevin dynamics). On the other hand, for technical reasons, it is known that SGD is not a statistical query algorithm (because it examines training points individually) and does not fall into our framework. That said, recent work by [AS20] shows that SGD is universal in the sense that it can encode all polynomial-time learners. This implies that proving unconditional lower bounds for SGD would give a proof that $\P\neq\NP$. Thus, we cannot hope to prove unconditional lower bounds on SGD (unless we can prove $\P\neq\NP$).

Independent Work.

Independently, Diakonikolas et al. [DKKZ20] have given stronger correlational SQ lower bounds for the same class of functions with respect to the Gaussian distribution. Their bounds are exponential in the number of hidden units while ours is quasipolynomial. We can plug in their result and obtain exponential general SQ lower bounds for the associated probabilistic concept using our framework.

Related Work.

There is a large literature of results proving hardness results (or unconditional lower bounds in some cases) for learning various classes of neural networks [BR89, Vu98, KS09, LSSS14, GKKT17].

Roughly speaking, their lower bounds hold for $\lambda$-Lipschitz queries due to the composition of their one-layer neural networks with a $\delta$-function in order make the family more “boolean.” Because of their restriction on the tolerance parameter, they cannot rule out gradient descent with large batch sizes. Further, the slope of the activations they require in their constructions scales inversely with the Lipschitz and tolerance parameters.

To contrast with [SVWX17], note that our lower bounds hold for any inverse-polynomial tolerance parameter (i.e., will hold for polynomially-large batch sizes), do not require a Lipschitz constraint on the queries, and use only standard $1$-Lipschitz ReLU and/or sigmoid activations (with zero bias) for the construction of the hard family. Our lower bounds are typically quasipolynomial in the number of hidden units; improving this to an exponential lower bound is an interesting open question. Both of our models capture square-loss and logistic loss.

In terms of techniques, [SVWX17] build an orthogonal function family using univariate, periodic “wave” functions. Our construction takes a different approach, adding and subtracting activation functions with respect to overlapping “masks.” Finally, aside from the (black-box) use of a theorem from complex analysis, our construction and analysis are considerably simpler than the proof in [SVWX17].

A follow-up work [VW19] gave SQ lower bounds for learning classes of degree $d$ orthogonal polynomials in $n$ variables with respect to the uniform distribution on the unit sphere (as opposed to Gaussians) using inner product queries of bounded tolerance (roughly $1/n^{d}$). To obtain superpolynomial lower bounds, each function in the family requires superpolynomial description length (their polynomials also take on very small values, $1/n^{d}$, with high probability).

Shamir [Sha18] (see also the related work of [SSSS17]) proves hardness results (and lower bounds) for learning neural networks using gradient descent with respect to square-loss. His results are separated into two categories: (1) hardness for learning “natural” target families (one layer ReLU networks) or (2) lower bounds for “natural” input distributions (Gaussians). We achieve lower bounds for learning problems with both natural target families and natural input distributions. Additionally, our lower bounds hold for any nonlinear activations (as opposed to just ReLUs) and for broader classes of algorithms (SQ).

Recent work due to [GKK19] gives hardness results for learning a ReLU with respect to Gaussian distributions. Their results require the learner to output a single ReLU as its output hypothesis and require the learner to succeed in the agnostic model of learning. [KK14] prove hardness results for learning a threshold function with respect to Gaussian distributions, but they also require the learner to succeed in the agnostic model. Very recent work due to Daniely and Vardi [DV20] gives hardness results for learning randomly chosen two-layer networks. The hard distributions in their case are not Gaussians, and they require a nonlinear clipping output activation.

Positive Results. Many recent works give algorithms for learning one-layer ReLU networks using gradient descent with respect to Gaussians under various assumptions [ZSJ+17, ZPS17, BG17, ZYWG19] or use tensor methods [JSA15, GLM18]. These results depend on the hidden weight vectors being sufficiently orthogonal, or the coefficients in the second layer being positive, or both. Our lower bounds explain why these types of assumptions are necessary.

Preliminaries

We use $[n]$ to denote the set $\{1,\dots,n\}$, and $S\subseteq_{k}T$ to indicate that $S$ is a $k$-element subset of $T$. We denote euclidean inner products between vectors $u$ and $v$ by $u~{}{\cdot}~{}v$. We denote the element-wise product of vectors $u$ and $v$ by $u\circ v$, that is, $u\circ v$ is the vector $(u_{1}v_{1},\dots,u_{n}v_{n})$.

Gradient descent with respect to squared loss is captured by inner product queries, since the gradient is given by

Here the first term can be estimated directly using knowledge of the distribution, while the latter is a vector each of whose elements is an inner product query.

We now formally define the learning problems we consider.

For the classification setting, we consider two different notions of learning $p$-concepts. One is learning the target up to small $L_{2}$ error, to be thought of as a strong form of learning. The other, weaker form, is achieving a nontrivial inner product (i.e. unnormalized correlation) with the target. We prove lower bounds on both in order to capture different learning goals.

If the functions in our class satisfy a norm lower bound, say $\|c\|_{D}^{2}\geq(1+\alpha)\epsilon^{2}$, then a simple calculation shows that learning with $L_{2}$ error $\epsilon$ implies weak learning with advantage $\alpha\epsilon^{2}/2$.

Our definition of weak learning also captures the standard boolean sense of weak learning, in which the learner is required to output a boolean hypothesis with 0/1 loss bounded away from $1/2$. Indeed, by an easy calculation, the 0/1 loss of a function $f:X\to\{\pm 1\}$ satisfies

The difficulty of learning a concept class in the SQ model is captured by a parameter known as the statistical dimension of the class.

Let ${\mathcal{C}}$ be a concept class of either real-valued concepts or $p$-concepts (i.e. their corresponding conditional mean functions) on a domain $X$, and let $D$ be a distribution on $X$. The (un-normalized) correlation of two concepts $c,c^{\prime}\in{\mathcal{C}}$ under $D$ is $|\langle c,c^{\prime}\rangle_{D}|$.In the $p$-concept setting, it is instructive to note that in the notation of [FGR+17], this correlation is precisely the distributional correlation $\chi_{D_{0}}(D_{c},D_{c^{\prime}})$ of the induced labeled distributions $D_{c}$ and $D_{c^{\prime}}$ under the reference distribution $D_{0}=D\times\operatorname{Unif}\{\pm 1\}$. The average correlation of ${\mathcal{C}}$ is defined to be

The statistical dimension on average at threshold $\gamma$, $\operatorname{SDA}_{D}({\mathcal{C}},\gamma)$, is the largest $d$ such that for all ${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ with $|{\mathcal{C}}^{\prime}|\geq|{\mathcal{C}}|/d$, $\rho_{D}({\mathcal{C}}^{\prime})\leq\gamma$.

For any general and large concept class ${\mathcal{C}}^{*}$ (such as all one-layer neural nets), we may consider a specific subclass ${\mathcal{C}}\subseteq{\mathcal{C}}^{*}$ and prove lower bounds on learning ${\mathcal{C}}$ in terms of the SDA of ${\mathcal{C}}$. These lower bounds extend to ${\mathcal{C}}^{*}$ because if it is hard to learn a subset, then it is hard to learn the whole class.

We will mainly be interested in the statistical dimension in a setting where bounds on pairwise correlations are known. In that case the following lemma holds.

Suppose a concept class ${\mathcal{C}}$ has pairwise correlation $\gamma$, i.e. $|\langle c,c^{\prime}\rangle_{D}|\leq\gamma$ for $c\neq c^{\prime}\in{\mathcal{C}}$, and squared norm at most $\beta$, i.e. $\|c\|_{D}^{2}\leq\beta$ for all $c\in{\mathcal{C}}$. Then for any $\gamma^{\prime}>0$, $\operatorname{SDA}_{D}({\mathcal{C}},\gamma+\gamma^{\prime})\geq|{\mathcal{C}}|\frac{\gamma^{\prime}}{\beta-\gamma}$. In particular, if ${\mathcal{C}}$ is a class of orthogonal concepts (i.e. $\gamma=0$) with squared norm bounded by $\beta$, then $\operatorname{SDA}({\mathcal{C}},\gamma^{\prime})\geq|{\mathcal{C}}|\frac{\gamma^{\prime}}{\beta}$.

Let $d=|{\mathcal{C}}|\frac{\gamma^{\prime}}{\beta-\gamma}$, and observe that for any subset ${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ satisfying $|{\mathcal{C}}^{\prime}|\geq|{\mathcal{C}}|/d=\frac{\beta-\gamma}{\gamma^{\prime}}$,

Orthogonal Family of Neural Networks

For our construction, we need our functions to be orthogonal, and we need a lower bound on their norms. For the first property we only need the distribution on the domain to satisfy a relaxed kind of spherical symmetry that we term sign-symmetry, which says that the distribution must look identical on all orthants. To lower bound the norms, we need to assume that the distribution is Gaussian ${\cal N}(0,I)$.

The outer activation $\psi$ is an odd, increasing function, i.e. $\psi(-x)=-\psi(x)$.

Note that $\psi$ could be the identity function.

The inner activation $\phi\in L_{2}({\cal N}(0,I))$.

The construction of our orthogonal family of neural networks is simple and exploits sign-symmetry.

Notice that the size of this family is $\binom{n}{k}=n^{\Theta(k)}$ (for appropriate $k$), which is $n^{\Theta(\log m)}$ in terms of $m$. We will take $k=\Theta(\log n)$, so that $m=\operatorname{poly}(n)$ and thus the neural networks are $\operatorname{poly}(n)$-sized, and the size of the family is $n^{\Theta(\log n)}$, i.e. quasipolynomial in $n$.

We now prove that our functions are orthogonal under any sign-symmetric distribution.

where $\chi_{S}(z)=\prod_{i\in S}z_{i}=\chi(z_{S})$ is the parity on $S$ of $z$. Indeed, observe first that

Consider $f_{S}$ and $f_{T}$ for any two distinct $S,T\subseteq_{k}[n]$. Recall that by the definition of sign-symmetry, for any $z\in\{\pm 1\}^{n}$ and $x$ drawn from $D$, $x$ and $x\circ z$ has the same distribution. Using this and Eq. 1, we have

Our proof actually shows that any family of functions satisfying Eq. 1 is an orthogonal family under any sign-symmetric distribution.

We still need to establish that our functions are nonzero. For this we need to specialize to the Gaussian distribution, as well as consider specific activation functions (a similar analysis can in principle be carried out for other sign-symmetric distributions). For any $n$ and $k$, it follows from Lemma A.1 that if the inner activation $\phi$ has a nonzero Hermite coefficient of degree $k$ or higher, then the functions in ${\mathcal{C}_{\text{orth}}}(n,k)$ are nonzero. The sigmoid, ReLU and sign functions all satisfy this property.

Here we also assume that all $c\in{\mathcal{C}_{\text{orth}}}(n,k)$ are nonzero for our distribution $D$.

Follows from Theorem 3.5 and Lemma 2.6, using a loose upper bound of 1 on the squared norm. ∎

We also need to prove norm lower bounds on our functions for our notions of learning to be meaningful. In Appendix A, we prove the following.

Let the inner activation function $\phi$ be $\operatorname{ReLU}$ or sigmoid, and let the outer activation function $\psi$ be any odd, increasing, continuous function. Let the underlying distribution $D$ be $\mathcal{N}(0,I_{n})$. Then $\|f_{S}\|=\Omega(e^{-\Theta(k)})$, where the hidden constants depend on $\psi$ and $\phi$, for any $f_{S}\in{\mathcal{C}_{\text{orth}}}(n,k)$.

With this in hand, we now state our main SQ lower bounds.

In particular, there exist $k=\Theta(\log n)$ and $\tau=1/n^{\Theta(\log n)}$ such that $A$ requires at least $n^{\Omega(\log n)}$ queries of tolerance $\tau$ to learn ${\mathcal{C}_{\text{orth}}}(n,k)$ with advantage $1/\operatorname{poly}(n)$. In this case $m=\operatorname{poly}(n)$, so that each function in the family has polynomial size. This is our main superpolynomial lower bound.

The proof amounts to careful choices of the parameters $\epsilon,\gamma$ and $\tau$ in Corollary 3.7 and Corollary 4.6. Recall that $\operatorname{SDA}({\mathcal{C}_{\text{orth}}}(n,k),\gamma)\geq n^{\Theta(k)}\gamma$. We pick $\gamma=n^{-\Theta(k)}$ appropriately such that $d=\operatorname{SDA}({\mathcal{C}_{\text{orth}}}(n,k),\gamma)$ is still $n^{\Theta(k)}$. Theorem 3.8 gives us a norm lower bound of $\exp(-\Theta(k))$, allowing us to take $\epsilon=\exp(-\Theta(k))$ and $\tau=\sqrt{\gamma}=n^{-\Theta(k)}$ in Corollary 4.6. ∎

SQ Lower Bounds

Prior work [Szö09, Fel12] has already established the following fundamental result, which we phrase in terms of our definition of statistical dimension. For the reader’s convenience, we include a proof in Appendix B.

Let $D$ be a distribution on $X$, and let ${\mathcal{C}}$ be a real-valued concept class over a domain $X$ such that $\|c\|_{D}>\epsilon$ for all $c\in{\mathcal{C}}$. Consider any SQ learner that is allowed to make only inner product queries to an SQ oracle for the labeled distribution $D_{c}$ for some unknown $c\in{\mathcal{C}}$. Let $d=\operatorname{SDA}_{D}({\mathcal{C}},\gamma)$. Then any such SQ learner needs at least $\Omega(d)$ queries of tolerance $\sqrt{\gamma}$ to learn ${\mathcal{C}}$ up to $L_{2}$ error $\epsilon$.

SQ Lower Bounds for p-concepts

It turns out to be fruitful to view our learning problem in terms of a decision problem over distributions. We define the problem of distinguishing a valid labeled distribution from a randomly labeled one, and show a lower bound for this problem. We then show that learning is at least as hard as distinguishing, thereby extending the lower bound to learning as well. Our analysis closely follows that of [FGR+17].

Let ${\mathcal{C}}$ be a class of $p$-concepts over a domain $X$, and let $D$ be a distribution on $X$. Let $D_{0}=D_{c_{0}}$ be the randomly labeled distribution $D\times\operatorname{Unif}\{\pm 1\}$. Suppose we are given SQ access either to a labeled distribution $D_{c}$ for some $c\in{\mathcal{C}}$ such that $c\neq c_{0}$ or to $D_{0}$. The problem of distinguishing between labeled and uniformly random distributions is to decide which.

Given access to $D_{c}$ for some truly boolean concept $c:X\to\{\pm 1\}$, it is easy to distinguish any other boolean function $c^{\prime}$ from $c$ since $\|c-c^{\prime}\|_{D}^{2}=2-2\langle c,c^{\prime}\rangle_{D}$ (which is information-theoretically optimal as a distinguishing criterion) can be computed using a single inner product query. However, if $c$ and $c^{\prime}$ are $p$-concepts, $\|c\|_{D}$ and $\|c^{\prime}\|_{D}$ are not 1 in general and may be difficult to estimate. It is not obvious how best to distinguish the two, short of directly learning the target.

Considering the distinguishing problem is useful because if we can show that distinguishing itself is hard, then any reasonable notion of learning will be hard as well, including weak learning. We give simple reductions for both our notions of learning.

Let $D$ be a distribution over the domain $X$, and let ${\mathcal{C}}$ be a $p$-concept class over $X$. Suppose there exists either

(a) a weak SQ learner capable of learning ${\mathcal{C}}$ up to advantage $\epsilon$ using $q$ queries of tolerance $\tau$, where $\tau\leq\epsilon/2$; or,

(b) an SQ learner capable of learning ${\mathcal{C}}$ (assume $\|c\|_{D}\geq 3\epsilon$ for all $c\in{\mathcal{C}}$) up to $L_{2}$ error $\epsilon$ using $q$ queries of tolerance $\tau$, where $\tau\leq\epsilon^{2}$. Then there exists a distinguisher that is able to distinguish between an unknown $D_{c}$ and $D_{0}$ using at most $q+1$ queries of tolerance $\tau$.

We now prove the main lower bound on distinguishing.

Let $D$ be a distribution over the domain $X$, and let ${\mathcal{C}}$ be a $p$-concept class over $X$. Then any SQ algorithm needs at least $d=\operatorname{SDA}({\mathcal{C}},\gamma)$ queries of tolerance $\sqrt{\gamma}$ to distinguish between $D_{c}$ and $D_{0}$ for an unknown $c\in{\mathcal{C}}$. (We will consider deterministic SQ algorithms that always succeed, for simplicity.)

(a) on the one hand, $\cup_{k=1}^{q}S_{k}={\mathcal{C}}$, so that $\sum_{k=1}^{q}|S_{k}|\geq|{\mathcal{C}}|$,

(b) while on the other, $|S_{k}|\leq|{\mathcal{C}}|/d$ for every $k$. Together, this will mean that $q\geq d$.

For the first claim, suppose $\cup_{k=1}^{q}S_{k}$ were not all of ${\mathcal{C}}$, and indeed say $c\in{\mathcal{C}}\setminus(\cup_{k=1}^{q}S_{k})$. This is a distribution that our answers were consistent with throughout, yet one that $A$’s solution ($D_{0}$) is incorrect for. But $A$ always succeeds, so for it not to have ruled out this $D_{c}$ is impossible.

For the second claim, suppose for the sake of contradiction that for some $k$, $|S_{k}|>|{\mathcal{C}}|/d$. By Definition 2.4, this means we know that $\rho_{D}(S_{k})\leq\gamma$. One of the key insights in the proof of [Szö09] is that by expressing query expectations entirely in terms of inner products, we gain the ability to apply simple algebraic techniques. To this end, for any query function $h$, let $\widehat{h}(x)=(h(x,1)-h(x,-1))/2$. Observe that for any $p$-concept $c$,

Note that since every query $h$ satisfies $\|h(\cdot,y)\|_{D}\leq 1$ for all $y$, it follows by the triangle inequality that $\|\widehat{h}\|_{D}\leq 1$. So by Cauchy-Schwarz and our observation that $\rho_{D}(S_{k})\leq\gamma$,

However since $|\langle\widehat{h_{k}},c\rangle_{D}|\ >\tau$, we also have that $\Phi=\sum_{c\in S_{k}}|\langle\widehat{h_{k}},c\rangle_{D}|\ >|S_{k}|\tau.$ Since $\tau=\sqrt{\gamma}$, this contradicts our upper bound and in turn completes the proof of our second claim. And as noted earlier, the two claims together imply that $q\geq d$. ∎

The final lower bounds on learning thus obtained are stated as a corollary for convenience. The proof follows directly from Lemma 4.4 and Theorem 4.5.

Let $D$ be a distribution over the domain $X$, and let ${\mathcal{C}}$ be a $p$-concept class over $X$. Let $\gamma,\tau$ be such that $\sqrt{\gamma}\leq\tau$. Let $d=\operatorname{SDA}({\mathcal{C}},\gamma)$.

(a) Let $\epsilon$ be such that $\tau\leq\epsilon^{2}$, and assume $\|c\|_{D}\geq 3\epsilon$ for all $c\in{\mathcal{C}}$. Then any SQ learner learning ${\mathcal{C}}$ up to $L_{2}$ error $\epsilon$ requires at least $d-1$ queries of tolerance $\tau$.

(b) Let $\epsilon$ be such that $\tau\leq\epsilon/2$. Then any weak SQ learner learning ${\mathcal{C}}$ up to advantage $\epsilon$ requires at least $d-1$ queries of tolerance $\tau$.

Experiments

We include experiments for both regression and classification. We train an overparameterized neural network on data from our function class, using gradient descent. We find that we are able to achieve close to zero training error, while test error remains high. This is consistent with our lower bound for these classes of functions.

For regression, we use a training set of size $T$ of data corresponding to $f\in{\mathcal{C}_{\text{orth}}}(n,k)$ instantiated with $\phi=\tanh$ and $\psi$ being the identity. We draw $x\sim\mathcal{N}(0,I_{n})$, and $y=f(x)$. We train a sum of tanh network on this data using gradient descent on squared loss, which we plot in Fig. 1(b). This setup models the natural way of using neural networks for regression problems.

In both cases, we train neural networks whose number of parameters considerably exceeds the amount of training data. In all our experiments, we plot the median over 10 trials and shade the inter-quartile range of the data.

Similar results hold with the inner activation $\phi$ being $\operatorname{ReLU}$ instead of $\tanh$, and are shown in Fig. 2.

References

Appendix A Bounding the function norms under the Gaussian

Our goal in this section will be to give lower bounds on the norms of the functions in ${\mathcal{C}_{\text{orth}}}(n,k)$, which is a technical requirement for our results to hold (see Lemma 4.4 and Corollary 4.6). Note that when learning with respect to $L_{2}$ error, such a lower bound is necessary if we wish to state SQ lower bounds, since if the target had small norm, say $\|f\|_{D}\leq\epsilon$, then the zero function trivially achieves $L_{2}$ error $\epsilon$.

Since $x\sim\mathcal{N}(0,I_{k})$, $\frac{\langle\alpha,x_{S}\rangle}{\sqrt{k}}$ and $\frac{\langle\beta,x_{S}\rangle}{\sqrt{k}}$ are both standard Gaussian and have correlation $\frac{\langle\alpha,\beta\rangle}{k}$, we then apply the following well-known property of the Hermite polynomials.

where $\delta_{i,j}$ is the Dirac delta function.

where $w_{i}=\alpha_{i}\beta_{i}$ and $\theta_{i}=w_{i}\alpha_{i}$. Note that 3.3 implies that $\sum_{i=0}^{\infty}\widehat{\phi_{i}}^{2}<\infty$ , the series above is absolute convergent. Then,

since we consider all distinct monomials in \big{(}\sum_{l=1}^{k}w_{l}\big{)}^{i}. Note that $\sum_{\begin{subarray}{c}i_{1}+\cdots+i_{k}=i\\ i_{1},\dots,i_{k}\text{ are odd}\end{subarray}}\binom{i}{i_{1},\dots,i_{k}}$ is always non-negative and is positive iff $i\geq k$ and $i\equiv k\pmod{2}$. ∎

The goal of this section is to give a lower-bound of $\left\lVert f\right\rVert$ for $\phi=\operatorname{ReLU}$ under the standard Gaussian distribution $\mathcal{N}(0,I)$. To this end, we prove an anti-concentration for $g$. We first give a lower bound on $\left\lVert g\right\rVert$ based on the Hermite coefficients of $\phi$. If $g$ were bounded, this alone would imply anti-concentration as in Section A.2. But since it is not, we first introduce $g^{T}$, where all activations are truncated at some $T$. We pick $T$ large enough that $g$ and $g^{T}$ behave almost identically over ${\cal N}(0,I)$. We then show a lower bound on $\left\lVert g^{T}\right\rVert$, translate that into an anticoncentration result for $g^{T}$, and finally into one for $g$.

Let $T>0$ be some constant to be determined later. Let

The following lemma from [GKK19] describes the Hermite coefficients of ReLU.

In particular, $c_{2i}^{2}=\Theta(i^{-2.5})$.

We can now derive a lower bound on the norm of $g$.

The lemma then follows by the Stirling’s approximation,

and the bound on the Hermite coefficients,

For the difference of $g(x)$ and $g^{T}(x)$, we have

Let $\operatorname{ReLU}_{w}(x)$ be shorthand for $\operatorname{ReLU}(\frac{x~{}{\cdot}~{}w}{\sqrt{k}})$, and similarly $\operatorname{ReLU}_{w}^{T}$. Observe that by the triangle inequality,

where the last equality holds because for any unit vector $v$ and $x\sim\mathcal{N}(0,I)$, $x~{}{\cdot}~{}v$ has the distribution $\mathcal{N}(0,1)$. Now,

where $p(x)$ is the probability density function of $\mathcal{N}(0,1)$. Note that $p^{\prime}(x)=-xp(x)$. We have

For large enough $T=\Omega(k)$, it holds from Lemmas A.3 and A.4 that

Since $\left|{g^{T}(x)}\right|\leq T\,2^{k}$,

The lower bound on $\left\lVert f\right\rVert$ now follows easily.

Since $f=\psi\circ g$, from Lemma A.6 and the fact that $\psi$ is odd and increasing, we have that

A.2 Sigmoid Activation

Here we consider $g$ and $f$ with $\phi(x)=\sigma(x)=\frac{1}{1+e^{-x}}$. For the asymptotic bound of Hermite polynomial coefficients, we need the following theorem from [Boy84].

For a function $f(z)$ whose convergence is limited by simple poles at the roots of $z^{2}=-\gamma^{2}$ with residue $R$, the non-zero expansion coefficients $\{a_{n}\}$ of $f(z)$ as a series of normalized Hermite functions have magnitudes asymptotically given by

Applying this to $f(x)=e^{-\frac{x^{2}}{2}}\sigma(\sqrt{2}x)$ and translating the Hermite coefficients for the series in terms of Hermite functions to those in terms of Hermite polynomials, we have

where $c_{0}=0.5,c_{2i}=0$ for $i\geq 1$ and all non-zero odd terms satisfies

Similar to Lemma A.3, we can derive a lower bound of $\left\lVert g\right\rVert$ for some $k$’s.

Using the same argument as Corollary A.7, we have the following bound.

A.3 General activations

It is not hard to see that the norm analysis of ReLU and sigmoid extends to any activation function for which a suitable lower bound on the Hermite coefficients holds, and which is either bounded or grows at a polynomial rate, so that under the standard Gaussian it behaves essentially identically to its truncated form. In particular, a lower bound of $\alpha^{-j}$ for any constant $\alpha<4/e$ on the $j^{\text{th}}$ Hermite coefficient suffices to give $\|g\|\geq\exp(\Theta(k))$, by the same argument as in Lemma A.3 and Lemma A.12. This then suffices to give $\|f\|\geq\exp(-\Theta(k))$, as above.

In fact, even a very weak lower bound on $\|f\|$ yields some superpolynomial bound on learning. Suppose we only had $\|f\|\geq 1/\exp(\exp(\Theta(k)))$, for instance. Then we can take $k=\log\log n$ and have $\|f\|\geq 1/\operatorname{poly}(n)$ and still obtain a lower bound of $n^{\log\log n}=n^{\omega(1)}$ (see Theorem 3.9). Any lower bound on $\|f\|$ will be a function only of $k$, so a similar argument applies.

Appendix B SQ lower bound for real-valued functions proof

We give a self-contained variant of the elegant proof of [Szö09] for the reader’s convenience. For simplicity, we include the function in our class ${\mathcal{C}}$ — this can only negligibly change the SDA, and it makes the core argument cleaner.

Let $D$ be a distribution on $X$, and let ${\mathcal{C}}$ be a real-valued concept class over a domain $X$ such that $0\in{\mathcal{C}}$, and $\|c\|_{D}>\epsilon$ for all $c\in{\mathcal{C}},c\neq 0$. Consider any SQ learner that is allowed to make only inner product queries to an SQ oracle for the labeled distribution $D_{c}$ for some unknown $c\in{\mathcal{C}}$. Let $d=\operatorname{SDA}_{D}({\mathcal{C}},\gamma)$. Then any such SQ learner needs at least $d/2$ queries of tolerance $\sqrt{\gamma}$ to learn ${\mathcal{C}}$ up to $L_{2}$ error $\epsilon$.

Let $\tau=\sqrt{\gamma}$. If $h_{k}$ is the $k^{\text{th}}$ query, let $S_{k}=\{c\in{\mathcal{C}}\mid\langle c,h_{k}\rangle_{D}>\tau\}$ be the functions ruled out by our response of 0. (A similar argument will hold for $S_{k}^{\prime}=\{c\in{\mathcal{C}}\mid\langle c,h_{k}\rangle_{D}<-\tau\}$.) Let $\Phi=\langle h_{k},\sum_{c\in S_{k}}c\rangle_{D}$. We claim that $\left|{S_{k}}\right|\leq\left|{{\mathcal{C}}}\right|/d$. Suppose not. Then $\rho_{D}(S_{k})\leq\gamma$ by Definition 2.4, and

contradicting the fact that $\Phi>|S_{k}|\tau$ by definition of $S_{k}$.

Similarly $|S_{k}^{\prime}|=|\{c\in{\mathcal{C}}\mid\langle c,h_{k}\rangle_{D}<-\tau\}|\leq|{\mathcal{C}}|/d$. Thus we rule out at most a $2/d$ fraction of functions with each query, and hence need at least $d/2$ queries to rule out all other possibilities. ∎