Tight Concentrations and Confidence Sequences From the Regret of Universal Portfolio

Francesco Orabona*, Kwang Sung Jun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

— A classic problem in statistics is the estimation of the expectation of random variables from samples. This gives rise to the tightly connected problems of deriving concentration inequalities and confidence sequences, i.e., confidence intervals that hold uniformly over time. Previous studies have shown that it is possible to convert the regret guarantee of an online learning algorithm into concentration inequalities, but these concentration results were not tight. In this paper, we show regret guarantees of universal portfolio algorithms applied to the online learning problem of betting give rise to new implicit time-uniform concentration inequalities for bounded random variables. The key feature of our concentration results is that they are centered around the maximum log wealth of the best fixed betting strategy in hindsight. We propose numerical methods to solve these implicit inequalities, which results in confidence sequences that enjoy the empirical Bernstein rate with the optimal asymptotic behavior while being never worse than Bernoulli-KL confidence bounds. We further show that our confidence sequences are never vacuous with even one sample, for any given target failure rate δ ∈ (0, 1). Our empirical study shows that our confidence bounds achieve the state-of-the-art performance, especially in the small sample regime.

Original languageEnglish (US)
Pages (from-to)436-455
Number of pages20
JournalIEEE Transactions on Information Theory
Volume70
Issue number1
DOIs
StatePublished - Jan 1 2024

Bibliographical note

Publisher Copyright:
© 2023 The Authors.

Keywords

  • Confidence sequence
  • regret
  • universal portfolio

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'Tight Concentrations and Confidence Sequences From the Regret of Universal Portfolio'. Together they form a unique fingerprint.

Cite this