Sharp Finite-Time Iterated-Logarithm Martingale Concentration

Martingales are indispensable in studying the temporal dynamics of stochastic processes arising in a multitude of fields [10, 14]. Particularly when such processes have complex long-range dependences, it is often of interest to concentrate martingales uniformly over time. On the theoretical side, a fundamental limit to such concentration is expressed by the law of the iterated logarithm (LIL). However, this only concerns asymptotic behavior. In many applications, it is more natural to instead consider concentration that holds uniformly over all finite times. This manuscript presents such bounds for the large classes of martingales which are addressed by Hoeffding [11] and Bernstein [8] inequalities. These new results are optimal within small constants, and can be viewed as finite-time generalizations of the upper half of the LIL.