A Short Note on a Variant of the Squint Algorithm

Haipeng Luo

cs.LGMar 3, 2026

A Short Note on a Variant of the Squint Algorithm

Authors: Haipeng Luo

Organizations: University of Southern California

Abstract

This short note describes a simple variant of the Squint algorithm of Koolen and Van Erven [2015] for the classic expert problem. Via an equally simple modification of their proof, we prove that this variant ensures a regret bound that resembles the one shown in a recent work by Freund et al. [2026] for a variant of the NormalHedge algorithm [Chaudhuri et al., 2009].

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 113 papers

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4Minimax Regret Regret Minimization
Google Research · Yale University · Google DeepMind
A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound
Apr 29, 2026Francesco OrabonaRegret Minimization Online Learning
King Abdullah University of Science and Technology (KAUST) · Thuwal, 23955-6900, Kingdom of Saudi Arabia
Tracking a Small Set of Experts in Online Convex Optimization
Oct 14, 2026Angelos Assos, Anand Brahmbhatt, Elad HazanOnline Convex Optimization
Princeton University · Google DeepMind Princeton

Sep 23, 2026J/K move · Enter open · S save

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw+3

Google Research · Yale University · Google DeepMind

Minimax Regret Regret Minimization

Open paper AskPDF arXiv

Prediction with expert advice is a fundamental problem in online learning. When the time horizon

T

is known in advance, the minimax cumulative regret over

n

experts is asymptotically

\sqrt{\frac{T \ln n}{2}}

. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to

T

, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time

t

, the best known guarantee has been

\sqrt{t \ln n}

---a factor of

\sqrt{2}

worse---and it has remained unknown whether this factor of

\sqrt{2}

is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies

R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}

simultaneously for every

t \ge 1

Abstract

Regret Minimization

Explore similar work

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

A Note on How to Remove the ln⁡ln⁡T\ln\ln TlnlnT Term from the Squint Bound

Tracking a Small Set of Experts in Online Convex Optimization

A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound