The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
46,672 characters
Sharp regret--Hellinger bounds for Gaussian empirical Bayes via polynomial approximation
\ifpdf
\DeclareGraphicsExtensions{.pgf}
\graphicspath{{figures/}{plots/}}
\fi
\title{Sharp regret--Hellinger bounds for Gaussian empirical Bayes via polynomial approximation}
\author{Jiafeng Chen and Yihong Wu\thanks{
J.~Chen is with the Department of Economics, Stanford University, Stanford, CA, USA, \texttt{[email removed]}.
Y.~Wu is with the Department of Statistics and Data Science, Yale University, New Haven CT, USA,
\texttt{[email removed]}.
}}
\date{May 3, 2026}
\maketitle
\begin{abstract}
A central problem in the theory of empirical Bayes is to control the regret (excess risk) of a
learned Bayes rule by the Hellinger distance between the estimated and true marginal
densities. In the normal means model, the classical result of Jiang and Zhang
\cite{JiangZhang2009} achieves this only after regularizing the Bayes rule and incurs an extraneous cubic logarithmic factor through a delicate recursive argument.
This
paper
introduces a new technique, based on polynomial approximation and Bernstein-type
inequalities for weighted $L_2$ norms, that bounds the unregularized regret directly.
The method is conceptually simpler and yields sharper, sometimes optimal, regret bounds. For
compactly supported priors, we prove the sharp bound that the regret is at most $O(\epsilon^2 \frac{\log(1/\epsilon)}{\log\log(1/\epsilon)})$,
where $\epsilon$ is the Hellinger distance between the marginal densities. The same method also extends to priors with exponential tails.
Conversely, we
show that regularization is genuinely necessary for heavy-tailed priors under only bounded moment assumptions. As a statistical consequence, we obtain improved regret
bounds for the nonparametric maximum likelihood estimator.
\end{abstract}
\tableofcontents
\section{Introduction}
Empirical Bayes (EB) is a powerful framework for large-scale statistical inference that applies Bayesian methods with a data-driven prior, thereby adapting to the latent structure in the data \cite{robbins1956empirical,zhang2003compound}. For an account of the remarkable successes of EB in both theory and practice, we refer to the monograph and survey of Efron \cite{efron2012large,efron2024empirical}. A key benchmark for an EB procedure is its \textit{regret}: the excess risk relative to the Bayesian oracle that knows the true prior, or, in the compound setting, the empirical distribution of the parameters.
A standard setting for EB is the normal means model.
Consider $\theta \sim G$ and $Y=\theta+Z$, where $Z\sim N(0,1)$ is independent of $\theta$. Tweedie's formula expresses the Bayes estimator in terms of the \textit{score} of the
marginal distribution of $Y$, namely, the Gaussian mixture $f_G := G * N(0,1)$:
\begin{equation}
m_G(y) := \mathbb{E}[\theta|Y=y] = y + \frac{f'_G(y)}{f_G(y)}.
\label{eq:tweedie}
\end{equation}
This estimator minimizes the mean-squared error (MSE) among all estimators of $\theta$:
$\min_{\widehat\theta(\cdot)} \mathbb{E}_G[(\theta-\widehat\theta(Y))^2] =
\mathbb{E}_G[(\theta-m_G(Y))^2]$.
In the context of empirical Bayes, $m_G$ in \prettyref{eq:tweedie} is referred to as \textit{oracle Bayes}, which requires the knowledge of the true prior $G$.
When
the Bayes rule $m_H$ with a misspecified prior $H$ is used, the regret, namely, the excess
MSE over the oracle risk, is given by
\begin{equation}
\mathsf{Regret}(H\|G) :=
\mathbb{E}_G[(m_H(Y)-m_G(Y))^2]
=
\int_{\mathbb{R}} \left( \frac{f_G'}{f_G}-\frac{f_H'}{f_H} \right)^2 f_G dy,
\label{eq:regret}
\end{equation}
the second equality applying the Tweedie's formula \prettyref{eq:tweedie}.
This quantity is also known as \textit{relative Fisher information}
in information theory and optimal transport \cite{villani.topics,raginsky2013concentration} and \textit{score matching loss} in generative modeling \cite{hyvarinen2005estimation}.
In practice---and especially in the
\textit{$g$-modeling} approach \cite{efron2014two}---$H$ is a prior estimated from a
training sample and $\mathsf{Regret}(H\|G)$ is the incurred regret when the learned Bayes rule
$m_H$ is applied to a fresh test data point.
Widely used approaches for learning the prior include maximum likelihood and minimum distance, both of which aim at approximating the true data-generating distribution $f_G$. As such, a central problem in EB theory is to control the regret $\mathsf{Regret}(H\|G)$ using statistical distance between $f_G$ and $f_H$, most commonly the squared Hellinger distance:
\begin{equation}
d_{\rm H}^2(f_G,f_H) :=
\int (\sqrt{f_G}-\sqrt{f_H})^2.
\label{eq:hellinger}
\end{equation}
A foundational result in nonparametric EB of this type is due to Jiang and Zhang
\cite{JiangZhang2009}.
A substantial body of subsequent work in statistics and econometrics builds on this result; see, for
instance, \cite{jiang2020general,saha2020nonparametric,soloff2025multivariate,SW22,adusumilli2025empirical,ghosh2025stein,chen2026empirical,ignatiadis2026compound,kim2026empirical}. In addition, this result also finds applications beyond the classical realm of EB; for example, it plays a crucial role in constructing optimal kernel-based estimators of score functions for diffusion models \cite{WWY24}.
A key ingredient
of Jiang--Zhang's result \cite[Lemma 1]{JiangZhang2009}
controls the following regularized version of the regret \prettyref{eq:regret}:
\[
\mathsf{Regret}_{\rho}(H \Vert G) := \int_\R \pr{
\frac{f'_G}{f_G \vee \rho} - \frac{f'_H}{ f_H \vee \rho}
}^2 f_G dy.
\addtocounter{equation}{1}\tag{\theequation}\label{eq:regularized_regret}
\]
This quantity is related to the regret of the \textit{regularized} Bayes estimator
\begin{equation}
m_{H,\rho}(y) := y + \frac{f'_H(y)}{f_H(y)\vee\rho}
\label{eq:bayes-rho}
\end{equation}
where the regularization parameter $\rho$ ensures the denominator is not too small.
Using a delicate recursive argument,
Jiang and Zhang showed that \prettyref{eq:regularized_regret} can be bounded by the Hellinger distance
$\epsilon := d_{\rm H}(f_G,f_H)$ as follows:
\begin{equation}
\mathsf{Regret}_{\rho}(H \Vert G)
\lesssim \epsilon^2 \max\left\{ \left( \log \frac{1}{\rho} \right)^3, \log \frac{1}{\epsilon} \right\}.
\label{eq:JZ09}
\end{equation}
This quantity can be further related to the regret of the regularized estimator \prettyref{eq:bayes-rho} by quantifying the regularization error on the true Bayes rule, under suitable tail assumptions on the prior $G$.
In practice, $\rho$ is typically chosen as a small polynomial of $\epsilon$, leading to a regret bound of the order $O(\epsilon^2 (\log \frac{1}{\epsilon})^3)$.
The key difficulty of proving a regret--Hellinger inequality like \prettyref{eq:JZ09} is
that regret compares the scores (derivative of log density) while Hellinger only compares
the densities themselves. To bridge this gap, Jiang and Zhang introduced a sequence $\Delta_k$ defined in terms of the $k$th derivative of $f_G-f_H$, where $\Delta_0$ and $\Delta_1$ are approximately the Hellinger and the regularized regret, respectively.
They then proved a remarkable recursive inequality
$\Delta_k^2 \leq \Delta_{k-1}(\Delta_{k+1} + C \sqrt{\log(1/\rho)} \Delta_k)$ and bounded $\Delta_k$ separately using Fourier analysis, concluding the desired \prettyref{eq:JZ09} by backward induction.
Since its introduction, the Jiang--Zhang method has remained essentially the only route for
bounding the regret of $g$-modeling estimators,\footnote{One exception is \cite{JPW21} for the Poisson EB, where the regret can be bounded optimally by the Hellinger thanks to the discreteness of the Poisson model and the light tail of the prior. Nevertheless, this method fails for the moment class and an argument \`a la Jiang--Zhang is still needed \cite{SW22}.}
with extensions to multiple dimensions \cite{saha2020nonparametric}, higher-order estimands
\cite{ghosh2025stein} (see also the earlier version of \cite{chen2026empirical}), heteroskedastic variances \cite{jiang2020general,soloff2025multivariate,chen2026empirical}, and the Poisson model
\cite{SW22}.
At the same time, it is long suspected that this argument may not be
tight,\footnote{\cite{JiangZhang2009} remarked that ``Still, the cubic power of the
logarithmic factors [...]
is crude.'' and that
``we do not believe that mathematical
induction is sharp in the argument with higher and higher order of differentiation
in the proof of Lemma 1.''
} partially contributing to a $\operatorname{polylog}(n)$
gap between the best known regret upper bound and information-theoretic limits
\cite{polyanskiy2021sharp,kang2026function}. Moreover, it is also not obvious whether the
regularization in ~(\ref{eq:regularized_regret}) is merely a proof technique or plays a
more fundamental role for empirical Bayes.
\paragraph{Main contributions.}
We present a new technique for bounding regret in terms of Hellinger
distance \textit{without regularization}.
Compared to the recursive argument of Jiang and Zhang, the proposed method is conceptually simpler
and yields sharper, sometimes optimal, regret bounds.
The major contributions of this paper are as follows.
\begin{itemize}
\item For priors with compact support, we show that
\begin{equation}
\mathsf{Regret}(H \Vert G) \lesssim \epsilon^2 \frac{\log \frac{1}{\epsilon}}{\log \log \frac{1}{\epsilon}},
\label{eq:regret-compact-intro}
\end{equation}
and prove that this is unimprovable in the worst case.
This result has several statistical consequences, including improved regret guarantee for the nonparametric maximum likelihood estimator (NPMLE). Notably, when applied to the support-constrained NPMLE with sample size $n$, it yields a high-probability regret bound for the \textit{unregularized} estimator: $\mathsf{Regret}(\widehat G_n \Vert G) \lesssim \frac{1}{n} (\log n)^3 (\log
\log n)^{-1}$, compared to the previously known best result of $\frac{1}{n} (\log n)^5$ with regularization \cite{JiangZhang2009}.\footnote{The lower bound in \cite{polyanskiy2021sharp} is $\Omega(\frac{1}{n} (\log n/\log \log n)^2)$, where the remaining $\log n$ gap stems from a gap between upper and lower bounds of estimating the density $f_G$ in Hellinger distance. If an estimator $H=\widehat G$ were to match the $\epsilon^2 = \Omega(n^{-1} \log n)$ lower bound of \cite{kim2014minimax}, then this argument would match the optimal rate up to $\log \log n$ factors.}
\item We extend this argument to priors with exponential tails, such as subgaussian or subexponential priors. For subgaussian priors, we show that $\mathsf{Regret}(H\Vert G) \lesssim \epsilon^2 \log \frac{1}{\epsilon} \log \log \frac{1}{\epsilon}$, which is optimal up to $\log\log$ factors.
\item Finally, attempting to extend this argument to heavier-tailed priors reveals that
the regularization in \cite{JiangZhang2009} is in fact necessary in this regime. We show
that, under only a bounded $p$th-moment assumption, the unregularized regret can be as
large as $\Omega (\epsilon^ {2-2/p})$, while the regularized regret bound \prettyref{eq:JZ09} continues to hold.
\end{itemize}
\paragraph{Proof ideas.}
As discussed earlier, controlling regret in terms of Hellinger distance entails bounding a derivative in terms of the original function.
Such a bound is clearly impossible in general, but it becomes possible for certain classes
of regular functions, most notably \textit{polynomials}. This crucial insight is gained
through interactions with GPT-5.4 using OpenAI Codex. It motivates the following
program:
\begin{enumerate}
\item
Identify a target function $g$ and a weight function $w$ such that
the Hellinger distance $d_{\rm H}^2(f_G,f_H)$ is largely determined by
$\|g\|_{L_2(w)}^2 := \int g^2 w dy$ and the regret $\mathsf{Regret}(H\|G)$ by
$\|g'\|_{L_2(w)}^2$.
\item Show that the weight $w$ satisfies a \emph{Bernstein-type inequality}:
for any degree-$k$ polynomial $p$,
\begin{equation}
\|p'\|_{L_2(w)} \leq a_k
\|p\|_{L_2(w)}
\label{eq:bernstein-general}
\end{equation}
\item Quantify the approximation error: find a degree-$k$ polynomial $p$ so that $\|g-p\|_{L_2(w)}$ and
$\|g'-p'\|_{L_2(w)}$ is bounded in terms of $k$.
\end{enumerate}
Putting these ingredients together and optimizing the degree yield a regret--Hellinger inequality.
There are multiple ways to execute this program. To fix ideas, let us focus on the class of compactly supported priors. One may choose
$g = \frac{f_G-f_H}{f_G+f_H}$ and $w=(f_G+f_H)/2=f_{(G+H)/2} * \varphi$,
in order to capitalize on the classical Bernstein inequality for the standard Gaussian density $\varphi$ (an immediate consequence of properties of Hermite polynomials; see \prettyref{rmk:bernstein-perturb}):
\begin{equation}
\|p'\|_{L_2(\varphi)} \leq \sqrt{k}
\|p\|_{L_2(\varphi)}
\label{eq:bernstein-gaussian}
\end{equation}
and hence (by linearity) for any Gaussian mixture. In addition,
the best degree-$k$ polynomial approximation error of this choice of $g$ is at most $\mathop{\rm exp}(-\Omega(\sqrt{k}))$.
Choosing $k =\Theta((\log \frac{1}{\epsilon})^2)$ leads to $\mathsf{Regret}(H\|G) = O(\epsilon^2 (\log \frac{1}{\epsilon})^2)$, which already improves over the state of the art of \cite{JiangZhang2009} and does so without regularization.
To obtain the sharp inequality, we instead choose
\[
g = \frac{f_G-f_H}{\varphi}, \quad w= \frac{\varphi^2}{(f_G+f_H)/2}.
\]
This $g$ admits a substantially better polynomial approximation error of $\mathop{\rm exp}(-\Omega(k
\log k))$. In addition, we prove a Bernstein-type inequality
\prettyref{eq:bernstein-general} for the non-standard weight $w$ with $a_k = O(\sqrt{k})$.
Setting
$k =\Theta(\log \frac{1}{\epsilon}/ \log\log \frac{1}{\epsilon})$
yields the desired \prettyref{eq:regret-compact-intro}.
We note that there is a sizable literature on Bernstein-type inequalities for weighted
norms (see, e.g., \cite{LevinLubinsky2001,lubinsky2007survey}); however these results
require additional assumptions that appear difficult to verify in our setting. Instead, we
present self-contained proofs using a linear algebraic argument, as the inequality \prettyref{eq:bernstein-general} boils down to bounding the operator norm of the matrix representing the differentiation operator on the space of polynomials.
\section{Main results}
\subsection{New Regret--Hellinger inequality}
\begin{theorem}
\label{thm:ub-compact-intro}
Let $G,H$ be supported on $[-M,M]$.
There exists a constant $C=C(M)$ such that
\[
\mathsf{Regret}(H\|G)
\leq
C \epsilon^2 \frac{\log \frac{1}{\epsilon}}{\log \log \frac{1}{\epsilon}}
\]
where $\epsilon^2 = d_{\rm H}^2(f_{G},f_{H})$.
\end{theorem}
The following result shows that the regret upper bound in \prettyref{thm:ub-compact-intro} is sharp up to constants:
\begin{theorem}
There exists a sequence $(G_m,H_m)$ all supported on $[-1,1]$, such that
$\epsilon_m^2 \equiv d_{\rm H}^2(f_{G_m},f_{H_m}) \to 0$ and
\[
\mathsf{Regret}(H_m\|G_m)
\geq
c_0 \epsilon_m^2 \frac{\log \frac{1}{\epsilon_m}}{\log \log \frac{1}{\epsilon_m}}
\]
where $c_0$ is an absolute constant.
\label{thm:lb}
\end{theorem}
We now extend \prettyref{thm:ub-compact-intro} to priors with exponential tails.
For $\alpha, \sigma>0$, define
\begin{equation}
\label{eq:Galpha}
{\mathcal{G}}_{\alpha}(\sigma) = \{\text{Law}(U):
\mathbb{E}[\mathop{\rm exp}((|U|/\sigma)^\alpha] \leq 2\}.
\end{equation}
In the special case of $\alpha=2$, this is the class of subgaussian distributions with
proxy variance proportional to $\sigma^2$; for $\alpha = 1$, it is the subexponential
class.
\begin{theorem}
\label{thm:ub-exp}
Let $G,H\in {\mathcal{G}}_\alpha(\sigma)$.
There exists a constant $C=C(\alpha,\sigma)$ such that
\[
\mathsf{Regret}(H\|G)
\leq
\begin{cases}
C \epsilon^2 \left( \log \frac{1}{\epsilon} \right)^{2/\alpha}
\left( \log\log \frac{1}{\epsilon} \right)^2 & \alpha\leq 2 \\
C \epsilon^2 \log \frac{1}{\epsilon}
\log\log \frac{1}{\epsilon}
& \alpha>2
\end{cases}
\]
where $\epsilon^2 = d_{\rm H}^2(f_{G},f_{H})$.
\end{theorem}
For heavy-tailed priors---for instance, those satisfying only a bounded $p$th-moment
condition---we show in \prettyref{app:moment} that regret can be polynomially larger than
the squared Hellinger distance. Hence the regularization of \cite{JiangZhang2009} is not
merely a proof device but is in fact necessary in order to obtain a regret nearly linear
in $d_{\rm H}^2$.
\subsection{Statistical applications}
\label{sec:statsapp}
Next we discuss implications of these
regret--Hellinger inequalities for empirical Bayes.
To simplify presentation and compare with existing results, we consider priors that are either compactly supported or subgaussian.
One of the most popular methods for learning a prior is the nonparametric maximum
likelihood estimator (NPMLE) \cite{KW56}:
\begin{equation}
\widehat G_{\rm NPMLE}
= \mathop{\rm argmax}_{H \in {\mathcal{P}}(\mathbb{R})} \sum_{i=1}^n \log f_H(y_i).
\label{eq:NPMLE}
\end{equation}
where $y_1,\ldots,y_n$ are the given data points and the maximization is over all probability measures on $\mathbb{R}$.
It is known that \prettyref{eq:NPMLE} admits a unique and discrete maximizer, which has at most $n$ atoms in the worst case and $O(\log n)$ atoms in the typical case when $y_i$'s are drawn independently from a subgaussian distribution \cite{simar1976maximum,lindsay1983geometry1,PW20-npmle}.
Suppose the NPMLE is computed based on a training set $y_1,\ldots,y_n$ and then applied to a fresh test data point. The resulting regret (excess over the Bayes squared error) is bounded by the following result, which improves over the state of the art $O((\log n)^5/n)$ in
\cite{JiangZhang2009} for regularized NPMLE.
\begin{corollary}
\label{cor:NPMLE}
Let $y_1,\ldots,y_n{\stackrel{\text{i.i.d.\xspace}}{\sim}} f_G$, where $G \in {\mathcal{G}}_2(\sigma)$ is subgaussian with constant $\sigma$.
There exist constants $c,C$, depending on $\sigma$, such that with probability $1-n^{-c}$,
\begin{equation}
\mathsf{Regret}(\widehat G_{\rm NPMLE}\|G) \leq \frac{
C (\log n)^3 (\log \log n)^2}{n}.
\label{eq:reg-NPMLE}
\end{equation}
\end{corollary}
The proof of \prettyref{cor:NPMLE} is a direct consequence of \prettyref{thm:ub-exp}, once $\widehat G_{\rm NPMLE}$ is shown to be $O(1)$-subgaussian with high probability. This is done in \prettyref{app:NPMLE}.
Several further remarks are in order.
\begin{itemize}
\item Constrained NPMLE:
Suppose the true prior $G$ is supported on $[-M,M]$ for some constant $M$. Consider a constrained version of \prettyref{eq:NPMLE},
\begin{equation}
\widehat G_{\rm NPMLE}'
= \mathop{\rm argmax}_{H \in {\mathcal{P}}([-M',M'])} \sum_{i=1}^n \log f_H(y_i).
\label{eq:NPMLE-constrained}
\end{equation}
where $M'\geq M$ is a constant. In this case, \prettyref{eq:reg-NPMLE} can be improved to
\begin{equation}
\mathsf{Regret}(\widehat G_{\rm NPMLE}\|G) \leq \frac{
C (\log n)^3}{n \log\log n}.
\label{eq:reg-NPMLE-constrained}
\end{equation}
which is an immediate consequence of \prettyref{thm:ub-compact-intro} and the density estimation guarantee
$O((\log n)^2/n)$ for NPMLE (see
\cite[Theorem 4.1]{ghosal.vdv}, \cite[Theorem 1]{Zhang_2009}, or \cite[Theorem 6]{PW20-npmle}).\footnote{Notably, these results are all proved (using different method) for subgaussian priors; currently there is no improved density estimation rates for compactly supported priors.}
\item
State-of-the-art regret bound:
It is of interest to combine our Hellinger-regret inequality with the best known result on estimating Gaussian mixtures. The Birg\'e-Le Cam estimator is a general construction for density estimation based on pairwise comparison \cite{Birge83}. Despite its computational intractability, its Hellinger risk can be bounded using the local Hellinger entropy of the model class.\footnote{In fact, for Gaussian mixture with compactly supported mixing distribution, it is known that the optimal (minimax) Hellinger rate is \textit{determined} by the local Hellinger entropy \cite{JPW20}. The exact behavior of this local entropy is still open.} This local entropy is bounded in \cite{NW21} by constructing a covering of the
truncated moment space of the mixing distributions, leading to the squared Hellinger rate of
$O(\frac{1}{n}(\frac{\log n}{\log\log n})^{1.5})$ for the Birg\'e-Le Cam estimator.
Combining this with \prettyref{thm:ub-compact-intro} yields the regret upper bound of
$O(\frac{1}{n}(\frac{\log n}{\log\log n})^{2.5})$,
which appears the best known in the literature.
\item Comparison with lower bound and a conjecture:
In the normal mean model, \cite{polyanskiy2021sharp} showed that the minimax regret is at least $O(\frac{1}{n} \frac{\log n}{\log\log n})$ and $O(\frac{(\log n)^2}{n})$ for compactly supported and subgaussian priors, respectively.
We conjecture that these lower bound are tight and the bottleneck lies in resolving the sharp Hellinger rate.
The intuition is the following: despite the infinite dimensionality for these nonparametric mixture classes,
their ``effective model complexity'' is in fact finite, in the sense that each mixture density $f_G$ can be approximated by a $k$-component finite mixture within total variation distance $n^{-10}$, where $k=O(\frac{\log n}{\log \log n})$ for compactly supported $G$ and
$k=O(\log n)$ for subgaussian $G$ \cite{PW20-npmle}. As such, with sample size $n$, the
true nonparametric mixture is statistically indistinguishable from its finite-mixture approximation. As such, the density estimation error is expected to behave as $\frac{k}{n}$ (effective dimension over sample size.) For compact support, provided that such an upper bound of $O(\frac{1}{n}\frac{\log n}{\log \log n})$ can be established in squared Hellinger, applying \prettyref{thm:ub-compact-intro} immediately yields $O(\frac{1}{n}(\frac{\log n}{\log \log n})^2)$ for regret, matching the lower bound in \cite{polyanskiy2021sharp}.
\end{itemize}
\section{Compactly supported priors}
\label{sec:compact}
We prove a more precise version of \prettyref{thm:ub-compact-intro}
that is applicable to growing $M$.
\begin{theorem}
\label{thm:ub-compact}
Let $G,H$ be supported on $[-M,M]$.
Let $f_G = G * N(0,1)$ and $f_H = H * N(0,1)$.
Assume that the second moments of $G$ and $H$ are at most $\sigma^2$.
There exists an absolute constant $C_0$ such that
\[
\mathsf{Regret}(H\|G)
\leq
C_0 e^{\sigma^2/2} \cdot
\begin{cases}
(M+1)^2 \cdot
\epsilon \frac{\log \frac{1}{\epsilon}}{\log \frac{\log \frac{1}{\epsilon}}{M^2}} &
M^2 \leq \frac{1}{10} \log\frac{1}{\epsilon} \\
M^4 \epsilon &
M^2 \geq \frac{1}{10} \log\frac{1}{\epsilon}
\end{cases}.
\]
\end{theorem}
\subsection{A first reduction}
We first bound $\mathsf{Regret}$ by quantities $\delta, \Delta$, defined below.
\begin{lemma}
\label{lmm:reduction}
\[
\mathsf{Regret}(H\|G)
\leq C_0 M^2 \delta + C_0 \Delta
\]
for some absolute constant $C_0$, where
\begin{align}
\delta &= 2 \int_\mathbb{R} \frac{(f_G-f_H)^2}{f_G+f_H} \\
\Delta &= 2 \int_\mathbb{R} \frac{(m_Gf_G-m_Hf_H)^2}{f_G+f_H}.
\end{align}
\end{lemma}
\begin{proof}
Write
\begin{align}
\frac{f'_G}{f_G} - \frac{f'_H}{f_H}
= & ~ \frac{f_G'}{f_G}-\frac{2f_G'}{f_G+f_H} + \frac{2(f_G'-f_H')}{f_G+f_H} +
\frac{2f_H'}{f_G+f_H} - \frac{f_H'}{f_H}\nonumber\\
= & ~ \frac{f_G'(f_H-f_G)}{f_G(f_G+f_H)} + \frac{2(f_G'-f_H')}{f_G+f_H} +
\frac{f_H'(f_H-f_G)}{f_H(f_G+f_H)} \nonumber \\
= & ~ (m_G+m_H)
\frac{(f_H-f_G)}{f_G+f_H} + 2 \frac{m_G f_G-m_H f_H}{f_G+f_H}.
\label{eq:decomp}
\end{align}
The proof is completed by noticing that $|m_G|,|m_H|\leq M$.
\end{proof}
Note that $\delta$ is on par with the squared Hellinger distance
$\epsilon^2$:
\begin{equation}
\frac{\epsilon^2}{2}\leq \delta \leq \epsilon^2.
\label{eq:delta-eps}
\end{equation}
Thus, \prettyref{lmm:reduction} reduces the problem to proving
\[
\Delta \leq C \delta \frac{\log \frac{1}{\delta}}{\log\log \frac{1}{\delta}}.
\]
\subsection{Polynomial approximation and a Bernstein-style inequality}
Let $f \equiv (f_G+f_H)/2= f_{(G+H)/2}$.
Define the density ratio
\begin{equation}
g = \frac{f_G-f_H}{\varphi}
\label{eq:g}
\end{equation}
where $\varphi$ is the standard normal density.
Define the weight function
\begin{equation}
w = \frac{\varphi^2}{f}.
\label{eq:w}
\end{equation}
Crucially, we have
\begin{align}
\delta &= \int_{\mathbb{R}} g^2 w = \|g\|_{L_2(w)}^2 \label{eq:delta}\\
\Delta &= \int_{\mathbb{R}} (g'(x))^2 w(x)\,dx = \|g'\|_{L_2
(w)}^2
\label{eq:Delta}.
\end{align}
To estimate the differential operator on $g$, we first approximate $g$ by a polynomial, bound the operator norm of
the differential operator on polynomials by a linear algebraic argument, then quantify the approximation error bound. These are carried out in the following two lemmas.
\begin{lemma}[Bernstein-style inequality for weight $w$]
\label{lmm:bernstein}
Let $p$ be a degree-$k$ polynomial. Then
\[
\|p'\|_{L_2(w)}
\leq (2M+1)\sqrt{k+1} \|p\|_{L_2(w)}.
\]
\end{lemma}
\begin{lemma}[Polynomial approximation]
\label{lmm:poly-f}
Let $g$ be given in \prettyref{eq:g}. Assume that $\nu = (G+H)/2$ has zero mean.
For any $k \geq 2e M^2$,
there exists a degree-$k$ polynomial $p$ such that
\[
\|g-p\|_{L_2(w)}^2 \leq
\|g'-p'\|_{L_2(w)}^2
\leq 4M^2 \left( \frac{eM^2}{k} \right)^k.
\]
\end{lemma}
\subsection{Complete the proof}
With Lemmas \ref{lmm:reduction}--\ref{lmm:poly-f}, we now prove \prettyref{thm:ub-compact}.
\begin{proof}
Without loss of generality, we may assume $\delta \leq 0.01$.
In addition, we may assume $\nu=\frac{G+H}{2}$ has zero mean at a price of inflating
$M$ to $2M$. Indeed, suppose the mean $\mu$ is not zero. Let $\widetilde G$ and $\widetilde
H$ be the shifted version of $G$ and $H$ by $-\mu$ respectively, so that $\widetilde
\nu=(\widetilde G+\widetilde H)/2$ has zero mean.
Since $\mu \in [-M,M]$,
$\widetilde G,\widetilde H$ are both supported on $[-2M,2M]$. Furthermore,
both the Hellinger distance and the regret are shift-invariant:
$\mathsf{Regret}(\widetilde H\|\widetilde G)= \mathsf{Regret}(H\|G)$ and
$d_{\rm H}^2(f_{\widetilde G},f_{\widetilde H}) = d_{\rm H}^2(f_G,f_H)$.
First, for a degree-$k$ polynomial, we have
\begin{align*}
\|g'\|_{L_2(w)}
&\leq
\|g'-p'\|_{L_2(w)} +
\|p'\|_{L_2(w)}\\
&\leq
\|g'-p'\|_{L_2(w)}+
(2M+1)\sqrt{k+1} \|p\|_{L_2(w)}\\
&\leq \|g'-p'\|_{L_2(w)}+
(2M+1)\sqrt{k+1} (\|g\|_{L_2(w)}
+ \|g-p\|_{L_2(w)})
\end{align*}
where the second inequality follows from \prettyref{lmm:bernstein}.
Combining \prettyref{lmm:bernstein}, \prettyref{lmm:poly-f}, and
\prettyref{eq:delta}--\prettyref{eq:Delta}, we obtain
\[
\Delta
\lesssim
(M+1)^2 k \delta+
M^2 (M+1)^2 k \left( \frac{eM^2}{k} \right)^{k}
\]
provided $k\geq 2eM^2$.
Finally, we optimize $k$.
If $M^2 \leq 0.1 \log \frac{1}{\delta}$, we choose $k = C_1 M^2 \frac{\log \frac{1}{\delta}}{\log \frac{\log \frac{1}{\delta}}{M^2}}$
for suitably large absolute constant $C_1$.
If $M^2 \geq 0.1 \log \frac{1}{\delta}$, we choose $k = C_1 M^2$. In both cases, the
second term in the preceding display is at most $\delta^{10}$. Finally, invoking \prettyref{lmm:reduction} completes the proof.
\end{proof}
\subsection{Proof of lemmas}
\paragraph{Proof of \prettyref{lmm:bernstein}}
Define the inner product weighted by $w$ as:
\[
\langle f, g \rangle \equiv \int_\mathbb{R} f g w, \quad f,g\in L_2(w).
\]
Note that $w$ has at least a Gaussian tail so $L_2(w)$ includes all polynomials.
Denote by $\{q_j: j\geq 0\}$ the system of orthonormal polynomials for $w$ such that
\[
\langle q_i, q_j \rangle = {1\{{i=j}\}}.
\]
In particular, $\langle q_i, p \rangle=0$ for all polynomial of degree at most $i-1$.
To be definitive, assume that the leading coefficient of each $q_i$ is (strictly) positive, denoted by $\kappa_j>0$.
Expand a degree-$k$ polynomial $p$ as
$p=\sum_{j=0}^k a_j q_j$ and
$p'=
\sum_{j=0}^k b_j q_j$, where the coefficients are related by vector-matrix multiplication:
\[
b = L a
\quad \text{ and }\quad
\|p'\|_{L_2(w)}
\leq \|L\|_{\mathrm{op}} \|p\|_{L_2(w)}.
\]
where $ \|L\|_{\mathrm{op}}$ is the largest singular value of the $(k+1)\times (k+1)$ matrix $L$.
We thus analyze $L$ and bound ${\left\Vert L \right\Vert}_{\mathrm{op}}$. Note that $p'=\sum_{j=0}^k a_j q_j'$, and
so $L= (L_ {ij})$ is given by expanding each $q_j'$, namely
\[
q_j' = \sum_{i=0}^k L_{ij} q_i.
\]
By orthogonality,
$L_{ij} = \langle q_i, q_j' \rangle$. Clearly, $L_{ij} = 0$ for all $i\geq j$; in other words, $L$ is upper triangular.
Note that, by integration by parts, we have
\begin{equation}
\langle f', g \rangle =
- \langle f, g' \rangle + \langle f, gV' \rangle \quad \text{where } \quad w = e^{-V}, \quad V'=-\frac{w'}{w},
\label{eq:adjoint}
\end{equation}
for all $f,g$ with at most exponential growth.
Therefore, \[
L_{ij} =
\begin{cases}
0, & i \ge j\\
\ip{q_i, q_j V'} & i < j
\end{cases},
\]
since $\ip{q_i', q_j} = 0$ when $ i < j$.
To bound the operator norm of $L$, we decompose it into a \textit{dense} part and a \textit{sparse} part.
Since $w = \varphi^2/f$, $f= f_\nu$ with $\nu=\frac{G+H}{2}$ supported on $[-M,M]$, we have
\begin{equation}
V'(y) = -(\log w)'(y) = \frac{f_\nu'}{f_\nu}(y) + 2 y = m_\nu(y) + y
\label{eq:Vprime}
\end{equation}
Then
$L=A+B$,
where
\[
A_{ij} =
\begin{cases}
\langle q_i, q_j m_\nu \rangle & i < j\\
0 & \text{else}
\end{cases}
\quad
B_{ij} =
\begin{cases}
\langle q_{j-1}, q_j y \rangle & i = j-1\\
0 & \text{else}
\end{cases}
\]
where we used the fact that, by orthogonality,
$\langle q_i, q_j y \rangle=
\langle q_i y, q_j \rangle
=0$ if $i<j-1$.
It remains to bound the operator norms of $A$ and $B$ separately.
For $A$, we compute its Frobenius norm:
\[
\|A\|_F^2=
\sum_{j=1}^k \sum_{i=0}^{j-1}
\langle q_i, q_j m_\nu \rangle^2
\leq \sum_{j=1}^k \|q_j m_\nu\|_{L_2(w)}^2
\leq M^2 \sum_{j=1}^k \| {q_j}\|_{L_2(w)}^2 = M^2 k.
\]
Thus $\|A\|_{\mathrm{op}} \leq M \sqrt{k}$.
Note that $B$ contains a single superdiagonal. Then
\[
\|B\|_{\mathrm{op}} = \max_{j=1,\ldots,k} |a_j|
\]
where
\[
a_j \equiv B_{j-1,j} =
\langle q_{j-1}, q_j y \rangle = \ip{q_{j-1}y, q_j}.
\]
Equivalently, $a_j$ appears in the three-term recursion:
\begin{align}
y q_j(y) = a_{j+1} q_{j+1}(y)
+ b_j q_j(y) + a_j q_{j-1}(y)
\end{align}
for some $b_j$.
By assumption
$q_j(y)=\kappa_j y^j +\ldots$ and $q_{j-1}(y)=\kappa_{j-1} y^j +\ldots$ with
$\kappa_j>0$. Thus $q_j = \frac{\kappa_j}{\kappa_{j-1}}y q_{j-1} + p_{j-1}$ for some
polynomial of degree at most $j-1$.
Comparing leading coefficients, we thus get
$a_j =\langle q_j , q_{j-1} y \rangle
= \frac{\kappa_{j-1}}{\kappa_j}>0$.
By a similar argument, $\langle q_j', q_{j-1} \rangle = \frac{j\kappa_j}{\kappa_{j-1}}$.
Applying \prettyref{eq:adjoint} and \prettyref{eq:Vprime},
\[
\underbrace{\langle q_j', q_{j-1} \rangle}_{j/a_j} =
-\underbrace{\langle q_j, q_{j-1}' \rangle}_{=0} +
\langle q_j , q_{j-1} V' \rangle
= \underbrace{\langle q_j , q_{j-1} m_\nu \rangle}_{\equiv \beta_j} + \underbrace{\langle q_j , q_{j-1}y \rangle}_{a_j}
\]
Thus we get
$a_j(a_j+\beta_j) = j$, that is,
$a_j = (-\beta_j + \sqrt{\beta_j^2 + 4 j})/2$. Applying Cauchy-Schwarz,
\[
|\beta_j| = |\langle q_j , q_{j-1} m_\nu \rangle| \leq
\|q_j\|_{L_2(w)} \|q_{j-1}\|_{L_2(w)}
\|m_\nu\|_\infty \leq M.
\]
and hence $a_j \leq \sqrt{j} + M$.
This shows
\[
\|B\|_{\mathrm{op}} \leq \sqrt{k}+M
\]
and hence $\|L\|_{\mathrm{op}} \leq \sqrt{k}+M + M\sqrt{k}$, as desired.
\begin{remark}
\label{rmk:bernstein-perturb}
The same argument shows that the weight $w$ satisfies the following Bernstein-style inequality
\[
\|p'\|_{L_2(w)}
\leq O(\sqrt{k}) \|p\|_{L_2(w)}
\]
for all
degree-$k$ polynomial $p$, provided that the score function
$V'= -(\log w)'$ is a bounded perturbation to a linear function
\[
|V'(y) - c y| \leq C
\]
for some constant $c,C$.
This can be viewed as a perturbation result to the Bernstein inequality for Gaussians.\footnote{This is an immediate consequence of the derivative of Hermite polynomials: $H_j'=j H_{j-1}$ \cite{orthogonal.poly}.} For example, for $w=\varphi$,
\[
\|p'\|_{L_2(\varphi)}
\leq \sqrt{k} \|p\|_{L_2(\varphi)},
\]
attained at Hermite polynomials.
\end{remark}
\paragraph{Proof of \prettyref{lmm:poly-f}}
Since $\nu=(G+H)/2$ is centered, we have by Jensen's inequality
\[
f(y) = \mathbb{E}_{U\sim \nu}[\varphi(y-U)]
\geq \mathop{\rm exp}(-\sigma^2/2) \varphi(y)
\]
where $\mathbb{E}_{U\sim \nu}[U^2] \leq \sigma^2$ by the assumption that the second moments of $G$ and $H$ are both at most $\sigma^2$.
Thus
\begin{equation}
w(y) \leq \mathop{\rm exp}(\sigma^2/2) \varphi(y)
\label{eq:w-phi}
\end{equation}
So it suffices to bound the approximation error of $g$ and $g'$ in $L_2(\varphi)$, under standard Gaussian.
It is well-known that the likelihood ratio between a Gaussian mixture and a standard
Gaussian admits the following Hermite expansion (see, e.g., \cite[Lemma 9]{WY18}):
\[
\frac{f_G(y)}{\varphi(y)} = \sum_{j\geq 0} \frac{m_j(G)}{j!} H_j(y)
\]
where $H_j$ is the degree-$j$ Hermite polynomial satisfying $\mathbb{E}[H_i(Z)H_j(Z)]=i! {1\{{i=j}\}}$, and $m_j(G)$ is the $j$th moment of $G$.
Hence
\[
g(y) =
\frac{f_G(y)-f_H(y)}{\varphi(y)} = \sum_{j\geq 0} \frac{m_j(G)-m_j(H)}{j!} H_j(y).
\]
Truncate this series at $k$ and denote it by $p(y)$. Then we also have
$g'(y)-p'(y) =
\sum_{j>k} \frac{m_j(G)-m_j(H)}{j!} H_j'(y) =
\sum_{j>k} \frac{m_j(G)-m_j(H)}{(j-1)!} H_{j-1}(y)$.
Thus
\[
\|g-p\|_{L^2(\varphi)}^2 = \sum_{j>k} \frac{|m_j(G)-m_j(H)|^2}{j!},
\quad
\|g'-p'\|_{L^2(\varphi)}^2 = \sum_{j>k} \frac{|m_j(G)-m_j(H)|^2}{(j-1)!}
\]
and it suffices to bound the latter.
Note that $|m_j(G)|,|m_j(H)| \leq M^j$ and $j! \geq (j/e)^j$, we get
\begin{equation}
\|g'-p'\|_{L^2(\varphi)}^2
\leq 2M^2 \sum_{\ell\geq k} \left( \frac{eM^2}{k} \right)^\ell
\label{eq:gp-compact}
\end{equation}
completing the proof by summing the geometric series.
\section{Priors with exponential tails}
\label{sec:exp}
In this section we prove \prettyref{thm:ub-exp}, extending the regret bound in
\prettyref{thm:ub-compact} for compactly supported priors to those in the class
${\mathcal{G}}_\alpha(\sigma)$ defined in \prettyref{eq:Galpha}, having exponential tails. Throughout this section, all constants (including those implicit in $\lesssim$) depend on $\alpha,\sigma$.
Note that one may apply \prettyref{thm:ub-compact} by approximating the true prior with a
compact-supported one. This yields a worse logarithmic factor. For example, for the
subgaussian class, applying
\prettyref{thm:ub-compact} with $M \asymp \sqrt{\log \frac{1}{\epsilon}}$ yields an
$O\pr{\epsilon (\log \frac{1}{\epsilon})^2}$ upper bound, which is inferior to
\prettyref{thm:ub-exp}. Instead, we take a more direct approach.
Similar to the proof of \prettyref{thm:ub-compact}, the first step is again to reduce $\mathsf{Regret}(H\|G)$ to a weighted derivative quantity $\Delta$.
Recall the definitions of $g$, $w$, $\delta$, and $\Delta$ in
~(\ref{eq:g})--~(\ref{eq:Delta}) from \prettyref{sec:compact}.
\begin{prop}[Reduction to $\Delta$]
\label{prop:exp-delta-reduction}
For $H,G \in \mathcal{G}_\alpha(\sigma)$,
\[
\mathsf{Regret}(H\|G)
\lesssim
\Delta
+
\delta \left( \log \frac{1}{\delta} \right)^{2/(\alpha\wedge 2)}.
\]
\end{prop}
\begin{proof}
By the
same decomposition \prettyref{eq:decomp} in \prettyref{lmm:reduction},
\[
\mathsf{Regret}(H\|G)
\lesssim
\int_\mathbb{R} (m_G+m_H)^2 \frac{(f_G-f_H)^2}{f_G+f_H}
+
\int_\mathbb{R} \frac{(m_Gf_G-m_Hf_H)^2}{f_G+f_H}.
\]
By ~(\ref{eq:Delta}), the second term is $\Delta/2$, so
\[
\mathsf{Regret}(H\|G)
\lesssim
\int_\mathbb{R} (m_G+m_H)^2 \frac{(f_G-f_H)^2}{f_G+f_H}
+ \Delta.
\]
To bound the posterior mean, we apply ~(\ref{eq:V1}) from \prettyref{lem:Vpp-phi2-over-f},
with $a:=\sigma(\log 4)^{1/\alpha}$ satisfying $F([-a,a])\geq 1/2$ for $F\in{\mathcal{G}}_\alpha(\sigma)$ using Markov's inequality,
obtaining
\[
|m_F(y)| \leq C(1+|y|),
\qquad
y\in\mathbb{R}. \addtocounter{equation}{1}\tag{\theequation} \label{eq:posterior-mean-bound}
\]
Fix $T>1 $ to be specified next. Then $
|m_G(y)|+|m_H(y)|
\lesssim
T$ for any $|y|\leq T$,
so
\[
\int_{|y|\leq T} (m_G+m_H)^2 \frac{(f_G-f_H)^2}{f_G+f_H}
\lesssim
T^2 \delta.
\]
For $|y| > T$, using
$
\frac{(f_G-f_H)^2}{f_G+f_H} \leq f_G+f_H$
and ~(\ref{eq:posterior-mean-bound}) again we obtain
\[
(m_G(y)+m_H(y))^2 (f_G(y)+f_H(y))
\lesssim
y^2(f_G(y)+f_H(y)).
\]
Thus
\[
\mathsf{Regret}(H\|G)
\lesssim
T^2 \delta + \Delta + \int_{|y|>T} y^2(f_G+f_H).
\]
Since $G\in {\mathcal{G}}_\alpha(\sigma)$ and $f_G = G * N(0,1)$, by Chernoff bound, the tail contribution is at most
\[
\int_{|y|>T} y^2 f_G \lesssim T^2 \mathop{\rm exp}(-c T^{\alpha \wedge 2})
\]
for some constant $c$, and the same holds for $f_H$. Finally, choosing \[
T:=C \left( \log\left( 1+\frac{1}{\delta} \right) \right) \right)}^{1/(\alpha\wedge 2)},
\]
for appropriately large $C$,
we have
$ \int_{|y|>T} y^2(f_G+f_H) \leq \delta^2$, completing the proof.
\end{proof}
The next lemma is an analogue of the polynomial approximation in \prettyref{lmm:poly-f}.
\begin{lemma}
\label{lmm:exp-poly}
Let $g = \frac{f_H-f_G}{\varphi}$
be given in \prettyref{eq:g}.
Assume that $\nu=(G+H)/2$ has mean zero for $G, H \in \mathcal G_\alpha(\sigma)$. Then there exist constants
$c,C>0$, depending only on $\alpha,\sigma$, such that for every $k\geq 1$
there is a degree-$k$ polynomial $p_k$ with
\[
\|g-p_k\|_{L_2(w)}^2
\vee
\|g'-p_k'\|_{L_2(w)}^2
\leq
\begin{cases}
C \mathop{\rm exp}\left( -c k^{\alpha/2} \right),
& \alpha\leq 2,\\
C \mathop{\rm exp}\left( -c k \log k \right),
& \alpha>2.
\end{cases}
\]
\end{lemma}
Finally, the following result is an analogue of \prettyref{lmm:bernstein}.
The proof is deferred to the end of \prettyref{app:bernstein}.
\begin{prop}
\label{prop:exp-bernstein}
Assume that $\nu=(G+H)/2$ has mean zero for $G, H \in \mathcal G_\alpha(\sigma)$. Then every degree-$k$ polynomial
$p$ with $k\geq 2$ satisfies
\[
\|p'\|_{L_2(w)}
\lesssim
\sqrt{k}\,\log k\,\|p\|_{L_2(w)}.
\]
\end{prop}
Putting these together, we prove \prettyref{thm:ub-exp}.
\begin{proof}[Proof of \prettyref{thm:ub-exp}]
Since
\[
\epsilon^2
=
\int_\mathbb{R} \frac{(f_G-f_H)^2}{(\sqrt{f_G}+\sqrt{f_H})^2}
\asymp
\int_\mathbb{R} \frac{(f_G-f_H)^2}{f_G+f_H}
=
\delta = \|g\|_{L_2
(w)}^2,
\]
it suffices to work with $\delta$. As in the proof of \prettyref{thm:ub-compact}, it is without loss of generality to assume
$
\delta\leq e^{-e},
$
and
$\nu=(G+H)/2$ is mean-zero by inflating the constant $\sigma$.
By \prettyref{prop:exp-delta-reduction}, it remains to bound $\Delta=\|g'\|_{L_2
(w)}^2$.
Let $p_k$ be the polynomial from \prettyref{lmm:exp-poly}. By
\prettyref{prop:exp-bernstein},
\[
\|g'\|_{L_2(w)}
\leq
\|g'-p_k'\|_{L_2(w)}
+
C_{\alpha,\sigma}\sqrt{k+1}\log k
\left(
\|g\|_{L_2(w)}+\|g-p_k\|_{L_2(w)}
\right)
\]
that is,
\[
\Delta
\lesssim
k\log^2 k\,\bigl(\delta+E_k\bigr),
\]
where $E_k
:=
\|g-p_k\|_{L_2(w)}^2
\vee
\|g'-p_k'\|_{L_2(w)}^2$.
Applying \prettyref{lmm:exp-poly}, setting
\[
k=
\begin{cases}
\Big\lceil
C_{\alpha,\sigma}
\log^{2/\alpha}\left( \frac{e}{\delta} \right)
\Big\rceil & \alpha\leq 2\\
\Big\lceil
C_{\alpha,\sigma}
\frac{\log\left( \frac{e}{\delta} \right)}
{\log\left( e+\log\left( \frac{e}{\delta} \right) \right) \right)}}
\Big\rceil & \alpha > 2\\
\end{cases}
\]
with suitably large $C_{\alpha,\sigma}$ ensures
$E_k\leq \delta$ and completes the proof.
\end{proof}
\begin{proof}[Proof of \prettyref{lmm:exp-poly}]
Let
\[
L:=
\begin{cases}
c \sqrt{k},
& \alpha\leq 2,\\
c \bigl(k\log k\bigr)^{1/\alpha},
& \alpha>2,
\end{cases}
\]
where $c>0$ is a sufficiently small constant depending on $\alpha$.
Let $k$ be sufficiently large so that $L\geq 1$.
Write
\[
G=G_{\leq L}+G_{>L},
\qquad
H=H_{\leq L}+H_{>L},
\]
where $G_{\leq L}$ and $H_{\leq L}$ are the restrictions to $[-L,L]$, and set
\[
g_{\leq L}
:=
\frac{f_{G_{\leq L}}-f_{H_{\leq L}}}{\varphi},
\qquad
g_{>L}
:=
\frac{f_{G_{>L}}-f_{H_{>L}}}{\varphi}.
\]
Then $
g=g_{\leq L}+g_{>L}$.
For the compact part, the argument is identical to that of \prettyref{lmm:poly-f}. Since $\nu$ is centered and belongs to ${\mathcal{G}}_\alpha(\sigma)$, its second
moment is at most a constant depending only on $\alpha,\sigma$.
Applying \prettyref{eq:w-phi}, we have $w \lesssim \varphi$ everywhere.
Thus \prettyref{eq:gp-compact} yields a degree-$k$ polynomial $p_k$ such that
\[
\|g_{\leq L}-p_k\|_{L_2(w)}^2
\vee
\|g_{\leq L}'-p_k'\|_{L_2(w)}^2
\lesssim
L^2 \left( \frac{eL^2}{k} \right)^k
\]
provided that $k \geq 2e L^2$.
By the choice of $L$,
\[
L^2 \left( \frac{eL^2}{k} \right)^k
\leq
\begin{cases}
C\mathop{\rm exp}(-c k),
& \alpha\leq 2,\\
C\mathop{\rm exp}\left( -c k\log k \right),
& \alpha>2.
\end{cases}
\]
It remains to control the tail part. Unlike the proof of \prettyref{lmm:poly-f}, we cannot use $w \lesssim \phi$ and bound $L_2(\varphi)$, because $\|g\|_{L_2(\varphi)}$ may be infinite (e.g.~for Gaussian $G$ with sufficiently large variance.)
Instead, we directly control the tail in $L_2(w)$, where $w=\frac{\varphi^2}{f}$. Since
$f=\frac{f_G+f_H}{2}$, we have
\begin{align*}
\|g_{>L}\|_{L_2(w)}^2
&\leq
2 \int \frac{f_{G_{>L}}(y)^2}{f(y)}\,dy
+
2 \int \frac{f_{H_{>L}}(y)^2}{f(y)}\,dy\\
&\leq
4 \int \frac{f_{G_{>L}}(y)^2}{f_G(y)}\,dy
+
4 \int \frac{f_{H_{>L}}(y)^2}{f_H(y)}\,dy\\
&\leq
4 \int f_{G_{>L}}(y)\,dy
+
4 \int f_{H_{>L}}(y)\,dy\\
&=
4 G(|U|>L)+4 H(|U|>L) \lesssim
\mathop{\rm exp}(-c L^\alpha)
\end{align*}
the last step applying Chernoff's bound.
For the derivative, note that
\[
\left(\frac{f_{G_{>L}}}{\varphi}\right)(y)
= \int \mathop{\rm exp}\left( yu-\frac{u^2}{2} \right)\,G_{>L}(du), \qquad
\left(\frac{f_{G_{>L}}}{\varphi}\right)'(y)
= \int u \mathop{\rm exp}\left( yu-\frac{u^2}{2} \right)\,G_{>L}(du).
\]
Thus
\[
\left(\frac{f_{G_{>L}}}{\varphi}\right)(y)
=
\frac{f_{G>L}(y)}{\varphi(y)}
\int u \pi(du), \quad
\pi(du) := \frac{ \mathop{\rm exp}\left( yu-\frac{u^2}{2} \right)
G_{>L}(du)
}{\int \mathop{\rm exp}\left( yu-\frac{u^2}{2} \right)\,G_{>L}(du)}
\]
where $\pi$ is a probability measure. Thus Cauchy-Schwarz gives
\[
\left(\frac{f_{G_{>L}}}{\varphi}\right)'(y)^2
\leq
\frac{f_{G>L}(y)}{\varphi(y)}
\int u^2 \mathop{\rm exp}\left( yu-\frac{u^2}{2} \right)\,G_{>L}(du),
\]
and similarly for $H_{>L}$. Therefore
\begin{align*}
\|g_{>L}'\|_{L_2(w)}^2
&\leq
2 \int \left(\frac{f_{G_{>L}}}{\varphi}\right)'(y)^2
\frac{\varphi(y)^2}{f(y)}\,dy
+
2 \int \left(\frac{f_{H_{>L}}}{\varphi}\right)'(y)^2
\frac{\varphi(y)^2}{f(y)}\,dy\\
&\leq
4 \int \left(\frac{f_{G_{>L}}}{\varphi}\right)'(y)^2
\frac{\varphi(y)^2}{f_G(y)}\,dy
+
4 \int \left(\frac{f_{H_{>L}}}{\varphi}\right)'(y)^2
\frac{\varphi(y)^2}{f_H(y)}\,dy\\
&\leq
4 \int_{|u|>L} u^2\,G(du)
+
4 \int_{|u|>L} u^2\,H(du) \lesssim
L^2 \mathop{\rm exp}(-c L^\alpha),
\end{align*}
the last step again applying Chernoff's bound.
By the choice of $L$, the tail part satisfies
\[
\|g_{>L}\|_{L_2(w)}^2
\vee
\|g_{>L}'\|_{L_2(w)}^2
\leq
\begin{cases}
C' \mathop{\rm exp}(-c k^{\alpha/2}),
& \alpha\leq 2,\\
C' \mathop{\rm exp}\left( -c k\log k \right),
& \alpha>2.
\end{cases}
\]
Finally, the proof is completed using
\[
\|g-p_k\|_{L_2(w)}^2
\leq
2\|g_{\leq L}-p_k\|_{L_2(w)}^2
+
2\|g_{>L}\|_{L_2(w)}^2,
\]
and similarly for the derivative.
\end{proof}