Provable limitations of deep learning

Introduction

It is known that the class of neural networks (NNs) with polynomial network size can express any function that can be implemented in a given polynomial time, and that their sample complexity scales polynomially with the network size. Thus NNs have favorable approximation and estimation errors. The main challenge is with the optimization error, as there is no known efficient training algorithm for NNs with provable guarantees, in particular, it is NP-hard to implement the ERM rule [KS09, DSS16].

The success behind deep learning is to train deep NNs with descent algorithms (e.g., coordinate, gradient or stochastic gradient descent); this gives record performances in image [KSH12], speech [HDY+12] and document recognitions [LBBH98], and the scope of applications is increasing on a daily basis [LBH15, GBC16]. While deep learning operates in an overparametrized regime, and while SGD optimizes a highly non-convex objective function, the training by SGD gives astonishingly low generalization errors in these applications. A major research effort is devoted to explaining these successes, with various components claimed responsible, such as the compositional structure of neural networks matching that of real signals, the implicit regularizations behind SGD (e.g., its stochastic component), the increased size of data sets and the augmented computational power, among others.

With the wide expansion of the field, one would like to also envision the potential limits of deep learning. This is the focus of this paper. To understand the limitations of deep learning, we look for classes of functions that are efficiently learnable by some algorithm, but not for deep learning.

The function that computes the parity of a Boolean vector is a well-known candidate [LeC16], as most functions that SGD is likely to try would be essentially uncorrelated with it, making it difficult to get close enough to the right function in a manageable time. However, any Boolean function that can be computed in time $O(T(n))$ can also be expressed by a neural network of size $O(T(n)^{2})$ [Par94, SSBD14], and so one could always start with a neural net that is set to compute the desired function, such as the parity function. The problem is thus meaningful only if one constraints the type of initialization (e.g., random initializations) or if one deals with a class of functions (concept class) rather than a specific one, as commonly done for parities [Sha18, Raz16]. We next discuss the example of parities before going back to general function distributions in Sections 1.4 and 2.

The problem of learning parities is formulated as follows. Define the class of all parity functions by $\mathcal{F}=\{p_{s}:s\subseteq[n]\}$, where $p_{s}:\{+1,-1\}^{n}\to\{+1,-1\}$ is such that

Nature picks $S$ uniformly at random in $2^{[n]}$, and with access to $\mathcal{F}$ but not to $S$, the problem is to run a descent algorithm for a polynomial number of steps $t$ (in $n$) to obtain $w^{(t)}$ (e.g., coordinate, gradient or stochastic gradient descent using labeled samples $(X_{i},P_{S}(X_{i}))$ where the $X_{i}$’s are independently and uniformly drawn in $\{+1,-1\}^{n}$).

The goal is to have the neural network output a label $eval_{w^{(t)}}(X)$ on a uniformly random input $X$ that (at least) correlates with the true label $p_{S}(X)$, such as

for some notion of mutual information (e.g., TV, KL or Chi-squared mutual information), or

Note that this is a weak learning requirement, thus failing at this is discarding any stronger requirements related to PAC-learning as mentioned in Section 2. Note also that this objective can be achieved if we do not restrict ourselves to using a NN trained with a descent algorithm. In fact, one can simply take an algorithm that builds a basis from enough samples (e.g., $n+\Omega(\log(n))$) and solves the resulting system of linear equations to reconstruct $S$. This seems however far from how deep learning proceeds. For instance, SGD is “memoryless” in that it updates the weights of the NN at each step with a sample but does not a priori explicitly remember the previous samples. Since each sample gives very little information about the true $S$, it thus seems unlikely for SGD to make any progress on a polynomial time horizon. However, it is far from trivial to argue this formally if we allow the NN to be arbitrarily large and with arbitrary initialization (albeit of polynomial complexity), and in particular inspecting the gradient is typically not sufficient. In fact, we claim that this is wrong, and deep learning can learn the parity function with a careful (though poly-time) initialization — See Sections 2.3 and 7.

On the other hand, if the initialization is done at random, as commonly assumed [SSBD14], and the descent algorithm is run with perturbations, as sometimes advocated in different forms [GHJY15, WT11, RRT17], or if one does not move with the full gradient such as in (block-)coordinate descent or more generally bounded-memory update rules, then we show that it is in fact hard to learn parities. We will provide results in such settings showing the failure of deep learning.

Note also that having GD run with little noise is not equivalent to having noisy labels for which learning parities can be hard irrespective of the algorithm used [BKW03, Reg05]; in fact, the amount of noise that we need for running GD to obtain failure is exponentially small, which would effectively represent no noise if that noise was added on the labels itself (e.g., Gaussian elimination would still work).

2 An illustrative experiment

To illustrate the phenomenon, we consider the following data set and numerical experiment in PyTorch [PGC+17]. The elements in $\mathcal{X}$ are images with a white background and either an even or odd number of black dots, with the parity of the dots determining the label — see Figure 1. The dots are drawn by building a $k\times k$ grid with white background and activating each square with probability $1/2$.

We then train a neural network to learn the parity label of these images. The architecture is a 3 hidden linear layer perceptron with 128 units and ReLU non linearities trained using binary cross entropy. The training and testing dataset are composed of 1000 images of grid-size $k=13$. We used PyTorch implementation of SGD with step size 0.1 and i.i.d. rescaled uniform weight initialization [HZRS15].

Figure 2 show the evolution of the training loss, testing and training errors. As can be seen, the net can learn the training set but does not generalize better than random guessing.

Note that this is not exactly the model of Section 1.1. In the experiment, each image can be viewed as a Boolean vector of dimension $k^{2}$, but the parity is taken over the entire vector, rather than a subset $S$. This is however similar to our setup due to the following observation.Another minor distinction is to sample from a pre-set training set v.s. sampling fresh samples, but both can be implemented similarly for the experiment. First consider the same experiment where one only takes the parity on the set $S$ consisting of the first half of the image; this would have the same performance outcome. Now, since the net is initialized with i.i.d. random weights, taking $S$ has the first half or any other random subset of $\approx k^{2}/2$ components leads to the same outcome by symmetry. Therefore, we expect failure for the same reason as we expect failure in our model with enough randomness in the initialization.

3 Learning general function and input distributions

In this paper, we will investigate the effect of general input distribution $P_{\mathcal{X}}$ and function distribution $P_{\mathcal{F}}$ on deep learning.

Let $n>0$, $\epsilon>0$, $P_{\mathcal{X}}$ be a probability distribution on $\mathcal{X}=\mathcal{D}^{n}$ for some set $\mathcal{D}$, and $P_{\mathcal{F}}$ be a probability distribution on the set of functions from $\mathcal{X}$ to $\{+1,-1\}$.

4 Insights about failures and successes of deep learning

Our negative results reveal a measure that captures when the considered deep learning algorithms fail.

For a probability measure $P_{\mathcal{X}}$ on the data domain $\mathcal{X}$, and a probability measure $P_{\mathcal{F}}$ on the class of functions $\mathcal{F}$ from $\mathcal{X}$ to $\mathcal{Y}=\{+1,-1\}$, we define the cross-predictability of $P_{\mathcal{F}}$ with respect to $P_{\mathcal{X}}$ by

The main insight is as follows. All of the algorithms that we consider essentially take a neural net, attempt to compute how well the functions computed by the net and slightly perturbed versions of the net correlate with the target function, and adjust the net in the direction of higher correlation. If none of these functions have significant correlation with the target function, this will generally make little or no progress. The descent algorithm evolves in a flat minima where no significant progress is made in a polynomial time horizon.

Of course, for any specific target function, we could initialize the net to correlate with it. However, if the target function is randomly drawn from a class with negligible cross-predictability, and if one cannot operate with GD or SGD perfectly, then no function is significantly correlated with the target function with nonnegligible probability and a descent algorithm will generally fail to learn the function in polynomial time.

Consider a symmetric function distribution, i.e., one that is invariant under a permutation of the input variables (e.g., random monomials). If one cannot learn this distribution with any initialization of the net, one cannot learn any given function in the distribution support with a random i.i.d. initialization of the net. This is because a random i.i.d. initialization of the net is itself symmetric under permutation.

Further, we claim that the cross-predictability measure can be used to understand when a given function $h$ cannot be learned in poly-time with GD/SGD on poly-size nets that are randomly initialized, without imposing noise or memory constraints on how GD/SGD are run.

Namely, define the cross-predictability between a target function and a random neural net as

where $(G,f)$ is a random neural net under the distribution $\mu_{NN}$, i.e., $f$ is a fixed non-linearity, $G$ is a random graph that consists of complete bipartiteOne could consider other types of graphs but a certain amount of randomness has to be present in the model. graphs between consecutive layers of a poly-size NN, with weights i.i.d. centered Gaussian of variance equal to one over the width of the previous layer, and $X\sim P_{\mathcal{X}}$ is independent of $G$. We then claim that if such a cross-predictability decays super-polynomially, training such a random neural net with a polynomial number of steps of GD or SGD will fail at learning even without memory or noise constraints. Again, as mentioned above, if the target function is permutation invariant, it cannot be learned with a random initialization and noisy GD with small random noise. So the claim is that the random initialization gives already enough randomness in one step to cover all the added randomness from noisy GD.

4.2 Succeeding with large cross-predictability

In the case of random degree $k$ monomials, i.e., parity functions on a uniform subset $S$ of size $k$ with uniform inputs, we will show that deep learning fails at learning under memory or noise constraints as soon as $k=\omega(1)$. This is because the cross-predictability scales as ${n\choose k}^{-1}$, which is already super-polynomial when $k=\omega(1)$.

On the flip side, if $k$ is constant, it is not hard to show that GD can learn this function distribution by inputting all the ${n\choose k}$ monomials in the first layer (and for example the cosine non-linearity to compute the parity in one hidden layer). Therefore, for random degree $k$ monomials, the deep learning algorithms described in our theorems will succeed at learning if and only if $k=O(1)$. Thus one can only learn “local” functions in that sense.

We believe that small cross-predictability does not take place for typical labelling functions concerned with images or sounds, where many of the functions we would want to learn are correlated both with each other and with functions a random neural net is reasonably likely to compute. For instance, the objects in an image will correlate with whether the image is outside, which will in turn correlate with whether the top left pixel is sky blue. A randomly initialized neural net is likely to compute a function that is nontrivially correlated with the last of these, and some perturbations of it will correlate with it more, which means the network is in position to start learning the functions in question.

Intuitively, this is due to the fact that images and image classes have more compositional structures (i.e., their labels are well explained by combining ‘local’ features). Instead, parity functions of large support size, i.e., not constant size but growing size, are not well explained by the composition of local features of the vectors, and require more global operations on the input.

5 Succeeding beyond cross-predictability

As previously mentioned, certain methods of training a neural net cannot learn a random function drawn from any distribution with a cross-predictability that goes to zero at a superpolynomial rate. This raises the question of whether or not these methods can successfully learn a random function drawn from any distribution with a cross-predictability that is at least the inverse of a polynomial.

The first obstacle to learning such a function is that some functions cannot be computed to a reasonable approximation by any neural net of polynomial size. A probability distribution that always yields the same function has a cross-predictability of $1$, but if that function cannot be computed with nontrivial accuracy by any polynomial-sized neural net, then any method of training such a net will fail to learn it.

However, we cannot do much better than this. To demonstrate that, consider a probability distribution over functions that returns the function that always outputs $1$ with probability $1/\ln(n)$, the function that always outputs $-1$ with probability $1/\ln(n)$, and a random function otherwise. This distribution has a cross-predictability of $\theta(1/\ln^{2}(n))$. However, a function drawn from this distribution is only efficiently learnable if it is one of the constant functions. As such, any method of attempting to learn a function drawn from this distribution that uses a subexponential number of samples will fail with probability $1-O(1/\ln(n))$. In particular, this type of example demonstrates that for any $g=o(1)$, there exists a probability distribution of functions with a cross-predictability of at least $g(n)$ such that no efficient algorithm can learn this distribution with an accuracy of $1/2+\Omega(1)$.

However, one can likely prove that a neural net trained by noisy GD or noisy SGD can learn $P_{\mathcal{F}}$ if it satisfies the following property. Let $m$ be polynomial in $n$, and assume that there exists a set of functions $g_{1},...,g_{m}$ such that each of these functions is computable by a polynomial-sized neural net and the projection of a random function drawn from $P_{\mathcal{F}}$ onto the vector space spanned by $g_{1},...,g_{m}$ has an average magnitude of $\Omega(1)$. In order to learn $P_{\mathcal{F}}$, we start with a neural net that has a component that computes $g_{i}$ for each $i$, and edges linking the outputs of all of these components to its output. Then, the training process can determine how to combine the information provided by these components to compute the function with an advantage that is within a constant factor of the magnitude of its projection onto the subspace they define. That yields an average accuracy of $1/2+\Omega(1)$. However, we do not think that this is a necessary condition to be able to learn a distribution using a neural net trained by noisy SGD or the like.

6 Related works

The difficulty of learning parities with NNs is not new. The parity was already known to be hard based on the early works on the perceptron [MP87], see also [Hås87, All96]. We now discuss various works related to ours.

Statistical querry algorithms. The lack of correlations between two parity functions and its implication in learning parities appear also in the context of statistical query learning algorithms [Kea98, BFJ+94], which are algorithms that access estimates of the expected value of some query function over the underlying data distribution (e.g., the first moment statistics of inputs’ coordinates).

In particular, gradient-based algorithms with approximate oracle access are realizable as statistical query algorithms, and [Kea98] implies that the class of parity functions cannot be learned by such algorithms, which gives a result similar in nature to our Theorem 3. However, the result from [Kea98] and its generalization in [BKW03] have a few differences from those presented here; first these papers define successful learning for any function in a class of function, where as we will work with typical functions from a function distributions; second these papers require the noise to be adversarial, while we use statistical (and thus less restrictive) noise; finally the proof techniques are different, mainly based on Fourier analysis in [BKW03] and on hypothesis testing here.

One could also use [Kea98] to obtain a variant of our Theorem 2. Technically [Kea98] only says that a SQ algorithm with a polynomial number of queries and inverse polynomial noise cannot learn a parity function, but the proof would still work with appropriately chosen exponential parameters. To further convert this to the setting with statistical noise, one could use an argument saying that the Gaussian noise is large enough to mostly drown out the adversarial noise if the latter is small enough, but the resulting bounds would be slightly looser than ours because that would force one to make trade offs between making the amount of adversarial noise in the SQ result low and minimizing the probability that one of the queries does provide meaningful information. Alternately, one could probably rewrite their proof using Gaussian noise instead of bounded adversarial noise and bound sums of $L_{1}$ differences between the probability distributions corresponding to different functions instead of arguing that with high probability the bound on the noise quantity is high enough to allow the adversary to give a generic response to the query.

To see how Theorem 3 departs from the setting of [BKW03] beyond the statistical noise discussed above, note that the cross-predictability captures the expected inner product $\langle F_{1},F_{2}\rangle_{P_{\mathcal{X}}}$ over two i.i.d. functions $F_{1},F_{2}$ under $P_{\mathcal{F}}$, whereas the statistical dimension defined in [BKW03] is the largest number $d$ of functions $f_{i}\in\mathcal{F}$ that are nearly orthogonal, i.e, $|\langle f_{i},f_{j}\rangle_{P_{\mathcal{X}}}|\leq 1/d^{3}$, $1\leq i<j\leq d$. Therefore, while the cross-predictability and statistical dimension tend to be negatively correlated, one can construct a family $\mathcal{F}$ that contains many almost orthogonal functions, yet with little mass under $P_{\mathcal{F}}$ on these so that the distribution has a high cross-predictability. For example, take a class containing two types of functions, hard and easy, such as parities on sets of components and almost-dictatorships which agree with the first input bit on all but $n$ of the inputs. The parity functions are orthogonal, so the union contains a set of size $2^{n}$ that is pairwise orthogonal. However, there are about $2^{n}$ of the former and $2^{n^{2}}$ of the latter, so if one picks a function uniformly at random on the union, it will belong to the latter group with high probability, and the cross-predictability will be $1-o(1)$. So one can build examples of function classes where it is possible to learn with a moderate cross-predictability while the statistical dimension is large and learning fails in the sense of [BKW03].

