Minimax-optimal estimation for sparse multi-reference alignment with collision-free signals

Subhro Ghosh Authors are listed in the alphabetical order of their surnames.Department of Mathematics, National University of Singapore ([email protected]) Soumendu Sundar Mukherjee ¹¹footnotemark: 1 Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata ([email protected]) Jing Bin Pan ¹¹footnotemark: 1 Department of Mathematics, National University of Singapore, ([email protected])Corresponding author: Jing Bin Pan ([email protected])

Abstract

The Multi-Reference Alignment (MRA) problem aims at the recovery of an unknown signal from repeated observations under the latent action of a group of cyclic isometries, in the presence of additive noise of high intensity $\sigma$ . It is a more tractable version of the celebrated cryo EM model. In the crucial high noise regime, it is known that its sample complexity scales as $\sigma^{6}$ . Recent investigations have shown that for the practically significant setting of sparse signals, the sample complexity of the maximum likelihood estimator asymptotically scales with the noise level as $\sigma^{4}$ . In this work, we investigate minimax optimality for signal estimation under the MRA model for so-called collision-free signals. In particular, this signal class covers the setting of generic signals of dilute sparsity (wherein the support size $s=O(L^{1/3})$ , where $L$ is the ambient dimension.

We demonstrate that the minimax optimal rate of estimation in for the sparse MRA problem in this setting is $\sigma^{2}/\sqrt{n}$ , where $n$ is the sample size. In particular, this widely generalizes the sample complexity asymptotics for the restricted MLE in this setting, establishing it as the statistically optimal estimator. Finally, we demonstrate a concentration inequality for the restricted MLE on its deviations from the ground truth.

1 Introduction

1.1 Introduction

Multi-reference alignment (MRA) is the problem of estimating an unknown signal from noisy samples that are subject to latent rotational transformations. In recent years, the MRA model has found practical applications in many scientific fields, such as structural biology StructuralBiology1 StructuralBiology2 StructuralBiology3 StructuralBiology4 StructuralBiology5 StructuralBiology6 , image recognition ImageRecognition1 ImageRecognition2 ImageRecognition3 ImageRecognition4 , robotics Robotics and signal processing SignalProcessing1 SignalProcessing2 , and has garnered significant research interest as a result. Most notably, the MRA model serves as a simplified model for the three-dimensional reconstruction problem in cryo-electron microscopy (cryo-EM) CryoEM1 Generic CryoEM2 .

In this paper, we study the estimation problem in the MRA model MRA1 Generic MRA2 for collision-free signals. Identify the vector space $\mathbb{R}^{L}$ with the space of functions $\mathbb{Z}/L\mathbb{Z}\to\mathbb{R}$ . Let

\displaystyle\mathcal{R}:=\{R^{(\ell)}\ :\ 1\leq\ell\leq L\}

denote the cyclic group of coordinate shifts, where $R^{(\ell)}:\mathbb{R}^{L}\to\mathbb{R}^{L}$ is the linear operator given by $(R^{(\ell)}\theta)(i)=\theta(i+\ell)$ . In the general MRA estimation problem, the objective is to recover an unknown parameter $\theta\in\mathbb{R}^{L}$ , known in the literature as a signal, from $n$ independent noisy observations $X_{1},X_{2},\cdots,X_{n}$ given by

\displaystyle X_{i}=G_{i}\theta+\sigma\xi_{i},\ \ \ \ \ \ \ i\in\{1,\cdots,n\},

(1)

where the $G_{i}$ ’s are drawn from $\mathcal{R}$ independently and uniformly at random and each $\xi_{i}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{I}_{d})$ is i.i.d standard Gaussian noise that is independent of the $R_{i}$ ’s. We remark that while the canonical distribution on $\mathcal{R}$ is uniform, other distributions have also been considered OtherDistribution .

In this model, any vector $\theta$ is statistically indistinguishable from its cyclic shifts $R^{(1)}\theta,\cdots,R^{(L-1)}\theta$ . Consequently, the parameter $\theta$ is only identifiable up to the action of $\mathcal{R}$ . Hence we study the estimation problem under the rotation-invariant distance

\displaystyle\rho(\theta,\phi):=\min_{G\in\mathcal{R}}\left\lVert\theta-G\phi\right\rVert.

Here, $\left\lVert\cdot\right\rVert$ refers to the usual Euclidean norm.

Both the dimension $L$ and the noise level $\sigma$ are assumed to be known. In many practical applications such as cryo-EM, the noise level is very high but can be lowered over time by technological improvements Improvement . As such, understanding the relationship between the difficulty of the estimation problem and the quantity $\left\lVert\theta\right\rVert/\sigma$ , known as the signal-to-noise ratio is of fundamental importance. With that in mind, we focus our work on understanding the asymptotic sampling complexity in the MRA model as $\sigma\to+\infty$ .

The MRA problem, particularly in the low-noise regime, has been mostly attacked using the synchronization approach MRA1 . However, it was recently recognised as a Gaussian mixture model BRW , which enabled the use of various methods such as the method of moments MethodOfMoments Generic and expectation-maximization ExpectationMaximization . For a more detailed discussion on the likelihood landscape of such models, we refer the reader to LikelihoodLandscape1 LikelihoodLandscape2 LikelihoodLandscape3 LikelihoodLandscape4 .

1.2 Estimation rates for MRA and sparsity

In the two seminal papers by Bandeira, Rigollet and Weed BRW Generic in 2017, it was shown that the general MRA model in the high noise regime has a sampling complexity of $O(\sigma^{L})$ in the worst case, and $O(\sigma^{6})$ in the case of signals having full Fourier support. This has motivated investigations into variations of the MRA model where a better sampling complexity may be achieved. One such variation is the MRA estimation problem for certain classes of sparse signals, where the restricted maximum likelihood estimator (abbrv. MLE) has been shown to exhibit an improved sampling complexity of $O(\sigma^{4})$ Sparse . We refer the reader to Sparse1 and Sparse2 for an investigation into algorithmic aspects of sparse MRA and the role of sparsity in the related problem of cryo EM.

While it is of interest to understand the the sample complexity asymptotics for the restricted MLE, it only shades light on the performance of a certain type of estimators. In order to have a complete understanding of the problem, one needs to understand minimax optimal rates of estimation for the model. In other words, the central question is, what is the best possible behaviour over candidate estimators for the worst possible error over a sufficiently rich class of signals. Minimax optimality in statistical problems has a long and rich history; for a detailed account we refer the interested reader to Tsybakov . In the context of the MRA problem, minimax optimal rate of estimation for the general MRA problem is known to be $\sigma^{3}/\sqrt{n}$ (c.f. BRW ; Zhou-Zhou2022 ). However, minimax optimality for the sparse MRA problem is not understood, and in view of different sample complexity asymptotics, is not covered by the minimax theory on general signal spaces. This is the broad direction that we propose to explore in the work.

1.3 The space of collision free signals

In this work, we will focus our attention on a particular class of sparse signals called collision-free signals. For a vector $\theta\in\mathbb{R}^{L}$ , let $\mathcal{D}(\theta)$ denote the multiset of differences

\displaystyle\mathcal{D}(\theta):=\big{\{}i-j\ (\text{mod }L)\ :\ i,j\in\text{supp}(\theta)\text{ with }i\neq j\big{\}}.

We say that $\theta$ is collision-free if each element in $\mathcal{D}(\theta)$ appears with multiplicity exactly $1$ .

The notion of collision-freeness is motivated by the beltway problem in combinatorial optimization. The beltway problem consists of recovering a set $\mathcal{S}$ of integers from their pairwise differences $\mathcal{D}_{\mathcal{S}}$ , up to the trivial symmetry of translating all the numbers in the set by the same amount. In 1939, Piccard Piccard conjectured that if two sets of integers $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ have the same set of pairwise differences $\mathcal{D}$ , and the pairwise differences are known to be unique (i.e. $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are collision-free), then the sets $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ must be translates of each other.

A counterexample to Piccard’s conjecture was found by Bloom Bloom in 1975 for $|\mathcal{S}|=6$ . In 2007, a complete resolution was brought about by Bekir and Golomb Golomb , who showed that Piccard’s conjecture holds for $|\mathcal{S}|\geq 7$ . In our current context, this means that the support of a collision-free signal $\theta$ can be recovered from $\mathcal{D}(\theta)$ up to translation as long as $|\text{Supp}(\theta)|\geq 7$ . This fact will play a crucial role in allowing us to obtain improved bounds on the sampling complexity.

With the above discussion in mind, we will assume that the unknown parameter $\theta$ satisfies:

(i)

$\theta$ is collision free;
(ii)

$\sigma\geq\left\lVert\theta\right\rVert$ ;
(iii)

There exist positive constants $m,M,\epsilon\in\mathbb{R}_{>0}$ such that $m\leq|\theta(i)|\leq M$ for all $i\in\text{Supp}(\theta)$ and $s:=|\text{Supp}(\theta)|\geq\max\{7,(2+\epsilon)M^{2}/m^{2}\}$ .

Let $\mathcal{T}$ denote the set of signals satisfying the above three conditions. In our analysis, we will only keep track of the dependence on $\sigma$ and $s$ . The other quantities $L,m,M$ and $\epsilon$ are fixed throughout the paper

Collision free signals arise as a natural concept in the setting of sparsity, especially in the context of sparse MRA. It is straightforward to envisage that the sparser a signal, the more likely it is for its support to be a collision free subset of $\mathbb{Z}/L\mathbb{Z}$ . Indeed, a randomly chosen subset of $\mathbb{Z}/L\mathbb{Z}$ (with expected size $s$ ) is going to be collision free with high probability as long as $s=O(L^{1/3})$ (c.f Sparse Appendix D). The latter corresponds to the regime of so-called dilute sparsity, per the terminology used in the investigations in Sparse , and has a natural place in the study of sparse MRA.

1.4 Main Results

For a signal $\theta$ , let $P_{\theta}$ denote the distribution of a random variable $X$ satisfying

\displaystyle X=G\theta+\sigma\xi,

where $G$ is drawn from $\mathcal{R}$ uniformly and $\xi_{i}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{I}_{d})$ . Let $f_{\theta}:\mathbb{R}^{d}\to\mathbb{R}$ denote the density function of $P_{\theta}$ . Explicitly,

\displaystyle f_{\theta}(x)

\displaystyle=\frac{1}{\sigma^{L}(2\pi)^{L/2}}\mathbb{E}_{G}\bigg{[}\exp\bigg{(}-\frac{1}{2\sigma^{2}}\left\lVert x-G\theta\right\rVert^{2}\bigg{)}\bigg{]}.

Given $n$ i.i.d samples $X_{1},\cdots,X_{n}$ as in (1), we analyse the performance of the restricted maximum likelihood estimator (MLE) $\tilde{\theta}_{n}$ given by

\displaystyle\tilde{\theta}_{n}:=\underset{\phi\in\mathcal{T}}{\text{arg max}}\sum_{i=1}^{n}\log\mathbb{E}_{G}\bigg{[}\exp\Big{(}-\frac{1}{2\sigma^{2}}\left\lVert X_{i}-G\phi\right\rVert^{2}\Big{)}\bigg{]}.

Our main results are the following two theorems, which characterises the rate of estimation in the collision-free MRA model.

Theorem 1.4.1.

We have that

\inf_{\hat{\theta}_{n}}\sup_{\theta\in\mathcal{T}}\mathbb{E}\big{[}\rho(\hat{\theta}_{n},\theta)\big{]}\asymp\frac{\sigma^{2}}{\sqrt{n}},

(2)

where the infimum is taken over all estimators $\hat{\theta}_{n}$ based on $n$ samples $X_{1},\cdots,X_{n}$ .

Theorem 1.4.2.

Fix a constant $\delta\in(0,2\sqrt{L}M)$ . There exist constants $C_{s},\tilde{C}_{s}\in\mathbb{R}_{>0}$ depending on $s$ such that for all $n\geq C_{s}\delta^{-4}\sigma^{12}$ and for all $\theta\in\mathcal{T}$ , the restricted MLE $\tilde{\theta}_{n}$ satisfies

\displaystyle P(\rho(\tilde{\theta}_{n},\theta)\geq\delta)\leq C_{s}\sigma^{5s}\delta^{-2s}\exp\bigg{(}-\frac{\tilde{C}_{s}n\delta^{4}}{\sigma^{12}}\bigg{)}.

Theorem 1.4.1 is a direct consequence of the following two results, which we state below for independent interest.

The first result is a uniform upper bound for the restricted MLE of $O(\sigma^{4})$ , which is a marked improvement over the pointwise upper bound in (Sparse, , Theorem 4).

Theorem 1.4.3.

There exists positive constants $C$ and $C_{s}$ , where $C_{s}$ depends on $s$ , such that the restricted MLE $\tilde{\theta}_{n}$ satisfies

\mathbb{E}\big{[}\rho(\tilde{\theta}_{n},\theta)\big{]}\leq C\cdot\frac{\sigma^{2}}{\sqrt{n}}+C\cdot\frac{\sigma^{3}\log n}{sn}+C_{s}\cdot\frac{\sigma^{11}}{n}

(3)

uniformly over all choices $\theta\in\mathcal{T}$ for all $\sigma$ sufficiently large.

The second result is a lower bound on the minimax rate of estimation in the sparse MRA model. In particular, it shows that the restricted MLE achieves the optimal sampling complexity of $O(\sigma^{4})$ .

Theorem 1.4.4.

Fix a sparsity $s\in\mathbb{Z}_{\geq 1}$ . Let $\mathcal{T}_{s}$ denote the set of vectors $\theta\in\mathcal{T}$ satisfying $|\text{Supp}(\theta)|=s$ . For any $\sigma\geq\max_{\theta\in\mathcal{T}_{s}}\left\lVert\theta\right\rVert$ , there exists a universal constant $M$ such that

\displaystyle\inf_{\tilde{\theta}_{n}}\sup_{\theta\in\mathcal{T}_{s}}\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\big{]}\geq M\min\bigg{\{}\frac{\sigma^{2}}{\sqrt{n}},\ 1\bigg{\}},

where the infimum is taken over all estimators $\tilde{\theta}_{n}$ on $n$ samples from $P_{\theta}$ .

In section 2, we will introduce the key ingredients that will be used to derive our main results. Sections 3, 4 and 5 are dedicated to the proofs of theorem 1.4.3, 1.4.4 and 1.4.2 respectively.

2 Preliminaries

In this section, we introduce and prove some properties about the Kullback-Leibler divergence and the moment tensors. Both are key tools that play a central role in our analysis.

2.1 Kullback-Leibler Divergence and Moment Tensors

In the MRA model, the Kullback-Leibler (KL) divergence admits an explicit formula:

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})=\frac{1}{2\sigma^{2}}(\left\lVert\phi\right\rVert^{2}-\left\lVert\theta\right\rVert^{2})+\mathbb{E}_{\xi}\bigg{[}\log\frac{\mathbb{E}_{G}[\exp(\frac{1}{\sigma^{2}}(\theta+\sigma\xi)^{T}G\theta)]}{\mathbb{E}_{G}[\exp(\frac{1}{\sigma^{2}}(\theta+\sigma\xi)^{T}G\phi)]}\bigg{]}.

An important piece of machinery to analyse the KL divergence is the family of moment tensors. For any positive integer $m$ , the mth moment tensor of a vector $\theta\in\mathbb{R}^{L}$ is the quantity $\mathbb{E}[(G\theta)^{\otimes m}]\in(\mathbb{R}^{L})^{\otimes m}.$ If $\phi\in\mathbb{R}^{L}$ is another vector, the mth moment difference tensor between $\theta$ and $\phi$ is defined to be

\displaystyle\Delta_{m}(\theta,\phi):=\mathbb{E}[(G\theta)^{\otimes m}-(G\phi)^{\otimes m}]\in(\mathbb{R}^{L})^{\otimes m}.

