Proof. By Itô calculus (see ), \[\begin{align} d \exp(\lambda X_t) &= \lambda \exp(\lambda X_t) \,dX_t + \frac{\lambda^2}{2} \exp(\lambda X_t)(dX_t)^2 \\ &= \lambda \exp(\lambda X_t) \sqrt{2} \beta \,dW_t + \lambda \exp(\lambda X_t) 2 \beta^2 F_\mu(t) \partial_x \Phi(t,X_t)\,dt + 2 \beta^2 \frac{\lambda^2}{2} \exp(\lambda X_t)\,dt. \end{align}\] Taking expectations (which makes the \(dW_t\) term vanish) and then differentiating yields, \[\begin{align} \frac{d}{dt} \mathop{{}\mathbb{E}}[\exp(\lambda X_t)] &= 2 \beta^2 |\lambda| \mathop{{}\mathbb{E}}[\exp(\lambda X_t) F_\mu(t) \partial_x \Phi(t,X_t)] + \beta^2 \lambda^2 \mathop{{}\mathbb{E}}[\exp(\lambda X_t)] \\ &\leqslant\beta^2 (2 |\lambda| + \lambda^2) \mathop{{}\mathbb{E}}[\exp(\lambda X_t)]\, , \end{align}\] where we use the fact that \(X_t\) is finite almost surely and that \(|\partial_x \Phi(t,x)| \leqslant 1\) (by ). Then, by Grönwall’s inequality, \[\mathop{{}\mathbb{E}}[\exp(\lambda X_t)] \leqslant\exp(\beta^2(2|\lambda| + \lambda^2)(t-t_0)) \mathop{{}\mathbb{E}}[\exp(\lambda X_{t_0})] = \exp(\beta^2 (2|\lambda| +\lambda^2)(t-t_0)) \exp(\lambda x_0). \qedhere\] ◻

Proof of . Write \((t_0,x_0)\) for the point where we want to bound \(\partial_x \Phi\). Let \(X_t\) be as in . The upper point on \(\partial_x \Phi\) follows from the fact that \(\tanh(X_1) \leqslant 1\). For the lower bound, note that \[1 - \tanh(X_1) = \frac{2 \exp(-X_1)}{\exp(X_1) + \exp(-X_1)} \leqslant 2 \exp(-2X_1)\,.\] Hence, taking the expectation \[1 - \partial_x \Phi(t_0,x_0) \leqslant 2 \mathop{{}\mathbb{E}}[\exp(-2X_1)] \leqslant 2 \exp(8 \beta^2(1 - t_0)) \exp(-2x_0). \qedhere\] The upper bound \(\partial_{x,x} \Phi \leqslant 1\) is given in [39]. For the lower bound, note by that \[\partial_{x,x} \Phi(t_0,x_0) \geqslant\mathop{{}\mathbb{E}}[\mathop{\mathrm{sech}}(X_1)^2] \geqslant[\mathop{{}\mathbb{E}}\mathop{\mathrm{sech}}(X_1)]^2 \geqslant\frac{1}{\mathop{{}\mathbb{E}}[\cosh(X_1)]^2},\] where the last line follows because \[1 = \mathop{{}\mathbb{E}}[ \cosh(X_1)^{1/2} \mathop{\mathrm{sech}}(X_1)^{1/2} ] \leqslant(\mathop{{}\mathbb{E}}[\cosh(X_1)] \mathop{{}\mathbb{E}}[\mathop{\mathrm{sech}}(X_1)])^{1/2}.\] Note that by , \[\begin{align} \mathop{{}\mathbb{E}}[\cosh(X_1)] &= \frac{1}{2} \left( \mathop{{}\mathbb{E}}[e^{X_1}] + \mathop{{}\mathbb{E}}[e^{-X_1}] \right) \\ &\leqslant\frac{1}{2} \exp(3 \beta^2(1-t_0))[e^{x_0} + e^{-x_0}]. \end{align}\] Hence, \[\partial_{x,x} \Phi(t_0,x_0) \geqslant[\exp(3 \beta^2(1 - t_0)) \cosh(x_0)]^{-2},\] which is the desired lower bound. ◻

Proof. (1) Since \(|\partial_x \Phi| \leqslant 1\), the function \(\Phi(t,x)\) is \(1\)-Lipschitz in \(x\). Hence, if \(|y| > 1\), then \(xy\) grows faster than \(\Phi(t,x)\) as \(x \to \pm \infty\), and so the supremum will be infinite. For the case \(|y| \leqslant 1\), note that \[\int_0^\infty |1 - \partial_x \Phi(t,x)| \,dx < \infty\] by , and therefore \(\Phi(t,x) - x\) is bounded for \(x > 0\). Thus, by evenness of \(\Phi(t,\cdot)\), we have that \(|x| - \Phi(t,x)\) is bounded. In particular for \(y \in [-1,1]\), \(xy - \Phi(t,x)\) is bounded above, so \(\Lambda(t,y) < \infty\).

(2) By the strict convexity of \(\Phi\), the function \(\partial_x \Phi(t,\cdot)\) is strictly increasing. Also, by the limits at \(\pm \infty\) are \(\pm 1\). Hence, \(\partial_x \Phi(t,\cdot)\) defines a bijection \(\mathbb{R}\to (-1,1)\) which has a smooth inverse since \(\partial_{x,x} \Phi > 0\). Hence, for every \(y \in (-1,1)\), there is a unique \(x = [\partial_x \Phi(t,\cdot)]^{-1}(y)\) such that \(\partial_x \Phi(t,x) = y\). This relation implies that \(\partial_x[ xy - \Phi(t,x)] = 0\). Since the function \(xy - \Phi(t,x)\) is concave in \(x\), any critical point must be a maximizer. Writing \(x(y) = [\partial_x \Phi(t,\cdot)]^{-1}(y)\), so by the chain rule \[\partial_y \Lambda(t,y) = \frac{\partial}{\partial y} \left[ xy - \Phi(t,x) \right] = x + y \frac{dx}{dy} - \partial_x \Phi(t,x) \frac{dx}{dy} = x.\] (3) Therefore, since the maximizer is unique, integrating the previous equality gets \[\Lambda(t,y) = y [\partial_x \Phi(t,\cdot)]^{-1}(y) - \Phi(t, [\partial_x \Phi(t,\cdot)]^{-1}(y)).\] By the inverse function theorem, \([\partial_x \Phi(t,\cdot)]^{-1}\) is \(C^\infty\) since \(\Phi \in C^\infty\) by and \(\partial_{x,x}\Phi > 0\). It follows that \(\Lambda(t,\cdot)\) is a smooth function of \(y\) because the \(C^{\infty}\) property is closed under finite sums and products and compositions. ◻

Proof. (1) Fix \(y\), and let \(x = \partial_y \Lambda(t,y)\), so that \(y = \partial_x \Phi(t,x)\). Then we have \[1 - y = 1 - \partial_x \Phi(t,x) \leqslant 2 \exp(8\beta^2(1-t)) \exp(-2x).\] Thus, \[\log(1 - y) \leqslant\log(2) + 8 \beta^2(1 - t) - 2x.\] and \[2x \leqslant-\log(1 - y) + \log(2) + 8 \beta^2(1-t)\,,\] and so \[\partial_y \Lambda(t,y) \leqslant\frac{1}{2} \log \frac{2}{1-y} + 4 \beta^2(1-t).\] This is the bound we want in the case that \(y \geqslant 0\), and the bound follows in the negative case too since \(\partial_y \Lambda\) is an odd function of \(y\).

(2) Since \(\Lambda\) is an even function of \(y\), we have \[|\Lambda(t,y') - \Lambda(t,y)| = |\Lambda(t,|y'|) - \Lambda(t,|y|)|.\] Therefore, since also \(||y'| - |y|| \leqslant|y' - y|\), it suffices to prove the claim when \(y', y \geqslant 0\). Furthermore, assume without loss of generality that \(y' \geqslant y \geqslant 0\). Thus, \[\begin{align} 0 \leqslant\Lambda(t,y') - \Lambda(t,y) &= \int_y^{y'} \partial_y \Lambda(t,u)\,du \\ &\leqslant\int_y^{y'} \left( \frac{1}{2} \log \frac{2}{1-u} + 4 \beta^2 (1 - t) \right)\,du. \end{align}\] Now since right-hand side is an increasing function of \(u\), shifting the interval of integration from \([y,y']\) to \([1-(y'-y),1]\) can only increase the value. Hence, \[\begin{align} \Lambda(t,y') - \Lambda(t,y) &\leqslant\int_{1-(y'-y)}^1 \left( \frac{1}{2} \log \frac{2}{1-u} + 4 \beta^2 (1 - t) \right)\,du \\ &= \int_0^{(y'-y)/2} \log \frac{1}{v}\,dv + 4 \beta^2 (1 - t)(y'-y), \end{align}\] where we made the substitution \(1 - u = 2v\) in the integral of the first term. By integration by parts, \[\begin{align} \int_0^w \log \frac{1}{v}\,dv &= -\int_0^w \log v\,dv \\ &= \left[ -v \log v \right]_0^w + \int_0^w v(1/v)\,dv \\ &= -w \log w + w \\ &= w\left(\log \frac{1}{w} + 1 \right). \end{align}\] Thus, we get \[\Lambda(t,y') - \Lambda(t,y) \leqslant\frac{y' - y}{2} \left(\log \frac{2}{y'-y} + 1 + 8 \beta^2(1 - t) \right).\] This is the desired bound in the case where \(y' \geqslant y \geqslant 0\), which implies the general case.

Finally, to show the last claim, observe that \[\begin{align} \left(\log \frac{2}{|y'-y|} + 1 + 8 \beta^2(1-t) \right) &\leqslant\left(\log \frac{2}{|y'-y|} + 1 + 8 \beta^2 \right) \\ &= (1 + 8 \beta^2) \left( 1 + \frac{1}{1 + 8 \beta^2} \log \frac{2}{|y'-y|} \right) \\ &\leqslant(1 + 8 \beta^2) \exp \left( \frac{1}{1 + 8 \beta^2} \log \frac{2}{|y'-y|} \right) \\ &= (1 + 8 \beta^2) \left| \frac{y' - y}{2} \right|^{-\frac{1}{1 + 8\beta^2}}. \end{align}\] Therefore, \[\frac{|y' - y|}{2} \left(\log \frac{2}{|y'-y|} + 1 + 8 \beta^2(1 - t) \right) \leqslant(1 + 8 \beta^2) \left| \frac{y' - y}{2} \right|^{1 - \frac{1}{1 + 8\beta^2}},\] which is the desired estimate. ◻

Proof. (1) Note that since \(|x| - \Phi(t,x)\) is bounded, the function \(xy - \Phi(t,x) - \frac{\gamma}{2} x^2\) is bounded above by a quadratic with negative leading term and hence the supremum is finite.

(2) Note that \(x \mapsto \partial_x \Phi(t,x) + \gamma x\) is a smooth strictly increasing function with derivative bounded below, and therefore it defines a bijection \(\mathbb{R}\to \mathbb{R}\) with smooth inverse. The rest of the argument for (2), as well as (3) and (4), is the same as . ◻

Proof. We prove (1) and (2) together. From the proof of , we know that \(\partial_y \Lambda(t,\cdot) = [\partial_x \Phi(t,\cdot)]^{-1}\) is an increasing diffeomorphism from \((-1,1)\) to \(\mathbb{R}\), and hence so is \(\mathop{\mathrm{id}}+ \gamma \partial_y \Lambda(t, \cdot)\). Thus, there is a unique point \(y'\) with \(y' + \gamma \partial_y \Lambda(t,y') = y\). Direct computation shows that \(y'\) is a critical point of \(\Lambda(t,y') + \frac{1}{2 \gamma} (y' - y)^2\). Since that function is strictly convex on \([-1,1]\), the critical point must be the minimizer.

To solve for the minimum value, first write \(x = \partial_y \Lambda(t,y')\), so that \(y' = \partial_x \Phi(t,x)\), and thus \(y = y' + \gamma \partial_y \Lambda(t,y') = y' + \gamma x = \partial_x \Phi(t,x) + \gamma x\). Hence, \(x\) is the maximizer in the definition of \(\tilde{\Lambda}_{\gamma}(t,y)\) and also the maximizer in the definition of \(\Lambda(t,y')\), so that \[\begin{align} \tilde{\Lambda}_{\gamma}(t,y) &= xy - \Phi(t,x) - \frac{\gamma}{2} x^2 \\ &= x(y' + \gamma x) - \Phi(t,x) - \frac{\gamma}{2} x^2 \\ &= xy' - \Phi(t,x) + \frac{\gamma}{2} x^2 \\ &= \Lambda(t,y') + \frac{1}{2 \gamma} (y' - y)^2 \\ &= \inf_{y'' \in [-1,1]} \Lambda(t,y'') + \frac{1}{2 \gamma} (y'' - y)^2, \end{align}\] which finishes the proof of (1). Furthermore, since \(x\) is the maximizer for \(\tilde{\Lambda}_{\gamma}(t,y)\), we have \(\partial_y \tilde{\Lambda}_{\gamma}(t,y) = x = \partial_y \Lambda(t,y')\), and so \[y' = y - \gamma \partial_y \Lambda(t,y') = y - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,y),\] which finishes the proof of (2).

(3) The upper bound on \(\tilde{\Lambda}_{\gamma}\) follows by taking \(y' = y\) as a candidate for the infimum in (1). For the lower bound, note by that \[\Lambda(t,y') + \frac{1}{2 \gamma} (y' - y)^2 \geqslant\Lambda(t,y) - (1 + 8 \beta^2) \left( \frac{|y'-y|}{2} \right)^{1 - 1/(1 + 8 \beta^2)} + \frac{2}{\gamma} \left( \frac{|y'-y|}{2} \right)^2.\] Let us find the minimum value of the function \(f: [0,\infty) \to \mathbb{R}\) given by \[f(s) = -(1 + 8 \beta^2) s^{8\beta^2/(1 + 8 \beta^2)} + \frac{2}{\gamma} s^2.\] Note \[f'(s) = -8 \beta^2 s^{-1/(1 + 8 \beta^2)} + \frac{4}{\gamma} s,\] so critical points occur when \[\begin{align} 2 \beta^2 s^{-1/(1+8\beta^2)} &= \frac{1}{\gamma} s \\ 2 \beta^2 \gamma &= s^{1 + 1/(1 + 8 \beta^2)} = s^{(2 + 8\beta^2)/(1 + 8 \beta^2)} \\ s &= (2 \beta^2 \gamma)^{(1 + 8 \beta^2)/(2 + 8 \beta^2)}, \end{align}\] and here \[\begin{align} f(s) &= -(1 + 8 \beta^2) (2 \beta^2 \gamma)^{8 \beta^2/(2 + 8 \beta^2)} + \frac{2}{\gamma} (2 \beta^2 \gamma)^{2(1+8\beta^2)/(2 + 8 \beta^2)} \\ &= -(1 + 8 \beta^2) (2 \beta^2 \gamma)^{8 \beta^2/(2 + 8 \beta^2)} + \frac{2}{\gamma}(2 \beta^2 \gamma) (2 \beta^2 \gamma)^{8\beta^2/(2 + 8 \beta^2)} \\ &= -(1 + 4 \beta^2) (2 \beta^2 \gamma)^{4\beta^2/(1 + 4 \beta^2)}. \end{align}\] Since \(f(0) = 0\) and \(\lim_{s \to \infty} f(s) = \infty\), this is the minimum and hence gives a lower bound for \(f(|y'-y|/2)\), which proves the desired lower bound for \(\tilde{\Lambda}_{\gamma}(t,y)\). ◻

Proof. (1) Note that there is some interval \([-b,b]\) such that \(\partial_y \tilde{\Lambda}_{\gamma}(t, \cdot)[-a,a] \subseteq [-b,b]\) for all \(t \in [0,1]\). This follows in the case \(\gamma = 0\) from and in the case \(\gamma > 0\) from . Next, writing \(\tilde{\Phi}_{\gamma}(t,x) = \Phi(t,x) + \frac{\gamma}{2} x^2\), we see that \(\partial_{x,x} \tilde{\Phi}_{\gamma}\) is bounded below on \([-b,b]\) by some constant \(c\) using , and therefore, for \(x, x' \in [-b,b]\), we have \[c|x - x'| \leqslant|\partial_x \tilde{\Phi}_{\gamma}(t,x) - \partial_x \tilde{\Phi}_{\gamma}(t,x')|.\] Furthermore, from , since \(\partial_x^k \Phi\) is weakly differentiable in \(t\) and the derivative is bounded, we know that \(\partial_x^k \Phi\) is Lipschitz in \(t\), uniformly in \(y\).

Now fix \(y \in [-a,a]\) and let \(t, t' \in [0,1]\). Write \[\begin{align} 0 &= y - y \\ &= \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \partial_x \tilde{\Phi}_{\gamma}(t',\partial_y \tilde{\Lambda}_{\gamma}(t',y)) \\ &= \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t',y)) + \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t',y)) - \partial_x \tilde{\Phi}_{\gamma}(t', \partial_y \tilde{\Lambda}_{\gamma}(t',y)) \end{align}\] We have that \(\partial_x \tilde{\Phi}_{\gamma}(t,y)\) is Lipschitz in \(t\) uniformly in \(y\), and therefore, \(|\partial_x \tilde{\Phi}_{\gamma}(t,x) - \partial_x \tilde{\Phi}_{\gamma}(t',x)| \leqslant L\,|t - t'|\). Therefore \[\begin{align} c\,|\partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_y \tilde{\Lambda}_{\gamma}(t',y)| &\leqslant|\partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t',y))| \\ &= |\partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t',y)) - \partial_x \tilde{\Phi}_{\gamma}(t', \partial_y \tilde{\Lambda}_{\gamma}(t',y))| \\ &\leqslant L|t - t'|. \end{align}\] Hence, \(|\partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_y \tilde{\Lambda}_{\gamma}(t',y)| \leqslant(L/c) |t - t'|\) as desired.

Lipschitzness and boundedness of \(\partial_y \tilde{\Lambda}_{\gamma}(t,y)\) in \(t\) uniformly for \(y \in [-a,a]\) implies Lipschitzness of \(\tilde{\Lambda}_{\gamma}\) in \(t\) uniformly for \(y \in [-a,a]\) because \(\tilde{\Lambda}_{\gamma}(t,y) = y \partial_y \tilde{\Lambda}_{\gamma}(t,y) - \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y))\). To obtain Lipschitzness of the higher-order derivatives, we use the formula \[\partial_{y,y} \tilde{\Lambda}_{\gamma} = \frac{1}{\partial_{x,x} \tilde{\Phi}_{\gamma}(t,\partial_y \tilde{\Lambda}_{\gamma}(t,y))}\, ,\] which is obtained by the observation that \(x = \partial_y\tilde{\Lambda}_{\gamma}(t,y) = \left(\partial_x \tilde{\Phi}_{\gamma}(t,x)\right)^{-1}[y]\) is the unique maximizer, followed by an invocation of the inverse function theorem as \(\partial_x \tilde{\Phi}_{\gamma}(t,x)\) is continuously differentiable. Taking spatial derivatives of this formula expresses \(\partial_y^k \tilde{\Lambda}_{\gamma}(t,y)\) as a composition of spatial derivatives of \(\Phi\) (which are Lipschitz in \(t\) and \(x\)) with \(\partial_y \tilde{\Lambda}_{\gamma}(t,y)\) (which is Lipschitz in \(t\)), where the only term in the denominator is \(\partial_{x,x} \tilde{\Phi}_{\gamma}\) which we know is bounded below on \([-b,b]\). This implies Lipschitzness of the higher derivatives of \(\tilde{\Lambda}_{\gamma}\).

(2) Let \(t_0\) be a point of continuity of \(F_\mu\), so that \(\partial_x^k\Phi\) is differentiable there, and hence so is \(\partial_x^k \tilde{\Phi}_{\gamma}\) since \(\tilde{\Phi}_{\gamma}(t,x) = \Phi(t,x) + (\gamma/2) x^2\). Let \(y \in [-a,a]\) as in the previous argument. Recall \(\partial^k \Phi(t,x)\) is bounded for \(x \in [-b,b]\). Using the same relations as in the previous argument, write \[\begin{align} 0 &= \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t_0,y)) + \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t_0,y)) - \partial_x \tilde{\Phi}_{\gamma}(t_0, \partial_y \tilde{\Lambda}_{\gamma}(t_0,y)) \\ &= \partial_{x,x} \tilde{\Phi}_{\gamma}(t,\partial_y \tilde{\Lambda}_{\gamma}(t_0,y)) ( \partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_y \tilde{\Lambda}_{\gamma}(t_0,y)) + O(| \partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_y \tilde{\Lambda}_{\gamma}(t_0,y)|^2) \\ &\quad + \partial_t\partial_x \tilde{\Phi}_{\gamma}(t_0, \partial_y \tilde{\Lambda}_{\gamma}(t_0,y))(t- t_0) + o(t-t_0). \end{align}\] Since \(\partial_y \tilde{\Lambda}_{\gamma}\) is Lipschitz in \(t\) uniformly for \(y \in [-a,a]\), the term \(O(| \partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_y \tilde{\Lambda}_{\gamma}(t_0,y)|^2)\) is \(O(|t - t_0|^2)\), and therefore, \[\partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_y \tilde{\Lambda}_{\gamma}(t_0,y) = -\frac{1}{\partial_{x,x} \tilde{\Phi}_{\gamma}(t,\partial_y \tilde{\Lambda}_{\gamma}(t_0,y))} \partial_t \tilde{\Phi}_{\gamma}(t_0, \partial_y \tilde{\Lambda}_{\gamma}(t_0,y))(t - t_0) + o(t - t_0),\] which shows differentiability \[\label{eq:32partial32t32y32Lambda} \partial_t \partial_y \tilde{\Lambda}_{\gamma}(t_0,y) = -\frac{\partial_t \partial_x \tilde{\Phi}_{\gamma}(t_0, \partial_y \tilde{\Lambda}_{\gamma}(t_0,y))}{\partial_{x,x} \tilde{\Phi}_{\gamma}(t_0,\partial_y \tilde{\Lambda}_{\gamma}(t_0,y))}.\tag{12}\] For differentiability of \(\Lambda\) in \(t\) at the point \((t_0,y)\), we again express \(\Lambda\) in terms of \(\partial_y \Lambda\) and \(\Phi\). Similarly, the higher order derivatives of \(\Lambda\) are shown to be differentiable in \(t\) at \(t = t_0\) by expressing them as compositions of derivatives \(\partial_x^k \Phi\) (which are differentiable in \(t\) at \(t = t_0\) by (2)) and \(\partial_y \Lambda\) and using the chain rule.

(3) Let \(t\) be a point of continuity for \(F_\mu\). Note that \[\begin{align} \partial_t \tilde{\Phi}_{\gamma}(t,x) &= \partial_t \Phi(t,x) \\ &= -\beta^2 \left( \partial_{x,x} \Phi(t,x) + F_\mu(t) \partial_x \Phi(t,x)^2 \right) \\ &= -\beta^2 \left( \partial_{x,x} \tilde{\Phi}_{\gamma}(t,x) - \gamma + F_\mu(t) (\partial_x \tilde{\Phi}_{\gamma}(t,x) - \gamma x)^2 \right). \end{align}\] Now differentiate the relation \[\tilde{\Lambda}_{\gamma}(t,y) = y \partial_y \tilde{\Lambda}_{\gamma}(t,y) - \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y))\] in \(t\) to obtain \[\partial_t \tilde{\Lambda}_{\gamma}(t,y) = y \partial_t \partial_y \tilde{\Lambda}_{\gamma}(t,y) - \partial_t \tilde{\Phi}_{\gamma}(t,\partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \partial_x \tilde{\Phi}_{\gamma}(t,\partial_y \tilde{\Lambda}_{\gamma}(t,y)) \partial_t \partial_y\tilde{\Lambda}_{\gamma}(t,y).\] Since \(y = \partial_x \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y))\), the first and third terms on the right-hand side cancel and \[\begin{align} \partial_t \tilde{\Lambda}_{\gamma}(t,y) &= -\partial_t \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) \\ &= \beta^2 \left( \partial_{x,x} \tilde{\Phi}_{\gamma}(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \gamma + F_\mu(t)( \partial_x \tilde{\Phi}_{\gamma}(t,\partial_y \tilde{\Lambda}_{\gamma}(t,y)) - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,y))^2 \right) \\ &= \beta^2 \left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,y)} -\gamma + F_\mu(t)(y - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,y))^2 \right). \end{align}\]

(4) In the case \(\gamma = 0\), the initial condition arises due to \(\log \left(2\cosh\right)\) being the Fenchel-Legendre conjugate of the binary entropy function rescaled to the domain \([-1,1]\), see for example [45]. The case for \(\gamma > 0\) then follows by . ◻

Proof. Assuming the equation for \(X_t\), we have by Itô calculus that \[\begin{align} dY_t &= d \partial_x \Phi(t,X_t) \\ &= \partial_{x,x} \Phi(t,X_t) \,dX_t + \partial_{t,x} \Phi(t,X_t)\,dt + \frac{1}{2} \partial_{x,x,x} \Phi(t,X_t) (dX_t)^2 \\ &= \sqrt{2} \beta \partial_{x,x} \Phi(t,X_t)\,dW_t + 2 \beta^2 F_\mu(t)\partial_{x,x} \Phi(t,X_t) \partial_x \Phi(t,X_t)\,dt + \partial_{t,x} \Phi(t,X_t)\,dt + \beta^2 \partial_{x,x,x} \Phi(t,X_t)\,dt \\ &= \sqrt{2} \beta \partial_{x,x} \Phi(t,X_t)\,dW_t + \partial_x[\partial_t \Phi + \beta^2 \partial_{x,x} \Phi + \beta^2 F_{\mu}(t) (\partial_x \Phi)^2](t,X_t)\,dt \\ &= \frac{\sqrt{2} \beta}{\partial_{y,y}\Lambda(t,Y_t)}\,dW_t + 0. \end{align}\] Conversely, suppose that \(Y_t\) satisfies this equation and note \(X_t = \partial_y \Lambda(t,Y_t)\). Then by Itô calculus, \[\begin{align} dX_t &= d \partial_y\Lambda(t,Y_t) \\ &= \partial_{y,y} \Lambda(t,Y_t)\,dY_t + \partial_{t,y} \Lambda(t,Y_t)\,dt + \frac{1}{2} \partial_{y,y,y} \Lambda(t,Y_t) (dY_t)^2 \\ &= \sqrt{2} \beta \,dW_t + \partial_{t,y} \Lambda(t,Y_t)\,dt + \beta^2 \frac{\partial_{y,y,y} \Lambda(t,Y_t)}{\left(\partial_{y,y} \Lambda(t,Y_t)\right)^2}\,dt \\ &= \sqrt{2} \beta\,dW_t + \partial_y\left[\partial_t \Lambda - \frac{\beta^2}{\partial_{y,y} \Lambda} \right](t,Y_t)\,dt \\ &= \sqrt{2} \beta\,dW_t + \partial_y\left[\beta^2 F_{\mu}(t) y^2 \right]_{y=Y_t}\,dt \\ &= \sqrt{2} \beta\,dW_t + 2 \beta^2 F_{\mu}(t) Y_t\,dt \\ &= \sqrt{2} \beta\,dW_t + 2 \beta^2 F_{\mu}(t) \partial_x \Phi(t,X_t)\,dt. \qedhere \end{align}\] ◻

Proof. As in the proof of [44], we use the Ruelle Probability Cascade construction, which we include for the reader’s convenience in . By , there exist nonnegative random variables \((v_\alpha)_{\alpha \in \mathbb{N}^r}\) such that \(\sum_{\alpha \in \mathbb{N}^r} v_\alpha = 1\), and random variables \((Z_\alpha)_{\alpha \in \mathbb{N}^r}\) such that for all \(x\), \[\Phi(t_0,x) = \mathop{{}\mathbb{E}}\log \sum_{\alpha \in \mathbb{N}^r} 2 v_\alpha \cosh(x + Z_\alpha).\] Now let \[T(x) = \frac{d}{dx} \log \sum_{\alpha \in \mathbb{N}^r} 2 v_\alpha \cosh(x + Z_\alpha) = \frac{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \sinh(x + Z_\alpha)}{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)}.\] Since \(|\sinh| \leqslant|\cosh|\), we have \(|T(x)| \leqslant 1\). Also, by direct computation \[\begin{align} T'(x) &= \frac{d}{dx} \frac{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \sinh(x + Z_\alpha)}{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)} \\ &= \frac{\frac{d}{dx} [\sum_{\alpha \in \mathbb{N}^r} v_\alpha \sinh(x + Z_\alpha)]}{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)} - \frac{[\sum_{\alpha \in \mathbb{N}^r} v_\alpha \sinh(x + Z_\alpha)] \frac{d}{dx} [\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)]}{[\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)]^2} \\ &= \frac{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)}{\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)} - \frac{[\sum_{\alpha \in \mathbb{N}^r} v_\alpha \sinh(x + Z_\alpha)] [\sum_{\alpha \in \mathbb{N}^r} v_\alpha \sinh(x + Z_\alpha)]}{[\sum_{\alpha \in \mathbb{N}^r} v_\alpha \cosh(x + Z_\alpha)]^2} \\ &= 1 - T(x)^2. \end{align}\] Note that \(\log \sum_{\alpha \in \mathbb{N}^r} 2 v_\alpha \cosh(x + Z_\alpha)\) is integrable over the probability space. This random variable above is also \(1\)-Lipschitz in \(x\) since \(|T(x)| \leqslant 1\). Hence, we may apply the bounded convergence theorem to the difference quotients to conclude that \[\partial_x \Phi(t_0,x) = \frac{d}{dx} \mathop{{}\mathbb{E}}\log \sum_{\alpha \in \mathbb{N}^r} 2 v_\alpha \cosh(x + Z_\alpha) = \mathop{{}\mathbb{E}}[T(x)].\] By similar reasoning, for any polynomial \(F(\tau)\), since \((d/dx) F(T(x)) = F'(T(x)) (1 - T(x)^2)\) is bounded, we have \[\frac{d}{dx} \mathop{{}\mathbb{E}}[F(T(x))] = \mathop{{}\mathbb{E}}[F'(T(x))(1 - T(x)^2)].\] We apply this procedure inductively starting with \(F_1(\tau) = \tau\) and this results in claim (3). ◻

Proof. Fix \(t_0\) and assume first that \(\mu\) is atomic. Let \(T(x)\) be as in . Then \[\partial_x^j \Phi(t_0,x) = \mathop{{}\mathbb{E}}[F_j(T(x))] = \mathop{{}\mathbb{E}}[F_{j-1}'(T(x))(1 - T(x)^2)].\] Let \(C_j = \max_{\tau \in [-1,1]} |F_{j-1}'(\tau)|\). Then \[|\partial_x^j \Phi(t_0,x)| \leqslant\mathop{{}\mathbb{E}}[|F_{j-1}'(T(x))|(1 - T(x)^2)] \leqslant C_j \mathop{{}\mathbb{E}}[1 - T(x)^2] = C_j \partial_x^2 \Phi(t_0,x).\] In particular, since \(F_2(\tau) = 1 - \tau^2\) and \(F_2'(\tau) = -2 \tau\), we have \(C_3 = 2\). Moreover, \(F_3(\tau) = -2 \tau(1 - \tau^2)\) and \(F_3'(\tau) = -2(1 - 3 \tau^2)\). Clearly, \(-2 \leqslant 1 - 3 \tau^2 \leqslant 1\), and so \(C_4 = 4\).

It remains to extend the claim from atomic measures to general measures. By [5], if \(\mu_k\) is a sequence of measures with \(\mu_k \to \mu\) in the weak-\(*\) topology, then \(\Phi_{\mu_k} \to \Phi_\mu\) uniformly, and hence our estimates also hold for \(\mu\). ◻

Proof of . (1) Fix \(t\), and let \(x(y) = \partial_y \tilde{\Lambda}_{\gamma}(t,y)\), so that \(y = \partial_x \Phi(t, x(y)) + \gamma x(y)\). Recall also by the formula for derivatives of inverse function that \[\frac{dx}{dy} = \partial_{y,y} \tilde{\Lambda}_{\gamma}(t,y) = \frac{1}{\partial_{x,x} \Phi(t,x(y)) + \gamma}.\] Then because \(0 \leqslant\partial_{x,x} \Phi(t,x) \leqslant 1\) by , we get \[\frac{1}{1 + \gamma} \leqslant\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,y) \leqslant\frac{1}{\gamma},\] which is the asserted estimate.

(2) By the chain rule, \[\partial_{y,y,y} \tilde{\Lambda}_{\gamma}(t,y) = \partial_y \left( \frac{1}{\partial_{x,x} \Phi(t,x(y)) + \gamma} \right) = -\frac{\partial_{x,x,x} \Phi(t,x)}{(\partial_{x,x} \Phi(t,x) + \gamma)^2} \frac{dx}{dy} = -\frac{\partial_{x,x,x} \Phi(t,x)}{(\partial_{x,x} \Phi(t,x) + \gamma)^3}.\] Then by , \[\frac{|\partial_{x,x,x} \Phi(t,x)|}{(\partial_{x,x} \Phi(t,x) + \gamma)^3} \leqslant\frac{|\partial_{x,x,x} \Phi(t,x)|}{\gamma^2 \partial_{x,x} \Phi(t,x)} \leqslant\frac{2}{\gamma^2}.\]

(3) By the chain rule, \[\partial_y \left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma} (t,y)} \right) = \partial_y \left( \partial_{x,x} \Phi(t,x) + \gamma \right) = \partial_{x,x,x} \Phi(t,x) \frac{dx}{dy} = \frac{\partial_{x,x,x} \Phi(t,x)}{\partial_{x,x} \Phi(t,x) + \gamma}.\] By , this is bounded in absolute value by \(2\).

(4) Note that \[\begin{align} \partial_t \left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma} (t,y)} \right) &= \partial_t \left( \partial_{x,x} \Phi(t, \partial_y \tilde{\Lambda}_{\gamma}(t,y)) \right) \\ &= \partial_t \partial_{x,x} \Phi(t, x) + \partial_{x,x,x} \Phi(t,x) \partial_t \partial_y\tilde{\Lambda}_{\gamma}(t,y). \end{align}\] From 12 , \[\begin{align} \partial_t \partial_y \tilde{\Lambda}_{\gamma}(t,y) &= -\frac{\partial_t \partial_x \tilde{\Phi}_{\gamma}(t,x)}{\partial_{x,x} \tilde{\Phi}_{\gamma}(t,x)} \\ &= -\frac{\partial_t \partial_x \Phi(t,x)}{\partial_{x,x} \Phi(t,x) + \gamma}, \end{align}\] so that \[\label{eq:32formula32for32dt32dy32dy} \partial_t \left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma} (t,y)} \right) = \partial_t \partial_{x,x} \Phi(t, x) -\partial_{x,x,x} \Phi(t,x)\frac{\partial_t \partial_x \Phi(t,x)}{\partial_{x,x} \Phi(t,x) + \gamma};\tag{14}\] we now proceed to estimate both terms on the right-hand side. By the Parisi PDE , we have \[\begin{align} \partial_t \partial_x \Phi &= -\beta^2 \partial_x \left( \partial_{x,x} \Phi + F_\mu(t) \partial_x (\partial_x \Phi)^2 \right) \\ &= -\beta^2 \left( \partial_{x,x,x} \Phi + 2 F_\mu(t) \partial_x \Phi \partial_{x,x} \Phi \right) \\ \partial_t \partial_{x,x} \Phi &= -\beta^2 \partial_x \left( \partial_{x,x,x} \Phi + 2 F_\mu(t) \partial_x \Phi \partial_{x,x} \Phi \right) \\ &= -\beta^2 \left( \partial_{x,x,x,x} \Phi + 2 F_\mu(t) (\partial_{x,x} \Phi)^2 + 2 F_\mu(t) \partial_x \Phi \partial_{x,x,x} \Phi \right). \end{align}\] In particular, by , \[\begin{align} |\partial_{x,x,x} \Phi(t,x) \cdot \partial_t \partial_x \Phi(t, x)| &\leqslant\beta^2 |\partial_{x,x,x} \Phi|^2 + 2 \beta^2 F_\mu(t) |\partial_x \Phi\partial_{x,x,x} \Phi| \partial_{x,x} \Phi \label{eq:32estimate32for32dt32dx} \\ &\leqslant 4 \beta^2 (\partial_{x,x} \Phi)^2 + 4 \beta^2 (\partial_{x,x} \Phi)^2. \nonumber \end{align}\tag{15}\] and \[\begin{align} |\partial_t \partial_{x,x} \Phi(t, x)| &\leqslant\beta^2 |\partial_{x,x,x,x} \Phi| + 2 \beta^2 F_\mu(t) (\partial_{x,x} \Phi)^2 + 2 \beta^2 F_\mu(t) |\partial_x \Phi \partial_{x,x,x} \Phi| \label{eq:32estimate32for32dt32dx32dx} \\ &\leqslant 4 \beta^2 \partial_{x,x} \Phi + 2 \beta^2 (\partial_{x,x} \Phi)^2 + 4 \beta^2 |\partial_x \Phi| \partial_{x,x} \Phi \nonumber \\ &\leqslant 10 \beta^2. \nonumber \end{align}\tag{16}\] Substituting our estimates 16 for \(\partial_t \partial_{x,x} \Phi\) and 15 for \(\partial_t \partial_x \Phi\) into 14 yields \[\begin{align} \left| \partial_t \left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma} (t,y)} \right) \right| &\leqslant|\partial_t \partial_{x,x} \Phi| + \left| \frac{\partial_t \partial_x \Phi(t,x)}{\partial_{x,x} \Phi(t,x) + \gamma} \right| \\ &\leqslant 10 \beta^2 + \frac{8 \beta^2 (\partial_{x,x} \Phi(t,x))^2}{\partial_{x,x} \Phi(t,x) + \gamma} \\ &\leqslant 18 \beta^2. \qedhere \end{align}\] ◻

Proof. To estimate this value, we use  and  to simplify the expected value under the primal Auffinger-Chen dynamics , \[\begin{align} d \Lambda(t,Y_t) &= \partial_y \Lambda(t,Y_t) \,dY_t + \frac{1}{2} \partial_{y,y} \Lambda(t,Y_t) (dY_t)^2 + \partial_t \Lambda(t,Y_t)\,dt \\ &= \frac{\sqrt{2} \beta \partial_y \Lambda(t,Y_t)}{\partial_{y,y} \Lambda(t,Y_t)}\,dW_t + \left( \frac{\beta^2}{\partial_{y,y} \Lambda(t,Y_t)} + \partial_t \Lambda(t,Y_t) \right)\,dt \\ &= \frac{\sqrt{2} \beta \partial_y \Lambda(t,Y_t)}{\partial_{y,y} \Lambda(t,Y_t)}\,dW_t + \left( \frac{2 \beta^2}{\partial_{y,y} \Lambda(t,Y_t)} + \beta^2 F_\mu(t) Y_t^2 \right)\,dt\,. \end{align}\] Hence, after taking expectations and using , \[\begin{align} \frac{d}{dt} \mathop{{}\mathbb{E}}\Lambda(t,Y_t) &= 2 \beta^2 \mathop{{}\mathbb{E}}\frac{1}{\partial_{y,y} \Lambda(t,Y_t)} + \beta^2 F_\mu(t) \mathop{{}\mathbb{E}}[Y_t^2] \\ &= \beta^2\left( 2 \int_t^1 F_\mu(s)\,ds + t F_\mu(t) \right). \end{align}\] We obtain the statement asserted in the lemma by integrating this and noting that \(Y_0 = 0\). ◻

Proof. First, let \(Z_t^\gamma = Y_t + \gamma \partial_y \Lambda(t,Y_t)\). Proposition 12 (2) implies that \(\mathop{\mathrm{id}}- \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,\cdot)\) is the inverse function of \(\mathop{\mathrm{id}}+ \gamma \partial_y \Lambda(t,\cdot)\). Thus we have \(Y_t = Z_t^\gamma - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)\). Moreover, the function \(\mathop{\mathrm{id}}- \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,\cdot)\) is \(1\)-Lipschitz since its derivative is \(1 - \gamma \partial_{y,y} \tilde{\Lambda}_{\gamma}(t,\cdot)\), which is bounded below by \(1 - \gamma / \gamma = 0\) and bounded above by \(1 - \gamma / (1 + \gamma) \leqslant 1\), using Proposition 15 (1). Hence, we have \[\mathop{{}\mathbb{E}}|Y_t^\gamma - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma) - Y_t|^2 \leqslant\mathop{{}\mathbb{E}}|Y_t^\gamma - (Y_t + \gamma \partial_y \Lambda(t,Y_t))|^2,\] which is the first inequality in 19 . It remains to estimate \(\mathop{{}\mathbb{E}}|Y_t^\gamma - (Y_t + \gamma \partial_y \Lambda(t,Y_t))|^2\).

It follows from Itô calculus that \[\begin{align} dZ_t^\gamma &= dY_t + \gamma \partial_{y,y}\Lambda(t,Y_t)\,dY_t + \frac{1}{2} \gamma \partial_{y,y,y} \Lambda(t,Y_t) (dY_t)^2 + \gamma \partial_{t,y} \Lambda(t,Y_t)\,dt \\ &= \sqrt{2} \beta \left( \frac{1}{\partial_{y,y} \Lambda(t,Y_t)} + \gamma \right)\,dW_t + \gamma \left( \beta^2 \frac{\partial_{y,y,y} \Lambda(t,Y_t)}{\partial_{y,y} \Lambda(t,Y_t)^2} + \partial_{t,y} \Lambda(t,Y_t) \right)\,dt \\ &= \frac{\sqrt{2}\beta}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)}\,dW_t + 2 \gamma \beta^2 F_\mu(t) Y_t\,dt. \end{align}\] Here we simplified the \(dt\) term using the same computations as converting from the dual to primal PDE. To simplify the \(dW_t\) time, we used the following fact: Recall from the proof of that \(\partial_y \tilde{\Lambda}_{\gamma} = \partial_y \Lambda \circ (\mathop{\mathrm{id}}+ \gamma \partial_y \Lambda)^{-1}\), and hence \[\partial_{y,y} \tilde{\Lambda}_{\gamma} = \frac{\partial_{y,y} \Lambda}{1 + \gamma \partial_{y,y} \Lambda} \circ (\mathop{\mathrm{id}}+ \gamma \partial_y \Lambda)^{-1},\] and hence \[\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}} \circ (\mathop{\mathrm{id}}+ \gamma \partial_y \Lambda) = \frac{1}{\partial_{y,y} \Lambda} + \gamma.\] Thus in particular, \[\label{eq:32relating32two32drivers} \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)} = \frac{1}{\partial_{y,y} \Lambda(t,Y_t)} + \gamma.\tag{21}\] Finally, we remark that some further justification is required for the Itô computation above since \(\partial_{y,y} \Lambda\) blows up at \(\pm 1\). One can proceed rigorously by expressing \(Z_t^\gamma\) in terms of the dual process \(X_t\) as \[Z_t^\gamma = \partial_x \tilde{\Phi}_{\gamma}(t,X_t) = \partial_x \Phi(t,X_t) + \gamma X_t.\] Computing \(dZ_t^\gamma\) by the Itô formula is justified by [39] and results in the same expression as above, as in the proof of .

With \(dZ_t^\gamma\) in hand, we now compute \[\begin{align} d[(Z_t^\gamma - Y_t^\gamma)^2] &= 2(Z_t^\gamma - Y_t^\gamma)(dZ_t^\gamma - dY_t^\gamma) + (dZ_t^\gamma - dY_t^\gamma)^2 \\ &= 2(Z_t^\gamma - Y_t^\gamma) \left( \frac{\sqrt{2} \beta}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)} - \frac{\sqrt{2} \beta}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma)} \right)\,dW_t + 2(Z_t^\gamma - Y_t^\gamma) \cdot 2 \gamma \beta^2 F_\mu(t) Y_t\,dt \\ & \quad + 2 \beta^2 \left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)} - \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma)} \right)^2\,dt. \end{align}\] Taking the expectation and using the fact that \(1/ \partial_{y,y} \tilde{\Lambda}_{\gamma}\) is \(2\)-Lipschitz by (3), we get that \[\begin{align} \frac{d}{dt} \mathop{{}\mathbb{E}}[(Z_t^\gamma - Y_t^\gamma)^2] &= 4 \beta^2 \mathop{{}\mathbb{E}}[(Z_t^\gamma - Y_t^\gamma) \cdot \gamma F_\mu(t) Y_t] + 2 \beta^2 \mathop{{}\mathbb{E}}\left( \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)} - \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma)} \right)^2 \\ &\leqslant 2 \beta^2 \mathop{{}\mathbb{E}}[(Z_t^\gamma - Y_t^\gamma)^2] + 2 \beta^2 \gamma^2 \mathop{{}\mathbb{E}}[Y_t^2] + 8 \beta^2 \mathop{{}\mathbb{E}}[(Z_t^\gamma - Y_t^\gamma)^2] \\ &\leqslant 10 \beta^2 \mathop{{}\mathbb{E}}[(Z_t^\gamma - Y_t^\gamma)^2] + 2 \beta^2 \gamma^2. \end{align}\] since \(\mathop{{}\mathbb{E}}[Y_t^2] \leqslant 1\). Therefore, since \(Z_0^\gamma = 0 = Y_0^\gamma\), Grönwall’s inequality implies that \[\label{eq:32Y32minus32Z32estimate} \mathop{{}\mathbb{E}}[(Z_t^\gamma - Y_t^\gamma)^2] \leqslant\int_0^t 2 \beta^2 \gamma^2 e^{10\beta^2 (t-s)} \,ds = \frac{1}{5} \gamma^2 (e^{10\beta^2 t} - 1).\tag{22}\] This proves the second inequality in 19 . For the last claim 20 , note that \(\partial_y\Lambda(t,Y_t) = X_t\) and \(|\partial_x\Phi(x,t)| \leqslant 1\) by . Moreover, \[\begin{align} d(X_t^2) &= 2 X_t \,dX_t + (dX_t)^2 \\ &= 2X_t \left( \sqrt{2} \beta\,dW_t + 2 \beta^2 F_\mu(t) \partial_x \Phi(t,X_t)\,dt \right) + 2 \beta^2 \,dt \\ &\leqslant 2\sqrt{2}\beta X_t \,dW_t + 2 \beta^2 (2 + X_t^2) \,dt, \end{align}\] where we have used the inequality \(2 X_t \leqslant 1 + X_t^2\). Hence, \[\frac{d}{dt} \mathop{{}\mathbb{E}}[X_t^2] \leqslant 2 \beta^2(2 + \mathop{{}\mathbb{E}}[X_t^2]) \leqslant 10 \beta^2 (2/5 + \mathop{{}\mathbb{E}}[X_t^2])\] Therefore, since \(X_0 = 0\), we have \[\mathop{{}\mathbb{E}}[X_t^2] \leqslant\frac{2}{5} (e^{10 \beta^2 t} - 1).\] Hence, by this inequality and , \[\begin{align} \left\lVert{Y_t^\gamma - Y_t}\right\rVert_{L^2} &\leqslant\left\lVert{Y_t^\gamma - Y_t - \gamma X_t}\right\rVert_{L^2} + \gamma \left\lVert{X_t}\right\rVert_{L^2} \\ &\leqslant\frac{\gamma}{\sqrt{5}} (e^{10 \beta^2 t} - 1)^{1/2} + \frac{\sqrt{2}}{\sqrt{5}} \gamma (e^{10 \beta^2 t} - 1)^{1/2} \\ &\leqslant\sqrt{2} \gamma (e^{10 \beta^2 t} - 1)^{1/2}, \end{align}\] which proves the asserted estimate 20 . ◻

Proof. Consider \(Z_t^\gamma\) as in the previous proof. From 21 , we observe that \[\label{eq:32compare32L232norm32for32Zt32and32Yt} \left\lVert{ \frac{1}{\partial_{y,y} \Lambda(t,Y_t)} }\right\rVert_{L^2} \leqslant\left\lVert{ \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)} }\right\rVert_{L^2} \leqslant\left\lVert{ \frac{1}{\partial_{y,y} \Lambda(t,Y_t)} }\right\rVert_{L^2} + \gamma.\tag{25}\] Using the fact that \(1 / \partial_{y,y} \tilde{\Lambda}_{\gamma}\) is \(2\)-Lipschitz ( (3)), together with 22 , \[\left\lVert{\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)} - \frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma)}}\right\rVert_{L^2} \leqslant 2 \left\lVert{Z_t^\gamma - Y_t^\gamma}\right\rVert_{L^2} \leqslant 2 \cdot 5^{-1/2} \gamma (e^{10 \beta^2 t} - 1)^{1/2} \leqslant e^{5 \beta^2 t} \gamma.\] Hence, \[\label{eq:32compare32L232norm32for32Zt32and32Yt322} \left\lVert{\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)}}\right\rVert_{L^2} - e^{5 \beta^2 t} \gamma \leqslant\left\lVert{\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma)}}\right\rVert_{L^2} \leqslant\left\lVert{\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Z_t^\gamma)}}\right\rVert_{L^2} + e^{5 \beta^2 t} \gamma.\tag{26}\] By 25 and 26 , we have \[\left\lVert{\frac{1}{\partial_{y,y} \Lambda(t,Y_t)} }\right\rVert_{L^2} - e^{5 \beta^2 t}\gamma \leqslant\left\lVert{\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(t,Y_t^\gamma)}}\right\rVert_{L^2} \leqslant\left\lVert{\frac{1}{\partial_{y,y} \Lambda(t,Y_t)} }\right\rVert_{L^2} + ( 1 + e^{5 \beta^2 t}) \gamma\] We finally substitute in the fact that under fRSB \(\left\lVert{\frac{1}{\partial_{y,y} \Lambda(t,Y_t)}}\right\rVert_{L^2} = \frac{1}{\sqrt{2} \beta}\) () to obtain the first asserted estimate 23 .

To prove the second estimate 24 , observe that by the Itô isometry, \[\left\lVert{Y_t^\gamma}\right\rVert_{L^2}^2 = \int_0^t 2 \beta^2 \left\lVert{\frac{1}{\partial_{y,y} \tilde{\Lambda}_{\gamma}(s,Y_s^\gamma)}}\right\rVert_{L^2}^2\,ds.\] Using 23 , the latter can be upper-bounded by \[\int_0^t 2\beta^2\left(\frac{1}{\sqrt{2}\beta} + \left(1 + e^{5\beta^2 t}\gamma\right)\right)^2\,ds \leqslant t\left(1 + \sqrt{2} \beta (1 + e^{5 \beta^2 t})\gamma\right)^2,\] and the lower bound is proved similarly. ◻

Proof. Invoke with \(J = \sqrt{\kappa}\log\left (\frac{m\kappa\log\kappa}{\varepsilon'\sqrt{\lambda_{\min}}}\right)\) and with \(m = (\log \kappa + 3)\log(1/(\varepsilon'\lambda_{\min}\left|v\right|_2))\). ◻

Proof. The runtime bottleneck will be sampling \(u_k\) approximating \(h_k \sim \mathcal{N}(0, Q_k^2)\), which may be characterized as \(h_k := L_kg_k\) for \(g_k \in \mathbb{R}^n\) a vector with i.i.d. standard Gaussian entries, where \[\begin{align} L_k := \sqrt{2\beta \tilde{b}n^{\delta}}\;\Pi_{\sigma_k^{\perp}}\left(\tilde{b}^2 + (\tilde{a} - \nabla^2\operatorname{obj}(k\eta,\sigma_k))^2\right)^{-1/2} \end{align}\] so that \(L_kL_k^{\mathsf{T}} = Q_k^2\). To apply , we will note that since \(\nabla^2\mathop{\mathrm{obj}}(k\eta, \sigma_k) = \beta(A + A^{\mathsf{T}}) - \nabla^2V(k\eta, \sigma_k)\), matrix-vector multiplication by the matrix \(K_k := \tilde{b}^2 + (\tilde{a} - \nabla^2\mathop{\mathrm{obj}}(k\eta, \sigma_k))^2\) can be computed in \(O(n^2)\) time. Furthermore, the spectrum of \(K_k\) is lower-bounded by \(\tilde{b}^2\) and it is upper-bounded by \(\tilde{b}^2 + (|\tilde{a}| + \left\lVert \nabla^2\mathop{\mathrm{obj}}(k\eta, \sigma_k) \right\rVert_{_\mathsf{op}})^2 \leqslant\exp(O(\beta^2))\) since \(\left\lVert \nabla^2\mathop{\mathrm{obj}}(k\eta, \sigma_k) \right\rVert_{_\mathsf{op}} \leqslant 3\beta + \gamma^{-1} \leqslant 3\beta + e^{O(\beta^2)}\).

