the better question is why does gradient descent work for them
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.
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.
sure, that gives some relief - but it says nothing in practice 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.
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.
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.
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].
Perhaps more important, just because it is easy to escape any local minimum does not mean that there is necessarily a trend towards a really good optimum, as it can just bounce between a bunch of really bad ones for a long time. This actually happens almost all the time if you try to design your entire architecture from scratch, e.g. highly connected networks. People who are new to the field sometimes don't seem to understand why SGD doesn't just always fix everything; this is why. You need very strong inductive biases in your architecture design to ensure that the loss (which is data-dependent so you cannot ascertain this property a priori) exhibits a global bowl-like shape (we often call this a 'funnel') to provide a general trajectory for the optimizer toward good solutions. Sometimes this only works for some optimizers and not others.
This is why architecture design is something of an art form, and explaining "why neural networks work so well" is a complex question involving a ton of parts, all of which contribute in meaningful ways. There are often plenty of counterexamples to any simpler explanation.
If they were all correlated with each other that does not seem far fetched.
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.
The only people for whom this is an open question are the academics - everyone else understands it's entirely because of the bagillions of parameters.
The actual reason is due to complex biases that arise from the interaction of network architectures and the optimizers and persist in the regime where data scales proportionally to model size. The multiscale nature of the data induces neural scaling laws that enable better performance than any other class of models can hope to achieve.
That’s a lot of words to say that, if you encode a class of things as numbers, there’s a formula somewhere that can approximate an instance of that class. It works for linear regression and works as well for neural network. The key thing here is approximation.
I can construct a Gaussian process model (essentially fancy linear regression) that will fit _all_ of my medical image data _exactly_, but it will perform like absolute rubbish for determining tumor presence compared to if I trained a convolutional neural network on the same data and problem _and_ perfectly fit the data.
I could even train a fully connected network on the same data and problem, get any degree of fit you like, and it would still be rubbish.
Data labeling is pretty big industry in some countries and I guess dropping 200 kilodollars on labeling is beyond the reach of most academics, even if they would not care about ethics of that.
Thats been my understanding of the crux of mystery.
Would love to be corrected by someone more knowledgable though
Transformers are superior "database" encodings as the hype about LLMs points out, but there have been promising ML models that were focusing on memory parts for their niche use cases, which could be promising concepts if we could make them work with attention matrixes and/or use the frequency projection idea on their neuron weights.
The way RNNs evolved to LSTMs, GRUs, and eventually DNCs was pretty interesting to me. In my own implementations and use cases I wasn't able to reproduce Deepmind's claims in the DNC memory related parts. Back at the time the "seeking heads" idea of attention matrixes wasn't there yet, maybe there's a way to build better read/write/access/etc gates now.
[1] a fairly good implementation I found: https://github.com/joergfranke/ADNC
- It's not gradient boosting per se that's good on tabular data, it's trees. Other fitting methods with trees as the model are also usually superior to NNs on tabular data.
- Trees are better on tabular data because they encode a useful inductive bias that NNs currently do not. Just like CNNs or ViTs are better on images because they encode spatial locality as an inductive bias.
As you noted, the industry has moved the goalposts to Agency and Long-horizon Persistence. The transition from building 'calculators that predict' to 'systems that endure' is a non-equilibrium thermodynamics problem. There is math/formulas and basic laws at play here that apply to AI just as much as it applies to other systems. Ironically it is the same math. The same thing that results in a signal persisting in a model will result in agents persisting.
This is my specific niche. I study how things persist. It’s honestly a bit painful watching the AI field struggle to re-learn first principles that other disciplines have known for decades. I have a doc I use to help teach folks how the math works and how to apply it to their domain and it is fun giving it to folks who stop guessing, like a cheat code for their productivity.
https://meta-r0ze.github.io/Informational-Energetics/Informa...
This is my fear with software development in general. There's a hundred-year old point of view right next door that'll solve problems and I'm too incurious to see it.
I have a relative with a focus in math education that I've been stealing ideas from, and I think we'd both appreciate a look at your doc if you don't mind.
So instead we're more likely to see navel-gazing "singularity" stories that fit with telling your investors they will become fantastically rich.
Awesome. What is holding you back? What do you need the funding for?
Many people additionally have little patience for research when the engineering is moving so quickly. Even many interpretability researchers give up far too soon if research doesn't yield immediately gratifying results.
This would be great, as from the "classical" perspective, the results of over-parametization and potentially other parts of NN architecture make no sense (to me, at least). I do accept that double-descent appears to empirically work, but it really, really shouldn't. In fact, as someone who's a big fan of Hastie et al's Elements, the bias variance tradeoff suggests that they shouldn't.
This has been bugging me (sporadically) for years, and any progress towards an answer would be incredibly useful (most probably in a philosophical sense I suppose).
As an aside, I've only read the Introduction, but this appears to be a well-written paper and a research program I can get behind. I really want this stuff to work.
I guess it's similar to bagging and boosting, which were empirically successful well before we had any theoretical understanding of why they work.
It really isn't so mysterious once you begin to examine how the rule of thumb for the bias-variance tradeoff (remember that it is the relationship with model size that is curious, not the tradeoff itself) came to be. The easiest ways to arrive at this rule are through an information criterion like the AIC or BIC, where the model size appears in the penalty term for the log-likelihood. These criteria have a bunch of assumptions, all of which are crucial, and absolutely none of which apply for neural networks. The biggest one is that the only limiting regime is in the size of the dataset, so there are vastly more data than model parameters. Neural networks have parameter counts within a constant ratio of the number of datapoints. Another is that the model has a non-singular Hessian in a neighbourhood of the optimum. Neural networks do not have this. Once you abandon the rule of thumb and actually do the math in the appropriate limiting regimes, there's no contradiction anymore.
I've found the biggest mystery for people though is the fact that performance actually _improves_ after the interpolation threshold. This seems insane if you come at it from the point of view that the model "could have done anything" if there are more parameters than data. But this isn't true at all. The fact that you have obtained _a solution_ means that you imposed some implicit bias that guided which solution you end up in. For linear regression, that is often the minimum L2 norm solution, which _literally_ minimizes the variance keeping all else fixed. If you add more parameters to play with, obviously it should be able to minimize the variance even further, right? If the bias is zero and the variance is reduced, you get better performance. If you use a different optimizer than gradient descent, you can end up at the minimum L1 norm solution (effectively LASSO), which is well-known to perform really well regardless of the number of parameters.
Of course, linear regression is not neural network regression, and the situation in deep learning is far more complicated. But the same idea applies. Every single part of the training procedure is carefully designed to bias the obtained solution toward something with minimal variance. Stochastic optimizers (even dropout) settle in wide minima which have smaller variances. Some optimizers prioritize stronger correlations in the weights. Bottlenecks in the architecture induce low-rank solutions. Data augmentation induce known invariances that reduce variance along those directions. Convolutional designs induce regularity with respect to the input space. Neural networks are not magic; they are the product of hundreds of intentional design decisions over decades. When you increase the size of the model, all of these features are exacerbated.
Quantifying all of this in the theory is difficult because there are a lot of moving parts. But if you study a simplified model and consider each mechanism individually, the picture becomes pretty clear.
The skepticism I'm seeing in the comments really highlights how little of this work is trickling down to the public, which is very sad to see. While it can offer few mathematical mechanisms to infer optimal network design yet (mostly because just trying stuff empirically is often faster than going through the theory, so it is more common to retroactively infer things), the question "why do neural networks work better than other models?" is getting pretty close to a solid answer. Problem is, that was never the question people seem to have ever really been interested in, so the field now has to figure out what questions we ask next.