# Differentially Private Generalized Linear Models Revisited

Raman Arora Raef Bassily Cristóbal Guzmán  Department of Computer Science, The
Johns Hopkins University<EMAIL_ADDRESS>of Computer Science &
Engineering and the Translational Data Analytics Institute (TDAI), The Ohio
State University<EMAIL_ADDRESS>of Applied Mathematics,
University of Twente and Institute for Mathematical and Computational
Engineering, Pontificia Universidad Católica de Chile<EMAIL_ADDRESS>Michael Menart  Enayat Ullah Department of Computer Science & Engineering, The
Ohio State University<EMAIL_ADDRESS>of Computer Science, The
Johns Hopkins University<EMAIL_ADDRESS>
###### Abstract

We study the problem of $(\epsilon,\delta)$-differentially private learning of
linear predictors with convex losses. We provide results for two subclasses of
loss functions. The first case is when the loss is smooth and non-negative but
not necessarily Lipschitz (such as the squared loss). For this case, we
establish an upper bound on the excess population risk of
$\widetilde{O}\left(\frac{\|w^{*}\|}{\sqrt{n}}+\min\left\\{\frac{\|w^{*}\|^{2}}{(n\epsilon)^{2/3}},\frac{\sqrt{d}\|w^{*}\|^{2}}{n\epsilon}\right\\}\right)$,
where $n$ is the number of samples, $d$ is the dimension of the problem, and
$w^{*}$ is the minimizer of the population risk. Apart from the dependence on
$\|w^{\ast}\|$, our bound is essentially tight in all parameters. In
particular, we show a lower bound of
$\widetilde{\Omega}\left(\frac{1}{\sqrt{n}}+{\min\left\\{\frac{\|w^{*}\|^{4/3}}{(n\epsilon)^{2/3}},\frac{\sqrt{d}\|w^{*}\|}{n\epsilon}\right\\}}\right)$.
We also revisit the previously studied case of Lipschitz losses [26]. For this
case, we close the gap in the existing work and show that the optimal rate is
(up to log factors)
$\Theta\left(\frac{\|w^{*}\|}{\sqrt{n}}+\min\left\\{\frac{\|w^{*}\|}{\sqrt{n\epsilon}},\frac{\sqrt{\text{rank}}\|w^{*}\|}{n\epsilon}\right\\}\right)$,
where rank is the rank of the design matrix. This improves over existing work
in the high privacy regime. Finally, our algorithms involve a private model
selection approach that we develop to enable attaining the stated rates
without a-priori knowledge of $\|w^{*}\|$.

##  1 Introduction

Ensuring privacy of users’ data in machine learning algorithms is an important
desideratum for multiple domains, such as social and medical sciences.
Differential privacy (DP) has become the gold standard of privacy-preserving
data analysis as it offers formal and quantitative privacy guarantees and
enjoys many attractive properties from an algorithmic design perspective [14].
However, for various basic machine learning tasks, the known risk guarantees
are potentially sub-optimal and pessimistic.

In this work, we make progress towards resolving one of the most basic machine
learning problems under differential privacy: learning linear predictors with
convex losses.

###  1.1 Related Work

Differentially private machine learning has been thoroughly studied for over a
decade. In the Lipschitz-convex setting, tight rates are known for both the
empirical and population risk [9, 6]. Specifically, it was shown that in the
constrained setting, dependence on the dimension in the form of
$\Omega\big{(}\frac{\sqrt{d}}{n\epsilon}\big{)}$ is unavoidable even for
generalized linear models (GLM) (see Section 2 for a formal definition). By
contrast, in the unconstrained setting, it has been shown that dimension
independent rates are possible for GLMs [17]. In this setting, assuming prior
knowledge of $\left\|{w^{*}}\right\|$, the best known rate is
$O\left({\frac{\left\|{w^{*}}\right\|}{\sqrt{n}}+\frac{\left\|{w^{*}}\right\|\sqrt{\text{rank}}}{n\epsilon}}\right)$
[26], where rank is the expected rank of the design matrix. However, without
prior knowledge of $\left\|{w^{*}}\right\|$, these methods exhibit quadratic
dependence on $\left\|{w^{*}}\right\|$. Furthermore, these results crucially
rely on the assumption that the loss is Lipschitz to bound the sensitivity.
Although gradient clipping has been proposed to remedy this problem [26, 11],
it is known that the solution obtained by clipping may not coincide with the
one of the original model.

Without Lipschitzness, work on differentially private GLMs has largely been
limited to linear regression [30, 12]. Here, dimension independent rates have
only been obtained under certain sparsity assumptions.

More generally, smooth non-negative losses have been studied in the non-
private setting by [25], where it was shown such functions can obtain risk
guarantees with linear dependence on the minimizer norm (as in the Lipschitz
case). This work also established a lower bound of
$\Omega\big{(}\frac{1}{\sqrt{n}}\big{)}$ on the excess population risk for
this class of loss functions. [23] additionally establishes a lower bound of
$\Omega\left\\{{\min\left\\{{\frac{\left\|{w^{*}}\right\|^{2}+d}{n},\frac{\left\|{w^{*}}\right\|}{\sqrt{n}}}\right\\}}\right\\}$
on the excess population risk by way of linear regression111The [25] bound
assumes $\|{\mathcal{Y}}\|,H,\|{\mathcal{X}}\|=\Omega(1)$. The bounds of [23]
were originally stated for the constrained setting, but can easily be
converted. More details in Appendix E..

###  1.2 Our Contributions

| $H$-Smooth, Non-negative |  $G$-Lipschitz
---|---|---
| $\sqrt{H}\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|\leq\left\|{{\mathcal{Y}}}\right\|$ | $\sqrt{H}\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|>\left\|{{\mathcal{Y}}}\right\|$ |
| $d\leq\left({\frac{\left\|{w^{*}}\right\|\sqrt{H}\left\|{{\mathcal{X}}}\right\|n\epsilon}{\left\|{{\mathcal{Y}}}\right\|}}\right)^{2/3}$ | $d>\left({\frac{\left\|{w^{*}}\right\|\sqrt{H}\left\|{{\mathcal{X}}}\right\|n\epsilon}{\left\|{{\mathcal{Y}}}\right\|}}\right)^{2/3}$ | $d\leq\left({n\epsilon}\right)^{2/3}$ | $d>\left({n\epsilon}\right)^{2/3}$ | $\text{rank}\leq n\epsilon$ | $\text{rank}>n\epsilon$
DP | UB | $\frac{\sqrt{H}\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|\sqrt{d}}{n\epsilon}$ | $\frac{\left({\sqrt{H}\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|}\right)^{4/3}\left\|{{\mathcal{Y}}}\right\|^{2/3}}{\left({n\epsilon}\right)^{2/3}}$ | $\frac{H\left\|{w^{*}}\right\|^{2}\left\|{{\mathcal{X}}}\right\|^{2}\sqrt{d}}{n\epsilon}$ | $\frac{H\left\|{w^{*}}\right\|^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{\left({n\epsilon}\right)^{2/3}}$ | $\frac{G\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|\sqrt{\text{rank}}}{n\epsilon}$ | $\frac{G\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|}{\sqrt{n\epsilon}}$
| Theorem 1 | Theorem 2 | Theorem 1 |  Theorem 2, 3 | [26] |  Theorem 10, 5
LB | Tight | Tight | $\frac{\sqrt{H}\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|\sqrt{d}}{n\epsilon}$ | $\frac{\left({\sqrt{H}\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|}\right)^{4/3}\left\|{{\mathcal{Y}}}\right\|^{2/3}}{\left({n\epsilon}\right)^{2/3}}$ | Tight | Tight
| Theorem 4 | Theorem 4 | Theorem 4 | Theorem 4 | Theorem 6 | Theorem 6
Non-private | UB | $\frac{\sqrt{H}\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|\left\|{w^{*}}\right\|}{\sqrt{n}}$ | $\frac{G\left\|{w^{*}}\right\|\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}$
|  [25] |  [21]
LB | $\frac{\min\left\\{{\|{\mathcal{Y}}\|,\left\|{w^{*}}\right\|\|{\mathcal{X}}\|}\right\\}}{\sqrt{n}}+\min\left\\{{\|{\mathcal{Y}}\|^{2},\frac{H\left\|{w^{*}}\right\|^{2}\|{\mathcal{X}}\|^{2}+d\|{\mathcal{Y}}\|^{2}}{n},\frac{\sqrt{H}\left\|{w^{*}}\right\|\|{\mathcal{Y}}\|\|{\mathcal{X}}\|}{\sqrt{n}}}\right\\}$ |  Tight
|  [25, 23] |  [21]

Table 1:  Summary of Rates. Parameters: $d$: dimension, $n$: sample size, $H$:
smoothness parameter, $w^{*}$: minimum norm population risk minimizer,
$\|{\mathcal{X}}\|$: bound on feature vectors, $\|{\mathcal{Y}}\|$: bound on
loss at zero, $G$: Lipschitzness parameter, $\mathsf{rank}$: expected rank of
the design matrix, $\epsilon$: privacy parameter ($\delta$ factors omitted).
The actual private excess risk bounds are the sum of the expressions shown in
the DP rows and their non-private counterparts. Details on non-private lower
bounds in Appendix E.

##### Smooth nonegative GLMs.

Our primary contribution is a new and nearly optimal rate for the problem of
differentially private learning of smooth GLMs. In this setting, we focus on
characterizing the excess risk in terms of $n,d,\epsilon$ and
$\left\|{w^{*}}\right\|$. Specifically, we show that it is possible to achieve
a rate of
$\widetilde{O}\left({\frac{\left\|{w^{*}}\right\|}{\sqrt{n}}+\min\left\\{{\frac{\left\|{w^{*}}\right\|^{2}}{(n\epsilon)^{2/3}},\frac{\sqrt{d}\left\|{w^{*}}\right\|^{2}}{n\epsilon}}\right\\}}\right)$
on the excess population risk. Our new rates exhibit an interesting low/high
dimensional transition at $d\approx(\left\|{w^{*}}\right\|n\epsilon)^{2/3}$.
First, in the low dimensional regime, we develop a novel analysis of noisy
gradient decent (GD) inspired by techniques from [25]. In particular, we show
that Noisy GD gives an improved rate for non-negative smooth functions (not
necessarily GLMs). This is based on an average stability analysis of Noisy GD.
As we elaborate in Section 3.1, a straightforward application of uniform
stability leads to sub-optimal bounds and hence a new analysis is required. We
note in passing that this upper bound works for (unconstrained) DP-SCO with
smooth (non-Lipschitz) losses, which is of independent interest. For the high
dimensional regime, we perform random projections of the data (specifically,
the Johnson-Lindenstrauss transform) for dimensionality reduction, roughly
reducing the problem to its low dimensional counterpart. We also develop a
lower bound for the excess risk under DP of
$\widetilde{\Omega}\left({{\min\left\\{{\frac{\left\|{w^{*}}\right\|^{4/3}}{(n\epsilon)^{2/3}},\frac{\sqrt{d}\left\|{w^{*}}\right\|}{n\epsilon}}\right\\}}}\right)$.
We note that non-privately a lower bound of
$\widetilde{\Omega}\left({\frac{1}{\sqrt{n}}+\min\left\\{{\frac{d+\left\|{w^{*}}\right\|^{2}}{n},\frac{\left\|{w^{*}}\right\|}{\sqrt{n}}}\right\\}}\right)$
is known on the excess population risk [25, 23]. We note that these private
and non-private lower bounds imply that our bound is optimal up to factors of
$\left\|{w^{*}}\right\|$ (see Table 1).

##### Lipschitz GLMs.

For the Lipschitz case, we close a subtle but important gap in existing rates.
In this setting, it has been shown that one can characterize the excess risk
in terms of the expected rank of the design matrix, rank, instead of $d$ [26].
In this setting, the best known rate was
$\widetilde{O}\left({\frac{\left\|{w^{*}}\right\|}{\sqrt{n}}+\frac{\sqrt{\text{rank}}\left\|{w^{*}}\right\|}{n\epsilon}}\right)$.
We show an improved rate of
$\widetilde{O}\left({\frac{\left\|{w^{*}}\right\|}{\sqrt{n}}+\min\left\\{{\frac{\left\|{w^{*}}\right\|}{\sqrt{n\epsilon}},\frac{\sqrt{\text{rank}}\left\|{w^{*}}\right\|}{n\epsilon}}\right\\}}\right)$.
This improves in the high privacy regime where
$\epsilon\leq\frac{\text{rank}}{n}$. In fact, the upper bound
$O\left({\frac{\left\|{w^{*}}\right\|}{\sqrt{n\epsilon}}}\right)$ for this
rate can be obtained with only minor adjustments to the regularization method
of [17]. Our second contribution in this setting is extending the lower bound
of [26] to hold for all values of $\left\|{w^{*}}\right\|>0$ and
$\text{rank}\in[n]$. This is in contrast to the original lower bound which
only holds for problem instances where
$\left\|{w^{*}}\right\|^{2}=\text{rank}$ and $\text{rank}\in[n\epsilon]$.

##### Model selection.

As part of our methods, we develop a differentially private model selection
approach which eliminates the need for a-priori knowledge of
$\left\|{w^{*}}\right\|$. Although such methods are well established in the
non-private case, (see e.g. [24]), in the private case no such methods have
been established. Our method, as in the non-private case, performs a grid
search over estimates of $\left\|{w^{*}}\right\|$ and picks the best model
based on the loss. However, in the private setting we must account for the
fact the the loss evaluation must be privatized. This is non-trivial in the
non-Lipschitz smooth case as the loss at a point $w$ may grow quadratically
with $\left\|{w}\right\|$.

##### Lower bounds for Non-Euclidean DP-SCO.

Our lower bound construction generalizes to Non-Euclidean $\ell_{p}/\ell_{q}$
variants of DP-SCO with Lipschitz convex losses [7]. Herein, we assume that
the loss function is $G_{q}$-Lipschitz with respect to $\ell_{q}$ norm, and
radius of the constraint set is bounded in $\ell_{p}$ norm by $B_{p}$. For
this setting, we give a lower bound of
$\Omega\left({G_{q}B_{p}\min\left({\frac{1}{\left({n\epsilon}\right)^{1/p}},\frac{d^{(p-1)/p}}{n\epsilon}}\right)}\right)$
on excess empirical/population risk of any (potentially unconstrained)
$(\epsilon,\delta)$-DP algorithm; see Corollary 4 in Appendix B.4 for a formal
statement and proof. For $p=\infty$ and $p\geq 2,d\leq n\epsilon$, this
matches the best known upper bounds in [7].

##### Non-private settings.

As by-products, we give the following new results for the non-private setting.
For details on the parameters used below we refer to Table 1.

  * 1.

We show that gradient descent, when run on convex non-negative $\widetilde{H}$
smooth functions (not necessarily GLMs), it achieves the optimal rate of
$O\big{(}\frac{\sqrt{\widetilde{H}}\left\|{w^{*}}\right\|\|{\mathcal{Y}}\|}{\sqrt{n}}\big{)}$
(see Corollary 1). This is done via an average-stability analysis of gradient
descent. This result is interesting as it also shows GD only needs $n$
iterations, which is known not to work for non-smooth SCO [5, 1, 2].

  * 2.

In Section D, we give a procedure to boost the confidence of algorithms for
risk minimization with convex non-negative $\widetilde{H}$ smooth functions
(not necessarily GLMs). The standard boosting analysis based on Hoeffding’s
inequality does not give a bound with a linear dependence on the parameters
$(\left\|{w^{*}}\right\|,\|{\mathcal{X}}\|,\|{\mathcal{Y}}\|)$, and hence a
tighter analysis is required.

###  1.3 Techniques

##### Upper bounds.

We give two algorithms for both the smooth and Lispschitz cases. The first
method is simple and has two main steps. First, optimize the regularized
empirical risk over the constraint set $\left\\{{w:\left\|{w}\right\|\leq
B}\right\\}$ for some $B\geq\left\|{w^{*}}\right\|$. Then output a
perturbation of the regularized minimizer with Gaussian noise (which is not
requried to be in the constraint set). This method is akin to that of [17]
with the modification that the regularized minimizer is constrained to a ball.
We elaborate on this key difference shortly.

The second method is based on dimensionality reduction. We use smaller
dimensional data-oblivious embeddings of the feature vectors. A linear JL
transform suffices to give embeddings with the required properties. We then
run a constrained DP-SCO method (Noisy GD) in the embedded space, and use the
transpose of the JL transform to get a $d$ dimensional model. In this method,
the embedding dimension required is roughly the threshold on dimension at
which the rates switch from dimension dependent to independent bounds. We also
remark that [20] applied a similar technique to provide dimension independent
classification error guarantees for privately learning support vector machines
under hard margin conditions.

We note that a crucial part in all of these methods is the use of constrained
optimization as a subroutine, where the constraint set is a ball of radius
$\left\|{w^{*}}\right\|$. This is in stark contrast to the Lipschitz case
where existing methods such as those presented by [17, 26] rely on the fact
that projection is not required. In the smooth case however, constrained
optimization helps ensure that the norm of the gradient is roughly bounded by
the diameter of the constraint set. We note that in the high dimensional
regime, the property that the _final_ output of the algorithm can have large
norm is still crucial to the success of our algorithms.

##### Lower bounds.

For our lower bounds in the smooth case we rely on the connection between
stability and privacy. Specifically, we will utilize a lemma from [10] which
bounds the accuracy of one-dimensional differentially private algorithms. We
then combine this with packing arguments to obtain stronger lower bounds for
high dimensional problems. For the Lipschitz case, we adapt the method of
[26].

##  2 Preliminaries

In the following we detail several concepts needed for the presentation of
this paper.

##### Risk minimization.

Let ${\mathcal{X}}\subseteq{\mathbb{R}}^{d}$ be the domain of features, and
${\mathcal{Y}}\subseteq{\mathbb{R}}$ be the domain of responses. A linear
predictor is any $w\in{\mathbb{R}}^{d}$. Let
$\ell:\mathbb{R}^{d}\times({\mathcal{X}}\times{\mathcal{Y}})\to\mathbb{R}$ be
a loss function. Given some unknown distribution ${\mathcal{D}}$ over
$({\mathcal{X}}\times{\mathcal{Y}})$, we define the population loss
$L(w;{\mathcal{D}})=\underset{(x,y)\sim{\mathcal{D}}}{\mathbb{E}}\left[\ell(w;(x,y))\right]$.
Given some dataset $S\in({\mathcal{X}}\times{\mathcal{Y}})^{n}$ drawn i.i.d.
from ${\mathcal{D}}$, the objective is to obtain
$\widehat{w}\in\mathbb{R}^{d}$ which minimizes the excess population risk,
$L(\widehat{w};{\mathcal{D}})-\min\limits_{w\in\mathbb{R}^{d}}\left\\{{L(w;{\mathcal{D}})}\right\\}$.
Given a population risk minimization problem, we will denote $w^{\ast}$ to be
a _minimum norm_ solution to this problem. We define the empirical risk as
$\widehat{L}(w;S)=\frac{1}{n}\sum\limits_{(x,y)\in S}\ell(w;(x,y))$. We define
the following quantities for notational convenience:
$\varepsilon_{\mathsf{risk}}(w)=L(w;{\mathcal{D}})-L(w^{*};{\mathcal{D}})$,
$\varepsilon_{\mathsf{erm}}(w)=\widehat{L}(w;S)-\widehat{L}(w^{*};S)$, and
$\varepsilon_{\mathsf{gen}}(w)=L(w;{\mathcal{D}})-\widehat{L}(w;S)$. We define
${\mathcal{B}}\left({B}\right)$ to be the Euclidean ball of radius $B$ on
${\mathbb{R}}^{d}$.

##### Generalized linear models.

We will more specifically be interested in the problem of learning generalized
linear models, where there exists some function
$\phi:\mathbb{R}\times{\mathcal{Y}}\rightarrow\mathbb{R}$ such that the loss
function can be written as
$\ell(w;(x,y))=\phi(\left\langle{w},{x}\right\rangle,y)$. We define parameter
bounds
$\left\|{{\mathcal{X}}}\right\|=\max_{x\in{\mathcal{X}}}{\left\|{x}\right\|}$
and
$\left\|{{\mathcal{Y}}}\right\|^{2}=\max_{y\in{\mathcal{Y}}}{|\phi(0,y)|}$.
Note that for many common loss functions, the latter condition is the moral
equivalent of assuming labels bounded by $\|{\mathcal{Y}}\|$. For ease of
notation, we write $\phi(\left\langle{w},{x}\right\rangle,y)$ as
$\phi_{y}(\left\langle{w},{x}\right\rangle)$ and denote function
$\phi_{y}:z\mapsto\phi(z,y)$. We say that the loss function is $G$-Lipschitz
GLM if all $y\in{\mathcal{Y}}$, $\phi_{y}:{\mathbb{R}}\rightarrow{\mathbb{R}}$
is $G$-Lipschitz. We similarly define $H$-smooth GLM.

##### Differential privacy [13].

We restrict our investigation to the class of algorithms which minimize the
excess population risk under the constraint of differential privacy. A
randomized algorithm ${\mathcal{A}}$ is said to be $(\epsilon,\delta)$
differentially private (i.e., $(\epsilon,\delta)$-DP) if for any pair of
datasets $S$ and $S^{\prime}$ differing in one point and any event
$\mathcal{E}$ in the range of ${\mathcal{A}}$ it holds that

$\mathbb{P}[{\mathcal{A}}(S)\in\mathcal{E}]\leq
e^{\epsilon}\mathbb{P}[{\mathcal{A}}(S^{\prime})\in\mathcal{E}]+\delta.$

For our lower bounds, we will make use of the following Lemma from [10].

######  Lemma 1.

Let ${\mathcal{Z}}$ be a data domain and let $S$ and $S^{\prime}$ be two
datasets each in ${\mathcal{Z}}^{n}$ that differ in at most $\Delta$ entries,
and let ${\mathcal{A}}:{\mathcal{Z}}^{n}\to\mathbb{R}$ be any
$(\epsilon,\delta)$-DP algorithm. For all $\tau\in\mathbb{R}$, if
$\Delta\leq\frac{\operatorname{log}\left(1/2\gamma\right)}{\epsilon}$ and
$\delta\leq\frac{1}{16}(1-e^{-\epsilon})$, then
$\underset{}{\mathbb{E}}\left[|{\mathcal{A}}(S)-\tau|+|{\mathcal{A}}(S^{\prime})-\tau^{\prime}|\right]\geq\frac{1}{4}|\tau-\tau^{\prime}|.$

Finally, we introduce the Johnson-Lindenstrauss (JL) transform to perform
random projections.

######  Definition 1 ($(\alpha,\beta)$-JL property).

A distribution over matrices $\mathbb{R}^{k\times d}$ satisfies
$(\alpha,\beta)$-JL property if for any $u,v\in{\mathbb{R}}^{d}$,
$\mathbb{P}\left[\left|{\left\langle{\Phi u},{\Phi
v}\right\rangle-\left\langle{u},{v}\right\rangle}\right|>\alpha\left\|{u}\right\|\left\|{v}\right\|\right]\leq\beta.$

It is well known that several such “data-oblivious” (i.e. independent of
$u$,$v$) distributions exist with
$k=O\left({\frac{\operatorname{log}\left(1/\beta\right)}{\alpha^{2}}}\right)$
[19]. We note that the JL property is typically described as approximation of
norms (or distances), but it is easy to deduce the above dot product
preservation property from it; for completeness we give this as Lemma 12.
Finally, we use $\Phi{\mathcal{D}}$ to denote the push-forward measure of the
distribution ${\mathcal{D}}$ under the map $\Phi:(x,y)\mapsto(\Phi x,y)$.
Similarly, given a data set $S=\left\\{{(x_{i},y_{i})}\right\\}_{i}$, we
define $\Phi S:=\left\\{{\left({\Phi x_{i},y_{i}}\right)_{i}}\right\\}$

##  3 Smooth Non-negative GLMs

For smooth non-negative GLMs, we present new upper and lower bounds on the
excess risk. For our upper bounds, we here assume that the algorithm is given
access to some upper bound on $\left\|{w^{*}}\right\|$, that we denote by $B$.
We later show in Section 5 how to obtain such a rate without prior knowledge
of $\left\|{w^{*}}\right\|$. We also emphasize that the privacy of these
algorithms holds regardless of whether or not $B\geq\left\|{w^{*}}\right\|$.

###  3.1 Upper Bounds

Before presenting our algorithms, we highlight some key ideas underlying all
our methods. A crucial property of non-negative smooth loss functions which
allows one to bound sensitivity, and thus ensure privacy, is the self-bounding
property (e.g. Sec. 12.1.3 in [24]), which states that for an
$\widetilde{H}$-smooth non-negative function $f$ and
$u\in\operatorname{dom(f)}$, $\left\|{\nabla
f(u)}\right\|\leq\sqrt{4\widetilde{H}f(u)}$.

This property implies that the gradient grows at most linearly with
$\left\|{w}\right\|$. More precisely, we have the following.

######  Lemma 2.

Let $\ell$ be an $H$-smooth non-negative GLM. Then for any
$w\in{\mathcal{B}}\left({B}\right)$ and
$(x,y)\in({\mathcal{X}}\times{\mathcal{Y}})$ we have
$\left\|{\nabla\ell(w,(x,y))}\right\|\leq
2\left\|{{\mathcal{Y}}}\right\|\sqrt{H}\|{\mathcal{X}}\|+2HB\|{\mathcal{X}}\|^{2}$.

In order to leverage this property, all our algorithms in this setting utilize
constrained optimization as a subroutine, where the constraint set is
${\mathcal{B}}\left({B}\right)$ and the Lipschitz constant is
$G=2\left\|{{\mathcal{Y}}}\right\|\sqrt{H}\|{\mathcal{X}}\|+2HB\|{\mathcal{X}}\|^{2}$.
This, in conjunction with the self-bounding property ensures reasonable bounds
on sensitivity. In turn, this allows us to ensure privacy without excessive
levels of noise.

Finally, we note that our upper bounds for smooth GLMs distinguish low and
high dimensional regimes, transitioning at
$d=\min\Big{(}\left({\frac{B\sqrt{H}\|{\mathcal{X}}\|}{\|{\mathcal{Y}}\|}}\right)^{\frac{2}{3}}\\!\\!,\,1\Big{)}(n\epsilon)^{\frac{2}{3}}$.

####  3.1.1  Low dimensional regime

We start with the low dimensional setting where we use techniques developed
for constrained DP-SCO for Lipschitz losses (not necessarily GLMs). Existing
private algorithms for DP-SCO (e.g., [6, 15]) lead to excess risk bounds that
scale with $\frac{HB^{2}}{\sqrt{n}}$. On the other hand, the optimal non-
private rate [25] scales with $\frac{\sqrt{H}B}{\sqrt{n}}$, which may indicate
that the private rate implied by the known methods is sub-optimal. We show
that this gap can be closed by a novel analysis of private GD.

A standard proof of excess risk of (noisy) gradient descent for smooth convex
functions is based on uniform stability [16, 6]. However, this still leads to
sub-optimal rates. Hence we turn to an average stability based analysis of GD,
yielding the following result.

######  Theorem 1.

Let $\ell$ be a non-negative, convex, $\widetilde{H}$-smooth loss function,
bounded at zero by $\left\|{{\mathcal{Y}}}\right\|^{2}$. Let $B,n>0$,
$n_{0}=\frac{\widetilde{H}B^{2}}{\|{\mathcal{Y}}\|^{2}}$,
$G=2\left\|{{\mathcal{Y}}}\right\|\sqrt{\widetilde{H}}+2\widetilde{H}B$. Then,
for any $\epsilon,\delta>0$, Algorithm 1 invoked with
${\mathcal{W}}={\mathcal{B}}\left({B}\right)$, $T=n$,
$\sigma^{2}=\frac{8G^{2}T\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}$,
$\eta=\min\Big{(}\frac{B}{\sqrt{T}\max\big{(}\sqrt{\widetilde{H}}\|{\mathcal{Y}}\|,\sigma\sqrt{d}\big{)}},\frac{1}{4\widetilde{H}}\Big{)}$
is $(\epsilon,\delta)$-differentially private. Further, given a dataset $S$ of
$n\geq n_{0}$ i.i.d samples from an unknown distribution ${\mathcal{D}}$, the
excess risk of output of Algorithm 1 is bounded as,

$\displaystyle\mathbb{E}[\varepsilon_{\mathsf{risk}}(\widehat{w})]\leq
O\Bigg{(}\frac{\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{GB\sqrt{d\operatorname{log}\left(1/\delta\right)}}{n\epsilon}\Bigg{)}.$

We note that since $H$-smooth GLMs satisfy the Theorem condition with
parameter $\widetilde{H}\leq H\|{\mathcal{X}}\|^{2}$, we obtain results for
GLMs as a direct corollary.

##### Non-private risk bound:

As a corollary (see Corollary 1 in Appendix A.3.1), with no privacy
constraint, the above result (setting $\epsilon\rightarrow\infty$ and
$\delta=1$) shows that gradient descent achieves the optimal excess risk
bound, previously shown to be achievable by regularized ERM and one-pass SGD
[25]. The lower bound, $n_{0}$, simply means that the trivial solution “zero”
has larger excess risk.

##### Proof sketch of Theorem 1.

The privacy proof simply follows from [9] since the loss function is
$G$-Lipschitz in the constraint set. For utility, we first introduce two
concepts used in the proof. Let $S$ be a dataset of $n$ i.i.d samples
$\left\\{{(x_{i},y_{i})}\right\\}_{i=1}^{n}$, $S^{(i)}$ be the dataset where
the $i$-th data point is replaced by an i.i.d. point
$(x^{\prime},y^{\prime})$. Let ${\mathcal{A}}$ be an algorithm which takes a
dataset as input and outputs ${\mathcal{A}}(S)$. The average argument
stability of ${\mathcal{A}}$, denoted as $\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})$ is defined as

$\displaystyle\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}=\mathbb{E}_{S,i,(x^{\prime},y^{\prime})}\|{\mathcal{A}}(S)-{\mathcal{A}}(S^{(i)})\|^{2}.$

The average regret of gradient descent (Algorithm 1) with iterates
$\left\\{{w_{t}}\right\\}_{t=1}^{T}$ is

$\displaystyle\textstyle\varepsilon_{\mathsf{reg}}({\mathcal{A}};w^{*})=\frac{1}{T}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)].$

The key arguments are as follows: we first bound the generalization error, or
on-average stability, in terms of average argument stability and excess
empirical risk (Lemma 4). We then bound average argument stability in terms of
average regret (Lemma 5). Finally, in Lemma 6, we provide bounds on excess
empirical risk and average regret of noisy gradient descent. Substituting
these in the excess risk decomposition gives the claimed bound. The full proof
with the above lemmas is deferred to Appendix A.3.1.

Algorithm 1 Noisy GD

0: Dataset $S$, loss function $\ell$, constraint set ${\mathcal{W}}$, steps
$T$, learning rate $\eta$, noise scale $\sigma^{2}$

1: $w_{0}=0$

2: for $t=1$ to $T-1$ do

3: $\xi\sim{\mathcal{N}}(0,\sigma^{2}{\mathbb{I}})$

4:
$w_{t+1}=\Pi_{{\mathcal{W}}}\left({w_{t}-\eta\left({\widehat{L}(w_{t};S)+\xi}\right)}\right)$
where $\Pi_{{\mathcal{W}}}$ is the Euclidean projection on to ${\mathcal{W}}$

5: end for

5: $\widehat{w}=\frac{1}{T}\sum_{t=1}^{T}w_{j}$

####  3.1.2 High dimensional regime

Algorithm 2 JL Method

0: Dataset $S=\left\\{{(x_{1},y_{1}),...,(x_{n},y_{n})}\right\\}$, loss
function $\ell$, $k$, $B,\eta,T$, $\sigma^{2}$

1: Sample JL matrix $\Phi\in\mathbb{R}^{k\times d}$

2: $\widetilde{S}=\left\\{{\left({\Phi x_{1},y_{1}}\right),\left({\Phi
x_{2},y_{2}}\right),\ldots,\left({\Phi x_{n},y_{n}}\right)}\right\\}$

3:
$\widetilde{w}=\operatorname{NoisyGD}(\widetilde{S},\ell,{\mathcal{B}}\left({2B}\right),T,\eta,\sigma^{2})$

3: $\widehat{w}=\Phi^{\top}\widetilde{w}$

In the high dimensional setting, we present two techniques.

##### JL method.

In the JL method, Algorithm 2, we use a data-oblivious JL map $\Phi$ to embed
all feature vectors in dataset $S$ to $k<d$ dimensions. Let dataset
$\widetilde{S}=\left\\{{\left({\Phi x_{i},y_{i}}\right)}\right\\}_{i=1}^{n}$.
We then run projected Noisy GD method (Algorithm 1) on the loss with dataset
$\widetilde{S}$ and the diameter of the constraint set as $2B$. Finally, we
map the returned output $\widetilde{w}$ back to $d$ dimensions using
$\Phi^{\top}$ to get $\widehat{w}=\Phi^{\top}\widetilde{w}$. We note that no
projection is performed on $\widehat{w}$ and thus the output may have large
norm due to re-scaling induced by $\Phi^{\top}$.

######  Theorem 2.

Let
$k=O\left({\frac{B\sqrt{H}\left\|{{\mathcal{X}}}\right\|\operatorname{log}\left(2n/\delta\right)n\epsilon}{\left\|{{\mathcal{Y}}}\right\|\left\|{{\mathcal{X}}}\right\|+\sqrt{H}B\left\|{{\mathcal{X}}}\right\|^{2}}}\right)^{2/3}$,
${\mathcal{W}}={\mathcal{B}}\left({B}\right)$, $T=n$,
$\sigma^{2}=\frac{8G^{2}T\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}$,
$\eta=\min\Big{(}\frac{B}{\sqrt{T}\max\big{(}\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|,\sigma\sqrt{d}\big{)}},\frac{1}{4H\|{\mathcal{X}}\|^{2}}\Big{)}$
and
$n_{0}=\frac{HB^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{\left\|{{\mathcal{Y}}}\right\|^{2}}$.
Algorithm 2 satisfies $(\epsilon,\delta)$-differential privacy. Given a
dataset $S$ of $n\geq n_{0}$ i.i.d samples, of the output $\widehat{w}$ is
bounded by

$\displaystyle\mathbb{E}[\varepsilon_{\mathsf{risk}}(\widehat{w})]\leq\widetilde{O}\Bigg{(}\frac{\sqrt{H}B\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|}{\sqrt{n}}+\frac{\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|\sqrt{\left\|{{\mathcal{Y}}}\right\|}}\right)^{\frac{4}{3}}+\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{2}}{(n\epsilon)^{\frac{2}{3}}}\Bigg{)}.$

##### Proof sketch of Theorem 2.

From the JL property, with
$k=O(\operatorname{log}\left(n/\delta\right)/\alpha^{2})$, w.h.p. norms of all
feature vectors and $w^{*}$, as well as inner products between are preserved
upto an $\alpha$ tolerance (see Definition 1). The preservation of norms of
feature vectors implies the gradient norms are preserved, and thus privacy
guarantee of sub-routine, Algorithm 1, suffices to establish DP. For the
utility proof, from our analysis of Noisy GD (Theorem 1) and using the JL
property, the excess risk of $\widehat{w}$ under ${\mathcal{D}}$ w.r.t. the
risk of $\Phi w^{*}$ under $\Phi{\mathcal{D}}$ is bounded as,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})$ $\displaystyle-L(\Phi
w^{*};\Phi{\mathcal{D}})]\leq
O\Bigg{(}\frac{\sqrt{H}\|{\mathcal{X}}\|B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|+H\|{\mathcal{X}}\|^{2}B^{2}}\right)B\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}\Bigg{)}.$

From smoothness and JL property, the, “JL error” is:

$\displaystyle\mathbb{E}[L(\Phi
w^{*};\Phi{\mathcal{D}})]-L(w^{*};{\mathcal{D}})]\leq\widetilde{O}\left(\frac{HB^{2}\|{\mathcal{X}}\|^{2}}{k}\right).$

The above is optimized for the value of $k$ prescribed in Theorem 2,
substituting which gives the claimed bound.

Algorithm 3 Regularized Output Perturbation

0: Dataset $S=\left\\{{(x_{1},y_{1}),...,(x_{n},y_{n})}\right\\}$, loss
function $\ell$, $\lambda,B,\sigma^{2}$

1:
$\widetilde{w}=\mathop{\arg\min}\limits_{w\in{\mathcal{B}}\left({B}\right)}\left\\{{L(w;S)+\frac{\lambda}{2}\left\|{w}\right\|^{2}}\right\\}$

2: $\xi\sim{\mathcal{N}}(0,\sigma^{2}\mathrm{I}_{d})$

2: $\widehat{w}=\widetilde{w}+\xi$

##### Constrained regularized ERM + output perturbation.

Our second technique is _constrained_ regularized ERM with output perturbation
(Algorithm 3). A similar technique for the Lipschitz case was seen in [17],
however we note that the addition of the constraint set
${\mathcal{B}}\left({B}\right)$ is crucial in bounding the sensitivity in the
smooth case.

######  Theorem 3.

Let $n_{0}=\frac{HB^{2}\|{\mathcal{X}}\|^{2}}{\|{\mathcal{Y}}\|^{2}}$. Then
Algorithm 3 run with
$\sigma^{2}=O\left({\frac{\left({\left\|{{\mathcal{Y}}}\right\|^{2}+H^{2}B^{2}\left\|{{\mathcal{X}}}\right\|^{4}}\right)\operatorname{log}\left(1/\delta\right)}{\lambda^{2}n^{2}\epsilon^{2}}}\right)$
and
$\lambda=\left({\frac{\left({\left\|{{\mathcal{Y}}}\right\|+HB\left\|{{\mathcal{X}}}\right\|^{2}}\right)\sqrt{H}\left\|{{\mathcal{X}}}\right\|}{Bn\epsilon}}\right)^{2/3}\left({\operatorname{log}\left(1/\delta\right)}\right)^{1/3}$
satisfies $(\epsilon,\delta)$-differential privacy. Given a dataset $S$ of
$n\geq n_{0}$ i.i.d samples, the excess risk of its output $\widehat{w}$ is
bounded as

$\displaystyle\mathbb{E}[\varepsilon_{\mathsf{risk}}(\widehat{w})]$
$\displaystyle\leq\widetilde{O}\Bigg{(}\frac{\sqrt{H}B\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|+\|{\mathcal{Y}}\|^{2}}{\sqrt{n}}+\frac{\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{4/3}\left\|{{\mathcal{Y}}}\right\|^{2/3}+\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{2}}{(n\epsilon)^{2/3}}\Bigg{)}.$

We note that we can use the same technique in the low dimensional setting too,
yielding a rate of
$\frac{\sqrt{H}B\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|+\|{\mathcal{Y}}\|^{2}}{\sqrt{n}}+\frac{GB\sqrt{d}}{n\epsilon}$.
However, in contrast to Theorem 1 and 2, these results have an additional
$\frac{\|{\mathcal{Y}}\|^{2}}{\sqrt{n}}$ term (in both regimes). Thus, in the
regime when $\|{\mathcal{Y}}\|\leq\sqrt{H}B\|{\mathcal{X}}\|$, the two upper
bounds are of the same order.

##### Proof sketch of LABEL:{thm:smooth-output-perturbation}.

The privacy proof follows the Gaussian mechanism guarantee together with the
fact that the $\ell_{2}$-sensitivity of constrained regularized ERM is
$O\left({\frac{G}{\lambda n}}\right)$ [4]. For utility, we use the Rademacher
complexity based result of [25] to bound the generalization error of
$\widetilde{w}$. The other term, error from noise,
$\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]\leq
O(H\sigma^{2}\|{\mathcal{X}}\|^{2})$ from smoothness of GLM. Combining these
two and optimizing for $\lambda$ gives the claimed result.

###  3.2 Lower Bounds

The proof technique for our lower bound relies on the connection between
differential privacy and sensitivity shown in [10]. The underlying mechanisms
behind the proof is also similar in nature to the method seen in [27]. We note
that although we present the following theorem for empirical risk, a reduction
found in [6] implies the following result holds for population risk as well
(up to log factors).

######  Theorem 4.

Let $\epsilon\in[1/n,1]$, $\delta\leq\frac{1}{16}(1-e^{-\epsilon})$. For any
$(\epsilon,\delta)$-DP algorithm, ${\mathcal{A}}$, there exists a dataset $S$
with empirical minimizer of norm $B$ such that the excess empirical risk of
${\mathcal{A}}$ is lower bounded by
$\Omega\left\\{{\min\left\\{{\|{\mathcal{Y}}\|^{2},\frac{(B\|{\mathcal{X}}\|)^{4/3}(H\|{\mathcal{Y}}\|)^{2/3}}{(n\epsilon)^{2/3}},\frac{\sqrt{d}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|\sqrt{H}}{n\epsilon}}\right\\}}\right\\}$.

The problem instance used in the proof is the squared loss function, and thus
this result holds additionally for the more specific case of linear
regression. We also note this lower bound implies our upper bound is optimal
whenever $B\|{\mathcal{X}}\|\leq\|{\mathcal{Y}}\|$, which is a commonly
studied regime in linear regression [25, 18]. We here provide a proof sketch
and defer the full proof to Appendix A.7.

##### Proof sketch of Theorem 4

Define $F(w;S)=\frac{1}{n}\sum_{(x,y)\in
S}(\left\langle{w},{x}\right\rangle-y)^{2}$. Let
$d^{\prime}<\min\left\\{{n,d}\right\\}$ and $b,p\in[0,1]$ be parameters to be
chosen later. For any $\boldsymbol{\sigma}\in\left\\{{\pm
1}\right\\}^{d^{\prime}}$, define the dataset $S_{\boldsymbol{\sigma}}$ which
consists of the union of $d^{\prime}$ subdatasets, $S_{1},...,S_{d^{\prime}}$
given as follows. Set $\frac{pn}{d^{\prime}}$ of the feature vectors in
$S_{j}$ as $\|{\mathcal{X}}\|e_{j}$ (the rescaled $j$’th standard basis
vector) and the rest as the zero vector. Set $\frac{pn}{2d}(1+b)$ of the
labels as $\boldsymbol{\sigma}_{j}\|{\mathcal{Y}}\|$ and $\frac{pn}{2d}(1-b)$
labels as $-\boldsymbol{\sigma}_{j}\|{\mathcal{Y}}\|$. Let
$w^{\boldsymbol{\sigma}}=\mathop{\arg\min}_{w\in\mathbb{R}^{d}}\left\\{{F(w;S_{\boldsymbol{\sigma}})}\right\\}$
be the ERM minimizer of $F(\cdot;S_{\boldsymbol{\sigma}})$. Following from
Lemma 2 of [23] we have that for any $\bar{w}\in\mathbb{R}^{d}$ that

$F(\bar{w};S_{\boldsymbol{\sigma}})-F(w^{\boldsymbol{\sigma}};S_{\boldsymbol{\sigma}})\geq\frac{p\|{\mathcal{X}}\|^{2}}{2d^{\prime}}\sum_{j=1}^{d^{\prime}}{(\bar{w_{j}}-w^{\boldsymbol{\sigma}}_{j})^{2}}.$
(1)

We will now show lower bounds on the per-coordinate error. Consider any
$\boldsymbol{\sigma}$ and $\boldsymbol{\sigma}^{\prime}$ which differ only at
index $j$ for some $j\in[d^{\prime}]$. Note that the datasets
$S_{\boldsymbol{\sigma}}$ and $S_{\boldsymbol{\sigma}^{\prime}}$ differ in
$\Delta=\frac{pn}{2d^{\prime}}[(1+b)-(1-b)]=\frac{pbn}{d^{\prime}}$ points.
Let
$\tau=w_{j}^{\boldsymbol{\sigma}}=\frac{\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}$
and
$\tau^{\prime}=w_{j}^{\boldsymbol{\sigma}^{\prime}}=-\frac{\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}$
(i.e. the $j$ components of the empirical minimizers for $S$ and
$S^{\prime}_{j}$ respectively). Note that
$|w_{j}^{\boldsymbol{\sigma}}-w_{j}^{\boldsymbol{\sigma}^{\prime}}|=\frac{2\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}$.
Setting
$d^{\prime}=\big{(}\frac{p\|{\mathcal{X}}\|Bn\epsilon}{\|{\mathcal{Y}}\|}\big{)}^{2/3}$
and
$b=\big{(}\frac{\|{\mathcal{X}}\|B}{\|{\mathcal{Y}}\|\sqrt{pn\epsilon}}\big{)}^{2/3}$
ensures $\Delta\leq\frac{1}{\epsilon}$, and thus Lemma 1 can be used to obtain

$\displaystyle\underset{}{\mathbb{E}}\left[|{\mathcal{A}}(S_{\boldsymbol{\sigma}})_{j}-w_{j}^{\boldsymbol{\sigma}}|^{2}+|{\mathcal{A}}(S_{\boldsymbol{\sigma}^{\prime}})_{j}-w_{j}^{\boldsymbol{\sigma}^{\prime}}|^{2}\right]\geq\frac{1}{32}\frac{\|{\mathcal{Y}}\|^{2}b^{2}}{\|{\mathcal{X}}\|^{2}}=\frac{B^{4/3}\|{\mathcal{Y}}\|^{2/3}}{32(\|{\mathcal{X}}\|pn\epsilon)^{2/3}}.$

One can now show via a packing argument that

$\displaystyle\sup_{\boldsymbol{\sigma}\in\left\\{{\pm
1}\right\\}^{d^{\prime}}}\left\\{{\underset{}{\mathbb{E}}\left[F({\mathcal{A}}(S_{\boldsymbol{\sigma}}))-F(w^{\boldsymbol{\sigma}})\right]}\right\\}$
$\displaystyle\geq\frac{(\|{\mathcal{X}}\|B)^{4/3}\|{\mathcal{Y}}\|^{2/3}p^{1/3}}{128(n\epsilon)^{2/3}},$

The result then follows from setting
$p=\min\left\\{{1,\frac{d^{3/2}\|{\mathcal{Y}}\|}{B\|{\mathcal{X}}\|n\epsilon}}\right\\}$.

##  4 Lipschitz GLMs

In the Lipschitz case, we close a subtle gap in existing rates. We recall that
in this setting a more precise characterization in terms of the expected rank
of the design matrix is possible (as opposed to using $d$). The best known
upper bound is
$\widetilde{O}\left({\frac{\left\|{w^{*}}\right\|\sqrt{\text{rank}}}{n\epsilon}}\right)$
assuming knowledge of $\left\|{w^{*}}\right\|$. This bound was shown to be
optimal when $\epsilon\geq\text{rank}/n$ and
$\left\|{w^{*}}\right\|=\sqrt{\text{rank}}$ [26].

We first show that in the high privacy regime where
$\epsilon\leq\text{rank}/n$, an improved rate is possible. Specifically, we
show that in this regime constrained regularized ERM with output perturbation
and achieves the optimal rate. In fact, we note that the method of [17] (i.e.
_unconstrained_ regularized ERM with output perturbation), can obtain this
rate when $\epsilon=O(1)$ if the regularization parameter is set differently.
We present the constrained version in order to leverage Rademacher complexity
arguments and provide a slightly cleaner bound that holds for all
$\epsilon>0$.

######  Theorem 5.

Algorithm 3 run with parameters
$\sigma^{2}=\frac{4G^{2}\left\|{{\mathcal{X}}}\right\|^{2}\operatorname{log}\left(1/\delta\right)}{\lambda^{2}n^{2}\epsilon^{2}}$
and
$\lambda=\frac{G\|{\mathcal{X}}\|\left({\operatorname{log}\left(1/\delta\right)}\right)^{1/4}}{B\sqrt{n\epsilon}}$
satisfies $(\epsilon,\delta)$-DP. Given a dataset of $n$ i.i.d. samples from
${\mathcal{D}}$, its output has excess risk
$\underset{}{\mathbb{E}}\left[\varepsilon_{\mathsf{risk}}(\widehat{w})\right]=\widetilde{O}\left({\frac{GB\|{\mathcal{X}}\|}{\sqrt{n}}+\frac{GB\|{\mathcal{X}}\|}{\sqrt{n\epsilon}}}\right)$.

We also state and prove a similar bound using the JL technique in Appendix B.

Next, we generalize the lower bound of [26] to show this new bound is optimal
for all settings of $B$, rank, and $\epsilon$. We now show that a modification
of the lower bound present in [26] shows our upper bound is tight. We note
that their lower bound only held for problem instances where
$\text{rank}=\left\|{w^{*}}\right\|^{2}$ and $\epsilon\leq\text{rank}/n$. By
contrast, the upper bound
$O(\frac{\sqrt{\text{rank}}\left\|{w^{*}}\right\|}{n\epsilon})$ holds for any
values of rank and $\left\|{w^{*}}\right\|$.

######  Theorem 6.

Let $G,\left\|{{\mathcal{Y}}}\right\|,\left\|{{\mathcal{X}}}\right\|,B>0$,
$\epsilon\leq 1.2$ and $\delta\leq\epsilon$. For any $(\epsilon,\delta)$-DP
algorithm ${\mathcal{A}}$, there exists a $G$-Lipschitz GLM loss bounded at
zero by $\left\|{{\mathcal{Y}}}\right\|$ and a distribution ${\mathcal{D}}$
with $\left\|{w^{*}}\right\|\leq B$ such that the output of ${\mathcal{A}}$ on
$S\sim{\mathcal{D}}^{n}$ satisfies
$\mathbb{E}[\varepsilon_{\mathsf{risk}}({\mathcal{A}}(S))]=\Omega\Big{(}GB\|{\mathcal{X}}\|\min\Big{(}1,\frac{1}{\sqrt{n\epsilon}},\frac{\sqrt{\text{rank}}}{n\epsilon}\Big{)}\Big{)}$.

All proofs for this section are deferred to Appendix B.

##  5 Adapting to $\left\|{w^{*}}\right\|$

Our method for privately adapting to $\left\|{w^{*}}\right\|$ is given in
Algorithm 4. We start by giving a high level overview and defining some
necessary preliminaries. The algorithm works in the following manner. First we
define a number of “guesses” $K$ for $\left\|{w^{*}}\right\|$,
$B_{1},...,B_{K}$ where $B_{j}=2^{j}:\forall j\in[K]$. Then given black box
access to a DP optimization algorithm, ${\mathcal{A}}$, Algorithm 4 generates
$K$ candidate vectors $w_{1},...,w_{K}$ using ${\mathcal{A}}$, training set
$S_{1}\in({\mathcal{X}}\times{\mathcal{Y}})^{n/2}$, and the guesses
$B_{1},...,B_{K}$. We assume ${\mathcal{A}}$ satisfies the following accuracy
assumption for some confidence parameter $\beta>0$.

######  Assumption 1.

There exists a function $\mathsf{ERR}:\mathbb{R}^{+}\mapsto\mathbb{R}^{+}$
such that for any $B\in\mathbb{R}^{+}$, whenever
$B\geq\left\|{w^{*}}\right\|$, w.p. at least $1-\frac{\beta}{4K}$ under the
randomness of $S_{1}\sim{\mathcal{D}}^{\frac{n}{2}}$ and ${\mathcal{A}}$ it
holds that
$\varepsilon_{\mathsf{risk}}({\mathcal{A}}(S_{1},B);{\mathcal{D}})\leq\mathsf{ERR}(B)$.

After generating the candidate vectors, the goal is to pick guess with the
smallest excess population risk in a differentially private manner using a
validation set $S_{2}$. The following assumption on ${\mathcal{A}}$ allows us
both to ensure the privacy of the model selection algorithm and verify that
$\widehat{L}(w_{j};S_{2})$ provides a tight estimate of
$L(w_{j};{\mathcal{D}})$.

######  Assumption 2.

There exist a function $\Delta:\mathbb{R}^{+}\mapsto\mathbb{R}^{+}$ such that
for any dataset $S_{2}\in({\mathcal{X}}\times{\mathcal{Y}})^{n/2}$ and $B>0$

$\underset{{\mathcal{A}}}{\mathbb{P}}[\exists(x,y)\in
S_{2}:|\ell({\mathcal{A}}(S_{1},B);(x,y))|\geq\Delta(B)]\leq\frac{\min\left\\{{\delta,\beta}\right\\}}{4K}$

Specifically, our strategy will be to use the Generalized Exponential
Mechanism, $\operatorname{GenExpMech}$, of [22] in conjunction with a
penalized score function. Roughly, this score function penalty ensures the
looser guarantees on the population loss estimate when $B$ is large do not
interfere with the loss estimates at smaller values of $B$. We provide the
relevant details for $\operatorname{GenExpMech}$ in Appendix C.1. We now state
our result.

Algorithm 4 Private Grid Search

0: Dataset ${\mathcal{S}}\in({\mathcal{X}}\times{\mathcal{Y}})^{n}$, grid
parameter $K\in\mathbb{R}$, optimization algorithm:
${\mathcal{A}}:({\mathcal{X}}\times{\mathcal{Y}})^{n}\times\mathbb{R}\mapsto\mathbb{R}^{d}$,
privacy parameters $(\epsilon,\delta)$

1: Partition $S$ into two disjoint sets, $S_{1}$ and $S_{2}$, of size
$\frac{n}{2}$

2: $w_{0}=0$

3: for $j\in[K]$ do

4: $B_{j}=2^{j}$

5: $w_{j}={\mathcal{A}}(S_{1},B_{j})$

6:
$\widetilde{L}_{j}=\widehat{L}(w_{j};S_{2})+\frac{\Delta(B_{j})\operatorname{log}\left(K/\beta\right)}{n}+\sqrt{\frac{4\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(K/\beta\right)}{n}}$

7: end for

8: Set $j^{*}$ as the output of $\operatorname{GenExpMech}$ run with privacy
parameter $\frac{\epsilon}{2}$, confidence parameter $\frac{\beta}{4}$, and
sensitivity/score pairs
$(0,\|{\mathcal{Y}}\|^{2}),(\Delta(B_{1}),\widetilde{L}_{1})...,(\Delta(B_{K}),\widetilde{L}_{K})$,

9: Output $w_{j^{*}}$

######  Theorem 7.

Let $\ell:\mathbb{R}^{d}\times({\mathcal{X}}\times{\mathcal{Y}})$ be a smooth
non-negative loss function such that $\ell(0,(x,y))\leq\|{\mathcal{Y}}\|^{2}$
for any $x,y\in({\mathcal{X}}\times{\mathcal{Y}})$. Let
$\epsilon,\delta,\beta\in[0,1]$. Let $K>0$ satisfy
$\mathsf{ERR}(2^{K})\geq\|{\mathcal{Y}}\|^{2}$. Let ${\mathcal{A}}$ be an
$(\frac{\epsilon}{2K},\frac{\delta}{2K})$-DP algorithm satisfying Assumption
2. Then Algorithm 4 is $(\epsilon,\delta)$-DP. Further, if ${\mathcal{A}}$
satisfies Assumption 1 and $S_{1}\sim{\mathcal{D}}^{n/2}$ then Algorithm 4
outputs $\bar{w}$ s.t. with probability at least $1-\beta$,

$\displaystyle\varepsilon_{\mathsf{risk}}($
$\displaystyle\bar{w};{\mathcal{D}})\leq\min\Big{\\{}\|{\mathcal{Y}}\|^{2},\mathsf{ERR}(2\max\left\\{{\left\|{w^{*}}\right\|,1}\right\\})+\sqrt{\frac{4\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(4K/\beta\right)}{n}}+\frac{5\Delta(2\max\left\\{{\left\|{w^{*}}\right\|,1}\right\\})}{n\epsilon}\Big{\\}}.$

We note that we develop a generic confidence boosting approach to obtain high
probability guarantees from our previously described algorithms in Section 8,
and thus obtaining algorithms which satisfy 1 is straightforward. We provide
more details on how our algorithms satisfy Assumption 2 in Appendix C.4. The
following Theorem details the guarantees implied by this method for output
perturbation with boosting (see Theorems 13,15). Full details are in Appendix
C.3.

######  Theorem 8.

Let $K,\epsilon,\delta,\beta>0$ and ${\mathcal{A}}$ be the algorithm formed by
running 3 with boosting and privacy parameters
$\epsilon^{\prime}=\frac{\epsilon}{K}$, $\delta^{\prime}=\frac{\delta}{K}$.
Then there exists a setting of $K$ such that
$K=\Theta\left({\operatorname{log}\left(\max\left\\{{\frac{\|{\mathcal{Y}}\|\sqrt{n}}{\|{\mathcal{X}}\|\sqrt{H}},\frac{\|{\mathcal{Y}}\|^{2}(n\epsilon)^{2/3}}{\sqrt{H}\|{\mathcal{X}}\|^{2}}}\right\\}\right)}\right)$
and Algorithm 4 run with ${\mathcal{A}}$ and $K$ is $(\epsilon,\delta)$-DP and
when given $S\sim{\mathcal{D}}^{n}$, satisfies the following w.p. at least
$1-\beta$ (letting $B^{*}=2\max\left\\{{\left\|{w^{*}}\right\|,1}\right\\}$)

$\displaystyle\varepsilon_{\mathsf{risk}}(\widehat{w})$
$\displaystyle=\widetilde{O}\Bigg{(}\min\Big{\\{}\|{\mathcal{Y}}\|^{2},\frac{\left({\sqrt{H}B^{*}\left\|{{\mathcal{X}}}\right\|}\right)^{4/3}\left\|{{\mathcal{Y}}}\right\|^{2/3}+\left({\sqrt{H}B^{*}\left\|{{\mathcal{X}}}\right\|}\right)^{2}}{(n\epsilon)^{2/3}}$
$\displaystyle+\frac{\sqrt{H}B^{*}\left\|{{\mathcal{X}}}\right\|\max\left\\{{\left\|{{\mathcal{Y}}}\right\|,1}\right\\}+\left\|{{\mathcal{Y}}}\right\|^{2}}{\sqrt{n}}+\frac{\|{\mathcal{Y}}\|^{2}+H(B^{*}\|{\mathcal{X}}\|)^{2}}{n\epsilon}\Big{\\}}\Bigg{)}.$

##### Confidence Boosting:

We give an algorithm to boost the confidence of unconstrained, smooth DP-SCO
(with possibly non-Lipschitz losses). We split the dataset $S$ into $m+1$
chunks and run an $(\epsilon,\delta)$-DP algorithm over the $m$ chunks to get
$m$ models, and then use Report Noisy Max mechanism to select a model with
approximately the least empirical risk. We show that this achieves the optimal
rate of
$\widetilde{O}\left({\frac{\sqrt{H}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|}{\sqrt{n}}}\right)$
whereas the previous high probability result of [25] had an additional
$\widetilde{O}\left({\frac{\|{\mathcal{Y}}\|^{2}}{\sqrt{n}}}\right)$ term,
which was also limited to only GLMs. The key idea is that non-negativity,
convexity, smoothness and loss bounded at zero, all together enable strong
bounds on the variance of the loss, and consequently give stronger
concentration bounds. The details are deferred to Appendix D.

## Acknowledgements

RA and EU are supported, in part, by NSF BIGDATA award IIS-1838139 and NSF
CAREER award IIS-1943251. RB’s and MM’s work on this research is supported by
NSF Award AF-1908281 and Google Faculty Research Award. CG’s research is
partially supported by INRIA Associate Teams project, FONDECYT 1210362 grant,
and National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
Part of this work was done while CG was at the University of Twente.