The relationship between the KL divergence and the moment tensors are given by the following results.

Theorem 2.1.1.

(BRW, , Lemma 8) Let $\theta,\phi\in\mathbb{R}^{L}$ . Let $\upvartheta=\theta-\mathbb{E}[G\theta]$ and $\varphi=\phi-\mathbb{E}[G\phi]$ . Then

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})=D_{\text{KL}}(P_{\upvartheta}\;\|\;P_{\varphi})+\frac{1}{2\sigma^{2}}\left\lVert\Delta_{1}(\theta,\phi)\right\rVert^{2}.

Theorem 2.1.2.

(BRW, , Theorem 9) Let $\theta,\phi\in\mathbb{R}^{L}$ satisfy $3\rho(\theta,\phi)\leq\left\lVert\theta\right\rVert\leq\sigma$ and $\mathbb{E}[G\theta]=\mathbb{E}[G\phi]=0$ . For any positive integer $k$ , there exist universal constants $\underline{C}$ and $\overline{C}$ such that

\displaystyle\underline{C}\sum_{m=1}^{\infty}\frac{\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}}{(\sqrt{3}\sigma)^{2m}m!}\leq D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\leq 2\sum_{m=1}^{k-1}\frac{\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}}{\sigma^{2m}m!}+\overline{C}\frac{\left\lVert\theta\right\rVert^{2k-2}\rho(\theta,\phi)^{2}}{\sigma^{2k}}.

A few remarks are in order. Firstly, the assumption that $\mathbb{E}[G\theta]=\mathbb{E}[G\phi]=0$ means that the first moment tensor $\Delta_{1}(\theta,\phi)$ vanishes. Thus the summations in the above theorem start from $m=2$ . Secondly, the result still holds if the hypothesis $3\rho(\theta,\phi)\leq\left\lVert\theta\right\rVert$ is replaced by $\rho(\theta,\phi)\leq K_{0}\left\lVert\theta\right\rVert$ for any fixed positive constant $K_{0}\in\mathbb{R}_{>0}$ . In our current setting, we let $K_{0}=3$ . A full proof of this statement can be found in Appendix C.

2.2 Collision-Free Signals

As a consequence of the resolution of the Piccard’s conjecture, collision-free signals are very well-behaved locally. This notion can be formalised in terms of the following lower bounds on the KL-divergence and moment tensors.

Lemma 2.2.1.

(Sparse, , Lemma 5) For any pair of collision free signals $\theta,\phi\in\mathcal{T}$ , we have

\displaystyle\left\lVert\Delta_{2}(\theta,\phi)\right\rVert\geq\sqrt{\frac{2\epsilon}{2+\epsilon}}\cdot\frac{1}{\sqrt{L}}\cdot\sqrt{s}\cdot\rho(\theta,\phi).

Proposition 2.2.2.

(Sparse, , Proposition 17) There exists a postive constant $\epsilon_{0}\in\mathbb{R}_{>0}$ such that for all collision free signals $\theta,\phi\in\mathcal{T}$ satisfying $\rho(\theta,\phi)<\epsilon_{0}$ and for all $\sigma$ sufficiently large,

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C\sigma^{-4}\cdot\left\lVert\Delta_{2}(\theta,\phi)\right\rVert^{2}.

Combining the above two results, we obtain the following local lower bound for the KL divergence of collision free signals.

Proposition 2.2.3.

There exist positive constants $\epsilon_{0},C\in\mathbb{R}_{>0}$ such that for any pair of collision free signals $\theta,\phi\in\mathbb{R}^{L}$ with $\theta\in\mathcal{T}$ and $\rho(\theta,\phi)<\epsilon_{0}$ and for any $\sigma$ sufficiently large,

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C\sigma^{-4}s\cdot\rho(\theta,\phi)^{2}

The threshold $\epsilon_{0}$ also satisfies the following property: for any $\theta,\phi\in\mathbb{R}^{L}$ satisfying $\theta\in\mathcal{T}$ and $\lVert\theta-\phi\rVert<\epsilon_{0}$ , we have $\text{Supp}(\theta)=\text{Supp}(\phi)$ .

2.3 Global Lower Bound for the KL Divergence

In this section, we will complement the sharp local bound for the KL divergence in Proposition 2.2.3 with the following global bound.

Proposition 2.3.1.

Let $\theta,\phi\in\mathbb{R}^{L}$ be two collision free signals, with $\theta\in\mathcal{T}$ . There exists a constant $C_{s}$ , depending on $s$ , such that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C_{s}\sigma^{-6}\rho(\theta,\phi)^{2}.

for all $\sigma$ sufficiently large.

As it turns out, the third moment tensor for collision free signals have a very simple form. Thus our strategy for proving Proposition 2.3.1 will be to show that the third moment difference tensor is nonvanishing for two distinct collision free signals and then invoke Theorem 2.1.2.

Lemma 2.3.2.

Let $\theta,\phi\in\mathbb{R}^{L}$ be two collision free signals lying in distinct orbits. Then $\Delta_{3}(\theta,\phi)\neq 0$ .

Proof.

We will show that the orbit of any collision free signal $\theta$ can be recovered purely from its third moment tensor. The collision free property of $\theta$ implies that for any $1\leq i,j\leq L$ with $i\neq j$ , we have that

	$\displaystyle\mathbb{E}[(G\theta)^{\otimes 3}]_{i,j,j}$	$\displaystyle=\frac{1}{L}\sum_{g\in\mathbb{Z}_{L}}\theta(i+g)\theta(j+g)\theta(j+g)$
		$\displaystyle=\begin{cases}0&\ \text{ if }i-j\not\in\mathcal{D}(\theta)\\ \dfrac{1}{L}\theta(i^{\prime})\theta(j^{\prime})\theta(j^{\prime})&\ \text{ otherwise, where }i^{\prime},j^{\prime}\in\text{supp}(\theta)\text{ with }i-j=i^{\prime}-j^{\prime}.\end{cases}$

In particular, the set $\mathcal{D}(\theta)$ , and hence the support of $\theta$ , can be recovered from its third moment tensor up to $\mathcal{R}$ -orbit. Next, for each $i\in\text{Supp}(\theta)$ , to recover $\theta(i)$ , let $1\leq j\leq L$ be such that $i-j\in\mathcal{D}(\theta)$ . We have that

\displaystyle\mathbb{E}[(G\theta)^{\otimes 3}]_{i,i,j}=\frac{1}{L}\theta(i)\theta(i)\theta(j)\ \ \ \ \text{ and }\ \ \ \ \frac{1}{L}\mathbb{E}[(G\theta)^{\otimes 3}]_{i,j,j}=\theta(i)\theta(j)\theta(j).

Thus

\displaystyle\theta(i)^{3}=\dfrac{L\cdot\mathbb{E}[(G\theta)^{\otimes 3}]_{i,i,j}^{2}}{\mathbb{E}[(G\theta)^{\otimes 3}]_{i,j,j}}

can be obtained from the third moment tensor. The conclusion follows. ∎

Lemma 2.3.3.

Let $\theta,\phi\in\mathbb{R}^{L}$ . We denote $\overline{\theta}=\frac{1}{L}\sum_{i=1}^{L}\theta(i)$ and $\overline{\phi}=\frac{1}{L}\sum_{i=1}^{L}\phi(i)$ . Let $\upvartheta=\theta-\mathbb{E}[G\theta]$ and $\varphi=\phi-\mathbb{E}[G\phi]$ . Then

\displaystyle\Delta_{3}(\theta,\phi)=\Delta_{3}(\upvartheta,\varphi)+3\text{Sym}\Big{(}\mathbbm{1}\otimes\big{(}\overline{\theta}\cdot\mathbb{E}[(G\upvartheta)^{\otimes 2}]-\overline{\phi}\cdot\mathbb{E}[(G\varphi)^{\otimes 2}]\big{)}\Big{)}+(\overline{\theta}^{3}-\overline{\phi}^{3})\cdot\mathbbm{1}^{\otimes 3},

where Sym is the symmetrization operator which acts on order- $3$ tensors by averaging over all permutations of the indices:

\displaystyle\text{Sym}(T)_{i,j,k}:=\frac{1}{6}\sum_{\sigma\in S_{3}}T_{\sigma(i),\sigma(j),\sigma(k)}.

Proof.

Let $\mu_{\theta}=\mathbb{E}[G\theta]$ and $\mu_{\phi}=\mathbb{E}[G\phi]$ . Observe that

	$\displaystyle\mathbb{E}[(G\theta)^{\otimes 3}]$	$\displaystyle=\mathbb{E}[(G\upvartheta+G\mu_{\theta})^{\otimes 3}]$
		$\displaystyle=\mathbb{E}[(G\upvartheta+\mu_{\theta})^{\otimes 3}]$
		$\displaystyle=\mathbb{E}[(G\upvartheta)^{\otimes 3}]+\mathbb{E}[G\upvartheta\otimes G\upvartheta\otimes\mu_{\theta}]+\mathbb{E}[G\upvartheta\otimes\mu_{\theta}\otimes G\upvartheta]+\mathbb{E}[\mu_{\theta}\otimes G\upvartheta\otimes G\upvartheta]$
		$\displaystyle+\mathbb{E}[G\upvartheta\otimes\mu_{\theta}\otimes\mu_{\theta}]+\mathbb{E}[\mu_{\theta}\otimes G\upvartheta\otimes\mu_{\theta}]+\mathbb{E}[\mu_{\theta}\otimes\mu_{\theta}\otimes G\upvartheta]+\mu_{\theta}\otimes\mu_{\theta}\otimes\mu_{\theta}$
		$\displaystyle=\mathbb{E}[(G\upvartheta)^{\otimes 3}]+\mathbb{E}[G\upvartheta\otimes G\upvartheta\otimes\mu_{\theta}]+\mathbb{E}[G\upvartheta\otimes\mu_{\theta}\otimes G\upvartheta]+\mathbb{E}[\mu_{\theta}\otimes G\upvartheta\otimes G\upvartheta]$
		$\displaystyle+\mathbb{E}[G\upvartheta]\otimes\mu_{\theta}\otimes\mu_{\theta}+\mu_{\theta}\otimes\mathbb{E}[G\upvartheta]\otimes\mu_{\theta}+\mu_{\theta}\otimes\mu_{\theta}\otimes\mathbb{E}[G\upvartheta]+\mu_{\theta}^{\otimes 3}$
		$\displaystyle=\mathbb{E}[(G\upvartheta)^{\otimes 3}]+3\text{Sym}\big{(}\mu_{\theta}\otimes\mathbb{E}[(G\upvartheta)^{\otimes 2}]\big{)}+\mu_{\theta}^{\otimes 3}.$

Since the Symmetrization operator is linear, we obtain

\displaystyle\Delta_{3}(\theta,\phi)=\Delta_{3}(\upvartheta,\varphi)+3\text{Sym}\Big{(}\mathbbm{1}\otimes\big{(}\overline{\theta}\cdot\mathbb{E}[(G\upvartheta)^{\otimes 2}]-\overline{\phi}\cdot\mathbb{E}[(G\varphi)^{\otimes 2}]\big{)}\Big{)}+(\overline{\theta}^{3}-\overline{\phi}^{3})\cdot\mathbbm{1}^{\otimes 3},

as desired. ∎

We are now ready to prove Proposition 2.3.1.

Proof of Proposition 2.3.1.

Since both the KL divergence and the orbit distance are invariant under the action of the group $\mathcal{R}$ , we assume without loss of generality that $\rho(\theta,\phi)=\left\lVert\theta-\phi\right\rVert$ . By Proposition 2.2.3 , it suffices to prove the above statement for the case of $\rho(\theta,\phi)\geq\epsilon_{0}.$ We will divide our argument into two cases.

Case 1. $\epsilon_{0}\leq\rho(\theta,\phi)\leq 3\left\lVert\theta\right\rVert$ .

Observe that $\rho(\theta,\phi)$ is bounded above as $\left\lVert\theta\right\rVert$ is (recall that we require $|\theta(i)|\leq M$ for all $1\leq i\leq L$ ). Thus it suffices to show that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq\sigma^{-6}\epsilon_{s}

for some small constant $\epsilon_{s}$ depending only on $s$ . In what follows, we denote $\upvartheta=\theta-\mathbb{E}[G\theta]$ and $\varphi=\phi-\mathbb{E}[G\phi]$ . Firstly, by lemma 2.3.2, we have that $\Delta_{3}(\theta,\phi)\neq 0$ . For each $\theta\in\mathcal{T}$ , define

\displaystyle B_{\theta,\epsilon_{0}}:=\big{\{}\phi\in\mathbb{R}^{L}\ :\ \epsilon_{0}\leq\rho(\theta,\phi)\leq 3\left\lVert\theta\right\rVert\big{\}}.

Then set

\displaystyle\delta_{0}:=\inf_{\theta\in\mathcal{T}}\inf_{\phi\in B_{\theta,\epsilon_{0}}}\left\lVert\Delta_{3}(\theta,\phi)\right\rVert.

Note that $\delta_{0}$ is a strictly positive constant since both $B_{\theta,\epsilon_{0}}$ and $\mathcal{T}$ are compact sets. Furthermore, $\delta_{0}$ is independent of both $\theta$ and $\phi$ (but may depend on $s$ ). Let $\delta\in\mathbb{R}_{>0}$ be a small constant, whose value may decrease from line to line, satisfying

\left\lVert 3\cdot\text{Sym}\Big{(}\mathbbm{1}\otimes\big{(}\overline{\theta}\cdot\mathbb{E}[(G\upvartheta)^{\otimes 2}]-\overline{\phi}\cdot\mathbb{E}[(G\varphi)^{\otimes 2}]\big{)}\Big{)}+(\overline{\theta}^{3}-\overline{\phi}^{3})\cdot\mathbbm{1}^{\otimes 3}\right\rVert\leq\frac{\delta_{0}}{2}

(4)

for all $\theta,\phi\in\mathbb{R}^{L}$ such that $|\overline{\theta}-\overline{\phi}|\leq\delta$ and $\left\lVert\Delta_{2}(\upvartheta,\varphi)\right\rVert\leq\delta$ . By Theorem 2.1.1,

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})=\frac{1}{2\sigma^{2}}\left\lVert\Delta_{1}(\theta,\phi)\right\rVert^{2}+D_{\text{KL}}(P_{\upvartheta}\;\|\;P_{\varphi}).

Thus if $|\overline{\theta}-\overline{\phi}|>\delta$ , we have that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq\frac{1}{2\sigma^{2}}\left\lVert\Delta_{1}(\theta,\phi)\right\rVert^{2}\geq\frac{\delta^{2}L}{2\sigma^{2}}\geq\delta^{2}\sigma^{-6}.

Now suppose that $|\overline{\theta}-\overline{\phi}|\leq\delta$ . If $\left\lVert\Delta_{2}(\upvartheta,\varphi)\right\rVert>\delta$ , by (BRW, , Theorem 9), there exists an universal positive constant $C\in\mathbb{R}_{>0}$ such that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq D_{\text{KL}}(P_{\vartheta}\;\|\;P_{\varphi})\geq C\frac{\left\lVert\Delta_{2}(\upvartheta,\varphi)\right\rVert^{2}}{\sigma^{4}}\geq\frac{C\delta^{2}}{\sigma^{4}}\geq\delta^{2}\sigma^{-6}.

Finally, suppose that we have both $|\overline{\theta}-\overline{\phi}|\leq\delta$ and $\left\lVert\Delta_{2}(\upvartheta,\varphi)\right\rVert\leq\delta$ . Using (4) and Lemma 2.3.3, we obtain

\displaystyle\left\lVert\Delta_{3}(\upvartheta,\varphi)\right\rVert\geq\left\lVert\Delta_{3}(\theta,\phi)\right\rVert-\frac{\delta_{0}}{2}\geq\frac{\delta_{0}}{2}.