There have been further extensions of the statistical-dimension, such as in [FGR+17] which allows for a probability measure on the functions as well. The statistical dimension as defined in Definition 2.6 of [FGR+17] measures the maximum probability subdistribution with a sufficiently high correlation among its members.Another difference with [FGR+17] is that our results show failures for weak rather than exact learning. As a result, any probability distribution with a low cross predictability must have a high statistical dimension in that sense. However, a distribution of functions that are all moderately correlated with each other could have an arbitrarily high statistical dimension despite having a reasonably high cross-predictability. For example, using definition 2.6 of [FGR+17] with constant $\bar{\gamma}$ on the collection of functions from $\{0,1\}^{n}->\{0,1\}$ that are either 1 on $1/2+\sqrt{\gamma}/4$ of the possible inputs or 1 on $1/2-\sqrt{\gamma}/4$ of the inputs, gives a statistical dimension with average correlation $\gamma$ that is doubly exponential in $n$. However,this has a cross predictability of $\gamma^{2}/16$.

One could imagine a way to prove Thm 1 with prior SQ works as follows, (i) generalize the paper of [SVW15] that establishes a result similar to our Thm 1 for the special case of parities to the class of low cross-predictability functions, (ii) show that this class has the right notion of statistical dimension that is high. However, the distinction between low cross-predictability and high stat-dimensional would kick in at this point. If we take the example mentioned in the previous paragraph, the version of SGD used in Theorem 1 could learn to compute a function drawn from this distribution with expected accuracy $1/2+\sqrt{\gamma}/8$ given $O(1/\gamma)$ samples, so the statistical dimension of the distribution is not limiting its learnability by such algorithms in an obvious way. One might be able to argue that a low cross-predictability implies a high statistical dimension with a value of $\gamma$ that vanishes sufficiently quickly and then work from there. However, it is not clear exactly how one would do that, or why it would give a preferred approach.

Paper [FGV17] also shows that gradient-based algorithms with approximate oracle access are realizable as statistical query algorithms, however, [FGV17] makes a convexity assumption that is not satisfied by non-trivial neural nets. SQ lower bounds for learning with data generated by neural networks is also investigated in [SVWX17] and for neural network models with one hidden nonlinear activation layer in [VW18].

Finally, the current SQ framework does not apply to noisy SGD (even for adversarial noise). In fact, we believe that it is possible to learn parities with better noise-tolerance and complexity than any SQ algorithm will do — see further discussion below and in Sections 2.3 and 7.

Memory-sample trade-offs. In [Raz16], it is shown that one needs either quadratic memory or an exponential number of samples in order to learn parities, settling a conjecture from [SVW15]. This gives a non-trivial lower bound on the number of samples needed for a learning problem and a first complete negative result in this context, with applications to bounded-storage cryptography [Raz16]. Other works have extended the results of [Raz16]; in particular [KRT17] applies to k-sparse sources, [Raz17] to other functions than parities, and [GRT18] exploits properties of two-source extractors to obtain comparable memory v.s. sample complexity trade-offs, with similar results obtained in [BOY17]. The cross-predictability has also similarity with notions of almost orthogonal matrices used in $L_{2}$-extractors for two independent sources [CG88, GRT18].

In contrast to this line of works (i.e., [Raz16] and follow-up papers), our Theorem 1 specialized to the parity functions shows that one needs exponentially many samples to learn parities if less than $n/24$ pre-assigned bits of memory are used per sample. These are thus different models and results. Our result does not say anything interesting about our ability to learn parities with an algorithm that has free access to memory, while the result of [Raz16] says that it would need to have $\Omega(n^{2})$ total memory or an exponential number of samples. On the flip side, our result shows that an algorithm with unlimited amounts of memory will still be unable to learn a random parity function from a subexponential number of samples if there are sufficiently tight limits on how much it can edit the memory while looking at each sample. The latter is relevant to study SGD with bounded memory as discussed in this paper.

Note also that for the special case of parities, one could aim for Theorem 1 using [SVW15] with the following argument. If bounded-memory SGD could learn a random parity function with nontrivial accuracy, then we could run it a large number of times, check to see which iterations learned it reasonably successfully, and combine the outputs in order to compute the parity function with an accuracy that exceeded that allowed by Corollary 4 in [SVW15]. However, in order to obtain a generalization of this argument to low cross-predictability functions, one would need to address the points made previously regarding Theorem 1 and [SVW15] (point (i) and (ii)).

Gradient concentration. Finally, [SSS17], with an earlier version in [Sha18] from the first author, also give strong support to the impossibility of learning parities. In particular the latter discusses whether specific assumptions on the “niceness” of the input distribution or the target function (for example based on notions of smoothness, non-degeneracy, incoherence or random choice of parameters), are sufficient to guarantee learnability using gradient-based methods, and evidences are provided that neither class of assumptions alone is sufficient.

[SSS17] gives further theoretical insights and practical experiments on the failure of learning parities in such context. More specifically, it proves that the gradient of the loss function of a neural network will be essentially independent of the parity function used. This is achieved by a variant of our Lemma 2 below with the requirement in [SSS17] that the loss function is 1-LipschitzThe proofs are both simple but slightly different, in particular Lemma 2 does not make regularity assumptions.. This provides a strong intuition of why one should not be able to learn a random parity function using gradient descent or one of its variants, and this is backed up with theoretical and experimental evidence, bringing up the issue of the flat minima. However, it is not proved that one cannot learn parity using stochastic gradient descent or the like. The implication is far from trivial, as with the right algorithm, it is indeed possible to reconstruct the parity function from the gradients of the loss function on a list of random inputs. In fact, as mentioned above and further discussed in this paper, we believe that it is possible to learn a random parity function in polynomial time by using GD or SGD with a careful poly-time initialization of the net (that is of course also agnostic to the parity function). As we show further here, obtaining formal negative results requires more specific assumptions and elaborate proofs, already for GD and particularly for SGD.

Results

Before we can talk about the effectiveness of deep learning at learning parity functions, we have to establish some basic notions about deep learning. First of all, in this paper we will be using the following definition for a neural net.

Find an ordering $v^{\prime}_{1},...,v^{\prime}_{m}$ of the vertices in $G$ other than the constant vertex and input vertices such that for all $j>i$, there is not an edge from $v^{\prime}_{j}$ to $v^{\prime}_{i}$.

The gradient descent (GD) algorithm does the following. Its input includes the initial neural net, a learning rate, and the number of time steps the algorithm runs for. At each time step, the algorithm computes the derivative of the net’s expected loss with respect to each of its edge weights, and then decreases each edge weight by the derivative with respect to that weight times the learning rate. After the final time step, it returns the current neural net.

One problem with GD is that it requires computing an expectation over every possible input, which is generally impractical. One possible fix to that is to use stochastic gradient descent (SGD) instead of gradient descent. The input to SGD includes the initial neural net, a learning rate, and the number of time steps the algorithm runs for. However, instead of computing an expectation over all possible inputs in each time step, SGD randomly selects a single input in each time step, computes the derivative of the net’s loss at that input with respect to each edge weight, and decreases every edge weight by the corresponding derivative times the learning rate. Note that the stochasticity in SGD is sometimes also claimed to help with the generalization error of deep learning; with the insight that it helps with stability, implicit regularization or bad critical points [HRS16, ZBH+16, PP17, KLY18].

A third option is to use coordinate (or block-coordinate) descent (CD) instead of gradient descent. This works as SGD, except that in each time step CD only updates a small number of edge weights, with all other weights remaining fixed. There are multiple options for deciding which edge weights to change, some of which would base the decision on the chosen input, but our result involving CD will be generic and not depend on the details of how the edges are chosen.

It is also possible to use a noisy version of any of the algorithm mentioned above. This would be the same as the noise-free version, except that in each time step, the algorithm independently draws a noise term for each edge from some probability distribution and adds it to that edge’s weight. Adding noise can help avoid getting stuck in local minima or regions where the derivatives are small [GHJY15], however it can also drown out information provided by the gradient, and some learning algorithms are extremely sensitive to noise.

Finally, each of these algorithms needs to start with an initial set of weights before initiating the descent. A priori, the initialization could be done according to any rule, albeit with manageable complexity since we will focus in this paper on the efficiency of algorithms. However, in practice, SGD implementations in deep learning typically start with random initializations, see [SSBD14], or variants such as [HZRS15] that involve different types of probability distributions for the initial weights. Note that random initializations have also been shown to help with escaping certain bad extremal points [LSJR16].

We want to answer the question of whether or not training a neural net with these algorithms is a universal method of learning, in the sense that it can learn anything that is reasonably learnable. We next define exactly what this means.

Let $n>0$, $\epsilon>0$, $P_{\mathcal{X}}$ be a probability distribution on $\{0,1\}^{n}$, and $P_{\mathcal{F}}$ be a probability distribution on the set of functions from $\{0,1\}^{n}$ to $\{0,1\}$. Also, let $X_{0},X_{1},...$ be independently drawn from $P_{\mathcal{X}}$ and $F\sim P_{\mathcal{F}}$. An algorithm learns $(P_{\mathcal{F}},P_{\mathcal{X}})$ with accuracy $1/2+\epsilon$ if the following holds. There exists $T>0$ such that if the algorithm is given the value of $(X_{i},F(X_{i}))$ for each $i<T$ and it is given the value of $X_{T}$, it returns $Y_{T}$ such that $P[F(X_{T})=Y_{T}]\geq 1/2+\epsilon$.

In particular, we talk about “learning parities” in the case where $P_{\mathcal{F}}$ picks a parity function uniformly at random and $P_{\mathcal{X}}$ is uniform on $\{+1,-1\}^{n}$, as defined in Section 1.1.

For each $n>0$, letNote that these are formally sequences of distributions. $P_{\mathcal{X}}$ be a probability distribution on $\{0,1\}^{n}$, and $P_{\mathcal{F}}$ be a probability distribution on the set of functions from $\{0,1\}^{n}$ to $\{0,1\}$. We say that $(P_{\mathcal{F}},P_{\mathcal{X}})$ is efficiently learnable if there exists $\epsilon>0$, $N>0$, and an algorithm with running time polynomial in $n$ such that for all $n\geq N$, the algorithm learns $(P_{\mathcal{F}},P_{\mathcal{X}})$ with accuracy $1/2+\epsilon$.

2 Negative results

In order to disprove the universality of learning of these algorithms, we need an efficiently learnable function that they fail to learn. In this paper, we will use a random parity function with input that is uniformly distributed in $\{0,1\}^{n}$. One can easily learn such a function by taking a linear sized sample of its values on random inputs, finding a basis of $\{0,1\}^{n}$ in the inputs sampled, and then using the fact that these parity functions are linear. However, as we will show, some of the algorithms listed above are unable to learn such a function. The fundamental problem is that any two different parity functions are uncorrelated, so no function is significantly correlated with a nonnegligible fraction of them. As a result, the neural nets will generally fail to even come close enough to computing the desired function for the gradient to provide useful feedback on how to improve it. We will formalize this idea by defining a quantity called cross-predictability and showing that it is exponentially small for random parity functions. Similar negative results would hold for other families of functions with comparably low cross-predictability. The results in question are the following:

Coordinate descent with a polynomial number of steps and precision fails at learning parities with non-trivial accuracy.

Specializing previous theorem to the case of parities, one obtains the following. Let $\epsilon>0$. For each $n>0$, let $(f,g)$ be a neural net of polynomial size in $n$ such that each edge weight is recorded using $O(\log(n))$ bits of memory. Run stochastic gradient descent on $(f,g)$ with at most $2^{n/24}$ time steps and with $o(n/\log(n))$ edge weights updated per time step. For all sufficiently large $n$, this algorithm fails at learning parities with accuracy $1/2+\epsilon$.

As discussed in Section 1.6, one could obtain the special case of Theorem 1 for parities using [SVW15] with the following argument. If bounded-memory SGD could learn a random parity function with nontrivial accuracy, then we could run it a large number of times, check to see which iterations learned it reasonably successfully, and combine the outputs in order to compute the parity function with an accuracy that exceeded that allowed by Corollary 4 in [SVW15]. However, in order to obtain a generalization of this argument to low cross-predictability functions, one would need to address the points made in Section 1.6 regarding statistical dimension and cross-predictability.

For each $n>0$, let $(f,g)$ be a neural net of polynomial size in $n$. Run gradient descent on $(f,g)$ with less than $2^{n/10}$ time steps, a learning rate of at most $2^{n/10}$, Gaussian noise with variance at least $2^{-n/10}$ and overflow range of at most $2^{n/10}$. For all sufficiently large $n$, this algorithm fails at learning parities with accuracy $1/2+2^{-n/10}$.

See Section 1.6 for how the above compares to [Kea98]; in particular, an application of [Kea98] would not give the above exponents.

More generally, we have the following result that applies to low cross-predictability functions (and beyond some cases of large statistical dimension — see Section 1.6).

The polynomial deep learning system of previous corollary can weakly learn a random degree-$k$ monomial if and only if $k=O_{n}(1)$.

An overflow range of $B$ means that any value (e.g., derivatives of the loss function for a certain input) potentially exceeding $B$ (or $-B$) is kept at $B$ (or $-B$).

We could alternately have defined the algorithm such that if there is any input for which one of the derivatives is larger than the overflow range, we give up and return random predictions. In this case, the result above would still hold.

As a third option, we could define $\epsilon$ to be the probability that there is a time step in which the derivative of the loss function with respect to some edge weight is greater than the overflow range for some input. In this case, given that no such overflow occurs, the algorithm would fail to learn parities with accuracy $1/2+2^{-n/10}/(1-\epsilon)$.

Note that having GD run with a little noise is not equivalent to having noisy labels for which learning parities can be hard irrespective of the algorithm used [BKW03, Reg05]. The amount of noise needed for GD in the above theorem is exponentially small, and if such amount of noise were added to the sample labels themselves, then the noise would essentially be ineffective (e.g., Gaussian elimination would still work with rounding, or if the noise were Boolean with such variance, no flip would take place with high probability). The failure is thus due to the nature of the algorithm.

In the case of full gradient descent, the gradients of the losses with respect to different inputs mostly cancel out, so an exponentially small amount of noise is enough to drown out whatever is left. With stochastic gradient descent, that does not happen, and we have the following instead.

Let $(f,g)$ be a NN, and recall that $w(g)$ denotes the set of weights on the edges of $g$. Define the $\tau$-neighborhood of $(f,g)$ as

For each $n>0$, let $(f,g)$ be a neural net with size $m$ polynomial in $n$, and let $B,\gamma,T>0$ such that $B$, $1/\gamma$, and $T$ are polynomial in $n$. There exist $\sigma=O(m^{2}\gamma^{2}B^{2}/n^{2})$ and $\sigma^{\prime}=O(m^{3}\gamma^{3}B^{3}/n^{2})$ such that the following holds. Perturb the weight of every edge in the net by a Gaussian distribution of variance $\sigma$ and then train it with a noisy stochastic gradient descent algorithm with learning rate $\gamma$, $T$ time steps, and Gaussian noise with variance $\sigma^{\prime}$. Also, let $p$ be the probability that at some point in the algorithm, there is a neural net $(f,g^{\prime})$ in $N_{\tau}(f,g)$, $\tau=O(m^{2}\gamma B/n)$, such that at least one of the first three derivatives of the loss function on the current sample with respect to some edge weight(s) of $(f,g^{\prime})$ has absolute value greater than $B$. Then this algorithm fails to learn parities with an accuracy greater than $1/2+2p+O(Tm^{4}B^{2}\gamma^{2}/n)$.

Normally, we would expect that if training a neural net by means of SGD works, then the net will improve at a rate proportional to the learning rate, as long as the learning rate is small enough. As such, we would expect that the number of time steps needed to learn a function would be inversely proportional to the learning rate. This theorem shows that if we set $T=c/\gamma$ for any constant $c$ and slowly decrease $\gamma$, then the accuracy will approach $1/2+2p$ or less. If we also let $B$ slowly increase, we would expect that $p$ will go to , so the accuracy will go to $1/2$. It is also worth noting that as $\gamma$ decreases, the typical size of the noise terms will scale as $\gamma^{3/2}$. So, for sufficiently small values of $\gamma$, the noise terms that are added to edge weights will generally be much smaller than the signal terms.

The bound on the derivatives of the loss function is essentially a requirement that the behavior of the net be stable under small changes to the weights. It is necessary because otherwise one could effectively multiply the learning rate by an arbitrarily large factor simply by ensuring that the derivative is very large. Alternately, excessively large derivatives could cause the probability distribution of the edge weights to change in ways that disrupt our attempts to approximate this probability distribution using Gaussian distributions. For any given initial value of the neural net, and any given $M>0$, there must exists some $B$ such that as long as none of the edge weights become larger than $M$ this will always hold. However, that $B$ could be very large, especially if the net has many layers.

