\section{Sketch of the Analysis}
\label{sec:analysis_idea}
In this section we briefly explain the main arguments at the basis of our analysis.
We start from the analysis of the localized excess risk, which is decomposed into the generalization error (i.e., the difference between the risk and empirical risk) and the gap between the empirical risk and the risk of the minimizer $\bw^{\star}_{\lambda}$,
\begin{align}
\label{eq:gibbs_gen_error_decomp}
\E\br{R(\boldsymbol{w}) - R(\bw^{\star}_{\lambda}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}(r)}
  &= \E\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}(r)}\\
  \label{eq:gibbs_gen_error_decomp2}
  &+ \E\br{\wh{R}_S(\boldsymbol{w}) - R(\bw^{\star}_{\lambda}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}(r)}
\end{align}
where the expectation is taken with respect to the empirical Gibbs density~\eqref{eq:gibbs}.
For brevity we omit the indices corresponding to the minima, as in the localized setting we consider a local minimum at the time.
The generalization error of Gibbs-ERM is captured by Theorem~\ref{thm:gibbs_gen_error} below (whose proof can be found in Section~\ref{sec:stability}).
\begin{theorem}[Generalization bound]
  \label{thm:gibbs_gen_error}
Consider any loss function $f : \reals^d \times \mathcal{Z} \to \mathbb{R}$ that is $\sigma$-sub-Gaussian in the first argument with respect to the Gibbs density
\begin{equation}
  \label{eq:gibbs_finite_sums}
  \wh{p}_{S,\gamma}(\boldsymbol{w}) \propto e^{-\frac{\gamma}{m} \sum_{i=1}^m f(\boldsymbol{w}, z_i)} \qquad \gamma > 0
\end{equation}
conditioned on a measurable $A \subseteq \reals^d$. Then the generalization error of Gibbs-ERM satisfies
\[
  \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in A} } \leq \frac{4 \sigma^2 \gamma}{m}~.
\]
\end{theorem}
Assuming that $f$ is everywhere bounded by $M$, Hoeffding Lemma implies the bound $\frac{M^2 \gamma}{2 m}$.
Under the same boundedness assumption, a bound with similar rates was also shown by~\cite{xu2017information} within the mutual information framework.
Our proof works by showing that the Gibbs density is on-average replace-one stable in the sense of~\cite[Section 13]{shalev2014understanding} (we include it here for completeness).

The second quantity~\eqref{eq:gibbs_gen_error_decomp2} is less straightforward to control in a distribution-dependent setting.
\cite{raginsky2017nonconvex} give a global upper bound
\[
  \wh{R}_S(\boldsymbol{w}) - R(\bw^{\star}_{\lambda}) = \mathcal{\tilde{O}}\pr{\frac{d}{\gamma}}
\]
by further decomposing~\eqref{eq:gibbs_gen_error_decomp2} as follows
\[
  \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}[\wh{R}_S(\boldsymbol{w})] - \min_{\boldsymbol{u} \in \reals^d} \wh{R}_S(\boldsymbol{u}) + \min_{\boldsymbol{u} \in \reals^d} \wh{R}_S(\boldsymbol{u}) - \E_S[\wh{R}(\bw^{\star}_{\lambda})]~.
\]
The second term is bounded trivially, while the analysis of the first term follows the so called ``almost ERM'' argument. In other words, understanding how ``close'' the solutions generated by Gibbs-ERM are to the solutions of \ac{ERM}.

In our distribution-dependent setting we follow a different route: consider the case of \ac{RLS}, where the empirical risk is an average of square-regularized losses.
A rather straightforward argument (based on Gaussian integration) gives the following \emph{identity} in an ``almost ERM'' style:
\begin{align*}
  \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{\wh{R}_S(\boldsymbol{w})} - \min_{\boldsymbol{u} \in \reals^d} \wh{R}_S(\boldsymbol{u})
  =
  \frac{1}{\gamma} \, \mathrm{tr}\pr{\nabla^2 \wh{R}_S(\bhatw_{\lambda}) \pr{\nabla^2 \wh{R}_S(\bhatw_{\lambda}) + \lambda \boldsymbol{I}}^{-1} }
\end{align*}
where $\bhatw_{\lambda}$ is a minimizer of the \ac{RLS} problem.
Observe that in the above identity we obtain an empirical counterpart of the effective dimension introduced in~\eqref{eq:gibbs_local_excess}.
Since our goal is a distribution-dependent result, one possibility is to consider the concentration of Hessian eigenvalues. However, we follow a more direct approach. As we said earlier, the ``almost ERM'' analysis of \ac{RLS} is relatively easy using Gaussian integration (since $\wh{p}_{S,\gamma}$ is a Gaussian density).
Since we deal instead with general smooth densities, our idea is to quantify the gap between the density at hand and the Gaussian density.
This is nicely handled by the \emph{transportation lemma}~\citep[Lemma 4.18]{boucheron2013concentration}, characterizing the difference between the expectations of different densities in terms of the KL-divergence between them.
As a comparison we choose the Gaussian density
$
  q_{\gamma} \propto \exp\big(-\frac{\gamma}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2\big)
$,
which only depends only on distribution-related quantities.
An ``almost ERM'' style analysis applied to $q_{\gamma}$ will give us exactly a distribution-dependent effective dimension.
So, the only issue is the actual gap between densities. By expanding the KL-divergence we observe that the critical terms are
\begin{align}
  &- \gamma \E_S\br{\E_{\wh{p}_{S,\gamma}}\br{\wh{R}_{S,\lambda}(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}}}
  + \frac{\gamma}{2} \E_S\br{\E_{\wh{p}_{S,\gamma}}\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }} \nonumber\\
  \lesssim \ &-\gamma \E_S\br{\E_{\wh{p}_{S,\gamma}}\br{R_{\lambda}(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}}} + \frac{\gamma^2}{m}
  + \frac{\gamma}{2} \E_S\br{ \E_{\wh{p}_{S,\gamma}}\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }} \label{eq:analysis_explained_1}\\
  \lesssim \ &\gamma \varepsilon(r) + \frac{\gamma^2}{m}~. \label{eq:analysis_explained_2}
\end{align}
To obtain~\eqref{eq:analysis_explained_1}, instead of using concentration, we resort to the generalization bound of Theorem~\ref{thm:gibbs_gen_error}, whereas~\eqref{eq:analysis_explained_2} is obtained by Taylor expansion of the regularized risk around its minimizer.
This is formally shown in Lemma~\ref{lem:truncated_EER_to_ERM}, while the decomposition~\eqref{eq:gibbs_gen_error_decomp} is bounded in Theorem~\ref{thm:gibbs_local_excess}.
Hence, the gap is quantified by the approximation error at the radius $r$ plus a sample-dependent term due to the use of empirical Gibbs density.
These terms appear in excess risk bounds~\eqref{eq:gibbs_local_excess},~\eqref{eq:gibbs_global_excess}, and~\eqref{eq:gibbs_global_pseudo_excess}.
\subsection{Global Analysis}
Starting from the conditional local excess risk in the form given by the left-hand side of~\eqref{eq:gibbs_gen_error_decomp}, we analyze a notion of global risk by bounding the probability of individual ellipsoids (i.e., neighborhoods of minima) and that of the complement of their union. Since for $\gamma \to \infty$ the probability of a complement approaches zero (as discussed in Remark~\ref{rem:tuning_r}), in order to obtain an asymptotic bound it is enough to focus on the relative probability of ellipsoids. In Lemma~\ref{lem:erm_prob} we derive upper and lower bounds on this probability via Laplace approximation (Lemma~\ref{lem:ellipse_prob}), and then analyze their limit for $\gamma \to \infty$. Combining the local excess risk bound and the bound on the asymptotic relative probability of ellipsoids allows us to control the asymptotic global pseudo excess risk~\eqref{eq:gibbs_global_pseudo_excess} ---see Corollary~\ref{cor:global_excess_risk_asymptotic}.

Finally, using a nonasymptotic bound on the probability of a complement ---see the proof of Theorem~\ref{thm:global_excess_risk}--- we can apply the law of total expectation to get also a nonasymptotic bound on the global excess risk.

\subsubsection*{Acknowledgments}
Authors would like to thank Olivier Bousquet, Sébastien Gerchinovitz, and Abbas Mehrabian for stimulating discussions on this work.

\section{Preliminaries}
Throughout this paper, we use $f \lesssim g$ to indicate that there exists a universal constant $C > 0$ such that $f \leq C g$ holds uniformly over all arguments.
Let $\mathcal{B}_r(\boldsymbol{z}) \subset \field{R}^d$ be the ball of center $\boldsymbol{z}$ and radius $r > 0$ and let $\mathcal{B}_r = \mathcal{B}_r(\boldsymbol{0})$.
Given a positive definite $d \times d$ matrix $\boldsymbol{M}$, define $\|\boldsymbol{x}\|_{\boldsymbol{M}}^2 = \boldsymbol{x}^{\top} \boldsymbol{M} \boldsymbol{x}$ for $\boldsymbol{x} \in \mathbb{R}^d$.
Then, for any positive semi-definite $d \times d$ matrix $\boldsymbol{A}$ and $r > 0$ the corresponding ellipsoid centered at $\boldsymbol{x}_0\in\mathbb{R}^d$ is defined as $\mathcal{E}(\boldsymbol{x}_0, \boldsymbol{A}, r) \equiv \cbr{\boldsymbol{x} \in \mathbb{R}^d ~:~ \|\boldsymbol{x}_0 - \boldsymbol{x}\|_{\boldsymbol{A}} \leq r}$.

If $p$ and $q$ are densities that are absolutely continuous with respect to a measure $\mu$ over $\reals^d$, the Kullback-Liebler (KL) divergence between $p$ and $q$ is defined as
\begin{align*}
  \mathrm{KL}(p, q) &= \E_{\boldsymbol{w} \sim p}\Big[\ln\big(p(\boldsymbol{w})\big) - \ln\big(q(\boldsymbol{w})\big)\Big]~.
\end{align*}
\section{Introduction}

In the parametric setting of statistical learning, the learner is given a tuple $S = \pr{z_1, \ldots, z_m}$ of \emph{training examples}, that are drawn independently of each other from a fixed and unknown probability distribution $\mathcal{D}$ supported on an \emph{example space} $\mathcal{Z}$. Based on the training examples $S$ the learner selects a model $\boldsymbol{w}$ from a parameter space $\reals^d$.
The learner's goal is to minimize the \emph{statistical risk} $R(\boldsymbol{w}) = \E_z[\ell(\boldsymbol{w}, z)]$ of the selected model, where $z$ is drawn from $\mathcal{D}$ and $\ell \,:\, \reals^d \times \mathcal{Z} \to [0, M]$ is some known \emph{loss function}, which we assume to be non-negative, bounded, and twice differentiable.

