Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

Introduction

In recent years, the impressive practical success of deep learning has motivated the development of provably efficient learning algorithms for various classes of neural networks. A large body of research (see Section 1.4 for a brief overview) has resulted in efficient learning algorithms for shallow networks with common activation functions (e.g., ReLUs or sigmoids) under various assumptions on the underlying distribution and the weight structure of the network. Despite intensive investigation, the broad question of whether deep neural networks are efficiently learnable with provable guarantees remains an outstanding theoretical challenge in machine learning. In particular, the class of networks for which efficient learners are known is relatively limited, even in the realizable case (i.e., when the data is drawn from a neural network in the class).

In this work, we continue this line of investigation by studying the learnability of a simple class of networks without imposing strong restrictions on the structure of its weights. Specifically, we focus on the problem of learning one-hidden-layer ReLU networks under the Gaussian distribution in the presence of additive random label noise. Our goal is to understand the complexity of this problem in the PAC learning model without assumptions on the weight matrix of the network.

Perhaps surprisingly, the complexity of PAC learning one-hidden-layer ReLU networks (even with positive weights) has remained open, even in the realizable setting, under Gaussian marginals, and for $k=3$ [Kli17]Formally speaking, the $k=2$ case does not appear explicitly in the literature, but an efficient algorithm easily follows from prior work on parameter estimation (e.g., [GLM18]).. A line of prior work [GLM18, BJW19, GKLW19] had studied the task of parameter estimation for this concept class, i.e., the task of recovering the unknown coefficients $\alpha_{i}$ and weight vectors $\mathbf{w}^{(i)}$ of the data generating network within small accuracy. It should be noted that for parameter estimation to even be information-theoretically possible, some assumptions on the target function are necessary. The aforementioned prior works made the common assumption that the weight matrix $\mathbf{W}=[\mathbf{w}^{(i)}]_{i=1}^{k}$ is full-rank. Under this assumption, they provided efficient parameter learning algorithms with respect Gaussian marginals for the case of positive coefficients, i.e., for $\mathcal{C}_{k}^{+}$. Importantly, the sample and computational complexity of these algorithms scale polynomially with the condition number of $\mathbf{W}$. In contrast, no such algorithm is known for general coefficients, i.e., for $\mathcal{C}_{k}$, even under the aforementioned strong assumptions on the weights.

In contrast to parameter estimation, PAC learning one-hidden-layer ReLU networks does not require any assumptions on the structure of the weight matrix. The PAC learning problem for this class is information-theoretically solvable with polynomially many samples. The question is whether a computationally efficient algorithm exists. It should also be noted that proper PAC learning is not generally equivalent to parameter estimation, as it is in principle possible to have two networks that define close-by functions and whose parameters are significantly different.

2 Our Results

Before we state our main theorems, we formally define the PAC learning problem.

Our main positive result is the first computationally efficient PAC learning algorithm for $\mathcal{C}_{k}^{+}$.

We remark that our main algorithmic result is more general, in the sense that it immediately extends to positive coefficient one-hidden-layer networks composed of any non-negative Lipschitz activation function. See Theorem 3.1 for a detailed statement.

The natural interpretation of Theorem 1.4 is the following: If the SQ algorithm uses statistical queries of accuracy $d^{-\Omega(k)}$, then simulating a single query with iid samples would require $d^{\Omega(k)}$ samples (hence time). Otherwise, the algorithm would require $2^{d^{\Omega(1)}}$ time (since each query requires at least one unit of time). Theorem 1.4, combined with our Theorem 1.3, provides a (super-polynomial) computational separation between the PAC learnability of $\mathcal{C}_{k}$ and $\mathcal{C}_{k}^{+}$ in the correlational SQ model.

We note that the statement of our general SQ lower bound (Theorem 4.3) is much more general than Theorem 1.4. Specifically, we obtain a correlational SQ lower bound for PAC learning (under Gaussian marginals) a class of functions of the form $\sigma(\sum_{i=1}^{k}\alpha_{i}\phi(\mathbf{w}^{(i)},\mathbf{x}))$, where roughly speaking $\sigma$ is any odd non-vanishing function and $\phi$ is not a low-degree polynomial.

3 Our Techniques

Here we provide an overview of our techniques in tandem with a comparison to prior work. We start with our algorithm establishing Theorem 1.3. Our learning algorithm for $\mathcal{C}_{k}^{+}$ employs a data-dependent dimension reduction procedure. Specifically, we give an efficient method to reduce our $d$-dimensional learning problem down to a $k$-dimensional problem, that can in turn be efficiently solved by a simple covering method.

We note that the idea of using dimension-reduction to find a low-dimensional invariant subspace has been previously used in the context of PAC learning intersections of LTFs [Vem10, DKS18]. Our algorithm and its analysis of correctness are quite different from these prior works. We also note that [GLM18] also used information based on low-degree moments for their parameter estimation algorithm, but in a qualitatively different way. In particular, [GLM18] used tensor-decomposition techniques (based on moments of degree up to four) to uniquely identify the weight vectors, under structural assumptions on the weight matrix (full-rank and bounded condition number).

We now proceed to explain our SQ lower bound construction. As is well-known, there is a general methodology to establish such lower bounds, via an appropriate notion of SQ dimension [BFJ+94, FGR+17]. In our setting, to prove an SQ lower bound, it suffices to find a large collection of functions $f_{1},\ldots,f_{m}\in\mathcal{C}_{k}$ with the following properties: (1) The $f_{i}$’s are pairwise far away from each other, and (2) The $f_{i}$’s have small pairwise correlations. The difficulty is, of course, to construct such a family. We describe our construction in the following paragraph.

