An iterated-logarithm price of anytime validity for log-optimal e-processes: Lean formalization

7 The iterated-logarithm rate

These are the results of Section 4.3 of the paper, of the end of Section S1.6, of Section S1.7, and of Section S2.5 on the mixtures with \(\rho ^2{\lt}1-s^2\), together with the frontier of Section 1. A ratio such as \(\Gamma _T/\log \log T\) is a quotient in \([-\infty ,\infty ]\), so that a limit statement also states that the numerator is eventually finite.

Definition 78 The e-process of Proposition 3(ii)
✓

For \(j\ge 1\), let \(T_j=\lceil \exp (e^j)\rceil \), \(q_j=1+s^2/\{ (1-s^2)(j+1)\} \), and \(u_j=\{ (j+1)/(s^2j)\} (2+2\log T_j/\log q_j)^{1-s^2j/(j+1)}\). Let \(E_t=\sum _{j=1}^\infty E^{\star }_{t\wedge T_j}/\{ j(j+1)u_j\} \).

Definition 79 The minimax regret in the worst case over the location
✓

For \(\mu \in \mathbb {R}\), \(R^\mu _t\) is the regret defined by (2) and (3) with \(Q_\mu \) in place of \(Q\), with any numéraires of \(Q_\mu \), and the minimax regret in the worst case over \(\mu \) is \(\inf _{(E_t)}\max _{0\le t\le T}\sup _{\mu \in \mathbb {R}}R^\mu _t(E_t)\).

Lemma 80 The upper bound of Proposition 3(i)
✓

Let \(s\in (0,1)\). For every \(b{\gt}1-s^2\), \(\log \eta _T{\lt}b\log \log T\) for all large \(T\).

Proof ▶

Lemma S3 with \(q\) chosen so that \((1-s^2)q{\lt}b\), which replaces letting \(q\to 1\); the term \(\log (2+2\log T/\log q)\) is bounded explicitly by \(\log \log T+\log (2+2/\log q)\) for \(T\ge 3\).

Let \(s\in (0,1)\) and \(\rho {\gt}0\), and let \(\Gamma _T\) satisfy (S9) for every admissible \(r\), \(K\), \(T\), and \(c\). Then, for every \(a{\lt}1-s^2\), \(a\log \log T{\lt}\Gamma _T\) for all large \(T\).

Proof ▶

The choices of the paper: \(c'=s(2\log K+4\log \log K)^{1/2}\), \(c=(c'+r^{-1/2})/(1-r^{-1/2})\), and \(K=\lfloor \log T/\log r\rfloor \). The \(O\) and \(o\) terms of the paper are explicit: with \(\delta =1-r^{-1/2}\), the right-hand side of (S9) is at least \((1-s^2/\delta ^2)\log K-28(\log K)^{1/2}-C_0\), and \(\log \log T-\log (2\log r)\le \log K\le \log \log T\) when \(\log T/\log r\ge 6\). The ratio \(r\) is chosen with \(1-s^2/\delta ^2{\gt}\max (a,0)\), so that the case of a coefficient that is not positive, which the paper treats with \(\Gamma _T\ge 0\), does not arise.

Let \(s\in (0,1)\) and \(\rho ^2\ge 1-s^2\). Then \(\eta _{T_j}\le u_j\), the process \((E_t)\) is an e-process, adapted to \((\mathcal{G}_t)\), and \(\limsup _{t\to \infty }R_t(E_t)/\log \log t\le 1-s^2\). If, moreover, \(\Gamma _T/\log \log T\to 1-s^2\), then \(\limsup _{t\to \infty }R_t(E_t)/\log \log t\ge 1-s^2\).

Proof ▶

