# Differentially Private Optimization with Sparse Gradients

Badih Ghazi  Google Research  Cristóbal Guzmán  Google Research  Institute for
Mathematical and Computational Engineering, Faculty of Mathematics and School
of Engineering, Pontificia Universidad Católica de Chile  Pritish Kamath
Google Research  Ravi Kumar  Google Research  Pasin Manurangsi  Google
Research

###### Abstract

Motivated by applications of large embedding models, we study differentially
private (DP) optimization problems under sparsity of individual gradients. We
start with new near-optimal bounds for the classic mean estimation problem but
with sparse data, improving upon existing algorithms particularly for the
high-dimensional regime. Building on this, we obtain pure- and approximate-DP
algorithms with almost optimal rates for stochastic convex optimization with
sparse gradients; the former represents the first nearly dimension-independent
rates for this problem. Finally, we study the approximation of stationary
points for the empirical loss in approximate-DP optimization and obtain rates
that depend on sparsity instead of dimension, modulo polylogarithmic factors.

##  1 Introduction

The pervasiveness of personally sensitive data in machine learning
applications (e.g., advertising, public policy, and healthcare) has led to the
major concern of protecting users’ data from their exposure. When releasing or
deploying these trained models, differential privacy (DP) offers a rigorous
and quantifiable guarantee on the privacy exposure risk [19].

Consider neural network models whose inputs have categorical features with
large vocabularies. A typical way for dealing with such features is to use
embedding tables; namely, for a feature that takes $K$ distinct values, we
create trainable parameters $w_{1},\ldots,w_{K}\in\mathbb{R}^{k}$, and use
$w_{a}$ as input to the neural network when the corresponding input feature is
$a$. A natural outcome of considering such models is that the per-example
gradients are guaranteed to be sparse; when the input feature is $a$, then
only the gradient with respect to $w_{a}$ is non-zero. Given the prevalence of
sparse gradients in practical deep learning applications, GPUs/TPUs that are
optimized to leverage gradient sparsity are commercially offered and widely
used in industry [22, 38, 1, 25]. To leverage precisely this sparsity of
gradients, recent practical work has considered DP stochastic optimization
with sparse gradients for large embedding models for different applications
including recommendation systems, natural language processing, and ads
modeling [41, 21].

Despite its relevance and promising empirical results, there is limited
understanding of the theoretical limits of DP learning under gradient
sparsity. In this work, we propose a theoretical framework for studying this
problem, together with nearly tight bounds for various settings.

###  1.1 Our Results

We initiate the study of DP optimization under gradient sparsity. More
precisely, we consider a stochastic optimization (SO) problem,
$\min\\{F_{\mathcal{D}}(x):x\in{\mathcal{X}}\\}$, where
${\mathcal{X}}\subseteq\mathbb{R}^{d}$ is a convex set, and
$F_{\mathcal{D}}(x)=\mathbb{E}_{z\sim{\mathcal{D}}}[f(x,z)]$, with
$f(\cdot,z)$ enjoying some regularity properties, and ${\mathcal{D}}$ is a
probability measure supported on a set ${\mathcal{Z}}$. Our main assumption is
gradient sparsity: for an integer $0\leq s\leq d$,

$\forall x\in\mathcal{X},\,z\in\mathcal{Z}\ :\qquad\|\nabla f(x,z)\|_{0}\leq
s\,,$

where $\|y\|_{0}$ denotes the number of nonzero entries of $y$. We also study
empirical risk minimization (ERM), where given a dataset
$S=(z_{1},\ldots,z_{n})$ we aim to minimize
$F_{S}(x):=\frac{1}{n}\sum_{i\in[n]}f(x,z_{i})$.

Our results unearth three regimes of accuracy rates for the above setting: (i)
the small dataset size regime where the optimal rate is constant, (ii) the
large dataset size where the optimal rates are polynomial in the dimension and
(iii) an intermediate dataset size regime where a high-dimensional rate can be
obtained111We will generally refer to high-dimensional or nearly dimension-
independent rates indistinguishably, meaning more precisely that the rates
scale poly-logarithmically with the dimension. (this roughly corresponds to
the square root of the classical rate, where $d$ is replaced by $s\log d$; see
Table 1 and Table 2, for the precise rates). These results imply in particular
that even for high-dimensional models, this problem is tractable under
gradient sparsity. Interestingly, without sparsity, these poly-logarithmic
rates are unattainable in the light of known lower bounds [6].

Setting | Upper bound | Lower bound
---|---|---
$\varepsilon$-DP | $1\wedge\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sqrt{\frac{s\ln d}{\varepsilon n}}}$}\wedge\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{\sqrt{sd}}{\varepsilon n}}$}$ |  (Thm. 3.2) | $1\wedge\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sqrt{\frac{s\ln(d/(\varepsilon n))}{\varepsilon n}}}$}\wedge\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{\sqrt{sd}}{\varepsilon n}}$}$ |  (Thm. 4.1)
$(\varepsilon,\delta)$-DP | $1\wedge\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{(s\ln(d/s)\ln(1/\delta))^{1/4}}{\sqrt{\varepsilon n}}}$}\wedge\frac{\sqrt{d\ln(1/\delta)}}{\varepsilon n}$ |  (Thm. 3.4) | $1\wedge\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{(s\ln(1/\delta))^{1/4}}{\sqrt{\varepsilon n}}}$}\wedge\frac{\sqrt{d\ln(1/\delta)}}{\varepsilon n}$ |  (Thm. 4.5)
Table 1: Rates for DP mean estimation with sparse data of unit $\ell_{2}$-norm. Bounds stated for constant success/failure probability, resp. We use $a\wedge b$ to denote $\min(a,b)$. New results ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{highlighted}}$.  Setting | Guarantee |  New Upper bound (sparse) |  [1mm] Upper bound (non-sparse)
---|---|---|---
Convex $(\varepsilon,\delta)$-DP | ERM | ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{(s\ln(d)\ln(1/\delta))^{1/4}}{\sqrt{\varepsilon n}}}$ |  (Thm. 5.1) | $\frac{\sqrt{d\ln(1/\delta)}}{\varepsilon n}$
SCO | $\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{(s\ln(d)\ln(1/\delta))^{1/4}}{\sqrt{\varepsilon n}}}$}+\frac{1}{\sqrt{n}}$ |  (Thm. 5.6) | $\frac{\sqrt{d\ln(1/\delta)}}{\varepsilon n}+\frac{1}{\sqrt{n}}$
Convex $\varepsilon$-DP | ERM |  ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Big{(}\frac{s\ln(d)}{\varepsilon n}\Big{)}^{1/3}}$ (Thm. 5.1, 5.5) | $\frac{d}{\varepsilon n}$
SCO | $\hbox{\pagecolor{blue!5}${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Big{(}\frac{s\ln(d)}{\varepsilon n}\Big{)}^{1/3}}$}+\frac{1}{\sqrt{n}}$ |  (Thm. 5.6) | $\frac{d}{\varepsilon n}+\frac{1}{\sqrt{n}}$
Noncvx. $(\varepsilon,\delta)$-DP | Emp. Grad. Norm | ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{(s\ln(d/s)\ln^{3}(1/\delta))^{1/8}}{(\varepsilon n)^{1/4}}}$ |  (Thm. 6.8) | $\Big{(}\frac{\sqrt{d\ln(1/\delta)}}{\varepsilon n}\Big{)}^{2/3}$
Table 2: Rates for high-dimensional DP optimization with sparse gradients,
compared to best-existing upper bounds in the non-sparse case. Bounds stated
for constant success probability. Function parameters and polylog$(n)$ factors
omitted. Improvements
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{highlighted}}$.

In Section 3, we start with the fundamental task of $\ell_{2}$-mean estimation
of a dataset with sparse data (which reduces to ERM with sparse linear losses
[6]). Here, we obtain new upper bounds (see Table 1). These rates are obtained
by adapting the projection mechanism [31], with a convex relaxation that makes
our algorithms efficient. Note that for pure-DP, even our low-dimensional rate
of $\sqrt{sd}/(\varepsilon n)$ can be substantially smaller than the dense
pure-DP rate of $d/(\varepsilon n)$ [6], whenever $s\ll d$. For approximate-DP
we also obtain a sharper upper bound by solving an $\ell_{1}$-regression
problem of a noisy projection of the empirical mean over a random subspace.
Its analysis combines ideas from compressed sensing [40] with sparse
approximation via the Approximate Carathéodory Theorem [32].

In Section 4, we prove lower bounds that show the near-optimality of our
algorithms. For pure-DP, we obtain a new lower bound of
$\Omega(s\log(d/s)/(n\varepsilon))$, which is based on a packing of sparse
vectors. While this lower bound looks weaker than the standard
$\Omega(d/(n\varepsilon))$ lower bound based on dense packing [23, 6], we
design a novel bootstrapping via a block diagonal construction where each
block contains a sparse lower bound as above. This, together with a padding
argument [6], yields lower bounds for the three regimes of interest. For
approximate-DP, we also use the block diagonal bootstrapping, where this time
the blocks use classical fingerprinting codes in dimension $s$ [6, 34]. Our
lower bounds, however, have a gap of $\ln(d/s)^{1/4}$ in the high-dimensional
regime; we conjecture that the aforementioned compressed sensing-based upper
bound is tight.

In Section 5, we study DP-SO and DP-ERM in the convex case. For approximate-
DP, our upper bounds are obtained by regularized output perturbation with an
$\ell_{\infty}$ projection post-processing step. While this projection step is
rather unusual, its role is clear from the analysis: it leverages the
$\ell_{\infty}$ bounds of noise addition, which in conjunction with convexity
provides an error guarantee that also leverages the gradient sparsity. These
algorithms are nearly-optimal, by the aforementioned lower bounds. For pure-
DP, we provide two different algorithms: one based on regularized output
perturbation (which is efficient, but it requires an additional smoothness
assumption), and one based on the exponential mechanism [29] run over a net of
suitably sparse vectors (which is inefficient, but does not require
smoothness). Neither of these algorithms matches the lower bound for mean
estimation (the gap in the exponent of the rate is of $1/6$), but they attain
the first nearly dimension-independent rates for this problem. Finally, we
prove that our DP-ERM bounds transfer to DP-SO guarantees, by virtue of the
stability of regularized ERM.

In Section 6 we study the approximation of stationary points in DP-ERM. We
propose the use of stochastic gradient (SGD) with a mean estimation gradient
oracle based on the results in Section 3. The main challenge here is the
presence of bias in mean estimation, which dramatically deteriorates the rates
of SGD. In view of this, we propose a bias-reduction method inspired by the
simulation literature [9]. This bias-reduction technique uses a random batch
size in an exponentially increasing schedule and a telescopic estimator of the
gradient which—used in conjunction with our DP mean estimation
methods—provides a stochastic first-order oracle that attains bias similar to
the one of a full-batch algorithm, with moderately bounded variance. Note that
using the full-batch in this case would lead to polynomially weaker rates for
stationarity; in turn, our method leverages the batch randomization to conduct
a more careful privacy accounting based on subsampling and the fully-adaptive
properties of DP [39]. The resulting rate (see Table 1) is approximately the
square-root of the rate of noisy SGD in the dense setting where the dimension
is replaced by $s\ln(d/s)$, i.e., the desired high-dimensional rate. A plain
application of these ideas leads to only constant success probability results,
and hence in Section 7 we propose a private confidence boosting procedure to
exponentially amplify the success probability.

###  1.2 Related Work

DP optimization is an extensively studied topic for over a decade (see Bassily
et al. [6, 7], Feldman et al. [20], and the references therein). In this
field, some works have highlighted the role of feature sparsity (e.g., using
sparsity-promoting $\ell_{1}$-ball constraints) in near-dimension independent
excess-risk rates for DP optimization, both for ERM and SCO [24, 35, 36, 4, 8,
15, 14]. These settings are unrelated to ours, as sparse predictors are
typically related to dense gradients.

Another proposed assumption to mitigate the impact of dimension in DP learning
is that gradients lie in a small dimensional subspace [42, 26]. This is an
arguably strong assumption that is not easy to verify, and therefore requires
systematic empirical validation. Moreover, the determination of the subspace
where gradients need to be projected requires access to nontrivial amounts of
public data, which depending on the application may be restrictive.

Substantially less studied is the role of gradient sparsity. Closely related
to our work, Zhang et al. [41] studied DP-ERM under gradient sparsity, with
some stronger assumptions. Aside from an additional $\ell_{\infty}$ assumption
on the individual gradients, the following partitioning sparsity assumption is
imposed: the dataset $S$ can be uniformly partitioned into subsets
$S_{1},\ldots,S_{m}$, where each of these sets satisfies a uniform bound on
gradient sparsity: for all $k\in[m]$ and $x\in{\mathcal{X}}$,
$\big{\|}\sum_{z\in S_{k}}\nabla f(x,z)\big{\|}_{0}\leq c_{1}$. The work shows
poly-logarithmic in the dimension rates, for both convex and nonconvex
settings: for convex objectives the rate is $\frac{\mbox{\footnotesize
polylog}(d)}{\varepsilon\sqrt{n}}$, and in the nonconvex case is
$\frac{\mbox{\footnotesize polylog}(d)}{\sqrt{\varepsilon}n^{1/4}}$. Our
results only assume individual gradient sparsity, so on top of being more
general, they are also faster and provably nearly optimal in the convex case.

Another relevant work is Ghazi et al. [21], which studies the computational
and utility benefits for DP with sparse gradients in neural networks with
embedding tables. With the caveat that variable selection on stochastic
gradients is performed at the level of contributing buckets (i.e. rows of the
embedding table), rather than on gradient coordinates, this work shows
substantial improvements on computational efficiency (as the bucket selection
leads to a more efficient batch gradient computation) and also on the
resulting utility.

In Asi et al. [3], bias-reduction is used to mitigate the regularization bias
in SCO. While they also borrow inspiration from [9], both their techniques and
scope of their work are unrelated to ours.

###  1.3 Future Directions

Our work provides a number of structural results on DP optimization with
sparse gradients. We hope these results inspire further research in this area,
thus we highlight some open questions.

First, we conjecture that for approximate-DP mean estimation—similarly to the
pure-DP case—a lower bound
$\Omega\big{(}\sqrt{s\log(d/s)\ln(1/\delta)}/[n\varepsilon]\big{)}$ should
exist; such construction could be bootstrapped with a block-diagonal dataset
(more precisely, Lemma 4.3), proving the optimality of our algorithms. Second,
for pure-DP, we believe there should exist an algorithm attaining rates analog
to those for mean estimation. It appears however that most of the variants of
the output perturbation approach (including the use of phasing [20, 4, 5])
cannot attain such rates.

We believe that our bias-reduction approach may find further use in DP. For
example, [28, 30] have identified strong limitations from bias in mean
estimation. While similar lower bounds may hold for sparse estimation, bias-
reduction allows us to amortize this error within an iterative method,
preventing their error accumulation. Further exploring this phenomenon may
help circumventing the presence of bias for other settings in DP.

Finally, there is no evidence of our nonconvex rate being optimal. While it is
known that in the dense case noisy SGD is not optimal [2], known acceleration
approaches are based on variance reduction, which appears to be incompatible
with our bias-reduction.

##  2 Notation and Preliminaries

In this work, $\|\cdot\|=\|\cdot\|_{2}$ is the standard Euclidean norm on
$\mathbb{R}^{d}$. We will also make use of $\ell_{p}$-norms, where
$\|x\|_{p}:=\big{(}\sum_{j\in[d]}|x_{j}|^{p}\big{)}^{1/p}$ for $1\leq
p\leq\infty$. For $p=0$, we use the notation $\|x\|_{0}=|\\{j\in[d]:x_{j}\neq
0\\}|$, i.e., the cardinality of the support of $x$. We denote the $r$-radius
ball centered at $x$ of the $p$-norm in $\mathbb{R}^{d}$ by ${\cal
B}_{p}^{d}(x,r):=\\{y\in\mathbb{R}^{d}:\|y-x\|_{p}\leq r\\}$. Given $s\in[d]$
and $L>0$, the set of $s$-sparse vectors is (the scaling factor $L$ is omitted
in the notation for brevity)

${\cal S}_{s}^{d}:=\\{x\in\mathbb{R}^{d}:\,\|x\|_{0}\leq s,\,\|x\|_{2}\leq
L\\}.$ (1)

Note that Jensen’s inequality implies: if $\|x\|_{0}\leq s$ and $1\leq
p<q\leq\infty$, then $\|x\|_{p}\leq s^{1/p-1/q}\|x\|_{q}$.

######  Remark 2.1.

The upper bound results in this paper hold even if we replace the set ${\cal
S}_{s}^{d}$ of sparse vectors by the strictly larger $\ell_{1}$ ball ${\cal
B}_{1}^{d}(0,L\sqrt{s})$ (inclusion follows from the aforementioned
inequality). Note that while our upper bounds extend to the $\ell_{1}$
assumption above, our lower bounds work under the original sparsity
assumption.

Let $f:\mathcal{X}\times\mathcal{Z}\mapsto\mathbb{R}$ be a loss function. The
function evaluation $f(x,z)$ represents the loss incurred by hypothesis
$x\in\mathcal{X}$ on datapoint $z\in\mathcal{Z}$. In stochastic optimization
(SO), we consider a data distribution ${\cal D}$, and our goal is to minimize
the expected loss under this distribution

$\textstyle\min_{x\in\mathcal{X}}\Big{\\{}F_{\mathcal{D}}(x):=\mathbb{E}_{z\sim{\cal
D}}[f(x,z)]\Big{\\}}.$ (SO)

Throughout, we use $x^{\ast}({\cal D})$ to denote an optimal solution to (SO),
which we assume exists. We note in passing that existence of such optimal
solution is guaranteed when ${\cal X}$ is compact, but otherwise additional
work is needed to assert such existence; on the other hand, if multiple
optimal solutions exist, we can choose an arbitrary one (e.g., a minimal norm
solution). In the empirical risk minimization (ERM) problem, we consider
sample datapoints $S=(z_{1},\ldots,z_{n})$ and our goal is to minimize the
empirical error with respect to the sample

$\textstyle\min_{x\in\mathcal{X}}\Big{\\{}F_{S}(x):=\frac{1}{n}\sum_{i\in[n]}f(x,z_{i})\Big{\\}}.$
(ERM)

We denote by $x^{\ast}(S)$ an arbitrary optimal solution to (ERM), which we
assume exists. Even when $S$ is drawn i.i.d. from ${\cal D}$, solutions (or
optimal values) of (SO) and (ERM) do not necessarily coincide.

We present the definition of differential privacy (DP), deferring useful
properties and examples to Appendix A. Let $\mathcal{Z}$ be a sample space,
and $\mathcal{X}$ an output space. A dataset is a tuple $S\in\mathcal{Z}^{n}$,
and datasets $S,S^{\prime}\in\mathcal{Z}^{n}$ are _neighbors_ (denoted as
$S\simeq S^{\prime}$) if they differ in only one of their entries.

######  Definition 2.2 (Differential Privacy).

Let $\mathcal{A}:\mathcal{Z}^{n}\mapsto\mathcal{X}$. We say that $\mathcal{A}$
is _$(\varepsilon,\delta)$ -(approximately) differentially private (DP)_ if
for every pair $S\simeq S^{\prime}$, we have for all
$\mathcal{E}\subseteq\mathcal{X}$ that

$\Pr[\mathcal{A}(S)\in\mathcal{E}]~{}\leq~{}e^{\varepsilon}\cdot\Pr[\mathcal{A}(S^{\prime})\in\mathcal{E}]+\delta.$

When $\delta=0$, we say that $\mathcal{A}$ is $\varepsilon$-DP or pure-DP.

The privacy and accuracy of some of the perturbation based methods we use to
privatize our algorithms are based on the following simple facts (see e.g.
[19]).

######  Fact 2.3 (Laplace & Gaussian mechanisms).

For all $g:{\cal Z}^{n}\mapsto\mathbb{R}^{d}$

  1. (a)

If $\ell_{1}$-sensitivity of $g$ is bounded, i.e.,
$\Delta_{1}^{g}:=\sup_{S\simeq S^{\prime}}\|g(S)-g(S^{\prime})\|_{1}<+\infty$,
then ${\cal A}_{\mathsf{Lap}}^{g}(S):=g(S)+\xi$ where
$\xi\sim\mathsf{Lap}^{\otimes d}(\Delta_{1}^{g}/\varepsilon)$ is
$\varepsilon$-DP.

  2. (b)

If $\ell_{2}$-sensitivity of $g$ is bounded, i.e.,
$\Delta_{2}^{g}:=\sup_{S\simeq S^{\prime}}\|g(S)-g(S^{\prime})\|_{2}<+\infty$,
then ${\cal A}_{\mathcal{N}}^{g}(S):=g(S)+\xi$, where
$\xi\sim\mathcal{N}\big{(}0,\sigma^{2}I\big{)}$ for
$\sigma\geq\frac{\Delta_{2}^{g}\sqrt{2\log(1.25/\delta)}}{\varepsilon}$ is
$(\varepsilon,\delta)$-DP.

######  Fact 2.4 (Laplace & Gaussian concentration).

Let $\sigma>0$ and $0<\beta<1$.

  1. (a)

For $\xi\sim\mathsf{Lap}(\sigma)^{\otimes d}$: (i)
$\|\xi\|_{\infty}\lesssim\sigma\log(d/\beta)$ holds with probability
$1-\beta$, and (ii) $\|\xi\|_{2}\lesssim\sigma\sqrt{d}\log(d/\beta)$ holds
with probability $1-\beta$.

  2. (b)

For $\xi\sim\mathcal{N}(0,\sigma^{2}I)$, (i)
$\|\xi\|_{\infty}\lesssim\sigma\sqrt{\log(d/\beta)}$ holds with probability
$1-\beta$, (ii)
$\|\xi\|_{2}\lesssim\sigma\big{(}\sqrt{d}+\sqrt{\log(1/\beta)}\big{)}$ holds
with probability $1-\beta$, and (iii) $\mathbb{E}\|\xi\|_{2}^{2}=d\sigma^{2}$.

##  3 Upper Bounds for DP Mean Estimation with Sparse Data

In this section we study the problem of DP mean estimation with sparse data.
Our main result is that the projection mechanism [31] is nearly optimal, both
for pure- and approximate-DP. In our case, we interpret the marginals on each
of the $d$-dimensions as the queries of interest: this way, the
$\ell_{2}$-error on private query answers corresponds exactly to the
$\ell_{2}$-norm estimation error. A key difference to the approach in Nikolov
et al. [31] and related works is that we project the noisy answers onto the
set ${\cal K}:={\cal B}_{1}^{d}(0,L\sqrt{s})$, which is a (coarse) convex
relaxation of $\mathrm{conv}({\cal S}_{s}^{d})$. This is crucial to make our
algorithm efficiently implementable.

Algorithm 1 Projection_Mechanism$(\bar{z}(S),\varepsilon,\delta,n)$

algorithm]alg:proj

Vector $\bar{z}(S)=\frac{1}{n}\sum_{i=1}^{n}z_{i}$ from dataset $S\in({\cal
S}_{s}^{d})^{n}$; $\varepsilon,\delta\geq 0$, privacy parameters

$\tilde{z}=\bar{z}(S)+\xi$, with
$\xi\sim\begin{cases}\mathsf{Lap}(\sigma)^{\otimes d}&\text{with
}\sigma=\big{(}\frac{2L\sqrt{s}}{n\varepsilon}\big{)}\text{ if
}\delta=0\,,\\\\[2.84526pt] \mathcal{N}(0,\sigma^{2}I)&\text{with
}\sigma^{2}=\frac{8L^{2}\ln(1.25/\delta)}{(n\varepsilon)^{2}}\text{ if
}\delta>0\,.\\\ \end{cases}$

return $\hat{z}=\operatorname*{\mathrm{argmin}}\limits_{z\in{\cal
K}}\|z-\tilde{z}\|_{2}$, where ${\cal K}:={\cal B}_{1}^{d}(0,L\sqrt{s})$

######  Lemma 3.1.

In LABEL:alg:proj, it holds that
$\|\hat{z}-\bar{z}(S)\|_{2}\leq\sqrt{2L\|\xi\|_{\infty}\sqrt{s}}$, almost
surely.

###### Proof.

From the properties of the Euclidean projection, we have

$\displaystyle\langle\hat{z}-\bar{z}(S),\hat{z}-\tilde{z}\rangle\leq 0.$ (2)

Hence,

$\displaystyle\|\hat{z}-\bar{z}(S)\|_{2}^{2}$
$\displaystyle=\left<\hat{z}-\bar{z}(S),\hat{z}-\tilde{z}\right>+\left<\hat{z}-\bar{z}(S),\xi\right>~{}\overset{\eqref{eq:proj-
angle}}{\leq}~{}\left<\tilde{z}-z(S),\xi\right>$ $\displaystyle\leq
2\cdot\max_{u\in{\cal K}}\left<u,\xi\right>~{}\leq~{}2\cdot\max_{u\in{\cal
K}}\|u\|_{1}\cdot\|\xi\|_{\infty}~{}=~{}2L\|\xi\|_{\infty}\sqrt{s},$

where we used the fact that $\mbox{conv}({\cal S}_{s}^{d})\subseteq{\cal K}$.
∎

We now provide the privacy and accuracy guarantees of LABEL:alg:proj.

######  Theorem 3.2.

For $\delta=0$, LABEL:alg:proj is $\varepsilon$-DP, and with probability
$1-\beta$:

$\displaystyle\textstyle\|\hat{z}-\bar{z}(S)\|_{2}\lesssim
L\cdot\min\left\\{\frac{\sqrt{sd}\ln(d/\beta)}{n\varepsilon},\sqrt{\frac{s\ln(d/\beta)}{n\varepsilon}}\right\\}.$

###### Proof.

First, the privacy follows from the $\ell_{1}$-sensitivity bound of the
empirical mean

$\textstyle\Delta_{1}=\sup_{S\simeq
S^{\prime}}\|\bar{z}(S)-\bar{z}(S^{\prime})\|_{1}=\frac{1}{n}\sup_{z,z^{\prime}\in{\cal
S}_{s}^{d}}\|z-z^{\prime}\|_{1}\leq\frac{2L\sqrt{s}}{n},$

together with 2.3(a).

For the accuracy, the first term follows from 2.4(a)-(ii), and the fact that
Euclidean projection does not increase the $\ell_{2}$-estimation error, and
the second term follows from Lemma 3.1 with the fact that
$\|\xi\|_{\infty}\leq
O\left(\frac{L\sqrt{s}}{n\varepsilon}\cdot\log(d/\beta)\right)$ holds with
probability at least $1-\beta$, by 2.4(a)-(i). ∎

######  Theorem 3.3.

For $\delta>0$, LABEL:alg:proj is $(\varepsilon,\delta)$-DP, and with
probability $1-\beta$:

$\displaystyle\textstyle\|\hat{z}-\bar{z}(S)\|_{2}\lesssim
L\cdot\min\left\\{\frac{(\sqrt{d}+\sqrt{\log(1/\beta)})\sqrt{\ln(1/\delta)}}{n\varepsilon},\frac{(s\log(1/\delta)\log(d/\beta))^{1/4}}{\sqrt{n\varepsilon}}\right\\}.$

###### Proof.

The privacy guarantee follows from the $\ell_{2}$-sensitivity bound of the
empirical mean, $\Delta_{2}=\frac{2L}{n}$, together with 2.3(b). For the
accuracy, the first term in the minimum follows from 2.4(b)-(ii), and the fact
that Euclidean projection does not increase the $\ell_{2}$-estimation error.
The second term follows from Lemma 3.1 and 2.4(b)-(ii). ∎

###  3.1 Sharper Approximate DP Mean Estimation via Compressed Sensing

We propose a sharper algorithm for approximate-DP mean estimation based on
compressed sensing [40]. The precise improvements relate to reducing the
$\log(d)$ factor to $\log(d/s)$, and a faster rate dependence on the
confidence $\beta$. The idea is that for sufficiently high dimensions a small
number of random measurements suffices to estimate a noisy and approximately
sparse signal. These properties follow from existing results in compressed
sensing, which provide guarantees based on the $\ell_{2}$-norm of the noise,
and the best sparse approximation in the $\ell_{2}$-norm (known as
$\ell_{2}\text{-}\ell_{2}$-stable and noisy recovery) [40]. We will exploit
such robustness in two ways: regarding the noise robustness, this property is
used in order to perturb our measurements, which will certify the privacy; on
the other hand, the approximate recovery property is used to find a sparser
approximation of our empirical mean. As the approximation is only used for
analysis, we can resort on the Approximate Caratheodory Theorem to certify the
existence of a sparse vector whose sparsity increases more moderately with $n$
than the empirical average [32] .

An interesting feature of this algorithm is that $\ell_{1}$-minimization
promotes sparse solutions, and thus we expect our output to be approximately
sparse: this is not a feature that we particularly exploit, but it may be
relevant for computational and memory considerations. Furthermore, note that
the $\ell_{1}$-minimization problem does not require exact optimality for the
privacy guarantee, hence approximate solvers can be used without compromising
the privacy.

Algorithm 2 Gaussian $\ell_{1}$-Recovery$(\bar{z}(S),\varepsilon,\delta,n)$

Vector $\bar{z}(S)=\frac{1}{n}\sum_{i\in[n]}z_{i}\in\mathbb{R}^{d}$ from
dataset $S\in({\cal S}_{s,d})^{n}$; privacy parameters $\varepsilon,\delta>0$

$m\eqsim n\varepsilon\sqrt{\frac{s\ln(d/s)}{\ln(1/\delta)}}$

return $\hat{z}=\begin{cases}\bar{z}(S)+\xi\text{, where
}\xi\sim\mathcal{N}(0,\sigma^{2}I_{d\times d})\text{ and
}\sigma^{2}=\frac{8L^{2}\ln(1.25/\delta)}{(n\varepsilon)^{2}}\text{,}&\text{
if }d<m\ln^{2}m,\text{ else}\\\\[2.84526pt]
\tilde{z}\cdot\mathds{1}{\\{\|\tilde{z}\|\leq 2L\\}}\text{, where
}\tilde{z}=\arg\min\\{\|z\|_{1}:Az=b\\}\text{,
}A\sim(\mathcal{N}(0,\frac{1}{m}))^{m\times d},&\\\\[2.84526pt]
\phantom{\tilde{z}\cdot\mathds{1}{\\{\|\tilde{z}\|\leq
2L\\}}\text{,}}b=A\bar{z}(S)+\xi\text{ and
}\xi\sim\mathcal{N}(0,\sigma^{2}I_{m\times m})\text{ with
}\sigma^{2}=\frac{18L^{2}\ln(2.5/\delta)}{(n\varepsilon)^{2}}&\end{cases}$

######  Theorem 3.4.

Let $m\eqsim n\varepsilon\sqrt{s\ln(d/s)}/\sqrt{\ln(1/\delta)}$. If
$6\exp\\{-cm\\}\leq\delta<\frac{s\ln(d/s)}{m^{2}}$ (where $c>0$ is a constant)
and $0<\varepsilon\leq 1$, then Algorithm 2 is $(\varepsilon,\delta)$-DP, and
with probability $1-\delta/2-\beta$,

$\|\hat{z}-\bar{z}(S)\|_{2}\lesssim
L\min\Big{\\{}\frac{(\sqrt{d}+\sqrt{\ln(1/\beta)})\sqrt{\ln(1/\delta)}}{n\varepsilon},\frac{(s\ln(d/s)\ln(1/\delta))^{1/4}}{\sqrt{n\varepsilon}}+\frac{\sqrt{\ln(1/\beta)\ln(1/\delta)}}{n\varepsilon}\Big{\\}}.$
(3)

Moreover, we have the following second moment estimate,

$\mathbb{E}[\|\hat{z}-\bar{z}\|_{2}^{2}]\lesssim
L^{2}\min\Big{\\{}\frac{d\ln(1/\delta)}{(n\varepsilon)^{2}},\frac{\sqrt{s\ln(d/s)\ln(1/\delta)}}{n\varepsilon}\Big{\\}}.$

###### Proof.

First, if $d<m\ln^{2}m$, Algorithm 2 is $(\varepsilon,\delta)$-DP by privacy
of Gaussian noise addition and the post-processing property of DP. Moreover,
its (high-probability and second moment) accuracy guarantees are direct from
2.4.

Next, if $d\geq m\ln^{2}m$, we start with the privacy analysis. Let $S\simeq
S^{\prime}$ and suppose they only differ in their $i$-th entry. We note that
due to our choice of $m$, $A$ is an approximate restricted isometry with
probability $1-3\exp\\{-cm\\}$ [16] (where $c$ is the same as in the theorem
statement); in particular, letting
$K\eqsim\frac{n\varepsilon}{\sqrt{s\ln(d/s)\ln(1/\delta)}}$, we have that for
all $v\in\mathbb{R}^{d}$ which is $(sK)$-sparse

$\frac{1}{2}\|v\|_{2}\leq\|Av\|_{2}\leq\frac{3}{2}\|v\|_{2}.$

Hence, due to our assumption on $\delta$, the event above has probability at
least $1-\delta/2$, and therefore

$\|A(\bar{z}-\bar{z}^{\prime})\|_{2}=\frac{1}{n}\|A(z_{i}-z_{i}^{\prime})\|_{2}\leq\frac{3L}{n},$

where we used the fact that $z_{i}-z_{i}^{\prime}$ is $(2s)$-sparse. We
conclude by the choice of $\sigma^{2}$ that $A\bar{z}+\xi$ is
$(\varepsilon,\delta)$-DP, and thus $\tilde{z}$ is $(\varepsilon,\delta)$-DP
by postprocessing.

We now proceed to the accuracy guarantee. By Wojtaszczyk [40, Theorem 3.6
(b)], under the same event as stated above (which has probability
$1-\delta/2$) we have

$\|\hat{z}-\bar{z}\|_{2}\lesssim\|\xi\|_{2}+\inf_{z:\,\|z\|_{0}\leq
sK}\|z-\bar{z}\|_{2}.$

For the first term, we use Gaussian norm concentration to guarantee that with
probability $1-\beta$,

$\|\xi\|_{2}\lesssim\big{(}\sqrt{m}+\sqrt{\ln(1/\beta)}\big{)}\sigma\lesssim\Big{(}\sqrt{Ks\ln(d/s)}+\sqrt{\ln\big{(}\frac{1}{\beta}\big{)}}\Big{)}\frac{L\sqrt{\ln(1/\delta)}}{n\varepsilon}.$

For the second term, by the Approximate Carátheodory Theorem [32], the infimum
above is upper bounded by $O(L/\sqrt{K})$; for this, note that $\bar{z}$ lies
in the convex hull of ${\cal S}_{s}^{d}$. Given our choice of $K$, we have
that, with probability $1-\delta/2-\beta$

$\|\hat{z}-\bar{z}\|_{2}\lesssim
L\Big{(}\frac{[s\ln(d/s)\ln(1/\delta)]^{1/4}}{\sqrt{n\varepsilon}}+\frac{\sqrt{\ln(1/\beta)\ln(1/\delta)}}{n\varepsilon}\Big{)}.$

We conclude by providing the second moment estimate, by a simple tail
integration argument. First, by the law of total probability, and letting
${\cal E}$ be the event of $A$ being an approximate restricted isometry,

$\mathbb{E}\|\hat{z}-\bar{z}\|_{2}^{2}\leq\mathbb{E}[\|\hat{z}-\bar{z}\|_{2}^{2}|{\cal
E}]+9L^{2}\delta,$

where we also used that $\|\hat{z}\|_{2}\leq 2L$ and $\|\bar{z}\|_{2}\leq L$,
almost surely. Now, conditionally on ${\cal E}$, we have that letting
$\alpha\eqsim L\frac{[s\ln(d/s)\ln(1/\delta)]^{1/4}}{\sqrt{n\varepsilon}}$
(below $c>0$ is an absolute constant),

$\displaystyle\mathbb{E}[\|\hat{z}-\bar{z}\|_{2}^{2}|{\cal E}]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\Big{[}\|\hat{z}-\bar{z}\|_{2}\geq
u\Big{]}(2u)du$
$\displaystyle\leq\frac{\alpha^{2}}{2}+\int_{0}^{\infty}\mathbb{P}\Big{[}\|\hat{z}-\bar{z}\|_{2}-\alpha\geq\tau\Big{]}2(\alpha+\tau)d\tau$
$\displaystyle\leq\frac{\alpha^{2}}{2}+\int_{0}^{\infty}2\exp\Big{\\{}-\frac{c(n\varepsilon)^{2}}{L^{2}\ln(1/\delta)}\tau^{2}\Big{\\}}(\alpha+\tau)d\tau$
$\displaystyle\lesssim\frac{\alpha^{2}}{2}+2\alpha
L\frac{\sqrt{\ln(1/\delta)}}{n\varepsilon}+L^{2}\frac{\ln(1/\delta)}{(n\varepsilon)^{2}}$
$\displaystyle\lesssim\alpha^{2},$

where in the second inequality we used the previous high-probability upper
bound (here $c>0$ is an absolute constant), and in the last step we used that
$n\varepsilon>\sqrt{\ln(1/\delta)}$. Finally, by our assumptions on $\delta$,
$9L^{2}\delta\lesssim\alpha^{2}$, this concludes the proof. ∎

##  4 Lower Bounds for DP Mean Estimation with Sparse Data

We provide matching lower bounds to the upper bounds obtained in the previous
section. Note that although the lower bounds we state are for mean estimation,
known reductions imply analogous lower bounds for DP-ERM and DP-SCO [6, 7].
First, for pure-DP we provide a new packing-type construction based on sparse
vectors. This construction is used later in a block-diagonal form, which
provides the right low/high-dimensional transition. On the other hand, for
approximate-DP, a block diagonal reduction with existing fingerprinting codes
[12, 34], suffices to obtain lower bounds that exhibit a nearly tight
low/high-dimensional transition. For simplicity, we consider the case of
$L=1$, i.e. ${\cal S}_{s}^{d}=\\{z\in\mathbb{R}^{d}:\,\|z\|_{0}\leq
s,\|z\|_{2}\leq 1\\}$; it is easy to see that any lower bound scales linearly
in $L$.

###  4.1 Lower Bounds for Pure-DP

Our main lower bound for pure-DP mechanisms is as follows.

######  Theorem 4.1.

Let $\varepsilon>0$ and $s<d/2$. Then the empirical mean estimation problem
over ${\cal S}_{s}^{d}$ satisfies

$\textstyle\inf\limits_{\mathcal{A}\,:\,\varepsilon\mbox{-\footnotesize DP}}\
\sup\limits_{S\in({\cal
S}_{s}^{d})^{n}}\mathbb{P}\left[\|\mathcal{A}(S)-\bar{z}(S)\|_{2}~{}\gtrsim\min\Big{\\{}1,\sqrt{\frac{s\log\left(d/[\varepsilon
n]\right)}{\varepsilon n}},\frac{\sqrt{sd}}{\varepsilon
n}\Big{\\}}\right]\gtrsim 1.$

The statement above—as well as those which follow—should be read as “for all
DP algorithms ${\cal A}$, there exists a dataset $S$, such that the mean
estimation error is lower bounded by $\alpha(n,d,\varepsilon,\delta)$ with
probability at least $\beta(n,d,\varepsilon,\delta)$” (where in this case
$\alpha\gtrsim\min\Big{\\{}1,\sqrt{\frac{s\log\left(d/[\varepsilon
n]\right)}{\varepsilon n}},\frac{\sqrt{sd}}{\varepsilon n}\Big{\\}}$ and
$\beta\gtrsim 1$).

We also introduce a strengthening of the worst-case lower bound, based on hard
distributions.

######  Definition 4.2.

Given a sample space ${\cal Z}$, we say that a probability $\mu$ over ${\cal
Z}^{n}$ induces an $(\alpha,\beta)$-distributional lower bound for
$(\varepsilon,\delta)$-DP mean estimation if

$\inf_{{\cal A}:\,(\varepsilon,\delta)\text{-DP}}\mathbb{P}_{S\sim\mu,{\cal
A}}\Big{[}\|{\cal A}(S)-\bar{z}(S)\|_{2}\geq\alpha\Big{]}\geq\beta.$

Note this type of lower bound readily implies the previously stated worst-case
lower bounds known in DP. On the other hand, while the existence of hard
distributions follow by the existence of hard datasets (by Yao’s minimax
principle), we have chosen to provide explicit constructions of these
distributions, just for the sake of clarity. For the pure case, in Lemma A.3
we show that an adaptation of known packing-type lower bounds [23] provides
distributional lower bounds for mean estimation, and for the approximate case,
we note that fingerprinting distributions induce distributional lower bounds,
e.g. [13, 15, 27].

Theorem 4.1 follows by combining the two results that we provide next. First,
and our main technical innovation in the sparse case is a block-diagonal
dataset bootstrapping construction, which turns a low-dimensional lower bound
into a high-dimensional one. While we state this result for norm-bounded
sparse data, any family where low-dimensional instances can be embedded into
the high-dimensional ones by padding with zeros would enjoy a similar
property.

######  Lemma 4.3 (Block-Diagonal Lower Bound Bootstrapping).

Let $n_{0},t\in\mathbb{N}$ and $\alpha_{0}>0$. Let
${\mathcal{P}}\subseteq{\cal S}_{s}^{t}$, for which there exists a
distribution $\mu$ over ${\cal P}^{n_{0}}$ that induces an
$(\alpha_{0},\rho_{0})$-distributional lower bound for
$(\varepsilon,\delta)$-DP mean estimation. Then, for any $d\geq t$, $n\geq
n_{0}$ and $K\leq\min\big{\\{}\frac{n}{n_{0}},\frac{d}{t}\big{\\}}$, there
exists a distribution $\tilde{\mu}$ over $({\cal S}_{s}^{d})^{n}$ that induces
a $(\alpha,\rho)$-distributional lower bound for $(\varepsilon,\delta)$-DP
mean estimation, where
$\alpha\gtrsim\frac{\alpha_{0}n_{0}}{n}\sqrt{\rho_{0}K}$ and $\rho\geq
1-\exp(-\rho_{0}/8)$.

###### Proof.

Consider an $n\times d$ data matrix $D$ whose rows correspond to datapoints of
a dataset $S$, and whose columns correspond to their $d$ features. We will
indistinctively refer to $S$ or $D$ as needed (these are equivalent
representations of a dataset). This data matrix will be comprised of $K$
diagonal blocks, $D_{1},\ldots,D_{K}$; in particular, outside of these blocks,
the matrix has only zeros. These blocks are sampled i.i.d. from the hard
distribution $\mu$ given by hypothesis. Denote $\tilde{\mu}$ the law of $D$.
Let now $\bar{z}_{k}(D_{k})\in\mathbb{R}^{t}$ be the mean (over rows) of
dataset $D_{k}$. Then, the mean (over rows) of dataset $D$ is given by

$\bar{z}(D)=\frac{n_{0}}{n}\big{[}\bar{z}_{1}(D_{1})\big{|}\ldots\big{|}\bar{z}_{K}(D_{K})\big{]},$

where $[z_{1}|\ldots|z_{K}]\in\mathbb{R}^{d}$ denotes the concatenation of
$z_{1},\ldots,z_{K}$ (note that if $K<d/t$, then the concatenation above needs
to be padded with $(d-tK)$-zeros, which we omit for simplicity).
Let ${\cal A}$ be an $(\varepsilon,\delta)$-DP algorithm, and let ${\cal
A}_{k}$ its output on the $k$-th block variables, then

$\|{\cal A}(D)-\bar{z}(D)\|_{2}^{2}=\sum_{k=1}^{K}\Big{\|}{\cal
A}_{k}(D)-\frac{n_{0}}{n}\bar{z}_{k}(D_{k})\Big{\|}_{2}^{2}=\frac{n_{0}^{2}}{n^{2}}\sum_{k=1}^{K}\big{\|}\frac{n}{n_{0}}{\cal
A}_{k}(D)-\bar{z}_{k}(D_{k})\Big{\|}_{2}^{2}.$

Let now ${\cal B}_{k}(D):=\frac{n}{n_{0}}{\cal A}_{k}(D)$, and note it is
$(\varepsilon,\delta)$-DP w.r.t. $D_{k}$ (as it is DP w.r.t. $D$); further, by
the independence of $D_{1},\ldots,D_{K}$, we can condition on $(D_{h})_{h\neq
k}$, to conclude that the squared $\ell_{2}$-error $\|{\cal
B}_{k}(D)-\bar{z}_{k}(D_{k})\|_{2}^{2}$ must be at least $\alpha_{0}^{2}$,
with probability at least $\rho_{0}$ (both on $D_{k}$ and the internal
randomness of ${\cal B}_{k}$). Letting $Y_{k}:=\mathbf{1}_{\\{\|{\cal
B}_{k}(D)-\bar{z}_{k}(D_{k})\|_{2}\geq\alpha_{0}\\}}$, we have

$\displaystyle\mathbb{P}\Big{[}\|{\cal
A}(D)-\bar{z}(D)\|_{2}^{2}\geq\big{(}\frac{\alpha_{0}n_{0}}{n}\big{)}^{2}\frac{\rho
K}{2}\Big{]}$
$\displaystyle\geq\mathbb{P}\Big{[}\sum_{k=1}^{K}Y_{k}\geq\frac{\rho
K}{2}\Big{]}.$

We will now use a coupling argument to lower bound the probability above.
First, we let $U_{1},\ldots,U_{K}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mbox{Unif}([0,1])$, and
$W_{k}=\mathbf{1}_{\\{U_{i}\geq\rho_{0}\\}}$ which are i.i.d.. On the other
hand, we define

$\displaystyle p_{k}(y_{1},\ldots,y_{k-1})$
$\displaystyle:=\mathbb{P}[Y_{k}=1|Y_{1}=y_{1},\ldots,Y_{k-1}=y_{k-1}]$
$\displaystyle\tilde{Y}_{k}$ $\displaystyle:=\mathbf{1}_{\\{U_{k}\geq
p_{k}(\tilde{Y}_{1},\ldots,\tilde{Y}_{k-1})\\}}.$

Noting that $Y\stackrel{{\scriptstyle d}}{{=}}\tilde{Y}$, and that
$\tilde{Y}_{k}\geq W_{k}$ almost surely, due to the fact that
$p_{k}\geq\rho_{0}$ almost surely (which it follows from the $\ell_{2}$-error
argument discussed above), we have

$\mathbb{P}\Big{[}\sum_{k=1}^{K}Y_{k}\geq\frac{\rho
K}{2}\Big{]}=\mathbb{P}\Big{[}\sum_{k=1}^{K}\tilde{Y}_{k}\geq\frac{\rho
K}{2}\Big{]}\geq\mathbb{P}\Big{[}\sum_{k=1}^{K}W_{k}\geq\frac{\rho
K}{2}\Big{]}\geq 1-\exp(-\rho_{0}/8),$

where we used the one-sided multiplicative Chernoff bound.
Therefore, $\|{\cal
A}(D)-\bar{z}(D)\|_{2}^{2}\gtrsim\Big{(}\frac{\alpha_{0}n_{0}}{n}\Big{)}^{2}\rho
K$, with probability $1-\exp(-\rho_{0}/8)$. We conclude that $\tilde{\mu}$
induces a $(\alpha,\rho)$-distributional lower bound for $\varepsilon$-DP mean
estimation, as claimed. ∎

The above result needs as input a base lower bound. We note that in the sparse
setting, there are packing-based constructions that provide such a base lower
bound.

######  Theorem 4.4.

Let $\varepsilon>0$ and $s<d/2$. Then there exists $\mu$ supported on $({\cal
S}_{s}^{d})^{n}$ that induces an $(\alpha,\rho)$-distributional lower bound
for $\varepsilon$-DP mean estimation with
$\alpha\gtrsim\min\left\\{1,\frac{s\log(d/s)}{\varepsilon n}\right\\}$ and
$\rho=1/2$.

###### Proof.

By Lemma A.1, there exists a set ${\cal P}$ of $1/\sqrt{2}$-packing vectors on
${\cal C}_{s}^{d}$ with $\log(|{\cal P}|)\gtrsim s\log(d/s)$. Lemma A.3 thus
implies the desired lower bound. ∎

With all the building blocks in place, we now prove Theorem 4.1.

###### Proof of Theorem 4.1.

We divide the analysis into the different regimes of sample size $n$. First,
if $n\lesssim\frac{s\log(d/s)}{\varepsilon}$, then Theorem 4.4 provides an
$\Omega(1)$ lower bound.

Next we consider the case $\frac{s\log(d/s)}{\varepsilon}\lesssim
n\lesssim\frac{d}{\varepsilon}$. For $s\leq t\leq d$ to be determined, let
$n_{0}=\frac{s\log(t/s)}{\varepsilon}$. We choose $t$ so that
$\frac{d}{t}\eqsim\frac{n}{n_{0}}$: this can be attained by choosing
$t\eqsim\frac{ds}{\varepsilon n}\log\big{(}\frac{d}{\varepsilon n}\big{)}$.
This implies in the context of Lemma 4.3 that
$K=\frac{d}{t}\eqsim\frac{n}{n_{0}}$. By Theorem 4.4, this implies a lower
bound $\alpha_{0}\gtrsim 1$, with constant probability $1/2$ for sparse mean
estimation in dimension $t$. By Lemma 4.3, we conclude a sparse mean
estimation lower bound of
$\frac{\alpha_{0}n_{0}}{n}\sqrt{\frac{K}{2}}\gtrsim\frac{1}{\sqrt{K}}\gtrsim\sqrt{\frac{s\log(d/n\varepsilon)}{\varepsilon
n}}$ holds with constant probability.

On the other hand, if $n\gtrsim\frac{d}{\varepsilon}$, let
$n^{*}\eqsim\frac{d}{\varepsilon}$. By the previous paragraph, for datasets of
size $n^{*}$ the following lower bound holds,
$\Omega\Big{(}\sqrt{\frac{s\log(d/\varepsilon n^{*})}{\varepsilon
n^{*}}}\Big{)}\gtrsim\sqrt{\frac{s}{d}}$. For any $n>n^{*}$, by Lemma A.2, we
have the lower bound
$\Omega\Big{(}\sqrt{\frac{s}{d}}\frac{n^{*}}{n}\Big{)}\gtrsim\frac{\sqrt{sd}}{\varepsilon
n}$ holds with constant probability. ∎

###  4.2 Lower Bounds for Approximate-DP

While the lower bound for the approximate-DP case is similarly based on the
block-diagonal reduction, its base lower bound follows more directly from the
dense case.

######  Theorem 4.5.

Let $\varepsilon\in(0,1]$, $2^{-o(n)}\leq\delta\leq\frac{1}{n^{1+\Omega(1)}}$.
Then the empirical mean estimation problem over ${\cal S}_{s}^{d}$ satisfies

$\textstyle\inf\limits_{\mathcal{A}\,:\,(\varepsilon,\delta)\mbox{\text{\footnotesize-
DP}}}\sup\limits_{S\in({\cal
S}_{s}^{d})^{n}}\mathbb{P}\left[\|{\mathcal{A}}(S)-\bar{z}(S)\|_{2}\gtrsim\min\Big{\\{}1,\frac{[s\ln(1/\delta)]^{1/4}}{\sqrt{n\varepsilon}},\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon}\Big{\\}}\right]\gtrsim
1.$

###### Proof.

We divide the analysis into the different regimes of sample size $n$. First,
if $n\lesssim\sqrt{s\ln(1/\delta)}/\varepsilon$, then embedding an
$s$-dimensional lower bound construction [13]222While [13] only provides
1-dimensional distributional lower bounds for approximate DP mean estimation,
it is easy to convert these into higher dimensional lower bounds, see e.g.
[15, 27]. and padding it with zeros for the remaining $d-s$ features, provides
an $\Omega(1)$ lower bound with constant probability.

Next, we consider the case $\sqrt{s\ln(1/\delta)}/\varepsilon\lesssim
n\lesssim\frac{d\sqrt{\ln(1/\delta)}}{\sqrt{s}\varepsilon}$. Let
$n_{0}=\sqrt{s\ln(1/\delta)}/\varepsilon$, $t=s$, and
$K=\frac{n}{n_{0}}\lesssim\frac{d}{s}$, where the last inequality holds by our
regime assumption. The classical $s$-dimensional mean estimation lower bound
by [13] provides a $\alpha_{0}\gtrsim 1$ lower bound with constant
probability. Hence by Lemma 4.3, the sparse mean estimation problem satisfies
a lower bound
$\Omega\big{(}\frac{\alpha_{0}n_{0}}{n}\sqrt{K}\big{)}\gtrsim\frac{1}{\sqrt{K}}\gtrsim\frac{[s\ln(1/\delta)]^{1/4}}{\sqrt{\varepsilon
n}}$, with constant probability.

We conclude with the final range,
$n\gtrsim\frac{d\sqrt{\ln(1/\delta)}}{\sqrt{s}\varepsilon}$. First, letting
$n^{\ast}\eqsim\frac{d\sqrt{\ln(1/\delta)}}{\sqrt{s}\varepsilon}$, we note
that this sample size falls within the range of the previous analysis, which
implies a lower bound with constant probability of
$\frac{[s\ln(1/\delta)]^{1/4}}{\varepsilon\sqrt{n^{\ast}}}\gtrsim\frac{\sqrt{s}}{\sqrt{d}}$.
Now, if $n>n^{\ast}$, by Lemma A.2, we conclude that the following lower bound
holds with constant probability,
$\Omega\Big{(}\frac{\sqrt{s}}{\sqrt{d}}\frac{n^{\ast}}{n}\Big{)}\gtrsim\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon}$.
∎

##  5 DP Convex Optimization with Sparse Gradients

We now start with our study of DP convex optimization with sparse gradients.
In this section and later, we will impose subsets of the following
assumptions:

  1. (A.1)

Initial distance: For SCO, $\|x^{0}-x^{\ast}({\cal D})\|\leq D$; for ERM,
$\|x^{0}-x^{\ast}(S)\|\leq D$.

  2. (A.2)

Diameter bound: $\|x-y\|\leq D$, for all $x,y\in\mathcal{X}$.

  3. (A.3)

Convexity: $f(\cdot,z)$ is convex, for all $z\in\mathcal{Z}$.

  4. (A.4)

Loss range: $f(x,z)-f(y,z)\leq B$, for all $x,y\in\mathcal{X}$,
$z\in\mathcal{Z}$.

  5. (A.5)

Lipschitzness: $f(\cdot,z)$ is $L$-Lipschitz, for all $z\in\mathcal{Z}$.

  6. (A.6)

Smoothness: $\nabla f(\cdot,z)$ is $H$-Lipschitz, for all $z\in\mathcal{Z}$.

  7. (A.7)

Individual gradient sparsity: $\nabla f(x,z)$ is $s$-sparse, for all
$x\in\mathcal{X}$ and $z\in\mathcal{Z}$.

Our first DP optimization algorithm is a modification of the well-known output
perturbation method. The modification corresponds to a projection step that
minimizes the _$\ell_{\infty}$_ -distance after noise addition, instead of the
$\ell_{2}$-distance. The full description is included in LABEL:alg:output-
pert-inf.

Algorithm 3 Output_Perturbation

algorithm]alg:output-pert-inf

Dataset $S=(z_{1},\dots,z_{n})\in{\mathcal{Z}}^{n}$, $\varepsilon,\delta\geq
0$ privacy params., $f(\cdot,z)$ $L$-Lipschitz convex function (if $\delta=0$
further assume $H$-smooth) with $s$-sparse gradient, $\lambda\geq 0$
regularization param.

Let
$x_{\lambda}^{\ast}(S)=\operatorname*{\mathrm{argmin}}_{x\in\mathcal{X}}F^{\lambda}_{S}(x)$,
where
$F^{\lambda}_{S}(x):=\big{[}F_{S}(x)+\frac{\lambda}{2}\|x\|_{2}^{2}\big{]}$

$\tilde{x}=x_{\lambda}^{\ast}(S)+\xi$, with
$\xi\sim\begin{cases}\mathsf{Lap}(\sigma)^{\otimes d}&\text{with
}\sigma=\frac{2\sqrt{2s}L}{\lambda\varepsilon
n}\big{(}\frac{2H}{\lambda}+1\big{)}\text{ if }\delta=0\,,\\\\[2.84526pt]
{\mathcal{N}}(0,\sigma^{2}I)&\text{with
}\sigma^{2}=\frac{8L^{2}\ln(1.25/\delta)}{[\lambda\varepsilon n]^{2}}\text{ if
}\delta>0\,.\\\ \end{cases}$

return
$\hat{x}=\operatorname*{\mathrm{argmin}}_{x\in\mathcal{X}}\|x-\tilde{x}\|_{\infty}$
(breaking ties arbitrarily)

######  Theorem 5.1.

Consider an ERM problem under assumptions: initial distance (Item (A.1)),
convexity (Item (A.3)), Lipchitzness (Item (A.5)) and gradient sparsity (Item
(A.7)). Then, LABEL:alg:output-pert-inf is $(\varepsilon,\delta)$-DP, and it
satisfies the following excess risk guarantees, for any $0<\beta<1$:

  * •

If $\delta=0$, and under the additional assumption of smoothness (A.6) and
unconstrained domain, ${\mathcal{X}}=\mathbb{R}^{d}$, then selecting
$\lambda=\Big{(}\frac{L^{2}H}{D^{2}}\frac{s\log(d/\beta)}{\varepsilon
n}\Big{)}^{1/3}$, it holds with probability $1-\beta$ that

$\textstyle F_{S}(\hat{x})-F_{S}(x^{\ast}(S))\lesssim
L^{2/3}H^{1/3}D^{4/3}\Big{(}\frac{s\log(d/\beta)}{\varepsilon
n}\Big{)}^{1/3}.$

  * •

If $\delta>0$ then selecting
$\lambda=\frac{L}{D}\cdot\frac{[s\log(1/\delta)\log(d/\beta)]^{1/4}}{\sqrt{\varepsilon
n}}$, we have with probability $1-\beta$ that

$\displaystyle F_{S}(\hat{x})-F_{S}(x^{\ast}(S))\lesssim
LD\cdot\frac{(s\log(1/\delta)\log(d/\beta))^{1/4}}{\sqrt{\varepsilon n}}.$

######  Remark 5.2.

For the case $\delta>0$, the theorem above can also be proved if we replace
the initial distance assumption (Item (A.1)) by the diameter assumption (Item
(A.2)).

###### Proof.

We proceed by cases:

  * •

Case $\delta=0$. First, we prove that privacy of the algorithm. To do this, we
first establish a bound on the $\ell_{1}$-sensitivity of the (quadratically)
regularized ERM. Note that the first-order optimality conditions in this case
correspond to

$x_{\lambda}^{\ast}(S)=-\frac{1}{\lambda}\nabla F_{S}(x_{\lambda}^{\ast}(S)).$

Therefore, if $S\simeq S^{\prime}$, where $S=(z_{1},\ldots,z_{n})$ and
$S=(z_{1}^{\prime},\ldots,z_{n}^{\prime})$ only differ in one entry,

$\displaystyle\|x_{\lambda}^{\ast}(S)-x_{\lambda}^{\ast}(S^{\prime})\|_{1}$
$\displaystyle\leq\frac{1}{\lambda}\|\nabla
F_{S}(x_{\lambda}^{\ast}(S))-\nabla
F_{S^{\prime}}(x_{\lambda}^{\ast}(S^{\prime}))\|_{1}$
$\displaystyle\leq\frac{1}{\lambda n}\sum_{i=1}^{n}\|\nabla
f(x_{\lambda}^{\ast}(S),z_{i})-\nabla
f(x_{\lambda}^{\ast}(S^{\prime}),z_{i}^{\prime})\|_{1}$
$\displaystyle\leq\frac{1}{\lambda
n}\Big{[}(n-1)\sqrt{2s}H\|x_{\lambda}^{\ast}(S)-x_{\lambda}^{\ast}(S^{\prime})\|_{2}+2\sqrt{2s}L\Big{]}$
$\displaystyle\leq\frac{1}{\lambda n}\Big{(}4\sqrt{2s}HL\frac{n-1}{\lambda
n}+2\sqrt{2s}L\Big{)}$ $\displaystyle\leq\frac{2\sqrt{2s}L}{\lambda
n}\big{(}\frac{2H}{\lambda}+1\big{)}.$

Above, in the third inequality we used the gradient sparsity (A.7), and the
smoothness (A.6), assumptions. In the fourth inequality we used that the
regularized ERM has $\ell_{2}$-sensitivity $\frac{4L}{\lambda n}$ [10, 33,
18]. We conclude the privacy then by 2.3(a).

We also remark that by 2.4(a)-(i),
$\|\xi\|_{\infty}\lesssim\frac{L\sqrt{s}\ln(d/\beta)}{\lambda
n\varepsilon}\Big{(}\frac{H}{\lambda}+1\Big{)}$, with probability $1-\beta$.

  * •

Case $\delta>0$. The privacy guarantee follows from the fact that the
$\ell_{2}$-sensitivity of $x_{\lambda}^{\ast}(S)$ is $\frac{4L}{\lambda n}$
[10, 33, 18], together with 2.3(b).

Moreover, by 2.4(b)-(i),
$\|\xi\|_{\infty}\lesssim\frac{L\sqrt{\ln(d/\beta)}}{\lambda n\varepsilon}$,
with probability $1-\beta$.

We continue with the accuracy analysis, making a unified presentation for both
pure and approximate DP. First, by the optimality conditions of the
regularized ERM,

$F_{S}(x_{\lambda}^{\ast}(S))-F_{S}(x^{\ast}(S))\leq\frac{\lambda}{2}\|x^{\ast}(S)\|^{2}\leq\frac{\lambda}{2}D^{2}.$
(4)

We need the following key fact, which follows by the definitions of $\hat{x}$
and $\tilde{x}$,

$\|\hat{x}-x_{\lambda}^{\ast}(S)\|_{\infty}\leq\|\hat{x}-\tilde{x}\|_{\infty}+\|\tilde{x}-x_{\lambda}^{\ast}(S)\|_{\infty}\leq
2\|\xi\|_{\infty}.$ (5)

Using these two bounds, we proceed as follows

$\displaystyle F_{S}(\hat{x})-F_{S}(x^{\ast}(S))$ $\displaystyle\leq
F_{S}(\hat{x})-F_{S}(x_{\lambda}^{\ast}(S))+\frac{\lambda}{2}D^{2}\leq\langle\nabla
F_{S}(\hat{x}),\hat{x}-x_{\lambda}^{\ast}(S)\rangle+\frac{\lambda}{2}D^{2}$
$\displaystyle\leq\|\nabla
F_{S}(\hat{x})\|_{1}\|\hat{x}-x_{\lambda}^{\ast}(S)\|_{\infty}+\frac{\lambda}{2}D^{2}$
$\displaystyle\leq\sqrt{2s}L\|\xi\|_{\infty}+\frac{\lambda}{2}D^{2},$

where the second inequality follows by convexity of $F_{S}$, and the fourth
one by the gradient sparsity assumption and (5).

The conclusion follows by plugging in the respective bounds of $\lambda$ and
$\|\xi\|_{\infty}$, for both pure and approximate DP cases.

∎

###  5.1 A Pure DP-ERM Algorithm for Nonsmooth Losses

We now prove that the rates of pure DP-ERM in the convex case above can be
obtained without the smoothness assumption, albeit with an inefficient
algorithm. This algorithm is based on the exponential mechanism, and it
leverages the fact that the convex ERM with sparse gradient always has an
approximate solution which is sparse. This result requires an additional
assumption on the feasible set:

$\displaystyle\big{(}x\in{\cal X}\wedge
P\subseteq[d]\big{)}\quad\Longrightarrow\quad x|_{P}\in{\cal X},$ (6)

where $x|_{P}\in\mathbb{R}^{d}$ is the vector such that $x_{P,j}=x_{j}$ if
$j\in P$, and $x_{P,j}=0$ otherwise. We will say that ${\cal X}$ is
sparsifiable if (6) holds. Note this property holds e.g. for $\ell_{p}$-balls
centered at the origin.

######  Lemma 5.3.

Let ${\cal X}$ be a convex sparsifiable set. Consider the problem (ERM) under
convexity (Item (A.3)), bounded diameter (Item (A.2)), Lipschitzness (Item
(A.5)) and gradient sparsity (Item (A.7)), assumptions. If $x^{\ast}(S)$ is an
optimal solution of (ERM) and $\tau>0$, then there exists $\tilde{x}\in{\cal
X}$ such that $\|\tilde{x}\|_{0}\leq 1/\tau^{2}$, and

$F_{S}(\tilde{x})-F_{S}(x^{\ast}(S))\leq L\sqrt{s}\tau.$

###### Proof.

Let $\tilde{x}\in\mathbb{R}^{d}$ be defined as

$\tilde{x}_{j}=\left\\{\begin{array}[]{ll}x_{j}&\mbox{ if
}|x_{S,j}^{\ast}|\geq\tau\\\ 0&\mbox{ otherwise.}\end{array}\right.$

Note that $\tilde{x}\in{\cal X}$ since $x^{\ast}(S)\in{\cal X}$ and ${\cal X}$
is sparsifiable. Now we note that

$\|\tilde{x}\|_{0}\leq\sum_{j:\,|x_{S,j}^{\ast}|\geq\tau}\frac{(x_{S,j}^{\ast})^{2}}{\tau^{2}}\leq\frac{1}{\tau^{2}}.$

Finally, for the accuracy guarantee, we use convexity as follows,

$\displaystyle F_{S}(\tilde{x})-F_{S}(x^{\ast}(S))$
$\displaystyle\leq\langle\nabla F_{S}(\tilde{x}),\hat{x}-x^{\ast}(S)\rangle$
$\displaystyle\leq\|\nabla
F_{S}(\tilde{x})\|_{1}\|\tilde{x}-x^{\ast}(S)\|_{\infty}$ $\displaystyle\leq
L\sqrt{s}\tau,$

where in the last step we used that $\nabla f(\hat{x},z_{i})\in{\cal
S}_{s}^{d}$ and the definition of $\tilde{x}$. ∎

We present now the sparse exponential mechanism, which uses the result above
to approximately solve (ERM) with nearly dimension-independent rates.

Algorithm 4 ``Sparse Exponential Mechanism—

Dataset $S=\\{z_{1},\dots,z_{n}\\}\subseteq{\cal Z}$, $\varepsilon$ privacy
parameter, $f(\cdot,z)$ $L$-Lipschitz convex function with $s$-sparse
gradients and range bounded by $B$, $0<\beta<1$ confidence parameter

Let $\tau>0$ be such that
$\frac{\tau^{3}}{\ln(d/[\tau\beta])}=\frac{L\sqrt{s}\varepsilon n}{B}$

Let ${\cal N}_{\tau}$ be a $\tau$-net of $1/\tau^{2}$-sparse vectors over
${\cal X}$ with $|{\cal
N}_{\tau}|\leq\binom{d}{1/\tau^{2}}\big{(}\frac{3}{\tau}\big{)}^{1/\tau^{2}}$

Let $\hat{x}$ be a random variable supported on ${\cal N}_{\tau}$ such that
$\mathbb{P}[\hat{x}=x]\propto\exp\big{\\{}-\frac{B}{\varepsilon
n}F_{S}(x)\big{\\}}$

Return $\hat{x}$

######  Remark 5.4.

The bound on $|{\cal N}_{\tau}|$ claimed in Algorithm 4 follows from a
standard combinatorial argument (e.g. [37]). Moreover, it follows that $|{\cal
N}_{\tau}|\lesssim\Big{(}\frac{d}{\tau}\Big{)}^{1/\tau^{2}}$.

######  Theorem 5.5.

Let ${\cal X}$ be a convex sparsifiable set. Consider a problem (ERM) under
bounded diameter (Item (A.2)), convexity (Item (A.3)), bounded range (Item
(A.4)), Lipschitzness (Item (A.5)) and gradient sparsity (Item (A.7)),
assumptions. Then Algorithm 4 satisfies with probability $1-\beta$

$F_{S}(\hat{x})-F_{S}(x^{\ast}(S))\lesssim
L^{2/3}B^{1/3}\Big{(}\frac{s}{\varepsilon
n}\ln\Big{(}\frac{L\sqrt{s}\varepsilon
n}{B}\frac{d}{\beta}\Big{)}\Big{)}^{1/3}.$

###### Proof.

Let $\tilde{x}$ be the vector whose existence is guaranteed by Lemma 5.3. By
the high-probability guarantee of the exponential mechanism [19] with
probability $1-\beta$,

$F_{S}(\hat{x})-F_{S}(\tilde{x})\leq\frac{B}{\varepsilon n}\Big{(}\ln|{\cal
N}_{\tau}|+\ln(1/\beta)\Big{)}\lesssim\frac{B}{\varepsilon
n}\frac{\ln\big{(}\frac{d}{\tau\beta}\big{)}}{\tau^{2}}.$

Hence, using Lemma 5.3 with the upper bound above,

$\displaystyle F_{S}(\hat{x})-F_{S}(x^{\ast}(S))$ $\displaystyle\leq
F_{S}(\hat{x})-F_{S}(\tilde{x})+F_{S}(\tilde{x})-F_{S}(x^{\ast}(S))$
$\displaystyle\lesssim\frac{B}{\varepsilon
n}\frac{\ln(d/[\tau\beta])}{\tau^{2}}+L\sqrt{s}\tau$
$\displaystyle\lesssim\Big{(}L^{2}B\frac{s}{\varepsilon
n}\ln\Big{(}\frac{L\sqrt{s}\varepsilon
n}{B}\big{(}\frac{d}{\beta}\big{)}^{3}\Big{)}\Big{)}^{1/3},$

where we used our choice of $\tau$. ∎

###  5.2 DP-SCO via Output Perturbation

We note that the proposed output perturbation approach (LABEL:alg:output-pert-
inf) leads to nearly optimal population risk bounds for approximate-DP, by a
slightly different tuning of the regularization parameter $\lambda$.

######  Theorem 5.6.

Consider a problem (SO) under bounded initial distance (Item (A.1)) (or
bounded diameter, Item (A.2), if $\delta>0$), convexity (Item (A.3)),
Lipschitzness (Item (A.5)), bounded range (Item (A.4)), and gradient sparsity
(Item (A.7)). Then, LABEL:alg:output-pert-inf is $(\varepsilon,\delta)$-DP,
and for $0<\beta<1$,

  * •

If $\delta=0$, and under the additional assumption of smoothness (A.6) and
unconstrained domain, ${\mathcal{X}}=\mathbb{R}^{d}$. Selecting
$\lambda=\Big{(}\frac{L^{2}H}{D^{2}}\frac{s\log(d/\beta)}{\varepsilon
n}\Big{)}^{1/3}$, then with probability $1-\beta$

$\textstyle F_{S}(\hat{x})-F_{S}(x^{\ast}({\cal
D}))~{}\lesssim~{}L^{2/3}H^{1/3}D^{4/3}\Big{(}\frac{s\log(d/\beta)}{\varepsilon
n}\Big{)}^{1/3}+B\sqrt{\frac{\ln(1/\beta)}{n}}.\vspace{-0.2cm}$

  * •

If $\delta>0$. Selecting
$\lambda=\frac{L}{D}\Big{(}\frac{\ln(n)\ln(1/\beta)}{n}+\frac{\sqrt{s\ln(1/\delta)\ln(d/\beta)}}{\varepsilon
n}\Big{)}^{1/2}$, then with probability $1-\beta$

$\textstyle F_{\mathcal{D}}(\hat{x})-F_{\mathcal{D}}(x^{\ast}({\cal
D}))~{}\lesssim~{}LD\frac{[s\ln(1/\delta)\log(d/\beta)]^{1/4}}{\sqrt{\varepsilon
n}}+(LD\sqrt{\ln n}+B)\sqrt{\frac{\ln(1/\beta)}{n}}.\vspace{-0.1cm}$

######  Remark 5.7.

Note first that in the proof below we are not addressing the privacy of
LABEL:alg:output-pert-inf, as this has already been proven in Theorem 5.1.

On the other hand, note that the same proof below –using the in-expectation
generalization guarantees of uniformly stable algorithms [10]– provides a
sharper upper bound for the expected excess risk for the pure and approximate
DP cases, which would hold w.p. $1-\beta$ over the algorithm internal
randomness

$\displaystyle\mathbb{E}_{S}[F_{\cal D}(\hat{x})-F_{\cal D}(x^{\ast}({\cal
D}))]$ $\displaystyle\lesssim$ $\displaystyle
L^{2/3}H^{1/3}D^{4/3}\Big{(}\frac{s\log(d/\beta)}{\varepsilon
n}\Big{)}^{1/3},$ $\displaystyle\mathbb{E}_{S}[F_{\cal D}(\hat{x})-F_{\cal
D}(x^{\ast}({\cal D}))]$ $\displaystyle\lesssim$ $\displaystyle
LD\frac{[s\ln(1/\delta)\log(d/\beta)]^{1/4}}{\sqrt{\varepsilon n}}.$

###### Proof.

Using the $\ell_{2}$-sensitivity of $x_{\lambda}^{\ast}(S)$,
$\Delta_{2}=\frac{4L}{\lambda n}$, we have the following generalization bound
[11]: with probability $1-\beta/2$

$F_{\cal
D}(x_{\lambda}^{\ast}(S))-F_{S}(x_{\lambda}^{\ast}(S))\lesssim\frac{L^{2}}{\lambda
n}\ln(n)\ln\Big{(}\frac{1}{\beta}\Big{)}+B\sqrt{\frac{\ln\big{(}\frac{1}{\beta}\big{)}}{n}}=:\gamma.$

The bound of (4) can be obviously modified by comparison with the population
risk minimizer, $x^{\ast}({\cal D})$: in particular, the event above333We also
need concentration to upper bound $F_{S}(x^{\ast}({\cal D}))-F_{\cal
D}(x^{\ast}({\cal D}))$. However, this is easy to do by e.g. Hoeffding’s
inequality, leading to a bound $\lesssim\gamma$. implies that

$F_{\cal D}(x_{\lambda}^{\ast}(S))-F_{\cal D}(x^{\ast}({\cal D}))\lesssim
F_{S}(x_{\lambda}^{\ast}(S))-F_{S}(x^{\ast}({\cal
D}))+\gamma\leq\frac{\lambda}{2}\|x^{\ast}({\cal
D})\|_{2}^{2}+\gamma\lesssim\lambda D^{2}+\gamma.$

On the other hand, the bound (5) works exactly as in the proof of Theorem 5.1.
Hence, we have that with probability $1-\beta/2$,

$\displaystyle F_{\cal D}(\hat{x})-F_{\cal D}(x^{\ast}({\cal D}))$
$\displaystyle\lesssim F_{\cal D}(\hat{x})-F_{\cal
D}(x_{\lambda}^{\ast}(S))+\lambda D^{2}+\gamma$
$\displaystyle\lesssim\langle\nabla F_{\cal
D}(\hat{x}),\hat{x}-x_{\lambda}^{\ast}(S)\rangle+\lambda D^{2}+\gamma$
$\displaystyle\lesssim 2L\sqrt{s}\|\xi\|_{\infty}+\frac{L^{2}}{\lambda
n}\ln(n)\ln\Big{(}\frac{1}{\beta}\Big{)}+\lambda
D^{2}+\frac{B}{\sqrt{n}}\sqrt{\ln\big{(}\frac{1}{\beta}\big{)}},$

where in the last step we used that $\|\nabla F_{\cal
D}(\hat{x})\|_{1}=\|\mathbb{E}_{z}[\nabla
f(\hat{x},z)]\|_{1}\leq\mathbb{E}_{z}[\|\nabla f(\hat{x},z)\|_{1}]\leq
L\sqrt{s}$ (the last step which follows by the gradient sparsity), inequality
(5), and the definition of $\gamma$.

We proceed now by separately studying the different cases for $\delta$:

  * •

Case $\delta=0$. The bound above becomes

$F_{\cal D}(\hat{x})-F(x^{\ast}({\cal D}))\lesssim\frac{L^{2}}{\lambda
n}\Big{(}\frac{s\ln(d/\beta)}{\varepsilon}\big{(}\frac{H}{\lambda}+1\big{)}+\ln
n\ln(1/\beta)\Big{)}+\lambda D^{2}+B\sqrt{\frac{\ln(1/\beta)}{n}}.$

Our choice of $\lambda$ provides the claimed bound.

  * •

Case $\delta>0$. Here, the upper bound takes the form

$F_{\cal D}(\hat{x})-F(x^{\ast}({\cal D}))\lesssim\frac{L^{2}}{\lambda
n}\Big{(}\frac{\sqrt{s\ln(d/\beta)\ln(1/\delta)}}{\varepsilon}+\ln(n)\ln(1/\beta)\Big{)}+\lambda
D^{2}+B\sqrt{\frac{\ln(1/\beta)}{n}}.$

The proposed value of $\lambda$ leads to the bound below that holds with
probability $1-\beta$,

$\displaystyle F_{\cal D}(\hat{x})-F_{\cal D}(x^{\ast}({\cal D}))$
$\displaystyle\lesssim B\sqrt{\frac{\ln(1/\beta)}{n}}+LD\sqrt{\frac{\ln
n\ln(1/\beta)}{n}+\frac{\sqrt{s\ln(1/\delta)\log(d/\beta)}}{\varepsilon n}}$
$\displaystyle\lesssim(LD\sqrt{\ln
n}+B)\sqrt{\frac{\ln(1/\beta)}{n}}+LD\frac{[s\ln(1/\delta)\log(d/\beta)]^{1/4}}{\sqrt{\varepsilon
n}}.$

∎

##  6 A Bias-Reduction Method for the Stochastic Gradient Method with Sparse
Gradients

For nonconvex objectives, the most natural and popular algorithms are based on
SGD. In this section, we show how to integrate the nearly-optimal approximate-
DP mean estimation algorithms from Section 3 to design a stochastic first-
order oracle that can be readily used by any stochastic first-order method.
The key challenge here is that estimators from Section 3 are inherently
biased, which is known to dramatically deteriorate the rates of stochastic
first-order methods. Hence, we start by introducing a bias-reduction method.

###  6.1 Subsampled Bias-Reduced Gradient Estimator for DP-ERM

We propose Algorithm 5, inspired by a debiasing technique proposed in [9]. The
idea is the following: we know that the projection mechanism would provide
more accurate gradient estimators with larger sample sizes, and we will see
that its bias improves analogously. We choose our batch size as a random
variable with exponentially increasing range, and given such a realization we
subtract the projection mechanism applied to the whole batch minus the same
mechanism applied to both halves of this batch.444We follow the Blanchet-Glynn
notation of $O$ and $E$ to denote the ‘odd’ and ‘even’ terms for the batch
partition [9]; notice this partition is arbitrary. This subtraction, together
with a multiplicative and additive correction, results in the expected value
of the outcome ${\cal G}(x)$ corresponding to the term associated with the
largest batch size, leading to its expected accuracy being boosted by such
large sample size, without necessarily utilizing such amount of data (in fact,
the probability of such batch size being picked is exponentially small,
compared to the smallest possible one). The caveat with this technique, as we
will see, relates to a heavy-tailed distribution of outcomes, and therefore
great care needs to be made in order to analyze the accuracy guarantees of
this method.

Instrumental to our analysis is the following truncated geometric
distribution.

######  Definition 6.1.

A random variable $N$ has a truncated geometric distribution with parameter
$M\in\mathbb{N}$ iff its probability mass is supported on $\\{0,\ldots,M\\}$,
with corresponding probabilities

$p_{k}=\left\\{\begin{array}[]{cc}C_{M}/2^{k}&k\leq M\\\
0&k>M,\end{array}\right.$ (7)

where $C_{M}=[2(1-2^{-(M+1)})]^{-1}$ is the normalizing constant. Its law will
be denoted by $\mathsf{TGeom}(M)$.

######  Remark 6.2.

Note that $1/2\leq C_{M}\leq 1$. I.e., the normalizing constant of the
truncated geometric distribution is uniformly bounded away from $0$ and
$+\infty$.

Algorithm 5 Subsampled_Bias-
Reduced_Gradient_Estimator$(x,S,N,\varepsilon,\delta)$

Dataset $S=(z_{1},\ldots,z_{n})\in{\cal Z}^{n}$, $\varepsilon,\delta>0$
privacy parameters, $L$-Lipschitz loss $f(x,z)$ with $s$-sparse gradient,
$x\in{\cal X}$, batch size parameter $N\sim\mathsf{TGeom}(M)$ with
$M=\lfloor\log_{2}(n)\rfloor-1$

Let $B\sim\mathsf{Unif}\big{(}\binom{n}{2^{N+1}}\big{)}$, $O,E$ a partition of
$B$ with $|O|=|E|=2^{N}$, $I\sim\mathsf{Unif}([n])$

$G_{N+1}^{+}(x,B)=\text{{Projection\\_Mechanism}}(\nabla
F_{B}(x),\varepsilon/4,\delta/4,2^{N+1})$ (LABEL:alg:proj)

$G_{N}^{-}(x,O)=\text{{Projection\\_Mechanism}}(\nabla
F_{O}(x),\varepsilon/4,\delta/4,2^{N})$

$G_{N}^{-}(x,E)=\text{{Projection\\_Mechanism}}(\nabla
F_{E}(x),\varepsilon/4,\delta/4,2^{N})$

$G_{0}(x,I)=\text{{Projection\\_Mechanism}}(\nabla
f(x,z_{I}),\varepsilon/4,\delta/4,1)$

Return $\textstyle{\cal
G}(x)=\frac{1}{p_{N}}\Big{(}G_{N+1}^{+}(x,B)-\frac{1}{2}\big{(}G_{N}^{-}(x,O)+G_{N}^{-}(x,E)\big{)}\Big{)}+G_{0}(x,I)$

Algorithm 6 Subsampled_Bias-Reduced_Sparse_SGD$(x^{0},S,\varepsilon,\delta)$

Initialization $x^{0}\in{\cal X}$; Dataset
$S=(z_{1},\ldots,z_{n})\in\mathcal{Z}^{n}$; $\varepsilon,\delta$, privacy
parameters; stepsize $\eta>0$; gradient oracle for $L$-Lipschitz and with
$s$-sparse gradient loss $f(\cdot,z)$

$t\leftarrow-1$

while
$\sqrt{2\ln\big{(}\frac{4}{\delta}\big{)}\sum_{s=0}^{t-1}\big{(}\frac{3\cdot
2^{N_{t}+1}+1}{16n}\big{)}^{2}}+\frac{\varepsilon}{2}\sum_{s=0}^{t-1}\big{(}\frac{3\cdot
2^{N_{t}+1}+1}{16n}\big{)}^{2}\leq\frac{1}{2}$ and
$\sum_{s=0}^{t-1}\frac{3\cdot 2^{N_{t}+1}+1}{16n}\leq\frac{1}{4}$ do

$t\leftarrow t+1$

$N_{t}\sim\mathsf{TGeom}(M)$ where $M=\lfloor\log_{2}(n)\rfloor-1$

${\cal G}(x^{t})=$ Subsampled_Bias-
Reduced_Gradient_Estimator$(x^{t},S,N_{t},\varepsilon/8,\delta/4)$ (Alg. 5)

$x^{t+1}=\Pi_{\cal X}\big{[}x^{t}-\eta{\cal G}(x^{t})\big{]}$

end while

return $\begin{cases}\bar{x}=\frac{1}{t+1}\sum_{s=0}^{t}x^{s}&\text{if
}f(\cdot,z)\text{ is convex}\,,\\\\[2.84526pt] x^{\hat{t}}\text{ where
}\hat{t}\sim\mathsf{Unif}(\\{0,\ldots,T\\})&\,\text{ if}f(\cdot,z)\text{ is
not convex}.\\\ \end{cases}$

We propose Algorithm 6, which interacts with the oracle given in Algorithm 5.
For convenience, we will denote the random realization from the truncated
geometric distribution used at iteration $t$ by $N_{t}$. The idea is that,
using the fully adaptive composition property of DP [39], we can run the
method until our privacy budget is exhausted. Due to technical reasons,
related to the bias-reduction, we need to shift by one the termination
condition in the algorithm. In particular, our algorithm goes over the privacy
budget of $(\varepsilon/2,\delta/2)$. The additional slack in the privacy
budget guarantees that even with the extra oracle call the algorithm respects
the privacy constraint.

######  Lemma 6.3.

Algorithm 6 is $(\varepsilon,\delta)$-DP.

###### Proof.

The proof is based on the fully adaptive composition theorem of differential
privacy [39]. For this, we consider $\\{{\cal A}_{t}\\}_{t\geq 0}$, where
${\cal A}_{0}(S)=(x^{0},N_{0})$ (here $N_{0}$ the first truncated geometric
parameter), and inductively, ${\cal A}_{t+1}({\cal A}_{t}(S),S)$ for $t\geq 0$
takes as input ${\cal A}_{t}(S)=(x^{t},N_{t})$, computes ${\cal G}(x_{t})$
using the subsampled debiased gradient estimator (Algorithm 5), and performs a
projected gradient step based on ${\cal G}(x^{t})$. Let ${\cal H}_{t}$ be the
$\sigma$-algebra induced by $({\cal A}_{s})_{s=0,\ldots,t}$.

Suppose now that ${\cal A}_{t}$ is $(\varepsilon_{t},\delta_{t})$-DP, where
$(\varepsilon_{t},\delta_{t})$ are ${\cal H}_{t}$-measurable (we will later
obtain these parameters), and let
$T:=\inf\\{t:\varepsilon_{[0:t]}>\varepsilon/2,\,\,\delta_{[0:t]}>\delta/2\\}$,
in the language of Theorem A.4 (notice that in the context of that theorem, we
are choosing $\delta^{\prime}=\delta^{\prime\prime}=\delta/4$). We first claim
that $(x^{t})_{t=0,\ldots,T-1}$ is $(\varepsilon/2,\delta/2)$-DP, which
follows directly from Theorem A.4. Next, we will later show that
$\varepsilon_{t}\leq\varepsilon/4$ and $\delta_{t}\leq\delta/4$, almost surely
(this applies in particular to $x_{T}$), and therefore by the composition
property of DP, $(x_{t})_{t\leq T}$ is $(\varepsilon,\delta)$-DP.

Next, we provide the bounds on $(\varepsilon_{t},\delta_{t})$ required to
conclude the proof. For this, we first note that –conditionally on $x^{t}$,
$N_{t}$ and $B_{t}$– the computation of $G_{N_{t}+1}^{+}(x^{t},B_{t})$,
$G_{N_{t}}^{-}(x^{t},O_{t})$, $G_{N_{t}}^{-}(x^{t},E_{t})$, is
$(3\varepsilon/32,3\delta/16)$-DP. Furthermore, by privacy amplification by
subsampling, this triplet of random variables is
$(\varepsilon^{\prime},\delta^{\prime})$, with

$\varepsilon^{\prime}=\ln\Big{(}1+\frac{2^{N_{t}+1}}{n}(e^{3\varepsilon/32}-1)\Big{)}\leq\frac{2^{N_{t}+1}}{n}\frac{3\varepsilon}{16},\qquad\delta^{\prime}=\frac{2^{N_{t}+1}}{n}\frac{3\delta}{16},$

where we used above that $\varepsilon\leq 1$. Similarly, we have that
$G_{0}(x,I)$ is $\big{(}\frac{\varepsilon}{16n},\frac{\delta}{16n}\big{)}$-DP.
Therefore, by the basic composition theorem of DP, we have the following
privacy parameters for the $t$-th iteration of the algorithm

$\varepsilon_{t}=(3\cdot
2^{N_{t}+1}+1)\frac{\varepsilon}{16n},\quad\delta_{t}=(3\cdot
2^{N_{t}+1}+1)\frac{\delta}{16n}.$

This proves in particular that $(\varepsilon_{t},\delta_{t})$ are ${\cal
H}_{t}$-measurable, and that $\varepsilon_{t}\leq\varepsilon/4$, and
$\delta_{t}\leq\delta/4$ almost surely, which concludes the proof ∎

###  6.2 Bias and Moment Estimates for the Debiased Gradient Estimator

We provide bias and second moment estimates for our debiased estimator of the
empirical gradient. In summary, we show that this estimator has bias matching
that of the full-batch gradient estimator, while at the same time its second
moment is bounded by a mild function of the problem parameters.

######  Lemma 6.4.

Let $d\gtrsim\frac{n\varepsilon\sqrt{s\ln(d/s)}}{\sqrt{\ln(1/\delta)}}$.
Algorithm 5, enjoys bias and second moment bounds

$\displaystyle\Big{\|}\mathbb{E}[{\cal G}(x)-\nabla F_{S}(x)|x]\Big{\|}$
$\displaystyle\textstyle\lesssim~{}\frac{L[s\ln(d/s)\ln(1/\delta)]^{1/4}}{\sqrt{n\varepsilon}}=:b,$
$\displaystyle\mathbb{E}[\|{\cal G}(x)\|^{2}|x]$
$\displaystyle\textstyle\lesssim~{}\frac{L^{2}\ln(n)\sqrt{s\ln(d/s)\ln(1/\delta)}}{\varepsilon}=:\nu^{2}.$

###### Proof.

For simplicity, we assume without loss of generality that $n$ is a power of 2,
so that $2^{M+1}=n$.

Bias  Let, for $k=0,\ldots,M$,
$G_{k+1}^{+}(x)=\mathbb{E}[G_{N+1}^{+}(x,B)|N=k,x]$, and

$G_{k}^{-}(x)=\mathbb{E}[G_{N}^{-}(x,E)|N=k,x]=\mathbb{E}[G_{N}^{-}(x,O)|N=k,x],$

where the last equality follows by the identical distribution of $O$ and $E$.
Noting further that $G_{k}^{+}(x)=G_{k}^{-}(x)$ (which follows by the uniform
sampling and the cardinality of the used datapoints), and using the law of
total probability, we have

$\displaystyle\mathbb{E}[{\cal G}(x)|x]$ $\displaystyle=$
$\displaystyle\textstyle\sum_{k=0}^{M}\Big{(}G_{k}^{+}(x)-G_{k-1}^{-}(x)\Big{)}+\mathbb{E}[G_{0}(x,I)|x]$
$\displaystyle=$ $\displaystyle\textstyle
G_{M+1}^{+}(x)-G_{0}^{-}(x)+\mathbb{E}[G_{0}(x,I)|x]$ $\displaystyle=$
$\displaystyle\textstyle\mathbb{E}[G_{M+1}^{+}(x)-\nabla F_{S}(x)]+\nabla
F_{S}(x),$

where we also used that $\mathbb{E}[G_{0}(x,I)|x]=G_{0}^{-}(x)$ (since $I$ is
a singleton). Next, by Theorem 3.4

$\textstyle\|\mathbb{E}[{\cal G}(x)|x]-\nabla
F_{S}(x)\|\leq\|\mathbb{E}[G_{M+1}^{+}(x)-\nabla F_{S}(x)]\|\lesssim
L\frac{[s\ln(d/s)\ln(1/\delta)]^{1/4}}{\sqrt{n\varepsilon}}.$

Second moment bound  Using the law of total probability, and that $O,E$ are a
partition of $B$:

$\displaystyle\mathbb{E}[\|{\cal G}(x)\|^{2}|x]$
$\displaystyle=\sum_{k=0}^{M}p_{k}\mathbb{E}\Big{[}\Big{\|}\frac{1}{p_{k}}[G_{N+1}^{+}(x,B)-\nabla
F_{B}(x)]$ $\displaystyle-\frac{1}{2p_{k}}\big{[}G_{N}^{-}(x,O)-\nabla
F_{O}(x)+G_{N}^{-}(x,E)-\nabla
F_{E}(x)\big{]}+G_{0}(x,I)\Big{\|}^{2}\Big{|}x,N=k\Big{]}$
$\displaystyle~{}\leq~{}2\mathbb{E}[\|G_{0}(x,I)\|^{2}|x]+4\sum_{k=0}^{M}\frac{1}{p_{k}}\mathbb{E}\Big{[}\Big{\|}G_{N+1}^{+}(x,B)-\nabla
F_{B}(x)\Big{\|}^{2}\Big{|}x,N=k\Big{]}$
$\displaystyle~{}~{}~{}+~{}\sum_{k=0}^{M}\frac{1}{p_{k}}\Big{(}\mathbb{E}\Big{[}\Big{\|}G_{N}^{-}(x,O)-\nabla
F_{O}(x)\Big{\|}^{2}\Big{|}x,N=k\Big{]}+\mathbb{E}\Big{[}\Big{\|}G_{N}^{-}(x,E)-\nabla
F_{E}(x)\Big{\|}^{2}\Big{|}x,N=k\Big{]}\Big{)}.$

We now use Theorem 3.4, to conclude that

$\displaystyle\textstyle\mathbb{E}\Big{[}\Big{\|}G_{N+1}^{+}(x,B)-\nabla
F_{B}(x)\Big{\|}^{2}\Big{|}x,N=k\Big{]}$
$\displaystyle\textstyle\lesssim\frac{L^{2}\sqrt{s\ln(d/s)\ln(1/\delta)}}{2^{k+1}\varepsilon}$
$\displaystyle\textstyle\max_{A\in\\{O,E\\}}\Big{\\{}\mathbb{E}\Big{[}\Big{\|}G_{N}^{-}(x,A)-\nabla
F_{A}(x)\Big{\|}^{2}\Big{|}x,N=k\Big{]}\Big{\\}}$
$\displaystyle\textstyle\lesssim\frac{L^{2}\sqrt{s\ln(d/s)\ln(1/\delta)}}{2^{k}\varepsilon}$
$\displaystyle\textstyle\mathbb{E}\big{\|}G_{0}(x,I)\big{\|}^{2}$
$\displaystyle\textstyle\lesssim\frac{L^{2}\sqrt{s\ln(d/s)\ln(1/\delta)}}{\varepsilon}.$

Recalling that $M+1=\log_{2}n$ and $p_{k}=2^{-k}$, these bounds readily imply
that $\mathbb{E}\|{\cal G}(x)\|^{2}\lesssim\nu^{2}$. ∎

###  6.3 Accuracy Guarantees for Subsampled Bias-Reduced Sparse SGD

The previous results provide useful information about the privacy, bias and
second-moment of our proposed oracle. Our goal now is to provide excess risk
rates for DP-ERM. For this, we need to prove the algorithm runs for long
enough, i.e., a lower bound on the stopping time of Algorithm 6,

$\textstyle
T:=\inf\Big{\\{}t:\frac{\varepsilon}{2}<\sqrt{2\ln\big{(}\frac{4}{\delta}\big{)}{\displaystyle\sum_{s=0}^{t}}\big{(}\frac{3\cdot
2^{N_{t}+1}+1}{16n}\big{)}^{2}}+\frac{\varepsilon}{2}{\displaystyle\sum_{s=0}^{t}}\frac{3\cdot
2^{N_{t}+1}+1}{16n}\,\,\mbox{ or
}\,\,\frac{\delta}{4}<{\displaystyle\sum_{s=0}^{t}}\frac{3\cdot
2^{N_{t}+1}+1}{16n}\Big{\\}}.$ (8)

####  6.3.1 Lower Bounds on the Stopping Time

Given the heavy-tailed nature of the batch sizes, the sums defining $T$ may
not concentrate strongly enough to directly yield high-probability lower
bounds for $T$. What we will do instead is showing that with constant
probability $T$ behaves as desired.

To justify the approach, let us provide a simple in-expectation bound on how
the privacy budget accumulates in the definition of $T$: letting
$\varepsilon_{t}=\frac{(3\cdot 2^{N_{t}+1}+1)\varepsilon}{16n}$, we have that

$\mathbb{E}\Big{[}\sum_{s=0}^{t}\varepsilon_{s}^{2}\Big{]}=\frac{(t+1)\varepsilon^{2}}{(16n)^{2}}\mathbb{E}\Big{[}(3\cdot
2^{N_{1}+1}+1)^{2}\Big{]}\leq\frac{2(t+1)\varepsilon^{2}}{(16n)^{2}}\Big{(}9\mathbb{E}[2^{2(N_{1}+1)}]+1\big{]}\Big{)}\lesssim\frac{t\varepsilon^{2}}{n},$

where in the last step we used that
$\mathbb{E}\big{[}2^{2(N_{1}+1)}\big{]}=C_{M}\sum_{k=1}^{M+1}2^{k}\lesssim n$.
This in-expectation analysis can be used in combination with ideas from
stopping times to establish bounds for $T$.

######  Lemma 6.5.

Let $0<\delta<1/n^{2}$. In the notation of Algorithm 6, let $T$ be the
stopping time defined in eqn. (8). Then, there exists $t=Cn/\log(2/\delta)$
(with $C>0$ an absolute constant) such that

$\mathbb{P}[T\leq t]\leq 1/4.$

On the other hand,

$\frac{n^{2}}{(n+1)\ln(4/\delta)}-1\leq\mathbb{E}[T]\leq\frac{64n}{9\ln(4/\delta)}.$

###### Proof.

Let $A=\sum_{s=0}^{t-1}\big{(}\frac{3\cdot 2^{N_{s}+1}+1}{16n}\big{)}^{2}$,
and note that for $t\leq T+1$, $A\leq 1$ almost surely. Then, we have that

$\varepsilon_{[0:t-1]}=\sqrt{2\ln(4/\delta)\varepsilon^{2}A}+\frac{\varepsilon^{2}}{2}A\leq
2\varepsilon\sqrt{2\ln(4/\delta)A}.$

Now, by eqn. (8) and the union bound,

$\displaystyle\mathbb{P}[T\leq t]$
$\displaystyle\leq\mathbb{P}\Big{[}2\varepsilon\sqrt{2\ln(4/\delta)A}>\varepsilon/2\Big{]}+\mathbb{P}\Big{[}\sum_{s=0}^{t-1}(3\cdot
2^{N_{t}+1}+1)>4n\Big{]}$
$\displaystyle\leq\mathbb{P}\Big{[}\sum_{s=0}^{t-1}\big{(}3\cdot
2^{N_{t}+1}+1\big{)}^{2}>\frac{32n^{2}}{\ln\big{(}\frac{4}{\delta}\big{)}}\Big{]}+\mathbb{P}\Big{[}\sum_{s=0}^{t-1}(3\cdot
2^{N_{t}+1}+1)>4n\Big{]}$
$\displaystyle\leq\frac{t\ln\big{(}\frac{4}{\delta}\big{)}}{16n^{2}}\big{(}9\mathbb{E}[2^{2(N_{t}+1)}]+1\big{)}+\frac{t}{4n}[6(M+1)+1]$
$\displaystyle\leq\frac{t\ln\big{(}\frac{4}{\delta}\big{)}}{16n^{2}}[18n+1]+\frac{t}{4n}[6\log(n)+1]$
$\displaystyle\leq 1/4,$

where the third step follows from Markov’s inequality and the fact that
$(N_{s})_{s}$ are i.i.d., and the last step follows from our choice of
$t=Cn/\log(4/\delta)$ with $C>0$ sufficiently small (here we use the fact that
$\delta<1/n^{2}$).

For the second part, we use that by the definition of $T$ (eqn. (8))

$\displaystyle\frac{\varepsilon}{2}<\sqrt{2\varepsilon^{2}\ln\big{(}\frac{4}{\delta}\big{)}\sum_{s=0}^{T}\frac{(3\cdot
2^{N_{s}+1}+1)^{2}}{(16n)^{2}}}+\frac{\varepsilon^{2}}{2}\sum_{s=0}^{T}\frac{(3\cdot
2^{N_{s}+1}+1)^{2}}{(16n)^{2}}\,\,\,\vee\,\,\,\frac{1}{4}<\sum_{s=0}^{T}\frac{3\cdot
2^{N_{s}+1}+1}{16n}$ $\displaystyle\Longrightarrow\quad
n^{2}<\max\left\\{8\ln\big{(}\frac{4}{\delta}\big{)}\sum_{s=0}^{T}\frac{(3\cdot
2^{N_{s}+1}+1)^{2}}{(16)^{2}},n\sum_{s=0}^{T}\frac{3\cdot
2^{N_{s}+1}+1}{4}\right\\}$

Taking expectations and bounding the maximum by the sum allows us to use
Wald’s identity as follows,

$\displaystyle n^{2}$
$\displaystyle<\mathbb{E}[T+1]\Big{(}8\ln\big{(}\frac{4}{\delta}\Big{)}\frac{2(9n+1)}{16^{2}}+n\frac{3\log(n)+1}{4}\Big{)}$
$\displaystyle\leq\mathbb{E}[T+1]\ln\big{(}\frac{4}{\delta}\Big{)}(n+1),$

which proves the claimed bound.

The upper nound on $\mathbb{E}[T]$ is obtained similarly. Again, by eqn. (8),

$\displaystyle\frac{32n^{2}}{\ln(4/\delta)}\geq\mathbb{E}\Big{[}\sum_{s=0}^{T-1}\big{(}3\cdot
2^{N_{s}+1}+1)\big{)}^{2}\Big{]}\geq\mathbb{E}[T]\frac{9n}{2}.$