A learner following the \acf{ERM} principle selects a model with the smallest empirical risk. Learners often also incorporate a penalty, leading to selecting a model from the set
\begin{equation}
  \label{eq:erm}
  \argmin_{\boldsymbol{w} \in \reals^d}\cbr{ \wh{R}_S(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2}\,, \qquad \lambda > 0\,,
\end{equation}
where $\wh{R}_S(\boldsymbol{w})$ is the \emph{empirical risk} of $\boldsymbol{w}$, defined by
\[
  \wh{R}_S(\boldsymbol{w}) = \frac{1}{m} \sum_{i=1}^m \ell(\boldsymbol{w}, z_i)\,.
\]
In the following, we will abbreviate the regularized empirical risk by $\wh{R}_{S,\lambda}$ and its population counterpart, $\E[\wh{R}_{S,\lambda}]$,  by $R_{\lambda}$.
In this paper we study a randomized version of \ac{ERM} known as \emph{Gibbs-ERM}.
A Gibbs algorithm outputs a model $\boldsymbol{w} \in \reals^d$ sampled from the \emph{Gibbs density}
\begin{equation}
  \label{eq:gibbs}
  \wh{p}_{S,\gamma}(\boldsymbol{w}) = \frac{1}{Z} \, e^{-\gamma \pr{ \wh{R}_S(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2 }}\,, \qquad \gamma > 0\,,
\end{equation}
where $Z = \int_{\reals^d} e^{-\gamma \pr{ \wh{R}_S(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2 }} \diff \boldsymbol{w}$ is the normalization constant and $\wh{R}_S$ is assumed to be such that $Z < \infty$ (for instance, this is the case when $\|\cdot\|$ is any norm and $\wh{R}_S$ is nonnegative).
It is not hard to see that we obtain \ac{ERM} as a special case of~\eqref{eq:gibbs} for $\gamma \to \infty$.
In the following expectations $\E[\cdot]$ are taken with respect to the joint distribution over the sample space $\mathcal{Z}^m \times \mathbb{R}^d$ (i.e., the product of the example space and the parameter space) unless explicitly stated otherwise, for instance $\E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}[\cdot]$.

Gibbs-ERM reveals its usefulness when the regularized empirical risk is non-convex and~\eqref{eq:erm} becomes intractable. This scenario brings out the connections between Gibbs-ERM and stochastic optimization algorithms, for instance \ac{SGLD} ---see below, along with a number of other settings in which Gibbs-ERM arises naturally.
One tantalizing related line of research lies in understanding theoretical properties of learning in overparameterized problems, such as deep neural networks, through the prism of stochastic optimization, since in these settings \ac{SGD} and its variants become de facto method of choice.
We believe that Gibbs-ERM principle provides an opportunity for explaining some of the learning-theoretic phenomena in this area.

In this paper we focus on the statistical properties of the Gibbs-ERM by analyzing distribution-dependent excess risk bounds.
In particular, we give upper bounds on the excess risk that can be much smaller compared to the previous literature, for instance \ac{SGLD}~\citep{raginsky2017nonconvex}, depending on the interplay between the data-generating distribution and the loss function.

\paragraph{\emph{\ac{SGLD} algorithm.}}
The recent interest in stochastic gradient descent algorithms for non-convex optimization led to the study of a variant called \ac{SGLD}. Apart from its simplicity, \ac{SGLD} has amenable theoretical properties, such as asymptotic convergence to global minima and polynomial saddle-point escape times~\citep{ge2015escaping}.
The update rule of plain \ac{SGLD} is
\[
  \widehat{\boldsymbol{w}}_{ t + 1 } = \widehat{\boldsymbol{w}}_{ t } - \eta \nabla \wh{R}_{S,\lambda}(\widehat{\boldsymbol{w}}_t) + \sqrt { \frac{2 \eta}{\gamma} } \, \boldsymbol{\xi}_t \qquad t=0, 1, 2, \ldots
\]
where $\widehat{\boldsymbol{w}}_1$ is sampled from a fixed distribution, $\boldsymbol{\xi}_t$ is a standard Gaussian ``noise'' vector (independent from the choice of $\widehat{\boldsymbol{w}}_1$), and $\eta$ is a step size.
The \ac{SGLD} algorithm is known to approximate the continuous-time Langevin diffusion equation
\begin{equation}
  \label{eq:langevin}
  \diff \boldsymbol{w}(t) = - \nabla \wh{R}_{S,\lambda}(\boldsymbol{w}(t)) \diff t + \sqrt { \frac{2}{\gamma} } \, \diff \boldsymbol{b}(t) , \quad t \geq 0
\end{equation}
where $\boldsymbol{b}(t)$ is the standard Brownian motion.
Indeed, under appropriate assumptions on the empirical risk, one can show that the solution to~\eqref{eq:langevin} admits~\eqref{eq:gibbs} as a stationary distribution~\citep{raginsky2017nonconvex,tzen2018local}.
While convergence in the limit is reassuring, the best known bound on the mixing time is of order $\text{polylog}(1/\varepsilon) \, e^{\mathcal{\tilde{O}}(d)}$ for non-convex empirical risks assuming that objective is smooth and dissipative (roughly speaking, assuring that the process~\eqref{eq:langevin} on average moves towards the origin)~\citep{raginsky2017nonconvex,xu2018global},
and it is not clear whether the exponential dependence on the parameters can be eliminated.

\paragraph{\emph{Information Risk Minimization.}}
Gibbs-ERM naturally arises when introducing a relative entropy regularization in the so-called Information Risk Minimization framework~\citep{zhang2006information,xu2017information}. Indeed $\wh{p}_{S,\gamma}$ in~\eqref{eq:gibbs} can be equivalently defined as the solution to the following convex optimization problem
\begin{equation}
  \label{eq:IRM}
  \arginf_{\widehat{p} \in \mathcal{M}_1}\cbr{ \E_{\boldsymbol{w} \sim \widehat{p}}\br{\wh{R}_S(\boldsymbol{w})} + \frac{1}{\gamma} \, \mathrm{KL}\pr{\widehat{p} \ || \ \mathcal{N}(\boldsymbol{0}, \lambda^{-1} \boldsymbol{I})} }\,,
\end{equation}
where $\mathcal{M}_1$ is the set of all sample-dependent probability densities on $\reals^d$, with sample drawn from $\mathcal{D}$, and $\mathrm{KL}$-divergence is defined between densities that are absolutely continuous with respect to some measure over $\reals^d$.
Problem~\eqref{eq:IRM} can be also motivated from perspective of the PAC-Bayesian analysis~\citep{mcallester1998some,seeger2002pac}, where~\eqref{eq:gibbs} is the density minimizing the bound on the expected risk.
Another instance of~\eqref{eq:IRM} is the well-known Maximum Entropy Discrimination framework of~\cite{jaakkola1999maximum}.
\paragraph{\emph{Sampling from~\eqref{eq:gibbs}.}}
Markov chain Monte Carlo (MCMC) algorithms can be used to sample directly from~\eqref{eq:gibbs}. Unfortunately, this is often known to be computationally inefficient~\citep{andrieu2003introduction}. On the other hand, there is a number of cases where MCMC demonstrates amenable computational properties, for instance when sampling from log-concave densities~\citep{andrieu2003introduction}.
Recent works have also showed that for a particular class of densities (such as smooth and strongly concave densities) variations of MCMC algorithms can sometimes achieve linear convergence~\citep{cheng2018underdamped},
for certain non-log-concave densities MCMC variants can achieve polynomial convergence in the dimension~\citep{cheng2018sharp}, or ever achieve faster convergence than optimization algorithms~\citep{ma2018sampling}.
Another popular line of research is a variational approximations of the Gibbs density, such as Variational Bayes~\citep{wang2018frequentist} where one resorts to the variational approximation of a target density.

\subsection{Our Contribution}
The algorithms discussed above perform randomized empirical risk minimization.
However, minimizing empirical risk does not always lead to minimization of the risk.
Hence, the quality of the solution $A(S)$ generated by the randomized algorithm $A$ given the training set $S$
is typically analyzed through the notion of \emph{excess risk} $\E_{S, A}\br{R(A(S))} - R(\bw^{\star})$, where $\bw^{\star}$ is one of the minimizers of the risk. This is decomposed into the generalization error $R(A(S)) - \wh{R}_S(A(S))$ and the term $\wh{R}_S(A(S)) - R(\bw^{\star})$.
Similarly to~\cite{raginsky2017nonconvex}, we follow instead a Gibbs-centric decomposition of the excess risk
\[
  \E_{S, A}\br{R(A(S))} - R(\bw^{\star})
  =
  \underbrace{\E_{S, A, \boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(A(S)) - R(\boldsymbol{w})}}_{\text{Computational excess risk}}
  +
  \underbrace{\E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w})} - R(\bw^{\star})}_{\text{Statistical excess risk}}\,.
\]
The first term is due solely to the dynamics of the algorithm, be it \ac{SGLD} or a sampling procedure, while the second one is a purely learning-theoretic quantity.
\cite{raginsky2017nonconvex} mainly focused on the finite-time analysis of the first term for \ac{SGLD} while showing convergence for non-convex objective functions.
Their analysis of the second term ---the statistical excess risk--- provides a bound of order (ignoring logarithmic factors)
\begin{equation}
  \label{eq:raginsky_excess}
  \frac{(\gamma + d)^2}{\lambda_{\star} m} + \frac{d}{\gamma}
\end{equation}
where $\lambda_{\star}$ is a positive spectral gap characterizing the exponential convergence rate of the Langevin diffusion to the stationary point. They conservatively bounded the reciprocal of $\lambda_{\star}$ as
\begin{equation}
  \label{eq:raginsky_spectral_gap}
  \frac{1}{\lambda_{\star}} = \mathcal{\tilde{O}} \pr{ \frac { 1 } { \gamma ( d + \gamma ) } } + \pr{1 + \frac { d } { \gamma } } e ^ { \mathcal{\tilde{O}} ( \gamma + d ) }~.
\end{equation}

This results in a statistical excess risk bound with a rather pessimistic exponential dependence on the ambient dimension $d$.
Therefore, a natural question to ask is whether the dependence on $d$ can be improved by taking into account specific properties of the learning problem,
and whether the dependence on $\lambda_{\star}$ can be avoided altogether (since the \emph{statistical} excess risk does not really depend on the convergence properties of \ac{SGLD}).
We believe that $\lambda_{\star}$ (which has exponential dependence on the dimension) can be avoided in the analysis of \cite{raginsky2017nonconvex}, although in their case this would not have improved the final result due to the contribution of the computational excess risk.

In this paper we consider the statistical excess risk, while we forego computational aspects of concrete algorithms.
In particular, we focus on the \emph{distribution-dependent} analysis of \emph{statistical excess risk} (or, simply, excess risk).
In the following we show upper bounds on the statistical excess risk that can be much smaller than~\eqref{eq:raginsky_excess} depending on the interplay between the data-generating distribution and the loss function.

The notion of excess risk considered in this paper is defined with respect to the \emph{regularized} minimizer of the risk
\begin{equation}
  \label{eq:regularized_risk}
  \bw^{\star}_{\lambda} \in \argmin_{\boldsymbol{w} \in \reals^d}\cbr{R(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2}~.
\end{equation}
Note that this is not a limitation because we can always recover the regularizer-free analysis by looking at the asymptotic behavior $\lambda \rightarrow 0$.
In the following, we assume that both risk and empirical risk are bounded and twice differentiable, and the Hessian matrix of the risk is locally-Lipschitz (in a sense precisely defined later on).
Therefore, the objective function of~\eqref{eq:regularized_risk} (as well as the one of~\eqref{eq:erm}) can have more than one minimum. However we assume that local minima are \emph{isolated}, meaning that a sufficiently small neighborhood of $\bw^{\star}_{\lambda}$ contains a unique minimum.
One compelling example is a large family of non-convex \emph{strict-saddle} \ac{ERM} problems~\citep{ge2015escaping,gonen2017fast}, such as matrix completion, tensor decomposition, PCA, ICA, and others.
Another example of such is an empirical risk of a \emph{ReLU neural network} with weight decay, or L2 regularization,~\cite[Theorem 1]{milne2018piecewise} where minima resulting in a sufficiently small empirical risk are locally strongly-convex.
Even though the theorem holds for empirical measures, we suspect that it could be extended to the population risk through the uniform convergence argument.
\paragraph{Localized excess risk.}
Before delving into the global analysis of the excess risk, we look at the \emph{local} approximation properties of the Gibbs-ERM principle, which will also be instrumental in the forthcoming global analysis.
We begin by looking at the \emph{localized} excess risk with respect to a fixed  minimizer $\bw^{\star}_{\lambda}$.
Specifically, we consider the excess risk of a parameter $\boldsymbol{w}$ generated by Gibbs-ERM within a certain neighborhood around $\bw^{\star}_{\lambda}$. This is defined as
\[
  \Delta(\bw^{\star}_{\lambda}) = \E_S\br{\E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) - R(\bw^{\star}_{\lambda}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}}} \,,
\]
where conditioning is taken on the event that $\boldsymbol{w}$ lies in the ellipsoid $\mathcal{E}^{\star}\pr{r}$ of radius $r$ centered at the minimizer $\bw^{\star}_{\lambda}$ and aligned with the curvature of the risk at that minimum.
We prove (Theorem~\ref{thm:gibbs_local_excess}) that
the local excess risk behaves as%
\footnote{Throughout this paper, we use $f \lesssim g$ to say that there exists a universal constant $C > 0$ such that $f \leq C g$ holds uniformly over all arguments.}
\begin{equation}
  \label{eq:gibbs_local_excess}
  \Delta(\bw^{\star}_{\lambda})
  \lesssim
  \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}}
  + \varepsilon(r)
  + \sqrt{\gamma \varepsilon(r)}
  + \frac{\gamma}{\sqrt{m}}
\end{equation}
where $\boldsymbol{H}^{\star}$ is the Hessian matrix $\nabla^2 R(\bw^{\star}_{\lambda})$, $\boldsymbol{H}^{\star}_{\lambda} = \boldsymbol{H}^{\star} + 2 \lambda \boldsymbol{I}$, and $\varepsilon(r)$ is a local approximation error that vanishes as $r\to 0$
(defined precisely in Section~\ref{sec:smooth_loss}).
The trace term in~\eqref{eq:gibbs_local_excess}, a distribution-dependent quantity known as the \emph{effective dimension} of minimizer $\bw^{\star}_{\lambda}$, can be also expressed as $\lambda_1 / (\lambda_1 + \lambda) + \cdots + \lambda_d / (\lambda_d + \lambda)$ where $\lambda_1, \ldots, \lambda_d$ are the eigenvalues of $\boldsymbol{H}^{\star}$. This can be viewed as a ``soft'' version of the rank of $\boldsymbol{H}^{\star}$.
Note that $\mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} \leq d$ always, and $\mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} \ll d$ whenever the spectrum of the Hessian matrix is light-tailed.
This notion of effective dimension occasionally appears in the analysis of ridge regression~\citep{audibert2011robust,neu2018iterate}.