Again by Theorem 2.1.2, we obtain

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq D_{\text{KL}}(P_{\vartheta}\;\|\;P_{\varphi})\geq C\frac{\left\lVert\Delta_{3}(\upvartheta,\varphi)\right\rVert^{2}}{\sigma^{6}}\geq\frac{C\delta^{2}_{0}}{4\sigma^{6}}.

The desired conclusion follows by choosing $\epsilon_{s}=\min\{\frac{C\delta_{0}^{2}}{4},\delta^{2}\}.$

Case 2. $\rho(\theta,\phi)>3\left\lVert\theta\right\rVert.$

By Lemma A.1 , we in fact have a stronger bound $D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C\sigma^{-4}\rho(\theta,\phi)^{2}$ . ∎

3 Uniform Rates of Convergence for the Maximum Likelihood Estimator

The goal of this section is to prove Theorem 1.4.3. Throughout this section, we fix a collision free signal $\theta\in\mathcal{T}$ , which plays the role of the unknown parameter which we are trying to estimate. Let $s=|\text{Supp}(\theta)|$ and define the subspace

\displaystyle L_{\theta}:=\Big{\{}\phi\in\mathbb{R}^{L}\ :\ \phi(i)=0\text{ for all }i\not\in\text{Supp}(\theta)\Big{\}}.

In this section, all derivatives will be taken with respect to the subspace $L_{\theta}$ . In other words, for a (twice continuously differentiable) function $g:\mathbb{R}^{L}\to\mathbb{R}$ and a point $p\in\mathbb{R}^{L}$ , we define the gradient and the Hessian to be

	$\displaystyle\nabla g(p)_{i}$	$\displaystyle:=\begin{cases}\dfrac{\partial g}{\partial x_{i}}(p)&\text{if }i\in\text{Supp}(\theta),\\ 0&\text{otherwise};\end{cases}$
	$\displaystyle(H_{g}(p))_{ij}$	$\displaystyle:=\begin{cases}\dfrac{\partial g}{\partial x_{i}\partial x_{j}}(p)&\text{if }i,j\in\text{Supp}(\theta),\\ 0&\text{otherwise}.\end{cases}$

Let $D:\mathbb{R}^{L}\to\mathbb{R}_{+}$ denote the map

\displaystyle D(\phi):=D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})=\mathbb{E}\bigg{[}\log\frac{f_{\theta}(X)}{f_{\phi}(X)}\bigg{]}.

Let $H=H_{D}$ denote the Hessian of the above map at the point $\theta$ (on the subspace $L_{\theta}$ ). Since $H$ is positive semidefinite, it induces a seminorm $\lVert\cdot\rVert_{H}:\mathbb{R}^{L}\to\mathbb{R}_{+}$ via

\displaystyle\left\lVert\phi\right\rVert_{H}:=\sqrt{\phi^{T}H\phi}.

For i.i.d samples $X_{1},\cdots,X_{n}$ drawn according to $P_{\theta}$ , the restricted MLE $\tilde{\theta}_{n}$ is a minimizer of

\displaystyle D_{n}(\phi):=\frac{1}{n}\sum_{i=1}^{n}\log\frac{f_{\theta}}{f_{\phi}}(X_{i})

on the set $\mathcal{T}.$

Our proof builds upon the approach in (BRW, , Theorem 4). In our proof, we will invoke the following results.

Lemma 3.0.1.

(BRW, , Lemma B.6) Let $\epsilon\in\mathbb{R}_{>0}$ and let $\mathcal{B}_{\epsilon}=\{\phi\in\mathbb{R}^{L}\ :\ \rho(\phi,\theta)\leq\epsilon\}$ . Let $H_{D_{n}}$ denote the Hessian of $D_{n}$ . There exists a constant $C$ such that

\displaystyle\mathbb{E}\bigg{[}\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert^{2}_{\text{op}}\bigg{]}\leq C\frac{\log n}{n\sigma^{4}}.

Lemma 3.0.2.

(BRW, , Lemma B.7) Let $\mathcal{L}$ be any vector subspace of $\mathbb{R}^{L}$ . Suppose that there exists a positive integer $k$ and positive constants $c$ and $C$ such that for all $\theta,\phi\in\mathcal{L}$ satisfying $c^{-1}\leq\left\lVert\theta\right\rVert\leq c$ and $\left\lVert\theta\right\rVert\leq\sigma$ , we have that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C\sigma^{-2k}\rho(\theta,\phi)^{2}.

Then the restricted MLE $\tilde{\theta}_{n}$ satisfies

\displaystyle\mathbb{E}[\rho(\tilde{\theta}_{n},\theta)^{2}]\leq\tilde{C}\frac{\sigma^{4k-2}}{n}

for some positive constant $\tilde{C}$ .

Lemma 3.0.3.

(BRW, , Lemma B.15) There exists a positive constant $C$ depending only on the dimension $L$ such that for any $\theta,\phi\in\mathbb{R}^{L}$ with $\left\lVert\theta\right\rVert\leq 1$ ,

\displaystyle\bigg{|}D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})-\frac{1}{2}\left\lVert\theta-\phi\right\rVert^{2}_{H}\bigg{|}\leq C\frac{\left\lVert\phi-\theta\right\rVert^{2}}{\sigma^{3}}.

Proof of Theorem 1.4.3.

The key idea behind the proof is that for $n\to+\infty$ , the dominant term in (3) is the first term, which is controlled by the local nature of the signals. Since collision free signals are very well-behaved locally (Proposition 2.2.3), this allows us to obtain sharper uniform bounds on the rate of convergence of the restricted MLE.

We assume without loss of generality that $\rho(\tilde{\theta}_{n},\theta)=\lVert\tilde{\theta}_{n}-\theta\rVert.$ Furthermore, since $\left\lVert\theta\right\rVert$ is bounded, we also assume $\left\lVert\theta\right\rVert=1$ and $\sigma\geq 1$ by replacing $\theta$ and $\sigma$ by $\theta/\left\lVert\theta\right\rVert$ and $\sigma/\left\lVert\theta\right\rVert$ respectively.

Let $\delta$ be a fixed positive constant and let $A$ be a positive constant whose value may change from line to line. Define the event $\mathcal{E}:=\{\rho(\tilde{\theta}_{n},\theta)\leq\epsilon\}$ , where $\epsilon$ is another positive constant whose exact value will be determined later. We decompose

\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\big{]}=\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\mathbbm{1}_{\mathcal{E}}\big{]}+\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\mathbbm{1}_{\mathcal{E}^{c}}\big{]}

(5)

and bound each term separately. Note that the first term entails the local behaviour of the restricted MLE while the second term entails the global behaviour of the restricted MLE.

Local bound: For the first term, let $B_{1}$ and $B_{2}$ denote the constants as in Lemma 3.0.3 and Proposition 2.2.3 respectively. We first choose $\delta$ sufficiently small such that

\displaystyle\frac{\delta B_{1}}{B_{2}}\leq\frac{1}{2}.

Let $\sigma\in\mathbb{R}_{>0}$ be sufficiently large such that $s\delta\sigma^{-1}<\epsilon_{0}$ and choose $\epsilon=s\delta\sigma^{-1}$ . By Lemma 3.0.3 and Proposition 2.2.3, we have that

\displaystyle\Big{|}D(\tilde{\theta}_{n})-\frac{1}{2}\lVert\tilde{\theta}_{n}-\theta\rVert^{2}_{H}\Big{|}

\displaystyle\leq B_{1}\frac{\lVert\tilde{\theta}_{n}-\theta\rVert^{3}}{\sigma^{3}}\leq\frac{B_{1}s\delta\lVert\tilde{\theta}_{n}-\theta\rVert^{2}}{\sigma^{4}}\leq\frac{1}{2}D(\tilde{\theta}_{n}).

Hence

\displaystyle\frac{1}{3}\lVert\tilde{\theta}_{n}-\theta\rVert_{H}^{2}\leq D(\tilde{\theta}_{n})\leq\lVert\tilde{\theta}_{n}-\theta\rVert^{2}_{H}.

Together with Proposition 2.2.3, we get

\displaystyle\lVert\tilde{\theta}_{n}-\theta\rVert^{2}_{H}\geq A\sigma^{-4}s\lVert\tilde{\theta}_{n}-\theta\rVert^{2}.

(6)

The function $D_{n}$ satisfy $D_{n}(\theta)=0$ and attains its minimum value on $\mathcal{T}$ at $\tilde{\theta}_{n}$ . As such, we must have $D_{n}(\tilde{\theta}_{n})\leq 0.$ Furthermore, since $\lVert\tilde{\theta}_{n}-\theta\rVert<\epsilon_{0}$ , we also have that $\text{Supp}(\tilde{\theta}_{n})=\text{Supp}(\theta)$ . Expanding $D-D_{n}$ as a Taylor series about $\theta$ , we obtain

	$\displaystyle\frac{1}{3}\lVert\tilde{\theta}_{n}-\theta\rVert^{2}_{H}$	$\displaystyle\leq D(\tilde{\theta}_{n})-D_{n}(\tilde{\theta}_{n})$
		$\displaystyle-\nabla D_{n}(\theta)^{T}(\tilde{\theta}_{n}-\theta)+\frac{1}{2}(\tilde{\theta}_{n}-\theta)^{T}\big{(}H_{D}(\eta)-H_{D_{n}}(\eta)\big{)}(\tilde{\theta}_{n}-\theta)$

where $\eta\in\mathbb{R}^{d}$ is a vector on the line segment between $\theta$ and $\tilde{\theta}_{n}$ . We employ the dual norm $\left\lVert\cdot\right\rVert_{H}^{*}$ to bound the first term and the operator norm $\left\lVert\cdot\right\rVert_{\text{op}}$ to bound the second term. This gives

\displaystyle\frac{1}{3}\lVert\tilde{\theta}_{n}-\theta\rVert^{2}_{H}\leq\left\lVert\nabla D_{n}(\theta)\right\rVert^{*}_{H}\lVert\tilde{\theta}_{n}-\theta\rVert_{H}+\dfrac{1}{2}\lVert\tilde{\theta}_{n}-\theta\rVert^{2}\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert_{\text{op}}

where $\mathcal{B}_{\epsilon}:=\big{\{}\phi\in\mathbb{R}^{d}\ :\ \rho(\phi,\theta)\leq\epsilon\big{\}}.$ Using (6) and dividing by $\lVert\tilde{\theta}_{n}-\theta\rVert_{H}$ throughout on both sides,

\displaystyle\sigma^{-2}\sqrt{s}\lVert\tilde{\theta}_{n}-\theta\rVert

\displaystyle\leq A\Big{(}\lVert\nabla D_{n}(\theta)\rVert^{*}_{H}+\frac{\sigma^{2}}{\sqrt{s}}\lVert\tilde{\theta}_{n}-\theta\rVert\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert_{\text{op}}\Big{)}.

Multiplying both sides by $\sigma^{2}/\sqrt{s}$ and applying Young’s inequality to the second term on the right-hand side yields

\displaystyle\lVert\tilde{\theta}_{n}-\theta\rVert

\displaystyle\leq A\bigg{(}\frac{\sigma^{2}}{\sqrt{s}}\left\lVert\nabla D_{n}(\theta)\right\rVert^{*}_{H}+\frac{\sigma^{7}}{s}\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert_{\text{op}}^{2}+\frac{\sigma}{s}\lVert\tilde{\theta}_{n}-\theta\rVert^{2}\bigg{)}.

Taking expectation on both sides,

\displaystyle\begin{split}\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\mathbbm{1}_{\mathcal{E}}\big{]}&\leq\frac{A\sigma^{2}}{\sqrt{s}}\cdot\mathbb{E}_{\theta}\big{[}\left\lVert\nabla D_{n}(\theta)\right\rVert^{*}_{H}\big{]}+\frac{A\sigma^{7}}{s}\cdot\mathbb{E}_{\theta}\bigg{[}\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert_{\text{op}}^{2}\bigg{]}\\ &+\frac{A\sigma}{s}\cdot\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)^{2}\big{]}.\end{split}

(7)

This concludes the local analysis of the restricted MLE.

Global bound: We first address the second term in (5). Since $\rho(\tilde{\theta}_{n},\theta)\geq s\delta\sigma^{-1}$ on $\mathcal{E}^{c}$ , we obtain

\displaystyle\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\mathbbm{1}_{\mathcal{E}^{c}}\big{]}\leq\frac{A\sigma}{s}\cdot\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)^{2}\big{]}

which can be combined with the third term in (7). This gives

\displaystyle\begin{split}\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)\big{]}&\leq\frac{A\sigma^{2}}{\sqrt{s}}\cdot\mathbb{E}_{\theta}\big{[}\left\lVert\nabla D_{n}(\theta)\right\rVert^{*}_{H}\big{]}+\frac{A\sigma^{7}}{s}\cdot\mathbb{E}_{\theta}\bigg{[}\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert_{\text{op}}^{2}\bigg{]}\\ &+\frac{A\sigma}{s}\cdot\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)^{2}\big{]}.\end{split}

(8)

We will establish an upper bound for each of the three terms in the above equation separately.

For the first term, Bartlett’s identities state that for each $1\leq i\leq n$ ,

	$\displaystyle\mathbb{E}_{\theta}\big{[}\nabla\log f_{\phi}(X_{i})\|_{\phi=\theta}\big{]}$	$\displaystyle=0$
	$\displaystyle\mathbb{E}_{\theta}\big{[}(\nabla\log f_{\phi}(X_{i})\|_{\phi=\theta})(\nabla\log f_{\phi}(X_{i})\|_{\phi=\theta})^{T}\big{]}$	$\displaystyle=H_{D}(\theta)=H.$

Since $\nabla D_{n}(\theta)=\displaystyle-\frac{1}{n}\sum_{i=1}^{n}\nabla\log f_{\phi}(X_{i})\big{|}_{\phi=\theta}$ and the $X_{i}$ ’s are independent, we get

\displaystyle\mathbb{E}_{\theta}\big{[}\nabla D_{n}(\theta)\nabla D_{n}(\theta)^{T}\big{]}=\frac{1}{n}H.

In particular, the nullspace of $H$ is contained in the nullspace of $\nabla D_{n}(\theta)\nabla D_{n}(\theta)^{T}$ almost surely since any vector $v$ lying in the nullspace of $H$ satisfies

\displaystyle 0\leq\mathbb{E}_{\theta}\big{[}v^{T}\nabla D_{n}(\theta)\nabla D_{n}(\theta)^{T}v\big{]}=\frac{1}{n}v^{T}Hv=0.

Since the row space of a symmetric matrix is the orthogonal complement of its nullspace, this means that the row space of $\nabla D_{n}(\theta)\nabla D_{n}(\theta)^{T}$ (and hence the row space of $\nabla D_{n}(\theta))$ is contained in the row space of $H$ almost surely. As a result,

$\displaystyle\mathbb{E}_{\theta}\big{[}\left\lVert\nabla D_{n}(\theta)\right\rVert^{*}_{H}\big{]}$	$\displaystyle=\mathbb{E}_{\theta}\Big{[}\sqrt{\nabla D_{n}(\theta)^{T}H^{\dagger}\nabla D_{n}(\theta)}\Big{]}$
	$\displaystyle\leq\sqrt{\mathbb{E}_{\theta}\big{[}\text{Tr}\big{(}\nabla D_{n}(\theta)^{T}H^{\dagger}\nabla D_{n}(\theta)\big{)}\big{]}}$
	$\displaystyle=\sqrt{\frac{1}{n}\text{Tr}(H^{\dagger}H)}\leq\sqrt{\frac{s}{n}},$	(9)

where $H^{\dagger}$ denotes the Moore-Penrose inverse of $H$ . For the second term, we invoke Lemma 3.0.1 to get

\mathbb{E}_{\theta}\bigg{[}\sup_{\phi\in\mathcal{B}_{\epsilon}}\left\lVert H_{D}(\phi)-H_{D_{n}}(\phi)\right\rVert_{\text{op}}^{2}\bigg{]}\leq A\frac{\log n}{n\sigma^{4}}.