As in Section S1.6. Lemma S3 with \(T=T_j\) and \(q=q_j\) gives \(\eta _{T_j}\le u_j\), so that \(\mathrm{E}_\theta (E_{\tau \wedge n})\le 1\). The paper shows that \(E^{\star }_t\to 0\) almost surely by the strong law of large numbers; here, the nonnegative martingale \((E^{\star }_t)\) with respect to \((\mathcal{G}_t)\) converges almost surely by Doob’s theorem, which suffices for \(E_t\) to converge almost surely, by dominated convergence for the series over \(j\), and Fatou’s lemma gives \(\mathrm{E}_\theta (E_\tau )\le 1\). For the upper limit, \(j=\lfloor \log \log t\rfloor +1\) and the explicit bound \(\log \{ j(j+1)u_j\} \le (1-s^2)j+4\log (j+2)+C\). For the lower limit, the paper takes a maximizer \(t_T\) of \(R_t(E_t)\) over \(t\le T\); here, the argument is by contradiction with \(\Gamma _T\le \max _{t\le T}R_t(E_t)\).

Let \(s\in (0,1)\) and \(\rho ^2\ge 1-s^2\). (i) As \(T\to \infty \), \(\Gamma _T/\log \log T\to 1-s^2\) and \(\log \eta _T/\log \log T\to 1-s^2\). (ii) The process \((E_t)_{t\ge 0}\) of Definition 78 is an e-process with \(\limsup _{t\to \infty }R_t(E_t)/\log \log t=1-s^2\).

Proof ▶

The upper bounds follow from \(\Gamma _T\le \log \eta _T\) (Proposition 1(iii)) and Lemma 80, and the lower bounds from Lemma S6 and Lemma 81, with the numéraires of Proposition 2. Part (ii) is Lemma 82.

Let \(s\in (0,1)\) and \(\rho {\gt}0\), and let \(Q=\int Q_\mu \mathrm{N}(0,\rho ^2)(\mathrm{d}\mu )\), without the condition \(\rho ^2\ge 1-s^2\). Numéraires of \(Q\) exist, by the theorem of Larsson, Ramdas and Ruf, and, for any numéraires of \(Q\), \(\Gamma _T/\log \log T\to 1-s^2\) and \(\log \eta _T/\log \log T\to 1-s^2\) as \(T\to \infty \).

Proof ▶

As in Section S2.5. For \(t\ge t_\rho \), the proof of Proposition 2 applies at the horizon \(t\), so that \(\Pi _t=\prod _{i=2}^t\ell (Y_i)\) is the numéraire, and the differences \(d_t\) between the optimal e-power and \(\mathrm{E}_Q(\log \Pi _t)\) are bounded. The paper takes \(C=\max _{t{\lt}t_\rho }d_t\) and \(t_\rho =\lceil (1-s^2)/\rho ^2\rceil \); here, \(C=\sum _{t{\lt}t_\rho }|d_t|\) and \(t_\rho =\lceil (1-s^2)/\rho ^2\rceil +1\). The e-process \((\Pi _{t\wedge T}/\eta '_T)_{t\ge 0}\), with \(\eta '_T\) the value of Lemma 2(ii), comes from Proposition 1(iii) for the mixture with \(\rho =1\), since the e-process property does not involve the alternative, and gives \(\Gamma _T\le C+\log \eta '_T\). The lower bound is Lemma S6, which holds for every \(\rho {\gt}0\), with Lemma 81. For the limit of \(\log \eta _T\), Proposition 1(iii) gives \(\Gamma _T\le \log \eta _T\), and \(\eta _T\le t_\rho +\eta '_T\): for \(t\ge t_\rho \), the numéraire equals \(\Pi _t\) \(Q\)-almost surely, hence \(P_\theta \)-almost surely, since \(P_{\theta ,t}\ll Q_t\) through the distributions of \((\bar X_t,Y^t)\), and, for \(t{\lt}t_\rho \), its expectation under every null distribution is at most one.

Proposition 85 Proposition 3(i) for every \(\rho {\gt}0\)
✓

Let \(s\in (0,1)\) and \(\rho {\gt}0\). For any numéraires of \(Q\), \(\Gamma _T/\log \log T\to 1-s^2\) and \(\log \eta _T/\log \log T\to 1-s^2\) as \(T\to \infty \) (Section 4.3).

Proof ▶

Proposition S5, which Section 4.3 cites.

Let \(s\in (0,1)\) and \(\rho ^2\ge 1-s^2\). (i) For \(T\ge 1\), \(\kappa +\Gamma _T\le \inf _{(E_t)}\max _{0\le t\le T}\sup _{\mu \in \mathbb {R}}R^\mu _t(E_t)\le \kappa +\log \eta _T\), and the middle term divided by \(\log \log T\) tends to \(1-s^2\) as \(T\to \infty \). (ii) The e-process \((E_t)\) of Proposition 3(ii) satisfies \(\sup _{\mu \in \mathbb {R}}R^\mu _t(E_t)=\kappa +R_t(E_t)\) for \(t\ge 1\), so that \(\limsup _{t\to \infty }\sup _{\mu \in \mathbb {R}}R^\mu _t(E_t)/\log \log t=1-s^2\).

Proof ▶

As in Section S1.7. Every stopping time \(\tau \) of \((\mathcal{F}_t)\) satisfies \(\tau =0\) everywhere or \(\tau \ge 1\) everywhere, since \(\mathcal{F}_0\) is trivial, so that \(E_0\) may be replaced by one. For the lower bound, the paper averages \(R^\mu _t(E)\) over \(\mu \sim \mathrm{N}(0,\rho ^2)\); here, \(R^\mu _t(E)\le r\) for every \(\mu \) implies \(\kappa +R_t(E)\le r\), by averaging the e-powers \(\mathrm{E}_{Q_\mu }(\log E)\ge t\kappa -r\), which is the same computation with a bound in place of the average. For the upper bound, the e-process \((E^{\star }_{t\wedge T}/\eta _T)_{t\ge 0}\) depends on the data only through the \(Y_i\), and Lemma 60 gives its regrets against every \(Q_\mu \); so does the e-process of Proposition 3(ii), which gives part (ii).

Lemma 87 The growth of the minimax regret
✓

For \(s\in (0,1)\), the minimax regret in the worst case over \(\mu \) tends to infinity, and, for every \(\varepsilon {\gt}0\), its ratio to \((\log T)^\varepsilon \) tends to zero, while the optimal e-power \(T\kappa \) of each \(Q_\mu \) grows linearly (Section 4.3).

Proof ▶

Theorem 1 with \(\rho =1\); the minimax regret in the worst case over \(\mu \) lies between zero and \(\kappa +\log \eta _T{\lt}\kappa +\log \log T\) for large \(T\), and \(\log x=o(x^\varepsilon )\). The optimal e-power is Proposition S4(i).

Theorem 88 The frontier of the Gaussian location problem
✓

For every \(s{\gt}0\), the minimax regret in the worst case over \(\mu \) is bounded uniformly in \(T\) if and only if \(s\ge 1\), that is, if and only if the alternatives have at least the variance of the null (Section 1).

Proof ▶

For \(s{\lt}1\), Lemma 87; for \(s\ge 1\), Lemma 71.

Proposition 89 When the minimax regret tends to infinity
✓

For every \(s{\gt}0\) and \(\mu \), \(\Gamma _T\) does not tend to infinity for the alternative \(Q_\mu \). For the mixtures \(Q\) with \(\rho \ge 0\), \(\Gamma _T\to \infty \) exactly when \(s{\lt}1\) and \(\rho {\gt}0\), however small \(\rho \) is (Section S2.5).

Proof ▶

For \(Q_\mu \), Proposition S4. For the mixtures, Proposition S5 if \(s{\lt}1\) and \(\rho {\gt}0\), Proposition 4 if \(s\ge 1\), and Proposition S4 if \(\rho =0\), since the mixture with \(\rho =0\) is \(Q_\mu \) with \(\mu =0\). Propositions S4 and 4 are stated for specific numéraires and transfer to any numéraires by uniqueness, since the minimax regret depends on the numéraires only up to \(Q\)-null sets.