On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
This work addresses theoretical performance guarantees for sequential prediction tasks, which is incremental as it builds on existing minimax regret analysis in the literature.
The paper tackles the problem of sequential probability assignment under logarithmic loss by analyzing minimax regret in terms of geometric quantities like covering numbers and scale-sensitive dimensions. It shows that the minimax regret without side information can be upper bounded by sequential square-root entropy, and for cases with side information, it provides matching upper and lower bounds up to log factors for certain classes.
We study the problem of sequential probability assignment under logarithmic loss, both with and without side information. Our objective is to analyze the minimax regret -- a notion extensively studied in the literature -- in terms of geometric quantities, such as covering numbers and scale-sensitive dimensions. We show that the minimax regret for the case of no side information (equivalently, the Shtarkov sum) can be upper bounded in terms of sequential square-root entropy, a notion closely related to Hellinger distance. For the problem of sequential probability assignment with side information, we develop both upper and lower bounds based on the aforementioned entropy. The lower bound matches the upper bound, up to log factors, for classes in the Donsker regime (according to our definition of entropy).