(10)

Finally, for the third term, we invoke Lemma 3.0.2 with the weaker global bound in Proposition 2.3.1 (i.e. $k=3$ ). We obtain

\mathbb{E}_{\theta}\big{[}\rho(\tilde{\theta}_{n},\theta)^{2}\big{]}\leq A_{s}\frac{\sigma^{10}}{n}

(11)

for some positive constant $A_{s}$ depending on $s$ . Putting (9), (10) and (11) back into (8), we have

\displaystyle\mathbb{E}\big{[}\rho(\tilde{\theta}_{n},\theta)\big{]}\leq A\frac{\sigma^{2}}{\sqrt{n}}+A\frac{\sigma^{3}\log n}{sn}+A_{s}\frac{\sigma^{11}}{sn}.

The conclusion follows. ∎

4 Lower Bound for Collision Free Signals

In this section, we prove Theorem 1.4.4.

Proof.

For convenience of notation, we assume that $s$ is even. The proof for the case in which $s$ is odd is conceptually similar but notationally more complicated. By Le Cam’s two point argument, for any $\phi,\psi\in\mathcal{T}_{s}$ , we have that

\displaystyle\inf_{\hat{\theta}_{n}}\sup_{\theta\in\mathcal{T}_{s}}\mathbb{E}_{\theta}\big{[}\rho(\hat{\theta}_{n},\theta)\big{]}\geq\rho(\phi,\psi)\cdot\left(\frac{2-\sqrt{2nD_{\text{KL}}(P_{\phi}\;\|\;P_{\psi})}}{8}\right)

where the infimum is taken over all estimators $\hat{\theta}_{n}$ on $n$ samples. Thus it suffices to construct two signals $\theta_{n},\phi\in\mathcal{T}_{s}$ such that

\displaystyle\rho(\phi,\theta_{n})\geq M\min\bigg{\{}\frac{\sigma^{2}}{\sqrt{n}},\ 1\bigg{\}}

for some universal constant $M\in\mathbb{R}_{>0}$ but $D_{\text{KL}}(P_{\phi}^{n}\;\|\;P^{n}_{\theta_{n}})=nD_{\text{KL}}(P_{\phi}\;\|\;P_{\theta_{n}})\leq 1/2$ . Let $\{i_{1},i_{2},\cdots,i_{s}\}\subseteq\{1,\cdots,L\}$ be such that each element in the multiset

\displaystyle\big{\{}i_{j}-i_{k}\ :\ 1\leq j,k\leq s\text{ with }j\neq k\big{\}}

appears with multiplicity exactly $1$ . Define

	$\displaystyle\phi_{j}$	$\displaystyle:=\begin{cases}(-1)^{k}\dfrac{1}{\sqrt{s}}&\text{ if }j=i_{k}\text{ for }1\leq k\leq s\\ 0&\text{ otherwise}\end{cases}$
	$\displaystyle(\theta_{n})_{j}$	$\displaystyle:=\begin{cases}(-1)^{k}\dfrac{1}{\sqrt{s}}&\text{ if }j=i_{k}\text{ for }1\leq k\leq s-2\\[8.53581pt] -\dfrac{1}{\sqrt{s}}-\delta&\text{ if }j=i_{k}\text{ for }k=s-1\\[8.53581pt] \dfrac{1}{\sqrt{s}}+\delta&\text{ if }j=i_{k}\text{ for }k=s\\[8.53581pt] 0&\text{ otherwise}\end{cases}$

where $\displaystyle\delta=c\min\bigg{\{}\frac{\sigma^{2}}{\sqrt{n}},1\bigg{\}}$ for some universal constant $c$ to be specified.

Note that $\mathbb{E}[G\phi]=\mathbb{E}[G\theta]=0$ and $\rho(\phi,\theta_{n})=2\delta\leq 1/3$ for $c<1/6$ . Since both $\phi$ and $\theta_{n}$ are mean zero signals, with $\left\lVert\phi\right\rVert=1$ , we can invoke Theorem 2.1.2 (with $k=2$ ) to obtain

\displaystyle D_{\text{KL}}(P_{\phi}\;\|\;P_{\theta_{n}})\leq\overline{C}\frac{\rho(\theta,\phi)^{2}}{\sigma^{4}}\leq\frac{1}{2n}

by choosing $c<\dfrac{1}{2\overline{C}}$ . ∎

5 Concentration of the Maximum Likelihood Estimator

In this section, we fix a collision free signal $\theta\in\mathcal{T}$ that plays the role of the true signal which we wish to approximate. The goal of this section is to prove Theorem 1.4.2.

Recall that for i.i.d samples $X_{1},\cdots,X_{n}$ drawn according to $P_{\theta}$ , the restricted MLE $\tilde{\theta}_{n}$ is the minimizer of the negative log-likehood

	$\displaystyle R_{n}(\phi):$	$\displaystyle=-\frac{1}{n}\sum_{i=1}^{n}\log f_{\phi}(X_{i})$
		$\displaystyle=\frac{L}{2}\log 2\pi\sigma^{2}+\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\frac{\left\lVert G\theta+\sigma\xi_{i}\right\rVert^{2}+\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}\bigg{)}-\log\mathbb{E}_{G}\bigg{[}\exp\bigg{(}\frac{(G\theta+\sigma\xi_{i})^{T}G\phi}{\sigma^{2}}\bigg{)}\bigg{]}\bigg{)}.$

on $\mathcal{T}$ . Since $G\theta+\sigma\xi$ is equal in distribution to $G(\theta+\sigma\xi)$ , we obtain

\displaystyle R_{n}(\phi)\stackrel{{\scriptstyle d}}{{=}}\frac{L}{2}\log 2\pi\sigma^{2}+\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\frac{\left\lVert\theta+\sigma\xi_{i}\right\rVert^{2}+\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}\bigg{)}-\log\mathbb{E}_{G}\bigg{[}\exp\bigg{(}\frac{(\theta+\sigma\xi_{i})^{T}G\phi}{\sigma^{2}}\bigg{)}\bigg{]}\bigg{)}.

(12)

In particular, $R_{n}(\phi)$ does not depend on the randomness of the group action. Thus we let $R(\phi)=\mathbb{E}[R_{n}(\phi)]$ denote its mean with respect to the Gaussian noise $\xi_{1},\cdots,\xi_{n}$ .

Lemma 5.0.1.

Let $K,\delta\in\mathbb{R}_{>0}$ be fixed constants. There exists a $\delta$ -net $N_{\delta}$ (with respect to the Euclidean norm on $\mathbb{R}^{L}$ ) for the subset

\displaystyle S:=\Big{\{}\phi\in\mathbb{R}^{L}\ :\ |\text{supp}(\phi)|\leq s\text{ and }\left\lVert\phi\right\rVert\leq K\Big{\}}

satisfying $|N_{\delta}|\leq L^{s}\bigg{(}\dfrac{3K}{\delta}\bigg{)}^{s}$ .

Proof.

For each tuple of indices $(i_{1},\cdots,i_{s})$ with $1\leq i_{1}<i_{2}<\cdots<i_{s}\leq L$ , define the set

\displaystyle S_{i_{1},\cdots,i_{s}}:=\Big{\{}\phi\in\mathbb{R}^{L}\ :\ \text{supp}(\phi)\subseteq\{i_{1},\cdots,i_{s}\}\text{ and }\left\lVert\phi\right\rVert\leq K\Big{\}}.

By viewing $S_{i_{1},\cdots,i_{s}}$ as a subset of the $s$ -dimensional linear subspace

\displaystyle L_{i_{1},\cdots,i_{s}}=\Big{\{}\phi\in\mathbb{R}^{L}\ :\ \text{supp}(\phi)\subseteq\{i_{1},\cdots,i_{s}\}\Big{\}},

we see that there exists a $\delta$ -net $N^{(i_{1},\cdots,i_{s})}_{\delta}$ for $S_{i_{1},\cdots,i_{s}}$ satisfying $|N^{(i_{1},\cdots,i_{s})}_{\delta}|\leq(3K/\delta)^{s}.$ Define $N_{\delta}$ to be the union of the $N_{\delta}^{(i_{1},\cdots,i_{s})}$ ’s. Since there are ${L}\choose{s}$ possible choices for $i_{1},\cdots,i_{s}$ , we have that

\displaystyle|N_{\delta}|\leq\begin{pmatrix}L\\ s\end{pmatrix}\bigg{(}\frac{3K}{\delta}\bigg{)}^{s}\leq L^{s}\bigg{(}\frac{3K}{\delta}\bigg{)}^{s}.

∎

Lemma 5.0.2.

There exists a universal constant $c\in\mathbb{R}_{>0}$ and a constant $C_{s}\in\mathbb{R}_{>0}$ depending on $s$ such that for any $K,t\in\mathbb{R}_{>0}$ ,

	$\displaystyle P\bigg{(}\sup_{\phi\in\mathcal{T}:\left\lVert\phi\right\rVert\leq K}\|$	$\displaystyle R_{n}(\phi)-R(\phi)\|>4t\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{-s}K^{s}(t^{-s}+t^{-s/2})\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}+C_{s}\exp\big{(}-cn\min\{t,t^{2}\}\big{)}.$

Proof.

In what follows, let $c$ and $C_{s}$ be constants whose value may change from line to line. Using (12), for any $\phi\in\mathbb{R}^{d}$ , we may write

\displaystyle R_{n}(\phi)=\textup{I}-\textup{II}(\phi)+\text{const}(\phi)

where

	I	$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{2\sigma^{2}}\lVert\theta+\sigma\xi_{i}\rVert^{2}$
	$\displaystyle\textup{II}(\phi)$	$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}f(\xi_{i},\phi):=\frac{1}{n}\sum_{i=1}^{n}\log\mathbb{E}_{G}\bigg{[}\exp\bigg{(}\frac{(\theta+\sigma\xi_{i})^{T}G\phi}{\sigma^{2}}\bigg{)}\bigg{]}$

and $\text{const}(\phi)$ is a term not depending on the randomness of the $\xi_{i}$ ’s. We analyse the concentration of I and $\textup{II}(\phi)$ separately. Define the event $\mathcal{E}=\{|\textup{I}-\mathbb{E}[\textup{I}]|<2t\}$ . First observe that for each $1\leq i\leq n$ ,

\displaystyle\frac{1}{2\sigma^{2}}\lVert\theta+\sigma\xi_{i}\rVert^{2}=\frac{1}{2\sigma^{2}}\big{(}\left\lVert\theta\right\rVert^{2}+2\sigma\theta^{T}\xi_{i}+\sigma^{2}\lVert\xi_{i}\rVert^{2}\big{)}.

The first term is deterministic while the distributions of the second and third terms are given by

\displaystyle\frac{1}{\sigma n}\sum_{i=1}^{n}\theta^{T}\xi_{i}\sim\mathcal{N}\bigg{(}0,\frac{1}{\sigma^{2}n}\left\lVert\theta\right\rVert^{2}\bigg{)}\ \ \ \ \ \ \ \text{ and }\ \ \ \ \ \ \ \sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}\sim\chi_{nL}^{2}.

By Gaussian tail bounds, we have that

\displaystyle P\Bigg{(}\bigg{|}\frac{1}{\sigma n}\sum_{i=1}^{n}\theta^{T}\xi_{i}\bigg{|}\geq t\Bigg{)}\leq 2\exp\bigg{(}-\frac{n\sigma^{2}t^{2}}{2\lVert\theta\rVert^{2}}\bigg{)}.

For the chi-square random variable, we will invoke the following well-known chi-square tail bound.

Theorem 5.0.3.

(Chi-square, , Lemma 1). Let $X\sim\chi^{2}_{k}$ be a chi-squared distributed random variable with $k$ degrees of freedom. Then for any $x\in\mathbb{R}$ ,

	$\displaystyle P(X-k\geq 2\sqrt{kx}+2x)$	$\displaystyle\leq\exp(-x)$
	$\displaystyle P(k-X\geq 2\sqrt{kx})$	$\displaystyle\leq\exp(-x).$

Observe that

\displaystyle P\bigg{(}\frac{1}{2n}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}-\frac{L}{2}\geq t\bigg{)}

\displaystyle=P\bigg{(}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}-Ln\geq 2nt\bigg{)}.

Let $x\in\mathbb{R}_{>0}$ be such that $\sqrt{nLx}+x=nt.$ If $x\geq\dfrac{nt}{2}$ , then $n\sqrt{2Lt}+nt\leq 2nt$ and so

\displaystyle P\bigg{(}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}-Ln\geq 2nt\bigg{)}\leq P\bigg{(}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}-Ln\geq n\sqrt{2Lt}+nt\bigg{)}\leq\exp\bigg{(}-\frac{nt}{2}\bigg{)}.

On the other hand, if $\sqrt{nLx}\geq\dfrac{nt}{2}$ , then $x\geq\dfrac{nt^{2}}{4L}$ and so $nt+\dfrac{nt^{2}}{2L}\leq 2nt$ . Thus

\displaystyle P\bigg{(}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}-Ln\geq 2nt\bigg{)}\leq P\bigg{(}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}-Ln\geq nt+\frac{nt^{2}}{2L}\bigg{)}\leq\exp\bigg{(}-\frac{nt^{2}}{4L}\bigg{)}.

Next, we have that

\displaystyle P\bigg{(}\frac{L}{2}-\frac{1}{2n}\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}\geq t\bigg{)}

\displaystyle=P\bigg{(}Ln-\sum_{i=1}^{n}\lVert\xi_{i}\rVert^{2}\geq 2nt\bigg{)}\leq\exp\bigg{(}-\frac{nt^{2}}{L}\bigg{)}.

To summarise, we have the following bound

\displaystyle P\Bigg{(}\bigg{|}\frac{1}{2n}\sum_{i=1}^{n}\left\lVert\xi_{i}\right\rVert^{2}-\frac{L}{2}\bigg{|}\geq t\Bigg{)}\leq 2\exp\big{(}-cn\min\{t,t^{2}\}\big{)}

This implies that

	$\displaystyle P(\mathcal{E}^{c})$	$\displaystyle\leq 2\exp\bigg{(}-\frac{n\sigma^{2}t^{2}}{2\left\lVert\theta\right\rVert^{2}}\bigg{)}+2\exp\big{(}-cn\min\{t,t^{2}\}\big{)}$
		$\displaystyle\leq C_{s}\exp\big{(}-cn\min\{t,t^{2}\}\big{)}$		(13)

where we have used the fact that $\left\lVert\theta\right\rVert\leq\sigma$ for the last inequality.

On the event $\mathcal{E}$ , we have $|R_{n}(\phi)-R(\phi)|\leq 2t+|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]|$ as well as

\frac{1}{n}\sum_{i=1}^{n}\lVert\theta+\sigma\xi_{i}\rVert^{2}\leq\mathbb{E}\big{[}\lVert\theta+\sigma\xi_{i}\rVert^{2}]+4t\sigma^{2}=\left\lVert\theta\right\rVert^{2}+(L+4t)\sigma^{2}\leq(2L+4t)\sigma^{2}.

(14)

We now control the concentration of $\textup{II}(\phi)$ . Differentiating $f(\xi,\phi)$ with respect to $\xi$ , we obtain

\displaystyle\left\lVert\nabla_{\xi}f(\xi,\phi)\right\rVert=\left\lVert\frac{\mathbb{E}_{G}\big{[}\exp(\frac{(\theta+\sigma\xi)^{T}G\phi}{\sigma^{2}})\cdot\frac{1}{\sigma}G\phi\big{]}}{\mathbb{E}_{G}\big{[}\exp(\frac{(\theta+\sigma\xi)^{T}G\phi}{\sigma^{2}})\big{]}}\right\rVert\leq\frac{\mathbb{E}_{G}\big{[}\exp(\frac{(\theta+\sigma\xi)^{T}G\phi}{\sigma^{2}})\cdot\frac{1}{\sigma}\left\lVert\phi\right\rVert\big{]}}{\mathbb{E}_{G}\big{[}\exp(\frac{(\theta+\sigma\xi)^{T}G\phi}{\sigma^{2}})\big{]}}=\frac{\left\lVert\phi\right\rVert}{\sigma}.

Thus $f(\xi,\phi)$ is $\frac{\left\lVert\phi\right\rVert}{\sigma}$ -Lipschitz in $\xi$ . By the following Gaussian concentration result:

Theorem 5.0.4.

(Concentration, , Theorem 5.5) Let $X\sim\mathcal{N}(0,I_{n})$ be a standard Gaussian vector. Let $L\in\mathbb{R}_{>0}$ and let $f:\mathbb{R}^{n}\to\mathbb{R}$ be an $L$ -lipschitz function. Then for all $\lambda\in\mathbb{R}$ ,

\displaystyle\log\mathbb{E}[e^{\lambda(f(X)-\mathbb{E}[f(X)])}\leq\frac{\lambda^{2}}{2}L^{2}.

for a fixed $\phi\in\mathbb{R}^{d}$ , the random variable $f(\xi,\phi)-\mathbb{E}[f(\xi,\phi)]$ is $\frac{\left\lVert\phi\right\rVert^{2}}{\sigma^{2}}$ -subgaussian. Hoeffding’s inequality then yields

	$\displaystyle P\big{(}\|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]\|>t\big{)}$	$\displaystyle=P\bigg{(}\frac{1}{n}\bigg{\|}\sum_{i=1}^{n}f(\xi_{i},\phi)-\mathbb{E}[f(\xi_{i},\phi)]\bigg{\|}\geq t\bigg{)}$
		$\displaystyle=P\bigg{(}\bigg{\|}\sum_{i=1}^{n}f(\xi_{i},\phi)-\mathbb{E}[f(\xi_{i},\phi)]\bigg{\|}\geq nt\bigg{)}$
		$\displaystyle\leq 2\exp\bigg{(}-\frac{n\sigma^{2}t^{2}}{2\left\lVert\phi\right\rVert^{2}}\bigg{)}.$

Now set $\delta=\dfrac{t\sigma}{4\sqrt{L+t}}$ and let $N_{\delta}$ be a $\delta$ -net of $\{\theta\in\mathcal{T}\ :\ \left\lVert\theta\right\rVert\leq M\}$ having cardinality

\displaystyle|N_{\delta}|\leq L^{s}\bigg{(}\frac{12K\sqrt{L+t}}{t\sigma}\bigg{)}^{s}.

Next, the gradient of $\mathbb{E}_{\xi}[f(\xi,\phi)]$ when differentiating with respect to $\phi$ is given by

	$\displaystyle\left\lVert\nabla_{\phi}\mathbb{E}_{\xi}[f(\xi,\phi)]\right\rVert$	$\displaystyle=\left\lVert\mathbb{E}_{\xi}\Bigg{[}\frac{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi))^{T}\phi}{\sigma^{2}})\cdot\frac{G^{T}(\theta+\sigma\xi)}{\sigma^{2}}\big{]}}{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi))^{T}\phi}{\sigma^{2}})\big{]}}\Bigg{]}\right\rVert$
		$\displaystyle\leq\mathbb{E}_{\xi}\Bigg{[}\frac{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi))^{T}\phi}{\sigma^{2}})\cdot\lVert\frac{\theta+\sigma\xi}{\sigma^{2}}\rVert\big{]}}{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi))^{T}\phi}{\sigma^{2}})\big{]}}\Bigg{]}=\frac{1}{\sigma^{2}}\mathbb{E}_{\xi}[\left\lVert\theta+\sigma\xi\right\rVert].$

This can be upper bounded by

\displaystyle\frac{1}{\sigma^{2}}\mathbb{E}_{\xi}[\left\lVert\theta+\sigma\xi\right\rVert]\leq\frac{\left\lVert\theta\right\rVert+\sigma\mathbb{E}[\left\lVert\xi\right\rVert]}{\sigma^{2}}\leq\frac{\sigma+\sigma\sqrt{\mathbb{E}[\lVert\xi\rVert^{2}]}}{\sigma^{2}}=\frac{2\sqrt{L}}{\sigma}.

On the other hand, on the event $\mathcal{E}$ , for a fixed $\xi\in\mathbb{R}^{d}$ , the gradient of $\textup{II}(\phi)$ is given by

	$\displaystyle\left\lVert\nabla_{\phi}\textup{II}(\phi)\right\rVert$	$\displaystyle=\left\lVert\frac{1}{n}\sum_{i=1}^{n}\Bigg{[}\frac{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi_{i}))^{T}\phi}{\sigma^{2}})\cdot\frac{G^{T}(\theta+\sigma\xi_{i})}{\sigma^{2}}\big{]}}{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi_{i}))^{T}\phi}{\sigma^{2}})\big{]}}\Bigg{]}\right\rVert$
		$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\Bigg{[}\frac{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi_{i}))^{T}\phi}{\sigma^{2}})\cdot\lVert\frac{\theta+\sigma\xi_{i}}{\sigma^{2}}\rVert\big{]}}{\mathbb{E}_{G}\big{[}\exp(\frac{(G^{T}(\theta+\sigma\xi_{i}))^{T}\phi}{\sigma^{2}})\big{]}}\Bigg{]}=\frac{1}{\sigma^{2}}\cdot\frac{1}{n}\sum_{i=1}^{n}\left\lVert\theta+\sigma\xi_{i}\right\rVert.$

This can be upper bounded by

\displaystyle\frac{1}{\sigma^{2}}\cdot\frac{1}{n}\sum_{i=1}^{n}\lVert\theta+\sigma\xi_{i}\rVert\leq\frac{1}{\sigma^{2}}\sqrt{\frac{1}{n}\sum_{i=1}^{n}\lVert\theta+\sigma\xi_{i}\rVert^{2}}\leq\frac{\sqrt{2L+4t}}{\sigma}

where the last inequality follows from $(\ref{Concentration6})$ . This means that on the event $\mathcal{E}$ , the function $\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]$ (for each fixed $\xi$ ) is Lipschitz in $\phi$ , with Lipschitz constant at most

\displaystyle\frac{2\sqrt{L}}{\sigma}+\frac{\sqrt{2L+4t}}{\sigma}\leq\frac{4\sqrt{L+t}}{\sigma}=\frac{t}{\delta}.

It then follows that

	$\displaystyle P\bigg{(}\sup_{\phi\in\mathcal{T}:\left\lVert\phi\right\rVert\leq K}\|R_{N}(\phi)-R(\phi)\|>4t\text{ and }\mathcal{E}\bigg{)}$	$\displaystyle\leq P\bigg{(}\sup_{\phi\in\mathcal{T}:\left\lVert\phi\right\rVert\leq K}\|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]\|>2t\text{ and }\mathcal{E}\bigg{)}$
		$\displaystyle\leq P\bigg{(}\sup_{\phi\in N_{\delta}}\|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]\|>t\bigg{)}$
		$\displaystyle\leq 2\|N_{\delta}\|\exp\bigg{(}-\frac{n\sigma^{2}t^{2}}{2K^{2}}\bigg{)}$
		$\displaystyle\leq C_{s}\bigg{(}\frac{K\sqrt{L+t}}{t\sigma}\bigg{)}^{s}\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{-s}K^{s}\bigg{(}\frac{\sqrt{1+t}}{t}\bigg{)}^{s}\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{-s}K^{s}(t^{-s}+t^{-s/2})\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}.$

Combining this with (13) gives the desired result. ∎

Proof of Theorem 1.4.2.

In what follows, let $C_{s}$ and $\tilde{C}_{s}$ be constants depending on $s$ whose value may change from line to line. We employ a slicing argument. For the given value of $\delta$ and each integer $k\in\mathbb{Z}_{\geq 1}$ , define

\displaystyle\Gamma_{k}=\Big{\{}\phi\in\mathbb{R}^{L}:k\delta\leq\rho(\theta,\phi)<(k+1)\delta\Big{\}}.

Then for all $\phi\in\Gamma_{k}$ , we have that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C_{s}\sigma^{-6}\rho(\theta,\phi)^{2}\geq C_{s}\sigma^{-6}k^{2}\delta^{2}

by Proposition 2.3.1. Let $t_{k}=C_{s}\sigma^{-6}k^{2}\delta^{2}$ . By shrinking the constant $C_{s}$ , we have that

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq 10t_{k}.

Note that $\max\{2\sqrt{L}M,k\delta\}\leq 2\sqrt{L}Mk$ since $\delta\leq 2\sqrt{L}M$ . Invoking Lemma 5.0.2 with $t=t_{k}$ and $K=\max\{2\sqrt{L}M,k\delta\}$ , we have that

	$\displaystyle\ \ \ \ P\bigg{(}\sup_{\phi\in\mathcal{T}:\left\lVert\phi\right\rVert\leq\max\{2\sqrt{L}M,k\delta\}}\|R_{n}(\phi)-R(\phi)\|>4t_{k}\bigg{)}$
	$\displaystyle\leq C_{s}(\sigma^{5s}k^{-s}\delta^{-2s}+\sigma^{2s}\delta^{-s})\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{10}}\bigg{)}+C_{s}\exp\bigg{(}-\tilde{C}_{s}n\min\bigg{\{}\frac{k^{2}\delta^{2}}{\sigma^{6}},\frac{k^{4}\delta^{4}}{\sigma^{12}}\bigg{\}}\bigg{)}$
	$\displaystyle\leq C_{s}\sigma^{5s}\delta^{-2s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{10}}\bigg{)}+C_{s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{12}}\bigg{)}.$

Note that $D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})=R(\phi)-R(\theta)\geq 10t_{k}$ . Thus in the event in which we have both $|R_{n}(\theta)-R(\theta)|\leq 4t_{k}$ and $|R_{n}(\phi)-R(\phi)|\leq 4t_{k}$ , since $R_{n}(\phi)-R_{n}(\theta)\geq 2t_{k}\geq 0$ , we see that $\phi$ is not the restricted MLE (recall that the restricted MLE $\tilde{\theta}_{n}$ minimises $R_{n}(\tilde{\theta}_{n})$ on $\mathcal{T}$ ). Thus

	$\displaystyle P(\tilde{\theta}_{n}\in\Gamma_{k})$	$\displaystyle\leq C_{s}\sigma^{5s}\delta^{-2s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{10}}\bigg{)}+C_{s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{12}}\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{5s}\delta^{-2s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{12}}\bigg{)}+C_{s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{12}}\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{5s}\delta^{-2s}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{12}}\bigg{)}$

where the last inequality uses the fact that $\sigma^{5s}\delta^{-2s}$ is bounded below by a constant. Summing over $k\in\mathbb{Z}_{\geq 1}$ gives

	$\displaystyle P(\rho(\tilde{\theta}_{n},\theta)\geq\delta)$	$\displaystyle\leq\sum_{k=1}^{\infty}P(\tilde{\theta}_{n}\in\Gamma_{k})$
		$\displaystyle\leq C_{s}\sigma^{5s}\delta^{-2s}\sum_{k=1}^{\infty}\exp\bigg{(}-\frac{\tilde{C}_{s}nk^{2}\delta^{4}}{\sigma^{12}}\bigg{)}.$

Now for $n\geq\widetilde{C}_{s}^{-1}\delta^{-4}\sigma^{12},$ the infinite summation is bounded by the geometric series

\displaystyle\exp\bigg{(}-\frac{\tilde{C}_{s}n\delta^{4}}{\sigma^{12}}\bigg{)}\sum_{k=0}^{\infty}\exp(-k),

which in turn is dominated by the first term. Thus

\displaystyle P(\rho(\tilde{\theta}_{n},\theta)\geq\delta)\leq C_{s}\sigma^{5s}\delta^{-2s}\exp\bigg{(}-\frac{\tilde{C}_{s}n\delta^{4}}{\sigma^{12}}\bigg{)}

as desired. ∎

6 Acknowledgements

SG was supported in part by the MOE grants R-146-000-250-133, R-146-000-312-114 and MOE-T2EP20121-0013.

SSM was partially supported by an INSPIRE research grant (DST/INSPIRE/04/2018/002193) from the Department of Science and Technology, Government of India and a Start-Up Grant from Indian Statistical Institute, Kolkata.

References

