Proof. Because \(f\) is differentiable and strongly convex, \(\boldsymbol{x}^*\) is the unique stationary point of \(f\). It is therefore enough to prove that \(\boldsymbol{x}_t\ne\boldsymbol{x}^*\) for all \(t\le T\) almost surely.

The claim holds at \(t=0\) by assumption. Conditional on the history immediately before sampling \(\boldsymbol{u}_t\), suppose that \(\boldsymbol{x}_t\ne\boldsymbol{x}^*\). The update displacement in Algorithm 1 is a scalar multiple of the Gaussian direction \(\boldsymbol{u}_t\). Hence the identity \(\boldsymbol{x}_{t+1}=\boldsymbol{x}^*\) would require \(\boldsymbol{u}_t\in\operatorname{span}\{\boldsymbol{x}_t-\boldsymbol{x}^*\}\). This is a one-dimensional subspace, and the conditional Gaussian law of \(\boldsymbol{u}_t\) assigns it probability zero when \(d\ge2\). A finite induction over \(t=0,\dots,T-1\) proves the result. ◻

Proof. The iterate \(\boldsymbol{x}_t\) is \(\mathcal{F}_t^{-}\)-measurable, and Algorithm 1 samples \(\boldsymbol{u}_t\) and a fresh oracle sample \(\xi_t\) independently at iteration \(t\). Hence conditioning on either \(\mathcal{F}_t^{-}\) or \(\mathcal{F}_t^{u}\) fixes \(\boldsymbol{x}_t\) (and, in the latter case, \(\boldsymbol{u}_t\)) while leaving \(\xi_t\) distributed as a fresh oracle sample. Assumption 2 gives the conditional mean-zero identity, and Assumption 3, applied pointwise at the realized \(\boldsymbol{x}_t\), gives the displayed conditional exponential-moment bound. ◻

Proof. The displayed lower bound on \(T+T_0\) makes the right-hand side of Eq. ?? no larger than \(\varepsilon\). The high-dimensional condition ensures that Corollary 1 applies at the selected horizon, so its probability guarantee carries over directly. Because \(T_0=\Theta(dL/\mu)\) and the remaining dependence on \(T\) and \(\delta\) enters logarithmically through \(\Lambda\) and \(\Gamma_T(\delta)\), suppressing fixed problem parameters and logarithmic factors yields \(\widetilde{\mathcal{O}}(d/\varepsilon)\) iterations whenever an admissible horizon exists. Each iteration makes one two-point oracle query, that is, two function evaluations using the same sample. ◻

Proof of Theorem 1. Let \(\mathcal{G}_T\) be the event whose probability is at least \(1-\delta\) by Lemma 14. On this event, the weighted-suffix events \(\mathcal{E}_{\rho_K}\), \(\mathcal{E}_{\rho_{K,k}}\), and the norm event \(\mathcal{E}_u\) hold for all relevant \(K,k\). Also, for every \(K\le T\), the product-linear implication \(\mathcal{L}_K(\bar A_K)\) holds with the deterministic envelopes \(\bar A_K\) specified in Lemma 14. In addition, the terminal nonnegative controls \(\widehat{\mathcal{E}}_{V_T}\), \(\mathcal{E}_{Q_T}\), and \(\mathcal{E}_{\alpha_T}\) hold. Moreover, all logarithmic factors in the auxiliary lemmas are bounded by \(c_\delta\Lambda=\Gamma_T(\delta)\), and Lemma 13 holds for every \(K\le T\).

We prove the deterministic implication on \(\mathcal{G}_T\) by induction on \(K\).

4.5.0.1 Base case.

For \(K=0\), the first term in the definition of \(\mathcal{C}\) in Eq. ?? gives \[\Delta_0 \le \frac{\mathcal{C}d \Theta_T}{T_0}.\]

4.5.0.2 Induction hypothesis.

Fix any \(K\in\{1,\dots,T\}\), and assume that, for every \(k=0,\dots,K-1\), \[\label{eq:IH95main} \Delta_k \le \frac{\mathcal{C}d \Theta_T}{T_k}.\tag{7}\]

On \(\mathcal{G}_T\), Eq. ?? in Lemma 3 holds. We bound its four terms separately.

4.5.0.3 Initial term.

By Eq. ?? , \(\rho_K\Delta_0\le c_\rho(T_0/T_K)\Delta_0\). Hence, since \(\mathcal{C}\ge 8c_\rho T_0 \Delta_0/(d\Theta_T)\) in Eq. ?? , we have \[\label{eq:init95absorb} \rho_K \Delta_0 \leq c_\rho \frac{T_0}{T_K}\Delta_0 \le \frac{\mathcal{C}}{8}\frac{d \Theta_T}{T_K}.\tag{8}\]

4.5.0.4 Terminal comparison for nonnegative suffix terms.

For \(k<K\le T\), the definitions of \(\rho_{K,k}\) and \(\rho_{T,k}\) give \[\rho_{K,k} = \rho_{T,k} \exp\left(\sum_{t=K}^{T-1}\frac{1}{T_t}\right).\] Since \[\sum_{t=K}^{T-1}\frac{1}{T_t} \le 1+\log\frac{T_T}{T_K},\] there is a universal constant \(C\) such that \[\label{eq:terminal95suffix95compare} \rho_{K,k}\le C\frac{T_T}{T_K}\rho_{T,k}, \qquad 0\le k<K\le T,\tag{9}\] and hence \[\label{eq:terminal95suffix95compare95sq} \rho_{K,k}^2\le C \left(\frac{T_T}{T_K}\right)^2\rho_{T,k}^2, \qquad 0\le k<K\le T.\tag{10}\] Thus any nonnegative suffix-weighted sum at terminal time \(K\) is bounded by the corresponding terminal-\(T\) sum, with the appropriate power of \(T_T/T_K\).

4.5.0.5 Signed linear product term.

The linear term in Lemma 3 is multiplied by the actual suffix product \(\Pi_{K,k}\), not by the deterministic upper bound \(\rho_{K,k}\). Since this term is signed, the replacement \(\Pi_{K,k}\le\rho_{K,k}\) is not order-preserving at the level of the linear sum. Instead, the event in Lemma 14 includes the bound from Lemma 7, which controls the signed product-linear sum with the actual product \(\Pi_{K,k}\). It remains to verify the variance-proxy condition \(A_K^\Pi\le\bar A_K\).

Set \[\bar\Delta_k=\frac{\mathcal{C}d\Theta_T}{T_k}, \qquad k=0,\dots,T-1,\] so that \(\Delta_k\le\bar\Delta_k\) throughout the induction range \(k<K\). Let \(z_k=(\boldsymbol{u}_k^\top\nabla f(\boldsymbol{x}_k))/\|\nabla f(\boldsymbol{x}_k)\|\). On \(\mathcal{E}_u\), using \(\Pi_{K,k}\le\rho_{K,k}\), \(L\)-smoothness, and the induction hypothesis, \[A_K^\Pi \le \frac{4L}{d} \sum_{k=0}^{K-1} \frac{\rho_{K,k}^2}{T_k^2}\bar\Delta_k z_k^2.\] For the terminal weights in Lemma 9, write \[\bar W_{T-1}^{(T)} := \sum_{k=0}^{T-1}\frac{\rho_{T,k}^2}{T_k^2}\bar\Delta_k, \qquad \bar Q_{T-1}^{(T)} := \sum_{k=0}^{T-1} \left(\frac{\rho_{T,k}^2}{T_k^2}\bar\Delta_k\right)^2, \qquad \bar M_{T-1}^{(T)} := \max_{0\le k\le T-1} \frac{\rho_{T,k}^2}{T_k^2}\bar\Delta_k.\] The squared terminal comparison in Eq. 10 and the terminal event \(\widehat{\mathcal{E}}_{V_T}\) give \[A_K^\Pi \le C \frac{L}{d} \left(\frac{T_T}{T_K}\right)^2 \left[ \bar W_{T-1}^{(T)} + \sqrt{\bar Q_{T-1}^{(T)}\Gamma_T(\delta)} + \bar M_{T-1}^{(T)}\Gamma_T(\delta) \right].\] By Lemma 13 and Lemma 19, \[\bar W_{T-1}^{(T)} \le \frac{\mathcal{C}d c_\rho^2\Theta_T\Lambda}{T_T^2}, \qquad \bar Q_{T-1}^{(T)} \le \frac{2\mathcal{C}^2d^2c_\rho^4\Theta_T^2}{T_T^4T_0}, \qquad \bar M_{T-1}^{(T)} \le \frac{\mathcal{C}d c_\rho^2\Theta_T}{T_T^2T_0}.\] Using \(\Gamma_T(\delta)=c_\delta\Lambda\) and \(\Lambda\ge1\), the three terms after multiplying by \((L/d)(T_T/T_K)^2\) are bounded respectively by \[C\frac{L\mathcal{C}c_\rho^2\Theta_T\Lambda}{T_K^2}, \qquad C\frac{L\mathcal{C}c_\rho^2\Theta_T}{T_K^2} \sqrt{\frac{c_\delta\Lambda}{T_0}}, \qquad C\frac{L\mathcal{C}c_\rho^2\Theta_T\Lambda}{T_K^2} \frac{c_\delta}{T_0}.\] Since \(\sqrt{c_\delta\Lambda/T_0}\le C\Lambda(1+c_\delta/T_0)\), these estimates imply \[A_K^\Pi \le C \frac{L\mathcal{C}c_\rho^2\Theta_T\Lambda}{T_K^2} \left(1+\frac{c_\delta}{T_0}\right) \le \bar A_K,\] after choosing the universal constant \(C_A\) in Lemma 14 large enough. Hence \(\mathcal{L}_K(\bar A_K)\) reduces to \(\mathcal{E}_{Y_K}^{\Pi}(\bar A_K)\). Therefore, on \(\mathcal{G}_T\), \[\label{eq:Y95up} \frac{4d}{\mu} \sum_{k=0}^{K-1} \Pi_{K,k} \frac{ \nabla f(\boldsymbol{x}_k)^\top\boldsymbol{u}_k\,\boldsymbol{u}_k^\top\boldsymbol{e}_k }{ T_k\|\boldsymbol{u}_k\|^2 } \le C\frac{d\sigma c_\rho\Theta_T}{\mu T_K} \sqrt{ L\mathcal{C} \left(1+\frac{c_\delta}{T_0}\right)} \stackrel{\eqref{eq:cC}}{\le} \frac{\mathcal{C}d\Theta_T}{8T_K}.\tag{11}\]

