# When does deep learning fail?

Deep learning is an increasingly hot topic nowadays.

What are the main assumptions that render deep learning lacking in some data sets. Ex: Does it perform well on noisy data sets ?

One can generally think of two types of hardness results in machine learning: Information theoretic hardness in the context of statistical learning (namely, giving a lower bound to the minimal number of examples required to learn) and algorithmic hardness (i.e, a bad algorithmic choice means that the optimization becomes impossible).

In the context of deep learning, discussing hardness is tricky, since we actually know very little in terms of why theoretically deep learning works. (Recall: The optimization problem solved in deep learning is that of minimizing a high dimensional highly non convex function, and is known to be NP-hard in general. i.e, there are no guarantees w.r.t reaching the global minimum. And yet in practice, practitioners have used variants of SGD to solve many problems very well. There have been some recent advances in giving a justifiable answer as to why this is so, but this is outside the scope of your question.)

One very nice example for algorithmic hardness in deep learning is for trying to learn problems in which the gradient is non-informative. Deep learning currently uses some form of SGD to update the weights of the network. for example, mini-batches GD computes the gradient of the cost function over a random sample of $b$ examples w.r.t. to the parameters $\theta$ :

$\theta_{t+1} = \theta_t - \alpha_t \cdot \nabla_\theta J(\theta; x^{(i:i+b)},y^{(i:i+b)})$

In other words, DL optimization is trying to globally optimize a function by using local gradient information; This suggest that if a learning problem is characterized by non-informative gradients, then no deep learning architecture will be able to learn it.

Learning random parities is the following learning problem:

After choosing a vector $\boldsymbol{v^*} > \in \left\{ 0,1\right\}^d$, the goal is to train a predictor mapping $\boldsymbol{x\in}\left\{ 0,1\right\} ^{d}$ to $y=\left(-1\right)^{\left\langle \boldsymbol{x,v^{*}}\right\rangle }$, where $\boldsymbol{x}$ is uniformly distributed. In other words, we're trying to learn a mapping that determines if the number of 1's in a certain subset of coordinates of $\boldsymbol{x}$ (indicated by $\boldsymbol{v^*}$) is even or odd.

In "Failures of Gradient-Based Deep Learning" (Shamir, 2017) the authors prove that the this problem (and more generally, every linear function composed with a periodic one) suffers from non-informative gradients, thus rendering the optimization problem as difficult.

They also demonstrate this empirically, by measuring the accuracy as a function of the number of training iterations, for various input dimensions.

The network used here is one fully connected layer of width $10d$ with ReLU activations, and a fully connected output layer with linear activation and a single unit. (The width is chosen as to ensure that the required parity function is indeed realized by such a network)

Q: Why is it that learning parity only becomes difficult at around $d=30$?

It fails when you don't impose the right structure on the problem. Convolutional neural networks work because they assume pixels which are close to each other are related, so it makes sense to apply spatial convolutions to your features. And in so doing, you've reduced the hypothesis search space dramatically, which means deep learning is more likely to arrive at an optimal solution.

If you apply deep learning to a problem where the features aren't amenable to spatial/temporal convolutions, then deep learning will fail, because it doesn't make sense to be summing up certain features and applying functions to the summation, which is what neural networks do.

If someone can think of an example of where deep learning has been successfully applied to data which is not images or audio (or spatial/temporal data), I would be delighted to retract this answer.