[1] Emmanuel Abbe, Tamir Bendory, William Leeb, João M Pereira, Nir Sharon, and Amit Singer. Multireference alignment is easier with an aperiodic translation distribution. IEEE Transactions on Information Theory, 65(6):3565–3584, 2018.
[2] Afonso S Bandeira, Moses Charikar, Amit Singer, and Andy Zhu. Multireference alignment using semidefinite programming. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 459–470, 2014.
[3] Afonso S Bandeira, Jonathan Niles-Weed, and Philippe Rigollet. Optimal rates of estimation for multi-reference alignment. Mathematical Statistics and Learning, 2(1):25–75, 2020.
[4] Alberto Bartesaghi, Alan Merk, Soojay Banerjee, Doreen Matthies, Xiongwu Wu, Jacqueline LS Milne, and Sriram Subramaniam. 2.2 å resolution cryo-em structure of $\beta$ -galactosidase in complex with a cell-permeant inhibitor. Science, 348(6239):1147–1151, 2015.
[5] Ahmad Bekir and Solomon Golomb. There are no further counterexamples to s. piccard’s theorem. Information Theory, IEEE Transactions on, 53:2864 – 2867, 09 2007.
[6] Tamir Bendory, Alberto Bartesaghi, and Amit Singer. Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities. IEEE signal processing magazine, 37(2):58–76, 2020.
[7] Tamir Bendory, Nicolas Boumal, Chao Ma, Zhizhen Zhao, and Amit Singer. Bispectrum inversion with application to multireference alignment. IEEE Transactions on signal processing, 66(4):1037–1050, 2017.
[8] Tamir Bendory, Yuehaw Khoo, Joe Kileel, Oscar Mickelin, and Amit Singer. Autocorrelation analysis for cryo-em with sparsity constraints: Improved sample complexity and projection-based algorithms. Proceedings of the National Academy of Sciences, 120(18):e2216507120, 2023.
[9] Tamir Bendory, Oscar Mickelin, and Amit Singer. Sparse multi-reference alignment: Sample complexity and computational hardness. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8977–8981. IEEE, 2022.
[10] Gary S Bloom. A counterexample to a theorem of s. piccard. Journal of Combinatorial Theory, Series A, 22(3):378–379, 1977.
[11] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013.
[12] Nicolas Boumal, Tamir Bendory, Roy R Lederman, and Amit Singer. Heterogeneous multireference alignment: A single pass approach. In 2018 52nd Annual Conference on Information Sciences and Systems (CISS), pages 1–6. IEEE, 2018.
[13] Lisa Gottesfeld Brown. A survey of image registration techniques. ACM computing surveys (CSUR), 24(4):325–376, 1992.
[14] Victor-Emmanuel Brunel. Learning rates for gaussian mixtures under group action. In Conference on Learning Theory, pages 471–491. PMLR, 2019.
[15] Robert Diamond. On the multiple simultaneous superposition of molecular structures by rigid body transformations. Protein Science, 1(10):1279–1287, 1992.
[16] Zehao Dou, Zhou Fan, and Harrison Zhou. Rates of estimation for high-dimensional multi-reference alignment. arXiv preprint arXiv:2205.01847, 2022.
[17] Ian L Dryden and Kanti V Mardia. Statistical shape analysis: with applications in R, volume 995. John Wiley & Sons, 2016.
[18] Zhou Fan, Roy R Lederman, Yi Sun, Tianhao Wang, and Sheng Xu. Maximum likelihood for high-noise group orbit estimation and single-particle cryo-em. arXiv preprint arXiv:2107.01305, 2021.
[19] Zhou Fan, Yi Sun, Tianhao Wang, and Yihong Wu. Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model. Communications on Pure and Applied Mathematics, 76(6):1208–1302, 2023.
[20] Hassan Foroosh, Josiane B Zerubia, and Marc Berthod. Extension of phase correlation to subpixel registration. IEEE transactions on image processing, 11(3):188–200, 2002.
[21] Subhroshekhar Ghosh and Philippe Rigollet. Sparse multi-reference alignment: Phase retrieval, uniform uncertainty principles and the beltway problem. Foundations of Computational Mathematics, pages 1–48, 2022.
[22] Roberto Gil-Pita, Manuel Rosa-Zurera, P Jarabo-Amores, and Francisco López-Ferreras. Using multilayer perceptrons to align high range resolution radar signals. In Artificial Neural Networks: Formal Models and Their Applications–ICANN 2005: 15th International Conference, Warsaw, Poland, September 11-15, 2005. Proceedings, Part II 15, pages 911–916. Springer, 2005.
[23] Anya Katsevich and Afonso S Bandeira. Likelihood maximization and moment matching in low snr gaussian mixture models. Communications on Pure and Applied Mathematics, 76(4):788–842, 2023.
[24] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of statistics, pages 1302–1338, 2000.
[25] Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
[26] Wooram Park and Gregory S Chirikjian. An assembly automation approach to alignment of noncircular projections in electron microscopy. IEEE Transactions on Automation Science and Engineering, 11(3):668–679, 2014.
[27] Wooram Park, Charles R Midgett, Dean R Madden, and Gregory S Chirikjian. A stochastic kinematic model of class averaging in single-particle electron microscopy. The International journal of robotics research, 30(6):730–754, 2011.
[28] Amelia Perry, Jonathan Weed, Afonso S Bandeira, Philippe Rigollet, and Amit Singer. The sample complexity of multireference alignment. SIAM Journal on Mathematics of Data Science, 1(3):497–517, 2019.
[29] Sophie Piccard. Sur les ensembles de distances des emsembles de points d’un espace euclidien. 1939.
[30] Ya’Acov Ritov. Estimating a signal with noisy nuisance parameters. Biometrika, 76(1):31–37, 1989.
[31] Dirk Robinson, Sina Farsiu, and Peyman Milanfar. Optimal registration of aliased images using variable projection with applications to super-resolution. The Computer Journal, 52(1):31–42, 2009.
[32] David M Rosen, Luca Carlone, Afonso S Bandeira, and John J Leonard. A certifiably correct algorithm for synchronization over the special euclidean group. In Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics, pages 64–79. Springer, 2020.
[33] Brian M Sadler and Georgios B Giannakis. Shift-and rotation-invariant object reconstruction using the bispectrum. JOSA A, 9(1):57–69, 1992.
[34] Sjors HW Scheres, Mikel Valle, Rafael Nunez, Carlos OS Sorzano, Roberto Marabini, Gabor T Herman, and Jose-Maria Carazo. Maximum-likelihood multi-reference refinement for electron microscopy images. Journal of molecular biology, 348(1):139–149, 2005.
[35] Devika Sirohi, Zhenguo Chen, Lei Sun, Thomas Klose, Theodore C Pierson, Michael G Rossmann, and Richard J Kuhn. The 3.8 å resolution cryo-em structure of zika virus. Science, 352(6284):467–470, 2016.
[36] Douglas L Theobald and Phillip A Steindel. Optimal simultaneous superpositioning of multiple structures with missing data. Bioinformatics, 28(15):1972–1979, 2012.
[37] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer series in statistics. Springer, 2009.
[38] J Portegies Zwart, René van der Heiden, Sjoerd Gelsema, and Frans Groen. Fast translation invariant classification of hrr range profiles in a zero phase representation. IEE Proceedings-Radar, Sonar and Navigation, 150(6):411–418, 2003.

A Appendix A

Lemma A.1.

Let $\theta,\phi\in\mathbb{R}^{L}$ be two vectors and suppose that $\rho(\theta,\phi)\geq 3\left\lVert\theta\right\rVert$ . Then there exists a constant $C_{L}$ , depending on $L$ , such that $D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C_{L}\sigma^{-4}\rho(\theta,\phi)^{2}.$

Proof.

By replacing $\theta,\phi$ and $\sigma$ with $\theta/\left\lVert\theta\right\rVert,\phi/\left\lVert\theta\right\rVert$ and $\sigma/\left\lVert\theta\right\rVert$ respectively, we may assume that $\left\lVert\theta\right\rVert=1$ and $\sigma\geq 1$ . We further assume without loss of generality that $\rho(\theta,\phi)=\left\lVert\theta-\phi\right\rVert$ . Now observe that

\displaystyle\big{|}\left\lVert\theta-\phi\right\rVert-\left\lVert\phi\right\rVert\big{|}\leq\left\lVert\theta\right\rVert\leq\frac{1}{3}\left\lVert\theta-\phi\right\rVert,

where the left-hand side follows from two different applications of the triangle inequality. Thus $\left\lVert\phi\right\rVert\approx\left\lVert\theta-\phi\right\rVert$ so it suffices to show that there exists a positive constant $C_{L}$ such that $D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq C_{L}\sigma^{-4}\left\lVert\phi\right\rVert^{2}$ whenever $\left\lVert\phi\right\rVert\geq 2$ . We will directly use the Donsker-Varadhan formula

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})=\sup_{f}\bigg{\{}\underset{X\sim P_{\theta}}{\mathbb{E}}\big{[}f(X)\big{]}-\log\Big{(}\underset{X\sim P_{\phi}}{\mathbb{E}}\big{[}e^{f(X)}\big{]}\Big{)}\bigg{\}}

with $f(x):=-\lambda\left\lVert x\right\rVert^{2}$ , where $\lambda\geq 0$ is a constant to be specified. For the first term, we have

	$\displaystyle\underset{X\sim P_{\theta}}{\mathbb{E}}\Big{[}-\lambda\left\lVert X\right\rVert^{2}\Big{]}$	$\displaystyle=\underset{X\sim P_{\theta}}{\mathbb{E}}\Big{[}-\lambda\left\lVert G\theta+\sigma\xi\right\rVert^{2}\Big{]}$
		$\displaystyle=-\lambda\underset{X\sim P_{\theta}}{\mathbb{E}}\Big{[}\left\lVert G\theta\right\rVert^{2}+2\sigma(G\theta)^{T}\xi+\sigma^{2}\left\lVert\xi\right\rVert^{2}\Big{]}$
		$\displaystyle=-\lambda(1+\sigma^{2}L).$

For the second term, note that for $X=G\phi+\sigma\xi$ , conditioned on $G$ , the random variable $\left\lVert\frac{1}{\sigma}X\right\rVert^{2}$ has a non-central $\chi^{2}$ -distribution with $L$ degrees of freedom. We obtain

	$\displaystyle-\log\underset{X\sim P_{\phi}}{\mathbb{E}}\Big{[}e^{-\lambda\sigma^{2}\left\lVert\frac{1}{\sigma}X\right\rVert^{2}}\Big{]}$	$\displaystyle=-\log\mathbb{E}_{G}\bigg{[}\exp\Big{(}\frac{-\lambda\left\lVert G\phi\right\rVert^{2}}{1+2\lambda\sigma^{2}}\Big{)}(1+2\lambda\sigma^{2})^{-L/2}\bigg{]}$
		$\displaystyle=\frac{\lambda}{1+2\lambda\sigma^{2}}\left\lVert\phi\right\rVert^{2}+\frac{L}{2}\log(1+2\lambda\sigma^{2}).$

We get

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq\sup_{\lambda\in\mathbb{R}_{\geq 0}}\Bigg{\{}\frac{\lambda}{1+2\lambda\sigma^{2}}\left\lVert\phi\right\rVert^{2}+\frac{L}{2}\log(1+2\lambda\sigma^{2})-\lambda(1+\sigma^{2}L)\Bigg{\}}.

Choose $\lambda=\dfrac{1}{4\sigma^{4}L}.$ Then $\displaystyle 2\lambda\sigma^{2}\leq 1$ so the quantity on the right-hand side is at least

\displaystyle\frac{\lambda}{2}\left\lVert\phi\right\rVert^{2}+\frac{L}{2}(2\lambda\sigma^{2}-4\lambda^{2}\sigma^{4})-\lambda(1+\sigma^{2}L)

where we have used the fact that $\log(1+x)\geq x-x^{2}$ for $x\in\mathbb{R}_{\geq 0}$ . Since $\left\lVert\phi\right\rVert\geq 2$ , we have that

	$\displaystyle D_{\text{KL}}(P_{\theta}\;\\|\;P_{\phi})$	$\displaystyle\geq\Big{(}\frac{\lambda}{4}\left\lVert\phi\right\rVert^{2}+\lambda\Big{)}+(L\lambda\sigma^{2}-2L\lambda^{2}\sigma^{4})-(\lambda+L\lambda\sigma^{2})$
		$\displaystyle=\frac{1}{16\sigma^{4}L}\left\lVert\phi\right\rVert^{2}-\frac{1}{8\sigma^{4}L}\geq\frac{1}{32\sigma^{4}L}\left\lVert\phi\right\rVert^{2}$

as desired. ∎

B Appendix B

Proposition B.1.

Let $\theta,\phi\in\mathbb{R}^{L}$ be two collision free signals such that $\Delta_{2}(\theta,\phi)=0$ . If $s\geq 7$ , then $\phi$ either lies in the orbit of $\theta$ or lies in the orbit of $-\theta$ .

Proof.

We have that for any $1\leq i,j\leq L$ with $i\neq j$ ,

	$\displaystyle\mathbb{E}[(G\theta)^{\otimes 2}]_{i,j}$	$\displaystyle=\frac{1}{L}\sum_{g\in\mathbb{Z}_{L}}\theta(i+g)\theta(j+g)$
		$\displaystyle=\begin{cases}0&\ \text{ if }i-j\not\in\text{Supp}(\theta)\\ \dfrac{1}{L}\theta(i^{\prime})\theta(j^{\prime})&\ \text{ otherwise, where }i^{\prime},j^{\prime}\in\text{supp}(\theta)\text{ with }i-j=i^{\prime}-j^{\prime}.\end{cases}$

Thus the support of $\theta$ is completely determined by the second moment tensor due to the resolution of the beltway problem. As $\Delta_{2}(\theta,\phi)=0$ , we must have $\text{Supp}(\theta)=\text{Supp}(R_{\ell}\phi)$ for some $1\leq\ell\leq L$ . Without loss of generality assume $\ell=L$ . In other words, we have $\text{supp}(\theta)=\text{supp}(\phi)$ . Let $\{k_{1},k_{2},\cdots,k_{s}\}$ denote their (common) support. Then the condition

\displaystyle\theta(k_{i})\theta(k_{i^{\prime}})=\phi(k_{i})\phi(k_{i^{\prime}})\ \ \ \ \ \ \text{ for all }1\leq i,i^{\prime}\leq s

is equivalent to condition that the pairwise product of the ratios

\displaystyle\frac{\theta(k_{1})}{\phi(k_{1})},\ \frac{\theta(k_{2})}{\phi(k_{2})},\cdots,\ \frac{\theta(k_{s})}{\phi(k_{s})}

must all evaluate to $1$ . This implies that these ratios must either all be positive or all be negative. After reordering if necessary, we assume without loss of generality that

\displaystyle\bigg{|}\frac{\theta(k_{1})}{\phi(k_{1})}\bigg{|}\geq\bigg{|}\frac{\theta(k_{2})}{\phi(k_{2})}\bigg{|}\geq\cdots\geq\bigg{|}\frac{\theta(k_{s})}{\phi(k_{s})}\bigg{|}.

If the ratios are all positive, then since

\displaystyle\frac{\theta(k_{1})}{\phi(k_{1})}\cdot\frac{\theta(k_{2})}{\phi(k_{2})}=1,

we must have $\theta(k_{2})/\phi(k_{2})\leq 1$ . If the above inequality is strict, then

\displaystyle\frac{\theta(k_{2})}{\phi(k_{2})}\cdot\frac{\theta(k_{3})}{\phi(k_{3})}<1,

a contradiction. Hence

	$\displaystyle\frac{\theta(k_{2})}{\phi(k_{2})}\cdot\frac{\theta(k_{i})}{\phi(k_{i})}=1\text{ for all $i\neq 2$}$	$\displaystyle\implies\frac{\theta(k_{i})}{\phi(k_{i})}=1\ \text{ for all $1\leq i\leq L$}$
		$\displaystyle\implies\theta=\phi.$

In the latter case, a similar argument yields that $\theta(k_{i})/\phi(k_{i})=-1$ for all $1\leq i\leq L$ and so $\theta=-\phi$ . ∎

C Appendix C

We give a full proof of the modifield Theorem 2.1.2. We first prove a modified version of lemma B.12. Fix a positive number $K_{0}\geq 1.$

Lemma C.1.

For any $m\in\mathbb{Z}_{\geq 1}$ and $\theta,\phi\in\mathbb{R}^{L}$ satisfying $\left\lVert\theta\right\rVert=1$ and $\rho(\theta,\phi)\leq K_{0}$ , we have

\displaystyle\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}\leq 12\cdot 18^{m}K_{0}^{2m}\rho(\theta,\phi)^{2}.

Proof.

Assume without loss of generality that $\rho(\theta,\phi)=\left\lVert\theta-\phi\right\rVert=:\epsilon.$ By Jensen’s inequality,

\displaystyle\left\lVert\mathbb{E}[(G\theta)^{\otimes m}-(G\phi)^{\otimes m}]\right\rVert^{2}

\displaystyle\leq\mathbb{E}\big{[}\lVert(G\theta)^{\otimes m}-(G\phi)^{\otimes m}\rVert^{2}\big{]}=\lVert\theta^{\otimes m}-\phi^{\otimes m}\rVert^{2}.

Expanding the norm yields

	$\displaystyle\lVert\theta^{\otimes m}-\phi^{\otimes m}\rVert^{2}$	$\displaystyle=\left\lVert\theta\right\rVert^{2m}-2\langle\theta,\phi\rangle^{m}+\left\lVert\phi\right\rVert^{2m}$
		$\displaystyle=1-2(1+\gamma)^{m}+(1+2\gamma+\epsilon^{2})^{m}$

where $\gamma:=\langle\theta,\phi-\theta\rangle$ is such that $|\gamma|\leq\epsilon$ by Cauchy Schwarz.

By the binomial theorem, for all $x$ such that $|x|\leq 3K_{0}^{2}$ , there exists an $r_{m}$ such that

\displaystyle(1+x)^{m}=\sum_{k=0}^{m}\begin{pmatrix}m\\ k\end{pmatrix}x^{k}=1+mx+r_{m}

with $|r_{m}|\leq 18^{m}K_{0}^{2m}x^{2}$ . By assumption, we have $|2\gamma+\epsilon^{2}|\leq 3K_{0}^{2}$ and so

	$\displaystyle\lVert\theta^{\otimes m}-\phi^{\otimes m}\rVert^{2}$	$\displaystyle\leq 1-2-2m\gamma+2\cdot 18^{m}K_{0}^{2m}\epsilon^{2}+1+2m\gamma+m\epsilon^{2}+18^{m}K_{0}^{2m}\cdot 9\epsilon^{2}$
		$\displaystyle=2\cdot 18^{m}K_{0}^{2m}\epsilon^{2}+m\epsilon^{2}+18^{m}K_{0}^{2m}\cdot 9\epsilon^{2}$
		$\displaystyle\leq 12\cdot 18^{m}K_{0}^{2m}\epsilon^{2}.$

∎

We now proof the upper bound of the modified Theorem 2.1.2.

Proof.

