On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies

07/25/2022
by   J. Jon Ryu, et al.
0

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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset