mollifier to our CDF function. In the passing we remark that, prior to this
work, we aren’t even aware if the weaker _Gaussian_ analogue of this statement
was known (in particular, the results of [HKM13, ST17] only require Gaussian
anti-concentration for which they use a result of Nazarov [Naz03] as a black-
box).

In order to prove our main theorem (stated below), we follow the result of
[OST19, Kan14a] closely since they are able to handle intersections of unate
functions which is the case for positive spectrahedra. However, there are two
subtleties.

  1. ($i$)

In [OST19] they bucket the set of halfspaces (which form the polytope) and
show that each bucket has significant weight. Crucially for them, they use the
fact that intersections of halfspaces are still unate functions. But this is
not the case for positive spectrahedra. For this, we need to modify the
bucketing procedure (akin to what happens in the proof of Theorem 36) so that
this bucketing of positive spectrahedra still results in a unate function.

  2. ($ii$)

In [OST19] they prove an analogue of Lemma 45 which shows that each bucket has
“significant weight”. However our proof deviates significantly from the proof
in [OST19]. For them, proving the statement in the lemma (for diagonal
matrices), follows directly from Paley-Zygmund inequality, but as far as we
are aware, we do not have a matrix-version of this inequality. Due to this
difficulty, we modify their proof and use the matrix Chernoff bound to prove
the statement above.

######  Theorem 41.

Let $k\geq 0$ be an integer and $\tau\leq\frac{1}{100\sqrt{\log k}}$. Let
$\\{B_{1},B_{2}\\}\subseteq\mathsf{Sym}_{k}$, $\\{A^{i}_{1}\\}_{i\in[n]}$ and
$\\{A^{i}_{2}\\}_{i\in[n]}$ be sequences of $\mathsf{PSD}$ and $\mathsf{NSD}$
matrices, respectively. They satisfy that for all $i\in[n],j\in[2]$,
$A^{i}_{1}\preceq\tau\cdot\mathbb{I},A^{i}_{2}\succeq-\tau\mathbb{I}$ and
$\sum_{i=1}^{n}(A^{i}_{j})^{2}\succeq\mathbb{I}$. Then for every $\Lambda\geq
20\tau\log k$, we have

$\Pr_{\bm{x}\sim\mathcal{U}_{n}}\left[\exists j\in[2]\text{ s.t.
}\lambda_{\max}\left(\sum_{i}\bm{x}_{i}A^{i}_{j}-B_{j}\right)\in(-\Lambda,\Lambda]\right]\leq
O(\Lambda).$

Using the standard bits-to-Gaussians trick [O’D14, Chapter 11], we have the
following corollary.

######  Corollary 42.

Let $k\geq 0$ be an integer and $\tau\leq\frac{1}{\log k}$. Let
$\\{B_{1},B_{2}\\}\subseteq\mathsf{Sym}_{k}$, $\\{A^{i}_{1}\\}_{i\in[n]}$ and
$\\{A^{i}_{2}\\}_{i\in[n]}$ be sequences of $\mathsf{PSD}$ and $\mathsf{NSD}$
matrices, respectively. They satisfy that for all $i\in[n],j\in[2]$,
$A^{i}_{1}\preceq\tau\cdot\mathbb{I},A^{i}_{2}\succeq-\tau\mathbb{I}$ and
$\sum_{i}(A^{i}_{j})^{2}\succeq\mathbb{I}$ . Then for every $\Lambda\geq
20\tau\log k$, we have

$\Pr_{\bm{g}\sim\mathcal{G}^{n}}\left[\exists j\in[2]\text{ s.t.
}\lambda_{\max}\left(\sum_{i}\bm{g}_{i}A^{i}_{j}-B_{j}\right)\in(-\Lambda,\Lambda]\right]\leq
O(\Lambda).$

In order to prove this theorem we will use the following two lemmas by
[OST19]. Before stating these lemmas, we introduce a few definitions from
[OST19] (adapted to our setting of positive spectrahedra). For the rest of the
section, we let $F:\\{-1,1\\}^{n}\rightarrow\\{0,1\\}$ be the indicator of an
intersection of positive spectrahedra, i.e., for every $j\in[2]$, let
$F_{j}(x)=\left[\sum_{i=1}^{n}x_{i}A_{j}^{i}\preceq B_{j}\right]$, where
$\left\\{A^{i}_{j}\right\\}_{j\in\left\\{1,2\right\\}}$ are sequences of
$\mathsf{PSD}$($\mathsf{NSD}$) matrices and

$\displaystyle
F(x)=\bigwedge_{j=1}^{2}F_{j}(x)=\bigwedge_{j=1}^{2}\left[\sum_{i=1}^{n}x_{i}A_{j}^{i}\preceq
B_{j}\right].$ (42)

  1. 1.

For a set $S\subseteq\\{-1,1\\}^{n}$, let $\mathcal{E}(S)$ be the fraction of
$n\cdot 2^{n-1}$ edges which have one endpoint in $S$ and one endpoint in
$S^{c}$ (i.e., complement of $S$).

  2. 2.

We let $H_{j}\subseteq\\{-1,1\\}^{n}$ be the _indicator-set_ for $F_{j}$,
i.e., $x\in H_{j}$ if and only if $F_{j}(x)=1$. Additionally, suppose we have
sets $\\{\bar{H}_{1},\bar{H}_{2}\\}$ such that $H_{j}\subseteq\bar{H}_{j}$
such that $\bar{H}_{j}$ are also the indicator-sets of unate functions. Let
$\partial H_{j}=\bar{H}_{j}\backslash H_{j}$.

  3. 3.

For $\alpha\in[0,1]$, we say $\partial H_{j}$ is _$\alpha$ -semi thin_ if for
every $x\in H_{j}$, at least an $\alpha$-fraction of its hypercube-neighbours
(i.e., set of $y\in\\{-1,1\\}^{n}$ for which $d(x,y)=1$) are outside $\partial
H_{j}$.

  4. 4.

We now define a few sets: let

$F=\bar{H}_{1}\cap\bar{H}_{2},\qquad
F^{\circ}={H}_{1}\cap{H}_{2},\qquad\partial F=F\backslash F^{\circ}$

With this terminology, we have the following lemma that bounds the number of
edges that cross $F$.

######  Lemma 43 ([OST19, Theorem 7.18]).

For $j\in[2]$, let $H_{j}$ be as defined above. Suppose $H_{j}$ is
$\alpha$-semi thin, then

$\mathsf{vol}(\partial F)\leq O\left(\frac{1}{\alpha\sqrt{n}}\right)$

Using this lemma, we get the following theorem (which is the analogue of
[OST19, Theorem 7.19]).

######  Theorem 44.

Let $\lambda>0,\alpha\in[0,1],\\{B_{1},B_{2}\\}\subseteq\mathsf{Sym}_{k}$. Let
$\\{A^{i}_{j}\\}_{i\in[n],j\in[2]}\subseteq\mathsf{Sym}_{k}$ satisfy that
$A^{i}_{1}\succeq 0,A^{i}_{2}\preceq 0$ for all $i\in[n]$. At least
$\alpha$-fraction of $i\in[n]$ satisfy that
$A^{i}_{1}\succeq\lambda\cdot\mathbb{I}$ and
$A^{i}_{2}\preceq-\lambda\cdot\mathbb{I}$. Then, we have

$\Pr_{\bm{x}\sim\mathcal{U}_{n}}\left[\exists j\in[2]\text{ s.t.
}\lambda_{\max}\left(\sum_{i}\bm{x}_{i}A^{i}_{j}-B_{j}\right)\in(-2\lambda,0]\right]\leq
O\left(\frac{1}{\alpha\sqrt{n}}\right).$

###### Proof.

Let $\\{A^{i}_{j}\\},\\{B_{j}\\}$ be as in the theorem statement. Let

$H_{j}=\Big{\\{}x\in\\{-1,1\\}^{n}:\lambda_{\max}\left(\sum_{i}x_{i}A^{i}_{j}-B_{j}\right)\leq-2\lambda\Big{\\}},\quad\bar{H}_{j}=\Big{\\{}x\in\\{-1,1\\}^{n}:\lambda_{\max}\left(\sum_{i}x_{i}A^{i}_{j}-B_{j}\right)\leq
0\Big{\\}}.$

Clearly we then have that

$\partial
H_{j}=\left\\{x\in\\{-1,1\\}^{n}:\lambda_{\max}\left(\sum_{i}x_{i}A^{i}_{j}-B_{j}\right)\in(-2\lambda,0]\right\\}$

and

$\partial F=\left\\{x\in\\{-1,1\\}^{n}:\exists j\in[2]\text{ s.t.
}\lambda_{\max}\left(\sum_{i}x_{i}A^{i}_{j}-B_{j}\right)\in(-2\lambda,0]\right\\}.$

Since we assumed that at least an $\alpha$-fraction of $i$s satisfied
$A^{i}_{1}\succeq\lambda\cdot\mathbb{I}$ and
$A^{i}_{2}\preceq-\lambda\cdot\mathbb{I}$, it follows that $H_{j}$ is
$\alpha$-semi thin, hence we can apply Lemma 43 to obtain the theorem
statement. ∎

Using this theorem, we are now ready to prove our main technical lemma which
says that we can always “randomly bucket” our positive spectrahedron so that
many of these buckets have “pretty large” smallest eigenvalue.

######  Lemma 45.

Let $\\{A^{i}\\}_{i\in[n]}\subseteq\mathsf{Sym}_{k}$ be a sequence of positive
semidefinite matrices which is $\left(\tau,M\right)$-regular with
$\tau\leq\frac{1}{100\sqrt{\log k}}$. Let $m\geq\frac{1}{10\tau^{2}\log k}$
and $\pi:[n]\rightarrow[m]$ be a random hash function that independently
assigns each $i\in[n]$ to a uniformly random bucket in $[m]$. For $c\in[m]$,
let

$\sigma_{c}=\sum_{j\in\pi^{-1}(c)}A^{j}$

and we say the bucket $c\in C$ is _good_ if $\sigma_{c}\succeq\frac{1}{2\tau
m}\cdot\mathbb{I}$. Then,

$\Pr\left[\text{at most }3m/4\text{ buckets }c\in[m]\text{ are good
}\right]\leq\exp\left(-m/4\right).$

###### Proof.

Let $\bm{z}_{i}\in\\{0,1\\}$ be a random variable satisfying
$\Pr[\bm{z}_{i}=1]=1/m$. Let $Z_{i}=\bm{z}_{i}\cdot A^{i}$, hence one can
write $\sigma_{c}=\sum_{i}Z_{i}$. In particular, this implies

$\mathbb{E}\left[\sigma_{c}\right]=\frac{1}{m}\sum_{i}A^{i}\succeq\frac{1}{\tau\cdot
m}\sum_{i}\left(A^{i}\right)^{2}\succeq\frac{1}{\tau m},$

where we used $A^{i}\preceq\tau\cdot\mathbb{I}$. Applying Fact 5 (for
$\delta=1/2$, $\mu=1/\tau m$, $R=\tau$) we have

$\mathrm{Pr}\>\\!\\!\left[\sum_{i}Z_{i}\succeq\frac{1}{2\tau
m}\mathbb{I}\right]\geq
1-k\cdot\left(\frac{2}{e}\right)^{\frac{1}{2\tau^{2}m}}\geq\frac{9}{10}$

For $j\in[n]$ and $c\in[m]$ define random variables

$Y_{c,j}=\begin{cases}1~{}\mbox{if $\pi(j)=c$}\\\
0~{}\mbox{otherwise},\end{cases}\quad\text{ and }\qquad
X_{j}=\left[\sum_{c=1}^{m}Y_{c,j}\sigma_{c}\succeq\frac{1}{2\tau
m}\mathbb{I}\right].$

Using the Claim 46 below, $X_{1},\ldots,X_{n}$ are negatively associated. Thus
we may apply the Chernoff bound to $\sum_{i=1}^{m}X_{i}$ which has mean at
least $3m/4$, which gives us the lemma statement.

######  Claim 46.

The random variables $X_{1},\ldots,X_{n}$ are negatively associated.

###### Proof.

From [DP09, Page 35, Example 3.1], the set of random variables
$\left\\{Y_{c,j}\right\\}_{1\leq c\leq m}$ are negatively associated for
$j\in[n]$. Note that $\left\\{Y_{1,j},\ldots,Y_{m,j}\right\\}_{j\in[n]}$ are
$n$ independent families of random variables. By [DP09, Page 35],
$\left\\{Y_{c,j}\right\\}_{c\in[m],j\in[n]}$ are negatively associated. Given
$\sigma_{1},\ldots,\sigma_{m}$,
$\left[\sum_{c=1}^{m}Y_{c,j}\sigma_{c}\succeq\frac{1}{2\tau
m}\mathbb{I}\right]$ is a monotone non-decreasing function of
$Y_{c,1},\ldots,Y_{c,n}$. Thus from [DP09, Page 35], $X_{1},\ldots,X_{m}$ are
negatively associated. ∎

The proof of this claim concludes the proof of the lemma. ∎

We are now ready to proof our main theorem.

###### Proof of Theorem 41.

For $j\in[2]$, let $f_{j}(x)=\sum_{i=1}^{n}x_{i}A^{i}_{j}$. Let
$\pi:[n]\rightarrow[2m]$ be a random hash function that independently assigns
each $i\in[n]$ to uniformly random bucket in $[2m]$. Let
$C_{1},\ldots,C_{2m}\subseteq[n]$ be the buckets and $z\in\\{-1,1\\}^{2m}$ be
uniformly random. Consider the function
$g_{j}:\\{-1,1\\}^{2k}\rightarrow\mathsf{Sym}_{k}$ defined as

$g_{j}(z)=\sum_{q=1}^{2m}z_{q}\cdot\sum_{i\in C_{q}}A^{i}_{j}.$

