The Exact Mixability of Follow-the-Perturbed-Leader

Follow-the-perturbed-leader with Gumbel noise in online learning and perturb-and-MAP in structured prediction run the same device, an independent standard Gumbel for every variable-value pair of a decision set followed by a single call to the optimizer. One Gumbel per action would make the perturbed maximizer an exact sample of exponential weights, whose regret against a mixable loss stays bounded at every horizon, but the actions are exponentially many. Noise on the variables keeps the single call and loses that exactness, at a price in learning rate that neither literature has determined. We determine that price on every product decision set, the configuration space of a graphical model, where it is exactly the fractional certificate complexity of what the loss reads. Dividing the learning rate of exponential weights by that complexity keeps the regret bounded at every horizon, whatever the energies of the model, and no smaller divisor does. A measure from Boolean function complexity thereby acquires an operational meaning, as the cost of a single optimizer call.