18
$\begingroup$

In a nutshell

Has consistency been studied for any of the 'typical' deep learning models used in practice, i.e. neural networks with multiple hidden layers, trained with stochastic gradient descent? If so, what have been the findings?

There seems to be some confusion as to why I mention optimization procedures in connection with consistency. Consistency is a property of estimators, and while we are free to choose any estimator, I chose to restrict the question to estimators that we can actually calculate. Hence the necessity to specify an algorithm.

I would also like to point out that universal approximation theorems (UATs) typically only show that neural networks as a function class are rich enough to model certain kinds on nonlinear relationships, and those I know of do not deal with calculable estimators. Hence some motivation for my question: UATs, even those with specific error bounds, give no guarantees as to the performance of real-world neural nets.

The details

A consistent estimator converges in probability to its true value if the sample size grows to infinity. We can apply this concept to nonparametric models like (regression) neural networks:

Let the DGP be

$$ \mathbb{E}[y] = f(x) + \varepsilon $$

and we assume that $f\in\mathcal{F}$ for some function class $\mathcal{F}$.

We train the neural network with some algorithm $A_n:(X,Y)^n\rightarrow\mathcal{F'_n}$ such that

$$ f_n = A_n((x_1,y_1),\dots,(x_n,y_n)) $$

is our trained network for dataset size $n$.

Then a neural network would be consistent for $\mathcal{F}$ if

$$ \lim_{n\rightarrow\infty} \mathbb{P}[\|f_n-f\| >\delta] = 0 $$

for all $\delta>0$.

Does there exist a neural network that is consistent in this sense?

[Edit 3] What kind of network? Which $\mathcal{F}$? Which norm?

To say that 'Neural networks' is a broad class is an understatement, pretty much every model can be represented as a neural network. There are a number of specifications however which do not have other representations (yet), namely the 'typical' neural network:

  • trained with a variation of stochastic gradient descent
  • more than 1 hidden layer
  • ridge activation function: $x\mapsto u(a'x+b)$ for some univariate function $u$ (this includes ReLU and its variations, sigmoid and its variations) or pooling activation function
  • dense/convolutional/recurrent or a combination thereof

Any of these 'typical' networks is fine. Another way to view the question would be: "If I want to choose my network architecture such that my network is a consistent estimator, what would be a valid choice?".

With regards to $\mathcal{F}$ I have even less restrictions. It should not be a finite-dimensional space (e.g. polynomials with some finite order), that would be cheating. Beyond that, whatever is necessary to get consistency. Beppo Levi, $C^k$, Hilbert, Sobolev, pick your favorite. Compact support is fine of course, although not necessary.

Finally, while I realize that not all norms are equivalent on infinite-dimensional spaces such as $\mathcal{F}$, I am happy with convergence in probability under any norm. After all, it depends on $\mathcal{F}$ which norms even make sense.

Edit

When I say that neural networks are nonparametric models, I mean that we should let the size of the network depend on the size of the dataset. If we do not do this, it is quite obvious that neural networks are inconsistent because networks of fixed size have irreducible approximation errors - no network with ReLU or sigmoid activation can represent $e^x$ exactly, for example.

[Edit 2] Why is this relevant?

Neural networks have a reputation for being "very good at very complex tasks". It seems to me this reputation stems from some high-profile achievements in image classification, language processing and (video)game playing. Without question, neural networks have been able to distill meaningful signals from the very high-dimensional input spaces these problems have. At the same time, neural networks have been found to be incredibly nonrobust, which has been studied under the nomer of 'adversarial attacks'.

The kind of nonrobustness that neural networks show (namely sensitive to small perturbations) is a strong hint to me that the signals found by neural networks are, at least in part, spurious. That is hardly a stretch; with input dimensions in the hundreds of thousands, even uncorrelated random noise will likely contain a number of strong spurious correlations (linear dependence), and the amount of reasonably smooth nonlinear dependencies will be much larger.

This is where consistency comes in. If training neural networks is consistent, at least there is hope that under the right conditions (given by the consistency proof) the spurious signals disappear. If on the other hand training is inconsistent, we should look for ways to adapt the learning process to make it consistent.


Here is my reasoning: We know that

$$ g_n = \arg\min_{f\in\mathcal{F}'_n}\sum_{i=1}^n{(y_i-f(x_i))}^2 $$

is consistent if $\mathcal{F}'_n$ is chosen very precisely, for example according to the universal approximation proof in this paper.

The problem is that neural networks are known to have multiple local minima in their loss function and have no special structure we can exploit, therefore there does not exist an algorithm that can find with certainty the elusive $g_n$.

In particular, the average discrepancy between local and global minima need not converge to zero. That would be enough to not have consistency.

This does not conflict with the universal approximation theorem because that theorem does not concern algorithms, it only answers the question if $\lim_{n\rightarrow\infty}\mathcal{F'_n}$ is dense in $\mathcal{F}$.


Am I wrong? How well known/studied is this in the ML literature? For example, the deep learning book has a whole section on the theory of consistency, but never relays it back to deep learning.

$\endgroup$
9
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Mar 10 at 20:29
  • 1
    $\begingroup$ I disagree. That theorem applies to an esoteric estimator; the minimization required in equation (2.4) is not practically possible because 1) you would have to find the global minimum of a non-convex function and 2) you would have to minimize over a number of hyperparameters as well. While their result is stronger than an asymptotic UAT, it still does not concern estimators that can actually be calculated. $\endgroup$
    – Sebastiaan
    Mar 13 at 14:10
  • 1
    $\begingroup$ @Sebastiaan, here again, one should distinguish the difference between (1) convergence of sample quantities to their population counterparts and (2) convergence of some optimization algorithm to the actual optimum in a given sample. Statistical and econometric theory typically concerns the former, not the latter. Keeping this in mind will help understand theoretical results more easily. $\endgroup$ Mar 13 at 16:20
  • 1
    $\begingroup$ @Sebastiaan why you are talking about the practical problems of a solution of empirical minimization? $\hat{f}$ in equation (2.4) by definition is the minimizer of empirical risk that exists and for statistical guarantees (like consistency), it doesn't matter whether you have an effective procedure (algorithm) to solve it or not. If this is not how you think about consistency then I suggest Vapnik, Statistical Learning Theory - Chapter 3. The main result of that chapter is: erm is consistent iff growth function increases slower than the number of learning examples. $\endgroup$
    – D.G
    Mar 13 at 22:57
  • 1
    $\begingroup$ @D.G Consistency concerns estimators. We are free to choose which estimators to study. I choose to study estimators we can actually calculate. $\endgroup$
    – Sebastiaan
    Mar 14 at 6:14
1
$\begingroup$

Some details must be defined before the question can be answered.

There are different sorts of neuron and network connections, and these need specifying. There are also different measures of how well a learnt function approximates the function to be learned.

The universal approximation theorem assumes compact support, so probably this should be specified in the question. Neural nets do not extrapolate. For example, RELUs are asymptotically linear so a RELU network, however well it approximates the objective function within the support of the training set, can only learn a function that is asymptotically linear.

There are also different training algorithms - the answer must be dependent on which is chosen.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you for pointing this out, I will clarify in the question. I left a lot of freedom on purpose: I wish to see a proof that there exists a neural network, usable in practice, that is consistent, whatever the specification. $\endgroup$
    – Sebastiaan
    Mar 10 at 18:15
  • $\begingroup$ Just as a curiosity, while most universal approximation theorems I have seen require compact support, this is not a necessity, just a product of the space being studied. For example, the asymptotic linearity of ReLUs is not a problem in $L_2$ space, and neither is the asymptotic constancy of sigmoid-style activations. $\endgroup$
    – Sebastiaan
    Mar 10 at 18:53
0
+150
$\begingroup$

TL;DR SGD works great on some problems because the problems it works great on possess significant symmetry, redundancy and smoothness. For such problems a greedy general-purpose algorithm exists, that finds a global or almost global minimum given finite noisy data and relatively small number of iterations. But, of course, general optimization problems are not solvable by greedy strategies.

Answer: I suspect that for a practically-useful consistency requirement you will always be able to find a counter-example where the theory fails.

  1. The true complexity of the function can be infinite-dimensional or at least very large. You could in general have a tabulated mapping $x \rightarrow y$ where $y$ are pre-defined random numbers.
  2. SGD relies on the idea that "natural" functions are at least to some extent smooth. SGD is completely useless in trying to find the minimum of an "unnatural" function such as Weierstrass function or a large class of chaotic functions. Again, no proof, but it is not hard to imagine a problem class where no general algorithm except of brute-force search exists.

The problems in 1,2 could be alleviated by restricting the smoothness of the function and enforcing a compact domain, thus ensuring that there is only a finite number of local minima regions. While this certainly is not true for all problems of practical relevance, it is true for some, and it simplifies the problem significantly. Given a smoothness constraint we can guarantee that local minima regions are at least a certain minimal distance apart, so we could guarantee a global minimum via GD + Grid Search. But Grid Search is practically unfeasible due to curse of dimensionality. SGD is to some extent similar to simulated annealing:

  • It theoretically has a chance to visit the whole compact domain via random chance, but depending on initial conditions and parameter choices the chances of visiting the basin of attraction of the global minimum can be arbitrarily low.
  • If no good prior for initial condition exists, it may be required to randomly reset the initial condition after a certain number of iterations. This would guarantee that the basin of attraction of the global minimum is eventually visited, but it need not work better than grid search.
$\endgroup$
2
  • $\begingroup$ The bounty expired in a couple of minutes and this is the first decent attempt at an answer so it is yours. It seems for now we have to conclude that there is no theory on consistency related to neural networks found in practice. $\endgroup$
    – Sebastiaan
    Mar 15 at 10:18
  • $\begingroup$ Thanks. I'm well aware that perhaps this answer is not fully satisfactory or answer the question at all. I am just trying to point out that it is likely that significant further assumptions are necessary to get to any results. I'm happy to follow up later if I can still contribute in any way $\endgroup$ Mar 15 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.