For $q\in[2m]$, define $\bar{A}^{q}_{j}=\sum_{i\in C_{q}}A^{i}_{j}$, so
$g_{j}(z)=\sum_{q}z_{q}\bar{A}^{q}_{j}$. Observe that distribution of $f_{j}$
and $g_{j}$ are the same, i.e., for every $D\in\mathsf{Sym}_{k}$ we have

$\displaystyle\Pr_{\bm{z}\sim\mathcal{U}_{2m},\\{C_{i}\\}}[g_{j}(\bm{z})=D]=\Pr_{\bm{x}\sim\mathcal{U}_{n}}[f_{j}(\bm{x})=D].$
(43)

In order to see this we argue that the $n$-bit string $w\in\\{-1,1\\}^{n}$
defined as $w_{i}=z_{q}$ iff $i\in C_{q}$, is uniformly random. To show this,
we first prove the following: for $z\in\\{-1,1\\}^{2m}$, let
$S=\\{q\in[2m]:z_{q}=1\\}$ and $T=\cup_{q\in S}C_{q}$. Then, observe that for
every $T\subseteq[n]$, we have $\Pr_{\bm{z},\\{C_{q}\\}}[\textbf{T}=T]=2^{-n}$
(for every $i\in[n]$, the probability of $i\in C_{q}$ is $1/(2m)$ and the
probability $C_{q}$ is included in $T$ is $1/2$ since $z_{q}$ is a uniformly
random bit, hence for every $i\in[n]$, we have $\Pr_{\bm{z},\\{C_{q}\\}}[i\in
T]=\sum_{i=1}^{2m}(1/2m)\cdot(1/2)=1/2$ and this is independent for every
$i\in[n]$ by construction). It is now easy to see that $w$ is uniformly random
because

$\Pr_{\bm{z},\\{C_{j}\\}}[W=w]=\sum_{T}\Pr[\textbf{T}=T]\cdot\Pr[W=w|\textbf{T}=T]=\frac{1}{2^{n}}\sum_{T}\Pr[W=w|\textbf{T}=T]=2^{-n},$

where the last equality used the fact that once we fix $T$, then all the bits
of $w$ which are $1$ are fixed.

For $m=\frac{1}{20\tau^{2}\log k}$, let $\pi:[n]\rightarrow[2m]$ be a random
hash that buckets these $n$ variables (jointly for $j\in[2]$). By Lemma 45, we
argued that, with probability at least $1-e^{-m/2}$, at least $9m/5$ of the
$2m$ buckets are good for $j=1$, i.e., a good bucket $q\in[2m]$ for $j=1$
satisfies $\sum_{i\in\pi^{-1}(q)}A^{i}_{1}\succeq\frac{1}{4\tau
m}\cdot\mathbb{I}$. For the same reason, with probability at least
$1-e^{-m/2}$, at least $9m/5$ of the $2m$ buckets are good for $j=2$, i.e., a
good bucket $q\in[2m]$ for $j=2$ satisfies
$\sum_{i\in\pi^{-1}(q)}A^{i}_{2}\preceq-\frac{1}{4\tau m}\cdot\mathbb{I}$.
Applying a union bound, at least $8m/5$ of $2m$ buckets are good for every
$j\in[2]$ with probability at least $1-2\cdot e^{-m/2}$.

By the argument in the start of the proof, we know that after bucketing, we
can convert each $f_{j}$ into a function
$g_{j}:\\{-1,1\\}^{2m}\rightarrow\mathsf{Sym}_{k}$ such that $f_{j}$ and
$g_{j}$ have the same distribution. Now we can invoke Theorem 44 as follows:
we know that a $4/5$-fraction of $q\in[2m]$ satisfy
$\bar{A}^{q}_{1}\succeq\frac{1}{4\tau m}\cdot\mathbb{I}$ and
$\bar{A}^{q}_{2}\preceq-\frac{1}{4\tau m}\cdot\mathbb{I}$, so we have

$\displaystyle\Pr_{\bm{z}\sim\mathcal{U}_{m}}\left[\exists
j\in[2]~{}\text{s.t.}~{}\lambda_{\max}\left(\sum_{q=1}^{m}\bm{z}_{q}\bar{A}^{q}_{j}-B_{j}\right)\in(-1/2\tau
m,0]\right]\leq O\left(\sqrt{\frac{1}{m}}\right)+2e^{-m/2}.$

We now prove the main theorem statement. In order to do so, first observe
that, we can partition the bound on the LHS into $\lceil 2\Lambda\tau m\rceil$
intervals as $\Lambda\geq 1/2\tau m$ from our choice of parameters.151515To be
precise, for a vector $v\in\mathbb{R}^{k}$, observe that the event
$\left[\forall i\in[k]:v_{i}\leq b_{i}+\Lambda,\text{ and }\exists
j\in[k]:v_{j}\geq b_{j}-\Lambda\right]$ can be broken down into the
intersections of $\Lambda/2\tau m$ events given by
$\bigwedge_{\ell=0}^{2\Lambda\tau m-1}[\forall i\in[k]:v_{i}\leq
b_{i}+\Lambda-\ell/2\tau m,\text{ and }\exists
j\in[\ell]:v_{j}>b_{j}-\Lambda-(\ell+1)/2\tau m]$. and by a union bound we
have

$\displaystyle\Pr_{\bm{x}\sim\mathcal{U}_{n}}\left[\exists j\in[2]\text{ s.t.
}\lambda_{\max}\left(\sum_{i}\bm{x}_{i}A^{i}_{j}-B_{j}\right)\in(-\Lambda,\Lambda]\right]$
$\displaystyle\leq$ $\displaystyle O\left(\Lambda\cdot\tau\cdot
m\left(\sqrt{\frac{1}{m}}+\exp(-\Omega(m/2))\right)\right)$

From the choice of the parameters, the first term above dominates. And thus

$\Pr_{\bm{x}\sim\mathcal{U}_{n}}\left[\exists j\in[2]\text{ s.t.
}\lambda_{\max}\left(\sum_{i}\bm{x}_{i}A^{i}_{j}-B_{j}\right)\in[-\Lambda,0]\right]\leq
O\left(\Lambda\right).$

Similarly one can also show when the LHS of the equation above is replaced
with $(0,\Lambda]$. Hence we get our theorem statement. ∎

##  6 Invariance principle for positive spectrahedra

In this section, we establish our main invariance principle.

###  6.1 Invariance principle for the spectral Bentkus mollifier

We now prove our main lemma which is an invariance principle for the Bentkus
mollifier. We remark that our analysis is the standard Lindeberg-style
argument for proving invariance principles, but when applied to the spectral
Bentkus mollifier. We first write out the Fréchet series for the Bentkus
mollifier, which we then upper bound using our main Theorem 28. In order to
upper bound the error terms in the Fréchet series, we use the matrix Rosenthal
inequality (in Fact 7) to bound the moments of random matrices (we remark that
this inequality will also be useful in our $\mathsf{PRG}$ construction).
Superficially, our proof techniques resemble the previous invariance principle
proofs used in [HKM13, ST17, OST19], but the quantities we need to bound are
very different from their analysis since we are dealing with matrices.

######  Lemma 47.

Let $k\geq 1,\theta,\tau\in(0,1)$ and
$\Psi_{\theta}:\mathsf{Sym}_{k}\rightarrow{\mathbb{R}}$ be defined as
$\Psi_{\theta}\left(Q\right)=\left(G_{\theta}\circ\lambda\right)\left(Q\right)$
where $G_{\theta}$ is the Bentkus mollifier defined in Eq. (20). Let
$S_{1},S_{2}$ be $(\tau,M)$-regular positive spectrahedra specified by
matrices $\\{A^{1}_{1},\ldots,A^{n}_{1},B_{1}\\}$ and
$\\{A^{1}_{2},\ldots,A^{n}_{2},B_{2}\\}$ respectively. Let $A^{i}=\mbox{\rm
diag}\left(A^{i}_{1},A^{i}_{2}\right)$ and $B=\mbox{\rm
diag}\left(B_{1},B_{2}\right)$ be block diagonal matrices. Then

$\displaystyle\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mathcal{U}_{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{x}_{i}A^{i}-B\right)\right]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\right]\right|\leq
O\left(\frac{\log^{7}k}{\theta^{3}}\cdot(M+\|B\|^{2})\cdot(M\cdot\tau)^{1.5}\right).$

This inequality still holds if $\bm{x}$ is $\left(80\log k\right)$-wise
uniform.

###### Proof.

Let $t=\lceil 1/\tau\rceil$. Let $\mathcal{H}=\\{h:[n]\rightarrow[t]\\}$ be a
family of $(80\log k)$-wise uniform hashing functions, i.e., for every subset
$I\subseteq[n]$ of size at most $80\log k$, and $b\in[t]^{I}$, we have

$\Pr_{\bm{h}\in\mathcal{H}}\left[\bm{h}(i)=b_{i}\right]=\frac{1}{t^{|I|}},$

where the probability is taken over a uniformly random function
$h\in\mathcal{H}$. Fix an $h\in\mathcal{H}$ (think of $h$ as a partition of
$[n]$ into $t$ blocks $S_{1},\ldots,S_{t}\subseteq[n]$, where
$S_{i}=h^{-1}(i)$ for all $i\in[t]$). For $\bm{x}\sim\mathcal{U}_{n}$ and
$\bm{y}\sim\mathcal{G}^{n}$ let us divide $\bm{x},\bm{y}$ into blocks
$\bm{x}^{1},\ldots,\bm{x}^{t}$ and $\bm{y}^{1},\ldots,\bm{y}^{t}$ according to
$h$. It is not hard to see that $\bm{x}^{i}\sim\mathcal{U}^{|h^{-1}(i)|}$ and
$\bm{y}^{i}\sim\mathcal{G}^{|h^{-1}(i)|}$. We now upper bound the quantity

$\displaystyle\left|\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{U}_{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{x}_{i}A^{i}-B\right)\right]-\mathop{\mathbb{E}}_{\bm{y}\in\mathcal{G}^{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{y}_{i}A^{i}-B\right)\right]\right|$
(44)

by the standard hybrid argument. Let $\\{Z^{0},\ldots,Z^{t}\\}$ be a set of
random variable on $n$ coordinates such that $Z^{0}$ is the uniform
distribution on $\\{-1,1\\}^{n}$ and $Z^{t}$ is uniform in $\mathcal{G}^{n}$.
To this end, define $Z^{\ell}$ as follows: for $j\in[\ell]$, let
$Z^{\ell}_{|h^{-1}(j)}=\bm{y}^{j}$ and for $\ell<j\leq t$ let
$Z^{\ell}_{|h^{-1}(j)}=\bm{x}^{j}$. It is easy to see that
$Z^{0}\sim\mathcal{U}_{n}$ and $Z^{t}\sim\mathcal{G}^{n}$. We now can upper
bound Eq. (44) as

$\displaystyle\begin{aligned}
&\left|\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{U}_{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{x}_{i}A^{i}-B\right)\right]-\mathop{\mathbb{E}}_{\bm{y}\sim\mathcal{G}^{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{y}_{i}A^{i}-B\right)\right]\right|\\\
&=\left|\sum_{\ell=1}^{t}\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}Z^{\ell}_{i}A^{i}-B\right)\right]-\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}Z^{\ell-1}_{i}A^{i}-B\right)\right]\right|\\\
&\leq\sum_{\ell=1}^{t}\left|\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}Z^{\ell}_{i}A^{i}-B\right)\right]-\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}Z^{\ell-1}_{i}A^{i}-B\right)\right]\right|\end{aligned}$
(45)

We now upper bound each of the $t$ quantities on the RHS of Eq. (45). Fix
$\ell\in[t]$ and let us assume for simplicity that $h^{-1}(\ell)=[m]$. By
definition of $Z^{\ell}$ we observe that $Z^{\ell}_{j}=Z^{\ell+1}_{j}$ for all
$j\in\\{m+1,\ldots,n\\}$ and in fact we have

$Z^{\ell}=(\bm{x}_{1},\ldots,\bm{x}_{m},Z_{m+1},\ldots,Z_{n}),\quad
Z^{\ell+1}=(\bm{y}_{1},\ldots,\bm{y}_{m},Z_{m+1},\ldots,Z_{n}),$

where $\bm{x}_{i}\sim\mathcal{U}_{1}$ and $y_{i}\in\mathcal{G}$ is uniform in
their respective domains. Crucially note that $Z_{m+1},\ldots,Z_{n}$ is
independent of the $\bm{x}_{i}$s or $\bm{y}_{i}$s by definition of
$Z^{\ell},Z^{\ell+1}$. Rewriting the $\ell$-th term in Eq. (45), we get

$\displaystyle\left|\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[\Psi_{\theta}\left(\underbrace{\sum_{i=1}^{m}\bm{x}_{i}A^{i}}_{Q}+\underbrace{\sum_{i=m+1}^{n}Z_{i}A^{i}-B}_{P}\right)\right]-\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[\Psi_{\theta}\left(\underbrace{\sum_{i=1}^{m}\bm{y}_{i}A^{i}}_{R}+\underbrace{\sum_{i=m+1}^{n}Z_{i}A^{i}-B}_{P}\right)\right]\right|$
(46)

Let us analyze both these quantities separately. We can first write the
Fréchet series for both these expressions as

$\displaystyle\Psi_{\theta}(Q+P)=\Psi_{\theta}(P)+D\Psi_{\theta}\left(P\right)\left[Q\right]+\frac{1}{2}D^{2}\Psi_{\theta}\left(P\right)\left[Q,Q\right]+\frac{1}{6}D^{3}\Psi_{\theta}\left(P^{\prime}\right)\left[Q,Q,Q\right]$
(47)

where $P^{\prime}=P+\xi Q$ for some $\xi\in[0,1]$.161616This follows directly
from the mean value theorem for Fréchet derivatives [AP95].

