sub-psi process

Sub-$\psi$ processes were introduced by Howard et al. (2020) in Time-uniform Chernoff bounds via nonnegative supermartingales. The core insight was that many seemingly distinct concentration inequalities can be unified by noticing that they all stem, at their core, from nonnegative supermartingales. Sub-$\psi$ processes are a way to generalize the discussion and provide concentration inequalities for large classes of distributions, while also making the bounds time-uniform at no loss (and sometimes a gain).

Let $\psi :[0,{\lambda }_{\max })\to {\mathbb{R}}_{\ge 0}$ be some function. In the scalar case, we say a pair of stochastic processes $(S_t),(V_t)$ are a sub-$\psi$ process if

$$\exp \{\lambda S_t-\psi (\lambda )V_t\}\le L_t^{\lambda }.$$

where $L_t^{\lambda }$ is a supermartingale. That is, the process $\exp \{\lambda S_t-\psi (\lambda )V_t\}$ is upper bounded by a nonnegative supermartingale.

In ${\mathbb{R}}^d$, we say $(S_t),(V_t)$ are sub-$\psi$ (where $S_t\in {\mathbb{R}}^d$ and $V_t\in {\mathbb{R}}^{d\times d})$ if for all $\nu \in {\mathbb{S}}^{d-1}$,

$$\exp \{\lambda ⟨\nu ,S_t⟩-\psi (\lambda )⟨\nu ,V_t\nu ⟩\}\le L_t^{\lambda ,\nu },$$

where $L_t^{\lambda ,\nu }$ is a nonnegative supermartingale. The extension of sub-$\psi$ processes to ${\mathbb{R}}^d$ was initially provided by Whitehouse, Wu, and Ramdas.

Examples

todo