4.5.0.6 Quadratic-noise term.

We invoke Lemma 11 only at the terminal index \(T\). On \(\mathcal{G}_T\), using Eq. ?? , Lemma 13, and Lemma 19, \[\begin{align} \sum_{k=0}^{T-1} \frac{ \rho_{T,k} }{ T_k^2} \cdot \frac{|\boldsymbol{u}_k^\top \boldsymbol{e}_k|^2}{\left\|\boldsymbol{u}_k\right\|^2} &\le \frac{2\sigma^2}{d} \sum_{k=0}^{T-1}\frac{\rho_{T,k}}{T_k^2} + 2\sigma^2 \log\frac{1}{\delta_T^{(Q)}} \max_{0\le k\le T-1}\frac{\rho_{T,k}}{T_k^2} \\ &\le \frac{2\sigma^2 c_\rho\Lambda}{dT_T} + \frac{2\sigma^2 c_\rho c_\delta\Lambda}{T_TT_0}. \end{align}\] Therefore Eq. 9 implies, for the current induction terminal time \(K\), \[\label{eq:Q95up} \begin{align} &\frac{32Ld^2}{\mu^2} \sum_{k=0}^{K-1} \frac{\rho_{K,k}}{T_k^2} \cdot \frac{|\boldsymbol{u}_k^\top \boldsymbol{e}_k|^2}{\|\boldsymbol{u}_k\|^2} \leq C\frac{Ld\sigma^2c_\rho\Lambda}{\mu^2T_K} \left( 1 + \frac{d c_\delta}{T_0} \right) \stackrel{\eqref{eq:cC}}{\leq} \frac{\mathcal{C}\cdot d\cdot \Theta_T}{8T_K}. \end{align}\tag{12}\]

4.5.0.7 Smoothing-bias term.

Let \[a_k:= \frac{dL^2}{2\mu T_k} + \frac{4d^2L^3}{\mu^2T_k^2}.\] We invoke Lemma 12 only at the terminal index \(T\). On \(\mathcal{G}_T\), write \[A_T:=\sum_{k=0}^{T-1}\rho_{T,k}a_k,\qquad B_T:=\sum_{k=0}^{T-1}\rho_{T,k}^2a_k^2,\qquad M_T:=\max_{0\le k\le T-1}\rho_{T,k}a_k.\] Then Lemma 12 and Eq. ?? give \[\sum_{k=0}^{T-1}\rho_{T,k}a_k\|\boldsymbol{u}_k\|^2 \le Cd\left(A_T+\sqrt{\Gamma_T(\delta)B_T} +\Gamma_T(\delta)M_T\right).\] Using \(\rho_{T,k}\le c_\rho T_k/T_T\), Lemma 19, \(T_T\ge T_0\), and \(\Gamma_T(\delta)=c_\delta\Lambda\), the three terms satisfy \[\begin{align} dA_T &\le Cc_\rho d \left(c_1+\frac{c_2\Lambda}{T_0}\right), \\ d\sqrt{\Gamma_T(\delta)B_T} &\le Cc_\rho d\sqrt{c_\delta\Lambda} \left(\frac{c_1}{\sqrt{T_0}}+\frac{c_2}{T_0^{3/2}}\right), \\ d\Gamma_T(\delta)M_T &\le Cc_\rho d c_\delta\Lambda \frac{1}{T_0} \left(c_1+\frac{c_2}{T_0}\right). \end{align}\] Substituting \(c_1=dL^2/(2\mu)\), \(c_2=4d^2L^3/\mu^2\), and \(T_0=32dL/\mu\), and using \(d,\Lambda\ge1\) and \(\sqrt{c_\delta\Lambda}\le \Lambda(1+c_\delta)\), yields \[\sum_{k=0}^{T-1}\rho_{T,k}a_k\|\boldsymbol{u}_k\|^2 \le Cc_\rho d^2\Lambda(1+c_\delta) \left(1+\frac{L^2}{\mu}+\frac{L^3}{\mu^2}\right),\] after increasing the universal numerical constant if necessary. Hence, by Eq. 9 , \[\label{eq:alp95up} \alpha^2 \sum_{k=0}^{K-1}\rho_{K,k} \left( \frac{dL^2}{2\mu T_k} + \frac{4d^2L^3}{\mu^2 T_k^2} \right)\|\boldsymbol{u}_k\|^2 \leq C\alpha^2\frac{T_T}{T_K} c_\rho d^2\Lambda(1+c_\delta) \left(1+\frac{L^2}{\mu}+\frac{L^3}{\mu^2}\right) \leq \frac{\mathcal{C}d \Theta_T}{8 T_K},\tag{13}\] where the last inequality uses \(\alpha^2=1/(dT_T)\), \(\Theta_T=\Lambda\Gamma_T(\delta)\), and the last term in the definition of \(\mathcal{C}\) in Eq. ?? , after increasing the universal numerical constant if necessary.

4.5.0.8 Conclusion of the induction step.

Combining Eq. ?? , 8 , 11 , 12 , and 13 , we conclude that \[\Delta_K \le \left( \frac{\mathcal{C}}{8} + \frac{\mathcal{C}}{8} + \frac{\mathcal{C}}{8} + \frac{\mathcal{C}}{8} \right) \frac{ d\Theta_T}{T_K} \le \mathcal{C}\frac{ d\Theta_T}{T_K}.\] This proves the induction step. Since the induction is deterministic on \(\mathcal{G}_T\), it holds simultaneously for all \(K\le T\). Taking \(K=T\) yields the first inequality in Eq. ?? . To obtain the displayed big-\(\mathcal{O}\) form, multiply each term in the maximum defining \(\mathcal{C}\) by \(d\Theta_T/(T+T_0)\), use \(\Theta_T=\Lambda\Gamma_T(\delta)\), \(T_0=32dL/\mu\), and \(c_\rho\ge1\), and absorb fixed problem parameters and universal numerical factors into the implicit constant. ◻

Proof of Corollary 1. By Eq. ?? , with probability at least \(1-\delta\), \[f(\boldsymbol{x}_T)-f(\boldsymbol{x}^*) \le C \left( \frac{c_\rho T_0\Delta_0}{T+T_0} + c_\rho^2 \frac{d\Lambda\Gamma_T(\delta)}{T+T_0} \left(1+\frac{\Gamma_T(\delta)}{T_0}\right) \right).\] By the definition of \(c_\rho\), the assumption \(T_0\gtrsim\Gamma_T(\delta)\) gives \(c_\rho=\mathcal{O}(1)\). Absorbing this numerical bound into the constant yields Eq. ?? . The final \(\widetilde{\mathcal{O}}(d/T)\) display is the same estimate with fixed problem parameters and logarithmic factors suppressed. ◻

Proof. By the lower-tail part of Lemma 15, for each \(i\), \[\Pr\left( X_i\le k-2\sqrt{k\tau} \right)\le e^{-\tau}, \qquad \tau>0.\] Take \(\tau=\log N+\log(1/\delta)\). A union bound over \(i=1,\dots,N\) gives \[\Pr\left( \min_{1\le i\le N}X_i \le k-2\sqrt{k\left(\log N+\log\frac{1}{\delta}\right)} \right) \le Ne^{-\tau} =\delta.\] ◻

Proof. By the fundamental theorem of calculus, \[\frac{f(\boldsymbol{x}+\alpha\boldsymbol{u};\xi)-f(\boldsymbol{x}-\alpha\boldsymbol{u};\xi)}{2\alpha} = \frac{1}{2}\int_{-1}^{1} \boldsymbol{u}^\top\nabla f(\boldsymbol{x}+s\alpha\boldsymbol{u};\xi)\,ds.\] Hence \[\frac{f(\boldsymbol{x}+\alpha\boldsymbol{u};\xi)-f(\boldsymbol{x}-\alpha\boldsymbol{u};\xi)}{2\alpha} = \boldsymbol{u}^\top\nabla f(\boldsymbol{x};\xi)+\beta,\] where \[\beta := \frac{1}{2}\int_{-1}^{1} \boldsymbol{u}^\top\bigl(\nabla f(\boldsymbol{x}+s\alpha\boldsymbol{u};\xi)-\nabla f(\boldsymbol{x};\xi)\bigr)\,ds.\] By \(L\)-smoothness, \[|\beta| \le \frac{1}{2}\int_{-1}^{1} L|s|\alpha\|\boldsymbol{u}\|^2\,ds = \frac{L\alpha}{2}\|\boldsymbol{u}\|^2.\] Multiplying the scalar central difference by \(\boldsymbol{u}\) gives Eq. ?? . ◻

Proof. The function \(x\mapsto 1/(x+T_0)\) is positive and decreasing. Therefore \[\sum_{t=k}^{K-1}\frac{1}{t+T_0} \ge \int_k^K\frac{dx}{x+T_0} = \log\frac{T_K}{T_k}.\] For the upper bound, \[\sum_{t=k}^{K-1}\frac{1}{t+T_0} \le \frac{1}{T_k} + \int_k^K\frac{dx}{x+T_0} \le 1+\log\frac{T_K}{T_k} \le 1+\log T_K.\] Similarly, \[\sum_{t=k}^{K-1}\frac{1}{(t+T_0)^2} \le \frac{1}{T_k^2} + \int_k^\infty\frac{dx}{(x+T_0)^2} = \frac{1}{T_k^2}+\frac{1}{T_k} \le \frac{2}{T_k},\] because \(T_k>1\). ◻

Proof. By rotational invariance of the standard Gaussian distribution, we may assume \(\boldsymbol{a}=e_1\). Then \[Y=\frac{X_1^2}{X_1^2+\cdots+X_d^2}.\] For \(d=1\), this ratio is one almost surely. For \(d\ge2\), \(X_1^2\sim\chi^2_1\) and \(\sum_{i=2}^dX_i^2\sim\chi^2_{d-1}\) are independent. Equivalently, these two variables are independent gamma random variables with common scale parameter and shapes \(1/2\) and \((d-1)/2\). The ratio of the first gamma variable to their sum therefore has the \(\mathrm{Beta}(1/2,(d-1)/2)\) distribution. ◻

Proof. The variable \(P_{k+1}\) is \(\mathcal{H}_k\)-measurable, whereas \(\vartheta_k\) is \(\mathcal{H}_{k+1}\)-measurable. Hence the transformed increments \(\vartheta_k/P_{k+1}\) are adapted martingale differences. The conditional mgf assumption gives the same sub-Gaussian bound with variance proxy \(v_k/P_{k+1}^2\). Thus \(\widetilde{M}_K\) is a sub-Gaussian martingale with variance proxy \[\widetilde{V}_K:=\sum_{k=0}^{K-1}\frac{v_k}{P_{k+1}^2}.\]

For every \(\lambda>0\), \[L_K(\lambda) := \exp\left( \lambda\widetilde{M}_K -\lambda^2\sigma^2\widetilde{V}_K \right), \qquad K=0,\dots,T,\] is a nonnegative supermartingale. Indeed, after conditioning on \(\mathcal{H}_k\), the one-step multiplicative factor has expectation at most one by the preceding conditional mgf bound. Lemma 17 therefore gives, for every \(r>0\), \[\Pr\left( \exists K\le T: \lambda\widetilde{M}_K-\lambda^2\sigma^2\widetilde{V}_K\ge r \right) \le e^{-r}.\]

We next apply a peeling argument to the intrinsic variance. Fix a deterministic \(U>0\). For \(j=0,1,2,\dots\), set \[I_j:=\left(2^{-j-1}U,\,2^{-j}U\right], \qquad \delta_j:=\frac{6\delta}{\pi^2(j+1)^2}, \qquad r_j:=\log\frac{1}{\delta_j},\] and choose \[\lambda_j:= \sqrt{\frac{r_j}{\sigma^2\,2^{-j}U}}.\] The intervals \(I_j\) partition \((0,U]\). On the complement of the Ville event for epoch \(j\), every \(K\le T\) with \(\widetilde{V}_K\in I_j\) satisfies \[\widetilde{M}_K \le \lambda_j\sigma^2\widetilde{V}_K+\frac{r_j}{\lambda_j} = \sigma\sqrt{r_j} \left( \frac{\widetilde{V}_K}{\sqrt{2^{-j}U}} +\sqrt{2^{-j}U} \right) \le 3\sigma\sqrt{\widetilde{V}_K\,r_j}.\] The last inequality uses \(\widetilde{V}_K\le2^{-j}U\le2\widetilde{V}_K\) on \(I_j\). Moreover, on this epoch, \[r_j \le C\left\{ \log\frac{1}{\delta} + \log\left(1+\log\left(e+\frac{U}{\widetilde{V}_K}\right)\right) \right\}.\] Since \(\sum_{j\ge0}\delta_j\le\delta\), a union bound over the variance epochs shows that, with probability at least \(1-\delta\), the following bound holds simultaneously for all \(K\le T\) with \(0<\widetilde{V}_K\le U\): \[\label{eq:stitched95product95mg95raw95boundary} \widetilde{M}_K \le C\sigma\sqrt{\widetilde{V}_K \left( \log\frac{1}{\delta}+ \log\left(1+\log\left(e+\frac{U}{\widetilde{V}_K}\right)\right) \right)}.\tag{14}\] The estimate is already uniform in the terminal time \(K\); Lemma 17 handled the maximum over \(K\) inside each epoch. If \(\widetilde{V}_K=0\), then all variance proxies up to time \(K\) are zero, and the conditional mgf bound with zero proxy forces the corresponding martingale increments to vanish almost surely; hence \(\widetilde{M}_K=0\).

Apply Eq. 14 with \(U=U_\star\). For every \(K\) that can contribute to the failure event—that is, every \(K\) satisfying \(A_K\le\bar A_K\)—the event \(\mathcal{P}_T\) implies \[\widetilde{V}_K=P_K^{-2}A_K \le (T+T_0)^{C_P}\bar A_K,\] and hence \(\widetilde{V}_K\le U_\star\). Multiplying Eq. 14 by \(P_K\) therefore gives \[S_K \le C\sigma \sqrt{ A_K \left( \log\frac{1}{\delta}+ \log\left(1+\log\left(e+\frac{U_\star}{\widetilde{V}_K}\right)\right) \right)}.\] It remains only to replace the random variance \(A_K\) by the deterministic envelope \(\bar A_K\). If \(A_K=0\), then \(\widetilde{V}_K=0\) and hence \(S_K=0\), so such a \(K\) cannot contribute to the failure event. We may therefore consider \(0<A_K\le\bar A_K\). Since \(q_t\le1\), \(P_K\le1\), so \(\widetilde{V}_K=P_K^{-2}A_K\ge A_K\); hence the logarithmic factor with \(U_\star/\widetilde{V}_K\) is no larger than the same factor with \(U_\star/A_K\). For \(0<a\le b\) and \(U>0\), we use the deterministic inequality \[\label{eq:variance95envelope95loglog95transfer} a\log\left(1+\log\left(e+\frac{U}{a}\right)\right) \le Cb\left[ 1+\log\left(1+\log\left(e+\frac{U}{b}\right)\right) \right].\tag{15}\] To see this, write \(s=b/a\ge1\) and \(x=U/b\). Since \(e+sx\le s(e+x)\), we have \[\log\left(1+\log(e+sx)\right) \le C\left[ \log\left(1+\log(e+x)\right) + \log\left(1+\log s\right) \right].\] Multiplying by \(a=b/s\) and using \(\sup_{s\ge1}s^{-1}\log(1+\log s)<\infty\) proves the displayed inequality, after increasing the universal constant \(C\). Applying Eq. 15 with \(a=A_K\), \(b=\bar A_K\), and \(U=U_\star\), and also using \(A_K\log(1/\delta)\le\bar A_K\log(1/\delta)\), yields \[S_K \le C_{\mathrm{st}}\sigma\sqrt{\bar A_K\,G}\] for every \(K\le T\) with \(A_K\le\bar A_K\), where the assumed deterministic bound on \(\max_K\log(1+\log(e+U_\star/\bar A_K))\) and \(G\ge1+\log(1/\delta)\) were used in the final step. Thus the displayed failure event is contained in the complement of the stitched event constructed above, whose probability is at most \(\delta\). ◻

Proof. If \(d=1\), then \(\zeta_t=1\) almost surely. The lower bounds are immediate, while the prefix bound follows from \(\sum_{t=0}^{K-1}w_t\le 1+\log(T+T_0)\), after increasing \(C\). Hence we assume \(d\ge2\).

Conditional on \({{\mathcal{F}}}_{t-1}\), the vector \(\boldsymbol{a}_t\) is fixed and \(\boldsymbol{u}_t\sim\mathcal{N}(0,I_d)\). Therefore \[\zeta_t\mid{{\mathcal{F}}}_{t-1} \sim \mathrm{Beta}\left(\frac{1}{2},\frac{d-1}{2}\right),\] and Lemma 21 gives \[\mathbb{E}[\zeta_t\mid{{\mathcal{F}}}_{t-1}]=\frac{1}{d}, \qquad \mathrm{Var}(\zeta_t\mid{{\mathcal{F}}}_{t-1})\le\frac{2}{d^2},\] together with the following centered moment estimate. For every integer \(p\ge1\), \[\mathbb{E}[\zeta_t^p\mid{{\mathcal{F}}}_{t-1}] = \prod_{i=0}^{p-1}\frac{i+1/2}{i+d/2} \le p!\left(\frac{2}{d}\right)^p.\] The last inequality uses \(i+d/2\ge d/2\) and \(\prod_{i=0}^{p-1}(2i+1)\le 2^p p!\). Thus, for every integer \(p\ge2\), \[\mathbb{E}\left[ \left|\zeta_t-\frac{1}{d}\right|^p \middle|{{\mathcal{F}}}_{t-1} \right] \le p!\left(\frac{4}{d}\right)^p.\] Set \[Z_t:=w_t\left(\frac{1}{d}-\zeta_t\right).\] Then \(Z_t\) is conditionally centered, \[\mathbb{E}[Z_t^2\mid{{\mathcal{F}}}_{t-1}] \le \frac{2w_t^2}{d^2}, \qquad Z_t\le\frac{w_t}{d}.\]