## References

  * ACKL [21] Idan Amir, Yair Carmon, Tomer Koren, and Roi Livni.  Never go full batch (in stochastic convex optimization).  Advances in Neural Information Processing Systems, 34, 2021.
  * AKL [21] Idan Amir, Tomer Koren, and Roi Livni.  Sgd generalizes better than gd (and regularization doesn’t help).  In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 63–92. PMLR, 15–19 Aug 2021.
  * BBL [03] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi.  Introduction to statistical learning theory.  In Summer school on machine learning, pages 169–207. Springer, 2003\.
  * BE [02] Olivier Bousquet and André Elisseeff.  Stability and generalization.  J. Mach. Learn. Res., 2:499–526, March 2002.
  * BFGT [20] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar.  Stability of stochastic gradient descent on nonsmooth convex losses.  Advances in Neural Information Processing Systems, 33, 2020.
  * BFTGT [19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta.  Private stochastic convex optimization with optimal rates.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * BGN [21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi.  Non-euclidean differentially private stochastic convex optimization.  In Conference on Learning Theory, pages 474–499. PMLR, 2021.
  * BLM [13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press, 2013.
  * BST [14] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464–473. IEEE, 2014.
  * CH [12] Kamalika Chaudhuri and Daniel J. Hsu.  Convergence rates for differentially private statistical estimation.  In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012. icml.cc / Omnipress, 2012.
  * CWH [20] Xiangyi Chen, Steven Z. Wu, and Mingyi Hong.  Understanding gradient clipping in private sgd: A geometric perspective.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 13773–13782. Curran Associates, Inc., 2020.
  * CWZ [21] T. Tony Cai, Yichen Wang, and Linjun Zhang.  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  The Annals of Statistics, 49(5):2825 – 2850, 2021.
  * DKM+ [06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In EUROCRYPT, 2006.
  * DR+ [14] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * FKT [20] Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: optimal rates in linear time.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439–449, 2020.
  * HRS [15] Moritz Hardt, Benjamin Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  CoRR, abs/1509.01240, 2015.
  * JT [14] Prateek Jain and Abhradeep Guha Thakurta.  (near) dimension independent risk bounds for differentially private learning.  In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 476–484, Bejing, China, 22–24 Jun 2014. PMLR.
  * KL [15] Tomer Koren and Kfir Y Levy.  Fast rates for exp-concave empirical risk minimization.  In NIPS, pages 1477–1485, 2015.
  * Nel [11] Jelani Nelson.  Sketching and streaming high-dimensional vectors.  PhD thesis, Massachusetts Institute of Technology, 2011.
  * NêUZ [20] Huy Lê Nguyễn, Jonathan Ullman, and Lydia Zakynthinou.  Efficient Private Algorithms for Learning Large-Margin Halfspaces.  In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 704–724. PMLR, 08 Feb–11 Feb 2020.
  * NY [83] A.S. Nemirovsky and E.R. Yudin.  Problem Complexity and Method Efficiency in Optimization.  A Wiley-Interscience publication. Wiley, 1983.
  * RS [15] Sofya Raskhodnikova and Adam D. Smith.  Efficient lipschitz extensions for high-dimensional graph statistics and node private degree distributions.  CoRR, abs/1504.07912, 2015.
  * Sha [15] Ohad Shamir.  The sample complexity of learning linear predictors with the squared loss.  J. Mach. Learn. Res., 16:3475–3486, 2015.
  * SSBD [14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge university press, 2014.
  * SST [10] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari.  Smoothness, low noise and fast rates.  In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
  * SSTT [20] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta.  Characterizing private clipped gradient descent on convex generalized linear problems.  CoRR, abs/2006.06783, 2020.
  * SU [17] Thomas Steinke and Jonathan Ullman.  Tight lower bounds for differentially private selection.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 552–563. IEEE, 2017.
  * Ver [18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * VGNA [20] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel.  Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions.  Stat, 9(1):e318, 2020.
  * Wan [18] Yu-Xiang Wang.  Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain.  In Amir Globerson and Ricardo Silva, editors, Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pages 93–103. AUAI Press, 2018.

##  Appendix A Missing Proofs from Section 3.1 (Smooth GLMs)

###  A.1 Utility Lemmas

######  Fact 1.

[24] For a $\widetilde{H}$-smooth non-negative function $f$, and for any
$u\in\operatorname{dom}(f)$, we have $\left\|{\nabla
f(u)}\right\|\leq\sqrt{4\widetilde{H}f(u)}$.

###  A.2 Proof of Lemma 2

From the self-bounding property (Fact 1), the $\|{\mathcal{Y}}\|^{2}$ bound on
loss at zero, and smoothness, we have the following bound on the gradient:

$\displaystyle\left\|{\nabla\ell(w;(x,y)}\right\|$
$\displaystyle\leq\left\|{\nabla\ell(0;(x,y))}\right\|+\left\|{\nabla\ell(w;(x,y))-\nabla\ell(0;(x,y))}\right\|$
$\displaystyle\leq
2\sqrt{H}\left\|{x}\right\|\ell(0;(x,y))+H\left\|{x}\right\|^{2}\left\|{w}\right\|$
$\displaystyle\leq
2\left({\sqrt{H}\left\|{{\mathcal{Y}}}\right\|\left\|{x}\right\|+H\left\|{x}\right\|^{2}\left\|{w}\right\|}\right).$
(2)

######  Lemma 3.

For any $w\in{\mathcal{B}}\left({B}\right)$ and any
$(x,y)\in({\mathcal{X}}\times{\mathcal{Y}})$ it holds that $\ell(w;(x,y))\leq
3(\|{\mathcal{Y}}\|^{2}+HB^{2}\|{\mathcal{X}}\|^{2})$.

###### Proof.

Using the fact that the loss function is
$G=\|{\mathcal{Y}}\|\sqrt{H}\|{\mathcal{X}}\|+BH\|{\mathcal{X}}\|^{2}$-Lipschitz
in the constraint set (Lemma 2) we have

$\displaystyle\ell(w;(x,y))$
$\displaystyle\leq\ell(0;(x,y))+\left|{\ell(w;(x,y))-\ell(0;(x,y))}\right|$
$\displaystyle\leq\|{\mathcal{Y}}\|^{2}+G\left\|{w}\right\|$
$\displaystyle\leq\|{\mathcal{Y}}\|^{2}+\|{\mathcal{Y}}\|\sqrt{H}B\|{\mathcal{X}}\|+HB^{2}\|{\mathcal{X}}\|^{2}$
$\displaystyle\leq
3\left({\|{\mathcal{Y}}\|^{2}+HB^{2}\|{\mathcal{X}}\|^{2}}\right)$

where the last step follow from AM-GM inequality. ∎

###  A.3 Low Dimension

Before presenting the proof of Theorem 1, we provide formal statements of its
Corollaries.

Corollary 1, stated below, gives an upper bound on excess risk of gradient
descent in the non-private setting.

######  Corollary 1.

Let $\ell$ be a non-negative convex $\widetilde{H}$ smooth loss function,
bounded at zero by $\left\|{{\mathcal{Y}}}\right\|^{2}$. Let
$n_{0}=\frac{\widetilde{H}B^{2}}{\|{\mathcal{Y}}\|^{2}}$,
${\mathcal{W}}={\mathcal{B}}\left({B}\right)$, $T=n$, and
$\eta=\min\Big{(}\frac{B}{\sqrt{T}\sqrt{\widetilde{H}}\|{\mathcal{Y}}\|},\frac{1}{4\widetilde{H}}\Big{)}$.
Given a dataset $S$ of $n\geq n_{0}$ i.i.d samples from an unknown
distribution ${\mathcal{D}}$, the excess risk of output of Algorithm 1 with
$\sigma=0$ is bounded as,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]\leq
O\left({\frac{\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}}\right).$

Corollary 2 below gives an upper bound on excess risk of noisy gradient
descent for non-negative smooth GLMs.

######  Corollary 2.

Let $n_{0}=\frac{H\|{\mathcal{X}}\|^{2}B^{2}}{\|{\mathcal{Y}}\|^{2}}$,
$\eta=\min\Big{(}\frac{B}{\sqrt{T}\max\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|,\sigma\sqrt{d}}\right)},\frac{1}{4H\|{\mathcal{X}}\|}\Big{)}$,
${\mathcal{W}}={\mathcal{B}}\left({B}\right)$,
$\sigma^{2}=\frac{8G^{2}T\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}$
and $T=n$. Let $\ell$ be a non-negative convex $H$ smooth GLM, bounded at zero
by $\left\|{{\mathcal{Y}}}\right\|^{2}$. Algorithm 1 satisfies
$(\epsilon,\delta)$-differential privacy. Given a dataset
$S\sim{\mathcal{D}}^{n}$, $n\geq n_{0}$, then the excess risk of output of
Algorithm 1 is bounded as,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]=O\Bigg{(}\frac{\sqrt{H}\|{\mathcal{X}}\|B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|+H\|{\mathcal{X}}\|^{2}B^{2}}\right)B\sqrt{d\operatorname{log}\left(1/\delta\right)}}{n\epsilon}\Bigg{)}.$

####  A.3.1 Proof of Theorem 1

Since Algorithm 1 uses a projection step, the iterates always lie in the
constraint set $\left\\{{w:\left\|{w}\right\|\leq B}\right\\}$. Hence, the
function over this constraint set is $G$-Lipschitz. From the analysis of Noisy
(S)GD in [9, 6], we have that the setting of noise variance $\sigma^{2}$
ensures that the algorithm satisfies $(\epsilon,\delta)$-DP

We now move to the utility part. We start with the decomposition of excess
risk as

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]=\mathbb{E}[L(\widehat{w};{\mathcal{D}})-\widehat{L}(\widehat{w};S)]+\mathbb{E}[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)]$
(3)

The key arguments are as follows: we first bound generalization gap, or on-
average stability (first term in the right hand side above), in terms of
average argument stability and excess empirical risk (Lemma 4). We then bound
average argument stability in terms of average regret (Lemma 5). Finally, in
Lemma 6, we provide bounds on excess empirical risk and average regret of
gradient descent. Substituting these in the above equation gives the claimed
bound. We now fill in the details.

We start with Lemma 4 which gives the following bound on the generalization
gap:

$\displaystyle\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-\widehat{L}(\widehat{w};S)]$
$\displaystyle\leq\frac{\sqrt{\widetilde{H}}B}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}\left({\mathbb{E}[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)]}\right)+\frac{2\sqrt{\widetilde{H}n}\|{\mathcal{Y}}\|}{B}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}+\frac{\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}$
(4)

Substituting the bound on $\varepsilon_{\mathsf{av-stab}}({\mathcal{A}})$ from
Lemma 5, the second term becomes,

$\displaystyle\frac{2\sqrt{\widetilde{H}n}\|{\mathcal{Y}}\|}{B}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}$
$\displaystyle\leq\frac{16\widetilde{H}^{3/2}\eta^{2}T\|{\mathcal{Y}}\|}{\sqrt{n}B}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{16\widetilde{H}^{3/2}\eta^{2}T\|{\mathcal{Y}}\|}{\sqrt{n}B}$
$\displaystyle\leq\frac{16\sqrt{\widetilde{H}}B}{\sqrt{n}\|{\mathcal{Y}}\|}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{16\sqrt{\widetilde{H}}B}{\sqrt{n}\|{\mathcal{Y}}\|}$
$\displaystyle\leq\frac{16}{n}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{16\sqrt{\widetilde{H}}B}{\sqrt{n}\|{\mathcal{Y}}\|}.$

Substituting the above in Eqn. (4) and using the fact that
$\frac{\sqrt{\widetilde{H}}B}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}\leq 1$
from the lower bound on $n$, we get:

$\displaystyle\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-\widehat{L}(\widehat{w};S)]$
$\displaystyle\leq\left({\mathbb{E}[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)]}\right)+\frac{16}{n}\left({\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]}\right)$
$\displaystyle+\frac{17\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}.$

From the excess empirical risk guarantee (Lemma 6), the terms excess empirical
risk $\mathbb{E}[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)]$ and average
regret
$\frac{1}{n}\left({\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]}\right)$
are both bounded by the same quantity. Thus, substituting the above in Eqn.
(3) and substituting the bound from 6, we have,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]$
$\displaystyle\leq\frac{18}{n}\sum_{j=1}^{n}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{17\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}$
$\displaystyle\leq
O\left({\frac{\sqrt{H}B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\sqrt{d}GB\operatorname{log}\left(1/\delta\right)}{n\epsilon}}\right).$

Substituting the value of $G$ completes the proof.

######  Lemma 4.

Let $n\geq\frac{\widetilde{H}B^{2}}{\|{\mathcal{Y}}\|^{2}}$. Let $\ell$ be a
non-negative $\widetilde{H}$ smooth convex loss function. Let $S$ be a dataset
of $n$ i.i.d. samples from an unknown distribution ${\mathcal{D}}$, and
$w^{*}$ denote the optimal population risk minimizer. The generalization gap
of algorithm ${\mathcal{A}}$ is bounded as,

$\displaystyle\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-\widehat{L}({\mathcal{A}}(S);S)]$
$\displaystyle\leq\frac{\sqrt{\widetilde{H}}B}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}\left({\mathbb{E}[\widehat{L}({\mathcal{A}}(S);S)-\widehat{L}(w^{*};S)]}\right)+\frac{2\sqrt{\widetilde{H}n}\|{\mathcal{Y}}\|}{B}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}$
$\displaystyle+\frac{\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}.$

###### Proof.

Let $\widehat{w}:={\mathcal{A}}(S)$, $S^{(i)}$ be the dataset where the $i$-th
data point is replaced by an i.i.d. point $(x^{\prime},y^{\prime})$ and let
$\widehat{w}^{(i)}$ be the corresponding output of ${\mathcal{A}}$.

A standard fact (see [24]) is that generalization gap is equal to on-average
stability:

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-\widehat{L}(\widehat{w};S)]=\mathbb{E}[\ell(\widehat{w}^{(i)};(x_{i},y_{i}))-\ell(\widehat{w};(x_{i},y_{i})].$

From smoothness and self-bounding property, we have,

$\displaystyle\ell(\widehat{w}^{(i)};(x_{i},y_{i}))-\ell(\widehat{w};(x_{i},y_{i})$
$\displaystyle\leq\left\|{\nabla\ell(\widehat{w};(x_{i},y_{i}))}\right\|\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|+\frac{\widetilde{H}}{2}\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|^{2}$
$\displaystyle\leq
2\sqrt{\widetilde{H}\ell((\widehat{w};(x_{i},y_{i}))}\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|+\frac{\widetilde{H}}{2}\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|^{2}.$

Taking expectation, using Cauchy-Schwarz inequality and substituting average
argument stability, we get,

$\displaystyle\mathbb{E}\left[\ell(\widehat{w}^{(i)};(x_{i},y_{i}))-\ell(\widehat{w};(x_{i},y_{i})\right]$
$\displaystyle\leq
2\sqrt{\widetilde{H}\mathbb{E}[\ell((\widehat{w};(x_{i},y_{i}))]}\sqrt{\mathbb{E}[\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|^{2}]}+\frac{\widetilde{H}}{2}\mathbb{E}\left[\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|^{2}\right]$
(5) $\displaystyle\leq
2\sqrt{\widetilde{H}\mathbb{E}[\widehat{L}(\widehat{w};S)]}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})+\frac{\widetilde{H}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}}{2}$
$\displaystyle\leq\frac{\sqrt{\widetilde{H}}B\mathbb{E}[\widehat{L}(\widehat{w};S)]}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}+\frac{\sqrt{\widetilde{H}n}\left\|{{\mathcal{Y}}}\right\|\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}}{B}+\frac{\widetilde{H}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}}{2}$
$\displaystyle\leq\frac{\sqrt{\widetilde{H}}B}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}\left({\mathbb{E}[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)]}\right)+\frac{\sqrt{\widetilde{H}n}\left\|{{\mathcal{Y}}}\right\|\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}}{B}+\frac{\widetilde{H}\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}}{2}$
$\displaystyle+\frac{\sqrt{\widetilde{H}}B}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}\mathbb{E}[\widehat{L}(w^{*};S)]$
$\displaystyle\leq\frac{\sqrt{\widetilde{H}}B}{\sqrt{n}\left\|{{\mathcal{Y}}}\right\|}\left({\mathbb{E}[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)]}\right)+\left({\frac{\sqrt{\widetilde{H}n}\|{\mathcal{Y}}\|}{B}+\frac{\widetilde{H}}{2}}\right)\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}$
$\displaystyle+\frac{\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}$ (6)

where the third inequality follows from AM-GM inequality, and last follows
since $w^{*}$ is the optimal solution:
$\mathbb{E}[\widehat{L}(w^{*};S)]=L(w^{*};{\mathcal{D}})\leq
L(0;{\mathcal{D}})\leq\|{\mathcal{Y}}\|^{2}$. Finally, using the lower bound
on $n$, we have
$\frac{\widetilde{H}}{2}\leq\frac{\sqrt{\widetilde{H}n}\|{\mathcal{Y}}\|}{B}$,
substituting which gives the claimed bound. ∎

######  Lemma 5.

The average argument stability for noisy GD (Algorithm 1) run for $T$
iterations with step size $\eta\leq\frac{4}{\widetilde{H}}$ is bounded as

$\varepsilon_{\mathsf{av-
stab}}({\mathcal{A}})^{2}\leq\frac{8\widetilde{H}\eta^{2}T}{n}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{8\widetilde{H}\eta^{2}T\|{\mathcal{Y}}\|^{2}}{n}.$

###### Proof.

The uniform argument stability analysis for (Noisy) (S)GD is limited to the
Lipschitz setting [16, 6, 5] and therefore not directly applicable. We
therefore need to modify the arguments to give an average stability analysis
in smooth (non-Lipschitz) case.

Let $\widehat{w}:={\mathcal{A}}(S)$, $S^{(i)}$ be the dataset where the $i$-th
data point is replaced by an i.i.d. point $(x^{\prime},y^{\prime})$ and let
$\widehat{w}^{(i)}$ be the corresponding output of ${\mathcal{A}}$. Moroever,
let $w_{i}$ denote the iterate of noisy SGD on dataset $S$ and similarly
$\widetilde{w}_{i}^{(i)}$ for dataset $S^{(i)}$.

We simply couple the Gaussian noise sampled at each iteration to be equal on
both datasets. Using the fact the the updates are non-expansive, we have

$\displaystyle\left\|{w_{t+1}-w_{t+1}^{\prime}}\right\|$
$\displaystyle\leq\left\|{w_{t}-w_{t}^{\prime}}\right\|+\frac{\eta\left({\left\|{\nabla\ell(w_{t};(x_{i},y_{i}))}\right\|+\left\|{\nabla\ell(w_{t}^{\prime};(x^{\prime};y^{\prime}))}\right\|}\right)}{n}$
$\displaystyle\leq\frac{\eta\sum_{j=1}^{t}\left({\left\|{\nabla\ell(w_{j};(x_{i},y_{i}))}\right\|+\left\|{\nabla\ell(w_{j}^{\prime};(x^{\prime};y^{\prime}))}\right\|}\right)}{n}.$

From the self-bounding property (Fact 1),
$\left({\left\|{\nabla\ell(w_{j};(x_{i},y_{i}))}\right\|}\right)\leq
2\sqrt{\widetilde{H}\ell(w_{j};(x_{i},y_{i}))}$). Therefore, we get,

$\displaystyle\mathbb{E}[\left\|{w_{t}-w_{t}^{\prime}}\right\|^{2}]$
$\displaystyle\leq\frac{4\widetilde{H}\eta^{2}T}{n^{2}}\sum_{j=1}^{t}\left({\mathbb{E}[\ell(w_{j};(x_{i},y_{i}))+\ell(w_{j}^{\prime};(x^{\prime},y^{\prime}))]}\right)$
$\displaystyle=\frac{8\widetilde{H}\eta^{2}T}{n^{2}}\sum_{j=1}^{t}\mathbb{E}[\widehat{L}(w_{j};S)].$

For the average iterate,

$\displaystyle\mathbb{E}\left[\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|^{2}\right]$
$\displaystyle\leq\frac{1}{T^{2}}T\sum_{t=1}^{T}\mathbb{E}[\left\|{w_{t}-w_{t}^{\prime}}\right\|^{2}]\leq\frac{8\widetilde{H}\eta^{2}T}{n^{2}}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)]$
$\displaystyle\leq\frac{8\widetilde{H}\eta^{2}T}{n}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{8\widetilde{H}\eta^{2}T}{n}\mathbb{E}[\widehat{L}(w^{*};S)]$
$\displaystyle\leq\frac{8\widetilde{H}\eta^{2}T}{n}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)]+\frac{8\widetilde{H}\eta^{2}T\|{\mathcal{Y}}\|^{2}}{n}$

where the last inequality follows since $w^{*}$ is the population risk
minimizer: $\mathbb{E}[\widehat{L}(w^{*};S)]=L(w^{*};{\mathcal{D}})]\leq
L(0;{\mathcal{D}})\leq\|{\mathcal{Y}}\|^{2}$. ∎

######  Lemma 6.

Let $n\geq\frac{\widetilde{H}B^{2}}{\|{\mathcal{Y}}\|^{2}}$,
$\eta=\min\left({\frac{B}{\sqrt{T}\max\left({\sqrt{\widetilde{H}}\|{\mathcal{Y}}\|,\sigma\sqrt{d}}\right)},\frac{1}{4\widetilde{H}}}\right)$,
$\sigma^{2}=\frac{8G^{2}T\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}$
and $T=n$. We have,

$\displaystyle\mathbb{E}\left[\widehat{L}(\widehat{w};S)-\widehat{L}(w^{*};S)\right]\leq\frac{1}{T}\sum_{j=1}^{T}\mathbb{E}\left[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)\right]\leq
O\left({\frac{\sqrt{H}B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\sqrt{d}G\operatorname{log}\left(1/\delta\right)}{n\epsilon}}\right).$

where $w^{*}$ is the (minimum norm) population risk minimizer.

###### Proof.

From standard analysis of (S)GD,

$\displaystyle\mathbb{E}\left[\left\|{w_{t+1}-w^{*}}\right\|^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\|{w_{t}-\eta\left({\nabla\widehat{L}(w_{t};S)+\xi_{t}}\right)-w^{*}}\right\|^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\|{w_{t}-w^{*}}\right\|^{2}\right]+\eta^{2}\mathbb{E}\left[\left\|{\nabla\widehat{L}(w_{t};S)}\right\|^{2}\right]+\eta^{2}\sigma^{2}d-2\eta\mathbb{E}\left[\widehat{L}(w_{t};S)-\widehat{L}(w^{*};S)\right]$
$\displaystyle\leq\mathbb{E}\left[\left\|{w_{t}-w^{*}}\right\|^{2}\right]+4\eta^{2}\widetilde{H}\mathbb{E}[\widehat{L}(w_{t};S)]+\eta^{2}\sigma^{2}d-2\eta\mathbb{E}\left[\widehat{L}(w_{t};S)-\widehat{L}(w^{*};S)\right]$

where the last inequality follows from self-bounding property (Fact 1).
Rearranging, and using the fact that
$\mathbb{E}[\widehat{L}(w^{*};S)=L(w^{*};{\mathcal{D}})]\leq
L(0;{\mathcal{D}})\leq\|{\mathcal{Y}}\|^{2}$ we get,

$\displaystyle\left({1-2\eta\widetilde{H}}\right)\mathbb{E}\left[\widehat{L}(w_{t};S)-\widehat{L}(w^{*};S)\right]\leq\frac{\mathbb{E}\left[\left\|{w_{t}-w^{*}}\right\|^{2}-\left\|{w_{t+1}-w^{*}}\right\|^{2}\right]}{2\eta}+2\eta\left({\widetilde{H}\|{\mathcal{Y}}\|^{2}+\sigma^{2}d}\right)$

From the choice of $\eta$, we have
$\left({1-2\eta\widetilde{H}}\right)\geq\frac{1}{2}$. Averaging over $T$
iterations, we get that the average regret is,

$\displaystyle\frac{1}{T}\sum_{j=1}^{T}\mathbb{E}\left[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)\right]\leq\frac{B^{2}}{\eta
T}+4\eta\left({\widetilde{H}\|{\mathcal{Y}}\|^{2}+\sigma^{2}d}\right).$

Setting
$\eta=\min\left({\frac{B}{\sqrt{T}\max\left({\sqrt{\widetilde{H}}\|{\mathcal{Y}}\|,\sigma\sqrt{d}}\right)},\frac{1}{4\widetilde{H}}}\right)$,
we get

$\displaystyle\frac{1}{T}\sum_{j=1}^{T}\mathbb{E}\left[\widehat{L}(w_{j};S)-\widehat{L}(w^{*};S)\right]=O\left({\frac{\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{T}}+\frac{B\sqrt{d}\sigma}{\sqrt{T}}+\frac{\widetilde{H}B^{2}}{T}}\right).$

Finally, substituting
$\sigma^{2}=\frac{8G^{2}T\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}$,
$T=n$ and using the lower bound on $n$ gives the claimed bound on average
regret. Applying convexity to lower bound average regret by excess empirical
risk of $\widehat{w}$ gives the same bound on excess empirical risk. ∎

###  A.4 High Dimension

###### Proof of Theorem 2.

Let $\alpha\leq 1$ be a parameter to be set later. From the JL property with
$k=O\left({\frac{\operatorname{log}\left(2n/\delta\right)}{\alpha^{2}}}\right)$,
with probability at least $1-\delta/2$, for all data points $x_{i}$,
$\left\|{\Phi
x_{i}}\right\|\leq\left({1+\alpha}\right)\left\|{x_{i}}\right\|\leq
2\left\|{{\mathcal{X}}}\right\|$, and $\left\|{\Phi w^{*}}\right\|^{2}\leq
2\left\|{w^{*}}\right\|^{2}\leq 2B^{2}$.

Further, by Lemma 2, for any $w$ in the embedding space with
$\left\|{w}\right\|^{2}\leq B$, with probability at least $1-\delta/2$, the
loss is $G$ Lipschitz where
$G=2\left\|{{\mathcal{Y}}}\right\|\sqrt{H}\left\|{{\mathcal{X}}}\right\|+2HB\left\|{{\mathcal{X}}}\right\|^{2}$.
The privacy guarantee now follows from the privacy of Noisy SGD and post-
processing.

For the utility guarantee, let $L(w;\Phi{\mathcal{D}})$ and
$\widehat{L}(w;\Phi S)$ denote population and empirical risk (resp) where test
and training feature vectors (resp) are mapped using $\Phi$. The excess risk
can be decomposed as:

$\displaystyle\mathbb{E}\left[L(\Phi^{\top}\widetilde{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})\right]=\mathbb{E}\left[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})\right]+\mathbb{E}\left[L(\Phi
w^{*};\Phi{\mathcal{D}})-L(w^{*};{\mathcal{D}})\right].$ (7)

The first term in Eqn. (7) is bounded by the utility guarantee of the DP-SCO
method. In particular, from Lemma 7 (below), we have

$\displaystyle\mathbb{E}[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})]=O\left({\frac{\sqrt{H}\|{\mathcal{X}}\|B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|+H\|{\mathcal{X}}\|^{2}B^{2}}\right)B\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}}\right).$

The second term in Eqn. (7) is bounded by the JL property together with
smoothness and the fact that $w^{*}$ is the optimal solution thus $\nabla
L(w^{*};{\mathcal{D}})=0$. This gives us

$\displaystyle\mathbb{E}[L(\Phi
w^{*};\Phi{\mathcal{D}})]-L(w^{*};{\mathcal{D}})]\leq\frac{H}{2}\mathbb{E}\left[\left|{\left\langle{\Phi
w^{*}},{\Phi
x}\right\rangle-\left\langle{w^{*}},{x}\right\rangle}\right|^{2}\right]\leq\frac{\alpha^{2}H\left\|{w^{*}}\right\|^{2}\|{\mathcal{X}}\|^{2}}{2}\leq\widetilde{O}\left(\frac{HB^{2}\|{\mathcal{X}}\|^{2}}{k}\right).$

Combining, we get,

$\displaystyle\mathbb{E}\left[L(\Phi^{\top}\widetilde{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})\right]\leq\widetilde{O}\left({\frac{\sqrt{H}\|{\mathcal{X}}\|B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|+H\|{\mathcal{X}}\|^{2}B}\right)B\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}+\frac{HB^{2}\|{\mathcal{X}}\|^{2}}{k}}\right).$

Setting
$k=O\left({\frac{BH\left\|{{\mathcal{X}}}\right\|\operatorname{log}\left(2n/\delta\right)n\epsilon}{G}}\right)^{2/3}$
completes the proof.

∎

######  Lemma 7.

Let $\Phi\in{\mathbb{R}}^{d\times k}$ be a data-oblivious JL matrix. Let
$S=\left\\{{\left({x_{i},y_{i}}\right)}\right\\}_{i=1}^{n}$ of $n$ i.i.d data
points and let $\Phi S:=\left\\{{(\Phi x_{i},y_{i})}\right\\}_{i=1}^{n}$. Let
$\widetilde{w}\in{\mathbb{R}}^{k}$ be the average iterate returned by
Algorithm 1 with
$\sigma^{2}=O\left({\frac{G^{2}\left\|{{\mathcal{X}}}\right\|^{2}\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}}\right)$
on dataset $\Phi S$. For
$k=\Omega\left({\operatorname{log}\left(n\right)}\right)$, the excess risk of
$\widetilde{w}$ on $\Phi{\mathcal{D}}$ is bounded as,

$\displaystyle\mathbb{E}[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})]\leq
O\left({\frac{\sqrt{H}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|+H\|{\mathcal{X}}\|^{2}B}\right)B\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}}\right).$

###### Proof.

Let $S^{(i)}$ be the dataset where the $i$-th data point is replaced by an
i.i.d. point $(x^{\prime},y^{\prime})$ and let $\widetilde{w}^{(i)}$ be the
corresponding output of Noisy-SGD on $\Phi S^{(i)}$. Define
$\overline{S}:=\left\\{{S,(x^{\prime},y^{\prime})}\right\\}$ and let
$H(\Phi,\overline{S})$ denote an upper bound on the smoothness parameter of
the family of loss function $\left\\{{\ell(w;(\Phi
x;y))}\right\\}_{(x,y)\in\overline{S}}$.

We want to apply Theorem 1, but the theorem requires that
$n\geq\frac{2H\|{\mathcal{X}}\|^{2}B^{2}}{\|{\mathcal{Y}}\|^{2}}$. In the
proof below, we will use it to bound
$H(\Phi,\overline{S})\leq\frac{n\|{\mathcal{Y}}\|^{2}}{B^{2}}$. We use the JL
property to get this. Let $\alpha\leq 1$ be a parameter to be set later. Note
that $H(\Phi,\overline{S})\leq H\sup_{(x,y)\in\overline{S}}\left\|{\Phi
x}\right\|^{2}\leq
H\left({1+\alpha}\right)\left\|{{\mathcal{X}}}\right\|^{2}\leq
2H\left\|{{\mathcal{X}}}\right\|^{2}$ with probability at least $1-\delta$ for
$k=O\left({\frac{\operatorname{log}\left(2n/\delta\right)}{\alpha^{2}}}\right)$.
Thus, if we assume
$n\geq\frac{2H\|{\mathcal{X}}\|^{2}B^{2}}{\|{\mathcal{Y}}\|^{2}}$, then w.h.p.
$H(\Phi,\overline{S})\leq\frac{n\|{\mathcal{Y}}\|^{2}}{B^{2}}$. Also from the
JL property, $\left\|{\Phi w^{*}}\right\|\leq 2B$.

Decomposing excess risk and writing generalization gap as on-average
stability, we have

$\displaystyle\mathbb{E}_{\Phi,S}[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})]$
$\displaystyle=\mathbb{E}_{\Phi,S}[L(\Phi^{\top}\widetilde{w};{\mathcal{D}})-\widehat{L}(\Phi^{\top}\widetilde{w};S)]+\mathbb{E}_{\Phi,S}[\widehat{L}(\Phi^{\top}\widetilde{w};S)]-\widehat{L}(\Phi
w^{*};\Phi S)]$
$\displaystyle=\mathbb{E}_{\overline{S},\Phi}[\ell(\widetilde{w}^{(i)};(\Phi
x_{i},y_{i}))-\ell(\widetilde{w};(\Phi
x_{i},y_{i}))+\widehat{L}(\Phi^{\top}\widetilde{w};S)-\widehat{L}(\Phi
w^{*};\Phi S)].$

We now fix the randomness of $\overline{S}$ and bound the terms in high
probability w.r.t. the random $\Phi$. Let
$\operatorname{IAS}(\overline{S},i)=\left\|{\widehat{w}-\widehat{w}^{(i)}}\right\|$
denote the instance argument stability. Repeating the analysis in Theorem 1,
from Eqn. (A.3.1), the first term is bounded as,

$\displaystyle\ell(\widetilde{w}^{(i)};(\Phi
x_{i},y_{i}))-\ell(\widetilde{w};(\Phi x_{i},y_{i}))$
$\displaystyle\leq\frac{\sqrt{H(\Phi,\overline{S})}B}{\sqrt{n}Y}\left({\ell(\widehat{w};(\Phi
x_{i},y_{i}))-\widehat{L}(\Phi w^{*};\Phi S)}\right)$
$\displaystyle+\left({\frac{\sqrt{H(\Phi,\overline{S})n}\|{\mathcal{Y}}\|}{B}+\frac{H(\Phi,\overline{S})}{2}}\right)\operatorname{IAS}(\overline{S},i)^{2}+\frac{\sqrt{H(\Phi,\overline{S})B\|{\mathcal{Y}}\|}}{\sqrt{n}}$
$\displaystyle\leq\frac{2\sqrt{H}\|{\mathcal{X}}\|B}{\sqrt{n}Y}\left({\ell(\widehat{w};(\Phi
x_{i},y_{i}))-\widehat{L}(\Phi w^{*};\Phi S)}\right)$
$\displaystyle+\frac{4\sqrt{Hn}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|}{B}\operatorname{IAS}(\overline{S},i)^{2}+\frac{2\sqrt{HB\|{\mathcal{Y}}\|}\|{\mathcal{X}}\|}{\sqrt{n}}$
(8)

where the last inequality holds from application of JL property: with
probability at least $1-\delta$,
$H(\Phi,\overline{S})\leq\frac{n\|{\mathcal{Y}}\|^{2}}{B^{2}}$ (from the lower
bound on $n$) and $H(\Phi,\overline{S})\leq 2H\|{\mathcal{X}}\|^{2}$.

As in the proof of Lemma 5, $\operatorname{IAS}(\overline{S},i)$ is bounded
as,

$\displaystyle\operatorname{IAS}(\overline{S},i)^{2}$
$\displaystyle\leq\frac{8H(\Phi,\overline{S})\eta^{2}T}{n}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\ell(w_{j};(\Phi
x_{i},y_{i}))+\ell(w_{j}^{\prime};(\Phi
x^{\prime},y^{\prime}))-2\widehat{L}(\Phi w^{*};\Phi
S)]+\frac{8H(\Phi,\overline{S})\eta^{2}T\|{\mathcal{Y}}\|^{2}}{n}$
$\displaystyle\leq\frac{16H\|{\mathcal{X}}\|^{2}\eta^{2}T}{n}\frac{1}{n}\sum_{j=1}^{T}\mathbb{E}[\ell(w_{j};(\Phi
x_{i},y_{i}))+\ell(w_{j}^{\prime};(\Phi
x^{\prime},y^{\prime}))-2\widehat{L}(\Phi w^{*};\Phi
S)]+\frac{16H\|{\mathcal{X}}\|^{2}\eta^{2}T\|{\mathcal{Y}}\|^{2}}{n}.$

Substituting the above in equation A.4, taking expectation with respect to
$\overline{S}$ and from manipulations as in the proof of Theorem 1, we get
that with probability at least $1-\delta$, we have

$\displaystyle\mathbb{E}_{S}[L(\Phi^{\top}\widetilde{w};{\mathcal{D}})-\widehat{L}(\Phi^{\top}\widetilde{w};S)]$
$\displaystyle\leq 2\left({\mathbb{E}[\widehat{L}(\widehat{w};\Phi
S)-\widehat{L}(\Phi w^{*};\Phi S)]}\right)$
$\displaystyle+\frac{32}{n}\left({\sum_{j=1}^{T}\mathbb{E}[\widehat{L}(w_{j};\Phi
S)-\widehat{L}(w^{*};\Phi
S)]}\right)+\frac{34\sqrt{\widetilde{H}}B\|{\mathcal{Y}}\|}{\sqrt{n}}.$

Let
$G(\Phi,S)=G=2\left\|{{\mathcal{Y}}}\right\|\sqrt{H(\Phi,\overline{S})}+2H(\Phi,\overline{S})\left\|{\Phi
w^{*}}\right\|$ denote the Lispchitzness parameter of the family of loss
functions $\left\\{{\ell(w;(\Phi x,y)}\right\\}_{(x,y)\in\overline{S}}$. From
the analysis in Lemma 6, the average regret and excess empirical risk terms
are both bounded by the following quantity with high probability.

$\displaystyle
O\left({\frac{\sqrt{H(\Phi,\overline{S})}B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\sqrt{k}G(\Phi,S)\operatorname{log}\left(1/\delta\right)}{n\epsilon}}\right)\leq
O\left({\frac{\sqrt{H}B\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\sqrt{k}G\operatorname{log}\left(1/\delta\right)}{n\epsilon}}\right).$

This gives the following high probability bound,

$\displaystyle\mathbb{E}[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})]\leq
O\left({\frac{\sqrt{H}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|}{\sqrt{n}}+\frac{\left({\sqrt{H}\|{\mathcal{X}}\|\|{\mathcal{Y}}\|+H\|{\mathcal{X}}\|^{2}B}\right)B\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}}\right).$

For the in-expectation bound, note that in the above proof the JL property was
used for: with probability at least $1-\delta$,
$\sup_{(x,y)\in\overline{S}}\left\|{\Phi
x}\right\|\leq\left({1+\frac{\sqrt{\operatorname{log}\left(n/\delta\right)}}{k}}\right)\left\|{{\mathcal{X}}}\right\|$
and $\left\|{\Phi
w^{*}}\right\|\leq\left({1+\frac{\sqrt{\operatorname{log}\left(n/\delta\right)}}{k}}\right)B$.
All these quantities appear in the numerator in the above bound. Therefore the
excess risk random variable w.r.t $\Phi$ has a tail with a
$\operatorname{poly}\left({\frac{\sqrt{\operatorname{log}\left(n/\delta\right)}}{k}}\right)$
term. This is a (non-centered) sub-Weibull random variable and from
equivalence of tail and moments bounds (e.g. Theorem 3.1 in [29]) and
$\frac{\operatorname{log}\left(n\right)}{k}\leq O(1)$, we get the claimed
expectation bound.

∎

###  A.5 Constrained Regularized ERM with Output Perturbation

We here state a key result from [25]. Let
$\mathfrak{R}_{n}(B,\left\|{{\mathcal{X}}}\right\|)$ denote the expected
Rademacher complexity of linear predictors with norm bound by $B$, with $n$
datapoints and norm of each point bounded by $\left\|{{\mathcal{X}}}\right\|$.

######  Theorem 9.

[[25]] Let $\ell$ be an $H$-smooth GLM and let $R$ be a bound on the loss
function. For a dataset $S$ of $n$ i.i.d samples, with probability at least
$1-\beta$, for all $w$ such that $\left\|{w}\right\|\leq B$, we have

