What the hindsight was worth

The tail was named somewhere else records a borrowing. A search for a mountain-valley lettering of the rhombille tessellation patch costs eighty-four steps on its best run and does not finish inside twenty thousand on two runs in five, and stopping every attempt at a hundred steps and starting again is thirty-two times cheaper than letting each one run. None of that was found here. The heavy tail was described in the study of satisfiability search in the late 1990s, the restart that answers it in 1998, and the arithmetic of restarting a random search in 1993.

The essay ends by pointing at the part of the borrowing it did not use. The cutoff of a hundred was read off the measured runs afterwards, and nobody running the search could have chosen it in advance. The 1993 result is about exactly that situation: a restart schedule that needs no knowledge of the distribution at all, with a guarantee attached. Running it on the same runs says how much the hindsight was worth.

The schedule that needs no knowledge #

Michael Luby, Alistair Sinclair and David Zuckerman considered a Las Vegas algorithm — one whose answer is always right and whose running time is random — and asked how to stop and restart it so as to minimise the expected total time.

They proved two things. If the distribution of running times is known, the best strategy is a fixed cutoff: stop every attempt at the same length, the length that minimises one attempt’s expected cost divided by its chance of success. That is the strategy the restart curve found, at a hundred nodes.

If the distribution is not known, there is a single schedule that works for every distribution. It runs attempts with cutoffs in the sequence

1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, …

times a chosen unit — each block is the block before it repeated twice, followed by a doubling. Every power of two appears, each half as often as the one below it, so whatever the right cutoff is, the schedule spends a bounded share of its effort near it. They showed its expected cost is within a logarithmic factor of the best fixed cutoff’s, for any distribution whatever, and that no schedule ignorant of the distribution can do better than a logarithmic factor in the worst case.

Pricing it on the measured runs #

The runs make the price computable exactly rather than by simulation. Each of the hundred and twenty measured runs is a number of nodes, or unfinished at twenty thousand.

An attempt with cutoff $c$ costs $\mathbb{E}[\min(X, c)]$ — the average over the runs of the smaller of the run’s length and the cutoff — and fails with probability $P(X > c)$, the share of runs longer than $c$. Attempt $i$ on the schedule is reached only if every earlier attempt failed, so the expected total is the sum over attempts of the chance of reaching it times its cost:

$$\mathbb{E}[\text{total}] = \sum_i \Bigl(\prod_{j<i} P(X > c_j)\Bigr)\,\mathbb{E}[\min(X, c_i)]$$

The sum is run until the chance of still being searching is below a part in a trillion. Nothing is sampled: the same hundred and twenty numbers that produced the fixed-cutoff curve produce this one, so the comparison is between two strategies on one distribution.

At a unit of one node the answer is 3,222 nodes. The best fixed cutoff, a hundred, costs 512. The universal schedule pays 6.3 times the hindsight’s price.

A logarithm, measured #

A factor of 6.3 is not a random number, and the theory says what to compare it with.

The guarantee is that the schedule costs at most $192\,\ell\,(\log_2 \ell + 5)$, where $\ell$ is the best fixed strategy’s expected cost. On these runs that bound is 1,375,611 nodes, which the schedule beats by more than two orders of magnitude. The constant 192 is the price of a proof that holds for every distribution, and a particular distribution is usually much kinder.

The logarithm is the part that survives, and it shows. The best cutoff is a hundred nodes, and $\log_2 100$ is 6.64. The measured factor, 6.30, is close to it. The intuition is the schedule’s own: to reach attempts of about a hundred nodes it has to have climbed through every smaller power of two, and it spends roughly as much on each level of that climb as on the level it needed. Seven levels below a hundred, and about six and a third times the cost.

The climb can be counted exactly. In the schedule’s first thirty-one attempts the cutoff one appears sixteen times, two eight times, four four times, eight twice and sixteen once, so each of five levels is handed the same sixteen units, eighty in all. The equal division continues at every length. The first attempt with a cutoff of sixty-four is the hundred and twenty-seventh, and the first with a cutoff of a hundred and twenty-eight — the first long enough to contain the hindsight’s hundred — is the two hundred and fifty-fifth.