$\displaystyle\Psi_{\theta}(R+P)=\Psi_{\theta}(P)+D\Psi_{\theta}\left(P\right)\left[R\right]+\frac{1}{2}D^{2}\Psi_{\theta}\left(P\right)\left[R,R\right]+\frac{1}{6}D^{3}\Psi_{\theta}\left(P^{\prime\prime}\right)\left[R,R,R\right],$
(48)

where $P^{\prime\prime}=P+\xi^{\prime}R$ for some $\xi\in[0,1]$.

Now, observe that since the first moment and the second moment of $\bm{x}$
match with the standard normal distributions. Thus we have that

$\displaystyle\begin{aligned}
\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[D\Psi_{\theta}\left(P\right)\left[R\right]\right]&=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[D\Psi_{\theta}\left(P\right)\left[Q\right]\right]\\\
\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[D^{2}\Psi_{\theta}\left(P\right)\left[R,R\right]\right]&=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\bm{x}\sim\mathcal{U}_{n}\\\
\bm{y}\sim\mathcal{G}^{n}\end{subarray}}\left[D^{2}\Psi_{\theta}\left(P\right)\left[Q,Q\right]\right].\end{aligned}$
(49)

So by taking the difference of Eq. (48) and Eq. (47), only the third order
spectral derivatives remain to be bounded. For this, we now use the Corollary
29 and obtain

$\displaystyle\big{|}D^{3}\Psi_{\theta}\left(P^{\prime}\right)\left[Q,Q,Q\right]\big{|}\leq
O\left(\frac{\Delta_{1}^{2}}{\theta^{3}}\log^{3}k\cdot\mbox{$\|{Q}\|$}^{3}\right)$
(50)
$\displaystyle\big{|}D^{3}\Psi_{\theta}\left(P^{\prime\prime}\right)\left[R,R,R\right]\big{|}\leq
O\left(\frac{\Delta_{2}^{2}}{\theta^{3}}\log^{3}k\cdot\mbox{$\|{R}\|$}^{3}\right).$
(51)

where $\Delta_{1}=\mbox{$\|{P^{\prime}}\|$}$ and
$\Delta_{2}=\mbox{$\|{P^{\prime\prime}}\|$}$.

Thus, the absolute value of Eq. (46) is upper bounded by

$\frac{\log^{3}k}{\theta^{3}}\mathbb{E}\left[\Delta_{1}^{2}\mbox{$\|{Q}\|$}^{3}+\Delta_{2}^{2}\mbox{$\|{R}\|$}^{3}\right]\leq\frac{\log^{3}k}{\theta^{3}}\left(\mathbb{E}\left[\mbox{$\|{P^{\prime}}\|$}^{4}\right]^{1/2}\mathbb{E}\left[\mbox{$\|{Q}\|$}^{6}\right]^{1/2}+\mathbb{E}\left[\mbox{$\|{P^{\prime\prime}}\|$}^{4}\right]^{1/2}\mathbb{E}\left[\mbox{$\|{R}\|$}^{6}\right]^{1/2}\right),$
(52)

where the inequality is by Cauchy-Schwarz inequality.

Using 6 and the fact that $\sum_{i}(A^{i})^{2}\preceq M\cdot\mathbb{I}$, we
have

$\displaystyle\mathbb{E}\left[\mbox{$\|{P^{\prime}}\|$}^{4}\right]\leq
O\left(\log^{2}k\cdot
M^{2}+\mbox{$\|{B}\|$}^{4}\right),\quad\mathbb{E}\left[\mbox{$\|{P^{\prime\prime}}\|$}^{4}\right]\leq
O\left(\log^{2}k\cdot M^{2}+\mbox{$\|{B}\|$}^{4}\right)$ (53)

We now upper bound the last term in Eq. (52) using the following claim.

######  Claim 48.

It holds that $\mathbb{E}\left[\mbox{$\|{Q}\|$}^{6}\right]\leq
O\left(\log^{6}k\cdot\tau^{3}\cdot M^{3}\right)$,
$\mathbb{E}\left[\mbox{$\|{R}\|$}^{6}\right]\leq
O\left(\log^{6}k\cdot\tau^{3}\cdot M^{3}\right)$.

Before proving this claim, observe that combining Claim 48 with Eq. (53),
(52), we can upper bound Eq. (52) (and in turn Eq. (46)) by

$\displaystyle O\left(\frac{\log^{3}k}{\theta^{3}}\cdot\left(M\log
k+\|B\|^{2}\right)\cdot\left(\log^{3}k\cdot\tau^{1.5}\cdot
M^{1.5}\right)\right)\leq
O\left(\frac{\log^{7}k}{\theta^{3}}\cdot(M+\|B\|^{2})\cdot(M\cdot\tau)^{1.5}\right)$

Putting together this inequality with Eq. (45), we finally get

$\displaystyle\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{U}_{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}x_{i}A^{i}\right)\right]-\mathop{\mathbb{E}}_{y\sim\mathcal{G}^{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}y_{i}A^{i}\right)\right]\Big{|}\leq
O\left(\frac{\log^{7}k}{\theta^{3}}\cdot(M+\|B\|^{2})\cdot(M\cdot\tau)^{1.5}\right),$

concluding the theorem proof. We now prove the claim above.

###### Proof of Claim 48.

Note that $Q=\sum_{i=1}^{n}\bm{x}_{i}A^{i}$, where
$\left(\bm{x}_{1},\ldots,\bm{x}_{n}\right)$ is i.i.d. with
$\mathrm{Pr}\>\\!\\!\left[\bm{x}_{i}=1\right]=\mathrm{Pr}\>\\!\\!\left[\bm{x}_{i}=-1\right]=\frac{1}{2t}$
and $\mathrm{Pr}\>\\!\\!\left[\bm{x}_{i}=0\right]=1-1/t$. Then using Fact 7,
we have

$\displaystyle\mathbb{E}\left[\mbox{$\|{Q}\|$}_{8p}^{8p}\right]^{1/8p}$
$\displaystyle\leq$
$\displaystyle\sqrt{8p-1}\Big{\|}\left(\frac{1}{t}\sum_{i}\left(A^{i}\right)^{2}\right)^{1/2}\Big{\|}_{8p}+\left(8p-1\right)\left(\frac{1}{t}\sum_{i}\mbox{$\|{A^{i}}\|$}_{8p}^{8p}\right)^{1/8p}$
$\displaystyle\leq$ $\displaystyle\sqrt{8p-1}\cdot\sqrt{\frac{M}{t}}\cdot
k^{\frac{1}{8p}}+\left(8p-1\right)\left(\frac{\tau^{8p-2}\cdot k\cdot
M}{t}\right)^{1/8p}$

where the second inequality used $\sum_{i}\left(A^{i}\right)^{2}\preceq
M\cdot\mathbb{I}$ for both terms and $0\preceq A^{i}\preceq\tau\mathbb{I}$ for
upper bounding the second term. Setting $p=10\log k$, $t=1/\tau$ we have

$\left(\mathbb{E}\left[\mbox{$\|{Q}\|$}_{8p}^{8p}\right]\right)^{1/8p}\leq
O\left(\sqrt{\log k}\cdot\sqrt{\tau}\cdot\sqrt{M}+\log
k\cdot\tau\cdot(M/\tau)^{1/(80\log k)}\right)=O\left(\log
k\cdot\sqrt{\tau}\cdot\sqrt{M}\right).$

Thus, we have

$\mathbb{E}\left[\mbox{$\|{Q}\|$}^{6}\right]\leq\left(\mathbb{E}\left[\mbox{$\|{Q}\|$}_{8p}^{8p}\right]\right)^{\frac{3}{4p}}\leq
O\left(\log^{6}k\cdot\tau^{3}\cdot M^{3}\right),$

where in the first inequality note that the LHS is the spectral norm and the
RHS is the $(8p)$-Schatten norm. This proves the first inequality in the claim
statement. The second inequality in the claim follows by the exact same
argument (since Fact 7 applies to even $\sum_{i}{\bm{g}}_{i}A^{i}$). ∎

The proof of this claim concludes the proof of the theorem. Additionally,
observe that since the largest Schatten power of $Q$ that we use is $8p=80\log
k$, the proof of this theorem also works for $\bm{x}$ that is $(80\log
k)$-wise uniform. ∎

###  6.2 Invariance principle for positive spectrahedra

We are now ready to prove our main theorem, which involves combining our anti-
concentration Theorem 41 and our invariance principle for Bentkus mollifier in
Lemma 47.171717We remark that our theorem statements should also hold true for
a larger class of _proper distributions_ as considered in [HKM13], which
requires one to extend our main Theorem 22 to show that even the $4$th order
spectral derivatives can be bounded by $\|f^{(4)}\|_{1}$. We believe this
should be possible and leave this to be made rigorous for future work.

######  Theorem 49.

Let $k\geq 1$, $M\geq 1,\gamma\geq 1,\tau\in[0,1],\delta\in[0,1]$. Let
$S_{1},S_{2}$ be $(\tau,M)$-regular positive spectrahedra specified by
matrices $\\{A^{1}_{1},\ldots,A^{n}_{1},B_{1}\\}\in\mathsf{Sym}_{k}$ and
$\\{A^{1}_{2},\ldots,A^{n}_{2},B_{2}\\}\in\mathsf{Sym}_{k}$ respectively
satisfying $\mbox{$\|{B_{1}}\|$},\mbox{$\|{B_{2}}\|$}\leq~{}\gamma$. Let
$S=S_{1}\cap S_{2}$. If $\mu$ is a $\left(80\log k\right)$-wise uniform
distribution over $\\{-1,1\\}^{n}$, then

$\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mu}[\bm{x}\in
S]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}[\bm{g}\in
S]\right|\leq C\cdot\left(M+\gamma^{2}\right)^{1/5}\cdot\log^{7/5}k\cdot
M^{3/10}\cdot\tau^{3/10},$

for some universal constant $C>0$.

###### Proof.

Again for notational simplicity, let $A^{i}=\mbox{\rm
diag}\left(A^{i}_{1},A^{i}_{2}\right)$ and $B=\mbox{\rm
diag}\left(B_{1},B_{2}\right)$ be block diagonal matrices. We conclude the
result by combining Fact 24, Lemma 47 and Corollary 41 as follows: first Lemma
47 implies

$\displaystyle\begin{aligned}
&\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mu}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{x}_{i}A^{i}-B\right)\right]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\right]\right|\leq
O\left(\frac{\log^{7}k}{\theta^{3}}\cdot(M+\|B\|^{2})\cdot(M\cdot\tau)^{1.5}\right),\end{aligned}$

In particular, using Fact 24 (for $D=B-\beta\cdot\mathbb{I}$ and
$D=B+\beta\cdot\mathbb{I}$), the “if” condition of Fact 24 is satisfied with

$\eta=O\left(\frac{\log^{7}k}{\theta^{3}}\cdot\left(M+(\gamma+\beta)^{2}\right)\cdot(M\cdot\tau)^{1.5}\right)$

where $\beta=O(\theta\cdot\sqrt{\log k/\delta})$. In particular, Fact 24 and
Corollary 42 now together imply that

$\displaystyle\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mu}\left[\Psi\left(\sum_{i=1}^{n}\bm{x}_{i}A^{i}-B\right)\right]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}\left[\Psi\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\right]\right|$
$\displaystyle\leq\gamma+3\delta+\Pr_{\bm{g}\sim\mathcal{G}^{n}}\left[\lambda_{\max}\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\in[-\Lambda,\Lambda]\right]$
$\displaystyle=O\left(\frac{\log^{7}k}{\theta^{3}}\cdot\left(M+\left(\gamma+\theta\cdot\sqrt{\log(k/\delta)}\right)^{2}\right)\cdot(M\cdot\tau)^{1.5}+\delta+\Lambda\right)$
$\displaystyle\leq
O\left(\frac{\log^{7}k}{\theta^{3}}\cdot\left(M+\left(\gamma+\sqrt{\log(k/\delta)}\right)^{2}\right)\cdot(M\cdot\tau)^{1.5}+\delta+\Lambda\right)$

Let us fix

$\displaystyle\theta\leftarrow\delta,\quad\theta\leftarrow\Lambda,\quad\left((M\cdot\tau)^{1.5}\cdot\log^{7}k\cdot\left(M+\left(\gamma+\sqrt{\log
k}\right)^{2}\right)\right)^{1/5}\leftarrow\theta.$

This gives us

$\displaystyle\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mu}\left[\Psi\left(\sum_{i=1}^{n}\bm{x}_{i}A^{i}-B\right)\right]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}\left[\Psi\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\right]\right|\leq\left((M\cdot\tau)^{1.5}\cdot\log^{7}k\cdot(M+\gamma^{2})\right)^{1/5}.$

∎

###  6.3 Application: Pseudorandom generators for positive spectrahedra.

We are now ready to describe our pseudorandom generator for fooling positive
spectrahedra. Our $\mathsf{PRG}$ is based on the well-known construction of
Meka and Zuckerman [MZ13] which we describe now. We remark that the same
$\mathsf{PRG}$ (with minor modifications and different parameter settings) was
used in [MZ13, HKM13, ST17] in order to obtain $\mathsf{PRG}$s for polytopes.

##### Meka-Zuckerman PRG.

We begin by describing the Meka-Zuckerman $\mathsf{PRG}$. Let us fix the
parameters $\delta\in(0,1)$, $\tau=\Omega(\delta^{10/3}/(\log^{5}k\cdot
M\cdot(M+\gamma^{2})))$ so that we have
$\left(M+\gamma^{2}\right)^{1/5}\cdot\log^{7/5}k\cdot
M^{3/10}\cdot\tau^{3/10}=\delta$ (where the LHS of this equality is the upper
bound obtained in our invariable principle proof). Let $t=\lceil 1/\tau\rceil$
and consider the family of $(80\log k)$-wise uniform functions
$\mathcal{H}=\\{h:[n]\rightarrow[t]\\}$, i.e., for every for every subset
$I\subseteq[n]$ of size at most $80\log k$, and $b\in[t]^{I}$, we have

$\Pr_{\bm{h}\in\mathcal{H}}\left[\bm{h}(i)=b_{i}\right]=\frac{1}{t^{|I|}},$

where the probability is taken over a uniformly random function
$h\in\mathcal{H}$. Efficient constructions of such hash function families are
known with $|\mathcal{H}|=O(n^{80\log k})$. For simplicity (as in the proof of
[MZ13, HKM13]), we also assume that for every $j\in[t]$, we have
$|h^{-1}(j)|=n/t$. Let $m=n/t$ and
$G_{0}:\\{0,1\\}^{s}\rightarrow\\{-1,1\\}^{m}$ generate a $(80\log k)$-wise
uniform distribution over $\\{-1,1\\}^{m}$, i.e., for every $I\subseteq[n]$ of
size at most $80\log k$ and $b\in\\{-1,1\\}^{I}$, we have

$\Pr_{\begin{subarray}{c}\bm{z}\in\\{0,1\\}^{s}\\\
\bm{x}=G_{0}(\bm{z})\end{subarray}}[\bm{x}_{i}=\bm{b}_{i}\text{ for all }i\in
I]=\frac{1}{2^{|I|}},$

where the probability is taken over uniformly random $z\in\\{0,1\\}^{s}$. It
is well-known by [NN93] that efficient constructions of generators $G_{0}$ are
known for $s=O(\log k\log n)$. Finally, we are ready to describe the Meka-
Zuckerman generator: for a given hash function family $\mathcal{H}$ and
generator $G_{0}$, define
$G:\mathcal{H}\times(\\{0,1\\}^{s})^{t}\rightarrow\\{-1,1\\}^{n}$ by

$G(h,z^{1},\ldots,z^{t})=x,\qquad\text{ where
}x_{|h^{-1}(i)}=G_{0}(z^{i})\text{ for }i\in[t].$

Clearly the seed length of this generator is

$O\left((\log n)(\log k)+(\log n)(\log k)\frac{1}{\tau}\right)=O((\log n)(\log
k)/\tau)=(\log n)\cdot\operatorname{poly}(\log k,M,1/\delta,\gamma),$

where the first term is the logarithm of the number of elements of the hash
function family $|\mathcal{H}|$, the second term because we have $s=O((\log
n)(\log k))$ and recall that we picked $t=O(1/\tau)$ and the final equality
used the bound on $\tau$ we fixed at the start of the proof.

We now restate our main theorem and prove it.

######  Theorem 50.

Let $\delta\in(0,1)$, $k,n,M\geq 1$ and $\tau\leq\delta^{10/3}/(\log^{5}k\cdot
M\cdot(M+\gamma^{2}))$. Let $S_{1},S_{2}$ be $(\tau,M)$-regular positive
spectrahedra specified by matrices
$\\{A^{1}_{1},\ldots,A^{n}_{1},B_{1}\\}\in\mathsf{Sym}_{k}$ and
$\\{A^{1}_{2},\ldots,A^{n}_{2},B_{2}\\}\in\mathsf{Sym}_{k}$ with
$\|B_{1}\|,\|B_{2}\|\leq\gamma$. Let $S=S_{1}\cap S_{2}$. There exists a
$\mathsf{PRG}$ $G:\\{0,1\\}^{r}\rightarrow\\{-1,1\\}^{n}$ with

$r=(\log n)\cdot\operatorname{poly}(\log k,M,1/\delta,\gamma)$

that $\delta$-fools $S$ with respect to the uniform distribution.

The proof of this theorem is a generic statement that allows one to go from
invariance principles proven using the proof techniques to construct
$\mathsf{PRG}$s. The proof uses the same proof ideas of Harsha, Klivans and
Meka [HKM13, Section 7.2] (except that now we directly proved _Boolean_ anti-
concentration instead of the weaker _Gaussian_ anti-concentration as proven by
[HKM13]). We provide the proof below for completeness.

###### Proof.

Again for notational simplicity, let $A^{i}=\mbox{\rm
diag}\left(A^{i}_{1},A^{i}_{2}\right)$ and $B=\mbox{\rm
diag}\left(B_{1},B_{2}\right)$ be block diagonal matrices. The $\mathsf{PRG}$
$G$ will be the Meka-Zuckerman $\mathsf{PRG}$ defined above, so the seed
length $r=(\log n)\cdot\operatorname{poly}(\log k,M,1/\delta,\gamma)$
immediately follows.

$\displaystyle\begin{aligned}
\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mathcal{U}_{r}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\left(G(\bm{x})\right)_{i}A^{i}-B\right)\right]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}\left[\Psi_{\theta}\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\right]\right|\leq
O\left(\frac{\log^{7}k}{\theta^{3}}\cdot(M+\|B\|^{2})\cdot(M\cdot\tau)^{1.5}\right),\end{aligned}$
(54)

where we used the fact that $G(x)$ for uniformly random $x\in\\{0,1\\}^{r}$
generates a $(80\log k)$-wise uniform distribution and Lemma 47 holds for
every $(80\log k)$-wise uniform distribution $\mu$. Repeating the same
calculation that we did in the proof of Theorem 49, we get

$\displaystyle\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mathcal{U}_{r}}\left[\Psi\left(\sum_{i=1}^{n}\left(G(\bm{x})\right)_{i}A^{i}-B\right)\right]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}\left[\Psi\left(\sum_{i=1}^{n}\bm{g}_{i}A^{i}-B\right)\right]\right|$
$\displaystyle\leq\gamma+3\delta+\Pr_{\bm{g}\sim\mathcal{G}^{n}}\left[\lambda_{\max}\left(A\left(\bm{g}\right)\right)\in(-\Lambda,\Lambda]\right]$
$\displaystyle=O\left(\frac{\log^{7}k}{\theta^{3}}\cdot(M+\|B\|^{2})\cdot(M\cdot\tau)^{1.5}+\delta+\Lambda\right),$

and using our assumption on $\tau$ (and the same parameters as in Theorem 49),
this implies that

$\left|\operatorname*{\mathbb{E}}_{\bm{x}\sim\mathcal{U}_{r}}[G(\bm{x})\in
S]-\operatorname*{\mathbb{E}}_{\bm{g}\sim\mathcal{G}^{n}}[\bm{g}\in
S]\right|\leq\delta,$

hence proving our theorem statement. ∎

