On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies

arXiv2207.12382MaRDI QIDQ6506313FDOQ6506313

Abstract: This paper considers the problem of constructing a confidence sequence for bounded random processes. Building upon the gambling approach pioneered by Hendriks (2018) and Jun and Orabona (2019) and following the recent work of Waudby-Smith and Ramdas (2020) and Orabona and Jun (2021), this paper revisits the idea of Cover (1991)'s universal portfolio in constructing confidence sequences and demonstrates new properties, based on a natural emph{two-horse race} perspective on the gambling approach. 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 only constant per-round time complexity. A higher-order generalization of a lower bound in (Fan et al, 2015), which is invoked in the proposed algorithm, may be of independent interest.

Has companion code repository: https://github.com/jongharyu/confidence-sequence-via-gambling

This page was built for publication: On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506313)