\section{Introduction}

One of the key challenges in machine learning research concerns the ``generalization'' behavior of learning algorithms. That is: if a learning algorithm performs well on the training set, what guarantees can one provide on its performance on new samples?

While the question of generalization is understood in many settings (\citep{introToLearning,learningBook}), existing bounds and techniques provide vacuous expressions when employed to show the generalization capabilities of deep neural networks (DNNs) (\citep{normsNN,vcDimNN, genErrDL1,genErrDL2}). In general,
classical measures of model expressivity (such as Vapnik-Chervonenkis
(VC) dimension (\citep{vcDim}), Rademacher complexity (\citep{rademacherComplexity}), etc.), fail to explain the generalization abilities
of DNNs due to the fact that they are typically over-parameterized models with less
training data than model parameters. 
A novel approach was introduced by \citep{explBiasMI}, and \citep{infoThGenAn} (further developed by \citep{conditionalMI,tighteningMI,fullVersionGeneralization,tpcGenerr} and many others), where information-theoretic techniques are used to link the generalization capabilities of a learning algorithm to information measures. These quantities are algorithm-dependent and can be used to analyze the generalization capabilities of general classes of updates and models, \textit{e.g.}, noisy iterative algorithms like Stochastic Gradient Langevin Dynamics (SGLD) (\citep{genErrMISGLD, optimalNoiseSGLD}), which can thus be applied to deep learning. Moreover, it has been shown that information-theoretic bounds can be non-vacuous and reflect the real generalization behavior even in deep
learning settings (\citep{genErrNoisyIterative,nonvacuousPAC, genErrSGDLDataDependent,genErrNoisyIterativeCMI}).

In this work we adopt and expand the framework introduced by \citep{genErrMISGLD}, but instead of focusing on the mutual information between the input and output of an iterative algorithm, we compute the maximal leakage (\citep{leakageLong}).
Maximal leakage, together with other information measures of the Sibson/R\'enyi family (maximal leakage can be shown to be Sibson Mutual information of order infinity (\citep{leakageLong})), have been linked to high-probability bounds on the generalization error (\citep{fullVersionGeneralization}). In particular, given a learning algorithm $\mathcal{A}$ trained on data-set $S$ (made of $n$ samples) one can provide the following guarantee in case of the $0-1$ loss:
\begin{equation}
    \mathbb{P}(|\text{gen-err}(\mathcal{A},S)|\geq \eta) \leq 2\exp(-2n\eta^2 + \ml{S}{\mathcal{A}(S)}).
\end{equation}
This deviates from much of the literature in which the focus is on bounding the \textbf{expected} generalization error instead (\citep{infoThGenAn,conditionalMI}). 
Consequently, if one can guarantee that for a class of algorithms, the maximal leakage between the input and the output is bounded, then one can provide an \textbf{exponentially decaying} (in the number of samples $n$) bound on the probability of having a large generalization error. This is in general not true for mutual information, which can typically only guarantee a linearly decaying bound on the probability of the same event (\citep{learningMI}). Moreover, a bound on maximal leakage implies a bound on mutual information (cf.~\Cref{eq:sibsonMI-increasing}) and, consequently, a bound on the expected generalization error of $\mathcal{A}$. The main advantage of maximal leakage lies in the fact that it depends on the distribution of the samples only through its support. It is thus naturally independent from the distribution over the samples and particularly amenable to analysis, especially in additive noise settings.

The contributions of this work can be summarized as follows:
\begin{itemize}
    \item we derive novel bounds on $\ml{S}{\mathcal{A}(S)}$ whenever $\mathcal{A}$ is a noisy, iterative algorithm (SGLD-like), which then implies generalization with high-probability;
    \item we show that the bounds provided on maximal leakage strictly improve the bounds provided by \citep{genErrMISGLD}, and we thus provide a tighter bound on the expected generalization error of said algorithms as well;
    \item we show that, under certain assumptions, adding Gaussian noise is asymptotically optimal in the number of dimensions $d$. In particular, we prove that the maximal leakage (and, consequently, the mutual information) between the input and output of this family of algorithms goes to $0$ with the number of dimensions. This implies that the input and output are \textit{asymptotically independent} which is consistent with practical observations 
 - larger neural networks generalize better;
  \item we leverage the analysis to extrapolate the optimal type of noise to be added (in the sense that it minimizes the induced maximal leakage), based on the assumptions imposed on the algorithm. In particular, 
  \begin{itemize}
      \item if one assumes the $L_p$ norm of the gradient to be bounded, with $p\leq 2$, our analysis shows that adding Gaussian noise is asymptotically optimal;
      \item if one assumes the $L_\infty$ norm of the gradient to be bounded, then adding uniform noise is optimal;
  \end{itemize}
  Hence, the analysis and computation of maximal leakage can be used to inform the design of novel noisy, iterative algorithms.
\end{itemize}

\subsection{Related Work}
The line of work exploiting information measures to bound the expected generalization started in~\citep{explBiasMI,infoThGenAn} and was then refined with a variety of approaches considering Conditional Mutual Information~\citep{conditionalMI,genErrNoisyIterativeCMI}, the Mutual Information between individual samples and the hypothesis~\citep{ismi} or improved versions of the original bounds~\citep{ISIT2019,improvingMICondProc}. Other approaches employed the Kullback-Leibler Divergence with a PAC-Bayesian approach~\citep{pacbayes,nonvacuousPAC}. 
Moreover, said bounds were then characterized for specific SGLD-like algorithms, denoted as ``noisy, iterative algorithms'' and used to provide novel, non-vacuous bounds for Neural Networks~\citep{genErrMISGLD,genErrSGDLDataDependent,genErrNoisyIterativeCMI, wang2023generalization} as well as for SGD algorithms~\citep{sgdBoundInfoTh}. Recent efforts tried to provide the optimal type of noise to add in said algorithms and reduce the (empirical) gap in performance between SGLD and SGD~\citep{optimalNoiseSGLD}.
All of these approaches considered the KL-Divergence or (variants of) Shannon's Mutual Information. General bounds on the expected generalization error leveraging arbitrary divergences were given in~\citep{tpcGenerr,convexAnalysisGenErr}.
Another line of work considered instead bounds on the probability of having a large generalization error~\citep{learningMI,fullVersionGeneralization,conditionalSibsonErrorBounds} and focused on large families of divergences and generalizations of the Mutual Information (in particular of the Sibson/R\'enyi-family, including conditional versions).

\section{Preliminaries, Setup, and a General Bound}
\subsection{Preliminaries}
\subsubsection{Information Measures}
The main building block of the information measures considered in this work is the R\'enyi's $\alpha$-divergence between two measures $P$ and $Q$, $D_\alpha(P\|Q)$ (which can be seen as a parametrized generalization of the Kullback Leibler-divergence)~\cite[Definition 2]{RenyiKLDiv}. Starting from R\'enyi's Divergence and the geometric averaging that it involves, Sibson built the notion of Information Radius~\citep{infoRadius} which can be seen as a special case of the following quantity~\citep{verduAlpha}: $
    I_\alpha(X,Y) = \min_{Q_Y} D_\alpha(P_{XY}\|P_{X}Q_Y). $
Sibson's $I_\alpha(X,Y)$ represents a generalization of Shannon's mutual information, indeed one has that: $
\lim_{\alpha\to 1}I_\alpha(X,Y)=I(X;Y) = \mathbb{E}_{P_{XY}}\left[\log\left(\frac{dP_{XY}}{dP_XP_Y}\right)\right].$
Differently, when $\alpha\to\infty$, one gets: \begin{equation}
I_\infty(X,Y)=\log\mathbb{E}_{P_Y}\left[ \esssup_{P_X} \frac{dP_{XY}}{dP_XP_Y} \right] =\ml{X}{Y},
\end{equation} where $\ml{X}{Y}$ denotes the maximal leakage from $X$ to $Y$, a recently defined information measure with an operational meaning in the context of privacy and security~\citep{leakageLong}. Maximal leakage represents the main quantity of interest for the scope of this paper, as  it is amenable to analysis and has been used to bound the generalization error~\citep{fullVersionGeneralization}. As such, we will bound the maximal leakage between the input and output of generic noisy iterative algorithms.

To that end, we mention a few useful properties of $\ml{X}{Y}$. If $X$ and $Y$ are jointly continuous random variables, then~\cite[Corollary 4]{leakageLong}
\begin{align}
    \ml{X}{Y} = \log \int \esssup_{P_X} f_{Y|X} (y|x) dy,
\end{align}
where $f_{Y|X}$ is the conditional pdf of $Y$ given $X$. Moreover, maximal leakage satisfies the following chain rule (the proof of which is given in Appendix~\ref{app:lem-chain-rule}):
\begin{lemma} \label{lem:chain-rule-maxLeak}
    Given a triple of random variables $(X,Y_1,Y_2)$, then
    \begin{align}
    \label{eq:lem-chain-rule}
    \ml{X}{Y_1, Y_2} \leq \ml{X}{Y_1} + \cml{X}{Y_2}{Y_1},
\end{align}
where the conditional maximal leakage $\cml{X}{Y_2}{Y_1}  = \esssup_{P_{Y_1}} \cml{X}{Y_2}{Y_1=y_1}$, where the latter term is interpreted as the maximal leakage from $X$ to $Y_2$ with respect to the distribution $P_{XY_2 | Y_1 = y_1}$. Consequently, for random variables $(X, (Y_i)_{i=1}^n)$,
\begin{align} \label{eq:lem:chain-rule-general}
    \ml{X}{Y^n} \leq \sum_{i=1}^n \cml{X}{Y_i}{Y^{i-1}}.
\end{align}
\end{lemma}
Moreover, one can relate $\ml{X}{Y}$ to $I(X;Y)$ through $I_\alpha$. Indeed, an important property of $I_\alpha$ is that it is non-decreasing in $\alpha$, hence for every $\infty>\alpha>1$:
\begin{equation} \label{eq:sibsonMI-increasing}
    I(X;Y) = I_1(X,Y) \leq I_\alpha(X,Y) \leq I_\infty(X,Y) = \ml{X}{Y}. 
\end{equation}
For more details on Sibson's $\alpha$-MI we refer the reader to~\citep{verduAlpha}, as for maximal leakage the reader is referred to~\citep{leakageLong}.

\subsubsection{Learning Setting}

Let $\mathcal{Z}$ be the sample space, $\mathcal{W}$ be the hypothesis space, and $\ell : \mathcal{W} \times \mathcal{Z} \rightarrow \mathbb{R}_+$ be a loss function. Say $\mathcal{W} \subseteq \mathbb{R}^d$. Let $S=(Z_1, Z_2, \ldots, Z_n)$ consist of $n$ i.i.d samples, where $Z_i \sim P$, with $P$ unknown. 
A learning algorithm $\mathcal{A}$ is a mapping $\mathcal{A}:\mathcal{Z}^n\to \mathcal{W}$ that given a sample $S$ provides a hypothesis $W=\mathcal{A}(S)$. $\mathcal{A}$ can be either a deterministic or a randomized mapping and undertaking a probabilistic (and information-theoretic) approach one can then equivalently consider $\mathcal{A}$ as a family of conditional probability distributions $P_{W|S=s}$ for $s\in \mathcal{Z}^n$ \textit{i.e.}, an information channel. Given a hypothesis $w\in\mathcal{W}$ the true risk of $w$ is denoted as follows:
\begin{equation}
    L_{P_Z}(w) = \mathbb{E}_{P}[\ell(w,Z)]
\end{equation}
while the empirical risk of $w$ on $S$ is denoted as follows:
\begin{equation}
    L_{S}(w) = \frac1n\sum_{i=1}^n \ell(w,Z_i).
\end{equation}
Given a learning algorithm $\mathcal{A}$, one can then define its generalization error as follows:
\begin{equation}
\text{gen-err}_\mathcal{P}(\mathcal{A},S)=L_{\mathcal{P}}(\mathcal{A}(S))-L_{S}(\mathcal{A}(S)).
\end{equation}
Since both $S$ and $\mathcal{A}$ can be random, $\text{gen-err}_\mathcal{P}(\mathcal{A},S)$ is a random variable and one can then study its expected value or its behavior in probability. Bounds on the expected value of the generalization error in terms of information measures are given in~\citep{infoThGenAn,ISIT2019,ismi,conditionalMI} stating different variants of the following bound (\cite[Theorem 1]{infoThGenAn}):
if $\ell(w,Z)$ is $\sigma^2$-sub-Gaussian\footnote{A $0$-mean random variable $X$ is said to be $\sigma^2$-sub-Gaussian if $\log\mathbb{E}[\exp(\lambda X)]\leq \sigma^2\lambda^2/2$ for every $\lambda\in\mathbb{R}$.} then
\begin{equation} \label{eq:gen-bound-MI}
    \left|\mathbb{E}[\text{gen-err}_\mathcal{P}(\mathcal{A},S)] \right| \leq \sqrt{\frac{2\sigma^2 I(S;\mathcal{A}(S))}{n}}.
\end{equation}
Thus, if one can prove that the mutual information between the input and output of a learning algorithm $\mathcal{A}$ trained on $S$ is bounded (ideally, growing less than linearly in $n$) then the expected generalization error of $\mathcal{A}$ will vanish with the number of samples.
Alternatively,~\cite{fullVersionGeneralization} demonstrate high-probability bounds, involving different families of information measures. One such bound, which is relevant to the scope of this paper is the following  
\cite[Corollary 2]{fullVersionGeneralization}: assume $\ell(w,Z)$ is $\sigma^2$-sub-Gaussian and let $\alpha>1$
\begin{equation}
    \mathbb{P}(|\text{gen-err}_P(\mathcal{A},S)|\geq t) \leq 2\exp\left(-\frac{\alpha-1}{\alpha}\left(\frac{nt^2}{2\sigma^2}- I_\alpha(S,\mathcal{A}(S))\right) \right) \label{eq:genErrProbBound},
\end{equation}
taking the limit of $\alpha\to\infty$ in~\eqref{eq:genErrProbBound} leads to the following~\cite[Corollary 4]{fullVersionGeneralization}:
\begin{equation}
    \mathbb{P}(|\text{gen-err}_P(\mathcal{A},S)|\geq t) \leq 2\exp\left(-\left(\frac{nt^2}{2\sigma^2}- \ml{S}{\mathcal{A}(S)}\right)\right) \label{eq:genErrProbBoundMaxLeak}.
\end{equation}
Thus, in this case, if one can prove that the maximal leakage between the input and output of a learning algorithm $\mathcal{A}$ trained on $S$ is bounded, then the \textbf{probability} of the generalization error of $\mathcal{A}$ being larger than any constant $t$ will decay \textbf{exponentially fast} in the number of samples $n$.
\subsection{Problem Setup}
We consider iterative algorithms, where each update is of the following form:
\begin{align} \label{eq:iteration}
W_t = g(W_{t-1}) - \eta_t F(W_{t-1},Z_t) + \xi_t, ~ \forall ~ t \geq 1,
\end{align}
where $Z_t \subseteq S$ (sampled according to some distribution), $g: \mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ is a deterministic function, $F(W_{t-1},Z_t)$ computes a direction (e.g., gradient), $\eta_t$ is a constant step-size, and $\xi_t =( \xi_{t1}, \ldots, \xi_{td})$ is noise. We will assume for the remainder of this paper that $\eta_t$ has an absolutely continuous distribution.
Let $T$ denote the total number of iterations, $W^t = (W_1, W_2, \ldots W_t)$, and $Z^t = (Z_1, Z_2, \ldots, Z_t)$. The algorithms under consideration further satisfy the following two assumptions
\begin{itemize}
\item {\bf Assumption 1 (Sampling):} The sampling strategy is agnostic to parameter vectors: 
\begin{align}
P(Z_{t+1}|Z^t, W^t, S) = P(Z_{t+1} |Z^t, S).
\end{align}
\item {\bf Assumption 2 ($\mathbf{L_p}$-Boundedness):} For some $p>0$ and $L>0$,  $\sup_{w,z} \| F(w,z) \|_p \leq L$.
\end{itemize}
As a consequence of the first assumption and the structure of the iterates, we get:
\begin{align} \label{eq:markov}
P(W_{t+1} | W^t, Z^T, S) = P(W_{t+1} | W_t, Z_{t+1}).
\end{align}
The above setup was proposed by Pensia \emph{et al.}~\citep{genErrMISGLD}, who specifically studied the case $p=2$. 
Denoting by $W$ the final output of the algorithm (some function of $W^T$), they show that
\begin{theorem}[{\cite[Theorem 1]{genErrMISGLD}}] \label{thm:Pensia}
If the boundedness assumption holds for $p=2$ and 
$\xi_t \sim \mathcal{N}(0, \sigma^2_t I_d)$, then
\begin{align} \label{eq:thm-Pensia}
I(S;W) \leq \frac{d}{2} \sum_{t=1}^T \log \left(1 + \frac{\eta^2_t L^2}{d \sigma^2_t} \right).
\end{align}
\end{theorem}
By virtue of inequality~\eqref{eq:gen-bound-MI}, this yields a bound on the expected generalization error.

In this work, we derive bounds on the maximal leakage between $\ml{S}{W}$ for iterative noisy algorithms, which leads to high-probability bounds on the generalization error (cf. equation~\eqref{eq:genErrProbBoundMaxLeak}). We consider different scenarios in which $F$ is bounded in $L_1$, $L_2$, or $L_\infty$ norm, and the added noise is Laplace, Gaussian, or Uniform.

\subsection{Notation} \label{sec:notation}
Given $d \in \mathbb{N}$, $w \in \mathbb{R}^d$, and $r >0$, let $\mathcal{B}_p^{d}(w,r) = \{ x \in \mathbb{R}^d: \| x - w \|_p \leq r \}$ denote the $L_p$-ball of radius $r$ and center $w$, and let $V_p (d,r)$ denote its corresponding volume. When the dimension $d$ is clear from the context, we may drop the superscript and write $\mathcal{B}_p(w,r)$. Given a set $S$, we denote its complement by $\overline{S}$. The $i$-th component of $w_t$ will be denoted by $w_{ti}$. 

We denote the pdf of the noise $\xi_t$ by $f_t: \mathbb{R}^d \rightarrow \mathbb{R}$. The following functional will be useful for our study: given $d \in \mathbb{N}$, $p > 0$, a pdf $f: \mathbb{R}^d \rightarrow R$, and an $r \geq 0$, define
\begin{align}
    \label{eq:def-h}
    h(d,p,f,r) \vcentcolon=  \int \limits_{\overline{\mathcal{B}_p^d}(0, r)} \sup_{x \in \mathcal{B}_p^d(0,r)} f(w - x) \mathrm{d} w. 
\end{align}
We denote the ``positive octant'' by $A_d$, i.e.,
\begin{align}
    \label{eq:def-positive-octant}
    A_d \vcentcolon= \{ w \in \mathbb{R}^d: w_i \geq 0, \text{ for all } i \in \{1,2,\ldots,d\} \}.
\end{align}
Since we will mainly consider pdfs that are symmetric (Gaussian, Laplace, uniform), the $h$ functional ``restricted'' to $A_d$ will be useful:
\begin{align}
    \label{eq:def-h-positive}
    h_+ (d,p,f,r) \vcentcolon=  \int \limits_{\overline{\mathcal{B}_p^d}(0, r) \cap A_d } \sup_{x \in \mathcal{B}_p^d(0,r)} f(w - x) \mathrm{d} w. 
\end{align}



\subsection{General Bound}


\begin{proposition} \label{prop:general}
    Suppose $f_{t}: \mathbb{R}^d \rightarrow \mathbb{R}$ is maximized for $x = 0$. If Assumptions 1 and 2 hold for some $p > 0$, then
\begin{align}
    \label{eq:prop-general}
    \ml{S}{W} \leq \sum_{t=1}^T \log \left( f_{t} (0) V_p(d,\eta_t L) + h(d,p,f_t, \eta_t L) \right),
\end{align}
where $h$ is defined in equation~\eqref{eq:def-h}.
\end{proposition}

The above bound is appealing as it implicitly poses an optimization problem: given a constraint on the noise pdf $f_t$ (say, a bounded variance), one may choose $f_t$ as to minimize the upper bound in equation~\eqref{eq:prop-general}. Moreover, despite its generality, we show that it is tight in several interesting cases, including when $p=2$ and $f_t$ is the Gaussian pdf.
The series of steps leading to the upper bound include only one inequality (the source of the ``looseness'' of the bound), which could be viewed as due to replacing Assumption 2 by the following statement: for all $w$, $\cup_z F(w,z) = \mathcal{B}_p^d(0,L)$, i.e., in addition to assuming $F(w,z) \in \mathcal{B}_p^d(0,L)$, we assume that, for every $w$, every point in the ball $\mathcal{B}_p^d(0,L)$ is attained for some $z$.

In the next section, we consider several scenarios for different values of $p$ and different noise distributions. As a testament to the tractability of maximal leakage, we derive exact semi-closed form expressions for the bound of Proposition~\ref{prop:general}. Finally, it is worth noting that the form of the bound allows to choose different noise distributions at different time steps, but these examples are outside the scope of this paper. \\


\begin{proof}
We proceed as in the the work of \citep{genErrMISGLD}: 
\begin{align}
\ml{S}{W} \leq \ml{Z^T}{W^T} \leq \sum_{t=1}^T \cml{Z^T}{W_t}{W^{t-1}} = \sum_{t=1}^T \cml{Z_t}{W_t}{W_{t-1}},
\end{align}
where the first inequality follows from Lemma 2 of \citep{genErrMISGLD} and the data processing inequality for maximal leakage~\cite[Lemma 1]{leakageLong}, the second inequality follows Lemma~\ref{lem:chain-rule-maxLeak}, and the equality follows from~\eqref{eq:markov}. Now,
\begin{align}
\exp\left\lbrace \cml{Z_t}{W_t}{W_{t-1}=w_{t-1}} \right\rbrace
    & =     \int_{\mathbb{R}^d} \esssup_{P_{z_t}} p(w_t | Z_t) \mathrm{d} w_t \\
    & = \int_{\mathbb{R}^d} \esssup_{P_{z_t}} f_t \left( w_t - g(w_{t-1}) + \eta_t F(w_{t-1},Z_t) \right) \mathrm{d} w_t, \\
    & = \int_{\mathbb{R}^d} \esssup_{P_{z_t}} f_t \left( w_t + \eta_t F(w_{t-1},Z_t) \right) \mathrm{d} w_t, 
\end{align}
where the last equality follows from a change of a variable $\tilde{w_t} = w_t - g(w_{t-1})$. Finally, since $\eta_t F(w_{t-1},z_t) \in \mathcal{B}_p(0, \eta_t L)$ by assumption, we can further upper-bound the above by:
\begin{align}
     & \exp\left\lbrace  \cml{Z_t}{W_t}{W_{t-1}=w_{t-1}} \right\rbrace \\
     & \leq \int_{\mathbb{R}^d} \sup\limits_{x_t \in \mathcal{B}_p(0,\eta_t L)} f_t \left( w_t + x_t \right) \mathrm{d} w_t  \label{eq:prop-ball-Lp} \\
     & = \int\limits_{\mathcal{B}_p(0,\eta_t L) } \sup\limits_{x_t \in \mathcal{B}_p(0,\eta_t L)}  f_{t} \left( w_{ti} + x_{ti} \right) \mathrm{d} w_t + \int\limits_{\mathcal{B}_p^\mathsf{c}(0,\eta_t L)} \sup\limits_{ x_t \in \mathcal{B}_p(0,\eta_t L)} f_t \left( w_t + x_t \right) \mathrm{d} w_t \\
     &  = f_{t} (0) V_p(d, \eta_t L) + \int\limits_{ \overline{\mathcal{B}_p} (0,\eta_t L)} \sup\limits_{ x_t \in \mathcal{B}_p(0,\eta_t L)} f_t \left( w_t - x_t \right) \mathrm{d} w_t,
\end{align}
where the last equality follows from the assumptions on $f_{t}$.
\end{proof}


\section{Boundedness in $L_2$-Norm}

Considering the case where $F$ computes a gradient, then boundedness in $L_2$-norm is a common assumption. It is commonly enforced, for instance, using gradient clipping \citep{abadi2016tensorflow,abadi2016deep,chen2020understanding}.

The case in which $p=2$ and the noise is Gaussian leads to the strongest result in this paper:

\begin{theorem} \label{thm:gaussian-ml}
If the boundedness assumption holds for $p \leq 2$ and 
$\xi_t \sim \mathcal{N}(0, \sigma^2_t I_d)$, then
\begin{align} \label{eq:thm-gaussian-ml}
\ml{S}{W} \leq  \sum_{t=1}^T \log \left( \frac{V_2 (d,\eta_t L)}{(2 \pi \sigma_t^2)^{d/2}} +  \frac{1}{\Gamma \left( \frac{d}{2} \right)  } \sum_{i=0}^{d-1} \Gamma \left( \frac{i+1}{2} \right)  
\left(  \frac{\eta_t L}{ \sigma_t \sqrt{2}}  \right)^{d-1-i} \right), 
\end{align} 
where $\displaystyle V_2(d,r) = \frac{\pi^{d/2}}{\Gamma \left(\frac{d}{2}+1 \right)} r^d$. Consequently, for fixed $T$,
\begin{align} \label{eq:thm-gaussian-limit}
\lim_{d \rightarrow \infty} \ml{S}{W}=0.
\end{align}
\end{theorem}

Remarkably, equation~\eqref{eq:thm-gaussian-limit} states that, as $d$ grows, $S$ and $W$ are asymptotically independent. The bound is asymptotically optimal for $\ml{S}{W}$ (indeed it yields an equality). More importantly, the induced high probability bound by equation~\eqref{eq:genErrProbBoundMaxLeak} is also optimal. Indeed, at the limit when $S$ and $W$ are independent, the bound~\eqref{eq:genErrProbBoundMaxLeak} recovers (the order optimal) McDiarmid's inequality \textit{i.e.}, under the assumptions of~\Cref{thm:gaussian-ml} and considering the $0-1$ loss:
\begin{equation}
    \mathbb{P}(|\text{gen-err}(\mathcal{A},S)|\geq t) \leq 2\exp(-2nt^2).
\end{equation} This can be seen as an explanation of the (arguably un-intuitive) phenomenon that deeper networks often generalize better (also analyzed by~\citep{wang2023generalization}). 

By contrast, this is not captured in the bound by~\citep{genErrMISGLD} given in equation~\eqref{eq:thm-Pensia}. Indeed, it is growing as a function of $d$, and tends to a non-zero value:
\begin{align}
    \lim_{ d \rightarrow \infty} \frac{d}{2} \sum_{t=1}^T \log \left(1 + \frac{\eta^2_t L^2}{d \sigma^2_t} \right) & = \sum_{t=1}^T \frac{\eta^2_t L^2}{2 \sigma^2_t},
\end{align}
where the equality follows from the fact that $\displaystyle \lim_{n \rightarrow \infty} (1+c/n)^c = e^c$ for all $c \in \mathbb{R}$. Notably, however, $I(S;W) \leq \ml{S}{W}$ (cf. equation~\eqref{eq:sibsonMI-increasing}), so that for large $d$, we have
\begin{align}
    I(S;W) \leq \ml{S}{W}\leq \text{right-hand side of~\eqref{eq:thm-gaussian-ml}} \leq \text{ right-hand side of~\eqref{eq:thm-Pensia}}.
\end{align}
As such, the bound in Theorem~\ref{thm:gaussian-ml} is also a tighter upper bound on $I(S;W)$.

Moreover, note that even if the parameter $L$ is large (e.g., Lipschitz constant of a neural network \citep{genErrSGDLDataDependent}), it appears in~\eqref{eq:thm-gaussian-ml} normalized by $\Gamma(d/2)$ so its effect is significantly dampened (as $d$ is also typically very large). 

Finally, note that the bound in Proposition~\ref{prop:general} is increasing in $p$: this can be seen from line~\eqref{eq:prop-ball-Lp}, where the supremum over $\mathcal{B}_p$ can be further upper-bounded by a supremum over $\mathcal{B}_{p'}$ for $p' > p$. Therefore for $q \leq p$, the bound induced by Proposition~\ref{prop:general} is smaller. The bound in~\Cref{thm:gaussian-ml} corresponds to $p=2$ and goes to 0 (as $d$ grows), hence the bound induced by Proposition~\ref{prop:general} goes to 0 for all $q \leq p$. In particular, adding Gaussian noise is asymptotically optimal (in the sense discussed above) when Assumption 2 holds for any $p \leq 2$. \\


\begin{proof}
To show that the right hand side of Equation~\eqref{eq:thm-gaussian-ml} goes to zero as as $d\rightarrow\infty$ is equal to zero, we use Stirling's approximation of the Gamma function: for all $ x >0$,
\begin{align}
    \sqrt{2 \pi} x^{x-\frac{1}{2}} e^{-x} \leq \Gamma(x) \leq \sqrt{2 \pi} x^{x-\frac{1}{2}} e^{-x} e^{\frac{1}{12x}}.
\end{align}
The details of the computation can be found in Appendix~\ref{app:stirling}.
We now turn to the proof of inequality~\eqref{eq:thm-gaussian-ml}. The conditions of Proposition~\ref{prop:general} are satisfied, thus it is sufficient to prove the bound for $p=2$:
\begin{align}
    \ml{S}{W} & \leq \sum_{t=1}^T \log \left( f_{t} (0) V_2(d,\eta_t L) + \int \limits_{\overline{\mathcal{B}_2}(0, \eta_t L)} \sup_{x_t \in \mathcal{B}_2(0,\eta_{t} L)} f_t(w_t - x_t) \mathrm{d} w_t \right) \\
    & = \sum_{t=1}^T \log \!\! \left( \!\! \frac{V_2(d,\eta_t L)}{(2 \pi \sigma_t^2)^{\frac{d}{2}}} + \!\!\!\! \int  \limits_{\overline{\mathcal{B}_2} (0, \eta_t L)} \!\! \sup_{x_t \in \mathcal{B}_2(0,\eta_{t} L)} \!\! \frac{1}{(2 \pi \sigma_t^2)^{\frac{d}{2}}} \exp \left\lbrace -\frac{\|w_t-x_t\|^2_2}{ 2 \sigma_t^2} \right\rbrace \mathrm{d} w_t \!\! \right) \! . \label{eq:prop-for-gaussian}
\end{align}
Hence, it remains to show that the second term inside the $\log$ matches that of equation~\eqref{eq:thm-gaussian-ml}. To that end, note that the point in $\mathcal{B}_2(0,\eta_t L)$ that minimizes the distance to $w_t$ is given $\frac{\eta_t L}{\| w_t \|} w_t$. So we get
\begin{align}
\| w_t - x_t \| \geq \| w_t - \frac{\eta_t L}{\| w_t \|} w_t \| = \| w_t\| - \eta_t L.
\end{align}
 Then, 
\begin{align} 
h(d,2,f_t,\eta_t L) & =     \int \limits_{\overline{\mathcal{B}_2} (0, \eta_t L)} \sup_{x_t \in \mathcal{B}_2(0,\eta_{t} L)} \frac{1}{(2 \pi \sigma_t^2)^{\frac{d}{2}}} \exp \left\lbrace -\frac{\|w_t-x_t\|^2_2}{ 2 \sigma_t^2} \right\rbrace \mathrm{d} w_t \\
&  = \int\limits_{\overline{\mathcal{B}_2} (0, \eta_t L)}  \frac{1}{(2 \pi \sigma_t^2)^{\frac{d}{2}}} \exp \left\lbrace - \frac{(\|w_t\|_2 - \eta_t L )^2}{2 \sigma_t^2} \right\rbrace \mathrm{d} w_t.
\label{eq:almost-there}
\end{align}
To evaluate this integral, we use spherical coordinates (details in Appendix~\ref{app:spherical}). Then,
\begin{align} \label{eq:MlGaussInt}
h(d,2,f_t,\eta_t L) = \left ( \frac{\eta_t L}{ \sigma_t \sqrt{2}} \right)^{d-1} \frac{1}{\Gamma \left( \frac{d}{2} \right)  } \sum_{i=0}^{d-1} \left( \frac{ \sigma_t \sqrt{2}}{\eta_t L}  \right)^i \Gamma \left( \frac{i+1}{2} \right).
\end{align}
Combining equations~\eqref{eq:prop-for-gaussian} and~\eqref{eq:MlGaussInt} yields~\eqref{eq:thm-gaussian-ml}.
\end{proof}

\begin{remark}
One could also derive a semi-closed form bound for the case in which the added noise is uniform. However, in that case $\ml{S}{W}$ goes to infinity as $d$ goes to infinity. The same behavior holds if the added noise is Laplace. Since the Gaussian noise leads to an asymptotically optimal bound, we skip the analysis of uniform and Laplace noise.
\end{remark}









\section{Boundedness in $L_\infty$-Norm}


The bound in Proposition~\ref{prop:general} makes minimal assumptions about the pdf $f_t$. In many practical scenarios we have more structure we could leverage. In particular, we make the following standard assumptions in this section: 
\begin{itemize}
    \item $\xi_t$ is composed of i.i.d components. Letting $f_{t0}$ be the pdf of a component, $\displaystyle f_t(x_t) \!\! = \!\! \prod_{i=1}^d f_{t0}(x_{ti})$.
    \item $f_{t0}$ is symmetric around 0 and non-increasing over $[0,\infty).$ 
\end{itemize}
In this setting, Proposition~\ref{prop:general} reduces to a very simple form for $p = \infty$:

\begin{theorem} \label{thm:Linf}
Suppose $f_{t}$ satisfies the above assumptions. If Assumptions 1 and 2 hold for $p = \infty$, then
\begin{align} \label{eq:thm-Linf}
\ml{S}{W} \leq \sum_{t=1}^T d \log \left( 1 + 2 \eta_t L f_{t0}(0) \right).
\end{align}
\end{theorem}

Unlike the bound of Theorem~\ref{thm:gaussian-ml}, the limit of $d$ to infinity here is infinite. However, the bounded-$L_\infty$ assumption is \textit{weaker} than assuming a bounded $L_2$-norm. Moreover, the assumption of having a bounded $L_\infty$-norm is satisfied in~\citep{pichapati2019adaclip} where the authors clipped the gradient in terms of the $L_\infty$-norm, thus ``enforcing'' the assumption. On the other hand, the theorem has an intriguing form as, under standard assumptions, the bound depends on $f_{t0}$ only through $f_{t0}(0)$. This naturally leads to an optimization problem: given a certain constraint on the noise, which distribution $f^\star$ minimizes $f(0)$? The following theorem shows that, if the noise is required to have a bounded variance, then $f^\star$ corresponds to the uniform distribution:

\begin{theorem} \label{thm:opt-noise}
 Let $\mathcal{F}$ be the family of probability densities (over $\mathbb{R}$) satisfying for each $f \in \mathcal{F}$: 
 \begin{enumerate}
 \item $f$ is symmetric around 0.
 \item $f$ is non-increasing over $[0, \infty)$.
 \item ${\rm \mathbf  E}_f [X^2] \leq \sigma^2$.
 \end{enumerate}
Then, the distribution minimizing $f(0)$ over $\mathcal{F}$ is the uniform distribution $\mathcal{U}( -\sigma \sqrt{3}, \sigma \sqrt{3})$.  
 \end{theorem}

That is, uniform noise is optimal in the sense that it minimizes the upper bound in Theorem~\ref{thm:Linf} under bounded variance constraints. The proof of Theorem~\ref{thm:opt-noise} is deferred to Appendix~\ref{app:opt-noise}.

\subsection{Proof of Theorem~\ref{thm:Linf}}
    Since the assumptions of Proposition~\ref{prop:general} hold, then
    \begin{align}
        \ml{S}{W} & \leq \sum_{t=1}^T \log \left( f_t(0) V_\infty(d,\eta_t L) + \int \limits_{\overline{\mathcal{B}_\infty}(0, \eta_t L)} \sup_{x_t \in \mathcal{B}_\infty(0,\eta_{t} L)} f_t(w_t - x_t) \mathrm{d} w_t \right) \\
        & = \sum_{t=1}^T \log \left( (2\eta_t L f_{t0}(0))^d  +  
        \int \limits_{\overline{\mathcal{B}_\infty}(0, \eta_t L)} \prod_{i=1}^d \sup_{ x_{ti}: |x_{ti}| \leq \eta_t L} f_{t0} (w_{ti}-x_{ti}) \mathrm{d} w_t
        \right).
    \end{align}
It remains to show that $h(d,\infty,f_t,\eta_t L)$ (i.e., the second term inside the $\log$ in~\Cref{eq:def-h}) is equal to $(1+2\eta_t L f_{t0}(0))^d -(2\eta_t L f_{t0}(0))^d $. We will derive a recurrence relation for $h$ in terms of $d$. To simplify the notation, we drop the subscript $t$ and ignore the dependence of $h$ on $p=\infty$, $f_t$, and $\eta_t L$, so that we simply write $h(d)$ (and correspondingly, $h_+(d)$, cf.~\Cref{eq:def-h-positive}).

By symmetry, $h(d) = 2^d h_+(d)$. Letting $w^{d-1}:=(w_1,\ldots,w_{d-1})$, we will decompose the integral over $\overline{\mathcal{B}_\infty^d}(0,\eta_t L)$ into two disjoint subsets: 1) $ w^{d-1} \notin \mathcal{B}_\infty^{d-1}(0,\eta_t L)$, in which case $w_d$ can take any value in $\mathbb{R}$, and 2) $w^{d-1} \in \mathcal{B}_\infty^{d-1}(0,\eta_t L)$, in which case $w_d$ must satisfy $|w_d| > \eta_t L$.
\begin{align}
    h_+(d) &  = 
    \int \limits_{\overline{\mathcal{B}^{d-1}_\infty}(0, \eta_t L) \cap A_{d-1} } \prod_{i=1}^{d-1} \sup_{ x_{i}: |x_{i}| \leq \eta_t L} f (w_{i}-x_{i})  \int_{0}^\infty \sup_{x_d: |x_d| \leq \eta_t L} f(w_d - x_d) \mathrm{d} w_d \mathrm{d} w^{d-1}  \label{eq:Linf-messy-1}\\
    & ~ + \int \limits_{{\mathcal{B}^{d-1}_\infty}(0, \eta_t L) \cap A_{d-1} } \prod_{i=1}^{d-1} \sup_{ x_{i}: |x_{i}| \leq \eta_t L} f (w_{i}-x_{i})  \int_{\eta_t L}^\infty \sup_{x_d: |x_d| \leq \eta_t L} f(w_d - x_d) \mathrm{d} w_d \mathrm{d} w^{d-1} \label{eq:Linf-messy-2}
\end{align}
The innermost integral of line~\eqref{eq:Linf-messy-2} is independent of $w^{d-1}$ so that the outer integral is equal to $h_{+}(d-1)$. Similarly, the innermost integral of line~\eqref{eq:Linf-messy-1} is independent of $w^{d-1}$, and the supremum in the outer integral yields $f(0)$ for every $i$. Hence, we get
\begin{align}
    h(d) = \left(1+2\eta_t L f(0) \right) h (d-1)+ (2 \eta_t L f(0))^{d-1}, \label{eq:recurrence-Linf}
\end{align}
the detailed proof of which is deferred to Appendix~\ref{app:recurrence-Linf}. 
Finally, it is straightforward to check that $h(1) =1$, hence $h(d) = (1+2\eta_t L f(0))^d-(2\eta_t L f(0))^d$.



 


 

 
\section{Boundedness in $L_1$-Norm}

In this section, we consider the setting where Assumption 2 holds for $p=1$. By Proposition~\ref{prop:general}, any bound derived for $p=2$ holds for $p=1$ as well. In particular, Theorem~\ref{thm:gaussian-ml} applies so that $\ml{S}{W}$ goes to zero when the noise is Gaussian. Nevertheless, it is possible to compute a semi-closed form directly for $p=1$ (cf. Theorem~\ref{thm:l1-gaussian} below), which would be inherently tighter.

Considering the optimality of Gaussian noise for the $p=2$ case, and the optimality of uniform noise (in the sense discussed above) for $p = \infty$ case, one might wonder if Laplace noise is optimal for the $p=1$ case. We answer this question in the negative, as the limit of the leakage in this case is a non-zero constant (cf. Theorem~\ref{thm:l1-laplace}), as opposed to the zero limit when the noise is Gaussian.  

\subsection{Bound for Laplace noise}
We say $X$ has a Laplace distribution, denoted by $X \sim \mathrm{Lap}(\mu,1/\lambda)$, if its pdf is given by $f(x)= \frac{\lambda}{2}e^{-\lambda |x-\mu|}$ for $x \in \mathbb{R}$, for some $\mu \in \mathbb{R}$ and $\lambda >0$. The corresponding variance is given by $2/\lambda^2$.
\begin{theorem} \label{thm:l1-laplace}
If the boundedness assumptions holds for $p=1$ and 
$\xi_t$ is composed of i.i.d components, each of which is $\sim \mathrm{Lap}(0, \frac{\sigma_t}{\sqrt{2}})$, then
\begin{align} \label{eq:thm-l1-laplace}
\ml{S}{W} \leq  \sum_{t=1}^T \log \left( \frac{V_1 (d,\eta_t L)}{( \sigma_t \sqrt{2})^{d}} +  \sum_{i=0}^{d-1} \frac{(\sigma_t \eta_t L/ \sqrt{2})^i}{ i ! }  \right), 
\end{align} 
where $\displaystyle V_1(d,r)  = \frac{(2r)^d}{ d!}$. Consequently, for fixed $T$,
\begin{align} \label{eq:thm-l1-laplace-limit}
\lim_{d \rightarrow \infty} \ml{S}{W} \leq \sum_{t=1}^T \frac{\sigma_t \eta_t L}{ \sqrt{2}}.
\end{align}
\end{theorem}

\begin{proof}
    We give a high-level description of the proof (as similar techniques have been used in proofs of earlier theorems) and defer the details to Appendix~\ref{app:l1-laplace}.  Since the multivariate Laplace distribution (for i.i.d variables) depends on the $L_1$-norm of the corresponding vector of variables, we need to solve the following problem: given $R >0$ and $w \notin \mathcal{B}_1(0,R)$, compute
    \begin{align} \label{eq:to-solve-B1-L1}
        \inf_{x \in \mathcal{B}_1(0,R)} \| w- x \|_1.
    \end{align}
The closest element in $\mathcal{B}_1(0,R)$ will lie on the hyperplane defining $\mathcal{B}_1$ that is in the same octant as $w$, so the problem reduces to projecting a point on a hyperplane in $L_1$-distance (the proof in the appendix does not follow this argument but arrives at the same conclusion). Then, we need to compute $h(d,1,f_t,\eta_t L)$. We use a similar approach as in the proof of Theorem~\ref{thm:Linf}, that is, we split the integral and derive a recurrence relation.
\end{proof}


\subsection{Bound for Gaussian noise}

Finally, we derive a bound on the induced leakage when the added noise is Gaussian:

\begin{theorem} \label{thm:l1-gaussian}
If the boundedness assumptions holds for $p=1$ and 
$\xi_t \sim \mathcal{N}(0, \sigma^2_t I_d)$, then
\begin{align} \label{eq:thm-l1-gaussian}
     \ml{S}{W} \leq  \sum_{t=1}^T \log \left( \frac{V_1(d,R_t)}{  (2 \pi \sigma^2)^{\frac{d}{2}}}+\frac{(2\eta_t L)^{d-1} (\sigma_t \sqrt{2 d}) }{ (2 \pi \sigma_t^2)^{\frac{d}{2}} ((d-1)!) }   \sum_{i=0}^{d-1} \left( \frac{\sigma_t \sqrt{2 d}}{\eta_t L} \right)^i \Gamma\left(\frac{i+1}{2}\right) \right).