[MRT12] A class of function $\mathcal{F}$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(\textperiodcentered,\textperiodcentered,\textperiodcentered,\textperiodcentered)$ such that for any $\varepsilon>0$ and $\delta>0$, for all distributions $D$ on $\mathcal{X}$ and for any target function $f\in\mathcal{F}$, the following holds for any sample size $m\geq poly(1/\varepsilon,1/\delta,n,size(f))$:

If $A$ further runs in $poly(1/\varepsilon,1/\delta,n,size(f))$, then $\mathcal{F}$ is said to be efficiently PAC-learnable. When such an algorithm $A$ exists, it is called a PAC-learning algorithm for $\mathcal{F}$.

Deep learning algorithms as described in Theorems 1, 2, 4, fail at PAC-learning the class of parity functions $\mathcal{F}=\{p_{s}:s\subseteq[n]\}$ in poly$(n)$-time.

3 Necessary limitations of negative results

We show that deep learning fails at learning parities in polynomial time if the descent algorithm is either run with limited memory or initialized and run with enough randomness. However, if initialized carefully and run with enough memory and precision, we claim that it is in fact possible to learn parities:

One can construct in polynomial time in $n$ a neural net $(f,g)$ that has polynomial size in $n$ such that for a learning rate $\gamma$ that is at most polynomial in $n$ and an integer $T$ that is at most polynomial in $n$, $(f,g)$ trained by SGD with learning rate $\gamma$ and $T$ time steps learns parities with accuracy $1-o(1)$.

In fact, we claim that a more general result holds for any efficiently learnable distribution, and that deep learning can universally learn any such distribution (though the initialization will be unpractical) — Section 7. Full proofs will follow in subsequent versions of the paper.

Other functions that are difficult for deep learning

This paper focuses on the difficulty of learning parities, with proofs extending to other function/input distributions having comparably low cross-predictability. Parities are not the most common type of functions used to generate real signals, but they are central to the construction of good codes (in particular the most important class of codes, i.e., linear codes, that rely heavily on parities). We mention now a few additional examples of functions that we believe would be also difficult to learn with deep learning.

Arithmetic. First of all, consider trying to teach a neural net arithmetic. More precisely, consider trying to teach it the following function. The function takes as input a list of $n$ numbers that are written in base $n$ and are $n$ digits long, combined with a number that is $n+1$ digits long and has all but one digit replaced by question marks, where the remaining digit is not the first. Then, it returns whether or not the sum of the first $n$ numbers matches the remaining digit of the final number. So, it would essentially take expressions like the following, and check whether there is a way to replace the question marks with digits such that the expression is true.

We believe that if the input contained the entire alleged sum, then deep learning with a random initialization would also be unable to learn to determine whether or not the sum was correct. However, in order to train it, one would have to give it correct expressions far more often than would arise if it was given random inputs drawn from a probability distribution that was independent of the digits’ meanings. As such, our notion of cross predictability does not apply in this case, and the techniques we use in this paper do not work for the version where the entire alleged sum is provided. The techniques instead apply to the above version.

Connectivity and community detection. Another example of a problem that we believe deep learning would have trouble with consists of determining whether or not some graphs are connected. This could be difficult because it is a global property of the graph, and there is not necessarily any function of a small number of edges that is correlated with it. Of course, that depends on how the graphs are generated. In order to make it difficult, we define the following probability distribution for random graphs.

Given $n,m,r>0$, let $AER(n,m,r)$ be the probability distribution of $n$-vertex graphs generated by the following procedure. First of all, independently add an edge between each pair of vertices with probability $m/n$ (i.e., start with an Erdős-Rényi random graph). Then, randomly select a cycle of length less than $r$ and delete one of its edges at random. Repeat this until there are no longer any cycles of length less than $r$.

Now, we believe that deep learning with a random initialization will not be able to learn to distinguish a graph drawn from $AER(n,10\ln(n),\sqrt{\ln(n)})$ from a pair of graphs drawn from $AER(n/2,10\ln(n),\sqrt{\ln(n)})$, provided the vertices are randomly relabeled in the latter case. That is, deep learning will not distinguish between a patching of two such random graphs (on half of the vertices) versus a single such graph (on all vertices). Note that a simple depth-first search algorithm would learn the function in poly-time. More generally, we believe that deep learning would not solve community detection on such variants of random graph modelsIt would be interesting to investigate the approach of [CLB17] on such models. (with edges allowed between the clusters as in a stochastic block model with similar loop pruning), as connectivity v.s. disconnectivity is an extreme case of community detection.

The key issue is that no subgraph induced by fewer than $\sqrt{\ln(n)}$ vertices provides significant information on which of these cases apply. Generally, the function computed by a node in the net can be expressed as a linear combination of some expressions in small numbers of inputs and an expression that is independent of all small sets of inputs. The former cannot possibly be significantly correlated with the desired output, while the later will tend to be uncorrelated with any specified function with high probability. As such, we believe that the neural net would fail to have any nodes that were meaningfully correlated with the output, or any edges that would significantly alter its accuracy if their weights were changed. Thus, the net would have no clear way to improve.

Proof techniques

Our main approach to showing the failure of an algorithm (e.g., SGD) using data from a test model (e.g, parities) with limited resources (e.g., samples and memory) for a desired task (e.g., non-trivial accuracy of prediction), will be to establish an indistinguishable to null condition (INC), namely, a condition on the resources that implies failure to statistically distinguish the trace of the algorithm on the test model from a null model, where the null model fails to provide the desired performance for trivial reasons. The INC is obtained by manipulating information measures, bounding the total variation distance of the two posterior measures between the test and null models. The failure of achieving the desired algorithmic performance on the test model is then a consequence of the INC, either by converse arguments – if one could achieve the claimed performance, one would be able to use the performance gap to distinguish the null and test models and thus contradict the INC – or directly using the total variation distance between the two probability distributions to bound the difference in the probabilities that the nets drawn from those distributions compute the function correctly (and we know that it fails to do so on the null model).

Let $D_{1}$ be the distribution of the data for the parity learning model, i.e., i.i.d. samples with labels from the parity model in dimension $n$;

Let $R=(R_{1},R_{2})$ be the resource in question, i.e., the number $R_{1}$ of edge weights of poly$(n)$ memory that are updated and the number of steps $R_{2}$ of the algorithm;

Let $A$ be the SGD (or coordinate descent) algorithm used with a constraint $C$ on the resource $R$;

Let $T$ be the task, i.e, achieving an accuracy of $1/2+\Omega_{n}(1)$ on a random input.

Chose $D_{0}$ as the null distribution that generates i.i.d. pure noise labels, such that the task $T$ is obviously not achievable for $D_{0}$.

Find a INC on $R$, i.e., a constraint $C$ on $R$ such that the trace of the algorithm $A$ is indistinguishable under $D_{1}$ and $D_{0}$; to show this,

show that the total variation distance between the posterior distribution of the trace of $A$ under $D_{0}$ and $D_{1}$ vanishes if the INC holds; to obtain this,

show that any $f$-mutual information between the algorithm’s trace and the model hypotheses $D_{0}$ or $D_{1}$ (chosen equiprobably) vanishes.

Most of the work then lies in part 2(a)-(b), which consist in manipulating information measures to obtain the desired conclusion. In particular, the Chi-squared mutual information will be convenient for us, as its “quadratic” form will allow us to bring the cross-predictability as an upper-bound, which is then easy to evaluate and is small for the parity model. This is carried out in Section 5 in the general context of so-called “sequential learning algorithms”, and then applied to SGD with bounded memory (or coordinate descent) in Section 2. For Theorem 2, one needs also to take into account the fact that information can be carried in the pattern of which weights can be updated, and these are taken into account with a proper SLA implementation, with Theorem 2 concluding from a contradiction argument as discussed in step 3. above.

Cross-predictability and sequential learning

We denote by $\mathcal{X}$ the domain of the data (e.g., Boolean vectors, matrices of pixels) and by $\mathcal{Y}$ the domain of the labels; for simplicity, we assume that $\mathcal{Y}=\{-1,+1\}$. A hypothesis is a function $f:\mathcal{X}\to\mathcal{Y}$ that labels data points in $\mathcal{X}$ with elements in $\mathcal{Y}$. We define $\mathcal{F}:=\mathcal{Y}^{\mathcal{X}}$.

Let $P_{\mathcal{X}}$ be a probability measure on $\mathcal{X}$, and $P_{\mathcal{F}}$ be a probability measure on $\mathcal{F}$ (the set of functions from $\mathcal{X}$ to $\mathcal{Y}$). Define the cross-predictability of $P_{\mathcal{F}}$ with respect to $P_{\mathcal{X}}$ by