$\displaystyle L(w;{\mathcal{D}})\leq\widehat{L}(w;S)+$ $\displaystyle
O\Bigg{(}\sqrt{\widehat{L}(w;S)}\left({\sqrt{H}\operatorname{log}^{1.5}(n)\mathfrak{R}_{n}(B,\left\|{{\mathcal{X}}}\right\|)+\sqrt{\frac{R\operatorname{log}\left(1/\beta\right)}{n}}}\right)$
$\displaystyle+H\operatorname{log}^{3}(n)\mathfrak{R}_{n}^{2}(B,\left\|{{\mathcal{X}}}\right\|)+\frac{R\operatorname{log}\left(1/\beta\right)}{n}\Bigg{)}.$
(9)

######  Corollary 3.

Let
$\widetilde{w}=\mathop{\arg\min}\limits_{w\in{\mathcal{B}}\left({B}\right)}\left\\{{\widehat{L}(w;S)}\right\\}$
and $n\geq\frac{HB^{2}\|{\mathcal{X}}\|^{2}}{\|{\mathcal{Y}}\|^{2}}$. Then
with probability at least $1-\beta$ under the randomness of $S$ we have

$L(\widetilde{w};{\mathcal{D}})-\widehat{L}(\widetilde{w};S)=\widetilde{O}\left({\frac{\sqrt{H}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|\sqrt{\operatorname{log}\left(1/\beta\right)}}{\sqrt{n}}+\frac{\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(1/\beta\right)}{\sqrt{n}}}\right).$

Further, in expectation under the randomness of S it holds that

$\mathbb{E}[L(\widetilde{w};{\mathcal{D}})-\widehat{L}(\widetilde{w};S)]=\widetilde{O}\left({\frac{\sqrt{H}\|{\mathcal{Y}}\|B\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}+\frac{\left\|{{\mathcal{Y}}}\right\|^{2}}{\sqrt{n}}}\right).$

###### Proof.

In our application, $w$ will be the output of regularized ERM $\widetilde{w}$,
thus
$\widehat{L}(\widetilde{w};S)\leq\widehat{L}_{\lambda}(0;S)\leq\left\|{{\mathcal{Y}}}\right\|^{2}$.

From Lemma 3 we have that $R\leq
3(\|{\mathcal{Y}}\|^{2}+HB^{2}\|{\mathcal{X}}\|^{2})$. Also,
$\mathfrak{R}_{n}(B,\left\|{{\mathcal{X}}}\right\|)\leq
O\left({\frac{B\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}}\right)$ [24]. We now
plug in the quantities into the above theorem to get that with probability at
least $1-\beta$,

$\displaystyle L(\widetilde{w};{\mathcal{D}})-\widehat{L}(\widetilde{w};S)$
$\displaystyle=\widetilde{O}\Bigg{(}\frac{\sqrt{H}B\|{\mathcal{X}}\|}{\sqrt{n}}\left({\|{\mathcal{Y}}\|+\frac{\sqrt{H}B\|{\mathcal{X}}\|}{\sqrt{n}}}\right)$
$\displaystyle+\frac{\left({\|{\mathcal{Y}}\|+\sqrt{H}B\|{\mathcal{X}}\|}\right)\sqrt{\operatorname{log}\left(1/\beta\right)}}{\sqrt{n}}\left({\|{\mathcal{Y}}\|+\frac{\left({\|{\mathcal{Y}}\|+\sqrt{H}B\|{\mathcal{X}}\|}\right)\sqrt{\operatorname{log}\left(1/\beta\right)}}{\sqrt{n}}}\right)\Bigg{)}$
$\displaystyle=\widetilde{O}\left({\frac{\sqrt{H}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|\sqrt{\operatorname{log}\left(1/\beta\right)}}{\sqrt{n}}+\frac{\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(1/\beta\right)}{\sqrt{n}}}\right)$

where the last follows by simplifications using the lower bound on $n$.

For the in expectation result, observe that the above Eqn (9) is a tail bound
for a sub-Gamma random variable with variance parameter
$O\left({\frac{\sqrt{H}B\|{\mathcal{X}}\|\|{\mathcal{Y}}\|}{\sqrt{n}}}\right)$
and scale parameter $O\left({\frac{\|{\mathcal{Y}}\|^{2}}{\sqrt{n}}}\right)$.
From the equivalence of tail and moment bounds of sub-Gamma random variables,
[8] we get the claimed in-expectation bound. ∎

###  A.6 Proof of Theorem 3

###### Proof.

Recall from Lemma 2 that the (un-regularized) loss is $G$-Lipschitz on the
constraint set with $\left\|{w}\right\|\leq B$, where
$\widetilde{G}:=\left({\sqrt{H}\left\|{{\mathcal{Y}}}\right\|+HB\left\|{{\mathcal{X}}}\right\|}\right){\left\|{{\mathcal{X}}}\right\|}$.
Note that from a standard analysis [4], we get that $\ell_{2}$ sensitivity (or
uniform argument stability) is $O\left({\frac{G}{n\lambda}}\right)$, hence
$\sigma^{2}=O\left({\frac{G^{2}\operatorname{log}\left(1/\delta\right)}{\lambda^{2}n^{2}\epsilon^{2}}}\right)$
ensures $(\epsilon,\delta)$-DP.

For the utility analysis, the excess risk can be decomposed as follows,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]$
$\displaystyle=\mathbb{E}[L(\widetilde{w};{\mathcal{D}})-\widehat{L}(\widetilde{w};S)]+\mathbb{E}[\widehat{L}(\widetilde{w};S)-\widehat{L}(w^{*};S)]+\mathbb{E}[L(\widetilde{w}+\xi;{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})].$

The first term is bounded by the Rademacher complexity result (Corollary 3).

The second term is simply bounded by
$\frac{\lambda}{2}\left\|{\widetilde{w}}\right\|^{2}\leq\frac{\lambda}{2}B^{2}$
since $\widetilde{w}$ lies in the constraint set. The third term is bounded
using smoothness as follows:

$\displaystyle\mathbb{E}[L(\widetilde{w}+\xi;{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]$
$\displaystyle=\mathbb{E}\left[\phi_{y}\left({\left\langle{\widetilde{w}+\xi},{x}\right\rangle}\right)-\phi_{y}\left({\left\langle{\widetilde{w}},{x}\right\rangle}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\phi_{y}^{\prime}(\left\langle{\widetilde{w}},{x}\right\rangle)\left\langle{\xi},{x}\right\rangle+\frac{H}{2}\left|{\left\langle{\xi},{x}\right\rangle}\right|^{2}\right]$
$\displaystyle\leq\frac{H}{2}\sigma^{2}\left\|{{\mathcal{X}}}\right\|^{2}=O\left({\frac{HG^{2}\left\|{{\mathcal{X}}}\right\|^{2}\operatorname{log}\left(1/\delta\right)}{\lambda^{2}n^{2}\epsilon^{2}}}\right)$

where the last inequality follows since $\mathbb{E}\xi=0$ and
$\left\langle{\xi},{x}\right\rangle\sim{\mathcal{N}}(0,\sigma^{2}\left\|{x}\right\|^{2})$.
We now plug in
$\lambda=\left({\frac{G\sqrt{H}\left\|{{\mathcal{X}}}\right\|}{B}}\right)^{2/3}\frac{\left({\operatorname{log}\left(1/\delta\right)}\right)^{1/3}}{\left({n\epsilon}\right)^{2/3}}$.
and
$G=\left({\sqrt{H}\left\|{{\mathcal{Y}}}\right\|+HB\left\|{{\mathcal{X}}}\right\|}\right){\left\|{{\mathcal{X}}}\right\|}$
to get,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]$
$\displaystyle\leq\widetilde{O}\Bigg{(}\frac{\sqrt{H}B\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|+\|{\mathcal{Y}}\|^{2}}{\sqrt{n}}+\frac{\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{4/3}\left\|{{\mathcal{Y}}}\right\|^{2/3}+\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{2}}{(n\epsilon)^{2/3}}\Bigg{)}.$

∎

###  A.7 Proof of Theorem 4

###### Proof.

Define $F(w;S)=\frac{1}{n}\sum_{(x,y)\in
S}(\left\langle{w},{x}\right\rangle-y)^{2}$. Let
$d^{\prime}<\min\left\\{{n,d}\right\\}$ and $b,p\in[0,1]$ be parameters to be
chosen later. For any $\boldsymbol{\sigma}\in\left\\{{\pm
1}\right\\}^{d^{\prime}}$, define the dataset $S_{\boldsymbol{\sigma}}$ which
consists of the union of $d^{\prime}$ subdatasets, $S_{1},...,S_{d^{\prime}}$
given as follows. Set $\frac{pn}{d^{\prime}}$ of the feature vectors in
$S_{j}$ as $\|{\mathcal{X}}\|e_{j}$ (the rescaled $j$’th standard basis
vector) and the rest as the zero vector. Set $\frac{pn}{2d}(1+b)$ of the
labels as $\boldsymbol{\sigma}_{j}\|{\mathcal{Y}}\|$ and $\frac{pn}{2d}(1-b)$
labels as $-\boldsymbol{\sigma}_{j}\|{\mathcal{Y}}\|$. Let
$w^{\boldsymbol{\sigma}}=\mathop{\arg\min}_{w\in\mathbb{R}^{d}}\left\\{{F(w;S_{\boldsymbol{\sigma}})}\right\\}$
be the ERM minimizer of $F(\cdot;S_{\boldsymbol{\sigma}})$. Following from
Lemma 2 of [23] we have that for any $\bar{w}\in\mathbb{R}^{d}$ that

$F(\bar{w};S_{\boldsymbol{\sigma}})-F(w^{\boldsymbol{\sigma}};S_{\boldsymbol{\sigma}})\geq\frac{p\|{\mathcal{X}}\|^{2}}{2d^{\prime}}\sum_{j=1}^{d^{\prime}}{(\bar{w_{j}}-w^{\boldsymbol{\sigma}}_{j})^{2}}.$
(10)

We will now show lower bounds on the per-coordinate error. Consider any
$\boldsymbol{\sigma}$ and $\boldsymbol{\sigma}^{\prime}$ which differ only at
index $j$ for some $j\in[d^{\prime}]$. Note that the datasets
$S_{\boldsymbol{\sigma}}$ and $S_{\boldsymbol{\sigma}^{\prime}}$ differ in
$\Delta=\frac{pn}{2d^{\prime}}[(1+b)-(1-b)]=\frac{pbn}{d^{\prime}}$ points.
Let
$\tau=w_{j}^{\boldsymbol{\sigma}}=\frac{\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}$
and
$\tau^{\prime}=w_{j}^{\boldsymbol{\sigma}^{\prime}}=-\frac{\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}$
(i.e. the $j$ components of the empirical minimizers for $S$ and
$S^{\prime}_{j}$ respectively). Note that
$|w_{j}^{\boldsymbol{\sigma}}-w_{j}^{\boldsymbol{\sigma}^{\prime}}|=\frac{2\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}$.
We thus have by Lemma 1 that for a certain
$b=b(\epsilon,n,d,B,p,\|{\mathcal{Y}}\|)$, ${\mathcal{A}}$ must satisfy

$\underset{}{\mathbb{E}}\left[|{\mathcal{A}}(S_{\boldsymbol{\sigma}})_{j}-w_{j}^{\boldsymbol{\sigma}}|+|{\mathcal{A}}(S_{\boldsymbol{\sigma}^{\prime}})_{j}-w_{j}^{\boldsymbol{\sigma}^{\prime}}|\right]\geq\frac{1}{4}\frac{\|{\mathcal{Y}}\|b}{\|{\mathcal{X}}\|}.$
(11)

Since we need $\Delta\leq\frac{1}{\epsilon}$, we must set
$b\leq\frac{d^{\prime}}{pn\epsilon}$. Furthermore, if we are interested in
problems with minimizer norm at most $B$, we need
$b\leq\frac{\|{\mathcal{X}}\|B}{\|{\mathcal{Y}}\|\sqrt{d^{\prime}}}$ to ensure
the norm of the minimizer is bounded by $B$. Balancing these two restrictions,
we set
$d^{\prime}=\big{(}\frac{p\|{\mathcal{X}}\|Bn\epsilon}{\|{\mathcal{Y}}\|}\big{)}^{2/3}$
which yields
$b=\big{(}\frac{\|{\mathcal{X}}\|B}{\|{\mathcal{Y}}\|\sqrt{pn\epsilon}}\big{)}^{2/3}.$
Assuming such settings of $b$ and $d^{\prime}$ are possible (e.g. $b\in[0,1]$)
we can apply Jensen’s inequality and the fact that $(a+b)^{2}\leq
2(a^{2}+b^{2})$ to Eqn. (11) to obtain

$\displaystyle\underset{}{\mathbb{E}}\left[|{\mathcal{A}}(S_{\boldsymbol{\sigma}})_{j}-w_{j}^{\boldsymbol{\sigma}}|^{2}+|{\mathcal{A}}(S_{\boldsymbol{\sigma}^{\prime}})_{j}-w_{j}^{\boldsymbol{\sigma}^{\prime}}|^{2}\right]\geq\frac{B^{4/3}\|{\mathcal{Y}}\|^{2/3}}{32(\|{\mathcal{X}}\|pn\epsilon)^{2/3}}.$

We will now show this implies there exists a
$\boldsymbol{\sigma}\in\left\\{{\pm 1}\right\\}^{d^{\prime}}$ such that
$F({\mathcal{A}}(S_{\boldsymbol{\sigma}}))-F(w^{\boldsymbol{\sigma}})=\Omega(\frac{(\|{\mathcal{X}}\|B)^{4/3}\|{\mathcal{Y}}\|^{2/3}p^{1/3}}{(n\epsilon)^{2/3}})$.
To prove this, we have the following analysis. Let $U=\left\\{{\pm
1}\right\\}^{d^{\prime}}$ and let $\boldsymbol{\sigma}_{-j}$ denote the vector
$\boldsymbol{\sigma}$ with its $j$’th component negated. We have

$\displaystyle\sup_{\boldsymbol{\sigma}\in
U}\left\\{{\underset{}{\mathbb{E}}\left[F({\mathcal{A}}(S_{\boldsymbol{\sigma}}))-F(w^{\boldsymbol{\sigma}})\right]}\right\\}$
$\displaystyle\geq\frac{1}{|U|}\sum_{\boldsymbol{\sigma}\in
U}\underset{}{\mathbb{E}}\left[F({\mathcal{A}}(S_{\boldsymbol{\sigma}}))-F(w^{\boldsymbol{\sigma}})\right]$
$\displaystyle=\frac{p\|{\mathcal{X}}\|^{2}}{d^{\prime}|U|}\sum_{j\in[d^{\prime}]}\sum_{\boldsymbol{\sigma}\in
U}\underset{}{\mathbb{E}}\left[|{\mathcal{A}}(S_{\boldsymbol{\sigma}})_{j}-w_{j}^{\boldsymbol{\sigma}}|^{2}\right]$
$\displaystyle=\frac{p\|{\mathcal{X}}\|^{2}}{d^{\prime}|U|}\sum_{j\in[d^{\prime}]}\sum_{\boldsymbol{\sigma}\in
U:\boldsymbol{\sigma}_{j}=1}\mathbb{E}\big{[}|{\mathcal{A}}(S_{\boldsymbol{\sigma}})_{j}-w_{j}^{\boldsymbol{\sigma}}|^{2}+|{\mathcal{A}}(S_{\boldsymbol{\sigma}_{-j}})_{j}-w_{j}^{\boldsymbol{\sigma}_{-j}}|^{2}\big{]}$
$\displaystyle\geq\frac{(\|{\mathcal{X}}\|B)^{4/3}\|{\mathcal{Y}}\|^{2/3}p^{1/3}}{128(n\epsilon)^{2/3}}.$

We recall this bound holds providing the settings of $d^{\prime}$ and $b$ fall
into the range $[1,\min\left\\{{n,d}\right\\}]$ and $[0,1]$ respectively.
First note $b>0$ always. Furthermore, $d^{\prime}<\min\left\\{{n,d}\right\\}$
and $b<1$ whenever

$\frac{\|{\mathcal{X}}\|^{2}B^{2}}{\|{\mathcal{Y}}\|^{2}n\epsilon}\leq
p\leq\min\left\\{{1,\frac{d^{3/2}\|{\mathcal{Y}}\|}{\|{\mathcal{X}}\|Bn\epsilon}}\right\\}.$
(12)

In the following, assume
$B\leq\frac{\|{\mathcal{Y}}\|\min\left\\{{\sqrt{n\epsilon},\sqrt{d}}\right\\}}{\|{\mathcal{X}}\|}$.
Note this is no loss of generality as we can obtain problem instances with
arbitrarily large $B$ by adding a dummy point with
$x=c^{\prime}e_{d^{\prime}+1}$ and $y=\|{\mathcal{Y}}\|$ where $c^{\prime}$ is
arbitrarily small so that the minimizer norm is $B$. Under this assumption on
$B$, using the restrictions on $p$, it can be verified that $d^{\prime}>1$
whenever $\epsilon>\frac{1}{n}$. Thus we have $b\in[0,1]$ and
$d^{\prime}\in[1,\min\left\\{{n,d}\right\\}]$ as required. Furthermore this
assumption on $B$ implies
$\frac{\|{\mathcal{X}}\|^{2}B^{2}}{\|{\mathcal{Y}}\|^{2}n\epsilon}\leq\min\left\\{{1,\frac{d^{3/2}\|{\mathcal{Y}}\|}{\|{\mathcal{X}}\|Bn\epsilon}}\right\\}$
and thus a valid setting of $p$ is possible. We now turn to setting $p$ in a
way which satisfies (12). We consider two cases, the high and low dimensional
regimes.
Case 1:
$d\geq\left({\frac{B\|{\mathcal{X}}\|n\epsilon}{\|{\mathcal{Y}}\|}}\right)^{2/3}$.
Setting $p=1$ gives a lower bound of
$\Omega\left({\min\left\\{{\|{\mathcal{Y}}\|^{2},\frac{B^{4/3}\|{\mathcal{X}}\|^{4/3}\|{\mathcal{Y}}\|^{2/3}}{32(n\epsilon)^{2/3}}}\right\\}}\right)$,
where the min with $\|{\mathcal{Y}}\|^{2}$ from the upper bound on $B$.
Case 2:
$d\leq\left({\frac{B\|{\mathcal{X}}\|n\epsilon}{\|{\mathcal{Y}}\|}}\right)^{2/3}.$
Setting $p=\frac{d^{3/2}\|{\mathcal{Y}}\|}{B\|{\mathcal{X}}\|n\epsilon}$ we
obtain a bound of
$\Omega\left({\min\left\\{{\|{\mathcal{Y}}\|^{2},\frac{\sqrt{d}B\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|}{n\epsilon}}\right\\}}\right)$
which we note is no larger than the bound from Case 1 in the low dimensional
regime and no smaller than the bound from Case 1 in the high dimensional
regime. Thus we can write the total bound as the minimum of these two bounds.
The $\|{\mathcal{Y}}\|^{2}$ term again comes from the restriction on $B$.

To obtain results for arbitrary $H$, we can set
$F(w;S)=\frac{H}{2n}\sum_{(x,y)\in
S}(\left\langle{w},{x}\right\rangle-\frac{2}{\sqrt{H}}y)^{2}$. This satisfies
$H$-smoothness and loss bounded at zero by $\|{\mathcal{Y}}\|^{2}$. Then
substituting $\|{\mathcal{Y}}\|$ in the previous expressions for
$2\|{\mathcal{Y}}\|/\sqrt{H}$ and multiplying through by $H/2$ one obtains the
claimed bound. ∎

##  Appendix B Missing Proofs from Section 4 (Lipschitz GLMs)

###  B.1 Proof of Theorem 5

###### Proof.

Note that from a standard analysis [4], we get that $\ell_{2}$ sensitivity of
the regularized minimizer $\widetilde{w}$ is
$\left({\frac{2G\|{\mathcal{X}}\|}{n\lambda}}\right)$, hence
$\sigma^{2}=\frac{4G^{2}\|{\mathcal{X}}\|^{2}\operatorname{log}\left(1/\delta\right)}{\lambda^{2}n^{2}\epsilon^{2}}$
ensures $(\epsilon,\delta)$-DP.

For the utility analysis, the excess risk can be decomposed as follows,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]$
$\displaystyle=\mathbb{E}[L(\widetilde{w};{\mathcal{D}})-\widehat{L}(\widetilde{w};S)]+\mathbb{E}[\widehat{L}(\widetilde{w};S)-\widehat{L}(w^{*};S)]+\mathbb{E}[L(\widetilde{w}+\xi;{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]$

The first term is bounded as
$O\left({\frac{BG\|{\mathcal{X}}\|}{\sqrt{n}}}\right)$ from Rademacher
complexity results on bounded linear predictors [24].

The second term is simply bounded by
$\frac{\lambda}{2}\left\|{\widetilde{w}}\right\|^{2}\leq\frac{\lambda}{2}B^{2}$
since $\widetilde{w}$ is the regularized ERM. The third term is bounded via
the following

$\displaystyle\mathbb{E}[L(\widetilde{w}+\xi;{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]$
$\displaystyle=\mathbb{E}\left[\phi_{y}\left({\left\langle{\widetilde{w}+\xi},{x}\right\rangle}\right)-\phi_{y}\left({\left\langle{\widetilde{w}},{x}\right\rangle}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[G|\left\langle{\xi},{x}\right\rangle|\right]$
$\displaystyle\leq
G\sigma\left\|{{\mathcal{X}}}\right\|\leq\frac{4G^{2}\|{\mathcal{X}}\|^{2}\sqrt{\operatorname{log}\left(1/\delta\right)}}{\lambda
n\epsilon}$

where the last inequality follows since $\mathbb{E}\xi=0$ and
$\left\langle{\xi},{x}\right\rangle\sim{\mathcal{N}}(0,\sigma^{2}\left\|{x}\right\|^{2})$.
Now plugging in
$\lambda=\frac{G\|{\mathcal{X}}\|\left({\operatorname{log}\left(1/\delta\right)}\right)^{1/4}}{B\sqrt{n\epsilon}}$
obtains the following result

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})]$
$\displaystyle=O\left({\frac{BG\|{\mathcal{X}}\|}{\sqrt{n}}+\frac{BG\|{\mathcal{X}}\|\operatorname{log}\left(1/\delta\right)^{1/4}}{\sqrt{n\epsilon}}}\right).$

∎

###  B.2 Upper Bound using JL Method

######  Theorem 10.

Let
$k=O\left({\operatorname{log}\left(2n/\delta\right)n\epsilon}\right),\sigma^{2}=\frac{8TG^{2}\left\|{{\mathcal{X}}}\right\|^{2}\operatorname{log}\left(2/\delta\right)}{n^{2}\epsilon^{2}},\eta=\frac{B}{G\|{\mathcal{X}}\|\left({1+\frac{\sqrt{k\operatorname{log}\left(2/\delta\right)}}{n\epsilon}}\right)T^{3/4}}$
and $T=n^{2}$. Algorithm 2 satisfies $(\epsilon,\delta)$-differential privacy.
Given a dataset $S$ of $n$ i.i.d samples, the excess risk of its output
$\widetilde{w}$ is bounded as

$\displaystyle\mathbb{E}[\varepsilon_{\mathsf{risk}}(\widehat{w})]=\widetilde{O}\left({\frac{GB\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}+\frac{GB\|{\mathcal{X}}\|}{\sqrt{n\epsilon}}}\right).$

###### Proof.

Let $\alpha\leq 1$ be a parameter to be set later. From the JL property, with
$k=O\left({\frac{\operatorname{log}\left(2n/\delta\right)}{\alpha^{2}}}\right)$,
with probability at least $1-\frac{\delta}{2}$, for feature vectors have
$\left\|{\Phi
x_{i}}\right\|\leq\left({1+\alpha}\right)\left\|{x_{i}}\right\|\leq
2\left\|{{\mathcal{X}}}\right\|$, and $\left\|{\Phi w^{*}}\right\|^{2}\leq
2\left\|{w^{*}}\right\|^{2}\leq 2B^{2}$. Thus, gradient of loss for data point
$(x,y)$ in $S$ at any $w$ is bounded as $\left\|{\ell(w;(\Phi
x,y)}\right\|=\phi_{y}^{\prime}(\left\langle{w},{\Phi
x}\right\rangle)\left\|{\Phi x}\right\|\leq 2G\left\|{{\mathcal{X}}}\right\|$.
The privacy guarantee thus follows from the privacy of DP-SCO and post-
processing.

For the utility guarantee, we decompose excess risk as:

$\displaystyle\mathbb{E}\left[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})\right]$
$\displaystyle=\mathbb{E}\left[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi S)\right]+\mathbb{E}\left[L(\Phi w^{*};\Phi
S)-L(w^{*};{\mathcal{D}})\right].$ (13)

The first term in Eqn. (13) is bounded by the utility guarantee of the DP-SCO
method. In particular, from Lemma 8 (below), we have

$\displaystyle\mathbb{E}\left[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi
S)\right]\leq\frac{GB\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}+O\left({\frac{G\left\|{{\mathcal{X}}}\right\|B\sqrt{k}}{n\epsilon}}\right).$

For the second term in Eqn (13), we use JL-property and Lipschitzness of GLM:

$\displaystyle\mathbb{E}\left[L(\Phi w^{*};\Phi
S)-L(w^{*};{\mathcal{D}})\right]$ $\displaystyle\leq
G\mathbb{E}\left[\left|{\left\langle{\Phi x},{\Phi
w^{*}}\right\rangle-\left\langle{x},{w^{*}}\right\rangle}\right|\right]$
$\displaystyle\leq\alpha
G\left\|{{\mathcal{X}}}\right\|\left\|{w^{*}}\right\|$
$\displaystyle=O\left({\frac{G\left\|{{\mathcal{X}}}\right\|B\sqrt{\operatorname{log}\left(2n/\delta\right)}}{\sqrt{k}}}\right).$

Combining, we get,

$\displaystyle\mathbb{E}\left[L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})\right]\leq\widetilde{O}\left({\frac{G\left\|{{\mathcal{X}}}\right\|B}{\sqrt{n}}+\frac{G\left\|{{\mathcal{X}}}\right\|B\sqrt{k}}{n\epsilon}+\frac{G\left\|{{\mathcal{X}}}\right\|B}{\sqrt{k}}}\right).$