First, it is not hard to see that (1) and (2) can only be simultaneously satisfied if almost all of the $f_{i}$’s have nearly-matching low-degree moments. In fact, we provide a construction in which all the low-degree moments of all of the $f_{i}$’s vanish. To achieve this, we build on an idea introduced in [DKS17]. Roughly speaking, the idea is to define a family of functions whose interesting information is hidden in a random low-dimensional subspace, so that learning an unknown function in the family amounts to finding the hidden subspace. In more detail, we will define a function in two dimensions which has the correct moments, and then embed it in a randomly chosen subspace.

4 Related Work

In recent years, there has been an explosion of research on provable algorithms for learning neural networks in various settings, see, e.g., [JSA15, SJA16, DFS16, ZLJ16, ZSJ+17, GLM18, GKLW19, BJW19, GKKT17, MR18, GK19, VW19] for some works on the topic. The majority of these works focused on parameter learning, i.e., the problem of recovering the weight matrix of the data generating neural network. In contrast, the focus of this paper is on PAC learning. We also note that PAC learning of simple classes of neural networks has been studied in a number of recent works [GKKT17, MR18, GK19, VW19]. However, the problem of PAC learning linear combinations of (even) $3$ ReLUs under any natural distributional assumptions (and in particular under the Gaussian distribution) has remained open. At a high-level, prior works either rely on tensor decompositions [SJA16, ZSJ+17, GLM18, GKLW19, BJW19] or on kernel methods [ZLJ16, DFS16, GKKT17, GK19]. In the following paragraphs, we describe in detail the prior works more closely related to the results of this paper.

The work of [GLM18] studies the parameter learning of positive linear combinations of ReLUs under the Gaussian distribution in the presence of additive (mean zero sub-gaussian) noise. That is, they consider the same concept class and noise model as we do, but study parameter learning as opposed to PAC learning. [GLM18] show that the parameters can be approximately recovered efficiently, under the assumption that the weight matrix is full-rank with bounded condition number. The sample complexity and running time of their algorithm scales polynomially with the condition number. More recently, [BJW19, GKLW19] obtained efficient parameter learning algorithms for vector-valued depth-$2$ ReLU networks under the Gaussian distribution. Similarly, the algorithms in these works have sample complexity and running time scaling polynomially with the condition number. We note that the algorithmic results in the aforementioned works do not apply to $\mathcal{C}_{k}$, i.e., the class of arbitrary linear combinations of ReLUs.

[VW19] show that gradient descent agnostically PAC learns low-degree polynomials using neural networks as the hypothesis class. Their approach has implications for (realizable) PAC learning of certain neural networks under the uniform distribution on the sphere. We note that their method implies an algorithm with sample complexity and running time exponential in $1/\epsilon$, even for a single ReLU. [GK19] give an efficient PAC learning algorithm for certain $2$-hidden-layer neural networks under arbitrary distributions on the unit ball. We emphasize that their algorithm does not apply for (positive) linear combinations of ReLUs. In fact, recent work has shown that the problem we solve in this paper is NP-hard under arbitrary distributions, even for $k=2$ [GKMR20].

The SQ model was introduced by [Kea98] in the context of learning Boolean-valued functions as a natural restriction of the PAC model [Val84]. A recent line of work [FGR+13, FPV15, FGV15, Fel16] extended this framework to general search problems over distributions. One can prove unconditional lower bounds on the computational complexity of SQ algorithms via an appropriate notion of Statistical Query dimension. A lower bound on the SQ dimension of a learning problem provides an unconditional lower bound on the computational complexity of any SQ algorithm for the problem.

The work of [VW19] establishes correlational SQ lower bounds for learning a class of degree-$k$ polynomials in $d$ variables. [Sha18] shows that gradient-based algorithms (a special case of correlational SQ algorithms) cannot efficient learn certain families of neural networks under well-behaved distributions (including the Gaussian distribution). We note that the lower bound constructions in these works do not imply corresponding lower bounds for one-hidden-layer ReLU networks.

Contemporaneous work [GGJ+20], using a different construction, obtained super-polynomial SQ lower bounds for learning one-hidden-layer neural networks (with ReLU and other activations) under the Gaussian distribution.

Preliminaries

Efficient Learning Algorithm

In this section, we give our upper bound for the problem of learning positive linear combinations of Lipschitz activations, thereby establishing Theorem 1.3. We prove the following more general statement:

Theorem 1.3 follows as a corollary of the above, by noting that the ReLU satisfies $L=1$ and $C=\frac{1}{\sqrt{2\pi}}$.

The following fact gives formulas for the low-degree Chow parameters of a one-layer network (see Appendix A, Fact A.1).

The crucial formula is the one of the degree-$2$ Chow parameters, Equation (1). In fact, we can already describe the main idea of our upper bound. Let us assume that we have the degree-$2$ Chow parameters matrix $\bm{A}$ exactly. Then, by using singular value decomposition, we would obtain a basis of the vector space spanned by the parameters $\mathbf{w}^{(i)}$. The dimension of this space is at most $k$ and therefore in that way we essentially reduce the dimension of the problem from $d$ down to $k$. To find parameters $\hat{\alpha}_{i},\hat{\mathbf{w}}^{(i)}$ that give small mean squared error, we can now make a grid $\mathcal{G}$ and pick the ones that minimize the empirical mean squared error with the samples, that is

Even though we do not have access to the matrix $\bm{A}$ exactly, we can estimate it empirically. Since the activation function $\phi(\cdot)$ is well-behaved and the distribution of the examples is Gaussian, we can get a very accurate estimate of $\bm{A}$ with roughly $\widetilde{O}(dk/\epsilon^{2})$ samples. We give the following lemma whose proof relies on matrix concentration and concentration of polynomials of Gaussian random variables (see Appendix B, Lemma B.1).

Let $f_{\mathbf{\alpha},\bm{W}}(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi(\langle\mathbf{w}^{(i)},\mathbf{x}\rangle)$, where $\phi(t)$ is an $L$-Lipschitz, non-negative activation function such that $\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)]\geq C$. Let $\bm{\Sigma}=\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f_{\alpha,\bm{W}}(\mathbf{x})\mathbf{x}\otimes\mathbf{x}]$ be the degree-$2$ Chow parameters of $f_{\alpha,\bm{W}}$. Then, for some $N=\widetilde{O}(dk/\epsilon^{2})$ samples $(\mathbf{x}^{(i)},y^{(i)})$, where $y^{(i)}=f_{\mathbf{\alpha},\bm{W}}(\mathbf{x}^{(i)})+\xi_{i}$ and $\xi_{i}$ is a zero-mean, subgaussian noise with variance $\sigma^{2}$, it holds with probability at least $99\%$ that

The next step is to quantify how accurately we need to estimate the degree-$2$ Chow parameters, so that doing SVD on the empirical matrix gives us a good approximation of the subspace spanned by the true parameters $\mathbf{w}^{(i)}$. We show that that estimating the degree-$2$ Chow parameter matrix within spectral norm roughly $\epsilon/k$ suffices. In particular, we show that the top-$k$ eigenvectors of our empirical estimate span approximately the subspace where the true parameters $\mathbf{w}^{(i)}$ lie. For the proof, we are going to use the following lemma that bounds the difference of a function evaluated at correlated normal random variables.

We call $\rho$-correlated a pair of random variables $(\mathbf{x},\mathbf{y})\sim D_{\rho}$. It holds

We are now ready to prove the key technical lemma of our approach. We remark that the following dimension reduction lemma is rather general and holds for any reasonable activation function, in the sense that the error is bounded as long as its expected derivative $\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[(\phi^{\prime}(t))^{2}]$ is bounded.

where for the last inequality we used Lemma 3.5 and the fact that the random variables $\langle\mathbf{w}^{(i)},\mathbf{x}\rangle$ and $\langle\mathbf{v}^{(i)},\mathbf{x}\rangle$ are $\rho_{i}$-correlated with $\rho_{i}=\langle\mathbf{w}^{(i)},\mathbf{v}^{(i)}\rangle$.

It suffices to prove that $\left\|\mathbf{r}^{(i)}\right\|_{2}=\left\|\mathbf{w}^{(i)}-\mathbf{v}^{(i)}\right\|_{2}\leq\epsilon^{\prime}$ for some sufficiently small $\epsilon^{\prime}$. Note that because $\mathbf{r}^{(i)}\in\cal V^{\perp}$, it holds ${\mathbf{r}^{(i)}}^{T}\bm{M}^{\prime}\mathbf{r}^{(i)}\leq\left\|\mathbf{r}^{(i)}\right\|_{2}^{2}\max_{\mathbf{u}\in{\cal V}^{\perp}}\frac{\mathbf{u}^{T}\bm{M}^{\prime}\mathbf{u}}{\left\|\mathbf{u}\right\|_{2}}$, because we know that the subspace $\cal W$ is spanned by the top $k$ eigenvectors of $\bm{M}^{\prime}$. Let $\mathbf{u}=\sum_{i=1}^{d}\mathbf{u}^{(i)}$, where $\mathbf{u}^{(i)}\in\ker(\bm{M}-\lambda_{i}\bm{I})$ for all $i\in\{k+1,\ldots,d\}$ and $\lambda_{i}$ is the $i$-th greatest eigenvalue. From Weyl’s inequality, we have that if $A_{i}$ are the eigenvalues of $\bm{A}^{\prime}$ in decreasing order then $\left\|A_{i}-\lambda_{i}\right\|_{1}\leq\epsilon$ and we know that the eigenvalues of $\bm{A}^{\prime}$ for $i>k$ are zero, because the $\operatorname{rank}(\bm{A})\leq k$. Thus,

because the eigenvalues of the eigenvectors of $\bm{M}^{\prime}$ in ${\cal V}^{\perp}$ are less than $\epsilon$, which implies that ${\mathbf{r}^{(i)}}^{T}\bm{M}^{\prime}\mathbf{r}^{(i)}$ $\leq\epsilon\left\|\mathbf{r}^{(i)}\right\|_{2}^{2}\;.$ We also have ${\mathbf{r}^{(i)}}^{T}\bm{A}^{\prime}\mathbf{r}^{(i)}\geq\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)(t^{2}-1)]\alpha_{i}{\mathbf{r}^{(i)}}^{T}\mathbf{w}^{(i)}{\mathbf{w}^{(i)}}^{T}\mathbf{r}^{(i)}=C_{1}\alpha_{i}\cdot\left(1-\left\|{\mathbf{v}^{(i)}}\right\|_{2}^{2}\right)^{2}=C_{1}\alpha_{i}\left\|\mathbf{r}^{(i)}\right\|_{2}^{4}\;,$ where the last equality follows from the Pythagorean theorem. Therefore,

Thus, we obtain $\alpha_{i}\left\|\mathbf{r}^{(i)}\right\|_{2}^{2}\leq 2\epsilon/C_{1}\;.$ The bound now follows directly from (3) since $2\alpha_{i}(1-\langle\mathbf{w}^{(i)},\mathbf{v}^{(i)}\rangle)=\alpha_{i}\left\|\mathbf{w}^{(i)}-\mathbf{v}^{(i)}\right\|_{2}^{2}=\alpha_{i}\left\|\mathbf{r}^{(i)}\right\|_{2}^{2}\leq 2\epsilon/C_{1}$. ∎

Now we have all the ingredients to complete our proof. Since the dimension of the subspace that we have learned is at most $k$, we can construct a grid with $(k/\epsilon)^{O(k)}$ candidates that contains an approximate solution. Our full algorithm is summarized as Algorithm 1. The proof of Theorem 3.1 follows from the above discussion and can be found in Appendix A (Theorem A.7.

Statistical Query Lower Bound

We start by formally defining the class of algorithms for which our lower bound applies. In the standard statistical query model, we do not have direct access to samples from the distribution, but instead can pick a function $q$ and get an approximation to its expected value. In this work, we consider algorithms that have access to correlational statistical queries, which are more restrictive and are defined as follows. We remark that in the following definition of inner product queries we do not assume that the concept $f(\mathbf{x})$ is bounded pointwise but only in the $L_{2}$ sense. The properties that we shall need for our result hold also under this weaker assumption.

We are now ready to define the conditions on the activations $\sigma,\phi$ that are needed for our construction. We define

To prove our lower bound we will use an appropriate notion of SQ dimension. Specifically, we define the Correlational SQ Dimension that captures the difficulty of learning a class $\cal C$.

The following lemma relates the Correlational Statistical Query Dimension of a concept class with the number of correlational statistical queries needed to learn it. The difficulty lies in creating a large family of functions with small average correlation. We will use the following result that translates correlational statistical dimension to a lower bound on the number of inner product queries needed to learn the function $f\in\mathcal{C}$. We note that in this paper we consider inner-product queries of the form $g(x)y$ where $y$ is not necessarily bounded. In fact, the proof of the following lemma does not require $g(x)y$ to be pointwise bounded (bounded $L_{2}$ norm is sufficient) as it can be seen from the arguments in [Szö09], [GGJ+20], [VW19].

We will require the following technical lemma, whose proof relies on Hermite polynomials, and can be found in Appendix C.2 (Lemma C.2).

In the following simple lemma, we show that two random $2$-dimensional subspaces in high dimensions are nearly orthogonal. In particular, we can have an exponentially large family of almost orthogonal planes. For the proof see Appendix C.2 (Lemma C.3).

The following lemma shows that the correlation of any function $f$ of $\mathcal{H}$ with any low-degree polynomial is zero. For the proof see Appendix C.2 (Lemma C.5).

Let $f_{\sigma,\phi}\in\mathcal{H}$. For every polynomial $p(\mathbf{x})$ of degree at most $k$, it holds $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[f_{\sigma,\phi}(\mathbf{x})\cdot p(\mathbf{x})]=0$.

We are now ready to prove our main result.

where in the second equality we used that Gaussian distributions are invariant under rotations and in the last that the expectation of $p(\mathbf{x})$ is zero. Then, using Lemma 4.6, it holds

where in the first inequality we used that the first $k$ moments are zero, in the second the fact that the spectral norm of these two matrices is less than one, and in the third inequality we used Parseval’s theorem. Thus, using Equation (7) into Equation (6), we get that the pairwise correlation is less than $\tau=O(d^{k(c-1/2)})$. Thus, from a straighforward calculation, the average correlation of the set $\mathcal{F}_{\sigma,\phi}^{\mathcal{W}}$ is less $\tau+\frac{1-\tau}{|\mathcal{F}_{\sigma,\phi}^{\mathcal{W}},|}\leq\tau+{|\mathcal{F}_{\sigma,\phi}^{\mathcal{W}}}|^{-1}\leq\tau+2^{-\Omega(d^{c})}$. Moreover, for $\tau^{\prime}=d^{O(k(c-1/2))}+2^{-\Omega(d^{c})}$, the $\textsc{SDA}(\mathcal{F}_{\sigma,\phi}^{\mathcal{W}},\mathcal{D},\tau^{\prime})=2^{\Omega(d^{c})}$ and the result follows from Lemma 4.5. ∎

Conclusions and Future Directions

This work is part of an extensive recent literature on designing provable algorithms for learning simple families of neural networks. In the context of one-hidden-layer networks, a number of concrete open questions remain: Can we improve the dependence on $k$ in the running time to polynomial? Can we design learning algorithms that succeed under less stringent distributional assumptions? We believe that progress in both these directions is attainable.

We thank the authors of [GGJ+20] for useful comments that helped us improve the presentation of our lower bound proof.

References

Appendix

Appendix A Omitted Proofs from Section 3

In the following simple fact, we compute the degree-$1$ and degree-$2$ Chow parameters of a one-layer network.

Let f(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi\big{(}\left\langle\mathbf{w}^{(i)},\mathbf{x}\right\rangle\big{)}. Then

where $B_{1}=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)]$ ,$C=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)t]$ and $B=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)(t^{2}-1)]$.

where in the third equality we used the fact that normal distribution is invariant under rotations. For the second equality, we have

where $\bm{R}_{i}$ is some rotation matrix that maps $\mathbf{w}^{(i)}$ to $\mathbf{e}_{1}$, and $J$ is the Jacobian of this rotation which has always determinant of 1. The Chow parameters of degree-$2$ are given by

There are four cases. The first case is when $k\neq l\neq 1$. By independence, we have that $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\phi(\mathbf{x}_{1})(\mathbf{x}_{k}\mathbf{x}_{l}-\delta_{k,l})]=\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\phi(\mathbf{x}_{1})]\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[(\mathbf{x}_{k}\mathbf{x}_{l})]=0$, where we used the independence of the random variables $\mathbf{x}_{k},\mathbf{x}_{l}$. Similarly, if $k\neq l$ and $k=1$ we have that $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\phi(\mathbf{x}_{1})(\mathbf{x}_{1}\mathbf{x}_{l})]=0$. If $k=l\neq 1$, then $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\phi(\mathbf{x}_{1})(\mathbf{x}_{l}^{2}-1)=0$, because $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\mathbf{x}_{l}^{2}]=1$. Thus, the only non-zero case is when $k=l=1$. Then, we obtain

Let $f_{\mathbf{\alpha},\bm{W}}(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi(\left\langle\mathbf{w}^{(i)},\mathbf{x}\right\rangle)$ and $f_{\mathbf{\beta},\bm{V}}(\mathbf{x})=\sum_{i=1}^{k}\beta_{i}\phi(\left\langle\mathbf{v}^{(i)},\mathbf{x}\right\rangle)$ with $\alpha_{i},\beta_{i}$ $>0$, then it holds $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[(f_{\mathbf{\alpha},\bm{W}}(\mathbf{x})-f_{\mathbf{\beta},\bm{V}}(\mathbf{x}))^{2}]\leq 2k\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[(\phi^{\prime}(t))^{2}]\sum_{i=1}^{k}\alpha_{i}^{2}\left\|\mathbf{v}^{(i)}-\mathbf{w}^{(i)}\right\|_{2}+k\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)^{2}]\sum_{i=1}^{k}(\alpha_{i}-\beta_{i})^{2}\;.$

Let $f(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi(\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle)$ and $y=f(\mathbf{x})+\xi$ where $\xi$ is zero mean subgaussian with variance $\sigma^{2}$. Let $B_{2}=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi^{2}(t)]$ and $c>0$ a constant, then using $O(kB_{2})$ samples we can find $\hat{\mu}$ such as

Let $\hat{\mu}=\frac{1}{m}\sum_{i=1}^{m}y^{(i)}$, then from Chebyshev’s inequality, we have

to get last inequality we used Cauchy–Schwarz. Taking $m=O(kB_{2})$ we get $\frac{1}{2}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f(\mathbf{x})]\leq\hat{\mu}+c\sqrt{\frac{\sigma^{2}}{k}}$ and $\hat{\mu}\leq\frac{3}{2}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f(\mathbf{x})]+c\sqrt{\frac{\sigma^{2}}{k}}$. ∎

Let $f(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi(\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle)$, $B_{2}=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi^{2}(t)]$ and $B_{4}=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi^{4}(t)]$. Then $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f^{4}(\mathbf{x})]\leq\frac{B_{4}}{B_{2}^{2}}k^{2}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f(\mathbf{x})^{2}]^{2}$.

To bound $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f^{4}(x)]$, using Cauchy-Schwartz, it holds that

where in the last inequality we used that $\sum_{i=1}^{k}\alpha_{i}^{2}B_{2}\leq\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f^{2}(\mathbf{x})]$. ∎

Let $f(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi(\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle)$ and $y=f(\mathbf{x})+\xi$ where $\xi$ is zero mean subgaussian with variance $\sigma^{2}$. Moreover, let $B_{2}=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi^{2}(t)]$ and $B_{4}=\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi^{4}(t)]$. Then, if $Y_{u}=\frac{1}{m}\sum_{i=1}^{m}(f_{u}(\mathbf{x}^{(i)})-y^{(i)}))^{2}$,we can find $\hat{Y}_{u}$ such that

with probability $1-\delta$ with $O(\frac{1}{\epsilon^{4}}\log(1/\delta))$ samples, where $c$ is a universal constant.

Let $Y=(f_{u}(\mathbf{x})-y)^{2}=(f_{u}(\mathbf{x})-f(\mathbf{x}))^{2}+y^{2}-2y(f_{u}(\mathbf{x})-f(\mathbf{x}))$. Then the variance of each term is

where in the third and in the fourth inequality we used that $(a\pm b)^{2}\leq 2a^{2}+2b^{2}$ and in the last one we used Lemma A.4. Thus,

where $c$ is a universal constant. From Chebyshev’s inequality, we have that we need $m=O(\frac{1}{\epsilon^{4}})$ for an error at most $\sqrt{c}\epsilon^{2}k^{2}(\frac{B_{4}^{1/2}}{B_{2}}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f^{2}(\mathbf{x})]+\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f_{u}^{2}(\mathbf{x})]+\sigma^{2}\right)$. Then using the median trick, we can boost the confidence to $1-\delta$ with $m\log(1/\delta)$ samples. ∎

Since the dimension of the subspace, that we have learned, is at most $k$, the following standard lemma gives us that a grid with $(k/\epsilon)^{O(k)}$ candidates suffices.

We are now ready to prove our main theorem, Theorem 3.1, which we restate for convenience.

Using Lemma A.6, the size of a cover is $|\mathcal{G}|\leq\left((1+4k/\epsilon)^{k}\log(k\epsilon)/\epsilon\right)^{k}$, because we need vectors with norm from $\epsilon M_{f}$ to $M_{f}$, our cover is created using the upper bound on $M_{f}$. We have that there exists $\bm{U}$ whose rows are vectors in the cover $\mathcal{G}$ such that

where in the first inequality we used Lemma A.2 and in the second one Fact A.3. The error of the best hypothesis(i.e., the one that minimizes the error) in the cover, will be

Finally, using the estimator from Line 7, Lemma A.5, we conclude that $m^{\prime\prime}=O(\frac{k^{4}}{\epsilon^{4}}\log(|\mathcal{G}|))$ samples are sufficient to test all the vectors of the cover $\mathcal{G}$ and find the one that minimizes the error with high probability. For each element $i\in\mathcal{G}$, let $e_{i}=\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[(f(\mathbf{x})-f_{i}(\mathbf{x}))^{2}]+\sigma^{2}$, which is the square error of the $i$-th hypothesis in $\mathcal{G}$ and let $\hat{e}_{i}$ be the estimated value. We have with high probability that

where we used $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f_{\bm{U}}(\mathbf{x})]\leq k\hat{\mu}\leq kM_{f}+2c^{\prime}\sigma\sqrt{k}$. Set $h(\mathbf{x})=\operatorname*{argmin}_{i\in\mathcal{G}}|\hat{e}_{i}-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\hat{e}_{i}]|$, using Equations (9) and (10), then

where the last inequality follows from Jensen’s inequality. ∎

Let $\mathcal{G}$ be a set of unit vectors of size $m$. We can construct a new set $\mathcal{G}^{\prime}$ of size $m\log(1/\epsilon)/\epsilon$ with the property: For every $\alpha\in[0,B]$ and every vector $\mathbf{v}\in\mathcal{G}$, there exists a $\mathbf{w}\in\mathcal{G}^{\prime}$ such that $\left\|\alpha\mathbf{v}-\mathbf{w}\right\|_{2}^{2}\leq\epsilon^{2}B^{2}$ and $\left\|\mathbf{v}-\frac{\mathbf{w}}{\left\|\mathbf{w}\right\|_{2}}\right\|_{2}^{2}=0$.

For each vector $\mathbf{v}\in\cal G$, add the vectors $(1-\epsilon)^{i}B\mathbf{v}$ for $i=0,\ldots,\log(1/\epsilon)/\epsilon$ to $\mathcal{G}^{\prime}$. Then, for all $\alpha\in[0,B]$ and for every vector $\mathbf{v}\in\mathcal{G}$ there exists a $\mathbf{w}\in G^{\prime}$ such that $\left\|\alpha\mathbf{v}-\mathbf{w}\right\|_{2}^{2}\leq\left\|(1-\epsilon)^{t+1}\mathbf{v}-\mathbf{v}(1-\epsilon)^{t}B\right\|_{2}^{2}\leq\epsilon^{2}B^{2}$, for a value $t$ such that $\alpha\in[(1-\epsilon)^{t+1}B,(1-\epsilon)^{t}B]$. ∎

Appendix B Empirical Estimates of Chow Parameters

In this section, we show that roughly $O(dk/\epsilon^{2})$ samples are sufficient to estimate the degree-$2$ Chow parameters in spectral norm. We will prove the following lemma (Lemma 3.4 in the main body).

Let $f_{\alpha,\bm{W}}(\mathbf{x})=\sum_{i=1}^{k}\alpha_{i}\phi(\langle\mathbf{w}^{(i)},\mathbf{x}\rangle)$, where $\phi(t)$ is an $L$-Lipschitz, positive activation function such that $\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)]\geq C$. Let $\bm{\Sigma}=\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f_{\alpha,\bm{W}}(\mathbf{x})\mathbf{x}\otimes\mathbf{x}]$ be the degree-$2$ Chow parameters of $f_{\alpha,\bm{W}}$. Then for $N=\widetilde{O}(dk/\epsilon^{2})$ samples $(\mathbf{x}^{(i)},y^{(i)})$, where $y^{(i)}=f_{\alpha,\bm{W}}(\mathbf{x}^{(i)})+\xi_{i}$ and $\xi_{i}$ is a zero-mean, subgaussian noise with variance $\sigma^{2}$, it holds with probability at least $99\%$ that

We will require the following lemma from [Ver10] about concentration of matrices with heavy-tailed independent rows.

We are also going to use the following concentration result on sums of random matrices.

We will also need the following well-known result on concentration of polynomials of independent Gaussian random variables. See, e.g., [O’D14].

We next bound the probability that $\left\|\mathbf{x}\right\|_{2}^{2}f_{\alpha,\bm{W}}(\mathbf{x})$ is large. We have

where for the second inequality we used the union bound and for the last one we used the rotation invariance of the normal distribution and the Euclidean norm to set $\mathbf{w}^{(j)}=\mathbf{e}_{1}$. Moreover, we used the fact that $\phi(\mathbf{x}_{1})\leq L|\mathbf{x}_{1}|$ since $\phi(\cdot)$ is $L$-Lipschitz.

where we used Lemma B.4 and the fact that $\mathbf{Var}_{\mathbf{x}\sim\mathcal{N}^{d}}[\left\|\mathbf{x}\right\|_{2}^{2}x_{1}]=\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[\left\|\mathbf{x}\right\|_{2}^{4}x_{1}^{2}]=d^{2}+4d+10\leq 15d^{2}$, for all $d\geq 1$. Note that $C^{\prime}=15C$, where $C$ is the absolute constant of Lemma B.4. Combining Equation (B), Equation (12) and the fact that $\sum_{j=1}^{k}\alpha_{j}=\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[f_{\alpha,\bm{W}}(\mathbf{x})]/\operatorname*{\mathbf{E}}_{t\sim\mathcal{N}}[\phi(t)]:=B$, we obtain

Define the random variables $y_{i}=\left\|\mathbf{x}^{(i)}\right\|_{2}^{2}f_{\alpha,\bm{w}}(\mathbf{x}^{(i)})$. Set $S=O(kdBL)$ and $Q=O(S\log k\log^{3}N)$ we have