If $\theta=0,$ then since $\rho(\theta,\phi)\leq K_{0}\left\lVert\theta\right\rVert$ , we must have $\phi=0$ as well so the statement trivially holds. Otherwise, first note that each term in (2.1.2) remains unchanged if the quantities $\theta$ , $\phi$ and $\sigma$ are replaced by $\theta/\left\lVert\theta\right\rVert,\ \phi/\left\lVert\theta\right\rVert$ and $\sigma/\left\lVert\theta\right\rVert$ respectively. The same is true when $\phi$ is replaced by another vector $G_{0}\phi$ in the same $\mathcal{R}$ -orbit. As such, we henceforth assume $\left\lVert\theta\right\rVert=1$ , $\sigma\geq 1$ and $\rho(\theta,\phi)=\left\lVert\theta-\phi\right\rVert.$

Instead of establishing an upper bound on the KL divergence $D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})$ directly, we instead work with the $\chi^{2}$ -divergence

\displaystyle\chi^{2}(P_{\theta},P_{\phi}):=\int_{\mathbb{R}^{d}}\frac{(f_{\theta}(x)-f_{\phi}(x))^{2}}{f_{\phi}(x)}\ dx.

and then pass to the KL divergence via the upper bound $D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\leq\chi^{2}(P_{\theta},P_{\phi})$ . Since $\mathbb{E}[G\phi]=0,$ Jensen’s inequality implies that

\displaystyle f_{\phi}(x)

\displaystyle\geq\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{-\frac{\left\lVert x\right\rVert^{2}+\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}e^{\frac{1}{\sigma^{2}}\mathbb{E}[x^{T}G\phi]}=\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{-\frac{\left\lVert x\right\rVert^{2}+\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}.

Hence

\displaystyle\frac{(f_{\theta}(x)-f_{\phi}(x))^{2}}{f_{\phi}(x)}\leq\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{\frac{-\left\lVert x\right\rVert^{2}+\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}\Big{(}e^{-\frac{\left\lVert\theta\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{1}{\sigma^{2}}x^{T}G\theta}\big{]}-e^{-\frac{\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{1}{\sigma^{2}}x^{T}G\phi}\big{]}\Big{)}^{2}.

To obtain our desired bound on the $\chi^{2}$ -divergence, we will integrate both sides with respect to $x$ . Expanding out the square on the right-hand side yield three terms, which we will evaluate separately. The first term is

\displaystyle\ \ \ \ e^{\frac{\left\lVert\phi\right\rVert^{2}-2\left\lVert\theta\right\rVert^{2}}{2\sigma^{2}}}\int_{\mathbb{R}^{d}}\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{-\frac{\left\lVert x\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{1}{\sigma^{2}}x^{T}(G+G^{\prime})\theta}\big{]}\ dx

where $G^{\prime}$ denotes an independent and identically distributed copy of $G$ . To simplify the expression, we seek to rewrite it as the integral of the density of a Gaussian by completing the square. We obtain

	$\displaystyle\ \ \ \ e^{\frac{\left\lVert\phi\right\rVert^{2}-2\left\lVert\theta\right\rVert^{2}}{2\sigma^{2}}}\int_{\mathbb{R}^{d}}\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{-\frac{\left\lVert x\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{1}{\sigma^{2}}x^{T}(G+G^{\prime})\theta}\big{]}\ dx$
	$\displaystyle=e^{\frac{\left\lVert\phi\right\rVert^{2}-2\left\lVert\theta\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\Bigg{[}\int_{\mathbb{R}^{d}}\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{-\frac{1}{2\sigma^{2}}(x-(G+G^{\prime})\theta)^{T}(x-(G+G^{\prime})\theta)}dx\cdot e^{\frac{1}{2\sigma^{2}}((G+G^{\prime})\theta)^{T}((G+G^{\prime})\theta)}\Bigg{]}$
	$\displaystyle=e^{\frac{\left\lVert\phi\right\rVert^{2}-2\left\lVert\theta\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\Big{[}e^{\frac{1}{2\sigma^{2}}((G+G^{\prime})\theta)^{T}((G+G^{\prime})\theta)}\Big{]}$
	$\displaystyle=e^{\frac{\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{\theta^{T}G\theta}{\sigma^{2}}}\big{]}$

Via similar computations, the second and third terms evaluate to

\displaystyle-2e^{\frac{\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{\theta^{T}G\phi}{\sigma^{2}}}\big{]}\ \ \ \ \ \text{ and }\ \ \ \ \ e^{\frac{\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}\mathbb{E}\big{[}e^{\frac{\phi^{T}G\phi}{\sigma^{2}}}\big{]}

respectively. As $\left\lVert\theta-\phi\right\rVert\leq K_{0}$ and $\left\lVert\theta\right\rVert=1$ , we have that $\left\lVert\phi\right\rVert^{2}\leq(K_{0}+1)^{2}\leq 4K_{0}^{2}$ and so

\displaystyle e^{\frac{\left\lVert\phi\right\rVert^{2}}{2\sigma^{2}}}\leq e^{\frac{2K_{0}^{2}}{\sigma^{2}}}.

A power series expansion yields

	$\displaystyle\chi^{2}(P_{\theta},P_{\phi})$	$\displaystyle\leq e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\mathbb{E}\Big{[}e^{\frac{\theta^{T}G\theta}{\sigma^{2}}}-2e^{\frac{\theta^{T}G\phi}{\sigma^{2}}}+e^{\frac{\phi^{T}G\phi}{\sigma^{2}}}\Big{]}$
		$\displaystyle=e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\sum_{m=1}^{\infty}\frac{1}{\sigma^{2m}m!}\mathbb{E}\big{[}(\theta^{T}G\theta)^{m}-2(\theta^{T}G\phi)^{m}+(\phi^{T}G\phi)^{m}\big{]}$
		$\displaystyle=e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\sum_{m=1}^{\infty}\frac{1}{\sigma^{2m}m!}\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}.$

With the lemma, and using the fact that $\sigma\geq 1$ , we conclude the proof with

	$\displaystyle e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\sum_{m=k}^{\infty}\frac{\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}}{\sigma^{2m}m!}$	$\displaystyle\leq 12e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\sum_{m=k}^{\infty}\frac{18^{m}K_{0}^{2m}\rho(\theta,\phi)^{2}}{\sigma^{2m}m!}$
		$\displaystyle\leq 12e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\cdot\frac{\rho(\theta,\phi)^{2}}{\sigma^{2k}}\sum_{m=k}^{\infty}\frac{18^{m}K_{0}^{2m}}{m!}$
		$\displaystyle\leq 12e^{\frac{2K_{0}^{2}}{\sigma^{2}}+18K_{0}^{2}}\cdot\frac{\rho(\theta,\phi)^{2}}{\sigma^{2k}}.$

∎

The remainder of the section is dedicated to proving the lower bound of the modified Theorem 2.1.2. To that end, we first recall the key ingredients used in the original proof of Theorem 2.1.2. At each step, the modifications that are needed to suit our current context are highlighted.

Definition C.2.

The (probabilist’s) Hermite polynomials are a family of polynomials $\{h_{k}\}_{k=0}^{\infty}$ defined by

\displaystyle h_{k}(x):=(-1)^{k}e^{\frac{x^{2}}{2}}\dfrac{\partial^{k}}{\partial x^{k}}e^{-\frac{x^{2}}{2}},\ \ \ \ \ \ k\in\mathbb{Z}_{\geq 0}.

Fact C.3.

The Hermite polynomials satisfy the following basic properties:

(i)

The polynomial $h_{k}(x)$ has degree $k$ ;
(ii)

The family $\{h_{k}\}_{k=0}^{\infty}$ is an orthogonal basis for $L^{2}(\mathbb{R},\gamma)$ , where $\gamma$ denotes the standard Gaussian measure on $\mathbb{R};$
(iii)

We have $\left\lVert h_{k}\right\rVert^{2}_{L^{2}(\mathbb{R},\gamma)}=k!$ ;
(iv)

For any $\mu\in\mathbb{R}$ , we have $\underset{Y\sim\mathcal{N}(\mu,1)}{\mathbb{E}}\big{[}h_{k}(Y)\big{]}=\mu^{k}.$

Definition C.4.

For each multi-index $\alpha=(\alpha_{1},\cdots,\alpha_{d})\in\mathbb{N}_{0}^{d}$ , define the multivariate polynomial $h_{\alpha}$ by

\displaystyle h_{\alpha}(x_{1},\cdots,x_{d}):=\prod_{i=1}^{d}h_{\alpha_{i}}(x_{i}).

The family $\big{\{}h_{\alpha}:\alpha\in\mathbb{N}_{0}^{d}\big{\}}$ is called the multivariate Hermite polynomials.

The multivariate Hermite polynomials form an orthogonal basis for the product space $L^{2}(\mathbb{R}^{d},\gamma^{\otimes d})$ . By properties (ii), (iii) and (iv) of Fact C.3, the family of rescaled Hermite polynomials $\{H_{\alpha}\ :\ \alpha\in\mathbb{N}^{d}_{0}\}$ defined by

H_{\alpha}(x_{1},\cdots,x_{d}):=\sigma^{|\alpha|}h_{\alpha}(\sigma^{-1}x_{1},\cdots,\sigma^{-1}x_{d})

(15)

satisfy the following identities

	$\displaystyle\displaystyle\underset{Z\sim\mathcal{N}(\boldsymbol{\mu},\sigma^{2}\boldsymbol{I}_{d})}{\mathbb{E}}\big{[}H_{\alpha}(Z)\big{]}$	$\displaystyle=\prod_{i=1}^{d}\mu_{i}^{\alpha_{i}}$		(16)
	$\displaystyle\underset{Z\sim\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})}{\mathbb{E}}\big{[}H_{\alpha}(Z)H_{\beta}(Z)\big{]}$	$\displaystyle=\begin{cases}\sigma^{2\|\alpha\|}\alpha!&\ \text{ if }\alpha=\beta\\ 0&\ \text{ otherwise}.\end{cases}$		(17)

Next, for each positive integer $m$ , we define the function $H_{m}:\mathbb{R}^{d}\to(\mathbb{R}^{d})^{\otimes m}$ in the following way. Given $x\in\mathbb{R}^{d}$ , set $H_{m}(x)$ to be the order- $m$ symmetric tensor whose $(i_{1},\cdots,i_{m})$ th-entry is given by $H_{\alpha^{(i_{1}\cdots i_{m})}}(x)$ , where $\alpha^{(i_{1}\cdots i_{m})}\in\{0,\cdots,m\}^{d}$ is the multi-index associated to $(i_{1},\cdots,i_{m})$ :

\displaystyle\alpha^{(i_{1}\cdots i_{m})}_{\ell}:=\big{|}\big{\{}{j\in[m]\ :\ i_{j}=\ell}\big{\}}\big{|},\ \ \ \ \ \ \ 1\leq\ell\leq d.

Note that $|\alpha^{(i_{1}\cdots i_{m})}|=m$ for each $m$ -tuple $(i_{1},\cdots,i_{m})\in[d]^{m}$ .

The motivation behind the above definition will gradually become apparent once we write the quantities $\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}$ in terms of the family $(H_{m})_{m=1}^{\infty}$ , where $\theta$ and $\phi$ are arbitrary vectors in $\mathbb{R}^{d}$ . For a positive integer $k$ , consider the degree $k$ polynomial

\displaystyle T_{k}(x):=\sum_{m=1}^{k}\frac{\langle\Delta_{m}(\theta,\phi),H_{m}(x)\rangle}{(\sqrt{3}\sigma)^{2m}m!}.

If $X\sim P_{\theta}$ , then (15) implies that

\displaystyle\mathbb{E}[T_{k}(X)]=\mathbb{E}_{G}\Bigg{[}\sum_{m=1}^{k}\frac{\big{\langle}\Delta_{m}(\theta,\phi),\mathbb{E}_{\xi}[H_{m}(X)]\big{\rangle}}{(\sqrt{3}\sigma)^{2m}m!}\Bigg{]}=\sum_{m=1}^{k}\frac{\big{\langle}\Delta_{m}(\theta,\phi),\mathbb{E}[(G\theta)^{\otimes m}]\big{\rangle}}{(\sqrt{3}\sigma)^{2m}m!}.

Hence if $Y\sim P_{\phi}$ , we get

\displaystyle\mathbb{E}[T_{k}(X)]-\mathbb{E}[T_{k}(Y)]=\sum_{m=1}^{k}\frac{\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}}{(\sqrt{3}\sigma)^{2m}m!}=:\delta.

To proceed, we will use the following lemma to relate the KL divergence between $P_{\theta}$ and $P_{\phi}$ to the quantity $\delta$ . (Remark: This lemma remains unchanged from lemma B.11 of the BRW paper).

Lemma C.5.

Let $P_{1}$ and $P_{2}$ be any two probability distributions on a measure space $(\Omega,\mathcal{F})$ . Suppose that there exists a measurable function $F:\Omega\to\mathbb{R}$ such that $\big{(}\mathbb{E}_{P_{1}}[F(X)]-\mathbb{E}_{P_{2}}[F(X)]\big{)}^{2}=\mu^{2}$ and $\max\big{\{}\text{var}_{P_{1}}(F(X)),\text{var}_{P_{2}}(F(X))\big{\}}\leq\sigma^{2}$ . Then

D_{\text{KL}}(P_{1}\;\|\;P_{2})\geq\frac{\mu^{2}}{4\sigma^{2}+\mu^{2}}.

(18)

Proof.

By replacing $F$ by $F+\lambda$ for a suitably chosen constant $\lambda$ , we may assume that $\mathbb{E}_{P_{1}}[F(X)]=\mu/2$ and $\mathbb{E}_{P_{2}}[F(X)]=-\mu/2$ . Let $Q_{1}$ and $Q_{2}$ denote the corresponding probability distributions of $F(X)$ when $X$ is distributed according to $P_{1}$ and $P_{2}$ respectively. By the data processing inequality, it suffices to prove the claimed bound for $D_{\text{KL}}(Q_{1}\;\|\;Q_{2}).$ We further assume that $Q_{1}$ is absolutely continuous with respect to $Q_{2}$ (otherwise the bound is trivial).

As the quantities involved in (18) arise from taking the expectation of random variables, our approach to establish the inequality will be to pass to the convex function $f:[0,+\infty)\to\mathbb{R}$ defined by

\displaystyle f(x):=x\log x-\frac{(x-1)^{2}}{2(x+1)}

and then apply Jensen’s inequality. This yields

\displaystyle\mathbb{E}_{Q_{2}}\Bigg{[}f\left(\frac{dQ_{1}}{dQ_{2}}\right)\Bigg{]}\geq f\Bigg{(}\mathbb{E}_{Q_{2}}\bigg{[}\frac{dQ_{1}}{dQ_{2}}\bigg{]}\Bigg{)}=f(1)=0.

Let $\mu$ be a dominating measure (i.e. $Q_{1}\ll\mu$ and $Q_{2}\ll\mu$ ) and let $q_{1}$ and $q_{2}$ denote the densities of $Q_{1}$ and $Q_{2}$ with respect to $\mu$ . The previous calculation implies that

\displaystyle D_{\text{KL}}(Q_{1}\;\|\;Q_{2})=\mathbb{E}_{Q_{2}}\bigg{[}\frac{dQ_{1}}{dQ_{2}}\log\frac{dQ_{1}}{dQ_{2}}\bigg{]}\geq\frac{1}{2}\int_{\mathbb{R}}\frac{(q_{1}(x)-q_{2}(x))^{2}}{(q_{1}(x)+q_{2}(x))}\ d\mu(x).

By the Cauchy-Schwarz inequality,

	$\displaystyle\mu^{2}$	$\displaystyle=\Bigg{(}\int_{\mathbb{R}}x\big{(}q_{1}(x)-q_{2}(x)\big{)}\ d\mu(x)\Bigg{)}^{2}$
		$\displaystyle\leq\int_{\mathbb{R}}x^{2}\big{(}q_{1}(x)+q_{2}(x)\big{)}\ d\mu(x)\int_{\mathbb{R}}\frac{(q_{1}(x)-q_{2}(x))^{2}}{q_{1}(x)+q_{2}(x)}\ d\mu(x)$
		$\displaystyle=(2\sigma^{2}+\mu^{2}/2)\int_{\mathbb{R}}\frac{(q_{1}(x)-q_{2}(x))^{2}}{q_{1}(x)+q_{2}(x)}\ d\mu(x).$

Hence

\displaystyle D_{\text{KL}}(Q_{1}\;\|\;Q_{2})\geq\frac{\mu^{2}}{4\sigma^{4}+\mu^{2}}

as desired. ∎

With the above lemma, our strategy for establishing lower bounds for the KL divergence will be to lower bound the quantity $\delta$ and upper bound the variances of both $T_{k}(X)$ and $T_{k}(Y)$ . To control $\delta$ , we will apply Lemma C.1. On the other hand, to control the variances, we will use its Hermite decomposition as a gateway to bring in heavy machinery from harmonic analysis. The following lemma remains unchanged from Lemma B.13 of the BRW paper.

Lemma C.6.

Fix a positive integer $k$ . Let $\zeta\in\mathbb{R}^{d}$ and suppose that $Y\sim P_{\zeta}$ . Then for any symmetric tensors $S_{1},\cdots,S_{k}$ , where $S_{m}\in(\mathbb{R}^{d})^{m}$ , we have

\displaystyle\text{var}\left(\sum_{m=1}^{k}\frac{\langle S_{m},H_{m}(Y)\rangle}{(\sqrt{3}\sigma)^{2m}m!}\right)\leq e^{\frac{\left\lVert\zeta\right\rVert^{2}}{2\sigma^{2}}}\sum_{k=1}^{k}\frac{\left\lVert S_{m}\right\rVert^{2}}{(\sqrt{3}\sigma)^{2m}m!}.

Proof.

Let $F(x)=\sum_{m=1}^{k}\frac{\langle S_{m},H_{m}(x)\rangle}{(\sqrt{3}\sigma)^{2m}m!}$ . To upper bound the variance, it suffices to upper bound the second moment $\mathbb{E}[F(Y)^{2}]$ . Before we are able to bring in results from the theory of Gaussian spaces, we first need to replace $P_{\zeta}$ with the centered multivariate normal distribution $Z\sim P_{0}=\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d}).$ To that end, we apply the Cauchy-Schwartz inequality to obtain