Balancing parameters by setting $k=\widetilde{O}(n\epsilon)$ gives the claimed
bound. ∎

######  Lemma 8.

Let $\Phi\in{\mathbb{R}}^{d\times k}$ be a data-oblivious JL matrix. Let
$S=\left\\{{\left({x_{i},y_{i}}\right)}\right\\}_{i=1}^{n}$ of $n$ i.i.d data
points and let $\Phi S:=\left\\{{(\Phi x_{i},y_{i})}\right\\}_{i=1}^{n}$. Let
$\widetilde{w}\in{\mathbb{R}}^{k}$ be the average iterate returned noisy SGD
procedure with Gaussian noise variance
$\sigma^{2}=O\left({\frac{G^{2}\left\|{{\mathcal{X}}}\right\|^{2}\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}}\right)$
on dataset $\Phi S$. For
$k=\Omega\left({\operatorname{log}\left(n\right)}\right)$, the excess risk of
$\widetilde{w}$ on $\Phi{\mathcal{D}}$ is bounded as,

$\displaystyle\mathbb{E}_{\Phi,S}[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})]\leq
O\left({\frac{GB\|{\mathcal{X}}\|}{\sqrt{n}}+\frac{GB\|{\mathcal{X}}\|\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}}\right).$
(14)

###### Proof.

The proof uses the analysis for excess risk bound for Noisy SGD in [5] with
the JL transform. Let $S^{(i)}$ be the dataset where the $i$-th data point is
replaced by an i.i.d. point $(x^{\prime},y^{\prime})$ and let
$\widetilde{w}^{(i)}$ be the corresponding output of Noisy-SGD on $\Phi
S^{(i)}$. Define $\overline{S}:=\left\\{{S,(x^{\prime},y^{\prime})}\right\\}$
and let $G(\Phi,\overline{S})$ denote an upper bound Lipschitzness parameter
of the family of loss functions $\left\\{{\ell(w;(\Phi
x;y))}\right\\}_{(x,y)\in\overline{S}}$.

We decompose the excess risk as:

$\displaystyle\mathbb{E}_{\Phi,S}[L(\widetilde{w};\Phi{\mathcal{D}})-L(\Phi
w^{*};\Phi{\mathcal{D}})]=\mathbb{E}_{\Phi,S}[L(\Phi^{\top}\widetilde{w};{\mathcal{D}})-\widehat{L}(\Phi^{\top}\widetilde{w};S)]+\mathbb{E}_{\Phi,S}[\widehat{L}(\Phi^{\top}\widetilde{w};S)]-\widehat{L}(\Phi
w^{*};\Phi S)].$

A well-known fact (see [24]) is that generalization gap is equal to on-
average-stability:

$\displaystyle\mathbb{E}_{\Phi,S}[L(\Phi^{\top}\widetilde{w};{\mathcal{D}})-\widehat{L}(\Phi^{\top}\widetilde{w};S)]$
$\displaystyle=\mathbb{E}_{\overline{S},\Phi}[\ell(\Phi^{\top}\widetilde{w}^{(i)};(x_{i},y_{i}))-\ell(\Phi^{\top}\widetilde{w};(x_{i},y_{i}))]$
$\displaystyle=\mathbb{E}_{\overline{S},\Phi}[\ell(\widetilde{w}^{(i)};(\Phi
x_{i},y_{i}))-\ell(\widetilde{w};(\Phi x_{i},y_{i}))].$

From the analysis in Theorem 3.3 from [5], it follows that

$\displaystyle\ell(\widetilde{w}^{(i)};(\Phi
x_{i},y_{i}))-\ell(\widetilde{w};(\Phi x_{i},y_{i}))\leq
G(\Phi;\overline{S})\left\|{\widetilde{w}^{(i)}-\widetilde{w}}\right\|\leq
O\left({G(\Phi;\overline{S})^{2}\left({\eta\sqrt{T}+\frac{\eta
T}{n}}\right)}\right).$ (15)

where the last equality follows from the GLM structure of the loss function.

From analysis of Noisy-SGD [9], the other term (excess empirical risk) can be
bounded as

$\displaystyle\widehat{L}(\widetilde{w};\Phi S)]-\widehat{L}(\Phi w^{*};\Phi
S)\leq
O\left({\eta\left({G(\Phi;\overline{S})^{2}+\frac{kG(\Phi;\overline{S})^{2}\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}}\right)+\frac{\left\|{\Phi
w^{*}}\right\|^{2}}{T\eta}}\right)$ (16)

We now take expectation with respect to $\Phi$. Note that
$G(\Phi,\overline{S})=\sup_{(x,y)\in\overline{S}}\sup_{w}\left|{g_{x}(\left\langle{w},{\Phi
x}\right\rangle)}\right|\left\|{\Phi x}\right\|$, where $g_{x}$ is the an
element of the sub-differential of $\phi_{x}$ at
$\left\langle{w},{x}\right\rangle$. By the Lipschitzness assumption
$\left|{g_{x}(\left\langle{w},{\Phi x}\right\rangle)}\right|\leq G$ and from
the JL property, with probability at least $1-\delta$,
$\sup_{(x,y)\in\overline{S}}\left\|{\Phi
x}\right\|\leq\left({1+\frac{\sqrt{\operatorname{log}\left(n/\delta\right)}}{k}}\right)\left\|{{\mathcal{X}}}\right\|$.
Similarly,
$\left\|{\Phi^{\top}w^{*}}\right\|\leq\left({1+\frac{\sqrt{\operatorname{log}\left(n/\delta\right)}}{k}}\right)B$.
Observe that the tail is that of a (non-centered) sub-Gaussian random variable
with variance parameter $O\left({\frac{1}{k}}\right)$. Using the equivalence
of tail and moment bounds of sub-Gaussian random variables [8] and the fact
that $\frac{\operatorname{log}\left(n\right)}{k}\leq O(1)$, we get the
following bounds for Eqn. (15) and (16):

$\displaystyle\mathbb{E}_{\Phi}\left[\ell(\widetilde{w}^{(i)};(\Phi
x_{i},y_{i}))-\ell(\widetilde{w};(\Phi x_{i},y_{i})\right]\leq
O\left({G^{2}\left\|{{\mathcal{X}}}\right\|^{2}\left({\eta\sqrt{T}+\frac{\eta
T}{n}}\right)}\right)$

$\displaystyle\mathbb{E}_{\Phi}\left[\widehat{L}(\widetilde{w};\Phi
S)]-\widehat{L}(\Phi w^{*};\Phi
S)\right]\leq\widetilde{O}\left({\eta\left({G^{2}\left\|{{\mathcal{X}}}\right\|^{2}+\frac{kG^{2}\left\|{{\mathcal{X}}}\right\|^{2}\operatorname{log}\left(1/\delta\right)}{n^{2}\epsilon^{2}}}\right)+\frac{B^{2}}{T\eta}}\right).$

Finally, as in [5], taking expectation with respect $\overline{S}$ in the two
inequalities above, setting
$\eta=\frac{B}{G\|{\mathcal{X}}\|\left({1+\frac{\sqrt{k\operatorname{log}\left(1/\delta\right)}}{n\epsilon}}\right)T^{3/4}}$
and $T=n^{2}$ and combining gives the claimed bound. ∎

###  B.3 Proof of Theorem 6

The proof follows from the more general Theorem 11 stated below. Instantiating
Theorem 11 with $p=q=2$ satisfies all the requirements of our Theorem 6.
Finally, let $w^{*}$ be the population risk minimizer of the hard instance in
Theorem 11. We then have,

$\displaystyle\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-\min_{w}L(w;{\mathcal{D}})]$
$\displaystyle=\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-L(w^{*};{\mathcal{D}})]$
$\displaystyle\geq\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-\min_{w:\left\|{w}\right\|_{2}\leq
B}L(w;{\mathcal{D}})]$
$\displaystyle\geq\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(\widetilde{\mathrm{w}};{\mathcal{D}})]$
$\displaystyle=\Omega\left({GB\|{\mathcal{X}}\|\min\left({1,\frac{1}{\sqrt{n\epsilon}},\frac{\sqrt{\text{rank}}}{n\epsilon}}\right)}\right).$

This completes the proof.

###  B.4 Lower bound for Non-Euclidean DP-GLM

######  Theorem 11.

Let $G,\left\|{{\mathcal{Y}}}\right\|,\left\|{{\mathcal{X}}}\right\|,B>0$,
$\epsilon\leq 1.2,\delta\leq\epsilon$ and $p,q\geq 1$. For any
$(\epsilon,\delta)$-DP algorithm ${\mathcal{A}}$, there exists sets
${\mathcal{X}}$ and ${\mathcal{Y}}$ such that for any $x\in{\mathcal{X}}$,
$\left\|{x}\right\|_{q}\leq 1$, a distribution ${\mathcal{D}}$ over
${\mathcal{X}}\times{\mathcal{Y}}$, a $G$-Lipschitz GLM loss bounded at zero
by $\left\|{{\mathcal{Y}}}\right\|$ and a $\widetilde{w}$ with
$\left\|{\widetilde{w}}\right\|_{p}\leq B$ such that the output of
${\mathcal{A}}$ on $S\sim{\mathcal{D}}^{n}$ satisfies

$\displaystyle\mathbb{E}[L({\mathcal{A}}(S);{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]=\Omega\left({GB\|{\mathcal{X}}\|\min\left({1,\frac{1}{\left({n\epsilon}\right)^{1/p}},\frac{\left({\text{rank}}\right)^{(p-1)/p}}{n\epsilon}}\right)}\right).$

###### Proof.

The construction below is from [26] with some changes. We provide the complete
proof below. Consider the following $1$-Lipschitz loss function:

$\displaystyle\ell(w;(x,y))=\left|{y-\left\langle{w},{x}\right\rangle}\right|.$

Firstly, we argue that we can assume $\left\|{{\mathcal{Y}}}\right\|=\infty$.
This is because for any arbitrarily large value of $y$ we can translate the
above function below so that the the loss is bounded by
$\left\|{{\mathcal{Y}}}\right\|$. However, this translation doesn’t change the
excess risk. Also, as in [9], it suffices to consider $G=1$, since we can
simply scale the $1$-Lipschitz loss function and get a factor of the $G$ in
the lower bound. Let $d^{\prime}\leq\min\left({\text{rank},n\epsilon}\right)$,
$0\leq\alpha\leq 1$ and $\beta>0$ be parameters to be set later. Since
$d^{\prime}\leq\text{rank}$, without loss of generality, we will represent the
features $x$ as $d^{\prime}$ dimensional vectors.

Consider a distribution ${\mathcal{D}}$, where $x=e_{0}:=\vec{0}$ with
probability $1-\alpha$, and with probability $\alpha$,
$x\sim\operatorname{Unif}(\left\\{{\left\|{{\mathcal{X}}}\right\|e_{i}}\right\\}_{i=1}^{d^{\prime}})$.
Note that $\left\|{x}\right\|_{q}\leq\left\|{{\mathcal{X}}}\right\|$ and for
any $q\geq 1$ for $x\in\text{supp}({\mathcal{D}}_{x})$ where
${\mathcal{D}}_{x}$ denotes the marginal of ${\mathcal{D}}$ w.r.t. the $x$
variable. This implies the loss $w\mapsto\ell(w;(x,y))$ is
$\left\|{{\mathcal{X}}}\right\|$-Lipschitz in $\ell_{q}$-norm, when
$x\in\text{supp}({\mathcal{D}}_{x})$ and for all $y$. Let the fingerprinting
code $z\in\left\\{{0,1}\right\\}^{d^{\prime}}$ be drawn from a product
distribution with mean $\mu\in[0,1]^{d^{\prime}}$ where each co-ordinate
$\mu_{i}\sim\operatorname{Beta}(\beta,\beta)$. Finally we have
$y=\frac{B}{\left({d^{\prime}}\right)^{1/p}}\left\langle{x},{z}\right\rangle$.
Let $S=\left\\{{(x_{i},y_{i})}\right\\}_{i=1}^{n}$ be $n$ i.i.d. samples drawn
from ${\mathcal{D}}$. Define
$\widetilde{w}=\frac{B}{\left({d^{\prime}}\right)^{1/p}}\mu$; note that
$\left\|{\widetilde{w}}\right\|_{p}\leq B$.

Let ${\mathcal{A}}$ be any $(\epsilon,\delta)$-DP algorithm, which given $S$
outputs $\widehat{w}$. Its excess risk with respect to $\widetilde{w}$ can be
lower bounded as,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]$
$\displaystyle=\mathbb{E}[\left|{y-\left\langle{\widehat{w}},{x}\right\rangle}\right|-\left|{y-\left\langle{\widetilde{w}},{x}\right\rangle}\right|]$
$\displaystyle\geq\mathbb{E}[\left|{\left\langle{\widehat{w}-\widetilde{w}},{x}\right\rangle}\right|-2\left|{y-\left\langle{\widetilde{w}},{x}\right\rangle}\right|].$
(17)

The last term above is upper bounded as:

$\displaystyle\mathbb{E}[\left|{y-\left\langle{\widetilde{w}},{x}\right\rangle}\right|]=\frac{B}{\left({{}d^{\prime}}\right)^{1/p}}\mathbb{E}[\left|{\left\langle{z},{x}\right\rangle-\left\langle{\mu},{x}\right\rangle}\right|]=\frac{B\left\|{{\mathcal{X}}}\right\|}{\left({{d^{\prime}}}\right)^{1/p}}\frac{\alpha}{{d^{\prime}}}\sum_{i=1}^{d^{\prime}}\mathbb{E}\left|{z_{i}-\mu_{i}}\right|.$

By direct computation,

$\displaystyle\mathbb{E}\left|{z_{i}-\mu_{i}}\right|=\mathbb{E}\left[\left|{1-\mu_{i}}\right|\mu_{i}+\left|{-\mu_{i}}\right|\left({1-\mu_{i}}\right)\right]=2\mathbb{E}\mu_{i}\left({1-\mu_{i}}\right)=\frac{2\beta}{1+2\beta}.$

This gives us that

$\displaystyle\mathbb{E}[\left|{y-\left\langle{\widetilde{w}},{x}\right\rangle}\right|]\leq\frac{2\alpha\beta
B\left\|{{\mathcal{X}}}\right\|}{\left({1+2\beta}\right)\left({{d^{\prime}}}\right)^{(p+1)/p}}.$
(18)

The first term in the right hand side Inequality (17) is,

$\displaystyle\mathbb{E}[\left|{\left\langle{\widehat{w}-\widetilde{\mu}},{x}\right\rangle}\right|=\frac{B}{\left({{d^{\prime}}}\right)^{1/p}}\mathbb{E}\left|{\left\langle{\frac{\left({{d^{\prime}}}\right)^{1/p}}{B}\widehat{w}-\mu},{x}\right\rangle}\right|=\frac{B\left\|{{\mathcal{X}}}\right\|\alpha}{{\left({d^{\prime}}\right)^{(p+1)/p}}}\mathbb{E}\sum_{j=1}^{d^{\prime}}\left|{\frac{\left({{d^{\prime}}}\right)^{1/p}}{B}\widehat{w}_{j}-\mu_{j}}\right|.$
(19)

Define $v\in{\mathbb{R}}^{d^{\prime}}$ with
$v_{i}=\frac{{\left({d^{\prime}}\right)^{1/p}}\widehat{w}_{i}}{B}$. Note that,

$\displaystyle\sum_{j=1}^{d^{\prime}}\left|{\frac{{\left({d^{\prime}}\right)^{1/p}}}{B}\widehat{w}_{j}-\mu_{j}}\right|=\left\|{v-\mu}\right\|_{1}\geq\left\|{v-\mu}\right\|_{2}\geq\left\|{\widehat{v}-\mu}\right\|_{2}\geq\left\|{\widehat{v}-\mu}\right\|_{2}^{2}$

where the first inequality above follows from relationship between $\ell_{1}$
and $\ell_{2}$ norm, the second follows from projection property and
$\widehat{v}$ denotes the projection of $v$ onto $[0,1]^{d}$, and the last
inequality follows from boundedness of coordinates of $\widehat{v}-\mu$.

The key step now is application of the fingerprinting lemma (simplified below,
see Lemma B.1 in [26] for complete statement) from [27] which roughly
speaking, “relates the error to correlation”; for any
$\widehat{v}\in[0,1]^{d^{\prime}}$, we have

$\displaystyle\mathbb{E}\left\|{\widehat{v}-\mu}\right\|_{2}^{2}\geq\frac{{d^{\prime}}}{4\left({1+2\beta}\right)}-\frac{1}{\beta}\sum_{i=1}^{n}\mathbb{E}\left\langle{\widehat{v}},{z_{i}-\mu}\right\rangle.$
(20)

As in [26], the correlation simplifies as

$\displaystyle\mathbb{E}\left\langle{\widehat{v}},{z_{i}-\mu}\right\rangle$
$\displaystyle=\sum_{j=0}^{d^{\prime}}\mathbb{E}[\left\langle{\widehat{v}},{z_{i}-\mu}\right\rangle|x_{i}=e_{j}]\mathbb{P}[x_{i}=\|{\mathcal{X}}\|e_{j}]=\frac{\alpha}{{d^{\prime}}}\mathbb{E}[\widehat{v}_{j}\left({z_{i}-\mu}\right)_{j}|x_{i}=\|{\mathcal{X}}\|e_{j}]$

where the last equality follows since $\widehat{v}$ only depends on the
coordinate of $z_{i}$ for which $x_{i}=1$. Now, let $\widehat{v}^{\sim i}$
denotes the solution obtained if $z_{i}$ were replaced by an independent
sample. From boundedness,
$\left\|{\widehat{v}_{j}\left({z_{i}-\mu}\right)_{j}}\right\|_{\infty}\leq 1$.
Using differential privacy, we have,

$\displaystyle\mathbb{E}[\widehat{v}_{j}\left({z_{i}-\mu}\right)_{j}|x_{i}=\|{\mathcal{X}}\|e_{j}]\leq\left({e^{\epsilon}-1}\right)\mathbb{E}\left[\left|{\widehat{v}_{j}^{\sim
i}\left({z_{i}-\mu}\right)_{j}}\right||x_{i}=\|{\mathcal{X}}\|e_{j}\right]+\delta\leq\left({e^{\epsilon}-1}\right)+\delta\leq
3\epsilon$

where the last inequality uses the assumption that $\epsilon\leq 1.2$ and
$\delta\leq\epsilon$. Plugging this in Eqn. (20), we get

$\displaystyle\mathbb{E}\left\|{\widehat{v}-\mu}\right\|_{2}^{2}\geq\frac{{d^{\prime}}}{4\left({1+2\beta}\right)}-3\alpha
n\epsilon.$

Plugging the above in Eqn. (19), we get

$\displaystyle\mathbb{E}[\left|{\left\langle{\widehat{w}-\widetilde{w}},{x}\right\rangle}\right|\geq\frac{B\left\|{{\mathcal{X}}}\right\|\alpha}{{d^{\prime}}^{(p+1)/p}}\left({\frac{{d^{\prime}}}{4\left({1+2\beta}\right)}-3\alpha
n\epsilon}\right).$

Using the above, and the bound in Eqn. (17), we get that,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]$
$\displaystyle\geq\frac{B\left\|{{\mathcal{X}}}\right\|\alpha}{{d^{\prime}}^{(p+1)/p}}\left({\frac{{d^{\prime}}}{4\left({1+2\beta}\right)}-3\alpha
n\epsilon}\right)-\frac{2\alpha\beta
B\left\|{{\mathcal{X}}}\right\|}{\left({1+2\beta}\right)\left({{d^{\prime}}}\right)^{1/p}}$
$\displaystyle=\frac{B\left\|{{\mathcal{X}}}\right\|\alpha}{\left({1+2\beta}\right)\left({{d^{\prime}}}\right)^{1/p}}\left({\frac{1}{4}-\frac{3\alpha\left({1+2\beta}\right)n\epsilon}{{d^{\prime}}}-2\beta}\right).$

Now, we set $\beta=\frac{1}{16}$. When $\text{rank}\leq 48n\epsilon$ we set
$d^{\prime}=\text{rank}$ and
$\alpha=\min\left({\frac{{d^{\prime}}}{48\left({1+2\beta}\right)n\epsilon},1}\right)$.
The minimum term becomes
$\frac{{d^{\prime}}}{48\left({1+2\beta}\right)n\epsilon}$ and obtain an excess
risk lower bound of,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]\geq\frac{B\left\|{{\mathcal{X}}}\right\|\left({{d^{\prime}}}\right)^{(p-1)/p}}{1024n\epsilon}.$

On the other hand, when $\text{rank}>48n\epsilon$, set $\alpha=1$ and
${d^{\prime}}=\lfloor 48n\epsilon\rfloor$ (so that it is at least $1$) to get
an excess risk lower bound of,

$\displaystyle\mathbb{E}[L(\widehat{w};{\mathcal{D}})-L(\widetilde{w};{\mathcal{D}})]\geq\min\left({\frac{B\left\|{{\mathcal{X}}}\right\|}{16\left({n\epsilon}\right)^{1/p}},B\left\|{{\mathcal{X}}}\right\|}\right).$

Finally, note that we can arbitrarily increase the rank of the construction
beyond $48n\epsilon$ by adding datapoints with orthogonal feature vectors of
small enough magnitude and arbitrary labels. Combining the two lower bounds
obtains the claimed bound. ∎

######  Corollary 4.

Let $G,B>0$, $\epsilon\leq 1.2,\delta\leq\epsilon$ and $p,q\geq 1$. Let
${\mathcal{W}}\subset{\mathbb{R}}^{d}$ such that for any $w\in{\mathcal{W}}$,
$\left\|{w}\right\|_{p}\leq B$. For any $(\epsilon,\delta)$-DP algorithm
${\mathcal{A}}$, there exists a set ${\mathcal{Z}}$, a distribution
${\mathcal{D}}$ over ${\mathcal{Z}}$ and a loss function $w\mapsto\ell(w;z)$,
which is convex, $G$-Lipschitz w.r.t. $\ell_{q}$ norm for $w\in{\mathcal{W}}$,
for all $z\in{\mathcal{Z}}$ such that the output of ${\mathcal{A}}$ on
$S\sim{\mathcal{D}}^{n}$ (which may not lie in ${\mathcal{W}}$), satisfies

$\displaystyle\mathbb{E}_{{\mathcal{A}},S}[\mathbb{E}_{z\sim{\mathcal{D}}}\ell({\mathcal{A}}(S);z)-\min_{w\in{\mathcal{W}}}\mathbb{E}_{z\sim{\mathcal{D}}}\ell(w;z)]=\Omega\left({GB\min\left({1,\frac{1}{\left({n\epsilon}\right)^{1/p}},\frac{d^{(p-1)/p}}{n\epsilon}}\right)}\right).$

Using generalization properties of differential privacy, we get the same bound
as above for excess empirical risk; see Corollary B.4 in [26] for details.

##  Appendix C Missing Details for Section 5 (Adapting to
$\left\|{w^{*}}\right\|$)

###  C.1 Generalized Exponential Mechanism

######  Theorem 12.

[22] Let $K>0$ and $S\in{\mathcal{Z}}^{n}$. Let $q_{1},...,q_{K}$ be functions
s.t. for any adjacent datasets $S,S^{\prime}$ it holds that
$|q_{j}(S)-q_{j}(S^{\prime})|\leq\gamma_{j}:\forall j\in[K]$. There exists an
Algorithm, $\operatorname{GenExpMech}$, such that when given sensitivity-score
pairs $(\gamma_{1},q_{1}(S)),...,(\gamma_{N},q_{N}(S))$, privacy parameter
$\epsilon>0$ and confidence parameter $\beta>0$, outputs $j\in[N]$ such that
with probability at least $1-\beta$ satisfies
$q_{j}(S)\leq\min\limits_{j\in[N]}\left\\{{q_{j}(S)+\frac{4\gamma_{j}\operatorname{log}\left(N/\beta\right)}{\epsilon}}\right\\}$.

###  C.2 Proof of Theorem 7

Note that by assumptions on ${\mathcal{A}}$, the process of generating
$w_{1},...,w_{K}$ is $(\epsilon/2,\delta/2)-DP$. Furthermore, by Assumption 2
with probability at least $\delta/2$ the sensitivity values passed to
$\operatorname{GenExpMech}$ bound sensitivity. Thus by the privacy guarantees
of $\operatorname{GenExpMech}$ and composition we have that the entire
algorithm is $(\epsilon,\delta)$-DP.

We now prove accuracy. In order to do so, we first prove that with high
probability every $\widetilde{L}_{j}$ is an upper bound on the true population
loss of $w_{j}$. Specifically, define
$\tau_{j}=\frac{\Delta(B_{j})\operatorname{log}\left(4K/\beta\right)}{n}+\sqrt{\frac{4\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(4K/\beta\right)}{n}}$
(i.e. the term added to each $L(w_{j};S_{2})$ in Algorithm 4). Note it
suffices to prove

$\mathbb{P}\left[\exists
j\in[K]:|L(w_{j};S_{2})-L(w_{j};{\mathcal{D}})|\geq\tau_{j}\right]\leq\frac{\beta}{2}.$
(21)

Fix some $j\in[K]$. Note that the non-negativity of the loss implies that
$\ell(w_{B}^{*};(x,y)^{2})\geq 0$. The excess risk assumption then implies
that
$\underset{(x,y)\sim{\mathcal{D}}}{\mathbb{E}}\left[\ell(w_{j};(x,y))^{2}\right]\leq
4\|{\mathcal{Y}}\|^{2}$, which in turn bounds the variance. Further, with
probability at least $1-\frac{\beta}{4K}$ it holds that for all $(x,y)\in
S_{2}$ that $\ell(w,(x,y))\leq\Delta_{0}+\Delta(B)$. Thus by Bernstein’s
inequality we have

$\mathbb{P}\left[|L(w;S_{2})-L(w;{\mathcal{D}})|\geq
t\right]\leq\operatorname{exp}\left(-\frac{t^{2}n^{2}}{\Delta(B_{j})tn+4n\|{\mathcal{Y}}\|^{2}}\right)+\frac{\beta}{4K}$

Thus it suffices to set
$t=\frac{\Delta(B_{j})\operatorname{log}\left(4K/\beta\right)}{n}+\sqrt{\frac{4\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(4K/\beta\right)}{n}}$
to ensure $\mathbb{P}\left[|L(w;S_{2})-L(w;{\mathcal{D}})|\geq
t\right]\leq\frac{\beta}{2K}$. Taking a union bound over all $j\in K$
establishes (21). We now condition on this event for the rest of the proof.

Now consider the case where $j^{*}\neq 0$ and $\left\|{w^{*}}\right\|\leq
2^{K}$. Note that the unconstrained minimizer $w^{*}$ is the constrained
minimizer with respect to any ${\mathcal{B}}\left({r}\right)$ for
$r\geq\left\|{w^{*}}\right\|$. With this in mind, let
$j^{\prime}=\min\limits_{j\in[K]}\left\\{{j:w^{*}\in{\mathcal{B}}\left({2^{j}}\right)}\right\\}$
(i.e. the index of the smallest ball containing $w^{*}$). In the following we
condition on the event that $\forall j\in[K],j\geq j^{\prime}$, the parameter
vector $w_{j}$ satisfies excess population risk at most $\mathsf{ERR}(2^{j})$.
We note by Assumption 2 that this (in addition to the event given in (21))
happens with probability at least $1-\frac{3\beta}{4}$. By the guarantees of
$\operatorname{GenExpMech}$, with probability at least $1-\beta$ we
(additionally) have

$\displaystyle L(w_{j^{*}};{\mathcal{D}})\leq L(w_{j^{*}};S_{2})+\tau_{j^{*}}$
$\displaystyle\leq\min\limits_{j\in[K]}\left\\{{L(w_{j};S_{2})+\tau_{j}+\frac{4\Delta(B_{j})\operatorname{log}\left(4K/\beta\right)}{n\epsilon}}\right\\}$
$\displaystyle\leq
L(w_{j^{\prime}};S_{2})+\tau_{j^{\prime}}+\frac{4\Delta(B_{j^{\prime}})\operatorname{log}\left(4K/\beta\right)}{n\epsilon}$
$\displaystyle\leq
L(w_{j^{\prime}};{\mathcal{D}})+2\tau_{j^{\prime}}+\frac{4\Delta(B_{j^{\prime}})\operatorname{log}\left(4K/\beta\right)}{n\epsilon}.$

Since $2^{j^{\prime}}\leq\max\left\\{{2\left\|{w^{*}}\right\|,1}\right\\}$ we
have

$\displaystyle L(w_{j^{*}};{\mathcal{D}})-L(w^{*};{\mathcal{D}})$
$\displaystyle\leq
L(w_{j^{\prime}};{\mathcal{D}})-L(w^{*};{\mathcal{D}})+2\tau_{j^{\prime}}+\frac{4\Delta(B_{j^{\prime}})\operatorname{log}\left(4K/\beta\right)}{n\epsilon}$
$\displaystyle\leq\mathsf{ERR}(2\max\left\\{{\left\|{w^{*}}\right\|,1}\right\\})+2\tau_{j^{\prime}}+\frac{4\Delta(\max\left\\{{2\left\|{w^{*}}\right\|,1}\right\\})\operatorname{log}\left(4K/\beta\right)}{n\epsilon}$
$\displaystyle\leq\mathsf{ERR}(2\max\left\\{{\left\|{w^{*}}\right\|,1}\right\\})+\sqrt{\frac{4\|{\mathcal{Y}}\|^{2}\operatorname{log}\left(4K/\beta\right)}{n}}+\frac{5\Delta(\max\left\\{{2\left\|{w^{*}}\right\|,1}\right\\})\operatorname{log}\left(4K/\beta\right)}{n\epsilon}$

where the second inequality comes from the fact the assumption that
$\left\|{w^{*}}\right\|\leq\|{\mathcal{Y}}\|^{2}$. Now note that by the
assumption that $\mathsf{ERR}(2^{K})\geq\|{\mathcal{Y}}\|^{2}$, whenever
$\left\|{w^{*}}\right\|\geq 2^{K}$ it holds that
$\|{\mathcal{Y}}\|^{2}\leq\mathsf{ERR}(\left\|{w^{*}}\right\|)$. However since
the sensitivity-score pair $(0,\|{\mathcal{Y}}\|^{2})$ is passed to
$\operatorname{GenExpMech}$, the excess risk of the output is bounded by at
most $\|{\mathcal{Y}}\|^{2}$ by the guarantees of
$\operatorname{GenExpMech}$).

###  C.3 Proof of Theorem 8

Let $\widehat{w}$ denote the output of the regularized output perturbation
method with boosting and noise and privacy parameters
$\epsilon^{\prime}=\frac{\epsilon}{K}$ and $\delta^{\prime}=\frac{\delta}{K}$.
We have by Theorem 15 that with probability at least $1-\frac{\beta}{4K}$ that

$\displaystyle L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})$
$\displaystyle=\widetilde{O}\Bigg{(}\frac{\sqrt{H}B\left\|{{\mathcal{X}}}\right\|\left\|{{\mathcal{Y}}}\right\|+\left\|{{\mathcal{Y}}}\right\|^{2}}{\sqrt{n}}+\frac{\left({\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{4/3}\left\|{{\mathcal{Y}}}\right\|^{2/3}+\left({\sqrt{H}B\left\|{{\mathcal{X}}}\right\|}\right)^{2}}\right)}{(n\epsilon)^{2/3}}$
$\displaystyle+\frac{\left({\|{\mathcal{Y}}\|^{2}+HB^{2}\|{\mathcal{X}}\|^{2}}\right)}{n\epsilon}+\frac{\left({\|{\mathcal{Y}}\|+\sqrt{H}B\|{\mathcal{X}}\|}\right)}{\sqrt{n}}\Bigg{)}.$

Note that this is no smaller than $\|{\mathcal{Y}}\|^{2}$ when
$B=\Omega\left({\max\left\\{{\frac{\|{\mathcal{Y}}\|\sqrt{n\epsilon}}{\|{\mathcal{X}}\|\sqrt{H}},\frac{\|{\mathcal{Y}}\|^{2}(n\epsilon)^{2/3}}{\sqrt{H}\|{\mathcal{X}}\|^{2}}}\right\\}}\right)$,
and thus it suffices to set
$K=\Theta\left({\operatorname{log}\left(\max\left\\{{\frac{\|{\mathcal{Y}}\|\sqrt{n}}{\|{\mathcal{X}}\|\sqrt{H}},\frac{\|{\mathcal{Y}}\|^{2}(n\epsilon)^{2/3}}{\sqrt{H}\|{\mathcal{X}}\|^{2}}}\right\\}\right)}\right)$
to satisfy the condition of the Theorem statement.

Let $\sigma_{j}$ denote the level noise used for when the guess for
$\left\|{w^{*}}\right\|$ is $B_{j}$. To establish Assumption 2, by Lemma 10 we
have that this assumption is satisfies with
$\Delta(B)=\|{\mathcal{Y}}\|^{2}+H\|{\mathcal{X}}\|^{2}\sigma_{j}^{2}\operatorname{log}\left(K/\min\left\\{{\beta,\delta}\right\\}\right))+HB^{2}\|{\mathcal{X}}\|^{2}$.
In particular, we note for the setting of $\sigma_{j}$ implied by Theorem 15