Next, to get a sense of the strength of the bound and as a sanity check, one may look at limiting cases
with respect to parameters $\lambda$ and $\gamma$.
When $\lambda \to 0$, corresponding to the unregularized Gibbs-ERM principle, our bound becomes
\[
  \Delta(\bw^{\star}) \lesssim \frac{1}{\gamma} \, \rank(\boldsymbol{H}^{\star}) + \text{poly}(m, \gamma, r, \lambda_{\mathrm{min}}(\boldsymbol{H}^{\star}))
\]
where $\lambda_{\mathrm{min}}(\boldsymbol{H}^{\star})$ denotes the smallest non-zero eigenvalue of $\boldsymbol{H}^{\star}$.
Assuming the radius is set to $r = \gamma^{-\frac{1+p}{3}}$ for some $p > 0$, the polynomial term in the right-hand side of the above bound vanishes as $\gamma,m\to\infty$, even for singular $\boldsymbol{H}^{\star}$.
On the other hand, for $\lambda > 0$ and $\gamma,m\to\infty$
the right-hand side of~\eqref{eq:gibbs_local_excess} tends to zero, and the bound backs up the intuition that the Gibbs-ERM principle should exactly recover the \ac{ERM} solution. This observation also serves as a sanity check that the bound is reasonably tight, at least with respect to $\gamma$.

Finally, in cases when the Hessian matrix of the risk is constant, for instance in \ac{RLS} problems, $\varepsilon(r) = 0$ and our bound specializes to
\begin{equation*}
  \Delta(\bw^{\star}_{\lambda})
  \lesssim
  \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}}
  + \frac{\gamma}{\sqrt{m}}~.
\end{equation*}
When $\gamma$ is tuned optimally the above bound becomes $\Delta(\bw^{\star}_{\lambda}) \lesssim m^{-\frac{1}{4}}\sqrt{\mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}}}$.
Note that, for the square loss, the best known dependence on $m$ that can be achieved is $m^{-\frac{1}{2}}$. The worse exponent in our bound is the price we pay for the generality of our approach.
Although our results are never worse in terms of the dimension, the dependence on the sample size in our bounds is worse than in those of~\cite[(3.27)]{raginsky2017nonconvex}.
This is because we are stating bounds in terms of the distribution-dependent effective dimension. We can obtain the same rate as~\cite{raginsky2017nonconvex} by expressing the effective dimension in terms of the empirical risk.

\paragraph{Global excess risk.}
Next, we consider a \emph{global} notion of excess risk,
\[
  \Delta(\pi) = \E_S\br{\E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w})}} - \E_{I \sim \pi} \br{R(\bw^{\star}_{\lambda, I})}\,.
\]
Here, in the second term $\pi$ is a distribution over the countable set $\mathcal{I}$ of all minima (recall that minima are isolated).
In this setting, all minima, Hessian matrices, approximation errors, and ellipsoids gain a corresponding subscript $i \in \mathcal{I}$: $\bw^{\star}_{\lambda, i}$, $\boldsymbol{H}^{\star}_{\lambda,i}$, $\varepsilon_i(r)$, and $\mathcal{E}^{\star}_i(r)$.

We first focus on the finite-temperature distribution over minima of the regularized risk
\begin{equation}
  \label{eq:pi_gamma}
  \pi_{\gamma,r}(i) = \frac{\mathbb{P}_{\gamma}(\mathcal{E}^{\star}_i(r))}{\sum_{j \in \mathcal{I}} \mathbb{P}_{\gamma}(\mathcal{E}^{\star}_j(r)) }\,, \qquad i \in \mathcal{I}\,,
\end{equation}
where probabilities are taken with respect to the population Gibbs density $p_{\gamma}(\boldsymbol{w}) \propto e^{-\gamma R_{\lambda}(\boldsymbol{w})}$.
For this distribution we prove that
\begin{equation}
  \label{eq:gibbs_global_excess}
\Delta(\pi_{\gamma,r})
  \lesssim
  \frac{1}{\gamma} \, \E\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}}
  + \frac{\gamma}{\sqrt{m}}
  + \E[\varepsilon_I(r)] + \sqrt{\gamma \E[\varepsilon_I(r)]} + \mathbb{P}_{\gamma}(\sC^{\star}(r))\,,
\end{equation}
for any $r < r_0$ where the radius $r_0$ is chosen such that all ellipsoids in the set $\big\{\mathcal{E}^{\star}_i(r) \,:\, i \in \mathcal{I}\big\}$ are disjoint,
$\sC^{\star}(r)$ is the \emph{complement} of the union of the ellipsoids in this set (i.e., the volume outside of minima), and the expectation is taken with respect to $I \sim \pi_{\gamma,r}$.

Note that there is a trade-off in~\eqref{eq:gibbs_global_excess} between the first term, which is essentially a bound on the expected excess risk in the neighborhood of a minimum drawn according to $\pi_{\gamma,r}$, and the last term, which is the probability of sampling outside of the neighborhood of any minimum.
This means that we can obtain an \emph{oracle inequality} by choosing $r \in [0, r_0]$ such that it minimizes the right-hand side of~\eqref{eq:gibbs_global_excess}.

Now we focus on the probability of the complement, which behaves as
\begin{equation}
  \label{eq:intro_prob_complement}
  \mathbb{P}_{\gamma}(\sC^{\star}(r)) \leq 1 - \pr{1 - d e^{-r^2 \gamma \alpha_{d/2}}} \sum_{i \in \mathcal{I}} e^{-\frac{1}{3} \gamma \varepsilon_i(r)}\,,
\end{equation}
where $\alpha_{d/2}$ depends only on $d$.
So, as long as $r^2 \gamma$ is increasing and $\gamma \varepsilon_i(r)$ is non-increasing, the probability of generating a solution outside of the minima decreases.
For example, when $r = \gamma^{\frac{p-1}{2}}$ for $p \in (0, 1/3]$ (as discussed in Section~\ref{sec:global}) the right-hand side of~\eqref{eq:intro_prob_complement} vanishes as $\gamma \to \infty$.

\paragraph{Asymptotic pseudo excess risk.}
It is also natural to ask what happens in the zero-temperature regime $\gamma \to \infty$, when the Gibbs-ERM principle reduces to a rule for selecting empirical risk minimizers.
We can study this by observing that~\eqref{eq:gibbs_global_excess} vanishes when the radius is set to $r = \gamma^{\frac{p-1}{2}}$ ---as we previously discussed--- and $\gamma$ is set to $m^{\frac{1}{4}}$,
which is a meaningful result. Indeed, whenever $m = \infty$, then $\gamma = \infty$ and the risk of Gibbs-ERM should not differ from the risk of a minimum drawn from the limiting distribution $\pi_{\infty} = \lim_{\gamma \rightarrow \infty} \pi_{\gamma,r}$.
Interestingly, the distribution $\pi_{\infty}$ has the following analytic form (this is shown in Lemma~\ref{lem:erm_prob} assuming the tuning $r = \gamma^{\frac{p-1}{2}}$):
\begin{equation}
\label{eq:pi_infty}
\pi_{\infty}(i) = \frac{1}{\sum_{j \in \mathcal{I}^{\text{\scshape{glob}}}} \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda, i})}{\det(\boldsymbol{H}^{\star}_{\lambda, j})} }}\,,
	\qquad i \in \mathcal{I}^{\text{\scshape{glob}}}
\end{equation}
where $\mathcal{I}^{\text{\scshape{glob}}}$ is a countable set enumerating global minima of the regularized risk.
Hence, the probability of a minimum $\bw^{\star}_{\lambda, i}$ is proportional to the reciprocal of the normalized volume of the ellipsoid defined by the eigenvalues of the Hessian at that minimum. In particular, this implies that the probability of choosing a global minimum with larger volume is higher.
Note that all suboptimal minima have zero probability under $\pi_{\infty}$.
At the same time, in this asymptotic regime it is also rather clear that Gibbs-ERM generates models outside of the neighborhoods of the minima with zero probability.
These two observations show how to strike a middle ground between the nonasymptotic bound of~\eqref{eq:gibbs_global_excess} and the asymptotic distribution~\eqref{eq:pi_infty}. This is captured by the global asymptotic \emph{pseudo} excess risk
\[
  \Delta^{\infty}_r = \E_{I \sim \pi_{\infty}}\br{\E_S\br{\E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}_I(r)}} - R(\bw^{\star}_{\lambda, I})}\,, \qquad r > 0\,,
\]
which bounds the localized excess risk at finite temperature $\gamma > 0$ when minima are drawn from the global limiting distribution $\pi_{\infty}$.
For any $r \geq 0$ we have
\begin{equation}
  \label{eq:gibbs_global_pseudo_excess}
    \Delta^{\infty}_r \lesssim \frac{1}{\gamma} \, \E\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}}
    + \E \br{\varepsilon_I(r)}
    + \sqrt{\gamma \E \br{\varepsilon_I(r)}}
  + \frac{\gamma}{\sqrt{m}}~.
\end{equation}
Observe that whereas the local excess risk~\eqref{eq:gibbs_local_excess} is essentially controlled by the soft rank of the minimum, the bound~\eqref{eq:gibbs_global_pseudo_excess} implies that globally this is not necessarily the case, since low-rank minima have smaller probability under distribution $\pi_{\infty}$.

\subsection{Additional Related Work}
\input{related}

\subsection{Common Tools}
We compute the Taylor expansion of $R_{\lambda}(\boldsymbol{w})$ for $\boldsymbol{w} \in \mathcal{E}(\bw^{\star}_{\lambda}, \nabla^2 R_{\lambda}(\bw^{\star}_{\lambda}), r)$, where $\bw^{\star}_{\lambda}$ is a minimizer of the regularized risk,
  %
\begin{align}
  R_{\lambda}(\boldsymbol{w})
  &\geq
    R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{1}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 - \frac{L^{\star}(r)}{6} \, \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|^3 \nonumber\\
  &\geq
    R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{1}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 - \frac{L^{\star}(r)}{6} \pr{\frac{r}{\sqrt{\lambda_{\mathrm{min}} + \lambda}}}^3 \label{eq:taylor_lower_lmin}\\
  &=
    R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{1}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 - \frac{1}{6} \varepsilon(r)~ \label{eq:taylor_lower}
\end{align}
where $\varepsilon(r)$ is defined in~\eqref{eq:approx}, and~\eqref{eq:taylor_lower_lmin} follows because $\sqrt{\lambda_{\mathrm{min}} + \lambda} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\| \leq r$ where $\lambda_{\mathrm{min}}$ is the smallest non-zero eigenvalue of $\nabla^2 R(\bw^{\star}_{\lambda})$. In a similar way we have the upper expansion
\begin{equation}
  \label{eq:taylor_upper}
  R_{\lambda}(\boldsymbol{w})
  \leq
  R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{1}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 + \frac{1}{6} \varepsilon(r)~.
\end{equation}
We now introduce a crucial \emph{transportation lemma} which is instrumental in the following proofs.
\begin{lemma}[\protect{\citep[Lemma~4.18]{boucheron2013concentration}}]
  \label{lem:transportation}
  Let $Z$ be a real-valued integrable random variable with distribution $P$ such that
  \[
    \ln \E\br{e^{\alpha (Z - \E[Z])}} \leq \frac{\alpha^2 \sigma^2}{2} \qquad \alpha > 0
  \]
  for some $\sigma > 0$ and let $Z'$ be another random variable with distribution $Q$.
  If $Q$ is absolutely continuous with respect to $P$ and such that $\mathrm{KL}(Q \ || \ P) < \infty$, then
  $
    \E[Z'] - \E[Z] \leq \sqrt{2 \sigma^2 \mathrm{KL}\pr{Q \ || \ P}}
  $.
\end{lemma}
Next, we prove a helpful lemma about the log-ratio of Gibbs integrals.
\begin{lemma}
  \label{lem:ln_Z_Z_bound}
  Let $f_A, f_B : \mathcal{X} \to \mathbb{R}$ such that
  \[
    Z_A = \int_{\mathcal{B}} e^{-\gamma f_A(\boldsymbol{x})} \diff \boldsymbol{x}
  \]
  is finite for all $\gamma > 0, \mathcal{B} \subseteq \mathcal{X}$
  and let
  \[
    p_A(\boldsymbol{x}) = \frac{1}{Z_A} \, e^{-\gamma f_A(\boldsymbol{x})} \quad \gamma > 0, \ \boldsymbol{x} \in \mathcal{B}
  \]
  where $f_B$ is similarly defined.
  Whenever $Z_A > 0$ we have that
  \[
    - \ln\pr{\frac{Z_A}{Z_B}}
    \leq
    \gamma \int_{\mathcal{B}} p_B(\boldsymbol{x}) \pr{f_A(\boldsymbol{x}) - f_B(\boldsymbol{x})} \diff \boldsymbol{x}~.
  \]
\end{lemma}
\begin{proof}
  Observe that
  \begin{align*}
    \frac{Z_A}{Z_B} &=
                      \frac{\int_{\mathcal{B}} e^{-\gamma f_A(\boldsymbol{x})} \diff \boldsymbol{x}}{\int_{\mathcal{B}} e^{-\gamma f_B(\boldsymbol{x})} \diff \boldsymbol{x}}
                    =
                      \frac{\int_{\mathcal{B}} e^{-\gamma f_A(\boldsymbol{x})} e^{\gamma \pr{f_B(\boldsymbol{x}) - f_B(\boldsymbol{x})}} \diff \boldsymbol{x}}{\int_{\mathcal{B}} e^{-\gamma f_B(\boldsymbol{x})} \diff \boldsymbol{x}}
                    =
                      \int_{\mathcal{B}} p_B(\boldsymbol{x}) e^{\gamma \pr{f_B(\boldsymbol{x}) - f_A(\boldsymbol{x})}} \diff \boldsymbol{x}~.
  \end{align*}
Since $-\ln()$ is a convex function, by Jensen's inequality we obtain the desired result.
\end{proof}

\subsection{Statements about Probability Mass of Ellipsoids}
Before we prove our bound on the global excess risk, we introduce some necessary technical notions about the \emph{regularized gamma function}, which can be interpreted as the probability of an Euclidean ball of radius $z$ under a Gaussian density with covariance matrix $\boldsymbol{I}$.
\begin{theorem}[\protect{\citep[Regularized Gamma Function]{nist2018gamma}}]
Denote the regularized gamma function by
  \[
    P(a, z) = \frac{\Gamma(a) - \Gamma(a,z)}{\Gamma(a)}
  \]
  where $\Gamma(a,z)$ is the upper incomplete Gamma function given by
  \[
    \Gamma(a,z) = \int_z^{\infty} t^{a-1} e^{-t} \diff t~.
  \]
  Then, for all $z \geq 0$ and $a > 0$,
  \begin{equation}
    \label{eq:lb_regularized_gamma}
    \pr{1 - e^{-\alpha_a z}}^a \leq P(a, z)
  \end{equation}
  where
  \begin{equation}
    \label{eq:alpha_a}
    \alpha_a =
    \begin{cases}
      1 & 0 < a < 1\\
      \frac{1}{\Gamma(1+a)^{\frac{1}{a}}} & a > 1~.
    \end{cases}
  \end{equation}
  with equality in~\eqref{eq:lb_regularized_gamma} only when $a=1$.
\end{theorem}
\begin{prop}[Truncated Gaussian Integrals]
  \label{prop:ball_trunc_gaussian_int}
  For any $\gamma, r > 0$,
  \[
    \int_{\mathcal{B}(r)} e^{-\frac{\gamma}{2} \|\boldsymbol{u}\|^2} \diff \boldsymbol{u} = \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}
  \]
   where $\mathcal{B}(r)$ is the $d$-dimensional Euclidean ball.
  In addition, for any $d \times d$ semi-definite matrix $\boldsymbol{A}$,
  \[
    \int_{\mathcal{E}(\boldsymbol{0}, \boldsymbol{A}, r)} e^{-\frac{\gamma}{2} \|\boldsymbol{u}\|_{\boldsymbol{A}}^2} \diff \boldsymbol{u}
    =
    \frac{1}{\sqrt{\det(\boldsymbol{A})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}~.
  \]
\end{prop}
\begin{proof}
  By the integration of radial functions
  \begin{align*}
    \int_{\mathcal{B}(r)} e^{-\frac{\gamma}{2} \|\boldsymbol{u}\|^2} \diff \boldsymbol{u}
    &=
      2 \, \frac{\pi^{\frac{d}{2}}}{\Gamma\pr{\frac{d}{2}}} \int_0^r e^{-\frac{\gamma}{2} x^2} x^{d-1} \diff x \\
    &=
      \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} \, \frac{\Gamma\pr{\frac{d}{2}} - \Gamma\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}}{\Gamma\pr{\frac{d}{2}}} \\
    &=
      \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}~.
  \end{align*}
  In addition we have
  \begin{align*}
    \int_{\mathcal{E}(\boldsymbol{0}, \boldsymbol{A}, r)} e^{-\frac{\gamma}{2} \|\boldsymbol{u}\|_{\boldsymbol{A}}^2} \diff \boldsymbol{u}
    &=
      \int_{\|\boldsymbol{u}\|_{\boldsymbol{A}} \leq r} e^{-\frac{\gamma}{2} \|\boldsymbol{u}\|_{\boldsymbol{A}}^2} \diff \boldsymbol{u}\\
    &=
      \frac{1}{\sqrt{\det(\boldsymbol{A})}} \int_{\|\boldsymbol{v}\| \leq r} e^{-\frac{\gamma}{2} \|\boldsymbol{v}\|^2} \diff \boldsymbol{v}\\
    &=
      \frac{1}{\sqrt{\det(\boldsymbol{A})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}~.
  \end{align*}
  where the third step is obtained through the change of variables $\diff \boldsymbol{A}^{\frac{1}{2}} \boldsymbol{u} = \diff \boldsymbol{v}$.
\end{proof}
Recall that $\mathcal{E}^{\star}(r) \equiv \mathcal{E}(\bw^{\star}_{\lambda}, \boldsymbol{H}^{\star}_{\lambda}, r)$, where $\boldsymbol{H}^{\star}_{\lambda} = \nabla^2 R_{\lambda}(\bw^{\star}_{\lambda})$.
\begin{lemma}[Bounds on the Ellipsoid probability mass.]
  \label{lem:ellipse_prob}
  Let $\bw^{\star}_{\lambda}$ be any minimizer of $R_{\lambda}$.
  Then the following results hold for probabilities of ellipsoids under the density $e^{-\gamma R_{\lambda}(\boldsymbol{w})} / Z$,
  \begin{align*}
    \P\big(\mathcal{E}^{\star}(r)\big)
    &\leq
    \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{\gamma}{6} \varepsilon(r)} \,
    \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}
    \\
    \P\big(\mathcal{E}^{\star}(r)\big)
    &\geq
    \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) - \frac{\gamma}{6} \varepsilon(r)} \,
    \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}
    \\
    \P\big(\mathcal{E}^{\star}(r)\big) &\geq e^{-\frac{\gamma}{3} \varepsilon(r)} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}~.
  \end{align*}
\end{lemma}
\begin{proof}
By applying the lower Taylor expansion~\eqref{eq:taylor_lower} in the exponent of the Gibbs density we get
\begin{align}
  \P\big(\mathcal{E}^{\star}(r)\big) &= \frac{1}{Z} \int_{\mathcal{E}^{\star}(r)} e^{-\gamma R_{\lambda}(\boldsymbol{w})} \diff \boldsymbol{w} \nonumber\\
                         &\leq \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{\gamma}{6} \varepsilon(r)}
                           \int_{\mathcal{E}^{\star}(r)} e^{- \frac{\gamma}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2} \diff \boldsymbol{w} \nonumber\\
                         &= \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{\gamma}{6} \varepsilon(r)} \,
                           \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \int_{\mathcal{B}(r)} e^{- \frac{\gamma}{2} \|\boldsymbol{u}\|^2} \diff \boldsymbol{u} \label{eq:P_ellipse_bounds_change}\\
                         &= \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{\gamma}{6} \varepsilon(r)} \,
                           \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}
                           \label{eq:P_ellipse_bounds_gauss_int}
\end{align}
where~\eqref{eq:P_ellipse_bounds_change} is obtained via the change of variables $\boldsymbol{u} = \boldsymbol{H}^{\star \frac{1}{2}}_{\lambda} (\boldsymbol{w} - \bw^{\star}_{\lambda})$
and~\eqref{eq:P_ellipse_bounds_gauss_int} via Proposition~\ref{prop:ball_trunc_gaussian_int}.
This shows the first result.
The second result follows in a similar way exploiting the upper Taylor expansion~\eqref{eq:taylor_upper},
\begin{align}
  \P\big(\mathcal{E}^{\star}(r)\big) &\geq \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) - \frac{\gamma}{6} \varepsilon(r)}
                           \int_{\mathcal{E}^{\star}(r)} e^{- \frac{\gamma}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2} \diff \boldsymbol{w} \nonumber\\
                         &= \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) - \frac{\gamma}{6} \varepsilon(r)} \,
                           \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \int_{\mathcal{B}(r)} e^{- \frac{\gamma}{2} \|\boldsymbol{u}\|^2} \diff \boldsymbol{u} \nonumber\\
                         &= \frac{1}{Z} \, e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) - \frac{\gamma}{6} \varepsilon(r)} \,
                           \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}~.
                           \label{eq:P_ellipse_bounds_gauss_int_lower}
\end{align}
Finally, we give a lower bound on the probability of $\mathcal{E}^{\star}(r)$.
We start by upper bounding the normalization constant using the lower Taylor expansion~\eqref{eq:taylor_lower},
\begin{align*}
  Z &= \int_{\reals^d} e^{-\gamma R_{\lambda}(\boldsymbol{w})} \diff \boldsymbol{w}\\
    &\leq e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{\gamma}{6} \varepsilon(r)} \int_{\reals^d} e^{- \frac{\gamma}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2} \diff \boldsymbol{w}\\
    &\leq e^{-\gamma R_{\lambda}(\bw^{\star}_{\lambda}) + \frac{\gamma}{6} \varepsilon(r)} \, \frac{1}{\sqrt{\det(\boldsymbol{H}^{\star}_{\lambda})}} \pr{\frac{2 \pi}{\gamma}}^{\frac{d}{2}}~.
\end{align*}
Combining the above with~\eqref{eq:P_ellipse_bounds_gauss_int_lower} gives
$
  \P\big(\mathcal{E}^{\star}(r)\big) \geq e^{-\frac{\gamma}{3} \varepsilon(r)} P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}}
$
thus completing the proof.
\end{proof}
\paragraph{Lemma~\ref{lem:erm_prob} (restated)}
  %
  For all $r > 0$,
  \begin{align*}
    \pi_{\gamma,r}(i)
    \leq
    \frac{e^{\frac{\gamma}{3} \max_{k \in \mathcal{I}}\varepsilon_k(r)}}
    {\sum_{j \in \mathcal{I}} e^{\gamma \pr{ R_{\lambda}(\bw^{\star}_{\lambda, i}) - R_{\lambda}(\bw^{\star}_{\lambda, j})}}
    \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda,i})}{\det(\boldsymbol{H}^{\star}_{\lambda,j})} }
    }
    \qquad i \in \mathcal{I}~.
  \end{align*}
  %
  Moreover, assuming without loss of generality that $R_{\lambda}(\bw^{\star}_{\lambda, i}) = 0$ for all $i \in \mathcal{I}^{\text{\scshape{glob}}}$, and setting $r = \gamma^{-p}$ for $p > 0$, we have
  %
  \[
    \lim_{\gamma \rightarrow \infty}\pi_{\gamma,r}(i)
    = \begin{cases}
    \frac{1}{\sum_{j \in \mathcal{I}^{\text{\scshape{glob}}}} \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda, i})}{\det(\boldsymbol{H}^{\star}_{\lambda, j})} }} & i \in \mathcal{I}^{\text{\scshape{glob}}}
  \\
    0 & i \in \mathcal{I}^{\text{\scshape{subopt}}}~.
  \end{cases}
  \]
\begin{proof}
  Throughout this proof we consider probabilities of ellipsoids under the density $e^{-\gamma R_{\lambda}(\boldsymbol{w})} / Z$, and we abbreviate $R^{\star}_{\lambda,i}  = R_{\lambda}(\bw^{\star}_{\lambda, i})$.
  Applying Lemma~\ref{lem:ellipse_prob} with $\bw^{\star}_{\lambda} = \bw^{\star}_{\lambda, i}$ readily gives
\begin{align}
  \pi_{\gamma,r}(i)
  &=
    \frac{\P(\boldsymbol{w} \in \mathcal{E}^{\star}_i(r))}{\sum_{j \in \mathcal{I}} \P(\boldsymbol{w} \in \mathcal{E}^{\star}_j(r))} \nonumber\\
  &\leq
    \frac{e^{\frac{\gamma}{6} \varepsilon_i(r)}}
    {\sum_{j \in \mathcal{I}} e^{\gamma \pr{ R^{\star}_{\lambda,i} - R^{\star}_{\lambda,j}} - \frac{\gamma}{6} \varepsilon_j(r)}
    \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda,i})}{\det(\boldsymbol{H}^{\star}_{\lambda,j})} }
    } \nonumber\\
  &\leq
    \frac{e^{\frac{\gamma}{6} \max_{k \in \mathcal{I}}\varepsilon_k(r)}}
    {\sum_{j \in \mathcal{I}} e^{\gamma \pr{ R^{\star}_{\lambda,i} - R^{\star}_{\lambda,j}} - \frac{\gamma}{6} \max_{k \in \mathcal{I}}\varepsilon_k(r)}
    \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda,i})}{\det(\boldsymbol{H}^{\star}_{\lambda,j})} }
    } \nonumber\\
  &=
    \frac{e^{\frac{\gamma}{3} \max_{k \in \mathcal{I}}\varepsilon_k(r)}}
    {\sum_{j \in \mathcal{I}} e^{\gamma \pr{ R^{\star}_{\lambda,i} - R^{\star}_{\lambda,j}}}
    \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda,i})}{\det(\boldsymbol{H}^{\star}_{\lambda,j})} }
    }~.
  \label{eq:pi_gamma_bound_proof}