\end{align}
\end{theorem}
~\Cref{thm:l1-gaussian} is tighter than~\Cref{thm:gaussian-ml} for any given $d$ moreover one has, again, that:
\begin{align} 
    \lim_{d \rightarrow \infty} \ml{S}{W} = 0. \label{eq:limitToInfinityL1}
\end{align}
\Cref{eq:limitToInfinityL1} follows from~\Cref{thm:gaussian-ml} and the fact that the bound in Proposition~\ref{prop:general} is increasing in $p$ (cf. discussion below~\Cref{thm:gaussian-ml}).

In order to prove~\Cref{thm:l1-gaussian} one has to solve a problem similar to the one introduced in~\Cref{thm:l1-laplace} (cf. equation~\eqref{eq:to-solve-B1-L1}). However, in this case a different norm is involved: i.e., given $R >0$ and $w \notin \mathcal{B}_1(0,R)$, one has to compute
\begin{align}
    \inf_{x \in \mathcal{B}_1(0,R)} \|w-x\|_2.
\end{align}
Again, one can argue that the point achieving the infimum lies on the hyperplane defining $\mathcal{B}_1$ that is in the same octant as $w$. In other words, the minimizer $x^\star$ is such that the sign of each component is the same sign as the corresponding component of $w$ (and lies on the boundary of $\mathcal{B}_1$). Thus, we are simply projecting a point on a hyperplane. The induced integral is solved by an opportune choice of change of variables.  The details of the proof are given in Appendix~\ref{app:l1-gaussian}.

\newpage 
