7 ms·

"why do neural networks work better than other models?" That sounds really interesting - any references (for a non specialist)?

andbberger 5mo ago
https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore... the better question is why does gradient descent work for them
- jmalicki 5mo ago
  The properties that the uniform approximation theorem proves are not unique to neural networks. Any models using an infinite dimensional Hilbert space, such as SVMs with RBF or polynomial kernels, Gaussian process regression, gradient boosted decision trees, etc. have the same property (though proven via a different theorem of course). So the universal approximation theorem tells us nothing about why should expect neural networks to perform better than those models.
  - hodgehog11 5mo ago
    Extremely well said. Universal approximation is necessary but not sufficient for the performance we are seeing. The secret sauce is implicit regularization, which comes about analogously to enforcing compression.
    - jimmypk 5mo ago
      [flagged]
      - hackinthebochs 5mo ago
        >Do you think grokking is consistent with implicit regularization as compression Pretty sure it's been shown that grokking requires L1 regularization which pushes model parameters towards zero. This can be viewed as compression in the sense of encoding the distribution in the fewest bits possible, which happens to correspond to better generalization.
        hodgehog11 5mo ago
        Couldn't have said it better, although this is only for grokking with the modular addition task on networks with suitable architectures. L1 regularization is absolutely a clear form of compression. The modular addition example is one of the best cases to see the phenomenon in action.
  - NooneAtAll3 5mo ago
    Universal approximation is like saying that a problem is computable sure, that gives some relief - but it says nothing in practice unlike f.e. which side of P/NP divide the problem is on
    - ngruhn 5mo ago
      > unlike f.e. which side of P/NP divide the problem is on Actually the P/NP divide is a similar case in my opinion. In practice a quadratic algorithm is sometimes unacceptably slow and an NP problem can be virtually solved. E.g. SAT problems are routinely solved at scale.
      - imtringued 5mo ago
        An NP problem can contain subproblems that are not worst case problems. It's similar to the gap between pushdown automata and Turing machines. You can check if pushdown automata will terminate or not. You can't do it for Turing machines, but this doesn't stop you from running a pushdown automata algorithm on the turning machine with decidable termination.
    - Mithriil 5mo ago
      Asymptotics has been used to validate tons of statistical tools. This is just another tool being validated. If you have a tool that you don't know works when data increases (n-> infinity), then you shouldn't use it. So practicaly, I believe it has serious implications.
      - jmalicki 5mo ago
        It's very much necessary but not sufficient. In real life the sample complexity matters a lot too, which is also asymptotics, but a more important one. E.g. how the central limit theorem is far more powerful than the law of large numbers.
  - soVeryTired 5mo ago
    Whenever people bring this up I like to remind them that linear interpolation is a universal function approximator.
    - bilsbie 5mo ago
      Can you expand on that?
      - hansvm 5mo ago
        I'll use 1NN as the interpolation strategy instead since I think it illustrates the same point and saves a few characters. Recap: 1NN says that given a query Q you choose any pair (X,Y) from your learned "model" (a finite set of (X,Y) pairs) M minimizing |Q-X|. Your output is Y. The following kind of argument works for linear interpolation too (you can even view 1NN as 1-point interpolation), but it's ever so slightly messier since definitions vary a fair bit, you potentially need to talk about the existence of >1 discrete "nearest" or "enclosing" set of neighbors, and proving that you can get away with fewer points than 1NN or have lower error than 1NN is itself also messier. Pick your favorite compact-domain, continuous function embedded in some Euclidean space. For any target error you'd like to hit, the uniform continuity of that function guarantees that if your samples cover the domain well enough (no point in the domain is greater than some fixed distance, needing smaller distances for lower errors, from some point in your model) then the maximum error from a 1NN strategy is bounded by the associated error given by uniform continuity (which, again, you can make as small as you'd like by increasing the sampling resolution). The compact domain means you can physically achieve those error bounds with finite sample sizes. For a simple example, imagine fitting more and more, smaller and smaller, line segments to y=x^2 on [-1,1].
    - Mithriil 5mo ago
      I don't think that this is true. You need an infinite number of dimensions for this (think Taylor's expansion, Fourier expansion, infinitely wide or deep NNs..)
      - jmalicki 5mo ago
- fc417fc802 5mo ago
  I don't follow. Why wouldn't it work? It seems to me that a biased random walk down a gradient is about as universal as it gets. A bit like asking why walking uphill eventually results in you arriving at the top.
  - hodgehog11 5mo ago
    It wouldn't work if your landscape has more local minima than atoms in the known universe (which it does) and only some of them are good. Neural networks can easily fail, but there's a lot of things one can do to help ensure it works.
    - appplication 5mo ago
      Not a mathematician so I’m immediately out of my depth here (and butchering terminology), but it seems, intuitively, like the presence of a massive amount of local minima wouldn’t really be relevant for gradient descent. A given local minimum would need to have a “well” at least be as large as your step size to reasonably capture your descent. E.g. you could land perfectly on a local minima but you won’t stay the unless your step size was minute or the minima was quite substantial.
      - fc417fc802 5mo ago
        I believe what was meant was that assuming local minima of a sufficient size to capture your probe, given a sufficiently high density of those, you become extremely likely to get stuck. A counterpoint regarding dimensionality is made by the comment adjacent to yours.
      - sdenton4 5mo ago
        The randomness (and exploration) encouraged by batch training also helps avoid 'real' minima, if they exist.
    - anvuong 5mo ago
      A funny thing is, in very high-dimensional space, like millions and billions of parameters, the chance that you'd get stuck in a local minima is extremely small. Think about it like this, to be stuck in a local minima in 2D, you only need 2 gradient components to be zero, in higher dimension, you'd need every single one of them, millions up millions of them, to be all zero. You'd only need 1 single gradient component to be non-zero and SGD can get you out of it. Now, SGD is a stochastic walk on that manifold, not entirely random, but rather noisy, the chance that you somehow walk into a local minima is very very low, unless that is a "really good" local minima, in a sense that it dominates all other local minimas in its neighborhood.
- hansvm 5mo ago
  Interestingly, there exist problems which provably can't be learned via gradient descent for them.

andbberger 5mo ago

https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore... the better question is why does gradient descent work for them

jmalicki 5mo ago
The properties that the uniform approximation theorem proves are not unique to neural networks. Any models using an infinite dimensional Hilbert space, such as SVMs with RBF or polynomial kernels, Gaussian process regression, gradient boosted decision trees, etc. have the same property (though proven via a different theorem of course). So the universal approximation theorem tells us nothing about why should expect neural networks to perform better than those models.
- hodgehog11 5mo ago
  Extremely well said. Universal approximation is necessary but not sufficient for the performance we are seeing. The secret sauce is implicit regularization, which comes about analogously to enforcing compression.
  - jimmypk 5mo ago
    [flagged]
    - hackinthebochs 5mo ago
      >Do you think grokking is consistent with implicit regularization as compression Pretty sure it's been shown that grokking requires L1 regularization which pushes model parameters towards zero. This can be viewed as compression in the sense of encoding the distribution in the fewest bits possible, which happens to correspond to better generalization.
      - hodgehog11 5mo ago
        Couldn't have said it better, although this is only for grokking with the modular addition task on networks with suitable architectures. L1 regularization is absolutely a clear form of compression. The modular addition example is one of the best cases to see the phenomenon in action.
- NooneAtAll3 5mo ago
  Universal approximation is like saying that a problem is computable sure, that gives some relief - but it says nothing in practice unlike f.e. which side of P/NP divide the problem is on
  - ngruhn 5mo ago
    > unlike f.e. which side of P/NP divide the problem is on Actually the P/NP divide is a similar case in my opinion. In practice a quadratic algorithm is sometimes unacceptably slow and an NP problem can be virtually solved. E.g. SAT problems are routinely solved at scale.
    - imtringued 5mo ago
      An NP problem can contain subproblems that are not worst case problems. It's similar to the gap between pushdown automata and Turing machines. You can check if pushdown automata will terminate or not. You can't do it for Turing machines, but this doesn't stop you from running a pushdown automata algorithm on the turning machine with decidable termination.
  - Mithriil 5mo ago
    Asymptotics has been used to validate tons of statistical tools. This is just another tool being validated. If you have a tool that you don't know works when data increases (n-> infinity), then you shouldn't use it. So practicaly, I believe it has serious implications.
    - jmalicki 5mo ago
      It's very much necessary but not sufficient. In real life the sample complexity matters a lot too, which is also asymptotics, but a more important one. E.g. how the central limit theorem is far more powerful than the law of large numbers.