On the rhombille patch that has a hard consequence, because its best run is eighty-four nodes. Every attempt before the two hundred and fifty-fifth has a cutoff of sixty-four or less, so every one of them runs to its cutoff and fails, with certainty. Their cutoffs add to 896 nodes. Before the universal schedule makes a single attempt that could succeed, it has spent 896 nodes — 1.75 times the hindsight cutoff’s entire expected cost. The rest of its 3,222 is the chance that the attempt of a hundred and twenty-eight fails too, and the next climb through the short levels that follows.

That is a pleasing agreement and it should not be over-read. The factor depends on how much of the distribution’s probability sits near the best cutoff; a distribution with more short runs would make the lower levels pay for themselves and the factor smaller. What the measurement supplies is one instance with a factor close to the logarithm, which is the order the theorem predicts.

Choosing the unit is choosing the scale #

The schedule has one parameter, the unit its cutoffs are multiplied by, and the table in the first figure sweeps it.

At a unit of two nodes the cost is 2,854. At five, 2,542. At ten, 2,152; at twenty, 1,762; at fifty, 848. At a hundred it falls to 551, within eight per cent of the hindsight cutoff, and at two hundred it rises again to 638.

So the schedule’s gap from the hindsight is almost entirely a matter of the unit. At the right unit it is nearly as good as knowing the distribution. The difficulty is that the right unit is the best cutoff, near enough — a hundred again — and choosing it requires knowing the scale of the running times, which is the knowledge the schedule exists not to need.

A unit is a guess at the scale of the distribution, and a good guess is worth a factor of six. A unit of one is the honest choice for somebody with no information. Any larger unit is an assumption about how long a run of the search usually takes, and on the rhombille patch that assumption, if right, recovers nearly everything.

That is a sharper version of the original borrowing’s caution. The restart result transferred intact; what did not transfer was the measured cutoff, which looked like a property of the search and was a property of having already run it.

The same price in a different problem #

The shape of this gap has a familiar form outside search.

A person going skiing for an unknown number of days can rent skis each day or buy them once. If the number of days were known the choice would be trivial. Not knowing it, the best a strategy can guarantee is to rent until the rental paid equals the purchase price and then buy — which never costs more than twice what the best choice in hindsight would have. The study of such problems, in which a decision must be made before the information that would settle it arrives, measures a strategy by that ratio to the hindsight optimum.

The universal restart schedule is the same kind of object. It is an online strategy for a decision — when to give up on an attempt — that depends on a distribution not yet seen, and its worst-case ratio to the hindsight optimum is a logarithm where the skier’s is a constant. The 6.3 measured here is that ratio, observed on a folding search, and it is a small illustration of a large idea: the price of not knowing can be bounded, and the bound is a different kind of number from the saving the knowledge would buy.

What is being restarted #

It is worth being concrete about what an attempt produces, because the whole arithmetic depends on it and it is easy to lose sight of.

A finished attempt returns a lettering of the rhombille patch — a mountain or valley for each of its creases — whose arcs close no loop, which the search checks as it goes and which is then put past the four conditions at every vertex and past a folded sheet rebuilt from scratch. That is what makes the search a Las Vegas algorithm in the borrowed sense: its answer is always right when it comes, and only the time to it is random. An unfinished attempt produces nothing at all, and discarding it loses nothing but the nodes it spent.

That is also why the comparison is fair to both strategies. Neither the fixed cutoff nor the universal schedule changes what counts as success or how an attempt searches. They differ only in when they give up, and the question of when to give up on a search whose answer, when it comes, is certain is exactly the question the 1993 result answered.

The other borrowings this field has recorded had a different shape. A test imported without its hypothesis took a rule and lost the sentence saying which sheets it applied to; the same vertex found four times was rediscovery, the same object found independently. This one imported a theorem with its hypothesis intact — attempts independent, answers certain — and what it lost was a number. The fixed cutoff was carried over as though it were a property of the search, and it was a property of a particular set of runs.

And then the coin #

The measurement has a complication that the borrowed literature would have predicted, and it changes what the 6.3 is a price of.

The difficulty was in the coin found where the rhombille patch’s tail comes from. The search chooses which letter to try first on each crease by tossing a coin, so that different seeds give different letterings; replace the coin with a constant and the patch is lettered in about eighty steps on every run, with no spread and no tail. The heavy tail is not a property of the pattern but of the randomisation, which is exactly the framing of the 1997 measurements: a heavy tail belongs to a randomised search meeting an instance, not to the instance.

So the restart schedule here is answering a problem the coin created. With the coin removed, neither the fixed cutoff nor the universal schedule is needed: the search finishes in its minimum every time.

That is not a reason to discard the measurement. A search usually has a coin for a reason — here, to explore letterings rather than return the same one — and a practitioner who wants the exploration and cannot afford the tail needs exactly the schedule priced above. But it is a reason to say that the 6.3 is a price paid for a design choice, and that the cheapest remedy for a heavy tail is sometimes to find where it came from.

What the comparison cannot show #

The figures price two strategies on a hundred and twenty runs, and a hundred and twenty runs are a sample.

The hindsight cutoff was chosen on the same runs it is priced on, which flatters it: a cutoff chosen on one sample and priced on another would do slightly worse, and the gap to the universal schedule would be slightly smaller. Forty-eight of the runs did not finish within twenty thousand nodes, and the pricing counts them as longer than every cutoff, which is conservative for short cutoffs and uninformative about how long those runs would have been — so the schedule’s attempts past twenty thousand cannot be priced at all, and at units of one the schedule’s probability of still searching when it reaches that length is small enough not to matter.

Nor can the figures show a different patch. The four patches with no tail would make the universal schedule pointless and a fixed cutoff pointless too, since every run finishes near its minimum. The comparison is informative only where there is a tail, and among the five patches measured there is one.

And they cannot show what a worst case looks like. A logarithmic factor is a worst-case guarantee, the kind of statement hardness results make about the hardest instance rather than a typical one, and one measured distribution landing near the logarithm says nothing about how bad the factor can be on a distribution built to defeat the schedule.

The search the prices assume #

Attempts are independent. Each restart reseeds the coin and starts from nothing, carrying no learnt constraint forward, which is what makes a Las Vegas algorithm’s restart arithmetic apply. A search that learnt from its failed attempts would be a different object with different prices.

The runs are a faithful sample of the distribution. The pricing treats the hundred and twenty measured lengths as the distribution itself. With more runs the numbers would move a little and the logarithmic shape would not.

And cost is nodes. The expected totals count search nodes, not time, and a node’s cost is taken to be the same on every attempt.

How the prices were computed #

Both prices are exact expectations over the same runs. The fixed-cutoff cost is one attempt’s expected cost over its chance of success; the universal schedule’s is the sum over attempts of the chance of reaching each times its expected cost. No attempt is simulated.

The schedule is required to cost more than the hindsight cutoff and less than its own guarantee, and some unit larger than one is required to improve on a unit of one. The first condition is what makes the hindsight worth something; the second is what makes the guarantee a guarantee; the third is what makes the unit a real choice.

Still open: whether the unit can be learnt while searching #

The gap between a unit of one and a unit of a hundred is most of the gap to the hindsight, and a unit is a single number. That suggests a middle course the two strategies bracket: estimate the scale of the running times from the attempts already made, and set the unit from the estimate. Every failed attempt carries information about the distribution — at the least, that runs of that length fail — and a schedule that adjusted its unit as it went would sit somewhere between knowing nothing and knowing everything.

Whether that recovers the factor of six without giving up the guarantee is a question the borrowed field has studied, and it is worth asking here only as a measurement on these runs: the instrument exists and the answer is a few lines of arithmetic on numbers already in hand.

The other continuation runs back through the diagnosis. If the tail comes from the coin, then the question worth asking of any randomised search on a crease pattern is how much randomness it needs for the exploration it wants — and whether a smaller amount of randomness, spent somewhere other than on every crease, would keep the exploration and lose the tail.

The habit worth carrying is a question to put to any tuned parameter. Was it chosen before the data or after? A parameter read off the results it is evaluated on is a measurement of hindsight, and the honest comparison is always against the strategy that did not have it.