\end{align}
This proves the first statement.

Now we look at the asymptotics of $\pi_{\gamma,r}(i)$ as $\gamma \to \infty$ assuming that $r = \gamma^{-p}$ for $p > 0$.
First, observe that for any $i \in \mathcal{I}$
\begin{align*}
  \lim_{\gamma \rightarrow \infty} \varepsilon_i(\gamma^{-p})
  &=
    \lim_{\gamma \rightarrow \infty} L^{\star}_i(\gamma^{-p}) \pr{\frac{1}{\gamma^p \sqrt{\lambda_{\mathrm{min},i} + \lambda}}}^3
  = 0
\end{align*}
because $\lim_{\gamma \to \infty} L^{\star}_i(\gamma^{-p}) = \mathcal{O}(1)$ and $\lambda_{\mathrm{min},i} + \lambda > 0$.
Thus, the numerator of~\eqref{eq:pi_gamma_bound_proof} approaches $1$.
Now, we turn our attention to the denominator. First, we consider global minimizers recalling our assumption that $R^{\star}_{\lambda,i} = 0$.
Denoting $\delta_{i,j}(\gamma) = e^{\gamma \pr{ R^{\star}_{\lambda,i} - R^{\star}_{\lambda,j}}}$, we observe that for all $\gamma \geq 0$ and $i \in \mathcal{I}^{\text{\scshape{glob}}}$,
\begin{align*}
\lim_{\gamma \rightarrow \infty}  \delta_{i,j}(\gamma) =
\begin{cases}
 1 & j \in \mathcal{I}^{\text{\scshape{glob}}}
\\
 0 & j \in \mathcal{I}^{\text{\scshape{subopt}}}
\end{cases}
\end{align*}
where the second case holds because the exponent in $\delta_{i,j}(\gamma)$ is negative.
This implies
\[
  \lim_{\gamma \rightarrow \infty}\pi_{\gamma,r}(i) \leq
  \frac{1}{\sum_{j \in \mathcal{I}^{\text{\scshape{glob}}}} \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda, i})}{\det(\boldsymbol{H}^{\star}_{\lambda, j})} }}
  \qquad i \in \mathcal{I}^{\text{\scshape{glob}}}.
\]
Next, we consider the local minima, and observe that for all $\gamma \geq 0$ and $i \in \mathcal{I}^{\text{\scshape{subopt}}}$,
\begin{align*}
\lim_{\gamma \rightarrow \infty}  \delta_{i,j}(\gamma) =
\begin{cases}
 0 & \text{if $R^{\star}_{\lambda,i} \leq R^{\star}_{\lambda,j}$}
\\
 \infty & \text{otherwise.}
\end{cases}
\end{align*}
Therefore, for all $i \in \mathcal{I}^{\text{\scshape{subopt}}}$,
$
  \lim_{\gamma \rightarrow \infty}\pi_{\gamma,r}(i) = 0
$.
This proves the second statement and completes the proof.
\end{proof}
\subsection{Generalization Bound for Gibbs-ERM}
\label{sec:stability}
We start by proving a generalization bound for Gibbs-ERM.
\paragraph{Theorem~\ref{thm:gibbs_gen_error} (restated)}
Consider any loss function $f : \reals^d \times \mathcal{Z} \to \mathbb{R}$ that is $\sigma$-sub-Gaussian in the first argument with respect to the Gibbs density
\[
	\wh{p}_{S,\gamma}(\boldsymbol{w}) \propto e^{-\frac{\gamma}{m} \sum_{i=1}^m f(\boldsymbol{w}, z_i)} \qquad \gamma > 0
\]
conditioned on a measurable $A \subseteq \reals^d$. Then the generalization error of Gibbs-ERM satisfies
\[
  \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in A} } \leq \frac{4 \sigma^2 \gamma}{m}~.
\]
\begin{proof}
Consider the training examples $S$ drawn i.i.d.\ from $\mathcal{D}$ and, for $i=1,\ldots,m$, denote by ${S^{(i)}} = \cbr{z_1, \ldots, z_{i-1}, z, z_{i+1}, \ldots, z_m}$ a replace-one training data, where $z$ is independently drawn from $\mathcal{D}$.
Throughout the proof, we drop $\gamma$ from the notation for the Gibbs density $\wh{p}_{S,\gamma}$.
Introduce the conditional Gibbs densities
$
  \wh{p}_{S \mid A}(\boldsymbol{w})
$
and
$
  \wh{p}_{\Srep \mid A}(\boldsymbol{w})
$.
We denote by $\E_{\wh{p}_{S \mid A}}[\cdot]$ and $\E_{\wh{p}_{\Srep \mid A}}[\cdot]$ expectations with respect to $\wh{p}_{S \mid A}$ and $\wh{p}_{\Srep \mid A}$.
We start by rewriting the expected generalization error as
\begin{align}
  \E_S \E_{\wh{p}_{S}}\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) \mid \boldsymbol{w} \in A}
  &= \E_S\br{ \E_{\wh{p}_{S \mid A}}\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) } }\\
  &= \E_{S,z}\br{ \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z)} } - \frac{1}{m} \sum_{i=1}^m \E_{S}\br{ \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z_i)} } \label{eq:gibbs_replace_one_stab_1}\\
  &= \frac{1}{m} \sum_{i=1}^m \pr{ \E_{S,z}\br{ \E_{\wh{p}_{\Srep \mid A}}\br{f(\boldsymbol{w}, z_i)} } - \E_{S}\br{ \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z_i)} } } \tag{switch $z$ and $z_i$ in the first term}\\
  &= \frac{1}{m} \sum_{i=1}^m \pr{ \E_{S,z}\br{ \E_{\wh{p}_{\Srep \mid A}}[f(\boldsymbol{w}, z_i)] - \E_{\wh{p}_{S \mid A}}[f(\boldsymbol{w}, z_i)] } }~. \label{eq:gibbs_replace_one_stab}
\end{align}
Now we bound~\eqref{eq:gibbs_replace_one_stab} showing the average replace-one stability of Gibbs distribution.
We use the transportation Lemma~\ref{lem:transportation} with $Q = \wh{p}_{S \mid A}$ and $P = \wh{p}_{\Srep \mid A}$ we get that
\begin{equation}
  \label{eq:stab_bound_sqrt_sigma_KL}
  \E_{\wh{p}_{\Srep \mid A}}[f(\boldsymbol{w}, z_i)] - \E_{\wh{p}_{S \mid A}}[f(\boldsymbol{w}, z_i)] \leq \sqrt{2 \sigma^2 \mathrm{KL}\pr{\wh{p}_{\Srep \mid A} ~||~ \wh{p}_{S \mid A}}}~.
\end{equation}
Next, we focus on $\mathrm{KL}$-divergence,
\begin{align}
  \mathrm{KL}\pr{\wh{p}_{\Srep \mid A} ~||~ \wh{p}_{S \mid A}}
  &=
    \gamma \E_{\wh{p}_{\Srep \mid A}}\br{\wh{R}_S(\boldsymbol{w}) - \wh{R}_{{S^{(i)}}}(\boldsymbol{w})} - \ln\pr{\frac{Z_{{S^{(i)}}}}{Z_S} \, \frac{\P_{\wh{p}_{\Srep}}(A)}{\P_{\wh{p}_{S}}(A)} }\\
  &=
    \gamma \E_{\wh{p}_{\Srep \mid A}}\br{\wh{R}_S(\boldsymbol{w}) - \wh{R}_{{S^{(i)}}}(\boldsymbol{w})} - \ln\pr{\frac{\int_A e^{-\gamma \wh{R}_{{S^{(i)}}}(\boldsymbol{w})} \diff \boldsymbol{w}}{\int_A e^{-\gamma \wh{R}_S(\boldsymbol{w})} \diff \boldsymbol{w}} }\\
  &\leq
    \gamma \E_{\wh{p}_{\Srep \mid A}}\br{\wh{R}_S(\boldsymbol{w}) - \wh{R}_{{S^{(i)}}}(\boldsymbol{w})}
    +
    \gamma \E_{\wh{p}_{S \mid A}}\br{\wh{R}_{{S^{(i)}}}(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w})} \tag{by Lemma~\ref{lem:ln_Z_Z_bound}}\\
  &=
    \frac{\gamma}{m} \E_{\wh{p}_{\Srep \mid A}}\br{ f(\boldsymbol{w}, z_i) - f(\boldsymbol{w}, z) } +
    \frac{\gamma}{m} \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z) - f(\boldsymbol{w}, z_i)}\\
  &=
    \frac{\gamma}{m} \pr{ \E_{\wh{p}_{\Srep \mid A}}\br{f(\boldsymbol{w}, z_i)} - \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z_i)} }\\
  &+\frac{\gamma}{m} \pr{ \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z)} - \E_{\wh{p}_{\Srep \mid A}}\br{f(\boldsymbol{w}, z)} } ~. \label{eq:gibbs_stability_bound_on_kl}
\end{align}
By taking expectation with respect to $S$ and $z$ on both sides, we get that the first term in~\eqref{eq:gibbs_stability_bound_on_kl} can be expressed as
\begin{equation}
  \label{eq:gibbs_stability_expectation_of_kl}
  \E_{S,z}\br{ \E_{\wh{p}_{\Srep \mid A}}\br{f(\boldsymbol{w}, z_i)} - \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z_i)} } = \E_{S,z}\br{\E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z)} - \E_{\wh{p}_{\Srep \mid A}}\br{f(\boldsymbol{w}, z)}}
\end{equation}
where we could switch $z_i$ and $z$ on the right-hand side because their are both independently drawn from $\mathcal{D}$.
Thus, the expectation of~\eqref{eq:stab_bound_sqrt_sigma_KL} with respect to $S$ and $z$ is upper-bounded as
\begin{align}
  \E_{S,z}\br{\E_{\wh{p}_{\Srep \mid A}}[f(\boldsymbol{w}, z_i)] - \E_{\wh{p}_{S \mid A}}[f(\boldsymbol{w}, z_i)]}
  &\leq
    \E_{S,z}\sqrt{2 \sigma^2 \mathrm{KL}\pr{\wh{p}_{\Srep \mid A} ~||~ \wh{p}_{S \mid A}}}\\
  &\leq
    \sqrt{2 \sigma^2 \E_{S,z}\br{\mathrm{KL}\pr{\wh{p}_{\Srep \mid A} ~||~ \wh{p}_{S \mid A}}}} \tag{Jensen's inequality}\\
  &\leq
    2 \sqrt{\frac{\sigma^2 \gamma}{m}
    \E_{S,z}\br{\E_{\wh{p}_{\Srep \mid A}}\br{f(\boldsymbol{w}, z_i)} - \E_{\wh{p}_{S \mid A}}\br{f(\boldsymbol{w}, z_i)}}  }~.
\end{align}
Solving the above with respect to the term on the left-hand side we get that for any $i=1,\ldots,m$,
\begin{align}
  \E_{S,z}\br{\E_{\wh{p}_{\Srep \mid A}}[f(\boldsymbol{w}, z_i)] - \E_{\wh{p}_{S \mid A}}[f(\boldsymbol{w}, z_i)]} \leq \frac{4 \sigma^2 \gamma}{m}~.
\end{align}
Substituting the above into~\eqref{eq:gibbs_replace_one_stab_1} gives the desired generalization bound.
\end{proof}

\subsection{Global Excess Risk Bounds}
We first show a nonasymptotic (i.e., finite $\gamma$) global excess risk bound.
\paragraph{Theorem~\ref{thm:global_excess_risk} (restated)}
  Assume the same as in Lemma~\ref{lem:truncated_EER_to_ERM}.
  Then for any $r \in [0, r_0]$ the global excess risk satisfies
  \begin{equation*}
  \Delta(\pi_{\gamma,r})
  \lesssim
  \frac{1}{\gamma} \, \E\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}}
  + \frac{\gamma}{\sqrt{m}}
  +  \E[\varepsilon_I(r)] + \sqrt{\gamma \E[\varepsilon_I(r)]} + \mathbb{P}_{\gamma}(\sC^{\star}(r))
  \end{equation*}
  where the expectation is taken with respect to $I \sim \pi_{\gamma,r}$
  and the probability of the complement of the minima is bounded as
  \begin{align}
    \mathbb{P}_{\gamma}(\sC^{\star}(r))
    &\leq
      1 - \pr{1 - d e^{-r^2 \gamma \alpha_{d/2}}} \sum_{i \in \mathcal{I}} e^{-\frac{1}{3} \gamma \varepsilon_i(r)}
  \end{align}
  with $\alpha_{d/2}$ defined in~\eqref{eq:alpha_a}.
\begin{proof}
Denote the sample-dependent global excess risk by
\begin{align*}
  \Delta_S(\pi_{\gamma,r}) = \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{ R(\boldsymbol{w}) } - \E_{I \sim \pi_{\gamma,r}}\br{ R(\bw^{\star}_{\lambda, I}) }
\end{align*}
and let the probabilities $\P\big(\mathcal{E}^{\star}_i(r)\big)$ and $\P\big(\sC^{\star}(r)\big)$ be defined with respect to the population Gibbs distribution
$
  p_{\gamma}(\boldsymbol{w}) \propto e^{-\gamma R_{\lambda}(\boldsymbol{w})}
$ with $\gamma > 0$.

We first focus on the first term on the right-hand side of $\Delta_S(\pi_{\gamma,r})$. By the law of total expectation, for any $r \in [0, r_0]$,
\begin{align}
  \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{ R(\boldsymbol{w}) } &= \sum_{i \in \mathcal{I}} \P\big(\mathcal{E}^{\star}_i(r)\big) \E\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}_i(r)}
                                   + \P\big(\sC^{\star}(r)\big) \E\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \sC^{\star}(r)} \nonumber\\
                               &\leq \sum_{i \in \mathcal{I}} \frac{\P\big(\mathcal{E}^{\star}_i(r)\big)}{\sum_{j \in \mathcal{I}} \P\big(\mathcal{E}^{\star}_j(r)\big)} \, \E\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}_i(r)} \tag{ellipsoids are disjoint by Assumption~\ref{asm:global}}\\
                                 &+ \P\big(\sC^{\star}(r)\big) M \tag{risk is bounded}\\
                               &= \sum_{i \in \mathcal{I}} \pi_{\gamma,r}(I=i) \E\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}_i(r)} \tag{by definition of $\pi_{\gamma,r}$} \nonumber\\
                               &+ \P\big(\sC^{\star}(r)\big) M~. \label{eq:half_bound_on_global_excess_risk}
\end{align}
An upper bound on $\E\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}_i(r)}$ is given by Theorem~\ref{thm:gibbs_local_excess}, thus all that is left to show is that the probability of the complement is small. Since the ellipsoids are disjoint
\[
  \P\big(\sC^{\star}(r)\big) = 1 - \sum_{i \in \mathcal{I}} \P\big(\mathcal{E}^{\star}_i(r)\big)~.
\]
To upper bound $\P\big(\sC^{\star}(r)\big)$ we need a lower bound on $\P\big(\mathcal{E}^{\star}(r)\big)$. This is provided by the last inequality in Lemma~\ref{lem:ellipse_prob}, that is,
\begin{align}
\nonumber
  \sum_{i \in \mathcal{I}} \P\big(\mathcal{E}^{\star}_i(r)\big)
  &\geq
    P\pr{\frac{d}{2}, \frac{r^2 \gamma}{2}} \sum_{i \in \mathcal{I}} e^{-\frac{\gamma \varepsilon_i(r)}{3}}\\
  &\geq
    \pr{1 - e^{-r^2 \gamma \alpha_{d/2}}}^{\frac{d}{2}} \sum_{i \in \mathcal{I}} e^{-\frac{\gamma \varepsilon_i(r)}{3}} \label{eq:lower_bound_on_sum_P_Estar_2}\\
  &\geq
  \nonumber
    \pr{1 - d e^{-r^2 \gamma \alpha_{d/2}}} \sum_{i \in \mathcal{I}} e^{-\frac{\gamma \varepsilon_i(r)}{3}}
\end{align}
where~\eqref{eq:lower_bound_on_sum_P_Estar_2} is derived from the lower bound on the regularized Gamma function~\eqref{eq:lb_regularized_gamma},
and the last inequality is obtained from the Bernoulli inequality
\[
  (1 + x)^{\frac{d}{2}} \geq (1 + x)^d \geq 1 + d x \qquad d \in \mathbb{N}, \ x \geq -1~.
\]
Thus,
\begin{align}
  \P\big(\sC^{\star}(r)\big) \leq 1 - \pr{1 - d e^{-r^2 \gamma \alpha_{d/2}}} \sum_{i \in \mathcal{I}} e^{-\frac{1}{3} \gamma \varepsilon_i(r)}~.
\end{align}
Taking expectation with respect to $S$, and combining Theorem~\ref{thm:gibbs_local_excess} with~\eqref{eq:half_bound_on_global_excess_risk} and Jensen's inequality, we obtain
\begin{align*}
  \Delta(\pi_{\gamma,r})
  &\leq
    \E_{I \sim \pi_{\gamma,r}}\br{ \E_S\Big[\E\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}_i(r)} \Big] - R(\bw^{\star}_{\lambda, I}) }
    + M\, \P\big(\sC^{\star}(r)\big) \\
  &\leq
    \frac{1}{\gamma} \, \E_{I \sim \pi_{\gamma,r}}\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}} + \frac{1}{6}\E_{I \sim \pi_{\gamma,r}}\br{\varepsilon_I(r)}
    + \frac{M}{2} \sqrt{\frac{\gamma}{3} \E_{I \sim \pi_{\gamma,r}}\br{\varepsilon_I(r)} + \frac{M^2 \gamma^2}{2 m}}
    + \frac{M^2 \gamma}{2 m} \\
    &+ M\, \P\big(\sC^{\star}(r)\big)~.
\end{align*}
The proof is concluded by stating the above with respect to radius $r \in [0, r_0]$ ---recall that the radius cannot exceed $r_0$, the largest radius ensuring that ellipsoids remain disjoint.
\end{proof}
\paragraph{Corollary~\ref{cor:global_excess_risk_asymptotic} (restated)}
  Assume the same as in Lemma~\ref{lem:truncated_EER_to_ERM}.
  Then, for any $r > 0$, the global asymptotic pseudo-excess risk satisfies
  \[
    \Delta^{\infty}_r \lesssim \frac{1}{\gamma} \, \E\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}}
    + \E \br{\varepsilon_I(r)}
    + \sqrt{\gamma \E \br{\varepsilon_I(r)} + \frac{\gamma^2}{m}}
  + \frac{\gamma}{m}
\]
where $I$ is distributed according to
\[
\pi_{\infty}(i) =
  \frac{1}{\sum_{j \in \mathcal{I}^{\text{\scshape{glob}}}} \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda, i})}{\det(\boldsymbol{H}^{\star}_{\lambda, j})} }}~.
\]
\begin{proof}
  Recall that the global asymptotic pseudo-excess risk is defined as
  \begin{align*}
    \Delta^{\infty}_r = \E_{I \sim \pi_{\infty}}\br{\E_S\br{\E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}_I(r)}} - R(\bw^{\star}_{\lambda, I})}~.
  \end{align*}
  %
  Distribution $\pi_{\infty}$ is given by Lemma~\ref{lem:erm_prob}, while the local excess risk centered at $\bw^{\star}_{\lambda, I}$ is bounded by Theorem~\ref{thm:gibbs_local_excess}.
  This immediately yields the statement.
\end{proof}
\subsection{Localized Excess Risk Bounds}
\label{sec:proofs_smooth}
First, we prove a key lemma about the conditional expectation of quadratic forms.
\begin{lemma}
  \label{lem:conditional_trace_lemma}
  Suppose that $\boldsymbol{x} \sim \mathcal{N}(\boldsymbol{0}, \boldsymbol{M})$.
  Then for the ellipsoid
  \[
    \mathcal{E}(r) \equiv \cbr{\boldsymbol{x} \in \mathbb{R}^d ~:~ \|\boldsymbol{x}\|_{\boldsymbol{M}^{-1}} \leq r} \qquad r > 0
  \]
  and for any \ac{PSD} $d \times d$ matrix $\boldsymbol{A}$
  we have that
  \begin{align*}
    \E\br{\boldsymbol{x}^{\top} \boldsymbol{A} \boldsymbol{x} \,\Big|\, \boldsymbol{x} \in \mathcal{E}(r)} &= \frac{F_{d+2}(r^2)}{F_{d}(r^2)} \, \mathrm{tr}\pr{\boldsymbol{A} \boldsymbol{M}}
                                                 \leq \mathrm{tr}\pr{\boldsymbol{A} \boldsymbol{M}}~.
  \end{align*}
  where $F_k$ is the CDF of a $\mathcal{X}^2$-distribution with $k$ degrees of freedom.

  Moreover the above implies that
  \begin{equation}
    \lim_{r \rightarrow 0} \E\br{\boldsymbol{x}^{\top} \boldsymbol{A} \boldsymbol{x} \,\Big|\, \boldsymbol{x} \in \mathcal{E}(r)} = 0~.
  \end{equation}
  %
\end{lemma}
\begin{proof}
  Observe that
  %
  \begin{align}
    \E\br{\boldsymbol{x}^{\top} \boldsymbol{A} \boldsymbol{x} \,\Big|\, \boldsymbol{x} \in \mathcal{E}(r)}

    &= \E\br{\mathrm{tr}\pr{\boldsymbol{A} \boldsymbol{x} \boldsymbol{x}^{\top}} \,\Big|\, \boldsymbol{x} \in \mathcal{E}(r)}\\
    &= \mathrm{tr}\pr{\boldsymbol{A} \E\br{\boldsymbol{x} \boldsymbol{x}^{\top} \,\Big|\, \boldsymbol{x} \in \mathcal{E}(r)}} \tag{by linearity of trace}\\
    &= \mathrm{tr}\pr{\boldsymbol{A} \boldsymbol{\tilde{M}}}
  \end{align}
  %
  where $\boldsymbol{\tilde{M}}$ is the covariance matrix of the Gaussian density $\mathcal{N}(\boldsymbol{0}, \boldsymbol{M})$ conditioned on $\mathcal{E}(r)$.
Next, we apply a result about moments of multivariate Gaussian densities under elliptical truncation~\cite[p. 941]{tallis1963elliptical} to get that
  \begin{align}
    \boldsymbol{\tilde{M}} &= \frac{F_{d+2}(r^2) - F_{d+2}(0)}{F_{d}(r^2) - F_{d}(0)} \, \boldsymbol{M}
           = \frac{F_{d+2}(r^2)}{F_{d}(r^2)} \, \boldsymbol{M} \label{eq:ratio_of_chi_square_CDF}
  \end{align}
  %
  where $F_d$ is a CDF of a $\mathcal{X}^2$ distribution.
  This proves the first identity.

  The inequality is proven by expanding $\boldsymbol{\tilde{M}}$ further in terms of the Gamma function $\Gamma(\cdot)$ and the incomplete Gamma function $\gamma(\cdot, \cdot)$:
  %
  \begin{align*}
           \boldsymbol{\tilde{M}} &= \frac{\Gamma\pr{\frac{d}{2}}}{\Gamma\pr{1 + \frac{d}{2}}} \, \frac{\gamma\pr{1 + \frac{d}{2}, \frac{r^2}{2}}}{\gamma\pr{\frac{d}{2}, \frac{r^2}{2}}} \, \boldsymbol{M}
           = \frac{2}{d} \, \frac{\gamma\pr{1 + \frac{d}{2}, \frac{r^2}{2}}}{\gamma\pr{\frac{d}{2}, \frac{r^2}{2}}} \, \boldsymbol{M}
	\preceq \boldsymbol{M}~.
  \end{align*}
  Finally, we look at the limit of the ratio in the right-hand side of~\eqref{eq:ratio_of_chi_square_CDF} as $r \rightarrow 0$.
  By L'H\^opital's rule,
 \begin{align*}
    \lim_{r \rightarrow 0} \frac{F_{d+2}(r^2)}{F_{d}(r^2)}
    &=
      \lim_{r \rightarrow 0} \frac{\mathcal{X}^2_{d+2}(r^2)}{\mathcal{X}^2_{d}(r^2)}\\
    &=
      \lim_{r \rightarrow 0} \frac{r^d e^{-\frac{r^2}{2}}}{2^{1 + \frac{d}{2}} \Gamma\pr{1 + \frac{d}{2}}}
      \,
      \frac{2^{\frac{d}{2}} \Gamma\pr{\frac{d}{2}}}{r^{d - 2} e^{-\frac{r^2}{2}}}\\
    &=
      \lim_{r \rightarrow 0} \frac{r^d e^{-\frac{r^2}{2}}}{2^{1 + \frac{d}{2}} \Gamma\pr{1 + \frac{d}{2}}}
      \,
      \frac{2^{\frac{d}{2}} \Gamma\pr{\frac{d}{2}}}{r^{d - 2} e^{-\frac{r^2}{2}}}\\
    &=
      \lim_{r \rightarrow 0} \frac{r^2}{d}
    = 0
  \end{align*}
concluding the proof.
\end{proof}
Recall that $\mathcal{E}^{\star}\pr{r} \equiv \mathcal{E}(\bw^{\star}_{\lambda}, \boldsymbol{H}^{\star}_{\lambda}, r)$ is the ellipsoid of radius $r$ centered at $\bw^{\star}_{\lambda}$.
\paragraph{Lemma~\ref{lem:truncated_EER_to_ERM} (restated)}
For any minimizer $\bw^{\star}_{\lambda}$ of the regularized risk we have
\begin{align*}
  \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{\wh{R}_S(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} } - R(\bw^{\star}_{\lambda})
  \leq
    \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} + \frac{\varepsilon(r)}{6}
  + \frac{M}{2} \sqrt{\frac{\gamma \varepsilon(r)}{3} + \frac{M^2 \gamma^2}{2 m}}~.
\end{align*}
\begin{proof}
We abbreviate the regularized empirical risk by
$
  \wh{R}_{S,\lambda}(\boldsymbol{w}) = \wh{R}_S(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2
$
and recall that the regularized risk is denoted by
$
  R_{\lambda}(\boldsymbol{w}) = R(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2
$.
Throughout the proof, we drop $\gamma$ from the notation for the Gibbs densities $\wh{p}_{S,\gamma}$.
Let $\wh{p}_{S \mid \sEstar}$ be the Gibbs density~\eqref{eq:gibbs} conditioned on the ellipsoid $\mathcal{E}^{\star}\pr{r}$.
Similarly, let $q_{\mid \sEstar}$ be the the Gaussian density
\[
  q(\boldsymbol{w}) = \frac{1}{Z_q} \, e^{- \frac{\gamma}{2} \|\boldsymbol{w} - \widehat{\boldsymbol{w}}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2} \qquad \boldsymbol{w} \in \reals^d
\]
conditioned on $\mathcal{E}^{\star}\pr{r}$.

We begin by observing that $\wh{R}_S$ is trivially $M^2/8$-sub-Gaussian since the loss function is bounded by $M$. Hence, by the transportation Lemma~\ref{lem:transportation},
\begin{align}
\nonumber
  \E_S&\br{ \E_{\wh{p}_{S}}\br{\wh{R}_S(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} - \E_{q}\br{\wh{R}_S(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} }\\
  &= \E_S\br{ \E_{\wh{p}_{S \mid \sEstar}}\br{\wh{R}_S(\boldsymbol{w})} - \E_{q_{\mid \sEstar}}\br{\wh{R}_S(\boldsymbol{w})} } \label{eq:almost_erm_smooth:1}\\
  &\leq \frac{M}{2} \E_S\br{\sqrt{\mathrm{KL}\pr{\wh{p}_{S \mid \sEstar} \ || \ q_{\mid \sEstar}}}}
  \leq \frac{M}{2} \sqrt{\E_S\br{\mathrm{KL}\pr{\wh{p}_{S \mid \sEstar} \ || \ q_{\mid \sEstar}}}} \label{eq:almost_erm_smooth:transportation_KL}
\end{align}
where the last inequality is obtained by Jensen's inequality.
The KL term can be written as follows
\begin{align}
\nonumber
  \E_S\br{\mathrm{KL}\pr{\wh{p}_{S \mid \sEstar} \ || \ q_{\mid \sEstar}}} = &\E_S\E_{\wh{p}_{S \mid \sEstar}}\br{ \ln\pr{\frac{\wh{p}_{S \mid \sEstar}(\boldsymbol{w})}{q_{\mid \sEstar}(\boldsymbol{w})}} }\\
\nonumber
  = &\E_S\E_{\wh{p}_{S}}\br{ \ln\pr{\wh{p}_{S \mid \sEstar}(\boldsymbol{w})} } - \E_S\E_{\wh{p}_{S}}\br{ \ln\pr{q_{\mid \sEstar}(\boldsymbol{w})} }\\
\nonumber
  = &- \gamma \E_S \E_{\wh{p}_{S}}\br{ \wh{R}_{S,\lambda}(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} } - \E_S\br{\ln(\P_{\wh{p}_{S}}(\mathcal{E}^{\star}\pr{r}) \, Z_{\wh{p}_{S}})} \\
\label{eq:almost_erm_smooth:Rhat_lower}
  &+ \frac{\gamma}{2} \E_S \E_{\wh{p}_{S}}\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} } + \E_S\br{\ln(\P_{q}(\mathcal{E}^{\star}\pr{r}) \, Z_{q})}~.
\end{align}
Now we relate the regularized empirical risk~\eqref{eq:almost_erm_smooth:Rhat_lower} to the regularized risk.
By applying Theorem~\ref{thm:gibbs_gen_error} with $A \equiv \mathcal{E}^{\star}(r)$ we get
\begin{align*}
  \E_S\E_{\wh{p}_{S}}\br{R_{\lambda}(\boldsymbol{w}) - \wh{R}_{S,\lambda}(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}}
  &= \E_S\E_{\wh{p}_{S}}\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}}
  \leq \frac{M^2 \gamma}{2 m}~.
\end{align*}
Using this result we can write
\begin{align}
\nonumber
  \E_S\br{\mathrm{KL}\pr{\wh{p}_{S \mid \sEstar} \ || \ q_{\mid \sEstar}}} \leq &- \gamma \E_S\E_{\wh{p}_{S}}\br{R_{\lambda}(\boldsymbol{w}) \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} + \frac{M^2 \gamma^2}{2 m}\\
\nonumber
                                         &+ \frac{\gamma}{2} \E_S \E_{\wh{p}_{S}}\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 \,\big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }\\
\nonumber
                                         &- \E_S\br{\ln\pr{\frac{\P_{\wh{p}_{S}}(\mathcal{E}^{\star}\pr{r}) \, Z_{\wh{p}_{S}}}{\P_{q}(\mathcal{E}^{\star}\pr{r}) \, Z_{q}}}}\\
  \leq &- \gamma R^{\star}_{\lambda} + \frac{\gamma \varepsilon(r)}{6}
         + \frac{M^2 \gamma^2}{2 m} \label{eq:almost_erm_smooth:Rl_taylor_lower}\\
                                         &- \E_S\br{\ln\pr{\frac{\P_{\wh{p}_{S}}(\mathcal{E}^{\star}\pr{r}) \, Z_{\wh{p}_{S}}}{\P_{q}(\mathcal{E}^{\star}\pr{r}) \, Z_{q}}}} \label{eq:almost_erm_smooth:expected_log_ratio}
\end{align}
where~\eqref{eq:almost_erm_smooth:Rl_taylor_lower} is obtained by applying the lower Taylor expansion~\eqref{eq:taylor_lower} to $\boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}$ .
Now we bound the expected log-ratio term in~\eqref{eq:almost_erm_smooth:expected_log_ratio} as
\begin{align}
  - \E_S\br{\ln\pr{\frac{\P_{\wh{p}_{S}}(\mathcal{E}^{\star}\pr{r}) Z_{\wh{p}_{S}}}{\P_{q}(\mathcal{E}^{\star}\pr{r}) Z_{q}}}}
  &=
    - \E_S\br{\ln\pr{\frac{\int_{\mathcal{E}^{\star}\pr{r}} e^{-\gamma \wh{R}_{S,\lambda}(\boldsymbol{w})} }{\int_{\mathcal{E}^{\star}\pr{r}} e^{-\frac{\gamma}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2} }}}\\
  &\leq
    \gamma \E_S \E_q\br{\wh{R}_{S,\lambda}(\boldsymbol{w}) - \frac{1}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} \tag{by Lemma~\ref{lem:ln_Z_Z_bound}}\\
  &=
    \gamma \E_q\br{R_{\lambda}(\boldsymbol{w}) - \frac{1}{2} \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}_{\lambda}}^2 \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} \tag{Since $\E_S[\wh{R}_{S,\lambda}(\boldsymbol{w})] = R_{\lambda}(\boldsymbol{w})$}\\
  &\leq
    \gamma R^{\star}_{\lambda} + \frac{\gamma \varepsilon(r)}{6}~.
\end{align}
where the last inequality is derived from the upper Taylor expansion~\eqref{eq:taylor_upper}.
Substituting the above into~\eqref{eq:almost_erm_smooth:expected_log_ratio} gives
\begin{equation}
\label{eq:bound_KL_term}
  \E_S\br{\mathrm{KL}\pr{\wh{p}_{S \mid \sEstar} \ || \ q_{\mid \sEstar}}} \leq \frac{\gamma \varepsilon(r)}{3} + \frac{M^2 \gamma^2}{2 m}~.
\end{equation}
Now we go back to~\eqref{eq:almost_erm_smooth:1} and, using the upper Taylor expansion~\eqref{eq:taylor_upper}, we get
\begin{align}
\nonumber
  \E_S \E_{q_{\mid \sEstar}}\br{\wh{R}_S(\boldsymbol{w})} &= \E_{q_{\mid \sEstar}}\br{R(\boldsymbol{w})} \tag{since $\E_S[\wh{R}_S(\boldsymbol{w})] = R(\boldsymbol{w})$}\\
\nonumber
  &\leq R(\bw^{\star}_{\lambda})\\
  &+ \nabla R(\bw^{\star}_{\lambda})^{\top} \pr{ \E_q \br{\boldsymbol{w} - \bw^{\star}_{\lambda} \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} } \label{eq:almost_erm_smooth:truncated_first_moment}\\
\nonumber
  &+ \E_q\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}}^2 \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }
  + \frac{1}{6} L^{\star}(r) \E_q\br{\|\boldsymbol{w} - \bw^{\star}_{\lambda}\|^3 \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }\\
\nonumber
  &\leq R(\bw^{\star}_{\lambda})\\
\label{eq:almost_erm_smooth:truncated_second_moment}
  &+ \E_q\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}}^2 \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }
  + \frac{\varepsilon(r)}{6}~.
\end{align}
where~\eqref{eq:almost_erm_smooth:truncated_first_moment} vanishes since the first moment of elliptically-truncated Gaussian is zero~\citep{tallis1963elliptical}.
Finally, we bound the first term in~\eqref{eq:almost_erm_smooth:truncated_second_moment} by invoking Lemma~\ref{lem:conditional_trace_lemma}.
By taking $\boldsymbol{M} = \gamma \boldsymbol{H}^{\star}_{\lambda}$, $\boldsymbol{A} = \boldsymbol{H}^{\star}$, and $\boldsymbol{x} = \boldsymbol{w} - \bw^{\star}_{\lambda}$, and using Lemma~\ref{lem:conditional_trace_lemma} we get
\begin{align*}
  \mathcal{E}^{\star}\pr{r} &\equiv \cbr{\boldsymbol{w} \in \mathbb{R}^d \ : \ \sqrt{\gamma (\boldsymbol{w} - \bw^{\star}_{\lambda})^{\top} \boldsymbol{H}^{\star}_{\lambda} (\boldsymbol{w} - \bw^{\star}_{\lambda})} \leq r }
\end{align*}
and
\begin{align*}
  \E_q\br{ \|\boldsymbol{w} - \bw^{\star}_{\lambda}\|_{\boldsymbol{H}^{\star}}^2 \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r} }
  &\leq
    \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}}~.
\end{align*}
Now, combining these results with the bound on KL-divergence~\eqref{eq:bound_KL_term}, and
substituting into~\eqref{eq:almost_erm_smooth:transportation_KL}, gives the stated result.
\end{proof}
\paragraph{Theorem~\ref{thm:gibbs_local_excess} (restated)}
Assume the same as in Lemma~\ref{lem:truncated_EER_to_ERM}.
Then,
\begin{equation*}
  \Delta(\bw^{\star}_{\lambda})
  \leq
  \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} + \frac{\varepsilon(r)}{6}
  + \frac{M}{2} \sqrt{\frac{\gamma \varepsilon(r)}{3} + \frac{M^2 \gamma^2}{2 m}}
  + \frac{M^2 \gamma}{2 m}~.
\end{equation*}
\begin{proof}
  %
  From the definition of local generalization error,
  %
  \begin{align*}
    \Delta(\bw^{\star}_{\lambda})
    &=
    \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} } - R(\bw^{\star}_{\lambda})\\
    &= \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{R(\boldsymbol{w}) - \wh{R}_S(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} }\\
    &+ \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{\wh{R}_S(\boldsymbol{w}) \mid \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} } - R(\bw^{\star}_{\lambda})\\
    &\leq \frac{M^2 \gamma}{2 m}
    +\frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} + \frac{\varepsilon(r)}{6}
     + \frac{M}{2} \sqrt{\frac{\gamma \varepsilon(r)}{3} + \frac{M^2 \gamma^2}{2 m}}
  \end{align*}
  %
  where the last inequality is derived from Theorem~\ref{thm:gibbs_gen_error} and Lemma~\ref{lem:truncated_EER_to_ERM}.
\end{proof}
\section{Proofs}
\input{proofs_common.tex}
\input{proofs_gibbs_stability.tex}
\input{proofs_local.tex}
\input{proofs_erm_gibbs.tex}
\input{proofs_global.tex}

\section{Main results}
\label{sec:smooth_loss}
\subsection{Local analysis}
We first turn our attention to the local analysis considering a fixed minimizer\footnote{We will drop subscript indexing of minima in this section.}
\begin{equation}
  \bw^{\star}_{\lambda} \in \argmin\cbr{R(\boldsymbol{w}) + \lambda \|\boldsymbol{w}\|^2}~.