$\displaystyle\mathbb{E}[F(Y)^{2}]$	$\displaystyle=\int_{\mathbb{R}^{d}}f_{\zeta}(x)F(x)^{2}\ dx$
	$\displaystyle\leq\left(\int_{\mathbb{R}^{d}}f_{0}(x)F(x)^{4}\ dx\right)^{1/2}\left(\int_{\mathbb{R}^{d}}\frac{f_{\zeta}(x)^{2}}{f_{0}(x)}\ dx\right)^{1/2}$
	$\displaystyle=\mathbb{E}\big{[}F(Z)^{4}\big{]}^{1/2}\left(\int_{\mathbb{R}^{d}}\frac{f_{\zeta}(x)^{2}}{f_{0}(x)}\ dx\right)^{1/2}.$	(19)

We first address the second term. This is done by proceeding in a similar fashion as in the proof of the upper bound of the modified Theorem 9. Observe that

\displaystyle\int_{\mathbb{R}^{d}}\frac{f_{\zeta}(x)^{2}}{f_{0}(x)}\ dx

\displaystyle=\frac{1}{\sigma^{d}(2\pi)^{d/2}}\int_{\mathbb{R}^{d}}\frac{\mathbb{E}\big{[}\exp(-\frac{1}{2\sigma^{2}}(\left\lVert x\right\rVert^{2}-2x^{T}G\zeta+\left\lVert\zeta\right\rVert^{2}))\big{]}^{2}}{\exp(-\frac{1}{2\sigma^{2}}\left\lVert x\right\rVert^{2})}\ dx.

By applying Jensen’s inequality and then completing the square afterwards, we obtain

	$\displaystyle\ \ \ \ \int_{\mathbb{R}^{d}}\frac{f_{\zeta}(x)^{2}}{f_{0}(x)}\ dx$
	$\displaystyle\leq\mathbb{E}\Bigg{[}\frac{1}{\sigma^{d}(2\pi)^{d/2}}\int_{\mathbb{R}^{d}}\frac{\exp\big{(}-\frac{1}{\sigma^{2}}(\left\lVert x\right\rVert^{2}-2x^{T}G\zeta+\left\lVert\zeta\right\rVert^{2})\big{)}}{\exp(-\frac{1}{2\sigma^{2}}\left\lVert x\right\rVert^{2})}\ dy.\Bigg{]}$
	$\displaystyle=\mathbb{E}\Bigg{[}\frac{1}{\sigma^{d}(2\pi)^{d/2}}\int_{\mathbb{R}^{d}}\exp\left(-\frac{1}{2\sigma^{2}}\left\lVert x\right\rVert^{2}+\frac{2}{\sigma^{2}}x^{T}G-\frac{2}{\sigma^{2}}\left\lVert\zeta\right\rVert^{2}\right)\ dy\cdot\exp\bigg{(}\frac{1}{\sigma^{2}}\left\lVert\zeta\right\rVert^{2}\bigg{)}\Bigg{]}$
	$\displaystyle=\exp\bigg{(}\frac{1}{\sigma^{2}}\left\lVert\zeta\right\rVert^{2}\bigg{)}.$		(20)

We now come to the crux of the matter, which is to establish an upper bound on the first term $(\mathbb{E}[F(Z)^{4}])^{1/2}$ . To accomplish that goal, we bring in some standard results about the Ornstein-Uhlenbeck semigroup, which is a family of operators $U_{\rho}:L^{2}(\mathbb{R}^{d},\gamma^{\otimes d})\to L^{2}(\mathbb{R}^{d},\gamma^{\otimes d})$ defined by

\displaystyle U_{\rho}(f)(z):=\underset{Z^{\prime}\sim\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})}{\mathbb{E}}\Big{[}f\big{(}\rho z+\sqrt{1-\rho^{2}}\cdot Z^{\prime}\big{)}\Big{]},\ \ \ \ \ \ \rho\in[-1,1].

Here, we highlight that our definition of $U_{\rho}$ differs from the standard definition in the literature in the sense that expectation is taken with respect to a multivariate normal distribution with covariance matrix $\sigma^{2}\boldsymbol{I}_{d}$ as opposed to $\boldsymbol{I}_{d}$ to compensate for the scaling in $(\ref{AppendixC5}).$

The set $\{H_{\alpha}\ :\ \alpha\in\mathbb{N}^{d}_{0}\}$ is an eigenbasis for the family $(U_{\rho})$ , with $U_{\rho}(H_{\alpha})=\rho^{|\alpha|}H_{\alpha}$ [25, Proposition 11.37]. By viewing $\langle S_{m},H_{m}(x)\rangle$ as a polynomial in $x$ , we get

	$\displaystyle U_{\rho}\big{(}\langle S_{m},H_{m}(x)\rangle\big{)}$	$\displaystyle=U_{\rho}\left(\sum_{1\leq i_{1},\cdots,i_{m}\leq d}(S_{m})_{i_{1}\cdots i_{m}}(H_{m})_{i_{1}\cdots i_{m}}\right)$
		$\displaystyle=\sum_{1\leq i_{1},\cdots,i_{m}\leq d}(S_{m})_{i_{1}\cdots i_{m}}U_{\rho}\big{(}H_{\alpha^{(i_{1}\cdots i_{m})}}\big{)}$
		$\displaystyle=\rho^{m}\sum_{1\leq i_{1},\cdots,i_{m}\leq d}(S_{m})_{i_{1}\cdots i_{m}}H_{\alpha^{(i_{1}\cdots i_{m})}}=\rho^{m}\langle S_{m},H_{m}(x)\rangle,$

where we have used the fact that $|\alpha^{(i_{1}\cdots i_{m})}|=m$ . Thus if we define the degree $k$ polynomial

\displaystyle\widetilde{F}(x):=\sum_{m=1}^{k}\frac{\langle S_{m},H_{m}(x)\rangle}{(\sqrt{3})^{m}\sigma^{2m}m!},

then $U_{1/\sqrt{3}}(\widetilde{F})=F.$ Next, we will invoke the Gaussian hypercontractivity theorem:

Theorem C.7.

[25, Theorem 11.23] Let $1\leq p\leq q\leq\infty$ and let $f\in L^{p}(\mathbb{R}^{n},\gamma)$ , where $\gamma$ is the standard Gaussian measure on $\mathbb{R}^{n}$ . Then $\left\lVert U_{\rho}f\right\rVert_{q}\leq\left\lVert f\right\rVert_{p}$ for $0\leq\rho\leq\sqrt{\frac{p-1}{q-1}}$ .

In our current context, the Gaussian hypercontractivity theorem implies that

\displaystyle\mathbb{E}\big{[}F(Z)^{4}\big{]}^{1/2}\leq\mathbb{E}\big{[}\widetilde{F}(Z)^{2}\big{]}.

It remains to compute $\mathbb{E}[\widetilde{F}(Z)^{2}]$ . Due to the orthogonality relations in (17), when we expand the square, most of the terms will vanish. Since $S_{m}$ and $H_{m}(x)$ are both symmetric tensors, for any tuple $(i_{1},\cdots,i_{m})\in[d]^{m}$ , the quantities $(S_{m})_{i_{1}\cdots i_{m}}$ and $(H_{m}(x))_{i_{1}\cdots i_{m}}$ depend only on the multi-set $\{i_{1},\cdots,i_{m}\}.$ Thus for each $\alpha\in\mathbb{N}^{d}_{0}$ such that $|\alpha|=m$ , if we define

\displaystyle S_{\alpha}:=(S_{m})_{i_{1}\cdots i_{m}}

where $(i_{1},\cdots,i_{m})$ is any $m$ -tuple satisfying $\alpha^{(i_{1}\cdots i_{m})}=\alpha$ , we have that

\displaystyle\langle S_{m},H_{m}(x)\rangle=\sum_{\begin{subarray}{c}|\alpha|=m\end{subarray}}\frac{m!}{\alpha!}S_{\alpha}H_{\alpha}(x).

Applying the orthogonality relations in (17), we obtain

$\displaystyle\mathbb{E}\big{[}F(Z)^{4}\big{]}^{1/2}\leq\mathbb{E}\big{[}\widetilde{F}(Z)^{2}\big{]}$	$\displaystyle=\sum_{m=1}^{k}\mathbb{E}\Bigg{[}\bigg{(}\frac{1}{(\sqrt{3})^{m}\sigma^{2m}m!}\sum_{\begin{subarray}{c}\|\alpha\|=m\end{subarray}}\frac{m!}{\alpha!}S_{\alpha}H_{\alpha}(Z)\bigg{)}^{2}\Bigg{]}$
	$\displaystyle=\sum_{m=1}^{k}\frac{1}{3^{m}\sigma^{4m}}\sum_{\begin{subarray}{c}\|\alpha\|=m\end{subarray}}\frac{S_{\alpha}^{2}}{\alpha!^{2}}\cdot\mathbb{E}\big{[}H_{\alpha}(Z)^{2}\big{]}$
	$\displaystyle=\sum_{m=1}^{k}\frac{1}{(\sqrt{3}\sigma)^{2m}m!}\sum_{\begin{subarray}{c}\|\alpha\|=m\end{subarray}}\frac{m!}{\alpha!}S_{\alpha}^{2}$
	$\displaystyle=\sum_{m=1}^{k}\frac{\left\lVert S_{m}\right\rVert^{2}}{(\sqrt{3}\sigma)^{2m}m!}.$	(21)

Plugging in (20) and (21) back into (19) gives the desired conclusion. ∎

We now conclude our discussion in this section by putting together everything that was introduced. Note that while the constants in our proof differ from the original proof given in [3, Theorem 9], the spirit of the proof remains unchanged.

Proof.

As in the proof of the upper bound, we assume $\rho(\theta,\phi)=\left\lVert\theta-\phi\right\rVert,\ \left\lVert\theta\right\rVert=1$ and $\sigma\geq 1$ . By Lemma C.1, we have

\displaystyle\delta=\sum_{m=1}^{k}\frac{\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}}{(\sqrt{3}\sigma)^{2m}m!}\leq 12\rho(\theta,\phi)^{2}\sum_{m=0}^{\infty}\frac{18^{m}\cdot K_{0}^{2m}}{3^{m}m!}\leq 12K_{0}^{2}e^{6K_{0}^{2}}.

By Lemma C.6, since $\left\lVert\theta\right\rVert^{2}=1$ and $\left\lVert\phi\right\rVert^{2}\leq(K_{0}+1)^{2}\leq 4K_{0}^{2}$ , the variances of $T_{k}(X)$ and $T_{k}(Y)$ are bounded above by $e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\delta$ . Now since $4e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\leq 12K_{0}^{2}e^{6K_{0}^{2}}$ applying Lemma C.5 then gives

\displaystyle D_{\text{KL}}(P_{\theta}\;\|\;P_{\phi})\geq\frac{\delta^{2}}{4e^{\frac{2K_{0}^{2}}{\sigma^{2}}}\delta+\delta^{2}}\geq\frac{\delta^{2}}{24K_{0}^{2}e^{6K_{0}^{2}}\delta}=\frac{1}{24}K_{0}^{-2}e^{-6K_{0}^{2}}\sum_{m=1}^{k}\frac{\left\lVert\Delta_{m}(\theta,\phi)\right\rVert^{2}}{(\sqrt{3}\sigma)^{2m}m!}.

Finally, as the summands are nonnegative, letting $k\to\infty$ gives the desired result. ∎

	$\displaystyle P\big{(}\|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]\|>t\big{)}$	$\displaystyle=P\bigg{(}\frac{1}{n}\bigg{\|}\sum_{i=1}^{n}f(\xi_{i},\phi)-\mathbb{E}[f(\xi_{i},\phi)]\bigg{\|}\geq t\bigg{)}$
		$\displaystyle=P\bigg{(}\bigg{\|}\sum_{i=1}^{n}f(\xi_{i},\phi)-\mathbb{E}[f(\xi_{i},\phi)]\bigg{\|}\geq nt\bigg{)}$
		$\displaystyle\leq 2\exp\bigg{(}-\frac{n\sigma^{2}t^{2}}{2\left\lVert\phi\right\rVert^{2}}\bigg{)}.$

	$\displaystyle P\bigg{(}\sup_{\phi\in\mathcal{T}:\left\lVert\phi\right\rVert\leq K}\|R_{N}(\phi)-R(\phi)\|>4t\text{ and }\mathcal{E}\bigg{)}$	$\displaystyle\leq P\bigg{(}\sup_{\phi\in\mathcal{T}:\left\lVert\phi\right\rVert\leq K}\|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]\|>2t\text{ and }\mathcal{E}\bigg{)}$
		$\displaystyle\leq P\bigg{(}\sup_{\phi\in N_{\delta}}\|\textup{II}(\phi)-\mathbb{E}[\textup{II}(\phi)]\|>t\bigg{)}$
		$\displaystyle\leq 2\|N_{\delta}\|\exp\bigg{(}-\frac{n\sigma^{2}t^{2}}{2K^{2}}\bigg{)}$
		$\displaystyle\leq C_{s}\bigg{(}\frac{K\sqrt{L+t}}{t\sigma}\bigg{)}^{s}\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{-s}K^{s}\bigg{(}\frac{\sqrt{1+t}}{t}\bigg{)}^{s}\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}$
		$\displaystyle\leq C_{s}\sigma^{-s}K^{s}(t^{-s}+t^{-s/2})\exp\bigg{(}-\frac{cn\sigma^{2}t^{2}}{K^{2}}\bigg{)}.$