LessWrong 2.0 Reader

We know there are difficult computational problems. P vs NP is more narrow than that; it's sometimes phrased as "are there problems that are not difficult to verify but difficult to solve?", where "difficult" means that it cannot be done in asymptotically polynomial time.

Our observations are compatible with a world that is generated by a Turing machine with just a couple thousand bits.

Yes, but this is kinda incompatible with QM without mangled worlds.

I don't know where anger fits into this. Also I should look at how these behaviors manifest in other animals.

Yes, this is exactly the point. 

QM doesn't need a random seed!

Connotationally, even if things are pseudorandom, they still might be "random" for all practical purposes, e.g. if the only way to calculate them is to simulate the entire universe. In other words, we may be unable to exploit the pseudorandomness.

I'm just computational complexity theory enthusiast, but my opinion is that P vs NP centered explanation of computational complexity is confusing. Explanation of NP should happen in the very end of the course.

There is nothing difficult in proving that computationally hard functions exist: time hierarchy theorem implies that, say, P is not equal EXPTIME. Therefore, EXPTIME is "computationally hard". What is difficult is to prove that very specific class of problems which have zero-error polynomial-time verification algorithms is "computationally hard".

This distinction isnt material. The distinction I am getting at is whether our physics (simulation) is using a large K-incompressible seed or not.

I think that there is a way to compensate for this effect.

To illustrate compensation, consider the following experiment: Imagine that I want to resurrect a particular human by creating a quantum random file. This seems absurd as there is only $2^{-\text{a lot}}$ chance that I create the right person. However, there are around d $2^{\text{a lot}}$ copies of me in different branches who perform similar experiments, so in total, any resurrection attempt will create around 1 correct copy, but in a different branch. If we agree to trade resurrections between branches, every possible person will be resurrected in some branch.

Here, it means that we can ignore worries that we create a model of the wrong AI or that AI creates a wrong model of us, because a wrong model of us will be a real model of someone else, and someone else's wrong model will be a correct model of us.

Thus, we can ignore all branching counting at first approximation, and instead count only the probability that Aligned AI will be created. It is reasonable to estimate it as 10 percent, plus or minus an order of magnitude.

In that case, we need to trade with non-aligned AI by giving 10 planets of paperclips for each planet with humans.

Pseudorandom warp fields

[tl;dr the loss landscape around a set of weights encoding an unlearnable 'pseudorandom' function will be warped in such a way that gradient optimizers will bob around for exponentially long. ]

Unlearnable Functions: Sample Complexity and Time Complexity

Computational learning theory contains numerous 'no-go' results indicating that many functions are not tractably learnable.

The most classical result is probably the VC dimension and PAC learnability. A good example to think about are parity functions. The output is, in some sense, very (maximally) sensitive to the input*. Effectively, this means that we need a lot of data points to pin down the functions. These functions require an intractable number of data points to learn effectively due to their high sample complexity.

Using pseudorandom generators (e.g., Blum-Blum-Shub), one can similarly construct functions that need a superpolynomial amount of time to learn.

Neural networks are very expressive. The oft-cited universal approximation theorem states that any function may be approximated by neural networks (but be careful with the required network size and depth). These superpolynomial-hard functions may be expressed by neural networks, but they wouldn't be learnable due to optimization challenges and the exponential time required.

Gradient Optimizers and Cursed Landscapes

There is some old work by Stuart Kauffman investigating what kinds of landscapes are learnable by optimization processes like evolution by natural selection. The takeaway is that 'most' fitness landscapes aren't navigable by optimization processes akin to gradient descent; there are too many local minima, making efficient search infeasible.

I conjecture that the landscape around a set of weights w∈Ww \in Ww∈W encoding a pseudorandom-hard function fff becomes extremely oscillatory. This warping causes any gradient optimizer (regardless of step size) to get stuck in local minima or wander around for exponentially long periods***.

This has practical implications for reasoning about the inductive bias of Stochastic Gradient Descent (SGD). Most existing convergence proofs for gradient optimizers impose conditions such as Lipschitz continuity on the landscape. Or they will talk about 'long tails of ϵ\epsilonϵ-approximate saddle points'.

*This is the start of the beautiful field of Fourier analysis of Boolean circuits. Thanks to Jake and Kaarel for introducing me to this circle of ideas recently—it's very cool!

**Here's something I am confused about: the Statistical Learning Theory (SLT) point of view would be that parameters encoding these functions would have large λ\lambdaλ (e.g., eigenvalues of the Hessian). I am a little confused about this since λ\lambdaλ is bounded by d2\frac{d}{2}2d​, which can be high but not exponentially large. Perhaps this is where the mysterious multiplicity parameter mmm comes in—or lower-order contributions to the free-energy formula.

***Perhaps 'superpolynomially long' is a more accurate description.