On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912289217576960 |
|---|---|
| author | Jia, Zeyu Polyanskiy, Yury Rakhlin, Alexander |
| author_facet | Jia, Zeyu Polyanskiy, Yury Rakhlin, Alexander |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17823 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy Jia, Zeyu Polyanskiy, Yury Rakhlin, Alexander Machine Learning Information Theory 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). |
| title | On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy |
| topic | Machine Learning Information Theory |
| url | https://arxiv.org/abs/2503.17823 |