Proof of Lemma 1. Since \(L(x_1, x_2) = (x_1+x_2) A(x_2/(x_1+x_2))\) for all \(\boldsymbol{x} =(x_1, x_2) \in [0,\infty)^d\) such that \(x_1 + x_2>0\), we have, for \(\boldsymbol{x} \in (0,\infty)^2\), \[\begin{align} \partial_{1} L(x_1, x_2) &= A\Big(\frac{x_2}{x_1+x_2}\Big) -\frac{x_2}{x_1+x_2}A'\Big(\frac{x_2}{x_1+x_2}\Big), \\ \partial_{2} L(x_1, x_2) &= A\Big(\frac{x_2}{x_1+x_2}\Big) + \frac{x_1}{x_1+x_2}A'\Big(\frac{x_2}{x_1+x_2}\Big). \end{align}\] Moreover, \(\partial_{1} L(x_1, 0) = \partial_{2} L(0,x_2) = 1\) for \(x_1,x_2>0\). Continuity of \(\partial_{1} L\) on \((0,\infty)^2\) is immediate. Further, for a sequence \(\boldsymbol{x}_n\) in \((0,\infty)^2\) converging to \(\boldsymbol{x}=(x_1, 0)\) with \(x_1>0\), we have \(\lim_{n\to\infty}x_{n2}/(x_{n1}+x_{n2})=0\), which implies \(\lim_{n\to\infty} \partial_{1} L(\boldsymbol{x}_n) = A(1)=1=\partial_{1} L(\boldsymbol{x})\) by continuity of \(A\) on \([0,1]\) and boundedness of \(A'\) on \((0,1)\). Hence, \(\partial_{1} L\) is continuous on \(E_1\), and the same arguments show continuity of \(\partial_{2} L\) on \(E_2\). Regarding the second-order partial derivatives, note that, for \(\boldsymbol{x} \in (0,\infty)^2\), \[\begin{align} \partial_{11} L (x_1,x_2) &= \frac{x_2^2}{(x_1+x_2)^3}A''\Big(\frac{x_2}{x_1+x_2}\Big) = \frac{t^2 A''(t)}{x_1+x_2} \\ \partial_{22} L (x_1,x_2) &= \frac{x_1^2}{(x_1+x_2)^3}A''\Big(\frac{x_2}{x_1+x_2}\Big) = \frac{(1-t)^2 A''(t)}{x_1+x_2} \\ \partial_{12} L(x_1,x_2) &= -\frac{x_1x_2}{(x_1+x_2)^3}A''\Big(\frac{x_2}{x_1+x_2}\Big) = - \frac{t(1-t) A''(t)}{x_1+x_2}, \end{align}\] where we write \(t=x_2/(x_1+x_2)\). Continuity on \((0,\infty)^2\) is immediate. Moreover, \[\begin{align} \frac{t^2 A''(t)}{x_1+x_2} &= t(1-t)A''(t) \frac{x_2}{x_1+x_2} \frac{1}{x}_1 \le A_\infty \frac{1}{x_1} \\ \frac{(1-t)^2 A''(t)}{x_1+x_2} &= t(1-t)A''(t) \frac{x_1}{x_1+x_2} \frac{1}{x}_2 \le A_\infty \frac{1}{x_2} \end{align}\] and \[\begin{align} \Big|-\frac{t(1-t) A''(t)}{x_1+x_2} \Big| \le \frac{A_\infty}{x_1+x_2} \le \frac{A_\infty}{x_1 \vee x_2}, \end{align}\] which finalizes the proof. ◻

Proof of Theorem 2 and Theorem 3. We start by noting that our assumption \(n/k \ge T\) implies that, for any \(\boldsymbol{x} \in [0,T]^d\), we have \(kx_j/n \le 1\) for all \(j \in [d]\). In the subsequent proof, we will only consider such \(\boldsymbol{x}\).

Recall the definition \(\boldsymbol{V}_i=(V_{i1}, \dots, V_{id})^\top\) with \(V_{ij}=1-F_j(X_{ij})\) for \(j\in[d]\) and \(i\in[n]\). Let \(V_{1:n,j} \le V_{2:n, j} \le \dots \le V_{n:n,j}\) denote the order statistics of \(V_{1j}, \dots V_{nj}\), and define \(Q_{nj}(v_j) = V_{\lceil nv_j \rceil:n, j}\) for \(v_j \in (0,1]\), where \(\lceil a \rceil\) denote the smallest integer not smaller than \(a\). For completeness, we define \(Q_{nj}(0)=0\). Note that \(Q_{nj}(v_j) = G_{nj}^\leftarrow(v_j)\) with \(G_{nj}(u_j) = \frac{1}{n} \sum_{i=1}^n \boldsymbol{1}(V_{ij} \le u_j)\) the empirical cdf of \(V_{1j}, \dots, V_{nj}\) and \[\begin{align} \label{eq:generalized-inverse} H^\leftarrow(v) = \inf\{u \in[0,\infty): H(u) \ge v\} \end{align}\tag{31}\] the left-continuous generalized inverse of a non-decreasing function \(H:[0,\infty) \to [0,\infty)\).

Observing that the rank of \(V_{ij}\) among \(V_{1j}, \dots, V_{nj}\) is equal to \(n+1-R_{ij}\), we have \(V_{ij} < V_{\lceil kx_j \rceil:n, j}\) if and only if \(n+1-R_{ij} < \lceil kx_j \rceil\), which in turn is equivalent to \(R_{ij}>n+1-kx_j\) ². We may therefore write \(\widehat L_n(\boldsymbol{x})=\widetilde{L}_n(S_n(\boldsymbol{x}))\) for \(\boldsymbol{x} \in [0, T]^d\), where \(\widetilde{L}_n\) is from 8 and where \(S_n(\boldsymbol{x}) = (S_{n1}(x_1), \dots, S_{nd}(x_d))^\top\) with \[\begin{align} \label{eq:snj} S_{nj}(x_j) &= \frac{n}{k} Q_{nj}\Big(\frac{k}{n} x_j \Big) = \frac{n}{k} V_{\lceil kx_j \rceil:n, j} \boldsymbol{1}(x_j>0), \qquad j \in [d]. \end{align}\tag{32}\] Further, let \[\begin{align} \label{eq:Lnj-tilde} \widetilde{L}_{nj}(x_j) &:= \widetilde{L}_n(0, \dots, 0, x_j, 0, \dots 0) = \frac{1}{k} \sum_{i=1}^n \boldsymbol{1}\Big(V_{ij} < \frac{k}{n}x_j \Big) \end{align}\tag{33}\] and note that \(\widetilde{L}_{nj}^\leftarrow(x_j) = S_{nj}(x_j)\). Finally, recalling the definition of \(\widetilde{\mu}_n\) from 9 , note that \(\mathbb{E}[\widetilde{L}_n(\boldsymbol{x})]=\widetilde{\mu}_n(\boldsymbol{x})\) and that \(\widetilde{\mu}_{nj}(x_j):= \widetilde{\mu}_n(0, \dots, 0, x_j, 0, \dots 0)\) satisfies \(\widetilde{\mu}_{nj}(x_j)=\widetilde{\mu}^\leftarrow_{nj}(x_j)=x_j\).

The above definitions and identities imply the decomposition \[\begin{align} \label{eq:decomposition1-Lbn} \mathbb{L}_n = \sqrt k (\widehat L_n - L ) &= \nonumber \sqrt k (\widetilde{L}_n \circ S_n - \widetilde{\mu}_n \circ S_n) + \sqrt k (L \circ S_n - L) + \sqrt k (\widetilde{\mu}_n \circ S_n - L \circ S_n) \\&= \widetilde{\mathbb{L}}_n \circ S_n + \sqrt k (L \circ S_n - L) + \sqrt k (\widetilde{\mu}_n - L) \circ S_n. \end{align}\tag{34}\] By Lemma 115 , we have, on an event \(\Omega_0\) with probability at least \(1-(d+1)\delta\), \[\begin{align} \label{eq:Snj-uniform-bound} \max_{j\in[d]} \sup_{x_j \in [0,T]} |S_{nj}(x_j) - x_j| \le C_{s}r(\delta,T,k), \end{align}\tag{35}\] where \(C_{s}\approx 89.18\) is from Lemma 11 and where \(r\) is defined in 13 . Subsequently, we work on this event.

We now distinguish between the two theorems: under the conditions of Theorem 2, we have \(C_{s}r \le \kappa_L\) by our assumption \(r \le \kappa_L/C_{s}\). Hence, for any \(\boldsymbol{x} \in A\), we have \(S_n(\boldsymbol{x}) \in A^{\oplus \kappa_L}\), whence we can apply [cond:smoothness-hoelder] and the mean value theorem to conclude that there exists a (random) \(t^* := t^*_n(\boldsymbol{x}) \in [0,1]\) such that \[\begin{align} \sqrt k \{ L(S_n(\boldsymbol{x})) - L(\boldsymbol{x}) \} &= \sum_{j \in [d]} \partial_{j} L(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x}))\sqrt k\{ S_{nj}(x_j) - x_j \}. \end{align}\] Likewise, under the conditions of Theorem 3, for any \(\boldsymbol{x} \in [0,T]^d \setminus (\mathfrak B^{\oplus C_{s}r})\), we have \(S_n(\boldsymbol{x}) \in [0,T+C_{s}r]^d \setminus \mathfrak B\) by 35 , and [cond:smoothness-good] and the mean value theorem allows to conclude that the previous display holds for any \(\boldsymbol{x} \in [0,T]^d \setminus (\mathfrak B^{\oplus C_{s}r})\).

In the following, we either consider \(\boldsymbol{x} \in A\) (Theorem 2), or \(\boldsymbol{x} \in [0,T]^d \setminus (\mathfrak B^{\oplus C_{s}r})\) (Theorem 3). In both cases, the previous display and 34 , together with the definitions \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) = \widetilde{\mathbb{L}}_n(\boldsymbol{x}) - \sum_{j=1}^d \partial_{j} L(\boldsymbol{x}) \widetilde{\mathbb{L}}_{nj}(x_j)\) and \(B_n(\boldsymbol{x}) = \sqrt k \{ \widetilde{\mu}_n(\boldsymbol{x}) - L(\boldsymbol{x})\}\), imply the fundamental decomposition \[\begin{align} \label{eq:decomposition2-Lbn} \mathbb{L}_n(\boldsymbol{x}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n (\boldsymbol{x}) - B_n(S_n(\boldsymbol{x})) = D_{n1}(\boldsymbol{x}) + D_{n2}(\boldsymbol{x}) + D_{n3}(\boldsymbol{x}), \end{align}\tag{36}\] where \[\begin{align} D_{n1}(\boldsymbol{x}) \tag{37} & = \widetilde{\mathbb{L}}_n \circ S_n(\boldsymbol{x}) - \widetilde{\mathbb{L}}_n(\boldsymbol{x}), \\ D_{n2}(\boldsymbol{x}) \tag{38} &= \sum_{j \in [d]} \partial_{j} L\big(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x})\big) \big[ \sqrt k\{ S_{nj}(x_j) - x_j \} + \widetilde{\mathbb{L}}_{nj}(x_j) \big] \\ D_{n3}(\boldsymbol{x}) \tag{39} &=\sum_{j \in [d]} \big[ \partial_{j} L(\boldsymbol{x})- \partial_{j} L\big(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x})\big) \big] \widetilde{\mathbb{L}}_{nj}(x_j). \end{align}\] Moreover, since the partial derivatives of \(L\) are bounded by \(1\) (whenever they exist), we have \[\begin{align} \label{eq:definition-dn2-prime} |D_{n2}(\boldsymbol{x})| \le \sum_{j\in [d]} \Big|\sqrt k\{ S_{nj}(x_j) - x_j \} + \widetilde{\mathbb{L}}_{nj}(x_j) \Big| =: D_{n2}'(\boldsymbol{x}); \end{align}\tag{40}\] note that \(D_{n2}'\) is well-defined on \([0,\infty)^d\).

Regarding Theorem 2, its first result is now an immediate consequence of Lemma 2, 3 and 4. Moreover, \[\sup_{\boldsymbol{x} \in A} |B_n(S_n(\boldsymbol{x}))| \le \sup_{\boldsymbol{x} \in A^{\oplus C_{s}r}} |B_n(\boldsymbol{x})|\] is an immediate consequence of 35 .

Regarding Theorem 3, its first result is an immediate consequence of Lemma 2, 3 and 5. ◻

Proof of Lemma 2. Subsequently, let \(\Omega_0\) denote the event of probability at least \(1-(d+1)\delta\) on which 114 and 115 are met, and let \(C_{s}\approx 89.18\) denote the universal constant in 115 .

Let \(\boldsymbol{x} \in [0,T]^d\). Then, on \(\Omega_0\), we have \[\begin{align} \sup_{\boldsymbol{x}\in [0,T]^d} | D_{n1}(\boldsymbol{x}) | = \sup_{\boldsymbol{x}\in [0,T]^d} | \widetilde{\mathbb{L}}_n(S_n(\boldsymbol{x})) - \widetilde{\mathbb{L}}_n(\boldsymbol{x}) | \le \omega_{\widetilde{\mathbb{L}}_{n}}\Big(\max_{j \in [d]} \sup_{x_j \in [0,T]} |S_{nj}(x_j) - x_j |; [0,2T]^d\Big) \end{align}\] where \(\omega_{f}(\varepsilon;B)\) denotes the modulus of continuity of \(f\) with respect to the maximum norm as defined in 1 , and where we used 114 .

We next distinguish two cases. First, suppose that \(C_{s}r \le 2T\), where \(r=\sqrt{(T/k) \log(1/\delta)}\) is from 13 . Then, on the event \(\Omega_0\), by 114 and 115 , \[\begin{align} \sup_{\boldsymbol{x}\in [0,T]^d} | D_{n1}(\boldsymbol{x}) | \le \omega_{\widetilde{\mathbb{L}}_{n}}(C_{s}r; [0,2T]^d) = \sqrt{\frac{n}{k} } \omega_{ \beta_{n}}\Big(\frac{k}{n}C_{s}r; [0,2Tk/n]^d\Big), \end{align}\] with \(\beta_n\) from 118 . Next, by 119 from Lemma 12 (which is applicable since \(C_{s}r \le 2T\)), there exists a set \(\Omega_1\) with probability at least \(1-\delta\) such that, on \(\Omega_1\), \[\begin{align} \label{eq:lemma1-bound1} \sqrt{\frac{n}{k} }\omega_{ \beta_{n}}\Big(\frac{k}{n}C_{s}r; [0,2Tk/n]^d\Big) \le \kappa \sqrt{C_{s}r \log\Big(\frac{4dT}{C_{s}r\delta}\Big)}, \end{align}\tag{43}\] where \[\kappa = 2d \Big[ \sqrt{\frac{4}{9C_{s}kr} \log\Big( \frac{4dT}{C_{s}r\delta}\Big)} + 2 +60 \sqrt{2d} \Big].\] Since \(\log(x) \le x\) and \(1 \le \log(1/\delta) \le 2kT/7\), we have \[\begin{align} \label{eq:bound-kappa} \frac{4}{9C_{s}kr} \log\Big( \frac{4dT}{C_{s}r\delta}\Big) &= \nonumber \frac{4}{9C_{s}kr} \Big\{ \log \Big(\frac{4dT}{C_{s}r}\Big) + \log(1/\delta) \Big\} \\&\le \nonumber \frac{4}{9C_{s}kr} \Big\{ \frac{4dT}{C_{s}r} + \sqrt{\log(1/\delta)\cdot2kT/7}\Big\} \\&= \frac{4}{9C_{s}kr} \Big\{ \frac{4d rk}{C_{s}\log(1/\delta)} + \sqrt{2/7}rk\Big\} \le \frac{4}{9C_{s}} \Big\{ \frac{4d}{C_{s}} + \sqrt{2/7}\Big\}; \end{align}\tag{44}\] note that the upper bound only depends on \(d\). As a consequence, by 43 , there exist constants \(D_{1,1}=D_{1,1}(d)\) and \(D_{1,2}=D_{1,2}(d)\) only depending on \(d\) such that, on \(\Omega_1\), \[\begin{align} \sqrt{\frac{n}{k} }\omega_{ \beta_{n}}\Big(\frac{k}{n}C_{s}r; [0,2Tk/n]^d\Big) \le D_{1,1} \sqrt{r \log\Big(\frac{TD_{1,2}}{r\delta}\Big)} = \lambda_{n,k,d,T}^{(1)}(\delta), \end{align}\] which in turn implies 41 on the event \(\Omega_0 \cap \Omega_1\) and in the case \(C_{s}r \le 2T\). The assertion follows from the fact that this event has probability at least \(1-(d+2)\delta\).

It remains to treat the case \(C_{s}r > 2T\). In that case, on \(\Omega_0\), by the triangle inequality, \[\begin{align} \sup_{\boldsymbol{x}\in [0,T]^d} | D_{n1}(\boldsymbol{x}) | \le 2 \sup_{\boldsymbol{x} \in [0,2T]^d} |{\widetilde{\mathbb{L}}_{n}} (\boldsymbol{x}) |. \end{align}\] By Lemma 10, there exists an event \(\Omega_1'\) that has probability at least \(1-\delta\) such that, on \(\Omega_1'\) and with \(C_{s}\) from 115 , \(\sup_{\boldsymbol{x} \in [0,2T]^d} |{\widetilde{\mathbb{L}}_{n}} (\boldsymbol{x}) | \le (188/3) \cdot \sqrt 2 \cdot d \sqrt{T \log(1/\delta)} \le C_{s}d \sqrt{T\log(1/ \delta)}\). Hence, on \(\Omega_0 \cap \Omega_1'\), we have \[\begin{align} \sup_{\boldsymbol{x}\in [0,T]^d} | D_{n1}(\boldsymbol{x}) | \le 2 C_{s}d \sqrt{T \log(1/\delta)} &\le \sqrt{2} C_{s}^{3/2} d \sqrt{r \log(1/\delta)} \\&\le \sqrt{2} C_{s}^{3/2} d \sqrt{r\log\Big(\frac{\sqrt{2/7} \cdot T}{r\delta} \Big)}, \end{align}\] where we used that \(T \le C_{s}r/2\) and \(r \le \sqrt{2/7} \cdot T\) at the last two inequalities. By possibly increasing \(D_{1,1}\) and \(D_{1,2}\), the upper bound is bounded by \(\lambda_{n,k,d,T}^{(1)}(\delta)\). Overall, we have shown that 41 holds on the event \(\Omega_0 \cap \Omega_1'\) and in the case \(C_{s}r > 2T\). The assertion follows from the fact that this event has probability at least \(1-(d+2)\delta\). ◻

Proof of Lemma 3. We start by writing \[\begin{align} \sqrt k\{ S_{nj}(x_j) - x_j \} &=- \sqrt k \{ \widetilde{L}_{nj}(S_{nj}(x_j)) - S_{nj}(x_j) \} + \sqrt k \{ \widetilde{L}_{nj}(S_{nj}(x_j)) - x_j \} \\ &= - \widetilde{\mathbb{L}}_{nj} \circ S_{nj}(x_j) + \sqrt k \{ \widetilde{L}_{nj}(\widetilde{L}_{nj}^\leftarrow(x_j)) - x_j \} \end{align}\] A picture reveals that \(|\widetilde{L}_{nj}(\widetilde{L}_{nj}^\leftarrow(x_j)) - x_j| \le k^{-1}\) for all \(x_j \le n/k\). Hence, since \(n/k\ge T\) by assumption, we obtain the bound \[D_{n2}'(\boldsymbol{x}) \le \sum_{j\in [d]} \Big|\sqrt k\{ S_{nj}(x_j) - x_j \} + \widetilde{\mathbb{L}}_{nj}(x_j) \Big| \le \frac{d}{\sqrt k} + \sum_{j\in [d]} \Big| \widetilde{\mathbb{L}}_{nj}(x_j) - \widetilde{\mathbb{L}}_{nj} \circ S_{nj}(x_j) \Big|.\]

We now argue as in the proof of Lemma 2: let \(\Omega_0\) denote the event of probability at least \(1-(d+1)\delta\) on which 114 and 115 are met, and let \(C_{s}\ge 1\) denote the universal constant in 115 . In the case where \(C_{s}r\le 2T\), we then have, on \(\Omega_0\), \[\begin{align} \sup_{\boldsymbol{x} \in [0,T]^d} D_{n2}'(\boldsymbol{x}) &\le \frac{d}{\sqrt{k}} + d \max_{j \in [d]} \omega_{\widetilde{\mathbb{L}}_{n,j}}(C_{s}r; [0,2T]) = \frac{d}{\sqrt{k}} + d \max_{j \in [d] } \sqrt{\frac{n}{k} } \omega_{ \beta_{n,j}}\Big(\frac{k}{n}C_{s}r; [0,2Tk/n]\Big), \end{align}\] where \(r=\sqrt{(T/k)\log(1/\delta)}\) is as in 13 and where \(\beta_{n,j}\) is the \(j\)th margin of \(\beta_n\) from 118 . As a consequence, by Lemma 12 and the union bound, \[\begin{align} \sup_{\boldsymbol{x} \in [0,T]^d} D_{n2}'(\boldsymbol{x}) &\le \frac{d}{\sqrt{k}} + d \kappa \sqrt{C_{s}r\log\Big(\frac{4T}{C_{s}\delta r}\Big)} \end{align}\] with probability at least \(1-(2d+1)\delta\), where \[\kappa=2\Big[ \sqrt{\frac{4}{9C_{s}kr} \log\Big( \frac{4T}{C_{s}r\delta}\Big)} + 2 +60 \sqrt{2} \Big] \le 2\Big[ \frac{2\sqrt{4+C_{s}(2/7)^{1/2}}}{3C_{s}} + 2 + 60\sqrt 2\Big]\] and where we used 44 with \(d=1\) for the last inequality. We hence find universal constants \(D_{2,1}\) and \(D_{2,2}\) such that that 42 holds with with probability at least \(1-(2d+1)\delta\), for the case \(C_{s}r\le 2T\).

For the case \(C_{s}r > 2T\), note that \(\widetilde{\mathbb{L}}_{nj}(x_j) = \widetilde{\mathbb{L}}_{nj}(0,\dots,0,x_j,0,\dots,0)\) and thus \[\max_{j \in [d]} \omega_{\widetilde{\mathbb{L}}_{n,j}}(C_{s}r; [0,2T]) \le \omega_{\widetilde{\mathbb{L}}_{n}}(C_{s}r; [0,2T]^d).\] Using the bound \[\max_{j \in [d]} \omega_{\widetilde{\mathbb{L}}_{n,j}}(C_{s}r; [0,2T]) \le 2 \max_{j \in [d]} \sup_{x_j \in [0,2T]}\big|\widetilde{\mathbb{L}}_{n,j}(x_j)\big|\] and then arguing similarly to the case \(C_{s}r > 2T\) in the proof of Lemma 2 completes the proof after possibly enlarging \(D_{2,1}\) and \(D_{2,2}\). ◻

Proof of Lemma 4. Recall that, for \(\boldsymbol{x} \in A\), \[\begin{align} D_{n3}(\boldsymbol{x}) =\sum_{j \in [d]} \big[ \partial_{j} L(\boldsymbol{x})- \partial_{j} L\big(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x})\big) \big] \widetilde{\mathbb{L}}_{nj}(x_j), \end{align}\] with \(t^*=t^*(n,x)\in[0,1]\). By Lemma 11, it holds that \(\max_{j\in[d]} \sup_{x_j \in [0,T]} |S_{nj}(x_j) - x_j| \le C_{s}r\) on a set \(\Omega_0\) of probability at least \(1-(d+1)\delta.\) Hence, on this set, the assumption \(C_{s}r \le \kappa_L\) and [cond:smoothness-hoelder] imply that \[\big| \partial_{j} L(\boldsymbol{x})- \partial_{j} L\big(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x}) \big| \le K_L\|\boldsymbol{x} - S_{n}(\boldsymbol{x})\|^{\alpha_L}_{\infty} \le K_L(C_{s}r)^{\alpha_L}\] for all \(\boldsymbol{x}\in A\). As a consequence, \[|D_{n3}(\boldsymbol{x})| \le K_L(C_{s}r)^{\alpha_L} \sum_{j \in[d]} |\widetilde{\mathbb{L}}_{nj}(x_j)| \le d K_L(C_{s}r)^{\alpha_L} \max_{j\in [d]} \sup_{x_j \in [0,T]} |\widetilde{\mathbb{L}}_{nj}(x_j) |.\] By Lemma 10, with probability at least \(1-d\delta\), \[\max_{j \in [d]} \sup_{x_j \in [0,T]} |\tilde{\mathbb{L}}_{nj}(x_j) | \le (188/3) \sqrt{T\log(1/\delta)} \le C_{s}\sqrt{T\log(1/\delta)}.\] Combining the previous displays, we find that \[\sup_{\boldsymbol{x} \in A} |D_{n3}(\boldsymbol{x})| \le C_{s}^{1+\alpha_L} K_Ld r^{\alpha_L} \sqrt{T \log(1/\delta)}\] with probability at least \(1-(2d+1)\delta\). Choosing \(D_{3} = C_{s}^{1+\alpha_L} K_Ld\) yields the desired bound. ◻

Proof of Lemma 5. Subsequently, let \(\Omega_0\) denote the event of probability at least \(1-(d+1)\delta\) on which 114 and 115 are met, and let \(C_{s}\approx 89.18\) denote the universal constant in 115 .

Recall that, for \(\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})\), \[\begin{align} D_{n3}(\boldsymbol{x}) =\sum_{j \in [d]} \big[ \partial_{j} L(\boldsymbol{x})- \partial_{j} L\big(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x})\big) \big] \widetilde{\mathbb{L}}_{nj}(x_j), \end{align}\] with \(t^*=t^*(n,x)\in[0,1]\). We now distinguish two cases, according to whether \(4C_{s}r \le T\) or \(4C_{s}r>T\). In the latter case, using that \(0 \le \partial_{j} L(\cdot ) \le 1\) and Lemma 10 (which is applicable since \(\log(1/\delta) \le \log(d/\delta) \le 2kT/7 \le Tk\)), we have \[\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}(\boldsymbol{x})| \le d \max_{j\in [d]} \sup_{x_j < T} \big| \widetilde{\mathbb{L}}_{nj}(x_j) \big| \le d(188/3) \sqrt{T \log(1/\delta)} = d C_{s}\sqrt{T\log(1/\delta)/2}\] with probability at least \(1-d\delta\). Since \(T<4C_{s}r\) and \(r \le \sqrt{2/7} \cdot T \le T\), the upper bound satisfies \[d C_{s}\sqrt{T \log(1/\delta) /2 } \le d C_{s}^{3/2} \sqrt{2r \log(1/\delta)} \le d C_{s}^{3/2} \sqrt{2r \log\Big(\frac{T}{r\delta} \Big)} \le \lambda_{n,k,m,T,K_L}^{(4)},\] provided we choose \(D_{4}\ge d C_{s}^{3/2}\sqrt{2}\). Note that we do not need any smoothness assumptions on \(L\) here.

It remains to treat the case \(4C_{s}r \le T\). For each \(\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})\), we may decompose \[D_{n3}(\boldsymbol{x}) = D_{n3}^0(\boldsymbol{x}) + D_{n3}^+(\boldsymbol{x}) := \sum_{j\in [d]} A_{nj}(\boldsymbol{x}) \boldsymbol{1}(x_j < 2C_{s}r) + \sum_{j\in [d]} A_{nj}(\boldsymbol{x}) \boldsymbol{1}(x_j \in [2C_{s}r,T])\] where \[A_{nj}(\boldsymbol{x}) := \big[ \partial_{j} L(\boldsymbol{x})- \partial_{j} L\big(\boldsymbol{x} + t^*(S_n(\boldsymbol{x}) - \boldsymbol{x})\big) \big] \widetilde{\mathbb{L}}_{nj}(x_j).\] We start by bounding \(D_{n3}^0(\boldsymbol{x})\). Again using that \(0 \le \partial_{j} L(\cdot) \le 1\), we have, for any \(j \in [d]\), \[|A_{nj}(\boldsymbol{x})| \boldsymbol{1} (x_j < 2C_{s}r) \le \sup_{0 < x_j < 2C_{s}r} \big|\widetilde{\mathbb{L}}_{nj}(x_j) \big|.\] As a consequence, again by Lemma 10 applied with \(T = 2C_{s}r\) and \(d=1\), the union bound and the fact that \(r \le T\), we have \[\label{eq:bound-dn3-0} \sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^0(\boldsymbol{x})| \le d C_{s}^{3/2} \sqrt{r \log(1/\delta)} \le d C_{s}^{3/2} \sqrt{r\log\Big(\frac{T}{r\delta} \Big)}\tag{45}\] with probability at least \(1-d\delta\); note that Lemma 10 can be applied with \(T = 2C_{s}r\) here because \(\log(1/\delta) = r\sqrt{k\log(1/\delta) /T} \le \sqrt{2/7}\cdot rk = [\sqrt{2/7} / (2C_{s})] \cdot 2C_{s}r k \le 2C_{s}r k\) by assumption.

We continue by bounding \(\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^+(\boldsymbol{x})|\). Again working on the set \(\Omega_0\), note that \(\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})\) implies that \([\boldsymbol{x}, S_n(\boldsymbol{x})] \subseteq G :=[0,T]^d \setminus \mathfrak B\). Further, the condition \(x_j \ge 2C_{s}r\) implies that \(S_{nj}(x_j) \ge C_{s}r >0\). As a consequence, we may apply Lemma 13 to obtain the bound \[\begin{align} \big| A_{nj}(\boldsymbol{x}) \big| \boldsymbol{1}(x_j \in [2C_{s}r,T]) &\le K_L\max\Big\{\frac{1}{x_j},\frac{1}{S_{nj}(x_j)}\Big\} \| S_n(\boldsymbol{x}) - \boldsymbol{x}\|_1 \big| \widetilde{\mathbb{L}}_{nj}(x_j)\big| \boldsymbol{1} (x_j \in [2C_{s}r , T ]) \\ &\le K_Ld \times C_{n1} \times C_{n2}, \end{align}\] where \[\begin{align} C_{n1} &= \max_{\ell \in [d]} \sup_{x_\ell \in [0,T]} \big| S_{n\ell}(x_\ell) - x_\ell \big|, \\ C_{n2} &= \max_{j \in [d]} \sup_{x_j \in [2C_{s}r,T]} \max \Big\{\frac{1}{x_j},\frac{1}{S_{nj}(x_j)} \Big\} \big| \widetilde{\mathbb{L}}_{nj}(x_j)\big|, \end{align}\] which in turn yields \[\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^+(\boldsymbol{x})| \le K_Ld^2 \times C_{n1} \times C_{n2}.\] Since we are working on \(\Omega_0\), we have \(C_{n1} \le C_{s}r\). Concerning \(C_{n2}\), note that for \(x_j\ge 2C_{s}r\), \[\begin{align} S_{nj}(x_j) = x_j \Big(1+\frac{S_{nj}(x_j) - x_j}{x_j} \Big) &\ge x_j \Big(1- \frac{\max_{\ell \in [d]} \sup_{x_\ell \in [0,T]}|S_{n\ell}(x_j) - x_j| }{2C_{s}r} \Big) \\&= x_j \Big(1-\frac{C_{n1}}{2C_{s}r} \Big) \ge \frac{x_j}{2}, \end{align}\] where we have used that \(C_{n1} \le C_{s}r\) on the event \(\Omega_0\). As a consequence, with \(\beta_{nj}(u_j)\) the \(j\)th coordinate of \(\beta_n\) from 118 , \[\begin{align} C_{n2} \le 2\max_{j \in [d]} \sup_{x_j \in [2C_{s}r,T]} \frac{1}{x_j} \big| \widetilde{\mathbb{L}}_{nj}(x_j)\big| &\le 2 (2C_{s}r)^{-1/2} \max_{j \in [d]} \sup_{x_j \in [2C_{s}r,T]}\frac{1}{x_j^{1/2}} \big| \widetilde{\mathbb{L}}_{nj}(x_j)\big| \\&= 2^{1/2} (C_{s}r)^{-1/2} \max_{j \in [d]} \sup_{x_j \in [2C_{s}r,T]}\frac{1}{x_j^{1/2}} \Big|\sqrt{\frac{n}{k}}\beta_{nj}\Big(\frac{k}{n} x_j\Big)\Big| \\&= 2^{1/2} (C_{s}r)^{-1/2} \max_{j \in [d]} \sup_{x_j \in [ 2C_{s}r\frac{k}{n}, T\frac{k}{n}]} \frac{|\beta_{nj}(x_j)|}{{x_j}^{1/2}}. \end{align}\] Thus, on \(\Omega_0\), we obtain the upper bound \[\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^+(\boldsymbol{x})| \le K_Ld^2 (2C_{s}r)^{1/2} \max_{j \in [d]} \sup_{x_j \in [ 2C_{s}r\frac{k}{n}, T\frac{k}{n}]} \frac{|\beta_{nj}(x_j)|}{{x_j}^{1/2}}.\] By Corollary 11.2.1 on page 446 in [58] (with \(\delta=1/2\) in the notation of that reference; it should also be noted that some considerations show that the result also applies with our definition of \(\beta_{nj}\) that is based on ‘\(<\)’ instead of ‘\(\le\)’ inside the indicators), which is applicable since \(n/k\ge 2T\) by assumption and since \(2C_{s}r\tfrac{k}n / (T \tfrac{k}n) =2C_{s}r/T \le 1/2\) in our current case \(4C_{s}r \le T\), we have, for any \(\varepsilon>0\), \[\label{eq:showel95alpha47x-new} \mathbb{P}\Big( \sup_{x_1 \in [ 2C_{s}r\frac{k}{n}, T\frac{k}{n}]} \frac{\beta_{n1}(x_1)^{\pm}}{{x_1}^{1/2}} \ge \varepsilon\Big) \le 6 \log\Big( \frac{T}{2C_{s}r}\Big)\exp\Big(- \gamma_{\pm} \frac{\varepsilon^2}{8} \Big),\tag{46}\] where \(a^+ = \max(a,0)\) and \(a^- = \max(-a,0)\) for \(a \in \mathbb{R}\) and \(\gamma_- =1\) and \[\gamma_+ = \begin{cases} \frac{1}{2} & \text{if } \varepsilon\le \frac{3}{2}(2C_{s}kr)^{1/2},\\ \frac{3}{4} \frac{(2C_{s}kr)^{1/2}}{\varepsilon} & \text{if } \varepsilon> \frac{3}{2}(2C_{s}kr)^{1/2}. \end{cases}\]

We will later show that for \(\varepsilon=\lambda/(K_Ld^2(2C_{s}r)^{1/2})\) and our choice of \(\lambda\) below it holds that \(\varepsilon\le \frac{3}{2} \sqrt{2C_{s}rk}\). Then, since \(\gamma_- = 1 \ge 1/2 = \gamma_+\) and \(|a| = a^+ \vee a^-\) for any \(a\in \mathbb{R}\), Equation 46 implies that \[\mathbb{P}\Big( \sup_{x_1 \in [2r\frac{k}{n} ,T \frac{k}{n}]} \frac{|\beta_{n1}(x_1)|}{{x_1}^{1/2}} > \varepsilon\Big) \le 12 \log\Big( \frac{T}{2C_{s}r}\Big) \exp\Big(- \frac{\varepsilon^2}{16} \Big) .\] As a result, \[\begin{align} \mathbb{P}\Big( \Big\{\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^+(\boldsymbol{x})| > \lambda \Big\} \cap \Omega_0\Big) \le 12 d \log\Big( \frac{T}{2C_{s}r}\Big) \exp\Big(-\frac{\lambda^2}{32C_{s}K_L^2d^4 r} \Big) \end{align}\] which is equal to \(d\delta\) if we set \[\begin{align} \label{eq:lambda-dn543} \lambda = 4\sqrt{2C_{s}}K_Ld^2 \sqrt{r \log\Big(\frac{12 \log(T/(2C_{s}r))}{\delta}\Big)}. \end{align}\tag{47}\] Overall, \[\begin{align} \mathbb{P}\Big( \sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^+(\boldsymbol{x})| > \lambda \Big) &\le \mathbb{P}\Big( \Big\{\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})} |D_{n3}^+(\boldsymbol{x})| > \lambda \Big\} \cap \Omega_0 \Big) + \mathbb{P}(\Omega_0^c) \\&\le (2d+1)\delta, \end{align}\] and together with 45 , we get \[\sup_{\boldsymbol{x} \in [0,T]^d \setminus(\mathfrak B^{\oplus C_{s}r})}|D_{n3}(\boldsymbol{x})| \le d C_{s}^{3/2} \sqrt{r\log\Big(\frac{T}{\delta r}\Big)} + 4K_Ld^2 \sqrt{2C_{s}r \log\Big(\frac{12 \log(T/(2C_{s}r))}{\delta}\Big)}\] with probability at least \(1-(3d+1)\delta\). Since \(\log(x) \le x/e\) for \(x\ge 1\) \[\label{eq:lambda5bnd-new} \frac{12\log(T/(2C_{s}r))}{\delta} \le \frac{6e^{-1} T}{ \delta C_{s}r} \le \frac{T}{ \delta r},\tag{48}\] we obtain that, with probability at least \(1-(3d+1)\delta\), \[\sup_{\boldsymbol{x} \in W_m^0(T)} |D_{n3}(\boldsymbol{x})| \le \Big(d C_{s}^{3/2} + 4 K_Ld^2 \sqrt{2C_{s}} \Big) \sqrt{r \log\Big(\frac{T}{\delta r} \Big)},\] which is bounded by \(\lambda_{n,k,m,T,K_L}^{(4)}\) if we choose \(D_{4}\) at least as large as the term in round brackets. This yields the claim for the case \(4C_{s}r \le T\). The two cases \(4C_{s}r \le T\) and \(4C_{s}r> T\) can then easily be merged by choosing \(D_4\) appropriately.

Finally, we need to show that \(\varepsilon= \lambda/(K_Ld^2(2C_{s}r)^{1/2}) \le \frac{3}{2} \sqrt{2C_{s}kr}\) holds for \(\lambda\) in 47 , provided that \(4C_{s}r \le T\). Using 48 , we have \[\varepsilon= \frac{\lambda}{K_Ld^2\sqrt{2C_{s}r}} = 4\sqrt{ \log\Big(\frac{12 \log(T/(2C_{s}r))}{\delta}\Big)} \le 4\sqrt{\log\Big(\frac{6e^{-1}T}{C_{s}\delta r}\Big)}.\] Next, using \(r=\sqrt{T\log(1/\delta)/k} \ge\sqrt{T/k}\), \(C_{s}\ge 1\) and \(6 /e \ge 1\), and again using that \(\log(x)\le x/e\) for \(x \ge 1\), it follows that \[\log\Big(\frac{6e^{-1}T}{\delta C_{s}r}\Big)\le \log\Big(\frac{6e^{-1}\sqrt{Tk}}{\delta}\Big)\le 6e^{-2}\sqrt{Tk}+ \log(1/\delta).\] By assumption, we also have \(1\le \log(1/\delta) \le \sqrt{Tk\log(1/\delta)}\sqrt{2/7}\), which yields the upper bound \[6e^{-2}\sqrt{Tk}+ \log(1/\delta) \le \sqrt{Tk \log(1/\delta)}\big(6e^{-2} + \sqrt{2/7}\big).\] With \(16(6e^{-2} + \sqrt{2/7}) = 21.54\ldots < 22\) we obtain that \(\varepsilon^2 \le 22\sqrt{Tk\log(1/\delta)} = 22 rk\), which is bounded by \((9/2) C_{s}kr\) by definition of \(C_{s}\approx 89.18\) in Lemma 11. ◻

Proof of Theorem 7. Without loss of generality, we can assume that \(\log^5(pn) / k \le 1\); otherwise, the result is trivial.

The triangle inequality yields \[d_K(\boldsymbol{S}_n, \boldsymbol{G}_n) \le d_K(\boldsymbol{S}_n, \boldsymbol{T}_n) + d_K(\boldsymbol{T}_n, \boldsymbol{G}_n).\] We start by bounding \(d_K(\boldsymbol{S}_n , \boldsymbol{T}_n)\). An application of Lemma 14 yields, for any \(\lambda>0\), \[\begin{align} \label{eq:d-s-t} d_K(\boldsymbol{S}_n , \boldsymbol{T}_n) \le \mathbb{P}\big(\|\boldsymbol{S}_n-\boldsymbol{T}_n\|_\infty \ge \lambda\big) + \sup_{\boldsymbol{x} \in \mathbb{R}^p} \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}+\lambda \boldsymbol{1} ) - \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}-\lambda \boldsymbol{1}). \end{align}\tag{49}\] The first term can be dealt with using Corollary 1. Denote by \(\lambda=\lambda_{n,k}(\delta)\) the upper bound in Corollary 1 for suitable \(\delta\) chosen below and for \(T=1\); we justify below that the corollary can be applied. With this, we obtain that \[\begin{align} \mathbb{P}\Big(\| \boldsymbol{S}_n - \boldsymbol{T}_n \|_\infty > \lambda \Big) = \mathbb{P}\Big( \max_{\boldsymbol{y} \in A} \big|{\mathbb{L}}_{n}(\boldsymbol{y}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n}(\boldsymbol{y}) \big| > \lambda \Big) \le |\mathcal{I}|(6m+5) \delta \le 11|\mathcal{I}|m\delta. \end{align}\] Regarding the supremum on the right of 49 , we have, by Theorem 18, \[\begin{align} &\phantom{{}={}} \nonumber \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}+\lambda\boldsymbol{1} ) - \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}-\lambda\boldsymbol{1} ) \\&= \nonumber \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}+\lambda\boldsymbol{1} ) - \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}-\lambda\boldsymbol{1} ) + \big\{ \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}+\lambda\boldsymbol{1} ) - \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}+\lambda\boldsymbol{1} ) \big\} \\&\nonumber + \big\{ \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}-\lambda\boldsymbol{1} ) - \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}-\lambda\boldsymbol{1} ) \big\} \\&\le\nonumber \frac{2\lambda}{\sigma_{\min}^2} \big\{ 2+\sqrt{2\log p} \big\} + 2 d_K(\boldsymbol{T}_n, \boldsymbol{G}_n) \\&\le \label{eq:bound-dK} \frac{8\lambda}{\sigma_{\min}^2} \sqrt{\log p} + 2 d_K(\boldsymbol{T}_n, \boldsymbol{G}_n) \end{align}\tag{50}\] where we have used that \(p \ge 2\) and that \(2/\sqrt{\log(2)}+\sqrt 2 \approx 3.81 \le 4\) at the last inequality. Overall, \[\label{eq:cltXZ} d_K(\boldsymbol{S}_n, \boldsymbol{G}_n) \le 11|\mathcal{I}|m\delta + \frac{8\lambda_{n,k}(\delta)}{\sigma_{\min}^2} \sqrt{\log(p)} + 3 d_K(\boldsymbol{T}_n, \boldsymbol{G}_n).\tag{51}\] We proceed by bounding \(d_K(\boldsymbol{T}_n, \boldsymbol{G}_n)\). Note that the coordinates of \(\boldsymbol{T}_n\) are of the form \(\sum_{i=1}^n Y_{i,n,I}(\boldsymbol{x}_I)\), where \[\begin{align} Y_{i,n,I}(\boldsymbol{x}_I) &= \frac{1}{\sqrt k} \Big[ \boldsymbol{1}(\exists j \in I: V_{ij} < kx_j/n) - \mathbb{P}(\exists j \in I: V_{ij} < kx_j/n) \\ & - \sum_{j\in I} \partial_{j} L_I(\boldsymbol{x}_I) \big\{\boldsymbol{1}(V_{ij} < kx_j/n) - kx_j/n \big\} \Big], \end{align}\] with \(\mathbb{E}[Y_{i,n,I}(\boldsymbol{x}_I) ]=0\) and \(\sum_{i=1}^n \mathbb{E}[|Y_{i,n,I}(\boldsymbol{x}_I)|^2 ]\) equal to one of the diagonal entries of \(\Sigma_n\). We are going to apply the CCK-result from Theorem 19, and need to check its conditions. The first conditions holds with \(b_1=\sigma_{\min}^2\). The second and third condition hold with \(B_n = (m+1) (\log 2)^{-1} \sqrt{n/k}\) and \(b_2 = 4(1+m)m(\log2)^2\); indeed, \[\begin{align} \sum_{i=1}^n \mathbb{E}[|Y_{i,n,I}(\boldsymbol{x}_I) |^{4}] &\le \nonumber (1+m)^3\frac{n}{k^{3/2}} \mathbb{E}[|Y_{i,n,I}(\boldsymbol{x}_I)|] \\&\le \nonumber 2(1+m)^3\frac{1}{k} \Big[ \widetilde{\mu}_{n,I}(\boldsymbol{x}_I) + \sum_{j \in I} x_j \Big] \\&\le \label{eq:bound-yni4} 4(1+m)^3m \frac{1}{k}= b_2 B_n^2 \frac{1}{n}, \end{align}\tag{52}\] where we used the triangle inequality, the fact that that for a Bernoulli\((p)\) random variable \(X\) we have \(\mathbb{E}|X-p| = 2p(1-p) \le 2p\), and \(|\widetilde{\mu}_{n,I}(\boldsymbol{x}_I)| \le \sum_{j \in I} x_j \le m\) by the union bound. Moreover \[\sqrt n|Y_{i,n,I}(\boldsymbol{x}_I) | / B_n \le \sqrt{n/k} (m+1)/B_n = \log(2).\] An application of Theorem 19 then yields \[3d_K(\boldsymbol{T}_n , \boldsymbol{G}_n) \le c_1 \Big( \frac{\log^5(pn)}{k} \Big)^{1/4},\] for some constant \(c_1\) depending on \(\sigma_{\min}^2\) and \(m\) only.

It remains to bound the first and second term in 51 , for which we use \[\delta=\frac{1}{m|\mathcal{I}|}\Big( \frac{\log^5(pn)}{k} \Big)^{1/4}\] to balance the first and the last term. Indeed, the first term in 51 then satisfies \[11|\mathcal{I}|m\delta \le 11 \Big( \frac{\log^5(pn)}{k} \Big)^{1/4}.\]

Finally, regarding the second summand in 51 , we start by justifying the application of Corollary 1 with the above choice of \(\delta\) and with \(T=1\). First, our assumption \(\log^5(pn) / k \le 1\) from the beginning of the proof implies that \(\delta \le 1/(m|\mathcal{I}|) < 1/e\), while the assumption \(\log(m^2 |\mathcal{I}|k^{1/4} ) \le 2k/7\) yields, \[\begin{align} \log(m/\delta) &= \log\Big( \frac{m^2|\mathcal{I}|k^{1/4}}{\log^{5/4}(pn)}\Big) \le \log(m^2 |\mathcal{I}| k^{1/4}) \le 2k/7. \end{align}\] Finally, the assumption \(\log(m |\mathcal{I}|k^{1/4} ) \le \kappa_L^2 k/ C_{s}^2\) yields \[r = \sqrt{\frac{1}{k}\log\Big( \frac{1}{\delta}\Big)} = \sqrt{\frac{1}{k}\log\Big( \frac{m|\mathcal{I}|k^{1/4}}{\log^{5/4}(pn)} \Big)} \le \sqrt{\frac{1}{k}\log( m|\mathcal{I}|k^{1/4})} \le \kappa_L/C_{s}.\] Overall, all Conditions of Corollary 1 are met.

It remains to bound the second summand in 51 , which is \[\begin{align} \label{eq:bound-on-logp-term} \frac{8\lambda_{n,k}(\delta)}{\sigma_{\min}^2} \sqrt{\log(p)} &= \nonumber \frac{8}{\sigma_{\min}^2} \sqrt{\log(p)} \Big\{ \max_{I \in \mathcal{I}} B_{n,k,T}(L_I; A_I^{\oplus \kappa_L})+ \frac{m}{\sqrt{k}} \\&+ D_{1} \sqrt{r\log\Big(\frac{D_{2}}{\delta r}\Big)} + D_3 r^{\alpha_L}\sqrt{ \log\Big(\frac{1}{\delta}\Big)} \Big\}. \end{align}\tag{53}\] First, since \(\log(p)/k \le 1\) by our assumption at the beginning of the proof, we have \[\sqrt{\frac{\log p}{k}} \le \Big( \frac{\log p}{k} \Big)^{1/4} \le \Big( \frac{\log^5(pn)}{k} \Big)^{1/4}.\] Next, with our above choice of \(\delta\), we have, using \(|\mathcal{I}| \le p\) and the fact that \(pk \ge 2\) implies \(\log(mpk) \le C_{1,m}^2 \log(pk)\) with \(C_{1,m} = \{1 + \log(m)/\log(2)\}^{1/2}\), \[r = \sqrt{\frac{1}{k} \log\Big( \frac{m|\mathcal{I}|k^{1/4}}{\log^{5/4}(pn)}\Big)} \le \sqrt{\frac{1}{k} \log\big(m p k^{1/4}\big)} \le C_{1,m} \sqrt{\frac{\log( p k)}{k}}\] Also, \[\delta = \frac{1}{m|\mathcal{I}|} \Big( \frac{\log^5(pn)}{k} \Big)^{1/4} \ge \frac{1}{m|\mathcal{I}|k^{1/4}} \ge \frac{1}{mpk^{1/4}}\] and \(r \ge k^{-1/2}\) (since \(\delta < 1/e\)). Hence, the last two terms in 53 can be bounded as follows: first, \[\begin{align} \sqrt{r\log\Big(\frac{D_{2}}{\delta r}\Big)} \sqrt{\log p} &\le \Big(\frac{C_{1,m}^2\log(pk)}{k} \Big)^{1/4} \sqrt{\log(D_2mpk^{3/4}) \log p} \\&\le \Big(\frac{C_{1,m}^2\log(pk)}{k} \Big)^{1/4} \sqrt{D_2'\log(pk) \log p} \\&\le (C_{1,m}D_2')^{1/2} \Big(\frac{\log^5(pk)}{k} \Big)^{1/4}\le (C_{1,m}D_2')^{1/2} \Big(\frac{\log^5(pn)}{k} \Big)^{1/4}, \end{align}\] where \(D_2'=1+ \log(D_2m)/\log (2)\) only depends on \(m\). Second, \[\begin{align} r^{\alpha_L}\sqrt{\log\Big(\frac{1}{\delta }\Big)} \sqrt{\log p} &\le C_{1,m}^{\alpha_L}\Big(\frac{\log(pk)}{k} \Big)^{\alpha_L/2} \sqrt{\log(mpk^{1/4}) \log p} \\&\le C_{1,m}^{\alpha_L}\Big(\frac{\log(pk)}{k} \Big)^{\alpha_L/2} \sqrt{C_{1,m}^2\log(pk) \log p} \\&\le C_{1,m}^{1+\alpha_L}\Big(\frac{\log(pk)}{k} \Big)^{1/4} \sqrt{\log(pk) \log p} \\&\le C_{1,m}^2 \Big(\frac{\log^5(pn)}{k} \Big)^{1/4}, \end{align}\] where we used that \(\alpha_L \in [1/2,1]\) and that \(\log(pk)/k \le 1\) (which is a consequence of our assumption at the beginning of the proof). Assembling terms starting from 51 , we have shown that \[\begin{align} d_K(\boldsymbol{S}_n, \boldsymbol{G}_n) &\le \frac{8}{\sigma_{\min}^2} \sqrt{\log p} \Big(\max_{I \in \mathcal{I}} B_{n,k,T}(L_I; A_I^{\oplus \kappa_L}) \Big) \\ &+ \Big(c_1 + 11 + 8\frac{m + D_1(C_{1,m}D_2')^{1/2} + D_3 C_{1,m}^2}{\sigma_{\min}^2} \Big) \Big(\frac{\log^5(pn)}{k} \Big)^{1/4}, \end{align}\] which implies the assertion. ◻

Proof of Remark 10. A generic element of \(\Sigma_n\), say the entry at position \((q,q') \in [p]^2\), can be written as \[\begin{align} \sigma_{n,I,J}(\boldsymbol{x}_I, \boldsymbol{x}_J) = \mathbb{E}[ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{x}_I) \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,J}(\boldsymbol{x}_J)] \end{align}\] for certain \(I, J \in \mathcal{I}\) and \(\boldsymbol{x}_I \in A_I, \boldsymbol{x}_J \in A_J\). Write \[\begin{align} Y_{I}(\boldsymbol{x}_I) = \frac{1}{\sqrt k}\Big[ \boldsymbol{1}(J_{I}(\boldsymbol{x}_I)) - \mathbb{P}(J_{I}(\boldsymbol{x}_I)) - \sum_{j \in I} \partial_{j} L_I(\boldsymbol{x}_I) \big\{\boldsymbol{1}(J_{j}(x_{I,j})) - kx_{I,j}/n \big\} \Big], \end{align}\] where \(\boldsymbol{x}_I=(x_{I,j})_{j \in I} \in (0,1]^I\), \(J_{I}(\boldsymbol{x}_I) = \{ \exists j \in I: V_{j} < kx_{I,j}/n\}\) and \(J_{j}(x_{I,j})=J_{\{j\}}(x_{I,j})=\{V_{j} < kx_{I,j}/n\}\). We then have \[\begin{align} \sigma_{n,I,J}(\boldsymbol{x}_I, \boldsymbol{x}_J) &=\nonumber n \mathbb{E}[Y_{I}(\boldsymbol{x}_I) Y_{J}(\boldsymbol{x}_J)] \\&= \nonumber \frac{n}{k} \bigg[ \mathbb{P}[J_{I}(\boldsymbol{x}_I) \cap J_{J}(\boldsymbol{x}_J)] - \mathbb{P}[J_{I}(\boldsymbol{x}_I)] \mathbb{P}[J_{J}(\boldsymbol{x}_J)] \\ &- \nonumber \sum_{\ell \in I}\partial_{\ell} L_I(\boldsymbol{x}_I) \Big\{ \mathbb{P}[J_{\ell}( x_{I,\ell}) \cap J_{J}(\boldsymbol{x}_J)] - \frac{kx_{I,\ell}}{n} \mathbb{P}[J_{J}(\boldsymbol{x}_J)] \Big\} \\ &- \nonumber \sum_{j \in J}\partial_{j} L_J(\boldsymbol{x}_J) \Big\{ \mathbb{P}[J_{j}(x_{J,j}) \cap J_{I}(\boldsymbol{x}_I)] - \frac{kx_{J,j}}{n} \mathbb{P}[J_{I}(\boldsymbol{x}_I)] \Big\} \\ &+ \label{eq:covariance-formula} \sum_{\ell \in I, j \in J}\partial_{\ell} L_I(\boldsymbol{x}_I)\partial_{j} L_J(\boldsymbol{x}_J) \Big\{ \mathbb{P}[J_{\ell}(x_{I,\ell}) \cap J_{j}(x_{J,j})] - \frac{k^2x_{I,\ell}x_{J,j}}{n^2} \Big\} \bigg]. \end{align}\tag{54}\] The variance is obtained for \(I=J\) and \(\boldsymbol{x}_I = \boldsymbol{x}_J\), which yields \[\begin{align} \sigma_{n,I}^2(\boldsymbol{x}_I) &= \frac{n}{k} \bigg[ \mathbb{P}[J_{I}(\boldsymbol{x}_I)] - \mathbb{P}[J_{I}(\boldsymbol{x}_I)]^2 \\ &- 2 \sum_{\ell \in I}\partial_{\ell} L_I(\boldsymbol{x}_I) \Big\{ \frac{kx_{I,\ell}}{n} - \frac{kx_{I,\ell}}{n} \mathbb{P}[J_{I}(\boldsymbol{x}_I)] \Big\} \\ &+ \sum_{\ell \in I}\{ \partial_{\ell} L_I(\boldsymbol{x}_I) \}^2 \Big\{ \frac{kx_{I,\ell}}{n} - \frac{k^2x_{I,\ell}^2}{n^2} \Big\} \\ &+ \sum_{j,\ell \in I, j \ne \ell}\partial_{\ell} L_I(\boldsymbol{x}_I)\partial_{j} L_I(\boldsymbol{x}_I) \Big\{ \mathbb{P}[J_{\ell}(x_{I,\ell}) \cap J_{j}(x_{I,j})] - \frac{k^2x_{I,\ell}x_{I,j}}{n^2} \Big\} \bigg], \end{align}\] where we have used that \(\mathbb{P}[J_{\ell}(x_{I,\ell}) \cap J_{I}(\boldsymbol{x}_I)] =\mathbb{P}[J_{\ell}(x_{I,\ell})] = kx_{I,\ell}/n\). As a consequence, \[\begin{align} \sigma_I^2 (\boldsymbol{x}_I) = \lim_{n \to \infty}\sigma_{n,I}^2(\boldsymbol{x}_I) &= L_I(\boldsymbol{x}_I) - \sum_{\ell \in I}x_{I,\ell}\partial_{\ell} L_I(\boldsymbol{x}_I) \{ 2-\partial_{\ell} L_I(\boldsymbol{x}_I)\} \\ &+ 2\sum_{j,\ell \in I, j < \ell}\partial_{\ell} L_I(\boldsymbol{x}_I)\partial_{j} L_I(\boldsymbol{x}_I) R_{\{j, \ell\}}(x_{I,j}, x_{I,\ell}). \end{align}\] Homogeneity of \(L_I\) implies that the directional derivative of \(L_I\) in \(\boldsymbol{x}_I\) in direction \(\boldsymbol{v}=\boldsymbol{x}_I/\| \boldsymbol{x}_I\|_2\) is given by \[\partial_{\boldsymbol{v}} L_I(\boldsymbol{x}_I) = \lim_{h \to 0}h^{-1}\{ L_I(\boldsymbol{x}_I+h\boldsymbol{x}_I/\| \boldsymbol{x}_I\|_2) - L_I(\boldsymbol{x}_I)\} = L_I(\boldsymbol{x}_I) / \| \boldsymbol{x}_I\|_2.\] If \(L_I\) is differentiable at \(\boldsymbol{x}_I\) (a consequence of convexity and existing continuous partial derivatives in neighbourhood of \(\boldsymbol{x}_I\); see Lemma 15), we obtain that \[L_I(\boldsymbol{x}_I) = \| \boldsymbol{x}_I\|_2 \cdot \partial_{\boldsymbol{v}} L_I(\boldsymbol{x}_I) = \| \boldsymbol{x}_I\|_2 \cdot \langle \boldsymbol{v}, \nabla L_I(\boldsymbol{x}_I)) = \sum_{\ell \in I} x_{I,\ell} \partial_{\ell} L_I(\boldsymbol{x}_I).\] As a consequence, we may write \[\begin{align} \sigma_I^2 (\boldsymbol{x}_I) &= - \boldsymbol{x}_I^\top \nabla L_I(\boldsymbol{x}_I) + (\nabla L_I(\boldsymbol{x}_I))^\top \mathcal{R}_I (\nabla L_I(\boldsymbol{x}_I)) \\&= - L_I(\boldsymbol{x}_I) + (\nabla L_I(\boldsymbol{x}_I))^\top \mathcal{R}_I (\nabla L_I(\boldsymbol{x}_I)) , \end{align}\] where \(\mathcal{R}_I = (R_{j,\ell}(x_{I,j}, x_{I,\ell}))_{j,\ell \in I}\) is a \(|I| \times |I|\) matrix, with diagonal entries \(R_{j,j}(x_{I,j}, x_{I,j}) = x_{I,j}\). Suppose that \(\mathcal{R}_I\) is positive definite. Then, by the Cauchy-Schwarz-inequality, \[(\nabla L_I(\boldsymbol{x}_I))^\top \mathcal{R}_I (\nabla L_I(\boldsymbol{x}_I)) \ge \frac{(\boldsymbol{x}_I^T \nabla L_I(\boldsymbol{x}_I))^2}{\boldsymbol{x}_I^\top \mathcal{R}_I^{-1} \boldsymbol{x}_I} = \frac{L_I^2(\boldsymbol{x}_I)}{\boldsymbol{x}_I^\top \mathcal{R}_I^{-1} \boldsymbol{x}_I},\] which yields \[\sigma_I^2 (\boldsymbol{x}_I) \ge - L_I(\boldsymbol{x}_I) + \frac{L_I^2(\boldsymbol{x}_I)}{\boldsymbol{x}_I^\top \mathcal{R}_I^{-1} \boldsymbol{x}_I}.\] In the bivariate case \(I=\{j,\ell\}\) and \(\boldsymbol{x}_I=(x_j,x_\ell)\), some tedious but straightforward calculation shows that the right-hand side is equal to \[\frac{r(x_j+x_\ell - r)(x_j-r)(x_\ell-r)}{(x_j+x_\ell-2r)x_j x_\ell}\] where \(r=R_I(x_j,x_\ell)\) denotes the off-diagonal element of \(\mathcal{R}_I\). Since \(0 \le r \le x_j \wedge x_\ell\), the expression is strictly positive if an only if \(R_I \notin\{ R_{{\text{ind}}}, R_{\text{pd}}\}\), where \(R_{{\text{ind}}} \equiv 0\) and \(R_{\text{pd}}(x,y) = x \wedge y\) correspond to tail independence and perfect tail dependence, respectively. ◻

Proof of Theorem 11. The conditions of Proposition 15 are a subset of the conditions of Theorem 11, whence it suffices to show that the upper bound in ?? can be bounded as claimed in the theorem. Since \(n,p \ge 2\) we may assume without loss of generality that \(k \ge 2\), which yields \(\log(p+k) \le \log(pk) \le \log(pn)\). Hence, \[\begin{align} h\log(p+k) & \le c_h' [k^{-1}\log (p+k)]^{1/4} \log(p+k) \le c_h' \delta_n, \\ \frac{r_{n,2}\log(p+k)}{\sqrt{h}} &\le c_h^{-1/2}\frac{k^{-1/2}\log^{1/2}(pk) \log(p+k)}{k^{-1/4}\log^{1/4}(p+k)} \le c_h^{-1/2}\frac{\log^{5/4}(pk)}{k^{1/4}} \le c_h^{-1/2}\delta_n, \\ \frac{r_{n,2}^2\log(p+k)}{h} &\le c_h^{-1}\frac{k^{-1}\log(pk)\log(p+k)}{k^{-1/2}\log^{1/2}(p+k)} \le c_h^{-1}\frac{\log^{3/2}(pk)}{k^{1/2}} \le c_h^{-1} \delta_n^2, \\ \frac{\log(p+k)}{h\sqrt{k}} \Big[\frac{\log^3(pk)}{k} \Big]^{1/4} &\le c_h^{-1}\frac{\log(p+k)\log^{3/4}(pk)}{k^{3/4}k^{-1/2} \log^{1/2}(p+k)} \le c_h^{-1} \frac{\log^{5/4}(pk)}{k^{1/4}} \le c_h^{-1} \delta_n. \end{align}\] Finally \[\frac{\log(p+k)}{h\sqrt{k}} \le c_h^{-1}\frac{\log(p+k)}{k^{1/2}k^{-1/2} \log^{1/2}(p+k)} = c_h^{-1} \sqrt{\log(p+k)},\] so \[\frac{1}{h\sqrt{k}} B_{n,k}(L_I ; A_I^{\oplus\kappa_L})\log(p+k) \le c_h^{-1} \sqrt{\log(p+k)} B_{n,k}(L_I ; A_I^{\oplus\kappa_L}).\] Combining the above and noting that we can assume \(\delta_n \le 1\) since otherwise the bound is trivial by setting \(c_2=1\) completes the proof. ◻

Proof of Proposition 15. Throughout the proof we assume \(k^{-1}\log(pk) \le 1\) as the statement is trivial otherwise. By Lemma 6 we have with probability one \[\label{eq:boot-bound-KS-first} d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \boldsymbol{G}_n) \lesssim \frac{1}{k} + \frac{\Delta \cdot \log(p+k)}{\sigma_{\mathrm{min}}^2} + d_K( \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n).\tag{56}\] Set \[\delta := \frac{1}{m|\mathcal{I}|} \Big( \frac{\log^5(pn)}{k} \Big)^{1/4}.\] In the proof of Theorem 7 we verify that the conditions of Corollary 1 hold with this choice of \(\delta\). Moreover, \(n/k\ge 2\) by assumption, and using that \(|\mathcal{I}| \le p\) and \(\log(pn) \ge 1\), the assumption \(\log(mpk^{1/4}) \le \kappa_L^2/(8 C_{s}^2)\) implies \(r=\sqrt{k^{-1}\log(1/\delta)} \le \kappa_L/(2^{3/2} C_{s})\). Hence all conditions of Lemma 8 hold with this choice of \(\delta\). The latter lemma shows that, with probability at least \(1 - |\mathcal{I}|(6m+7)\delta\) \[\Delta \lesssim h + \sqrt{r} + \frac{r^2}{h} + \frac{r}{\sqrt{h}} + \frac{1}{h\sqrt{k}} \Big\{ B_{n,k}(L_I ; A_I^{\oplus\kappa_L}) + \sqrt{r \log\Big(\frac{1}{\delta r}\Big)} \Big\}\] where the implicit constant depends on \(m\) and \(K_L\) only.

The assumption \(p \ge 2\) implies \(\log(mpk) \le C_{1,m}^2 \log(pk)\), where \(C_{1,m} = \{1 + \log(m)/\log(2)\}^{1/2}\) only depends on \(m\). Recalling that \(p,n \ge 2\) and \(k^{-1}\log(pn) \le 1\), and noting \(p \ge |\mathcal{I}|\) by definition of \(\mathcal{I}\), we find \[r = \sqrt{\frac{1}{k} \log\Big( \frac{m|\mathcal{I}|k^{1/4}}{\log^{5/4}(pn)}\Big)} \le \sqrt{\frac{1}{k} \log\big(m p k^{1/4}\big)} \le C_{1,m} \sqrt{ \frac{\log(pk)}{k}}\] and \[\delta = \frac{1}{m|\mathcal{I}|} \Big( \frac{\log^5(pn)}{k} \Big)^{1/4} \ge \frac{1}{m |\mathcal{I}| k^{1/4} } \ge \frac{1}{mpk^{1/4}}.\] Thus, noting that \(r \ge k^{-1/2}\) (this follows from \(\delta < e^{-1}\)) \[r\log\Big(\frac{1}{r\delta}\Big) \le r \log(mpk^{3/4}) \le r \log(mpk) \le C_{1,m}^3 \Big[\frac{\log^3(pk)}{k} \Big]^{1/2}.\] In summary, there exists a universal constant \(c_1\) and constant \(c_{2,m}\) depending only on \(m\) and \(K_L\) such that, with probability at least \(1-c_1\delta_n\), \[\label{eq:boot-bound-Delta-final} \Delta \leq c_{2,m} \Big[ h + \sqrt{r_{2,n}} + \frac{r_{2,n}^2}{h} + \frac{r_{2,n}}{\sqrt{h}} + \frac{1}{h\sqrt{k}} \Big\{ B_{n,k}(L_I ; A_I^{\oplus\kappa_L}) + \Big[\frac{\log^3(pk)}{k} \Big]^{1/4} \Big\} \Big]\tag{57}\] where \(r_{2,n} = \sqrt{k^{-1}\log(pk)}\) as defined in the theorem..

To bound \(d_K( \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n)\) we apply Theorem 3 from [43]. In the proof of Theorem 7, we verified that the conditions of that theorem are satisfied by \(X_i\) in their notation replaced with \(\sqrt{n}\boldsymbol{Y}_{i,n}\) in our notation with \(\underline{\sigma}^2 = \sigma^2_{\mathrm{min}}\), \(B_n = (m+1)(\log 2)^{-1}\sqrt{n/k}\) and \(\overline{\sigma}^2 = 4 (\log 2)^2 m (m+1)\). From this we obtain, for constants \(c_{3,m}, c_{4,m}\) that depend on \(m, \sigma_{\mathrm{min}}\) only, \[\label{eq:boot-bound-KS} d_K( \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n) \leq c_{3,m}\delta_n\tag{58}\] with probability at least \(1-c_{4,m}\delta_n\). Combining the bounds in 56 –58 completes the proof. ◻

Proof of Lemma 6. By the triangle inequality, we have \[d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \boldsymbol{G}_n) \le d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data})) + d_K( \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n).\] To bound \(d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}))\) we will apply Lemma 14 conditionally on the data. Write \(\mathbb{P}_e\) and \(\mathbb{E}_e\) for the conditional probability/expectation given the data \((\boldsymbol{X}_1, \dots, \boldsymbol{X}_n)\). Then, for any \(\lambda>0\), \[\begin{align} d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data})) &\le \mathbb{P}_e( \| \boldsymbol{S}_n^* - \boldsymbol{S}_n^\circ\|_\infty \ge \lambda) \\ &+ \sup_{\boldsymbol{x} \in \mathbb{R}^p} \mathbb{P}_e( \boldsymbol{S}_n^\circ \le \boldsymbol{x}+\lambda \boldsymbol{1} ) - \mathbb{P}_e( \boldsymbol{S}_n^\circ \le \boldsymbol{x}-\lambda \boldsymbol{1}), \end{align}\] By the same calculation as in 50 in the proof of Theorem 7, we have \[\begin{align} &\phantom{{}={}} \mathbb{P}_e( \boldsymbol{S}_n^\circ \le \boldsymbol{x}+\lambda\boldsymbol{1} ) - \mathbb{P}_e( \boldsymbol{S}_n^\circ \le \boldsymbol{x}-\lambda\boldsymbol{1} ) \\&= \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}+\lambda\boldsymbol{1} ) - \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}-\lambda\boldsymbol{1} ) + \big\{ \mathbb{P}_e( \boldsymbol{S}_n^\circ \le \boldsymbol{x}+\lambda\boldsymbol{1} ) - \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}+\lambda\boldsymbol{1} ) \big\} \\& + \big\{ \mathbb{P}( \boldsymbol{G}_n \le \boldsymbol{x}-\lambda\boldsymbol{1} ) - \mathbb{P}_e( \boldsymbol{S}_n^\circ \le \boldsymbol{x}-\lambda\boldsymbol{1} ) \big\} \\&\le \frac{8\lambda}{\sigma_{\min}^2} \sqrt{\log p} + 2 d_K(\mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n) \end{align}\] where we have used Theorem 18. Overall, \[\begin{align} \label{eq:bound-boot} d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \boldsymbol{G}_n) \le \mathbb{P}_e( \| \boldsymbol{S}_n^* - \boldsymbol{S}_n^\circ\|_\infty \ge \lambda) + \frac{8\lambda}{\sigma_{\min}^2} \sqrt{\log p} + 3 d_K( \mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n), \end{align}\tag{60}\] and it remains to choose \(\lambda\) appropriately and to bound the first summand on the right. For that purpose, write \[\|\boldsymbol{S}_n^* - \boldsymbol{S}_n^\circ\|_\infty = \max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} |D_{I}(\boldsymbol{x}_I)| ,\] where \[\begin{align} D_{I}(\boldsymbol{x}_I) := \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup ^*_{n,I}(\boldsymbol{x}_I) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup ^\circ_{n,I}(\boldsymbol{x}_I) = \sum_{i=1}^n e_i S_{i,I}(\boldsymbol{x}_I) \end{align}\] with \(S_{i,I}(\boldsymbol{x}_I)\) defined in the statement of the lemma. We also let \[\Delta_I^2(\boldsymbol{x}_I) := \sum_{i=1}^n S_{i,I}^2(\boldsymbol{x}_I)\] and note that \(\Delta^2 = \max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} \Delta_I^2(\boldsymbol{x}_I)\).

Since the multipliers \(e_1,\dots,e_n\) are standard Gaussian, we have \[\mathbb{P}_e( D_{I}(\boldsymbol{x}_I) \in \cdot) = \mathcal{N}(0, \Delta_I^2(\boldsymbol{x}_I))(\cdot).\] For \(\eta>0\), let \[\lambda = \mathbb{E}_e[\max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} |D_{I}(\boldsymbol{x}_I)| ] + \eta.\] The Borell-TIS inequality [59] then yields \[\begin{align} \mathbb{P}_e\Big( \max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} |D_{I}(\boldsymbol{x}_I)| > \lambda\Big) &= \mathbb{P}_e\Big( \max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} |D_{I}(\boldsymbol{x}_I)| > \mathbb{E}_e[\max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} |D_{I}(\boldsymbol{x}_I)| ] + \eta\Big) \\&\le \exp\Big(- \frac{\eta^2}{2 \max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} \mathbb{E}_e[|D_{I}(\boldsymbol{x}_I)|^2 ]}\Big) \\&= \exp\Big(- \frac{\eta^2}{2 \Delta^2}\Big). \end{align}\] Moreover, by the inequality at the beginning of Section 2.5 in [60], we have \[\mathbb{E}_e\Big[\max_{I \in \mathcal{I}} \max_{\boldsymbol{x}_I \in A_I} |D_{I}(\boldsymbol{x}_I)| \Big] \le \Delta \sqrt{2\log(2p)} \le 2 \Delta \sqrt{\log p},\] where the last inequality follows from \(p \ge 2\). Using these bounds and definitions, 60 yields \[\begin{align} d_K( \mathcal{L}(\boldsymbol{S}_n^* \mid \mathrm{data}), \boldsymbol{G}_n) & \le \nonumber \exp\Big(- \frac{\eta^2}{2 \Delta^2}\Big) + \frac{8}{\sigma_{\min}^2} \eta\sqrt{\log p} + \frac{16}{\sigma_{\min}^2} \Delta \log p \\&+ 3 d_K(\mathcal{L}(\boldsymbol{S}_n^\circ \mid \mathrm{data}), \boldsymbol{G}_n). \end{align}\] Setting \(\eta = \Delta \sqrt{2\log k}\) and noting that \(\log k, \log p \leq \log(p+k)\) completes the proof. ◻

Proof of Lemma 7. We start by introducing the notation \[\begin{align} \label{eq:J95iI} J_{i,I} = \{ \exists j \in I: V_{ij} < kx_j/n \}, \qquad \hat{J}_{i,I} = \{ \exists j \in I: \hat{V}_{ij} < kx_j/n \}, \end{align}\tag{62}\] and note that \(\mathbb{P}(J_{i,I}) = (k/n) \widetilde{\mu}_{n,I}(\boldsymbol{x}_I)\). Hence, \[\begin{align} S_{i,I}(\boldsymbol{x}_I) &\equiv \widehat Y_{i,I}(\boldsymbol{x}_I) - Y_{i,I}(\boldsymbol{x}_I) + \frac{1}{n} \sum_{i'=1}^n Y_{i',I}(\boldsymbol{x}_I) =\frac{1}{\sqrt k } \big( A_{i,I} - B_{i,I} - C_{i,I} + D_{i,I} \big) \end{align}\] where \[\begin{align} A_{i,I} &= \boldsymbol{1}(\hat{J}_{i,I}) - \boldsymbol{1}(J_{i,I}) \\ B_{i,I} &= \frac{k}{n} \Big\{ \widehat L_{n,I}(\boldsymbol{x}_I) - \widetilde{\mu}_{n,I}(\boldsymbol{x}_I) \Big\} \\ C_{i,I} &= \sum_{j \in I} \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I) \Big\{ \boldsymbol{1}(\hat{V}_{ij} < kx_j/n) - kx_j/n \Big\} - \partial_{j} L_{I}(\boldsymbol{x}_I) \Big\{ \boldsymbol{1}(V_{ij} < kx_j/n) - kx_j/n \Big\} \\ D_{i,I} &= \frac{1}{n} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{x}_I); \end{align}\] note that \(B_{i,I}\) and \(D_{i,I}\) do not depend on \(i\). As a consequence, since \((a+b+c+d)^2 \le 4(a^2+b^2+c^2+d^2)\), we obtain that \(\sum_{i=1}^n S_{i,I}^2(\boldsymbol{x}_i) \le 4(A^2+B^2+C^2+D^2)\), where \[A^2 = \frac{1}{k}\sum_{i=1}^n A_{i,I}^2, \qquad B^2 =\frac{n}{k} B_{1,I}^2, \qquad C^2 = \frac{1}{k}\sum_{i=1}^n C_{i,I}^2, \qquad D^2 = \frac{n}{k} D_{1,I}^2.\] A direct computation yields \[D^2 \le \frac{1}{kn} | \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{x}_I)|^2 \le \frac{2}{kn} | \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I) |^2 + \frac{2|I|^2}{kn} \max_{j\in I} | \widetilde{\mathbb{L}}_{nj}(x_j)|^2.\] We will further show below that \[\begin{align} \tag{63} A^2 &\le \frac{|I|}{\sqrt k} \max_{j \in I} | \widetilde{\mathbb{L}}_{nj}(x_j)| + \frac{|I|}{k}, \\ \tag{64} B^2 &\le \frac{3|I|^2}{n} \max_{j\in I} | \widetilde{\mathbb{L}}_{nj}(x_j)|^2 + \frac{3}{n} | \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I) |^2 + \frac{3|I|^2}{kn}, \\ \tag{65} C^2 &\le 2|I|^2\max_{j\in I} \big| \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I) - \partial_{j} L_{I}(\boldsymbol{x}_I) \big|^2 + \frac{2|I|^2}{\sqrt k}\max_{j\in I} |\widetilde{\mathbb{L}}_{nj}(x_j)| + \frac{2|I|^2}{k}, \end{align}\] which in turn implies \[\begin{align} \sum_{i=1}^n S_{i,I}^2(\boldsymbol{x}_i) \le \frac{4|I|+(8+12/n)|I|^2}{k} &{} + \frac{4|I|+8|I|^2}{\sqrt k} \max_{j\in I} | \widetilde{\mathbb{L}}_{nj}(x_j)| \\&{} + \frac{(12+8/k)|I|^2}{n} \max_{j\in I} | \widetilde{\mathbb{L}}_{nj}(x_j)|^2 \\&{} + \frac{12+8/k}{n} | \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I) |^2 \\&{} + 8|I|^2\max_{j\in I} \big| \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I) - \partial_{j} L_{I}(\boldsymbol{x}_I) \big|^2. \end{align}\] The squared terms involving \(| \widetilde{\mathbb{L}}_{nj}(x_j)|^2\) and \(| \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I) |^2\) can be absorbed into the non-squared ones by using the trivial bounds \(| \widetilde{\mathbb{L}}_{nj}(x_j)| \le n/\sqrt k\) and \(| \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I) | \le n/\sqrt k\). Further, it follows from Lemma 9 that \[\begin{align} \big| \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I)- \partial_{j} L_{I}(\boldsymbol{x}_I) \big|^2 & \le 4K_L^2 h^2 + \frac{4}{h^2k}\sup_{\boldsymbol{y}_I \in \bar B_{h}(\boldsymbol{x}_I)} \big|\mathbb{L}_{n,I}(\boldsymbol{y}_I) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{y}_I)\big|^2 \\ &+ 4K_L^2 \frac{|I|^2}{k} \max_{j \in I}\sup_{y_j\in [x_j-h,x_j+h]} \big|\widetilde{\mathbb{L}}_{nj}(y_j)\big|^2 \\ &+ \frac{4}{h^2k} \omega_{\widetilde{\mathbb{L}}_{n,I}}(2h;\bar B_h(\boldsymbol{x}_I))^2. \end{align}\] Assembling terms we find the claimed bound in the formulation of the lemma.

It remains to show 63 65 . We start by showing 63 . For that purpose, note that \[\begin{align} \phantom{{}={}} \big| \boldsymbol{1}(\hat{J}_{i,I}) - \boldsymbol{1}(J_{i,I}) \big| &\le \sum_{j\in I} \big|\boldsymbol{1}(\hat{V}_{ij} < kx_j/n) - \boldsymbol{1}(V_{ij} < kx_j/n)\big|. \end{align}\] Subsequently, we fix \(j \in I\). By definition of \(\hat{V}_{ij}\), we have \(\hat{V}_{ij} < kx_j/n\) if and only if \(R_{ij}>n+1-kx_j\), which in turn is equivalent to \(V_{ij}<V_{\lceil kx_j \rceil:n,j}\), as shown at the beginning of the proof of Theorem 3. Hence, depending on whether \(V_{\lceil kx_j \rceil:n,j} < kx_j/n\) or not, we either have ‘\(\{\hat{V}_{ij} < kx_j/n\} \subseteq\{V_{ij} < kx_j/n\}\) for all \(i\in[n]\)’ or ‘\(\{V_{ij} < kx_j/n\} \subseteq\{\hat{V}_{ij} < kx_j/n\}\) for all \(i\in [n]\)’. It follows that all differences \(\boldsymbol{1}(\hat{V}_{ij} < kx_j/n) -\boldsymbol{1}(V_{ij}< k/n)\) with \(i \in [n]\) have the same sign, and we can rewrite \[\begin{align} \label{eq:sum-Ai-2} \sum_{i=1}^n \big|\boldsymbol{1}(\hat{V}_{ij} < kx_j/n) -\boldsymbol{1}(V_{ij} < kx_j/n)\big| &= \nonumber \Big|\sum_{i=1}^n \boldsymbol{1}(\hat{V}_{ij} < kx_j/n) -\boldsymbol{1}(V_{ij} < kx_j/n)\Big| \\&=\nonumber \Big|\sum_{i=1}^n \boldsymbol{1}(R_{ij} > n+1-\lceil kx_j \rceil ) -\boldsymbol{1}(V_{ij} < kx_j/n)\Big| \\&=\nonumber \Big|(\lceil kx_j \rceil -1) - k \widetilde{L}_{nj}(x_j)\Big| \\&\le \nonumber k |\widetilde{L}_{nj}(x_j) - x_j| + \big|(\lceil kx_j \rceil -1) - kx_j\big| \\&\le \sqrt k |\widetilde{\mathbb{L}}_{nj}(x_j) | + 1. \end{align}\tag{66}\] The previous two displays yield 63 .

We next show 64 . Note that \[\begin{align} B_{1,I} \nonumber = \frac{k}{n} \Big\{ \widehat L_{n,I}(\boldsymbol{x}_I) - \widetilde{\mu}_{n,I}(\boldsymbol{x}_I) \Big\} &= \frac{k}{n} \Big\{ \widehat L_{n,I}(\boldsymbol{x}_I) - \widetilde{L}_{n,I}(\boldsymbol{x}_I) + \widetilde{L}_{n,I}(\boldsymbol{x}_I) - \widetilde{\mu}_{n,I}(\boldsymbol{x}_I) \Big\} \\ &= \frac{k}{n} \Big\{ \widehat L_{n,I}(\boldsymbol{x}_I) - \widetilde{L}_{n,I}(\boldsymbol{x}_I) \Big\} + \frac{\sqrt{k}}{n}\widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I). \end{align}\] By the triangle inequality, we have \[\begin{align} \big|\widehat L_{n,I}(\boldsymbol{x}_I) - \widetilde{L}_{n,I}(\boldsymbol{x}_I) \big| \le \frac{1}{k} \sum_{i=1}^n \big| \boldsymbol{1}(\hat{J}_{i,I}) - \boldsymbol{1}(J_{i,I}) \big| &\le \label{eq:bound-for-b} \frac{|I|}{\sqrt k} \max_{j \in I} | \widetilde{\mathbb{L}}_{nj}(x_j)| + \frac{|I|}{k} \end{align}\tag{67}\] where we used 63 at the last inequality. The claimed identity in 64 then follows from combining the previous two displays and the inequality \((a+b+c)^2 \le 3(a^2+b^2+c^2)\).

We next show 65 , and for that purpose, note that \(C_{i,I}=\sum_{j \in I} C_{i,I,j}\), where \[\begin{align} C_{i,I,j} &\equiv \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I) \Big\{ \boldsymbol{1}(\hat{V}_{ij} < kx_j/n) - kx_j/n \Big\} - \partial_{j} L_{I}(\boldsymbol{x}_I) \Big\{ \boldsymbol{1}(V_{ij} < kx_j/n) - kx_j/n \Big\} \\&= \Big\{ \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I)- \partial_{j} L_{I}(\boldsymbol{x}_I) \Big\} \Big\{ \boldsymbol{1}(\hat{V}_{ij} < kx_j/n) - kx_j/n \Big\} \\ & + \partial_{j} L_{I}(\boldsymbol{x}_I) \Big\{\boldsymbol{1}(\hat{V}_{ij} < kx_j/n) - \boldsymbol{1}(V_{ij} < kx_j/n) \Big\} . \end{align}\] Next, \[\begin{align} \frac{1}{k} \sum_{i=1}^n \Big| \boldsymbol{1}(\hat{V}_{ij} < kx_j/n) - kx_j/n \Big|^2 &= \frac{1}{k} \Big\{ (1-2kx_j/n) \Big( \sum_{i=1}^n \boldsymbol{1}(\hat{V}_{ij} < kx_j/n) \Big) + k^2x_j^2/n \Big\} \\&= \frac{1}{k} \Big\{(1-2kx_j/n)(\lceil kx_j \rceil -1) + k^2x_j^2/n \Big\} \\& \le x_j (1-kx_j/n) \le x_j \le 1. \end{align}\] where we used the assumption that \(x_j \le 1 \le n/(2k)\) and the fact that \((\lceil kx_j \rceil -1) \le kx_j\). As a consequence, since \(0 \le \partial_{j} L(\boldsymbol{x}_I) \le 1\) and \((a+b)^2 \le 2(a^2+b^2)\), we obtain the bound \[\begin{align} \frac{1}{k} \sum_{i=1}^n C_{i,I,j}^2 &\le 2 \big| \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I)- \partial_{j} L_{I}(\boldsymbol{x}_I) \big|^2 + \frac{2}{k} \sum_{i=1}^n \big| \boldsymbol{1}(\hat{V}_{ij} \le kx_j/n) - \boldsymbol{1}(V_{ij} \le kx_j/n) \big|^2 \\&\le 2 \big| \widehat{\partial_{j} L}_{I}(\boldsymbol{x}_I)- \partial_{j} L_{I}(\boldsymbol{x}_I) \big|^2 + \frac{2}{\sqrt k} | \widetilde{\mathbb{L}}_{nj}(x_j)| + \frac{2}{k}, \end{align}\] where the last bound follows from 66 . This inequality, combined with \[\frac{1}{k} \sum_{i=1}^n C_{i,I}^2 \le \frac{1}{k} \sum_{i=1}^n |I| \sum_{j \in I} C_{i,I,j}^2 \le |I|^2 \max_{j \in I} \frac{1}{k} \sum_{i=1}^n C_{i,I,j}^2\] yields 65 . ◻

Proof of Lemma 8. Throughout the proof, \(\lesssim\) denotes inequality up to a constant only depending on \(m\) and \(K_L\). Fix some \(I \in \mathcal{I}\), and recall that \(|I| \le m\). We apply Lemma 7 with \(\varepsilon= (\kappa_L/2) \wedge 1\) and \(\boldsymbol{x}_I \in A_I\) to obtain that \[\begin{align} \label{eq:bound-on-si-uniform} \sup_{\boldsymbol{x}_I \in A_I} \Delta_I^2(\boldsymbol{x}_I) \lesssim h^2 + \frac{1}{k} + \frac{1}{\sqrt k}\sup_{\boldsymbol{y}_I \in [0,2]^I}\big|\widetilde{\mathbb{L}}_{n,I}(\boldsymbol{y}_I)\big| &{} \nonumber + \frac{1}{k}\sup_{\boldsymbol{y}_I \in [0,2]^I}\big|\widetilde{\mathbb{L}}_{n,I}(\boldsymbol{y}_I)\big|^2 \\&{} \nonumber + \frac{1}{h^2k}\sup_{\boldsymbol{y}_I \in A_I^{\oplus h}} \big|\mathbb{L}_{n,I}(\boldsymbol{y}_I) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{y}_I)\big|^2 \\&{} + \frac{1}{h^2k} \sup_{\boldsymbol{x}_I \in A_I} \omega_{\widetilde{\mathbb{L}}_{n,I}}(2h;\bar B_h(\boldsymbol{x}_I))^2. \end{align}\tag{68}\] where we have used that, for each \(\boldsymbol{x}_I \in A_I \subseteq(0,1]^I\), \[\max \Big(| \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x}_I) |, \max_{j \in I}\sup_{y_j\in [x_j-h,x_j+h]} \big|\widetilde{\mathbb{L}}_{nj}(y_j)\big| \Big) \le \sup_{\boldsymbol{y}_I \in [0,2]^I}\big|\widetilde{\mathbb{L}}_{n,I}(\boldsymbol{y}_I)\big|,\] (recall that \(h < \varepsilon\le 1\)). We need to bound each term on the right-hand side of 68 . First, by Lemma 10, we have \[\begin{align} \label{eq:sni-proof-1} \frac{1}{\sqrt k}\sup_{\boldsymbol{y}_I \in [0,2]^I}\big|\widetilde{\mathbb{L}}_{n,I}(\boldsymbol{y}_I)\big| \lesssim \sqrt{\frac{2}{k} \log\Big(\frac{1}{\delta}\Big)} \lesssim r \end{align}\tag{69}\] on an event \(\Omega_{I,1}\) with probability at least \(1-\delta\). Moreover, since \(r = \sqrt{k^{-1} \log(1/\delta)} \le \sqrt{2/7} < 1\) by our assumption \(\log(m/\delta) \le 2k/7\), the same upper bound holds true for the squared term \(k^{-1}\sup_{\boldsymbol{y}_I \in [0,2]^I}|\widetilde{\mathbb{L}}_{n,I}(\boldsymbol{y}_I)|^2\).

Next, we apply Theorem 2 with \(T=2\) (note that \(n/k \ge 2\) by assumption), \(L=L_I\) and \(A= A_I^{\oplus h}\); note that \(A_I^{\oplus h} \subseteq{A_I^{\oplus \min(1,\kappa_L/2)}}\) such that \((A_I^{\oplus h}, L_I)\) satisfies [cond:smoothness-hoelder] with \(\alpha_L =1\) by our assumption on \(L\). Further note that \(r(\delta,2,k)\) in Theorem 2 is equal to \(\sqrt 2 r = \sqrt{2} r(\delta,1,k)\) in our current notation. We obtain that \[\sup_{\boldsymbol{y}_I \in A_I^{\oplus h}} \big|\mathbb{L}_{n,I}(\boldsymbol{x}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{x})\big| \lesssim B_{n,k}(L_I ; A_I^{\oplus h+C_{s}\sqrt 2r}) + \frac{1}{\sqrt{k}} + \sqrt{r \log\Big(\frac{1}{\delta r}\Big)} + r\sqrt{\log\Big(\frac{1}{\delta}\Big)}\] on an event \(\Omega_{I,2}\) with probability at least \(1-(6m+5)\delta\). Since \(r \le \sqrt{2/7}<1\) as noted earlier, and \(\delta < 1/e\), we have \[\frac{1}{\sqrt{k}} + r\sqrt{\log\Big(\frac{1}{\delta}\Big)} \lesssim \sqrt{r \log\Big(\frac{1}{\delta r}\Big)}.\] Next, since \(h + C_{s}\sqrt 2 r \le \kappa_L/2+\kappa_L/2=\kappa_L\) by assumption, we have \[B_{n,k}(L_I ; A_I^{\oplus h+C_{s}\sqrt{2} r}) \le B_{n,k}(L_I ; A_I^{\oplus \kappa_L}).\] Overall, \[\begin{align} \label{eq:sni-proof-2} \frac{1}{h^2k}\sup_{\boldsymbol{y}_I \in A_I^{\oplus h}} \big|\mathbb{L}_{n,I}(\boldsymbol{x}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,I}(\boldsymbol{x})\big|^2 \lesssim \frac{1}{h^2k} \Big\{ B_{n,k}^2(L_I ; A_I^{\oplus\kappa_L}) + r \log\Big(\frac{1}{\delta r}\Big) \Big\}. \end{align}\tag{70}\] Next, from Lemma 12 we get \[\omega_{\widetilde{\mathbb{L}}_{n,I}}(2h;\bar B_h(\boldsymbol{x}_I)) = \sqrt{\frac{n}{k}} \omega_{\beta_{n,I}}\Big(\frac{k}{n} 2h ; \frac{k}{n}[\boldsymbol{x}_I - h \boldsymbol{1}_I,\boldsymbol{x}_I + h \boldsymbol{1}_I]\Big) \le \kappa \sqrt{2h \log(2 |I|/\delta)}\] on an event \(\Omega_{I,3}\) with probability at least \(1-\delta\), where \[\kappa = 2|I|\bigg[\sqrt{ \frac{2}{9kh}\log({2|I|}/{\delta})} + 2 + 60 \sqrt{2|I|}\bigg] \lesssim \Big(\frac{\log(1/\delta)}{kh}\Big)^{1/2} + 1.\] As a consequence, on \(\Omega_{I,3}\), \[\begin{align} \label{eq:sni-proof-3} \frac{1}{h^2k} \omega_{\widetilde{\mathbb{L}}_{n,I}}(2h;\bar B_h(\boldsymbol{x}_I))^2 \lesssim \frac{1}{kh} \kappa^2 \log(1/\delta) \lesssim \Big(\frac{\log(1/\delta)}{kh}\Big)^2 + \Big(\frac{\log(1/\delta)}{kh}\Big) = \frac{r^4}{h^2} + \frac{r^2}{h}. \end{align}\tag{71}\] Overall, combining 68 with 69 , 70 and 71 and the fact that \(k^{-1/2} \le r\), we find that, on the event \(\Omega_{I,1} \cap \Omega_{I,2} \cap \Omega_{I,3}\), \[\sup_{\boldsymbol{x}_I \in A_I} \Delta_I^2(\boldsymbol{x}_I) \lesssim h^2 + r + \frac{r^2}{h} + \frac{r^4}{h^2} + \frac{1}{h^2k} \Big\{ B_{n,k}^2(L_I ; A_I^{\oplus \kappa_L}) + r \log\Big(\frac{1}{\delta r}\Big) \Big\}.\] Moreover, \(\mathbb{P}(\Omega_{I,1} \cap \Omega_{I,2} \cap \Omega_{I,3}) \ge 1-(6m+7)\delta\). The assertion regarding the maximum over \(I \in \mathcal{I}\) then follows from the union bound. ◻

Proof. Note that \(|\min(a,1) - b| \le |a-b|\) for \(a \in \mathbb{R}, b \in [0,1]\). Together with the triangle inequality this yields \[\begin{align} \label{eq:pd-bound} |\widehat{\partial_{j} L}(\boldsymbol{x}) - \partial_{j} L(\boldsymbol{x}) | &\le \Big|\frac{\widehat L_n(\boldsymbol{x} + h \boldsymbol{e}_j) - L(\boldsymbol{x} + h \boldsymbol{e}_j)}{2h} - \frac{\widehat L_n(\boldsymbol{x} - h \boldsymbol{e}_j) - L(\boldsymbol{x} - h \boldsymbol{e}_j)}{2h}\Big| \nonumber\\ & + \Big|\frac{L(\boldsymbol{x} + h \boldsymbol{e}_j) - L(\boldsymbol{x} - h \boldsymbol{e}_j)}{2h} - \partial_{j} L(\boldsymbol{x})\Big| \nonumber\\ &= \Big|\frac{\mathbb{L}_n(\boldsymbol{x} + h \boldsymbol{e}_j) - \mathbb{L}_n(\boldsymbol{x} - h \boldsymbol{e}_j)}{2h\sqrt{k}} \Big| + \Big|\frac{L(\boldsymbol{x} + h \boldsymbol{e}_j) - L(\boldsymbol{x} - h \boldsymbol{e}_j)}{2h} - \partial_{j} L(\boldsymbol{x})\Big|. \end{align}\tag{72}\] We start with the second term on the right hand side. By the mean value theorem, there exists some \(t\in (-1,1)\) such that \[\frac{L(\boldsymbol{x} + h \boldsymbol{e}_j) - L(\boldsymbol{x} - h \boldsymbol{e}_j)}{2h} = \partial_{j} L(\boldsymbol{x} + t h \boldsymbol{e}_j).\] Using the Lipschitz continuity of \(\partial_{j} L\), we obtain \[\Big| \frac{L(\boldsymbol{x} + h \boldsymbol{e}_j) - L(\boldsymbol{x} - h \boldsymbol{e}_j)}{2h} - \partial_{j} L(\boldsymbol{x}) \Big| \le K_L|t| h \le K_Lh.\] For the first term on the right hand side of 72 , again using the triangle inequality, we have \[\begin{align} &\phantom{{}={}} \big| \mathbb{L}_n(\boldsymbol{x} + h \boldsymbol{e}_j) - \mathbb{L}_n(\boldsymbol{x} - h \boldsymbol{e}_j) \big| \\ &\le \big| \mathbb{L}_n(\boldsymbol{x} + h \boldsymbol{e}_j) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} + h \boldsymbol{e}_j) \big| + \big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} + h \boldsymbol{e}_j) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} - h \boldsymbol{e}_j) \big| \\& + \big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} - h \boldsymbol{e}_j) - \mathbb{L}_n(\boldsymbol{x} - h \boldsymbol{e}_j) \big| \\& \le 2\sup_{\boldsymbol{y} \in \bar B_{h}(\boldsymbol{x})} \big| \mathbb{L}_n(\boldsymbol{y}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{y}) \big| + \big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} + h \boldsymbol{e}_j) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} - h \boldsymbol{e}_j) \big|. \end{align}\] It remains to show that \[\big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} + h \boldsymbol{e}_j) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x} - h \boldsymbol{e}_j) \big| \le {2K_Ldh} \max_{j \in [d]} \sup_{y_j\in [x_j-h,x_j]} \big|\widetilde{\mathbb{L}}_{nj}(y_j)\big| + 2 \omega_{\widetilde{\mathbb{L}}_{n}}(2h;\bar B_{h}(\boldsymbol{x}))\] By definition of \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n}\), for any \(\boldsymbol{y}, \boldsymbol{y}' \in \bar B_\varepsilon(\boldsymbol{x})\), we have \[\begin{align} &\phantom{{}={}} \big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n}(\boldsymbol{y}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n}(\boldsymbol{y}')\big| \\ &\le \big|\widetilde{\mathbb{L}}_{n}(\boldsymbol{y}) - \widetilde{\mathbb{L}}_{n}(\boldsymbol{y}')\big| + \sum_{\ell \in [d]} \big|\partial_{\ell} L(\boldsymbol{y})\widetilde{\mathbb{L}}_{n\ell}(y_\ell) - \partial_{\ell} L(\boldsymbol{y}')\widetilde{\mathbb{L}}_{n\ell}(y_\ell')\big| \\ &\le \big|\widetilde{\mathbb{L}}_{n}(\boldsymbol{y}) - \widetilde{\mathbb{L}}_{n}(\boldsymbol{y}')\big| + \sum_{\ell \in [d]} \Big\{ \big|\partial_{\ell} L(\boldsymbol{y}) \big|\times\big|\widetilde{\mathbb{L}}_{n\ell}(y_\ell) - \widetilde{\mathbb{L}}_{n\ell}(y_\ell')\big| \\ & + \big|\widetilde{\mathbb{L}}_{n\ell}(y_\ell')\big|\times\big|\partial_{\ell} L(\boldsymbol{y}) - \partial_{\ell} L(\boldsymbol{y}')\big|\Big\} \\ &\le \big|\widetilde{\mathbb{L}}_{n}(\boldsymbol{y}) - \widetilde{\mathbb{L}}_{n}(\boldsymbol{y}')\big| + \sum_{\ell \in [d]} \Big\{\big|\widetilde{\mathbb{L}}_{n\ell}(y_\ell) - \widetilde{\mathbb{L}}_{n\ell}(y_\ell')\big| + \big|\widetilde{\mathbb{L}}_{n\ell}(y_\ell')\big|\times K_L\big\|\boldsymbol{y} -\boldsymbol{y}'\big\|_\infty\Big\}, \end{align}\] where we used \(|\partial_{\ell} L|\le 1\) and Lipschitz-continuity of the partial derivatives. For \(\boldsymbol{y} = \boldsymbol{x} + h \boldsymbol{e}_j\) and \(\boldsymbol{y}' = \boldsymbol{x} - h \boldsymbol{e}_j\), we obtain \[\big|{\widetilde{\mathbb{L}}}_{n}(\boldsymbol{y}) - {\widetilde{\mathbb{L}}}_{n}(\boldsymbol{y}')\big| \le \omega_{{\widetilde{\mathbb{L}}}_{n}}(2h;\bar B_{h}(\boldsymbol{x})).\] The term \(|\widetilde{\mathbb{L}}_{n\ell}(y_\ell) - \widetilde{\mathbb{L}}_{n\ell}(y_\ell')|\) equals zero for \(\ell \ne j\) and is bounded by \(\omega_{{\widetilde{\mathbb{L}}}_{n}}(2h;\bar B_{h}(\boldsymbol{x}))\) for \(\ell=j\). Finally, it holds that \[|\widetilde{\mathbb{L}}_{n\ell}(y_\ell')| \le \sup_{y_\ell \in [x_\ell-h, x_\ell]} |\widetilde{\mathbb{L}}_{n\ell}(y_\ell)|\] and \(\big\|\boldsymbol{y} -\boldsymbol{y}'\big\|_\infty = 2h.\) Combining the previous results yields the assertion. ◻

Proof of Theorem 14. Without loss of generality, we can assume that \(\log^5(pn) / k \le 1\); otherwise, the result is trivial. Under \(H(\rho)\), we can rewrite \[\begin{align} T_n^{(\rho)} &= \max_{(t,\boldsymbol{s}_1, \boldsymbol{s}_2,\boldsymbol{s}_1',\boldsymbol{s}_2') \in D(\rho)} \mathbb{D}_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) \end{align}\] where \(D(\rho)\) is from 29 and where \[\begin{align} \mathbb{D}_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) &= \mathbb{L}_{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - \mathbb{L}_{n,(\boldsymbol{s}_1', \boldsymbol{s}_2')}(1-t,t) \end{align}\] with \[\mathbb{L}_{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) = \sqrt k \{ \hat{L}_{(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) - L_{(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) \}.\] Likewise, we can rewrite \[T_n^{(\rho),*} = \max_{(t,\boldsymbol{s}_1, \boldsymbol{s}_2,\boldsymbol{s}_1',\boldsymbol{s}_2') \in D(\rho)} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup ^*_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t)\] where \[\begin{align} \label{eq:dbstar} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup ^*_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) = \sum_{i=1}^n e_{i} \big\{ \hat{Y}_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - \hat{Y}_{i,(\boldsymbol{s}_1', \boldsymbol{s}_2')}(1-t,t) \big\} \end{align}\tag{73}\] with \(\hat{Y}_{i, (\boldsymbol{s}_1, \boldsymbol{s}_2)}\) from 28 .

Next, recall \(D= D(1, \sqrt 2) = D(1) \cup D(\sqrt 2)\) with \(p = |D|\), and consider the stacked vectors \[\begin{align} \widetilde{\boldsymbol{S}}_n &= \big(\mathbb{D}_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t)\big)_{(t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2') \in D} \in \mathbb{R}^p, \\ \widetilde{\boldsymbol{T}}_n &= \big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup _{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t)\big)_{(t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2') \in D} \in \mathbb{R}^p, \\ \widetilde{\boldsymbol{S}}_n^* &= \big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup ^*_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t)\big)_{(t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2') \in D} \in \mathbb{R}^p, \end{align}\] where \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup ^*_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t)\) is from 73 and where \[\begin{align} \label{eq:bardbn} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup _{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) &= \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,(\boldsymbol{s}_1', \boldsymbol{s}_2')}(1-t,t) \end{align}\tag{74}\] with \[\begin{align} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) = \widetilde{\mathbb{L}}_{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) & - \sum_{j \in [2]}\partial_j L_{(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) \widetilde{\mathbb{L}}_{n,\boldsymbol{s}_j}(x_j), \end{align}\] and, with \(V_i(\boldsymbol{s}) = 1- F_{\boldsymbol{s}}(X_i(\boldsymbol{s}))\), \[\begin{align} \widetilde{\mathbb{L}}_{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) &= \frac{1}{\sqrt k} \sum_{i=1}^n \Big\{ \boldsymbol{1}\Big(\exists j \in \{1,2\}: V_i(\boldsymbol{s}_j) \le \frac{k}{n} x_j\Big) \\ & - \mathbb{P}\Big( \exists j \in \{1,2\}: V_i(\boldsymbol{s}_j) \le \frac{k}{n} x_j\Big)\Big\}, \\ \widetilde{\mathbb{L}}_{n,\boldsymbol{s}}(x) &= \frac{1}{\sqrt k} \sum_{i=1}^n \Big\{ \boldsymbol{1}\Big( V_{i}(\boldsymbol{s}) \le \frac{k}{n} x\Big) - \mathbb{P}\Big( V_{i}(\boldsymbol{s}) \le \frac{k}{n} x\Big)\Big\}. \end{align}\] Further, let \[\widetilde{\boldsymbol{G}}_n \sim \mathcal{N}_{p}(\boldsymbol{0}, \operatorname{Var}(\widetilde{\boldsymbol{T}}_n)).\] Note that \[T_n^{(\rho)} = \max_{q \in P(\rho)} \widetilde{S}_{nq}, \qquad T_n^{(\rho),*} = \max_{q \in P(\rho)} \widetilde{S}_{nq}^*\] and define \[\begin{align} T_n^{(\rho),g} = \max_{q \in P(\rho)} \widetilde{G}_{nq}^{(\rho)}, \end{align}\] where \(P(\rho)\) corresponds to all coordinate indices of \(\widetilde{\boldsymbol{S}}_n\) for which \({(t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2') \in D(\rho)}\). Define bivariate random vectors \[\boldsymbol{Y}_n = (T_n^{(1)}, T_n^{(\sqrt 2)}), \quad \boldsymbol{Y}_n^{g} = (T_n^{(1),g}, T_n^{(\sqrt 2),g}), \quad \boldsymbol{Y}_n^* = (T_n^{(1),*}, T_n^{(\sqrt 2),*}),\] and note that \[\begin{align} \mathbb{P}\big(Y_{n1} \le x, Y_{n2} \le y\big) &= \mathbb{P}\big( \widetilde{\boldsymbol{S}}_n \le \boldsymbol{s}_{x,y} \big), \\ \mathbb{P}\big( Y_{n1}^{g} \le x, Y_{n2}^{g} \le y) &= \mathbb{P}\big(\widetilde{\boldsymbol{G}}_n \le \boldsymbol{s}_{x,y} \big), \\ \mathbb{P}\big( Y_{n1}^*\le x, Y_{n2}^* \le y \mid \mathrm{data}\big) &= \mathbb{P}\big( \widetilde{\boldsymbol{S}}_n^* \le \boldsymbol{s}_{x,y} \mid \mathrm{data} \big), \end{align}\] where \(\boldsymbol{s}_{x,y} \in \mathbb{R}^p\) is the vector with coordinates \(s_j = x\) for \(j \in P(1)\) and \(s_j = y\) for \(j \in P(\sqrt 2)\). Hence, \[\begin{align} \label{eq:bound-K-dist} d_K\Big( \boldsymbol{Y}_n, \boldsymbol{Y}_n^{g} \Big) &\le d_K(\widetilde{\boldsymbol{S}}_n, \widetilde{\boldsymbol{G}}_n), \qquad d_K\Big( \mathcal{L}\big( \boldsymbol{Y}_n^* \mid \mathrm{data} \big), \boldsymbol{Y}_n^{g} \Big) \le d_K( \mathcal{L}(\widetilde{\boldsymbol{S}}_n^* \mid \mathrm{data} ), \widetilde{\boldsymbol{G}}_n), \end{align}\tag{75}\] which will eventually allow to apply Proposition 20.

In the following, let \[\begin{align} \label{eq:deltan} \delta_n = \Big( \frac{\log^5(pn)}{k} \Big)^{1/4} . \end{align}\tag{76}\] We will show below that there exist constants \(c_1, c_2, c_3\) only depending on \(K_L, \sigma_{\min}^2c_h, c_h'\) such that \[\begin{align} \tag{77} d_K(\widetilde{\boldsymbol{S}}_n, \widetilde{\boldsymbol{G}}_n) &\le c_1 \big[ \delta_n + \sqrt{\log p} B_{n,k} \big], \\ \tag{78} d_K( \mathcal{L}(\widetilde{\boldsymbol{S}}_n^* \mid \mathrm{data} ), \widetilde{\boldsymbol{G}}_n) &\le c_2 \big[\delta_n + \sqrt{\log(p+k)}\, B_{n,k} \big] \end{align}\] the latter holding with probability at least \(1-c_3\delta_n\). In view of 75 , an application of Proposition 20 implies that, for some constant \(c_0\) depending on \(c_1, c_2, c_3\), \[\Big|\mathbb{P}( C_n \le \hat{q}_{n,\alpha}^* ) - \alpha \Big| \le c_0 \big[\delta_n + \sqrt{\log(p+k)}\, B_{n,k} \big]\] as asserted.

It remains to show 77 and 78 . We start with the former and begin by observing that \[\begin{align} \label{eq:bound-dn1} \max_{(t,\boldsymbol{s}_1, \boldsymbol{s}_2,\boldsymbol{s}_1',\boldsymbol{s}_2') \in D(1,\sqrt 2)} & \big| \mathbb{D}_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup _{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) \big| \nonumber\\&\le 2 \max_{(\boldsymbol{s}_1, \boldsymbol{s}_2) \in \mathcal{P}_d(1, \sqrt 2)} \max_{t \in A} \big| \mathbb{L}_{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) \big|. \end{align}\tag{79}\] An application of Theorem 2 and the union bound implies that there exist constants \(D_1=D_1(K_L)\) and \(D_2\) such that, for \(\delta>0\) specified below, \[\begin{align} \label{eq:bound-dn2} &\max_{(\boldsymbol{s}_1, \boldsymbol{s}_2) \in \mathcal{P}_d(\rho)} \max_{t \in A} \big| \mathbb{L}_{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _{n,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) \big| \nonumber \\&\le B_{n,k} + \frac{2}{\sqrt k} + D_1 \sqrt{r \log \Big( \frac{D_2}{\delta r} \Big)} =: \lambda_{n,k}(\delta) \end{align}\tag{80}\] with probability at least \(1-17|\mathcal{P}_d(1, \sqrt 2)| \delta\). Here, we note that the last term in the final bound of 2 can be absorbed into the second-to last term at the cost of possibly increasing the constant since \(\alpha_L = 1\).

We now proceed as in the proof of Theorem 7, and obtain that, for any \(\lambda>0\), \[d_K(\widetilde{\boldsymbol{S}}_n,\widetilde{\boldsymbol{G}}_n) \le \mathbb{P}(\| \widetilde{\boldsymbol{S}}_n -\widetilde{\boldsymbol{T}}_n \|_\infty \ge \lambda) + \frac{8\lambda}{{\sigma}^2_{\min}}\sqrt{\log p} + 3d_K(\widetilde{\boldsymbol{T}}_n , \widetilde{\boldsymbol{G}}_n);\] see the derivations in 49 and 50 . With \(\lambda = \lambda_{n,k}(\delta)\) from 80 , we obtain that, for \(\delta\) chosen below, \[d_K(\widetilde{\boldsymbol{S}}_n,\widetilde{\boldsymbol{G}}_n) \le 17|\mathcal{P}_d(1, \sqrt 2)| \delta + \frac{8\lambda_{n,k}(\delta)}{{\sigma}^2_{\min}}\sqrt{\log p} + 3d_K(\widetilde{\boldsymbol{T}}_n , \widetilde{\boldsymbol{G}}_n).\] We proceed by bounding \(d_K(\widetilde{\boldsymbol{T}}_n , \widetilde{\boldsymbol{G}}_n)\). The coordinates of \(\widetilde{\boldsymbol{T}}_n\) are of the form \[\begin{align} \label{eq:yitssss} \sum_{i=1}^n Y_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - Y_{i,(\boldsymbol{s}_1', \boldsymbol{s}_2')}(1-t,t) =: \sum_{i=1}^n Y_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} \end{align}\tag{81}\] where \[\begin{align} Y_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) &= \frac{1}{\sqrt k} \Big[ \boldsymbol{1}(\exists j \in [2]: V_{i}(\boldsymbol{s}_j) < kx_j/n) - (k/n) L_{(\boldsymbol{s}_1, \boldsymbol{s}_2)}(\boldsymbol{x}) \\ & -\sum_{j \in [2]}\partial_{j} L_{(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2) \big\{\boldsymbol{1}( V_{i}(\boldsymbol{s}_j) < kx_j/n) - kx_j/n \big\} \Big]. \end{align}\] Note the resemblance between \(Y_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2)\) and \(Y_{I}(\boldsymbol{x}_I)\) from 19 , which allows us to make use of results in the proof of Theorem 7. For instance, using that \((a-b)^4 \le 8 (a^4 + b^4)\), we have \[\sum_{i=1}^n \mathbb{E}[|Y_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')}|^4] \le 16 \max_{(\boldsymbol{s}_1, \boldsymbol{s}_2) \in \mathcal{P}_d(1, \sqrt 2)} \max_{t \in A} \sum_{i=1}^n \mathbb{E}[|Y_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t, t)|^4 ],\] and the right-hand side has been bounded in the proof of Theorem 7 by some constant times \(n^{-1}\); see 52 . Similar elementary computations bound \(|Y_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2)|\), and the result follows by applying Theorem 19 to obtain \(d_K(\widetilde{\boldsymbol{T}}_n , \widetilde{\boldsymbol{G}}_n) \le \tilde{c}_1\delta_n,\) where \(\tilde{c}_1\) depends only on \(\sigma_{\min}^2\) and where \(\delta_n\) is from 76 .

Finally, letting \(\delta = |\mathcal{P}_d(1, \sqrt 2)|^{-1} \delta_n \le 3^{-1} < e^{-1}\), we will verify that the conditions of Theorem 2 hold. Specifically, using (ii) and (iii) we see \[\begin{align} \log(2/\delta) &\le \log (2 |\mathcal{P}_d(1, \sqrt 2)| k^{1/4}) \le 2k/7, \\ r := \sqrt{k^{-1} \log(\delta^{-1})}&\le \sqrt{k^{-1}\log (|\mathcal{P}_d(1, \sqrt 2)|k^{1/4})} \le \kappa_L/C_{s}. \end{align}\] Finally, combining the bounds \(r \ge k^{-1/2}, |\mathcal{P}_d(1, \sqrt 2)| \ge 3 \gtrsim D_2\) and \(|\mathcal{P}_d(1, \sqrt 2)| \le p\), elementary computations show that \[\sqrt{\log p} \sqrt{r \log\Big(\frac{D_2}{\delta r}\Big)} \le D_2' \delta_n\] for some constant \(D_2'\) depending on \(D_2\). Assembling terms, this implies 77 .

It remains to show 78 , for which we proceed as in the proof of Theorem 11, which itself is a consequence of Proposition 15. The proof of Proposition 15 is based on Lemmas 6-9. We will now discuss how these lemmas and their proofs can be adapted to the present setting.

Let \[\begin{align} \widetilde{\boldsymbol{S}}_n^\circ = \big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup ^\circ_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t)\big)_{(t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2') \in D} \in \mathbb{R}^p, \end{align}\] where \[\begin{align} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{D}} \endgroup ^\circ_{n, (\boldsymbol{s}_1, \boldsymbol{s}_2), (\boldsymbol{s}_1', \boldsymbol{s}_2')}(t) = \sum_{i=1}^n e_i \Big\{Y_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} - \frac{1}{n} \sum_{i'=1}^n Y_{i',(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} \Big\}, \end{align}\] with \(Y_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')}\) as defined in 81 . A careful inspection of the proof of Lemma 6 shows that it continues to holds with \(\boldsymbol{S}^*_n, \boldsymbol{S}_n^\circ\) and \(\boldsymbol{G}_n\) replaced by the respective tilde-versions. More specifically, we have \[d_K( \mathcal{L}(\widetilde{\boldsymbol{S}}_n^* \mid \mathrm{data}), \widetilde{\boldsymbol{G}}_n) \lesssim \frac{1}{k} + \frac{\widetilde{\Delta} \cdot \log(p+k)}{\sigma_{\mathrm{min}}^2} + d_K( \mathcal{L}(\widetilde{\boldsymbol{S}}_n^\circ \mid \mathrm{data}), \widetilde{\boldsymbol{G}}_n),\] where the constant in \(\lesssim\) is universal and where \[\begin{align} \widetilde{\Delta}^2 := \max_{(t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2') \in D} \widetilde{\Delta}^2_{t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2'}, \end{align}\] with \[\begin{align} \widetilde{\Delta}^2_{t, \boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2'} = \sum_{i=1}^n \Big\{\hat{Y}_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} - Y_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} - \frac{1}{n} \sum_{i'=1}^n Y_{i',(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} \Big\}^2 \end{align}\] and \[\hat{Y}_{i,(t,\boldsymbol{s}_1, \boldsymbol{s}_2, \boldsymbol{s}_1', \boldsymbol{s}_2')} = \hat{Y}_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(1-t,t) - \hat{Y}_{i,(\boldsymbol{s}_1', \boldsymbol{s}_2')}(1-t,t).\]

Next, note that Lemma 9 can be applied as is, after proper identification of the notation. Moreover, in view of the inequality \((a+b)^2 \le 2(a^2+b^2)\) and the fact that \(Y_{i,(\boldsymbol{s}_1, \boldsymbol{s}_2)}(x_1, x_2)\) essentially corresponds to \(Y_{I}(\boldsymbol{x}_I)\) from 19 , the bounds in Lemma 7 and Lemma 8 continue to hold, with the hidden universal constant multiplied by \(4\) and 2, respectively. More specifically, the tilde-version of Lemma 8 is as follows: \[\widetilde{\Delta} \lesssim h + \sqrt{r} + \frac{r}{\sqrt{h}} + \frac{r^2}{h} + \frac{1}{h\sqrt{k}} \Big\{ B_{n,k} + \sqrt{r \log\Big(\frac{1}{\delta r}\Big)} \Big\}\] with probability at least \(1-19 |\mathcal{P}_d(1, \sqrt 2)| \delta\). The rest of the proof follows the arguments in the proofs of Proposition 15 and Theorem 11. ◻

Proof of Proposition 16. Throughout, we write \(Q=Q_L\). By definition of the generalized inverse, it suffices to prove that \[\label{eq:bound-f} f_{Q,L}\big(\big\| \hat{\theta}_n-\theta_0 \big\|_2\big) < \eta+2C_g \sup_{\boldsymbol{x}\in [0,1]^d} \big| \widehat L_{n}(\boldsymbol{x})-L(\boldsymbol{x}) \big|.\tag{84}\] Note that, by the definition of \(\hat{\theta}_n\) and \(\eta\), \[\begin{align} \eta& > Q_n(\hat{\theta}_n) - Q_n(\theta_0) \\ &= \big(Q(\hat{\theta}_n) - Q(\theta_0)\big) - \big(Q(\hat{\theta}_n) - Q_n(\hat{\theta}_n)\big) - \big(Q_n(\theta_0) - Q(\theta_0)\big) \\ &\geq \big(Q(\hat{\theta}_n) - Q(\theta_0)\big) - \big|Q(\hat{\theta}_n) - Q_n(\hat{\theta}_n)\big| - \big|Q_n(\theta_0) - Q(\theta_0)\big|. \end{align}\] Thus \[f_{Q,L}\big(\big\| \hat{\theta}_n-\theta_0 \big\|_2\big) \le Q(\hat{\theta}_n) - Q(\theta_0) < 2 \sup_{\theta \in \Theta} \big| Q_n(\theta) - Q(\theta)\big|+ \eta.\] For each \(\theta \in \Theta\), the reverse triangle inequality implies that \[\begin{align} &\big| Q_n(\theta)-Q(\theta) \big|_2 \\ & = \bigg| \Big\| \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x})\big( L(\boldsymbol{x};\theta)-\widehat L_n(\boldsymbol{x}) \big) \mathrm d\mu(\boldsymbol{x}) \Big\|_2 - \Big\| \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x})\big( L(\boldsymbol{x};\theta)- L(\boldsymbol{x}) \big) \mathrm d\mu(\boldsymbol{x}) \Big\|_2 \bigg| \\& \leq \Big\| \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x})\big( L(\boldsymbol{x};\theta)-\widehat L_n(\boldsymbol{x}) \big) \mathrm d\mu(\boldsymbol{x}) - \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x})\big( L(\boldsymbol{x};\theta)- L(\boldsymbol{x}) \big) \mathrm d\mu(\boldsymbol{x}) \Big\|_2 \\ &= \Big\| \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x})\big( L(\boldsymbol{x}) - \widehat L_n(\boldsymbol{x})\big) \mathrm d\mu(\boldsymbol{x}) \Big\|_2. \end{align}\] By the triangle inequality for integrals, \[\begin{align} \label{eq:qn-q-hoelder} \Big\| \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x})\big( L(\boldsymbol{x}) - \widehat L_n(\boldsymbol{x})\big) \mathrm d\mu(\boldsymbol{x})\Big\|_2 &\leq \sup_{\boldsymbol{x}\in [0,1]^d} \big| \widehat L_n(\boldsymbol{x})-L(\boldsymbol{x}) \big| \times \int_{[0,1]^d} \| \boldsymbol{g}(\boldsymbol{x}) \|_2\, \mathrm d\mu(\boldsymbol{x}). \end{align}\tag{85}\] Combining the last three displayed formulas establishes 84 and completes the proof. ◻

Proof of Theorem 17. Throughout, we write \(Q=Q_L\) and utilize the following additional notation \[\boldsymbol{\psi}:= \int_{[0,1]^d } \boldsymbol{g}(\boldsymbol{x}) L(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x}), \quad \widehat \boldsymbol{\psi}:= \int_{[0,1]^d } \boldsymbol{g}(\boldsymbol{x})\widehat L_{n}(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x}).\] For a matrix \(A\), let \({\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2\) denote the spectral norm of \(A\), that is, \({\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2\) is largest singular value of \(A\). Further, \({\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_1\) is the maximum of the absolute column sums of \(A\), while \({\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_\infty\) is the maximum of the absolute row sums of \(A\); note that \({\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2^2 \leq {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_1 \cdot {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_\infty\). For either a vector or a matrix, \(\left\lVert\cdot\right\rVert_\infty\) refers to the absolute maximum entry; note that the previous inequality then yields \({\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \leq \sqrt{sq} \|A\|_\infty\) for \(A \in \mathbb{R}^{s \times q}\). Further, \(\|A\boldsymbol{b}\|_2 \le {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \|\boldsymbol{b}\|_2\) for \(A\in\mathbb{R}^{s \times q}\) and \(\boldsymbol{b} \in\mathbb{R}^{q}\). Finally, if \(A\) is a square matrix and \(\boldsymbol{b}\) a vector, we have \(|\boldsymbol{b}^\top A \boldsymbol{b}| \le {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert A \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \| \boldsymbol{b}\|_2^2\).

In what follows, we will without loss of generality assume that \(\kappa\leq 1\). Moreover, we will choose \(\tilde{C}_\beta\) and \(\tilde{C}_\eta\) not larger than \(1\), which implies \(\beta, \eta\le 1\).

Let \(\theta \in B_{\kappa}(\theta_0)\) and define \(\Delta_{\theta} \mathrel{\vcenter{:}}= \theta-\theta_0\). Under Assumption 1, we have the Taylor expansion \[\begin{align} \label{eq:expansion-qn2} Q_n^2(\theta)-Q_n^2(\theta_0) \nonumber &= \left[\nabla Q_n^2(\theta_0)\right]^{\top}\Delta_{\theta}+\frac{1}{2}\Delta_{\theta}^{\top} V_{n, \tilde{\theta}} \Delta_{\theta} \\ &= \frac{1}{2}\Delta_{\theta}^{\top} V_{\theta_0} \Delta_{\theta} + r_{n,1}(\theta) +r_{n,2}(\theta) +r_{n,3}(\theta), \end{align}\tag{86}\] where \(\tilde{\theta}\) is a convex combination of \(\theta\) and \(\theta_0\) and where \[\begin{align} r_{n,1}(\theta) &:= \left[\nabla Q_n^2(\theta_0)\right]^{\top}\Delta_{\theta}, \\ r_{n,2}(\theta) &:= \frac{1}{2}\Delta_{\theta}^\top(V_{n,\theta_0} - V_{\theta_0})\Delta_{\theta}, \\ r_{n,3}(\theta) &:= \frac{1}{2}\Delta_{\theta}^{\top} (V_{n, \tilde{\theta}}-V_{n,\theta_0}) \Delta_{\theta} . \end{align}\] We will show below that, on the event \(\Omega_1(n,\beta)\), \[\begin{align} \label{eq:bound-rn} r_{n,1}(\theta) &\le C_1 \beta \left\lVert\Delta_{\theta}\right\rVert_2, \qquad r_{n,2}(\theta) \le C_2 \beta \left\lVert\Delta_{\theta}\right\rVert_2^2, \qquad r_{n,3}(\theta) \le C_3(\beta) \left\lVert\Delta_{\theta}\right\rVert_2^{2+\gamma_{h}}, \end{align}\tag{87}\] where \(C_1=2 \sqrt{sq}C_\partial C_g\), \(C_2=s\sqrt q C_g C_{\partial^2}\), and \(C_3(\beta) := 3sq^{3/2}C_\partial C_{\partial^2} + sqC_{h}(C_g \beta + d_{\theta_0})\) with \(d_{\theta_0} := \max_{p \in [q]} |\varphi_p(\theta_0) - \psi_p|\); note that \(C_3(\beta)\) is increasing in \(\beta\) and hence bounded by \(C_3(1)\). Note that by using \(0\le L(\cdot),L(\cdot;\theta)\le d\), we have \(d_{\theta_0} \le dC_g\) which is an upper bound that does not depend on \(L\).

Regarding \(r_{n,1}(\theta)\), recall that \(\theta_0\) is the global minimizer of \(\theta \mapsto Q^2(\theta) = \|\boldsymbol{\varphi}(\theta)-\boldsymbol{\psi} \|_2^2\) and so \[0 = \nabla Q^2(\theta_0) = 2 \sum_{p \in [q]} \big(\varphi_p(\theta_0)-\psi_p\big)\nabla \varphi_p(\theta_0).\] Thus \[\begin{align} \label{eq:nableqn2} \nabla Q_n^2(\theta_0) &= \nonumber 2\sum_{p \in [q]} (\varphi_p(\theta_0) - \widehat \psi_p)\nabla \varphi_p(\theta_0) \\ &= 2\sum_{p \in [q]} \big( \psi_p - \widehat \psi_p \big)\nabla \varphi_p(\theta_0) = -\frac{2}{\sqrt k} J_{\theta_0}^\top \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x}). \end{align}\tag{88}\] As a consequence, on the event \(\Omega_1(n,\beta)\), recalling the definition of \(C_g\) and \(C_\partial\) in 22 and 24 , respectively, we have the bound \[\begin{align} \big| r_{n,1}(\theta) \big| &= \frac{2}{\sqrt k} \Big| \Big( J_{\theta_0}^\top \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x})\Big)^\top \Delta_{\theta} \Big| \\&\leq \frac{2}{\sqrt k} \Big\| J_{\theta_0}^\top \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x})\Big\|_2 \left\lVert\Delta_{\theta}\right\rVert_2 \\ &\leq \frac{2}{\sqrt k}{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert J_{\theta_0}^\top \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \times \Big\|\int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x}) \Big\|_2 \left\lVert\Delta_\theta\right\rVert_2 \\ &\leq \frac{2}{\sqrt k} \sqrt {sq}C_\partial C_g \Big(\sup_{\boldsymbol{x}\in [0,1]^d} \left|\mathbb{L}_n(\boldsymbol{x})\right|\Big) \left\lVert\Delta_\theta\right\rVert_2 \\ & \le 2 \sqrt{sq}C_\partial C_g \beta \left\lVert\Delta_{\theta}\right\rVert_2, \end{align}\] as claimed in 87 .

Next, regarding \(r_{n,2}(\theta)\), note that the \((j, \ell)\)-entry of \(V_{n, \theta_0}-V_{\theta_0}\in \mathbb{R}^{s \times s}\) is given by \[\begin{align} [V_{n,\theta_0}-V_{\theta_0}]_{j\ell} &= 2 \sum_{p \in [q]} \Big((\varphi_p(\theta_0) - \widehat \psi_p)\partial_{j\ell} \varphi_p(\theta_0) + \partial_j \varphi_p(\theta_0) \partial_\ell \varphi_p(\theta_0)\Big) \\ &\quad \quad - 2 \sum_{p \in [q]} \Big((\varphi_p(\theta_0) -\psi_p)\partial_{j\ell} \varphi_p(\theta_0) + \partial_j \varphi_p(\theta_0) \partial_\ell \varphi_p(\theta_0)\Big) \\ &= -2 (\widehat \boldsymbol{\psi}- \boldsymbol{\psi})^\top \partial_{j\ell} \boldsymbol{\varphi}(\theta_0) = - \frac{2}{\sqrt k} \Big[\int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x})\Big]^\top \partial_{j\ell} \boldsymbol{\varphi}(\theta_0). \end{align}\] Hence, on the event \(\Omega_{1}(n, \beta)\) \[\left\lVert V_{n, \theta_0}-V_{\theta_0}\right\rVert_\infty \leq 2 \sqrt q C_g C_{\partial^2} \beta,\] which in turn implies \[\begin{align} \label{eq:32V95n32-32V95theta32bound} \big|r_{n,2}(\theta) \big| = \left|\frac{1}{2} \Delta_{\theta}^\top (V_{n,\theta_0}-V_{\theta_0}) \Delta_{\theta}\right| &\leq \frac{1}{2} {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{n, \theta_0}-V_{\theta_0} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2\left\lVert\Delta_{\theta}\right\rVert^2_2 \leq s\sqrt q C_g C_{\partial^2} \beta \left\lVert\Delta_{\theta}\right\rVert_2^2 \end{align}\tag{89}\] as claimed in 87 .

Finally, regarding \(r_{n,3}(\theta)\), a similar calculation shows that the \((j, \ell)\)-entry of \(V_{n, \tilde{\theta}}- V_{n, \theta_0}\) can be written as \[\begin{align} [V_{n, \tilde{\theta}}- V_{n, \theta_0}]_{j\ell} &= 2 \sum_{p \in [q]} \Big(\partial_j \varphi_p(\tilde{\theta}) \partial_\ell \varphi_p(\tilde{\theta}) - \partial_j \varphi_p(\theta_0) \partial_\ell \varphi_p(\theta_0)\Big) \\ &\quad \quad + 2 \sum_{p \in [q]} \Big((\varphi_p(\tilde{\theta}) - \widehat \psi_p)\partial_{j\ell} \varphi_p(\tilde{\theta}) - (\varphi_p(\theta_0) -\widehat \psi_p)\partial_{j\ell} \varphi_p(\theta_0) \Big). \end{align}\] First, since \(|ab-cd| \le |a||b-d|+|d||a-c|\) and \(\tilde{\theta} \in B_{\kappa}(\theta_0)\), \[\begin{align} & \left|\partial_j \varphi_p(\tilde{\theta}) \partial_\ell \varphi_p(\tilde{\theta}) - \partial_j \varphi_p(\theta_0) \partial_\ell \varphi_p(\theta_0)\right| \\ &\leq \left|\partial_j \varphi_p(\tilde{\theta})\right| \left|\partial_\ell \varphi_p(\tilde{\theta})-\partial_\ell \varphi_p(\theta_0)\right| + \left|\partial_\ell \varphi_p(\theta_0)\right| \left|\partial_j \varphi_p(\tilde{\theta})-\partial_j \varphi_p(\theta_0)\right| \\ & \leq C_{\partial} \Big(\left|\partial_\ell \varphi_p(\tilde{\theta})-\partial_\ell \varphi_p(\theta_0)\right| + \left|\partial_j \varphi_p(\tilde{\theta})-\partial_j \varphi_p(\theta_0)\right|\Big) \\ & \leq 2 \sqrt{q}C_{\partial} C_{\partial^2}\|\tilde{\theta}-\theta_0\|_2, \end{align}\] where we have used that, by the mean value inequality and the fact that the partial derivatives of \(\theta \mapsto \partial_j \varphi_m(\theta)\) are bounded by \(C_{\partial^2}\) on \(B_{\kappa}(\theta_0)\), \[\begin{align} \label{eq:bound-pds-phi} \left|\partial_j \varphi_p(\tilde{\theta})-\partial_{j} \varphi_p(\theta_0)\right| &\le \nonumber \sup_{t \in (0,1)} \Big| \frac{d}{dt} \partial_j \varphi_p(\theta_0 + t(\tilde{\theta}-\theta_0)) \Big| \\&\le \sup_{t \in (0,1)} \big\|\nabla[\partial_j \varphi_p](\theta_0 + t(\tilde{\theta}-\theta_0))\big\|_2 \big\|\tilde{\theta} - \theta_0\big\|_2 \leq \sqrt{q}C_{\partial^2} \big\|\tilde{\theta} - \theta_0\big\|_2. \end{align}\tag{90}\] Second, recalling \(d_{\theta_0} := \max_{p \in [q]} |\varphi_p(\theta_0) - \psi_p|\), \[\begin{align} &\Big| (\varphi_p(\tilde{\theta}) - \widehat \psi_p)\partial_{j\ell} \varphi_p(\tilde{\theta}) - (\varphi_p(\theta_0) -\widehat \psi_p)\partial_{j\ell} \varphi_p(\theta_0) \Big| \\ &\leq \big| \partial_{j\ell}\varphi_p(\tilde{\theta}) \big| \left|\varphi_p(\tilde{\theta})-\varphi_p(\theta_0)\right| + \big| \varphi_p(\theta_0)-\widehat \psi_p \big| \left|\partial_{j\ell} \varphi_p(\tilde{\theta}) - \partial_{j\ell} \varphi_p(\theta_0)\right| \\&\leq \sqrt{q} C_\partial C_{\partial^2} \big\| \tilde{\theta}-\theta_0 \big\|_2 + C_{h}\big\| \tilde{\theta}-\theta_0 \big\|_2^{\gamma_{h}}\Big(\big| \varphi_p(\theta_0)- \psi_p \big| + \big| \widehat \psi_p - \psi_p \big| \Big) \\ &\leq [ \sqrt{q} C_\partial C_{\partial^2} + C_{h}(C_g \beta + d_{\theta_0})] \times \left\lVert\Delta_{\theta}\right\rVert_2^{\gamma_{h}}, \end{align}\] where we used that \(\|\tilde{\theta}- \theta_0\|_2 \le \|\theta- \theta_0\|_2= \left\lVert\Delta_{\theta}\right\rVert_2 \le \kappa\le 1\), and that \[\hat{\psi}_p - \psi_p = \frac{1}{\sqrt k} \int_{[0,1]^d}g_p(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x})\] is bounded by \(C_g \beta\) on the event \(\Omega_1(n, \beta)\), and that \(|\varphi_p(\tilde{\theta}) - \varphi_p(\theta_0)| \le \sqrt{q} C_{\partial} \big\|\tilde{\theta} - \theta_0\big\|_2\), which follows from the same arguments that were used in 90 . Combining the bounds so far we obtain \[\label{eq:32bound32for32V95n32-32V95n32theta} {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{n, \tilde{\theta}}-V_{n,\theta_0} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2\leq s \left\lVert V_{n, \tilde{\theta}}-V_{n,\theta_0}\right\rVert_\infty \leq 2C_3(\beta) \left\lVert\Delta_{\theta}\right\rVert_2^{\gamma_{h}},\tag{91}\] where \(C_3(\beta) = 3sq^{3/2}C_\partial C_{\partial^2} + sqC_{h}(C_g \beta + d_{\theta_0})\), which in turn implies \[\begin{align} \big|r_{n,3}(\theta) \big| = \left|\frac{1}{2} \Delta_{\theta}^\top (V_{n,\tilde{\theta}}-V_{\theta_0}) \Delta_{\theta}\right| &\leq \frac{1}{2} {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{n, \tilde{\theta}}-V_{\theta_0} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2\left\lVert\Delta_{\theta}\right\rVert^2_2 \leq C_3(\beta) \left\lVert\Delta_{\theta}\right\rVert_2^{2+\gamma_{h}} \end{align}\] as claimed in 87 .

Next, we will show that \[\label{eq:bounddiffQn942} \forall \theta \in \Theta: \qquad Q_n^2(\hat{\theta}_n) - Q_n^2(\theta) < 2dC_g \eta=:C_4 \eta.\tag{92}\] For that purpose, note that our assumption on \(\hat{\theta}_n\) yields \(Q_n(\hat{\theta}_n)-Q_n(\theta) < \eta\) for any \(\theta\in \Theta\). Moreover, by a similar calculation as in 85 , we have for any \(\theta \in \Theta\) (in particular, for \(\theta=\hat{\theta}_n\)) \[0 \le Q_n(\theta) \le C_g \sup_{\boldsymbol{x} \in [0,1]^d}\Big| \widehat L_n(\boldsymbol{x}) - L(\boldsymbol{x};\theta) \Big| \le dC_g,\] where we used that \(\widehat L(\boldsymbol{x}),L(\boldsymbol{x};\theta) \le \| \boldsymbol{x}\|_1\). As a consequence \[Q_n^2(\hat{\theta}_n) - Q_n^2(\theta) = \big(Q_n(\hat{\theta}_n)-Q_n(\theta)\big)\big(Q_n(\hat{\theta}_n)+Q_n(\theta)\big) < 2dC_g \eta\] as asserted in 92 .

We will next apply Proposition 16, and for that purpose, we need to check that \(f_{Q,L}(\varepsilon)>0\) for all \(\varepsilon>0\). In fact, for later purposes, we will need a precise lower bound on that function, and more specifically, we will now show that there exists a constant \(C_f>0\) depending on \(d,C_g,C_V\) and \(C_Q\) only such that \[\begin{align} \label{eq:fql-quadratic-bound} f_{Q,L}(\varepsilon) \equiv \inf_{\theta: \|\theta-\theta_0\|_2 \ge \varepsilon} \big\{ Q(\theta) - Q(\theta_0)\big\} \ge C_f (\varepsilon^2 \wedge 1). \end{align}\tag{93}\] Indeed, note that \(Q(\theta) \le d \int \| \boldsymbol{g}\|_2 \, \mathrm d\mu \le dC_g\) for all \(\theta \in \Theta\), whence \[Q^2(\theta) - Q^2(\theta_0) = (Q(\theta) - Q(\theta_0))(Q(\theta) + Q(\theta_0)) \le 2d C_g (Q(\theta) - Q(\theta_0)).\] As a consequence, with \(\tilde{C}_f = (2d C_g)^{-1}\) and with \(d_Q\) as defined in Assumption 1(v). \[Q(\theta) - Q(\theta_0) \ge \tilde{C}_f \big\{ Q^2(\theta) - Q^2(\theta_0) \big\} = \tilde{C}_f d_Q(\theta).\] Hence, \[\begin{align} f_{Q,L}(\varepsilon) &\ge \tilde{C}_f \inf_{\theta: \|\theta-\theta_0\|_2 \ge \varepsilon} d_Q(\theta) \\&= \tilde{C}_f \min\Big\{ \inf_{\theta: \kappa\ge \|\theta-\theta_0\|_2 \ge \varepsilon} d_Q(\theta), \inf_{\theta: \|\theta-\theta_0\|_2 > \kappa} d_Q(\theta) \Big\} \ge \tilde{C}_f \min\Big( \frac{C_V}{4} \varepsilon^2, C_Q\Big), \end{align}\] where we have used Assumption 1(v). This implies 93 with \(C_f = \tilde{C}_f\min(C_V/4, C_Q)\).

Next, note that \(f_{Q,L}^{\leftarrow}(u) \le \sqrt{u/C_f}\) for \(0 < u \le C_f\) by 93 . Choosing \(\tilde{C}_\eta\le (\kappa^2\wedge 1)C_f/2\) and \(\tilde{C}_\beta \le (\kappa^2\wedge 1)C_f/(4 C_g)\) ensures \(\eta + 2C_g \beta \le (\kappa^2 \wedge 1) C_f \le C_f\) for \(\beta \in (0,\tilde{C}_\beta)\) and \(\eta\in (0,\tilde{C}_\eta)\), and so \[\big\| \hat{\theta}_n-\theta_0\big\|_2 \leq f_{Q,L}^{\leftarrow}\Big(\eta+2 C_g \beta \Big) \leq \Big(\frac{\eta+2 C_g \beta}{C_f} \Big)^{1/2} \le (\kappa^2 \wedge 1)^{1/2} \le \kappa.\] by Proposition 16.

As a consequence, we can apply 86 and 87 with \(\hat{\Delta}_n=\Delta_{\hat{\theta}_n}=\hat{\theta}_n-\theta_0\) to obtain that \[\label{eq:qn2-mest} Q_n^2(\hat{\theta}_n) - Q_n^2(\theta_0) = \frac{1}{2} \hat{\Delta}_n^{\top} V_{\theta_0} \hat{\Delta}_n + r_{n,1}(\hat{\theta}_n) + r_{n,2}(\hat{\theta}_n) + r_{n,3}(\hat{\theta}_n),\tag{94}\] with the three error terms satisfying \[\begin{align} \label{eq:error-mest} |r_{n,1}(\hat{\theta}_n)| \le C_1 \beta \big\| \hat{\Delta}_n \big\|_2, \qquad |r_{n,2}(\hat{\theta}_n)| + |r_{n,3}(\hat{\theta}_n) | \leq C_5(\beta, \eta) \big\| \hat{\Delta}_n \big\|_2^2, \end{align}\tag{95}\] with \(C_5(\beta, \eta) := C_2\beta + C_3(\beta) \{ (\eta+2 C_g \beta)/{C_f}\}^{\gamma_{h}/2}\). Combining 92 (with \(\theta=\theta_0\)) with 94 and 95 , we obtain that \[\begin{align} C_{4} \eta & \ge \frac{1}{2} \hat{\Delta}_n^{\top} V_{\theta_0} \hat{\Delta}_n + r_{n,1}(\hat{\theta}_n) + r_{n,2}(\hat{\theta}_n) + r_{n,3}(\hat{\theta}_n) \\ &> \frac{1}{2} \lambda_{\text{min}}(V_{\theta_0}) \big\| \hat{\Delta}_n \big\|_2^2 - C_1 \beta \big\| \hat{\Delta}_n \big\|_2 - C_5(\beta, \eta) \big\| \hat{\Delta}_n \big\|_2^2. \end{align}\] Decreasing \(\tilde{C}_\beta\) and \(\tilde{C}_\eta\) if necessary, we can guarantee that \(C_{5}(\beta, \eta) \le \lambda_{\min}(V_{\theta_0})/4\) for any \(\beta \in (0,\tilde{C}_\beta)\) and \(\eta\in (0,\tilde{C}_\eta)\). Hence, \[\big\| \hat{\Delta}_n \big\|_2^2 < \frac{4}{\lambda_{\min}(V_{\theta_0})} \big( C_4 \eta+ C_1 \beta \big\| \hat{\Delta}_n \big\|_2 \big).\] For \(a,b>0\) and \(x \ge 0\), we have that \(x^2 \le ax+b\) implies \(x \le a+\sqrt b\); indeed, if \(x>a+\sqrt b\), we have \(x^2 > x(a+\sqrt b) >ax+(a +\sqrt b)\sqrt b > ax+b\). Thus, \[\label{eq:boundhatdelta1} \big\| \hat{\Delta}_n \big\|_2 \le \frac{2\sqrt{C_4 \eta}}{\sqrt{\lambda_{\min}(V_{\theta_0})}} + \frac{4C_1 \beta}{\lambda_{\min}(V_{\theta_0})}.\tag{96}\] As a consequence, \(\| \hat{\Delta}_n \|_2^2 \le C_6 \big( \eta+ \beta^2\big)\) with \(C_6 = \{8C_4/\lambda_{\min}(V_{\theta_0}) \} \vee \{32C_1^2/\lambda_{\min}^2(V_{\theta_0})\}\), which, using 87 with \(\theta=\hat{\theta}_n\), yields \[\begin{align} \label{eq:bound-errors-hat} |r_{n,2}(\hat{\theta}_n)| + |r_{n,3}(\hat{\theta}_n) | &\le \nonumber C_2\beta \big\| \hat{\Delta}_{n} \big\|_2^{2} + C_3(\beta)\big\| \hat{\Delta}_{n} \big\|_2^{2+\gamma_{h}} \\&\le\nonumber \Big( C_2C_6 \frac{\beta }{(\eta+ \beta^2)^{\gamma_{h}/2}}+C_3(\beta)C_6^{1+\gamma_{h}/2} \Big) (\eta+ \beta^2)^{1+\gamma_{h}/2} \\&\le C_{7}(\beta) (\eta+ \beta^2)^{1+\gamma_{h}/2}, \end{align}\tag{97}\] where \(C_7(\beta)= C_2C_6\beta^{1-\gamma_{h}} + C_3(\beta) C_6^{1+\gamma_{h}/2}\).

Next, let \[\widetilde{\Delta}_n = 2k^{-\frac{1}{2}}V_{\theta_0}^{-1} J_{\theta_0}^{\top} \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \mathrm d\mu(\boldsymbol{x}) = - V_{\theta_0}^{-1} \nabla Q_n^2(\theta_0)\] where the second equality follows from 88 . Note that we need to find \(\tilde{C}_r>0\) such that \(\| \hat{\Delta}_n - \widetilde{\Delta}_n \|_2^2 \le \tilde{C}_r(\eta+ \beta^{2+\gamma_{h}})\). On \(\Omega_1(n, \beta)\), we have \[\begin{align} \label{eq:boundhatdelta2} \big\| \widetilde{\Delta}_n \big\|_2 \le 2C_g {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{\theta_0}^{-1} J_{\theta_0}^{\top} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \beta \le 2C_g {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{\theta_0}^{-1} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert J_{\theta_0}^{\top} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \beta \le 2C_g C_V^{-1}\sqrt{sq} C_{\partial} \beta =: C_{8} \beta, \end{align}\tag{98}\] where we have used 85 . Further decreasing \(\tilde{C}_\beta\) if necessary, the right hand-side is bounded by \(\kappa\) for all \(\beta \in (0, \tilde{C}_\beta)\), which implies that \(\widetilde{\theta}_n := \theta_0 + \widetilde{\Delta}_n \in B_\kappa(\theta_0)\). We can hence apply the expansions and bounds derived at the beginning of this proof, specifically 86 , with \(\theta= \widetilde{\theta}_n\) and \(\Delta_{\widetilde{\theta}_n}= \widetilde{\Delta}_n\) to deduce that \[\label{eq:qn2-mest-tilde} Q_n^2(\widetilde{\theta}_n)-Q_n^2(\theta_0) = \frac{1}{2} \widetilde{\Delta}_{n}^\top V_{\theta_0} \widetilde{\Delta}_{n}+ r_{n,1}(\widetilde{\theta}_n) + r_{n,2}(\widetilde{\theta}_n) + r_{n,3}(\widetilde{\theta}_n),\tag{99}\] where, using 87 and 98 , \[\begin{align} \label{eq:bound-errors-tilde} |r_{n,2}(\widetilde{\theta}_n)| + |r_{n,3}(\widetilde{\theta}_n) | \le C_2\beta \big\| \widetilde{\Delta}_{n} \big\|_2^{2} + C_3(\beta)\big\| \widetilde{\Delta}_{n} \big\|_2^{2+\gamma_{h}} \le C_{9}(\beta) \beta^{2+\gamma_{h}}, \end{align}\tag{100}\] where \(C_{9}(\beta) = C_{8}^2\{ C_2\beta^{1-\gamma_{h}} + C_8^{\gamma_{h}}C_3(\beta)\}\). Overall, from 92 applied with \(\theta= \widetilde{\theta}_n\) and 94 and 99 , we find that \[\begin{align} C_{4} \eta &> Q_n^2(\hat{\theta}_n)-Q_n^2(\widetilde{\theta}_n) = \big( Q_n^2(\hat{\theta}_n)-Q_n^2(\theta_0)\big)-\big(Q_n^2(\widetilde{\theta}_n)-Q_n^2(\theta_0)\big) = M_n + \tilde{r}_n \end{align}\] where \[\begin{align} M_n &= \frac{1}{2} \hat{\Delta}_n^{\top} V_{\theta_0} \hat{\Delta}_n - \frac{1}{2} \widetilde{\Delta}_n^{\top} V_{\theta_0} \widetilde{\Delta}_n + \big[ \nabla Q_n^2(\theta_0)\big]^\top \big(\hat{\Delta}_n- \widetilde{\Delta}_n\big), \\ \tilde{r}_n &= r_{n,2}(\hat{\theta}_n)-r_{n,2}(\widetilde{\theta}_n) + r_{n,3}(\hat{\theta}_n)-r_{n,3}(\widetilde{\theta}_n). \end{align}\] In view of 97 and 100 , the remainder term satisfies \[|\tilde{r}_n| \le C_{7}(\beta) (\eta+ \beta^2)^{1+\gamma_{h}/2} + C_{9}(\beta) \beta^{2+\gamma_{h}} \le C_{10} (\eta+\beta^2)^{1+\gamma_{h}/2}\] with \(C_{10}=C_7(\tilde{C}_\beta) + C_{9}(\tilde{C}_\beta)\). Moreover, since \(\nabla Q_n^2(\theta_0) = - V_{\theta_0}\widetilde{\Delta}_n\), we find that \[\begin{align} M_n = \frac{1}{2} \hat{\Delta}_n^{\top} V_{\theta_0} \hat{\Delta}_n + \frac{1}{2} \widetilde{\Delta}_n^{\top} V_{\theta_0} \widetilde{\Delta}_n - \widetilde{\Delta}_n^{\top} V_{\theta_0} \hat{\Delta}_n &= \frac{1}{2} \Big\| V_{\theta_0}^{1/2}(\hat{\Delta}_n-\widetilde{\Delta}_n) \Big\|_2^2 \\&\ge \frac{1}{2} \lambda_{\min}(V_{\theta_0}) \big\|\hat{\Delta}_n-\widetilde{\Delta}_n\big\|_2^2. \end{align}\] Overall, \[C_4 \eta> \frac{1}{2} \lambda_{\min}(V_{\theta_0}) \big\|\hat{\Delta}_n-\widetilde{\Delta}_n\big\|_2^2 - C_{10}(\eta+\beta^2)^{1+\gamma_{h}/2}.\] Convexity of \(x \mapsto x^{1+\gamma_{h}/2}\) and the fact that \(\eta\le 1\) yields \[\big\|\hat{\Delta}_n-\widetilde{\Delta}_n\big\|_2^2 \le \frac{2}{\lambda_{\min}(V_{\theta_0})} \Big[ (C_4 + 2^{\gamma_{h}/2}C_{10}) \eta+ 2^{\gamma_{h}/2}C_{10} \beta^{2+\gamma_{h}} \Big].\] This proves 83 with \(\tilde{C}_{r1} = 2 (C_4 + 2^{\gamma_{h}/2}C_{10})/ {\lambda_{\min}(V_{\theta_0})}\).

To prove the second half of the theorem, note that \[\begin{align} & \Big\|\int_{[0,1]^d} V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x}) \mathbb{L}_n(\boldsymbol{x}) \, \mathrm d\mu(\boldsymbol{x}) - \int_{[0,1]^d\setminus A} V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x}) \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) \, \mathrm d\mu(\boldsymbol{x})\Big\|_2 \\ \le~& \int_{[0,1]^d\setminus A} \|V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x})\|_2 \cdot \big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) - {\mathbb{L}}_n(\boldsymbol{x}) \big| \, \mathrm d\mu(\boldsymbol{x}) + \int_{A} \|V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x})\|_2 \cdot |{\mathbb{L}}_n(\boldsymbol{x})| \, \mathrm d\mu(\boldsymbol{x}) \\ \le~& \Big(\sup_{\boldsymbol{x}\in [0,1]^d\setminus A} \big| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) - {\mathbb{L}}_n(\boldsymbol{x}) \big|\Big) \times \int_{[0,1]^d} \|V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x})\|_2 \, \mathrm d\mu(\boldsymbol{x}) \\ &+ \sqrt{k} \beta \int_{A} \|V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x})\|_2 \, \mathrm d\mu(\boldsymbol{x}). \end{align}\] The bound \[\begin{align} \label{eq:bound-vjg} \|V_{\theta_0}^{-1} J_{\theta_0}^\top\boldsymbol{g}(\boldsymbol{x})\|_2 \le {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{\theta_0}^{-1}J_{\theta_0}^\top \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \| \boldsymbol{g}(\boldsymbol{x}) \|_2 &\le {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{\theta_0}^{-1} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert J_{\theta_0}^\top \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2\| \boldsymbol{g}(\boldsymbol{x}) \|_2 \le C_V^{-1} \cdot \sqrt{sq} C_{\partial} \cdot \| \boldsymbol{g} (x)\|_2 \end{align}\tag{101}\] completes the proof of Theorem 17, with \(\tilde{C}_{r2} = C_V^{-1} \sqrt{sq} C_{\partial}(C_g \vee 1)\). ◻

Proof of Theorem 12. First, all assumptions of Theorem 3 are satisfied, and an application of that theorem implies that there exist constants \(D_1 = D_1(d,K_L)\) and \(D_2 = D_2(d,K_L)\) and an event \(\Omega_2\) that has probability at least \(1-(6d+5)\delta\) on which \[\sup_{\boldsymbol{x} \in [0,1]^d \setminus (\mathfrak B^{\oplus C_{s}r})} \big| \mathbb{L}_n(\boldsymbol{x}) - \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) \big| \le \zeta_{n,2} := B_{n,k}(L; [0,1+C_{s}r]^d) + \frac{d}{\sqrt{k}} + D_{1} \sqrt{r\log\Big(\frac{D_{2}}{\delta r}\Big)}.\]

On the same event, by 35 , \[\begin{align} \max_{j\in[d]} \sup_{x_j \in [0,1]} |S_{nj}(x_j) - x_j| \le C_{s}r, \end{align}\] and in view of the decomposition \[\begin{align} \mathbb{L}_n = \widetilde{\mathbb{L}}_n \circ S_n + \sqrt k (L \circ S_n - L) + B_n \circ S_n \end{align}\] from 34 , we obtain that \[\begin{align} \sup_{\boldsymbol{x}\in [0,1]^d}|\mathbb{L}_n(\boldsymbol{x})| &\le \sup_{\boldsymbol{x}\in [0,1+C_{s}r]^d}|\widetilde{\mathbb{L}}_n(\boldsymbol{x})| + C_{s}d r \sqrt{k} + B_{n,k}(L;[0,1+C_{s}r]^d) \\&\le \sup_{\boldsymbol{x}\in [0,2]^d}|\widetilde{\mathbb{L}}_n(\boldsymbol{x})| + C_{s}d r \sqrt{k} + B_{n,k}(L;[0,2]^d) \end{align}\] by Lipschitz continuity of \(L\) and using that \(C_{s}r \le 1\) by assumption.

The current choice of \(\delta\) also satisfies the conditions of Lemma 10 with \(T=2\). Hence there exists an event \(\Omega_3\) with probability at least \(1-\delta\) on which \[\sup_{\boldsymbol{x}\in [0,2]^d} |\widetilde{\mathbb{L}}_n(\boldsymbol{x})| \le (188/3) \cdot d \cdot \sqrt{2 \log(1/\delta)} = (188\sqrt 2/3) \cdot d r \sqrt{k}.\] Combining the above, we find that on \(\Omega_2\cap\Omega_3\) \[\sup_{\boldsymbol{x}\in [0,1]^d} \big|\mathbb{L}_n(\boldsymbol{x}) \big| \le (C_{s}+188\sqrt 2/3)dr \sqrt{k} + B_{n,k}(L;[0,2]^d) =\sqrt k \zeta_{n,1}.\] As a consequence, \(\Omega_2\cap\Omega_3 \subseteq\Omega_1(n,\zeta_{n,1})\) with \(\Omega_1(\cdot,\cdot)\) from 82 . By an application of the second part of Theorem 17 with \(A=\mathfrak B^{\oplus C_{s}r}\) we obtain \[\sqrt{k} \big( \hat{\theta}_n- \theta_0 \big) = 2V_{\theta_0}^{-1} J_{\theta_0}^\top \int_{[0,1]^d\setminus \mathfrak B^{\oplus C_{s}r}} \boldsymbol{g}(\boldsymbol{x}) \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) \, \mathrm d\mu(\boldsymbol{x}) + \sqrt{k} \boldsymbol{r}_{n,1}(\beta,\eta) + \boldsymbol{r}_{n,2}(\mathfrak B^{\oplus C_{s}r})\] where \[\|r_{n,2}(\mathfrak B^{\oplus C_{s}r})\|_2 \le \tilde{C}_{r2} \Big( \zeta_{n,2} + \sqrt{k} \zeta_{n,1}\int_{\mathfrak B^{\oplus C_{s}r}} \|\boldsymbol{g}(\boldsymbol{x})\|_2 \, \mathrm d\mu(\boldsymbol{x}) \Big).\] In the following, with a slight abuse of notation, we extend the definition of \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n\) to \([0,1]^d\) by replacing the partial derivatives of \(L\) by the their right-hand side counterparts as described in the paragraph before Theorem 12. Then, by an application of Lemma 10 we have, on an event \(\Omega_4\) that has probability at least \(1-(d+1)\delta\), \[\begin{align} \sup_{\boldsymbol{x}\in [0,1]^d}| \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x})| \le \sup_{\boldsymbol{x}\in [0,1]^d}|\widetilde{\mathbb{L}}_n(\boldsymbol{x})| + \sum_{j \in [d]}\sup_{x \in [0,1]} |\widetilde{\mathbb{L}}_{nj}(\boldsymbol{x})| \le 2\cdot(188/3)\cdot dr \cdot \sqrt{k}. \end{align}\] Thus, on the event \(\Omega_2\cap\Omega_3\cap\Omega_4\) and using 101 , we have \[\begin{align} &\Big\|2V_{\theta_0}^{-1} J_{\theta_0}^\top \int_{[0,1]^d\setminus \mathfrak B^{\oplus C_{s}r}} \boldsymbol{g}(\boldsymbol{x}) \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) \, \mathrm d\mu(\boldsymbol{x}) - 2V_{\theta_0}^{-1} J_{\theta_0}^\top \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) \, \mathrm d\mu(\boldsymbol{x})\Big\|_2 \\ & \le 4 \cdot(188/3)\cdot dr \cdot \sqrt{k} \cdot \int_{\mathfrak B^{\oplus C_{s}r}} \|V_{\theta_0}^{-1} J_{\theta_0}^\top \boldsymbol{g}(\boldsymbol{x})\|_2 \, \mathrm d\mu(\boldsymbol{x}) \\ & \le 4 \sqrt{k} \zeta_{n,1} \int_{\mathfrak B^{\oplus C_{s}r}} \|V_{\theta_0}^{-1} J_{\theta_0}^\top \boldsymbol{g}(\boldsymbol{x})\|_2 \, \mathrm d\mu(\boldsymbol{x}) \\&\le 4C_V^{-1} \sqrt{sq} C_{\partial} \cdot \sqrt{k} \zeta_{n,1}\int_{\mathfrak B^{\oplus C_{s}r}} \| \boldsymbol{g}(\boldsymbol{x})\|_2 \, \mathrm d\mu(\boldsymbol{x}) . \end{align}\] Noting that \(\Omega_2\cap\Omega_3\cap\Omega_4\) has probability at least \(1 - 7(d+1)\delta\) and that \[2V_{\theta_0}^{-1} J_{\theta_0}^\top \int_{[0,1]^d} \boldsymbol{g}(\boldsymbol{x}) \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\mathbb{L}} \endgroup _n(\boldsymbol{x}) \, \mathrm d\mu(\boldsymbol{x}) = \frac{1}{\sqrt{k}} \sum_{i=1}^n \big( Z_{i,n} - \mathbb{E}[Z_{i,n}] \big)\] by definition of \(Z_{i,n}\) in 23 completes the proof, after increasing \(\tilde{C}_{r2}\). ◻

Proof of Theorem 13. Without loss of generality, \[\begin{align} \label{eq:helpMestBmax} \frac{\log^5(sn)}{k} \leq 1, \quad B_{n,k}^{\mathcal{I}} \le 1 \end{align}\tag{102}\] as otherwise the right-hand side in the theorem is greater than 1. We start by bounding \(d_K(\boldsymbol{S}_n, \boldsymbol{T}_n)\). By Lemma 14, for any \(\lambda>0\), \[\begin{align} d_K(\boldsymbol{S}_n , \boldsymbol{T}_n) &\le \mathbb{P}\big(\|\boldsymbol{S}_n-\boldsymbol{T}_n\|_\infty \ge \lambda\big) + \sup_{\boldsymbol{x} \in \mathbb{R}^{s}} \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}+\lambda \boldsymbol{1} ) - \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}-\lambda \boldsymbol{1}) \\ &\leq \sum_{I \in \mathcal{I}} \mathbb{P}\big( \|\boldsymbol{S}_n^I - \boldsymbol{T}_n^I\|_2 \geq \lambda\big)+\sup_{\boldsymbol{x} \in \mathbb{R}^{s}} \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}+\lambda \boldsymbol{1} ) - \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}-\lambda \boldsymbol{1}), \end{align}\] where we have used the union bound and the fact that \(\| \cdot \|_\infty \le \| \cdot \|_2\). By the assumption that \(\sigma^2_{\min}>0\), with the same reasoning as in the proof of Theorem 7, specifically 50 , \[\begin{align} \sup_{\boldsymbol{x} \in \mathbb{R}^{s}} \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}+\lambda \boldsymbol{1} ) - \mathbb{P}( \boldsymbol{T}_n \le \boldsymbol{x}-\lambda \boldsymbol{1}) \leq \frac{8\lambda}{\sigma_{\min}^2} \sqrt{\log s} + 2 d_K(\boldsymbol{T}_n, \boldsymbol{G}_n). \end{align}\] Thus \[\begin{align} \label{eq:dk-sn-gn-m-estimators} d_K(\boldsymbol{S}_n, \boldsymbol{G}_n) \leq \sum_{I \in \mathcal{I}} \mathbb{P}(\left\lVert\boldsymbol{S}_n^I - \boldsymbol{T}_n^I\right\rVert_2 \geq \lambda) + \frac{8\lambda}{\sigma_{\min}^2} \sqrt{\log(s)} + 3 d_K(\boldsymbol{T}_n, \boldsymbol{G}_n). \end{align}\tag{103}\] In the remaining proof, we will choose a suitable \(\lambda\) to balance the second and third term and bound \(d_K(\boldsymbol{T}_n, \boldsymbol{G}_n)\).

Bounding \(d_K(\boldsymbol{T}_n, \boldsymbol{G}_n)\). We will apply Theorem 19 to the random vector \(\boldsymbol{Y}_{i,n} \in \mathbb{R}^{s}\) with entries given by \(Y_{i,n,(I,t)} = k^{-1/2} (Z_{i,n}^{I,t} - \mathbb{E}[Z_{i,n}^{I,t}])\), enumerating over \(I \in \mathcal{I}\) and \(t \in [s^I]\). By assumption, \(\mathbb{E}[Y_{i,n,(I,t)}^2] \geq \sigma^2_{\min}\).

Next, note that \[|Z_{i,n}^{I,t}| \le \| \boldsymbol{Z}_{i,n}^I\|_2\le 2 {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert V_{\theta_0^I}^{-1}J_{\theta_0^I}^\top \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 \| \boldsymbol{A}^I_{i,n}\|_2 \le 2 (C_V^{\mathcal{I}})^{-1}\sqrt{s^{\mathcal{I}} q^{\mathcal{I}}} C_{\partial}^{\mathcal{I}} \cdot \| \boldsymbol{A}^I_{i,n}\|_2\] where \(s^{\mathcal{I}} =\max_{I \in \mathcal{I}} s^I\) and \(q^{\mathcal{I}} = \max_{I \in \mathcal{I}} q^I\). Further, by the same argumentation that lead to 85 , we have \[\begin{align} \left\lVert\boldsymbol{A}^I_{i,n}\right\rVert_2 &\leq C_g^{\mathcal{I}} \sup_{\boldsymbol{x}\in [0,1]^I} \Big| \mathbf{1}\!\Big(\exists j\in I:\; V_{ij}<\frac{k}{n}x_j\Big) - \sum_{j\in I} \partial_j \widetilde{L}_I(\boldsymbol{x}_I)\, \mathbf{1}\!\Big(V_{ij}<\frac{k}{n}x_j\Big) \Big| \\ &\leq C_g^{\mathcal{I}} \left|I\right| \leq C_g^{\mathcal{I}} m. \end{align}\] Combining the previous two inequalities, we obtain that \[\begin{align} \label{eq:deftildeC} \sup_{I \in \mathcal{I}, t \in [q^I]}\big| Z_{i,n}^{I,t}-\mathbb{E}[Z_{i,n}^{I,t}]\big| \leq 2 (C_V^{\mathcal{I}})^{-1}\sqrt{s^{\mathcal{I}} q^{\mathcal{I}}} C_{\partial}^{\mathcal{I}}C_g^{\mathcal{I}} m =: \tilde{C}. \end{align}\tag{104}\] Also, \[\begin{align} \left\lVert\boldsymbol{A}^I_{i,n}\right\rVert_2 &\leq C_g^{\mathcal{I}} \Big\{ \sup_{\boldsymbol{x}_I \in [0,1]^I} \mathbf{1}\Big(\exists j\in I:\; V_{ij}<\frac{k}{n}x_j\Big) + \sum_{j \in I} \sup_{\boldsymbol{x}_I \in [0,1]^I} \mathbf{1}\Big(V_{ij}<\frac{k}{n}x_j\Big) \Big\} \\ &\leq 2C_g^{\mathcal{I}} \sum_{j \in I} \sup_{\boldsymbol{x}_I \in [0,1]^I} \mathbf{1}\Big(V_{ij}<\frac{k}{n}x_j\Big) \\ &\leq 2C_g^{\mathcal{I}} \sum_{j \in I} \mathbf{1}\Big(V_{ij}<\frac{k}{n}\Big), \end{align}\] which yields \[\begin{align} \mathbb{E}\big[\big| Z_{i,n}^{I,t} -\mathbb{E}[Z_{i,n}^{I,t}] \big| \big] \le 2 \mathbb{E}\big| Z_{i,n}^{I,t}\big| &\le 4(C_V^{\mathcal{I}})^{-1}\sqrt{s^{\mathcal{I}} q^{\mathcal{I}}} C_{\partial}^{\mathcal{I}} \cdot \mathbb{E}\| \boldsymbol{A}_{i,n}^{I} \|_2 \\&\le 8(C_V^{\mathcal{I}})^{-1}\sqrt{s^{\mathcal{I}} q^{\mathcal{I}}} C_{\partial}^{\mathcal{I}} C_g^{\mathcal{I}} m\cdot \frac{k}{n} =4 \tilde{C} \frac{k}{n}. \end{align}\] Hence, \[\begin{align} \sum_{i=1}^n \mathbb{E}\Big| k^{-1/2} \big(Z_{i,n}^{I,t}-\mathbb{E}[ Z^{I,t}_{i,n}] \big)\Big|^4 &\leq \tilde{C}^3 \frac{n}{k^2} \mathbb{E}\Big[\big| Z_{1,n}^{I,t} -\mathbb{E}[Z_{1,n}^{I,t}] \big| \Big] \leq 4\tilde{C}^4 \frac{1}{k} = \frac{b_2 B_n^2}{n}, \end{align}\] where \(B_n = (\log 2)^{-1}\tilde{C}\sqrt{n/k}\) and \(b_2 = 4(\log 2)^2 \tilde{C}^{2}\). With these choices, we also have \[\frac{\sqrt{n}\big| k^{-1/2}(Z_{i,n}^{I,t}-\mathbb{E}[Z_{i,n}^{I,t}])\big| }{B_n} \le \frac{\sqrt{n/k} \tilde{C}}{B_n} = \log2,\] and hence the conditions of Theorem 19 hold with \(b_1 = \sigma^2_{\min}\). An application of the theorem yields \[\begin{align} \label{eq:dk-tn-gn-m-estimators} d_K(\boldsymbol{T}_n, \boldsymbol{G}_n) \leq C_1 \Big( \frac{\log^5(s n)}{k}\Big)^{1/4}, \end{align}\tag{105}\] with \(C_1\) depending only on \(\sigma^2_{\min}\) and \(\tilde{C}\).

Choosing \(\lambda\). Let \[\begin{align} \label{eq:helpMestdefdelta} \delta = \frac{1}{m |\mathcal{I}|}\Big(\frac{\log^5(sn)}{k}\Big)^{1/4} \end{align}\tag{106}\] and recall \(r = r(\delta, 1,k) = \sqrt{k^{-1}\log(1/\delta)}\) from 13 . By our assumption in 102 from the beginning of the proof, we have \(\delta \le 1/(m|\mathcal{I}|) < e^{-1}\), and we will later verify that this \(\delta\) also satisfies the conditions \(\log(m/\delta)\le 2k/7\) and \(C_{s}r \le 1\). We may therefore apply Theorem 12 for each tuple \((L_I, \{L_I(\cdot; \theta^I): \theta^I \in \Theta^I\}, \boldsymbol{g}^I, \mu^I)\), which yields the existence of certain constants \(D_1^I, D_2^I>0, \tilde{C}_\beta^I, \tilde{C}_\eta^I \in (0,1]\) and \(\tilde{C}_{r1}^I, \tilde{C}_{r2}^I>0\) such that certain claims hold with probability at least \(1-7(|I|+1)\delta \ge 1-7(m+1)\delta\). In the following, we will make use of these claims.

Let \(\tilde{C}_\beta^{\mathcal{I}} = \min_{I \in \mathcal{I}} \tilde{C}_\beta^I\) and \[\begin{align} \label{eq:definition-zeta95n1-mest} \zeta_{n,1}^{\mathcal{I}} := \max_{I \in \mathcal{I}} \zeta_{n,1}^I, \qquad \zeta_{n,1}^I := \Big( k^{-1/2} \sup_{\boldsymbol{x}_I \in [0,2]^{I}} \left|B_n^I(\boldsymbol{x}_I)\right| +(C_{s}+188\sqrt 2/3)\cdot |I| r \Big). \end{align}\tag{107}\] We will later verify that \(\zeta_{n,1}^{\mathcal{I}} \le \tilde{C}_\beta^{\mathcal{I}},\) which in turn implies that \(\zeta_{n,1}^I \le C_\beta^{I}\) for each \(I \in \mathcal{I}\). Theorem 12 therefore guarantees that, for any \(\eta< \tilde{C}_{\eta}^{\mathcal{I}} := \min_{I \in \mathcal{I}} \tilde{C}_\eta^I\), \[\begin{align} \label{eq:dk-sni-tni-m-estimators} \sum_{I \in \mathcal{I}} \mathbb{P}\big( \|\boldsymbol{S}_n^I - \boldsymbol{T}_n^I\|_2 \geq \lambda_{n,k}(\delta) \big) \leq 7|\mathcal{I}|(m+1)\delta \leq 14|\mathcal{I}|m\delta = 14\cdot \Big(\frac{\log^5(sn)}{k}\Big)^{1/4} \end{align}\tag{108}\] where \(\lambda_{n,k}(\delta) := \zeta_{n,2}^{\mathcal{I}} + \zeta_{n,3}^{\mathcal{I}}\) with \[\begin{align} \zeta_{n,2}^{\mathcal{I}} & := \max_{I \in \mathcal{I}} \zeta_{n,2}^I, \qquad \zeta_{n,3}^{\mathcal{I}} := \max_{I \in \mathcal{I}} \zeta_{n,3}^I, \end{align}\] where, recalling that \(\gamma_{h}=1\) by assumption, \[\begin{align} \zeta_{n,2}^I &= \sqrt{\tilde{C}_{r1}^I k \{ (\zeta_{n,1}^{I})^{3} + \eta\} }, \\ \zeta_{n,3}^I &= \tilde{C}_{r2}^I \Big(\sup_{\boldsymbol{x}_I \in [0,2T]^{I}} |B_n^I(\boldsymbol{x}_I)| + \frac{\left|I\right|}{\sqrt{k}} + D_{1}^I \sqrt{r\log\Big(\frac{D_{2}^I}{\delta r}\Big)} \Big) \\ & + \sqrt k \zeta_{n,1}^I \int_{\mathfrak B_I^{\oplus C_{s}r}} \|{\boldsymbol{g}}^I(\boldsymbol{x}_I)\|_2 \, \mathrm d\mu^I(\boldsymbol{x}_I) \Big). \end{align}\] In summary, from 103 , 105 and 108 , \[\begin{align} \label{eq:bounddKprelim1} d_K(\boldsymbol{S}_n, \boldsymbol{G}_n) \lesssim (\zeta_{n,2}^{\mathcal{I}} + \zeta_{n,3}^{\mathcal{I}}) \sqrt{\log(s)} + \Big(\frac{\log^5(sn)}{k}\Big)^{1/4}, \end{align}\tag{109}\] where the constant in \(\lesssim\) depends on \(\sigma_{\min}\) and \(\tilde{C}\) from 104 .

We now bound \(\zeta_{n,2}^{\mathcal{I}}\). First, by our choice of \(\delta\) in 106 , \[\begin{align} \label{eq:boundhelpr951} r = \sqrt{\frac{1}{k} \log\Big( \frac{m|\mathcal{I}|k^{1/4}}{\log^{5/4}(sn)}\Big)} \leq \sqrt{\frac{1}{k} \log(m s k^{1/4})} \leq C_2 \sqrt{\frac{\log(sk)}{k}} \end{align}\tag{110}\] with \(C_2 = \sqrt{1+\log m}\) as \[\log(msk^{1/4}) \leq \log(m)+\log(sk) \leq \log(sk) \autobracket*{1 + \log m} = C_2^2 \log(sk),\] using that \(\log(sk) \geq \log(6) \ge 1\). Recall our assumption \(B_{n,k}^{\mathcal{I}} \le 1\) from the beginning of the proof. Moreover, since \(\delta \le e^{-1}\), we have \(k^{-1/2} \le r \le mr\) and thus, by 107 and 110 , \[\begin{align} \label{eq:helpboundzetan1} \zeta_{n,1}^{\mathcal{I}} \le (1+C_{s}+188\sqrt 2/3) \cdot mr \le C_3 \sqrt{\frac{\log(sk)}{k}} \end{align}\tag{111}\] where \(C_3 := C_2 (C_{s}+1+188\sqrt 2/3)m\). Hence, by subadditivity of \(x \mapsto \sqrt x\) on \([0,\infty)\), \[\begin{align} \zeta_{n,2}^{\mathcal{I}} &\le \sqrt{\tilde{C}_{r1}^{\mathcal{I}} k} \times \big\{ (\zeta_{n,1}^{\mathcal{I}})^{3/2} + \sqrt{\eta} \big\} \leq C_4 \Big\{ \Big(\frac{\log^3(sk)}{k}\Big)^{1/4} + \sqrt{k\eta}\Big\}, \label{eq:boundzetan2} \end{align}\tag{112}\] where \(\tilde{C}_{r1}^{\mathcal{I}} = \max_{I \in \mathcal{I}}\tilde{C}_{r1}^{I}\) and where \(C_4 = (\tilde{C}_{r1}^{\mathcal{I}})^{1/2}C_3^{3/2}\).

Next, we bound \(\zeta_{n,3}^{\mathcal{I}}\). First, using that \[\delta = \frac{1}{m|\mathcal{I}|} \Big( \frac{\log^5(sn)}{k} \Big)^{1/4} \ge \frac{1}{m|\mathcal{I}|k^{1/4}} \ge \frac{1}{msk^{1/4}}\] and \(r \geq k^{-1/2}\), we obtain, recalling 110 , \[\begin{align} \max_{I \in \mathcal{I}} D_1^I\sqrt{r\log\Big(\frac{D_{2}^I}{\delta r}\Big)} &\leq D_1^{\mathcal{I}}C_2^{1/2} \Big(\frac{\log(sk)}{k}\Big)^{1/4} \sqrt{\log(D_2^{\mathcal{I}} ms k^{3/4})} \leq C_5 \Big( \frac{\log^3(sk)}{k}\Big)^{1/4} \end{align}\] where \(D_j^{\mathcal{I}} = \max_{I \in \mathcal{I}} D_j^I\) and \(C_5 = D_1^{\mathcal{I}}C_2^{1/2} \{1 + \log(D_2^{\mathcal{I}} m)\}^{1/2}\) and we used \(sk\ge 3\) so that \[\log(D_2^{\mathcal{I}} ms k^{3/4}) = \log(D_2^{\mathcal{I}}m) + \log(s k^{3/4}) \leq \log(sk)\{ 1 + \log(D_2^{\mathcal{I}} m) \}.\] Together with 111 and \(C_{s}r \le \zeta_n\) by 110 with \(\zeta_n\) from the formulation of the theorem, we obtain that \[\begin{align} \label{eq:boundzetan3} \zeta_{n,3}^{\mathcal{I}} \le\tilde{C}_{r2}^{\mathcal{I}} \Big\{ B_{n,k}^{\mathcal{I}} + (C_5 +m)\Big( \frac{\log^3(sk)}{k}\Big)^{1/4} + C_3 \sqrt{\log(sk)} \int_{\mathfrak B_I^{\oplus \zeta_n}} \|{\boldsymbol{g}}^I(\boldsymbol{x}_I)\|_2 \, \mathrm d\mu^I(\boldsymbol{x}_I) \Big\} \end{align}\tag{113}\]

Combining the bounds in 109 , 112 and 113 we obtain \[\begin{align} d_K(\boldsymbol{S}_n, \boldsymbol{G}_n) &\lesssim \Big(\frac{\log^5(sn)}{k}\Big)^{1/4} + \sqrt{\log s}\Big\{ B_{n,k}^{\mathcal{I}} + \Big(\frac{\log^3(sk)}{k}\Big)^{1/4} \\ &+ \sqrt{k\eta} + \sqrt{\log(sk)} \int_{\mathfrak B_I^{\oplus \zeta_n}} \|{\boldsymbol{g}}^I(\boldsymbol{x}_I)\|_2 \, \mathrm d\mu^I(\boldsymbol{x}_I)\Big\}, \end{align}\] which implies the assertion.

It remains to verify that \(\delta\) as defined in 106 satisfies \(\log(m/\delta)\le 2k/7\) and \(C_{s}r \le 1\) and \(\zeta_{n,1}^{\mathcal{I}} \le \tilde{C}_\beta^{\mathcal{I}}\). First, \[\begin{align} \log\autobracket*{\frac{m}{\delta}} = \log\Big( \frac{m^2 \left|\mathcal{I}\right| k^{1/4}}{\log^{5/4}(sn)} \Big) \leq \log(m^2 \left|\mathcal{I}\right| k^{1/4}) \leq 2k/7 \end{align}\] by assumption (ii). Next, by assumption (iii), \[\begin{align} r = \sqrt{\frac{1}{k}\log\Big( \frac{1}{\delta}\Big)} = \sqrt{\frac{1}{k}\log\Big( \frac{m|\mathcal{I}|k^{1/4}}{\log^{5/4}(sn)} \Big)} \le \sqrt{\frac{1}{k}\log( m|\mathcal{I}|k^{1/4})} \le \frac{1}{C_{s}} \end{align}\] Finally, from 110 and 111 , \[\zeta_{n,1}^{\mathcal{I}} \le m(1+C_{s}+ 188\sqrt{2}/3) \sqrt{ \frac{1}{k}\log(m|\mathcal{I}|k^{1/4})}.\] The right-hand side is upper bounded by \(\tilde{C}_\beta^{\mathcal{I}}\) if we choose \(\tilde{C}_{k}^{\mathcal{I}} = [\tilde{C}_\beta^{\mathcal{I}} / \{m(1+C_{s}+ 188\sqrt{2}/3)\}]^2\). This completes the proof. ◻

Proof. Fix \(I \subseteq[d]\), write \(m=|I|\) and define \(\mu_{n,I} = \frac{1}{n} \sum_{i=1}^n \delta_{V_{i,I}}\) and let \(\mu_I\) denote the distribution of \(V_{i,I}\). Then we can write \[\sup_{\boldsymbol{x} \in [0,T]^I} | \widetilde{\mathbb{L}}_{n,I}(\boldsymbol{x})| = \frac{n}{\sqrt k} \sup_{A \in \mathcal{A}} | \mu_{n,I}(A) - \mu_I(A)|\] where \(\mathcal{A}\) contains all sets of the form \(A_{\boldsymbol{x}} = \{ \boldsymbol{z} \in [0,\infty)^I \mid \exists j \in I: z_j < (k/n) x_j \}\) with \(\boldsymbol{x} \in [0, T]^I\). Let \(\mathbb{A} := \bigcup_{A\in \mathcal{A}} A\), with \(p = \mu(\mathbb{A}) = \mathbb{P}(\exists j \in I : V_{ij} \le \frac{k}{n} T) \le mTk/n\). By Theorem A.1 in [26] we have, with probability at least \(1-\delta\), \[\sup_{A \in \mathcal{A}} | \mu_n(A) - \mu(A)| \le \frac{2}{3n} \log(1/\delta) + \sqrt{\frac{mTk}{n^2}} \Big\{ 2 \sqrt{\log(1/\delta)}+ 60 \sqrt m\Big\},\] where we have used that the VC-dimension of \(\mathcal{A}\) is \(m\). Since \(1 \le \log(1/\delta) \le m^2 T k\), we get the upper bound \[\begin{align} \sup_{\boldsymbol{x} \in [0,T]^I} | \tilde{\mathbb{L}}_{n,I}(\boldsymbol{x})| &\le \frac{2}{3 \sqrt k} \log(1/\delta) + \sqrt{mT} \Big\{ 2 \sqrt{\log(1/\delta)}+ 60 \sqrt m\Big\} \\&\le \frac{2}{3\sqrt k} m\sqrt{Tk \log(1/\delta)} + \sqrt{mT} \Big\{2\sqrt{\log(1/\delta)} + 60\sqrt{m}\Big\} \\& \le m\sqrt{T\log(1/\delta)}\Big\{ \frac{2}{3} + \frac{2}{\sqrt m} + 60 \Big\} \le (188/3) m \sqrt{T \log(1/\delta)} \end{align}\] with probability at least \(1-\delta\). ◻

Proof of Lemma 11. First, note that \(\sup_{x_j \in [0,T]} S_{nj}(x_j) = (n/k) \cdot V_{kT:n, j}\) by monotonicity. Moreover, writing \(G_{nj}(v_j)=n^{-1}\sum_{i=1}^n \boldsymbol{1}(V_{ij} \le v_j)\), we have \(V_{\ell:n} \le x\) iff \(G_{nj}(x) \ge \ell/n\) for all \(\ell \in[n]\) and \(x \in \mathbb{R}\), which implies \[\frac{n}{k} V_{kT:n, j} \le 2T \quad \Longleftrightarrow \quad G_{nj}\Big( 2\frac{kT}{n} \Big) \ge \frac{kT}{n}.\] As a consequence, by the union bound, \[\begin{align} \mathbb{P}\Big(\max_{j\in[d]} \sup_{x_j \in [0,T]} S_{nj}(x_j) > 2 T \Big) \le d \cdot \mathbb{P}\Big( G_{nj}\Big( 2\frac{kT}{n} \Big) < \frac{kT }{n} \Big) &\le d \cdot \big(\sqrt 2 e^{-1/2}\big)^{2kT} \\&= d \cdot \exp\big( - (1-\log2) kT \big\}, \end{align}\] where the second inequality follows from the multiplicative Chernoff bound; see, for instance, Exercise 2.11 in [60]. By our assumption \(\log(d/\delta) \le (1-\log2) kT\), the upper bound in the previous display is smaller than \(\delta\). This proves 114 .

We may now proceed analogously to the proof of Lemma 9 in [24] to show that \[\begin{align} \label{eq:bound-gauss} \max_{j\in[d]} \sup_{x_j \in [0,T]} \Big|S_{nj}(x_j) - \frac{\lceil kx_j\rceil}{k}\Big| \le (188\sqrt{2}/3) \sqrt{\frac{T}{k} \log\Big(\frac{1}{\delta}\Big)} \end{align}\tag{116}\] with probability at least \(1-(d+1)\delta\). Indeed, by the definition of \(S_{nj}\) in 32 , we have, on the event in 114 , \[\begin{align} \sup_{x_j \in [0,T]} \Big|S_{nj}(x_j) - \frac{\lceil kx_j\rceil}{k}\Big| &= \sup_{x_j \in (0,T]} \Big| S_{nj}(x_j) - \frac{n}{k} G_{nj}\big(V_{\lceil kx_j\rceil:n, j}\big) \Big| \\&= \frac{n}{k} \sup_{x_j \in (0,T]} \Big| \frac{k}{n} S_{nj}(x_j) - G_{nj}\Big( \frac{k}{n} S_{nj}(x_j) \Big) \Big| \\&\le \frac{n}{k} \sup_{x_j \in [0, 2T]} \Big| \frac{k}{n} x_j - G_{nj}\Big( \frac{k}{n} x_j \Big) \Big| \\&= \sup_{x_j \in [0, 2T]} \Big| x_j - \widetilde{L}_{nj}( x_j ) \Big| =\frac{1}{\sqrt k}\sup_{x_j \in [0,2T]} | \tilde{\mathbb{L}}_{nj}(x_j)| \end{align}\] where we used that \(\frac{n}{k} G_{nj}(\frac{k}{n} x_j - ) = \widetilde{L}_{nj}(x_j)\). As a result, since \(\log(1/\delta) \le \log(d/\delta) \le ( 1-\log2) kT \le 2Tk\), the assertion in 116 follows from Lemma 10, applied with \(T\) replaced by \(2T\), and the union bound. Finally, the result in 115 follows from the triangular inequality, observing that \[\sup_{x_j \in [0,T]} \Big| \frac{\lceil kx_j\rceil}{k} - x_j\Big| \le \frac{1}{k} \le \sqrt{1-\log2} \sqrt{\frac{T}{k} \log \Big(\frac{1}{\delta}\Big)},\] again using that \(\log(1/\delta) \le ( 1-\log2) kT\). ◻

Proof. The proof is largely inspired by [61]. For \(j \in [d]\) and \(k \in K_j := \{ 1, \dots, \lceil (b_j-a_j)/\varepsilon\rceil \}\) define \[\mathcal{A}_{j,k} = \Big\{ [\boldsymbol{x},\boldsymbol{y}) \subseteq[0,1)^d : \;a_j+\varepsilon(k - 1) \le x_j < y_j \le a_j+\varepsilon k \Big\},\] which has VC-dimension \(2d\). Next, let \(\mathbb{A}_{j,k} = \bigcup_{A \in \mathcal{A}_{j,k}} A\), and note that for all \(j \in [d], k \in K_j\) we have \(\mathbb{P}(\boldsymbol{V} \in \mathbb{A}_{j,k}) \le \mathbb{P}(V_j \in [a_j+\varepsilon(k-1), a_j+\varepsilon k]) \le \varepsilon\).

Let \(\tilde{\delta} >0\). Then, by Theorem A.1 in [26], applied with \(B = \mathbb{A}_{j,k}\), there exists an event \(\Omega_{j,k}\) with probability at least \(1-\tilde{\delta}\) such that, on \(\Omega_{j,k}\), \[\sup_{A\in \mathcal{A}_{j,k}} |\mu_{n}(A) - \mu(A) | \le \frac{2}{3n} \log(1/{\tilde{\delta}}) + \sqrt{\frac{\varepsilon}{n}}\Big\{2 \sqrt{\log(1/{\tilde{\delta}})}+ 60\sqrt{2d} \Big\},\] where \(\mu_{n} = n^{-1} \sum_{i=1}^n \delta_{\boldsymbol{V}_{i}}\) and where \(\mu\) is the distribution of \(\boldsymbol{V}_{i}\). Note that \(|K_j| = \lceil (b_j-a_j)/\varepsilon\rceil \le (b_j-a_j)/\varepsilon+ 1 \le 2(b_j-a_j)/\varepsilon\). On the intersection set \(\Omega_1 = \bigcap_{j \in [d]} \bigcap_{k \in K_j} \Omega_{j,k}\), which has probability at least \(1- \sum_{j \in [d]}|K_j| \tilde{\delta} \ge 1-2 \| \boldsymbol{b} - \boldsymbol{a} \|_1 \tilde{\delta} /\varepsilon\), we obtain that \[\max_{j \in [d]} \max_{k \in K_j }\sup_{A\in \mathcal{A}_{j,k}} |\mu_{n}(A) - \mu(A) | \le \Big[ \frac{2}{3n} \log(1/{\tilde{\delta}}) + \sqrt{\frac{\varepsilon}{n}}\Big\{2 \sqrt{\log(1/{\tilde{\delta}})}+ 60\sqrt{2d} \Big\} \Big].\] Let \[\mathcal{A}:= \Big\{\;R_{k_1, \dots, k_d} := \bigtimes_{j = 1}^d \big[ a_j+(k_j - 1)\varepsilon, (a_j+k_j\varepsilon)\wedge b_j \big] \;: \;k_j \in K_j \Big\}\] denote a cover of \([\boldsymbol{a}, \boldsymbol{b}]\) consisting of axis aligned hyper-rectangles \(R_{k_1, \dots, k_d}\) with edge length at most \(\varepsilon\), and note that \[\begin{align} \omega_{\alpha_{n}}(\varepsilon, [\boldsymbol{a}, \boldsymbol{b}]) &= \sup_{\|\boldsymbol{x} - \boldsymbol{y} \|_\infty \le \varepsilon, \boldsymbol{x},\boldsymbol{y} \in [\boldsymbol{a}, \boldsymbol{b}]} |\alpha_{n}(\boldsymbol{x}) - \alpha_{n}(\boldsymbol{y})| \le 2 \max_{R \in \mathcal{A}} \sup_{\boldsymbol{x}, \boldsymbol{y} \in R} |\alpha_{n}(\boldsymbol{x}) - \alpha_{n}(\boldsymbol{y})| \end{align}\] by the triangle inequality for the \(\| \cdot \|_\infty\)-norm.³

Next, for fixed \(R=R_{k_1 \dots k_d}\) and \(\boldsymbol{x}, \boldsymbol{y} \in R = R_{k_1,\dots,k_d} \subseteq[0,1]^d\) we have \[\begin{align} \alpha_n(\boldsymbol{x}) -\alpha_n(\boldsymbol{y}) &= \alpha_n(x_1, \dots, x_d) \pm \alpha(y_1, x_2, \dots, x_d) \pm \alpha_n(y_1, y_2, x_3, \dots, x_d) \\&\pm \dots \pm \alpha_n(y_1, \dots, y_{d-1}, x_d) - \alpha_n(y_1, \dots, y_d) \\&= \sum_{j \in [d]} \alpha_n(y_{1:j-1},x_{j:d}) - \alpha_n(y_{1:j},x_{j+1:d}) \end{align}\] where \(x_{i:j}=(x_i, \dots, x_j)\) for \(i \le j\), and where \(x_{i:j}\) should be interpreted as ‘not being there’ for \(i>j\). In what follows, with a slight abuse of notation, write \(\alpha_n(A) = \sqrt n\{\mu_n(A)-\mu(A)\}\) for Borel sets \(A\). This defines a finite signed measure. Fix \(j \in [d]\). First consider the case \(x_j > y_j\). Then \[\begin{align} T_{nj}(\boldsymbol{x}, \boldsymbol{y}) :=&\;\alpha_n(y_{1:j-1},x_{j:d}) - \alpha_n(y_{1:j},x_{j+1:d}) \\=&\; \alpha_n(y_{1:j-1}, x_j, x_{j+1:d}) - \alpha_n(y_{1:j-1},y_j, x_{j+1:d}) \\=&\; \alpha_n(A_{j>,\boldsymbol{x}, \boldsymbol{y}}), \end{align}\] with \[A_{j>,\boldsymbol{x}, \boldsymbol{y}} := [0,y_1) \times \dots \times [0,y_{j-1}) \times [y_j, x_j) \times [0,x_{j+1}) \times \dots \times [0,x_{d}) \in \mathcal{A}_{j,k_j}.\] Likewise, if \(x_j < y_j\), we have \[T_{nj}(\boldsymbol{x}, \boldsymbol{y}) = - \alpha_n( A_{j<,\boldsymbol{x}, \boldsymbol{y}}),\] where \[A_{j<,\boldsymbol{x}, \boldsymbol{y}} := [0,y_1) \times \dots \times [0,y_{j-1}) \times [x_j, y_j) \times [0,x_{j+1}) \times \dots \times [0,x_{d}) \in \mathcal{A}_{j,k_j},\] and if \(x_j=y_j\), we have \(T_{nj}(\boldsymbol{x}, \boldsymbol{y}) =0\). Overall, \(|T_{nj}(\boldsymbol{x}, \boldsymbol{y}) | \le \sup_{A \in \mathcal{A}_{j,k_j}} | \alpha_n(A)|\), which implies \[\begin{align} \sup_{\boldsymbol{x}, \boldsymbol{y} \in R} |\alpha_{n}(\boldsymbol{x}) - \alpha_{n}(\boldsymbol{y})| \le \sum_{j \in [d]} \sup_{A \in \mathcal{A}_{j,k_j}} | \alpha_{n}(A) | \le d \max_{j \in [d]}\max_{k_j \in K_j} \sup_{A \in \mathcal{A}_{j,k_j}} | \alpha_{n}(A) |. \end{align}\] Hence, \[\begin{align} \omega_{\alpha_{n}}(\varepsilon, [\boldsymbol{a}, \boldsymbol{b}]) \le 2d \max_{j \in [d]} \max_{k_j \in K_j}\sup_{A\in \mathcal{A}_{j,k_j}} | \alpha_{n}(A) |, \end{align}\] and thus, with probability at least \(1-2 \| \boldsymbol{b} - \boldsymbol{a} \|_1 \tilde{\delta} /\varepsilon\), \[\omega_{\alpha_{n}}(\varepsilon, [\boldsymbol{a}, \boldsymbol{b}]) \le 2d \sqrt n\Big[ \frac{2}{3n} \log(1/{\tilde{\delta}}) + \sqrt{\frac{\varepsilon}{n}}\Big\{2 \sqrt{\log(1/{\tilde{\delta}})}+ 60\sqrt{2d} \Big\} \Big].\] With \(\tilde{\delta} = \varepsilon\delta / ( 2 \| \boldsymbol{b} - \boldsymbol{a} \|_1 )\), the upper bound can be rewritten as \[2d \Big[ \frac{2}{3\sqrt n} \log\Big( \frac{2\| \boldsymbol{b} - \boldsymbol{a} \|_1}{\varepsilon\delta}\Big) +\Big\{2 \sqrt{\varepsilon\log\Big( \frac{2\| \boldsymbol{b} - \boldsymbol{a} \|_1}{\varepsilon\delta}\Big)}+ 60\sqrt{2d\varepsilon} \Big\} \Big],\] which is the first statement of the lemma.

Regarding the second statement concerning \(\beta_{n}\), note that the events of interest in its definition satisfy \[\big\{ \exists j \in [d]: V_{ij}<u_j \big\} = \big\{ \forall j \in [d]: V_{ij} \ge u_j \big\}^c = \big\{ \forall j \in [d]: U_{ij} \le 1-u_j \big\}^c\] where \(U_{ij}=1-V_{ij}\). As a consequence, \[\beta_{n}(\boldsymbol{u}) = - \tilde{\alpha}_{n}^\circ(\boldsymbol{1}-\boldsymbol{u})\] where \[\tilde{\alpha}_{n}^\circ(\boldsymbol{u}) = \frac{1}{\sqrt n} \sum_{i=1}^n \big[ \boldsymbol{1}(\forall j \in [d]: U_{ij} \le u_j) - \mathbb{P}(\forall j \in [d]: U_{ij} \le u_j) \big].\] Hence, \(\omega_{\beta_{n}}(\varepsilon; [\boldsymbol{a}, \boldsymbol{b}]) = \omega_{\tilde{\alpha}_{n}^\circ}(\varepsilon; [\boldsymbol{1}- \boldsymbol{b}, \boldsymbol{1} - \boldsymbol{a}])\). Define \(\alpha_{n}^\circ\) as in 117 , but with \(\boldsymbol{V}_i\) replaced by \(\boldsymbol{U}_i\), and note that the derived probability bound holds for \(\alpha_n^\circ\). Further note that \(\tilde{\alpha}_n^\circ(\boldsymbol{u}) = \lim_{\eta\downarrow 0} \alpha_n^\circ(\boldsymbol{u} + \eta \boldsymbol{1})\) for any \(\boldsymbol{u} \in [0,1)^d\), so that \(\omega_{\tilde{\alpha}_{n}^\circ}(\varepsilon; (\boldsymbol{1}- \boldsymbol{b}, \boldsymbol{1} - \boldsymbol{a})) = \omega_{ \alpha_{n}^\circ}(\varepsilon; (\boldsymbol{1}- \boldsymbol{b}, \boldsymbol{1} - \boldsymbol{a}))\). Moreover, for fixed \(\boldsymbol{a}, \boldsymbol{b}\) we have with probability one \(\tilde{\alpha}_{n}^\circ(\boldsymbol{u}) = \alpha_{n}^\circ(\boldsymbol{u})\) for all \(\boldsymbol{u}\) on the boundary of the set \([\boldsymbol{1}- \boldsymbol{b}, \boldsymbol{1} - \boldsymbol{a}]\), so that in fact \(\omega_{\tilde{\alpha}_{n}^\circ}(\varepsilon; (\boldsymbol{1}- \boldsymbol{b}, \boldsymbol{1} - \boldsymbol{a})) = \omega_{ \alpha_{n}^\circ}(\varepsilon; [\boldsymbol{1}- \boldsymbol{b}, \boldsymbol{1} - \boldsymbol{a}])\) with probability one. The assertion for \(\omega_{\beta_{n}}\) now follows from the probability bound on \(\omega_{\alpha_{n}^\circ}\). ◻

Proof of Lemma 13. For \(t\in[0,1]\), let \(\boldsymbol{x}(t) = \boldsymbol{y} + t (\boldsymbol{z} - \boldsymbol{y})\) denote the line segment connecting \(\boldsymbol{y}\) and \(\boldsymbol{z}\). Note that \(x_j(t)>0\). Since \(\boldsymbol{x}(t) \in [\boldsymbol{y}, \boldsymbol{z}] \subseteq G_j\) by assumption, the function \(f(t) = \partial_{j} L(\boldsymbol{x}(t))\) is well-defined, continuous on \([0,1]\) and continuously differentiable on \((0,1)\) with derivative \[f'(t) = \sum_{\ell \in [d] : y_\ell>0 \text{ or } z_\ell>0 } (z_\ell-y_\ell) \partial_{j\ell} L( \boldsymbol{x}(t)).\] By the mean-value theorem, there exists some \(t^* \in (0,1)\) such that \[\partial_{j} L(\boldsymbol{z}) - \partial_{j} L(\boldsymbol{y}) = f(1) - f(0) = f'(t^*) = \sum_{\ell \in [d] : y_\ell>0 \text{ or } z_\ell>0 } (z_\ell-y_\ell) \partial_{j\ell} L( \boldsymbol{x}(t^*)).\] Hence, by Condition [cond:smoothness-good], \[\begin{align} |\partial_{j} L(\boldsymbol{y}) - \partial_{j} L(\boldsymbol{z})| &\le \max_{\ell \in [d] : y_\ell>0 \text{ or } z_\ell>0 } \sup_{t \in (0,1)} |\partial_{j\ell} L( \boldsymbol{x}(t))| \times \sum_{\ell \in [d] : y_\ell>0 \text{ or } z_\ell>0 } |y_\ell-z_\ell| \\&\le K_L\Big( \sup_{t \in (0,1)} \frac{1}{x_j(t)}\Big) \times \sum_{\ell \in [d]} |y_\ell - z_\ell| \end{align}\] Since the denominator in the supremum on the right-hand side is an affine linear function, the supremum must be attained at one of the boundary points 0 or 1, with \(1/x_j(0)=1/y_j\) and \(1/x_j(1) = 1/z_j\). As a consequence, \(\sup_{t \in (0,1)} 1/x_j(t) =\max(1/y_j, 1/z_j)\), which yields the assertion. ◻

Proof of Lemma 14. Let \(\Delta = \big\{\|\boldsymbol{X}- \boldsymbol{Y}\|_\infty \geq \delta\big\}\). Then, for any \(\boldsymbol{x} \in \mathbb{R}^d\), \[\begin{align} \mathbb{P}\big(\boldsymbol{X} \le \boldsymbol{x} \big) \ge \mathbb{P}\big(\boldsymbol{X} \le \boldsymbol{x}, \Delta^c\big) &\ge \mathbb{P}\big( \boldsymbol{Y} \le \boldsymbol{x} - \delta \boldsymbol{1}, \Delta^c\big) \\ &= \mathbb{P}\big( \boldsymbol{Y}\le \boldsymbol{x}-\delta\boldsymbol{1} \big) - \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x}-\delta \boldsymbol{1}, \Delta\big) \\& \ge \mathbb{P}\big(\boldsymbol{Y}\le \boldsymbol{x}-\delta\boldsymbol{1} \big) - \mathbb{P}(\Delta). \end{align}\] As a consequence, \[\begin{align} \mathbb{P}\big(\boldsymbol{Y} \leq \boldsymbol{x}\big) -\mathbb{P}\big(\boldsymbol{X} \leq \boldsymbol{x} \big) & \le \mathbb{P}\big(\boldsymbol{Y} \leq \boldsymbol{x}\big) - \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x} - \delta \boldsymbol{1} \big) + \mathbb{P}(\Delta) \\ &\le \mathbb{P}\big(\boldsymbol{Y} \leq \boldsymbol{x}+\delta \boldsymbol{1}\big) - \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x} - \delta \boldsymbol{1} \big) + \mathbb{P}(\Delta). \end{align}\] Likewise, \[\begin{align} \mathbb{P}\big(\boldsymbol{X} \le \boldsymbol{x}, \Delta^c\big) \le \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x} + \delta\boldsymbol{1}, \Delta^c \big) \le \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x} + \delta \boldsymbol{1}), \end{align}\] which implies \[\begin{align} \mathbb{P}\big(\boldsymbol{X} \leq \boldsymbol{x}\big) -\mathbb{P}\big(\boldsymbol{Y} \leq \boldsymbol{x} \big) &= \mathbb{P}\big(\boldsymbol{X} \leq \boldsymbol{x}, \Delta\big) + \mathbb{P}\big(\boldsymbol{X} \leq \boldsymbol{x}, \Delta^c\big) -\mathbb{P}\big(\boldsymbol{Y} \leq \boldsymbol{x} \big) \\&\le \mathbb{P}\big(\boldsymbol{X} \leq \boldsymbol{x}, \Delta\big) + \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x} + \delta\boldsymbol{1}) - \mathbb{P}(\boldsymbol{Y} \le \boldsymbol{x}) \\&\le\mathbb{P}(\Delta) + \mathbb{P}\big(\boldsymbol{Y} \leq \boldsymbol{x}+\delta \boldsymbol{1}\big) - \mathbb{P}\big(\boldsymbol{Y} \le \boldsymbol{x} - \delta \boldsymbol{1} \big). \end{align}\] This concludes the proof. ◻

Proof. This is Nazarov’s inequality, see [62]. ◻

Proof. This is Theorem 1 in [43], with their \(X_{i}\) equal to our \(\sqrt n \boldsymbol{Y}_{i,n}\). ◻

Proof. Since \(U\) is an open set, there exists an \(\varepsilon>0\) such that \(\mathcal{B}_\varepsilon(\boldsymbol{x}) \subseteq U\). For \(\boldsymbol{h}\in \mathbb{R}^d\) with \(\|\boldsymbol{h}\|\le \varepsilon\), define \(\varphi(\boldsymbol{h}) = f(\boldsymbol{x} + \boldsymbol{h}) - f(\boldsymbol{x}) - \langle \nabla f(\boldsymbol{x}) , \boldsymbol{h} \rangle.\) Convexity of \(f\) implies that \(\varphi\) is convex as well. Denote by \(\boldsymbol{e}_i\) the standard basis vectors of \(\mathbb{R}^d\) so that \(\boldsymbol{h}\in \mathbb{R}^d\) can be written as \(\boldsymbol{h} = h_1 \boldsymbol{e}_1 + \dots + h_d \boldsymbol{e}_d\). Then, \[{\varphi(\boldsymbol{h})} = {\varphi\Big(\frac{1}{d} \sum_{i=1}^d dh_i \boldsymbol{e}_i\Big)} \le \frac{1}{d} \sum_{i=1}^d \varphi(d h_i \boldsymbol{e}_i) \le \frac{1}{d} \sum_{i=1}^d |\varphi(d h_i \boldsymbol{e}_i)|\] and as a result, using \(\|\boldsymbol{h}\| \ge |h_i|\), \[\frac{\varphi(\boldsymbol{h})}{\|\boldsymbol{h}\|} \le \frac{1}{d} \sum_{i=1}^d \frac{|\varphi(d h_i \boldsymbol{e}_i)|}{\|\boldsymbol{h}\|} \le \frac{1}{d} \sum_{i=1}^d \frac{|\varphi(d h_i \boldsymbol{e}_i)|}{|h_i|}.\] Next, \(\varphi(\boldsymbol{0}) = 0\) together with the convexity of \(\varphi\) implies \(0=\varphi(\boldsymbol{h}/2 - \boldsymbol{h}/2)\le (\varphi(\boldsymbol{h}) + \varphi(-\boldsymbol{h}))/2\) and thus \(-\varphi(\boldsymbol{h}) \le \varphi(-\boldsymbol{h})\). It follows that \[-\frac{\varphi(\boldsymbol{h})}{\|\boldsymbol{h}\|} \le \frac{\varphi(-\boldsymbol{h})}{\|-\boldsymbol{h}\|} \le \frac{1}{d} \sum_{i=1}^d \frac{|\varphi(-d h_i \boldsymbol{e}_i)|}{|-h_i|}.\] All that remains to show is that \(|\varphi(d h_i e_i)|/{| dh_i|}\) converges to \(0\) for \(h_i \to 0\), for each \(i\in [d]\). We have \[\frac{|\varphi(d h_i e_i)|}{d|h_i|} =\Big| \frac{f(x + de_i h_i)-f(x) - \partial_i f(x) dh_i}{dh_i}\Big| = \Big| \frac{f(x + de_i h_i)-f(x)}{dh_i} - \partial_i f (x) \Big| \to 0\] for \(h_i \to 0\) by definition of the partial derivatives. ◻

Proof of Proposition 20. Throughout, we denote the cdf of \(\boldsymbol{Y}_n\) by \(F_n\), the cdf of \(\boldsymbol{Y}_n^{g}\) by \(F_n^{g}\) and the conditional cdf of \(\boldsymbol{Y}_n^*\) given the data by \(F_n^*\). Moreover, we define \[C_n^{g} = \min_{q \in [p]} p_{nq}^{g}, \quad \text{ with } \quad p_{nq}^{g} = 1 - F_{nq}^{g}(Y_{nq}^{g}).\]

We start by noting that, if \(F\) and \(G\) are cdfs on the real line satisfying \(\sup_{x \in \mathbb{R}} |F(x) - G(x) | \le \lambda\), then \[\label{eq:marginal-quantiles2} \forall \alpha \in (0,1) : \qquad F^-(\alpha - \lambda) \le G^-(\alpha) \le F^-(\alpha + \lambda);\tag{120}\] here, \(F^{-}(v) = \inf\{ u \in \mathbb{R}: F(u) \ge v\}\) for \(v \in (0,1]\) and \(F^-(v)=-\infty\) for \(v \le 0\) and \(F^-(v)=+\infty\) for \(v>1\); note the slight difference to the generalized inverse used in 31 .

We will show below that \[\begin{align} \tag{121} \sup_{t \in \mathbb{R}} \Big| \mathbb{P}(C_n \le t) - \mathbb{P}(C_n^{g} \le t) \Big| \le \delta + \lambda + p \lambda^*, \\ \tag{122} \text{On } \Omega_n^*: \qquad \sup_{t \in \mathbb{R}} \Big| \mathbb{P}(C_n^* \le t \mid \mathrm{data}) - \mathbb{P}( C_n^{g} \le t ) \Big| \le (p+1) \lambda^*. \end{align}\] Combined with 120 , the bound in 122 then implies that, on \(\Omega_n^*\), \[F_{C_n^{g}}^{-} \big(\alpha - (p+1)\lambda^*\big) \le q_{n,\alpha}^* \le F_{C_n^{g}}^{-} \big(\alpha + (p+1)\lambda^*\big),\] where \(F_{C_n^{g}}\) is the cdf of \(C_n^{g}\). As a consequence, by 121 \[\begin{align} \mathbb{P}(C_n \le q^*_{n,\alpha}) &\le \mathbb{P}\big(C_n \le F_{C_n^{g}}^{-} \big(\alpha + (p+1)\lambda^*\big) \big) + \mathbb{P}\big((\Omega_n^*)^c\big) \\&\le \mathbb{P}\big(C_n^{g} \le F_{C_n^{g}}^{-} \big(\alpha + (p+1)\lambda^*\big) \big) + 2\delta + \lambda + p \lambda^* \le \alpha + 2\delta + \lambda + (2p+1)\lambda^* . \end{align}\] A lower bound can be obtain by similar arguments, and this yields the claim.

It remains to prove 121 and 122 . We start with the former, fix \(t\in \mathbb{R}\) and note that \[\begin{align} \mathbb{P}(C_n \le t) = 1 - \mathbb{P}\Big( \forall q \in [p]: 1-F_{nq}^*(Y_{nq}) > t \Big) &= 1- \mathbb{P}\Big(\forall q \in [p]: Y_{nq} < [F_{nq}^*]^-(1-t) \Big). \end{align}\] Our assumptions imply that, on the event \(\Omega_n^*\), we have \(\max_{p \in [q]}\sup_{x \in \mathbb{R}} |F_{nq}^*(x) - F_{nq}^{g}(x)| \le \lambda^*,\) where \(F_{nq}^{g}\) is the cdf of \(Y_{nq}^{g}\). As a consequence, on the same event and by 120 , \[\begin{align} \label{eq:fn42-fng-quantiles} \forall q \in [p]: \qquad [F_{nq}^*]^-(1-t) \ge [F_{nq}^{g}]^-(1-t-\lambda^*) \end{align}\tag{123}\] Combining the previous inequalities and using that \(\mathbb{P}((\Omega_n^*)^c) \le \delta\), we obtain that \[\begin{align} \mathbb{P}(C_n \le t) &\le 1 - \mathbb{P}\Big(\forall q \in [p]: Y_{nq} < [F_{nq}^{g}]^-(1-t-\lambda^*)\Big) + \mathbb{P}((\Omega_n^*)^c) \\& \le 1- \mathbb{P}\Big(\forall q \in [p]: Y_{nq}^{g} < [F_{nq}^{g}]^-(1-t-\lambda^*)\Big) + \delta + \lambda \\&= 1-F_n^{g}\big( [F_{n1}^{g}]^-(1-t-\lambda^*), \dots, [F_{np}^{g}]^-(1-t-\lambda^*) \big) + \delta + \lambda \\&= 1 - \mathfrak C_n^{g}(1-t-\lambda^*, \dots, 1-t-\lambda^*) + \delta + \lambda \end{align}\] where \(\mathfrak C_n^{g}\) is the copula of \(\boldsymbol{Y}_n^{g}\) (considered as a function on \(\mathbb{R}^p\)) and where we have used ?? at the second inequality. Since copulas are Lipschitz-continuous, we obtain that \[\begin{align} \mathbb{P}(C_n \le t) &\le 1- \mathfrak C_n^{g}(1-t, \dots, 1-t) + \delta + \lambda + p \lambda^* \\&= \mathbb{P}( C_n^{g} \le t ) + \delta + \lambda + p \lambda^*, \end{align}\] where the last equality follows from a straightforward calculation similar to the ones done above. With the same arguments, \[\mathbb{P}(C_n \le t) \ge \mathbb{P}( C_n^{g} \le t ) - \delta - \lambda - p \lambda^*.\] The previous two equations imply 121 .

It remains to prove 122 . By the same calculations as before, and on the event \(\Omega_n^*\) and for each fixed \(t \in \mathbb{R}\), \[\begin{align} \mathbb{P}(C_n^* \le t \mid \mathrm{data}) &= 1 - \mathbb{P}\Big( \forall q \in [p]: Y_{nq}^* < [F_{nq}^*]^-(1-t) \, \Big| \, \mathrm{data}\Big) \\&\le 1 - \mathbb{P}\Big( \forall q \in [p]: Y_{nq}^{g} < [F_{nq}^*]^-(1-t) \, \Big| \, \mathrm{data}\Big) + \lambda^* \\ &= 1 - \mathbb{P}\Big( \forall q \in [p]: Y_{nq}^{g} \le [F_{nq}^*]^-(1-t) \, \Big| \, \mathrm{data}\Big) + \lambda^* \\&\le 1 - \mathbb{P}\Big( \forall q \in [p]: Y_{nq}^{g} \le [F_{nq}^{g}]^-(1-t-\lambda^*) \, \Big| \, \mathrm{data}\Big) + \lambda^* \\&= 1 - \mathfrak C_n^{g}(1-t-\lambda^*, \dots, 1-t-\lambda^*) + \lambda^* \\&\le 1- \mathfrak C_n^{g}(1-t, \dots, 1-t) + (p+1) \lambda^* \\&= \mathbb{P}( C_n^{g} \le t ) + (p+1) \lambda^*, \end{align}\] where we have used 123 at the second inequality. The respective lower bound can be deduced similarly, and 122 thus follows from \(\mathbb{P}(\Omega_n^*) \ge 1- \delta\). ◻