## References

  * [AHK05] Sanjeev Arora, Elad Hazan, and Satyen Kale.  Fast algorithms for approximate semidefinite programming using the multiplicative weights update method.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 339–348. IEEE, 2005.
  * [AK07] Sanjeev Arora and Satyen Kale.  A combinatorial, primal-dual approach to semidefinite programs.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 227–236, 2007.
  * [AP95] Antonio Ambrosetti and Giovanni Prodi.  A primer of nonlinear analysis, volume 34.  Cambridge University Press, 1995.
  * [AS10] Brendan P.W. Ames and Hristo S. Sendov.  Asymptotic expansions of the ordered spectrum of symmetric matrices.  Nonlinear Analysis: Theory, Methods & Applications, 72(11):4288 – 4297, 2010.
  * [AS12] Brendan P.W. Ames and Hristo S. Sendov.  A new derivation of a formula by Kato.  Linear Algebra and its Applications, 436(3):722 – 730, 2012.
  * [AS16] Brendan P.W. Ames and Hristo S. Sendov.  Derivatives of compound matrix valued functions.  Journal of Mathematical Analysis and Applications, 433(2):1459 – 1485, 2016.
  * [AZLO16] Zeyuan Allen-Zhu, Yin Tat Lee, and Lorenzo Orecchia.  Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver.  In Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1824–1831, 2016.
  * [Baz09] Louay MJ Bazzi.  Polylogarithmic independence can fool DNF formulas.  SIAM Journal on Computing, 38(6):2220–2272, 2009.
  * [Ben90] Vidmantas Bentkus.  Smooth approximations of the norm and differentiable functions with bounded support in Banach space $\ell_{\infty}^{k}$.  Lithuanian Mathematical Journal, 30(3):223–230, 1990.
  * [Bha00] Rajendra Bhatia.  Pinching, trimming, truncating, and averaging of matrices.  The American Mathematical Monthly, 107(7):602–608, 2000.
  * [Bha13] Rajendra Bhatia.  Matrix analysis, volume 169.  Springer Science & Business Media, 2013.
  * [BHK+19] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin.  A nearly tight sum-of-squares lower bound for the planted clique problem.  SIAM Journal on Computing, 48(2):687–735, 2019.
  * [BLZ05] Jan Brinkhuis, Z-Q. Luo, and Shuzhong Zhang.  Matrix convex functions with applications to weighted centers for semidefinite programming.  Report / Econometric Institute, Erasmus University Rotterdam, (EI 2005-38), August 2005.
  * [Boo05] Carl de Boor.  Divided differences.  Surv. Approx. Theory 1, 2005.
  * [BPT12] Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas.  Semidefinite Optimization and Convex Algebraic Geometry.  Society for Industrial and Applied Mathematics, 2012.
  * [BS99] Rajendra Bhatia and Kalyan B. Sinha.  Derivations, derivatives and chain rules.  Linear Algebra and its Applications, 302-303:231 – 244, 1999.
  * [BSS98] Rajendra Bhatia, Dinesh Singh, and Kalyan B. Sinha.  Differentiation of operator functions and perturbation bounds.  Communications in Mathematical Physics, 191:603–611, 1998.
  * [CDS19] Eshan Chattopadhyay, Anindya De, and Rocco A Servedio.  Simple and efficient pseudorandom generators from Gaussian processes.  In 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [Col12] Rodney Coleman.  Calculus on normed vector spaces.  Springer Science & Business Media, 2012.
  * [CQT03] Xin Chen, Houduo Qi, and Paul Tseng.  Analysis of nonsmooth symmetric-matrix-valued functions with applications to semidefinite complementarity problems.  SIAM Journal on Optimization, 13(4):960–985, 2003.
  * [DGJ+10] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A Servedio, and Emanuele Viola.  Bounded independence fools halfspaces.  SIAM Journal on Computing, 39(8):3441–3462, 2010.
  * [DHK+10] Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghavendra, Rocco A Servedio, and Li-Yang Tan.  Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 533–542, 2010.
  * [DP09] Devdatt P. Dubhashi and Alessandro Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, 2009.
  * [Erd45] Paul Erdös.  On a lemma of Littlewood and Offord.  Bulletin of the American Mathematical Society, 51(12):898–902, 1945\.
  * [Fel68] Willliam Feller.  An introduction to probability theory and its applications, vol 1.  New York: Wiley, 1968.
  * [FF88] Péter Frankl and Z Furedi.  Solution of the Littlewood-Offord problem in high dimensions.  Annals of Mathematics, pages 259–270, 1988.
  * [FK20] Xiao Fang and Yuta Koike.  High-dimensional central limit theorems by Stein’s method.  arXiv preprint arXiv:2001.10917, 2020.
  * [FMP+15] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf.  Exponential lower bounds for polytopes in combinatorial optimization.  Journal of the ACM (JACM), 62(2):1–23, 2015.
  * [GKM18] Parikshit Gopalan, Daniel M Kane, and Raghu Meka.  Pseudorandomness via the discrete Fourier transform.  SIAM Journal on Computing, 47(6):2451–2487, 2018.
  * [GM12] Bernd Gärtner and Jiri Matousek.  Approximation algorithms and semidefinite programming.  Springer Science & Business Media, 2012.
  * [GOWZ10] Parikshit Gopalan, Ryan O’Donnell, Yi Wu, and David Zuckerman.  Fooling functions of halfspaces under product distributions.  In 2010 IEEE 25th Annual Conference on Computational Complexity, pages 223–234. IEEE, 2010.
  * [GW95] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  J. ACM, 42(6):1115–1145, 1995.
  * [GW13] Gus Gutoski and Xiaodi Wu.  Parallel approximation of min-max problems.  Computational Complexity, 22:385 – 428, 2013.
  * [Hau92] David Haussler.  Decision theoretic generalizations of the PAC model for neural net and other learning applications.  Information and computation, 100(1):78–150, 1992.
  * [HKM13] Prahladh Harsha, Adam Klivans, and Raghu Meka.  An invariance principle for polytopes.  Journal of the ACM (JACM), 59(6):1–25, 2013.
  * [HMV06] J William Helton, Scott A McCullough, and Victor Vinnikov.  Noncommutative convexity arises from linear matrix inequalities.  Journal of Functional Analysis, 240(1):105–191, 2006.
  * [IM12] Marcus Isaksson and Elchanan Mossel.  Maximally stable gaussian partitions with discrete applications.  Israel Journal of Mathematics, 189(1):347–396, 2012.
  * [JJUW11] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous.  QIP = PSPACE.  Journal of the ACM, 58(6), 2011.
  * [JLL+20] Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian.  Positive semidefinite programming: Mixed, parallel, and width-independent.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 789–802, 2020.
  * [JUW09] R. Jain, S. Upadhyay, and J. Watrous.  Two-message quantum interactive proofs are in PSPACE.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 534–543, 2009.
  * [JY11] R. Jain and P. Yao.  A parallel approximation algorithm for positive semidefinite programming.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 463–471, 2011.
  * [Kan10] Daniel M. Kane.  $k$-independent Gaussians fool polynomial threshold functions.  arXiv preprint arXiv:1012.1614, 2010.
  * [Kan11a] Daniel M. Kane.  The Gaussian surface area and noise sensitivity of degree-$d$ polynomial threshold functions.  computational complexity, 20(2):389–412, 2011.
  * [Kan11b] Daniel M. Kane.  k-independent Gaussians fool polynomial threshold functions.  In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC, pages 252–261. IEEE Computer Society, 2011\.
  * [Kan11c] Daniel M. Kane.  A small PRG for polynomial threshold functions of Gaussians.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pages 257–266. IEEE Computer Society, 2011.
  * [Kan14a] Daniel Kane.  The average sensitivity of an intersection of half spaces.  Research in the Mathematical Sciences, 1(1):13, 2014.
  * [Kan14b] Daniel M. Kane.  A pseudorandom generator for polynomial threshold functions of Gaussian with subpolynomial seed length.  In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 217–228. IEEE, 2014.
  * [KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio.  Agnostically learning halfspaces.  SIAM Journal on Computing, 37(6):1777–1805, 2008.
  * [KM15] Pravesh K. Kothari and Raghu Meka.  Almost optimal pseudorandom generators for spherical caps.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 247–256, 2015.
  * [KOS04] Adam R Klivans, Ryan O’Donnell, and Rocco A Servedio.  Learning intersections and thresholds of halfspaces.  Journal of Computer and System Sciences, 68(4):808–840, 2004.
  * [KOS08] Adam R Klivans, Ryan O’Donnell, and Rocco A Servedio.  Learning geometric concepts via Gaussian surface area.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 541–550. IEEE, 2008.
  * [KSS94] Michael J Kearns, Robert E Schapire, and Linda M Sellie.  Toward efficient agnostic learning.  Machine Learning, 17(2-3):115–141, 1994.
  * [Lew96] A. S. Lewis.  Derivatives of spectral functions.  Mathematics of Operations Research, 21(3):576–588, 1996.
  * [Lin22] J.W. Lindeberg.  Eine neue herleitung des exponentialgesetzes in der wahrscheinlichkeitsrechnung.  Mathematische Zeitschrift, 15:211–225, 1922.
  * [LO39] John Edensor Littlewood and Albert C Offord.  On the number of real roots of a random algebraic equation. ii.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 35, pages 133–148. Cambridge University Press, 1939.
  * [LRS15] James R Lee, Prasad Raghavendra, and David Steurer.  Lower bounds on the size of semidefinite programming relaxations.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 567–576, 2015.
  * [MJC+14] Lester Mackey, Michael I. Jordan, Richard Y. Chen, Brendan Farrell, and Joel A. Tropp.  Matrix concentration inequalities via the method of exchangeable pairs.  Ann. Probab., 42(3):906–945, 05 2014.
  * [MOO05] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz.  Noise stability of functions with low influences: invariance and optimality.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 21–30. IEEE, 2005.
  * [Mos08] Elchanan Mossel.  Gaussian bounds for noise correlation of functions and tight analysis of long codes.  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 156–165. IEEE Computer Society, 2008.
  * [MZ13] Raghu Meka and David Zuckerman.  Pseudorandom generators for polynomial threshold functions.  SIAM Journal on Computing, 42(3):1275–1301, 2013.
  * [Naz03] Fedor Nazarov.  On the maximal perimeter of a convex set in $\mathbb{R}^{n}$ with respect to a Gaussian measure.  In Geometric aspects of functional analysis, pages 169–187. Springer, 2003.
  * [NN93] Joseph Naor and Moni Naor.  Small-bias probability spaces: Efficient constructions and applications.  SIAM journal on computing, 22(4):838–856, 1993.
  * [NPS08] Jiawang Nie, Pablo A. Parrilo, and Bernd Sturmfels.  Semidefinite Representation of the k-Ellipse, pages 117–132.  Springer New York, New York, NY, 2008.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, 2014.
  * [OST19] Ryan O’Donnell, Rocco A Servedio, and Li-Yang Tan.  Fooling polytopes.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 614–625, 2019.
  * [OST20] Ryan O’Donnell, Rocco A Servedio, and Li-Yang Tan.  Fooling Gaussian PTFs via local hyperconcentration.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1170–1183, 2020.
  * [Per04] Yuval Peres.  Noise stability of weighted majority.  arXiv math/0412377, 2004.
  * [PT12] Richard Peng and Kanat Tangwongsan.  Faster and simpler width-independent parallel algorithms for positive semidefinite programming.  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’12, page 101–108. Association for Computing Machinery, 2012.
  * [Qua12] Ronan Quarez.  Symmetric determinantal representation of polynomials.  Linear algebra and its applications, 436(9):3642–3660, 2012.
  * [Rud86] Walter Rudin.  Real and Complex Analysis.  McGraw-Hill, 1986.
  * [Sch18] Claus Scheiderer.  Spectrahedral shadows.  SIAM Journal on Applied Algebra and Geometry, 2(1):26–44, 2018\.
  * [Sen07] Hristo S Sendov.  The higher-order derivatives of spectral functions.  Linear algebra and its applications, 424(1):240–281, 2007.
  * [Ser06] Rocco A Servedio.  Every linear threshold function has a low-weight approximator.  In 21st Annual IEEE Conference on Computational Complexity (CCC’06), pages 18–32. IEEE, 2006.
  * [ST17] Rocco A Servedio and Li-Yang Tan.  Fooling intersections of low-weight halfspaces.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 824–835. IEEE, 2017.
  * [Tao10] Terence Tao.  254a notes: Topics in random matrix theory., 2010.  https://terrytao.wordpress.com/tag/lindeberg-replacement-trick/.
  * [Tro12] Joel A. Tropp.  User-friendly tail bounds for sums of random matrices.  Foundations of Computational Mathematics, 12:389–434, 2012.
  * [Tro15] Joel A Tropp.  An introduction to matrix concentration inequalities.  arXiv preprint arXiv:1501.01571, 2015.
  * [Tro16] Joel A. Tropp.  The expected norm of a sum of independent random matrices: An elementary approach.  In Christian Houdré, David M. Mason, Patricia Reynaud-Bouret, and Jan Rosiński, editors, High Dimensional Probability VII, pages 173–202, Cham, 2016. Springer International Publishing.
  * [TV12] Terence Tao and Van Vu.  The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi.  Combinatorica, 32(3):363–372, 2012.
  * [Viz17] Cynthia Vizant.  Spectrahedra., 2017.  https://clvinzan.math.ncsu.edu/slides/MSRI_SpectrahedraSlides.pdf.
  * [Yao19] Penghui Yao.  A doubly exponential upper bound on noisy EPR states for binary games.  arXiv:1904.08832, 2019.

##  Appendix A Proof of Lemma 34: Case 2

Recall that the goal is to prove the following inequality

$\left|\sum_{i_{1}\neq i_{2}\neq
i_{3}}\frac{\frac{\overline{g}\left(x_{i_{1}}\right)-\overline{g}\left(x_{i_{3}}\right)}{x_{i_{3}}-x_{i_{1}}}-\frac{\overline{g}\left(x_{i_{1}}\right)-\overline{g}\left(x_{i_{2}}\right)}{x_{i_{2}}-x_{i_{1}}}}{x_{i_{3}}-x_{i_{2}}}G\left(x\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\leq
O\left(\Delta\log^{2}k\mbox{$\|{H}\|$}^{3}\right)$ (55)

First observe that the LHS of the inequality above can be rephrased as
follows.

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq
i_{3}}\frac{\frac{\overline{g}\left(x_{i_{1}}\right)-\overline{g}\left(x_{i_{3}}\right)}{x_{i_{3}}-x_{i_{1}}}-\frac{\overline{g}\left(x_{i_{1}}\right)-\overline{g}\left(x_{i_{2}}\right)}{x_{i_{2}}-x_{i_{1}}}}{x_{i_{3}}-x_{i_{2}}}G\left(x\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|$
$\displaystyle=\left|2\sum_{i_{1}\neq i_{2}\neq i_{3}\atop
x_{i_{3}}>x_{i_{2}}}\frac{\frac{g^{\prime}\left(x_{i_{1}}\right)g\left(x_{i_{3}}\right)-g\left(x_{i_{1}}\right)g^{\prime}\left(x_{i_{3}}\right)}{x_{i_{3}}-x_{i_{1}}}g\left(x_{i_{2}}\right)-\frac{g^{\prime}\left(x_{i_{1}}\right)g\left(x_{i_{2}}\right)-g\left(x_{i_{1}}\right)g^{\prime}\left(x_{i_{2}}\right)}{x_{i_{2}}-x_{i_{1}}}g\left(x_{i_{3}}\right)}{x_{i_{3}}-x_{i_{2}}}G\left(x_{-\left\\{i_{1},i_{2},i_{3}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|$
(56)

Providing an upper bound on this consists of several lemmas and the result is
concluded by combing all of them via triangle inequalities. To keep the
expressions short, we use the following notations to represent Eq. (55), which
are clear in the context.

$\displaystyle\left|2\sum_{\begin{subarray}{c}i_{1}\neq i_{2}\neq i_{3}\\\
x_{i_{3}}>x_{i_{2}}\end{subarray}}\frac{\frac{\langle
i_{1}\rangle^{\prime}\langle i_{3}\rangle-\langle i_{1}\rangle\langle
i_{3}\rangle^{\prime}}{[i_{3}-i_{1}]}\langle i_{2}\rangle-\frac{\langle
i_{1}\rangle^{\prime}\langle i_{2}\rangle-\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{2}-i_{1}]}\langle
i_{3}\rangle}{[i_{3}-i_{2}]}\right|,$ (57)

where we implicitly hide the
$G\left(x_{-\left\\{i_{1},i_{2},i_{3}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}$
term. We first give a sketch of how we are going to upper bound this
inequality and break it into subsections.

$\eqref{eq:mainequationwecare}=\underbrace{\frac{\langle i_{1}\rangle\langle
i_{3}\rangle^{\prime}-\langle i_{1}\rangle^{\prime}\langle
i_{3}\rangle}{[i_{3}-i_{1}]}\cdot\frac{\langle i_{3}\rangle-\langle
i_{2}\rangle}{[i_{3}-i_{2}]}}_{Section~{}\ref{sec:2.1},\hskip
2.84526ptLemma~{}\ref{lem:3}}-\underbrace{\frac{\frac{\langle
i_{1}\rangle\langle i_{3}\rangle^{\prime}-\langle i_{1}\rangle^{\prime}\langle
i_{3}\rangle}{[i_{3}-i_{1}]}-\frac{\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}-\langle i_{1}\rangle^{\prime}\langle
i_{2}\rangle}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle i_{3}\rangle}_{(\star)}.$
(58)

We now break up $(\star)$ into two cases

$\displaystyle(\star)=\underbrace{(\star)\cdot\mathbb{I}[\min\\{x_{i_{1}},x_{i_{3}}\\}>x_{i_{2}}]}_{(\dagger)}+\underbrace{(\star)\cdot\mathbb{I}[x_{i_{1}}<x_{i_{2}}<x_{i_{3}}]}_{(\dagger\dagger)}.$
(59)

Note that there are the only two cases we need to handle since by symmetry
between $i_{2}$ and $i_{3}$, we can assume $x_{i_{3}}>x_{i_{2}}$, without loss
of generality. Now we bound these two terms, separately.

$(\dagger)=\underbrace{\frac{\frac{\langle i_{3}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{1}\rangle\langle i_{3}\rangle}_{Section~{}\ref{sec:2.2},\hskip
2.84526ptLemma~{}\ref{lem:5}}-\underbrace{\frac{\frac{\langle
i_{3}\rangle-\langle i_{1}\rangle}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle-\langle i_{1}\rangle}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{1}\rangle^{\prime}\langle i_{3}\rangle}_{Section~{}\ref{sec:2.2},\hskip
2.84526ptLemma~{}\ref{lem:333}}.$

and

$(\dagger\dagger)=\underbrace{\frac{\frac{\langle i_{1}\rangle\langle
i_{3}\rangle^{\prime}-\langle i_{3}\rangle\langle
i_{3}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}-\langle i_{2}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{3}\rangle}_{Section~{}\ref{sec:2.3},\hskip
2.84526ptLemma~{}\ref{lem:casev111}}+\underbrace{\frac{\frac{\langle
i_{3}\rangle^{\prime}-\langle i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}\langle
i_{3}\rangle-\frac{\langle i_{2}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{2}-i_{1}]}\langle
i_{2}\rangle}{[i_{3}-i_{2}]}\langle i_{3}\rangle}_{(\P)\hskip
2.84526ptSection~{}\ref{sec:2.3}},$ (60)

and

$\displaystyle(\P)=\underbrace{\frac{\langle i_{3}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}\cdot\frac{\langle i_{3}\rangle-\langle
i_{2}\rangle}{[i_{3}-i_{2}]}\cdot\langle
i_{3}\rangle}_{Section~{}\ref{sec:2.4},\hskip
2.84526ptLemma~{}\ref{lem:444}}+\underbrace{\frac{\frac{\langle
i_{3}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{2}\rangle\langle i_{3}\rangle}_{Section~{}\ref{sec:2.4},\hskip
2.84526ptLemma~{}\ref{lem:555}}$ (61)

Finally in order to upper bound Eq. (57), we simply bound each of these terms
by $O\left(\Delta\log^{3}k\mbox{$\|{H}\|$}^{3}\right)$ in the respective
sections (as underbraced by the terms).

###  A.1 Upper bounding first term in Eq. (58)

######  Lemma 51.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop x_{i_{3}}>x_{i_{2}}}\frac{\langle
i_{1}\rangle\langle i_{3}\rangle^{\prime}-\langle i_{1}\rangle^{\prime}\langle
i_{3}\rangle}{[i_{3}-i_{1}]}\cdot\frac{\langle i_{3}\rangle-\langle
i_{2}\rangle}{[i_{3}-i_{2}]}\right|\leq
O\left(\Delta^{2}\cdot\log^{2}k\cdot\mbox{$\|{H}\|$}^{3}\right).$

###### Proof of Lemma 51.

We apply Claim 22 to the first sum and obtain
$O\left(\Delta\max\left\\{g^{\prime}\left(x_{i_{1}}\right),g^{\prime}\left(x_{i_{3}}\right)\right\\}\right)$
(note that we have $\max\\{\cdot,\cdot\\}$ to compensate for the fact that
$x_{i_{1}}\geq x_{i_{3}}$ or $x_{i_{3}}\geq x_{i_{1}}$). Therefore, the left
hand side in Lemma 51 can be upper bounded by

$\displaystyle O\left(\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}}\Delta\left|\max\left\\{g^{\prime}\left(x_{i_{1}}\right),g^{\prime}\left(x_{i_{3}}\right)\right\\}\cdot\frac{g\left(x_{i_{3}}\right)-g\left(x_{i_{2}}\right)}{x_{i_{3}}-x_{i_{2}}}\cdot
G\left(x_{-\left\\{i_{1},i_{2},i_{3}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle O\left(\sum_{i_{1}\neq i_{2}\neq
i_{3}:\atop x_{i_{3}}>x_{i_{2}}\geq 0,x_{i_{1}}\geq
0}\left(\cdots\right)+\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}\geq 0,x_{i_{1}}<0}\left(\cdots\right)+\sum_{i_{1}\neq
i_{2}\neq i_{3}:\atop x_{i_{3}}>x_{i_{2}},x_{i_{2}}<0,x_{i_{1}}\geq
0}\left(\cdots\right)+\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}<0,x_{i_{2}}<0}\left(\cdots\right)\right)$

First term in Eq. (LABEL:eqn:casev1). Note that
$g\left(x\right)\geq\frac{1}{2}$ if $x\geq 0$. Since $g^{\prime}$ is monotone
decreasing in the interval $[0,\infty)$, the first summation is upper bounded
by

$\displaystyle O\left(\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}\geq 0,x_{i_{1}}\geq
0}\Delta\left|\max\left\\{g^{\prime}\left(x_{i_{1}}\right)g^{\prime}\left(x_{i_{2}}\right)G\left(x_{-i_{3}}\right),g^{\prime}\left(x_{i_{3}}\right)g^{\prime}\left(x_{i_{2}}\right)G\left(x_{-i_{1}}\right)\right\\}H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right|\right)$
(63) $\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\|G^{(2)}\|_{1}\cdot\max_{i_{1},i_{2}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle O\left(\Delta\cdot\log
k\cdot\max_{i_{1},i_{2}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)\leq
O\left(\Delta\cdot\log k\cdot\mbox{$\|{H^{3}}\|$}\right)$

where the second inequality is from Fact 20 and the last inequality follows by
Eq. (38).

Second term in Eq. (LABEL:eqn:casev1). The second summation is upper bounded
as follows. Again by the mean value theorem, we observe that

$\displaystyle O\left(\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}\geq
0,x_{i_{1}}<0}\Delta\left|\max\left\\{g^{\prime}\left(x_{i_{1}}\right)g^{\prime}\left(x_{i_{2}}\right),g^{\prime}\left(x_{i_{3}}\right)g^{\prime}\left(x_{i_{2}}\right)\right\\}G\left(x_{-i_{1}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\sum_{i_{1}:x_{i_{1}}<0}\mbox{$\|{G^{(1)}\left(x_{-i_{1}}\right)}\|$}_{1}\max_{i_{2}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|+\mbox{$\|{G^{(2)}\left(x_{-i_{1}}\right)}\|$}_{1}\max_{i_{2},i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right),$

where the last inequality is from Fact 20, Eq. (38) and the assumption that
$\left|\left\\{i:x_{i}\leq 0\right\\}\right|\leq 3\log k$.

Third term in Eq. (LABEL:eqn:casev1). Using the fact that $g^{\prime}(\cdot)$
is bounded by a constant, the third summation is upper bounded by

$\displaystyle O\left(\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{2}}<0,x_{i_{1}}\geq
0}\Delta\left|\max\left\\{g^{\prime}\left(x_{i_{1}}\right),g^{\prime}\left(x_{i_{3}}\right)\right\\}\cdot
G\left(x_{-\left\\{i_{2},i_{3}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
(64) $\displaystyle=$ $\displaystyle O\left(\sum_{i_{1}\neq i_{2}\neq
i_{3}:\atop x_{i_{3}}>x_{i_{2}},x_{i_{1}}\geq 0,x_{i_{2}}<0,x_{i_{3}}\geq
0}\left(\cdots\right)+\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}\geq
0,x_{i_{2}}<0,x_{i_{3}}<0}\left(\cdots\right)\right).$

For the first summation in Eq. (64), using the fact that
$g\left(x\right)\geq\frac{1}{2}$ when $x\geq 0$, it is upper bounded by

$\displaystyle O\left(\Delta\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}\geq 0,x_{i_{2}}<0,x_{i_{3}}\geq
0}\left|\max\left\\{g^{\prime}\left(x_{i_{1}}\right),g^{\prime}\left(x_{i_{3}}\right)\right\\}\cdot
G\left(x_{-\left\\{i_{2}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\sum_{i_{2}:x_{i_{2}}<0}\|G^{(1)}\|_{1}\max_{i_{1}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\sum_{i_{2}:x_{i_{2}}<0}\sqrt{\log
k}\max_{i_{1}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right),$

where the second inequality is from Fact 20, and the last inequality used Eq.
(38) and the assumption that $\left|\left\\{i:x_{i}\leq 0\right\\}\right|\leq
3\log k$.

In order to upper bound the second summation in Eq. (64), first observe that
both $g\left(\cdot\right)$ and $G\left(\cdot\right)$ are positive and upper
bounded by $1$. Thus, Eq. (64) can be bounded as

$\displaystyle O\left(\Delta\sum_{i_{2}\neq i_{3}:\atop
x_{i_{2}}<0,x_{i_{3}}<0}\sum_{i_{1}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)\leq
O\left(\Delta\cdot\log^{2}k\cdot\mbox{$\|{H}\|$}^{3}\right).$

where we again use Eq. (38) and the assumption that $\left|\left\\{i:x_{i}\leq
0\right\\}\right|\leq 3\log k$.

Fourth term in Eq. (LABEL:eqn:casev1). The last summation is upper bounded by
$O\left(\Delta\cdot\log^{2}k\cdot\mbox{$\|{H}\|$}^{3}\right)$ using the same
arguments to upper bound the second summation in Eq. (64). ∎

###  A.2 Upper bounding $(\dagger)$ first term in $(\star)$ in Eq. (59)

We upper bound the quantity in $(\star)$ in two cases that
$x_{i_{1}}>x_{i_{2}}$ and $x_{i_{2}}>x_{i_{1}}$. In order to prove this lemma
we need the following lemmas and claims.

######  Claim 52.

For integer $k\geq 1$, $X\in\mathsf{Sym}_{k}$ and $H\in\mathsf{Mat}_{k}$ it
holds that

$\big{\|}\left(XH+HX\right)e^{-\frac{X^{2}}{2}}\big{\|}_{2}\leq
2\mbox{$\|{X}\|$}\cdot\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}$

and

$\big{\|}e^{-\frac{X^{2}}{2}}\left(XH+HX\right)\big{\|}_{2}\leq
2\mbox{$\|{X}\|$}\cdot\mbox{$\|{e^{-X^{2}/2}H}\|$}_{2}$

###### Proof.

As the Schattern norm is unitarily invariant, we assume that $X=\mbox{\rm
diag}\left(x_{1},\ldots,x_{n}\right)$ is diagonal without loss of generality.
Then

$\mbox{$\|{\left(XH+HX\right)e^{-X^{2}/2}}\|$}_{2}^{2}=\sum_{i,j}H_{i,j}^{2}\left(x_{i}+x_{j}\right)^{2}e^{-x_{j}^{2}}\leq
4\mbox{$\|{X}\|$}^{2}\cdot\sum_{i,j}H_{i,j}^{2}e^{-x_{j}^{2}}=4\Delta^{2}\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}.$

The second inequality follows by the same argument. ∎

######  Lemma 53.

Given an integer $k\geq 1$, $u_{1},u_{2},u_{3}\geq 0$ satisfying
$u_{1}+u_{2}+u_{3}=1$ and
$X\in\mathsf{Sym}_{k},H_{1},H_{2},H_{3}\in\mathsf{Mat}_{k}$, if
$u_{1},u_{3}\leq\frac{1}{2}$, then it holds that

$\displaystyle\left|\mbox{\rm
Tr}\left[e^{-u_{1}X^{2}}H_{1}e^{-u_{2}X^{2}}H_{2}e^{-u_{3}X^{2}}H_{3}\right]\right|$
$\displaystyle\leq$
$\displaystyle\left(\mbox{$\|{H_{1}e^{-\frac{1}{2}X^{2}}}\|$}_{2}+\mbox{$\|{e^{-\frac{1}{2}X^{2}}H_{1}}\|$}_{2}\right)\cdot\left(\mbox{$\|{H_{2}e^{-\frac{1}{2}X^{2}}}\|$}_{2}+\mbox{$\|{e^{-\frac{1}{2}X^{2}}H_{2}}\|$}_{2}\right)\cdot\mbox{$\|{H_{3}}\|$}.$

###### Proof.

Using the inequality $\left|\mbox{\rm
Tr}ABC\right|\leq\mbox{$\|{A}\|$}_{2}\cdot\mbox{$\|{B}\|$}_{2}\cdot\mbox{$\|{C}\|$}$
(where $\|\cdot\|_{2}$ is the standard Frobenius norm and $\|\cdot\|$ is the
spectral norm), we have

$\displaystyle\left|\mbox{\rm
Tr}\left[e^{-u_{1}X^{2}}H_{1}e^{-u_{2}X^{2}}H_{2}e^{-u_{3}X^{2}}H_{3}\right]\right|\
$ $\displaystyle\leq$
$\displaystyle\mbox{$\|{e^{-u_{1}X^{2}}H_{1}e^{\left(u_{1}-\frac{1}{2}\right)X^{2}}}\|$}_{2}\cdot\mbox{$\|{e^{-u_{3}X^{2}}H_{2}e^{\left(u_{3}-\frac{1}{2}\right)X^{2}}}\|$}_{2}\cdot\mbox{$\|{H_{3}}\|$}.$

We conclude the result by Lemma 54. ∎

######  Lemma 54.

Given diagonal matrices $A=\mbox{\rm
diag}\left(a_{1},\ldots,a_{k}\right),B=\mbox{\rm
diag}\left(b_{1},\ldots,b_{k}\right)$ with $a_{1}\geq\cdots\geq a_{k}\geq 0$
and $b_{1}\geq\cdots\geq b_{k}\geq 0$ and an arbitrary matrix $H$, it holds
that

$\mbox{$\|{AHB}\|$}_{2}^{2}+\mbox{$\|{BHA}\|$}_{2}^{2}\leq\mbox{$\|{HAB}\|$}_{2}^{2}+\mbox{$\|{ABH}\|$}_{2}^{2}.$

In particular,

$\mbox{$\|{AHB}\|$}_{2}\leq\mbox{$\|{HAB}\|$}_{2}+\mbox{$\|{ABH}\|$}_{2}.$

###### Proof.

Note that

$\displaystyle\left(\mbox{$\|{HAB}\|$}_{2}^{2}+\mbox{$\|{ABH}\|$}_{2}^{2}\right)-\left(\mbox{$\|{AHB}\|$}_{2}^{2}+\mbox{$\|{BHA}\|$}_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\sum_{i,j}H_{i,j}^{2}\left(a_{i}^{2}b_{i}^{2}+a_{j}^{2}b_{j}^{2}-a_{i}^{2}b_{j}^{2}-a_{j}^{2}b_{i}^{2}\right)$
$\displaystyle=$
$\displaystyle\sum_{i,j}\left(a_{i}^{2}-a_{j}^{2}\right)\left(b_{i}^{2}-b_{j}^{2}\right)\geq
0,$

where the first equality is from the symmetry. ∎

######  Lemma 55.

Given an integer $k\geq 1$, matrices $A,B,C\in\mathsf{Mat}_{k}$ and
$X\in\mathsf{Sym}_{k}$ with $\mbox{$\|{X}\|$}\leq\Delta$, it holds that

$\displaystyle\left|\mbox{\rm
Tr}\left[D^{2}\left(e^{-X^{2}/2}\right)\left[A,B\right]C\right]\right|$
$\displaystyle\leq$ $\displaystyle
4\Delta^{2}\cdot\max\begin{Bmatrix}\left(\mbox{$\|{Ae^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}A}\|$}_{2}\right)\cdot\left(\mbox{$\|{Be^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}B}\|$}_{2}\right)\cdot\mbox{$\|{C}\|$},\\\
\left(\mbox{$\|{Ae^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}A}\|$}_{2}\right)\cdot\left(\mbox{$\|{Ce^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}C}\|$}_{2}\right)\cdot\mbox{$\|{B}\|$},\\\
\left(\mbox{$\|{Be^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}B}\|$}_{2}\right)\cdot\left(\mbox{$\|{Ce^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}C}\|$}_{2}\right)\cdot\mbox{$\|{A}\|$}\end{Bmatrix}.$

###### Proof.

Combining Lemma 12, Lemma 53 and the inequality that

$\mbox{$\|{\left(XA+AX\right)e^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}\left(XA+AX\right)}\|$}_{2}\leq
2\Delta\left(\mbox{$\|{Ae^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}A}\|$}_{2}\right)$

and

$\mbox{$\|{\left(XB+BX\right)e^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}\left(XB+BX\right)}\|$}_{2}\leq
2\Delta\left(\mbox{$\|{Be^{-X^{2}/2}}\|$}_{2}+\mbox{$\|{e^{-X^{2}/2}B}\|$}_{2}\right)$

and

$\mbox{$\|{XA+AX}\|$}\leq 2\Delta\mbox{$\|{A}\|$},\hskip
11.38109pt\mbox{$\|{XB+BX}\|$}\leq 2\Delta\mbox{$\|{B}\|$},$

we conclude the result. ∎

######  Lemma 56.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{1}}>x_{i_{2}},x_{i_{3}}>x_{i_{2}}}\frac{\frac{\langle
i_{3}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{1}\rangle\langle i_{3}\rangle\right|\leq
O\left(\Delta^{2}\cdot\log^{2.5}k\mbox{$\|{H}\|$}^{3}\right).$

###### Proof of Lemma 56.

We break the summation into two summations

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}\atop
x_{i_{1}}>x_{i_{3}}>x_{i_{2}}}\left(\cdots\right)\right|+\left|\sum_{i_{1}\neq
i_{2}\neq i_{3}\atop x_{i_{3}}>x_{i_{1}}>x_{i_{2}}}\left(\cdots\right)\right|$
(65)

For the first summation, we define

$A_{i,j}=\begin{cases}H_{i,j},&\mbox{if $x_{i}<x_{j}$}\\\
0,&\mbox{otherwise}.\end{cases}$

and Then $\mbox{$\|{A}\|$}\leq\log k\cdot\mbox{$\|{H}\|$}$ by Fact 4 (without
loss of generality, we may assume that $x_{i}$s are sorted in increasing
order. Further notice that all the diagonal entries of $H$ are zeros. Thus $A$
is the upper triangle part of $H$). We first bound the first term in Eq. (65).
In this direction, we first rewrite it as

$\displaystyle\frac{1}{\sqrt{2\pi}}\sum_{i_{2}}G\left(x_{-i_{2}}\right)\left(\left(D^{2}\left(e^{-X^{2}/2}\right)[A,A^{T}]H\right)_{i_{2},i_{2}}\right)=\frac{1}{\sqrt{2\pi}}\sum_{i_{2}{x_{i_{2}}<0}}\left(\cdots\right)+\frac{1}{\sqrt{2\pi}}\sum_{i_{2}:x_{i_{2}}\geq
0}\left(\cdots\right)$ (66)

where $X=\mbox{\rm diag}\left(x_{1},\ldots,x_{k}\right)$ and we implicitly
used that we are summing over terms with $x_{i_{2}}<x_{i_{3}}$. Note that $A$
is obtained from $H$ by zeroing out part of entries. Thus

$\max\left\\{\mbox{$\|{Ae^{-X^{2}/2}}\|$}_{2},\mbox{$\|{A^{T}e^{-X^{2}/2}}\|$}_{2},\mbox{$\|{e^{-X^{2}/2}A}\|$}_{2},\mbox{$\|{e^{-X^{2}/2}A^{T}}\|$}_{2}\right\\}\leq\mbox{$\|{He^{-X^{2}/2}}\|$}_{2},$
(67)

To upper bound first summation in Eq. (66), we apply Lemma 55, Eq. (67) and
inequalities $\mbox{$\|{A}\|$}\leq\log k\cdot\mbox{$\|{H}\|$}$ and
$\mbox{$\|{HE_{i_{2},i_{2}}}\|$}\leq\mbox{$\|{H}\|$}$ and obtain

$\left|\mbox{\rm
Tr}\left(D^{2}\left(e^{-X^{2}/2}\right)[A,A^{T}]HE_{i_{2},i_{2}}\right)\right|\leq
16\Delta^{2}\log k\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\cdot\mbox{$\|{H}\|$}.$
(68)

Thus, the first summation in Eq. (66) is upper bounded by

$\displaystyle\frac{\Delta^{2}\cdot\log
k}{\sqrt{2\pi}}\sum_{i_{2}:x_{i_{2}}<0}G\left(x_{-i_{2}}\right)\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\cdot\mbox{$\|{H}\|$}$
(69) $\displaystyle=$ $\displaystyle\left(\Delta^{2}\log
k\cdot\sum_{i_{2}:x_{i_{2}}<0}G\left(x_{-i_{2}}\right)\sum_{i_{1},i_{3}}e^{-x_{i_{3}}^{2}}H_{i_{1},i_{3}}^{2}\mbox{$\|{H}\|$}\right)$
$\displaystyle\leq$
$\displaystyle\left(\Delta^{2}\log^{2}k\cdot\max_{i_{2}}\sum_{i_{1}\neq
i_{3}}g^{\prime}\left(x_{i_{3}}\right)\cdot G\left(x_{-i_{2}}\right)\cdot
H_{i_{1},i_{3}}^{2}\mbox{$\|{H}\|$}\right)$ $\displaystyle\leq$ $\displaystyle
O\left(\Delta^{2}\log^{2.5}k\mbox{$\|{H}\|$}^{3}\right),$

where the first inequality is from the assumption that
$\left|\left\\{i:x_{i}<0\right\\}\right|\leq 3\log k$ and the second
inequality is from Fact 20.

For the second summation in Eq. (66), we define

$\tilde{H}_{i,j}=\begin{cases}\frac{H_{i,j}}{g\left(x_{j}\right)},&\mbox{if
$x_{j}\geq 0$}\\\ 0,&\mbox{otherwise}.\end{cases}$

Then $\mbox{$\|{\tilde{H}}\|$}\leq 2\mbox{$\|{H}\|$}$ as
$g\left(x_{i}\right)\geq\frac{1}{2}$ if $x_{i}\geq 0$. Again applying Eq.
(67), we can verify that the second summation in Eq. (66) is equal to

$\displaystyle\left|\frac{1}{\sqrt{2\pi}}G\left(x\right)\mbox{\rm
Tr}~{}D^{2}\left(e^{-X^{2}/2}\right)[A,A^{T}]\tilde{H}\right|\leq\frac{16\Delta^{2}\log
k}{\sqrt{2\pi}}G\left(x\right)\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\mbox{$\|{H}\|$}\leq
O\left(\Delta^{2}\cdot\log^{1.5}k\mbox{$\|{H}\|$}^{3}\right).$

where the first inequality is from Lemma 55 and the second inequality is from
Fact 20.

Finally, the second summation in Eq. (65) can be upper bounded using the
verbatim same arguments by
$O\left(\Delta^{2}\cdot\log^{2.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$. This
proves the lemma statement. ∎

######  Lemma 57.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}>x_{i_{2}}}\frac{\frac{\langle
i_{3}\rangle-\langle i_{1}\rangle}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle-\langle i_{1}\rangle}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{1}\rangle^{\prime}\langle i_{3}\rangle\right|\leq
O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$

###### Proof.

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}>x_{i_{2}}}\frac{\frac{\langle
i_{3}\rangle-\langle i_{1}\rangle}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle-\langle i_{1}\rangle}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{1}\rangle^{\prime}\langle i_{3}\rangle\right|=\left|\sum_{i_{1}\neq
i_{2}\neq i_{3}:\atop x_{i_{3}}>x_{i_{2}},x_{i_{1}}>x_{i_{2}}\geq
0}\left(\cdots\right)+\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}>0,x_{i_{2}}<0}\left(\cdots\right)\right|$ (70)

