Study notes: The Demon Is a Learner

The velocity relaxes almost at once to F/\gamma and then follows it, which leaves \dot x = F/\gamma (Tikhonov’s theorem). The small quantity is mk/\gamma^2, where k measures how steeply the force changes with position; m/\gamma is a time. Here mk/\gamma^2 = 16/100 = 0.16, below the threshold 1/4, so the body slides to rest without oscillating. It would oscillate below \gamma = \sqrt{4mk} = 8, and the first-order law is accurate only when mk/\gamma^2 is well below 1/4. Gradient descent is this limit with the loss as potential energy, F = -\nabla L. Heller’s m in F = m\cdot v plays the role of the drag coefficient \gamma.

Along \dot w = -\nabla L the loss falls at the rate |\nabla L|^2, so \frac{d}{dt}(L - L^*) \le -2\mu\,(L - L^*) and the excess shrinks at least as fast as e^{-2\mu t}. The condition forbids a flat spot anywhere but at the minimum value: the region holds no saddles, no spurious local minima and no local maxima. It does not need convexity, and the minimizers may form a curved valley with a flat floor. A network’s loss has other critical points, for example where every weight is zero, so the condition can hold only on part of the landscape. Wide networks satisfy it in a ball around their initialization.

The average gradient is 0.5 - 0.2 = 0.3, so \dot p = (-0.35,\ 0.09,\ 0.26), which sums to zero. A move \Delta costs \tfrac12\sum_i\Delta_i^2/p_i of divergence to second order, so the Fisher matrix is diagonal with 1/p_i in place i, and the same move costs ten times as much at 0.01 as at 0.1. Dividing the force by that matrix multiplies it by p_i. Heller’s m becomes 1/p_i, and a probability near zero barely moves. Evolutionary game theory knows the equation as the replicator dynamics. The other two geometries are gradient flow on the weights and the flow of a density downhill on its free energy, measured by the Wasserstein distance.

The line is the assumption that two balls about to collide are independent, so that the number of such pairs is the product of the two one-ball densities. Mechanics does not supply that number. A collision conserves energy and momentum and runs equally well backward. First argument: assume instead that balls are independent just after they collide, and the same algebra proves that entropy falls. Second, Loschmidt’s: reversing every velocity turns an entropy-raising history into an entropy-lowering one, so mechanics alone cannot make entropy rise. In the reversed gas the assumption fails, because each incoming pair is an outgoing pair of the original run, correlated by the collisions it has had.

10^{-6}\times100^{2.5} = 10^{-1}, so by then the rounded gas leaves the exact curve and its fall stops. Each further collision per disk costs a factor of a hundred: about two more decimal places in every position and velocity, a demand that grows without limit (the last section draws the consequence for a bounded observer). The mechanical gas and the gas whose colliding pairs are drawn at random give the same entropy curve, which is the H-theorem at work. The mechanical gas, reversed exactly at four collisions per disk, falls back to the entropy it began with. The rounded gas does not.

The entropy that rises belongs to a description that keeps one ball at a time, a coarse graining. If the balls start uncorrelated, every unit gained by the one-ball distribution, summed over the balls, is a unit stored in correlations among them. Boltzmann’s assumption says the description may discard those correlations, because none of them will come back as an incoming pair. In a gas prepared by ordinary means that is true, since nothing has tuned its correlations to its future. So the H-theorem is a theorem about forgetting, and what forgets is the description. A description forgets for free, and a physical system that shrinks its own possibilities has to send the difference somewhere.

• Gradient flow. It expands volume at the rate -\operatorname{tr}\nabla^2L, negative near a minimum, which a closed Hamiltonian system cannot do. A law that contracts volume is the shadow of a system coupled to a medium, and the medium takes up the volume, which is entropy.
• Resetting a bit. It maps two logical states onto one. Hamiltonian dynamics conserves fine-grained entropy, so the entropy k\ln 2 goes to the rest of the machine and the environment, as heat of at least kT\ln 2 into a bath at temperature T. This is Landauer’s principle.
• A computation. It need not pay. Any computation can be done by a logically reversible machine: compute, copy the answer, then run backward to clean up. What costs is throwing information away.
• A measurement. It can be done reversibly. The demon pays when it clears its memory to measure again, at least what it gained, which in Szilard’s engine is kT\ln 2 of work for one bit.

