Lower Bounds for Differentially Private ERM: Unconstrained and Non-Euclidean
Authors: Zhou Lu
Daogao Liu
Venue: Submitted to ICLR 2023 (2023)

Abstract: We consider the lower bounds of differentially private empirical risk minimization (DP-ERM) for convex functions in both constrained and unconstrained cases concerning the general $\ell_p$ norm beyond the $\ell_2$ norm considered by most of the previous works.

We provide a simple black-box reduction approach that can generalize lower bounds in constrained to unconstrained cases.
Moreover, for $(\epsilon,\delta)$-DP, we achieve the optimal $\Omega(\frac{\sqrt{d \log(1/\delta)}}{\epsilon n})$ lower bounds for both constrained and unconstrained cases and any $\ell_p$ geometry where $p\geq 1$ by considering $\ell_1$ loss over the $\ell_{\infty}$ ball.

Under review as a conference paper at ICLR 2023
LOWER BOUNDS FOR DIFFERENTIALLY PRIVATE ERM: UNCONSTRAINED AND NON-EUCLIDEAN
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the lower bounds differentially private empirical risk minimization (DP-ERM) for convex funetions in both constrained and unconstrained cases concerning the general &p norm beyond the & norm considered by most the previous works.
We provide simple black-box reduction approach that can generalize lower bounds in constrained to unconstrained cases. Moreover, for (c, 5D,P) we achieve the
(og(/)))) lower bounds for both constrained and unconstrained cases en
optimal Q2(
and any Ep geometry where p 2 1 by considering & loss over the Eoo ball.
INTRODUCTION
Since the seminal work of Dwork al. (2006), differential privacy (DP), defined below, has become the standard and rigorous notion of privacy guarantee for machine learning algorithms.
Definition 1.1 (Differential privacy). A randomized mechanism M is (e, didiifferenyially private for any event O e Range(MM) and for any neighboring databases D and D' that differ by a single data element, one has
Pr(M(D) O) S Pr(M(()) 0] +
Among the rich literature on DP, many fundamental problems are based on empirical risk minimization (ERM), and DP-ERN becomes one of the most well-studied problems in the DP community. See
e.g., Chaudhuri & Monteleoni (2008); Rubinstein et al. (2009): Chaudhuri et al. (211)) Kifer et al.
(2012)
al. (2013):) Bassily al. (2014); Jain & Thakurta (2014); Talwar al. (2015):
Kasiviswanathan & Jin (201)) ( Fukuchi et al. (2017 7): | Wu et al. (2017 Zhang et al. (2017
Wang
al. (2017); [yengar al. (2019); Bassily et (2020); Kulkarni al. (202) Asi
(222)
Bassily y et al. (202 lb); Wang et al. (2021) Bassily et al. (2021a): Gopi et al. (2022); Arora et al. (2022): Ganesh
(2022).
In DP-ERM, we are given family convex functions where each function {(-; is defined on convex set K. C Rd. and data-set D {ø1, ]n to design differentially private algorithm that can minimize the loss function
n
L(0,D)
((0
and the value [00 mingrek T.(O;; D) is called the excess empirical loss with respect to solution 0, measuring how it compares with the best solution in K.
DP-ERM in the constrained case and Euclidean geometry (with respect to & norm) was studied first, well-studied, and most of the previous literature belongs to this case. More specifically, the Euclidean constrained case considers convex loss functions defined on a bounded convex set C C Rd assuming the functions are I-Lipschitz over the convex set of diameter I with respect to the & norm. For pure-DP DP (i.e. (c, D)DD the seminal work Bassily et al. 2014) achieved tight upper and lower bounds e d As for approximate- DP (i.c. (D when > 0), previous works Bassily et al.
When 5 >>0 0, may refer to it as approximate- DP, and we name the particular case when 5 0 pu sometimes.

---

Under review as a conference paper at ICLR 2023
20 Steinke & Ullman (2016): Wang et al. (2017): Bassily et al. (2019) achieved the tight bound
(
en
DP-ERM in the unconstrained case was neglected before and gathered people's s attention recently.
Jain & Thakurta 2014); Song et al. (2021) found a tight bound Ó( vrrak) for minimizing the excess empiniaal risk of Generalized Linear Models (GLMs, see Definition A. in Appendix) in the unconstrained case and evaded the curse dimensionality, where rank is the rank of the feature matrix in the GLM problem. As comparison, the tight bound é vdd holds for the constrained DP-GLM, even for the overparameterized case when rank I n < d. The dimension-independeer result is intriguing, as modern machine learning models are usually huge, with millions to billions of parameters (dimensions).
A natural question arises whether one can get similar dimension dimension-independenn results for a more general family of functions beyond GLMs. Unfortunately, Asi et al. (2021) provided a negative answer and gave an SD( a lower bound for some general convex functions. Their method chooses appropriate objective functions and utilizes one-way marginals, but the extra logarithmic term their bound seems nontrivial to remove in the unconstrained case.
Another aspect is DP-ERM in non-Euclidean settings. Most previous works in the literature consider the constrained Euclidean setting where the convex domain and (sub)gradients of objective functions have bounded f2 norms, and DP-ERM concerning the general lp norm is much less well-understood. Motivated by the importance and wide applications of Non-Euulideea settings, some previous works Talwar al. (2015); Asi et al. (202T); [Bassily et al. (2021b) analyzed constrained DP-ERM with respect to the general Pp norm with many exciting results, and there is still room for improvement in
many regimes.
Article
Constrained?
Pp
Loss Function
Pure DP
Approximate DP
Bassily al.
2014
constrained
p=
GLM
Q d
Q vd
2 V Log (1/55) (1/5)
Steinke & Ullman (0166)
constrained
82
GLM
N/A
Song
22021
unconstrained both
p
GLM
N/A
Q /rank Fyr Vdd
Asi ct al.
2021)
p p=
general
N/A
? iou loy
a 1) log(1/6)
Bassily et al.
2021b
constrained
<< 1<
GLM
N/A
2 v (olog(1/))
Ours
both
5.p50000
general
2
Table 1: Comparison of lower bounds for private convex ERM. One easily extend our lower bounds in the unconstrained case to the constrained case. The lower bound Sf et al. (2021) is weaker than ours in the important over-parameteriize d >>>>>> setting, as rank S min((n,)
1.1 OUR CONTRIBUTIONS
This paper considers the lower bounds for DP-ERM under unconstrained and/or non-euclidean settings. We summarize our main results as follows:
We propose a black-box reduction approach, which directly generalizes the lower bounds in constrained cases to the unconstrained case. Such method is beneficial for its simplicity. Nearly all exiting lower bounds in the constrained case can be extended to the unconstrained case directly, and any new progress the constrained case be of immediate use due to its black-box nature.
We achieve 22( (d1gg(1/)) lower bounds for both constrained and unconstrained cases and any lp geometry for p 2 1 at the same time by considering & loss over the foc ball. This bound improves previous results, exactly matches the upper bounds for < < S 2 and obtains novel bounds for >
en
Thhe current best upper bound is (mmnn(log d, 1. (log(11/6) for S p S 2 and O 4'-1/p [og(1/6)
p-1
for < p
2

---

Under review as a conference paper at ICLR 2023
As example of the application of our simple reduction approach, will show how to get the Q d lower bound in the unconstrained pure-DP DP case from the result in constrained case Bassily et 20144), which is the first lower bound in this setting to the best of our knowledge. This reduction also demonstrates that evading the curse of dimensionality is impossible based on existing dimension-dependenn lower bounds, even in the (arguably less complicated) unconstrained case.
1.2 RELATED WORK
Previous studies on DP-ERM primarily focus on the constrained setting. The unconstrained case recently attracted people's interest because Jain & Thakurta (2014); Song al. (202I) found an O( Vrank
upper bound for minimizing the excess risk of GLMs, which evades the curse of dimen- sionality. It has been known that the constrained condition plays crucial role in achieving dimension independence, as pointed out by the ? ((v lower bound in Bassily et al. (204)), particularly for min- imizing constrained GLMs for the case when "rank S n d". There are fundamental differences direction.
between constrained and unconstrained cases, and analyzing the unconstrained case is an important
Most existing lower bounds of DP-ERM use GLM functions. For example, the objective function used in Bassily et al. (2014) is a linear function 8(0; =) (0, 2) which cannot be applied in the unconstrained case; otherwise, the loss value would be infinite. Considering this limitation, [Song al. (202)) adopted the objective functions {(0; 2) [00 æ²) y/. They transferred the problem of
minimizing GLM to estimating the mean of set of vectors, then got the lower bound by tools from
the coding theory.
Kairouz et al. 2020); Zhou et al. (2020) considered how to evade the curse of dimensionality for more general functions beyond GLMs with public data, which serves to identify low-rank subspace similar to Song et al. (2021) in spirit. DP Stochastic Convex Optimization (SCO) Feldman et al. (2020); Bassily et al.) (200)) 2019); Kulkarni et al. (2021): et al. (2021); Bassily et al. (202 is another important and fundamental problem which is closely related DP-ERM. Roughly speaking, in the SCO, the objective is to minimize the function (E<:p(((;:)) for some underlying distribution P, which requires analyses on the generalization ability of the algorithms. The tight bound of DP-SCO is usually the maximum among the informational lower bound on (non-private) SCO and the lower bound DP-ERM, and improved lower bounds DP-ERM can also benefit research on DP-SCO.
2 PRELIMINARY
We introduce the prior background knowledge required in the rest of the paper. Additional background knowledge, such as the definition of GLM, can be found in the appendix. We start with defining Lipschitz functions.
Definition 2.1 (G-Lipschitz Continuity). A function f K. + IR is G-Lipschitz continuous with respect f, geometry if for all 0 K,, one has:
If(0) S G -G)00 0'11p-
(2)
2.1 PROPERTIES DIFFERENTIAL PRIVACY
In this subsection, we introduce several very basic properties of differential privacy without proving them (refer Dwork al. (2014) for details).
Proposition 2.2 (Group privacy). If M: ::MAM x + +Y is (e, d)-iifferentially private mechanism, then for all pairs of datasets x, x' X", then (x)),((()) are ) indd)"""dditttnuushhhhb when x, x!
differs on at most k locations.
Proposition 2.3 (Post processing). If :: X + +Y is (c, 8) diffferenntill private and A: Y +
any randomized function, then A o M: X Z is also (c -ifffeerrnty private.
3

---

Under review as a conference paper at ICLR 2023
3 REDUCTION APPROACH
In this section, we prove a general black-box reduction theorem, which can directly generalize the lower bounds on DP-ERM in the constrained case to the unconstrained case. As an application, we give example for using our reduction approach to get pure-DP lower bound in the unconstrained case from the constrained case (Bsssily et al. (2014).
To begin with, introduce the following lemma from Cobzas & Mustata (1978) which gives Lipschitz extension of any convex Lipschitz function over some bounded convex set to the whole domain Rdd
Lemma 3.1 (Theorem 1 in Cobzas & Mustata (1978), Let f be convex function which is 17- Lipschitz w.r.t. l2 and defined on a convex bounded set K C IR. Define an auxiliary function (z) as:
9o = f(y) + a/l vll2.8 y E K, Ve E ER.
Then consider the function f R + R defined as f(x) = min (x)). We know f ny- -i-iichhitzz w.r.t. lg on Edd and f(x) = f(x) for any x E K.
For any E R we define 1xx == arg mingek 1|2- yl22. It is well-known in the convex analysis, that for a compact convex set and any point y 12 the the set {ar KC ||>-y1l2 < 1|2-, Vz XC * x} is always non-empty and singleton Hazan (2019) In short, to prove lower bounds for the unconstrained case, one can extend the loss function the constrained domain Rd with an important observation such convex extension: the loss L(0; D) at point O does not increase after projecting the convex domain KC, i.e. L(0; D) 2 (0); ; D). One can derive this property from the Pythagorean Theorem (Lemma 3.2) for any convex set by combining with the particular structure of the extension.
Lemma 3.2 (Pythagorean Theorem for convex set), Letting K. C. IRd be a convex set, y E IRd and == == (y), then for any E I. we have:
| 2112 S 11y -2112-
(4)
In the unconstrained case, we usually assume a public prior knowledge on C' where C 2 110 - 0" ||2. to is the public initial point and 0* is the optimal solution to T(::D) over Rd.
To proceed, we first assume some lower bound in the constrained case, which we use to reduce. The definition below defines witness function for any lower bound in the constrained case, for example in Bassily et al. (2014) the (witness) loss function simply linear and the lower bound is roughly Q(min (1, xd) ))
Definition 3.3. Let n, d be large enough, 0 < 8 < and O. We say functions é is a witness to the lower bound function f. if for any (e, 0)-DP algorithm, there exist a convex set IC C Rd of diameter C, family of G-Lipschitz convex functions {(0: =) defined on I. w.r.t. lg, dataset D of size n, such that with probability at least 1/2 (over the random coins of the algorithm),
L(Oprio (uprio;D)
min L(0:D) (d G)C)), OeK
where L(O,D)- = = -. ((0;z) 2.) and @eriv E K' is the output of the algorithm.
The function f can be any lower bound in the constrained case with dependence on the parameters, and is the loss function used construct the lower bound. We use the Lipschitz extension mentioned above to define our loss function in the unconstrained case, i.c.,
ε(0; z) min E(v; 2) + GIl0 w112
(5)
BER
which is convex, G-Lipschitz and equal to E(0; =) when 0 E K. by Lemma 3.1 Our intuition is simple: grrin lies in IC, then we are done by using the witness function and lower bound from Definition If not, the projection of gariv to K. should lead to smaller loss. However, the projected point cannot have a minimal loss due to the lower bound in Definition 3.3. let alone gprie itself. We have the following theorem that achieves the general reduction approach in the unconstrained setting:
3.3
4

---

Under review as a conference paper at ICLR 2023
Theorem 3.4. Assume f are the witness function and lower bound as in Definition 3.3 For any (c, (CD algorithm and any initial point fg E RR, there exist a family of G-Lipschitz convex functions 2) Rd - I being the È from Definition 3.3 dataset 'D of size n and the same function f, such that with probability at least 1/2 (over the random coins of the algorithm)
L(prrio D) L(0"; D) = ,,,,
(6)
where D(0;D)= = + &E El0; 21) is the ERM objective function, = arg mingend L(0;D),
C2 100 - 8 2l2 and geriv is the output of the algorithm.
Proof. Without loss of generality, let K. {0 1 foll2 S SC} be the Eg ball around 6g. let {(;: =) be the convex functions used in Definition 3.3 and as mentioned we can find our loss functions 2) =
minyex fyy: z) + G v/12. As 0 E K. we know that
L(O"; D) min L(B:D)
BEK
Denote gorie- = Hx (Bprio) the projected point of geriv to K. Because post-processing keeps privacy, outputting @eriv is also (e, 6)-DP. By Definition 3.3 we have
[@prie, D) min L(0; D) = ((f(d,,,,
(8)
0
If Gerio- gprie, which means Oprin E K, then because ε(0: 2) is equal f(0; 2) for any 0 KC and 2, one has [.pprro D) T. (ppriv; D) (0prie
If Ôpriv o Oeriv which means Oprie & K, then since {(1;z) =) is G-Lipschitz, for any 2, we have that (denoting y" = arg minyek ((y; - @rriv y1l2):
E(pprio; 2) = min E(y: 2) + Gl| @rrio y/12
wεk:
=()" + Gi 11" 1|2
((y":2) + G Gilgeriv v²112
min (yr;) + Gll 1/12 yER'
((0prin; 2);
where the third line is by the Pythagorean Theorem for the convex set, see Lemma 3.2 We have [(prrio, D) 2 L(ōeriv; D) L(pprie, D). In a word, we get
( D) N L(Qrrie, D) L(pprio; :D).
(9)
Combining Equation
and together, we have that i(prriv, D) - i D)
i( :D min L(0; D)
2 I(0prie D) min L D) 2 22ff(d.n,,,ō6....))
3.1 EXAMPLE FOR PURE-DP
This subsection gives concrete example of the reduction method in the pure-DP setting. In the construction of lower bounds for constrained DP-ERM in Bassily et (2014), they chose the linear function E(0; 2) (0, 2) as the objective function, which is not applicable in the unconstrained setting because could decrease to negative infinity. Instead, we extend the linear loss in unit & ball to the whole Rdd while preserving its Lipschitzness and convexity. We use such an extension to define our loss function in the unconstrained case. Namely, we define
E(0; z) = min - (y,, 2) + 1|0 v||
(10)
llellag1
5

---

Under review as a conference paper at ICLR 2023
for all 0, in the unit & ball, which is convex, 1-Lipschitz and equal to -0,, when ||0||2 1 according to Lemma 3.1 Specifically, it's easy to verify that E(0; 0) = max ||0122 11. When || = I, one has
((0;2) 2 min - (y,, 1,
(11)
where the equation holds if and only if 0 = 2.
For any dataset D {21, 2n we define L(O;D) 11 - E(O; E(O)2.). We need the following lemma from Bassily et al. (2014) to prove the lower bound. The proof is similar to that of Lemma 5, in Bassily al. 2014), except that we change the construction by adding points O (the all-zero dimensional vector) as our dummy points. For completeness, we include it here.
Lemma 3.5 (Part-One of Lemma 5.1 in Bassily et (2014) with slight modifications). Let n, d 2 and > 0. There is a number n² = (1min((1, 2) such that for any e-differentially private algorithm A, there is dataset DD = {zi,....Z,, C va 322" U {0} with II Ei=1 2sl12 = n² such that, with probability least 1/2 (taken over the algorithm random coins), we have
d
|A(D) - ((D)l2 Q1min(1, - )),
(12)
TEE
where ((D)
Σ
Lemma 3.5 basically says that for any c-PP algorithm, it's impossible to for it to estimate the
average of some dataset 2j...., 2n with accuracy o(min(1, ))). Using the loss functions defined in Equation [00.. Lemma 3.5 and our reduction theorem 3.4 have the following theorem, whose proof can be found in the appendix.
Theorem 3.6 (Lower bound for e-differentially private algorithms). Let n, d be large enough and c <>> For every C-differentially private algorithu with output garie E R&, there is a dataset 2n) Va val {0} such that, with probability at least 1/2 (over the algorithm random coins), we must have that
D f21 .5.,......
L(gerie; min L(0; D) = (min(1, )) BER"
(13)
4 IMPROVED BOUNDS
In this section, we consider lower bounds for approximate DP. We aim to improve previous results in two ways: to tighten the previous lower bounds and extend this bound to any non-euclidean geometry and the unconstrained case. We make the assumption that (n)(n) < < o(1/n). The assumption on 6 is common in the literature, for example, in Steinnke & Ullman 2016).
4.1 BACKGROUND
We briefly introduce previous lower bounds for constrained DP-ERM and how changing the loss to be & and domain be foo balls generalizes the lower bounds the unconstrained non-euclidean case.
As shown in Table Bassily al. (2014) demonstrates a lower bound 22 Ld for the constrained
ne case. They choose K. to be the unit Eg ball and the loss function be linear function {(;) 2) - (0, z).
The empirical loss function is L(0: D) - (8: Σ 2/n) with minimizer 6*
5
-= 2 Hence
21
for any solution 0, one has I(O0:1 D) D) EE lll (1 (9)0 > ll 1. | 0" 11.
Therefore one can reduce the lower bound for DP-ERM to the lower bound for estimating the mean of dataset, for example, the following lemma:
Lemma 4.1 (Part-Two of Lemma 5.1 in Bassily et al. (2014). Let e > 0, o(1/n) and M (miin(n, vd/c)). for any (c, DDP algorithm A, there is a dataset D {21,-.. 2n S {-1/Vd, 1/I/Vd,1/Vdl 1/Vd)* with || E== 2 E [M - M + 1] such that with probability at least 1/3 (taken
over A's random coins), have
[IA(D) ( 222 2mmin(1, Vd en
)
where ((D) n Σr 2i.

---

Under review as a conference paper at ICLR 2023
In word, Bassily al. (2014) uses linear functions as the objective functions and reduces the lower bound on DP-ERM to the lower bound on estimating the mean. Steinke & Ullman (2016) improved the lower bound by logarithmic factor by using the group privacy technique.
The previous framework fails in the unconstrained and non non-euclidean case for two reasons. First, they rely the lz ball the domain, which lacks the generalizability to the general lp norm. Second, to generalize the lower bound to the unconstrained case, linear functions are no longer appropriate to be loss functions, as they can take minus infinity values and do not have global minimum.
To address these concerns, we consider our problem in an &oo ball and choose the loss function to be ((0;=) =) ||0- 2||1- Formally, the loss function used is the following:
E(B; 2) 10 2||1, 0 R { {-1, 1)
The convex domain is is the Lo unit ball. For any data-set = {21 Jn we define
L(0; D) = D (();2,)
110 24 111
D
One main reason for our choice that & and for are the "strongest" norms for loss and domain, respectively, implying lower bounds for general lp geometry by the Holder inequality. Moreover, unlike linear functions, the & loss function can be generalized to the unconstrained case directly. suffices to figure out how to prove lower bounds for this constrained setting (with & loss functions in an loo unit ball).
Looking into previous lower bounds, such as Bassily et al. (2044) and Steinke & Ullman (2016), one finds that the core idea is two-step: reduce the lower bound of the DP-ERM to the lower bound of mean estimation first, then build the mean estimation by coding theory, particularly the fingerprinting code to be discussed later. In our case, we can not directly reduce the lower bound the DP-ERM to the lower bound of mean estimation due to the loss function and domain change. In particular, large mean estimation error does not necessarily imply a large empirical risk.
Consider simple example. Recall that want minimize L(0; (D) E.= e(0: 24 /n over the foc unit ball AC, where f(0) 2) ||e =1|2 and each E {0, 1)d the set up before. If n Σ" 2 1 where 1 means the all-one vector, then we know L(0;D) is a constant function, equaling to d/2 for any 0 K. In this example, for bad estimator Ohad, even if 01aaa - zi 2112 is large, it can still be minimizer to the loss function, i.e., L(Obad: D) minsek L(O:D)- =0. 0.
4.2 FINGERPRINTING CODES
Fingerprinting code was first introduced in Boneh Shaw (1998a). developed and frequently used to
demonstrate lower bounds in the DP community Bun et al. (2018): Steinke & Ullman (2016) 2015).
To overcome the challenge discussed before, we slightly modify the definition of the fingerprinting code used in this work.
Definition 4.2 lloss Fingerprinting Code). A y-complete, 7-sound, a-robust -loss fingerprinting
code for users with length d is a pair of random variables D {0, 1]mxd and Trace: [o, 1 + 2 such that the following hold:
Completeness: For any fixed M: {0, 1jxdd > [0,
Pr LMM()):)) min L(0;D) s ad (Trace(M(D)) 0) s 5.
Soundness:
For any E [n] and fixed M (0, 1d + 1]
Pr[i E
where D= denotes D with the ith row replaced by some fixed element of (0,
Definition 4.2 is similar to the one in Steinke & Ullman (016) (See Definition 3.2 in Steinke & Ullman 2016 ) except that their requirement of completeness is Pr[[]-M(D) q(D)] < ad
7

---

Under review as a conference paper at ICLR 2023
Trace(M((D)) = ك y. As discussed before, they the fingerprinting code in their version to build lower bound on the mean estimation, while we modify the definition and build a lower bound on the DP-ERM under our set-up.
Following the optimal fingerprinting construction Tardos 2008), and subsequent works Bun et al. (2018) Bassily al. (2014), we have the following result demonstrating the existence of fingerprinting code in our version.
Lemma 4.3. For every n 1, and 7 (0, 1]. there exists a "-complete, y-sound, 1/150-robust llososs fingerprinting code for n users with length where
d= On² 1og(1/7).
4.3 MAIN RESULT IN EUCLIDEAN GEOMETRY
Similar to Bun et al. 2018), we have the following standard lemma, which allows us to reduce any e < 1 to the I case without losing generality. The proof based on the well-known 'secrecy of the sample' lemma from Kasiviswanathan et al. (2011).
Lemma 4.4. For 0 < < condition has sample complexity n² for algorithms with (1, [[/n))) differential privacy (n" is the smallest sample size that there exists an
private algorithm A which satisfies Q), if and only if it also has sample complexity O(n" /e) for algorithms with (c, ((1/n)) -nifffrrrrenti privacy.
We apply the group privacy technique in Steinke & Ullman (206)), which needs the following technical lemma:
Lemma 4.5. Let n,k be two large positive integers such that k < n/1000. Let ni [n/k]. Let 21, 2ny be ng numbers where 2, E {0, 1, 1/2] for all E [nx]. For any real value q E [0, 11, if copy each z k times, and append knn '0" to get numbers " Ewo then we have
a 2/|/mK
Σ la 21/m| S 3k/n.
Proof. Without loss of generality, we can assume 2 2 = 1 = 2/65 = 2; and
kn
2ku+t2
z/1 = O. With this observation, we know
z l1/
z/1/nl
t=1
l - z (1/1/ k/n) Σ g/nl
i=n kn
l 2/ (1/mk= k//)] +
Σ
g/nl
1=1
-=n-km++1
k k) k/n S 3k/n.
no k/nn 1
This section's 's main result is the following theorem, which modifies and generalizes the techniques in Steinke & Ullman (006)) Bassily et al. (2014) to reach tighter bound for the unconstrained case. Theorem 4.6 (Lower bound for (e, didffferrent private algorithms). Let n, be large enough and 1 2 e 0,2-0(m 8 < o(1/n). For every (e, 5) -differrent private algorithm with outpul gpriv E Rd, there is data-set D = {Z1..., 2n } C {0, 1)ah U ( such that
LOLriri D) - L(O"; D) = Mminn(1, Volog(1/0) )GC)
(14)
T1
where E is G-Lipschitz w.E.t & geometry, 8r is minimizer of L(0; D), and C = v is the diameter of K. w.r.. E2 geometry, where K. is the unit Loo ball containing all possible true minimizers and differs from its usual definition in the constrained setting.
8

---

Under review as a conference paper at ICLR 2023
Remark 4.7. The dependence parameters GC makes sense. For example, can scale the loss function to be Aar; z) ||az 2||2 for some constant (0, 1), which decreases Lipschitz constant G but increases the diameter C' (we should choose I. to contain all possible minimizes).
This bound improves a log factor over [asssly et al. (0144) and can be directly extended to the constrained bounded setting, by setting the constrained domain to be the unit loo ball.
4.4 EXTENSION TO
GEOMETRY
We illustrate the power of our construction in Theorem 4.6 by showing that the same bound holds for any lp geometry where p > in the constrained setting, and the bound tight for all < improving/gennrraiiing existing results in Asi et al. (2021): Bassily et al. (2021b). Our construction advantageous in that uses & loss and & ball-like domain in the constrained setting, both being the strongest in their direction when relaxing to l geometry. Simply using the Holder incquality yields that the product of the Lipschitz constant G and the diameter of the domain C' equal when p varies in (o).
Theorem 4.8. Let n, d be large enough and 1 2 > 0,2-0(n) < 8 o(1/n) and 2 L. There exists convex set K. C Rdd, such that for every (c, 8) -)-differentially private algorithm with output garin E K., there is data-set D = {21...., .... C {0, 1] U 1121 such that
[[L(grriv D)- L(0"; D) (1 /dlog(1/0) GGC)
(15)
where 0 is minimizer of T(0; D), is G-L.ipschitz, and C is the diameter of the domain K. Both G and C are defined w.r.t. Ep geometry.
Proof. We use the same construction as in Theorem 3.6 which considers &g geometry. We only need to calculate the Lipschitz constant G and the diameter of the domain IC
For the Lipschitz constant G, notice that our loss the & norm: {(0; 2) = 10--21 =/11. is evident that it is (d >-Lipschitz w.r.t. lp geometry.
For the domain, i.e., the unit fo ball K, obvious that its diameter w.r.t. &, geometry d#.
To conclude, we find that for any 4p geometry where 2 1, we have GC which is independent of p. The bound holds for any Ep geometry by applying Theorem 4.6
For the unconstrained case, we notice that the optimal 0 under our construction must lie in the unit -bal = (s IR 10 S x S 1, Vi E [d]} by observing that projecting any point to does not increase the & loss. Therefore,
result can be generalized to the unconstrained case directly. In
word, our result presents lower bounds Q /dlog(1/0) for all p 2 1 and for both constrained case and unconstrained case. Remarkably, our bound is the best for near and p >> 2 to our knowledge.
En
5 CONCLUSION
This paper studies lower bounds for DP-ERM in the unconstrained case and non-cuclidean geometry. We propose simple but powerful black-box reduction approach that transfer any lower bound in the constrained case to the unconstrained one, indicating that getting rid dimension dependence generally impossible. We also prove better lower bounds for approximate-DD ERM for any Lp geometry when 2 1 by considering E loss over the foo ball. Our bound is tight when 1 < p < and novel for p > However, there is a gap between the current best upper bound Bassily al. (2021b) and our lower bound when >> 2. Filling this gap can be an exciting and interesting problem. Designing better algorithms for general (un)constrained DP-ERM based on our insights would also be an interesting and meaningful direction, which we leave as future work.
REFERENCES
Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, and Enayat Ullah. Differentially private generalized linear models revisited. arXiv preprint S0l::2255.03014 2022.

---

Under review as a conference paper at ICLR 2023
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in { geometry. arXiv preprint arXiv:2103.01516, 2021.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473 IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pp. 11222-222222 1291, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint arXiv:2006.06914 2020.
Racf Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34, 2021a.
Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization, arXiv preprint wrxiv:2203300221 2021b.
Dan Bonch and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions Information Theory, 146$):189711955, 1998a.
Dan Boneh and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory, 187551889- 1998b.
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal Computing, 47(5):1888-199 1938, 2018.
Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In NIPS,
volume 8, pp. 289-296. Citeseer, 2008.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
S Cobzas and C Mustata. Norm-preserving extension of convex lipschitz functions. J. Approx. Theory, 24(3):33-224,, 1978.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):21 1-47, 2014.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
Kazuto Fukuchi, Quang Khai Tran, and Jun Sakuma. Differentially private empirical risk mini- mization with input perturbation. In International Conference on Discovery Science, pp. 82-90. Springer, 2017.
Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Langevin diffusion: An almost universal algorithm for private euclidean (convex) optimization. arXiv preprint arXiv:2204.01585. 2022.
Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mecha- nism. arXiv preprint arXiv:2203.0022 2022.
Elad Hazan. Introduction to online convex optimization. arXiv preprint
2019.
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 299-316. IEEE, 2019.
10

---

Under review as a conference paper at ICLR 2023
Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differen- tially private learning. In International Conference on Machine Learning, pp. 484.484. PMLR, 2014.
Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Dimension independence in unconstrained private erm via adaptive preconditioning, arXiv preprini arXiv:2008. 06570, 2020.
Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization for
high-dimensional learning. In International Conference on Machine Learning, pp. 488 497. PMLR, 2016.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793 -96779,,,,,, 2011.
Daniel Kifer, Adam Smith, and Abbradeep Thakurta. Private convex empirical risk minimization and nigh-dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings. 2012.
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimization and stochastic convex optimization subquadratic steps. arXiv preprint arXiv:2103. 15352, 2021.
Benjamin IP Rubinstein, Peter L Bartlett, Ling Huang, and Nina Taft. Learning in a large function space:
mechanisms for svm learning. arXiv preprint 1rXiv:091.557000 2009.
Shuang Song, Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with differen- tially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp.
248. IEEE, 2013.
Shuang Song. Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference Artificial Intelligence and Statistics, pp. 2638-2646. PMLR, 2021.
Thomas Steinke and Jonathan Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In Conference learning theory, pp. 1588-1628. PMLR, 2015.
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2):3-22, 2016.
Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly-optimal private lasso. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 2, pp- 3025-3033. 2015.
Gábor Tardos. Optimal probabilistic fingerprint codes. Journal of the ACM (JACM), 55(2):1-24 2008.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, pp. 2722-2731, 2017.
Puyu Wang, Yunwen Lei, Yiming Ying, and Hai Zhang. Differentially private sgd with non-smooth loss. arXiv preprint arXiv:2101.0892. 2021.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, 1307-1322, 2017.
Jai Zhang. Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 3928.. 2017.
Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.0381.1 2020.

---

Under review as a conference paper at ICLR 2023
A
ADDITIONAL BACKGROUND KNOWLEDGE
A.1 GENERALIZED LINEAR MODEL (GLM)
The generalized linear model (GLM) is flexible generalization of ordinary linear regression that allows for response variables with error distribution models other than a normal distribution. To be specific,
Definition A.1 (Generalized linear model (GLM)). The generalized linear model (GLM) a special class of ERM problems where the loss function E(O, d) takes the following inner-product form:
E(O; 2) ((0,x)):))
(16)
for 2 = (z, Here, x E R usually called the feature vector and E called the response.
B CONSTRUCTION OF FINGERPRINTING CODES
To address the digital watermarking problem, Fingerprinting codes were introduced by Boneh & Shaw (1998b). Imagine a company selling software to users. A fingerprinting code is a pair of randomized algorithms (Gen, Trace), where Gen generates length d code for each user i. To prevent any malicious coalition of users copy and distributing the software, the Trace algorithm can trace one of the malicious users, given code produced by the coalition of users. They may only can the bits with divergence in the code: any bit in common is potentially vital to the software and risky change.
In this section, we introduce the fingerprinting code used by Bun et al. (2018) which is based on the first optimal fingerprinting code Tardos (2008) with additional error robustness. The mechanism of the fingerprinting code is described in Algorithm for completeness.
The sub-procedure part the original fingerprinting code Tardos (2088,, with a pair of randomized algorithms (Gen, Trace). The code generator Gen outputs a codebook C' E (0, ) of C the codeword of user i. The parameter is called the length of the fingerprinting code.
j[xdd The ith row
We make the formal definition of fingerprinting codes:
Definition B.1 (fineerprntiing codes). Given n, d E N,5 E (0, pair of (random) algorithms
(Gen, Trace) is called an (n, d)-fingerprinting code with security & E (0, 1] if Gen outputs a code- book C' {0, 1 and for any (possibly randomized) adversary AFp and any subset S C [m]. we set e + n AFp(Cs), then
Pr[c E F(Css) A Trace(C, =
[Trace (C,c) E SE
where F (Cs) = (CE ( (0. 1]2 Vj E [d] 3i S, =Gg]. c. and the probability is taken over the coins Gen, Trace and AFP.
Fingerprint codes imply the hardness of privately estimating the mean of a dataset over {0, 1)dd. Otherwise, the coalition of users can simply use the rounded mean of their codes produce the copy. Then the DP-ERM problem can be reduced to privately estimating the mean by using the linear loss whose minimizer precisely the mean.
The security property of fingerprinting codes asserts that any codeword can be "traced" to user i. Moreover, we require that the fingerprinting code can find one the malicious users even when they get together and combine their codewords in any way that respects the marking condition. That is. tracing algorithm Trace takes as inputs the codebook C and the combined codeword and outputs one of the malicious users with high probability.
The sub- sub-procedure Gen' first uses a sin? x like distribution to generate a parameter pj (the mean) for each column j independently, then generates C' randomly by setting each element to be I with probability according to its location. The sub-procedure Trace' computes a threshold value Z and score function' S,(c') for each user i, then reports when its score is higher than the threshold.
The main procedure was introduced in Bun et al. (2018), where Gen adds dummy columns to the original fingerprinting code and applies random permutation. Trace first 'undo' the
12

---

Under review as a conference paper at ICLR 2023
Algorithm 1 The Fingerprinting Code (Gen, Trace)
Sub-procedure Gen':
Let 100n² log(n/E) the length of the code.
Let 1/300n be parameter and let t' be such that sin
for j = 1..., d: do
Choose random uniformly from [t', x// 1') and let pj = sin2ry. Note that py [t, t]. For each = 1, .... n., set Cigy = 1 with probability pj independently. end for Return: C
Sub-procedure Trace' Trace((C,c')
Let Z 20n log(n/E) be parameter.
For each j = 1, ..., d, let Ø3 = / ((1-p))/pp
For each j = .... d, and each = 1, n. let Ui oú if Cj = 1 and U1i -1/9; else wise.
for each i 1,... n2: do
Let S:(d) = ΣØ= o Uij
Output if (c)) 2 Z/2.
Output L if (;(c') Z/2 for every i I,... n.
end for
Main-procedure Gen:
Let C' be the (random) output of Gen', C' {0, 1]axd Append 2d O-marked columns and 2d 1-marked columns to C.
Apply a random permutation ı to the columns of the augmented codebook.
Let the new codebook be C" (0, 1xx6d
Return: C
Main-procedun Trace(C, c'):
Obtain C' from the shared state with Gen.
Obtain C' by applying -- to the columns of C' and removing the dummy columns.
Obtain e by applying -1 to d' and removing the symbols corresponding fake columns.
Return: i randomly from Trace' (C, c).
permutation and remove the dummy columns, then Trace' as black box. This procedure makes the fingerprinting code more robust in tolerating a small fraction of errors to the marking condition.
In partieular, they prove the fingerprinting code Algorithm [ has the following property.
Theorem B.2 (Theorem 3.4 in Bun et al. (2018).. For every d. and y (0,1), there exists (n, d1-fingerprinting code with security ? robust to a 1/75 fraction of errors for, for
n n= == log(1//))
C OMITTED PROOF FOR SECTION 3
C.I PROOF OF LEMMA 3.5
The proof of Lemma 3.5 is basically the same as the proof in Bassily et al. (2014) with minor modifications. Readers familiar with the literature can feel free skip it.
Lemma 3.5 Let n. 2 2 and > There is a number n²* = 2(min(n, ))) such that for any e-differentially private algorithm A, there is dataset D = {=1,-., {,} C ( J U (0) with E >ill2 n² such that, with probability at least 1/2 (taken over the algorithm random coins),
we have
d M(min(1, -
IA(D) -(0)))((D))))) (DD)]12
(17)
me
where ((D) = -1E, 2i.
13

---

Under review as a conference paper at ICLR 2023
Proof. By using standard packing argument construct K = 2 points 20)) 2(K) in Va )a U (0) such that for every distinct pair 2(0)2 of these points, we have
|| 21 1
(18)
It is easy to show the existence of such set of points using the probabilistic method (for example, the Gilbert- Varshhmoo construction of linear random binary code).
20x Let's first consider the case where S n². We construct K datasets D(1) ..... D(K) where for each E [K], D(6) contains copies of 2(0) Note that g((()) (0), have that for all i + j.
Fix c > 0 and define n' = d
(lx(D()) ((D6)) )12 2
(19)
Let A be any e-differentially private algorithm. Suppose that for every D i E [K], with probability
least 1/2. [[A(D()) Il < 1 J.e.. Pr. (r((()) B(D > where for any dataset D, B(D) is defined as
1 1
B(D) (+ E Rd || ((D)ll2
(20)
Note that for all + j. D(1) and D(3) differs in all their n entries. Since A c-differentially private, for all E [A], we have Pr[A(D(1) E B(D()) 2 f ee Since all ((D are mutually disjoint, then
K 2
Pr(A(D()) B(D()) s
(21)
which implies that n >> n² for sufficiently large p. contradicting the fact that n". Hence, there must exist dataset (() on which A makes an f2-error on estimating ((D) which is at least 1/16 with probability at least 1/2. Note also that the Eg norm of the sum of the entries of such D(1) is n.
Next, we consider the case where n > n²" As before, we construct K = 2 datasets DD1) D(K)
of size n where for every E [K). the first n² elements of each dataset D5()) are the same as dataset D from before whereas the remaining n n² elements are 0.
Note that any two distinct datasets D(t) DD6 in this collection differ in exactly n' entries. Let A be any e-differentially private algorithm for answering q. Suppose that for every [K]. with probability at least 1/2, we have that
n"
(22)
16n
Note that for all i E [K], we have that (D(()) = n" (D((() Now, we define an algorithm for answering g on datasets D of size n² as follows. First, A appends as above to get a dataset D of size n. Then, it runs A on D and outputs n'A(D)) Hence, by the post-processing propertry of differential privacy, A is e-differentially private since A is e-differentially private. Thus for every i E [K], with probability at least 1/2, we have that |IĀ(D()) (((())ll < 1 1s: However, this contradicts our result in the first part of the proof. Therefore, there must exist a dataset DD6 in the above collection such that, with probability at least 1/2,
n" d
[{(()))) {((())) )|2 2
(23)
16n
320em
Note that the fg norm of the sum of entries of such 5(() is always n².
C.2 PROOF OF THEOREM 3.6
The proof does not use the reduction Theorem 3.4 directly as a black box but uses the intuition behind it in detail.
14

---

Under review as a conference paper at ICLR 2023
Theorem 3.6
Let n. 2 2 and > 0. For every e-differentially private algorithm with output garin E R there is a dataset D = {21,...,,,, C { Va. vaa
- va {0) such that, with probability at
least 1/2 (over the algorithm random coins), must have that
d
) ((PPre; D) min ((0 D) = ((min (1, ne
(24)
0
Proof. We can prove this theorem directly by combining the lower bound in Bassily et al. (2014)
and our reduction approach (Theorem 3.4 but try to give complete proof example to demonstrate how does our black-box reduction approach work out.
Let A be an e-differentially private algorithm for minimizing L and let (ariv denote its output, define r := &prie - 8" First, observe that for any 0 E Rd and dataset 'D as constructed in Lemma 3.5 (recall that D consists of n copies of vector { va va 1ad and n² copies of 0).
min (- (y, 2) + 110 - -yll)) = n :(0":D) n max (0, 110011 - 1} + n 11l2511
(25)
n
n
when 0" and also
L(prriv D)
n n
m0 ||0 11 + n
min (- (v, 2) + 1100010 -1112)
2 n"
min (- + ||geriv - -3112)
11vlla
= n²
min (-(y, + ||r + - y112)
n IlllasI
(because 0" = 2)
n2 min [|]]]]]
n
8n
the last inequality follows by discussing the norm of y - z. If [1y - ==1l2 S ||rl1//2,
then
||r + z yll 2 ||rl2// 2 min |r]l6/
(26)
combining with the fact that (y, 2) < 1 proves the last inequality.
If |yy - =112 2 ||rl|//2, then we have min (y, 2) 2 -1 + e1 without loss of generality and y (x) (21, where |lvll2 = 11 2 + = 2||2 S 1, we must have
1|r To prove this, we assume
8
Ei= 2 ||r11/4.
Since
d
1+
z + 201 S 1
(27)
1=1
Thus -(y, 2) -1 (y 2)
-1
11 2 + |1r11//8 as desired, which finishes the discussion
on the second case.
From the above result we have that
L(grion D) - L(0":)) min (1, 1r
(28)
8n
To proceed, suppose for the sake of a contradiction, that for every dataset D (21, .... 2n C (-r-- 1 ) U (0} with Em= æs|la = n², with probability more than 1/2, we have that | va val
0 Irrla # 2(1). Let Á be an c-differentialyy private algorithm that first runs A on the data and then outputs a" gorio Recall that g(D) n 0*, this implies that for every dataset D (,,,..,,,)) C ( Val du(()) with || DTh 21112 = n". with probability more than 1/2, [|Ā(D))
(DD)ll # (mmin(1, ne ) which contradicts Lemma 3.5 Thus, there must exists a dataset D va (d (0) with E'= ælI2 = n", such that with pr obability more than
(z1, ) c I 2
1/2, we have ||r||2 ||0prio 0 2|2 = 2(1). and as a result
L(B D) L(#": D) = 2(min(1, ))
(29)
15

---

Under review as a conference paper at ICLR 2023
D OMITTED PROOF FOR SECTION 4
D.1 PROOF OF LEMMA
Lemma 4.3
For every 2 1, and E (0, 1), there exists y-complete, y-sound, 1/150-robust
loss fingerprinting code for n users with length d where
d= log(1/7).
Proof. We want to find a such that any set satisfying the completeness condition in the above definition is subset of the F3 set of Bun al. (2018) after rounded to binary numbers, which is
(D(D) { d' 10,134
Pr Di [m],c] Dayl 2- JE(d]
1-
Suppose, round the output M(D) E [0. 1ja to a binary vector e E {0. 1] where e E (D()), then makes an "illegal" bit at least 3d columns, where each of these columns shares the same number (all-one or all-minus-one columns). It means that on each of these columns, MM() has the opposite sign to the shared number, which means this column, say the induced loss is lower bounded:
T1 (I(M(D): Pal (Di) Diyl)
(M(D), - Dig 1, j=1
which means L(M(D);) ming L(0:D) 2 Bd/2. By Theorem conclude our proof.
B.2
get 1/75 and
D.2 PROOF OF LEMMA
Lemma 4.4 For < a condition Q has sample complexity for algorithms with (1, ((1/n))): differential privacy (n² is the smallest sample size that there exists an (1,o(1/n) (1,o(1/)))-differ)) /nii)--)iffffrentiall private algorithm which satisfies Q), if and only if it also has sample complexity O(n" /e) for privacy.
algorithms with
Proof. The proof uses a black-bor reduction, therefore doesn't depend on Q. The direction that O(n"/e /e) samples sufficient equal to proving the assertion that given o1, (l)n)(())-diffeeenntt -differrentiall private algorithm A, we can get a new algorithm A'' with (e, o(f//m))-differentti privacy at the cost of shrinking the size of the dataset by a factor of c.
Given input and a dataset X, we construct A' to first generate a new dataset T by selecting each element of X with probability independently, then feed T to A. Fix an event S and two neighboring datasets X1, X2, that differs by a single element i. Consider running A on X₃. If i is not included run on X2. On the other hand, if is
in the sample T, then the output is distributed the same included in the sample T, then the behavior of A on T is only factor of off from the behavior of A on T {i). Again, because of independence, the distribution of T {i] is the same as the distribution of T conditioned on the omission of i.
For a set X, let px denote the distribution of A(X), ), we have that for any event S,
Px (5) = (1 cxxx, (S) & T) + px, (Shi E T)
(1 c))x, (S) e(e Px, (S) (S)+0) +
< exxp(2e)xx, (5) +
A lower bound of px, (S) 2 exp((=))pe (S) - e5/ can be obtained similarly. To conclude, since eδ o(1/n) /n) as the sample size n decreases by factor of e, A' has (2e, ((/))()))-ddffeeeentt privacy. The size of X is roughly I/c times larger than I', combined with the fact that A has sample complexity n² and T is fed to A. A'' has sample complexity at least ((n" /e).
For the other direction, simply using the composability of differential privacy yields the desired result. In particular, by the k-fold adaptive composition theorem in Dwork et al. (2006). we can combine 1/c independent copies of (c, 5) diifferentiall private algorithms to get an (1, d/E) one and notice that if o(1/n), then ó/c = (1/n) as well because the sample size n is scaled by a factor of at the same time, offsetting the increase in 8.
16

---

Under review as a conference paper at ICLR 2023
D.3 PROOF OF THEOREM 4.6
Theorem 4.6 Let n, d be large enough and 2 e > 0, 20()) < <ō<
< o(/n). For every (e, 0)-
differentially private algorithm with output Opriv Rd, there is data-set D (21, Zn} C (0.1) ( such that
v Vdlog(1/6) )GC)
E (Apri D) - L(0"; Q(min(1,
(30)
ne
where l is G-Lipschitz w.r.t le geometry, 0* is minimizer of L(0; D), and C v is the diameter of I. w.r.t. & geometry, where IC is the unit foo ball containing all possible true minimizers and differs from its usual definition in the constrained setting.
Proof. Let k (1og(1/6)) be parameter to be determined later satisfying k/n < 1/6000, and ng = |n/k]. Consider the case when 2 d,. first, where dna, Oc2ng log
Without loss of generality, we assume = 1 due to Lemma 4.4 and d, O log(1/5))
corresponds to the number Lemma 4.3 where we set 7 = 6.
We use contradiction to prove that for any (e, 6)DP mechanism M, there exists some D E {0. 1 lndd such that
(ML(M(D); D) L(0 (dd). mxd
(31)
Assume for contradiction that M: {0, 10xd - [0, 1] is (randomized) (c, d)-P mechanism such that
d
ELL(M(D): L(0
3000
for all D e {0, (0,1]xxd We then construct mechanism Mr {0, 1) x with respect M as follows: with input Dé {0, 11medd, Mr will copy DD for k times and append enough O's to get dataset D (0,1)=xd The output MD M(D). M2 is (k, 5) by the group privacy.
We consider algorithm AFP be the adversarial algorithm in the fingerprinting codes, which rounds the output MD( to the binary vector, i.e.. rounding those coordinates with values no less than 1/2 and the remaining 0, and let e Apr(M(D)) be the vector after rounding. As Mr is c (k, e-1 -DP, Apr is also (k, 2)
Considering the & loss, we can account for the loss caused by each coordinate separately. Recall that M& (D*) M(D). Thus we have that
(DL(MM ) D T.(0"; D
E[L(M(D);; :D))
-EL(M(DD):**) ([) L( L(0"; (IL(M(D)) L()
< &6kd/n + d/3000 S d/900,
where we use Lemma 4.5 for the third line.
By Markov Inequality, we know that
(D) D+) 150 1/5.
Lemma 4.3 implies
< d/150 A Trace t .c) =1] 6 (D*) -
By union bound, we can upper bound the probability Pr|Trace(D*: .)) c) =1] 1 +8 < 1/2. As result, there exists i" E (nu) such that
Prjt" E Traco(D* ,c]] 2 1/(2nx).
(32)
17

---

Under review as a conference paper at ICLR 2023
Consider the database with i" removed, denoted by D Let d' = App(MM(D denote the vector after rounding. By the second property of fingerprinting codes, we have that
Pr[i" Trace(D" i., c')] - d.
By the differential privacy and post-procsssing property of M,
Pr[i" Trace(D", c)] S Prli" (a e*
6.
E
which implies that
1
S 1.
(33)
2ng
Recall that 2-0(n) < easy to see there exists ((lo((1/)) and n /6000 make this inequality false, which is contraction. As result, there exists some D {0, 1 13 such that
< < o(1/n), and Equation 33 suggests k/n S 2e* for all valid k. But
B[L(M(D);;) D) : D)
3000 (dd).
For the (c, 8)-DP case when c << 1, setting Q to be the condition
[[L(M(D): D) L(0"; D)] O(d)
have that any (e, 6DDP mechanism M which satisfies for all D E {0, 10,1) must have S (1/d)og(1/))/c) In another word, for d 2 0(e'n) /² log(1/5)).
for all D e 10 in Lemma 4.4
for any (e, 8)- mechanism M, there exists some DD {0, 13d such that
LL((M(D); L(O; D)] 2 (dd).
Now we consider the case when < dne. i... when n > n* & Ω2( /llooog()//))e)) Given any dataset D E {0, 1 xd, we construct a new dataset D' based on D by appending dummy points to n rows among which half are and half are {1]d. n² odd, we append n-n'-1 points 0, n-n"-1 points (1)d and one point (1/2]d. 2
D: Specifically, if n" is even, we append
2
Denote the new dataset after appending by D', we will draw contradiction if there is an (c. 5)DP algorithm M' such that (IL(M(DD); D') L(0"; | = o(n'd/n) n) for all D', by reducing M' to an (c, dDD algorithm M which satisfies B[L(M(D);D)
L(O"; D)] o(d) for all D.
construct M by first constructing D', and then use M' as a black box to get M(D) M' It's clear that such algorithm for D preserves (e, ddiffferrnnt privacy. It suffices to show that if E[L(M'(D');
L D')] o(n'd/n)
(34)
then L(M(D): D) : D) = o(d), which contradicts the previous conclusion for the case n S n*. Specifically, if n² is even, have that
n B[L((((): D) L(O"; D)] =E(L(M((D)))) L(0;,'))))
and if n* is odd, we have that
n n'E[L(M(D): L( [D] nE(L((M
D')] + d/2.
both leading to the desired reduction. We try to explain the above two cases in more detail. n n is even, then the minimizer of L(: and L(0"; D) are the same. And the distributions of the M(D) and M are identical and indistinguishable. Multiplying n" or n depends on the number of rows (recall that we normalize the objective function in ERM). The second inequality is because we append one point (1/2)d, which can only increase the loss (11//2 0²1lz) by d/2 in the worst case.
Combining results for both cases, we have the following:
: D)] = Q(min(d, dn" -)) = M(min(d, d d (llg011/))
E (Orrin, ( D)
(35)
ME
Setting Lipschitz constant G vd and diameter C = v completes the proof.
18


Reviews:
[{"review_id": "wCs7m93Oiiv", "reviewer": "Reviewer_kgZa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied differentially private empirical risk minimization by establishing its lower bounds for the unconstrained case and for the non-euclidean setting. The two main contributions, according to the authors, are as follows: (1) the introduction of a simple but general black-box reduction approach that can transfer any lower bound in the constrained case to the unconstrained case and (2) the establishment of better lower bounds for approximate-DP ERM for any ℓp geometry when p ≥ 1.", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strength:\n\nThe problem studied in the paper, namely, differentially private empirical risk minimization, is important and has more and more practical applications\n\nWeaknesses:\nThe authors claimed that one of their main contributions is the establishment of lower bounds under lp norm. However, it is not clear to me why the lp norm is important here. I think this should be clearly clarified when/before summarizing the contributions of the present study. This is also my main concern.\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "n6IkQc4ih6", "reviewer": "Reviewer_9oeX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper gives lower bounds for differentially private ERM in the unconstrained and non-euclidean case. They provide a simple blackbox reduction approach to reduce lower bounds in the constrained case to unconstrained cases based on the idea of a Lipschitz extension of a function. They also give lower bounds for both the constrained and unconstrained cases by considering $\\ell_1$ loss over the $\\ell_\\infty$ ball.", "summary_of_the_review": "I think the weaknesses outweigh the strengths and in my opinion the results in this paper are not enough for a full paper contribution. The results are all technically correct, but very incremental and I do not think it is enough to be a full conference paper. ", "strength_and_weaknesses": "Strengths:\n1. The paper is clearly written, easy to understand and the contributions of the paper against the past work has been clearly highlighted.\n2. The ideas of extending the lower bounds to the unconstrained case are novel.\n3. The paper uses the $\\ell_1$ norm to give lower bounds for DP-ERM for a variety of $p$-norms.\n\nWeaknesses:\n1. For the jump from constrained to unconstrained case, the assumption of knowing an initial point $\\theta_0$ at a distance at most $C$ away from optimal, essentially makes the problem a constrained minimization problem and the rest of the calculations are fairly elementary.\n2. For the bounds using $\\ell_1$ norm, most of the heavy-lifting is done by previous work.\n3. Adding instances of why these geometries are useful and giving algorithms that achieve these bounds can make this paper stronger.\n4. It is unclear to me (and I am open to changing this opinion in deliberation with other reviewers and the meta reviewer), how much of a contribution this paper is to the ICLR community. I believe this paper would make an excellent contribution to TMLR since the proofs are correct and it would be nice to have something to cite instead of doing these things yourself as a part of another paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "XBC6IAbf8p", "reviewer": "Reviewer_hdk6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies empirical risk minimization with differential privacy and has two main results:\n\n* A simple reduction from constrained to unconstrained minimization that preserves, convexity, the Lipszhitzness constant (with respect to $\\ell_2$, and optimal solutions. This reduction allows extending privacy lower bounds from constrained to unconstrained optimization. This implies a lower bound for ERM under pure differential privacy in the unconstrained setting. \n\n* A lower bound of $\\Omega\\left(\\frac{\\sqrt{d \\log(1/\\delta)}}{\\varepsilon n}\\right)$ for ERM under $(\\varepsilon, \\delta)$-differential privacy where the loss is the $\\ell_1$ norm and optimization is over the cube $[-1, 1]^d$.", "summary_of_the_review": "The paper contains a neat new reduction, and some good-to-know lower bounds that are of somewhat niche interest. The work is solid but perhaps belongs in a more specialized venue.", "strength_and_weaknesses": "I enjoyed the reduction, which is simple but very neat. The idea is to take a convex 1-Lipschitz loss function $\\ell$ defined on a convex domain $K$, and extend it to all of $\\mathbb{R}^d$ by taking its inf-convolution with the $\\ell_2$ norm. This is a convex 1-Lipschitz loss function it is not hard to show that it induces an ERM problem with the same optimal value and solution. \n\nThe second lower bound is less exciting and follows from fingerprinting code techniques that are now standard.\n\nThe main issue with the paper is that the paper extends existing lower bounds in relatively minor ways. I am not sure how significant it is to extend ERM lower bounds from constrained to unconstrained optimization. Moreover, it seems like the lower bounds with respect to functions Lipschitz in $\\ell_p$ were known for $1 \\le p \\le 2$, which is also the regime in which these lower bounds are tight. These are both good things to know, but not groundbreaking.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject