Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals

Introduction

Our main results give a trade-off between the accuracy of the output hypothesis and the running time of the algorithm. We give the first evidence that there is no polynomial-time algorithm for finding a ReLU with error $\mathsf{opt}+\epsilon$, even when the marginal distribution is Gaussian:

Assuming hardness of the problem of learning sparse parities with noise, any algorithm for finding a ReLU on data drawn from a distribution with Gaussian marginals that has error at most $\mathsf{opt}+\epsilon$ runs in time $d^{\Omega(\log(1/\epsilon))}$.

Since gradient descent is known to be a statistical-query algorithm (see Section 4), a consequence of Theorem 1 is the following:

Gradient descent fails to converge to the global minimum for learning the best-fitting ReLU with respect to square-loss in polynomial time, even when the marginals are Gaussian.

This above corollary is unconditional (i.e. does not rely on any hardness assumptions) and shows the necessity of the realizable/noiseless setting in the work of Soltanolkotabi [Sol17] and Brutzkus and Globerson [BG17]. We also give the first approximation algorithm for finding the best-fitting ReLU with respect to Gaussian marginals:

There exists a polynomial-time algorithm for finding a ReLU with error $O(\mathsf{opt}^{2/3})+\epsilon$.

The above result uses a novel reduction from learning a ReLU to the problem of learning a halfspace with respect to $0/1$ loss. We note that the problem of finding a ReLU with error $O(\mathsf{opt})+\epsilon$ remains an outstanding open problem.

2 Our Techniques

In our work we must overcome two technical difficulties. First, in the Klivans and Kothari result, it is obvious that for distributions induced by learning sparse parity with noise, the best fitting majority function will be the one that is defined on inputs specified by $S$. In our setting with respect to ReLUs, however, the constant function $1/2$ will have square-loss $1/4$, and this may be much lower than the square-loss of any function of the form $\max(0,\textbf{w}\cdot\textbf{x})$. Thus, we need to prove the existence of a gap between the correlation of ReLUs with random noise (see Claim 3) versus the correlation of ReLUs with parity (see Claim 4).

Second, Klivans and Kothari use known formulas on the discrete Fourier coefficients of the majority function and an application of the central limit theorem to analyze how much the best-fitting majority correlates with the Gaussian lift of parity. No such bounds are known, however, for the ReLU function. As such we must perform a (somewhat involved) analysis of the ReLU function’s Hermite expansion in order to obtain quantitative correlation bounds.

Approximation Algorithm.

For our polynomial-time algorithm that outputs a ReLU with error $\mathsf{O(\mathsf{opt}^{2/3})}+\epsilon$, we apply a novel reduction to agnostically learning halfspaces. We give a simple transformation on the training set to a Boolean learning problem and show that the weight vector w corresponding to the best fitting halfspace on this transformed data set is not too far from the weight vector corresponding to the best fitting ReLU. We can then apply recent work for agnostically learning halfspaces with respect to Gaussians that have constant-factor approximation error guarantees. The exponent $2/3$ appears due to the use of an averaging argument (see Section 5).

3 Related Work

Several recent works have proved hardness results for finding the best-fitting ReLU with respect to square loss (equivalently, agnostically learning a ReLU with respect to square loss). Results showing NP-hardness (e.g., [MR18a, BDL18]) use marginal distributions that encode hard combinatorial problems. The resulting marginals are far from Gaussian. Work due to Goel et al. [GKKT17] uses a reduction from sparse parity with noise but only obtains hardness results for learning with respect to discrete distributions (uniform on $\{0,1\}^{d}$).

Using parity functions as a source of hardness for learning deep networks has been explored recently by Shalev-Shwartz et. al. [SSSS17] and Abbe and Sandon [AS18]. Their results, however, do not address the complexity of learning a single ReLU or consider the case of Gaussian marginals. Shamir [Sha18] proved that gradient descent fails to learn certain classes of neural networks with respect to Gaussian marginals, but these results do not apply to learning a single ReLU [VW18].

In terms of positive results for learning a ReLU, work due to Kalai and Sastry [KS09] (and follow-up work [KKKS11]) gave the first efficient algorithm for learning any generalized linear model (GLM) that is monotone and Lipschitz, a class that includes ReLUs. Their algorithms work for any distribution and can tolerate bounded, mean-zero and additive noise. Soltanolkotabi [Sol17] and Brutzkus and Globerson [BG17] were the first to prove that gradient descent converges to the unknown ReLU in polynomial time with respect to Gaussian marginals as long as the labels have no noise. Other works for learning one-layer ReLU networks with respect to Gaussian marginals or marginals with milder distribution assumptions [ZYWG18, GLM17, ZSJ+17, GKLW18, GKM18, MR18b] also assume a noiseless training set or training set with mean-zero i.i.d. (typically sub-Gaussian) noise. This is in contrast to the setting here (agnostic learning), where we assume nothing about the noise model.

There are several works for the related (but different) problem of agnostically learning halfspaces with respect to Gaussian marginals [KKMS08, ABL14, Zha18, DKS18]. While agnostically learning ReLUs may seem like an easier problem than agnostically learning halfspaces (at first glance the learner sees “more information” from the ReLU’s real-valued labels), the quantitative relationship between the two problems is still open. In the halfspace setting, we can assume without loss of generality that an adversary has flipped an $\mathsf{opt}$ fraction of the labels. In contrast, in the setting with ReLUs and square loss, it is possible for the adversary to corrupt every label.

Preliminaries

The model of learning we work with in the paper is the agnostic model of learning. In this model the labels are allowed to be arbitrary and the task of the learner is to output a hypothesis within an $\epsilon$ error of the optimal. More formally,

A class $\mathcal{C}$ is said to be agnostically learnable in time $t$ over the Gaussian distribution to error $\epsilon$ if there exists an algorithm ${\cal A}$ such that for any distribution $\mathcal{D}$ on $X\times Y$ with the marginal on $X$ being Gaussian, ${\cal A}$ uses at most $t$ draws from ${\cal D}$, runs in time at most $t$, and outputs a hypothesis $h\in\mathcal{C}$ such that $\mathsf{err}_{\mathcal{D}}(h)\leq\mathsf{opt}_{\mathcal{D}}(\mathcal{C})+\epsilon$.

We assume that ${\cal A}$ succeeds with constant probability. Note that the algorithm above outputs the “best-fitting” $c\in\mathcal{C}$ with respect to $\mathcal{D}$ up to an additive $\epsilon$. We will denote $\widehat{\mathsf{err}}_{\mathcal{S}}(h)$ to be the empirical error of $h$ over samples $\mathcal{S}$.

Learning Sparse Parities with Noise.

In this work we will show that agnostically learning $\mathcal{C}_{\mathsf{ReLU}}$ over the Gaussian distribution is as hard as the problem of learning sparse parities with noise over the uniform distribution on the hypercube.

Given access to samples drawn from the uniform distribution over $\{\pm 1\}^{d}$ and target function $y$ being the parity function over an unknown set $S\subseteq[d]$ of size $k$, the problem of learning sparse parities with noise is the problem of recovering the set $S$ given access to noisy labels where the label is flipped with probability $\eta$.

Learning sparse parities with noise is generally considered to be a computationally hard problem and has been used to give hardness results for both supervised [GKKT17] and unsupervised learning problems [BGS14]. The current best known algorithm for solving sparse parities with constant noise rate is due to Valiant [Val15] and runs in time $\approx d^{0.8k}$.

Any algorithm for solving $k$-SLPN up to constant error must run in time $d^{\Omega(k)}$.

Gaussian Lift of a Function

Our reduction will require the following definition of a Gaussian lift of a boolean function from [KK14].

Hermite Analysis and Gaussian Density

We will need the following facts about Hermite polynomials.

For all $m\geq 0$, $H_{2m+1}(0)=0$ and $H_{2m}=(-1)^{m}\frac{(2m)!}{m!2^{m}}$.

$\widehat{\mathsf{sign}}_{0}=0$ and for $i\geq 1$, $\widehat{\mathsf{sign}}_{i}=\sqrt{\frac{2}{\pi i!}}H_{i-1}(0)$.

Hardness of Learning ReLU

In this section, we will show that if there is an algorithm that agnostically learns a ReLU in polynomial time, then there is an algorithm for learning sparse parities with noise in time $d^{o(k)}$, violating Assumption 1. We will follow the approach of [KK14]. Let $\chi_{S}$ be an unknown parity for some $S\subseteq[d]$. We will show that there is an unbiased ReLU that is correlated with the Gaussian lift of the unknown sparse parity function. Notice that dropping a coordinate $j\in S$ from the input samples makes the labels of the resulting training set totally independent from the input. In contrast, dropping $j\notin S$ results in a training set that is still labeled by a noisy parity. Therefore, we can use an agnostic learner for ReLUs to detect a correlated ReLU and distinguish between the two cases. This allows us to identify the variables in $S$ one by one.

We formalize the above approach by first proving the following key property,

Let $\chi_{S}^{\gamma}$ denote the Gaussian lift of the parity on variables in $S\subset[d]$. For every $S\subset[d]$ with $|S|\leq k$ and $k=4l+2$ for some $l\geq 0$, there exists $\mathsf{ReLU}_{\textbf{w}_{S}}$ such that $\langle\mathsf{ReLU}_{\textbf{w}_{S}},\chi_{\alpha}^{\gamma}\rangle\geq 2^{-O(k)}$ where $\mathsf{ReLU}_{\textbf{w}_{S}}$ only depends on variables in $S$.

Let $\textbf{w}_{S}=\frac{1}{\sqrt{2\pi k}}\sum_{i\in S}\textbf{e}^{(i)}$ where $\textbf{e}^{(i)}$ is 1 at coordinate $i$ and 0 everywhere else. We will show that

Let $\widehat{\mathsf{sign}}_{n}$ and $\widehat{\mathsf{ReLU}}_{n}$ denote the degree $n$ Hermite coefficients of the $\mathsf{sign}$ function and $\mathsf{ReLU}$ function respectively. It is easy to see that the Hermite expansion of the Gaussian lift of a parity supported on $S$ is,

In order to finish the proof of Lemma 1 we will need the expansion of $\mathsf{ReLU}\left(\frac{\sum_{i}z_{i}}{\sqrt{k}}\right)$ in terms of products of univariate Hermite polynomials. Toward this end we establish the following claims.

$\widehat{\mathsf{ReLU}}_{0}=1/\sqrt{2\pi}$, $\widehat{\mathsf{ReLU}}_{1}=1/2$ and for $i\geq 2$, $\widehat{\mathsf{ReLU}}_{i}=\frac{1}{\sqrt{2\pi i!}}(H_{i}(0)+iH_{i-2}(0))$.

Combining Equation 1 and Claim 2 now yields,

From Fact 2 and Claim 4 we see that $\widehat{\mathsf{sign}}_{2m}=0$ and $\widehat{\mathsf{ReLU}}_{2m+1}=0$ for $m\geq 1$. Additionally, since $\widehat{\mathsf{sign}}_{0}=0$ we see that each $n_{i}\geq 1$. This gives us,

To finish the proof of Lemma 1, we will look at each term in the outer summation above. Let the term for any fixed $n\geq k$ be denoted by $T_{n}$. Since $\bar{H}_{i}(0)=0$ for odd $i$, observe that $T_{n}$ is non-zero if and only if $n$ is even and each $n_{i}=2n^{\prime}_{i}+1$ for $n^{\prime}_{i}\geq 0$. We have

Since $k=4l+2$ (by assumption), $T_{n}>0$ for all even $n\geq k$ and equal to 0 for all odd $n$. Thus $\sum_{n=k}^{\infty}T_{n}>T_{k}$. Lower bounding $T_{k}$, we have

Now we present our main algorithm (Algorithm 1) that reduces learning sparse parities with noise to agnostically learning ReLUs and a proof of its correctness.

If there is an algorithm to agnostically learn unbiased ReLUs on the Gaussian distribution in time and samples $T(d,1/\epsilon)$, then there is an algorithm to solve $k$-SLPN in time $O\left(\frac{2^{O(k)}}{(1-2\eta)^{2}}\log(d)\right)+O(d)T\left(d,\frac{2^{O(k)}}{1-2\eta}\right)$ where $\eta$ is the noise rate.

In particular, if Assumption 1 is true, then any algorithm for agnostically learning (unbiased) ReLUs on the Gaussian distribution must run in time $d^{\Omega(\log(1/\epsilon))}$.

Given a set of samples from the $k$-SPLN problem, we claim that Algorithm 1 can recover all indices $j$ belonging to the sparse parity when run with appropriate parameters. We will first show that if a variable is relevant then the error is smaller compared to when it is irrelevant. It is easy to see that $y^{\prime}$ is $\frac{\prod_{i\in S}\mathsf{sign}(x^{\prime}_{i})+1}{2}$ with probability $1-\eta$ and $\frac{1-\prod_{i\in S}\mathsf{sign}(x^{\prime}_{i})}{2}$ otherwise. Let $\mathcal{D}_{j}$ denote the distribution obtained by dropping the $j$th coordinate from the lifted distribution and let $S$ denote the set of active indices of the parity. The proof of the theorem follows from the following claims,

If $j\in S$ then for all w, $\mathsf{err}_{\mathcal{D}_{j}}(\mathsf{ReLU}_{\textbf{w}})=\frac{\|\textbf{w}\|^{2}}{2}-\frac{\|\textbf{w}\|}{\sqrt{2\pi}}+\frac{1}{2}\geq\frac{1}{2}-\frac{1}{4\pi}$.

If $j\notin S$ then there exists $\textbf{w}^{*}$ with $\|\textbf{w}^{*}\|=\frac{1}{\sqrt{2\pi}}$ such that $\mathsf{err}_{\mathcal{D}_{j}}(\mathsf{ReLU}_{\textbf{w}^{*}})<\frac{1}{2}-\frac{1}{4\pi}-\frac{2^{-O(k)}}{1-2\eta}.$

Claims 3 and 4 imply that we have a gap of at least $\frac{2^{-O(k)}}{1-2\eta}=\frac{2^{-ck}}{1-2\eta}$ for some $c>0$ between the relevant and irrelevant variable case. Setting $\epsilon=\frac{2^{-ck}}{1-2\eta}$ in Algorithm 1 will let us detect this gap. Since $\mathcal{A}$ is an agnostic learner for ReLU, as long as $M_{1}=T(d,2/\epsilon)$ we know that with probability $2/3$, for all $j\in S$, $\mathcal{A}$ runs on $\mathcal{S}_{j}$ and outputs $h_{j}$ such that $\mathsf{err}_{\mathcal{D}_{j}}(h_{j})\leq\min_{\textbf{w}}\mathsf{err}_{\mathcal{D}_{j}}(\mathsf{ReLU}_{\textbf{w}})\leq\frac{1}{2}-\frac{1}{4\pi}-\epsilon/2$, and for all $j\notin S$, $\mathsf{err}_{\mathcal{D}_{j}}(h_{j})\geq\frac{1}{2}-\frac{1}{4\pi}$.

Using standard concentration inequalities for sub-Gaussian and subexponential random variables [Ver] we see that using a validation set of $M_{2}=100/\epsilon^{2}$ samples, we have for all $j$, $|\widehat{\mathsf{err}}_{\mathcal{V}_{j}}(h_{j})-\mathsf{err}_{\mathcal{D}_{j}}(h_{j})|\leq\epsilon/4$. Therefore, we can differentiate the two cases as in the Algorithm with confidence $>1/2$. It is easy to see that the run time of the algorithm is $O(d)T(d,2/\epsilon)+O(1/\epsilon^{2})$, and that this can be amplified to obtain an algorithm with any desired confidence using standard techniques. ∎

Lower Bounds for SQ Algorithms

A consequence of Theorem 3 is that any statistical-query algorithm for agnostically learning a ReLU with respect to Gaussian marginals yields a statistical-query algorithm for learning parity functions on $k$ unknown input bits. This implies that there is no polynomial time statistical-query (SQ) algorithm that learns a ReLU with respect to Gaussian marginals for a certain restricted class of queries.

SQ Dimension.

Let $\mathcal{F}$ be a concept class and let $s$ be the SQ dimension of $\mathcal{F}$ with respect to $\mathcal{D}$. Then any learning algorithm that uses tolerance parameter lower bounded by $\tau>0$ and has access to an oracle that returns $\tau$-approximate expectations (with respect to $\mathcal{D}$) of unit norm correlation queries and queries that are independent of the target, requires at least $(s\tau^{2}-1)/2$ queries.

In this model of learning, we show the following lower bound for the problem of learning ReLUs over the Gaussian distribution.

Any SQ algorithm for agnostically learning a ReLU with respect to any distribution $\mathcal{D}$ satisfying Gaussian marginals over the attributes, requires $d^{\Omega(\log(1/\epsilon))}$ unit norm correlation queries or queries independent of the target with tolerance $\frac{1}{\text{poly}(d,1/\epsilon)}$ to an oracle that returns $\tau$-approximate expectations with respect to $\mathcal{D}$.

Define the problem of ‘restricted $k$-sparse parities’ as the problem of learning an unknown parity function $\chi_{S}$ over set $S$, where $S$ contains $k$ out of the first $d$ variables over $\mathcal{D}$ with input distribution $\mathcal{D}_{b}\times\mathcal{N}(0,I_{d})_{+}$. Here $\mathcal{D}_{b}$ is the uniform distribution on $\{\pm 1\}^{d}$ and the labels $y(\textbf{x})$ are given by $\chi_{S}(\textbf{x})$. It is easy to see that Theorem 4 implies that we require $d^{\Omega(k)}$ unit norm queries to learn this function class from queries to an oracle $\mathcal{O}$ with tolerance $1/\text{poly}(d,2^{k})$.

We give a proof by contradiction. Suppose we can agnostically learn ReLUs with respect to Gaussian marginals using an SQ algorithm ${\cal A}$ with $d^{o(\log\frac{1}{\epsilon})}$ queries to the corresponding oracle with tolerance $1/\text{poly}(d,\frac{1}{\epsilon})$. We will show how to use $\mathcal{A}$ to design an SQ algorithm for the problem of learning restricted $k$-sparse parities using $d^{o(k)}$ queries contradicting Theorem 4.

Since for $k=\Theta(\log\frac{1}{\epsilon})$, such an algorithm would solve the problem of ‘restricted $k$-sparse parities’ using $d^{o(k)}$ queries of tolerance $1/\text{poly}(d,2^{k})$. This contradicts the $d^{\Omega(k)}$ lower bound on the number of queries required to solve $k$-SPLN of tolerance $1/\text{poly}(d,2^{k})$ we get from Theorem 4. ∎

Approximation Algorithm

In this section we give a learning algorithm that runs in polynomial time in all input parameters and outputs a ReLU that has error $O(\mathsf{opt}^{2/3})+\epsilon$ where $\mathsf{opt}$ is the error of the best-fitting ReLU. The main reduction is a hard thresholding of the labels to create a training set with Boolean labels. We then apply a recent result giving a polynomial-time approximation algorithm for agnostically learning halfspaces over the Gaussian distribution due to Awasthi et. al. [ABL14]. We present our algorithm and give a proof of its correctness.

There is an algorithm (Algorithm 2) that given $O(\mathsf{poly}(d,1/\epsilon))$ samples $(\textbf{x},y)$ such that x is drawn from $N(0,I_{d})$ and $y\in$ recovers a unit vector w such that $\mathsf{err}(\mathsf{ReLU}_{\textbf{w}})\leq O(\mathsf{opt}^{2/3})+\epsilon$ where $\mathsf{opt}:=\min_{\|\textbf{w}\|=1}\mathsf{err}(\mathsf{ReLU}_{\textbf{w}}).$

Let $\textbf{w}^{*}=\operatorname*{arg\,min}_{\|\textbf{w}\|=1}\mathsf{err}(\mathsf{ReLU}_{\textbf{w}})$ and so, $\mathsf{err}(\mathsf{ReLU}_{\textbf{w}^{*}})=\mathsf{opt}$. Define the $S_{good}$ to be the set of points that are $\alpha$-close to the optimal $\mathsf{ReLU}$, i.e. $S_{good}=\{x:|y-\mathsf{ReLU}_{\textbf{w}^{*}}(\textbf{x})|\leq\alpha\}$. By Markov’s inequality,

We now apply Theorem 8 from [ABL14] which gives an algorithm with polynomial running time in $d$ and $1/\epsilon$ that outputs a w such that $\|\textbf{w}\|=1$ and $\|\textbf{w}-\textbf{w}^{\dagger}\|\leq O(\left(\frac{\mathsf{opt}}{\alpha^{2}}+2\alpha\right))+\epsilon$. For unit vectors $\textbf{a},\textbf{b}$, $\theta(\textbf{a},\textbf{b})<C\Pr[\mathsf{sign}(\textbf{a}\cdot\textbf{x})\neq\mathsf{sign}(\textbf{b}\cdot\textbf{x})]$ for some absolute constant $C$ where $\theta(\textbf{a},\textbf{b})$ is the angle between the vectors (see Lemma 2 in [ABL14]). The triangle inequality and the fact that $\|\textbf{a}-\textbf{b}\|\leq\theta(\textbf{a},\textbf{b})$ implies that if $\mathsf{err}_{0/1}(\textbf{a}),\mathsf{err}_{0/1}(\textbf{b})<\eta$ then $\|\textbf{a}-\textbf{b}\|\leq C\Pr[\mathsf{sign}(\textbf{a}\cdot\textbf{x})\neq\mathsf{sign}(\textbf{b}\cdot\textbf{x})]\leq O(\eta)$. Applying this to $\textbf{w}^{\dagger}$ and $\textbf{w}^{*}$ yields $\|{\textbf{w}}^{\dagger}-\textbf{w}^{*}\|<O(\frac{\mathsf{opt}}{\alpha^{2}}+2\alpha)$. Since the ReLU function is 1-Lipschitz, we have

Setting $\alpha=\mathsf{opt}^{1/3}$ and rescaling $\epsilon$ we have $\mathsf{err}(\mathsf{ReLU}_{\textbf{w}})\leq O(\mathsf{opt}^{2/3})+\epsilon.$ ∎

Conclusions and Open Problems

We have shown hardness for solving the empirical risk minimization problem for just one ReLU with respect to Gaussian distributions and given the first nontrivial approximation algorithm. Can we achieve approximation $O(\mathsf{opt})+\epsilon$? Note our results holds only for the case of unbiased ReLUs, as the constant function $1/2$ may achieve smaller square-loss than any unbiased ReLU. Interestingly, all positive results that we are aware of for learning ReLUs (or one-layer ReLU networks) with respect to Gaussians also assume the ReLU activations are unbiased (e.g., [BG17, Sol17, GKM18, GKLW18, GLM17, ZYWG18]). How difficult is the biased case?

References

Appendix A Useful Properties

For $\beta_{1},\ldots,\beta_{k}$ such that $\sum_{i=1}^{k}\beta_{i}^{2}=1$, we have

Observe that for $\textbf{z}\sim\mathcal{N}(0,\textbf{I}_{d})$, $\textbf{w}\cdot\textbf{z}\sim\mathcal{N}(0,||\textbf{w}||^{2})$, thus we have

The last follows from observing that the integral is $1/2$ of the variance of a $N(0,||\textbf{w}||^{2})$ variable. Similarly, we have

Here the last equality follows from standard computation of mean of the absolute value of a Gaussian random variable. ∎

Appendix B Omitted Proofs

Here we used the additional property on the recurrence of $H$, that is, $H_{n+1}(x)=xH_{n}(x)-nH_{n-1}$. ∎

Since $\sum_{i\in S}\left(\frac{1}{\sqrt{k}}\right)^{2}=1$ using Fact 3, we have

Here the third equality follows since $j\in S$ and not in $\textbf{z}_{-j}$ therefore, the label is random for the ReLU. The last equality follows from Lemma 1. Note that, for any ReLU, the minimum error is achieved when $||\textbf{w}||=\frac{1}{\sqrt{2\pi}}$. Thus when $j\not\in S$ the best ReLU achieves error at least $\frac{1}{2}-\frac{1}{4\pi}$. ∎

Since $j$ is not a relevant variable $S\subseteq[d]\setminus\{j\}$, from Theorem 1, we know that there exists $\mathsf{ReLU}_{\textbf{w}_{S}}$ with $||\textbf{w}_{S}||=1/\sqrt{2\pi}$ dependent only on variables in $S$ correlated with $\chi^{\gamma}_{S}$,