# Beyond Uniform Lipschitz Condition in Differentially Private Optimization

Rudrajit Das  Satyen Kale  Zheng Xu  Tong Zhang  Sujay Sanghavi

###### Abstract

Most prior results on differentially private stochastic gradient descent (DP-
SGD) are derived under the simplistic assumption of uniform Lipschitzness,
i.e., the per-sample gradients are uniformly bounded. We generalize uniform
Lipschitzness by assuming that the per-sample gradients have sample-dependent
upper bounds, i.e., per-sample Lipschitz constants, which themselves may be
unbounded. We provide principled guidance on choosing the clip norm in DP-SGD
for convex over-parameterized settings satisfying our general version of
Lipschitzness when the per-sample Lipschitz constants are bounded;
specifically, we recommend tuning the clip norm only till values up to the
minimum per-sample Lipschitz constant. This finds application in the private
training of a softmax layer on top of a deep network pre-trained on public
data. We verify the efficacy of our recommendation via experiments on 8
datasets. Furthermore, we provide new convergence results for DP-SGD on convex
and nonconvex functions when the Lipschitz constants are unbounded but have
bounded moments, i.e., they are heavy-tailed.

Machine Learning, ICML

##  1 Introduction

With the ever-increasing amount of data being used, there is a growing need
for the development of privacy-preserving training schemes for machine
learning (ML) models. Differential privacy (DP) (Dwork et al., 2006) is a
popular privacy-preserving framework that is being incorporated in the
training of ML models. We formally define DP in Definition 3.3, but at a high
level, DP can be guaranteed by adding Gaussian noise, where the noise scale is
determined by the “sensitivity” to an individual’s data. There has been
copious research on private optimization for private training; in this paper,
we focus on DP-SGD (Abadi et al., 2016) which is the default algorithm for
private optimization in practice.

We briefly introduce the problem setting and DP-SGD to facilitate further
discussion (see Section 3 for more details). We consider empirical risk
minimization (ERM) of $f(\bm{w})=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\bm{w})$,
where each $f_{i}:\mathbb{R}^{d}\xrightarrow{}\mathbb{R}$. In every iteration
of DP-SGD (stated in Algorithm 1), the optimizer receives a noise-perturbed
average of the clipped per-sample gradients for performing the update; noise
is added to guarantee differential privacy. Specifically, at iteration $t$,
the optimizer receives
$\bm{g}_{t}=\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)+\bm{\zeta}_{t}$, where $\mathcal{S}_{t}$ is a random
batch of samples formed by picking each sample in $\\{1,\ldots,n\\}$ with
probability $({b}/{n})$,
$\text{clip}(\bm{z},c):=\bm{z}\min(1,{c}/{\|\bm{z}\|})$ for a vector $\bm{z}$,
$\tau$ is the clipping threshold or clip norm, and $\bm{\zeta}_{t}$ is an
isotropic Gaussian random vector whose variance is proportional to $\tau^{2}$
and also depends on the amount of privacy required.

Clipping is employed in DP-SGD to bound the maximum sensitivity of the average
gradient to each sample’s individual gradient, which is required to set the
noise variance. However, clipping can also make $\bm{g}_{t}$ a biased
estimator of $\nabla f(\bm{w}_{t})$, and the amount of bias depends on the
clip norm $\tau$ – the higher we set $\tau$, the lower is the bias, and vice-
versa. As the noise variance is proportional to $\tau^{2}$, there is an
inherent tension between the bias and variance of $\bm{g}_{t}$ due to the clip
norm $\tau$. This raises a natural question - how do we set “good” clip norms
to balance the bias-variance tradeoff?

In order to circumvent the analysis of the clipping bias, most prior
convergence results for private optimization (Bassily et al., 2014, 2019; Wang
et al., 2018, 2019) assume that the loss function is uniformly Lipschitz for
all samples and model parameters, i.e., the per-sample gradients (w.r.t. the
model parameters) have a sample-independent upper bound known as the Lipschitz
constant. Under this assumption, the clip norm is set equal to the Lipschitz
constant resulting in zero bias as no clipping happens. But in practice, such
a choice of clip norm results in very poor performance; see Figure 1 and its
caption. Additionally, uniform Lipschitzness does not even hold for simple
problems like linear regression with Gaussian data, precluding the existence
of a trivial clip norm for analysis.

In this work, we generalize uniform Lipschitzness by instead assuming that the
per-sample gradients have sample-dependent upper bounds, i.e., per-sample
Lipschitz constants, which themselves may be unbounded. Under this generalized
assumption, we provide a theoretically-motivated clip norm selection strategy
for convex settings. Our method finds direct application in the private
training of the softmax layer of pre-trained deep networks which is a popular
and effective scheme for private training (De et al., 2022; Mehta et al.,
2022). In practice, the clip norm is tuned over multiple runs which is not
only computationally inefficient but also increases the privacy cost (Papernot
& Steinke, 2021). So it is desirable to have principled methods for setting
the clip norm to alleviate these two issues. Additionally, we provide novel
convergence results for DP-SGD when the per-sample Lipschitz constants are
heavy-tailed.

Before we state our contributions in detail, we need to briefly introduce the
metric quantifying convergence, which we call the “optimization risk”. Let
$\bm{w}_{\text{priv}}$ be the output of DP-SGD (Alg. 1). If $f$ is convex, the
optimization risk is the expected suboptimality gap, i.e.,
$\mathbb{E}[f(\bm{w}_{\text{priv}})]-\min_{\bm{w}}f(\bm{w})$. If $f$ is
nonconvex, the optimization risk is the expected gradient-norm squared, i.e.
$\mathbb{E}[\|\nabla f(\bm{w}_{\text{priv}})\|^{2}]$. When DP-SGD is
$(\varepsilon,\delta)$-DP (defined in Definition 3.3), our convergence results
are expressed in terms of the following key quantity:

$\varphi:={\sqrt{\nu d\log({1}/{\delta})}}/{n\varepsilon},$ (1)

where $d$ is the dimension of the model parameters, $n$ is the number of
samples, and $\nu$ is an absolute constant. We assume that $n$ is large enough
so that $\varphi<1$, and the number of iterations of DP-SGD is sufficiently
large. We now list our main contributions, and also summarize the main
theoretical results in Tables 1 and 2.

(a) Throughout this work, we generalize uniform Lipschitzness by assuming that
the per-sample gradients have sample-dependent upper bounds, i.e., per-sample
Lipschitz constants, which themselves may be unbounded; we call this
generalized Lipschitzness (4.1).

  * •

In Section 5, we provide a principled clip norm tuning strategy for DP-SGD
under generalized Lipschitzness. Specifically, we focus on convex settings
with near-interpolation like conditions (Asmp. 5.5), i.e.,
$\frac{1}{n}\sum_{i=1}^{n}(f_{i}(\bm{w}^{*})-\min_{\bm{w}}f_{i}(\bm{w}))\approx
0$ where $\bm{w}^{*}=\text{arg min}_{\bm{w}}f(\bm{w})$; over-parameterization
is an example of this. For such cases, we recommend tuning the clip norm only
till values up to the minimum per-sample Lipschitz constant (Remark 5.6), say
$G_{\text{min}}$, based on Theorem 5.4 where we show that the optimization
risk attains the best bound when the clip norm is $\leq G_{\text{min}}$. This
is in contrast to prior theoretical works which set the clip norm equal to the
maximum per-sample Lipschitz constant, say $G_{\text{max}}$, for ease of
analysis.

  * •

Our recommendation for convex settings is of relevance to the private training
of the softmax (i.e., last) layer of deep networks pre-trained on public data.
In Section 5.2, we corroborate our recommendation with experiments on
four111We show results on two more datasets in Appendix A. vision datasets,
viz., Caltech-256 (Griffin et al., 2007), Food-101 (Bossard et al., 2014),
CIFAR-100 and CIFAR-10, and two language datasets, viz., TweetEval Emoji
(Barbieri et al., 2018) and Emotion (Saravia et al., 2018). As an e.g., for
Caltech-256 and Food-101 with $\varepsilon=2$, the test accuracy obtained by
setting the clip norm $\tau=G_{\text{min}}$ is better than that of
$\tau=G_{\text{max}}$ by more than 23% and 11%, respectively.

(b) In Section 6, we provide optimization risk bounds for DP-SGD under
generalized Lipschitzness, without assuming interpolation, when the per-sample
Lipschitz constants have bounded $k^{\text{th}}$ moment, i.e., they are heavy-
tailed (Asmp. 6.1). For private unconstrained convex and smooth nonconvex
optimization under this assumption, we derive risk bounds of
$\mathcal{O}({\varphi^{1-\frac{2}{k+1}}})$ and
$\mathcal{O}({\varphi^{1-\frac{1}{2k-1}}})$, respectively222The seemingly
better result for the nonconvex setting is because of the difference in the
risk metrics between the convex and nonconvex cases.; see Theorems 6.2 and
6.8. Under an additional mild assumption, we improve the risk bound in the
convex case to $\mathcal{O}({\varphi^{1-\frac{1}{k}}})$ and also derive a
matching lower bound, thereby establishing the optimality of DP-SGD in this
case; see 6.4 and Theorems 6.5 and 6.6. These are the first results for
private unconstrained optimization under the heavy-tailed assumption or
anything similar. Our results also imply the optimality of DP-SGD in the
unconstrained convex case under uniform Lipschitzness; see Cor. 6.7. To our
knowledge, this is the first matching lower bound for the unconstrained convex
case under uniform Lipschitzness.

Table 1: Summary of our clip norm selection result (Thm. 5.4) for the convex
case under generalized Lipschitzness (Asmp. 5.1) and interpolation (Asmp.
5.5). $G_{1}$ and $G_{n}$ are the minimum and maximum per-sample Lipschitz
constants as per Asmp. 5.1. In the table, $\alpha^{*}=\alpha(G_{1})\geq 1$,
where $\alpha(G_{1})$ is defined in Definition 5.3, and
$B=\mathcal{O}(\|\bm{w}_{0}-\bm{w}^{*}\|G_{n}\varphi)$, where $\bm{w}_{0}$ is
the initial point, $\bm{w}^{*}$ is a minimizer of $f$ and
$\varphi=\mathcal{O}(\nicefrac{{\sqrt{d\log({1}/{\delta})}}}{{n\varepsilon}})$.

Clip Norm $\tau$ |  Risk Upper Bound when Perfect Interpolation holds ($\Delta(\bm{w}^{*})=0$ in Asmp. 5.5)
---|---
$\in(0,G_{1}]$ (this work) |  ${B}/{{\alpha}^{*}}$ (${\alpha}^{*}\geq 1$)
$\in(G_{1},G_{n})$ (this work) |  $\geq{B}/{\alpha}^{*}$ but $\leq B$
$G_{n}$ (default choice of prior theory) | $B$

Table 2: Summary of optimization risk (OR) bounds. OR is defined in Definition
3.5 and
$\varphi=\mathcal{O}(\nicefrac{{\sqrt{d\log({1}/{\delta})}}}{{n\varepsilon}})<1$.
In 6.1, we assume that the per-sample gradients have sample-dependent upper
bounds with bounded $k^{\text{th}}$ moment ($k>1$). In 6.4, we assume a mild
lower bound on function suboptimality of points far away from the optimum.

Reference | Assumption(s) & Setting | Risk Upper Bound | Matching Lower Bound?
---|---|---|---
Bassily et al. (2014) | Uniform Lipschitz & Convex Constrained | $\mathcal{O}(\varphi)$ | Yes
This work | Uniform Lipschitz & Convex Unconstrained ($\mathcal{W}=\mathbb{R}^{d}$) |  $\mathcal{O}(\varphi)$ (Cor. 6.7) | Yes, for $\delta<e^{-\varepsilon^{2}}$ (Cor. 6.7)
Kamath et al. (2021), Lowy & Razaviyayn (2023)333These two works consider the stochastic optimization setting with $(0,\mathcal{O}(\varepsilon^{2}))$-zCDP and derive bounds for the generalization error. In Appendix I, we show that the same bounds hold for the training error (i.e., OR) in empirical risk minimization with $(\varepsilon,\delta)$-DP. |  6.1 & Convex Constrained | $\mathcal{O}(\varphi^{1-\frac{1}{k}})$ | Yes
This work |  6.1 & Convex Unconstrained |  $\mathcal{O}(\varphi^{1-\frac{2}{k+1}})$ (Thm. 6.2) | ?
This work | Assumptions 6.1, 6.4 & Convex Unconstrained |  $\mathcal{O}(\varphi^{1-\frac{1}{k}})$ (Thm. 6.5) | Yes, for $\delta<e^{-\varepsilon^{2}}$ (Thm. 6.6)
Arora et al. (2022), Tran & Cutkosky (2022)444The $\mathcal{O}(\varphi^{4/3})$ bound is attained by algorithms very different from DP-SGD. For DP-SGD like algorithms, Wang et al. (2018) obtain the best known bound of $\mathcal{O}(\varphi)$. | Uniform Lipschitz & Smooth Nonconvex Unconstrained | $\mathcal{O}(\varphi^{4/3})$ | ?
This work |  6.1 & Smooth Nonconvex Unconstrained |  $\mathcal{O}(\varphi^{1-\frac{1}{2k-1}})$ (Thm. 6.8) | ?

##  2 Related Work

DP-(S)GD with Clipping: Abadi et al. (2016) introduce the famous DP-SGD
algorithm with clipping for differentially private training in practice. There
are some papers analyzing the effect of clipping in DP-(S)GD in different
settings such as Chen et al. (2020); Bu et al. (2021); Song et al. (2021).
However, these works do not provide any practical insights into how to set the
clip norm for DP-SGD, which is a key focus of our work. Related to our focus,
there are some variants of DP-SGD such as Andrew et al. (2019); Du et al.
(2021); Wu et al. (2021) that adaptively change the clip norm and/or noise
variance to improve convergence. However, practitioners typically use a
constant clip norm which does not change with the iteration number, and so we
only focus on how to set a constant clip norm used in vanilla DP-SGD (Abadi et
al., 2016).

Differentially Private Optimization under Uniform Lipschitzness: There are
several papers on private empirical risk minimization (ERM) (Chaudhuri &
Monteleoni, 2008; Chaudhuri et al., 2011; Kifer et al., 2012; Song et al.,
2013; Duchi et al., 2013; Bassily et al., 2014; Talwar et al., 2014, 2015; Wu
et al., 2017; Iyengar et al., 2019) and private stochastic optimization
(Bassily et al., 2014, 2019; Feldman et al., 2020; Asi et al., 2021a, b;
Kulkarni et al., 2021; Bassily et al., 2021) for convex Lipschitz objectives
within a bounded set. The optimal risk bound for private constrained convex
ERM over a bounded set in the Lipschitz case is $\mathcal{O}(\varphi)$
(Bassily et al., 2014). Zhang et al. (2017); Wang et al. (2018, 2019); Arora
et al. (2022); Tran & Cutkosky (2022) derive convergence results for private
unconstrained nonconvex ERM with Lipschitz and smooth objectives. Wang et al.
(2018, 2019) obtain a risk bound of $\mathcal{O}(\varphi)$ for DP-SGD like
algorithms. Arora et al. (2022); Tran & Cutkosky (2022) obtain an improved
bound of $\mathcal{O}(\varphi^{4/3})$ but with more advanced algorithms. These
papers simply clip the gradients up to the Lipschitz constant, and do not
explore the effect of clipping to smaller values. But as shown in Fig. 1, such
a choice of clip norm performs poorly in practice and besides, uniform
Lipschitzness may not always hold.

Bounded Gradient Moments: Our assumption of per-sample Lipschitz constants
having bounded $k^{\text{th}}$ moment, i.e. 6.1, generalizes the “heavy-
tailed” assumption of Wang et al. (2020); Hu et al. (2021) for private
stochastic convex optimization (SCO) with bounded second moment. The bounded
$k^{\text{th}}$ moment assumption has been also analyzed in Kamath et al.
(2021); Lowy & Razaviyayn (2023) for private SCO. However, these papers focus
only on constrained convex optimization. In practice, however, unconstrained
minimization is usually performed while training ML models. In this paper, we
focus on the more practical and harder (w.r.t. analysis) case of private
unconstrained convex as well as nonconvex optimization (which has not been
considered before) under this assumption. We discuss the assumptions of these
papers in more detail after 6.1. Note that none of these papers have any
result like our theoretically-motivated clip norm selection method for use in
practice with our level of experimental verification.

##  3 Preliminaries

Notation: Vectors and matrices are in bold face. For any $n\in\mathbb{N}$, the
set $\\{1,\ldots,n\\}$ is denoted by $[n]$, and the uniform distribution over
$\\{0,\ldots,n\\}$ is denoted by $\text{unif}[0,n]$. $\|.\|$ denotes the
$\ell_{2}$ norm throughout this work. For a function $h$ and any point
$\bm{x}\in\mathcal{X}$, the “suboptimality gap” (at $\bm{x}$) over
$\mathcal{X}$ means
$h(\bm{x})-\min_{\bm{x}^{\prime}\in\mathcal{X}}h(\bm{x}^{\prime})$. The
function
$\text{clip}(.,.):\mathbb{R}^{d}\times\mathbb{R}^{+}\xrightarrow{}\mathbb{R}^{d}$
is defined as:

$\text{clip}(\bm{z},c):=\bm{z}\min(1,{c}/{\|\bm{z}\|}).$ (2)

######  Definition 3.1 (Lipschitz).

$h:\mathcal{T}\xrightarrow{}\mathbb{R}$ is to said to be $G$-Lipschitz if
$\sup_{\bm{t}\in\mathcal{T}}\|\nabla h(\bm{t})\|\leq G$.

######  Definition 3.2 (Smooth).

$h:\mathcal{T}\xrightarrow{}\mathbb{R}$ is to said to be $L$-smooth if for all
$\bm{t},\bm{t}^{\prime}\in\mathcal{T}$, $\|\nabla h(\bm{t})-\nabla
h(\bm{t}^{\prime})\|\leq L\|\bm{t}-\bm{t}^{\prime}\|$.

######  Definition 3.3 (Differential Privacy (Dwork et al., 2014)).

Suppose each sample $\in\mathcal{S}$. Given a query function
$h:\mathcal{S}^{n}\xrightarrow{}\mathcal{X}$, a randomized mechanism
$\mathcal{M}:\mathcal{X}\xrightarrow{}\mathcal{Y}$ is said to be
$(\varepsilon,\delta)$-DP if for any two datasets
$\mathcal{D},\mathcal{D}^{\prime}\in\mathcal{S}^{n}$ differing in exactly one
sample and for any measurable $\mathcal{R}\in\mathcal{Y}$,
$\mathbb{P}(\mathcal{M}(h({D}))\in\mathcal{R})\leq
e^{\varepsilon}\mathbb{P}(\mathcal{M}(h({D}^{\prime}))\in\mathcal{R})+\delta$.

The customary way to guarantee DP is to add zero-mean Gaussian noise to the
output of $h(.)$ above; this is known as the Gaussian mechanism (Dwork et al.,
2014).

Problem Setting and DP-SGD: Suppose we are given a dataset of $n$ i.i.d.
samples (features and corresponding labels)
$\mathcal{Z}:=\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{n}$ drawn from some distribution
$\mathcal{D}$. We wish to train a model, parameterized by
$\bm{w}\in\mathcal{W}\subseteq\mathbb{R}^{d}$, on the data via DP-SGD such
that the whole training process is $(\varepsilon,\delta)$-DP. We use a loss
function $\ell(\bm{w},.)$ (for e.g., the squared loss or cross-entropy loss
with some regularization possibly) to learn the model. Let
$f_{i}(\bm{w}):=\ell(\bm{w},\bm{x}_{i},y_{i})$; then, we are trying to
privately minimize

$f(\bm{w})=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\bm{w}).$ (3)

DP-SGD is summarized in Algorithm 1. Gradient clipping is employed to bound
the sensitivity of the average gradient to each sample’s individual gradient.
Gaussian noise is added to guarantee DP. In Abadi et al. (2016), the last
iterate $\bm{w}_{T}$ is returned; in contrast, we return a random iterate. We
now specify the value of $\sigma_{n}^{2}$ required to make Alg. 1
$(\varepsilon,\delta)$-DP using the moments accountant method of Abadi et al.
(2016); we provide a short proof in Appendix G.

######  Theorem 3.4 (Moments Accountant (Abadi et al., 2016)).

For $\varepsilon<\mathcal{O}\big{(}\frac{b^{2}}{n^{2}}T\big{)}$, Algorithm 1
is $(\varepsilon,\delta)$-DP for $\sigma_{n}^{2}=\frac{\nu
T\log(\frac{1}{\delta})\tau^{2}}{n^{2}\varepsilon^{2}}$, where $\nu$ is an
absolute constant.

Algorithm 1 DP-SGD (Abadi et al., 2016)

1: Input: Domain of parameters $\mathcal{W}$, initial point
$\bm{w}_{0}\in\mathcal{W}$, number of iterations $T$, learning rates
$\\{\eta_{t}\\}_{t=0}^{T-1}$, sample selection probability $(b/n)$, clip norm
$\tau$ and noise variance $\sigma_{n}^{2}$.

2: for $t=0,\dots,T-1$ do

3: Form a random mini-batch $\mathcal{S}_{t}$ by picking each sample
independently of the others with probability $b/n$.

4: Get the noisy mini-batch stochastic gradient
$\bm{g}_{t}=\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)+\bm{\zeta}_{t}$, where
$\bm{\zeta}_{t}\sim\mathcal{N}(\vec{0}_{d},\sigma_{n}^{2}\text{I}_{d})$ and
$\text{clip}()$ is defined in (2).

5: Let $\bm{z}_{t+1}\xleftarrow{}\bm{w}_{t}-\eta_{t}\bm{g}_{t}$. Update
$\bm{w}_{t+1}\xleftarrow{}\Pi_{\mathcal{W}}(\bm{z}_{t+1})$, where
$\Pi_{\mathcal{W}}(\bm{z})$ is the projection of $\bm{z}$ onto $\mathcal{W}$.
(Note that $\Pi_{\mathbb{R}^{d}}(\bm{z})=\bm{z}$.)

6: end for

7: Return $\bm{w}_{\text{priv}}=\bm{w}_{\widehat{t}}$, where
$\widehat{t}\sim\text{unif}[0,T-1]$.

Finally, we define our convergence metric for DP-SGD which we call the
optimization risk.

######  Definition 3.5 (Optimization Risk).

Recall $\bm{w}_{\text{priv}}$ is the output of DP-SGD (Alg. 1) after $T$
iterations.
(i) Suppose $f$ is convex. We define the convex optimization risk as
$\textup{OR}(T):=\big{(}\mathbb{E}[f(\bm{w}_{\text{priv}})]-f(\bm{w}^{*})\big{)}$,
where $\bm{w}^{*}\in\text{argmin}_{\bm{w}\in\mathcal{W}}f(\bm{w})$.

(ii) Suppose $f$ is nonconvex & $\mathcal{W}=\mathbb{R}^{d}$. We define the
nonconvex optimization risk as $\textup{OR}(T):=\mathbb{E}[\|\nabla
f(\bm{w}_{\text{priv}})\|^{2}]$.

Note that the expectations above are w.r.t. the randomness of Algorithm 1 (in
particular, conditioned on the dataset $\mathcal{Z}$).

Also recall the key quantity $\varphi=\frac{\sqrt{\nu
d\log({1}/{\delta})}}{n\varepsilon}<1$ defined in Equation 1. Our bounds on
the optimization risk will be in terms of $\varphi$. For brevity, we only
present abridged versions of our results in the main paper and provide the
full versions and proofs in the Appendix.

##  4 Generalized Lipschitzness

Here we introduce our proposed generalization to the commonly used uniform
Lipschitzness assumption.

######  Assumption 4.1 (Generalized Lipschitzness).

For any $\bm{w}\in\mathcal{W}$ and $(\bm{x},y)\sim\mathcal{D}$, the following
holds for some sample-dependent function $G(\bm{x},y)$:

$\|\nabla_{\bm{w}}\ell(\bm{w},\bm{x},y)\|\leq G(\bm{x},y),$

where $\ell$ is our loss function (mentioned before Equation 3). We call
$G(\bm{x},y)$ the “per-sample Lipschitz constant”.555This assumption extends
to non-differentiable functions by replacing the gradient with sub-gradient.

Note that we are not imposing the condition that $G(\bm{x},y)$ be itself
bounded for all $(\bm{x},y)$. In fact, if we do impose that, then we recover
uniform Lipschitzness. We now provide an important example where generalized
Lipschitzness holds.

Logistic regression: Consider doing logistic regression for multi-class
classification with the cross-entropy loss, where $m$ is the number of
classes. Suppose $\bm{x}\sim\mathcal{F}$ (with a ‘1’ appended to account for
the bias term) is the feature and $y\in[m]$ is the corresponding class number.
In Appendix D, we show that
$\|\nabla\ell_{\bm{w}}(\bm{w},\bm{x},y)\|\leq\sqrt{2}\|\bm{x}\|$. Thus, 4.1
holds with $G(\bm{x},y)=\sqrt{2}\|\bm{x}\|$ for any $\mathcal{W}$.

##  5 Clip Norm Selection for DP-SGD under Generalized Lipschitzness

Here, we will provide a principled strategy to select the constant clip norm
$\tau$ (which does not change across iterations) in DP-SGD (Algorithm 1) under
generalized Lipschitzness when the maximum per-sample Lipschitz constant is
bounded, i.e., uniform Lipschitzness holds. To that end, we assume the
following.

######  Assumption 5.1.

4.1 holds for the dataset $\mathcal{Z}=\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{n}$
that we receive. Let $G_{i}=G(\bm{x}_{i},y_{i})$ for $i\in[n]$. Also, without
loss of generality, the sample indices are arranged so that
$0<G_{1}<\ldots<G_{n}<\infty$666We assume strict inequalities here because the
probability measure of equality holding is zero. Also, we assume $G_{1}>0$, as
otherwise $f_{1}$ is a constant function which is trivially minimized
everywhere, and we can minimize $\frac{1}{n-1}\sum_{i=2}^{n}f_{i}(\bm{w})$
instead..

Thus, $\\{G_{i}\\}_{i=1}^{n}$ are the per-sample Lipschitz constants for the
dataset $\mathcal{Z}$. For e.g., logistic regression with cross-entropy loss
satisfies 5.1 with $G_{i}=\sqrt{2}\|\bm{x}_{i}\|$ (see discussion on logistic
regression after 4.1).

Under 5.1, if we follow the approach of prior theoretical works such as
Bassily et al. (2014), then we would choose $G_{n}$ as the clip norm $\tau$ –
this is associated with zero bias (as no actual clipping occurs) but high
noise variance, yielding a risk bound of $\mathcal{O}(G_{n}\varphi)$ in the
convex case. While the dependence on $\varphi$ is tight (Bassily et al.,
2014), it is not clear if $\tau=G_{n}$ leads to the best constant factors in
the risk bound – which is what makes a difference in practice. Using Thm. 5.4
of this work, we show that the best constant factors are obtained by choosing
$\tau\leq G_{1}$ in convex problems with near-interpolation like conditions
(i.e., the training data can be almost perfectly fitted) while retaining the
$\mathcal{O}(G_{n}\varphi)$ dependence. This is consistent with experiments in
Section 5.2, where clip norms $\leq G_{1}$ perform the best. Intuitively, this
happens because the high noise variance associated with large clip norms is
more detrimental to convergence than the bias associated with small clip
norms. Let us now talk about this result in more detail.

###  5.1 Convex Case

The results here are for a general convex constraint set $\mathcal{W}$ which
can be $\mathbb{R}^{d}$ too. Before we can state our result, we need to
introduce some definitions first. Let $\Psi:=\text{arg
min}_{\bm{w}\in\mathcal{W}}f(\bm{w})$ and
$f_{i}^{*}=\min_{\bm{w}\in\mathcal{W}}f_{i}(\bm{w})$.

######  Definition 5.2.

For any $\bm{w}^{*}\in\Psi$, define
$\Delta(\bm{w}^{*}):=\frac{1}{n}\sum_{i\in[n]}(f_{i}(\bm{w}^{*})-f_{i}^{*})$.

######  Definition 5.3.

Suppose Assumption 5.1 holds. For clip norm $\tau\in(0,G_{n}]$, define:

$\alpha(\tau):=\inf_{\bm{w}\in\mathcal{W}\setminus\Psi}\frac{\frac{1}{n}\sum_{i\in[n]}\min\big{(}\frac{1}{\tau},\frac{1}{G_{i}}\big{)}\big{(}{f_{i}(\bm{w})-f_{i}^{*}}\big{)}}{\frac{1}{n}\sum_{i\in[n]}\frac{f_{i}(\bm{w})-f_{i}^{*}}{G_{n}}}.$

Note that:
(i) $\alpha(\tau)\geq 1$ for all $\tau\in(0,G_{n}]$ and $\alpha(G_{n})=1$.
(ii) $\alpha(\tau)$ is a non-increasing function of $\tau$.
(iii) $\alpha(\tau)=\alpha(G_{1})$ for all $\tau\in(0,G_{1}]$.
(iv) $\alpha(G_{1})$ is strictly greater than 1 unless there exists a
$\widetilde{\bm{w}}^{\ast}$ such that $\widetilde{\bm{w}}^{\ast}$ is a
minimizer of $\\{f_{i}\\}_{i=1}^{n-1}$ but not of $f_{n}$.
(v) $\frac{G_{n}}{\tau\alpha(\tau)}\geq 1$ for all $\tau\in(0,G_{n}]$.
(vi) $\frac{G_{n}}{\tau\alpha(\tau)}$ is a non-increasing function of $\tau$.

Let us see why $\alpha(\tau)\geq 1$ in Definition 5.3. By definition,
$f_{i}(\bm{w})-f_{i}^{*}\geq 0$ for all $\bm{w}\in\mathcal{W}$. Now since
$G_{1}<\ldots<G_{n}$ (as per 5.1) and $\tau\leq G_{n}$, we have that:

$\min\Big{(}\frac{1}{\tau},\frac{1}{G_{i}}\Big{)}\big{(}{f_{i}(\bm{w})-f_{i}^{*}}\big{)}\geq\frac{f_{i}(\bm{w})-f_{i}^{*}}{G_{n}}\text{
}\forall i\in[n].$ (4)

Thus, $\alpha(\tau)\geq 1$ for all $\tau\leq G_{n}$. (ii) and (iii) are easy
to verify using properties of $\min()$. Let us now discuss why (iv) must be
true. For $\tau=G_{1}$, the only way equality will hold in Equation 4 for some
$\bm{w}\notin\Psi$ is if $f_{i}(\bm{w})=f_{i}^{*}$ $\forall$ $i\in[n-1]$ but
$f_{n}(\bm{w})>f_{n}^{*}$; (iv) follows from this. (v) and (vi) can be checked
by just writing out the expression for $\frac{G_{n}}{\tau\alpha(\tau)}$ and
then using properties of $\min()$. We are now ready to present our result for
the convex case.

######  Theorem 5.4 (Convex Case).

Suppose each $f_{i}$ is convex, $\mathcal{W}$ is a convex set (which can be
$\mathbb{R}^{d}$) and Assumption 5.1 holds. Fix some $C>0$. In Alg. 1, set
$T=\frac{1}{3\varphi^{2}}$ and $\eta_{t}=\frac{3C\varphi}{2\tau}$ $\forall$
$t$ for clip norm $\tau$. Then, DP-SGD has the following optimization risk
bound as a function of $\tau\in(0,G_{n}]$:

$\textup{OR}(T)\leq\underbrace{\frac{1}{\alpha(\tau)}\Bigg{(}\bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+2C\bigg{)}G_{n}\varphi\Bigg{)}}_{\textup{(A)}}\\\
+\underbrace{\Bigg{(}\frac{G_{n}}{\tau\alpha(\tau)}-1\Bigg{)}{\Delta(\bm{w}^{*})}}_{\textup{(B)}},$
(5)

where $\Delta(\bm{w}^{*})\geq 0$ and $\alpha(\tau)\geq 1$ are as defined in
Definitions 5.2 and 5.3, respectively.

In Equation 5, term (A) is a non-decreasing function of $\tau$; this follows
from (ii) in Definition 5.3. But term (B) $\geq 0$ is a non-increasing
function of $\tau$; this follows from (v) and (vi) in Definition 5.3. Thus,
increasing $\tau$ increases (A) but reduces (B), and vice-versa. So in
general, there is a tradeoff between the values of (A) and (B) while setting
$\tau$. To provide a recommendation for the choice of $\tau$, we shall focus
on a commonly occurring scenario.

Interpolation: Modern over-parameterized ML models are able to perfectly fit
all the training data (Zhang et al., 2021; Ma et al., 2018). In such cases, it
is reasonable to make the following relaxed interpolation assumption (based on
Assumption 1 of Ma et al. (2018)).

######  Assumption 5.5 (Relaxed Interpolation).

There exists some
$\bm{w}^{*}\in\textup{argmin}_{\bm{w}\in\mathcal{W}}f(\bm{w})$ such that
$\Delta(\bm{w}^{*})=\frac{1}{n}\sum_{i\in[n]}(f_{i}(\bm{w}^{*})-f_{i}^{*})\approx
0$.

Assumption 1 of Ma et al. (2018) would imply the existence of some
$\bm{w}^{*}\in\textup{argmin}_{\bm{w}\in\mathcal{W}}f(\bm{w})$ such that
$\Delta(\bm{w}^{*})=0$ (as
$\bm{w}^{*}\in\textup{argmin}_{\bm{w}\in\mathcal{W}}f_{i}(\bm{w})$ $\forall$
$i\in[n]$, per their assumption). One can expect 5.5 to hold for separable
classification problems even without over-parameterization.

Under 5.5, the dominant term in the risk bound of Theorem 5.4 (Eq. (5)) would
be (A). As discussed previously, (A) is a non-decreasing function of $\tau$.
Thus, the lowest risk bound in Equation 5 is obtained for $\tau\in(0,G_{1}]$.
Also recall that $\alpha(\tau)=\alpha(G_{1})$ $\forall\text{
}\tau\in(0,G_{1}]$ (see (iii) in Definition 5.3). Since $\alpha(G_{n})=1$,
there is an $\alpha(G_{1})$-fold improvement in the risk bound with $\tau\leq
G_{1}$ compared to the naive choice of $\tau=G_{n}$ when
$\Delta(\bm{w}^{*})=0$.

######  Remark 5.6 (Recommendation).

For settings where interpolation holds (such as over-parameterization), we
recommend tuning the clip norm only till values up to the minimum per-sample
Lipschitz constant.

We assume that we have some prior estimate of the minimum Lipschitz constant,
just like prior works on uniform Lipschitzness assume that the maximum
Lipschitz constant is known. For e.g., it can be estimated privately by
applying the Report Noisy Max method (Dwork et al., 2014) on the negative
Lipschitz constants.

###  5.2 Empirical Results

We consider the base problem of private multinomial logistic regression (a
convex problem satisfying Asmp. 5.1) to corroborate our theory and
recommendation. But we focus on the more powerful application of privately
training (only) the last (softmax) layer of deep networks pre-trained on
public data which is equivalent to performing logistic regression with
features being the previous layer’s outputs. Training a softmax layer over
pre-trained networks is a popular and effective scheme for private training
(De et al., 2022; Mehta et al., 2022). This is because fine-tuning all the
layers may not significantly improve performance but the extra parameters
increase the privacy cost. In addition, training only the last layer is
computationally much cheaper than fine-tuning all the layers with DP-SGD (due
to per-sample clipping).

Our experiments here are conducted on four vision datasets available in
Torchvision, viz., Caltech-256 with 257 classes, Food-101 with 101 classes,
CIFAR-100 with 100 classes and CIFAR-10 with 10 classes, and two language
datasets available in Hugging Face, viz., TweetEval Emoji with 20 classes and
Emotion with 6 classes. For Caltech-256 and Food-101 (resp., CIFAR-100 and
CIFAR-10), we use 512-dimensional features obtained from the pre-softmax layer
of a pre-trained ResNet-34 (resp., ResNet-18) model on ImageNet for logistic
regression, which is equivalent to training the last (i.e., softmax) layer of
a pre-trained ResNet-34 (resp., ResNet-18) model. For the language datasets,
we use 768-dimensional features obtained from a pre-trained DistilBERT model
(Sanh et al., 2019) for logistic regression, which is the same as training a
linear layer on top of a pre-trained DistilBERT model. As mentioned after 5.1,
the per-sample Lipschitz constant is equal to $\sqrt{2}$ times the norm of the
sample’s feature vector (with a ‘1’ appended to incorporate the bias term). We
consider three privacy levels - $(2,10^{-5})$-DP, $(4,10^{-5})$-DP and
$(6,10^{-5})$-DP, with batch size = 500. We test several values of the clip
norm $\tau$, viz., the $0^{\text{th}}$, $10^{\text{th}}$, $20^{\text{th}}$,
$40^{\text{th}}$, $80^{\text{th}}$ and $100^{\text{th}}$ percentile of the
per-sample Lipschitz constants (as well as some values smaller than the
$0^{\text{th}}$ percentile). Note that $G_{1}$ and $G_{n}$ correspond to the
$0^{\text{th}}$ and $100^{\text{th}}$ percentiles, respectively. For each
value of $\tau$, we tune over several values of the constant learning rate
$\eta$, viz., $\\{0.0001,0.0003,0.0006,0.001,0.003,0.006,0.01,0.03,\\\
0.06,0.1,0.3,0.6,1,3,6,10\\}$. PyTorch’s Opacus library (Yousefpour et al.,
2021) is used for private training.

In Figure 1, we plot the best test accuracy obtained for different values of
$\tau$ (by tuning over $\eta$) averaged over the last 5 epochs and across 3
different runs. The figure caption discusses the results. The exact accuracy
values are listed in Appendix B. Also, in Appendix A, we show empirical
results on two more datasets, viz., EMNIST and Fashion-MNIST.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 1: Average test accuracy (depicted by the blobs) $\pm$ 1 standard
deviation (depicted by the bars around the blobs) in the last 5 epochs for
different values of clip norm $\tau$. “%” in the x-axis stands for percentile.
Observe that clip norms $\leq G_{1}$ ($0^{\text{th}}$ percentile or minimum of
per-sample Lipschitz constants) generally perform better than clip norms
$>G_{1}$. Specifically, the performance with $\tau=G_{1}$ is significantly
better than that with $\tau=G_{n}$ ($100^{\text{th}}$ percentile or maximum).
Concretely, for Caltech-256 and Food-101 (datasets with the largest no. of
classes), in the case of $\varepsilon=2$, the mean accuracy with $\tau=G_{1}$
is better than that with $\tau=G_{n}$ by $>$ 23% and 11%, respectively; the
corresponding improvement in the case of $\varepsilon=4$ is $>$ 15% and 7.5%,
respectively. These observations are consistent with our theory and
recommendation in Section 5.1.

Now that we have corroborated our insight from Section 5.1 that clip norms
$\leq$ $G_{1}$ yield the best performance, we shall show some results when
$G_{1}$ is first estimated privately using the Report Noisy Max method
(applied on the negative Lipschitz constants) and then used in DP-SGD as the
clip norm. We abbreviate the Report Noisy Max method as RNMM subsequently. We
show results for the first three datasets in Figure 1, viz., Caltech-256,
Food-101 and CIFAR-100. We set $\varepsilon=0.3$ for RNMM and
$\varepsilon=\\{1.7,3.7,5.7\\}$ for DP-SGD so that the total privacy budget is
$\varepsilon=\\{2,4,6\\}$ for which we showed results earlier without RNMM
(where we did not estimate $G_{1}$ privately).777We did not optimize the
splitting of privacy budget between RNMM and DP-SGD; this is something that
can be investigated in future work. Table 3 compares the results with and
without RNMM. The table caption discusses the results.

Table 3: Average test accuracy $\pm$ 1 standard deviation in the last 5 epochs
(i) with and (ii) without RNMM as described in the last paragraph of Section
5.2; the latter is the best accuracy (w.r.t. the clip norm) among the results
in Figure 1 (which are without RNMM). Note that the difference in accuracy
with and without RNMM reduces as $\varepsilon$ increases. Specifically, for
$\varepsilon=\\{4,6\\}$, RNMM does not harm performance too much.

Dataset |  $\varepsilon=2$ w/ RNMM |  $\varepsilon=2$ w/o RNMM |  $\varepsilon=4$ w/ RNMM |  $\varepsilon=4$ w/o RNMM |  $\varepsilon=6$ w/ RNMM |  $\varepsilon=6$ w/o RNMM
---|---|---|---|---|---|---
Caltech-256 | $70.03\pm 0.66$ | $74.03\pm 0.47$ | $78.27\pm 0.05$ | $79.00\pm 0.04$ | $79.53\pm 0.07$ | $80.50\pm 0.04$
Food-101 | $45.84\pm 2.00$ | $49.26\pm 1.00$ | $54.69\pm 0.14$ | $54.85\pm 0.14$ | $56.30\pm 0.12$ | $56.67\pm 0.10$
CIFAR-100 | $52.89\pm 1.02$ | $55.10\pm 0.26$ | $60.19\pm 0.09$ | $60.35\pm 0.13$ | $60.89\pm 0.04$ | $61.16\pm 0.11$

##  6 Convergence of DP-SGD under Heavy-Tailed Lipschitz Constants

When uniform Lipschitzness holds, the optimization risk is
$\mathcal{O}(\varphi)$ in the convex constrained case (Bassily et al., 2014)
as well as the smooth nonconvex unconstrained case (Wang et al., 2018). In
this section, we shall quantify the optimization risk under generalized
Lipschitzness (4.1) with the relaxation of the per-sample Lipschitz constants
being heavy-tailed, instead of being bounded; we do not assume interpolation
here. More specifically, we assume that the per-sample Lipschitz constants
have bounded $k^{\text{th}}$ uncentered moment, for some $k>1$, w.r.t. the
distribution $\mathcal{D}$. This is formally stated next.

######  Assumption 6.1 (Bounded $k^{\text{th}}$ Moment).

Suppose 4.1 holds. For some $k>1$ and $G>0$, we have:

$\Big{(}\mathbb{E}_{(\bm{x},y)\sim\mathcal{D}}\Big{[}\big{(}G(\bm{x},y)\big{)}^{k}\Big{]}\Big{)}^{1/k}\leq
G.$

Let us revisit the logistic regression example that we discussed after 4.1 to
see why 6.1 is weaker than uniform Lipschitzness. We saw that 4.1 holds with
$G(\bm{x},y)=\sqrt{2}\|\bm{x}\|$ here. Now, if the feature distribution
$\mathcal{F}$ is such that its support includes unbounded vectors but
$\mathbb{E}_{\mathcal{F}}[\|\bm{x}\|^{p}]\leq G_{\mathcal{F}}^{p}<\infty$ for
some $p>1$, then 6.1 holds here for $k=p$ and $G=\sqrt{2}G_{\mathcal{F}}$ but
uniform Lipschitzness does not hold. However, if the support of $\mathcal{F}$
includes only bounded vectors, then both 6.1 and uniform Lipschitzness hold.
Also note that uniform Lipschitzness is a special case of 6.1 with $k=\infty$
and a finite $G$.

6.1888This is of significance even in non-private optimization; for e.g.,
Zhang et al. (2020) show that the gradients of Transformer models such as BERT
are heavy-tailed. is similar to the bounded moment assumption made in Wang et
al. (2020); Kamath et al. (2021); Lowy & Razaviyayn (2023) for private
stochastic convex optimization (SCO). But Wang et al. (2020); Kamath et al.
(2021) assume coordinate-wise bounded moments which we do not, Wang et al.
(2020) only consider $k=2$ and Kamath et al. (2021) assume bounded centered
(around the mean) moment. All these papers provide results for the convex case
within a bounded convex set (i.e., $\mathcal{W}$ is bounded); we shall focus
on the unconstrained (i.e., $\mathcal{W}=\mathbb{R}^{d}$) convex case here,
which is more practical and harder (w.r.t. analysis). For completeness, we
include a result for ERM in the constrained convex case in Appendix I which
matches the bound of Kamath et al. (2021) for SCO. Moreover, we also present a
result for the unconstrained smooth nonconvex case; these works do not provide
any results for the smooth nonconvex case.

Before we present our results for the unconstrained convex case, let us first
discuss the main technical difficulty compared to the constrained convex case.
The overall optimization bias in the convex case depends on the bias in mean
gradient estimation induced due to clipping as well as on the distance of the
current point ($\bm{w}_{t}$) from the optimal point ($\bm{w}^{*}$), i.e.,
$\|\bm{w}_{t}-\bm{w}^{*}\|$ at iteration $t$. In the constrained convex case,
$\|\bm{w}_{t}-\bm{w}^{*}\|$ can be easily bounded by the diameter of the
constraint set. However, in the unconstrained case, bounding
$\|\bm{w}_{t}-\bm{w}^{*}\|$ needs extra work; surprisingly, this has not been
analyzed in prior work on DP-SGD. Now, we present our result under 6.1 in the
unconstrained convex case.

######  Theorem 6.2 (Unconstrained Convex Case).

Suppose 6.1 holds, $f$ is convex and $\mathcal{W}=\mathbb{R}^{d}$. Fix some
$\gamma\in(0,1)$ and $C>0$. In Algorithm 1, set $T={\varphi^{-2}}$,
$\tau=\mathcal{O}\big{(}{G}\gamma^{-\frac{1}{k}}\varphi^{-\frac{2}{k+1}}\big{)}$
and
$\eta_{t}=\mathcal{O}\big{(}C\gamma^{\frac{1}{k}}G^{-1}\varphi^{1+\frac{2}{k+1}}\big{)}$
for all $t<T$. Then with a probability of at least $(1-\gamma)$ which is
w.r.t. the random dataset $\mathcal{Z}$ that we obtain, DP-SGD (Algorithm 1)
has the following guarantee:

$\textup{OR}(T)\leq\mathcal{O}\Bigg{(}\frac{G}{\gamma^{1/k}}\Bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+C\Bigg{)}\Bigg{)}{\varphi^{(1-\frac{2}{k+1})}}.$

######  Remark 6.3 (Comparison with prior results).

As per Thm. 6.2, the optimization risk is
$\mathcal{O}(\varphi^{1-{\frac{2}{k+1}}})$ in the the bounded $k^{\text{th}}$
moment unconstrained convex case. In comparison, the risk is
$\mathcal{O}(\varphi^{1-{\frac{1}{k}}})$ in the bounded $k^{\text{th}}$ moment
constrained convex case as per Thm. I.1 in Appendix I, and
$\mathcal{O}(\varphi)$ in the uniform Lipschitz convex case (Bassily et al.,
2014).

The difference in the risk bound between the constrained and unconstrained
cases arises because $\|\bm{w}_{t}-\bm{w}^{*}\|=\mathcal{O}(1)$ (w.r.t.
$\varphi$) in the constrained case but our bound for
$\|\bm{w}_{t}-\bm{w}^{*}\|$ in the unconstrained case depends on $\varphi$. If
one is able to improve this bound for the unconstrained case, then the risk
for the unconstrained case will also improve; but doing so in the absence of
any other assumption seems difficult.

Under a mild additional assumption, we are able to improve the risk bound to
$\mathcal{O}(\varphi^{1-\frac{1}{k}})$ in the unconstrained case, thereby
matching the result in the constrained case. We present this extra assumption
first, followed by the result.

######  Assumption 6.4.

For any $\bm{w}$ s.t. $\|\bm{w}-\bm{w}^{*}\|>D=\mathcal{O}(1)$, where
$\bm{w}^{*}\in\text{arg min}_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})$:

$f(\bm{w})-f(\bm{w}^{*})>\Big{(}{16\varphi^{1-\frac{1}{k}}{G}}\Big{)}\|\bm{w}-\bm{w}^{*}\|.$
(6)

For large $n$ (our regime), $\varphi$ is small; thus,
${16\varphi^{(1-{1}/{k})}{G}}$ is also small in comparison to the average
Lipschitz constant $=\mathcal{O}(G)$ and so, assuming Equation 6 for points
far away from the optimum is reasonable. Besides, an assumption similar to
6.4, known as sharpness (or the Łojasiewicz inequality), has been used in
prior optimization literature (Polyak, 1979; Burke & Ferris, 1993; Bolte et
al., 2017; Roulet & d’Aspremont, 2017; Davis et al., 2018). We provide an
example for 6.4 in Appendix E.

######  Theorem 6.5 (Unconstrained Convex Case Under 6.4).

Suppose Assumptions 6.1 and 6.4 hold, $f$ is convex and
$\mathcal{W}=\mathbb{R}^{d}$. Fix some $C>0$. In Algorithm 1, set
$T=\varphi^{-2}$, $\tau=\mathcal{O}\big{(}G\varphi^{-\frac{1}{k}}\big{)}$ and
$\eta_{t}=\mathcal{O}\big{(}CG^{-1}\varphi^{1+\frac{1}{k}}\big{)}$ for all
$t<T$. Then with a probability of at least $3/4$ which is w.r.t. the random
dataset $\mathcal{Z}$ that we obtain, DP-SGD (Alg. 1) has the following
improved guarantee:

$\textup{OR}(T)\leq\mathcal{O}\Bigg{(}{G}\Bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+C+{D}\Bigg{)}\Bigg{)}{\varphi^{(1-\frac{1}{k})}}.$

Thus, the risk bound under 6.4 improves to
$\mathcal{O}(\varphi^{1-\frac{1}{k}})$, which matches the bound in the
constrained case. One caveat of the above result is that unlike Theorem 6.2,
the confidence estimate of the high-probability result cannot be controlled by
us. Next, we provide a matching lower bound showing the tightness of Theorem
6.5 w.r.t. $\varphi$.

######  Theorem 6.6 (Lower Bound for Unconstrained Convex Case Under 6.4).

Suppose $\delta<\exp(-\varepsilon^{2})$. There exists a convex loss function
$\ell$, such that for every $(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$
which tries to solve for $\bm{w}^{*}=\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})$ where $f$ is the average loss for a
dataset $\mathcal{Z}$ of $n$ samples drawn from the data distribution
$\mathcal{D}$, there exists a choice of $\mathcal{D}$ such that:

  * •

$f$ satisfies Assumptions 6.1 and 6.4 (the latter up to constant terms and
w.h.p. w.r.t. $\mathcal{Z}$).

  * •

$\mathbb{E}_{\mathcal{Z}\sim\mathcal{D}^{n},\mathcal{A}}\Big{[}f(\bm{w}_{\mathcal{Z}}^{(\mathcal{A})})-f(\bm{w}^{*})\Big{]}\geq\Omega\big{(}\varphi^{1-\frac{1}{k}}\big{)}$,
where $\bm{w}_{\mathcal{Z}}^{(\mathcal{A})}$ is the output of algorithm
$\mathcal{A}$ on the dataset $\mathcal{Z}$.

Thus, DP-SGD is optimal in the unconstrained convex case under Assumptions 6.1
& 6.4 (for $\delta<\exp(-\varepsilon^{2})$). We also have the following
corollary under uniform Lipschitzness.

######  Corollary 6.7 (Uniform Lipschitz).

For $k\to\infty$, i.e., under uniform Lipschitzness, the risk in the
unconstrained convex case regardless of 6.4 is $\mathcal{O}(\varphi)$ as per
Thm. 6.2 and 6.5. Further, Thm. 6.6 is a lower bound even w/o 6.4, and it
yields $\Omega(\varphi)$ for $k\to\infty$. Thus, DP-SGD is optimal in the
unconstrained convex case under uniform Lipschitzness (for
$\delta<\exp(-\varepsilon^{2})$).

Regarding the proof of Theorem 6.6: Even though we follow the proof outline of
Theorem 6.4 of Kamath et al. (2021), our proof is more involved. First, since
we are in the unconstrained setting, we had to use a non-obvious function (to
obtain the lower bound on). Second, since we are in the ERM setting, we have
to lower bound the expected training error which is harder than lower bounding
the expected generalization error in the SCO setting of Kamath et al. (2021).
Finally, since we are dealing with $(\varepsilon,\delta)$-DP (whereas Kamath
et al. (2021) deal with $(0,\rho)$-zCDP), we had to re-derive an important
tool in their analysis. That is also the reason we had to impose
$\delta<\exp(-\varepsilon^{2})$; removing this constraint is left for future
work. Note that this is the first lower bound for $(\varepsilon,\delta)$-DP in
the unconstrained case. See Appendix L for details.

Finally, we present our result under 6.1 in the unconstrained nonconvex case.

######  Theorem 6.8 (Unconstrained Nonconvex Case).

Suppose 6.1 holds, $f$ is $L$-smooth and $\mathcal{W}=\mathbb{R}^{d}$. Fix
some $\gamma\in(0,1)$. In Algorithm 1, set $T=\varphi^{-2}$,
$\tau=\mathcal{O}\big{(}\gamma^{-\frac{2}{2k-1}}\varphi^{-\frac{1}{2k-1}}\big{)}$
and
$\eta_{t}=\mathcal{O}\big{(}\gamma^{\frac{2}{2k-1}}\varphi^{1+\frac{1}{2k-1}}\big{)}$
for all $t<T$. Then with a probability of at least $(1-\gamma)$ which is
w.r.t. the random dataset $\mathcal{Z}$ that we obtain, DP-SGD (Alg. 1) has
the following guarantee:

$\textup{OR}(T)\leq\mathcal{O}\Big{(}{\gamma^{\frac{-2}{2k-1}}}\varphi^{(1-\frac{1}{2k-1})}\Big{)}.$

######  Remark 6.9 (Comparison with Prior Results).

As per Thm. 6.8, the risk is $\mathcal{O}(\varphi^{1-{\frac{1}{2k-1}}})$ in
the bounded $k^{\text{th}}$ moment nonconvex case. In comparison, Wang et al.
(2018, 2019) get a bound of $\mathcal{O}(\varphi)$ in the uniform Lipschitz
nonconvex case (equivalent to $k=\infty$) with DP-SGD like algorithms.

##  7 Limitations

We now discuss some limitations of our work which render interesting
directions of future work. We do not have a lower bound for the nonconvex case
in Section 6. Our clip norm selection strategy in Section 5 is only for the
convex case. Our iteration complexity ($T$) is worse than some related works
because we consider the vanilla DP-SGD algorithm of Abadi et al. (2016)
without any acceleration, whereas other works consider accelerated variants of
DP-SGD. In our case, we had to set
$T=\mathcal{O}(\nicefrac{{1}}{{\varphi^{2}}})$ in order to control the
clipping bias. But please note that the goal of this work is to attain smaller
optimization risk by properly choosing the clip norm, and not accelerate
convergence.

##  8 Conclusion

In this paper, we generalized uniform Lipschitzness by assuming that the per-
sample gradients have sample-dependent upper bounds called per-sample
Lipschitz constants. Under our generalized Lipschitzness assumption, we
provided a theoretically-motivated clip norm tuning recommendation for DP-SGD
in the convex case. We showed the effectiveness of our recommendation via
extensive experiments. Additionally, we derived novel convergence results for
unconstrained DP-SGD when the per-sample Lipschitz constants are heavy-tailed,
i.e., they have bounded moments.

## References

  * Abadi et al. (2016) Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pp. 308–318, 2016.
  * Acharya et al. (2021) Acharya, J., Sun, Z., and Zhang, H.  Differentially private assouad, fano, and le cam.  In _Algorithmic Learning Theory_ , pp. 48–78. PMLR, 2021.
  * Andrew et al. (2019) Andrew, G., Thakkar, O., McMahan, H. B., and Ramaswamy, S.  Differentially private learning with adaptive clipping.  _arXiv preprint arXiv:1905.03871_ , 2019.
  * Arora et al. (2022) Arora, R., Bassily, R., González, T., Guzmán, C., Menart, M., and Ullah, E.  Faster rates of convergence to stationary points in differentially private optimization.  _arXiv preprint arXiv:2206.00846_ , 2022.
  * Asi et al. (2021a) Asi, H., Duchi, J., Fallah, A., Javidbakht, O., and Talwar, K.  Private adaptive gradient methods for convex optimization.  In _International Conference on Machine Learning_ , pp. 383–392. PMLR, 2021a.
  * Asi et al. (2021b) Asi, H., Feldman, V., Koren, T., and Talwar, K.  Private stochastic convex optimization: Optimal rates in l1 geometry.  _arXiv preprint arXiv:2103.01516_ , 2021b.
  * Barbieri et al. (2018) Barbieri, F., Camacho-Collados, J., Ronzano, F., Espinosa-Anke, L., Ballesteros, M., Basile, V., Patti, V., and Saggion, H.  Semeval 2018 task 2: Multilingual emoji prediction.  In _Proceedings of The 12th International Workshop on Semantic Evaluation_ , pp. 24–33, 2018.
  * Bassily et al. (2014) Bassily, R., Smith, A., and Thakurta, A.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pp. 464–473. IEEE, 2014.
  * Bassily et al. (2019) Bassily, R., Feldman, V., Talwar, K., and Thakurta, A.  Private stochastic convex optimization with optimal rates.  _arXiv preprint arXiv:1908.09970_ , 2019.
  * Bassily et al. (2021) Bassily, R., Guzmán, C., and Menart, M.  Differentially private stochastic optimization: New results in convex and non-convex settings.  _Advances in Neural Information Processing Systems_ , 34:9317–9329, 2021.
  * Bolte et al. (2017) Bolte, J., Nguyen, T. P., Peypouquet, J., and Suter, B. W.  From error bounds to the complexity of first-order descent methods for convex functions.  _Mathematical Programming_ , 165(2):471–507, 2017\.
  * Bossard et al. (2014) Bossard, L., Guillaumin, M., and Van Gool, L.  Food-101 – mining discriminative components with random forests.  In _European Conference on Computer Vision_ , 2014.
  * Bu et al. (2021) Bu, Z., Wang, H., Long, Q., and Su, W. J.  On the convergence of deep learning with differential privacy.  _arXiv preprint arXiv:2106.07830_ , 2021.
  * Bun & Steinke (2016) Bun, M. and Steinke, T.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In _Theory of Cryptography Conference_ , pp. 635–658. Springer, 2016.
  * Burke & Ferris (1993) Burke, J. V. and Ferris, M. C.  Weak sharp minima in mathematical programming.  _SIAM Journal on Control and Optimization_ , 31(5):1340–1359, 1993.
  * Chaudhuri & Monteleoni (2008) Chaudhuri, K. and Monteleoni, C.  Privacy-preserving logistic regression.  In _NIPS_ , volume 8, pp. 289–296. Citeseer, 2008.
  * Chaudhuri et al. (2011) Chaudhuri, K., Monteleoni, C., and Sarwate, A. D.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Chen et al. (2020) Chen, X., Wu, S. Z., and Hong, M.  Understanding gradient clipping in private sgd: A geometric perspective.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Davis et al. (2018) Davis, D., Drusvyatskiy, D., MacPhee, K. J., and Paquette, C.  Subgradient methods for sharp weakly convex functions.  _Journal of Optimization Theory and Applications_ , 179(3):962–982, 2018.
  * De et al. (2022) De, S., Berrada, L., Hayes, J., Smith, S. L., and Balle, B.  Unlocking high-accuracy differentially private image classification through scale.  _arXiv preprint arXiv:2204.13650_ , 2022.
  * Du et al. (2021) Du, J., Li, S., Feng, M., and Chen, S.  Dynamic differential-privacy preserving sgd.  _arXiv preprint arXiv:2111.00173_ , 2021.
  * Duchi et al. (2013) Duchi, J. C., Jordan, M. I., and Wainwright, M. J.  Local privacy and statistical minimax rates.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pp. 429–438. IEEE, 2013.
  * Dwork et al. (2006) Dwork, C., McSherry, F., Nissim, K., and Smith, A.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pp. 265–284. Springer, 2006.
  * Dwork et al. (2014) Dwork, C., Roth, A., et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Feldman et al. (2020) Feldman, V., Koren, T., and Talwar, K.  Private stochastic convex optimization: optimal rates in linear time.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 439–449, 2020.
  * Griffin et al. (2007) Griffin, G., Holub, A., and Perona, P.  Caltech-256 object category dataset.  2007\.
  * Hu et al. (2021) Hu, L., Ni, S., Xiao, H., and Wang, D.  High dimensional differentially private stochastic optimization with heavy-tailed data.  _arXiv preprint arXiv:2107.11136_ , 2021.
  * Iyengar et al. (2019) Iyengar, R., Near, J. P., Song, D., Thakkar, O., Thakurta, A., and Wang, L.  Towards practical differentially private convex optimization.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pp. 299–316. IEEE, 2019.
  * Kamath et al. (2021) Kamath, G., Liu, X., and Zhang, H.  Improved rates for differentially private stochastic convex optimization with heavy-tailed data.  _arXiv preprint arXiv:2106.01336_ , 2021.
  * Kifer et al. (2012) Kifer, D., Smith, A., and Thakurta, A.  Private convex empirical risk minimization and high-dimensional regression.  In _Conference on Learning Theory_ , pp. 25–1. JMLR Workshop and Conference Proceedings, 2012.
  * Kulkarni et al. (2021) Kulkarni, J., Lee, Y. T., and Liu, D.  Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps.  _arXiv preprint arXiv:2103.15352_ , 2021.
  * Lowy & Razaviyayn (2023) Lowy, A. and Razaviyayn, M.  Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses.  In _International Conference on Algorithmic Learning Theory_ , pp. 986–1054. PMLR, 2023.
  * Ma et al. (2018) Ma, S., Bassily, R., and Belkin, M.  The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning.  In _International Conference on Machine Learning_ , pp. 3325–3334. PMLR, 2018.
  * Mehta et al. (2022) Mehta, H., Thakurta, A., Kurakin, A., and Cutkosky, A.  Large scale transfer learning for differentially private image classification.  _arXiv preprint arXiv:2205.02973_ , 2022.
  * Papernot & Steinke (2021) Papernot, N. and Steinke, T.  Hyperparameter tuning with renyi differential privacy.  In _International Conference on Learning Representations_ , 2021.
  * Papernot et al. (2020) Papernot, N., Thakurta, A., Song, S., Chien, S., and Erlingsson, U.  Tempered sigmoid activations for deep learning with differential privacy.  _arXiv preprint arXiv:2007.14191_ , pp. 10, 2020.
  * Polyak (1979) Polyak, B. T.  Sharp minima. institute of control sciences lecture notes, moscow, ussr, 1979.  In _IIASA workshop on generalized Lagrangians and their applications, IIASA, Laxenburg, Austria_ , 1979.
  * Roulet & d’Aspremont (2017) Roulet, V. and d’Aspremont, A.  Sharpness, restart and acceleration.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Sanh et al. (2019) Sanh, V., Debut, L., Chaumond, J., and Wolf, T.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  _arXiv preprint arXiv:1910.01108_ , 2019.
  * Saravia et al. (2018) Saravia, E., Liu, H.-C. T., Huang, Y.-H., Wu, J., and Chen, Y.-S.  CARER: Contextualized affect representations for emotion recognition.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 3687–3697, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.  doi: 10.18653/v1/D18-1404.  URL https://www.aclweb.org/anthology/D18-1404.
  * Song et al. (2013) Song, S., Chaudhuri, K., and Sarwate, A. D.  Stochastic gradient descent with differentially private updates.  In _2013 IEEE Global Conference on Signal and Information Processing_ , pp. 245–248. IEEE, 2013.
  * Song et al. (2021) Song, S., Steinke, T., Thakkar, O., and Thakurta, A.  Evading the curse of dimensionality in unconstrained private glms.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2638–2646. PMLR, 2021.
  * Talwar et al. (2014) Talwar, K., Thakurta, A., and Zhang, L.  Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry.  _arXiv preprint arXiv:1411.5417_ , 2014.
  * Talwar et al. (2015) Talwar, K., Guha Thakurta, A., and Zhang, L.  Nearly optimal private lasso.  _Advances in Neural Information Processing Systems_ , 28:3025–3033, 2015.
  * Tran & Cutkosky (2022) Tran, H. and Cutkosky, A.  Momentum aggregation for private non-convex erm.  _arXiv preprint arXiv:2210.06328_ , 2022.
  * Wang et al. (2018) Wang, D., Ye, M., and Xu, J.  Differentially private empirical risk minimization revisited: Faster and more general.  _arXiv preprint arXiv:1802.05251_ , 2018.
  * Wang et al. (2020) Wang, D., Xiao, H., Devadas, S., and Xu, J.  On differentially private stochastic convex optimization with heavy-tailed data.  In _International Conference on Machine Learning_ , pp. 10081–10091. PMLR, 2020.
  * Wang et al. (2019) Wang, L., Jayaraman, B., Evans, D., and Gu, Q.  Efficient privacy-preserving stochastic nonconvex optimization.  _arXiv preprint arXiv:1910.13659_ , 2019.
  * Wu et al. (2017) Wu, X., Li, F., Kumar, A., Chaudhuri, K., Jha, S., and Naughton, J.  Bolt-on differential privacy for scalable stochastic gradient descent-based analytics.  In _Proceedings of the 2017 ACM International Conference on Management of Data_ , pp. 1307–1322, 2017.
  * Wu et al. (2021) Wu, X., Wang, L., Cristali, I., Gu, Q., and Willett, R.  Adaptive differentially private empirical risk minimization.  _arXiv preprint arXiv:2110.07435_ , 2021.
  * Yousefpour et al. (2021) Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj, A., Zhao, J., Cormode, G., and Mironov, I.  Opacus: User-friendly differential privacy library in PyTorch.  _arXiv preprint arXiv:2109.12298_ , 2021.
  * Zhang et al. (2017) Zhang, J., Zheng, K., Mou, W., and Wang, L.  Efficient private erm for smooth objectives.  _arXiv preprint arXiv:1703.09947_ , 2017.
  * Zhang et al. (2020) Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S.  Why are adaptive methods good for attention models?  _Advances in Neural Information Processing Systems_ , 33:15383–15393, 2020.
  * Zhang et al. (2021) Zhang, X., Chen, X., Hong, M., Wu, Z. S., and Yi, J.  Understanding clipping for federated learning: Convergence and client-level differential privacy.  _arXiv preprint arXiv:2106.13673_ , 2021.

Appendix

## Contents

  * •

Appendix A: Empirical Results on EMNIST and Fashion-MNIST

  * •

Appendix B: Tables of Results for Section 5.2 and Appendix A

  * •

Appendix C: Some Empirical Results in the Non-Convex Case

  * •

Appendix D: Logistic Regression Satisfies Assumption 4.1

  * •

Appendix E: Example for Assumption 6.4

  * •

Appendix F: Some Useful Lemmas

  * •

Appendix G: Proof of Theorem 3.4

  * •

Appendix H: Full Version and Proof of Theorem 5.4

  * •

Appendix I: Result for the Constrained Convex Case under Assumption 6.1

  * •

Appendix J: Full Version and Proof of Theorem 6.2

  * •

Appendix K: Full Version and Proof of Theorem 6.5

  * •

Appendix L: Full Version and Proof of Theorem 6.6

  * •

Appendix M: Proof of Theorem I.3

  * •

Appendix N: Full Version and Proof of Theorem 6.8

##  Appendix A Empirical Results on EMNIST and Fashion-MNIST

Here, we show results for private multinomial logistic regression on two more
datasets, viz., (balanced) EMNIST with 47 classes and Fashion-MNIST with 10
classes. For both these datasets, we just use the flattened images as features
for logistic regression. Other experimental details are the same as in Section
5.2.

In Figure 2, we plot the best test accuracy obtained for different values of
the clip norm $\tau$ (by tuning over the learning rate $\eta$) averaged over
the last 5 epochs and across 3 independent runs (just like Figure 1). The
figure caption discusses the results. The exact accuracy values for these two
datasets are tabulated in Table 6 in Appendix B.

(a)

(b)

Figure 2: Average test accuracy (depicted by the blobs) $\pm$ 1 standard
deviation (depicted by the bars around the blobs) in the last 5 epochs for
different values of clip norm $\tau$. “%” in the x-axis stands for percentile.
Just as in Figure 1, clip norms $\leq G_{1}$ ($0^{\text{th}}$ percentile of
per-sample Lipschitz constants) perform better than clip norms $>G_{1}$, and
the performance with $\tau=G_{1}$ is much better than that with $\tau=G_{n}$
($100^{\text{th}}$ percentile). These observations validate our theory and
recommendation in Section 5.1.

##  Appendix B Tables of Results for Section 5.2 and Appendix A

Table 4: Caltech-256, Food-101 and CIFAR-100: Average test accuracy $\pm$ 1
standard deviation in the last 5 epochs for different values of clip norm
$\tau$ in the experiments of Section 5.2. Note that “pctl.” stands for
percentile. “Non-private baseline” is the accuracy of vanilla non-private SGD
in the same setting.

Caltech-256 |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=0.1$ | 73.70 $\pm$ 0.28 % | 79.00 $\pm$ 0.03 % | 80.50 $\pm$ 0.04 %
$\tau=1.0$ | 74.03 $\pm$ 0.47 % | 79.00 $\pm$ 0.08 % | 80.39 $\pm$ 0.07 %
$\tau=5.0$ | 73.80 $\pm$ 0.40 % | 79.00 $\pm$ 0.04 % | 80.00 $\pm$ 0.04 %
$\tau=10.0$ | 73.72 $\pm$ 0.28 % | 78.79 $\pm$ 0.08 % | 79.38 $\pm$ 0.05 %
$\tau=(0^{\text{th}}\text{ pctl.})$ | 73.54 $\pm$ 0.32 % | 78.42 $\pm$ 0.05 % | 79.41 $\pm$ 0.06 %
$\tau=(10^{\text{th}}\text{ pctl.})$ | 69.38 $\pm$ 0.45 % | 75.32 $\pm$ 0.08 % | 77.63 $\pm$ 0.05 %
$\tau=(20^{\text{th}}\text{ pctl.})$ | 68.73 $\pm$ 0.30 % | 74.81 $\pm$ 0.02 % | 77.37 $\pm$ 0.08 %
$\tau=(40^{\text{th}}\text{ pctl.})$ | 67.36 $\pm$ 0.29 % | 73.43 $\pm$ 0.06 % | 76.82 $\pm$ 0.09 %
$\tau=(80^{\text{th}}\text{ pctl.})$ | 65.25 $\pm$ 0.30 % | 71.35 $\pm$ 0.05 % | 75.38 $\pm$ 0.08 %
$\tau=(100^{\text{th}}\text{ pctl.})$ | 50.34 $\pm$ 0.57 % | 63.98 $\pm$ 0.07 % | 70.04 $\pm$ 0.10 %
Non-private baseline |  83.97 $\pm$ 0.02 %

Food-101 |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=0.1$ | 48.36 $\pm$ 1.08 % | 54.30 $\pm$ 0.16 % | 56.40 $\pm$ 0.12 %
$\tau=1.0$ | 48.57 $\pm$ 1.22 % | 54.28 $\pm$ 0.21 % | 56.62 $\pm$ 0.09 %
$\tau=5.0$ | 48.92 $\pm$ 1.14 % | 54.85 $\pm$ 0.14 % | 56.67 $\pm$ 0.10 %
$\tau=10.0$ | 49.26 $\pm$ 1.00 % | 54.73 $\pm$ 0.15 % | 56.49 $\pm$ 0.05 %
$\tau=(0^{\text{th}}\text{ pctl.})$ | 48.84 $\pm$ 0.89 % | 54.31 $\pm$ 0.11 % | 56.13 $\pm$ 0.08 %
$\tau=(10^{\text{th}}\text{ pctl.})$ | 45.54 $\pm$ 0.88 % | 52.22 $\pm$ 0.24 % | 54.29 $\pm$ 0.04 %
$\tau=(20^{\text{th}}\text{ pctl.})$ | 44.95 $\pm$ 0.94 % | 51.91 $\pm$ 0.20 % | 54.06 $\pm$ 0.09 %
$\tau=(40^{\text{th}}\text{ pctl.})$ | 43.69 $\pm$ 0.87 % | 51.43 $\pm$ 0.22 % | 53.88 $\pm$ 0.02 %
$\tau=(80^{\text{th}}\text{ pctl.})$ | 42.52 $\pm$ 0.96 % | 50.60 $\pm$ 0.20 % | 52.92 $\pm$ 0.09 %
$\tau=(100^{\text{th}}\text{ pctl.})$ | 37.36 $\pm$ 1.26 % | 46.71 $\pm$ 0.18 % | 49.73 $\pm$ 0.11 %
Non-private baseline |  63.20 $\pm$ 0.06 %

CIFAR-100 |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=0.1$ | 54.32 $\pm$ 0.64 % | 60.35 $\pm$ 0.13 % | 61.09 $\pm$ 0.07 %
$\tau=1.0$ | 54.49 $\pm$ 0.63 % | 60.26 $\pm$ 0.10 % | 61.15 $\pm$ 0.11 %
$\tau=5.0$ | 54.33 $\pm$ 0.42 % | 60.17 $\pm$ 0.08 % | 61.16 $\pm$ 0.11 %
$\tau=10.0$ | 55.10 $\pm$ 0.26 % | 59.44 $\pm$ 0.12 % | 60.36 $\pm$ 0.12 %
$\tau=17.7(0^{\text{th}}\text{ pctl.})$ | 54.40 $\pm$ 0.36 % | 58.93 $\pm$ 0.10 % | 59.96 $\pm$ 0.09 %
$\tau=29.2(10^{\text{th}}\text{ pctl.})$ | 52.16 $\pm$ 0.40 % | 57.40 $\pm$ 0.17 % | 59.89 $\pm$ 0.09 %
$\tau=31.6(20^{\text{th}}\text{ pctl.})$ | 51.61 $\pm$ 0.47 % | 57.57 $\pm$ 0.10 % | 58.72 $\pm$ 0.08 %
$\tau=34.7(40^{\text{th}}\text{ pctl.})$ | 49.98 $\pm$ 0.52 % | 56.67 $\pm$ 0.16 % | 58.15 $\pm$ 0.11 %
$\tau=40.1(80^{\text{th}}\text{ pctl.})$ | 47.23 $\pm$ 0.48 % | 55.15 $\pm$ 0.09 % | 56.87 $\pm$ 0.08 %
$\tau=55.7(100^{\text{th}}\text{ pctl.})$ | 45.40 $\pm$ 0.96 % | 51.77 $\pm$ 0.09 % | 54.46 $\pm$ 0.07 %
Non-private baseline |  66.91 $\pm$ 0.05 %

Table 5: CIFAR-10, TweetEval Emoji and Emotion: Average test accuracy $\pm$ 1
standard deviation in the last 5 epochs for different values of clip norm
$\tau$ in the experiments of Section 5.2. Note that “pctl.” stands for
percentile. “Non-private baseline” is the accuracy of vanilla non-private SGD
in the same setting.

CIFAR-10 |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=0.1$ | 83.61 $\pm$ 0.21 % | 84.84 $\pm$ 0.04 % | 85.41 $\pm$ 0.05 %
$\tau=1.0$ | 83.87 $\pm$ 0.15 % | 84.83 $\pm$ 0.04 % | 85.58 $\pm$ 0.06 %
$\tau=5.0$ | 83.90 $\pm$ 0.20 % | 84.87 $\pm$ 0.10 % | 85.45 $\pm$ 0.02 %
$\tau=10.0$ | 83.97 $\pm$ 0.15 % | 85.15 $\pm$ 0.07 % | 85.43 $\pm$ 0.06 %
$\tau=19.8(0^{\text{th}}\text{ pctl.})$ | 83.79 $\pm$ 0.20 % | 84.75 $\pm$ 0.06 % | 85.31 $\pm$ 0.08 %
$\tau=31.7(10^{\text{th}}\text{ pctl.})$ | 83.14 $\pm$ 0.18 % | 84.67 $\pm$ 0.15 % | 84.98 $\pm$ 0.10 %
$\tau=33.6(20^{\text{th}}\text{ pctl.})$ | 82.75 $\pm$ 0.15 % | 84.50 $\pm$ 0.09 % | 85.05 $\pm$ 0.03 %
$\tau=36.1(40^{\text{th}}\text{ pctl.})$ | 82.94 $\pm$ 0.23 % | 84.51 $\pm$ 0.11 % | 84.90 $\pm$ 0.07 %
$\tau=40.8(80^{\text{th}}\text{ pctl.})$ | 82.56 $\pm$ 0.22 % | 83.98 $\pm$ 0.10 % | 84.73 $\pm$ 0.08 %
$\tau=55.4(100^{\text{th}}\text{ pctl.})$ | 81.78 $\pm$ 0.16 % | 83.21 $\pm$ 0.11 % | 84.25 $\pm$ 0.06 %
Non-private baseline |  86.78 $\pm$ 0.05 %

TweetEval Emoji |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=0.1$ | 26.15 $\pm$ 0.26 % | 28.13 $\pm$ 0.12 % | 28.59 $\pm$ 0.21 %
$\tau=1.0$ | 26.21 $\pm$ 0.30 % | 28.21 $\pm$ 0.10 % | 28.68 $\pm$ 0.17 %
$\tau=5.0$ | 26.28 $\pm$ 0.33 % | 28.14 $\pm$ 0.10 % | 28.77 $\pm$ 0.23 %
$\tau=10.0$ | 26.34 $\pm$ 0.37 % | 28.00 $\pm$ 0.15 % | 28.57 $\pm$ 0.18 %
$\tau=13.8(0^{\text{th}}\text{ pctl.})$ | 26.04 $\pm$ 0.29 % | 27.86 $\pm$ 0.06 % | 28.40 $\pm$ 0.13 %
$\tau=15.9(10^{\text{th}}\text{ pctl.})$ | 25.92 $\pm$ 0.29 % | 27.67 $\pm$ 0.10 % | 28.06 $\pm$ 0.06 %
$\tau=16.2(20^{\text{th}}\text{ pctl.})$ | 25.78 $\pm$ 0.32 % | 27.63 $\pm$ 0.08 % | 28.06 $\pm$ 0.05 %
$\tau=16.7(40^{\text{th}}\text{ pctl.})$ | 25.83 $\pm$ 0.30 % | 27.50 $\pm$ 0.07 % | 28.01 $\pm$ 0.07 %
$\tau=17.5(80^{\text{th}}\text{ pctl.})$ | 25.70 $\pm$ 0.31 % | 27.46 $\pm$ 0.07 % | 27.93 $\pm$ 0.07 %
$\tau=20.8(100^{\text{th}}\text{ pctl.})$ | 25.55 $\pm$ 0.26 % | 27.06 $\pm$ 0.11 % | 27.73 $\pm$ 0.05 %
Non-private baseline |  30.10 $\pm$ 0.03 %

Emotion |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=0.1$ | 51.95 $\pm$ 0.42 % | 54.88 $\pm$ 0.30 % | 56.45 $\pm$ 0.25 %
$\tau=1.0$ | 52.39 $\pm$ 0.61 % | 55.05 $\pm$ 0.26 % | 56.10 $\pm$ 0.16 %
$\tau=5.0$ | 52.40 $\pm$ 0.57 % | 55.25 $\pm$ 0.13 % | 56.35 $\pm$ 0.20 %
$\tau=10.0$ | 52.24 $\pm$ 0.64 % | 54.95 $\pm$ 0.22 % | 55.82 $\pm$ 0.33 %
$\tau=14.6(0^{\text{th}}\text{ pctl.})$ | 51.86 $\pm$ 0.70 % | 54.52 $\pm$ 0.29 % | 55.83 $\pm$ 0.16 %
$\tau=16.4(10^{\text{th}}\text{ pctl.})$ | 51.59 $\pm$ 0.46 % | 54.25 $\pm$ 0.29 % | 55.03 $\pm$ 0.20 %
$\tau=16.8(20^{\text{th}}\text{ pctl.})$ | 51.03 $\pm$ 0.42 % | 54.16 $\pm$ 0.34 % | 55.09 $\pm$ 0.19 %
$\tau=17.2(40^{\text{th}}\text{ pctl.})$ | 50.84 $\pm$ 0.48 % | 54.21 $\pm$ 0.35 % | 55.04 $\pm$ 0.22 %
$\tau=17.8(80^{\text{th}}\text{ pctl.})$ | 50.94 $\pm$ 0.50 % | 53.78 $\pm$ 0.34 % | 54.97 $\pm$ 0.09 %
$\tau=20.2(100^{\text{th}}\text{ pctl.})$ | 50.34 $\pm$ 0.46 % | 53.64 $\pm$ 0.22 % | 54.21 $\pm$ 0.10 %
Non-private baseline |  60.43 $\pm$ 0.22 %

Table 6: EMNIST and Fashion-MNIST: Average test accuracy $\pm$ 1 standard
deviation in the last 5 epochs for different values of clip norm $\tau$ in the
experiments of Appendix A. Note that “pctl.” stands for percentile. “Non-
private baseline” is the accuracy of vanilla non-private SGD in the same
setting.

EMNIST |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=1.0$ | 62.78 $\pm$ 0.98 % | 65.90 $\pm$ 0.09 % | 67.02 $\pm$ 0.11 %
$\tau=3.0$ | 63.17 $\pm$ 0.94 % | 66.16 $\pm$ 0.10 % | 66.94 $\pm$ 0.10 %
$\tau=5.7(0^{\text{th}}\text{ pctl.})$ | 62.85 $\pm$ 0.89 % | 65.55 $\pm$ 0.17 % | 66.79 $\pm$ 0.04 %
$\tau=11.6(10^{\text{th}}\text{ pctl.})$ | 61.11 $\pm$ 0.99 % | 64.77 $\pm$ 0.25 % | 65.41 $\pm$ 0.11 %
$\tau=12.7(20^{\text{th}}\text{ pctl.})$ | 61.12 $\pm$ 0.98 % | 64.30 $\pm$ 0.09 % | 64.96 $\pm$ 0.10 %
$\tau=14.1(40^{\text{th}}\text{ pctl.})$ | 60.42 $\pm$ 0.96 % | 63.88 $\pm$ 0.13 % | 64.67 $\pm$ 0.14 %
$\tau=16.7(80^{\text{th}}\text{ pctl.})$ | 59.49 $\pm$ 0.83 % | 63.07 $\pm$ 0.10 % | 63.94 $\pm$ 0.08 %
$\tau=26.1(100^{\text{th}}\text{ pctl.})$ | 56.36 $\pm$ 1.04 % | 61.26 $\pm$ 0.16 % | 62.06 $\pm$ 0.08 %
Non-private baseline |  69.37 $\pm$ 0.04 %

Fashion-MNIST |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=1.0$ | 82.99 $\pm$ 0.13 % | 83.86 $\pm$ 0.11 % | 84.06 $\pm$ 0.02 %
$\tau=3.0(0^{\text{th}}\text{ pctl.})$ | 82.82 $\pm$ 0.18 % | 83.85 $\pm$ 0.06 % | 83.99 $\pm$ 0.11 %
$\tau=10.0(10^{\text{th}}\text{ pctl.})$ | 82.24 $\pm$ 0.14 % | 83.43 $\pm$ 0.08 % | 83.56 $\pm$ 0.06 %
$\tau=12.2(20^{\text{th}}\text{ pctl.})$ | 82.27 $\pm$ 0.07 % | 83.36 $\pm$ 0.09 % | 83.59 $\pm$ 0.09 %
$\tau=15.6(40^{\text{th}}\text{ pctl.})$ | 82.05 $\pm$ 0.19 % | 83.20 $\pm$ 0.07 % | 83.31 $\pm$ 0.08 %
$\tau=22.3(80^{\text{th}}\text{ pctl.})$ | 81.24 $\pm$ 0.14 % | 82.43 $\pm$ 0.07 % | 82.67 $\pm$ 0.10 %
$\tau=32.4(100^{\text{th}}\text{ pctl.})$ | 79.99 $\pm$ 0.18 % | 81.69 $\pm$ 0.12 % | 82.14 $\pm$ 0.10 %
Non-private baseline |  84.44 $\pm$ 0.05 %

##  Appendix C Some Empirical Results in the Non-Convex Case

Here we show some empirical results on a nonconvex neural network (NN)
problem. Specifically, we consider a two-layer feedforward NN having one
hidden layer with tanh activation. We use tanh instead of ReLU activation due
to two reasons: (i) Papernot et al. (2020) show that tanh performs better than
ReLU in private training of NNs (which we also observed), and (ii) we expect
Lipschitz constants to be smaller with tanh than ReLU. We run our experiments
on CIFAR-100 and EMNIST; we use pre-trained features for the former, while for
the latter, we use the raw images. Specifically, for CIFAR-100, we use
512-dimensional features obtained from the pre-softmax layer of a pre-trained
ResNet-18 model on ImageNet (same as in Section 5.2). For EMNIST, we use the
flattened images as features (just as mentioned in Appendix A). For both
datasets, we set the dimension of the hidden layer of the NN to be 256.
Computing the per-sample Lipschitz constants is much harder here so we just
test several values of the clip norm $\tau$, viz.,
$\\{1,3,6,12,18,24,30,36\\}$, and show the performance trend as a function of
$\tau$. All other experimental details are the same as in Section 5.2.

In Figure 3, we plot the best test accuracy obtained for different values of
$\tau$ (by tuning over $\eta$) averaged over the last 5 epochs and across 3
independent runs. The figure caption discusses the results. The exact values
are tabulated in Table 7.

So empirically, smaller clip norms perform better in two-layer nonconvex NNs,
similar to the convex case.

A single NVIDIA TITAN Xp GPU was used for all the experiments in this paper.

(a)

(b)

Figure 3: EMNIST and CIFAR-100 with two-layer NN: Average test accuracy
(depicted by the blobs) $\pm$ 1 standard deviation (depicted by the bars above
and below the blobs) in the last 5 epochs for different values of clip norm
$\tau$. The general trend above is that the accuracy drops as the clip norm
increases; this is similar to what we saw in the experiments on convex
problems, and consistent with the main message of Theorem 5.4 (even though it
is for the convex case), viz., smaller clip norms should perform better as
they attain a lower risk bound.  Table 7: EMNIST and CIFAR-100 with two-layer
NN: Average test accuracy $\pm$ 1 standard deviation in the last 5 epochs for
different values of clip norm $\tau$ in the experiments above. “Non-private
baseline” is the accuracy of vanilla non-private SGD in the same setting.

EMNIST |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=1$ | 65.32 $\pm$ 1.54 % | 72.03 $\pm$ 0.17 % | 73.59 $\pm$ 0.18 %
$\tau=3$ | 65.36 $\pm$ 1.54 % | 71.74 $\pm$ 0.16 % | 73.44 $\pm$ 0.06 %
$\tau=6$ | 63.72 $\pm$ 1.64 % | 70.89 $\pm$ 0.37 % | 73.28 $\pm$ 0.12 %
$\tau=12$ | 63.50 $\pm$ 1.60 % | 70.42 $\pm$ 0.33 % | 72.51 $\pm$ 0.14 %
$\tau=18$ | 62.87 $\pm$ 1.44 % | 68.04 $\pm$ 0.29 % | 70.65 $\pm$ 0.23 %
$\tau=24$ | 60.95 $\pm$ 1.19 % | 66.82 $\pm$ 0.33 % | 69.01 $\pm$ 0.11 %
$\tau=30$ | 58.43 $\pm$ 2.04 % | 64.91 $\pm$ 0.12 % | 66.30 $\pm$ 0.19 %
$\tau=36$ | 57.55 $\pm$ 1.83 % | 62.36 $\pm$ 0.19 % | 65.03 $\pm$ 0.20 %
Non-private baseline |  84.24 $\pm$ 0.05 %

CIFAR-100 |  (a) $(2,10^{-5})$-DP |  (b) $(4,10^{-5})$-DP |  (c) $(6,10^{-5})$-DP
---|---|---|---
$\tau=1$ | 54.92 $\pm$ 0.42 % | 59.08 $\pm$ 0.08 % | 61.33 $\pm$ 0.06 %
$\tau=3$ | 54.58 $\pm$ 0.40 % | 59.28 $\pm$ 0.24 % | 61.26 $\pm$ 0.04 %
$\tau=6$ | 54.54 $\pm$ 0.67 % | 59.43 $\pm$ 0.17 % | 61.33 $\pm$ 0.08 %
$\tau=12$ | 54.58 $\pm$ 0.55 % | 59.48 $\pm$ 0.11 % | 60.84 $\pm$ 0.10 %
$\tau=18$ | 53.28 $\pm$ 0.81 % | 57.94 $\pm$ 0.09 % | 59.41 $\pm$ 0.12 %
$\tau=24$ | 51.81 $\pm$ 0.65 % | 55.83 $\pm$ 0.23 % | 59.22 $\pm$ 0.09 %
$\tau=30$ | 50.01 $\pm$ 0.78 % | 55.10 $\pm$ 0.24 % | 58.09 $\pm$ 0.10 %
$\tau=36$ | 46.69 $\pm$ 0.46 % | 54.16 $\pm$ 0.23 % | 56.58 $\pm$ 0.16 %
Non-private baseline |  67.31 $\pm$ 0.04 %

##  Appendix D Logistic Regression Satisfies Assumption 4.1

Consider doing logistic regression for multi-class classification with the
cross-entropy loss, where $m$ is the number of classes. Suppose
$\bm{x}\sim\mathcal{F}$ (with a ‘1’ appended to account for the bias term) is
the feature vector and $y\in[m]$ is the corresponding class number. Let the
model parameter $\bm{w}$ be split as $\bm{w}=[\bm{w}_{1},\ldots,\bm{w}_{m}]$,
where each $\\{\bm{w}_{j}\\}_{j=1}^{m}\in\mathbb{R}^{d}$, $d$ being the
dimension of $\bm{x}$; so, $\bm{w}_{j}$ denotes the parameter vector
corresponding to class $j$. Then, our predicted probability of $\bm{x}$
belonging to class $j$ with the softmax predictor is:

$p_{j}=\frac{\exp(\bm{w}_{j}^{T}\bm{x})}{\sum_{k=1}^{m}\exp(\bm{w}_{k}^{T}\bm{x})}.$

We use the standard cross-entropy loss for logistic regression which gives us:

$\ell(\bm{w},\bm{x},y)=-\log({p}_{y}).$ (7)

Now, with some differentiation, it can be checked that:

$\|\nabla\ell_{\bm{w}}(\bm{w},\bm{x},y)\|=\Bigg{(}\sqrt{\sum_{j\neq
y}p_{j}^{2}+(1-p_{y})^{2}}\Bigg{)}\|\bm{x}\|\leq\sqrt{2}\|\bm{x}\|.$ (8)

Thus, logistic regression satisfies 4.1 with $G(\bm{x},y)=\sqrt{2}\|\bm{x}\|$
in any parameter domain $\mathcal{W}$.

##  Appendix E Example for Assumption 6.4

Suppose $f_{i}(\bm{w})=\|\bm{w}-\bm{w}_{i}^{\ast}\|$. Then,
$f(\bm{w})=\frac{1}{n}\sum_{i=1}^{n}\|\bm{w}-\bm{w}_{i}^{\ast}\|$ and
$\bm{w}^{\ast}=\text{arg min}_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})$.

Let $\overline{\bm{w}}^{\ast}=\frac{1}{n}\sum_{i=1}^{n}\bm{w}_{i}^{\ast}$. For
$\|\bm{w}-\bm{w}^{\ast}\|\geq
D:=\max(2\|\overline{\bm{w}}^{\ast}-\bm{w}^{\ast}\|,\frac{4}{n}\sum_{i=1}^{n}\|\overline{\bm{w}}^{\ast}-\bm{w}_{i}^{\ast}\|)$,
it can be shown that
$f(\bm{w})-f(\bm{w}^{\ast})\geq\frac{1}{4}\|\bm{w}-\bm{w}^{\ast}\|$. Noting
that $G=\mathcal{O}(1)$ here (as the sub-gradient of $f_{i}$ is bounded by 1
in magnitude), 6.4 easily holds here for small $\varphi$.

###### Proof.

Using the triangle inequality, we have for any $\bm{w}$ satisfying
$\|\bm{w}-\bm{w}^{\ast}\|\geq D$:

$\displaystyle f(\bm{w})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\|\bm{w}-\bm{w}_{i}^{\ast}\|$ (9)
$\displaystyle\geq\Big{\|}\bm{w}-\frac{1}{n}\sum_{i=1}^{n}\bm{w}_{i}^{\ast}\Big{\|}$
(10) $\displaystyle=\|\bm{w}-\overline{\bm{w}}^{\ast}\|$ (11)
$\displaystyle=\|\bm{w}-\bm{w}^{\ast}-(\overline{\bm{w}}^{\ast}-\bm{w}^{\ast})\|$
(12)
$\displaystyle\geq\Big{|}\|\bm{w}-\bm{w}^{\ast}\|-\|\overline{\bm{w}}^{\ast}-\bm{w}^{\ast}\|\Big{|}$
(13)
$\displaystyle=\Bigg{|}\frac{\|\bm{w}-\bm{w}^{\ast}\|}{2}+\frac{\|\bm{w}-\bm{w}^{\ast}\|}{2}-\|\overline{\bm{w}}^{\ast}-\bm{w}^{\ast}\|\Bigg{|}$
(14) $\displaystyle\geq\frac{\|\bm{w}-\bm{w}^{\ast}\|}{2}.$ (15)

Equation 15 follows because
$\frac{\|\bm{w}-\bm{w}^{\ast}\|}{2}\geq\frac{D}{2}\geq\|\overline{\bm{w}}^{\ast}-\bm{w}^{\ast}\|$
(from the definition of $D$). Next, since $\bm{w}^{\ast}$ is the minimizer of
$f$ and using the definition of $D$, we have:

$f(\bm{w}^{\ast})\leq
f(\overline{\bm{w}}^{\ast})=\frac{1}{n}\sum_{i=1}^{n}\|\overline{\bm{w}}^{\ast}-\bm{w}_{i}^{\ast}\|\leq\frac{D}{4}\leq\frac{\|\bm{w}-\bm{w}^{\ast}\|}{4}.$
(16)

Finally, subtracting Equation 16 from Equation 15 gives us the desired result.
∎

##  Appendix F Some Useful Lemmas

######  Lemma F.1 (Clipping Bias).

Suppose $\bm{v}(\bm{\zeta})$ (where $\bm{\zeta}$ denotes the source of
randomness) is an unbiased estimator of $\bm{v}$, i.e.
$\mathbb{E}_{\bm{\zeta}}[\bm{v}(\bm{\zeta})]=\bm{v}$. Let $b(\tau)$ denote the
clipping bias of $\text{clip}(\bm{v}(\bm{\zeta}),\tau)$, i.e.

$b(\tau)=\Big{\|}\bm{{v}}-\mathbb{E}_{\bm{\zeta}}\Big{[}\textup{clip}(\bm{v}(\bm{\zeta}),\tau)\Big{]}\Big{\|}.$

Then for any $p>1$,

$\displaystyle
b(\tau)\leq\Big{(}\mathbb{E}[\|\bm{v}(\bm{\zeta})\|^{p}]\Big{)}^{\frac{1}{p}}\Big{(}\mathbb{P}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{)}^{1-\frac{1}{p}}-\tau\mathbb{P}(\|\bm{v}(\bm{\zeta})\|\geq\tau).$

###### Proof.

We shall omit the subscript $\bm{\zeta}$ in expectations henceforth, and it
should be inferred from context. We can bound the clipping bias $b(\tau)$ with
a clip norm $\tau$ as:

$\displaystyle b(\tau)$
$\displaystyle=\Big{\|}\bm{{v}}-\mathbb{E}\Big{[}\text{clip}(\bm{v}(\bm{\zeta}),\tau)\Big{]}\Big{\|}$
(17)
$\displaystyle=\Big{\|}\bm{{v}}-\mathbb{E}\Big{[}\bm{v}(\bm{\zeta})\min\Big{(}1,\frac{\tau}{\|\bm{v}(\bm{\zeta})\|}\Big{)}\Big{]}\Big{\|}$
(18)
$\displaystyle=\Big{\|}\mathbb{E}\Big{[}\bm{v}(\bm{\zeta})\Big{(}1-\frac{\tau}{\|\bm{v}(\bm{\zeta})\|}\Big{)}\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{]}\Big{\|}$
(19)
$\displaystyle\leq\mathbb{E}\Big{[}\|\bm{v}(\bm{\zeta})\|{\Big{(}1-\frac{\tau}{\|\bm{v}(\bm{\zeta})\|}\Big{)}}\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{]}$
(20)
$\displaystyle=\mathbb{E}\Big{[}\|\bm{v}(\bm{\zeta})\|\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{]}-\tau\mathbb{E}[\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)]$
(21)
$\displaystyle\leq\Big{(}\mathbb{E}[\|\bm{v}(\bm{\zeta})\|^{p}]\Big{)}^{\frac{1}{p}}\Big{(}\mathbb{E}\Big{[}\Big{(}\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{)}^{q}\Big{]}\Big{)}^{\frac{1}{q}}-\tau\mathbb{P}(\|\bm{v}(\bm{\zeta})\|\geq\tau),$
(22)

for $p,q\in(1,\infty)$ such that $\frac{1}{p}+\frac{1}{q}=1$; this follows
from Hölder’s inequality. Now

$\displaystyle\mathbb{E}\Big{[}\Big{(}\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{)}^{q}\Big{]}=\mathbb{E}[\mathbbm{1}(\|\bm{v}(\bm{\zeta})\|\geq\tau)]=\mathbb{P}(\|\bm{v}(\bm{\zeta})\|\geq\tau).$
(23)

Plugging this back in Equation 22 and substituting
$\frac{1}{q}=1-\frac{1}{p}$, we get the desired result for $b(\tau)$. ∎

######  Corollary F.2 (Clipping Bias).

In the setting of Lemma F.1, we have the following simpler upper bound for any
$p>1$:

$b(\tau)\leq\frac{\mathbb{E}[\|\bm{v}(\bm{\zeta})\|^{p}]}{\tau^{p-1}}.$

###### Proof.

From Lemma F.1, we have that:

$\displaystyle
b(\tau)\leq\Big{(}\mathbb{E}[\|\bm{v}(\bm{\zeta})\|^{p}]\Big{)}^{\frac{1}{p}}\Big{(}\mathbb{P}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\Big{)}^{1-\frac{1}{p}},$
(24)

for any $p>1$. Using Markov’s inequality, we have:

$\mathbb{P}(\|\bm{v}(\bm{\zeta})\|\geq\tau)\leq\frac{\mathbb{E}[\|\bm{v}(\bm{\zeta})\|^{p}]}{\tau^{p}}.$
(25)

Plugging this in Equation 24, we get the desired result. ∎

It is worth mentioning here that a result similar to Corollary F.2 has been
established in Lemma 10 of Zhang et al. (2020).

##  Appendix G Proof of Theorem 3.4

Using the result of Abadi et al. (2016), we know that any $\bm{w}_{t}$, where
$t\in\\{0,\ldots,T-1\\}$, will be $(\varepsilon,\delta)$-DP if we set
$\sigma_{n}^{2}=\nu\frac{T\log(\frac{1}{\delta})}{n^{2}\varepsilon^{2}}\tau^{2}$
for some absolute constant $\nu$. Thus, $\bm{w}_{\widehat{t}}$ (where
$\widehat{t}$ is chosen uniformly at random from $\\{0,\ldots,T-1\\}$ as
defined in Algorithm 1) will also be $(\varepsilon,\delta)$-DP.

##  Appendix H Full Version and Proof of Theorem 5.4

######  Theorem H.1 (Convex Case).

Suppose each $f_{i}$ is convex and $\mathcal{W}$ is a convex set (which can be
$\mathbb{R}^{d}$). In Algorithm 1, for all $t<T$, set
$\eta_{t}=\eta=\frac{C}{T\tau}\Big{(}{\frac{1}{T}+\varphi^{2}}\Big{)}^{-1/2}$
for clip norm $\tau$, where $C>0$ is a parameter of our choice. Recall
$\bm{w}^{*}\in\textup{argmin}_{\bm{w}\in\mathcal{W}}f(\bm{w})$ and
$\widehat{t}\sim\textup{Unif}[0,T-1]$. Then, DP-SGD (Algorithm 1) has the
following convergence guarantee:

$\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{\widehat{t}})\|}\Big{)}(f_{i}(\bm{w}_{\widehat{t}})-f_{i}(\bm{w}^{*}))\Big{]}\leq\bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2C}+C\bigg{)}\tau\sqrt{\frac{1}{T}+\varphi^{2}}.$

Now suppose Assumption 5.1 holds. Then, DP-SGD has the following upper bound
on the optimization risk as a function of the clip norm $\tau\in(0,G_{n}]$:

$\textup{OR}(T)\leq\frac{1}{\alpha(\tau)}\Bigg{(}\bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2C}+C\bigg{)}G_{n}\sqrt{\frac{1}{T}+\varphi^{2}}\Bigg{)}+\Bigg{(}\frac{G_{n}}{\tau\alpha(\tau)}-1\Bigg{)}{\Delta(\bm{w}^{*})},$

where $\Delta(\bm{w}^{*})\geq 0$ and $\alpha(\tau)\geq 1$ are as defined in
Definitions 5.2 and 5.3, respectively.

Theorem 5.4 can be obtained from the above theorem by plugging in
$T=\frac{1}{3\varphi^{2}}$. The proof of Theorem H.1 is below.

### Proof:

###### Proof.

Suppose we use a constant clip norm $\tau$ and constant learning rate $\eta$.
For any $\bm{w}^{*}\in\text{argmin}_{\bm{w}\in\mathcal{W}}f(\bm{w})$,
$\|\bm{w}_{t+1}-\bm{w}^{*}\|\leq\|\bm{z}_{t+1}-\bm{w}^{*}\|$ as $\bm{w}_{t+1}$
is the projection of $\bm{z}_{t+1}$ onto the convex set $\mathcal{W}$. Thus:

$\displaystyle\mathbb{E}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\|\bm{z}_{t+1}-\bm{w}^{*}\|^{2}]$ (26)
$\displaystyle=\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2\eta\mathbb{E}[\langle\bm{g}_{t},\bm{w}_{t}-\bm{w}^{*}\rangle]+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
(27)
$\displaystyle=\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2\eta\mathbb{E}\Big{[}\Big{\langle}\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau),\bm{w}_{t}-\bm{w}^{*}\Big{\rangle}\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
(28)
$\displaystyle=\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-\frac{2\eta}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{t})\|}\Big{)}\langle\nabla
f_{i}(\bm{w}_{t}),\bm{w}_{t}-\bm{w}^{*}\rangle\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
(29)
$\displaystyle\leq\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-\frac{2\eta}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{t})\|}\Big{)}(f_{i}(\bm{w}_{t})-f_{i}(\bm{w}^{*}))\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}].$
(30)

Equation 30 follows from the convexity of $f_{i}$. Next, rearranging the above
a bit, followed by summing for $t=0$ through to $T-1$, and then dividing by
$2\eta T$ throughout, we get:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\Big{\\{}\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{t})\|}\Big{)}(f_{i}(\bm{w}_{t})-f_{i}(\bm{w}^{*}))\Big{]}\Big{\\}}$
$\displaystyle\leq\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}-\mathbb{E}[\|\bm{w}_{T}-\bm{w}^{*}\|^{2}]}{2\eta
T}+\frac{\eta}{2T}\sum_{t=0}^{T-1}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$ (31)
$\displaystyle\leq\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2\eta
T}+\frac{\eta}{2T}\sum_{t=0}^{T-1}\mathbb{E}[\|\bm{g}_{t}\|^{2}].$ (32)

Henceforth, we shall denote $\|\bm{w}_{0}-\bm{w}^{*}\|$ by $D_{0}$ for
brevity.

Next:

$\displaystyle\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
$\displaystyle=\mathbb{E}\Big{[}\Big{\|}\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)+\bm{\zeta_{t}}\Big{\|}^{2}\Big{]}$ (33)
$\displaystyle=\underbrace{\mathbb{E}\Big{[}\Big{\|}\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)\Big{\|}^{2}\Big{]}}_{\text{(I)}}+d\sigma_{n}^{2}.$
(34)

Let $z_{t,i}=1$ if sample $i\in\mathcal{S}_{t}$ and 0 otherwise; note that
$\mathbb{P}(z_{t,i}=1)=\frac{b}{n}$. With this, we can rewrite (I) as:

(I)
$\displaystyle=\mathbb{E}\Big{[}\Big{\|}\frac{1}{b}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)z_{t,i}\Big{\|}^{2}\Big{]}$ (35)
$\displaystyle=\frac{1}{b^{2}}\sum_{i\in[n]}\|\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)\|^{2}\text{E}[z_{t,i}^{2}]+\frac{1}{b^{2}}\sum_{i\neq
j}\langle\text{clip}(\nabla f_{i}(\bm{w}_{t}),\tau),\text{clip}(\nabla
f_{j}(\bm{w}_{t}),\tau)\rangle\text{E}[z_{t,i}z_{t,j}].$ (36)

Note that $\text{E}[z_{t,i}^{2}]=\frac{b}{n}$ $\forall$ $i\in[n]$,
$\text{E}[z_{t,i}z_{t,j}]=\frac{b^{2}}{n^{2}}$ $\forall$ $i\neq j$,
$\|\text{clip}(\nabla f_{i}(\bm{w}_{t}),\tau)\|^{2}\leq\tau^{2}$ $\forall$
$i\in[n]$ and $\langle\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau),\text{clip}(\nabla
f_{j}(\bm{w}_{t}),\tau)\rangle\leq\|\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)\|\|\text{clip}(\nabla
f_{j}(\bm{w}_{t}),\tau)\|\leq\tau^{2}$ $\forall$ $i\neq j$. Using all this
above, we get:

$\text{(I)}\leq\tau^{2}\Big{(}1+\frac{1}{b}-\frac{1}{n}\Big{)}.$ (37)

Plugging the above as well as the value of $\sigma_{n}^{2}$ back in Equation
34, we get:

$\displaystyle\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
$\displaystyle\leq\tau^{2}\Big{(}1+\frac{1}{b}-\frac{1}{n}+\frac{\nu
dT\log(1/\delta)}{n^{2}\varepsilon^{2}}\Big{)}$ (38)
$\displaystyle\leq\tau^{2}\Big{(}2+\frac{\nu
dT\log(1/\delta)}{n^{2}\varepsilon^{2}}\Big{)}$ (39) $\displaystyle\leq
2\tau^{2}\Big{(}1+\frac{\nu dT\log(1/\delta)}{n^{2}\varepsilon^{2}}\Big{)}.$
(40)

Equation 39 follows because $b\geq 1$.

Plugging Equation 40 in Equation 32, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{\\{}\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{t})\|}\Big{)}(f_{i}(\bm{w}_{t})-f_{i}(\bm{w}^{*}))\Big{]}\Big{\\}}\leq\frac{D_{0}^{2}}{2\eta
T}+{\eta T\tau^{2}}\Big{(}\frac{1}{T}+\frac{\nu
d\log(\frac{1}{\delta})}{n^{2}\varepsilon^{2}}\Big{)}.$ (41)

Plugging in $\eta=\frac{C}{T\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}}$ in the above equation, where
$C>0$ is a constant of our choice, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{\\{}\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{t})\|}\Big{)}(f_{i}(\bm{w}_{t})-f_{i}(\bm{w}^{*}))\Big{]}\Big{\\}}\leq\Big{(}\frac{D_{0}^{2}}{2C}+C\Big{)}\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}.$ (42)

Recalling that $\widehat{t}\sim\text{Unif}[0,T-1]$, we can rewrite the above
as:

$\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{\widehat{t}})\|}\Big{)}(f_{i}(\bm{w}_{\widehat{t}})-f_{i}(\bm{w}^{*}))\Big{]}\leq\Big{(}\frac{D_{0}^{2}}{2C}+C\Big{)}\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}.$ (43)

Next, Equation 43 can be further rewritten as:

$\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{\widehat{t}})\|}\Big{)}(f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*})\Big{]}\leq\Big{(}\frac{D_{0}^{2}}{2C}+C\Big{)}\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\\\
+\frac{1}{n}\sum_{i\in[n]}\mathbb{E}\Big{[}\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{\widehat{t}})\|}\Big{)}\Big{]}(f_{i}(\bm{w}^{*})-f_{i}^{*}),$
(44)

where $f_{i}^{*}=\min_{\bm{w}\in\mathcal{W}}f_{i}(\bm{w})$.

From 5.1, $\|\nabla f_{i}(\bm{w}_{\widehat{t}})\|\leq G_{i}$; thus,
$\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{\widehat{t}})\|}\Big{)}\geq\min\big{(}1,\frac{\tau}{G_{i}}\big{)}$.
Using this and the fact that $f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*}\geq 0$, we
get:

$\min\Big{(}1,\frac{\tau}{\|\nabla
f_{i}(\bm{w}_{\widehat{t}})\|}\Big{)}(f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*})\geq\min\Big{(}1,\frac{\tau}{G_{i}}\Big{)}(f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*}).$

Using this in Equation 44 together with the fact that
$\min\big{(}1,\frac{\tau}{\|\nabla f_{i}(\bm{w}_{\widehat{t}})\|}\big{)}\leq
1$ and then dividing by $\tau$ throughout, we get:

$\frac{1}{n}\sum_{i\in[n]}\min\Big{(}\frac{1}{\tau},\frac{1}{G_{i}}\Big{)}\mathbb{E}[f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*}]\leq\Big{(}\frac{D_{0}^{2}}{2C}+C\Big{)}\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}+\frac{1}{n}\sum_{i\in[n]}\frac{(f_{i}(\bm{w}^{*})-f_{i}^{*})}{\tau}.$
(45)

Next, from the definition of $\alpha(\tau)$ in Definition 5.3, we have that:

$\displaystyle\frac{1}{n}\sum_{i\in[n]}\min\Big{(}\frac{1}{\tau},\frac{1}{G_{i}}\Big{)}{\mathbb{E}[f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*}]}$
$\displaystyle\geq\frac{\alpha(\tau)}{n}\sum_{i\in[n]}\frac{\mathbb{E}[f_{i}(\bm{w}_{\widehat{t}})-f_{i}^{*}]}{G_{n}}$
(46)
$\displaystyle=\Big{(}\frac{\alpha(\tau)}{G_{n}}\Big{)}\underbrace{\Big{(}{\mathbb{E}[f(\bm{w}_{\widehat{t}})]-f(\bm{w}^{*})}\Big{)}}_{=\text{OR}(T)}+\Big{(}\frac{\alpha(\tau)}{G_{n}}\Big{)}\Big{(}\frac{1}{n}\sum_{i\in[n]}(f_{i}(\bm{w}^{*})-f_{i}^{*})\Big{)}.$
(47)

Next, using Equation 47 in Equation 45 and the definition of $\text{OR}(T)$,
we get (after some rearrangement):

$\text{OR}(T)\leq\frac{1}{\alpha(\tau)}\Bigg{(}\Big{(}\frac{D_{0}^{2}}{2C}+C\Big{)}G_{n}\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}+\Big{(}\frac{G_{n}}{\tau\alpha(\tau)}-1\Big{)}\underbrace{\Bigg{(}\frac{1}{n}\sum_{i\in[n]}(f_{i}(\bm{w}^{*})-f_{i}^{*})\Bigg{)}}_{\Delta(\bm{w}^{*})}.$
(48)

Recalling the definition of $\Delta(\bm{w}^{*})$, we get the desired result. ∎

##  Appendix I Result for the Constrained Convex Case under Assumption 6.1

As mentioned in the main paper, Kamath et al. (2021) consider stochastic
convex optimization (SCO) and derive upper and lower bounds of
$\mathcal{O}(\varphi^{1-\frac{1}{k}})$ and $\Omega(\varphi^{1-\frac{1}{k}})$
for the generalization error (i.e.,
$\mathbb{E}_{\bm{x}\sim\mathcal{D}}[\ell(\bm{w}_{\text{priv}},\bm{x})-\ell(\bm{w}^{**},\bm{x})]$,
where $\bm{w}^{**}:=\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}\mathbb{E}_{\bm{x}\sim\mathcal{D}}[\ell(\bm{w},\bm{x})]$)
in the constrained convex case under an assumption similar to
6.1999Specifically, Kamath et al. (2021) assume coordinate-wise bounded
centered moments.. We shall now show that the same bounds hold for the
training error (i.e., $f(\bm{w}_{\text{priv}})-f(\bm{w}^{*})$) in empirical
risk minimization (which is what we consider in this work) in the constrained
convex case under 6.1.

######  Theorem I.1 (Constrained Convex Case).

Suppose 6.1 holds, $f$ is convex and $\mathcal{W}$ is a bounded convex set
with diameter $D_{\mathcal{W}}<\infty$. Fix some $\gamma\in(0,1)$. In
Algorithm 1, set
$\tau=\frac{G}{\gamma^{1/k}}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{-\frac{1}{2k}}$
and
$\eta_{t}=\eta=\frac{D_{\mathcal{W}}}{T\tau}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{-\frac{1}{2}}$
for all $t<T$. Then with a probability of at least $(1-\gamma)$ which is
w.r.t. the random dataset $\mathcal{Z}$ that we obtain, DP-SGD (Algorithm 1)
has the following guarantee:

$\textup{OR}(T)\leq\frac{5D_{\mathcal{W}}G}{2\gamma^{1/k}}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}.$

So if we set $T=\frac{1}{\varphi^{2}}$ above, we get the following bound for
the risk:

$\textup{OR}(T)\leq\frac{5D_{\mathcal{W}}G}{2^{\frac{1}{2}(1+\frac{1}{k})}\gamma^{1/k}}{\varphi^{(1-\frac{1}{k})}}.$

######  Remark I.2 (Comparison with Lipschitz Case).

As per the above theorem, the optimization risk is
$\mathcal{O}(\varphi^{1-{\frac{1}{k}}})$ in the bounded $k^{\text{th}}$ moment
constrained convex case. In comparison, the risk is $\mathcal{O}(\varphi)$ in
the Lipschitz convex case (equivalent to $k=\infty$); see Bassily et al.
(2014).

We also have a matching lower bound in this case.

######  Theorem I.3 (Lower Bound for Constrained Convex Case).

Suppose $\varphi<o(1)$ and $\delta<\exp(-\varepsilon^{2})$. There exists a
convex loss function $\ell$ and a bounded convex set $\mathcal{W}$, such that
for every $(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$ which tries to
solve for $\bm{w}^{*}=\text{arg min}_{\bm{w}\in\mathcal{W}}f(\bm{w})$ where
$f$ is the average loss for a dataset $\mathcal{Z}$ of $n$ samples drawn from
the data distribution $\mathcal{D}$, there exists a choice of $\mathcal{D}$
such that:

  * •

$f$ satisfies Assumption 6.1.

  * •

$\mathbb{E}_{\mathcal{Z}\sim\mathcal{D}^{n},\mathcal{A}}\Big{[}f(\bm{w}_{\mathcal{Z}}^{(\mathcal{A})})-f(\bm{w}^{*})\Big{]}\geq\Omega\big{(}\varphi^{1-\frac{1}{k}}\big{)}$,
where $\bm{w}_{\mathcal{Z}}^{(\mathcal{A})}$ is the output of algorithm
$\mathcal{A}$ on the dataset $\mathcal{Z}$.

######  Remark I.4 (Tightness of Theorem I.1).

The $\mathcal{O}(\varphi^{1-\frac{1}{k}})$ bound on the risk in Theorem I.1 is
tight (for $\delta<\exp(-\varepsilon^{2})$).

We now prove Theorem I.1; the proof of Theorem I.3 is deferred to Appendix M.

### Proof of Theorem I.1:

###### Proof.

First, using Lemma I.5, we have that:

$\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}),\tau)-\nabla
f(\bm{w})\Big{\|}\leq\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}},$ (49)

where
$G_{\mathcal{Z}}^{k}=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$.

For any $\bm{w}^{*}\in\text{argmin}_{\bm{w}\in\mathcal{W}}f(\bm{w})$,
$\|\bm{w}_{t+1}-\bm{w}^{*}\|\leq\|\bm{z}_{t+1}-\bm{w}^{*}\|$ as
$\bm{w}_{t+1}=\Pi_{\mathcal{W}}(\bm{z}_{t+1})$. So:

$\displaystyle\mathbb{E}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\|\bm{z}_{t+1}-\bm{w}^{*}\|^{2}]$ (50)
$\displaystyle=\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2\eta\mathbb{E}[\langle\bm{g}_{t},\bm{w}_{t}-\bm{w}^{*}\rangle]+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
(51)
$\displaystyle=\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2\eta\mathbb{E}\Big{[}\Big{\langle}\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau),\bm{w}_{t}-\bm{w}^{*}\Big{\rangle}\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
(52)
$\displaystyle=\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-{2\eta}\mathbb{E}\Big{[}\Big{\langle}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau),\bm{w}_{t}-\bm{w}^{*}\Big{\rangle}\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
(53)
$\displaystyle\leq\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2{\eta}\mathbb{E}[\langle\nabla
f(\bm{w}_{t}),\bm{w}_{t}-\bm{w}^{*}\rangle]$ (54) $\displaystyle\text{
}+{2\eta}\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2\eta\mathbb{E}[f(\bm{w}_{t})-f(\bm{w}^{*})]$
(55) $\displaystyle\text{ }+{2\eta
D_{\mathcal{W}}}\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}].$

Equation 55 follows from the convexity of $f$ together with the fact that
$\|\bm{w}_{t}-\bm{w}^{*}\|\leq D_{\mathcal{W}}$. Next, rearranging the above a
bit, followed by summing for $t=0$ through to $T-1$, and then dividing by
$2\eta T$ throughout, we get:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}$
$\displaystyle\leq\frac{D_{\mathcal{W}}^{2}}{2\eta
T}+\frac{\eta}{2T}\sum_{t=0}^{T-1}\mathbb{E}[\|\bm{g}_{t}\|^{2}]+\frac{D_{\mathcal{W}}}{T}\sum_{t=0}^{T-1}\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla f(\bm{w}_{t})\Big{\|}\Big{]}$ (56)
$\displaystyle\leq\frac{D_{\mathcal{W}}^{2}}{2\eta T}+{\eta
T\tau^{2}}\Bigg{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}+\frac{1}{T}\Bigg{)}+\frac{D_{\mathcal{W}}G_{\mathcal{Z}}^{k}}{\tau^{k-1}},$
(57)

where the last step follows by using Equation 40 and Equation 49.

Plugging in $\eta=\frac{D_{\mathcal{W}}}{T\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}}$ above, we get:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}$
$\displaystyle\leq\frac{3D_{\mathcal{W}}\tau}{2}\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}+\frac{D_{\mathcal{W}}G_{\mathcal{Z}}^{k}}{\tau^{k-1}}.$
(58)

Let us choose $\tau=\frac{G}{\gamma^{1/k}}\Big{(}\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{-\frac{1}{2k}}$ above,
where $\gamma\in(0,1)$. With that, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq
D_{\mathcal{W}}\Bigg{(}\frac{3G}{2\gamma^{\frac{1}{k}}}+\frac{G_{\mathcal{Z}}^{k}\gamma^{1-\frac{1}{k}}}{G^{k-1}}\Bigg{)}\Bigg{(}\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Bigg{)}^{\frac{1}{2}(1-\frac{1}{k})}.$
(59)

Now, using Markov’s inequality, $G_{\mathcal{Z}}^{k}\leq\frac{G^{k}}{\gamma}$
with a probability of at least $1-\gamma$ w.r.t. the random dataset
$\mathcal{Z}$. Plugging this above, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\frac{5D_{\mathcal{W}}G}{2\gamma^{1/k}}\Bigg{(}\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Bigg{)}^{\frac{1}{2}(1-\frac{1}{k})},$
(60)

with a probability of at least $1-\gamma$ w.r.t. the random dataset
$\mathcal{Z}$.

Lastly, plugging in $\varphi=\frac{\sqrt{\nu
d\log({1}/{\delta})}}{n\varepsilon}$, noting that
$\mathbb{E}[f(\bm{w}_{\widehat{t}})]-f(\bm{w}^{*})=\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}$
and using the definition of $\text{OR}(T)$, we get the final result. ∎

######  Lemma I.5 (Clipping Bias under 4.1).

Under 4.1, we have for any $\bm{w}\in\mathcal{W}$:

$\Big{\|}\frac{1}{n}\sum_{i\in[n]}\textup{clip}(\nabla
f_{i}(\bm{w}),\tau)-\nabla
f(\bm{w})\Big{\|}\leq\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}},$

where
$G_{\mathcal{Z}}^{k}:=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$.

###### Proof.

Using Corollary F.2 and 4.1, we have for any $\bm{w}\in\mathcal{W}$:

$\displaystyle\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}),\tau)-\nabla f(\bm{w})\Big{\|}$
$\displaystyle=\|\mathbb{E}_{i}[\text{clip}(\nabla f_{i}(\bm{w}),\tau)]-\nabla
f(\bm{w})\|$ (61) $\displaystyle\leq\frac{\mathbb{E}_{i}[\|\nabla
f_{i}(\bm{w})\|^{k}]}{\tau^{k-1}}$ (62)
$\displaystyle\leq\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}},$ (63)

where
$G_{\mathcal{Z}}^{k}=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$. ∎

##  Appendix J Full Version and Proof of Theorem 6.2

######  Theorem J.1 (Unconstrained Convex Case).

Suppose 6.1 holds, $f$ is convex and $\mathcal{W}=\mathbb{R}^{d}$. Fix some
$\gamma\in(0,1)$ and $C>0$. In Algorithm 1, set
$\tau=\frac{G}{\gamma^{1/k}}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{-\frac{1}{k+1}}$
and
$\eta_{t}=\eta=\frac{C}{T\tau}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{-\frac{1}{2}}$
for all $t<T$. Then with a probability of at least $(1-\gamma)$ which is
w.r.t. the random dataset $\mathcal{Z}$ that we obtain, DP-SGD (Algorithm 1)
has the following guarantee:

$\textup{OR}(T)\leq\frac{G}{\gamma^{1/k}}\Bigg{\\{}\frac{1}{2}\Bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+4C\Bigg{)}\Big{(}{\frac{1}{T}+\varphi^{2}}\Big{)}^{\frac{1}{2}(1-\frac{2}{k+1})}+(\|\bm{w}_{0}-\bm{w}^{*}\|+C)\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{(1-\frac{2}{k+1})}\Bigg{\\}}.$

So if we set $T=\frac{1}{\varphi^{2}}$ above (which is what we do in Theorem
6.2), we get the following bound for the risk:

$\textup{OR}(T)\leq\frac{G}{\gamma^{1/k}}\Bigg{\\{}\frac{1}{2^{\frac{1}{2}+\frac{1}{k+1}}}\Bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+4C\Bigg{)}\varphi^{(1-\frac{2}{k+1})}+{2^{1-\frac{2}{k+1}}(\|\bm{w}_{0}-\bm{w}^{*}\|+C)}\varphi^{2(1-\frac{2}{k+1})}\Bigg{\\}}.$

We prove this result now.

### Proof:

###### Proof.

Everything remains the same till Equation 54 in the proof of Theorem I.1. That
is, we have:

$\displaystyle\mathbb{E}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2{\eta}\mathbb{E}[\langle\nabla
f(\bm{w}_{t}),\bm{w}_{t}-\bm{w}^{*}\rangle]$ (64) $\displaystyle\text{
}+{2\eta}\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{]}+\eta^{2}\mathbb{E}[\|\bm{g}_{t}\|^{2}],$

where $\bm{w}^{*}=\text{argmin}_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})$.

Using Lemma I.5, we have:

$\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{]}\leq\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|],$
(65)

where
$G_{\mathcal{Z}}^{k}=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$.

Now using Lemma J.2 in Equation 65, we get:

$\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{]}\leq\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\Bigg{(}\|\bm{w}_{0}-\bm{w}^{*}\|+\eta
T\Bigg{(}G_{\mathcal{Z}}+\tau\sqrt{\frac{\nu
d\log(1/\delta)}{n^{2}\varepsilon^{2}}}\Bigg{)}\Bigg{)}.$ (66)

Using the above equation and Equation 40 in Equation 64 as well as the
convexity of $f$, we get:

$\displaystyle\mathbb{E}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|^{2}]-2{\eta}\mathbb{E}[f(\bm{w}_{t})-f(\bm{w}^{*})]$
(67) $\displaystyle\text{
}+\frac{{2\eta}G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\Bigg{(}\|\bm{w}_{0}-\bm{w}^{*}\|+{\eta
TG_{\mathcal{Z}}}+\eta T\tau\sqrt{\frac{\nu
d\log(1/\delta)}{n^{2}\varepsilon^{2}}}\Bigg{)}+2\eta^{2}\tau^{2}\Big{(}1+\frac{\nu
dT\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}.$

Next, summing the above for $t=0$ through to $T-1$, rearranging a bit and then
dividing by $2\eta T$ throughout, we get the following:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2\eta
T}+{\eta T\tau^{2}}\Bigg{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}+\frac{1}{T}\Bigg{)}\\\
+\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\Big{(}\|\bm{w}_{0}-\bm{w}^{*}\|+{\eta
TG_{\mathcal{Z}}}+\eta T\tau\sqrt{\frac{\nu
d\log(1/\delta)}{n^{2}\varepsilon^{2}}}\Big{)}.$ (68)

Let us choose $\eta=\frac{C}{T\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}}$, where $C>0$ is some constant of
our choice. With that, we get after simplifying a bit:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\Big{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2C}+C\Big{)}{\tau}\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}+\frac{(\|\bm{w}_{0}-\bm{w}^{*}\|+C)G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\\\
+\frac{CG_{\mathcal{Z}}^{k+1}}{\tau^{k}}\frac{1}{\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}}.$

Let us choose $\tau=\frac{G}{\gamma^{1/k}}\Big{(}\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{-\frac{1}{k+1}}$ above,
where $\gamma\in(0,1)$. With that, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\frac{G}{\gamma^{1/k}}\Bigg{\\{}\Bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2C}+C+\frac{CG_{\mathcal{Z}}^{k+1}}{\big{(}{G}/{\gamma^{1/k}}\big{)}^{k+1}}\Bigg{)}\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{\frac{1}{2}(1-\frac{2}{k+1})}\\\
+(\|\bm{w}_{0}-\bm{w}^{*}\|+C)\Bigg{(}\frac{G_{\mathcal{Z}}^{k}}{\big{(}{G}/{\gamma^{1/k}}\big{)}^{k}}\Bigg{)}\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{(1-\frac{2}{k+1})}\Bigg{\\}}.$
(69)

Let:

$\text{(I)}:=\Bigg{(}\frac{CG_{\mathcal{Z}}^{k+1}}{\big{(}{G}/{\gamma^{1/k}}\big{)}^{k+1}}\Bigg{)}\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{\frac{1}{2}(1-\frac{2}{k+1})}+(\|\bm{w}_{0}-\bm{w}^{*}\|+C)\Bigg{(}\frac{G_{\mathcal{Z}}^{k}}{\big{(}{G}/{\gamma^{1/k}}\big{)}^{k}}\Bigg{)}\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{(1-\frac{2}{k+1})}.$

Now note that $G_{\mathcal{Z}}\leq\frac{G}{\gamma^{1/k}}$ implies:

$\text{(I)}\leq\underbrace{C\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{\frac{1}{2}(1-\frac{2}{k+1})}+(\|\bm{w}_{0}-\bm{w}^{*}\|+C)\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{(1-\frac{2}{k+1})}}_{:=\text{(II)}}.$

Thus,
$\mathbb{P}_{\mathcal{Z}}\big{(}\text{(I)}\leq\text{(II)}\big{)}\geq\mathbb{P}_{\mathcal{Z}}(G_{\mathcal{Z}}\leq{G}/{\gamma^{1/k}})$.
But using Markov’s inequality, $G_{\mathcal{Z}}^{k}\leq\frac{G^{k}}{\gamma}$
with a probability of at least $1-\gamma$ w.r.t. the random dataset
$\mathcal{Z}$. Thus, $\text{(I)}\leq\text{(II)}$ with a probability of at
least $1-\gamma$. Using this in Equation 69, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\frac{G}{\gamma^{1/k}}\Bigg{\\{}\Bigg{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{2C}+2C\Bigg{)}\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{\frac{1}{2}(1-\frac{2}{k+1})}+\\\
(\|\bm{w}_{0}-\bm{w}^{*}\|+C)\Bigg{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Bigg{)}^{(1-\frac{2}{k+1})}\Bigg{\\}},$
(70)

with a probability of at least $1-\gamma$ w.r.t. the random dataset
$\mathcal{Z}$.

Lastly, plugging in $\varphi=\frac{\sqrt{\nu
d\log({1}/{\delta})}}{n\varepsilon}$, noting that
$\mathbb{E}[f(\bm{w}_{\widehat{t}})]-f(\bm{w}^{*})=\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}$
and using the definition of $\text{OR}(T)$, we get the final result. ∎

######  Lemma J.2.

In the setting of the proof of Theorem J.1, for any $0<t<T$, we have:

$\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|]\leq\|\bm{w}_{0}-\bm{w}^{*}\|+\eta
T\Bigg{(}G_{\mathcal{Z}}+\tau\sqrt{\frac{\nu
d\log(1/\delta)}{n^{2}\varepsilon^{2}}}\Bigg{)},$ (71)

where
$G_{\mathcal{Z}}^{k}:=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$.

###### Proof.

Let us denote $\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)$ by $\bm{u}_{t}$. Now:

$\displaystyle\mathbb{E}_{\mathcal{S}_{t}}[\|\bm{u}_{t}\|]$
$\displaystyle\leq\mathbb{E}_{\mathcal{S}_{t}}\Big{[}\frac{1}{b}\sum_{i\in\mathcal{S}_{t}}\|\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)\|\Big{]}$ (72)
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}\|\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)\|$ (73)
$\displaystyle\leq\frac{1}{n}\sum_{i\in[n]}\|\nabla f_{i}(\bm{w}_{t})\|$ (74)
$\displaystyle\leq\Big{(}\frac{1}{n}\sum_{i\in[n]}\|\nabla
f_{i}(\bm{w}_{t})\|^{k}\Big{)}^{1/k}\hskip 113.81102pt\text{(using Jensen's
inequality)}$ (75) $\displaystyle\leq G_{\mathcal{Z}},$ (76)

where
$G_{\mathcal{Z}}^{k}:=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$.

Now for any $t>0$:

$\displaystyle\mathbb{E}[\|\bm{w}_{t}-\bm{w}^{*}\|]$
$\displaystyle\leq\mathbb{E}[\|(\bm{w}_{t}-\bm{w}_{0})+(\bm{w}_{0}-\bm{w}^{*})\|]$
(77)
$\displaystyle\leq\mathbb{E}[\|\bm{w}_{t}-\bm{w}_{0}\|]+\|\bm{w}_{0}-\bm{w}^{*}\|$
(78)
$\displaystyle\leq\eta\mathbb{E}\Big{[}\Big{\|}\sum_{t^{\prime}=0}^{t-1}(\bm{u}_{t^{\prime}}+\bm{\zeta}_{t^{\prime}})\Big{\|}\Big{]}+\|\bm{w}_{0}-\bm{w}^{*}\|$
(79)
$\displaystyle\leq\eta\mathbb{E}\Big{[}\Big{\|}\sum_{t^{\prime}=0}^{t-1}\bm{u}_{t^{\prime}}\Big{\|}\Big{]}+\eta\mathbb{E}\Big{[}\Big{\|}\sum_{t^{\prime}=0}^{t-1}\bm{\zeta}_{t^{\prime}}\Big{\|}\Big{]}+\|\bm{w}_{0}-\bm{w}^{*}\|$
(80)
$\displaystyle\leq\eta\sum_{t^{\prime}=0}^{t-1}\mathbb{E}[\|\bm{u}_{t^{\prime}}\|]+\eta\sqrt{\mathbb{E}\Big{[}\Big{\|}\sum_{t^{\prime}=0}^{t-1}\bm{\zeta}_{t^{\prime}}\Big{\|}^{2}\Big{]}}+\|\bm{w}_{0}-\bm{w}^{*}\|$
(81) $\displaystyle\leq{\eta
tG_{\mathcal{Z}}}+\eta\sqrt{t\sigma_{n}^{2}d}+\|\bm{w}_{0}-\bm{w}^{*}\|,$ (82)

where Equation 82 follows by using Equation 76 and because
$\sum_{t^{\prime}=0}^{t-1}\bm{\zeta}_{t^{\prime}}$ is
$\mathcal{N}(\vec{0},t\sigma_{n}^{2}\text{I}_{d})$. Plugging in the value of
$\sigma_{n}^{2}$ and using the fact that $t<T$, we get the desired result. ∎

##  Appendix K Full Version and Proof of Theorem 6.5

######  Theorem K.1 (Unconstrained Convex Case Under 6.4).

Suppose Assumptions 6.1 and 6.4 hold, $f$ is convex and
$\mathcal{W}=\mathbb{R}^{d}$. Fix some $C>0$. In Algorithm 1, set
$T\geq\frac{1}{\varphi^{2}}$,
$\tau={G}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{-\frac{1}{2k}}$ and
$\eta_{t}=\eta=\frac{C}{T\tau}\Big{(}\frac{1}{T}+\varphi^{2}\Big{)}^{-\frac{1}{2}}$
for all $t<T$. Then with a probability of at least ${3}/{4}$ which is w.r.t.
the random dataset $\mathcal{Z}$ that we obtain, DP-SGD (Algorithm 1) has the
following improved guarantee:

$\textup{OR}(T)\leq
G\Bigg{\\{}\Big{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+2C\Big{)}\Big{(}{\frac{1}{T}+\varphi^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}+{16}\varphi^{(1-\frac{1}{k})}D\Bigg{\\}}.$

So if we set $T=\frac{1}{\varphi^{2}}$ above (which is what we do in Theorem
6.5), we get the following bound for the risk:

$\textup{OR}(T)\leq{G}\Bigg{\\{}2^{\frac{1}{2}(1-\frac{1}{k})}\Big{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+2C\Big{)}+{16}D\Bigg{\\}}\varphi^{(1-\frac{1}{k})}.$

We now prove this result.

### Proof:

###### Proof.

Similar to Equation 64 in the proof of Theorem J.1, taking expectation only
w.r.t. the randomness in the current iteration $t$, we have:

$\displaystyle\mathbb{E}_{t}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]$
$\displaystyle\leq\|\bm{w}_{t}-\bm{w}^{*}\|^{2}-2{\eta}\langle\nabla
f(\bm{w}_{t}),\bm{w}_{t}-\bm{w}^{*}\rangle$ (83) $\displaystyle\text{
}+{2\eta}\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\|\bm{w}_{t}-\bm{w}^{*}\|+\eta^{2}\mathbb{E}_{t}[\|\bm{g}_{t}\|^{2}],$

where $\bm{w}^{*}=\text{argmin}_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})$.

Equation 65 in the proof of Theorem J.1 also holds here, i.e., we have:

$\Big{\|}\frac{1}{n}\sum_{i\in[n]}\text{clip}(\nabla
f_{i}(\bm{w}_{t}),\tau)-\nabla
f(\bm{w}_{t})\Big{\|}\|\bm{w}_{t}-\bm{w}^{*}\|\leq\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\|\bm{w}_{t}-\bm{w}^{*}\|,$
(84)

where
$G_{\mathcal{Z}}^{k}=\frac{1}{n}\sum_{i=1}^{n}(G(\bm{x}_{i},y_{i}))^{k}$.

Plugging in Equation 84 into Equation 83, we get:

$\displaystyle\mathbb{E}_{t}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]$
$\displaystyle\leq\|\bm{w}_{t}-\bm{w}^{*}\|^{2}-2{\eta}\langle\nabla
f(\bm{w}_{t}),\bm{w}_{t}-\bm{w}^{*}\rangle+{2\eta}\Big{(}\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{)}+\eta^{2}\mathbb{E}_{t}[\|\bm{g}_{t}\|^{2}].$
(85)

Further, using Equation 40 to bound $\mathbb{E}_{t}[\|\bm{g}_{t}\|^{2}]$ as
well as the convexity of $f$ above, we get:

$\mathbb{E}_{t}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]\leq\|\bm{w}_{t}-\bm{w}^{*}\|^{2}\underbrace{-2{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))+{2\eta}\Big{(}\frac{G_{\mathcal{Z}}^{k}}{\tau^{k-1}}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{)}}_{\text{(I)}}+2\eta^{2}\tau^{2}\Big{(}1+\frac{\nu
dT\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}.$ (86)

Now, plugging in our choice of $\tau={G}\Big{(}\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{-\frac{1}{2k}}$ in (I) and
using the fact that $T\geq\frac{n^{2}\varepsilon^{2}}{\nu
d\log({1}/{\delta})}$, we get:

(I)
$\displaystyle\leq-2{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))+4\eta\Big{(}\frac{G_{\mathcal{Z}}^{k}}{G^{k-1}}\Big{)}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}\|\bm{w}_{t}-\bm{w}^{*}\|.$
(87)

Now note that $G_{\mathcal{Z}}^{k}\|\bm{w}_{t}-\bm{w}^{*}\|$ depends on the
random dataset $\mathcal{Z}$. But $G_{\mathcal{Z}}^{k}\leq 4{G^{k}}$ implies
$G_{\mathcal{Z}}^{k}\|\bm{w}_{t}-\bm{w}^{*}\|\leq
4{G^{k}}\|\bm{w}_{t}-\bm{w}^{*}\|$ for all $t$. Thus,
$\mathbb{P}_{\mathcal{Z}}\Big{(}G_{\mathcal{Z}}^{k}\|\bm{w}_{t}-\bm{w}^{*}\|\leq
4{G^{k}}\|\bm{w}_{t}-\bm{w}^{*}\|,\text{ }\forall
t\Big{)}\geq\mathcal{P}_{\mathcal{Z}}\Big{(}G_{\mathcal{Z}}^{k}\leq
4{G^{k}}\Big{)}\geq\frac{3}{4}$, where the last step follows from Markov’s
inequality. Thus, for all $t$, we have:

(I) $\displaystyle\leq-2{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))+{16\eta
G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}\|\bm{w}_{t}-\bm{w}^{*}\|,$
(88)

with a probability of at least $\frac{3}{4}$ w.r.t. the random dataset
$\mathcal{Z}$. Henceforth, we will not mention this and it should be inferred
directly.

Case 1: $\|\bm{w}_{t}-\bm{w}^{*}\|\leq D$.
In this case, we simply have:

(I) $\displaystyle\leq-2{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))+{16\eta
G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}D.$
(89)

Case 2: $\|\bm{w}_{t}-\bm{w}^{*}\|>D$.
In this case, we have:

(I)
$\displaystyle\leq-{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))-{\eta}\underbrace{\Big{\\{}(f(\bm{w}_{t})-f(\bm{w}^{*}))-{16G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}\|\bm{w}_{t}-\bm{w}^{*}\|\Big{\\}}}_{\geq
0\text{ using \lx@cref{creftypecap~refnum}{asmp1-may4}}}$ (90)
$\displaystyle\leq-{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*})).$ (91)

Combining equations (89) and (90), we have:

(I) $\displaystyle\leq-{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))+{16\eta
G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}D.$
(92)

Now plugging Equation 92 in Equation 86, we get:

$\mathbb{E}_{t}[\|\bm{w}_{t+1}-\bm{w}^{*}\|^{2}]\leq\|\bm{w}_{t}-\bm{w}^{*}\|^{2}-{\eta}(f(\bm{w}_{t})-f(\bm{w}^{*}))+{16\eta
G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}D+2\eta^{2}\tau^{2}\Big{(}1+\frac{\nu
dT\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}.$ (93)

Next, summing the above for $t=0$ through to $T-1$ after taking expectation
throughout, rearranging a bit and then dividing by $\eta T$ throughout, we get
the following:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{\eta
T}+{2\eta T\tau^{2}}\Bigg{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}+\frac{1}{T}\Bigg{)}+{16G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}D.$
(94)

Plugging in our choice of $\eta=\frac{C}{T\tau\sqrt{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}}$, where $C>0$ is some constant of
our choice, and $\tau={G}\Big{(}\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{-\frac{1}{2k}}$, we get:

$\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}\leq\Big{(}\frac{\|\bm{w}_{0}-\bm{w}^{*}\|^{2}}{C}+2C\Big{)}G\Big{(}{\frac{1}{T}+\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}\\\
+{16G}\Big{(}\frac{\nu
d\log({1}/{\delta})}{n^{2}\varepsilon^{2}}\Big{)}^{\frac{1}{2}(1-\frac{1}{k})}D.$
(95)

Lastly, plugging in $\varphi=\frac{\sqrt{\nu
d\log({1}/{\delta})}}{n\varepsilon}$, noting that
$\mathbb{E}[f(\bm{w}_{\widehat{t}})]-f(\bm{w}^{*})=\frac{1}{T}\sum_{t=0}^{T-1}\Big{(}\mathbb{E}[f(\bm{w}_{t})]-f(\bm{w}^{*})\Big{)}$
and using the definition of $\text{OR}(T)$, we get the final result. ∎

##  Appendix L Full Version and Proof of Theorem 6.6

######  Theorem L.1 (Lower Bound for Unconstrained Convex Case Under 6.4).

Suppose $\varphi<o(1)$ and $\delta<\exp(-\varepsilon^{2})$. There exists a
convex loss function $\ell$, such that for every $(\varepsilon,\delta)$-DP
algorithm $\mathcal{A}$ which tries to solve for $\bm{w}^{*}=\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}f(\bm{w})$ where $f$ is the average loss for a
dataset $\mathcal{Z}$ of $n$ samples drawn from the data distribution
$\mathcal{D}$, there exists a choice of $\mathcal{D}$ such that:

  * •

$f$ satisfies Assumptions 6.1 and 6.4 (the latter up to constant terms and
with a probability of at least
$1-\exp\big{(}-\mathcal{O}\big{(}\nicefrac{{\sqrt{d\log(1/\delta)}}}{{\varepsilon}}\big{)}\big{)}$
w.r.t. $\mathcal{Z}$).

  * •

$\mathbb{E}_{\mathcal{Z}\sim\mathcal{D}^{n},\mathcal{A}}\Big{[}f(\bm{w}_{\mathcal{Z}}^{(\mathcal{A})})-f(\bm{w}^{*})\Big{]}\geq\Omega\big{(}\varphi^{1-\frac{1}{k}}\big{)}$,
where $\bm{w}_{\mathcal{Z}}^{(\mathcal{A})}$ is the output of algorithm
$\mathcal{A}$ on the dataset $\mathcal{Z}$.

As mentioned in the main text, even though we follow the proof outline of
Theorem 6.4 of Kamath et al. (2021), our proof is more involved. First, we had
to use a non-obvious loss function $\ell$ (to obtain the lower bound on) for
the unconstrained case. Second, since we are in the ERM setting, we have to
lower bound the expected training error which is harder than lower bounding
the expected generalization error in the SCO setting of Kamath et al. (2021);
see the footnote in the line after Equation 124 (i.e., footnote 12) for
details. Finally, note that Kamath et al. (2021) derive a bound for
$(0,\rho)$-zCDP while our bound is for $(\varepsilon,\delta)$-DP. To our
knowledge, $(\varepsilon,\delta)$-DP does not imply $(0,\tilde{\rho})$-zCDP
for some $\tilde{\rho}$ due to which we had to re-derive an important tool in
their analysis (specifically, Theorem 1.4 of Kamath et al. (2021)); see Lemma
L.3. That is also the reason we had to impose the constraint of
$\delta<\exp(-\varepsilon^{2})$.

###### Proof.

We shall borrow some ideas from Acharya et al. (2021) and Kamath et al.
(2021).

Let $\mathcal{V}$ be a set of $d$-dimensional points satisfying:

  * •

For all $\bm{v}\in\mathcal{V}$, $\bm{v}\in\\{0,1\\}^{d}$ and the number of 1’s
in $\bm{v}$ is $\frac{d}{2}$.

  * •

For all $\bm{v},\bm{v}^{\prime}\in\mathcal{V}$,
$d_{\text{Ham}}(\bm{v},\bm{v}^{\prime})\geq\frac{d}{8}$.

By Lemma 6 of Acharya et al. (2021), there must exist such a $\mathcal{V}$
with cardinality at least $2^{\frac{7d}{128}}$. Note that
$\|\bm{v}\|=\sqrt{d/2}$ for all $\bm{v}\in\mathcal{V}$.

Next, similar to Kamath et al. (2021), let $Q_{\bm{v}}$ be a distribution
whose support includes $\vec{0}_{d}$ and $p^{-1/k}\bm{v}$ for
$p=\frac{2\sqrt{d\log(1/\delta)}}{n\varepsilon}<\frac{1}{2}$, such that
$\mathbb{P}_{\bm{x}\sim Q_{\bm{v}}}(\bm{x}=\vec{0}_{d})=1-p$ and
$\mathbb{P}_{\bm{x}\sim Q_{\bm{v}}}(\bm{x}=p^{-1/k}\bm{v})=p$. Note that:

$\mathbb{E}_{\bm{x}\sim Q_{\bm{v}}}[\bm{x}]=p^{1-\frac{1}{k}}\bm{v}\text{ and
}\mathbb{E}_{\bm{x}\sim Q_{\bm{v}}}[\|\bm{x}\|^{k}]=\|\bm{v}\|^{k}.$ (96)

Now, let $\ell:\mathbb{R}^{d}\times\mathbb{R}^{d}\xrightarrow{}\mathbb{R}$ be
defined as:

$\ell(\bm{w},\bm{x})=-\langle\bm{w},\bm{x}\rangle+2\|\bm{x}\|\max\big{(}\|\bm{w}\|-1,0\big{)}.$
(97)

We have a dataset $\mathcal{Z}_{\bm{v}}$ of $n$ i.i.d. samples
$\\{\bm{x}_{i}\\}_{i=1}^{n}$ drawn from $Q_{\bm{v}}$. Then, we denote the
$i^{\text{th}}$ sample’s loss in $\mathcal{Z}_{\bm{v}}$ by:

$f_{\bm{v},i}(\bm{w})=\ell(\bm{w},\bm{x}_{i})=-\langle\bm{w},\bm{x}_{i}\rangle+2\|\bm{x}_{i}\|\max\big{(}\|\bm{w}\|-1,0\big{)}.$
(98)

Here, the subscript $\bm{v}$ denotes that $\mathcal{Z}_{\bm{v}}$ is drawn from
$Q_{\bm{v}}$. Next, the average loss is:

$f_{\bm{v}}(\bm{w})=\frac{1}{n}\sum_{i=1}^{n}f_{\bm{v},i}(\bm{w})=-\langle\bm{w},\overline{\bm{x}}\rangle+2\|\overline{\bm{x}}\|\max\big{(}\|\bm{w}\|-1,0\big{)},$
(99)

where $\overline{\bm{x}}=\frac{1}{n}\sum_{i=1}^{n}\bm{x}_{i}$. Equation 99
follows because each $\bm{x}_{i}=c_{i}\bm{v}$, where $c_{i}=0$ with a
probability of $1-p$ and $c_{i}=p^{-1/k}$ otherwise, due to which
$\frac{1}{n}\sum_{i=1}^{n}\|\bm{x}_{i}\|=\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\bm{x}_{i}\Big{\|}=\|\overline{\bm{x}}\|$.

Note that $q(\bm{w})=\max\big{(}\|\bm{w}\|-1,0\big{)}$ is convex. This is
because both $q_{1}(\bm{w})=\|\bm{w}\|-1$ and $q_{2}(\bm{w})=0$ are convex and
the point-wise maximum of convex functions is also convex. Thus,
$f_{\bm{v}}(\bm{w})$ is convex.

Now, we shall show that 6.1 holds. It can be checked that
$\|\nabla\ell(\bm{w},\bm{x})\|\leq 3\|\bm{x}\|$ for all
$\bm{w}\in\mathbb{R}^{d}$. Thus,

$\mathbb{E}_{\bm{x}\sim Q_{\bm{v}}}[\|\nabla\ell(\bm{w},\bm{x})\|^{k}]\leq
3^{k}\mathbb{E}_{\bm{x}\sim Q_{\bm{v}}}[\|\bm{x}\|^{k}]=(3\|\bm{v}\|)^{k},$
(100)

where the last step follows from Equation 96. Thus, 6.1 holds here with
$G=3\|\bm{v}\|=3\sqrt{\frac{d}{2}}$.

Let us first obtain $\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}f_{\bm{v}}(\bm{w})$. Note that if
$\|\overline{\bm{x}}\|=0$ (which happens when all the $\bm{x}_{i}$’s are
$\vec{0}_{d}$), $f_{\bm{v}}$ is identically 0 and so any point is a minimizer.
So, let us focus on the case of $\|\overline{\bm{x}}\|>0$; we claim that
$\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}f_{\bm{v}}(\bm{w})=\hat{\bm{x}}:={\overline{\bm{x}}}/{\|\overline{\bm{x}}\|}$.
Clearly, $\hat{\bm{x}}=\text{arg min}_{\bm{w}:\|\bm{w}\|\leq
1}f_{\bm{v}}(\bm{w})$. Also, for any $\bm{w}$ such that $\|\bm{w}\|>1$, we
have:

$\displaystyle f_{\bm{v}}(\bm{w})-f_{\bm{v}}(\hat{\bm{x}})$
$\displaystyle=-\langle\bm{w},\overline{\bm{x}}\rangle+2\|\overline{\bm{x}}\|\big{(}\|\bm{w}\|-1\big{)}+\|\overline{\bm{x}}\|$
(101)
$\displaystyle=\Big{(}-\langle\bm{w},\overline{\bm{x}}\rangle+\|\overline{\bm{x}}\|\|\bm{w}\|\Big{)}+\|\overline{\bm{x}}\|\|\bm{w}\|-\|\overline{\bm{x}}\|$
(102) $\displaystyle\geq\|\overline{\bm{x}}\|(\|\bm{w}\|-1)$ (103)
$\displaystyle>0.$ (104)

Equation 106 follows from the Cauchy-Schwarz inequality while Equation 104
follows because $\|\bm{w}\|>1$. Thus,
$f_{\bm{v}}(\bm{w})>f_{\bm{v}}(\hat{\bm{x}})$ for all $\bm{w}$ such that
$\|\bm{w}\|>1$. Hence, we must have $\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}f_{\bm{v}}(\bm{w})=\hat{\bm{x}}$. Also, note
that since each $\bm{x}_{i}=c_{i}\bm{v}$ where $c_{i}\in\\{0,p^{-1/k}\\}$,
$\overline{\bm{x}}=\Big{(}\frac{1}{n}\sum_{i=1}^{n}c_{i}\Big{)}\bm{v}$ with
$\frac{1}{n}\sum_{i=1}^{n}c_{i}>0$ and so,

$\hat{\bm{x}}=\bm{v}/\|\bm{v}\|:=\bm{w}_{\bm{v}}^{*},$ (105)

which is independent of the dataset $\mathcal{Z}_{\bm{v}}$ that we receive; in
fact, $\bm{w}_{\bm{v}}^{*}=\text{arg
min}_{\bm{w}\in\mathbb{R}^{d}}\mathbb{E}_{\bm{x}\sim
Q_{\bm{v}}}[\ell(\bm{w},\bm{x})]$. We shall be using these facts later.

Rewriting Equation 103 by replacing $\hat{\bm{x}}$ with $\bm{w}_{\bm{v}}^{*}$
in the LHS, we get:

$f_{\bm{v}}(\bm{w})-f_{\bm{v}}(\bm{w}_{\bm{v}}^{*})\geq\|\overline{\bm{x}}\|(\|\bm{w}\|-1)\text{
}\forall\text{ }\bm{w}\in\mathbb{R}^{d}.$ (106)

Also note that Equation 106 holds trivially for the case of
$\|\overline{\bm{x}}\|=0$.

Finally, let us show that 6.4 also holds up to constant factors with high-
probability over the dataset $\mathcal{Z}_{\bm{v}}$. Specifically, we shall
restrict our attention to
$\|\overline{\bm{x}}\|\geq\frac{p^{1-\frac{1}{k}}}{2}\|\bm{v}\|$. Since
$\mathbb{E}[\|\overline{\bm{x}}\|]=p^{1-\frac{1}{k}}\|\bm{v}\|$, using the
Chernoff bound for Binomial random variables101010Specifically, for $n$ i.i.d.
binomial ($\in\\{0,1\\}$) random variables $\\{Z_{i}\\}_{i=1}^{n}$ with
$\mathbb{P}(Z_{i}=1)=\mu$ $\forall$ $i\in[n]$, we use
$\mathbb{P}\Big{(}\frac{1}{n}\sum_{i=1}^{n}Z_{i}\leq{\mu}(1-\beta)\Big{)}\leq\exp(-\frac{n\mu\beta^{2}}{3})$
for $\beta\in(0,1)$., we have
$\|\overline{\bm{x}}\|\geq\frac{p^{1-\frac{1}{k}}}{2}\|\bm{v}\|$ with a
probability of at least

$1-\exp(-\mathcal{O}(np))=1-\exp\Big{(}-\mathcal{O}\Big{(}\frac{\sqrt{d\log(1/\delta)}}{\varepsilon}\Big{)}\Big{)},$
(107)

where the last step follows by plugging in
$p=\frac{2\sqrt{d\log(1/\delta)}}{n\varepsilon}$.

Now, let us consider all $\bm{w}$ such that
$\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|\geq 4$ – in this case, since
$\|\bm{w}_{\bm{v}}^{*}\|=1$, we must have $\|\bm{w}\|\geq 3$. Further

$\displaystyle\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|$ $\displaystyle\leq\|\bm{w}\|+1$
(108) $\displaystyle\leq 2(\|\bm{w}\|-1),$ (109)

where the last step holds for $\|\bm{w}\|\geq 3$. Equation 108 follows by
using the triangle inequality and the fact that $\|\bm{w}_{\bm{v}}^{*}\|=1$.
Using Equation 109 in Equation 106, we get for
$\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|\geq 4$:

$f_{\bm{v}}(\bm{w})-f_{\bm{v}}(\bm{w}_{\bm{v}}^{*})\geq\Omega\Big{(}\|\overline{\bm{x}}\|\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|\Big{)}.$
(110)

Recall that we are restricting our attention to
$\|\overline{\bm{x}}\|\geq\frac{p^{1-\frac{1}{k}}}{2}\|\bm{v}\|$ which occurs
with probability $\geq
1-\exp\Big{(}-\mathcal{O}\Big{(}\frac{\sqrt{d\log(1/\delta)}}{\varepsilon}\Big{)}\Big{)}$
(w.r.t. the random dataset $\mathcal{Z}_{\bm{v}}$). Using this as well as the
fact that $\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|$ is independent of
$\mathcal{Z}_{\bm{v}}$ in Equation 110, and then plugging in the value of
$p=\frac{2\sqrt{d\log(1/\delta)}}{n\varepsilon}$ and $G=3\|v\|$ (as defined
after Equation 100), we get:

$f_{\bm{v}}(\bm{w})-f_{\bm{v}}(\bm{w}_{\bm{v}}^{*})\geq\Omega\Big{(}p^{1-\frac{1}{k}}{\|\bm{v}\|}\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|\Big{)}=\Omega\Big{(}\big{(}\nicefrac{{\sqrt{d\log(1/\delta)}}}{{n\varepsilon}}\big{)}^{1-\frac{1}{k}}G\|\bm{w}-\bm{w}_{\bm{v}}^{*}\|\Big{)},$
(111)

with probability $\geq
1-\exp\Big{(}-\mathcal{O}\Big{(}\frac{\sqrt{d\log(1/\delta)}}{\varepsilon}\Big{)}\Big{)}$.
Hence, 6.4 holds up to constant factors with high-probability over the dataset
$\mathcal{Z}_{\bm{v}}$.

Now that we have shown that $f_{\bm{v}}$ is convex and satisfies Assumptions
6.1 and 6.4, let us move onto the lower bound. Let us denote the output of the
$(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$ (on the dataset
$\mathcal{Z}_{\bm{v}}$) by $\bm{w}_{\bm{v}}^{(\mathcal{A})}$111111A better
choice of notation would have been to put $\mathcal{Z}_{\bm{v}}$ instead of
just $\bm{v}$ in the subscript; however, we do not do so to avoid overloading
notation going further.. We shall consider two cases.

Case 1, $\|\bm{w}_{\bm{v}}^{(\mathcal{A})}\|\geq 3$: Using Equation 106, we
get

$\displaystyle
f_{\bm{v}}(\bm{w}_{\bm{v}}^{(\mathcal{A})})-f_{\bm{v}}(\bm{w}_{\bm{v}}^{*})$
$\displaystyle\geq 2\|\overline{\bm{x}}\|.$ (112)