We first record the block maximal estimate used below. Fix a deterministic interval \([r,s]\) on which \(w_t\le m_0\), choose a sign \(\mathfrak s\in\{-1,1\}\), and write \(A_{r,u}:=\sum_{t=r}^{u}w_t\) and \[M_{r,u}^{(\mathfrak s)} := \sum_{t=r}^{u} \mathfrak s\,w_t\left(\zeta_t-\frac{1}{d}\right).\] Let \(\mathcal{B}\subseteq\{r,\dots,s\}\) be a set of endpoints with largest element \(u_\star\), and suppose that \(A_{r,u_\star}\le2A_{r,u}\) for all \(u\in\mathcal{B}\). Then, for every \(\alpha\in(0,1)\), with probability at least \(1-\alpha\), \[\label{eq:weighted95block95maximal} M_{r,u}^{(\mathfrak s)} \le \frac{A_{r,u}}{2d} + \frac{Cm_0}{d}\log\frac{1}{\alpha}, \qquad u\in\mathcal{B}.\tag{16}\] Indeed, for every integer \(p\ge2\), the centered moment estimate above implies \[\mathbb{E}\!\left[ \left| \mathfrak s\,w_t\left(\zeta_t-\frac{1}{d}\right) \right|^p \middle|{{\mathcal{F}}}_{t-1} \right] \le \frac{p!}{2} \frac{32w_t^2}{d^2} \left(\frac{4m_0}{d}\right)^{p-2}.\] Hence, for \(0<\lambda<d/(4m_0)\), \[\mathbb{E}\!\left[ \exp\left\{ \lambda\mathfrak s\,w_t\left(\zeta_t-\frac{1}{d}\right) \right\} \middle|{{\mathcal{F}}}_{t-1} \right] \le \exp\left( \frac{\lambda^2(32w_t^2/d^2)}{2(1-4\lambda m_0/d)} \right).\] Therefore the standard exponential transform of \(M_{r,u}^{(\mathfrak s)}\), stopped at \(u_\star\), is a nonnegative supermartingale with variance proxy \[V_\star:=\frac{32}{d^2}\sum_{t=r}^{u_\star}w_t^2 \le \frac{32m_0A_{r,u_\star}}{d^2}\] and Bernstein scale \(b_\star:=4m_0/d\). Applying Lemma 17 and optimizing over \(\lambda\) give \[\Pr\!\left( \max_{r\le u\le u_\star}M_{r,u}^{(\mathfrak s)}\ge x \right) \le \exp\left(-\frac{x^2}{2(V_\star+b_\star x)}\right).\] Thus, with probability at least \(1-\alpha\), \[\max_{r\le u\le u_\star}M_{r,u}^{(\mathfrak s)} \le \frac{C}{d} \left( \sqrt{m_0A_{r,u_\star}\log\frac{1}{\alpha}} + m_0\log\frac{1}{\alpha} \right).\] For \(u\in\mathcal{B}\), use \(A_{r,u_\star}\le2A_{r,u}\) and \(2\sqrt{xy}\le x/2+2y\) to absorb the square-root term into \(A_{r,u}/(2d)+Cm_0d^{-1}\log(1/\alpha)\), proving 16 .

We next establish the lower scan. Partition time into dyadic annuli \[\mathcal{I}_j := \{t:2^jT_0\le t+T_0<2^{j+1}T_0\}, \qquad j=0,1,\dots,J_T.\] Empty annuli are ignored. On \(\mathcal{I}_j\), set \(m_j:=(2^jT_0)^{-1}\); then \(w_t\le m_j\), while \(w_t\ge m_j/2\), and the number of possible starting points is at most \(N_j\le 2^jT_0+1\).

Fix \(j\) and \(a\in\mathcal{I}_j\). For intervals \([a,b]\subseteq\mathcal{I}_j\), partition the endpoints by weighted mass: \[\mathcal{B}_{j,\ell}(a) := \{b\in\mathcal{I}_j:b\ge a,\; 2^{\ell-1}m_j\le A_{a,b}<2^\ell m_j\}, \qquad \ell\ge0.\] These blocks cover all admissible endpoints because \(A_{a,a}=w_a\ge m_j/2\). Moreover, \(\sum_{t\in\mathcal{I}_j}w_t\le C\); hence a nonempty block must satisfy \(2^{\ell-1}m_j\le C\), and therefore \[\ell\le C\bigl(\log(e+T_0)+j\bigr)\] after increasing the numerical constant \(C\). Thus only \(O(\log(e+T_0)+j)\) endpoint blocks are nonempty. If \(\mathcal{B}_{j,\ell}(a)\) is nonempty and \(b_{j,\ell}(a)\) is its largest endpoint, then \(A_{a,b_{j,\ell}(a)}<2A_{a,b}\) for every \(b\in\mathcal{B}_{j,\ell}(a)\). Apply 16 with sign \(\mathfrak s=-1\), so that \(M_{a,b}^{(-1)}=\sum_{t=a}^{b}w_t(1/d-\zeta_t)\), and assign the failure probability \[\delta_{j,a,\ell} = \frac{c\delta}{(j+1)^2(N_j+1)(\ell+1)^2J_T},\] where \(c>0\) is a universal normalizing constant. Since \(|\mathcal{I}_j|\le N_j\), the total confidence budget is bounded by \[\sum_{j=0}^{J_T}\sum_{a\in\mathcal{I}_j}\sum_{\ell\ge0} \delta_{j,a,\ell} \le \frac{c\delta}{J_T} \sum_{j=0}^{J_T}\frac{1}{(j+1)^2} \frac{|\mathcal{I}_j|}{N_j+1} \sum_{\ell\ge0}\frac{1}{(\ell+1)^2} \le Cc\delta.\] Choosing \(c\) small enough makes this at most \(\delta/2\). On the resulting event, all intervals contained in a single annulus satisfy \[\sum_{t=a}^{b}w_t\zeta_t \ge \frac{1}{2d}\sum_{t=a}^{b}w_t - \frac{C}{d} \left( m_j\Gamma_T^{\rm scan}(\delta) + \frac{j+1}{2^jT_0} \right).\] Here we used \[m_j\log\frac{1}{\delta_{j,a,\ell}} \le Cm_j\Gamma_T^{\rm scan}(\delta) + \frac{C(j+1)}{2^jT_0},\] which follows from \(N_j\le2^jT_0+1\) and from the bound \(\ell\le C(\log(e+T_0)+j)\) for nonempty endpoint blocks.

For an interval \([a,b]\) spanning multiple annuli, let \(j_0,\dots,j_1\) be the annuli it intersects. Decompose \([a,b]\) into the right tail of \(\mathcal{I}_{j_0}\), the full annuli \(\mathcal{I}_{j_0+1},\dots,\mathcal{I}_{j_1-1}\), and the left tail of \(\mathcal{I}_{j_1}\), omitting empty pieces. Applying the one-annulus bound to each piece, the leading weighted-mass terms sum to \((2d)^{-1}\sum_{t=a}^{b}w_t\). The accumulated error is at most \[\frac{C}{d} \sum_{j=j_0}^{j_1} \left( m_j\Gamma_T^{\rm scan}(\delta) + \frac{j+1}{2^jT_0} \right).\] Since each annulus is counted at most once and the deterministic errors are summable, \[\sum_{j\ge0}m_j\le\frac{2}{T_0}, \qquad \sum_{j\ge0}\frac{j+1}{2^jT_0}\le\frac{C}{T_0}.\] Using \(\Gamma_T^{\rm scan}(\delta)\ge1\) and increasing \(C\), this proves ?? .

For the prefix upper bound, apply the same exponential-supermartingale estimate with sign \(\mathfrak s=1\) to the centered process \[R_K:=\sum_{t=0}^{K-1}w_t\left(\zeta_t-\frac{1}{d}\right).\] Since \[\sum_{t=0}^{T-1}w_t^2\le\frac{2}{T_0}, \qquad w_0=\frac{1}{T_0},\] the preceding Bernstein–Ville calculation, now on the whole interval \([0,T-1]\), has variance proxy at most \(C/(d^2T_0)\) and Bernstein scale at most \(C/(dT_0)\). With probability at least \(1-\delta/2\), and using \(\Gamma_T^{\rm scan}(\delta)\ge\log(2/\delta)\), \[\max_{1\le K\le T}R_K \le \frac{C}{d} \left( \sqrt{\frac{\Gamma_T^{\rm scan}(\delta)}{T_0}} + \frac{\Gamma_T^{\rm scan}(\delta)}{T_0} \right).\] Using \(\sqrt{x}\le1+x\), adding \[\frac{1}{d}\sum_{t=0}^{K-1}w_t \le \frac{C(1+\log(T+T_0))}{d},\] and multiplying by \(d\), yields ?? . The suffix display ?? follows immediately from ?? with \(a=k+1\) and \(b=K-1\). ◻

Proof of Lemma 1. By the smoothness of \(f\) and the update rule of the algorithm, \[\begin{align} &f(\boldsymbol{x}_{t+1}) \\ \stackrel{\eqref{eq:L}}{\leq}& f(\boldsymbol{x}_t) - \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{g}(\boldsymbol{x}_t;\xi_t)\right\rangle + \frac{L\eta_t^2}{2} \left\|\boldsymbol{g}(\boldsymbol{x}_t;\xi_t)\right\|^2 \\ \stackrel{\eqref{eq:sg1}}{=}& f(\boldsymbol{x}_t) - \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t;\xi_t) + \beta_t \boldsymbol{u}_t\right\rangle + \frac{L\eta_t^2}{2} \left\|\boldsymbol{u}_t\boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t;\xi_t) + \beta_t \boldsymbol{u}_t\right\|^2\\ \leq& f(\boldsymbol{x}_t) - \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t;\xi_t)\right\rangle + \frac{\eta_t \beta_t^2}{2} + \frac{\eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2}{2}\\ &+ L\eta_t^2 \left( \left\|\boldsymbol{u}_t\right\|^2 |\boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t;\xi_t)|^2 + \beta_t^2 \left\|\boldsymbol{u}_t\right\|^2 \right)\\ =& f(\boldsymbol{x}_t) - \eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2 + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle \\ & + \frac{\eta_t \beta_t^2}{2} + \frac{\eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2}{2} + L\eta_t^2 \left( \left\|\boldsymbol{u}_t\right\|^2 |\boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t;\xi_t)|^2 + \beta_t^2 \left\|\boldsymbol{u}_t\right\|^2 \right)\\ \leq& f(\boldsymbol{x}_t) - \eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2 + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle + \frac{\eta_t \beta_t^2}{2} + \frac{\eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2}{2} \\ & + L\eta_t^2 \left( 2\left\|\boldsymbol{u}_t\right\|^2 \Big( |\boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t)|^2 + |\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2 \Big) + \beta_t^2 \left\|\boldsymbol{u}_t\right\|^2 \right) \\ =& f(\boldsymbol{x}_t) - \frac{\eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2}{2} + 2L\eta_t^2 \left\|\boldsymbol{u}_t\right\|^2 ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2 + \frac{\eta_t \beta_t^2}{2} + L\eta_t^2 \beta_t^2 \left\|\boldsymbol{u}_t\right\|^2\\ & + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle + 2L\eta_t^2\left\|\boldsymbol{u}_t\right\|^2|\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2. \end{align}\]

Consequently, \[\begin{align} f(\boldsymbol{x}_{t+1}) - f(\boldsymbol{x}^*) \leq& f(\boldsymbol{x}_t) - f(\boldsymbol{x}^*) - \frac{\eta_t ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2}{2} + 2L\eta_t^2 \left\|\boldsymbol{u}_t\right\|^2 ( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2 + \Delta_{\alpha, t}\\ & + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle + 2L\eta_t^2\left\|\boldsymbol{u}_t\right\|^2|\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2\\ =& f(\boldsymbol{x}_t) - f(\boldsymbol{x}^*) - \frac{\eta_t}{2} \left(1 - 4L\eta_t \left\|\boldsymbol{u}_t\right\|^2\right)( \boldsymbol{u}_t^\top \nabla f(\boldsymbol{x}_t))^2\\ & + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle + 2L\eta_t^2\left\|\boldsymbol{u}_t\right\|^2|\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2 + \Delta_{\alpha, t}\\ \leq& f(\boldsymbol{x}_t) - f(\boldsymbol{x}^*) - \frac{\eta_t}{4}\bigl(\boldsymbol{u}_t^\top\nabla f(\boldsymbol{x}_t)\bigr)^2 \\ & + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle + 2L\eta_t^2\left\|\boldsymbol{u}_t\right\|^2|\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2 + \Delta_{\alpha, t}\\ \leq& \left(1 - \frac{\mu\eta_t}{2} \frac{(\boldsymbol{u}_t^\top\nabla f(\boldsymbol{x}_t))^2}{\|\nabla f(\boldsymbol{x}_t)\|^2} \right)\cdot \Big( f(\boldsymbol{x}_t) - f(\boldsymbol{x}^*) \Big)\\ & + \eta_t \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle + 2L\eta_t^2\left\|\boldsymbol{u}_t\right\|^2|\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2 + \Delta_{\alpha, t}, \end{align}\] where the second inequality uses \(\eta_t\le1/(8L\left\|\boldsymbol{u}_t\right\|^2)\), and the final inequality uses the Polyak–Łojasiewicz inequality implied by \(\mu\)-strong convexity. ◻

Proof of Lemma 2. Write \(w_t:=\frac{1}{T_t},\) and use the angle variable \(\zeta_t\) defined after Proposition 1. By Lemma 23, with probability at least \(1-\delta\), the lower scan ?? and the prefix upper control ?? hold. Since the present \(\Gamma_T(\delta)\) dominates the scan confidence factor, we may replace \(\Gamma_T^{\rm scan}(\delta)\) by \(\Gamma_T(\delta)\) in the two resulting bounds.

The lower scan gives, for every interval, \[\sum_{t=a}^{b}w_t\zeta_t \ge \frac{1}{2d}\sum_{t=a}^{b}w_t - \frac{C}{dT_0}\Gamma_T(\delta).\] Setting \(a=k+1\) and \(b=K-1\), then multiplying by \(2d\) and exponentiating, gives, simultaneously for every \(1\le K\le T\) and every \(k=-1,0,\dots,K-2\), \[\exp\left( -2d\sum_{t=k+1}^{K-1} \frac{\zeta_t}{T_t} \right) \le \exp\left( -\sum_{t=k+1}^{K-1}\frac{1}{T_t} +\frac{2C}{T_0}\Gamma_T(\delta) \right).\] The case \(k=-1\) is exactly \(\mathcal{E}_{\rho_K}\), while \(k=0,\dots,K-2\) gives \(\mathcal{E}_{\rho_{K,k}}\). The remaining case \(k=K-1\) holds because the left-hand side is \(1\) and \(\rho_{K,K-1}\ge1\). The prefix upper control gives \[d\sum_{t=0}^{K-1}w_t\zeta_t \le C(1+\Lambda)+ \frac{C}{T_0}\Gamma_T(\delta) \le C\Lambda+C\frac{\Gamma_T(\delta)}{T_0}, \qquad K\le T,\] which is the event \(\mathcal{E}_\rho^+\). ◻

Proof of Lemma 3. Set \(\eta_t = 4d/[\mu (t+T_0) \left\|\boldsymbol{u}_t\right\|^2]\) with \(T_0 = 32 dL/\mu\), so that \(\eta_t \leq 1/(8L\left\|\boldsymbol{u}_t\right\|^2)\). Combining this choice with Eq. ?? gives \[\begin{align} \Delta_{t+1} \leq& \left(1 - \frac{2d}{T_t}\zeta_t \right)\cdot \Delta_t\\ & + \frac{4d }{\mu (t+T_0) \left\|\boldsymbol{u}_t\right\|^2} \cdot \left\langle \nabla f(\boldsymbol{x}_t), \boldsymbol{u}_t\boldsymbol{u}_t^\top \boldsymbol{e}_t\right\rangle\\ & + \frac{32L d^2 }{\mu^2 (t+T_0)^2 \left\|\boldsymbol{u}_t\right\|^4}\left\|\boldsymbol{u}_t\right\|^2|\boldsymbol{u}_t^\top \boldsymbol{e}_t|^2 + \Delta_{\alpha, t}. \end{align}\]

Unrolling the preceding recursion with \[\Pi_{K,k} := \prod_{t=k+1}^{K-1} \left( 1-\frac{2d}{T_t}\zeta_t \right),\] yields \[\begin{align} &\Delta_K \leq \prod_{t=0}^{K-1} \left( 1-\frac{2d}{T_t}\zeta_t \right) \cdot \Delta_0 \\ & + \sum_{k=0}^{K-1} \left( \Pi_{K,k} \cdot \frac{4d \cdot \left\langle \nabla f(\boldsymbol{x}_k), \boldsymbol{u}_k\boldsymbol{u}_k^\top \boldsymbol{e}_k\right\rangle}{\mu (k+T_0) \left\|\boldsymbol{u}_k\right\|^2} \right) \\ & + \sum_{k=0}^{K-1} \left( \Pi_{K,k} \cdot \left(\frac{32 Ld^2 }{\mu^2 (k+T_0)^2} \cdot \frac{|\boldsymbol{u}_k^\top \boldsymbol{e}_k|^2}{\left\|\boldsymbol{u}_k\right\|^2} + \Delta_{\alpha, k} \right) \right) \end{align}\]

Furthermore, Lemma 18 gives \(|\beta| \leq (L\alpha/2)\left\|\boldsymbol{u}\right\|^2\), and hence \[\begin{align} \Delta_{\alpha, t} =& \frac{\eta_t \beta_t^2}{2} + L\eta_t^2 \beta_t^2 \left\|\boldsymbol{u}_t\right\|^2 \leq \frac{\eta_t L^2 \alpha^2 \left\|\boldsymbol{u}_t\right\|^4}{8} + \frac{\eta_t^2 L^3 \alpha^2\left\|\boldsymbol{u}_t\right\|^6}{4} \\ =& \frac{ d L^2\alpha^2 \left\|\boldsymbol{u}_t\right\|^2}{2\mu(t+T_0)} + \frac{ 4d^2 L^3\alpha^2 \left\|\boldsymbol{u}_t\right\|^2}{ \mu^2 (t+T_0)^2 }. \end{align}\]

By the standing assumption \(L\ge\mu\), \(T_0=32dL/\mu\ge32d\). Hence each factor in \(\Pi_{K,k}\) is nonnegative, and \(1-x\le e^{-x}\) gives \[\Pi_{K,k} \le \exp\left( -2d\sum_{t=k+1}^{K-1} \frac{\zeta_t}{T_t} \right) \le \rho_{K,k}.\] The same argument with the product over \(t=0,\dots,K-1\), together with \(\mathcal{E}_{\rho_K}\), bounds the initial product by \(\rho_K\). On the events \(\mathcal{E}_{\rho_K}\) and \(\mathcal{E}_{\rho_{K,k}}\), we use this upper bound only for the nonnegative initial, quadratic, and smoothing terms. The linear term is signed and therefore keeps the actual product \(\Pi_{K,k}\): \[\begin{align} \Delta_K \leq& \rho_K \cdot \Delta_0 + \sum_{k=0}^{K-1} \Pi_{K,k} \left( \frac{4d \cdot \left\langle \nabla f(\boldsymbol{x}_k), \boldsymbol{u}_k\boldsymbol{u}_k^\top \boldsymbol{e}_k\right\rangle}{\mu (k+T_0) \left\|\boldsymbol{u}_k\right\|^2} \right) \\ &+ \sum_{k=0}^{K-1} \rho_{K,k} \left(\frac{32Ld^2 }{\mu^2 (k+T_0)^2} \cdot \frac{|\boldsymbol{u}_k^\top \boldsymbol{e}_k|^2}{\left\|\boldsymbol{u}_k\right\|^2} + \frac{ d L^2\alpha^2 \left\|\boldsymbol{u}_k\right\|^2}{2\mu(k+T_0)} + \frac{ 4d^2 L^3\alpha^2 \left\|\boldsymbol{u}_k\right\|^2}{ \mu^2 (k+T_0)^2 } \right). \end{align}\] ◻

Proof of Lemma 4. If \(z=0\), the claim is immediate. Otherwise, taking \(\lambda=1/(2\sigma^2)\) in the assumed norm bound and using \(|\langle\boldsymbol{e},z\rangle|\le\|\boldsymbol{e}\|\|z\|\) gives \[\mathbb{E}\left[ \exp\left( \frac{\langle\boldsymbol{e},z\rangle^2}{2\sigma^2\|z\|^2} \right) \middle|\mathcal{F} \right] \le e^{1/2}.\] Thus \(\langle\boldsymbol{e},z\rangle\) has a conditional \(\psi_2\)-norm bounded by a universal multiple of \(\sigma\|z\|\). For completeness, one may pass from this conditional Orlicz bound to an mgf bound by conditioning on \(\mathcal{F}\) and applying the usual moment argument pointwise: if \(X=\langle\boldsymbol{e},z\rangle\) and \(a=C\sigma\|z\|\), then \(\mathbb{E}[|X|^m\mid\mathcal{F}]\le C a^m m^{m/2}\) for all \(m\ge2\). Expanding \(\mathbb{E}[\exp(\theta X)\mid\mathcal{F}]\), using \(\mathbb{E}[X\mid\mathcal{F}]=0\), and summing the resulting series gives \(\mathbb{E}[\exp(\theta X)\mid\mathcal{F}]\le \exp(C\theta^2a^2)\). Absorbing the universal constants into \(C_{\mathrm{sg}}\) yields Eq. ?? . This is the Euclidean specialization of Lemma 2.1 in [18]. ◻

Proof of Lemma 5. If \(\boldsymbol{e}=0\), the displayed exponential moment equals one. We may therefore assume \(\boldsymbol{e}\ne0\) in the first part of the proof. Write \(\mathbf{v}=\boldsymbol{u}/\|\boldsymbol{u}\|\). Conditional on \(\boldsymbol{e}\), the random variable \[\Theta := \frac{(\mathbf{v}^\top\boldsymbol{e})^2}{\|\boldsymbol{e}\|^2}\] belongs to \([0,1]\) and satisfies \(\mathbb{E}[\Theta\mid\boldsymbol{e},\mathcal{F}]=1/d\). For \(s\ge0\), convexity of \(x\mapsto e^{sx}\) on \([0,1]\) gives \[e^{s\Theta} \le 1+\Theta(e^s-1).\] Therefore, \[\mathbb{E}_{\boldsymbol{u}}\left[ \exp\left( \lambda\frac{(\boldsymbol{u}^\top\boldsymbol{e})^2}{\|\boldsymbol{u}\|^2} \right) \middle|\boldsymbol{e},\mathcal{F} \right] \le 1+\frac{ \exp(\lambda\|\boldsymbol{e}\|^2)-1 }{d}.\] Taking conditional expectation with respect to \(\boldsymbol{e}\), using the conditional exponential-moment hypothesis of the lemma, and then \(1+x\le e^x\), we obtain \[\mathbb{E}\left[ \exp\left( \lambda\frac{(\boldsymbol{u}^\top\boldsymbol{e})^2}{\|\boldsymbol{u}\|^2} \right) \middle|\mathcal{F} \right] \le \exp\left( \frac{e^{\lambda\sigma^2}-1}{d} \right).\] When \(0<\lambda\le1/(2\sigma^2)\), \(e^{\lambda\sigma^2}-1\le 2\lambda\sigma^2\), proving Eq. ?? .

For the deterministic weighted statement, the conclusion is immediate when \(w_{\max}=0\). Otherwise, apply Eq. ?? conditionally at each time with \(\lambda w_k\) in place of \(\lambda\). If \(0<\lambda\le 1/(2\sigma^2w_{\max})\), then \[\mathbb{E}\exp\left( \lambda \sum_{k=0}^{K-1}w_k \frac{(\boldsymbol{u}_k^\top\boldsymbol{e}_k)^2}{\|\boldsymbol{u}_k\|^2} - \frac{2\lambda\sigma^2}{d}W \right) \le 1.\] Markov’s inequality with \(\lambda=1/(2\sigma^2w_{\max})\) yields Eq. ?? . ◻

Proof of Lemma 6. We first identify the conditional law of the future angles and then use its deterministic form to prove conditional independence from \(\xi_k\).

Let \(\mathcal{F}_t^-\) be the history immediately before sampling \(\boldsymbol{u}_t\). Conditional on \(\mathcal{F}_t^-\), the iterate \(\boldsymbol{x}_t\) is known. Hence, on the probability-one event from Proposition 1, \[a_t:=\frac{\nabla f(\boldsymbol{x}_t)}{\|\nabla f(\boldsymbol{x}_t)\|}\] is a fixed unit vector. The new direction \(\boldsymbol{u}_t\sim\mathcal{N}(0,I_d)\) is independent of \(\mathcal{F}_t^-\). Therefore, by rotational invariance and Lemma 20, for every bounded Borel function \(h\), \[\mathbb{E}[h(\zeta_t)\mid \mathcal{F}_t^-] = \int h\,d\nu,\qquad \nu=\mathrm{Beta}\left(\frac{1}{2},\frac{d-1}{2}\right).\] Crucially, the right-hand side is deterministic: it does not depend on \(\boldsymbol{x}_t\), even though \(\boldsymbol{x}_t\) may depend on earlier oracle samples such as \(\xi_k\).

If \(k=K-1\), there are no future angle variables and the claim is the empty product law. Otherwise set \[Z:=(\zeta_{k+1},\dots,\zeta_{K-1}),\qquad n:=K-k-1.\] For bounded Borel functions \(h_{k+1},\dots,h_{K-1}\), successive conditioning backward from time \(K-1\) gives \[\begin{align} \mathbb{E}\left[ \prod_{t=k+1}^{K-1}h_t(\zeta_t) \middle|\mathcal{F}_k^+ \right] & = \mathbb{E}\left[ \prod_{t=k+1}^{K-2}h_t(\zeta_t) \mathbb{E}\left[h_{K-1}(\zeta_{K-1})\middle|\mathcal{F}_{K-1}^{-}\right] \middle|\mathcal{F}_k^+ \right] \\ & = \left(\int h_{K-1}\,d\nu\right) \mathbb{E}\left[ \prod_{t=k+1}^{K-2}h_t(\zeta_t) \middle|\mathcal{F}_k^+ \right]. \end{align}\] Repeating the same step for \(t=K-2,\dots,k+1\) yields \[\mathbb{E}\left[ \prod_{t=k+1}^{K-1}h_t(\zeta_t) \middle|\mathcal{F}_k^+ \right] = \prod_{t=k+1}^{K-1}\int h_t\,d\nu.\] By the monotone-class theorem, this product-function identity implies that for every bounded Borel function \(h\) on \([0,1]^n\), \[\mathbb{E}[h(Z)\mid\mathcal{F}_k^+] = \int h\,d\nu^{\otimes n}.\] In other words, \[\mathcal{L}(Z\mid\mathcal{F}_k^+)=\nu^{\otimes n}.\] This is stronger than merely knowing the marginal laws: conditional on the post-update history \(\mathcal{F}_k^+\), the future angles are conditionally independent, and their joint law is a deterministic measure.

We now prove the claimed conditional independence. Let \(h\) be any bounded Borel function of \(Z\), and let \(\varphi\) be any bounded measurable function of \(\xi_k\). Since \(\mathcal{F}_k^+\) contains \(\xi_k\), the variable \(\varphi(\xi_k)\) is \(\mathcal{F}_k^+\)-measurable. Thus the tower property and the deterministic conditional law above give \[\begin{align} \mathbb{E}\!\left[\varphi(\xi_k)h(Z)\mid\mathcal{F}_k^{u}\right] = \mathbb{E}\!\left[ \varphi(\xi_k)\mathbb{E}[h(Z)\mid\mathcal{F}_k^+] \middle|\mathcal{F}_k^{u} \right] = \left(\int h\,d\nu^{\otimes n}\right) \mathbb{E}[\varphi(\xi_k)\mid\mathcal{F}_k^{u}]. \end{align}\] On the other hand, applying the same tower property without \(\varphi(\xi_k)\) gives \[\mathbb{E}[h(Z)\mid\mathcal{F}_k^{u}] = \int h\,d\nu^{\otimes n}.\] Combining the last two displays, \[\mathbb{E}\!\left[\varphi(\xi_k)h(Z)\mid\mathcal{F}_k^{u}\right] = \mathbb{E}[\varphi(\xi_k)\mid\mathcal{F}_k^{u}] \mathbb{E}[h(Z)\mid\mathcal{F}_k^{u}].\] This identity for all bounded measurable \(h\) and \(\varphi\) is precisely the conditional independence of \(\sigma(Z)\) and \(\xi_k\) given \(\mathcal{F}_k^{u}\).

Finally, \(\boldsymbol{e}_k=\nabla f(\boldsymbol{x}_k)-\nabla f(\boldsymbol{x}_k;\xi_k)\) is a measurable function of \((\boldsymbol{x}_k,\xi_k)\), while \(\boldsymbol{x}_k\) is already \(\mathcal{F}_k^{u}\)-measurable. Hence the same conditional independence holds with \(\boldsymbol{e}_k\) in place of \(\xi_k\). Equivalently, for every bounded measurable \(\psi\), \[\mathbb{E}\!\left[\psi(\boldsymbol{e}_k)\mid \mathcal{F}_k^{u}\vee\sigma(Z)\right] = \mathbb{E}\!\left[\psi(\boldsymbol{e}_k)\mid\mathcal{F}_k^{u}\right] \quad\text{a.s.}\] By monotone convergence, the same identity extends to nonnegative measurable \(\psi\). Therefore, revealing the future-angle \(\sigma\)-field preserves the conditional mean-zero property, the conditional law of \(\boldsymbol{e}_k\), and its sub-Gaussian bounds. ◻

Proof of Lemma 7. Since \(T_0=32dL/\mu\ge32d\) and \(0\le\zeta_t\le1\), the factors \(q_t\) belong to \([15/16,1]\). Hence they satisfy the product-factor condition in Lemma 22. Use the angle-enlarged pre-noise filtration \[\mathcal{H}_k := \mathcal{F}_k^{u}\vee\sigma(\zeta_{k+1},\dots,\zeta_{T-1}), \qquad 0\le k\le T-1, \qquad \mathcal{H}_T:=\mathcal{F}_T^{-},\] where \(\mathcal{F}_k^{u}\) is the post-direction history in Proposition 2. The family \((\mathcal{H}_k)_{k=0}^{T}\) is increasing. Indeed, for \(0\le k\le T-2\), \[\mathcal{F}_k^{u} \subseteq \mathcal{F}_k^{+} \subseteq \mathcal{F}_{k+1}^{-} \subseteq \mathcal{F}_{k+1}^{u},\] and \(\zeta_{k+1}\) is \(\mathcal{F}_{k+1}^{u}\)-measurable, while \(\sigma(\zeta_{k+2},\dots,\zeta_{T-1})\) is part of both adjacent enlarged fields. Thus \(\mathcal{H}_k\subseteq\mathcal{H}_{k+1}\). For the last step, \(\mathcal{H}_{T-1}=\mathcal{F}_{T-1}^{u}\subseteq \mathcal{F}_{T-1}^{+}\subseteq\mathcal{F}_T^{-}=\mathcal{H}_T\). With respect to this filtration, \(q_k\), \(P_{k+1}^{-1}\), and \(v_k\) below are \(\mathcal{H}_k\)-measurable, while \(\vartheta_k\) is \(\mathcal{H}_{k+1}\)-measurable. By Lemma 6, revealing the future scalar angles does not change the conditional mean-zero property or the conditional sub-Gaussian law of the current noise \(\boldsymbol{e}_k\).

Set \[\vartheta_k := \frac{1}{T_k} \frac{\nabla f(\boldsymbol{x}_k)^\top\boldsymbol{u}_k\,\boldsymbol{u}_k^\top\boldsymbol{e}_k}{\|\boldsymbol{u}_k\|^2}, \qquad v_k := C_{\mathrm{sg}} \frac{1}{T_k^2} \frac{(\nabla f(\boldsymbol{x}_k)^\top\boldsymbol{u}_k)^2}{\|\boldsymbol{u}_k\|^2}.\] Then \(\mathbb{E}[\vartheta_k\mid\mathcal{H}_k]=0\), and Lemma 4 gives, for every \(\lambda\in\mathbb{R}\), \[\mathbb{E}\!\left[ \exp(\lambda\vartheta_k)\mid\mathcal{H}_k \right] \le \exp(\lambda^2\sigma^2v_k).\] Since \(\Pi_{K,k}=P_K/P_{k+1}\), \[\sum_{k=0}^{K-1}Y_{K,k}^{\Pi} = P_K\sum_{k=0}^{K-1}\frac{\vartheta_k}{P_{k+1}}, \qquad P_K^2\sum_{k=0}^{K-1}\frac{v_k}{P_{k+1}^2} = C_{\mathrm{sg}}A_K^\Pi.\] Apply Lemma 22 with failure probability \(\delta_{\rm lin}\), confidence factor \(G\), and deterministic envelopes \(C_{\mathrm{sg}}\bar A_K\). The displayed dyadic-scale condition remains valid under this fixed rescaling of \(\bar A_K\), after a possible enlargement of the universal constant. Absorbing \(C_{\mathrm{sg}}\) and the universal product-bound constant into \(C_Y\) yields Eq. ?? . ◻

Proof of Lemma 8. By Lemma 16, for a fixed \(t\), with probability at least \(1-\delta^{(u)}/T\), \[\|\boldsymbol{u}_t\|^2 \ge d-2\sqrt{d\log(T/\delta^{(u)})}.\] The condition \(d\ge16\log(T/\delta^{(u)})\) implies the lower bound \(\|\boldsymbol{u}_t\|^2\ge d/2\). A union bound over \(t=0,\dots,T-1\) proves \(\Pr(\mathcal{E}_u)\ge1-\delta^{(u)}\). ◻

Proof of Lemma 9. We first prove the relaxed event. Conditional on the pre-direction history, the vector \(\nabla f(\boldsymbol{x}_k)/\|\nabla f(\boldsymbol{x}_k)\|\) is a predictable unit vector on the probability-one event from Proposition 1. Hence \(z_k=(\boldsymbol{u}_k^\top\nabla f(\boldsymbol{x}_k))/\|\nabla f(\boldsymbol{x}_k)\|\) is conditionally standard Gaussian. Since the weights \(\bar w_k=\rho_{K,k}^2\bar\Delta_k/T_k^2\) are deterministic, the Laurent–Massart proof applies by repeated conditioning. Indeed, for every \(\lambda<1/(2\bar M_{K-1})\), the conditional Gaussian square mgf gives \[\mathbb{E}\left[ \exp\left( \lambda\sum_{k=0}^{K-1}\bar w_k z_k^2 \right) \right] \le \prod_{k=0}^{K-1}(1-2\lambda\bar w_k)^{-1/2},\] which is the same mgf bound used in Lemma 15. Hence, with probability at least \(1-\delta_K^{(V)}\), \[\sum_{k=0}^{K-1}\bar w_k z_k^2 \le \sum_{k=0}^{K-1}\bar w_k + 2\sqrt{\bar Q_{K-1}\log\frac{1}{\delta_K^{(V)}}} + 2\bar M_{K-1}\log\frac{1}{\delta_K^{(V)}}.\] Choosing \(C_V\) large enough, this exact Laurent–Massart bound implies \(\widehat{\mathcal{E}}_{V_K}\).

Now assume that \(f\) is \(L\)-smooth and \(\Delta_k\le\bar\Delta_k\) for \(k<K\). Smoothness gives \(\|\nabla f(\boldsymbol{x}_k)\|^2\le2L\Delta_k\). Therefore, \[\sum_{k=0}^{K-1} \left( \frac{|\rho_{K,k}|\, |\nabla f(\boldsymbol{x}_k)^\top\boldsymbol{u}_k|}{T_k}\sigma \right)^2 \le 2L\sigma^2 \sum_{k=0}^{K-1} \frac{\rho_{K,k}^2}{T_k^2}\bar\Delta_k z_k^2.\] Multiplying the bound in \(\widehat{\mathcal{E}}_{V_K}\) by \(2L\sigma^2\) gives Eq. ?? , after choosing \(C_V\) large enough. ◻

Proof of Lemma 10. Apply Lemma 5 at time \(k\) with \(\mathcal{F}=\mathcal{F}_k^{-}\), the history before sampling \(\boldsymbol{u}_k\). Conditional on this history, \(\boldsymbol{e}_k\) satisfies the conditional mean-zero and exponential-moment conditions, and \(\boldsymbol{u}_k\) is an independent standard Gaussian direction. Use \[w_k=\frac{\rho_{K,k}}{T_k^2}, \qquad W=\sum_{k=0}^{K-1}\frac{\rho_{K,k}}{T_k^2}, \qquad w_{\max} = \max_{0\le k\le K-1}\frac{\rho_{K,k}}{T_k^2}.\] This gives the displayed event with probability at least \(1-\delta_K^{(Q)}\) by Eq. ?? . ◻

Proof of Lemma 11. The claimed inequality is precisely the defining inequality of \(\mathcal{E}_{Q_K}\). ◻

Proof of Lemma 12. Apply the Laurent–Massart inequality (Lemma 15) to the collection of Gaussian coordinates defining \(\|\boldsymbol{u}_k\|^2\), with coordinate weights \(w_k = \rho_{K,k} \left( \frac{c_1}{T_k} + \frac{c_2}{T_k^2} \right)\). The Laurent–Massart middle term is \[2\sqrt{d\log(1/\delta_K^{(\alpha)})\sum_k w_k^2}.\] Since \(d\ge1\), this is bounded by \[2d\sqrt{\log(1/\delta_K^{(\alpha)})\sum_k w_k^2}.\] Thus, with probability at least \(1-\delta_K^{(\alpha)}\), \[\begin{align} &\sum_{k=0}^{K-1} \rho_{K,k} \left( \frac{c_1}{T_k} + \frac{c_2}{T_k^2} \right)\left\|\boldsymbol{u}_k\right\|^2 \leq d \sum_{k=0}^{K-1} \rho_{K,k} \left( \frac{c_1}{T_k} + \frac{c_2}{T_k^2} \right) \\ &+ 2d\sqrt{ \log\frac{1}{\delta_K^{(\alpha)}} \cdot \sum_{k=0}^{K-1} \rho_{K,k}^2 \left( \frac{c_1}{T_k} + \frac{c_2}{T_k^2} \right)^2} + 2d \log\frac{1}{\delta_K^{(\alpha)}} \max_{0 \leq k \leq K-1} \rho_{K,k} \left( \frac{c_1}{T_k} + \frac{c_2}{T_k^2} \right). \end{align}\] This implies the stated relaxed event \(\mathcal{E}_{\alpha_K}\) after choosing the universal constant \(C_\chi\) large enough. ◻

Proof of Lemma 13. By Lemma 19 with \(k=0\), and by the definition of \(\rho_K\) in Eq. ?? , \[\begin{align} \rho_K \le& \exp\left(\frac{2C}{T_0}\Gamma_T(\delta)\right) \frac{T_0}{T_K} \leq c_\rho \frac{T_0}{T_K}. \end{align}\]

Similarly, by Lemma 19 and Eq. ?? , \[\begin{align} \rho_{K,k} &\le \exp\left(\frac{2C}{T_0}\Gamma_T(\delta)\right) \frac{T_{k+1}}{T_K}. \end{align}\] Since \(T_{k+1}=T_k+1\le2T_k\) for \(T_k\ge1\), we have \[\rho_{K,k} \le 2\exp\!\left( \frac{2C}{T_0}\Gamma_T(\delta) \right) \frac{T_k}{T_K} \leq c_\rho \frac{T_k}{T_K}.\] For the lower comparison, monotonicity of \(t\mapsto 1/(t+T_0)\) gives \[\sum_{t=k+1}^{K-1}\frac{1}{T_t} \le \int_k^{K-1}\frac{dx}{x+T_0} \le \log\frac{T_K}{T_k}.\] Therefore Eq. ?? implies \[\rho_{K,k} \ge \exp\!\left( \frac{2C}{T_0}\Gamma_T(\delta) \right) \frac{T_k}{T_K} = \frac{c_\rho}{2}\frac{T_k}{T_K}.\] ◻

Proof of Lemma 14. We combine finitely many time-uniform estimates with finitely many terminal estimates. Use the explicit failure levels \[\delta_{\rm scan} = \delta_{\rm prod} = \delta_u := \frac{\delta}{6}\] for Lemma 2, Lemma 7, and Lemma 8, respectively. More explicitly, choose the universal constant \(C\) in the scan estimates, in \(\rho_K,\rho_{K,k}\), and in \(c_\rho\) large enough so that \[C\,\Gamma_T(\delta) \ge C_0\left( 1+\log\frac{6}{\delta}+\log J_T+\log(e+T_0) \right),\] where \(C_0\) is the corresponding universal constant in Lemma 23. Thus applying Lemma 2 at failure level \(\delta/6\) yields exactly the displayed \(\rho\)-events with \(\Gamma_T(\delta)\) and the enlarged universal constant \(C\). The terminal events are run with \(\delta_\star=\exp\{-\Gamma_T(\delta)\}\). Because \(T_0=32dL/\mu\ge32\), \[\delta_\star = \frac{\delta}{e\,J_T\,(e+T_0)\,\log(e+\mathfrak S)} \le \frac{\delta}{6},\] so the three terminal failures contribute at most a fixed fraction of \(\delta\). A final union bound over \[\delta_{\rm scan}+\delta_{\rm prod}+\delta_u+3\delta_\star\le\delta\] gives the claimed probability.

The symbols \(\delta_K^{(\cdot)}=\delta_\star\) only set the deterministic thresholds in the fixed-\(K\) event notation; no union bound over \(K\) is taken. The weighted-suffix part follows from Lemma 2. The norm event \(\mathcal{E}_u\) follows from Lemma 8 and the dimension condition \(d\ge16\log(6T/\delta)\). This is the only direct union bound over individual Gaussian norms. The same dimension condition is used below to show that the prefix-scan confidence correction is uniformly bounded after division by \(T_0\), thereby producing a polynomial envelope for the product weights. These two uses are accounted for separately from the stitched \(\Gamma_T(\delta)\) confidence factor.

For the actual product-linear term, define \[q_t := 1-\frac{2d}{T_t}\zeta_t, \qquad P_0:=1,\qquad P_K:=\prod_{t=0}^{K-1}q_t.\] Since \(T_0=32dL/\mu\ge32d\), all \(q_t\in[15/16,1]\). The prefix upper-tail control, using the scan confidence factor \[\Gamma_T^{\rm scan}(\delta) := 1+\log\frac{6}{\delta}+\log J_T+\log(e+T_0),\] from Lemma 23, gives \[\label{eq:prefix95angle95product95envelope} d\sum_{t=0}^{K-1}\frac{\zeta_t}{T_t} \le C\Lambda+C\frac{\Gamma_T^{\rm scan}(\delta)}{T_0}, \qquad K\le T.\tag{17}\] Indeed, the dimension assumption gives \[\log T+\log\frac{1}{\delta}\le C d,\] while \(J_T\le C(1+\log(e+T+T_0))\). Since \(T_0=32dL/\mu\ge32d\), the remaining terms satisfy \[\frac{\log J_T+\log(e+T_0)}{T_0}\le C.\] Consequently \(\Gamma_T^{\rm scan}(\delta)/T_0\le C\), after increasing the universal constant \(C\). Since \(\Lambda=\log(T+T_0)\ge1\), Eq. 17 gives the simpler bound \[d\sum_{t=0}^{K-1}\frac{\zeta_t}{T_t} \le C\Lambda, \qquad K\le T.\] Moreover \(0\le 2d\zeta_t/T_t\le1/16\), and \(-\log(1-x)\le2x\) for \(0\le x\le1/16\). Hence, for every \(K\le T\), \[\log P_K^{-2} = -2\sum_{t=0}^{K-1}\log\left(1-\frac{2d\zeta_t}{T_t}\right) \le 4\sum_{t=0}^{K-1}\frac{2d\zeta_t}{T_t} = 8d\sum_{t=0}^{K-1}\frac{\zeta_t}{T_t} \le C\Lambda.\] Exponentiating and enlarging the universal constant gives \[P_K^{-2}\le e^{C\Lambda}=(T+T_0)^{C_P},\qquad K\le T,\] for a universal constant \(C_P\). The factor \(\Lambda=\log(T+T_0)\) is used here only to obtain this polynomial envelope for the product weights; the corresponding confidence cost below enters through the dyadic intrinsic-variance scale, not through a terminal-time union bound. Thus the event \(\mathcal{P}_T(C_P)\) in Lemma 7 holds on the weighted-scan event.

The deterministic envelopes in Eq. 6 are chosen with \(C_A\) large enough to dominate the terminal raw-projection transfer used in the induction proof below. Let \[U_T:=(T+T_0)^{C_P}\max_{K\le T}\bar A_K.\] Since Eq. 6 depends on \(K\) only through \(T_K^{-2}\), and since \(T_0\le T_K\le T+T_0\), uniformly over \(K\le T\), \[\frac{U_T}{\bar A_K} = (T+T_0)^{C_P} \max_{\ell\le T}\left(\frac{T_K}{T_\ell}\right)^2 \le (T+T_0)^{C_P}\left(\frac{T+T_0}{T_0}\right)^2 \le C(T+T_0)^{C_P+2}.\] The preceding polynomial ratio contributes only a double logarithm in \(T+T_0\). This term is controlled by the confidence factor because \[\frac{T(T+T_0)}{T_0}\ge T \quad\Longrightarrow\quad J_T\ge1+\lceil\log_2 T\rceil,\] so \(\log J_T\) controls \(\log\log(e+T)\) up to a universal constant, while \(\log(e+T_0)\) absorbs the remaining small-\(T\) and offset terms. Hence the preceding polynomial ratio gives \[\max_{K\le T} \log\left(1+\log\left(e+\frac{U_T}{\bar A_K}\right)\right) \le C\,\Gamma_T(\delta).\] Because \(\Gamma_T(\delta)\ge1+\log(1/\delta_{\rm prod})\), Lemma 7 with \(\delta_{\rm lin}:=\delta_{\rm prod}\) and \(G=\Gamma_T(\delta)\) gives, outside an additional failure probability \(\delta_{\rm prod}\), the implication \[A_K^\Pi\le\bar A_K \quad\Longrightarrow\quad \sum_{k=0}^{K-1}Y_{K,k}^{\Pi} \le C_Y\sigma\sqrt{\bar A_K\,\Gamma_T(\delta)}\] simultaneously for every \(K\le T\). Since \(\delta_K^{(Y)}=\delta_\star=e^{-\Gamma_T(\delta)}\), this is exactly \(\mathcal{L}_K(\bar A_K)\) for all \(K\le T\).

It remains to place the nonnegative controls required by the induction on the same event. These controls are used only with terminal index \(T\), so no terminal-time stitching is needed. Apply Lemma 9, Lemma 10, and Lemma 12 once, with \(K=T\), deterministic envelope \(\bar\Delta_k=\mathcal{C}d\Theta_T/T_k\), and confidence parameter \(\delta_\star\). Since \(\log(1/\delta_\star)=\Gamma_T(\delta)\), this gives \(\widehat{\mathcal{E}}_{V_T}\), \(\mathcal{E}_{Q_T}\), and \(\mathcal{E}_{\alpha_T}\) with the logarithmic thresholds recorded in Eq. ?? . Their total failure probability is at most \(3\delta_\star\), which is already included in the fixed confidence accounting at the start of the proof. Taking the intersection of this fixed finite family of controls proves the lemma. ◻