stitching for LIL rates

When constructing confidence sequences using either the method of mixtures or predictable plug-ins, one often ends up with rates on the order of $\sqrt{\log (t)/t}$. While this is clearly shrinking to zero at $t\to \infty$, it’s worth asking if it’s shrinking to zero at an optimal rate. If the problem satisfies a LIL (laws of the iterated logarithm), then the optimal rate is $\sqrt{\log \log (t)/t}$.

Obtaining bounds that shrink at this rate can be done via stitching (see time-uniform, nonparametric, nonasymptotic confidence sequences). This involves deploying distinct bounds over different epochs, and then taking a union bound to ensure time-uniform coverage. Eg, one might consider the epochs $[2^j,2^{j+1})$, and deploy an estimator ${\hat{\mu }}_t(j)$ with the guarantee

$$\mathbb{P}(\exists t\in [2^j,2^{j+1}):|{\hat{\mu }}_t(j)-{\theta }^{\ast }|\ge B(t,j))\le {\delta }_j,$$

where ${\theta }^{\ast }$ is some parameter of interest. If ${\sum }_j{\delta }_j\le \delta$, then we can get time-uniform coverage with probability $1-\delta$ for all $t\ge 1$ via a union bound. The goal is then to show that $B(t,j)$ shrinks at the desired logarithm rate. There are many examples of this, e.g. here, here, here, and here.

Duchi and Haque applied stitching to non-time-uniform estimator and still achieve iterated logarithm rates. In other words, they give a general reduction from fixed-time bounds to time-uniform bounds at the loss of only an iterated logarithm rate. In particular, they show that if for all $n\ge 1$, there exists a fixed-time estimator ${\hat{\theta }}_n$ of ${\theta }^{\ast }$ such that

$$\mathbb{P}(\Vert {\hat{\theta }}_n-\mu \Vert \le F(\log (1/\delta ),n))\ge 1-\delta ,$$

for some function $F:{\mathbb{R}}_{\ge 0}\times \mathbb{N}\to {\mathbb{R}}_{\ge 0}$, then the estimator ${\tilde{\theta }}_n={\hat{\theta }}_{g(n)}$ where $g(n)=\lfloor {\log }_2(n)\rfloor$ satisfies

$$\mathbb{P}(\forall n\ge 1:\Vert {\tilde{\theta }}_n-\mu \Vert \le F(2\log \log (n)+\log (1/\delta )+1/2,n/2))\ge 1-\delta .$$

That is, by updating the estimator only once every $2^k$ timesteps for $k\in \mathbb{N}$, we can transform any fixed-time estimator into a time-uniform estimator at an iterated logarithm cost.

While an elegant theoretical construction, it is somewhat dissatisfying for practical purposes as we only update the estimator every $2^j$ timesteps. If data collection stops at some time $n$ for $2^j<n<2^{j+1}$, then we must discard observations (indeed, possibly as many as $n/2-1$ observations). This is unlike the examples above, which use time-uniform estimates within each epoch, which allow the estimator to be updated after observation is received.