Therefore a low cross-predictability can be interpreted as having a low correlation between two sampled functions on a sampled input, or, as a low correlation between two sampled input on a sampled function. This suggests that two samples - such as those of two consecutive steps of SGD - may not have common information about a typical function being learned.

We discuss in Remark LABEL:sq_disc the analogy and difference between the cross-predictability and the statistical dimension. We next cover some examples.

Note that uniformly random parity functions have the same cross-predictability as uniformly random generic functions, with respect to uniform inputs. We will crucially exploit this property to prove the forthcoming results. We obtain in fact generalizations of two our results to other function distributions having cross-predictability that scales super-polynomially.

2 Learning from a bit

That is, a random input $X$ and a random hypothesis $F$ are drawn from the working model, leading to an output label $Y$. We store a bit $W$ after observing the labelled pair $(X,Y)$. We are interested in estimating how much information can this bit contain about $F$, no matter how “good” the function $g$ is. We start by measuring the information using the variance of the MSE or Chi-squared mutual informationThe Chi-squared mutual information should normalize this expression with respect to the variance of $W$ for non equiprobable random variables., i.e.,

which gives a measure on how random $W$ is given $F$. We provide below a bound in terms of the cross-predictability of $P_{\mathcal{F}}$ with respect to $P_{\mathcal{X}}$, and the marginal probability that $g$ takes value 1 on two independent inputs, which is a “inherent bias” of $g$.

The Chi-squared is convenient to analyze and is stronger than the classical mutual information, which is itself stronger than the squared total-variation distance by Pinsker’s inequality. More preciselySee for example [AB18] for details on these inequalities., for an equiprobable $W$,

Here we will need to obtain such inequalities for arbitrary marginal distributions of $W$ and in a self-contain series of lemmas. We then bound the latter with the cross-predictability which allows us to bound the error probability of the hypothesis test deciding whether $W$ is dependent on $F$ or not, which we later use in a more general framework where $W$ relates to the updated weights of the descent algorithm. We will next derive the bounds that are needed.These bounds could be slightly tightened but are largely sufficient for our purpose.

Consider now the new setup where $g$ is valued in $[m]$ instead of $\{0,1\}$:

We next specialize the bound in Theorem 4 to the case of uniform parity functions on uniform inputs, adding a bound on the $L_{1}$ norm due to Cauchy-Schwarz.

In short, the value of $W$ will not provide significant amounts of information on $F$ unless its number of possible values $m$ is exponentially large.

In the case where $P_{\mathcal{F}}=P_{n}$, taking the previous corollary and multiplying both sides by $2^{2n}$ yields

Notice that for fixed values of $P_{\mathcal{X}}$ and $g$, changing the value of $P_{\mathcal{F}}$ does not change the value of $P[W=i|f=p_{s}]$ for any $i$ and $s$. Therefore, inequality (54) holds for any choice of $P_{\mathcal{F}}$, and we also have the following.

3 Sequential learning algorithm

Next, we would like to analyze the effectiveness of an algorithm that repeatedly receives an ordered pair, $(X,F(X))$, records some amount of information about that pair, and then forgets it. To formalize this concept, we define the following.

A sequential learning algorithm $A$ on $(\mathcal{Z},\mathcal{W})$ is an algorithm that for an input of the form $(Z,(W_{1},...,W_{t-1}))$ in $\mathcal{Z}\times\mathcal{W}^{t-1}$ produces an output $A(Z,(W_{1},...,W_{t-1}))$ valued in $\mathcal{W}$. Given a probability distribution $D$ on $\mathcal{Z}$, a sequential learning algorithm $A$ on $(\mathcal{Z},\mathcal{W})$, and $T\geq 1$, a $T$-trace of $A$ for $D$ is a series of pairs $((Z_{1},W_{1}),...,(Z_{T},W_{T}))$ such that for each $i\in[T]$, $Z_{i}\sim D$ independently of $(Z_{1},Z_{2},...,Z_{i-1})$ and $W_{i}=A(Z_{i},(W_{1},W_{2},...,W_{i-1}))$.

and we will bound the last term by $O(q)$.

We need to prove that $P[W^{m}=w^{m}|P_{\mathcal{Z}}=\rho_{f}]\approx P[W^{m}=w^{m}|P_{\mathcal{Z}}=\star]$ most of the time. In order to do that, we will use the fact that

So, as long as $P[W_{i}=w_{i}|W^{i-1}=w^{i-1},P_{\mathcal{Z}}=\rho_{f}]\approx P[W_{i}=w_{i}|W^{i-1}=w^{i-1},P_{\mathcal{Z}}=\star]$ and $P[W_{i}=w_{i}|W^{i-1}=w^{i-1},P_{\mathcal{Z}}=\star]$ is reasonably large for all $i$, this must hold for the values of $w^{m}$ and $f$ in question. As such, we plan to define a good value for $(w^{m},f)$ to be one for which this holds, and then prove that the set of good values has high probability measure.

First, call a sequence $w^{m}\in\mathcal{W}^{m}$ typical if for each $1\leq i\leq m$, we have that

and denote by $\mathcal{T}$ the set of typical sequences

and denote by $\mathcal{G}$ the set of good pairs. A pair which is not good is called bad.

Note that for any $i$ and any $w_{1},...,w_{i-1}\in\mathcal{W}$, there exists a function $g_{w_{1},...,w_{i-1}}$ such that $W_{i}=g_{w_{1},...,w_{i-1}}(Z_{i})$. So, theorem 5 implies that

This means that for a given typical $w^{m}$, the probability that $w^{m}$ and $F^{\prime}$ are not good is at most $mq^{2}\leq q$.

Therefore, if $P_{\mathcal{Z}}=\star$, the probability that $W^{m}$ is typical but $W^{m}$ and $F^{\prime}$ is not good is at most $q$; in fact:

We already knew that $W^{m}$ is typical with probability $1-q$ under these circumstances, so $W^{m}$ and $S$ is good with probability at least $1-2q$ since

So, if $w^{m}$ and $f$ is good (and thus each term in the above product is within $q^{2}$ of 1), we have

Now, let $A^{\prime}$ be the algorithm that takes $(Z_{t},(W^{\prime}_{1},...,W^{\prime}_{t-1}))$ as input and does the following. First, it reconstructs $W_{t-1}$ from $(W^{\prime}_{1},...,W^{\prime}_{t-1})$. Then, it computes $W_{t}$ by running $A$ on $W_{t-1}$ and $Z_{t}$. Finally, it determines the value of $W^{\prime}_{t}$ by comparing $W_{t}$ to $W_{t-1}$ and returns it. This is an SLA, and $((Z_{1},W^{\prime}_{1}),...,(Z_{m},W^{\prime}_{m}))$ is an $m$-trace of $A^{\prime}$ for $P_{\mathcal{Z}}$. So, by the theorem

Furthermore, since $W_{m}$ can be reconstructed from $(W^{\prime}_{1},...,W^{\prime}_{m})$, this implies that

Finally, the probability of deciding correctly between the hypothesis $P_{\mathcal{Z}}=\star$ and $P_{\mathcal{Z}}\neq\star$ given the observation $W_{m}$ is at most

The theorem and its second corollary state that the algorithm can not determine whether or not $P_{\mathcal{Z}}=\star$. However, one could easily transform them into results showing that the algorithm can not effectively learn to compute $f$. More precisely, after running on $q/2$ pairs $(x,p_{f}(x))$, the algorithm will not be able to compute $p_{s}(x)$ with accuracy $1/2+\omega(1/\sqrt{q})$ with a probability of $\omega(1/q)$. If it could, then we could just train it on the first $m/2$ of the $Z_{i}$ and count how many of the next $m/2$ $Z_{i}$ it predicts the last bit of correctly. If $P_{\mathcal{Z}}=\star$, each of those predictions will be independently correct with probability $1/2$, so the total number it is right on will differ from $m/4$ by $O(\sqrt{m})$ with high probability. However, if $P_{\mathcal{Z}}=\rho_{f}$ and the algorithm learns to compute $\rho_{f}$ with accuracy $1/2+\omega(1/\sqrt{q})$, then it will predict $m/4+\omega(\sqrt{m})$ of the last $m/2$ correctly with high probability. So, we could determine whether or not $P_{\mathcal{Z}}=\star$ with greater accuracy than the theorem allows by tracking the accuracy of the algorithm’s predictions.