- soVeryTired 5mo ago
  Whenever people bring this up I like to remind them that linear interpolation is a universal function approximator.
  - bilsbie 5mo ago
    Can you expand on that?
    - hansvm 5mo ago
      I'll use 1NN as the interpolation strategy instead since I think it illustrates the same point and saves a few characters. Recap: 1NN says that given a query Q you choose any pair (X,Y) from your learned "model" (a finite set of (X,Y) pairs) M minimizing |Q-X|. Your output is Y. The following kind of argument works for linear interpolation too (you can even view 1NN as 1-point interpolation), but it's ever so slightly messier since definitions vary a fair bit, you potentially need to talk about the existence of >1 discrete "nearest" or "enclosing" set of neighbors, and proving that you can get away with fewer points than 1NN or have lower error than 1NN is itself also messier. Pick your favorite compact-domain, continuous function embedded in some Euclidean space. For any target error you'd like to hit, the uniform continuity of that function guarantees that if your samples cover the domain well enough (no point in the domain is greater than some fixed distance, needing smaller distances for lower errors, from some point in your model) then the maximum error from a 1NN strategy is bounded by the associated error given by uniform continuity (which, again, you can make as small as you'd like by increasing the sampling resolution). The compact domain means you can physically achieve those error bounds with finite sample sizes. For a simple example, imagine fitting more and more, smaller and smaller, line segments to y=x^2 on [-1,1].
  - Mithriil 5mo ago
    I don't think that this is true. You need an infinite number of dimensions for this (think Taylor's expansion, Fourier expansion, infinitely wide or deep NNs..)
    - jmalicki 5mo ago
fc417fc802 5mo ago
I don't follow. Why wouldn't it work? It seems to me that a biased random walk down a gradient is about as universal as it gets. A bit like asking why walking uphill eventually results in you arriving at the top.
- hodgehog11 5mo ago
  It wouldn't work if your landscape has more local minima than atoms in the known universe (which it does) and only some of them are good. Neural networks can easily fail, but there's a lot of things one can do to help ensure it works.
  - appplication 5mo ago
    Not a mathematician so I’m immediately out of my depth here (and butchering terminology), but it seems, intuitively, like the presence of a massive amount of local minima wouldn’t really be relevant for gradient descent. A given local minimum would need to have a “well” at least be as large as your step size to reasonably capture your descent. E.g. you could land perfectly on a local minima but you won’t stay the unless your step size was minute or the minima was quite substantial.
    - fc417fc802 5mo ago
      I believe what was meant was that assuming local minima of a sufficient size to capture your probe, given a sufficiently high density of those, you become extremely likely to get stuck. A counterpoint regarding dimensionality is made by the comment adjacent to yours.
    - sdenton4 5mo ago
      The randomness (and exploration) encouraged by batch training also helps avoid 'real' minima, if they exist.
  - anvuong 5mo ago
    A funny thing is, in very high-dimensional space, like millions and billions of parameters, the chance that you'd get stuck in a local minima is extremely small. Think about it like this, to be stuck in a local minima in 2D, you only need 2 gradient components to be zero, in higher dimension, you'd need every single one of them, millions up millions of them, to be all zero. You'd only need 1 single gradient component to be non-zero and SGD can get you out of it. Now, SGD is a stochastic walk on that manifold, not entirely random, but rather noisy, the chance that you somehow walk into a local minima is very very low, unless that is a "really good" local minima, in a sense that it dominates all other local minimas in its neighborhood.
hansvm 5mo ago
Interestingly, there exist problems which provably can't be learned via gradient descent for them.