\end{equation}
Specifically, we prove that the risk of Gibbs-ERM in a neighborhood of $\bw^{\star}_{\lambda}$ is controlled by the \emph{local} effective dimension
$
  \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}}
$,
defined in terms of the Hessian $\boldsymbol{H}^{\star} = \nabla^2 R(\bw^{\star}_{\lambda})$ of the risk of the minimizer, where $\boldsymbol{H}^{\star}_{\lambda} = \boldsymbol{H}^{\star} + 2 \lambda \boldsymbol{I}$.
We require that Hessians do not change ``too quickly'' by assuming that Hessian of the risk is Lipschitz in an ellipsoid $\mathcal{E}^{\star}(r) = \mathcal{E}(\bw^{\star}_{\lambda}, \boldsymbol{H}^{\star}_{\lambda}, r)$ centered at the minimizer and aligned with the local curvature. Formally the \emph{local Lipschitzness} of the Hessian is defined as follows.
\begin{definition}[Locally-Lipschitz Hessian]
The Hessian $\nabla^2 R$ is locally Lipschitz around a minimizer $\bw^{\star}_{\lambda}$ if there exists a function $L^{\star} : \mathbb{R}_+ \to \mathbb{R}_+$ such that
\begin{equation}
  \label{eq:lipschitz_hessian}
  \|\nabla^2 R(\bw^{\star}_{\lambda}) - \nabla^2 R(\boldsymbol{w})\|_2 \leq L^{\star}(r) \|\bw^{\star}_{\lambda} - \boldsymbol{w}\| \qquad \text{for all} \quad \boldsymbol{w} \in \mathcal{E}^{\star}(r)~.
\end{equation}
\end{definition}
Note that local Lipschitzness of the risk Hessian implies local Lipschitzness of the regularized risk Hessian for the same function $L^{\star}$.

Local Lipschitzness of Hessians plays an important role in bounding the gap between the Gibbs density and the Gaussian density, as discussed in Section~\ref{sec:analysis_idea}.
In particular, the approximation error introduced by taking a Taylor expansion of the regularized risk up to the third term is
\begin{equation}
  \label{eq:approx}
  \varepsilon(r) = L^{\star}\pr{r} \pr{\frac{r}{\sqrt{\lambda_{\mathrm{min}} + \lambda}}}^3 \qquad r \geq 0
\end{equation}
where $\lambda_{\mathrm{min}}$ is the smallest non-zero eigenvalue of $\boldsymbol{H}^{\star}$.
Observe that $\lim_{r \rightarrow \infty}\varepsilon(r) = 0$ because $L^{\star}(r)$ converges to $\|\nabla^2 R(\bw^{\star}_{\lambda})\|_2$, and that $\varepsilon(r) = 0$ for any constant Hessian matrices (e.g., in the case of \ac{RLS}).
Lemma~\ref{lem:truncated_EER_to_ERM} below here establishes a result needed to prove our bound on the local excess risk.
\begin{lemma}
\label{lem:truncated_EER_to_ERM}
For any minimizer $\bw^{\star}_{\lambda}$ of the regularized risk we have
\begin{align*}
  \E_S\br{ \E_{\boldsymbol{w} \sim \wh{p}_{S,\gamma}}\br{\wh{R}_S(\boldsymbol{w}) \,\Big|\, \boldsymbol{w} \in \mathcal{E}^{\star}\pr{r}} } - R(\bw^{\star}_{\lambda})
  \leq
    \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} + \frac{\varepsilon(r)}{6}
  + \frac{M}{2} \sqrt{\frac{\gamma \varepsilon(r)}{3} + \frac{M^2 \gamma^2}{2 m}}~.
\end{align*}
\end{lemma}
(The proof of Lemma~\ref{lem:truncated_EER_to_ERM}, along with that of all remaining statements in this section, can be found in Section~\ref{sec:proofs_smooth}.)
This lemma, combined with the bound on the generalization error (Theorem~\ref{thm:gibbs_gen_error}), gives the desired result.
\begin{theorem}[Localized Excess Risk Bound]
  \label{thm:gibbs_local_excess}
  Assume the same as in Lemma~\ref{lem:truncated_EER_to_ERM}.
  Then,
  %
  \begin{equation*}
    \Delta(\bw^{\star}_{\lambda})
    \leq
    \frac{1}{\gamma} \, \mathrm{tr}\pr{\boldsymbol{H}^{\star} \boldsymbol{H}^{\star -1}_{\lambda}} + \frac{\varepsilon(r)}{6}
    + \frac{M}{2} \sqrt{\frac{\gamma \varepsilon(r)}{3} + \frac{M^2 \gamma^2}{2 m}}
    + \frac{M^2 \gamma}{2 m}~.
  \end{equation*}
\end{theorem}

\subsection{Global analysis}
\label{sec:global}
We now turn our attention to the global analysis of the excess risk.
Since we deal with a countable set of local minima (indexed by $\mathcal{I}$), we add a subscript to all minima-dependent quantities, such as $\bw^{\star}_{\lambda, i}$, $\boldsymbol{H}^{\star}_{\lambda,i}$, $\mathcal{E}^{\star}_i(r)$. In particular, the approximation error is now defined as
\begin{equation}
  \label{eq:approx_global}
  \varepsilon_i(r) = L^{\star}_i\pr{r} \pr{\frac{r}{\sqrt{\lambda_{\mathrm{min},i} + \lambda}}}^3 \qquad r > 0, i \in \mathcal{I}
\end{equation}
where $L^{\star}_i$ is the local Lipschitz constant with respect to the minimum $\bw^{\star}_{\lambda, i}$, and $\lambda_{\mathrm{min},i}$ is the smallest non-zero eigenvalue of the Hessian matrix $\boldsymbol{H}^{\star}_{\lambda,i}$.

Next, we introduce an important assumption on the geometry of the regularized risk around its minimizers.
\begin{assumption}
  \label{asm:global}
All local minima $\bw^{\star}_{\lambda} \in \argmin_{\boldsymbol{w} \in \reals^d}R_{\lambda}(\boldsymbol{w})$ satisfy
  $\nabla R_{\lambda}(\bw^{\star}_{\lambda}) = \boldsymbol{0}$ and are such that $\nabla^2 R_{\lambda}(\bw^{\star}_{\lambda})$ is positive definite.
  In other words all local minima are \emph{isolated}.
\end{assumption}
The above assumption implies that there exists a number $r_0 > 0$ such that
\[
  r_0 = \max\cbr{ r > 0 ~:~ \bigcap_{i \in \mathcal{I}} \mathcal{E}^{\star}_i(r) \equiv \varnothing }~.
\]
In other words, ellipsoids centered at minimizers and aligned with the local curvature of $R_{\lambda}$ are non-overlapping.
In addition to the set $\mathcal{I}$, indexing minima of the regularized risk, let $\mathcal{I}^{\text{\scshape{glob}}} \subseteq \mathcal{I}$ index the global minima and denote its complement by $\mathcal{I}^{\text{\scshape{subopt}}} \equiv \mathcal{I} \setminus \mathcal{I}^{\text{\scshape{glob}}}$.
Finally, introduce the complement of the ellipsoids centered at the minima (later called, with some abuse of terminology, \emph{complement of the minima}),
\[
  \sC^{\star}(r) \equiv \reals^d \setminus \bigcup_{i \in \mathcal{I}} \mathcal{E}^{\star}_i(r) \qquad r \leq r_0~.
\]
The first result in this section concerns the distribution of local minima.
In particular, we give an upper bound on the relative probability $\pi_{\gamma,r}(i)$ of the $i$-th minimum, and then derive the analytic form of the asymptotic distribution $\pi_{\infty}$.
\begin{lemma}[Distribution of Minima]
  \label{lem:erm_prob}
  %
  For all $r > 0$,
  \begin{align*}
    \pi_{\gamma,r}(i)
    \leq
    \frac{e^{\frac{\gamma}{3} \max_{k \in \mathcal{I}}\varepsilon_k(r)}}
    {\sum_{j \in \mathcal{I}} e^{\gamma \pr{ R_{\lambda}(\bw^{\star}_{\lambda, i}) - R_{\lambda}(\bw^{\star}_{\lambda, j})}}
    \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda,i})}{\det(\boldsymbol{H}^{\star}_{\lambda,j})} }
    }
    \qquad i \in \mathcal{I}~.
  \end{align*}
  %
  %
  Moreover, assuming without loss of generality that $R_{\lambda}(\bw^{\star}_{\lambda, i}) = 0$ for all $i \in \mathcal{I}^{\text{\scshape{glob}}}$, and setting $r = \gamma^{-p}$ for $p > 0$, we have
  %
  \[
    \lim_{\gamma \rightarrow \infty}\pi_{\gamma,r}(i)
    = \begin{cases}
    \frac{1}{\sum_{j \in \mathcal{I}^{\text{\scshape{glob}}}} \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda, i})}{\det(\boldsymbol{H}^{\star}_{\lambda, j})} }} & i \in \mathcal{I}^{\text{\scshape{glob}}}
  \\
    0 & i \in \mathcal{I}^{\text{\scshape{subopt}}}~.
  \end{cases}
  \]
\end{lemma}
We are now ready to state the main result of this section.
\begin{theorem}[Global Excess Risk Bound]
  \label{thm:global_excess_risk}
  Assume the same as in Lemma~\ref{lem:truncated_EER_to_ERM}.
  Then for any $r \in [0, r_0]$ the global excess risk satisfies
  \begin{equation*}
  \Delta(\pi_{\gamma,r})
  \lesssim
  \frac{1}{\gamma} \, \E\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}}
  + \frac{\gamma}{\sqrt{m}}
  + \E[\varepsilon_I(r)] + \sqrt{\gamma \E[\varepsilon_I(r)]} + \mathbb{P}_{\gamma}(\sC^{\star}(r))
  \end{equation*}
  where the expectation is taken with respect to $I \sim \pi_{\gamma,r}$
  and the probability of the complement of the minima is bounded as
  \begin{equation}
  \label{eq:lb_P_complement}
  \mathbb{P}_{\gamma}(\sC^{\star}(r))
  \leq
  1 - \pr{1 - d e^{-r^2 \gamma \alpha_{d/2}}} \sum_{i \in \mathcal{I}} e^{-\frac{1}{3} \gamma \varepsilon_i(r)}
  \end{equation}
  with
    \begin{equation}
    \alpha_{d/2} =
    \begin{cases}
      1 & d = 1\\
      \Gamma\pr{1+\frac{d}{2}}^{-\frac{2}{d}} & \text{otherwise}~.
    \end{cases}
  \end{equation}
\end{theorem}
\begin{remark}
  \label{rem:tuning_r}
  We compute the value of $r$ approximately minimizing the the right-hand side in Theorem~\ref{thm:global_excess_risk}.
  Note that the probability of the complement of the minima decreases if we ensure that $r^2 \gamma$ increases in $\gamma$ and $\gamma \varepsilon_i(r) \propto r^3 \gamma$ is non-increasing.
For instance we may set $r^2 \gamma = \gamma^p$ for $p > 0$
so that $r^3 \gamma = \gamma^{1 + \frac{3}{2} (p-1)}$. Hence we require $1 + \frac{3}{2} (p-1) \leq 0$ which is satisfied for any $p \in (0, 1/3]$.
This implies that when $r = \gamma^{\frac{p-1}{2}}$ and $p \in (0, 1/3]$ the probability of the complement of the minima and the approximation terms $\gamma \varepsilon_i(r), \varepsilon_i(r)$ all vanish as $\gamma \to \infty$.
\end{remark}
Finally, combining the localized excess risk bound in Theorem~\ref{thm:gibbs_local_excess} with Lemma~\ref{lem:erm_prob} allows us to prove the following result about the asymptotic pseudo excess risk.
\begin{cor}
  \label{cor:global_excess_risk_asymptotic}
  Assume the same as in Lemma~\ref{lem:truncated_EER_to_ERM}.
  Then, for any $r > 0$, the global asymptotic pseudo-excess risk satisfies
  \[
    \Delta^{\infty}_r
    \lesssim
    \frac{1}{\gamma} \, \E\br{\mathrm{tr}\pr{\boldsymbol{H}^{\star}_{I} \boldsymbol{H}^{\star -1}_{\lambda,I}}}
    + \E \br{\varepsilon_I(r)}
    + \sqrt{\gamma \E \br{\varepsilon_I(r)} + \frac{\gamma^2}{m}}
  + \frac{\gamma}{m}
\]
where $I$ is distributed according to
\[
\pi_{\infty}(i) =
  \frac{1}{\sum_{j \in \mathcal{I}^{\text{\scshape{glob}}}} \sqrt{\frac{\det(\boldsymbol{H}^{\star}_{\lambda, i})}{\det(\boldsymbol{H}^{\star}_{\lambda, j})} }}~.
\]
\end{cor}