Approximating Solomonoff Induction

Sincere thanks.

They [modern SGD systems] are heuristic optimizers that have no guarantees of finding a global optimum. It's strange to call them "powerful global optimizers".

Not at all strange. As I pointed out in the post above - modern SGD functions as a global optimizer due to clever tricks such as over-parameterization, dropout, and momentum. These optimizers are also suprisingly powerful as measured in terms of actual solution quality vs computational cost - indeed they dominate most of the landscape. It is completely disingenous to call the dominate solution anything other than powerful.

In practice strong guarantees are not important. What actually matters is finding a solution that is good enough relative to computational costs, where 'good enough' is determined according to some more complex business/economic utility metric, where solution quality follows diminishing returns. For sufficiently complex problems, finding the actual global optimum is rarely ideal - it is far too far to the right on the asymptotic diminishing returns curve.

what if you don't know the distribution/prior?

I suppose the Bayesian answer to that is that a probability distribution is a description of one's knowledge, and that in principle, every state of knowledge, including total ignorance, can be represented as a prior distribution. In practice, one may not know how to do that. Fundamentalist Bayesians say that that is a weakness in our knowledge, while everyone else, from weak Bayesians to Sunday Bayesians, crypto-frequentists, and ardent frequentists, say it's a weakness of Bayesian reasoning. Not being a statistician, I don't need to take a view, although I incline against arguments deducing impossibility from ignorance.

The learning version

What are you contrasting with learning? I don't see a demarcation of principle between learning and any other sort of statistical prediction.

That's not even true. In practice, it's the best we've got, but it's still terrible in most interesting settings (or else you could solve NP-hard problems in practice, which you can't).

SGD seems to be sufficient to train neural networks on real world datasets. I would honestly argue that it's better than whatever algorithms humans use. In that generally it learns much faster and far better on many problems.

That's not sufficient for general intelligence. But I think the missing piece is not some super powerful optimization algorithm. A better optimizer is not going to change the field much or give us AGI.

And I also don't think the magic of the human brain is in really good optimization. Most scientists don't even believe that the brain can do anything as advanced as backpropagation, which requires accurately estimating gradients and propagating them backwards through long time steps. Most biologically plausible algorithms I've seen are super restricted or primitive.

It's because the neural net algorithms are not even close to finding the optimal neural net in complex situations.

I disagree. You can find the optimal NN and it still might not be very good. For example, imagine feeding all the pixels of an image into a big NN. No matter how good the optimization, it will do way worse than one which exploits the structure of images. Like convolutional NNs, which have massive regularity and repeat the same pattern many times across the image (an edge detector on one part of an image is the same at another part.)

That's trivial to do. It's not the problem here.

It's really not. Typical reinforcement learning is much more primitive than AIXI. AIXI, as best I understand it, actually simulates every hypothesis forward and picks the series of actions that lead to the best expected reward.

Even if you create a bunch of really good models, simulating them forward thousands of steps for every possible series of actions is impossible.

PAC learning, for instance, is fundamentally non-Bayesian. Saying that PAC learning approximates Bayesian inference is the same as saying that Bayesian inference approximates PAC learning. It's not a very meaningful statement.

I looked into PAC learning a bit when Scott Aaronson talked about it on his blog, and came to the following conclusion. 'Instead of saying “PAC-learning and Bayesianism are two different useful formalisms for reasoning about learning and prediction” I think we can keep just Bayesianism and reinterpret PAC-learning results as Bayesian-learning results which say that in some special circumstances, it doesn’t matter exactly what prior one uses. In those circumstances, Bayesianism will work regardless.'

Of course that was 7 years ago and I probably barely scratched the surface of the PAC learning literature even then. Are there any PAC learning results which can't be reinterpreted this way?

In that sense stochastic gradient descent will also find the global optimum, since the randomness will eventually push it to every point possible. It will just take the eternity of the universe, but so will exhaustive search.

It's also trivial to modify any local algorithm to be global, by occasionally moving around randomly. This is also effective in practice, at finding better local optima.

Everything approximates Bayesian inference, it's just a matter of how ideal the approximation is. If you have enough data, the maximum likelihood approaches bayesian inference.

Huh?

There is a view that everything that works must be an approximation of the ideal Bayesian method. This is argued by Yudkowsky in Beautiful Probability and Searching for Bayes-Structure.

I used Maximum likelihood as an example, which is where you take the most probable hypothesis (parameters in a statistical model.) Instead of weighing many hypotheses the bayesian way. If you have enough data, the most probable hypothesis should converge to the correct one.

You can't do an exhaustive search on an infinite set.

I don't really understand the question. Or what "sense" means in this context.

Are you asking how close the approximation is the ideal? I would say that depends on the amount of computing power available, and that it approaches it in the limit. But it gives reasonable answers on realistic computers, whereas SI does not.

There is also some loss based on the information required to build a finite turing machine of the right size. As opposed to the infinite number of other structures you can build with logic gates. E.g. a machine that is exactly like a finite turing machine, but the 15th memory cell is corrupted, etc.

I don't think this problem is unsolvable though. There are for example Neural Turing Machines which give it access to an infinite differentiable memory.

I only barely mentioned it in my post, but there are ways of approximating bayesian inference like MCMC. And in fact there are methods which can take advantage of stochastic gradient information, which should make them roughly as efficient as SGD.

There is also a recent paper by Deepmind, Weight Uncertainty in Neural Networks.