The first demon pays for n = 1{,}048{,}576 bits. The second converts the string into a short program that prints it: a fixed routine for \pi, plus about \log n = 20 bits to say how many digits. It then erases the program and pays for about 20 bits. The conversion can run reversibly at no cost because it forgets nothing: with x the string and y the program, K(x\mid y) is close to zero, since running the program gives the string back. The other n - \log n bits were only a longer way of writing the program. A learner that has found the regularity in its data stands where the second demon stands.

S = H(\text{state}\mid d) + K(d): the missing information plus the algorithmic information content of the record. A measurement shrinks the first term and grows the second, and for a system in equilibrium the decrease of ignorance is, on average, compensated by the growth of the minimal record. A single run can come out ahead. Keeping only the lucky runs needs a record of which runs were lucky, and that record costs, on average, at least what the luck gained. The sum is a two-part code, the length of a model plus the length of the data given the model, which is the minimum description length principle. The demon’s thermodynamic account and a learner’s model-selection account have the same form.

A bath’s noise is set before the system arrives and knows nothing of the distribution it acts on, so a process driven by it, with its law held fixed, drifts toward that law’s stationary distribution. Undoing the drift takes the time reversal of the diffusion, whose drift depends on the density at every moment through the score, the gradient of the log density. A diffusion model learns the score from data and with it turns noise into samples. A demon goes one step further and builds a correlation with the particular state in front of it, the thing Boltzmann’s assumption says is absent. Boyd, Crutchfield and Gu show that the work-maximizing demon is the maximum-likelihood learner. Boyd, Mandal and Crutchfield show that a demon can harvest correlations in its input only if its own memory reflects the structure that generated them.

\eta = 1 - \frac{T}{T'}\frac{I_{\text{mem}}}{I_{\text{rel}}} = 1 - \frac13\cdot\frac53 = \frac49, against Carnot’s 1 - \frac13 = \frac23, which the engine reaches only if all of its memory is relevant. Every bit written costs heat in proportion to T, and every relevant bit earns work in proportion to T'. Counted in units of T, a relevant bit is worth T'/T - 1 = 2 and an irrelevant one costs 1, so one more relevant bit pays off even if up to two irrelevant bits come with it. That exchange rate is the trade-off of the information bottleneck, which minimizing the bound on the engine’s dissipation gives. The irrelevant bits also loosen Kawaguchi and colleagues’ bound on the gap between training and test loss, roughly \sqrt{(I_{\text{mem}} - I_{\text{rel}} + 1)/n} for n examples.

K(x_t) \le K(x_0) + K(f) + K(t) + O(1), and K(t) grows only like \log t (the bound). So entropy grows because observers describe the world coarsely, not because the fine-grained state gets more complex. Shalizi and Moore’s answer has two halves. The observer supplies the observables. The dynamics then decides which refinement of them makes states that predict their own future, and those are the macrostates. A macrostate is what a predictor needs to keep. Boltzmann’s assumption makes the one-ball distribution such a state for a gas prepared by ordinary means, while the reversed gas has the same histogram with the opposite future. A JEPA searches for such states from data, and needs an anti-collapse term to do what the observables do.

The program finishes in the first phase with 2^i \ge 2^{10}\times1000 = 1{,}024{,}000, which is phase 20. The phases up to that one take at most 2^{21}\approx 2.1 million steps, within the bound of 4.096 million. For the ciphertext, the shortest fast program that decrypts the message contains the key, so the search takes about 2^k times the time of one decryption, the cost of trying every key. The thermodynamic ledger does not see it. Decryption can in principle run reversibly, at no cost in heat, and it adds no Shannon information while adding plenty of usable information, which is defined relative to the predictors an observer can afford. Bits price what an observer stores and forgets, and time prices what it can do with them.

The condition is that the learner is a physical system in a bath. “Where it is not, they share only a formula.”

• Training in software has no literal engine cycle, since Carnot’s argument needs a conserved energy and a loss is not conserved. Reading the Boltzmann machine’s two strokes as an engine is the authors’ reading and not Still’s, and the analogy stops at the output: the update dissipates the free energy instead of delivering it as work.
• Goldt and Seifert’s bound concerns the weights as a physical system, not the processors that compute them, which dissipate many orders of magnitude more.
• Friston’s variational free energy counts surprise against a model, in nats, and nothing in it is paid. That a system’s thermodynamic free energy encodes it is a further hypothesis.
• Kawaguchi and colleagues add that compressing is one way to generalize, not the only one and not a necessary one.
• Whether Landauer’s principle is independent of the second law is still argued.