To upper bound the first summation in Eq. (70), we apply Fact 3 and upper
bound the first summation by

$\displaystyle O\left(\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}},x_{i_{1}}>x_{i_{2}}\geq
0}\left|g^{\prime\prime}\left(\xi_{i_{1},i_{2},i_{3}}\right)g^{\prime}\left(x_{i_{1}}\right)G\left(x_{-\left\\{i_{1},i_{2}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle O\left(\left|\Delta\cdot\sum_{i_{1}\neq
i_{2}\neq i_{3}:\atop x_{i_{3}}>x_{i_{2}},x_{i_{1}}>x_{i_{2}}\geq
0}g^{\prime}\left(x_{i_{2}}\right)g^{\prime}\left(x_{i_{1}}\right)G\left(x_{-\left\\{i_{1},i_{2}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\mbox{$\|{G^{(2)}\left(x\right)}\|$}_{2}\max_{i_{1},i_{2}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle O\left(\Delta\cdot\log
k\cdot\mbox{$\|{H}\|$}^{3}\right)$

where the last inequality is from Fact 20 and Eq. (38). Note that
$\left|g^{\prime\prime}\left(\xi\right)\right|\leq\Delta$ for any
$\xi\in[x_{i_{2}},\max\left\\{x_{i_{1}},x_{i_{3}}\right\\}]$ by Eq. (13).
Applying Fact 3, the second summation in Eq. (70) is upper bounded by

$\displaystyle
O\left(\Delta\sum_{i_{2}:x_{i_{2}}<0}\sum_{i_{1},i_{3}}g^{\prime}\left(x_{i_{1}}\right)G\left(x_{-\left\\{i_{1},i_{2}\right\\}}\right)\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle O\left(\Delta\cdot\log
k\cdot\max_{i_{2}}\mbox{$\|{G^{(1)}\left(x_{-i_{2}}\right)}\|$}_{1}\cdot\max_{i_{1}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$

where the first inequality is from the assumption that
$\left|\left\\{i:x_{i}<0\right\\}\right|\leq 3\log k$ and the second
inequality is from Fact 20 and Eq. (38). ∎

###  A.3 Upper bounding first term in $(\dagger\dagger)$ in Eq. (60)

We now bound the first term in Eq. (60) when $x_{i_{3}}>x_{i_{2}}>x_{i_{1}}$.
Recall that the goal is to upper bound the following lemma.

######  Lemma 58.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\frac{\frac{\langle i_{1}\rangle\langle
i_{3}\rangle^{\prime}-\langle i_{3}\rangle\langle
i_{3}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}-\langle i_{2}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{3}\rangle\right|\leq
O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$

###### Proof of Lemma 58.

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\frac{\frac{\langle i_{1}\rangle\langle
i_{3}\rangle^{\prime}-\langle i_{3}\rangle\langle
i_{3}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}-\langle i_{2}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{3}\rangle\right|$ (71) $\displaystyle\leq$ $\displaystyle\sum_{i_{1}\neq
i_{2}\neq i_{3}:\atop x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\left|\frac{\frac{\langle
i_{1}\rangle\langle i_{2}\rangle^{\prime}-\langle i_{3}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}-\langle i_{2}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{3}\rangle\right|+\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\left|\frac{\frac{\langle i_{1}\rangle\langle
i_{3}\rangle^{\prime}-\langle i_{3}\rangle\langle
i_{3}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle i_{1}\rangle\langle
i_{2}\rangle^{\prime}-\langle i_{3}\rangle\langle
i_{2}\rangle^{\prime}}{[i_{3}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{3}\rangle\right|$ $\displaystyle=$ $\displaystyle\sum_{i_{1}\neq i_{2}\neq
i_{3}:\atop x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\left|\frac{\frac{\langle
i_{1}\rangle-\langle i_{3}\rangle}{[i_{3}-i_{1}]}-\frac{\langle
i_{1}\rangle-\langle i_{2}\rangle}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{2}\rangle^{\prime}\langle i_{3}\rangle\right|+\sum_{i_{1}\neq i_{2}\neq
i_{3}:\atop x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\left|\frac{\langle
i_{1}\rangle-\langle i_{3}\rangle}{[i_{3}-i_{1}]}\cdot\frac{\langle
i_{3}\rangle^{\prime}-\langle
i_{2}\rangle^{\prime}}{[i_{3}-i_{2}]}\cdot\langle i_{3}\rangle\right|$

The first term is upper bounded by
$O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$ using the same
argument in Lemma 57. The second term can be rephrased as

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\frac{g\left(x_{i_{1}}\right)-g\left(x_{i_{3}}\right)}{x_{i_{3}}-x_{i_{1}}}\cdot\frac{g^{\prime}\left(x_{i_{3}}\right)-g^{\prime}\left(x_{i_{2}}\right)}{x_{i_{3}}-x_{i_{2}}}g\left(x_{i_{3}}\right)G\left(x_{-i_{1}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|$
(72) $\displaystyle\leq$ $\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq
i_{3}:\atop x_{i_{3}}>x_{i_{2}}>x_{i_{1}},x_{i_{1}}\geq
0}\left(\cdots\right)\right|+\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}},x_{i_{1}}<0}\left(\cdots\right)\right|$

For the first summation in Eq. (72), we apply the mean value theorem for both
$g$ and $g^{\prime}$. From Eq. (13) it is upper bounded by

$\displaystyle\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}},x_{i_{1}}\geq
0}\Delta\left|g^{\prime}\left(x_{i_{1}}\right)g^{\prime}\left(x_{i_{2}}\right)g\left(x_{i_{3}}\right)G\left(x_{-i_{1}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\mbox{$\|{G^{(2)}\left(x\right)}\|$}_{1}\mbox{$\|{H}\|$}^{3}\right)$
$\displaystyle\leq$ $\displaystyle O\left(\Delta\cdot\log
k\cdot\mbox{$\|{H}\|$}^{3}\right).$

For the second term in Eq. (72), it is not hard to verify that

$\left|\frac{g^{\prime}\left(x_{i_{3}}\right)-g^{\prime}\left(x_{i_{2}}\right)}{x_{i_{3}}-x_{i_{2}}}\right|\leq\Delta\max\left\\{g^{\prime}\left(x_{i_{3}}\right),g\left(x_{i_{2}}\right)\right\\}$
(73)

Further notice that $\left|g^{\prime}\left(\cdot\right)\right|\leq 1$.
Applying the mean value theorem to $g$, we upper bound the second summation in
72 by

$\displaystyle O\left(\Delta\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}},x_{i_{1}}<0}\max\left\\{g^{\prime}\left(x_{i_{3}}\right),g^{\prime}\left(x_{i_{2}}\right)\right\\}g\left(x_{i_{3}}\right)G\left(x_{-i_{1}}\right)\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle O\left(\Delta\cdot\log
k\cdot\max_{i_{1}}\cdot\mbox{$\|{G^{(1)}\left(x_{-i_{1}}\right)}\|$}_{1}\cdot\max_{i_{2}}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$

where the first inequality is from the assumption that
$\left|\left\\{i:x_{i}<0\right\\}\right|\leq 3\log k$ and the second
inequality is from Fact 20 Eq. (38). ∎

###  A.4 Upper bounding the second term ($\P$) in Eq. (60)

Let us rewrite ($\P$) as a sum of two term as in Eq. (61). We first upper
bound the first easy term.

######  Lemma 59.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\frac{\langle i_{3}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}\cdot\frac{\langle i_{3}\rangle-\langle
i_{2}\rangle}{[i_{3}-i_{2}]}\cdot\langle i_{3}\rangle\right|\leq
O\left(\Delta\cdot\log^{2}k\cdot\mbox{$\|{H}\|$}^{3}\right)$

###### Proof of Lemma 59.

We split the summation into two cases that $x_{i_{2}}\geq 0$ and
$x_{i_{2}}<0$. For the case that $x_{i_{2}}\geq 0$, we apply the mean value
theorem to $g\left(\cdot\right)$ and Eq. (73), it is upper bounded by
$O\left(\Delta\cdot\log k\cdot\mbox{$\|{H}\|$}^{3}\right)$. For the case that
$x_{i_{2}}<0$, we have $x_{i_{1}}<0$. Note that
$\left|g^{\prime}\left(\cdot\right)\right|\leq 1$. Thus it is upper bounded by

$O\left(\sum_{i_{1}\neq i_{2}:\atop
x_{i_{1}}<x_{i_{2}}<0}\sum_{i_{3}}\left|H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\right)\leq
O\left(\log^{2}k\cdot\mbox{$\|{H}\|$}^{3}\right).$

∎

Next, our goal is to prove an upper bound on the second term in Eq. (61).

######  Lemma 60.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}:\atop
x_{i_{3}}>x_{i_{2}}>x_{i_{1}}}\frac{\frac{\langle
i_{3}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle
i_{2}\rangle^{\prime}-\langle
i_{1}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\langle
i_{2}\rangle\langle i_{3}\rangle\right|\leq O\left(\sqrt{\log
k}\cdot\mbox{$\|{H}\|$}^{3}\right).$

Before we prove this lemma, we first prove a “simpler” proposition which will
be crucial in upper bound the above.

######  Proposition 61.

$\left|\sum_{i_{1}\neq i_{2}\neq i_{3}}\frac{\frac{\langle
i_{1}\rangle^{\prime}-\langle
i_{3}\rangle^{\prime}}{[i_{3}-i_{1}]}-\frac{\langle
i_{1}\rangle^{\prime}-\langle
i_{2}\rangle^{\prime}}{[i_{2}-i_{1}]}}{[i_{3}-i_{2}]}\right|\leq
O\left(\Delta^{2}\cdot\sqrt{\log k}\cdot\mbox{$\|{H}\|$}^{3}\right)$

###### Proof.

Using Fact 10,

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq
i_{3}}\frac{\frac{g^{\prime}\left(x_{i_{3}}\right)-g^{\prime}\left(x_{i_{1}}\right)}{x_{i_{3}}-x_{i_{1}}}-\frac{g^{\prime}\left(x_{i_{2}}\right)-g^{\prime}\left(x_{i_{1}}\right)}{x_{i_{2}}-x_{i_{1}}}}{x_{i_{3}}-x_{i_{2}}}G\left(x\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|=\frac{1}{\sqrt{2\pi}}\left|\mbox{\rm
Tr}\left[D^{2}\left(e^{-\frac{X^{2}}{2}}\right)[H,H]\cdot
H\right]\right|G\left(x\right),$

where $X=\mbox{\rm diag}\left(x_{1},\ldots,x_{n}\right)$. Using Lemma 12, it
suffices to upper bound

$G\left(x\right)\left|\mbox{\rm
Tr}\left[e^{-\frac{uX^{2}}{2}}\left(XH+HX\right)e^{-\frac{v\left(1-u\right)X^{2}}{2}}\left(XH+HX\right)e^{-\frac{\left(1-v\right)\left(1-u\right)X^{2}}{2}}H\right]\right|$
(74)

and

$G\left(x\right)\left|\mbox{\rm
Tr}\left[e^{\frac{\left(u-1\right)X^{2}}{2}}H^{2}e^{-\frac{uX^{2}}{2}}H\right]\right|$
(75)

Note that $u+v\left(1-u\right)+\left(1-v\right)\left(1-u\right)$=1. At least
two of these three quantities are at most $\frac{1}{2}$. We upper bound Eq.
(74) in the following three cases.

If $u\leq\frac{1}{2}$ and $\left(1-u\right)\left(1-v\right)\leq\frac{1}{2}$,
using Claim 52, Lemma 53 and the fact that
$\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}=\mbox{$\|{e^{-X^{2}/2}H}\|$}_{2}$ as $H$ is
symmetric Eq. (74) is upper bounded by

$\displaystyle\big{\|}\left(XH+HX\right)e^{-\frac{X^{2}}{2}}\big{\|}_{2}^{2}\mbox{$\|{H}\|$}\leq
16\Delta^{2}\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\cdot\mbox{$\|{H}\|$}.$

If $u\leq\frac{1}{2}$ and $v\left(1-u\right)\leq\frac{1}{2}$, then the Eq.
(74) is upper bounded by

$\displaystyle\mbox{$\|{\left(XH+HX\right)e^{-\frac{X^{2}}{2}}}\|$}_{2}\cdot\mbox{$\|{He^{-\frac{X^{2}}{2}}}\|$}_{2}\mbox{$\|{XH+HX}\|$}$
$\displaystyle\leq$ $\displaystyle
2\Delta\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\cdot\mbox{$\|{XH+HX}\|$}$
$\displaystyle\leq$ $\displaystyle
4\Delta^{2}\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\cdot\mbox{$\|{H}\|$}.$

where the second last inequality is by Claim 52. The case that
$u\left(1-v\right)\leq\frac{1}{2}$ and $v\left(1-u\right)\leq\frac{1}{2}$
follows similarly. Also Eq. (75) can be upper bounded with similar arguments.
Thus

$G\left(x\right)\cdot\left|\mbox{\rm
Tr}~{}e^{\left(u-1\right)X^{2}/2}H^{2}e^{-uX^{2}/2}H\right|\leq
16\Delta^{2}G\left(x\right)\mbox{$\|{H}\|$}\cdot\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}.$
(76)

Therefore,

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq
i_{3}}\frac{\frac{g^{\prime}\left(x_{i_{3}}\right)-g^{\prime}\left(x_{i_{1}}\right)}{x_{i_{3}}-x_{i_{1}}}-\frac{g^{\prime}\left(x_{i_{2}}\right)-g^{\prime}\left(x_{i_{1}}\right)}{x_{i_{2}}-x_{i_{1}}}}{x_{i_{3}}-x_{i_{2}}}G\left(x\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|$
$\displaystyle\leq$ $\displaystyle\left(G(x)\cdot\mbox{\rm
Tr}\left[D^{2}\left(e^{-\frac{X^{2}}{2}}\right)[H,H]\cdot H\right]\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta^{2}G\left(x\right)\mbox{$\|{H}\|$}\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\right)$
$\displaystyle=$ $\displaystyle
O\left(\Delta^{2}\sum_{i_{1},i_{2}}e^{-x_{i_{2}}^{2}}H_{i_{1},i_{2}}^{2}G\left(x\right)\cdot\mbox{$\|{H}\|$}\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta^{2}\sum_{i_{1},i_{2}}g^{\prime}\left(x_{i_{2}}\right)G\left(x\right)H_{i_{1},i_{2}}^{2}\cdot\mbox{$\|{H}\|$}\right)\quad$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta^{2}\sum_{i_{1},i_{2}}g^{\prime}\left(x_{i_{2}}\right)G\left(x_{-i_{2}}\right)H_{i_{1},i_{2}}^{2}\cdot\mbox{$\|{H}\|$}\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta^{2}\mbox{$\|{G^{(1)}\left(x\right)}\|$}_{1}\cdot\left(\max_{i_{2}}\sum_{i_{1}}H_{i_{1},i_{2}}^{2}\right)\cdot\mbox{$\|{H}\|$}\right)$
$\displaystyle\leq$ $\displaystyle
O\left(\Delta^{2}\mbox{$\|{G^{(1)}\left(x\right)}\|$}_{1}\cdot\max_{i_{2}}\left(H^{2}\right)_{i_{2},i_{2}}\cdot\mbox{$\|{H}\|$}\right)$
$\displaystyle\leq$ $\displaystyle O\left(\Delta^{2}\cdot\sqrt{\log
k}\cdot\mbox{$\|{H}\|$}^{3}\right),$ (78)

where the second inequality used $e^{-x_{i}^{2}/2}\leq 1$, third inequality
used $g(x)\in[0,1]$ and the last inequality is from Fact 20. ∎

We are now ready to prove the main lemma. Note that end of the day we need to
bound the inequality in Lemma 60 which can be written as

$\displaystyle\left|\sum_{i_{1}\neq i_{2}\neq i_{3}\atop
i_{1}<i_{2},i_{1}<i_{3}}\frac{\frac{g^{\prime}\left(x_{i_{1}}\right)-g^{\prime}\left(x_{i_{3}}\right)}{x_{i_{3}}-x_{i_{1}}}-\frac{g^{\prime}\left(x_{i_{1}}\right)-g^{\prime}\left(x_{i_{2}}\right)}{x_{i_{2}}-x_{i_{1}}}}{x_{i_{3}}-x_{i_{2}}}G\left(x_{-\left\\{i_{1}\right\\}}\right)H_{i_{1},i_{2}}H_{i_{2},i_{3}}H_{i_{3},i_{1}}\right|\leq
O\left(\Delta^{2}\cdot\log^{2.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$ (79)

Observe that in this section we are concerned with
$x_{i_{1}}<x_{i_{2}}<x_{i_{3}}$ so the summation in this lemma and the
equation above are over the same indices.

###### Proof of Lemma 60.

By the paragraph above, proving this lemma is equivalent to proving Eq. (79).
The left hand side of Eq. (79) can be expressed as

$\displaystyle\left|\frac{1}{\sqrt{2\pi}}\sum_{i_{1}}G\left(x_{-i_{1}}\right)\left(\mbox{\rm
Tr}~{}D^{2}\left(e^{-X^{2}/2}\right)\left[A^{i_{1}},\left(A^{i_{1}}\right)^{T}\right]H\right)\right|=\left|\frac{1}{\sqrt{2\pi}}\sum_{i_{1}:x_{i_{1}}<0}\left(\cdots\right)+\frac{1}{\sqrt{2\pi}}\sum_{i_{1}:x_{i_{1}}\geq
0}\left(\cdots\right)\right|$ (80)

For the first summation above, let

$\left(A^{i_{1}}\right)_{i,j}=\begin{cases}H_{i,i_{1}},&\mbox{if $j=i_{1}$ and
$i>i_{1}$}\\\ 0,&\mbox{otherwise}.\end{cases}$

Note that $\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}=\mbox{$\|{e^{-X^{2}/2}H}\|$}_{2}$
as $H$ is symmetric. Using the same argument as Eq. (67), we have

$\max\left\\{\mbox{$\|{A^{i_{1}}e^{-X^{2}/2}}\|$}_{2},\mbox{$\|{\left(A^{i_{1}}\right)^{T}e^{-X^{2}/2}}\|$}_{2},\mbox{$\|{e^{-X^{2}/2}A^{i_{1}}}\|$}_{2},\mbox{$\|{e^{-X^{2}/2}\left(A^{i_{1}}\right)^{T}}\|$}_{2}\right\\}\leq\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}.$

Further notice that
$\mbox{$\|{A^{i_{1}}e^{-X^{2}/2}}\|$}_{2}\leq\mbox{$\|{He^{-X^{2}/2}}\|$}_{2},\mbox{$\|{A^{i_{1}}}\|$}\leq\mbox{$\|{H}\|$},$.
Following the same proof of Proposition 61, we can upper bound the first
summation in Eq. (80) by

$\displaystyle\frac{1}{\sqrt{2\pi}}\sum_{i_{1}:x_{i_{1}}<0}G\left(x_{-i_{1}}\right)\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}^{2}\cdot\mbox{$\|{H}\|$}\leq
O\left(\Delta^{2}\cdot\log^{2.5}k\mbox{$\|{H}\|$}^{3}\right),$

where the inequality follows from the argument in Eq. (69). For the second
summation, define

$B_{i_{1},i_{2}}=\begin{cases}\frac{H_{i_{1},i_{2}}}{\sqrt{g\left(x_{i_{1}}\right)}},&\mbox{if
$x_{i_{1}}\geq 0$}\\\ 0,&\mbox{otherwise}.\end{cases}$

Note that

$\max\left\\{\mbox{$\|{Be^{-X^{2}/2}}\|$}_{2},\mbox{$\|{B^{T}e^{-X^{2}/2}}\|$}_{2},\mbox{$\|{e^{-X^{2}/2}B}\|$}_{2},\mbox{$\|{e^{-X^{2}/2}B^{T}}\|$}_{2}\right\\}\leq\sqrt{2}\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}$

and $\mbox{$\|{B}\|$}\leq\sqrt{2}\mbox{$\|{H}\|$}$ (since $g(x)\geq 1/2$ for
$x\geq 0$). Then the second summation in Eq. (80) is equal to

$\displaystyle\left|G\left(x\right)\frac{1}{\sqrt{2\pi}}\mbox{\rm
Tr}~{}D^{2}\left(e^{-X^{2}/2}\right)\left[B,B^{T}\right]A\right|\leq\frac{1}{\sqrt{\pi}}G\left(x\right)\mbox{$\|{He^{-X^{2}/2}}\|$}_{2}\mbox{$\|{H}\|$}\leq
O\left(\Delta^{2}\cdot\log^{1.5}k\cdot\mbox{$\|{H}\|$}^{3}\right)$

where the inequality follows from the argument in Eq. (69). ∎