Demons in Imperfect Search
One day, a gradient descent algorithm ball was happily rolling down a high-dimensional surface hill. All it wanted was to roll as far down as possible. Unbeknownst to the ball, just off to the side was a steep drop-off—but there was a small bump between the ball and the drop-off. No matter; there was enough random noise on the ball that it would jump the bump sooner or later.
But the ball was headed into unfriendly territory.
As the ball rolled along, the bump became taller. The farther it rolled, the taller the bump grew, until no hope remained of finding the big drop anytime before the stars burned out. Then the road began to narrow, and to twist and turn, and to become flatter. Soon the ball rolled down only the slightest slope, with tall walls on both sides constraining its path. The ball had entered the territory of a demon, and now that demon was steering the ball according to its own nefarious ends.
This wasn’t the first time the ball had entered the territory of a demon. In early times, the demons had just been bumps which happened to grow alongside the ball’s path, for a time—chance events, nothing more. But every now and then, two bumps in close proximity would push the ball in different directions. The ball would roll on, oblivious, and end up going in one direction or the other. Whichever bump had “won” would continue to steer the ball’s trajectory—and so a selection process occurred. The ball tended to roll alongside bumps which more effectively controlled its trajectory—bumps which were taller, bumps which steered it away from competing bumps. And so, over time, bumps gave way to barriers, and barriers gave way to demons—twisty paths with high walls to keep the ball contained and avoid competing walls, slowing the ball’s descent to a crawl, conserving its potential energy in case a sharp drop were needed to avoid a competitor’s wall.
The ball’s downhill progress slowed and slowed. Even though the rich, high-dimensional space was filled with lower points to explore, the highly effective demons had built tall walls to carefully contain the ball within their own territory, drawing out its travels indefinitely.
This tale visualizes a pattern:
There is some optimization process—in this case, some variant of gradient descent.
The optimizing search is imperfect: gradient descent only looks at local information, so it doesn’t “know” if there’s a steep drop beyond a nearby bump.
Exploiting the imperfect search mechanism: in this case, the steep drop is hidden by raising high walls.
Demon: in a rich enough search space, a feedback loop can appear, inducing more-and-more-perfect exploitation of the imperfect search mechanism. A whole new optimization process appears, with goals quite different from the original.
Does this actually happen? Let’s look at a few real-world examples...
Optimization process: free energy minimization in a chemical system. Search operates by random small changes to the system state, then keeping changes with lower free energy (very roughly speaking).
Search is imperfect: the system does not immediately jump to the global maximum. It’s searching locally, based on random samples.
Exploiting the imperfect search mechanism: there’s often a free energy barrier between low-free-energy states. Biological systems manipulate the height of the barriers, raising or lowering the activation energies required to cross them, in order to steer the local-free-energy-minimization process toward some states and away from others.
Demon: in primordial times, some chemicals happened to raise/lower barriers to steer the process in such a way that it made more copies of the chemicals. This kicked off an unstable feedback loop, producing more and more such chemicals. The rest is natural history.
Optimization process: evolution, specifically selection pressure at the level of an organism. Search operates by making random small changes to the genome, then seeing how much the organism reproduces.
Search is imperfect: the system does not immediately jump to the global optimum. It’s searching locally, based on random samples, with the samples themselves chosen by a physical mechanism.
Exploiting the imperfect search mechanism: some genes can bias the random sampling, making some random changes more or less likely than others. For instance, in sexual organisms, the choice of which variant of a gene to retain is made at random during fertilization—but some gene variants can bias that choice in favor of themselves.
Demon: sometimes, a gene can bias the random sampling to make itself more likely to be retained. This can kick off an unstable feedback loop, e.g. a gene which biases toward male children can result in a more and more male-skewed population until the species dies out.
Optimization process: profit maximization. Search operates by people in the company suggesting and trying things, and seeing what makes/saves money.
Search is imperfect: the company does not immediately jump to perfect profit-maximizing behavior. Its actions are chosen based on what sounds appealing to managers, which in turn depends on the managers’ own knowledge, incentives, and personal tics.
Exploiting the imperfect search mechanism: actions which would actually maximize profit are not necessarily actions which look good on paper, or which reward the managers deciding whether to take them. Managers will take actions which make them look good, rather than actions which maximize profit.
Demon: some actions which make managers look good will further decouple looking-good from profit-maximization—e.g. changing evaluation mechanisms. This kicks off an unstable feedback loop, eventually decoupling action-choice from profit-maximization.
I’d be interested to hear other examples people can think of.
The big question is: when does this happen? There are enough real-world examples to show that it does happen, and not just in one narrow case. But it also seems like it requires a fairly rich search space with some structure to it in order to kick off a full demonic feedback loop. Can that instability be quantified? What are the relevant parameters?