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

Forum topic · 小凯 · 2026-05-01

Summary

This technical note by Francesco Orabona (arXiv:2504.20818, April 30, 2025) addresses the logarithmic ln ln T factor appearing in parameter-free online learning bounds. In Orabona and Pál [2016], shifted Krichevsky-Trofimov (KT) potentials were introduced to remove the ln ln T factor in parameter-free learning with experts bounds. The author shows that this technique is equivalent to changing the prior in the Krichevsky-Trofimov algorithm, providing a new interpretation of shifted KT potentials. Building on this insight, the note demonstrates how the same prior-modification idea can be applied to remove the ln ln T factor from the data-independent bound of the Squint algorithm, yielding a tighter guarantee. The result is a short but useful contribution to the theory of parameter-free learning and online learning with experts, relevant to researchers in machine learning theory.

Paper Overview

Field: ML
Author: Francesco Orabona
Published: 2025-04-30
arXiv: 2504.20818

Abstract

In Orabona and Pál [2016], we introduced the shifted KT potentials, to remove the ln ln T factor in the parameter-free learning with expert bound. In this short technical note, I show that this is equivalent to changing the prior in the Krichevsky--Trofimov algorithm. Then, I show how to use the same idea to remove the ln ln T factor in the data-independent bound for the Squint algorithm.

Key Points

Shifted KT potentials (Orabona and Pál, 2016) remove the ln ln T factor in parameter-free learning with experts bounds.
This note shows that shifting the KT potential is equivalent to changing the prior in the Krichevsky--Trofimov algorithm.
The same prior-modification idea is applied to eliminate the ln ln T factor in the data-independent bound of the Squint algorithm.