Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors derive an explicit analytic solution to the continuous-time partial differential equation governing the classic finite-horizon prediction with expert advice problem for five experts. The resulting formula proves that the adversary's $(1,0,1,0,0)$ rank strategy is globally optimal, confining the conjectured COMB strategy $(1,0,1,0,1)$ to a lower-dimensional boundary where $x_1=x_2$ and $x_3=x_4$. This resolves a central open problem in adversarial online learning, completing the exact characterization of minimax regret for $N=5$ with proofs fully certified in the Lean proof assistant.
Online learning's long-standing five-expert prediction problem is finally solved: the adversary's optimal finite-horizon policy is $(1,0,1,0,0)$, rigorously refuting the global optimality of the COMB strategy via a machine-verified Lean proof.
We give an explicit solution to the five expert prediction with expert advice partial differential equation (PDE) in the finite-time horizon setting. The solution formula establishes that the adversary's rank strategy $(1,0,1,0,0)$ is globally optimal, and the COMB strategy $(1,0,1,0,1)$ is optimal exactly on the set where $x_1=x_2$ and $x_3=x_4$. The formula is derived from the solution of the geometric-stopping problem given in our companion paper through the transform principle of Bayraktar, Ekren and Zhang, which links the two problems by a Laplace transform. Inverting the transform term by term expresses the solution through a series of Gaussian and complementary error function kernels. The optimality of $(1,0,1,0,0)$ is reduced to the signs of $41$ one-variable Gaussian series, which are certified with computer assistance by Poisson summation, first-mode domination and interval arithmetic on $1616$ rational cells. The proofs of our main theorems, certificates included, are also formalized in the Lean proof assistant.