The Price of a Few Comparisons - Sharp Probe-Complexity Thresholds for Constant Regret in Online Quadratic Optimization

We study full-information online quadratic optimization on $[-1,1]$ against an oblivious adversary, augmented by a hard budget of $k$ comparison probes: on at most $k$ rounds of the learner's choosing, before committing to its decision, the learner may name two points and learn which has smaller loss in the current round. Without probes the minimax regret is $\\Theta(\\log T)$. Our main result is a sharp threshold for the budget needed to make the regret constant: $\\Theta(\\log T\\cdot\\log\\log T)$ probes are necessary and sufficient. Both directions are new; the lower bound introduces a multi-scale one-bit information bottleneck argument that rules out the natural $\\Theta(\\log T)$ guess. We further determine the entire probe-regret trade-off at the level of rates, together with a universal constant floor. We then map the boundary of the phenomenon along four axes. Timing: if the $k$ probe rounds are instead drawn uniformly at random by the environment and announced in advance — the schedule of the closest prior work — the minimax regret becomes $\\Theta(1+\\ln(T/k))$, so constant regret requires a linear budget; adaptivity of probe timing is an exponentially valuable resource. Noise: if each comparison answer is flipped independently with probability $\\delta\\in(0,1/2)$, the threshold changes asymptotic order to $\\Theta_\\delta((\\log T)^2)$, driven by a rare-event bottleneck; the limits $\\delta\\to 0$ and $T\\to\\infty$ do not commute. Dimension: on the Euclidean ball in $\\mathbb{R}^d$ the threshold is $\\Theta(d\\cdot\\log T\\log\\log T)$ for fixed $d$, with an unavoidable $\\Omega(\\log d)$ regret floor even with a probe in every round. Curvature: for centered strongly convex, smooth losses the same threshold persists, while for linear losses probes are essentially useless: with $k=o(\\sqrt T)$ probes the regret remains $\\Theta(\\sqrt T)$. Centering plus curvature is thereby identified as the precise source of the phenomenon. Three constant-level gaps remain open, which we state explicitly: the two exponents in the trade-off curve, the optimal condition-number dependence, and the leading constants in the timing and noise thresholds.