Re-arranging terms provides the claimed lower bound. ∎

####  6.3.2 Excess Empirical Risk in the Convex Setting

As a first application, we study the accuracy guarantees of Algorithm 6 in the
convex setting. We remark that these rates will be slightly weaker than those
provided in Section 5, but this example is useful to illustrate the technique.
Towards this goal, we analyze the cumulative regret of the algorithm, namely
${\cal R}_{T}:=\sum_{t=0}^{T}[F_{S}(x^{t})-F_{S}(x^{\ast}(S))]$. Although this
is a standard and well-studied object in optimization, we need to obtain
bounds for this object when the stopping time $T$ is random. The key
observation here is that since $T$ is a stopping time, the event $\\{T\geq
t\\}$ is ${\cal F}_{t-1}$-measurable (here, $({\cal F}_{t}$ is the natural
filtration). This permits using our bias and second moment bounds analogously
to the case where $T$ is deterministic. Moreover, for the sake of analysis, we
will consider Algorithm 6 as running indefinitely, for all $t\geq 0$. This
would of course eventually violate privacy. However, since our algorithm stops
at time $T$, then privacy is guaranteed as done earlier in this section.

######  Proposition 6.6.

Let ${\cal R}_{t}:=\sum_{t=0}^{t}[F_{S}(x^{t})-F_{S}(x^{\ast}(S))]$, let $T$
be the stopping time defined in eqn. (8). Then

$\mathbb{E}[{\cal
R}_{T}]\leq\frac{1}{2\eta}\|x^{0}-x^{\ast}(S)\|^{2}+\mathbb{E}[T+1]\big{(}\frac{\eta\nu^{2}}{2}+b\big{)},$

where $b$ and $\nu^{2}$ are defined as in Lemma 6.4.

###### Proof.

By Proposition B.1 (see Appendix B),

$\displaystyle\mathbb{E}[{\cal R}_{T}]$
$\displaystyle\leq\mathbb{E}\Big{(}\frac{1}{2\eta}\|x^{0}-x^{\ast}(S)\|^{2}+\sum_{t=0}^{T}\big{[}\frac{\eta}{2}\|{\cal
G}(x^{t})\|^{2}+\langle\nabla F(x^{t})-{\cal
G}(x^{t}),x^{t}-x^{\ast}(S)\rangle\big{]}\Big{)}$
$\displaystyle=\mathbb{E}\Big{(}\frac{1}{2\eta}\|x^{0}-x^{\ast}(S)\|^{2}$
$\displaystyle+\sum_{t=0}^{\infty}\Big{\\{}\frac{\eta}{2}\mathbb{E}[\mathbf{1}_{\\{t\leq
T\\}}\|{\cal G}(x^{t})\|^{2}|{\cal F}_{t-1}]+\mathbb{E}[\mathbf{1}_{\\{t\leq
T\\}}\langle\nabla F(x^{t})-{\cal G}(x^{t}),x^{t}-x^{\ast}(S)\rangle|{\cal
F}_{t-1}]\Big{\\}}\Big{)}$
$\displaystyle=\mathbb{E}\Big{(}\frac{1}{2\eta}\|x^{0}-x^{\ast}(S)\|^{2}$
$\displaystyle+\sum_{t=0}^{\infty}\Big{\\{}\frac{\eta\mathbf{1}_{\\{T\geq
t\\}}}{2}\mathbb{E}[\|{\cal G}(x^{t})\|^{2}|{\cal
F}_{t-1}]+\mathbf{1}_{\\{T\geq t\\}}\mathbb{E}[\langle\nabla F(x^{t})-{\cal
G}(x^{t}),x^{t}-x^{\ast}(S)\rangle|{\cal F}_{t-1}]\Big{\\}}\Big{)}$

where in the first equality we used the tower property of the conditional
expectation, and in the second equality we used that $\\{T\geq t\\}$ is ${\cal
F}_{t-1}$-measurable.

Now, by Lemma 6.4, $\mathbb{E}[\langle\nabla F(x^{t})-{\cal
G}(x^{t}),x^{t}-x^{\ast}(S)\rangle|{\cal F}_{t-1}]\leq b$ and
$\mathbb{E}[\|{\cal G}(x^{t})\|^{2}|{\cal F}_{t-1}]\leq\nu^{2}$ (note that
${\cal F}_{t-1}$ does not include the randomness of $N_{t}$, and therefore the
bias and moment estimates as in the mentioned lemma hold), thus

$\mathbb{E}[{\cal
R}_{T}]\leq\frac{1}{2\eta}\|x^{0}-x^{\ast}(S)\|^{2}+\mathbb{E}[T+1]\big{(}\frac{\eta\nu^{2}}{2}+b\big{)}.$

∎

######  Theorem 6.7.

Let $\tau=\frac{C^{\prime}n}{\ln(2/\delta)}$, where $C^{\prime}>0$ is an
absolute constant. Let $\eta=\frac{D}{\nu\sqrt{\tau}}$,
$U=C[D\nu\sqrt{\tau}+b\tau]$, where $C>0$ is an absolute constant. Then
Algorithm 6 satisfies

$\mathbb{P}\Big{[}F_{S}(\bar{x})-F_{S}(x^{\ast}(S))\leq\frac{U}{\tau}\Big{]}\geq
1/2.$

###### Proof.

We start by noting that

$\displaystyle\mathbb{P}\Big{[}F_{S}(\bar{x})-F_{S}(x^{\ast}(S))>\frac{U}{\tau}\Big{]}$
$\displaystyle\leq\mathbb{P}\big{[}\\{T\leq\tau\\}\cup\\{{\cal
R}_{T}>U\\}\big{]}\leq\mathbb{P}\big{[}T\leq\tau]+\mathbb{P}[{\cal R}_{T}>U].$

For the first event, by Lemma 6.5, we have that $\mathbb{P}[T\leq\tau]\leq
1/4$ (which determines $C^{\prime}$). On the other hand, using Proposition 6.6
and Lemma 6.5, we have that for our choice of $\eta$, we have that

$\mathbb{E}[{\cal
R}_{T}]\leq\frac{D\nu\sqrt{\tau}}{2}+\mathbb{E}[T]\Big{(}\frac{D\nu}{2\sqrt{\tau}}+b\Big{)}\lesssim
D\nu\sqrt{\tau}+\tau b.$

In particular, for our choice of $U$ (with $C>0$ sufficiently large),

$\mathbb{P}[{\cal R}_{T}>U]\leq\frac{\mathbb{E}[{\cal
R}_{T}]}{U}\leq\frac{1}{4}.$

∎

The above result provides a nearly optimal empirical excess risk rate for DP-
SCO,

$O\Big{(}LD\,\frac{\sqrt{\ln n}[s\ln(d/s)\ln^{3}(1/\delta)]}{\sqrt{\varepsilon
n}}\Big{)},$

but only with constant probability. We defer to the next section how to boost
this guarantee to hold with arbitrarily high probability.

####  6.3.3 Near Stationary Points for the Empirical Risk

For nonconvex objectives it is known that obtaining vanishing excess risk is
computationally difficult. Hence, we study the more modest goal of
approximating stationary points, i.e. points with small norm of the gradient.
By combining known analyses of biased SGD with our bias-reduced oracle, we can
establish bounds on the success probability of the algorithm.

######  Theorem 6.8.

Consider a (nonconvex) (SO) problem, under the following assumptions:
Lipschitzness (Item (A.5)), smoothness (Item (A.6)), gradient sparsity (Item
(A.7)), and the following initial suboptimality assumption: namely, that given
our initialization $x^{0}\in\mathbb{R}^{d}$, we know ${\Gamma}>0$ such that

$F_{S}(x^{0})-F_{S}(x^{\ast}(S))\leq{\Gamma}.$ (9)

Let $\tau=\frac{C^{\prime}n}{\ln(2/\delta)}$ with $C^{\prime}>0$ an absolute
constant. Let $\eta=\sqrt{\frac{{\Gamma}}{Ht\nu^{2}}}$ and
$U=C\big{(}\sqrt{{\Gamma}H\tau}\nu+L\tau b\big{)}$ with $C>0$ an absolute
constant. Then Algorithm 6 satisfies $\mathbb{P}\Big{[}\|\nabla
F_{S}(x^{\hat{t}})\|_{2}^{2}\leq\frac{U}{\tau}\Big{]}\geq 1/2$, and

$\frac{U}{\tau}\lesssim\big{(}\sqrt{{\Gamma}H}L\sqrt{\ln(n)\ln(1/\delta)}+L^{2}\big{)}\frac{[s\ln(d/s)\ln(1/\delta)]^{1/4}}{\sqrt{\varepsilon
n}}.$

###### Proof.

First, given any $U>0$, we have that

$\displaystyle\mathbb{P}\Big{[}\|\nabla
F_{S}(x_{\hat{t}})\|_{2}>\sqrt{\frac{U}{\tau}}\Big{]}$
$\displaystyle\leq\mathbb{P}[T<\tau]+\mathbb{P}[T\|\nabla
F_{S}(x_{\hat{t}})\|_{2}^{2}>U]\leq\frac{1}{4}+\frac{\mathbb{E}[T\|\nabla
F_{S}(x^{\hat{t}})\|_{2}^{2}]}{U},$

where the last step follows by Lemma 6.5 and Chebyshev’s inequality,
respectively. Next, by definition of $\hat{t}$ and Proposition B.2 (see
Section B.2),

$\displaystyle\mathbb{E}[(T+1)\|\nabla
F(x^{\hat{t}})\|_{2}^{2}]=\mathbb{E}\Big{[}\sum_{t=0}^{T}\|\nabla
F(x^{t})\|_{2}^{2}\Big{]}$ $\displaystyle\leq\frac{{\Gamma}}{\eta}+\frac{\eta
H}{2}\mathbb{E}\Big{[}\sum_{t=0}^{T}\|{\cal
G}(x^{t})\|_{2}^{2}\Big{]}-\mathbb{E}\Big{[}\sum_{t=0}^{T}\langle\nabla
F(x^{t}),{\cal G}(x^{t})-\nabla F(x^{t})\rangle\Big{]}$
$\displaystyle\leq\frac{{\Gamma}}{\eta}+\frac{\eta
H}{2}\sum_{t=0}^{\infty}\mathbb{E}[\mathbf{1}_{\\{T\geq t\\}}\|{\cal
G}(x^{t})\|_{2}^{2}]-\sum_{t=0}^{\infty}\mathbb{E}[\mathbf{1}_{\\{T\geq
t\\}}\langle\nabla F(x^{t}),{\cal G}(x^{t})-\nabla F(x^{t})\rangle]$
$\displaystyle\leq\frac{{\Gamma}}{\eta}+\frac{\eta
H}{2}\sum_{t=0}^{\infty}\mathbb{P}[T\geq t]\mathbb{E}\big{(}\mathbb{E}[\|{\cal
G}(x^{t})\|_{2}^{2}|{\cal F}_{t-1}]\big{)}$
$\displaystyle\quad-\sum_{t=0}^{\infty}\mathbb{P}[T\geq
t]\mathbb{E}\big{(}\mathbb{E}[\langle\nabla F(x^{t}),{\cal G}(x^{t})-\nabla
F(x^{t})|{\cal F}_{t-1}\rangle]\big{)}$
$\displaystyle\leq\frac{{\Gamma}}{\eta}+\frac{\eta
H}{2}\mathbb{E}[T+1]\nu^{2}+\mathbb{E}[T+1]Lb$
$\displaystyle\lesssim\sqrt{{\Gamma}H\tau}\nu+\tau Lb,$

where the third inequality holds since $\\{T\geq t\\}$ is ${\cal
F}_{t-1}$-measurable (see the proof of Proposition 6.6 for details), and the
fourth inequality follows from Lemma 6.4, used the upper bound on
$\mathbb{E}[T]$ from Lemma 6.5, and our choice for $\eta$. Selecting
$U=C\big{(}\sqrt{{\Gamma}H\tau}\nu+L\tau b\big{)}$ with $C>0$ sufficiently
large, we get $\mathbb{E}[T\|\nabla F(x^{\hat{t}})\|_{2}^{2}]/U\leq 1/4$,
concluding the proof. ∎

##  7 Boosting the Confidence for the Bias-Reduced Stochastic Gradient Method

We conclude by providing a boosting method to amplify the success probability
of our bias-reduced method. This boosting comes with a polylogarithmic in the
confidence computational overhead (due to parallel runs of the method), and
its accuracy also suffers additional mild polylogarithmic factors on the
confidence.

Algorithm 7 Boosting_Bias-Reduced_SGD$(S,\varepsilon,\delta,K)$

Dataset $S\sim{\cal D}^{n}$, $\varepsilon,\delta>0$ privacy parameters, number
of parallel runs $K>0$

for $k\in[K]$ do

Run Algorithm 6 with privacy budget $(\varepsilon/(K+1),\delta/(K+1))$, denote
$\hat{x}_{k}$ its output

end for

if $f(\cdot,z)$ convex then

Return $\hat{x}:=x_{\hat{k}}$, where
$\hat{k}=\displaystyle{\arg\min_{k\in[K]}}[F_{S}(\hat{x}_{k})+\xi_{k}]$,
$\xi_{k}\sim\mathsf{Lap}(\lambda)$, and $\lambda=\frac{B(K+1)}{n\varepsilon}$.

else

Return $\hat{x}=x_{\hat{k}}$, where
$\hat{k}=\displaystyle{\arg\min_{k\in[K]}}\big{[}\|\nabla
F_{S}(\hat{x}_{k})\|_{2}+\xi_{k}\big{]}$, $\xi_{k}\sim\mathsf{Lap}(\lambda)$,
and $\lambda=\frac{2L(K+1)}{n\varepsilon}$.

end if

######  Theorem 7.1.

Algorithm 7 is $(\varepsilon,\delta)$-DP. Let $0<\beta<1$. In the convex case,
Algorithm 7 attains excess risk

$\mathbb{P}\Big{[}F_{S}(\hat{x})-F_{S}(x^{\ast}(S))\leq\alpha\Big{]}\geq
1-\beta,$

where

$\textstyle\alpha\lesssim LD\frac{\sqrt{\ln
n}\big{[}s\ln(\frac{d}{s})\ln^{3}(\frac{\ln(1/\beta)}{\delta})\big{]}^{1/4}}{\sqrt{\varepsilon
n}}\sqrt{\ln\big{(}\frac{1}{\beta}\big{)}}+\frac{B}{n\varepsilon}\ln\big{(}\frac{1}{\beta}\big{)}\ln\big{(}\frac{\ln(1/\beta)}{\beta}\big{)}.$

On the other hand, in the nonconvex case,

$\mathbb{P}\Big{[}\|\nabla F_{S}(\hat{x})\|_{2}\leq\alpha\Big{]}\geq 1-\beta,$

where

$\textstyle\alpha\lesssim\big{(}[{\Gamma}H]^{1/4}\sqrt{L}[\ln(n)\ln(1/\delta)]^{1/4}+L\big{)}\frac{[s\ln(d/s)\ln(1/\delta)]^{1/8}}{[\varepsilon
n]^{1/4}}+\frac{L}{n\varepsilon}\ln\big{(}\frac{1}{\beta}\big{)}\ln\big{(}\frac{\ln(1/\beta)}{\beta}\big{)}.$

###### Proof.

The privacy of the algorithm is proved as follows. First, the parallel runs of
the algorithm are
$\big{(}\frac{K}{K+1}\varepsilon,\frac{K}{K+1}\delta\big{)}$-DP, by the
composition property of DP. Finally, by adaptive composition, $\hat{x}$ is
$(\varepsilon,\delta)$-DP: for this, notice that the sensitivity in the convex
case of $F_{S}$ is $B/n$, whereas in the nonconvex case is $2L/n$; therefore,
in either case the score function used for the report noisy max mechanism is
such that the addition of Laplace noise makes $\hat{x}$,
$\big{(}\frac{1}{K+1}\varepsilon,\frac{1}{K+1}\delta\big{)}$-DP, conditionally
on $(\hat{x}_{k})_{k\in[K]}$.

We proceed now to the accuracy analysis. We prove first the result for convex
losses, and later point out the differences in the nonconvex case. First, by
the subexponential tails of the Laplace distribution, we have that letting
${\cal E}:=\\{(\forall k\in[K]):\,|\xi_{k}|\leq\gamma\\}$,

$\mathbb{P}[{\cal E}^{c}]=\mathbb{P}\Big{[}(\exists
k\in[K])\,\,|\xi_{k}|>\gamma\Big{]}\leq
2K\exp\big{\\{}-\frac{\gamma}{\lambda}\big{\\}}=2K\exp\Big{\\{}-\frac{n\varepsilon\gamma}{B(K+1)}\Big{\\}}.$

Next, for any $\alpha>0$,

$\mathbb{P}\Big{[}F_{S}(\hat{x})-F_{S}(x^{\ast}(S))>\alpha\Big{]}\leq\mathbb{P}\Big{[}\big{\\{}F_{S}(\hat{x})-F_{S}(x^{\ast}({\cal
D}))>\alpha\big{\\}}\cap{\cal E}\Big{]}+\mathbb{P}[{\cal E}^{c}].$

Next we have

$\displaystyle\mathbb{P}\Big{[}\big{\\{}F_{S}(\hat{x})-F_{S}(x^{\ast}(S))>\alpha\big{\\}}\cap{\cal
E}\Big{]}\leq\mathbb{P}\Big{[}\big{\\{}F_{S}(\hat{x}_{\hat{k}})+\xi_{\hat{k}}-F_{S}(x^{\ast}(S))>\alpha-\gamma\big{\\}}\cap{\cal
E}\Big{]}$
$\displaystyle=\mathbb{P}\Big{[}\big{\\{}\min_{k\in[K]}\big{[}F_{S}(\hat{x}_{k})+\xi_{k}\big{]}-F_{S}(x^{\ast}(S))>\alpha-\gamma\big{\\}}\cap{\cal
E}\Big{]}$
$\displaystyle\leq\mathbb{P}\Big{[}\min_{k\in[K]}\big{[}F_{S}(\hat{x}_{k})-F_{S}(x^{\ast}(S))\big{]}>\alpha-2\gamma\Big{]}$
$\displaystyle\leq\Big{(}\mathbb{P}\Big{[}F_{S}(\hat{x}_{1})-F_{S}(x^{\ast}(S))>\alpha-2\gamma\Big{]}\Big{)}^{K},$

where in the last step we used the independence of the parallel runs.

If we let now $\alpha>0$ be such that $\alpha-2\gamma\geq U/\tau$, by Theorem
6.7, we have that

$\displaystyle\mathbb{P}\Big{[}F_{S}(\hat{x})-F_{S}(x^{\ast}({\cal
D}))>\alpha\Big{]}$ $\displaystyle\leq
2^{-K}+2K\exp\Big{\\{}-\frac{n\varepsilon\gamma}{B(K+1)}\Big{\\}}.$

The following conditions are sufficient to ensure that the right hand side
above is upper bounded by $\beta$:

$K=\log_{2}\big{(}\frac{2}{\beta}\big{)}\quad\mbox{ and
}\quad\gamma\geq(K+1)\frac{B}{n\varepsilon}\ln\big{(}\frac{4K}{\beta}\big{)}.$

This ultimately implies that we can choose

$\alpha=\frac{U}{\tau}+2\gamma\lesssim LD\frac{\sqrt{\ln
n}\big{[}s\ln(\frac{d}{s})\ln^{3}(\frac{\ln(1/\beta)}{\delta})\big{]}^{1/4}}{\sqrt{\varepsilon
n}}\sqrt{\ln\big{(}\frac{1}{\beta}\big{)}}+\frac{2B}{n\varepsilon}\Big{(}\log_{2}\big{(}\frac{2}{\beta}\big{)}+1\Big{)}\ln\big{(}\frac{4\log_{2}(2/\beta)}{\beta}\big{)}.$

For the nonconvex case, we need to replace $B$ by $2L$ in the Laplace
concentration bound. Further, we consider the event $\\{\|\nabla
F(\hat{x}_{k}\|_{2})>\alpha\\}$ (as opposed to the optimality gap event). This
implies that we need to set $\alpha>0$ such that
$\alpha-2\gamma\geq\sqrt{U/\tau}$, and appeal to Theorem 6.8. This leads to

$\mathbb{P}\Big{[}\|F_{S}(\hat{x})\|_{2}>\alpha\Big{]}\leq
2^{-K}+2K\exp\Big{\\{}-\frac{n\varepsilon\gamma}{2L(K+1)}\Big{\\}}.$

The conclusion is immediate. ∎

##  8 Acknowledgements

C.G.’s research was partially supported by INRIA Associate Teams project, ANID
FONDECYT 1210362 grant, ANID Anillo ACT210005 grant, and National Center for
Artificial Intelligence CENIA FB210017, Basal ANID.

## References

  * Amirkhanyan and Fontaine [2022] G. Amirkhanyan and B. Fontaine.  Building large scale recommenders using cloud TPUs, 2022.  https://cloud.google.com/blog/topics/developers-practitioners/building-large-scale-recommenders-using-cloud-tpus.
  * Arora et al. [2023] R. Arora, R. Bassily, T. González, C. A. Guzmán, M. Menart, and E. Ullah.  Faster rates of convergence to stationary points in differentially private optimization.  In _ICML_ , pages 1060–1092, 2023.
  * Asi et al. [2021a] H. Asi, Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford.  Stochastic bias-reduced gradient methods.  In _NeurIPS_ , 2021a.
  * Asi et al. [2021b] H. Asi, V. Feldman, T. Koren, and K. Talwar.  Private stochastic convex optimization: Optimal rates in L1 geometry.  In _ICML_ , pages 393–403, 2021b.
  * Asi et al. [2021c] H. Asi, D. Lévy, and J. C. Duchi.  Adapting to function difficulty and growth conditions in private optimization.  In _NeurIPS_ , pages 19069–19081, 2021c.
  * Bassily et al. [2014] R. Bassily, A. D. Smith, and A. Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _FOCS_ , pages 464–473, 2014.
  * Bassily et al. [2019] R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta.  Private stochastic convex optimization with optimal rates.  In _NeurIPS_ , 2019.
  * Bassily et al. [2021] R. Bassily, C. Guzmán, and A. Nandi.  Non-euclidean differentially private stochastic convex optimization.  In _Conference on Learning Theory_ , pages 474–499. PMLR, 2021.
  * Blanchet and Glynn [2015] J. H. Blanchet and P. W. Glynn.  Unbiased monte carlo for optimization and functions of expectations via multi-level randomization.  In _WSC_ , pages 3656–3667, 2015.
  * Bousquet and Elisseeff [2002] O. Bousquet and A. Elisseeff.  Stability and generalization.  _Journal of Machine Learning Research_ , 2:499–526, 2002\.
  * Bousquet et al. [2020] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy.  Sharper bounds for uniformly stable algorithms.  In _COLT_ , pages 610–626, 2020.
  * Bun et al. [2014] M. Bun, J. R. Ullman, and S. P. Vadhan.  Fingerprinting codes and the price of approximate differential privacy.  In _STOC_ , pages 1–10, 2014.
  * Bun et al. [2017] M. Bun, T. Steinke, and J. R. Ullman.  Make up your mind: The price of online queries in differential privacy.  In P. N. Klein, editor, _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19_ , pages 1306–1325. SIAM, 2017.  doi: 10.1137/1.9781611974782.85.  URL https://doi.org/10.1137/1.9781611974782.85.
  * Cai et al. [2020] T. T. Cai, Y. Wang, and L. Zhang.  The cost of privacy in generalized linear models: Algorithms and minimax lower bounds, 2020.
  * Cai et al. [2021] T. T. Cai, Y. Wang, and L. Zhang.  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  _The Annals of Statistics_ , 49(5):2825 – 2850, 2021.
  * Candes and Tao [2005] E. Candes and T. Tao.  Decoding by linear programming.  _TOIT_ , 51(12):4203–4215, 2005.
  * Candès and Davenport [2013] E. J. Candès and M. A. Davenport.  How well can we estimate a sparse vector?  _Applied and Computational Harmonic Analysis_ , 34(2):317–323, 2013.
  * Chaudhuri et al. [2011] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate.  Differentially private empirical risk minimization.  _JMLR_ , 12:1069–1109, 2011.
  * Dwork and Roth [2014] C. Dwork and A. Roth.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Feldman et al. [2020] V. Feldman, T. Koren, and K. Talwar.  Private stochastic convex optimization: optimal rates in linear time.  In _STOC_ , pages 439–449, 2020.
  * Ghazi et al. [2023] B. Ghazi, Y. Huang, P. Kamath, R. Kumar, P. Manurangsi, A. Sinha, and C. Zhang.  Sparsity-preserving differentially private training of large embedding models.  In _NeurIPS_ , 2023.
  * Gunny et al. [2019] A. Gunny, C. Garg, L. Dolgovs, and A. Subramaniam.  Accelerating wide & deep recommender inference on GPUs, 2019.  https://developer.nvidia.com/blog/accelerating-wide-deep-recommender-inference-on-gpus.
  * Hardt and Talwar [2010] M. Hardt and K. Talwar.  On the geometry of differential privacy.  In _STOC_ , pages 705–714, 2010.
  * Jain and Thakurta [2014] P. Jain and A. G. Thakurta.  (near) dimension independent risk bounds for differentially private learning.  In _ICML_ , pages 476–484, 2014.
  * Jouppi et al. [2023] N. Jouppi, G. Kurian, S. Li, P. Ma, R. Nagarajan, L. Nai, N. Patil, S. Subramanian, A. Swing, B. Towles, et al.  TPU v4: an optically reconfigurable supercomputer for machine learning with hardware support for embeddings.  In _ISCA_ , 2023.
  * Kairouz et al. [2021] P. Kairouz, M. R. Diaz, K. Rush, and A. Thakurta.  (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces.  In _Conference on Learning Theory_ , pages 2717–2746. PMLR, 2021\.
  * Kamath and Ullman [2020] G. Kamath and J. R. Ullman.  A primer on private statistics.  _CoRR_ , abs/2005.00010, 2020.  URL https://arxiv.org/abs/2005.00010.
  * Kamath et al. [2023] G. Kamath, A. Mouzakis, M. Regehr, V. Singhal, T. Steinke, and J. Ullman.  A bias-variance-privacy trilemma for statistical estimation, 2023.
  * McSherry and Talwar [2007] F. McSherry and K. Talwar.  Mechanism design via differential privacy.  In _FOCS_ , pages 94–103, 2007.
  * Nikolov and Tang [2023] A. Nikolov and H. Tang.  Gaussian noise is nearly instance optimal for private unbiased mean estimation.  _arXiv preprint arXiv:2301.13850_ , 2023.
  * Nikolov et al. [2013] A. Nikolov, K. Talwar, and L. Zhang.  The geometry of differential privacy: the sparse and approximate cases.  In _STOC_ , pages 351–360, 2013.
  * Pisier [1981] G. Pisier.  Remarques sur un résultat non publié de b. maurey.  _Séminaire Analyse fonctionnelle (dit_ , pages 1–12, 1981.
  * Shalev-Shwartz et al. [2009] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan.  Stochastic convex optimization.  In _COLT_ , 2009.
  * Steinke and Ullman [2016] T. Steinke and J. R. Ullman.  Between pure and approximate differential privacy.  _J. Priv. Confidentiality_ , 7(2), 2016.
  * Talwar et al. [2014] K. Talwar, A. Thakurta, and L. Zhang.  Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry.  _arXiv preprint arXiv:1411.5417_ , 2014.
  * Talwar et al. [2015] K. Talwar, A. Thakurta, and L. Zhang.  Nearly-optimal private lasso.  In _NIPS_ , pages 3025–3033, 2015.
  * Vershynin [2009] R. Vershynin.  On the role of sparsity in compressed sensing and random matrix theory, 2009.
  * Wang et al. [2022] Z. Wang, Y. Wei, M. Lee, M. Langer, F. Yu, J. Liu, S. Liu, D. G. Abel, X. Guo, J. Dong, et al.  Merlin hugeCTR: GPU-accelerated recommender system training and inference.  In _RecSys_ , 2022.
  * Whitehouse et al. [2023] J. Whitehouse, A. Ramdas, R. Rogers, and S. Wu.  Fully-adaptive composition in differential privacy.  In _ICML_ , pages 36990–37007, 2023.
  * Wojtaszczyk [2010] P. Wojtaszczyk.  Stability and instance optimality for Gaussian measurements in compressed sensing.  _Foundations of Computational Mathematics_ , 10:1–13, 2010\.
  * Zhang et al. [2021] H. Zhang, I. Mironov, and M. Hejazinia.  Wide network learning with differential privacy.  _CoRR_ , abs/2103.01294, 2021.
  * Zhou et al. [2021] Y. Zhou, S. Wu, and A. Banerjee.  Bypassing the ambient dimension: Private SGD with gradient subspace identification.  In _ICLR_ , 2021.

## Appendix

##  Appendix A Auxiliary Privacy Results

We note the existence of packing sets of sparse vectors (e.g., Vershynin [37],
Candès and Davenport [17]). Denote by $\mathcal{C}_{s}^{d}$ the set of all
$s$-sparse vectors in $\\{0,1/\sqrt{s}\\}^{d}$; note that
$\mathcal{C}_{s}^{d}\subseteq{\cal S}_{s}^{d}$.

######  Lemma A.1.

For all $s$ and $d$ such that $s\leq d/2$, there exists a subset ${\cal
P}\subseteq{\cal C}_{s}^{d}$ such that $|{\cal P}|\geq(d/s-1/2)^{s/2}$ and for
all $u,v\in{\cal P}$, it holds that $\|u-v\|_{2}\geq 1/\sqrt{2}$.

###### Proof.

This follows from a simple packing-based construction (see, e.g., [17]). There
are $\binom{d}{s}$ vectors in $\mathcal{C}_{s}^{d}$, and for each vector
$v\in\mathcal{C}_{s}^{d}$, there are at most $\binom{d}{\lfloor s/2\rfloor}$
many vectors $u\in\mathcal{C}_{s}^{d}$ such that $\|u-v\|_{0}\leq s/2$ and
hence $\|u-v\|_{2}\leq 1/\sqrt{2}$. Thus, we can greedily pick vectors to be
$C$, guaranteeing that all vectors $u,v\in\mathcal{C}_{s}^{d}$ satisfy
$\|u-v\|_{0}>s/2$, and have $|C|\geq\binom{d}{s}/\binom{d}{\lfloor
s/2\rfloor}\geq\left(\frac{d}{s}-\frac{1}{2}\right)^{s/2}$. ∎

For completeness, we provide a classical dataset bootstrapping argument used
for DP mean estimation lower bounds [6]. Whereas in the original reference
this bootstrapping is achieved by appending dummy vectors which mutually
cancel out with the goal of maintaining the structure of vectors, we simply
append zero vectors as dummies as we do not need to satisfy an exact sparsity
pattern.

######  Lemma A.2 (Dataset bootstrapping argument from [6]).

Suppose for some $n$, there exists a mechanism $\mathcal{A}$ such that for all
$S\in({\cal S}_{s}^{d})^{n}$, it holds with probability at least $1/2$ that
$\|\mathcal{A}(S)-\bar{z}(S)\|_{2}\leq C$, for some $C\geq 0$. Then for all
$n^{*}<n$, there exists a mechanism $\mathcal{A}^{\prime}$ such that for all
$S^{\prime}\in({\cal S}_{s}^{d})^{n^{*}}$, it holds with probability at least
$1/2$ that $\|\mathcal{A}(S^{\prime})-\bar{z}(S^{\prime})\|_{2}\leq
C\frac{n}{n^{*}}$. Furthermore, $\mathcal{A}^{\prime}$ satisfies the same
privacy guarantees as $\mathcal{A}$, namely if $\mathcal{A}$ is
$\varepsilon$-DP (or $(\varepsilon,\delta)$-DP), then so is
$\mathcal{A}^{\prime}$.

###### Proof.

Given mechanism $\mathcal{A}$, consider mechanism $\mathcal{A}^{\prime}$ that
for any dataset $S^{\prime}\in({\cal S}_{s}^{d})^{n^{*}}$, builds dataset $S$
by adding $n-n^{*}$ copies of $\mathbf{0}$ to $S^{\prime}$ and returns
$\frac{n}{n^{*}}\mathcal{A}(S)$. From the guarantees of $\mathcal{A}$, it
holds that $\mathbb{P}\left[\|\mathcal{A}(S)-\bar{z}(S)\|_{2}\leq
C\right]\geq\frac{1}{2}$. Since
$\mathcal{A}^{\prime}(S^{\prime})=\frac{n}{n^{*}}\mathcal{A}(S)$ and
$\bar{z}(S^{\prime})=\frac{n}{n^{*}}\bar{z}(S)$, it follows that

$\mathbb{P}\left[\|\mathcal{A}^{\prime}(S^{\prime})-\bar{z}(S^{\prime})\|_{2}\leq
C\frac{n}{n^{*}}\right]~{}\geq~{}\frac{1}{2}\,.$

Since $\mathcal{A}^{\prime}$ just applies $\mathcal{A}$ once, it follows that
$\mathcal{A}^{\prime}$ satisfies the same privacy guarantee as $\mathcal{A}$.
∎

Next we provide a generic reduction of existence of packing sets with pure-DP
mean estimation lower bounds. Note however that the lower bounds we state work
on the distributional sense.

######  Lemma A.3 (Packing-based mean estimation lower bound, adapted from
Hardt and Talwar [23], Bassily et al. [6]).

Let ${\cal P}\subseteq\mathbb{R}^{d}$ be an $\alpha_{0}$-packing set of
vectors with $|{\cal P}|=p$. Then, there exists a distribution $\mu$ over
${\cal P}^{n}$ that induces an $(\alpha,\rho)$-distributional lower bound for
$\varepsilon$-DP mean estimation with
$\alpha=\frac{\alpha_{0}}{2}\min\Big{\\{}1,\frac{\log(p/2)}{\varepsilon
n}\Big{\\}}$ and $\rho=1/2$.

###### Proof.

Let $n^{*}=\frac{\log(p/2)}{\varepsilon}$. First, consider the case where
$n<n^{*}$. We construct $p$ datasets $S_{1},\ldots S_{p}$ where $S_{l}$
consists of $n$ copies of $z_{l}$, and define
$\mu=\mbox{Unif}(\\{S_{1},\ldots,S_{p}\\})$. Note that for all $k\neq l$, it
holds that $\|\bar{z}(S_{k})-\bar{z}(S_{l})\|_{2}\geq\alpha_{0}$. Suppose
$\mu$ does not induce a distributional lower bound. Then there exists ${\cal
A}$ which is $\varepsilon$-DP and has $\ell_{2}$-accuracy better than
$\alpha_{0}/2$ w.p. at least $1/2$: this implies in particular that

$\mathbb{P}_{l\sim\mbox{\footnotesize
Unif}([p])}\left[\mathcal{A}(S_{l})\in{\cal
B}_{2}^{d}(z_{l}),{\textstyle\frac{\alpha_{0}}{2}})\right]\geq\frac{1}{2}.$

For all distinct $k$, $l$, the datasets $S_{k}$ and $S_{l}$ differ in all $n$
entries, and hence for any $\varepsilon$-DP mechanism $\mathcal{A}$, it holds
that $\mathbb{P}[\mathcal{A}(S_{l})\in{\cal
B}_{2}^{d}(z_{k},\frac{\alpha_{0}}{2})]\geq\frac{1}{2}e^{-\varepsilon n}$.
However, by construction, ${\cal B}_{2}^{d}(z_{l},\frac{\alpha_{0}}{2})$ are
pairwise disjoint. Hence,

$\displaystyle 1$ $\displaystyle\geq\sum_{k=1}^{p}\mathbb{P}_{S\sim\mu}[{\cal
A}(S)\in{\cal
B}_{2}^{d}(z_{k},\alpha_{0}/2)]=\sum_{j=1}^{p}\sum_{k=1}^{p}\mathbb{P}_{S\sim\mu}[{\cal
A}(S)\in{\cal B}_{2}^{d}(z_{k},\alpha_{0}/2)|S=z_{j}]\frac{1}{p}$
$\displaystyle\geq\frac{e^{-\varepsilon
n}}{p}\sum_{j=1}^{p}\sum_{k=1}^{p}\mathbb{P}_{S\sim\mu}[{\cal A}(S)\in{\cal
B}_{2}^{d}(z_{k},\alpha_{0}/2)|S=z_{k}]\geq\frac{e^{-\varepsilon n}p}{2}.$

Thus, we get that $n\geq\frac{\log(p/2)}{\varepsilon}$, which is a
contradiction since we assumed $n<n^{*}$. Hence, $\mu$ induces an
$(\alpha_{0}/2,1/2)$-distributional lower bound for $\varepsilon$-DP mean
estimation.
Next, consider the case where $n>n^{*}$. Then the previous argument together
with Lemma A.2 implies an $(\alpha,\rho)$-lower bounded, where
$\alpha=\frac{n^{*}}{2n}$ and $\rho=1/2$, as desired. ∎

We will make use of the following fully adaptive composition property of DP,
which informally states that for a prescribed privacy budget, a composition of
(adaptively chosen) mechanisms whose privacy parameters are predictable, if we
stop the algorithm before the (predictable) privacy budget is exhausted, the
result of the full transcript is DP.

######  Theorem A.4 ($(\varepsilon,\delta)$-DP Filter, [39]).

Suppose $(\mathcal{A}_{t})_{t\geq 0}$ is a sequence of algorithms such that,
for any $t\geq 0$, $\mathcal{A}_{t}$ is $(\varepsilon_{t},\delta_{t})$-DP,
conditionally on $(\mathcal{A}_{1:t-1})$ (in particular,
$(\varepsilon_{t},\delta_{t})_{t}$ is $({\cal A}_{t})_{t}$-predictable). Let
$\varepsilon>0$ and $\delta=\delta^{\prime}+\delta^{\prime\prime}$ be the
target privacy parameters such that
$\delta^{\prime}>0,\delta^{\prime\prime}\geq 0$. Let

$\varepsilon_{[0:t]}:=\sqrt{2\ln\big{(}\frac{1}{\delta^{\prime}}\big{)}\sum_{s=0}^{t}\varepsilon_{s}^{2}}+\frac{1}{2}\sum_{s=0}^{t}\varepsilon_{s}^{2},\quad\mbox{
and }\qquad\delta_{[0:t]}:=\sum_{s=0}^{t}\delta_{s},$

and define the stopping time

$T((\varepsilon_{t},\delta_{t})_{t}):=\inf\Big{\\{}t:\,\varepsilon<\varepsilon_{[0:t+1]}\Big{\\}}\wedge\inf\Big{\\{}t:\,\delta^{\prime\prime}<\delta_{[0:t+1]}\Big{\\}}.$

Then, the algorithm $\mathcal{A}_{0:T(\cdot)}(\cdot)$ is
$(\varepsilon,\delta)$-DP, where
$T(x)=T\big{(}(\varepsilon_{t}(x),\delta_{t}(x)\big{)}_{t\geq 0}$.

##  Appendix B Analysis of Biased SGD

Given the heavy-tailed nature of our estimators, our guarantees for a single
run of SGD with bias-reduced first-order oracles only yields in-expectation
guarantees. Here we prove pathwise bounds that lead to such in-expectation
results.

###  B.1 Excess Empirical Risk: Convex Case

First, we provide a path-wise guarantee for a run of SGD with a biased oracle.
Importantly, this guarantee is made of a method which runs for a random number
of steps.

######  Proposition B.1.

Let $({\cal F}_{t})_{t}$ be the natural filtration, and $T$ be a random time.
Let $(x^{t})_{t}$ be the trajectory of projected SGD with deterministic
stepsize sequence $(\eta_{t})_{t}$, and (biased) stochastic first-order oracle
${\cal G}$ for a given function $F$. If $x^{\ast}\in\arg\min\\{F(x):x\in{\cal
X}\\}$, then the following event holds almost surely

$\sum_{t=0}^{T}[F(x^{t})-F(x^{\ast})]\leq\frac{1}{2\eta_{t}}\|x^{0}-x^{\ast}\|^{2}+\sum_{t=0}^{T}\big{[}\frac{\eta_{t}}{2}\|{\cal
G}(x^{t})\|^{2}+\langle\nabla F(x^{t})-{\cal
G}(x^{t}),x^{t}-x^{\ast}\rangle\big{]}.$

###### Proof.

By convexity

$\displaystyle F(x^{t})-F(x^{\ast})$ $\displaystyle\leq\langle\nabla
F(x^{t}),x^{t}-x^{\ast}\rangle=\underbrace{\langle\nabla F(x^{t})-{\cal
G}(x^{t}),x^{t}-x^{\ast}\rangle}_{:=b_{t}}+\langle{\cal
G}(x^{t}),x^{t}-x^{\ast}\rangle$ $\displaystyle\leq b_{t}+\langle{\cal
G}(x^{t}),x^{t}-x^{t+1}\rangle+\langle{\cal G}(x^{t}),x^{t+1}-x^{\ast}\rangle$
$\displaystyle\leq b_{t}+\frac{\eta_{t}}{2}\|{\cal
G}(x^{t})\|^{2}+\frac{1}{2\eta_{t}}\|x^{t}-x^{t+1}\|^{2}+\langle\nabla{\cal
G}(x^{t}),x^{t+1}-x^{\ast}\rangle$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{\leq}}b_{t}+\frac{\eta_{t}}{2}\|{\cal
G}(x^{t})\|^{2}+\frac{1}{2\eta_{t}}\|x^{t}-x^{t+1}\|^{2}+\frac{1}{\eta_{t}}\langle
x^{t+1}-x^{t},x^{\ast}-x^{t+1}\rangle$
$\displaystyle=b_{t}+\frac{\eta_{t}}{2}\|{\cal
G}(x^{t})\|^{2}+\frac{1}{2\eta_{t}}\|x^{t}-x^{\ast}\|^{2}-\frac{1}{2\eta_{t}}\|x^{t+1}-x^{\ast}\|^{2},$

where the second inequality follows by the Young inequality, and step $(\ast)$
we used the optimality conditions of the projected SGD step:

$\langle\eta_{t}{\cal G}(x^{t})+[x^{t+1}-x^{t}],x-x^{t+1}\rangle\geq
0\quad(\forall x\in{\cal X}).$

Therefore, summing up these inequalities, we obtain

$\displaystyle\sum_{t=0}^{T}[F(x^{t})-F(x^{\ast})]\leq\frac{1}{2\eta_{0}}\|x^{0}-x^{\ast}\|^{2}+\sum_{t=0}^{T}\Big{[}\frac{\eta_{t}}{2}\|{\cal
G}(x^{t})\|^{2}+b_{t}\Big{]}.$

Plugging in the definition of $b_{t}$ proves the result. ∎

###  B.2 Stationary Points: Nonconvex Case

######  Proposition B.2.

Let $F$ satisfy (A.6), and let ${\cal G}$ be a biased first-order stochastic
oracle for $F$. Let $(x^{t})_{t}$ be the trajectory of SGD with oracle ${\cal
G}$, constant stepsize $0<\eta\leq 1/[2H]$, and initialization $x^{0}$ such
that $F(x^{0})-\min_{x\in\mathbb{R}^{d}}F(x)\leq{\Gamma}$. Let $T$ be a random
time. Then the following event holds almost surely

$\sum_{t=0}^{T}\|\nabla F(x^{t})\|_{2}^{2}\leq\frac{{\Gamma}}{\eta}+\frac{\eta
H}{2}\sum_{t=0}^{T}\|{\cal G}(x^{t})\|_{2}^{2}-\sum_{t=0}^{T}\langle\nabla
F(x^{t}),{\cal G}(x^{t})-\nabla F(x^{t})\rangle$

###### Proof.

By smoothness of $f$, we have

$\displaystyle F(x^{t+1})-F(x^{t})$ $\displaystyle\leq-\eta\langle\nabla
F(x^{t}),{\cal G}(x^{t})\rangle+\frac{\eta^{2}H}{2}\|{\cal
G}(x^{t})\|_{2}^{2}$ $\displaystyle\leq-\eta\|\nabla
F(x^{t})\|_{2}^{2}-\eta\langle\nabla F(x^{t}),{\cal G}(x^{t})-\nabla
F(x^{t})\rangle+\frac{\eta^{2}H}{2}\|{\cal G}(x^{t})\|_{2}^{2}.$

Therefore,

$\displaystyle\sum_{t=0}^{T}\|\nabla F(x^{t})\|_{2}^{2}$
$\displaystyle\leq\frac{F(x^{0})-F(x^{T+1})}{\eta}-\sum_{t=0}^{T}\langle\nabla
F(x^{t}),{\cal G}(x^{t})-\nabla F(x^{t})\rangle+\frac{\eta
H}{2}\sum_{t=0}^{T}\|{\cal G}(x^{t})\|_{2}^{2}$
$\displaystyle\leq\frac{{\Gamma}}{\eta}-\sum_{t=0}^{T}\langle\nabla
F(x^{t}),{\cal G}(x^{t})-\nabla F(x^{t})\rangle+\frac{\eta
H}{2}\sum_{t=0}^{T}\|{\cal G}(x^{t})\|_{2}^{2}.$

∎