Negative results for deep learning

Before we can talk about the effectiveness of deep learning at learning these parity functions, we will have to establish some basic information about deep learning. First of all, in this paper we will be using the following definition for a neural net.

Find an ordering $v^{\prime}_{1},...,v^{\prime}_{m}$ of the vertices in $G$ other than the constant vertex and input vertices such that for all $j>i$, there is not an edge from $v^{\prime}_{j}$ to $v^{\prime}_{i}$.

We will write the evaluation of $(f,G)$ at $x$ as $eval_{(f,G)}(x)$.

Generally, we want to find a neural net that computes a certain function, or at least a good approximation of that function. A reasonable approach to doing that is to start with some neural network and then attempt to adjust its weights until it computes a reasonable approximation of the desired function. A common way to do that is to define a loss function in terms of how much the network’s outputs differ from the desired outputs, and then use gradient descent to try to adjust the weights. Of course, that may not be well defined if $f$ is not differentiable, it may not be possible to find weights for which the network approximates the desired function if it has too few vertices or is missing some key edges, and the gradient descent algorithm has an increased risk of getting stuck in a local minimum if $f$ has local minima. Allowing the loss function or the derivative of $f$ to take on arbitrarily large values under some circumstances can also cause problems, which can be mitigated by redefining our function to have input in $^{n}$ and output in $$and then using an$f$with output in$$. We would also like to ensure that$f$ can take on values arbitrarily close to any desired output in that range. As such, we give the following criteria for a neural net to be considered well behaved.

Let $(f,G)$ be a neural net. Then $(f,G)$ is normal if it satisifes the following properties. $f$ must be a a smooth function, the derivative of $f$ must be positive everywhere, the derivative of $f$ must be bounded, it must be the case that $\lim_{x\to-\infty}f(x)=0$ and $\lim_{x\to\infty}f(x)=1$, and $G$ must have an edge from the constant vertex to every other vertex except the input vertices.

In order to do that, we could try starting with some neural net $(f,G_{0})$, and then using the following algorithm to assign new weights to the graph’s edges.

GradientDescentStep(f, G, h, $P_{\mathcal{X}}$, L, $\gamma$, B):

If $w^{\prime}_{v,v^{\prime}}<-B$, set $w^{\prime}_{v,v^{\prime}}=-B$.

If $w^{\prime}_{v,v^{\prime}}>B$, set $w^{\prime}_{v,v^{\prime}}=B$.

Return the graph that is identical to $G$ except that its edge weight are given by the $w^{\prime}$.

GradientDescentAlgorithm(f, G, h, $P_{\mathcal{X}}$, L, $\gamma$, B, t):

If any of the edge weights in $G_{0}$ are less than $-B$, set all such weights to $-B$.

If any of the edge weights in $G_{0}$ are greater than $B$, set all such weights to $B$.

For each $0\leq i<t$, set $G_{i+1}=GradientDescentStep(f,G_{i},h,P_{\mathcal{X}},L,\gamma,B)$.

The hope is that if we set $G^{\prime}=GradientDescentAlgorithm(f,G,h,P_{\mathcal{X}},L,\gamma,B,t)$ for a small enough $\gamma$ and large enough $t$ then $eval_{(f,G^{\prime})}$ will be a good approximation of $h$. Of course, actually running this algorithm requires us to compute $eval_{(f,G)}(X)$ for every possible value of $X$ in every step, which is generally impractical. As a result, we are more likely to pick a single value of $X$ at each step, and adjust the net to give a better output on that input. More formally, we would use the following algorithm.

SampleGradientDescentStep(f, G, $Y$, $X$, L, $\gamma$, B):

If $w^{\prime}_{v,v^{\prime}}<-B$, set $w^{\prime}_{v,v^{\prime}}=-B$.

If $w^{\prime}_{v,v^{\prime}}>B$, set $w^{\prime}_{v,v^{\prime}}=B$.

Return the graph that is identical to $G$ except that its edge weights are given by the $w^{\prime}$.

StochasticGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, B, t):

If any of the edge weights in $G_{0}$ are less than $-B$, set all such weights to $-B$.

If any of the edge weights in $G_{0}$ are greater than $B$, set all such weights to $B$.

Draw $(X_{i},Y_{i})\sim P_{\mathcal{Z}}$, independently of all previous values.

Set $G_{i+1}=SampleGradientDescentStep(f,G_{i},Y_{i},X_{i},L,\gamma,B)$

2 Proof of Theorem 1

One possible variant of this is to only adjust a few weights at each time step, such as the $k$ that would change the most or a random subset. However, any such algorithm cannot learn a random parity function in the following sense.

This follows immediately from corollary 8. ∎

The theorem state that one cannot determine whether or not $P_{\mathcal{Z}}=\star$ from the final network. However, if we used a variant of corollary 8 we could get a result showing that the final network will not compute $p_{s}$ accurately. More precisely, after training the network on $2^{n/24-1}$ pairs $(x,p_{s}(x))$, the network will not be able to compute $p_{s}(x)$ with accuracy $1/2+\omega(2^{-n/48})$ with a probability of $\omega(2^{-n/24})$.

We can also use this reasoning to prove theorem 1, which is restated below.

3 Proof of Theorem 2

Before we talk about the effectiveness of noisy gradient descent, we need to formally define it. So, we define the following.

NoisyGradientDescentStep(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\delta$):

Return the graph that is identical to $G$ except that its edge weights are given by $w^{\prime}$.

NoisyGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\Delta$, t):

Generate $\delta^{(i)}$ by independently drawing $\delta^{(i)}_{v,v^{\prime}}$ from $\Delta$ for each $(v,v^{\prime})\in E(G)$.

Set $G_{i+1}=NoisyGradientDescentStep(f,G_{i},h,P_{\mathcal{Z}},L,\gamma,\delta^{(i)})$.

The case where one of the derivatives is very large causes enough problems that it is convenient to define versions of the algorithms that treat the derivative of the loss function with respect to a given edge weight on a given input as having some maximum value if it is actually larger. Then we can prove results for these algorithms, and argue that if none of the derivatives are that large using the normal versions must yield the same result. As such, we define the following:

BoundedNoisyGradientDescentStep(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\delta$, $B$):

Return the graph that is identical to $G$ except that its edge weights are given by $w^{\prime}$.

BoundedNoisyGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\Delta$, $B$, t):

Generate $\delta^{(i)}$ by independently drawing $\delta^{(i)}_{v,v^{\prime}}$ from $\Delta$ for each $(v,v^{\prime})\in E(G)$.

Set $G_{i+1}=BoundedNoisyGradientDescentStep(f,G_{i},h,P_{\mathcal{Z}},L,\gamma,\delta^{(i)},B)$.

In order to prove that noisy gradient descent fails to learn a random parity function, we first show that the gradient will be very small, and then argue that the noise will drown it out. The first steps are the following basic inequalities.

where we note that the equality from (94) to (97) is Parserval’s identity for the Fourier-Walsh basis (here we used Boolean outputs for the parity functions). ∎

Note that by the triangular inequality the above implies

As mentioned earlier, this is similar to Theorem 1 in [SSS17] that requires in addition the function to be the gradient of a 1-Lipschitz loss function.

We also mention the following corollary of Lemma 2 that results from Cauchy-Schwarz.

In other words, the expected value of any function on an input generated by a random parity function is approximately the same as the expected value of the function on a true random input. This in turn implies the following:

where the second to last inequality follows by applying the previous lemma to the formula in BoundedNoisyGradientDescentStep for the changes in edge weight. Next, observe that $Q_{\star}$ is a Gaussian distribution with mean $w^{(\star)}$ and covariance $\sigma^{2}I$. Similarly, $Q_{s}$ is a Gaussian distribution with mean $w^{(s)}$ and covariance $\sigma^{2}I$ for each $s$. As such,

Clearly, $Q_{s}^{(0)}=Q_{\star}^{(0)}$ for all $s$. Now, for each $s\subseteq[n]$ and $t>0$, let $Q_{\star s}^{(t)}$ be the probability distribution of the output of BoundedNoisyGradientDescentStep(f, $G^{\prime}_{t}$, $\rho_{s}$, L, $\gamma$, $\mathcal{N}(0,\sigma^{2}I)$, $B$), where $G^{\prime}_{t}\sim Q_{\star}^{(t-1)}$. Next, observe that $Q_{\star}^{(t)}$ is the probability distribution of the output of BoundedNoisyGradientDescentStep(f, $G^{\prime}_{t}$, $\star$, L, $\gamma$, $\mathcal{N}(0,\sigma^{2}I)$, $B$). So, by the previous lemma,

Also, for each $s$ and $t$, $Q_{s}^{(t)}$ is the probability distribution of the output of BoundedNoisyGradientDescentStep(f, $G^{\prime\prime}_{t}$, $\rho_{s}$, L, $\gamma$, $\mathcal{N}(0,\sigma^{2}I)$, $B$), where $G^{\prime\prime}_{t}\sim Q_{s}^{(t-1)}$. So, $||Q_{\star s}^{(t)}-Q_{s}^{(t)}||_{1}\leq||Q_{\star}^{(t-1)}-Q_{s}^{(t-1)}||_{1}$. Thus,

by the triangle inequality. The desired result follows by induction. ∎

This in turn implies the following elaboration of Theorem 2.

Let $Q_{\star}$ be the probability distribution of the output of BoundedNoisyGradientDescentAlgorithm(f, g, $\star$, L, $\gamma$, $\mathcal{N}(0,\sigma^{2}I)$, B, T) and $Q_{s}$ be the probability distribution of the output of BoundedNoisyGradientDescentAlgorithm(f, g, $\rho_{s}$, L, $\gamma$,$\mathcal{N}(0,\sigma^{2}I)$, B, T) for each $s\subseteq[n]$. By the previous corollary, we know that

Dividing both sides by $2^{2n}$ yields the desired conclusion. ∎

4 Proof of Theorem 3

We prove here an elaboration of Theorem 3.

For each $n>0$, take a neural net of size $|E|$, with any differentiable non-linearity and any initialization of the weights $W^{(0)}$, and train it with gradient descent with learning rate $\gamma$, any differentiable loss function, gradients computed on the population distribution $P_{\mathcal{X}}$ with labels from $F$, an overflow range of $A$, additive Gaussian noise of variance $\sigma^{2}$, and $S$ steps, i.e.,

where $\{Z^{(t)}\}_{t\in[S]}$ are i.i.d. $\mathcal{N}(0,\sigma^{2})$. Then,

Note that this theorem uses the BoundedNoisyGradientDescentAlgorithm, we simply re-wrote it to make the statement self-contained, using $W^{(t)}(X)$ as the evaluation of the neural net with weights $W^{(t)}$ on an input $X$.

For $t=1,\dots,S$ and $H\in\{F,\star\}$, define

and let $Q_{H}^{(t)}$ be the distribution of $W_{H}^{(t)}$.

where $P_{e}(\rho_{F},\rho_{\star})$ is the probability of error of the optimal (MAP) test for the hypothesis test between $\rho_{F}$ and $\star$ with equiprobable priors, i.e.,

Using Cauchy-Schwarz and previous inequality, we have

where $Z:=(X,Y)\sim P_{\mathcal{Z}}:=P_{\mathcal{X}}\times U_{\mathcal{Y}}$, $g(Z):=\psi_{u,v}(X,Y)$, and $h_{F}(Z)=1$ if $F(X)\neq Y$ and $h_{F}(Z)=-1$ otherwise. Therefore,

Multi-step bound. We now proceed with a cumulative argument. For $t\in[S+1]$ $H,h\in\{F,\star\}$, define

and denote by $Q^{(t-1)}_{H,h}$ the distribution of $W_{H,h}^{(t-1)}$.

Using the triangular and Data-Processing inequalities, we have

Indistinguishability. Finally, by the definition of the total variation distance,

5 Proof of Theorem 4

NoisySampleGradientDescentStep(f, G, $Y$, $X$, L, $\gamma$, B, $\delta$):

If $w^{\prime}_{v,v^{\prime}}<-B$, set $w^{\prime}_{v,v^{\prime}}=-B$.

If $w^{\prime}_{v,v^{\prime}}>B$, set $w^{\prime}_{v,v^{\prime}}=B$.

Return the graph that is identical to $G$ except that its edge weight are given by the $w^{\prime}$.

NoisyStochasticGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, B, $\Delta$, t):

If any of the edge weights in $G_{0}$ are less than $-B$, set all such weights to $-B$.

If any of the edge weights in $G_{0}$ are greater than $B$, set all such weights to $B$.

Draw $(X_{i},Y_{i})\sim P_{\mathcal{Z}}$, independently of all previous values.

Generate $\delta^{(i)}$ by independently drawing $\delta^{(i)}_{v,v^{\prime}}$ from $\Delta$ for each $(v,v^{\prime})\in E(G)$.

Set $G_{i+1}=NoisySampleGradientDescentStep(f,G_{i},Y_{i},X_{i},L,\gamma,B,\delta)$

The simplest way to add noise in order to impede learning a parity function would be to add noise drawn from a uniform distribution in order to drown out the information provided by the changes in edge weights. More precisely, consider setting $\Delta$ equal to the uniform distribution on $[-C,C]$. If the change in each edge weight prior to including the noise always has an absolute value less than $D$ for some $D<C$, then with probability $\frac{C-D}{C}$, the change in a given edge weight including noise will be in $[-(C-D),C-D]$. Furthermore, any value in this range is equally likely to occur regardless of what the change in weight was prior to the noise term, which means that the edge’s new weight provides no information on the sample used in that step. If $D/C=o(nE(G)/\ln(n))$ then this will result in there being $o(n/\log(n))$ changes in weight that provide any relevant information in each timestep. So, the resulting algorithm will not be able to learn the parity function by an extension of corollary 8. This leads to the following result:

This is a side result and we provide a concise proof.

Consider the following attempt to simulate NoisyStochasticGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\infty$, $\Delta$, t) with a sequential learning algorithm. First, independently draw $b^{t^{\prime}}_{v,v^{\prime}}$ from the uniform probability distribution on $[-D|E(G)|+D,D|E(G)|-D]$ for each $(v,v^{\prime})\in E(G)$ and $t^{\prime}\leq t$. Next, simulate NoisyStochasticGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\infty$, $\Delta$, t) with the following modifications. If there is ever a step where one of the adjustments to the weights before the noise term is added in is greater than $D$, record “failure” and give up. If there is ever a step where more than $n/\ln^{2}(n)$ of the weights change by more than $D|E(G)|-D$ after including the noise record ”failure” and give up. Otherwise, record a list of which weights changed by more than $D|E(G)|-D$ and exactly what they changed by. In all subsequent steps, assume that $W_{v,v^{\prime}}$ increased by $b^{t^{\prime}}_{v,v^{\prime}}$ in step $t^{\prime}$ unless the amount it changed by in that step is recorded.

First, note that if the values of $b$ are computed in advance, the rest of this algorithm is a sequential learning algorithm that records $O(n/\log(n))$ bits of information per step and runs for a subexponential number of steps. As such, any attempt to compute $p_{S}(X)$ based on the information provided by its records will have accuracy $1/2+o(1)$ with probability $1-o(1)$. Next, observe that in a given step in which all of the adjustments to weights before the noise is added in are at most $D$, each weight has a probability of changing by more than $D|E(G)|-D$ of at most $1/|E(G)|$ and these probabilities are independent. As such, with probability $1-o(1)$, the algorithm will not record ”failure” as a result of more than $n/\ln^{2}(n)$ of the weights changing by more than $D|E(G)|-D$. Furthermore, the probability distribution of the change in the weight of a given vertex conditioned on the assumption that said change is at most $D|E(G)|-D$ and a fixed value of said change prior to the inclusion of the noise term that has an absolute value of at most $D$ is the uniform probability distribution on $[-D|E(G)|+D,D|E(G)|-D]$. As such, substituting the values of $b^{t^{\prime}}_{v,v^{\prime}}$ for the actual changes in weights that change by less than $D|E(G)|-D$ has no effect on the probability distribution of the resulting graph. As such, the probability distribution of the network resulting from NoisyStochasticGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\infty$, $\Delta$, t) if none of the weights change by more than $D$ before noise is factored in differs from the probabiliy distribution of the network generated by this algorithm if it suceeds by $o(1)$. Thus, the fact that the SLA cannot generate a network that computed $p_{S}$ with nontrivial accuracy implies that NoisyStochasticGradientDescentAlgorithm(f, G, $P_{\mathcal{Z}}$, L, $\gamma$, $\infty$, $\Delta$, t) also fails to generate a network that computes $p_{S}$ with nontrivial accuracy. ∎