To finish the proof, it remains to bound the norm of the sum $\frac{1}{N}\sum_{i=1}^{N}\xi^{(i)}\mathbf{x}^{(i)}\otimes\mathbf{x}^{(i)}$. From Lemma B.3 we obtain that it is bounded above by

We now use Cauchy-Schwarz for the above expectation and observe that

which follows from Lemma B.4 similarly as our previous bound. Moreover, from Lemma B.2 we obtain that

Putting everything together, we obtain that with $N=\widetilde{O}(d/\epsilon^{2})$ samples, the expected norm of $\frac{1}{N}\sum_{i=1}^{N}\xi^{(i)}\mathbf{x}^{(i)}\otimes\mathbf{x}^{(i)}$ is at most $O(\sigma\epsilon)$. The result now follows from Markov’s inequality. ∎

Appendix C Omitted Proofs from SQ Lower Bound

C.2 Preliminaries: Hermite Polynomials

We denote by $f^{[k]}(x)$ the degree $k$ part of the Hermite expansion of $f$, $f^{[k]}(\mathbf{x})=\sum_{|J|=k}\hat{f}(J)\cdot H_{J}(\mathbf{x})$. We say that a polynomial $q$ is harmonic of degree $k$ if it is a linear combination of degree $k$ Hermite polynomials, that is $q$ can be written as

For a single dimensional Hermite polynomial it holds $H_{m}^{\prime}(x)=\sqrt{m}H^{\prime}_{m-1}(x)$. Using this, we obtain that for a multivariate Hermite polynomial $H_{M}(\mathbf{x})$, where $M=(m_{1},\ldots,m_{d})$ it holds

where $E_{i}=\mathbf{e}_{i}$ is the multi-index that has $1$ position $i$ and elsewhere. From this fact and the orthogonality of Hermite polynomials we obtain

Let $p,q$ be a harmonic polynomials of degree $k$. Then

Write $p(\mathbf{x})=\sum_{M:|M|=k}b_{M}H_{M}(\mathbf{x})$ and $q(\mathbf{x})=\sum_{M:|M|=k}c_{M}H_{M}(\mathbf{x})$. Since the Hermite polynomials are orthonormal we obtain $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}}[p(\mathbf{x})q(\mathbf{x})]=\sum_{M:|M|=k}c_{M}b_{M}$. Now, using Equation (13) iteratively we obtain

Observe that for every harmonic polynomial $p(x)$ of degree $k$ we have that $\nabla^{k}p(\mathbf{x})$ is a symmetric tensor of order $k$. Since the degree of the polynomial is $k$ and we differentiate $k$ times this tensor no longer depends on $\mathbf{x}$. Using Fact C.1 we observe that this operation (modulo a division by $\sqrt{k!}$) preserves the $L_{2}$ norm of the harmonic polynomial $p$, that is $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{N}^{d}}[p^{2}(\mathbf{x})]=\left\|\nabla^{k}p(\mathbf{x})\right\|_{2}^{2}/k!$.

To simplify notation, write $f(\mathbf{x})=p(\bm{U}\mathbf{x})$ and $g(\mathbf{x})=p(\bm{V}\mathbf{x})$. The (total) degree of $f$ is the same as the degree of $p$. Write $f(\mathbf{x})=\sum_{m=0}^{\infty}f^{[m]}(\mathbf{x})$ and $g(\mathbf{x})=\sum_{m=0}^{\infty}g^{[m]}(\mathbf{x})$. Then using Fact C.1 we obtain

Now we denote $\bm{R}=\nabla^{m}p^{[m]}(\mathbf{x})$ and observe that this tensor does not depend on $\mathbf{x}$. Moreover, denote $\bm{M}=\bm{U}\bm{V}^{T}$, $\bm{S}=\nabla^{m}p^{[m]}(\bm{U}\mathbf{x})=(\bm{U}^{T})^{\otimes m}\bm{R}\in\mathcal{U}^{\otimes m}$, and $\bm{T}=\nabla^{m}p^{[m]}(\bm{V}\mathbf{x})=(\bm{V}^{T})^{\otimes m}\bm{R}\in\mathcal{V}^{\otimes m}$. We have

where to get the last equality we used again Fact C.1. To finish the proof we combine this inequality with Equation (C.2). ∎

In the following simple lemma we prove that random $2$-dimensional subspaces in high dimensions are roughly orthogonal.

From Lemma C.4, it holds that there exists a set of $2^{\Omega(d^{c})}$ of unit vectors such that $|\cos\theta(\mathbf{u},\mathbf{v})|\leq O(d^{{c-1/2}})$, taking this vectors as columns in each matrix the result follows. ∎

Let $f_{\sigma,\phi}\in\mathcal{H}$. For every polynomial $p(\mathbf{x})$ of degree at most $k$, it holds $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[f_{\sigma,\phi}(\mathbf{x})\cdot p(\mathbf{x})]=0$.

Let $\mathbf{w}^{(m)}=(\cos\frac{2\pi m}{2k},\sin\frac{2\pi m}{2k})$ and $\alpha_{m}=(-1)^{m}$, for $m=1,\ldots,2k$. Let $R_{\pi/k}$ be an operator over functions that rotates the coordinates by $\pi/k$ (i.e., $(x,y)\mapsto(x\cos\frac{\pi}{k}+y\sin\frac{\pi}{k},-x\sin\frac{\pi}{k}+y\cos\frac{\pi}{k})$). Then