Therefore, by , there is a procedure that computes a vector \(u_k\in \mathbb{R}^n\) satisfying \(|u_k - h_k|_2 \leqslant\sqrt{2\beta\tilde{b} n^\delta}\,\varepsilon' |K_k^{-1/2}g_k|_2\) where \(h_k \sim \mathcal{N}(0, Q_k^2)\) and \(|K_k^{-1/2}g_k|_2\) is upper-bounded by \(O_{\varepsilon}(n)\) with overwhelming probability in time \(O(\tilde{b}^{-1}e^{O(\beta^2)}n^{2}\operatorname{polylog}(n, 1/\varepsilon'))\). By , \(\tilde{b} \geqslant\Omega(b^3/\beta^2) \geqslant\Omega(\beta n^{-3\delta})\) when \(b = \beta n^{-\delta}\). We may take \(\varepsilon'\) to be \(O(n^{-102})\) to obtain \(|u_k - h_k|_2 \leqslant O(n^{-100})\) with high probability while incurring only an additional logarithmic dependence on \(n\) in runtime.

The value of \(a\) in can be found by binary search in \(O(n\operatorname{polylog}(n,1/\varepsilon))\) time, since the step of computing the trace of \(D^{-2}\) is linear time, with all matrices involved being diagonal. Similarly, to find \(\tilde{a}\) and \(\tilde{b}\), it is only necessary to compute the traces and inverses of diagonal matrices.

The error between \(u_k\) and \(h_k\) accumulates linearly over the iterates in the analysis of \(H(\sigma)\) and its rounding \(H(\sigma^*)\) in . ◻

Proof. Note that \[\mathop{{}\mathbb{E}}[\sigma_j^*] = \frac{1+\sigma_j}{2} - \frac{1 - \sigma_j}{2} = \sigma_j.\] In other words, \(\mathop{{}\mathbb{E}}[\sigma^*] = \sigma\). Let \(\tilde{\sigma} = \sigma^* - \mathop{{}\mathbb{E}}\sigma^* = \sigma^* - \sigma\). Write \[\angles{\sigma^*, M \sigma^*} = \angles{\tilde{\sigma}, M \tilde{\sigma}} + 2 \angles{\tilde{\sigma}, M \sigma} + \angles{\sigma, M \sigma}.\] Since each component of \(\tilde{\sigma}\) is independent, zero-mean, and has sub-Gaussian norm at most 1, by the Hanson-Wright inequality [49] there is a constant \(c > 0\) such that \[\mathop{{}\mathbb{P}}\left(\angles{\tilde{\sigma}, M \tilde{\sigma}} - \mathop{{}\mathbb{E}}[\angles{\tilde{\sigma}, M \tilde{\sigma}}] < -t_{\mathrm{HW}}\right) \leqslant\exp\left(-c\min\left( \frac{t_{\mathrm{HW}}^2}{n\left\lVert{M}\right\rVert_2^2},\frac{t_{\mathrm{HW}}}{\left\lVert{M}\right\rVert}\right)\right)\,.\] So take \(t_{\mathrm{HW}} = \max(\left\lVert{M}\right\rVert_2n^{1-\alpha}/\sqrt{c},\left\lVert{M}\right\rVert n^{1-2\alpha}/c)\). Then we have

\[\mathop{{}\mathbb{E}}[\angles{\tilde{\sigma}, M \tilde{\sigma}}] = \angles{M, \mathop{{}\mathbb{E}}[\tilde{\sigma}\tilde{\sigma}^{\mathsf{T}}]} = \sum_{i \in [n]} M_{i,i}(1-\sigma_i^2) \geqslant-\sum_{i \in [n]}|M_{i,i}|\,.\]

Furthermore, \[\angles{\tilde{\sigma}, M \sigma} = \sum_{j=1}^n (M\sigma)_j \tilde{\sigma}_j.\] The random variables \((M \sigma)_j \tilde{\sigma}_j\) are independent with mean zero and each one is supported in \(\{(M \sigma)_j(-1 + \sigma_j), (M \sigma)_j(1 + \sigma_j)\}\). Therefore, by Hoeffding’s inequality, for \(t > 0\), \[\mathop{{}\mathbb{P}}(\angles{\tilde{\sigma}, M \sigma} \leqslant-t) \leqslant\exp\left( -\frac{t^2}{\sum_{j=1}^n (2(M \sigma)_j)^2} \right) = \exp\left(- \frac{t^2}{4 |M\sigma|_2^2} \right) \leqslant\exp\left(- \frac{t^2}{4 n\left\lVert{M}\right\rVert^2} \right),\] since \(|\sigma|_2^2 \leqslant n\). Now take \(t = 2 \left\lVert{M}\right\rVert n^{1-\alpha}\). Thus, \(\angles{\tilde{\sigma}, M \sigma} \geqslant-t\) implies that \[\angles{\sigma^*, M \sigma^*} \geqslant\angles{\sigma, M \sigma} - 4 \left\lVert{M}\right\rVert n^{1-\alpha} - \max\left(\left\lVert{M}\right\rVert_2n^{1-\alpha}/\sqrt{c},\left\lVert{M}\right\rVert n^{1-2\alpha}/c\right) -\sum_{i \in [n]}|M_{i,i}|,\] and the probability of violating this bound simplifies to \(\exp(-n^{1 - 2 \alpha})\). ◻

Proof. (1) For vectors \(\xi \in H\), we have \[|\angles{\xi, (z - A) \xi}| \geqslant|\mathop{\mathrm{Im}}\angles {\xi, (z - A) \xi}| = |\mathop{\mathrm{Im}}z|\, |\xi|^2.\] Thus, \(|(z - A) \xi| \geqslant|\mathop{\mathrm{Im}}z| \,|\xi|\), which implies that \(z - A\) is injective and has closed range. Meanwhile, the same inequality holds for the adjoint \(\overline{z} I - A\), and hence \(z I - A\) is surjective, hence invertible. Then \(|(z - A) \xi| \geqslant|\mathop{\mathrm{Im}}z| \,|\xi|\) implies that \(\left\lVert{(z - A)^{-1}}\right\rVert \leqslant 1 / |\mathop{\mathrm{Im}}z|\).

(2) By the resolvent identity and the non-commutative Hölder inequality, \[\begin{align} \left\lVert{(z - A)^{-1} - (z - B)^{-1}}\right\rVert_p &= \left\lVert{(z - A)^{-1}(A - B)(z - B)^{-1}}\right\rVert_p \\ &\leqslant\left\lVert{(z - A)^{-1}}\right\rVert \left\lVert{A - B}\right\rVert_p \left\lVert{(z - B)^{-1}}\right\rVert \\ &\leqslant\frac{1}{|\mathop{\mathrm{Im}}z|^2} \left\lVert{A - B}\right\rVert_p. \end{align}\]

(3) By the resolvent identity, \[\begin{align} &(z - A(t+\epsilon))^{-1} - (z - A(t))^{-1} = \\ &(z - A(t+\epsilon))^{-1}(z - A(t))(z - A(t))^{-1} - (z - A(t+\epsilon))^{-1} (z - A(t+\epsilon))(z - A(t))^{-1} \\ &= (z - A(t+\epsilon))^{-1}(A(t+\epsilon) - A(t))(z - A(t))^{-1}. \end{align}\] Dividing by \(\epsilon\) and taking the limit as \(\epsilon \to 0\) completes the proof. ◻

Proof. Recall that the \(R\)-transform of a semicircular element of variance \(2 \beta^2\) is \(r_{\sqrt{2} \beta S}(z) = 2 \beta^2 z\) (see e.g.[51]). By definition of the \(R\)-transform and by free independence, we have for \(z\) in a neighborhood of \(0\) that \[\begin{align} z &= g_{\sqrt{2} \beta S - D}(1/z + r_{\sqrt{2} \beta S - D}(z)) \\ &= g_{\sqrt{2} \beta S - D}(1/z + r_{-D}(z) + r_{\sqrt{2} \beta S}(z)) \\ &= g_{\sqrt{2} \beta S - D}( g_{-D}^{-1}(z) + 2 \beta^2 z). \end{align}\] Now we substitute \(w = g_{-D}^{-1}(z)\) (so \(w\) will range in a neighborhood of \(\infty\)) and obtain \[g_{-D}(w) = g_{\sqrt{2} \beta S - D}(w + 2 \beta^2 g_{-D}(w)).\] Then substituting \(w = f(z)\) for \(z\) large, we obtain \[g_{\sqrt{2} \beta S - D}(z) = g_{-D}(f(z)) = g_{\sqrt{2} \beta S - D}(f(z) + 2 \beta^2 g_{-D}(f(z))).\] Since \(g_{\sqrt{2} \beta S - D}\) is injective on a neighborhood of \(\infty\), this implies \[z = f(z) + 2 \beta^2 g_{-D}(f(z))\] holds in a neighborhood of infinity. But note that both sides are analytic on the upper half-plane and hence the identity extends to the entire upper half-plane by the identity theorem. Thus, \(f\) is injective and its inverse is given on its domain by \(z + 2 \beta^2 g_{-D}(z)\).

Next, let us prove the claim about the domain of \(f^{-1}\). First, if \(z \in \mathop{\mathrm{dom}}(f^{-1})\), then \(z + 2 \beta^2 g_{-D}(z)\) being equal to \(f^{-1}(z)\) must have positive imaginary part. Second, suppose that \(z + 2 \beta^2 g_{-D}(z)\) has positive imaginary part. Note that \[\begin{align} \mathop{\mathrm{Im}}[z + 2 \beta^2 g_{-D}(z)] &= \mathop{\mathrm{Im}}(z) + 2 \beta^2 \mathop{\mathrm{Im}}\operatorname{tr}[(z + D)^{-1}] \\ &= \mathop{\mathrm{Im}}(z) + 2 \beta^2 \operatorname{tr}( \mathop{\mathrm{Im}}((i \mathop{\mathrm{Im}}z + \mathop{\mathrm{Re}}z + D)^{-1})) \\ &= \mathop{\mathrm{Im}}(z) - 2 \beta^2 (\mathop{\mathrm{Im}}z) \operatorname{tr}( ((\mathop{\mathrm{Im}}z)^2 + (\mathop{\mathrm{Re}}z + D)^2)^{-1} ) \\ &= \mathop{\mathrm{Im}}(z) \left( 1 - 2 \beta^2 \operatorname{tr}( ((\mathop{\mathrm{Im}}z)^2 + (\mathop{\mathrm{Re}}z + D)^2)^{-1} )\right). \end{align}\] Hence, \(z + 2 \beta^2 g_{-D}(z)\) has positive imaginary part if and only if \(2 \beta^2 \operatorname{tr}( ((\mathop{\mathrm{Im}}z)^2 + (\mathop{\mathrm{Re}}z + D)^2)^{-1} ) < 1\). Furthermore, \(2 \beta^2 \operatorname{tr}( ((\mathop{\mathrm{Im}}z)^2 + (\mathop{\mathrm{Re}}z + D)^2)^{-1} )\) is a decreasing function of \(\mathop{\mathrm{Im}}z\), when \(\mathop{\mathrm{Re}}z\) is fixed. Hence, \(2 \beta^2 \operatorname{tr}( ((\mathop{\mathrm{Im}}z)^2 + (\mathop{\mathrm{Re}}z + D)^2)^{-1} ) < 1\) holds for \(z\), it also holds for \(z + iy\) for all \(y > 0\). Now for sufficiently large \(y\), we have that \(z + iy \in \mathop{\mathrm{dom}}(f^{-1})\) and so \[f(z + iy + 2 \beta^2 g_{-D}(z + iy)) = z + iy.\] Now \(z + iy + 2 \beta^2 g_{-D}(z + iy)\) has positive imaginary part and hence is in the domain of \(f\) for all \(y \geqslant 0\). Thus, by analytic continuation the above identity extends to all \(y \geqslant 0\), and in particular, \(f(z + 2 \beta^2 g_{-D}(z)) = z\), so that \(z \in \mathop{\mathrm{dom}}(f^{-1})\). ◻

Proof. (1) Note that \(2 \beta^2 \operatorname{tr}_n((a + D)^{-2})\) is a strictly decreasing function of \(a\) on \([-\min \mathop{\mathrm{Spec}}(D),\infty)\). As \(a \to \infty\), it converges to zero and as \(a \to -\min \mathop{\mathrm{Spec}}(D)\), it converges to \(+\infty\). Hence, by the intermediate value theorem and strict monotonicity, there is a unique point where it equals \(1\).

(2) Let \(h(z) = z + 2\beta^2 g_{-D}(z) = z + 2\beta^2 \operatorname{tr}((z+D)^{-1})\), which is the inverse function for \(f\) on the appropriate domain. Our first goal is to show that \(h\) is invertible on \((a,\infty) + i\mathbb{R}\) and in particular this region is contained in the image of \(f\). Suppose that \(x \in (a,\infty)\) and \(y \in \mathbb{R}\). We claim first that \(\mathop{\mathrm{Im}}h(x+iy)\) has the same sign as \(y\). Note that \[\mathop{\mathrm{Im}}h(x+iy) = y - 2\beta^2\operatorname{tr}(y(y^2 + (x+D)^2)^{-1}) = y\left(1 - 2\beta^2\operatorname{tr}((y^2 + (x + D)^2)^{-1})\right).\] Now \(2\beta^2\operatorname{tr}((y^2 + (x+D)^2)^{-1}) \leqslant 2\beta^2\operatorname{tr}((x+D)^{-2}) < 2\beta^2\operatorname{tr}((a+D)^{-2}) = 1\), and so \(\mathop{\mathrm{Im}}h(x+iy)\) is \(y\) times a strictly positive number, and so has the same sign as \(y\). By , we see that if \(y > 0\), then \(x+iy \in \mathop{\mathrm{dom}}(f)\). Similarly, if \(y < 0\), then \(x+iy\) is in the domain of the mirror version of \(f\) in the lower half-plane. In particular, \(h\) is injective on these two regions. We note the identity that \(h'(z) = 1 - 2\beta^2\operatorname{tr}((z+D)^{-2})\), and hence since \(\operatorname{tr}\mathop{\mathrm{Re}}X \leqslant\operatorname{tr}|X|\) for all \(X\), \[\begin{align} \mathop{\mathrm{Re}}h'(x+iy) &\geqslant 1 - 2 \beta^2 \operatorname{tr}(|(x + iy +D)^{-2}|) \\ &= 1 - 2 \beta^2 \operatorname{tr}((y^2 + (x+D)^2)^{-1}) \\ &> 1 - 2 \beta^2 \operatorname{tr}((a+D)^{-2}) \\ &= 0, \end{align}\] In particular, we see that \(h\) is strictly increasing on \((a,\infty)\) and thus injective there as well. Overall \(h\) is injective on \((a,\infty) + i\mathbb{R}\).

Also, since \(a > \min \mathop{\mathrm{Spec}}(D)\), we know \(g_{-D}\) is analytic on \((a,\infty) + i\mathbb{R}\). Therefore, \(g_{-D} \circ h^{-1}\) is analytic on \(h((a,\infty) + i\mathbb{R})\). Furthermore, we know that \(h^{-1}\) agrees with \(f\) on \(((a,\infty) + i\mathbb{R}) \cap \mathbb{H}\), so that \(g_{-D} \circ h^{-1}\) agrees with \(g_{-D} \circ f = g_{\sqrt{2}\beta S - D}\) on this region; the symmetrical statement holds for the lower half-plane. Hence, \(g_{\sqrt{2} \beta S - D}\) is analytic on \(h((a,\infty) + i\mathbb{R})\), and it follows by that \(h((a,\infty) + i\mathbb{R})\) is in the complement of the spectrum of \(\sqrt{2} \beta S - D\). In particular, \(h((a,\infty)) = (a + 2\beta^2 g_{-D}(a),\infty)\) is in the complement of the spectrum, and so \[\max \mathop{\mathrm{Spec}}(\sqrt{2} \beta S - D) \leqslant a + 2\beta^2 g_{-D}(a) = a + 2\beta^2\operatorname{tr}((a+D)^{-1}).\]

To see the reverse inequality, consider the behavior of \(h\) near the point \(a\). By construction, \(h'(a) = 0\) and \(h''(a) = 4 \beta^2 \operatorname{tr}((a+D)^{-3}) > 0\). Thus, \[h(z) - h(a) = \frac{1}{2}h''(a)(z - a)^2 + O((z-a)^3),\] hence, \(h(z) - h(a) = (z-a)^2 p(z)\) for some nonzero analytic function \(p(z)\), and in particular, \(h(z) - h(a) = q(z)^2\) for some analytic function \(q\) with \(q(a) = 0\) and \(q'(a) > 0\). Now \(q^{-1}\) is defined on some neighborhood \((a-\delta,a+\delta) + i(-\delta,\delta)\). We have \(h^{-1}(z) = q^{-1}(\sqrt{z - h(a)})\) on \((a,a+\delta) + i(-\delta,\delta)\), where \(\sqrt{z - h(a)}\) is defined by taking the slit in the negative real direction. This implies also that \[g_{\sqrt{2} \beta S - D}(z) = g_{-D}\left(q^{-1}\left(\sqrt{z - h(a)}\right) \right).\] Since \(g_{-D}\) is analytic on a neighborhood of \(a\), this identity extends to a neighborhood of \(h(a)\) say \((h(a)-\delta',h(a)+\delta') + i (-\delta',\delta')\). Our choice of square root \(\sqrt{z - h(a)}\) cuts the plane along \((-\infty,h(a)]\), mapping the “upper side” onto the positive imaginary axis and the “lower side” onto the negative imaginary axis. Since \((q^{-1})'(0) > 0\) and \[g_{-D}'(a) = \frac{d}{dz} \Bigr|_{z=a} \operatorname{tr}_n((z + D)^{-1}) = -\operatorname{tr}_n((a+D)^{-2}) = -\frac{1}{2 \beta^2} < 0,\] we get that for \(x \in (h(a)-\delta',h(a))\), we have \[\lim_{y \to 0^+} g_{\sqrt{2} \beta S - D}(x+iy) = \lim_{y \to 0^+} g_{-D}\left(q^{-1}\left(\sqrt{x+iy - h(a)}\right)\right) > 0,\] and the behavior as \(y \to 0^-\) is described by the complex conjugate. Thus, \(g_{\sqrt{2} \beta S - D}\) cannot extend to be analytic in a neighborhood of \(h(a)\) since the values from the upper side and the lower side disagree on \((h(a)-\delta,h(a))\). Therefore by , \(h(a) \in \mathop{\mathrm{Spec}}(\sqrt{2} \beta S - D)\). ◻

Proof. (1) Note that using and resolvent identities, \[\begin{align} \tilde{b} &= b + 2 \beta^2 \mathop{\mathrm{Im}}\operatorname{tr}_n[(ib + D)^{-1}] \\ &= b - 2 \beta^2 b \operatorname{tr}_n[(b^2 + D^2)^{-1}] \\ &= b(1 - 2 \beta^2 \operatorname{tr}_n[D^{-2}] - 2 \beta^2 \operatorname{tr}_n[(b^2 + D^2)^{-1} - D^{-2}]) \\ &= b(0 + 2 \beta^2 b^2 \operatorname{tr}_n[(b^2 + D^2)^{-1}D^{-2}]) \\ &= 2 \beta^2 b^3 \operatorname{tr}_n[(b^2 + D^2)^{-1}D^{-2}]). \end{align}\] Then we note that \[\operatorname{tr}_n[(b^2 + D^2)^{-1}D^{-2}]) \leqslant\operatorname{tr}_n[D^{-4}],\] and \[2 \beta^2 \operatorname{tr}_n(D^{-4}) \leqslant 2 \beta^2 \operatorname{tr}_n(D^{-2}) \left\lVert{D^{-1}}\right\rVert^2 = \left\lVert{D^{-1}}\right\rVert^2\] which implies the upper bounds from (1).

On the other hand, by Jensen’s inequality applied to the convex function \(t \mapsto (b^2t + 1)^{-1} t^2\) on \([0,\infty)\), \[\begin{align} \operatorname{tr}_n[(b^2 + D^2)^{-1}D^{-2}]) &= \operatorname{tr}_n[(b^2 D^{-2}+1)^{-1} D^{-4}] \\ &\geqslant(b^2 \operatorname{tr}_n(D^{-2}) + 1)^{-1} \operatorname{tr}_n(D^{-2})^2 \\ &= (b^2/2\beta^2 + 1)^{-1} \frac{1}{4 \beta^4} \\ &= (b^2 + 2 \beta^2)^{-1} (2 \beta^2)^{-1}. \end{align}\] Therefore, \[\tilde{b} \geqslant b^3(b^2 + 2 \beta^2)^{-1} \geqslant b^3(\beta^2 + 2 \beta^2)^{-1} = \frac{b^3}{3 \beta^2},\] which gives the lower bound from (1).

(2) Observe that \[-2 \beta^2 \mathop{\mathrm{Im}}g_{-D}(ib) = b - \tilde{b} \geqslant b - 2 \beta^2 b^3 \operatorname{tr}_n(D^{-4}),\] and again note \(2 \beta^2 \operatorname{tr}_n(D^{-4}) \leqslant\left\lVert{D^{-1}}\right\rVert^2\). ◻

Proof. First, consider the case where \(f = g\) and the inner product space is real. Fix an orthonormal basis \(w_1\), …, \(w_d\) for \(W\). Apply the previous lemma to \(\langle f(A),w_j \rangle\) for each \(j\), and then sum up the results over the basis. In the complex case, we apply the previous lemma to the real and imaginary parts of \(\angles{f(A), w_j}\).

In the case where \(f \ne g\), the left-hand side can be estimated using the Cauchy-Schwarz inequality, and then we apply the case of \(f = g\) proved above. ◻

Proof. Here we use a classic \(\epsilon\)-net argument. Let \(\Omega = \{D': \operatorname{tr}(D'(D')^*) = 1\}\) be a set of diagonal matrices and let \(\Omega_0\) be a maximal \(1/2\)-separated subset of \(\Omega\) with respect to \(\left\lVert{\cdot}\right\rVert_2\). Thus, every element of \(\Omega\) is within a distance of \(1/2\) from some element of \(\Omega_0\). The balls of radius \(1/2\) centered at points in \(\Omega_0\) are disjoint and contained in the ball of radius \(3/2\) and hence \(|\Omega_0| \leqslant 3^{2n}\) since we used complex entries. Thus, for any diagonal matrix \(B\), we have \[\left\lVert{B}\right\rVert_2 = \sup_{D' \in \Omega} \mathop{\mathrm{Re}}\angles{B,D'} \leqslant\max_{D' \in \Omega_0} |\mathop{\mathrm{Re}}\operatorname{tr}(BD')| + \frac{1}{2} \left\lVert{B}\right\rVert_2,\] so that \[\left\lVert{B}\right\rVert_2 \leqslant 2 \max_{D' \in \Omega_0} |\mathop{\mathrm{Re}}\operatorname{tr}(BD')|.\] If \(B\) is not necessarily diagonal, then \(\operatorname{tr}(BD') = \operatorname{tr}(E_{\mathcal{D}_n}[B]D')\) and hence \[\left\lVert{E_{\mathcal{D}_n}[B]}\right\rVert_2 \leqslant 2 \max_{D' \in \Omega_0} |\mathop{\mathrm{Re}}\operatorname{tr}(BD')|.\] We apply this with \(B = (\tilde{z} - 2\beta A_{\mathop{\mathrm{sym}}} + D)^{-1} - \mathop{{}\mathbb{E}}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]\), so \[\begin{align} \bigl \lVert E_{\mathcal{D}_n}[(\tilde{z} &- 2\beta A_{\mathop{\mathrm{sym}}} + D)^{-1} - \mathop{{}\mathbb{E}}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]] \bigr \rVert_2 \\ &\leqslant 2 \max_{D' \in \Omega_0} \bigl|\mathop{\mathrm{Re}}\operatorname{tr}_n[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}D' - \mathop{{}\mathbb{E}}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]D'] \bigr|. \end{align}\] Moreover, for every such \(D'\), we have that \(\mathop{\mathrm{Re}}\operatorname{tr}_n[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} D']\) is \(2 \beta / |\mathop{\mathrm{Im}}\tilde{z}|^2\)-Lipschitz as a function of \(A\) with respect to \(\left\lVert{\cdot}\right\rVert_2\). Therefore, by the concentration inequality of , \[\mathop{{}\mathbb{P}}\left( |(\mathop{\mathrm{id}}- \mathop{{}\mathbb{E}})\mathop{\mathrm{Re}}\operatorname{tr}_n[(\tilde{z} - 2\beta A_{\mathop{\mathrm{sym}}} + D)^{-1} D']| \geqslant\frac{2 \beta}{n^{8\delta} |\mathop{\mathrm{Im}}\tilde{z}|^2} \right) \leqslant 2 e^{-n^{2 - 16\delta} / 2}.\] By taking a union bound, we can arrange that \(|(\mathop{\mathrm{id}}- \mathop{{}\mathbb{E}})\operatorname{tr}_n[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} D']| \leqslant\frac{2 \beta}{n^{8\delta} |\mathop{\mathrm{Im}}\tilde{z}|^2}\) for all \(D' \in \Omega_0\) with probability at least \(1 - 2\cdot 3^{2n} e^{-n^{2-16\delta} / 2}\). ◻

Proof. We want to view \(E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]\) as a function of \(D^{-1}\) in the sphere of radius \(1/(\sqrt{2} \beta)\) with respect to \(\left\lVert{\cdot}\right\rVert_2\), show that it is Lipschitz, and hence deduce an estimate for all \(D^{-1}\) from an estimate on a sufficiently dense subset.

For the Lipschitz estimate, fix two nonnegative diagonal matrices \(D\) and \(D'\) with \(\operatorname{tr}(D^{-2}) = \operatorname{tr}((D')^{-2}) = 1/(2\beta^2)\), and let \(\tilde{z} = ib + 2 \beta^2 \operatorname{tr}((ib + D)^{-1})\) and \(\tilde{z}' = ib + 2 \beta^2 \operatorname{tr}((ib + D')^{-1})\). Note by the resolvent identity that \[\begin{align} (ib + D)^{-1} - (ib + D')^{-1} &= (ib + D)^{-1} (D' - D) (ib + D')^{-1} \\ &= (ib + D)^{-1} D (D^{-1} - (D')^{-1}) D'(ib + D')^{-1} \\ &= (1 - ib(ib + D)^{-1}) (D^{-1} - (D')^{-1}) (1 - ib(ib + D')^{-1}). \end{align}\] Furthermore, \(\left\lVert{(ib + D)^{-1}}\right\rVert \leqslant 1/b\) so that \(\left\lVert{1 - ib(ib + D)^{-1}}\right\rVert \leqslant 2\), and similarly for \(D'\). Hence, by the non-commutative Hölder’s inequality, \[\left\lVert{(ib + D)^{-1} - (ib + D')^{-1}}\right\rVert_2 \leqslant\left\lVert{1 - ib(ib + D)^{-1}}\right\rVert \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2 \left\lVert{1 - ib(ib + D')^{-1}}\right\rVert \leqslant 4 \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2.\] Thus, \[|\tilde{z} - \tilde{z}'| \leqslant 2 \beta^2 \left\lVert{(ib + D)^{-1} - (ib + D')^{-1}}\right\rVert_2 \leqslant 8 \beta^2 \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2.\] Another application of the resolvent identity yields that \[\begin{align} (\tilde{z} - 2\beta A_{\mathop{\mathrm{sym}}} + D)^{-1} & - (\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1} \\ &= (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(\tilde{z}' - \tilde{z} + D' - D)(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1} \tag{27} \\ &= (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(\tilde{z}' - \tilde{z})(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1} \tag{28} \\ &\quad + (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(D' - D)(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1} \tag{29} \end{align}\] Now by and (1), \[\left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}}\right\rVert \leqslant\frac{1}{\tilde{b}} \leqslant\frac{3 \beta^2}{b^3},\] and similarly for \(D'\). Hence, 28 can be bounded by \[\begin{align} \left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(\tilde{z}' - \tilde{z})(\tilde{z}' - 2\beta A_{\mathop{\mathrm{sym}}} + D')^{-1}}\right\rVert_2 &\leqslant\frac{M_1}{\beta^4 b^6} |\tilde{z} - \tilde{z}'| \\ &\leqslant\frac{M_2 \beta^6}{b^6} \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2 \\ &= M_2 n^{6\delta} \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2, \end{align}\] where \(M_1\) and \(M_2\) are universal constants. Then to estimate 29 , we write \[\begin{gather} \label{eq:32resolvent32to32estimate322} (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(D' - D)(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1} = (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}D(D^{-1} - (D')^{-1})D'(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1}. \end{gather}\tag{30}\] We write \[\begin{align} (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}D &= 1 - (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}}) \nonumber \\ &= 1 - (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}i\tilde{b} - (\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} (\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}}). \label{eq:32split32of32terms32to32estimate32resolvent} \end{align}\tag{31}\] As before, \[\left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} \tilde{b}}\right\rVert \leqslant 1.\] Meanwhile, \[\tilde{a} = \mathop{\mathrm{Re}}2\beta^2\operatorname{tr}((ib + D)^{-1}) = 2\beta^2\operatorname{tr}(D(b^2 + D^2)^{-1}) \leqslant 2\beta^2\operatorname{tr}(D^{-1}) \leqslant 2\beta^2\operatorname{tr}(D^{-2})^{1/2} = \sqrt{2}\beta.\] Furthermore, recall by , we have that \(\left\lVert{2A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant 3\) with probability \(1 - M_3 \exp(-M_4 n)\), and so \(\left\lVert{\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant(\sqrt{2} + 3) \beta\). Thus, \[\left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}})}\right\rVert \leqslant\frac{3 \beta^2}{b^3} (\sqrt{2} + 3) \beta \leqslant M_5 n^{3\delta}.\] Substituting all these estimates into 31 yields \[\left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}D}\right\rVert \leqslant M_6 n^{3 \delta},\] and of course a similar estimate holds for \(D'(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1}\). Plugging these back into 30 , we get \[\left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}(D' - D)(\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1}}\right\rVert_2 \leqslant M_6^2 n^{6\delta} \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2.\] Therefore, overall \[\left\lVert{(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} - (\tilde{z}' - 2 \beta A_{\mathop{\mathrm{sym}}} + D')^{-1}}\right\rVert_2 \leqslant M_7 n^{6 \delta} \left\lVert{D^{-1} - (D')^{-1}}\right\rVert_2.\] Finally, since \(E_{\mathcal{D}_n}\) is contractive in the \(2\)-norm, the map \[D \mapsto E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]\] is \(M_7 n^{6\delta}\)-Lipschitz in \(D^{-1}\) on the event \(\{\left\lVert{2A_{\mathop{\mathrm{sym}}}}\right\rVert\leqslant 3\}\). Hence, since this event does not depend on \(D\), the centered truncated map \[D^{-1}\mapsto E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]\mathbb{1}_{\{\left\lVert{2A_{\mathop{\mathrm{sym}}}}\right\rVert\leqslant 3\}}-\mathop{{}\mathbb{E}}[E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]\mathbb{1}_{\{\left\lVert{2A_{\mathop{\mathrm{sym}}}}\right\rVert\leqslant 3\}}]\] is \(2M_7 n^{6\delta}\)-Lipschitz. Moreover, uniformly in \(D\), \[\left\lVert{E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]}\right\rVert_2 \leqslant\frac{1}{\tilde{b}}\leqslant\frac{3\beta^2}{b^3}=3 \beta^2 \beta^{-3} n^{3\delta},\] and therefore \[\label{eq:A-diagonal-expected-truncation-ok} \left\lVert{\mathop{{}\mathbb{E}}E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]-\mathop{{}\mathbb{E}}[E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]\mathbb{1}_{\{\left\lVert{2A_{\mathop{\mathrm{sym}}}}\right\rVert\leqslant 3\}}]}\right\rVert_2 \leqslant 3M_3\beta^{-1} n^{3\delta}e^{-M_4 n}.\tag{32}\]

Next, fix a maximal subset \(\Omega_0\) of \(\Omega = \{D^{-1}: 2 \beta^2 \operatorname{tr}(D^{-2}) = 1\}\) that is \(\beta n^{-8\delta}\)-separated with respect to \(\left\lVert{\cdot}\right\rVert_2\). Thus, every element of \(\Omega\) is within a distance of \(\beta/n^{8\delta}\) from \(\Omega_0\). The balls centered at the elements of \(\Omega_0\) of radius \(\beta/(2n^{8\delta})\) are disjoint and contained in the ball of radius \(3\beta /2\) centered at \(0\), and so \(|\Omega_0| \leqslant(3 n^{8 \delta})^n\).

By the union bound and , with probability at least \[1 - 2(3n^{8\delta})^n 3^{2n} e^{-n^{2-16\delta}/2},\] over the Gaussian matrix, we have for all \(D^{-1} \in \Omega_0\), \[\left\lVert{E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} - \mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]]}\right\rVert_2 \leqslant\frac{4 \beta}{n^{8\delta} |\mathop{\mathrm{Im}}\tilde{z}|^2} \leqslant M_9 \beta^{-1} n^{-2\delta}\] where again we have applied (1) to estimate \(1 / |\mathop{\mathrm{Im}}\tilde{z}|^2 \leqslant 9 \beta^4 / (\beta n^{-\delta})^6\). By our choice of \(\Omega_0\), every \(D^{-1} \in \Omega\) is within a distance of \(\beta / n^{8\delta}\) of some \((D')^{-1} \in \Omega_0\). Therefore, when \(\left\lVert{2A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant 3\), by , \[\begin{align} &\left\lVert{E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]-\mathop{{}\mathbb{E}}E_{\mathcal{D}_n}\big[(\tilde{z}-2\beta A_{\mathop{\mathrm{sym}}}+D)^{-1}\big]}\right\rVert_2 \\ &\qquad\qquad - \left\lVert{ E_{\mathcal{D}_n}\big[(\tilde{z}'-2\beta A_{\mathop{\mathrm{sym}}}+D')^{-1}\big]-\mathop{{}\mathbb{E}}E_{\mathcal{D}_n}\big[(\tilde{z}'-2\beta A_{\mathop{\mathrm{sym}}}+D')^{-1}\big]}\right\rVert_2\\ &\leqslant 2M_7 n^{6\delta}\left\lVert{D^{-1}-(D')^{-1}}\right\rVert_2 + 3M_3\beta^{-1} n^{3\delta}e^{-M_4 n} \\ &\leqslant 2M_7 \beta n^{-2\delta} + 3M_3\beta^{-1} n^{3\delta}e^{-M_4 n}. \end{align}\] The last term is exponentially small in \(n\), so it may be absorbed into the constants. Therefore, \[\forall D \in \Omega, \quad \left\lVert{E_{\mathcal{D}_n}[(\tilde{z} - 2\beta A_{\mathop{\mathrm{sym}}} + D)^{-1} - \mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]]}\right\rVert_2 \leqslant M_{11} \beta n^{-2\delta},\] with probability at least \[1 - M_3 \exp(-M_4 n) - 2(3n^{8\delta})^n 3^{2n} e^{-n^{2-16\delta}/2}.\] Note since \(\delta \leqslant 1/17\), \[2(3n^{8\delta})^n 3^{2n} e^{-n^{2-16\delta}/2} = 2\exp(-\tfrac{1}{2}n^{2-16\delta} + 8\delta n \log n + 3 n \log 3) \leqslant M_{12} e^{-M_{13} n}.\] so the overall probability of error is bounded by \(M_{14} \exp(-M_{15} n)\). In the statement, we take \(C_1 = M_{14}\), \(C_2 = M_{15}\), and \(C_3 = M_{11}\). ◻

Proof. First, by cyclic symmetry of the trace, \[\operatorname{tr}_{nk}[G (B+B^{\mathsf{T}}) G (D' \otimes I_k)] = \operatorname{tr}_{nk}[B G (D' \otimes I_k) G] + \operatorname{tr}_{nk}[G (D' \otimes I_k) G B^{\mathsf{T}}]\] Now since \(G(z,t)\) is the inverse of a symmetric matrix, it is symmetric (here we mean symmetric with respect to transposition rather than Hermitian conjugation). Also, \(D'\) is symmetric. Thus, since transposition preserves the trace, \[\operatorname{tr}_{nk}[G (D' \otimes I_k) G B^{\mathsf{T}}] = \operatorname{tr}_{nk}[B G (D' \otimes I_k) G].\] Thus, we get \[\operatorname{tr}_{nk}[G B_{\mathop{\mathrm{sym}}} G (D' \otimes I_k)] = \operatorname{tr}_{nk}[B G (D' \otimes I_k) G] = \frac{1}{kn} \sum_{i,j=1}^{kn} B_{i,j} [G (D' \otimes I_k) G]_{j,i}.\] We take expectations on both sides and then use Gaussian integration by parts: \[\frac{1}{kn} \sum_{i,j=1}^{kn} \mathop{{}\mathbb{E}}\left[ B_{i,j} [G (D' \otimes I_k) G]_{j,i} \right] = \frac{1}{k^2n^2} \sum_{i,j=1}^{kn} \mathop{{}\mathbb{E}}\left[ \frac{\partial}{\partial B_{i,j}} \left[ G (D' \otimes I_k) G \right]_{j,i} \right]\] Using , we get \[\begin{align} \frac{\partial}{\partial B_{i,j}} G &= G \frac{\partial}{\partial B_{i,j}}[\beta t^{1/2}(B + B^{\mathsf{T}})] G \\ &= \beta t^{1/2} G (E_{i,j} + E_{j,i}) G \\ &= \beta t^{1/2} G E_{i,j} G + \beta t^{1/2} G E_{j,i} G, \end{align}\] where \(E_{i,j}\) are the standard matrix units in \(M_{nk}(\mathbb{C})\). Thus, \[\begin{align} \beta t^{-1/2} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G B_{\mathop{\mathrm{sym}}} G (D' \otimes I_k)] &= \frac{\beta^2}{k^2n^2} \sum_{i,j=1}^{nk} \mathop{{}\mathbb{E}}[G E_{i,j} G (D' \otimes I_k) G]_{j,i} \tag{37} \\ &\quad + \frac{\beta^2}{k^2n^2} \sum_{i, j=1}^{nk} \mathop{{}\mathbb{E}}[G E_{j,i} G (D' \otimes I_k) G]_{j,i} \tag{38} \\ &\quad + \frac{\beta^2}{k^2n^2} \sum_{i,j=1}^{nk} \mathop{{}\mathbb{E}}[G(D' \otimes I_k)G E_{i,j} G]_{j,i} \tag{39} \\ &\quad + \frac{\beta^2}{k^2n^2} \sum_{i,j=1}^{nk} \mathop{{}\mathbb{E}}[G (D' \otimes I_k)G E_{j,i} G]_{j,i} \tag{40}, \end{align}\] Taking first the terms 38 and 40 that contain \(E_{j,i}\), note that \[\eqref{eq:32matrix32resolvent32computation32term322} = \frac{\beta^2}{k^2n^2} \sum_{i, j=1}^{nk} \mathop{{}\mathbb{E}}[G_{j,j} [G (D' \otimes I_k) G]_{i,i}] = \beta^2 \operatorname{tr}_{nk}[G] \operatorname{tr}_{nk}[G (D' \otimes I_k) G].\] Likewise, 40 evaluates to \(\operatorname{tr}_{nk}[G(D' \otimes I_k)G] \operatorname{tr}_{nk}[G]\), which also equals 38 . Therefore, 38 and 40 become the term \(2 \beta^2 \mathop{{}\mathbb{E}}\bigg[ \operatorname{tr}_{nk}[G] \operatorname{tr}_{nk}[G(D' \otimes I_k)G]\) on the right-hand side of 36 in the statement of the lemma.

Next, consider the terms 37 and 39 that contain \(E_{i,j}\). Recall that \(G^{\mathsf{T}} = G\), or \(G_{i,j} = G_{j,i}\). Hence, \[\begin{align} \eqref{eq:32matrix32resolvent32computation32term321} &= \frac{\beta^2}{k^2n^2} \sum_{i,j=1}^{nk} \mathop{{}\mathbb{E}}[G_{j,i} [G (D' \otimes I_k) G]_{j,i}] = \frac{\beta^2}{k^2n^2} \sum_{i,j=1}^{nk} \mathop{{}\mathbb{E}}[G_{i,j} [G (D' \otimes I_k) G]_{j,i}] \\ &= \frac{\beta^2}{nk} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G[G(D' \otimes I_k)G]] = \frac{\beta^2}{nk} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G^3(D' \otimes I_k)]. \end{align}\] Similarly, 39 also evaluates to \(\frac{\beta^2}{nk} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G^3(D' \otimes I_k)]\). Therefore, 37 and 39 become the term \(\frac{2 \beta^2}{nk} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G^3(D' \otimes I_k)]\) on the right-hand side of 36 in the statement of the lemma. ◻

Proof. The argument is similar to the previous lemma. First, we observe that \((A \otimes I_k)^{\mathsf{T}} = A^{\mathsf{T}} \otimes I_k\) and \(G^{\mathsf{T}} = G\), and apply symmetry of the trace and transposes to get \[\operatorname{tr}_{nk}[G (A^{\mathsf{T}} \otimes I_k) G (D' \otimes I_k)] = \operatorname{tr}_{nk}[(D' \otimes I_k) G (A \otimes I_k) G] = \operatorname{tr}_{nk}[(A \otimes I_k)G(D' \otimes I_k) G].\] Therefore, \[\begin{align} \operatorname{tr}_{nk}[G (A_{\mathop{\mathrm{sym}}} \otimes I_k) G (D' \otimes I_k)] &= \operatorname{tr}_{nk}[(A \otimes I_k) G (D' \otimes I_k) G] \\ &= \sum_{i,j=1}^n A_{i,j} \operatorname{tr}_{nk}[(E_{i,j} \otimes I_k) G (D' \otimes I_k) G] \\ &= \frac{1}{n} \sum_{i,j=1}^n \mathop{{}\mathbb{E}}\left[ \frac{\partial}{\partial A_{i,j}} \operatorname{tr}_{nk}[(E_{i,j} \otimes I_k) G (D' \otimes I_k) G] \right], \end{align}\] where the last line follows from Gaussian integration by parts. Note that \[\frac{\partial}{\partial A_{i,j}} G = \beta (1 - t)^{1/2} G((E_{i,j} + E_{j,i}) \otimes I_k) G,\] and so \[\frac{\partial}{\partial A_{i,j}} [(E_{i,j} \otimes I_k) G (D' \otimes I_k) G] = (E_{i,j} \otimes I_k) G ((E_{i,j} + E_{j,i}) \otimes I_k) G (D' \otimes I_k) + (E_{i,j} \otimes I_k) G (D' \otimes I_k) ((E_{i,j} + E_{j,i}) \otimes I_k) G.\] Thus, we get \[\begin{align} \beta (1-t)^{-1/2} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G (A_{\mathop{\mathrm{sym}}} \otimes I_k) G (D' \otimes I_k)] &= \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(E_{i,j} \otimes I_k)G(E_{i,j} \otimes I_k) G (D' \otimes I_k) G] \tag{42} \\ &\quad + \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk} [(E_{i,j} \otimes I_k) G (E_{j,i} \otimes I_k) G (D' \otimes I_k) G] \tag{43} \\ &\quad + \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(E_{i,j} \otimes I_k)G(D' \otimes I_k)G (E_{i,j} \otimes I_k) G] \tag{44} \\ &\quad + \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(E_{i,j} \otimes I_k)G (D' \otimes I_k)G (E_{j,i} \otimes I_k)G] \tag{45}. \end{align}\] Note that 43 and 45 are the same up to cyclic symmetry of the trace and switching the indices \(i\) and \(j\). Each of these two terms evaluates to \[\begin{align} \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(E_{i,j} \otimes I_k)G(E_{i,j} \otimes I_k) G (D' \otimes I_k) G] &= \beta^2 \operatorname{tr}_{nk}[((\operatorname{tr}_n \otimes \mathop{\mathrm{id}})(G) \otimes I_k) G (D' \otimes I_k) G] \\ &= \beta^2 \mathbb{E} \operatorname{tr}_k[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G] (\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(D' \otimes I_k) G]. \end{align}\] Hence, 43 and 45 together produce the term \(2\beta^2 \mathbb{E} \operatorname{tr}_k[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G] (\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(D' \otimes I_k) G]\) on the right-hand side of 41 in the lemma statement. Meanwhile, 42 and 44 are equal to each other using cyclic symmetry of the trace, and each of these terms evaluates to \[\begin{align} \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(E_{i,j} \otimes I_k)G(E_{i,j} \otimes I_k) G (D' \otimes I_k) G] &= \frac{\beta^2}{n} \sum_{i,j=1}^{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(E_{i,i} \otimes I_k)(\mathsf{T}\otimes \mathop{\mathrm{id}})[G](E_{j,j} \otimes I_k) G (D' \otimes I_k) G] \\ &= \frac{\beta^2}{n} \operatorname{tr}_{nk}[(\mathsf{T}\otimes \mathop{\mathrm{id}})[G] G (D' \otimes I_k) G]. \end{align}\] Hence, 42 and 44 together produce the term \(\frac{2\beta^2}{n} \operatorname{tr}_{nk}[(\mathsf{T}\otimes \mathop{\mathrm{id}})[G] G (D' \otimes I_k) G]\) on the right-hand side of 41 in the lemma statement. ◻

Proof. We first note that \(\left\lVert{G(z,t)}\right\rVert \leqslant\frac{1}{|\mathop{\mathrm{Im}}z|}\) as a direct application of (1). Hence, \[|\operatorname{tr}_{nk}[G^3 (D' \otimes I_k)]| \leqslant\left\lVert{G^3}\right\rVert_2 \left\lVert{D' \otimes I_k}\right\rVert_2 \leqslant\left\lVert{G}\right\rVert^3 \left\lVert{D'}\right\rVert_2,\] where we use that \(\left\lVert{D' \otimes I_k}\right\rVert_2^2 = \operatorname{tr}_{nk}(((D')^*D' \otimes I_k)) = \operatorname{tr}_n((D')^*D') = \left\lVert{D'}\right\rVert_2^2\). This easily implies 46 . For the other estimate, note that \[\begin{align} |\operatorname{tr}_{nk}[(\mathsf{T}\otimes \mathop{\mathrm{id}})[G] G (D' \otimes I_k) G]| &\leqslant\left\lVert{(\mathsf{T}\otimes \mathop{\mathrm{id}})[G]}\right\rVert_2 \left\lVert{G(D' \otimes I_k)G}\right\rVert_2 \\ &\leqslant\left\lVert{G}\right\rVert_2 \left\lVert{G}\right\rVert \left\lVert{D' \otimes I_k}\right\rVert_2 \left\lVert{G}\right\rVert \\ &\leqslant\left\lVert{G}\right\rVert^3 \left\lVert{D'}\right\rVert_2. \end{align}\] Here we use the fact that \((\mathsf{T}\otimes \mathop{\mathrm{id}})\) is isometric with respect to \(\left\lVert{\cdot}\right\rVert_2\) since it performs a permutation of the entries of the matrix.³ We also use the non-commutative Hölder’s inequality. ◻

Proof. Consider the mappings \(M_{nk}(\mathbb{R}) \to M_k(\mathbb{C})\) given by \(f(B) = (\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G^*]\) and \(g(B) = (\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(D' \otimes I) G]\), and note that \[\mathop{{}\mathbb{E}}\operatorname{tr}_k\Bigl[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G] (\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(D' \otimes I_k) G]\Bigr] = \mathop{{}\mathbb{E}}\angles{f(B),g(B)}_{\operatorname{tr}_k}.\] To apply the Poincaré inequality, we first want to verify these are Lipschitz. Using (2), we see that \(G\) is \(\frac{2 \beta}{|\mathop{\mathrm{Im}}z|^2}\)-Lipschitz as a function of \(B\) with respect to \(\left\lVert{\cdot}\right\rVert_2\), which implies that \[f \text{ is } \frac{2 \beta}{|\mathop{\mathrm{Im}}z|^2} \text{-Lipschitz in } B.\] For \(g\), we use Lipschitzness of \(G\) in \(B\) together with the behavior of Lipschitz functions under products; more precisely, given two inputs \(B\) and \(\tilde{B}\), let \(G\) and \(\tilde{G}\) be the corresponding values of the resolvent \(G\). Then \[\begin{align} \left\lVert{G(D' \otimes I_k) G - \tilde{G}(D' \otimes I_k)\tilde{G}}\right\rVert_2 &\leqslant\left\lVert{(G - \tilde{G})(D' \otimes I_k)G}\right\rVert_2 + \left\lVert{\tilde{G}(D' \otimes I_k)(G - \tilde{G})}\right\rVert_2 \\ &\leqslant\left\lVert{G - \tilde{G}}\right\rVert_2 \left\lVert{D'}\right\rVert \left\lVert{G}\right\rVert + \left\lVert{\tilde{G}}\right\rVert \left\lVert{D'}\right\rVert \left\lVert{G - \tilde{G}}\right\rVert_2 \\ &\leqslant 2 \frac{\beta}{|\mathop{\mathrm{Im}}z|^2} \frac{1}{|\mathop{\mathrm{Im}}z|} \left\lVert{D'}\right\rVert. \end{align}\] Note here that we have the operator norm rather than the \(2\)-norm of \(D'\). Then since the \((\operatorname{tr}_n \otimes \mathop{\mathrm{id}})\) is a contraction with respect to \(2\)-norm, we see that \[g \text{ is } \frac{4 \beta}{|\mathop{\mathrm{Im}}z|^3} \left\lVert{D'}\right\rVert \text{-Lipschitz in } B.\] Now let \(\mathop{{}\mathbb{E}}_B\) denote the expectation with respect to \(B\) while holding \(A\) fixed. Note that \(B\) is invariant in distribution with respect to conjugation by \(I_n \otimes O\) for any matrix \(O\) in the \(k \times k\) orthogonal group, and of course \(I_n \otimes O\) leaves \(A \otimes I_k\) and \(D' \otimes I_k\) literally invariant. It follows that \(\mathop{{}\mathbb{E}}_B[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G]]\) is invariant under conjugation by the orthogonal group and hence is equal to a multiple of the identity; thus, \[\mathop{{}\mathbb{E}}_B[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G]] = \mathop{{}\mathbb{E}}_B \operatorname{tr}_{nk}[G].\] Similarly, \[\mathop{{}\mathbb{E}}_B[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(D' \otimes I_k) G]] = \mathop{{}\mathbb{E}}_B \operatorname{tr}_{nk}[G(D' \otimes I_k) G].\] By the Poincaré inequality (), \[\begin{align} \Bigl|\mathop{{}\mathbb{E}}_B \operatorname{tr}_k[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G](\operatorname{tr}_n \otimes \mathop{\mathrm{id}})&[G(D' \otimes I_k) G]] - \mathop{{}\mathbb{E}}_B \operatorname{tr}_{nk}[G] \mathop{{}\mathbb{E}}_B \operatorname{tr}_{nk}[G(D' \otimes I_k) G] \Bigr| \nonumber \\ &= |\mathop{{}\mathbb{E}}_B \angles{f(B),g(B)}_{\operatorname{tr}_k} - \angles{\mathop{{}\mathbb{E}}_B[f(B)], \mathop{{}\mathbb{E}}_B[g(B)]}_{\operatorname{tr}_k}| \nonumber \\ &= |\mathop{{}\mathbb{E}}_B \angles{f(B) - \mathop{{}\mathbb{E}}_B f(B), g(B) - \mathop{{}\mathbb{E}}_B g(B)}| \nonumber \\ &\leqslant\frac{\dim_{\mathbb{R}} M_k(\mathbb{C})}{(nk)^2} \left\lVert{f}\right\rVert_{\operatorname{Lip}} \left\lVert{g}\right\rVert_{\operatorname{Lip}} \nonumber \\ &\leqslant\frac{2}{n^2} \frac{2 \beta}{|\mathop{\mathrm{Im}}z|^2} \frac{4 \beta \left\lVert{D'}\right\rVert}{|\mathop{\mathrm{Im}}z|^3} \nonumber \\ &= \frac{16 \beta^2 \left\lVert{D'}\right\rVert}{n^2 |\mathop{\mathrm{Im}}z|^5}. \label{eq:32first32application32of32Poincare} \end{align}\tag{48}\] We can also apply the same reasoning to the scalar-valued functions \(B \mapsto \operatorname{tr}_{nk}[G]\) and \(B \mapsto \operatorname{tr}_{nk}[G(D' \otimes I_k) G]\), and thus we get \[\label{eq:32second32application32of32Poincare} |\mathop{{}\mathbb{E}}_B[\operatorname{tr}_{nk}[G] \operatorname{tr}_{nk}[G(D' \otimes I_k) G]] - \mathop{{}\mathbb{E}}_B \operatorname{tr}_{nk}[G] \mathop{{}\mathbb{E}}_B \operatorname{tr}_{nk}[G(D' \otimes I_k) G]| \leqslant\frac{16 \beta^2 \left\lVert{D'}\right\rVert}{(nk)^2 |\mathop{\mathrm{Im}}z|^5}.\tag{49}\] Combining 48 and 49 with the triangle inequality shows that \[\begin{gather} \Bigl|\mathop{{}\mathbb{E}}_B \operatorname{tr}_k[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(z,t)](\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(z,t)(D' \otimes I_k) G(z,t)]] - \mathop{{}\mathbb{E}}_B[\operatorname{tr}_{nk}[G(z,t)] \operatorname{tr}_{nk}[G(z,t)(D' \otimes I_k) G(z,t)]] \Bigr| \\ \leqslant\frac{16 \beta^2 \left\lVert{D'}\right\rVert}{n^2 |\mathop{\mathrm{Im}}z|^5} + \frac{16 \beta^2 \left\lVert{D'}\right\rVert}{(nk)^2 |\mathop{\mathrm{Im}}z|^5}. \end{gather}\] By integrating over \(A\), we can obtain the same inequality with \(\mathop{{}\mathbb{E}}\) rather than \(\mathop{{}\mathbb{E}}_B\). Finally, we recall that \(\left\lVert{D'}\right\rVert \leqslant n^{1/2} \left\lVert{D'}\right\rVert_2\) to complete the proof. ◻

Proof. By substituting 36 and 41 into 35 , we have \[\begin{align} h'(t) &= 2 \beta^2 \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G] \operatorname{tr}_{nk}[G(D' \otimes I_k)G] - 2 \beta^2 \mathop{{}\mathbb{E}}\operatorname{tr}_k[(\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G] (\operatorname{tr}_n \otimes \mathop{\mathrm{id}})[G(D' \otimes I_k) G]] \tag{50} \\ &\quad + \frac{\beta^2}{nk} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[G^3 (D' \otimes I_k)] \tag{51} \\ &\quad -\frac{2\beta^2}{n} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(\mathsf{T}\otimes \mathop{\mathrm{id}})[G] G (D' \otimes I_k) G]. \tag{52} \end{align}\] We then estimate 50 by Lemma 22, estimate 51 by 46 , and estimate 52 by 47 , which yields the bound asserted in this lemma. ◻

Proof of . Recall the values of \(h(0)\) and \(h(1)\) from 33 and 34 , note that \(|h(0) - h(1)| \leqslant\sup_{t \in [0,1]} |h'(t)|\), and apply our estimate for \(h'\) from Lemma 23 to obtain \[\begin{gather} \label{eq:32final32expectation32error32estimate32finite32k} |\mathop{{}\mathbb{E}}\operatorname{tr}_n[(z I_n - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1} D'] - \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(z I_{nk} - 2\beta B_{\mathop{\mathrm{sym}}} + D \otimes I_k)^{-1} (D' \otimes I_k)]| \\ \leqslant\frac{32 \beta^4 \left\lVert{D'}\right\rVert_2}{n^{3/2} |\mathop{\mathrm{Im}}z|^5} + \frac{32 \beta^4 \left\lVert{D'}\right\rVert_2}{n^{3/2} k^2 |\mathop{\mathrm{Im}}z|^5} + \frac{2 \beta^2 \left\lVert{D'}\right\rVert_2}{n |\mathop{\mathrm{Im}}z|^3} + \frac{2 \beta^2 \left\lVert{D'}\right\rVert_2}{nk |\mathop{\mathrm{Im}}z|^3}. \end{gather}\tag{53}\] Note that \(2B_{\mathop{\mathrm{sym}}}\) is \(\sqrt{2}\) times a standard \(nk \times nk\) GOE matrix. Moreover, \(D \otimes I_k\) and \(D' \otimes I_k\) are deterministic matrices. Thus, the asymptotic freeness theorem () implies that, for every non-commutative polynomial \(p\), the traces \(\operatorname{tr}_n[p(D \otimes I_k, D' \otimes I_k, 2 B_{\mathop{\mathrm{sym}}})]\) converge almost surely as \(k \to \infty\) to \(\tau_n[p(D,D',\sqrt{2} S)]\). The same also applies to the resolvent since this can be approximated by polynomials uniformly on compact subsets of the upper half-plane. Hence, \[\lim_{k \to \infty} \mathop{{}\mathbb{E}}\operatorname{tr}_{nk}[(z I_{nk} - 2 \beta B_{\mathop{\mathrm{sym}}} + D \otimes I_k)^{-1} (D' \otimes I_k)] = \tau_n[(z - \sqrt{2} \beta S + D)^{-1} D'].\] Thus, when we take \(k \to \infty\) in 53 , we obtain \[|\mathop{{}\mathbb{E}}\operatorname{tr}_n[(z - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}D'] - \tau_n[(z - \sqrt{2} \beta S + D)^{-1}D']| \leqslant\frac{32 \beta^4 \left\lVert{D'}\right\rVert_2}{n^{3/2} |\mathop{\mathrm{Im}}z|^5} + \frac{2 \beta^2 \left\lVert{D'}\right\rVert_2}{n |\mathop{\mathrm{Im}}z|^3}.\] By , letting \(f(z)\) be the subordination function, we obtain \[\tau_n[(z - \sqrt{2} \beta S + D)^{-1}D'] = \tau_n[(f(z) + D)^{-1} D'] = \operatorname{tr}_n[(f(z) + D)^{-1}D'],\] so that \[\left|\operatorname{tr}_n[(\mathop{{}\mathbb{E}}[(z - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (f(z) + D)^{-1})D'] \right| \leqslant\left( \frac{32 \beta^4}{n^{3/2} |\mathop{\mathrm{Im}}z|^5} + \frac{2 \beta^2}{n |\mathop{\mathrm{Im}}z|^3} \right) \left\lVert{D'}\right\rVert_2.\] Taking the supremum over \(\left\lVert{D'}\right\rVert_2 \leqslant 1\), we obtain the \(\left\lVert{\cdot}\right\rVert_2\)-norm of \(\mathop{{}\mathbb{E}}\circ E_{\mathcal{D}_n}[(z - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (f(z) + D)^{-1}\), and so ?? follows. ◻

Proof of . Let \(b\), \(\tilde{a}\), \(\tilde{b}\), \(\tilde{z}\) be as in the statement of the theorem, namely, \(b = \beta n^{-\delta}\), and \(\tilde{z} := ib + 2 \beta^2 g_{-D}(ib)\) where \(g_{-D}(z) = \operatorname{tr}_n((z+D)^{-1})\), and \(\tilde{a}\) and \(\tilde{b}\) are the real and imaginary parts of \(\tilde{z}\).

stating that \(2 \beta^2 \operatorname{tr}_n(D^{-1})\) is the maximum of the spectrum of \(\sqrt{2} \beta S - D\) where \(S\) is a semicircular operator freely independent of \(D\) follows from (2). Now recall \[\tilde{a} = 2 \beta^2 \mathop{\mathrm{Re}}\operatorname{tr}_n((ib+D)^{-1}),\] and so \[|2 \beta^2 \operatorname{tr}_n(D^{-1}) - \tilde{a}| \leqslant 2 \beta^2 |\mathop{\mathrm{Re}}\operatorname{tr}_n[D^{-1} - (ib + D)^{-1}]|.\] We have by and resolvent identities that \[\begin{align} \mathop{\mathrm{Re}}\operatorname{tr}_n[D^{-1} - (ib + D)^{-1}] &= \operatorname{tr}_n[D^{-1} - D(b^2 + D^2)^{-1}] \\ &= \operatorname{tr}_n[D[D^{-2} - (b^2 + D^2)^{-1}]] \\ &= \operatorname{tr}_n[DD^{-2}b^2(b^2+D^2)^{-1}] \\ &\leqslant b^2 \operatorname{tr}_n[D^{-3}]. \end{align}\] This proves the asserted estimate on \(a + 2 \beta^2 \operatorname{tr}_n[D^{-1}] - \tilde{a}\) since \(b^2 = \beta^2 n^{-2\delta}\).

For , note that \[\operatorname{tr}_n[P^2(\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^2] = \operatorname{tr}_n[\tilde{b}(\tilde{b}^2+(\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^2)^{-1}(\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^2] \leqslant\tilde{b},\] and by (1), we have \(\tilde{b} \leqslant 2 \beta^2 b^3 \operatorname{tr}_n(D^{-4})\) and then we substitute \(b = \beta n^{-\delta}\).

For , note that \[P^2 = -\mathop{\mathrm{Im}}[(\tilde{a} + i\tilde{b} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}],\] and observe that \(\mathop{\mathrm{Im}}\circ E_{\mathcal{D}_n} = E_{\mathcal{D}_n} \circ \mathop{\mathrm{Im}}\). Letting \(z := ib\), we estimate \[\begin{align} \left\lVert{E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (z + D)^{-1}}\right\rVert_2 &\leqslant\left\lVert{E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - \mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]}\right\rVert_2 \tag{54} \\ &\qquad\qquad + \left\lVert{\mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (z + D)^{-1}}\right\rVert_2 \tag{55} \end{align}\] By , with probability at least \(1 - M_1 \exp(-M_2 n)\) in the Gaussian matrix \(A\), we have for all choices of \(D\) that \[\label{eq:32RMT32main32splitting32solution} \left\lVert{E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - \mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}]}\right\rVert_2 \leqslant M_3 \beta n^{-2\delta},\tag{56}\] which takes care of 54 .

To estimate 55 , let \(f\) be the subordination function as in ; by construction \(\tilde{z} = z + 2 \beta^2 g_{-D}(z)\), and so \(f(\tilde{z}) = z\). Hence, by , we have \[\left\lVert{\mathop{{}\mathbb{E}}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (z + D)^{-1}}\right\rVert_2 \leqslant\frac{32 \beta^4}{n^{3/2} \tilde{b}^5} + \frac{2 \beta^2}{n \tilde{b}^3}.\] Then recall by (1) that \(\tilde{b}^{-1} \leqslant 3\beta^2 b^{-3} = 3 \beta^{-1} n^{3\delta}\). Also, \(E_{\mathcal{D}_n}\) is contractive in \(\left\lVert{\cdot}\right\rVert_2\), so that \[\left\lVert{\mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (z + D)^{-1}}\right\rVert_2 \leqslant\frac{M_4}{\beta n^{3/2-15\delta}} + \frac{M_5}{\beta n^{1-9\delta}}.\] Since \(\delta \leqslant 1/17 < 3/34 < 1/11\), we have that \(3/2 - 15 \delta \geqslant 2 \delta\) and \(1 - 9 \delta \geqslant 2 \delta\). Therefore, \[\label{eq:32RMT32main32splitting32solution322} \left\lVert{\mathop{{}\mathbb{E}}E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (z + D)^{-1}}\right\rVert_2 \leqslant M_6 \beta^{-1} n^{-2\delta}.\tag{57}\] Estimating 54 by 56 and 55 by 57 and bounding \(\beta^{-1}\) by a constant, we get \[\left\lVert{E_{\mathcal{D}_n}[(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}] - (z + D)^{-1}}\right\rVert_2 \leqslant M_7 \beta n^{-2\delta}.\] Then taking the negated imaginary parts of the operators, we get \[\left\lVert{E_{\mathcal{D}_n}[\tilde{b}(\tilde{b}^2 + (\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^2)^{-1}] - b(b^2 + D^2)^{-1}}\right\rVert_2 \leqslant M_7 \beta n^{-2\delta},\] which is the desired estimate with \(C_3 = M_7\).

For , note by (2), \[\operatorname{tr}_n[b(b^2+D^2)^{-1}] = -\mathop{\mathrm{Im}}g_{-D}(ib) \geqslant\frac{1}{2 \beta^2} (b - b^3 \left\lVert{D^{-1}}\right\rVert^2) \geqslant\frac{1}{2} \beta^{-1} n^{-\delta} (1 - \beta^2 n^{-2\delta} \left\lVert{D^{-1}}\right\rVert^2).\] Then using , \[\begin{align} \operatorname{tr}_n[P^2] = \operatorname{tr}[E_{\mathcal{D}_n}(P^2)] &\geqslant\operatorname{tr}_n[b(b^2+D^2)^{-1}] - \left\lVert{E_{\mathcal{D}_n}(P^2) - b(b^2+D^2)^{-1}}\right\rVert_2 \\ &\geqslant\frac{1}{2} \beta^{-1} n^{-\delta} - M_7 \beta n^{-2\delta} - \frac{1}{2} \beta \left\lVert{D^{-1}}\right\rVert^2 n^{-3\delta}. \end{align}\]

For , observe that \[\left\lVert{P^2}\right\rVert = \left\lVert{\mathop{\mathrm{Im}}(\tilde{z} - 2 \beta A_{\mathop{\mathrm{sym}}} + D)^{-1}}\right\rVert \leqslant\frac{1}{\mathop{\mathrm{Im}}\tilde{z}} \leqslant\frac{3 \beta^2}{b^3} = 3 \beta^{-1} n^{3\delta}. \qedhere\] ◻

Proof. By definition, \[\sqrt{2} \beta D_k^{-1} = \frac{\sqrt{2} \beta \operatorname{diag}(v_k(\sigma_{k}))}{\left\lVert{\sqrt{2} \beta \operatorname{diag}(v_k(\sigma_{k}))}\right\rVert_2}.\] In general, for a nonzero vector \(h\) in a Hilbert space, \[\left\lVert{\frac{h}{\left\lVert{h}\right\rVert} - h}\right\rVert = \left| \frac{1}{\left\lVert{h}\right\rVert} - 1 \right| \left\lVert{h}\right\rVert = \left| \left\lVert{h}\right\rVert - 1 \right|.\] Applying this to \(\sqrt{2} \beta \operatorname{diag}(v_k(\sigma_{k,j}))\) yields the first equality. For the second estimate, let \(\Sigma\) be a random variable on the same probability space as \(Y_{t_k}^\gamma\) such that the marginal of \(\Sigma\) is \(\mathop{\mathrm{emp}}(\sigma_k)\) and \(\Sigma\) and \(Y_{t_k}^\gamma\) are optimally coupled, i.e. \(\left\lVert{\Sigma - Y_{t_k}^\gamma}\right\rVert_{L^2} = d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y_t^\gamma))\). Since \(v\) is \(2\)-Lipschitz by , we have \[\left|\frac{1}{\sqrt{n}} \left|v_k(\sigma_{k})\right|_2 - \left\lVert{v_k(Y_{t_k}^\gamma)}\right\rVert_{L^2} \right| \leqslant\left\lVert{v_k(\Sigma) - v_k(Y_{t_k}^\gamma)}\right\rVert_{L^2} \leqslant 2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k), \operatorname{dist}(Y_{t_k}^\gamma)).\] We then recall from that \[\left| \left\lVert{v_k(Y_{t_k}^\gamma)}\right\rVert_{L^2} - \frac{1}{\sqrt{2} \beta} \right| \leqslant(1 + e^{5 \beta^2 t_k}) \gamma \leqslant(1 + e^{5 \beta^2}) \gamma.\] Combining these estimates yields the asserted statement. ◻

Proof. (1) By , writing \(b = \beta n^{-\delta}\), \[\label{eq:5463461-first-bound} \left\lVert{E_{\mathcal{D}_n}[P_k^2] - b (b^2 + D_k^2)^{-1}}\right\rVert_1 \leqslant\left\lVert{E_{\mathcal{D}_n}[P_k^2] - b (b^2 + D_k^2)^{-1}}\right\rVert_2 \leqslant M_1 \beta n^{-2\delta}.\tag{60}\] We define an intermediate term \(\Xi\) and find a common denominator \[\Xi := D_k^{-2} - (b^2 + D_k^2)^{-1} = b^2 (b^2 + D_k^2)^{-1} D_k^{-2}.\] Hence, \[\begin{align} \left\lVert{ \Xi }\right\rVert_1 &\leqslant b^2 \left\lVert{(b^2 + D_k^2)^{-1}}\right\rVert \left\lVert{D_k^{-2}}\right\rVert_1 \notag \\ &\leqslant b^2 \left\lVert{D_k^{-1}}\right\rVert^2 \frac{1}{2 \beta^2} \label{eq:Xi-bound} \end{align}\tag{61}\] Now recall that \(D_k^{-1} = \operatorname{diag}(v_k(\sigma_{k})) / \left\lVert{\sqrt{2} \beta \operatorname{diag}(v_k(\sigma_{k}))}\right\rVert_2\), and \(v \leqslant(1 + \gamma)\) by so that \[\left\lVert{D_k^{-1}}\right\rVert \leqslant\frac{1+\gamma}{\left\lVert{\sqrt{2} \beta \operatorname{diag}(v_k(\sigma_{k}))}\right\rVert_2}\] By , if \(2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k), \operatorname{dist}(Y_{t_k}^\gamma)) + (1 + e^{5 \beta^2}) \gamma \leqslant\frac{1}{2 \sqrt{2} \beta}\), then we obtain \[\left\lVert{\operatorname{diag}(v_k(\sigma_{k}))}\right\rVert_2 \geqslant\frac{1}{\sqrt{2} \beta} - \frac{1}{2\sqrt{2} \beta} = \frac{1}{2 \sqrt{2} \beta}.\] Hence, \(\left\lVert{D_k^{-1}}\right\rVert \leqslant 2(1+\gamma) \leqslant 6\), and so, substituting the last two inequalities into , \[\left\lVert{\Xi }\right\rVert_1 \leqslant\frac{4(1+\gamma)^2}{2 \beta^2} b^2 = 2(1+\gamma)^2n^{-2\delta}.\] Therefore, by the triangle inequality with the preceding bound and and because \(\gamma < 2\), \[\left\lVert{E_{\mathcal{D}_n}[P_k^2] - b D_k^{-2}}\right\rVert_1 \leqslant M_1 \beta n^{-2\delta} + 2 b n^{-2\delta} \leqslant M_2 \beta n^{-2\delta}.\] Furthermore, by , \[\left\lVert{P_k^2 - \Pi_{\sigma_k^\perp} P_k^2 \Pi_{\sigma_k^\perp}}\right\rVert_2 \leqslant 2 \left\lVert{P_k^2}\right\rVert \, \left\lVert{1 - \Pi_{\sigma_k^\perp}}\right\rVert_2 \leqslant\frac{C}{n^{1/2} \tilde{b}} \leqslant M_3 \beta^2 b^{-3} n^{-1/2} = M_4 \beta^{-1} n^{-1/2+3\delta}.\] We can bound \(n^{-1/2+3\delta}\) by \(n^{-2\delta}\) as well since \(\delta \leqslant 1/17\). Hence, by triangle inequality with the two preceding bounds and the contractivity of \(E_{\mathcal{D}_n}\), \[\left\lVert{E_{\mathcal{D}_n}[\Pi_{\sigma_k^\perp} P_k^2 \Pi_{\sigma_k^\perp}] - b D_k^{-2}}\right\rVert_2 \leqslant M_4 \beta n^{-2\delta}.\] Then multiplying by \(2 \beta^2 / b = 2 \beta n^\delta\), \[\left\lVert{E_{\mathcal{D}_n}[Q_k^2] - 2 \beta^2 D_k^{-2}}\right\rVert_2 \leqslant 2M_4 \beta^2 n^{-\delta}.\] This proves the first claim.

(2) By the Powers-Størmer inequality, since \(E_{\mathcal{D}_n}[Q_k^2]^{1/2}\) and \(D_k\) are nonnegative matrices, we have \[\begin{align} \left\lVert{E_{\mathcal{D}_n}[Q_k^2]^{1/2} - \sqrt{2} \beta D_k^{-1}}\right\rVert_2 &\leqslant\left\lVert{E_{\mathcal{D}_n}[Q_k^2] - 2 \beta^2 D_k^{-2}}\right\rVert_1^{1/2} \\ &\leqslant\left\lVert{E_{\mathcal{D}_n}[Q_k^2] - 2 \beta^2 D_k^{-2}}\right\rVert_2^{1/2} \\ &\leqslant(2M_4)^{1/2} \beta n^{-\delta/2}. \end{align}\]

(3) The third claim is immediate from the first claim since \(2 \beta^2 \operatorname{tr}_n(D_k^{-2}) = 1\) by construction.

(4) Note that \[\left\lVert{E_{\mathcal{D}_n}[Q_k^2]}\right\rVert_2 \leqslant 72 \beta^2 \left\lVert{D_k^{-2}}\right\rVert_2 + 2M_4 \beta^2 n^{-\delta} \leqslant 8 \beta^2 + 2M_4 \beta^2\] since we have \(\left\lVert{D_k^{-1}}\right\rVert \leqslant 6\).

(5) Note that by , \[\left\lVert{Q_k^2}\right\rVert \leqslant 2 \beta n^\delta \left\lVert{P_k^2}\right\rVert \leqslant C n^{4\delta}.\]

(6) Using , letting \(\overline{Q}_k^2 := 2 \beta n^\delta P_k^2\), we get \[\left\lVert{\left(2 \beta A_{\mathop{\mathrm{sym}}} - D_k - \tilde{a}\right) \overline{Q}_k}\right\rVert_2^2 = \operatorname{tr}_n\left(\overline{Q}_k^2 (\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}} + D_k)^2 \right) \leqslant 2 \beta^4 n^{-2\delta} \left\lVert{D_k^{-1}}\right\rVert^2 \leqslant 72 \beta^4 n^{-2 \delta}\] since \(\left\lVert{D_k^{-1}}\right\rVert \leqslant 6\). By the Powers-Størmer inequality, \[\left\lVert{Q_k - \overline{Q}_k}\right\rVert_2^2 \leqslant\left\lVert{Q_k^2 - \overline{Q}_k^2}\right\rVert_1 \leqslant 2\beta n^{\delta}\left(2\left\lVert{(1 - \Pi_{\sigma_k^\perp})P_k^2}\right\rVert_1 + \left\lVert{(1 - \Pi_{\sigma_k^\perp})P_k^2(1 - \Pi_{\sigma_k^\perp})}\right\rVert_1\right),\] which is bounded above by \(6\beta n^{\delta-1/2}\left\lVert{P_k^2}\right\rVert\), since \(\left\lVert{1 - \Pi_{\sigma_k^\perp}}\right\rVert_2 = n^{-1/2}\). So by triangle inequality, \[\label{eq:5463466-third-bound} \left\lVert{\left(2 \beta A_{\mathop{\mathrm{sym}}} - D_k - \tilde{a}\right) Q_k}\right\rVert_2 \leqslant 6 \sqrt{2} \beta^2 n^{-\delta} + \sqrt{6\beta} n^{\delta/2-1/4}\left\lVert{P_k}\right\rVert\left\lVert{2 \beta A_{\mathop{\mathrm{sym}}} - D_k - \tilde{a}}\right\rVert.\tag{62}\] Then recall from that \[|\tilde{a} - 2 \beta^2 \operatorname{tr}_n(D_k^{-1})| \leqslant 2 \beta^4 n^{-2\delta} \operatorname{tr}_n(D_k^{-3}) \leqslant n^{-2 \delta} \left\lVert{D_k^{-1}}\right\rVert \cdot 2 \beta^4 \operatorname{tr}_n(D_k^{-2}) \leqslant 12 \beta^2 n^{-2\delta}.\] Hence, by , \[\left\lVert{\left(\tilde{a} - 2 \beta^2 \operatorname{tr}_n(D_k^{-1})\right) Q_k}\right\rVert_2 \leqslant M_5 \beta \cdot 2\beta^2 n^{-2\delta}.\] Therefore, applying triangle inequality with and the preceding bound, \[\left\lVert{\left(2 \beta A_{\mathop{\mathrm{sym}}} - D_k - 2 \beta^2 \operatorname{tr}_n(D_k^{-1})\right) Q_k}\right\rVert_2 \leqslant 6 \sqrt{2} \beta^2 n^{-\delta} + M_6n^{-1/4+2\delta}(\beta+\gamma^{-1}) + M_5 \beta^3 \cdot 2 n^{-2\delta} ,\] where we used (1) and the high-probability event from to obtain \(\left\lVert{\tilde{a} - 2 \beta A_{\mathop{\mathrm{sym}}} + D_k}\right\rVert \leqslant M_7(\beta + \gamma^{-1})\) and gives \(\left\lVert{P_k}\right\rVert \leqslant M_8 \beta^{-1/2} n^{3\delta/2}\). ◻

Proof. Recall \[Y_{t + \eta}^\gamma - \left(Y_t^\gamma + \sqrt{2} \beta v(t,Y_t^\gamma)(W_{t+\eta} - W_t)\right) = \int_{0 \leqslant h \leqslant\eta} \sqrt{2} \beta \left[v(t+h,Y_{t+h}^\gamma) - v(t,Y_t^\gamma)\right] dW_{t+h}.\] By the Itô isometry, the Lipschitz bounds for \(v\) (), and the arithmetic-geometric mean inequality, \[\begin{align} \mathop{{}\mathbb{E}}\left|Y_{t+\eta}^\gamma - Y_t^\gamma - \sqrt{2} \beta v(t,Y_t^\gamma) (W_{t+\eta} - W_t)\right|^2 &= 2 \beta^2 \int_{0\leqslant h \leqslant\eta} \mathop{{}\mathbb{E}}\left|v(t+h,Y_{t+h}^\gamma) - v(t,Y_t^\gamma)\right|^2\,dh \\ &\leqslant 2 \beta^2 \int_0^\eta \left(M_1 \beta^2 h + 2|Y_{t+h}^\gamma - Y_t^\gamma|\right)^2 \,dh \\ &\leqslant\int_0^\eta \left(4M_1^2 \beta^6 h^2 + 8 \beta^2 |Y^{\gamma}_{t+h} - Y^{\gamma}_t|^2\right)\,dh. \end{align}\] Now note that since \(v\) is bounded by \(1+\gamma\), we also have \[\mathop{{}\mathbb{E}}\left|Y_{t+h}^\gamma - Y_t^\gamma\right|^2 = 2 \beta^2 \int_0^h \left|v(t+h',Y_{t+h'}^\gamma)\right|^2\,dh' \leqslant 2 \beta^2 h(1+\gamma).\] Therefore, we get \[\mathop{{}\mathbb{E}}\left|Y_{t+\eta}^\gamma - Y_t^\gamma - \sqrt{2} \beta v(t,Y^{\gamma}_t) (W_{t+\eta} - W_t)\right|^2 \leqslant\int_0^\eta (4M_1^2 \beta^6 h^2 + 16 \beta^4 h(1+\gamma)) \,dh = M_2 \beta^6 \eta^3 + M_3 \beta^4 \eta^2 \leqslant M_4 \beta^6 \eta^2.\] ◻

Proof. Consider the discrete probability space \([n]\) with normalized counting measure, and let \(\Sigma\) be a random variable that takes value \(\sigma_{k,j}\) on point \(j\), so that \(\Sigma\) has distribution \(\mathop{\mathrm{emp}}(\sigma_k)\). Also, let \(\Xi\) be the random variable that takes value \(((Q_k^2)_{j,j})^{1/2}\) at point \(j\). Let \(W\) be a normal random variable of variance \(\eta\) independent of \((\Sigma,\Xi)\). We first observe that \(\Sigma + \Xi W\) has the distribution \(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1})\). Indeed, for smooth functions \(f\), \[\mathop{{}\mathbb{E}}\frac{1}{n} \sum_{j=1}^n f(\sigma_{k+1,j}) = \mathop{{}\mathbb{E}}\frac{1}{n} \sum_{j=1}^n f\left(\sigma_{k,j} + \eta^{1/2} (Q_k Z_k)_j\right).\] Since \(\eta^{1/2}(Q_k Z_k)_j\) is a normal random variable of variance \(\eta (Q_k^2)_{j,j}\), the expectation is the same if we replace \(\eta^{1/2}(Q_k Z_k)_j\) with \(((Q_k^2)_{j,j})^{1/2} W\). Thus, \[\mathop{{}\mathbb{E}}\frac{1}{n} \sum_{j=1}^n f\left(\sigma_{k,j} + \eta^{1/2} (Q_k Z_k)_j\right) = \mathop{{}\mathbb{E}}\frac{1}{n} \sum_{j=1}^n f\left(\sigma_{k,j} + ((Q_k^2)_{j,j})^{1/2} W\right) = \mathop{{}\mathbb{E}}f(\Sigma + \Xi W).\]

By choosing an appropriate larger probability space, we can arrange that \(\Sigma\), \(\Xi\), and \((W_t)_{0 \leqslant t \leqslant t_k}\) be in the same probability space (hence also \(Y_t^\gamma\) is on the same probability space since \(Y_t^\gamma\) is obtained by solving the SDE with Brownian motion \(W_t\)) such that \(\Sigma\) and \(Y_{t_{k}}^\gamma\) are optimally coupled, that is, \[\left\lVert{\Sigma - Y_{t_k}^\gamma}\right\rVert_{L^2} = d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k), \operatorname{dist}(Y^{\gamma}_{t_k})\right).\] Then take the rest of the Brownian motion \((W_t - W_{t_k})_{t \geqslant t_k}\) to be independent of \((\Sigma,\Xi,(W_t)_{0 \leqslant t \leqslant t_{k+1}}\)). Since \(W_{t_{k+1}} - W_{t_k}\) has variance \(\eta\), we can identify it with the \(W\) from the previous paragraph.

Making the conditioning in \(\mathop{{}\mathbb{E}}\left[\mathop{\mathrm{emp}}(\sigma_{k+1}) | A, \sigma_1, \dots, \sigma_k\right]\) notationally implicit for brevity, we want to estimate \[d_{W,2}\left(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}),\operatorname{dist}(Y_{t_{k+1}}^\gamma \mid Y_{t_{k}}^\gamma)\right) \leqslant\left\lVert{(\Sigma + \Xi W) - Y_{t_{k+1}}^\gamma}\right\rVert_{L^2} = \left\lVert{(\Sigma - Y_{t_k}^\gamma) + (\Xi W - Y_{t_{k+1}}^\gamma + Y_{t_k}^\gamma)}\right\rVert_{L^2}.\] Observe that the conditional expectation of \(\Xi W\) given \((Y_{t_k}^\gamma,\Sigma)\) is zero because \(W\) is independent of these variables. Moreover, since \(Y_{t_{k+1}}^\gamma - Y_{t_k}^\gamma = \int_{t_k}^{t_{k+1}} \sqrt{2} \beta v(t,Y_t^\gamma)\,dW_t\), this also has conditional expectation zero given \((Y_{t_k}^\gamma,\Sigma)\). Thus, \(\Xi W - Y_{t_{k+1}}^\gamma + Y_{t_k}^\gamma\) and \(\Sigma - Y_{t_k}^\gamma\) are orthogonal in \(L^2\) and so \[\left\lVert{\Sigma + \Xi W - Y^{\gamma}_{t_{k+1}}}\right\rVert_{L^2}^2 = \left\lVert{\Sigma - Y_{t_k}^\gamma}\right\rVert_{L^2}^2 + \left\lVert{\Xi W - Y_{t_{k+1}}^\gamma + Y_{t_k}^\gamma}\right\rVert_{L^2}^2.\] Thus, \[\label{eq:lemma-5465-pythagorean} d_{W,2}\left(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y^{\gamma}_{t_{k+1}} \mid Y_{t_{k}}^\gamma)\right)^2 \leqslant d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y_{t_k}^\gamma)\right)^2 + \left\lVert{\Xi W - Y_{t_{k+1}}^\gamma + Y_{t_k}^\gamma}\right\rVert_{L^2}^2.\tag{63}\] Next, we estimate by triangle inequality \[\label{eq:lemma-5465-first-triangle} \left\lVert{\Xi W - Y_{t_{k+1}}^\gamma + Y_{t_k}^\gamma}\right\rVert_{L^2} \leqslant\left\lVert{\Xi W - \sqrt{2} \beta v_k(Y_{t_k}^\gamma) W}\right\rVert_{L^2} + \left\lVert{Y_{t_{k+1}}^\gamma - Y_{t_k}^\gamma - \sqrt{2} \beta v_k(Y_{t_k}^\gamma) W}\right\rVert_{L^2}.\tag{64}\] By , the second term of satisfies \[\label{eq:lemma-5465-first-triangle-second-term} \left\lVert{Y_{t_{k+1}}^\gamma - Y_{t_k}^\gamma - \sqrt{2} \beta v_k(Y_{t_k}^\gamma) W}\right\rVert_{L^2} \leqslant M_1 \beta^3 \eta.\tag{65}\] Meanwhile, by another triangle inequality, the first term satisfies \[\begin{align} \left\lVert{\Xi W - \sqrt{2} \beta v_k(Y_{t_k}^\gamma) W}\right\rVert_{L^2} &= \eta^{1/2} \left\lVert{\Xi - \sqrt{2} \beta v_k(Y_{t_k}^\gamma)}\right\rVert_{L^2} \notag \\ \label{eq:lemma-5465-second-triangle} &\leqslant\eta^{1/2} \left\lVert{\Xi - \sqrt{2} \beta v_k( \Sigma)}\right\rVert_{L^2} + \eta^{1/2} \left\lVert{\sqrt{2} \beta v_k(\Sigma) - \sqrt{2} \beta v_k(Y_{t_k}^\gamma)}\right\rVert_{L^2}. \end{align}\tag{66}\] Furthermore, and , along with the fact that \(1+e^{5\beta^2} \leqslant 2e^{5\beta^2}\), show that the first term of satisfies \[\begin{align} \left\lVert{\Xi - \sqrt{2} \beta v_k(\Sigma)}\right\rVert_{L^2} &\leqslant\left\lVert{E_{\mathcal{D}_n}[Q_k^2]^{1/2} - \sqrt{2} \beta D_k^{-1}}\right\rVert_2 + \sqrt{2} \beta \left\lVert{D_k^{-1} - \operatorname{diag}(v_k(\sigma_{k}))}\right\rVert_2 \\ &\leqslant M_2 \beta n^{-\delta/2} + 2 \sqrt{2} \beta d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y_{t_k}^\gamma)\right) + 2 \sqrt{2} \beta e^{5 \beta^2} \gamma. \end{align}\] Moreover, since \(v\) is \(2\)-Lipschitz in space by , we get for the second term \[\left\lVert{\sqrt{2} \beta v_k(\Sigma) - \sqrt{2} \beta v_{k}(Y^{\gamma}_{t_{k}})}\right\rVert_{L^2} \leqslant M_3 \beta d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y^{\gamma}_{t_k})\right).\] Thus, combining the last two inequalities with , \[\left\lVert{\Xi W - \sqrt{2} \beta v_{k}(Y^{\gamma}_{t_k})W}\right\rVert_{L^2} \leqslant\eta^{1/2}\left[M_2 \beta n^{-\delta/2} + M_4 \beta d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y^{\gamma}_{t_k})\right) + M_5 \beta e^{5\beta^2}\gamma\right],\] which then combines with and to yield \[\left\lVert{\Xi W - Y^{\gamma}_{t_{k+1}} + Y^{\gamma}_{t_k}}\right\rVert_{L^2} \leqslant M_1 \beta^3 \eta + \eta^{1/2} \beta \left[ M_2 n^{-\delta/2} + M_4 d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y^{\gamma}_{t_k})\right) + M_5 e^{5\beta^2}\gamma \right].\] Finally, using the arithmetic-geometric mean inequality, \[\left\lVert{\Xi W - Y^{\gamma}_{t_{k+1}} + Y^{\gamma}_{t_{k}}}\right\rVert_{L^2}^2 \leqslant\eta \beta^2 \cdot \left[ M_6 \beta^4 \eta + M_7 n^{-\delta} + M_8 d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_k),\operatorname{dist}(Y^{\gamma}_{t_k})\right)^2 + M_9 e^{10 \beta^2} \gamma^2 \right].\] This with shows the desired conclusion with \(C_1 = M_6\), \(C_2 = M_7\), \(C_3 = M_8\), \(C_4 = M_9\). ◻

Proof. Recall from that \(\left\lVert{Q_k^2}\right\rVert \leqslant M_1 n^{4\delta}\). Therefore, \((Q_k Z_k)_j\) is a normal random variable with mean zero and variance bounded by \(M_1 n^{4\delta}\). Thus, \[\mathop{{}\mathbb{P}}\left(\left|\left(Q_k Z_k\right)_j\right| \geqslant n^\alpha\right) \leqslant M_2 \exp(-M_3 n^{2 \alpha-4\delta}).\] The asserted estimate therefore follows from a union bound over the coordinates. ◻

Proof. Without loss of generality, assume that \(a = 0\). Let \(\tilde{Z} = b^{-1/2} Z\) which is a standard normal. Then \[\begin{align} \mathbb{E}\left[\mathbb{1}_{|Z| \geqslant c} |Z|^2\right] &= b \mathbb{E}\left[\mathbb{1}_{|\tilde{Z}| \geqslant b^{-1/2}c} |\tilde{Z}|^2\right] \\ &= \frac{2b}{\sqrt{2 \pi}} \int_{b^{-1/2}c}^\infty z^2 e^{-z^2/2}\,dz \\ &= \frac{2b}{\sqrt{2 \pi}} \left(\left[-ze^{-z^2/2}\right]_{b^{-1/2}c}^\infty + \int_{b^{-1/2}c}^\infty e^{-z^2/2}\,dz\right) \\ &\leqslant\frac{2b}{\sqrt{2 \pi}} \left[b^{-1/2}c e^{-b^{-1}c^2/2} + b^{1/2} c^{-1} \int_{b^{-1/2}c}^\infty ze^{-z^2/2}\,dz\right] \\ &= \frac{2b}{\sqrt{2 \pi}}(b^{-1/2}c + b^{1/2}c^{-1}) e^{-b^{-1}c^2/2}. \qedhere \end{align}\] ◻

Proof. By , \(\max_j |\sigma_{k+1,j} - \sigma_{k,j}| \leqslant\eta^{1/2} n^\alpha\) with probability at least \(1 - M_1 n \exp(-M_2 n^{2 \alpha-4\delta})\) in the Gaussian vector \(Z_k\) conditioned on \(A, Z_0, \dots, Z_{k-1}\). This in particular, together with \(K\eta \leqslant q^* \leqslant 1\), implies that \[\label{eq:max-coordinate-event} \max_j |\sigma_{k+1,j}| \leqslant(k+1) \eta^{1/2} n^\alpha \leqslant K \eta^{1/2} n^{\alpha} \leqslant\eta^{-1/2} n^\alpha\tag{67}\] with probability at least \(1 - M_1 Kn \exp(-M_2 n^{2 \alpha-4\delta})\). Fix \(\ell\) such that \(2^{\ell-1} \leqslant 2 \eta^{-1/2} n^\alpha \leqslant 2^\ell\). We truncate the expected empirical distribution as follows: Let \(\operatorname{proj}_{[-2^\ell,2^\ell]}\) be the truncation map \[\operatorname{proj}_{[-2^\ell,2^\ell]}(s) = \begin{cases} -2^\ell, & s \in (-\infty, -2^\ell] \\ s, & s \in [-2^\ell, 2^\ell] \\ 2^\ell, & s \in [2^\ell,\infty). \end{cases}\] and let \(\tau_0\) be the pushforward of \(\tau = \mathop{{}\mathbb{E}}\left[\mathop{\mathrm{emp}}(\sigma_{k+1}) | A, \sigma_1, \dots, \sigma_k\right]\) under \(\operatorname{proj}_{[-2^\ell,2^\ell]}\). Since \(|\sigma_{k,j}| \leqslant k\eta^{1/2} n^{\alpha} \leqslant\eta^{-1/2} n^\alpha\) by assumption, we have \[|\sigma_{k+1,j} - \sigma_{k,j}| \leqslant\eta^{-1/2} n^\alpha \implies |\sigma_{k+1,j}| \leqslant 2 \eta^{-1/2} n^\alpha \leqslant 2^\ell.\] and thus \[|\sigma_{k+1,j} - \mathop{\mathrm{proj}}_{[-2^\ell,2^\ell]}(\sigma_{k+1,j})| \leqslant\mathbb{1}_{|\sigma_{k+1,j} - \sigma_{k,j}| \geqslant\eta^{-1/2} n^\alpha} |\sigma_{k+1,j} - \sigma_{k,j}|.\] Note that \(\sigma_{k+1,j}\) is Gaussian with mean \(\sigma_{k,j}\) and variance bounded by \(M \eta n^{4 \delta}\) by . Therefore, by Lemma 29, \[\begin{align} \mathbb{E}[\mathbb{1}_{|\sigma_{k+1,j} - \sigma_{k,j}| \geqslant\eta^{-1/2} n^\alpha} (\sigma_{k+1,j} - \sigma_{k,j})^2] &\leqslant\frac{2M \eta n^{4 \delta}}{\sqrt{2\pi}}(M^{-1/2} \eta^{-1} n^{\alpha-\delta} + M^{1/2} \eta n^{\delta-\alpha}) e^{-M^{-1} \eta^{-1} n^{-2\delta} \eta^{-1} n^{2\alpha}} \\ &\leqslant 2 M^{3/2} n^{\alpha+3\delta}e^{-M^{-1} \eta^{-2} n^{2\alpha-2\delta}} . \end{align}\] Therefore, \[\begin{align} d_{W,2}(\tau,\tau_0)^2 &\leqslant\int_{|x| \geqslant\eta^{-1/2} n^\alpha} \left(x - \operatorname{proj}_{[-2^\ell,2^\ell]}(x)\right)^2\,d\tau(x) \notag\\ &\leqslant\frac{1}{n} \sum_{j=1}^n \mathbb{E}\left[|\sigma_{k+1,j} - \mathop{\mathrm{proj}}_{[-2^\ell,2^\ell]}(\sigma_{k+1,j})|^2\right] \notag\\ &\leqslant\frac{1}{n} \sum_{j=1}^n \mathbb{E}\left[ \mathbb{1}_{|\sigma_{k+1,j} - \sigma_{k,j}| \geqslant\eta^{-1/2} n^\alpha} (\sigma_{k+1,j} - \sigma_{k,j})^2\right] \notag\\ &\leqslant 2M^{3/2} n^{\alpha+3\delta} e^{-M^{-1} \eta^{-2} n^{2\alpha-2\delta}} \notag\\ &\leqslant M' n^{-\alpha},\label{eq:wass-tau-tau0} \end{align}\tag{68}\] where we choose \(M'\) such that \(M' \geqslant 2M^{3/2}n^{2\alpha+3\delta}e^{-M^{-1}\eta^{-2}n^{2\alpha-2\delta}}\) by choosing \(M' = 2M^{3/2}n_0e^{-M^{-1}n_0^{1/9}}\) for \(n_0\) solving \(0 = \frac{d}{dn_0}\left(n_0e^{-M^{-1}n_0^{1/9}}\right)\).

Now we proceed to estimate \(d_{W,1}(\mathop{\mathrm{emp}}(\sigma_{k+1}), \tau_0)\). Take \(f \in \mathsf{Lip}_1([-2^\ell,2^\ell])\), and extend \(f\) to an \(1\)-Lipschitz function on \(\mathbb{R}\) by setting \(f\) to be constant on \((-\infty,-2^\ell]\) and \([2^\ell,\infty)\), so that \(f \circ \mathop{\mathrm{proj}}_{[-2^\ell,2^\ell]} = f\). Consider \[F_f(Z_k) = \frac{1}{n} \sum_{j=1}^n f\left(\sigma_{k,j} + \eta^{1/2} (Q_k Z_k)_j \right)\] where \(Z_k\) is a standard Gaussian vector and recall from the proof of that the distribution of \(\sigma_{k,j}+\eta^{1/2}(Q_kZ_k)\) over the randomness of \(j\) and \(Z_k\) is equal to \(\mathop{{}\mathbb{E}}\left[\mathop{\mathrm{emp}}(\sigma_{k+1}) | A, \sigma_1, \dots, \sigma_k\right]\), so \(\mathop{{}\mathbb{E}}_{Z_k} [F_f(Z_k)] = \int f\,d\tau = \int (f \circ \mathop{\mathrm{proj}}_{[-2^\ell,2^\ell]})d\tau = \int f\,d\tau_0\). Moreover, \(F_f(Z_k)\) is an \(\eta^{1/2} \left\lVert{Q_k}\right\rVert /\sqrt{n}\)-Lipschitz function of \(Z_k\), since \[\begin{align} \frac{1}{n} \sum_{j=1}^n \left|f\left(\sigma_{k,j} + \eta^{1/2} (Q_k Z_k)_j \right) - f\left(\sigma_{k,j} + \eta^{1/2} (Q_k Z_k')_j \right)\right| &\leqslant\frac{1}{n} \eta^{1/2}\sum_{j=1}^n \left| (Q_k (Z_k-Z_k'))_j \right| \\&= \frac{\eta^{1/2}}{n} |Q_k (Z_k-Z_k')|_1 \leqslant\frac{\eta^{1/2}}{\sqrt{n}} \left\lVert{Q_k}\right\rVert\,|Z_k-Z_k'|_2 \,. \end{align}\] Now we apply the concentration estimate to the Lipschitz function \(F_f(Z_k)\) above, while noting that \(\left\lVert{Q_k}\right\rVert n^{-1/2} \leqslant M_5 n^{2\delta-1/2}\) by . By concentration of Lipschitz functions of Gaussians (i.e. with \(n=1\)), we have \[\left| F_f(Z_k) - \mathop{{}\mathbb{E}}_{Z_k} \left[F_f(Z_k)\right]\right| \leqslant\frac{1}{2^m}\] with probability at least \[1 - M_6 \exp \left( -M_7 n^{1-4\delta}2^{-2m}\eta^{-1} \right).\]

Choose \(m\) so that \(2^{-m} \leqslant\beta \eta^{1/2} n^{-2 \alpha} \leqslant 2^{-m+1}\). By and , we can estimate the \(L^1\) Wasserstein distance between measures supported in \([-2^\ell,2^\ell]\) up to an error of size \(1/2^m\) by testing only the \(1\)-Lipschitz functions \(f\) in some set \(\mathcal{F}\) satisfying \(|\mathcal{F}| = 2^{2^{\ell+m+1}}\). We use a union bound for the probability of error for each of these Lipschitz functions \(f\). This yields \[\begin{align} d_{W,1}(\mathop{\mathrm{emp}}(\sigma_{k+1}), \tau_0) &= \sup_{\left\lVert{f}\right\rVert_{\mathrm{Lip}}\leqslant 1}\left|\int f(d\mathop{\mathrm{emp}}(\sigma_{k+1}) - d\tau_0)\right| \\&\leqslant \frac{1}{2^m} + \sup_{f \in \mathcal{F}}\left|\int f(d\mathop{\mathrm{emp}}(\sigma_{k+1}) - d\tau_0)\right| \\&= \frac{1}{2^m} + \sup_{f \in \mathcal{F}}\left| F_f(Z_k) - \mathop{{}\mathbb{E}}_{Z_k} \left[F_f(Z_k)\right]\right| \\&\leqslant\frac{2}{2^m} \leqslant 2 \eta^{1/2} n^{-2\alpha} \end{align}\] with probability at least \[\label{eq:prob-lipschitz-function-union-bound} 1 - M_6 2^{2^{\ell+ m+1}} \exp \left( -M_7 n^{1-4\delta} 2^{-2m} \eta^{-1} \right),\tag{69}\] provided that \(\max_j |\sigma_{k+1,j}| \leqslant\eta^{-1/2} n^\alpha \leqslant 2^\ell\) which by happens with probability at least \[\label{eq:max-coordinate-event-prob} 1 - M_1 Kn \exp(-M_2 n^{2 \alpha-4\delta}).\tag{70}\] Hence, in this high-probability event, by Hölder’s inequality, \[d_{W,2}(\mathop{\mathrm{emp}}(\sigma_{k+1}),\tau_0) \leqslant 2^{\ell/2} d_{W,1}(\mathop{\mathrm{emp}}(\sigma_{k+1}),\tau_0)^{1/2} \leqslant M_8 \eta^{-1/4} n^{\alpha/2} \eta^{1/4} n^{-\alpha} = M_8 n^{-\alpha/2},\] which combines with by triangle inequality to obtain \[\label{eq:event-emp-close-to-exp} d_{W,2}(\mathop{\mathrm{emp}}(\sigma_{k+1}),\tau) \leqslant M_9 n^{-\alpha/2}.\tag{71}\]

It remains to evaluate the probability coming from concentration. By construction, \(2^{\ell} \leqslant 4 \eta^{-1/2} n^\alpha\) and \(2^{m} \leqslant 2\beta^{-1} \eta^{-1/2} n^{2 \alpha}\). Thus, \[2^{2^{\ell+m+1}} \leqslant M_{9} \exp\left(M_{10}\beta^{-1}\eta^{-1}n^{3\alpha}\right).\] Hence, \[\begin{align} M_6 2^{2^{\ell+ m+1}}&\exp \left( -M_7 n^{1-4\delta} 2^{-2m} \eta^{-1} \right) \\ &\leqslant M_6 M_{9} \exp\bigg(M_{10}\beta^{-1}\eta^{-1}n^{3\alpha} \bigg) \exp \left( -M_7 n^{1-4\delta} 2^{-2m}\eta^{-1} \right) \\ &\leqslant M_{11} \exp \left( -M_{12} \beta^2n^{1-4\delta-4 \alpha} +M_{10}\beta^{-1}\eta^{-1}n^{3\alpha} \right), \end{align}\] which, when combined with and , yields the final probability of the bounds and . ◻

Proof. By triangle inequality and making the conditioning in \(\mathop{{}\mathbb{E}}\left[\mathop{\mathrm{emp}}(\sigma_{k+1}) | A, \sigma_1, \dots, \sigma_k\right]\) notationally implicit for brevity, \[\begin{align} d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y^{\gamma}_{t_{k+1}})\right)^2 &\leqslant\left( d_{W,2}\left(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y^{\gamma}_{t_{k+1}})\right) + d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1})\right)\right)^2 \\ &= d_{W,2}\left(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y^{\gamma}_{t_{k+1}})\right)^2 \\ & \quad + 2 d_{W,2}\left(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y^{\gamma}_{t_{k+1}})\right) d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1})\right) \\ &\quad + d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1})\right)^2. \end{align}\] Assuming that \(d_{W,2}(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}),\operatorname{dist}(Y^{\gamma}_{t_{k+1}})) \leqslant 1\), we can bound \[\begin{gather} 2 d_{W,2}\left(\mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y^{\gamma}_{t_{k+1}})\right) d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1})\right) + d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \mathop{{}\mathbb{E}}\mathop{\mathrm{emp}}(\sigma_{k+1})\right)^2 \\ \leqslant M_1 n^{-\alpha/2} + M_2 n^{-\alpha}, \end{gather}\] using with \(\alpha = 1/9\). Combining this with using triangle inequality, we obtain the asserted estimate with probability \[1 - M_3\eta^{-1}n \exp \left( -M_4 n^{2/9-4\delta}\right) - M_5\exp\left(-M_6 n^{5/9-4\delta} + M_7 \beta^{-1} \eta^{-1} n^{3/9} \right).\] By our assumptions \(\beta \geqslant 1\) and \(\eta n^{1/90} \geqslant 1\), and hence \(\beta^{-1} \eta^{-1} n^{3/9} \leqslant n^{31/90}\). Since \(-M_6 n^{5/9-4\delta} + M_7 n^{31/90} - M_8 \leqslant-M_9n^{2/9-4\delta}\), we can absorb the \(M_5\exp\left(-M_6 n^{5/9-4\delta} + M_7 n^{31/90} \right)\) term into the \(M_3\eta^{-1}n\exp(-M_4 n^{2/9 - 4 \delta})\) term. ◻

Proof of . We induct over \(k = 0, \dots, k'-1\). Write \(\zeta_{n,\beta,\eta,\gamma} := M_2 \beta^4 \eta + M_3 n^{-\delta} + M_4 e^{10 \beta^2} \gamma^2 + M_5 \beta^{-2}\eta^{-1} n^{-1/18}\) and \(\Delta_k := d_{W,2}(\mathop{\mathrm{emp}}(\sigma_{k}), \operatorname{dist}(Y_{t_{k}}^\gamma))\). The inductive hypothesis will be that with probability at least \(1 - M_6 n(k-1)\eta^{-1} \exp \left( -M_7 n^{2/9-4\delta} \right)\), \[\label{eq:inductive-delta} \Delta_k^2 \leqslant\sum_{j=0}^{k-1} (1 + M_1 \eta \beta^2)^j \eta\beta^2 \cdot \zeta_{n,\beta,\eta,\gamma}\tag{72}\] and that the hypotheses of will hold for this value of \(k\) with \(\alpha = 1/9\).

Note that \(\Delta_0 = 0\) since \(\sigma_0 = 0\) and \(Y_0 = 0\), and furthermore the hypotheses of are vacuous at \(k=0\).

For the inductive step, combining the probability from the inductive hypothesis with the probability from puts us in an event with probability at least \(1 - M_6 nk\eta^{-1} \exp \left( -M_7 n^{2/9-4\delta} \right)\), so we can assume both bounds of hold. The first bound says that \[\Delta_{k+1}^2 - \Delta_k^2 \leqslant\eta \cdot \left[ M_1 \beta^2 \Delta_k^2 + M_2 \beta^6 \eta + M_3 \beta^2 n^{-\delta} + M_4 \beta^2 e^{10 \beta^2} \gamma^2 + M_5 \eta^{-1} n^{-1/18} \right],\] and hence by , \[\Delta_{k+1}^2 \leqslant(1 + M_1 \eta \beta^2) \Delta_k^2 + \eta\beta^2 \zeta_{n,\beta,\eta,\gamma} \leqslant\sum_{j=0}^{k} (1 + M_1 \eta \beta^2)^j \eta\beta^2 \cdot \zeta_{n,\beta,\eta,\gamma}\,,\] as required by for the next step of the induction.

The second bound of gives the first hypothesis of for the next step.

For the second hypothesis, note that \[\begin{align} \Delta_{k+1}^2 &\leqslant\sum_{j=0}^{k} (1 + M_1 \eta \beta^2)^j \eta\beta^2 \cdot \zeta_{n,\beta,\eta,\gamma} \notag\\ &= \frac{(1 + M_1 \eta \beta^2)^{k+1} - 1}{M_1 \eta \beta^2} \eta\beta^2 \cdot \zeta_{n,\beta,\eta,\gamma} \notag\\ \label{eq:SDE-inductive-hypothesis-exponential} &\leqslant M_1^{-1} \left(\exp( M_1 \beta^2 (k+1) \eta) - 1\right) \zeta_{n,\beta,\eta,\gamma}\,. \end{align}\tag{73}\] By the assumption in the theorem statement, an application of the arithmetic-geometric mean inequality, upper-bounding \((k+1) \eta\) by 1, and upper-bounding \((1 + e^{5\beta^2})^2\gamma^2\) by \(C_4^{-1}C_7 (\exp( C_4 \beta^2) - 1)e^{10\beta^2}\gamma^2\), \[\label{eq:32induction32hypothesis32for32all} 2\left( M_1^{-1} \left(\exp( M_1 \beta^2 (k+1) \eta) - 1\right) \zeta_{n,\beta,\eta,\gamma} \right)^{1/2} + (1 + e^{5\beta^2}) \gamma \leqslant\frac{1}{2 \sqrt{2} \beta}\,.\tag{74}\] The last two inequalities combine to give \[\label{eq:final-wasserstein-2-bound-loose} 2d_{W,2}\left(\mathop{\mathrm{emp}}(\sigma_{k+1}), \operatorname{dist}(Y_{t_{k+1}}^\gamma)\right) + (1 + e^{5 \beta^2}) \gamma \leqslant\frac{1}{2 \sqrt{2} \beta},\tag{75}\] which implies the second hypothesis of for the next step.

Finally, observe that the same induction that leads to also works when \(\Delta_k\) is taken instead to be \(d_{W,2}(\mathop{{}\mathbb{E}}\left[\mathop{\mathrm{emp}}(\sigma_{k+1}) | A, \sigma_1, \dots, \sigma_k\right], \operatorname{dist}(Y_{t_{k+1}}^\gamma))\), with the only difference being fewer applications of the triangle inequality and consequently fewer terms to upper-bound (alternatively, we may apply with ), so, invoking \(\beta \geqslant 1\), \[d_{W,2}\left(\mathop{{}\mathbb{E}}\left[\mathop{\mathrm{emp}}(\sigma_{k+1}) | A, \sigma_1, \dots, \sigma_k\right], \operatorname{dist}(Y^{\gamma}_{t_{k+1}})\right) \leqslant\frac{1}{2 \sqrt{2} \beta} \leqslant 1,\] which is the final assumption needed for , finishing the proof of the inductive step.

By , we obtain that for all \(k \in \{0,\dots,k'\}\), \[\begin{align} \Delta_k^2 &\leqslant M_1^{-1} \left(\exp( M_1 \beta^2 k' \eta) - 1\right) \zeta_{n,\beta,\eta,\gamma} \end{align}\] with probability at least \(1 - M_6 nk\eta^{-1} \exp \left( -M_7 n^{2/9-4\delta} \right)\), as required by the first conclusion of the theorem statement. The second conclusion is immediately implied by . ◻

Proof. Recall \(\Delta \sigma_k = \eta^{1/2} Q_k Z_k\). Note \[\mathop{{}\mathbb{E}}[\angles{2 \beta A_{\mathop{\mathrm{sym}}} \sigma_k - \partial_y \tilde{\Lambda}_{\gamma}(t_k,\sigma_k), \eta^{1/2} Q_k Z_k} \mid A, Z_0, \dots, Z_{k-1}] = 0\,,\] and the quantity in the expectation is a Lipschitz function of \(Z_k\) with Lipschitz norm bounded by \[\left( 2 \beta \left\lVert{A_{\mathop{\mathrm{sym}}}}\right\rVert + \max_{i \in [n]}|\partial_y \tilde{\Lambda}_{\gamma}(t_k,(\sigma_k)_i)| \right)|\sigma_k|_2 \eta^{1/2} \left\lVert{Q_k}\right\rVert.\] Recall \(2 \left\lVert{A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant 3\) since we are in the high probability event from . Furthermore, \(\left\lVert{Q_k}\right\rVert \leqslant M_1 n^{2\delta}\), which follows from  and . Lastly, it is apparent from that \(\Lambda(t,y)\) is an even function of \(y\), so \(\partial_y \Lambda(t,y)\) is an odd function, and this immediately yields that \(\partial_y \tilde{\Lambda}_{\gamma}(t,0) = 0\). Consequently, since \(\partial_{y,y} \tilde{\Lambda}_{\gamma} \leqslant 1/\gamma\) by , we have \[|\partial_y \tilde{\Lambda}_{\gamma}(t,y)| \leqslant\frac{1}{\gamma} |y|.\]

Hence, the Lipschitz norm can be bounded by \[M_1 \left( 3 \beta + \frac{1}{\gamma} \right) |\sigma_k|_2 \eta^{1/2} n^{2\delta}.\] Moreover, using , \[\begin{align} n^{-1/2} |\sigma_k|_2 = \left( \frac{1}{n}\sum_{j=1}^n \sigma_{k,j}^2\right)^{1/2}\!\! &{}\leqslant d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + \left\lVert{Y_{t_k}^\gamma}\right\rVert_{L^2} \\&{}\leqslant d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + t_k^{1/2} (1 + \sqrt{2} \beta (1 + e^{5 \beta^2 t_k}) \gamma). \end{align}\] Therefore, the Lipschitz norm can be bounded by \[\left( 3 \beta + \frac{1}{\gamma} \right) \left( M_2 + M_3\, d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + M_4 \beta e^{5 \beta^2} \gamma \right) \eta^{1/2} n^{1/2 + 2\delta}.\] Since we are in the high probability event from , we can assume that \[\left( M_2 + M_3\, d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + M_4 \beta e^{5 \beta^2} \gamma \right) \leqslant M_5.\] By the Gaussian concentration inequality for Lipschitz functions [49], we obtain the asserted error bound; here note that \((n^{2/3})^2 / (n^{1/2 + 2 \delta})^2 = n^{1/3 - 4 \delta}\). ◻

Proof. Recall that \[\angles{\Delta \sigma_k, \left(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))\right) \Delta \sigma_k} = \eta \angles{Z_k, Q_k \big(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))\big) Q_k Z_k}.\] Since \(Z_k\) is a standard Gaussian vector, \[\mathop{{}\mathbb{E}}\angles{\Delta \sigma_k, \left(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))\right) \Delta \sigma_k} = n \eta \operatorname{tr}_n\left[Q_k \left(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))\right) Q_k\right].\] For convenience, let \[R_k := \eta Q_k \left(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))\right) Q_k.\] By the Hanson-Wright inequality, \[\mathop{{}\mathbb{P}}\left(|\angles{Z_k, R_k Z_k} - \mathop{{}\mathbb{E}}\angles{Z_k, R_k Z_k}| > \zeta \right) \leqslant 2 \exp\left(-\min\left(\frac{\zeta^2}{16 n\left\lVert{R_k}\right\rVert_{2}^2}, \frac{\zeta}{4 \left\lVert{R_k}\right\rVert}\right) \right).\] Here we compute \(\left\lVert{R_k}\right\rVert_{2} \leqslant\left\lVert{R_k}\right\rVert\) and \[\begin{align} \left\lVert{R_k}\right\rVert &= \eta \left\lVert{Q_k \left(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j})) \right)Q_k}\right\rVert \\ &\leqslant\eta \left\lVert{2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))}\right\rVert \left\lVert{Q_k^2}\right\rVert \\ &\leqslant\eta \left( 3 \beta + \frac{1}{\gamma} \right) M_1 n^{4\delta}, \end{align}\] where we applied and the facts that \(\left\lVert{2 A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant 3\) and \(\partial_{y,y} \tilde{\Lambda}_{\gamma} \leqslant 1/\gamma\). Now we substitute \[\zeta = 4\eta \left( 3 \beta + \frac{1}{\gamma} \right) M_1 n^{2/3},\] so that \[\min\left(\frac{\zeta^2}{16n \left\lVert{R_k}\right\rVert_{2}^2}, \frac{\zeta}{4 \left\lVert{R_k}\right\rVert}\right) = \min \left( \frac{ n^{4/3}}{n^{1+4\delta}}, \frac{n^{2/3}}{n^{4 \delta}} \right) \geqslant n^{1/3-4\delta}. \qedhere\] ◻

Proof. Recall from that \[D_k = \sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))\] Therefore, we can write \[\begin{align} 2 \beta A_{\mathop{\mathrm{sym}}} &- \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j})) - 2 \beta^2 \operatorname{tr}_n(\operatorname{diag}(v(t_k,\sigma_k))) \\ &= \frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \left( 2 \beta A_{\mathop{\mathrm{sym}}} - D_k - 2 \beta^2 \operatorname{tr}_n(D_k^{-1}) \right) \\ & \quad + \left( 1 - \frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \right) 2 \beta A_{\mathop{\mathrm{sym}}} \\ &\quad + \left(1 - \frac{1}{2 \beta^2 \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2^2} \right) 2 \beta^2 \operatorname{tr}_n(\operatorname{diag}(v(t_k,\sigma_k))) \end{align}\] Thus, by the triangle inequality, \[\begin{align} \bigg \lVert \big(2 \beta A_{\mathop{\mathrm{sym}}} &- \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j})) - 2 \beta^2 \operatorname{tr}_n(\operatorname{diag}(v(t_k,\sigma_k)))\big) Q_k \bigg \rVert_2 \tag{82} \\ &\leqslant\frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \left\lVert{ (2 \beta A_{\mathop{\mathrm{sym}}} - D_k - 2 \beta^2 \operatorname{tr}(D_k^{-1})) Q_k }\right\rVert_2 \tag{83} \\ & \quad + \left| 1 - \frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \right| 2 \beta \left\lVert{A_{\mathop{\mathrm{sym}}} Q_k}\right\rVert_2 \tag{84} \\ &\quad + \left| \sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 - \frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \right| \sqrt{2} \beta \left\lVert{Q_k}\right\rVert_2, \tag{85} \end{align}\] where we used that \(\operatorname{tr}(\operatorname{diag}(v(t_k,\sigma_{k,j}))) \leqslant\left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2\). To estimate 83 , recall from that \[\left\lVert{ (2 \beta A_{\mathop{\mathrm{sym}}} - D_k - 2 \beta^2 \operatorname{tr}(D_k^{-1})) Q_k }\right\rVert_2 \leqslant M_1 \beta^2 n^{-\delta} + M_0(\beta+\gamma^{-1})n^{-1/4+2\delta}.\] To handle 84 and 85 , we recall from that \[\left\lVert{Q_k}\right\rVert_2 \leqslant M_2 \beta,\] and in addition, \(\left\lVert{2 A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant 3\). In order to bound 84 and 85 , we also need to estimate \(\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 - 1\); recall that in the proof of , and in particular in , we arranged that \[\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 \geqslant 1/2\] and \[\label{eq:32another32estimate32for32Hessian32error} \left| \sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 - 1 \right| \leqslant\sqrt{2} \beta \left( 2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k), \mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + (1 + e^{5 \beta^2}) \gamma \right).\tag{86}\] We therefore have that \[\label{eq:32another32estimate32for32Hessian32error322} \left| 1 - \frac{1}{(\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2)} \right| \leqslant 2 \cdot \sqrt{2} \beta \left( 2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k), \mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + (1 + e^{5 \beta^2}) \gamma \right),\tag{87}\] which we will substitute into 84 . Similarly, to estimate 85 , we use that \[\left| \sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 - \frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \right| \leqslant\left| \sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2 - 1 \right| + \left| 1 - \frac{1}{\sqrt{2} \beta \left\lVert{\operatorname{diag}(v(t_k,\sigma_{k,j}))}\right\rVert_2} \right|,\] which can then be estimated by 86 and 87 . Substituting all these estimates into 83 - 85 , we obtain the following bound for 82 : \[\begin{align} \bigg \lVert \big(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j})) - 2 \beta^2 \operatorname{tr}_n(\operatorname{diag}(v(t_k,\sigma_k)))\big) Q_k \bigg \rVert_2 &\leqslant M_3 \beta^2 n^{-\delta} + M_3\beta(\beta+\gamma^{-1}) n^{-1/4+2\delta} +\\ &M_4 \beta^3 \left( 2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k), \mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + (1 + e^{5 \beta^2}) \gamma \right). \end{align}\] This in turn implies that \[\begin{align} \operatorname{tr}_n\big[Q_k\big(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j})) - &2 \beta^2 \operatorname{tr}_n(\operatorname{diag}(v(t_k,\sigma_k)))\big) Q_k\big] \leqslant M_5\beta^3 n^{-\delta} + M_5\beta^2(\beta+\gamma^{-1}) n^{-1/4+2\delta} + \\ &\qquad\qquad\qquad M_6 \beta^4 \left( 2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k), \mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + (1 + e^{5 \beta^2}) \gamma \right). \end{align}\] Finally, we write \[\begin{align} &\operatorname{tr}_n[Q_k(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j}))) Q_k] - 2\beta^2\operatorname{tr}_n[\operatorname{diag}(v(t_k,\sigma_{k,j}))] = \\ &\operatorname{tr}_n\big[Q_k\big(2 \beta A_{\mathop{\mathrm{sym}}} - \operatorname{diag}(\partial_{y,y} \tilde{\Lambda}_{\gamma}(t_k,\sigma_{k,j})) - 2 \beta^2 \operatorname{tr}_n(\operatorname{diag}(v(t_k,\sigma_k)))\big) Q_k\big] + 2\beta^2(\operatorname{tr}_n[Q_k^2] - 1) \operatorname{tr}_n[\operatorname{diag}(v(t_k,\sigma_{k,j}))], \end{align}\] and recall from that \(|\operatorname{tr}_n[Q_k^2] - 1| \leqslant M_7 \beta^2 n^{-\delta}\). Since we already have the error term \(M_5 \beta^3 n^{-\delta}\), this new error can be combined with the previous one up to changing constants. ◻

Proof. Recall that \(|x|_r \leqslant|x|_p\) for every \(1 \leqslant p\leqslant r\). Therefore, \[|x|_3 = \left( \sum_{j=1}^n |x_j|^3 \right)^{1/3} \leqslant\left( \sum_{j=1}^n |x_j|^2 \right)^{1/2} = |x|_2\,.\] Consequently, \(f(\Delta \sigma_k) = \left( \sum_{j=1}^n |(\Delta \sigma_k)_j|^3 \right)^{1/3}\) is a \(1\)-Lipschitz function of \(\Delta \sigma_k\). Moreover, conditioned on \(A\) and \(Z_0\), …, \(Z_{k-1}\), the variable \(\Delta \sigma_k\) is Gaussian with covariance \(\eta Q_k^2\). By the concentration inequality for Lipschitz functions of Gaussian random variables [49], \[\label{eq:3-norm-remainder} \mathop{{}\mathbb{P}}\left(\left|f(\Delta \sigma_k) - \mathop{{}\mathbb{E}}\left[f(\Delta \sigma_k)\right]\right| \geqslant\eta^{1/2} n^{1/3}\right) \leqslant\exp\left(-\frac{n^{2/3}}{2 \left\lVert{Q_k^2}\right\rVert}\right) \leqslant\exp(-M_1 n^{2/3-4\delta}).\tag{88}\] As \(y = z^{1/3}\) is concave for \(z \in \mathbb{R}_{\geqslant 0}\), Jensen’s inequality implies \[\begin{align} \mathop{{}\mathbb{E}}f(\Delta \sigma_k) &= \mathop{{}\mathbb{E}}\left( \sum_{j=1}^n |(\Delta \sigma_k)_j|^3 \right)^{1/3} \\ &\leqslant\left( \mathop{{}\mathbb{E}}\sum_{j=1}^n |(\Delta \sigma_k)_j|^3 \right)^{1/3}\,. \end{align}\] Since \((\Delta \sigma_k)_i \sim \mathcal{N}\left(0, \eta(Q_k^2)_{i,i}\right)\), \[\mathop{{}\mathbb{E}}|\Delta \sigma_i|^3 = M_2 (Q_k^2)_{i,i}^{3/2}\eta^{3/2}\] for some constant \(M_2\). Thus, \[\begin{align} \mathop{{}\mathbb{E}}\left[f(\Delta \sigma_k)\right] &\leqslant M^{1/3}_2 \mathsf{Tr}_n(E_{\mathcal{D}_n}[\eta Q_k^2]^{3/2})^{1/3}\\ &= M_2^{1/3} n^{1/3} \eta^{1/2} \operatorname{tr}_n(E_{\mathcal{D}_n}[Q_k^2]^{3/2})^{1/3} \\ &\leqslant M_2^{1/3} n^{1/3} \eta^{1/2} \operatorname{tr}_n(E_{\mathcal{D}_n}[Q_k^2]^2)^{1/4} \\ &\leqslant M_3 n^{1/3} \eta^{1/2} \beta^{1/2}, \end{align}\] where the last inequality follows from and the assumed application of to \(Z_0, \dots, Z_{k-1}\). Therefore, by , \[\mathop{{}\mathbb{P}}\left(f(\Delta \sigma_k) \geqslant M_3 n^{1/3} \beta^{1/2}\eta^{1/2}\right) \leqslant\exp(-M_1 n^{2/3 - 4 \delta}).\] It follows that \[\sum_{i=1}^n |\Delta \sigma_i|^3 \leqslant M_4 n \beta^{3/2}\eta^{3/2}\,.\] with probability at least \[1 - \exp(-M_1 n^{2/3 - 4 \delta}).\] in the Gaussian vector \(Z_k\), conditioning on the vectors \(Z_0\), …, \(Z_{k-1}\) and assuming that they fall under the high probability event in . ◻

Proof. Let \(\Sigma\) be a random variable with distribution \(\mathop{\mathrm{emp}}(\sigma_{k+1})\) and let \(Y_t^\gamma\) be the stochastic process defined earlier. Consider an optimal coupling of \(\Sigma\) and \(Y_{t_{k+1}}^\gamma\) on some probability space. Recall that \(\mathop{\mathrm{id}}- \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,\cdot)\) is \(1\)-Lipschitz. Therefore, \[\begin{align} \left\lVert{[\Sigma - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,\Sigma)] - [Y_{t_{k+1}}^\gamma - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t, Y_{t_{k+1}}^\gamma)]}\right\rVert_{L^2} &\leqslant\left\lVert{\Sigma - Y_{t_{k+1}}^\gamma}\right\rVert_{L^2} \\ &= d_{W,2}(\operatorname{emp}(\sigma_{k+1}), \mathop{\mathrm{dist}}(Y_{t_{k+1}}^\gamma)). \end{align}\] Meanwhile, by , \[\left\lVert{[Y_{t_{k+1}}^\gamma - \gamma \partial_y \tilde{\Lambda}_{\gamma}(t, Y_{t_{k+1}}^\gamma)] - Y_{t_{k+1}}}\right\rVert_{L^2} \leqslant 5^{-1/2} e^{5 \beta^2} \gamma.\] Furthermore, from the proof of  in the case that \(\gamma = 0\), \[\left\lVert{Y_{t_{k+1}} - Y_t}\right\rVert_{L^2} \leqslant 2\beta\sqrt{\eta}\,.\] Finally, for any \(t \in [0,q^*_\beta)\), [9] implies that \(\left\lVert{Y_t}\right\rVert_{L^2} = t^{1/2}\). Thus, combining these estimates with the triangle inequality yields, \[\begin{align} \left| \left( \frac{1}{n} \sum_{j=1}^n (\sigma_{k+1,j} - \gamma\partial_y \tilde{\Lambda}_{\gamma}(t, \sigma_{k+1,j}))^2 \right)^{1/2} - t^{1/2} \right| &\leqslant\left\lVert{\Sigma - Y_t}\right\rVert_{L^2} \\ &\leqslant d_{W,2}(\operatorname{emp}(\sigma_{k+1}), \mathop{\mathrm{dist}}(Y_{t_{k+1}}^\gamma)) + 5^{-1/2} e^{5 \beta^2} \gamma + 2\beta \eta^{1/2}. \end{align}\] Now writing temporarily \(s = \frac{1}{n} \sum_{j=1}^n (\sigma_{k+1,j} - \gamma\partial_y \tilde{\Lambda}_{\gamma}(t, \sigma_{k+1,j}))^2\), we have \[\begin{align} |s - t| &= |s^{1/2} - t^{1/2}|(s^{1/2} + t^{1/2}) \\ &\leqslant|s^{1/2} - t^{1/2}|(t^{1/2} + |s^{1/2} - t^{1/2}| + t^{1/2}) \\ &\leqslant|s^{1/2} - t^{1/2}|(2 + |s^{1/2} - t^{1/2}|) \end{align}\] since \(t \leqslant 1\). Furthermore, if the assumptions of the theorem are satisfied, then \(d_{W,2}(\operatorname{emp}(\sigma_{k+1}), \mathop{\mathrm{dist}}(Y_{t_{k+1}}^\gamma)) + 5^{-1/2} e^{5 \beta^2} \gamma + 2 \beta \eta^{1/2}\) is bounded by a constant \(M\), so we can simply estimate this by \(|s - t| \leqslant M |s^{1/2} - t^{1/2}|\). ◻

Proof. Note that \(F_\mu(t) \leqslant 1\) and apply the previous lemma to estimate \(|\frac{1}{n} \sum_{j=1}^n ((\mathop{\mathrm{id}}- \gamma \partial_y \tilde{\Lambda}_{\gamma}(t,\cdot))(\sigma_{k+1,j}))^2 - t|\). ◻

Proof. We write \[\eta v(t_k,\sigma_k) - \int_{t_k}^{t_{k+1}} v(t,\sigma_{k+1})\,dt = \left( \eta v(t_k,\sigma_k) - \eta v(t_{k+1},\sigma_{k+1}) \right) + \left( \eta v(t_{k+1},\sigma_{k+1}) - \int_{t_k}^{t_{k+1}} v(t,\sigma_{k+1})\,dt \right)\] The first term telescopes when we sum over \(k\), that is, \[\left| \sum_{k=0}^{K-1} (v(t_k,\sigma_k) - v(t_{k+1},\sigma_{k+1})) \right| = |v(0,0) - v(t_K, \sigma_K)| \leqslant 1\] since \(\gamma \leqslant v \leqslant 1 + \gamma\) by . After multiplying by \(\beta^2 \eta\) and summing over \(j \in [n]\), the final contribution is \(\beta^2 \eta n \leqslant\beta^4 \eta n\).

To estimate the second term, recall that by (4), \[|v(t_{k+1},\sigma_{k+1}) - v(t,\sigma_{k+1})| \leqslant 18 \beta^2 (t_{k+1} - t).\] Integrating from \(t_k\) to \(t_{k+1}\) yields \[\left| \eta v(t_{k+1},\sigma_{k+1}) - \int_{t_k}^{t_{k+1}} v(t,\sigma_{k+1})\,dt \right| \leqslant 9 \beta^2 \eta^2.\] After summing over \(j\) and multiplying by \(\beta^2\), we obtain \[\left| \beta^2 \sum_{j=1}^n \eta v(t_{k+1},(\sigma_{k+1})_j) - \beta^2 \sum_{j=1}^n \int_{t_k}^{t_{k+1}} v(t,(\sigma_{k+1})_j)\,dt \right| \leqslant 9 \beta^4 \eta^2 n.\] Finally, summing over \(k\) gives a final contribution of \(9 \beta^4 (K \eta) \eta n \leqslant 9 \beta^4 \eta n\). ◻

Proof. We take the Taylor expansion in 76 - 81 and apply the bounds for each individual terms that we have proved, namely:

• 76 is estimated by ,

• 77 is estimated by ,

• 78 is estimated by ,

• 79 is estimated by .

Hence, assuming we are in the high probability events described in Theorem 27 and in each of those lemmas, we have \[\begin{align} \operatorname{obj}(t_{k+1}, \sigma_{k+1}) &- \operatorname{obj}(t_k,\sigma_k) \\ \geqslant&-\,n\eta \cdot M_1 \left( 3 \beta + \gamma^{-1} \right) \eta^{-1/2} n^{-1/3} \tag{89} \\ &- n\eta \cdot \biggl( M_2(3 \beta + \gamma^{-1}) \beta^2 n^{-1/3} + M_3 \beta^3 n^{-\delta} + M_4 \beta^4 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + M_5 e^{5 \beta^2} \beta^4 \gamma \biggr) \tag{90} \\ &- n\eta \cdot M_2\beta^2(\beta + \gamma^{-1})n^{-1/4+2\delta} \nonumber\\ &- n\eta \cdot M_6 \beta^{3/2} \gamma^{-2}\eta^{1/2} \tag{91} \\ &- n \eta \cdot \left[ M_7 \beta^2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_{k+1}), \mathop{\mathrm{dist}}(Y_{t_{k+1}}^\gamma)) + M_8 \beta^2 e^{5 \beta^2} \gamma + M_9 \beta^3 \eta^{1/2} \right] \tag{92} \\ & + \beta^2 \sum_{j=1}^n \eta v(t_k,\sigma_{k,j}) - \beta^2 \sum_{j=1}^n \int_{t_k}^{t_{k+1}} v(t,\sigma_{k+1,j})\,dt \tag{93} \\ &- n\eta \cdot \beta^2 \gamma \tag{94}\,, \end{align}\] where we have left 93 alone in order to apply telescoping later. We combine the remaining errors 89 - 92 and 81 and throw away terms that are dominated by other terms in the expansion, and we thus obtain: \[\begin{align} n \eta \cdot \biggl( M_{10} \left( 3 \beta + \gamma^{-1} \right) \eta^{-1/2} (n^{-1/3}+n^{-1/4+2\delta})& + M_{11} \beta^3 \gamma^{-2} \eta^{1/2} + M_{12} \beta^3 n^{-\delta} \\ &+ M_{13} \beta^2 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) + M_{13} \beta^4 e^{5 \beta^2} \gamma \biggr). \end{align}\] Then we recall from that \[\begin{align} d_{W,2}(\mathop{\mathrm{emp}}(\sigma_k),\mathop{\mathrm{dist}}(Y_{t_k}^\gamma)) &\leqslant\exp( M_{14} \beta^2) \left[ M_{15} \beta^4 \eta + M_{16} n^{-\delta} + M_{17} e^{10 \beta^2} \gamma^2 + M_{18} \beta^{-2} \eta^{-1} n^{-1/18} \right]^{1/2} \\ &\leqslant\exp( M_{14} \beta^2) \left( M_{19} \beta^2 \eta^{1/2} + M_{20} n^{-\delta/2} + M_{21} e^{5 \beta^2} \gamma + M_{21} \beta^{-1} \eta^{-1/2} n^{-1/36} \right). \end{align}\] Hence, the errors from 89 - 92 and 81 can be bounded by \[\label{eq:32most32Taylor32terms} n \eta \cdot e^{M_{22} \beta^2} \left( M_{23} \gamma^{-1} \eta^{-1/2} n^{-1/36} + M_{24} \gamma^{-2} \eta^{1/2} + M_{25} n^{-\delta/2} + M_{26} \gamma \right).\tag{95}\] Finally, we sum the error for \(k = 0\), …, \(K-1\). Hence, the \(n \eta\) in front of 95 becomes \(n K \eta \leqslant n\). Meanwhile, the summation over \(k\) of 93 is estimated by as smaller than \(9 \beta^4 \eta n\). Since we already have terms of the form \(n \exp(M \beta^2) \gamma^{-2} \eta^{1/2}\), this additional error can be absorbed by changing the constants. Therefore, \[\operatorname{obj}(t_K, \sigma_K) - \operatorname{obj}(t_0,\sigma_0) \geqslant-n \cdot e^{M_{22} \beta^2} \left( M_{23} \gamma^{-1} \eta^{-1/2} n^{-1/36} + M_{27} \gamma^{-2} \eta^{1/2} + M_{25} n^{-\delta/2} + M_{26} \gamma \right).\]

It remains to estimate the probability of failure. We take a union bound over the errors in each step that arise both from the proof of and from the arguments in this section. In , , , and , the probabilities are all bounded by \(M_{27} \exp(-M_{28} n^{1/3 - 4 \delta})\), assuming that \(Z_0\), …, \(Z_{k-1}\) are chosen already from the high probability events in . We take a union bound over the steps, where the number of terms is bounded by \(\eta^{-1}\), for a total probability of \(M_{27}\eta^{-1}\exp(-M_{28} n^{1/3 - 4 \delta})\). Meanwhile, the probabilities of error from are bounded by \(M_{29} n\eta^{-2}\exp(-M_{30} n^{2/9-4\delta})\), and so can combine these error estimates together at the cost of changing the constants. ◻

Proof.  

Unwinding the objective function.↩︎

By the definition of \(\mathop{\mathrm{obj}}\), \[\beta \angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} = \mathop{\mathrm{obj}}(q_\beta^*,\sigma_K) - \mathop{\mathrm{obj}}(0,0) + \sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*,\sigma_{K,j}) - n \Lambda(0,0) - n \beta^2 \int_0^{q_\beta^*} t F_\mu(t)\,dt.\] Thus, substituting \(\mathcal{E}(\beta)\) in , we get \[\beta \angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} = \beta \mathcal{E}(\beta)n + \mathop{\mathrm{obj}}(q_\beta^*,\sigma_K) - \mathop{\mathrm{obj}}(0,0) + \sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*,\sigma_{K,j}) - n \mathop{{}\mathbb{E}}\Lambda(q_\beta^*,Y_{q_\beta^*}).\] Recall that \(t_0 = 0\), \(\sigma_0 = 0\), and \(t_K = q_\beta^*\), and hence gives us a lower bound for \(\mathop{\mathrm{obj}}(q_\beta^*,\sigma_K) - \mathop{\mathrm{obj}}(0,0)\). It thus remains to estimate the approximation error \(\sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*,\sigma_{K,j}) - n \mathop{{}\mathbb{E}}\Lambda(q_\beta^*,Y_{q_\beta^*})\) for the entropy function, and then to perform a truncation to obtain a vector \(\tilde{\sigma} \in \{-1,1\}^n\) from \(\sigma_K\).

Approximation error for entropy.↩︎

We now use the SDE and regularity analysis from §2 to estimate \(\sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*, (\sigma_K)_j)\). Let \(\Sigma\) be a random variable with distribution \(\mathop{\mathrm{emp}}(\sigma_K)\), so that \[\frac{1}{n} \sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*, (\sigma_K)_j) = \mathop{{}\mathbb{E}}\tilde{\Lambda}_{\gamma}(q_\beta^*, \Sigma).\] Assume that \(\Sigma\) is on the same probability space as the processes \(Y_t\) and \(Y_t^\gamma\) such that \(\Sigma\) and \(Y_{q_\beta^*}\) are optimally coupled, that is, \(\left\lVert{\Sigma - Y_{q_\beta^*}}\right\rVert_{L^2} = d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K),\mathop{\mathrm{dist}}(Y_{q_\beta^*}))\). Let \(f: \mathbb{R}\to [-1,1]\) be the truncation \(f(y) = \mathop{\mathrm{sgn}}(y) \min(1, |y|)\). Since \(\tilde{\Lambda}_{\gamma}(t,y)\) is an increasing function of \(|y|\), we have \[\tilde{\Lambda}_{\gamma}(q_\beta^*, \Sigma) \geqslant\tilde{\Lambda}_{\gamma}(q_\beta^*, f(\Sigma)) \geqslant\Lambda(q_\beta^*, f(\Sigma)) - (1 + 4 \beta^2) (2 \beta^2 \gamma)^{4 \beta^2/(1 + 4 \beta^2)},\] where the second estimate follows from . Furthermore, by , \[\begin{align} \mathop{{}\mathbb{E}}|\Lambda(q_\beta^*, f(\Sigma)) - \Lambda(q_\beta^*, Y_{q_\beta^*})| &\leqslant(1 + 8 \beta^2) \mathop{{}\mathbb{E}}\left| \frac{f(\Sigma) - Y_{q_\beta^*}}{2} \right|^{8\beta^2 / (1 + 8 \beta^2)} \\ &\leqslant(1 + 8 \beta^2) \left( \frac{\left\lVert{f(\Sigma) - Y_{q_\beta^*}}\right\rVert_{L^1}}{2} \right)^{8\beta^2 / (1 + 8 \beta^2)}, \end{align}\] where the last estimate follows from Hölder’s inequality. Finally, note that since \(Y_{q_\beta^*} \in [-1,1]\), \[\begin{align} \left\lVert{f(\Sigma) - Y_{q_\beta^*}}\right\rVert_{L^1} &\leqslant\left\lVert{\Sigma - Y_{q_\beta^*}}\right\rVert_{L^1} \leqslant\left\lVert{\Sigma - Y_{q_\beta^*}}\right\rVert_{L^2} \\ &= d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K),\mathop{\mathrm{dist}}(Y_{q_\beta^*})) \\ &\leqslant d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \left\lVert{Y_{q_\beta^*}^\gamma - Y_{q_\beta^*}}\right\rVert_{L^2} \\ &\leqslant_{\text{\prettyref{lem:sde-closeness}}} d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma. \end{align}\] Thus, \[\begin{gather} \label{eq:32entropy32approximation32error} \sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*, (\sigma_K)_j) - n \mathop{{}\mathbb{E}}\Lambda(q_\beta^*, Y_{q^*_\beta}) \\ \geqslant-n \left( (1 + 8\beta^2) \left( d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma \right)^{8\beta^2 / (1 + 8 \beta^2)} + (1 + 4 \beta^2) (2 \beta^2 \gamma)^{4 \beta^2/(1 + 4 \beta^2)} \right). \end{gather}\tag{96}\]

Truncation error.↩︎

Recall we set \(\tilde{\sigma}_j = f(\sigma_{K,j})\) where \(f(y) = \mathop{\mathrm{sgn}}(y) \min(|y|,1)\). We will now estimate \(|\sigma_K - \tilde{\sigma}|_2\). Note that \[\frac{1}{n} |\sigma_K - \tilde{\sigma}|_2^2 = \mathop{{}\mathbb{E}}|\Sigma - f(\Sigma)|^2,\] where \(\Sigma\) is a random variable with distribution \(\mathop{\mathrm{emp}}(\sigma_K)\) as above. Since \(Y_{q_\beta^*} \in [-1,1]\), we have \(|\Sigma - f(\Sigma)| \leqslant|\Sigma - Y_{q_\beta^*}|\), so that, by , \[\begin{align} n^{-1/2} |\sigma_K - \tilde{\sigma}|_2 &= \left\lVert{\Sigma - f(\Sigma)}\right\rVert_{L^2} \\ &\leqslant\left\lVert{\Sigma - Y_{q_\beta^*}}\right\rVert_{L^2} \\ &\leqslant d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*})) \\ &\leqslant d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma. \end{align}\] Since \(\left\lVert{A_{\mathop{\mathrm{sym}}}}\right\rVert \leqslant 3\) in our given sample, we conclude that \[\begin{align} \angles{\tilde{\sigma}, A_{\mathop{\mathrm{sym}}} \tilde{\sigma}} &\geqslant\angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} + 2 \angles{\tilde{\sigma}, A_{\mathop{\mathrm{sym}}} (\tilde{\sigma} - \sigma_K)} - \angles{(\tilde{\sigma} - \sigma_K), A_{\mathop{\mathrm{sym}}}(\tilde{\sigma} - \sigma_K)} \\ &\geqslant\angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} - 6 |\tilde{\sigma}|_2 |\tilde{\sigma} - \sigma_K|_2 - 3 |\tilde{\sigma} - \sigma_K|_2^2 \\ &\geqslant\angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} - 6n \left\lVert{\Sigma - f(\Sigma)}\right\rVert_{L^2} - 3n \left\lVert{\Sigma - f(\Sigma)}\right\rVert_{L^2}^2. \end{align}\] In the high probability event of , \(d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma\) will be bounded by a constant, and hence \(\left\lVert{\Sigma - f(\Sigma)}\right\rVert_{L^2}^2 \leqslant M_1 \left\lVert{\Sigma - f(\Sigma)}\right\rVert_{L^2}\). Thus, \[\label{eq:32rounding32approximation32error} \angles{\tilde{\sigma}, A_{\mathop{\mathrm{sym}}} \tilde{\sigma}} \geqslant\angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} - nM_2 \left(d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma \right).\tag{97}\]

Putting the estimates together.↩︎

We write \[\begin{align} \beta \angles{\tilde{\sigma}, A_{\mathop{\mathrm{sym}}} \tilde{\sigma}} - \beta \mathcal{E}(\beta)n &= \beta \angles{\tilde{\sigma}, A_{\mathop{\mathrm{sym}}} \tilde{\sigma}} - \beta \angles{\sigma_K, A_{\mathop{\mathrm{sym}}} \sigma_K} \\ &\quad + \sum_{j=1}^n \tilde{\Lambda}_{\gamma}(q_\beta^*, \sigma_{K,j}) - n \mathop{{}\mathbb{E}}[\Lambda(q_\beta^*,Y_{q_\beta^*})] \\ &\quad +\mathop{\mathrm{obj}}(q_\beta^*,\sigma_K) - \mathop{\mathrm{obj}}(0,0). \end{align}\] On the right-hand side, the first line is estimated by 97 , the second line is estimated by 96 , and the third line is estimated by , which yields \[\begin{align} \beta \angles{\tilde{\sigma}, A_{\mathop{\mathrm{sym}}} \tilde{\sigma}} - \beta \mathcal{E}(\beta)n &\geqslant-n M_2 \beta \left( d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma \right) \\ &\quad -n M_3 \beta^2 \left( \left( d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma \right)^{8\beta^2 / (1 + 8 \beta^2)} + (2 \beta^2 \gamma)^{4 \beta^2/(1 + 4 \beta^2)} \right) \\ &\quad -n \cdot e^{C_4 \beta^2} \left( M_4 \gamma^{-1} \eta^{-1/2} n^{-1/36} + M_5 \gamma^{-2} \eta^{1/2} + M_6 n^{-\delta/2} + M_7 \gamma \right), \end{align}\] where we have estimated \((1 + \beta^2)^{8\beta^2 / (1 + 8 \beta^2)}\) by a constant times \(\beta^2\). To combine these estimates conveniently, note that the \(d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K),\mathop{\mathrm{dist}}(Y_{q_\beta^*}^{\gamma}))\) and \(\gamma\) terms on the first line can be absorbed into the estimate on the third line from , in the same way as we did in the proof of that theorem. For the second line, we write \[\left( d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma)) + \sqrt{2} e^{5 \beta^2} \gamma \right)^{8\beta^2 / (1 + 8 \beta^2)} \leqslant M_8 d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K), \mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma))^{8\beta^2 / (1 + 8 \beta^2)} + M_9 (e^{5 \beta^2} \gamma)^{8\beta^2 / (1 + 8 \beta^2)}.\] Since \(\gamma \leqslant 1\), and since \(4 \beta^2 / (1 + 4 \beta^2) \leqslant 8\beta^2/(1 + 8 \beta^2)\), we can thus write \[M_9 (e^{5 \beta^2} \gamma)^{8\beta^2 / (1 + 8 \beta^2)} + (2 \beta^2 \gamma)^{4 \beta^2/(1 + 4 \beta^2)} \leqslant e^{M_{10} \beta^2} \gamma^{4 \beta^2/(1 + 4 \beta^2)}.\] We finally combine this with the \(\gamma\) terms on the third line, and altogether the error is bounded by \[\begin{gather} n \biggl( M_{11} d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K),\mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma))^{8\beta^2/(1 + 8 \beta^2)} \\ + e^{C_4 \beta^2} \left( M_4 \gamma^{-1} \eta^{-1/2} n^{-1/36} + M_5 \gamma^{-2} \eta^{1/2} + M_6 n^{-\delta/2} + M_7 \gamma^{4 \beta^2/(1+4\beta^2)} \right) \biggr). \end{gather}\] Then we estimate \(d_{W,2}(\mathop{\mathrm{emp}}(\sigma_K),\mathop{\mathrm{dist}}(Y_{q_\beta^*}^\gamma))\) by and combine terms by similar reasoning as did before. This yields the estimate asserted in the theorem after dividing by \(\beta\). ◻

Proof. We now invoke  in conjunction with a precise set of parameterizations for \(\beta\), \(\eta\) and \(\gamma\) as functions of \(\varepsilon\in (0,1/2)\) that give the desired approximation to the energy, with high probability under the choice of input and the algorithm’s internal randomness. Direct computation shows that for large enough \(C\), our assumptions on \(\beta\), \(\eta\), \(\gamma\), and \(n\) imply the hypothesis 59 in Theorem 27, so that we can apply Theorem 31.

By  with our choices of \(\beta\), \(\eta\), and \(\gamma\), \[\frac{1}{n}H(\tilde{\sigma}) \geqslant\mathcal{E}(\beta) - O(\varepsilon^{2}) - O_{\varepsilon}(n^{-\alpha}).\] Set \(\sigma^* = \mathsf{round}(\tilde{\sigma})\) with \(\mathsf{round}(\cdot)\) defined as in . Then \[\frac{1}{n}H(\sigma^*) \geqslant_{\text{w.h.p. as in \prettyref{prop:rounding-energy}}} \frac{1}{n}H(\tilde{\sigma}) - \frac{O(1)}{n^\alpha}\,.\]

Putting the previous two estimates together with \(\alpha = \min\left(\delta/4,1/24\right)\) gives \[\begin{align} \frac{1}{n}H(\sigma^*) \geqslant\mathcal{E}(\beta) - \frac{O(1)}{n^\alpha} - O(\varepsilon^{2}) - O_{\varepsilon}(n^{-\alpha})\,. \end{align}\] Using the elementary log-sum-exp bound \[\frac{\mathcal{P}_{\beta}}{\beta} \leqslant\lim_{n \to \infty}\mathop{{}\mathbb{E}}\frac{1}{n}\max_{\sigma\in\{\pm1\}^n}H(\sigma) + \frac{\log 2}{\beta}\] together with [9], a simple integration-by-parts in conjunction with [9] (after adjusting for our normalization of the Hamiltonian) and \(\beta = \frac{10}{\varepsilon}\) so that \((2 \log 2 + 1/2)\varepsilon/10 < \varepsilon/5\) imply that, under fRSB, \[\mathcal{E}(\beta) = 2\beta\left(\int_0^{q^*_\beta}\left(\int_t^1 F_\mu(s)ds\right)dt\right) \geqslant\frac{\mathcal{P}_\beta}{\beta} - \frac{\varepsilon}{5}.\] Combining this with the previous inequality yields our first conclusion: \[\frac{1}{n}H(\sigma^*) \geqslant\frac{\mathcal{P}_\beta}{\beta} - \frac{\varepsilon}{5} - O(\varepsilon^2) - O_{\varepsilon}(n^{-\alpha}).\]

Then with the elementary log-sum-exp bound \[\frac{\mathcal{P}_{\beta}}{\beta} \geqslant\lim_{n \to \infty}\mathop{{}\mathbb{E}}\frac{1}{n}\max_{\sigma\in\{\pm1\}^n}H(\sigma) = \lim_{\beta \to \infty} \frac{\mathcal{P}_{\beta}}{\beta}.\] combined with  and the concentration of the ground state energy [49], we ultimately obtain with high probability \[\frac{1}{n}H(\sigma^*) \geqslant\frac{1}{n}\max_{\sigma \in \{-1,1\}^n} H(\sigma) - \frac{\varepsilon}{5} - O(\varepsilon^2) - o_n(1).\] By using the simple bound \(\lim_{n\to\infty}\mathop{{}\mathbb{E}}\frac{1}{n}\max_{\sigma \in \{-1,1\}^n} H(\sigma) \geqslant 1/2\) from  [9] (again, after adjusting for our normalization of the Hamiltonian), we obtain the multiplicative form \[H(\sigma^*)\geqslant \left(1-\frac{\varepsilon}{2}-O(\varepsilon^2)-o_n(1)\right) \max_{\sigma\in\{\pm1\}^n}H(\sigma). \qedhere\] ◻

Proof. Fix a transport plan \(\pi\) between \(\mu\) and \(\nu\). Then we have by Hölder’s inequality that \[\left( \mathbb{E}_{(x,y) \sim \pi} d(x,y)^p \right)^{1/p} \leqslant\left( \mathbb{E}_{(x,y) \sim \pi} d(x,y)^q \right)^{1/q}.\] Hence, taking the infimum over \(\pi\) proves the first claim. Similarly, if \(\mu\) and \(\nu\) are supported in a set of diameter \(K\), then \[\mathbb{E}_{(x,y) \sim \pi} d(x,y)^q \leqslant K^{q-p} \mathbb{E}_{(x,y) \sim \pi} d(x,y)^p.\] Taking the \(1/q\) power and taking the infimum over \(\pi\) completes the proof. ◻

Proof. On the interval \([t_j, t_{j+1}]\), we want \[\partial_t \Phi(t,x) = -\beta^2 (\partial_{x,x} \Phi(t,x) + \zeta_j \partial_x \Phi(t,x)^2).\] Hence, in the case where \(\zeta_j > 0\), \[\begin{align} \partial_t \exp( \zeta_j \Phi(t,x) ) &= \zeta_j \partial_t \Phi(t,x) \exp(\zeta_j \Phi(t,x)) \\ &= -\zeta_j \beta^2 (\partial_{x,x} \Phi(t,x) + \zeta_j \partial_x \Phi(t,x)^2) \exp(\zeta_j \Phi(t,x)) \\ &= -\beta^2 [\zeta_j \partial_{x,x} \Phi(t,x) + \zeta_j^2 \partial_x \Phi(t,x)^2]\exp\left(\zeta_j\Phi(t,x)\right) \\ &= -\beta^2 \partial_{x,x} [\exp(\zeta_j \Phi(t,x))]. \end{align}\] Recall from that \(|\partial_x \Phi(t,x)| \leqslant 1\) so \(\Phi\) grows linearly, and it is not hard to see that the solution to the heat equation is unique for a function that grows at most exponentially. Therefore, for \(t \in [t_j,t_{j+1}]\), we have \[\exp( \zeta_j \Phi(t,x) ) = \frac{1}{\sqrt{4\pi \beta^2 (t_{j+1} - t)}} \int_{\mathbb{R}} \exp(\zeta_j \Phi(t_{j+1},x+z)) \exp\left(-\frac{z^2}{4 \beta^2(t_{j+1} - t)} \right) \,dz.\] Hence, if \(Z_{j+1}\) is a normal random variable of mean zero and variance \(2 \beta^2(t_{j+1} - t_j)\), then we have \[\exp( \zeta_j \Phi(t_j,x) ) = \mathop{{}\mathbb{E}}[\exp(\zeta_j \Phi(t_{j+1},x+Z_{j+1}))],\] which is equivalent to the asserted formula. In the case when \(\zeta_j = 0\), the formula reduces to the standard probabilistic formula for solutions to the heat equation. ◻

Proof. First consider the case where \(\mu([0,t_0]) > 0\) so that all the \(\zeta_j\)’s are strictly positive. Let \(Z_1\), …, \(Z_r\) be independent normal random variables with \(\mathop{{}\mathbb{E}}[Z_{j+1}] = 0\) and \(\mathop{{}\boldsymbol{\mathrm{Var}}}(Z_{j+1}) = 2 \beta^2 (t_{j+1} - t_j)\). For compatibility with the notation of [23], recall that we can express \(Z_j\) as a function of a uniform random variable \(\omega_j\) on \([0,1]\) so that \(\omega_1\), …, \(\omega_r\) are independent. Let \(X_j\) be the random variable \[X_j(\omega_1,\dots,\omega_j) = \Phi(t_j, x + Z_1(\omega_1) + \dots + Z_j(\omega_j)),\] so that \[X_j(\omega_1,\dots,\omega_j) = \frac{1}{\zeta_j} \log \mathop{{}\mathbb{E}}\left[ \exp(\zeta_j X_{j+1}(\omega_1,\dots,\omega_{j+1})) \mid \omega_1, \dots, \omega_j \right]\] when \(\zeta_j > 0\) and \(X_j(\omega_1,\dots,\omega_j) =\mathbb{E} [X_{j+1}(\omega_1,\dots,\omega_{j+1}) \mid \omega_1, \dots, \omega_j]\) if \(\zeta_j = 0\). Now consider independent uniform random variables \(\omega_\alpha\) in \([0,1]\) indexed by strings \(\alpha = (n_1,\dots,n_j)\) of natural numbers, i.e.the index set is \(\mathcal{A} = \bigsqcup_{j=0}^\infty \mathbb{N}^j\). For \(\alpha = (n_1,\dots,n_r) \in \mathbb{N}^r\), write \[\Omega_\alpha = (\omega_{(n_1)}, \omega_{(n_1,n_2)},\dots,\omega_{(n_1,\dots,n_r)}).\] Let \((v_\alpha)_{\alpha \in \mathcal{A}}\) be the random weights constructed using the RPCs (). In particular, \(\sum_{\alpha \in \mathbb{N}^r} v_\alpha = 1\). Then [23] shows that \[X_0 = \mathop{{}\mathbb{E}}\log \sum_{\alpha \in \mathbb{N}^r} v_\alpha \exp X_r(\Omega_\alpha).\] In other words, \[\Phi(t_0,x) = \mathop{{}\mathbb{E}}\log \sum_{(n_1,\dots,n_r) \in \mathbb{N}^r} v_{(n_1,\dots,n_r)} \exp\left( \Phi(1,x+Z_1(\omega_{n_1}) + \dots Z_r(\omega_{(n_1,\dots,n_r)})) \right).\] Writing \[Z_\alpha(\Omega_\alpha) = Z_1(\omega_{n_1}) + \dots + Z_r(\omega_{(n_1,\dots,n_r)}),\] we see that \(Z_\alpha\) is normal with mean zero and variance \(\sum_{j=0}^{r-1} 2\beta^2 (t_{j+1} - t_j) = 2\beta^2 (1 - t_0)\). Finally, note \(\exp(\Phi(1,\cdot)) = 2 \cosh(\cdot)\), which proves the asserted formula.

In the case where \(\mu([0,t_0]) = 0\), note that \(t_1\) is the infimum of the support of \(\mu\). Then by the preceding argument, we can express \[\Phi(t_1,x) = \mathop{{}\mathbb{E}}\log \sum_{\alpha \in \mathbb{N}^r} 2 v_\alpha \cosh(x + Z_\alpha),\] where \(Z_\alpha\) is a Gaussian random variable of variance \(2 \beta^2(1 - t_1)\). Recall \(\Phi\) satisfies \(\partial_t \Phi = -\beta^2 \partial_{x,x} \Phi\) on \([t_0,t_1]\). Let \(Z\) be a normal random variable of mean zero and variance \(2 \beta^2 (t_1 - t_0)\) independent of all the other random variables. Then \[\begin{align} \Phi(t_0,x) &= \mathop{{}\mathbb{E}}\Phi(t_1,x+Z) \\ &= \mathop{{}\mathbb{E}}\log \sum_{\alpha \in \mathbb{N}^r} 2 v_\alpha \cosh(x + Z + Z_\alpha). \end{align}\] Hence, we have the asserted formula at \(t_0\) using \(\tilde{Z}_\alpha = Z + Z_\alpha\) which is normal of mean zero and variance \(2 \beta^2(1 - t_1) + 2 \beta^2(t_1 - t_0) = 2 \beta^2(1 - t_0)\). ◻