Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance

Blair Bilodeau, Dylan Foster, Daniel Roy
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:919-929, 2020.

Abstract

We consider the classical problem of sequential probability assignment under logarithmic loss while competing against an arbitrary, potentially nonparametric class of experts. We obtain tight bounds on the minimax regret via a new approach that exploits the self-concordance property of the logarithmic loss. We show that for any expert class with (sequential) metric entropy $\mathcal{O}(\gamma^{-p})$ at scale $\gamma$, the minimax regret is $\mathcal{O}(n^{\frac{p}{p+1}})$, and that this rate cannot be improved without additional assumptions on the expert class under consideration. As an application of our techniques, we resolve the minimax regret for nonparametric Lipschitz classes of experts.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-bilodeau20a, title = {Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance}, author = {Bilodeau, Blair and Foster, Dylan and Roy, Daniel}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {919--929}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/bilodeau20a/bilodeau20a.pdf}, url = {https://proceedings.mlr.press/v119/bilodeau20a.html}, abstract = {We consider the classical problem of sequential probability assignment under logarithmic loss while competing against an arbitrary, potentially nonparametric class of experts. We obtain tight bounds on the minimax regret via a new approach that exploits the self-concordance property of the logarithmic loss. We show that for any expert class with (sequential) metric entropy $\mathcal{O}(\gamma^{-p})$ at scale $\gamma$, the minimax regret is $\mathcal{O}(n^{\frac{p}{p+1}})$, and that this rate cannot be improved without additional assumptions on the expert class under consideration. As an application of our techniques, we resolve the minimax regret for nonparametric Lipschitz classes of experts.} }
Endnote
%0 Conference Paper %T Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance %A Blair Bilodeau %A Dylan Foster %A Daniel Roy %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-bilodeau20a %I PMLR %P 919--929 %U https://proceedings.mlr.press/v119/bilodeau20a.html %V 119 %X We consider the classical problem of sequential probability assignment under logarithmic loss while competing against an arbitrary, potentially nonparametric class of experts. We obtain tight bounds on the minimax regret via a new approach that exploits the self-concordance property of the logarithmic loss. We show that for any expert class with (sequential) metric entropy $\mathcal{O}(\gamma^{-p})$ at scale $\gamma$, the minimax regret is $\mathcal{O}(n^{\frac{p}{p+1}})$, and that this rate cannot be improved without additional assumptions on the expert class under consideration. As an application of our techniques, we resolve the minimax regret for nonparametric Lipschitz classes of experts.
APA
Bilodeau, B., Foster, D. & Roy, D.. (2020). Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:919-929 Available from https://proceedings.mlr.press/v119/bilodeau20a.html.

Related Material