where to get the second equality we used that $\alpha_{i}\phi\left(\left\langle(x\cos\frac{\pi}{k}+y\sin\frac{\pi}{k},-x\sin\frac{\pi}{k}+y\cos\frac{\pi}{k}),\mathbf{w}^{(i)}\right\rangle\right)=\alpha_{i}\phi\left(\left\langle(x,y),\mathbf{w}^{(i+1)}\right\rangle\right)$ from basic trigonometric identities and in the last one we used that $\sigma$ is an odd function. Let $p(x,y)=(x+{i\mkern 1.0mu}y)^{a}(x-{i\mkern 1.0mu}y)^{b}$, where ${i\mkern 1.0mu}$ is the imaginary unit, then we are going to prove that $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim D}[f(\mathbf{x})p(\mathbf{x})]=0$ as long as $a-b\not\equiv k\mod 2k$. We have

where $\theta$ is the argument (or the “phase”) of $x+{i\mkern 1.0mu}y$. This means that $p(x,y)$ is an eigenfunction of $R_{\pi/k}$ and $e^{{i\mkern 1.0mu}(\pi/k)(a-b)}$ the corresponding eigenvalue. Thus, it holds

where we used that $R_{\pi/k}$ is an adjoint operator in the inner product space of continuous functions along with Equations (16), (17). Thus, $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[f(\mathbf{x})p(\mathbf{x})]=0$, when $e^{{i\mkern 1.0mu}(\pi/k)(a-b)}\neq-1$, which happens when $a-b\not\equiv k\mod 2k$. To conclude the proof, note that every polynomial at most degree $k$ is a linear combination of the polynomials $p(x,y)=(x+{i\mkern 1.0mu}y)^{a}(x-{i\mkern 1.0mu}y)^{b}$ where $a,b\leq k$. This can be seen by setting $x=\frac{z+\bar{z}}{2}$ and $y=\frac{z-\bar{z}}{2{i\mkern 1.0mu}}$, where $z=x+{i\mkern 1.0mu}y$ and $\bar{z}=x-{i\mkern 1.0mu}y$. ∎

C.3 Interpretation of the class ℋℋ\mathcal{H}

In order for the lower bound construction of Section 4 to produce useful lower bounds, it will be necessary that the function given in Lemma 4.8 is non-vanishing. It turns out that this is the case under fairly weak conditions. In order to state our final result, we will first introduce some terminology:

Given these we have the following result implying that $S_{k}\phi(x)\neq 0$ for a number of functions of interest. For example, if $\phi(x)=\max(0,x)$, is a ReLU, then the even part of $\phi$ is the absolute value function, so $S_{k}\phi\neq 0$ for any even $k$. Similarly, if $\phi$ is a sigmoid, $S_{k}\phi\neq 0$ for any odd $k$.

We begin by noting that $S_{k}\phi(x)\neq 0$ if and only if $(S_{k}\phi(x))^{[m]}\neq 0$ for some $m$. We note that as a rotation $R_{k}$ preserves the degree-$m$ Hermite parts of a function, and therefore so does $S_{k}$. In particular, $(S_{k}\phi(x))^{[m]}=(S_{k}\phi(x)^{[m]}).$ In order to analyze this, we consider the variables $z=x+iy$ and $\bar{z}=x-iy$. We note that if $\phi(x)$ in one variable is given by the Hermite expansion $\phi(x)=\sum_{t=0}^{\infty}a_{t}h_{t}(x)$, that the two-variable version is given by $\sum_{t=0}^{\infty}a_{t}h_{m}((z+\bar{z})/2).$ Furthermore, we have that $(\phi(x))^{[m]}=a_{m}h_{m}((z+\bar{z})/2)$.

Now if $a_{m}=0$, then $(\phi(x))^{[m]}=0$ and therefore $S_{k}(\phi(x))^{[m]}=0$. Otherwise, $a_{m}h_{m}(x)$ has non-vanishing $x^{t}$ coefficients for all $t\leq m$ with $t\equiv m\pmod{2}$. Therefore, in this case $(\phi(x))^{[m]}$ will have a non-vanishing $z^{a}\bar{z}^{b}$ coefficient for all $a,b\geq 0$ with $a+b\leq m$ and $a+b\equiv m\pmod{2}$. Next, we need to understand what $S_{k}$ does to $z^{a}\bar{z}^{b}$.

For this we note that $Rz=e^{\pi i/k}z$ and $R\bar{z}=e^{-\pi i/k}\bar{z}$. Thus $R(z^{a}\bar{z}^{b})=e^{\pi i(a-b)/k}z^{a}\bar{z}^{b}.$ Therefore,

Thus, $S_{k}(\phi(x))^{[m]}$ will be non-vanishing if and only if $a_{m}\neq 0$ and there are some $a,b\geq 0$ with $a+b\leq m,a+b\equiv m\pmod{2}$ and $a-b\equiv k\pmod{2k}$. We claim that such $a,b$ exist if and only if $m\equiv k\pmod{2}$ and $m\geq k$. The only if part of this condition is clear. For the if part, we note that if these conditions are satisfied, we may take $a=\frac{m+k}{2}$ and $b=\frac{m-k}{2}$.

Therefore, we have that $S_{k}\phi(x)\neq 0$ if and only if there is some $m\equiv k\pmod{2}$ with $a_{m}\neq 0$ and $m\geq k$. Note that the $k$-parity-part of $\phi$ has the same Hermite coefficients as $\phi$ for $m\equiv k\pmod{2}$ and 0 coefficient for $m\not\equiv k\pmod{2}$. Thus, $\phi$ has a non-vanishing coefficient for some $m\geq k,m\equiv k\pmod{2}$ if and only if the $k$-parity-part of $\phi$ has some non-vanishing coefficient of degree $m\geq k$. Of course this happens if and only if the $k$-parity-part of $\phi$ is not a polynomial with degree less than $k$. This completes our proof. ∎