confidence sequences via conjugate mixtures

Suppose you are trying to generate a confidence sequence for a parameter $\mu$. Suppose you can write down a supermartingale of the form $M_t(\lambda )=\exp \{\lambda S_t(\mu )-\psi (\lambda )V_t\}$ for $\mu$ (eg, a sub-psi process based on an exponential inequality), where $(S_t(\mu ))$ is some process which is a function of $\mu$. $(S_t)$ is often the martingale $S_t(\mu )={\sum }_{i\le t}(X_i-\mu )$.

One option is to use a predictable sequence $({\lambda }_t{)}_{t\ge 1}$, employing a different ${\lambda }_t$ at each time step. See confidence sequences via predictable plug-ins.

Another approach, that of conjugate mixtures, is to integrate over $\lambda$. Suppose $M_t(\lambda$) is a supermartingale for all $\lambda \in \Lambda$. Then

$$N_t:={\int }_{\lambda }{M}_t(\lambda )\rho (\text{d}\lambda ),$$

is a supermartingale for any distribution $\rho$ over $\Lambda$ by Tonelli’s theorem. (For intuition take $\rho$ to be a discrete distribution). Applying Ville’s inequality to $N_t$ then yields a (sometimes implicit) CS for $\mu$.

Various distributions $\rho$ were studied by Howard et al, most of them giving implicit CSs. One nice exception is Robbins’ Gaussian mixture.

Robbins’ Gaussian mixture

If $X_1,X_2,\dots$ are $\sigma$-sub-Gaussian with conditional means ${\mu }_i=\mathbb{E}[X_i|X_1^{i-1}]$, then $M_t(\lambda )={\prod }_{i\le t}\exp \{\lambda (X_i-{\mu }_i)-{\lambda }^2{\sigma }^2/2\}$ is the standard sub-Gaussian supermartingale then taking $\rho$ to be Gaussian with mean 0 and variance $a^2$ gives the following bound:

$$\mathbb{P}\left(\exists t\ge 1:\left|\sum _{i\le t}{X}_i-{\mu }_i\right|\ge \sigma \sqrt{\frac{2(t{a}^2+1)}{t^2{a}^2}\log \left(\frac{\sqrt{t{a}^2+1}}{\alpha }\right)}\right)\le \alpha .$$

Robbins noted this CS (in a slightly less general sense) in the 1970s. This has been generalized to vector-valued random variables.

Refs

• Conjugate mixtures, Lecture notes by Aaditya Ramdas.