On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies

Abstract

This paper considers the problem of constructing a confidence sequence, which is a sequence of confidence intervals that hold uniformly over time, for estimating the mean of bounded real-valued random processes. This paper revisits the gambling-based approach established in the recent literature from a natural \emph{two-horse race} perspective, and demonstrates new properties of the resulting algorithm induced by Cover (1991)'s universal portfolio. The main result of this paper is a new algorithm based on a mixture of lower bounds, which closely approximates the performance of Cover's universal portfolio with constant per-round time complexity. A higher-order generalization of a lower bound on a logarithmic function in (Fan et al., 2015), which is developed as a key technique for the proposed algorithm, may be of independent interest.

20 pages, 3 figures. IEEE Transactions on Information Theory (to appear)

References in corpus (8)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Test Martingales, Bayes Factors and $p$-Values
• Minimum Description Length Revisited
• Efficient Online Portfolio with Logarithmic Regret
• Test Martingales for bounded random variables
• Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States
• Damped Online Newton Step for Portfolio Selection