Tight lower bounds for Differentially Private ERM
Authors: Daogao Liu
Zhou Lu
Venue: ICLR 2022 Submitted (2022)
Keywords: Differential Privacy
Empirical Risk Minimization
Lower bounds

Abstract: We consider the lower bounds of differentially private ERM for general convex functions. For approximate-DP, the well-known upper bound of DP-ERM is $O(\frac{\sqrt{p\log(1/\delta)}}{\epsilon n})$, which is believed to be tight. However, current lower bounds are off by some logarithmic terms, in particular $\Omega(\frac{\sqrt{p}}{\epsilon n})$ for constrained case and $\Omega(\frac{\sqrt{p}}{\epsilon n \log p})$ for unconstrained case.

We achieve tight $\Omega(\frac{\sqrt{p \log(1/\delta)}}{\epsilon n})$ lower bounds for both cases by introducing a novel biased mean property for fingerprinting codes. As for pure-DP, we utilize a novel $\ell_2$ loss function instead of linear functions considered by previous papers, and achieve the first (tight) $\Omega(\frac{p}{\epsilon n})$ lower bound. We also introduce an auxiliary dimension to simplify the computation brought by $\ell_2$ loss. Our results close a gap in our understanding of DP-ERM by presenting the fundamental limits. Our techniques may be of independent interest, which help enrich the tools so that it readily applies to problems that are not (easily) reducible from one-way marginals.

Under review as a conference paper at ICLR 2022
TIGHT LOWER BOUNDS FOR DIFFERENTIALLY PRI- VATE ERM
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the lower bounds of differentially private ERM for general con- vex functions. For approximate-DP, the well-known upper bound of DP-ERM
is O (oloog(1/)) which is believed to be tight. However, current lower bounds ((>2)) for constrained case and are off by some logarithmic terms, in particular Q vD en
en
/p 2 ( log for unconstrained case. We achieve tight 92( (1//)) lower bounds for both cases by introducing novel biased mean property for fingerprinting
codes.
As for pure-DP, we utilize novel 8g loss function instead of linear functions considered by previous papers, and achieve the first (tight) 9 (2)) lower bound. We also introduce an auxiliary dimension to simplify the computation brought by & loss.
Our results close gap in understanding of DP-ERM by presenting the funda- mental limits. Our techniques may be independent interest, which help enrich the tools so that it readily applies to problems that not (casily) reducible from one-way marginals.
INTRODUCTION
Since the seminal work of Dwork et al. (2006), differential privacy (DP) has become the standard and rigorous notion of privacy guarantee for machine learning algorithms, among which many fun- damental ones are based on empirical risk minimization (ERM). Motivated by this, private ERM becomes one the most well-studied problem in the DP literature, c.g. Chaudhuri and Monteleoni [ Rubinstein et al. (2009); (Chauduur et al. (2011): Kifer et (2012), (Song et al. (2013); Jain and Thakurta (2014); Bassily et al. (2014): Talwar et al. (2015): Kasiviswanathan and Jin (2016); Fukuchi et al. (2017): : Wu et al. (2017); Zhang et al. (2017); Wang et al. (2017): Iyengar et al. (2019); Bassily et al. 2020); Kulkarni et al. (2021) Asi et (222
Bassily et al. (2021) ); Wang
et al. (021).
Roughly speaking. in the ERM setting, we are given a convex function family defined on convex set C C E2 and sample set D = {dj,..., .d)) drawn i..d from some unknown distribution P with the objective to minimize the loss function
n
L(O:D)
((0, d4),
and the value (oo-DDDminng
-(0: -mingee T(O0;; D) is called the excess empirical loss with respect to solution 0, measuring how it compares with the best solution in C.
Private ERM in the constrained case was studied first and most of the previous literature belongs this case. More specifically, the constrained case considers convex loss functions defined on bounded convex set C' Ç Rº, Assuming the functions are I-Lipschitz over the convex set of diameter
1, the Q2 /F lower bound of private ERM is given by Bassily al. (014)) even for (special and simpler) generalized linear model (GLM).
However, there still several aspects that existing works don't cover. First, existing upper bounds off by at least logarithmic term / /Tog(1/85 (185. For example in Wang al. (201)); Bassily et al.

---

Under review as a conference paper at ICLR 2022
2019) they give upper bounds like O (411000011aa//log
which are believed to be tight. In Bassily et al. (2014; 4), they present lower bound {2( vP) by reducing linear loss to one-way marginal results in Hardt and Talwar Talwar Bun et al. (2018). In Steinke and Ullman (2015) they achieve the tight lower bound for answering one-way marginals with respect to & norm, but it does not imply tight lower bounds for general loss functions by the methods in Bassily et al. 2014) directly.
en
Another aspect is DP-ERM in the unconstrained case which was neglected before and gathered people's attention recently, see Jain and Thakurta (2014); SSng et al.) (202I). The unconstrained case is interesting in that can't 't use linear loss any more which lies at the heart of the construction in the constrained case. Moreover, previous algorithms in the constrained case suffer from the curse of dimensionality when p is large. For example, when p 12(")), the lower bound is S2(1) and any private algorithm can not get meaningful bounds on the excess empirical loss. Song et al. (2021)
proves an dimension-indeeenddae O /rrakk upper bound in the unconstrained setting for the special case of GLMs, where rank denotes the rank of the feature matrix of GLM. However, it's unknown if similar results can be achieved for general loss functionn. As for the lower bound, Asi et al.
en
2021 give S2( ne log lower bound by considering & loss as the objective functions and reducing the results also from one-way marginals.
1.1 OUR CONTRIBUTIONS
In this paper, we fill up the two gaps together by proving an (mmin(1, \plog(1/5) ne }) tight lower bound for the excess risk of unconstrained I I-Lipschitz convex loss functions for approximate dif- ferentially private algorithms. This bound is automatically applicable in the constrained case, which improves previous results and achieve tight lower bound for both constrained and unconstrained case. We summarize our main results as follows:
We prove an (1iin11 polg(1//) )) tight lower bound for the excess risk of unconstrained ne 1-Lipschitz convex loss functions for approximate differentially private algorithm. This bound improves Asi al. (2021) by log(p) /log))))ooo/(// [og(118) factor in the unconstrained case and matches the upper bound in Kairouz et al. (2020).
We also prove 0(min(1, }) lower bound for the excess risk of unconstrained 1- Lipschitz convex loss functions for any pure differential privacy algorithm.
Note that our main results for unconstrained case can be extended to constrained case directly, thus our lower bound for approximate private algorithm is /log(1/8 multiplicative better than the well- known bound in Bassily et al. (2014) with the help of group privacy technique in Steinke and Ullman (015).
A key contribution of this paper is novel tools for private lower bound techniques. For most problems, accuracy lower bound in the private setting is established via reduction from one-way marginals. Hence the tools for lower bounds is quite limited. We contribute to refinement of such tools in particular, we propose modifications such as the additional "biased means" property to fingerprinting codes, which is the key lower bound technique. Such modifications help enrich the tools so that it readily applies to problems which are not (easily) reducible from one-way wa- marginals.
1.2 OUR TECHNIQUES
In general, the direct technical challenge of the unconstrained case lies in the choice of loss function and the difficulties caused by the new loss function. The loss function is required to be convex and Lipschitz-continut
the same time. In the constrained case, the linear loss function is obviously good choice for constructing lower bounds, because it is easy to analyze and easily reducible from one-way marginals. However, in the unconstrained case any non-trivial linear loss function can take '-oo" value thus not applicable anymore. We further observe that convexity plus Lipschitz- continuity means 'asymptotically linear': the sub-gradient along any direction must converge. This observation guides in choosing new loss functions for unconstrained DP-ERM (which can be extended to constrained case directly). We briefly introduce the new problems caused by the new loss functions and our method to overcome them for approximate-D2 and pu separately.
2

---

Under review as a conference paper at ICLR 2022
1.2.1 APPROXIMATEEDD
The construction of our lower bound for approximate-DP is based on the Fingerprinting Codes, which was first studied by Wagner 1983) and developed by Bonnh and Shaw [998]; Tardos (008
From a technical perspective, we change the previously used linear loss and use an & norm function instead where f(0; d) = |0 dl|1. & loss has been used in concurrent work Asi et al. (2021) /P which proves an S2( 22 lug lower bound of approximate DP in the constrained case by reducing the
results from one-way marginals, and can be extended to unconstrained case directly. We improve this bound by logarithmic terms and achieve optimality by utilizing the group privacy technique from Steinkk and Ullman (2015). We observe a novel biased mean property in the fingerprinting code to successfully combine and adjust these techniques to fit the & loss.
We briefly describe the proof based on group privacy technique first. In the group privacy we need to copy some hard instances of data-set D of size ng == [n/k] according to the construction of fingerprinting codes by k times, and append n kng. data points to get a final data-set D of size n. Fix any (e, -iifferrentyl private algorithm A for D, if we remove one element i' from D&, we can get D and D_,- where D- and 'D can have at most i elements different. Running A on D and D_ respectively, we get an (ke, d'ffdffffrlltaal privacy algorithm for D and D .. Setting appropriately, if A can lead to small error on the DP-ERM, it can be an adversary which contradicts the properties of the fingerprinting codes. Intuitively, the differential privacy means it is hard find the removed element i", but fingerprinting codes suggest the removed element is traceable as long as DD satisfies the required properties and leads to small excess empirical loss with respect to LO0 D*).
The direct use of the biased mean property is in appending the n - kTn points. As nearly all of previous lower bounds in DP convex optimization are based on the results from one-way marginals, we try to demonstrate the proof in the language of one-way marginals. Because for linear functions, large one-way way marginal errors lead to large excess empirical loss directly, which means the lower bound of private one-way marginals can apply to DP-ERM. But it is obvious that without additional assumption, large one-way marginal errors can not mean large excess empirical loss of the & loss functions anymore. Consider the toy case when = and D = {d]
n//k] where de E {0, 1}.
Denote the mean of these |n/k] by DE Similarly let D be the mean values of DD constructed from D by method above. For example, if D 1/2 and we only append points 1/2,, then D 1/2 and whatever the one-way marginals are, the excess empirical loss (of the n L loss functions) ) can be 0, as L(O:D) = Σm= ||0-d, More specifically, we need |Di 1/2 should be larger than some value depending on k. then we can append kng dummy points safely. For general p, we need the unbiased mean property holds for a large fraction of coordinates. For any single dimension, the biased mean property serves to ensure the prediction of the column (dimension) is unchanged during the group privacy mechanism, in which some number of dummy points are appended that may potentially change the prediction of unbiased column. This novel property sets more stringent conditions. Fortunately, we observe that the previous construction of fingerprinting codes in Bun et al. (2018) satisfies it.
d4 11 is constant function over [0, 1]. So we need the mean DR to be biased.
1.2.2 PURE-DP
Although the square loss seems tempting in the constrained case, which intuitively reduces the unconstrained case to constrained because the loss value grows fast outside a bounded region and also makes computation simple. It's unfortunately non-Lipschitz in the unconstrained case thus not applicable directly.
We use the novel fg-norm loss as a natural substitute, which both convex and Lipschitz- continuous. Unlike the constrained case, the morm loss brings the drawback that the minimizer of the ERM problem no longer has a closed form solution or any nice property for computation. Roughly speaking, in the analysis of Bassil et al. (2014) they have an 'adding dummy points' pro- cedure which will perturb the minimizer. Linear loss has this nice property that after adding these dummy points the minimizer can only move along its direction, while for lz loss the minimizer might be intractable. To overcome this problem, we define the Fermat point and introduce an aux- iliary dimension to simplify the messy calculation brought by &g f-rnrrm loss in our analysis. The
3

---

Under review as a conference paper at ICLR 2022
dummy points have support only in this auxiliary dimension and guarantee that the perturbation of the minimizer is still along its own direction, reducing computation in any high dimension to a two-dimension subspace spanned by the minimizer and the auxiliary dimension.
1.3 CONSTRAINED AND UNCONSTRAINED
In this subsection, we briefly discuss the relationships and differences between constrained case and unconstrained case, and compare our bounds with previous bounds.
Previous studies on DP-ERM mostly focus on the constrained setting, and the unconstrained case recently attract people's 's interest because Jain and Thakurta (2014); ; (ong et al. (202I) found that an vrank upper bound can be achieved for minimizing the excess risk of GLMs, which evades the O en
curse of dimensionality.
has been known that the unconstrained condition is necessary for dimension independence, as pointed out by Bassily et al. (2014) in which they prove 52( yP) lower bound even for minimizing constrained GLMs for the case when "rank S n < p".
We are interested in the necessity of the unconstrained condition to get rank-dependent bound. The unconstrained GLM can be viewed as a vank-dimensional problem, as the noise added in the null space of the feature matrix will not affect the excess empirical loss. However, this does not hold in the constrained case. Take the dimension-indepeneee based on SGD as an example. The pitfall for the himeension-nndependent algorithm lies in projection if SGD is modified to projected-SGG SGD for constrained case, that running SGD in the constrained setting requires projection which might "increase rank". We can see there is some fundamental difference between constrained and unconstrained case, and analyzing unconstrained case is also an interesting and important direction.
algorithm in [Song et al. (202I) which is
Classic methods, like Bassily et al. (2014) usually connect linear loss to one-way marginals Bun al.] (2018), and then use lower bounds for one-way marginals to imply lower bounds for linear
loss. As Basssily et al. (2014) are using results from Hardt and Talwar (2010); Bun et al. (2018 8) in
one-way marginals and Steinke and Ullman (2055) achieves tight 2 y log(1/0) bound by using the novel group privacy technique, one may ask whether combining (Steinke and Ullman (2013) and Bassily et al. (2014) can achieve the tight lower bound in the constrained case trivially. Because Steinke and Ullman (2015) considers l distance but Bassily et al. (2014) considers & distance, there is a / gap between them and one can't 't directly combine them. Though with some effort, one may get tighter bounds in the constrained case by modifying the results in Steinke and Ullman (215) from l norm to le norm, then applying the analysis in Bassily et al. (2014).
As shown in Asi et al. 22221) proving nearly tight lower bound in the unconstrained case is direct by utilizing one-way marginals and choosing the right objective functions, but getting rid off those extra logarithmic terms in the unconstrained case is nontrivial as the one-way marginals can not work directly in group privacy. To the hest of our knowledge, our result is the first time that achieves this improved tight lower bound for general loss function class in both cases. See Table 1.4 for detailed comparisons between previous bounds and ours.
1.4 RELATED WORK
The existing lower bounds of excess empirical loss, i.e. the constrained case in Bassily et al. (2014) and the unconstrained case in (Sng et al. (202T), are all using GLM functions. The objective func- tion used in (Bassily et al. (2014) is E(0:d) d) (0, d) which can't applied in the unconstrained case, otherwise the loss value would be infinite. Considering this limitation, [Song et al.) (2021)
adopts (0; d) = 100, x) y/. They transfer the problem of minimizing GLM to estimating one-way marginals, and then get the lower bound by properties in the definition of the Fingerprinting Codes.
As mentioned before, our lower bound are based on l norms, thus we can not transfer to one- way marginals directly. Merely using the properties in the definition of Fingerprinting Codes is not enough for a good lower bound. Instead, we need to make full use of the concrete structure of the codes.
4

---

Under review as a conference paper at ICLR 2022
Article
Constrained!
Loss Function
Pure DP
Approximate DP
Bassily et al.
2014)
constrained
GLMM
22( LP
Song et al.
2021)
unconstrained
GLM
N/A
?
Yrank
Th
Asi al.
2021
both
general
N/A
O
vP
ne log
(log(1/0)
Ours
both
general
2
2
1LC.
Table 1: Comparison on lower bounds for private convex ERM. Our lower bounds can be extended
to constrained case easily. The lower bound of SSng et al. (2021) is weaker than ours in the important
p > n setting.
As for the upper bounds, the private ERM Wang et al. 2017 and private Stochastic Convex Op- timization (SCO) Feldman et al. (2020) for convex and smooth functions are extensively studied, where the objective to minimize the function [e-p[e(0; d)] in the SCO and people only need (nearly) linear gradient queries to get optimal excess loss. But for convex functions without any smoothness assumption, the current best algorithms Kulkarni al.) (2021): Asi et al. (202T) will need more queries (n 1.77 in the worst case). Besides, most of the previous works are consider- ing problems in &2 norm, and there are some recent results (Bassily et al. (2021) Asi al. (2021) studying the general fp norm.
1.5 ROADMAP
In section we introduce background knowledge needed the rest the paper. In section
we prove the main result of this paper, an (1 / }) lower bound for approximate DP- ERM in the unconstrained case. In section we discuss an (1mm(1 2 )) lower bound for the excess risk of pure DP algorithms for minimizing any unconstrained I-Lipschitz convex loss function. Section concludes this paper. All missing (lechnical) proofs can be found in the appendix.
PRELIMINARY
We consider minimizing the excess risk of unconstrained Lipschiz convex function with DP algo- rithms in this paper, where we let n denote the sample size and be the dimension of a sample. In this section, we will introduce main background knowledge required in the rest of the paper. Additional background knowledge such as the definition of GLM can be found in appendix.
Definition 2.1 (Differential privacy). randomized mechanism M is (c, diffferrentl private for any event O E Range(M) and for any neighboring databases D and D' that differ in a single data element, one has
Pr(M(D) E OO exp(e) PD(M(D') E 0 +
When 8 > 0, we refer to the above condition as approximate differential privacy. The special case when 8 = 0 called pure differential privacy.
Definition 2.2 (Empirical Risk Minimization). Given family of convex loss functions {E(0, dd) of over C. RRP and a set of samples D (di..... ,d) over the universe D, the objective of Empirical Risk Minimization (ERM) is to minimize
L(B: D) = Σ E(O; d4).
The excess empirical loss with respect to solution 0 is defined by
L(:: D) L(0*:
where 0* E arg mingex: T(0; D), measuring the performance of the solution compared with the best solution in K.
Definition 2.3 (G-Lipschitz Continuity). A function f : RP + R is G-Lipschitz continuous with respect to Eg norm if the following holds for all 0, 0' RP:
[(()) f(0') < G 0'1|2
5

---

Under review as a conference paper at ICLR 2022
The Chernoff Bound will serve to prove the fingerprinting code constructed in Bun al. (2018) satisfies our modified definition of fingerprinting code as well.
Proposition 2.4 (The Chernoff Bound). Let X Ei=1 1 X; where X; with probability p3 and Ps- Assume all X, are independent random variables. Let Σi=1 Pi-
X; 0 with probability Then
P([X u) 2 ou) S 2expp(-u6(12)
APPROXIMATE DP
In this section, consider the lower bound for approximate differential privacy where 2 2-0(n) 5 < o(1/n). Such assumption on is common in literature, for example in Steinke and Ullman 2015). We briefly introduce the (classic) fingerprinting codes first:
3.1 FINGERPRINTING CODES
Definition 3.1 (Fingerprinting codes). We are given n, E N,C E (0, A pair of (random) algorithms (Gen, Trace) is called an (n, fffiirerrrrriinnnn code with security & (0, Gen outputs code-book C' [0,1]axp and for any (possibly randomized) adversary App and any subset _ [n]. if we set c +-R (Css then
Pr[c E F(Cs) A Trace (C, c) =1]
Pr (C,c) E [n][S]
where F (Cs) = fee (0, 13 Vj E [d] E =c) c... and the probability taken over the coins of Gen, Trace and AFP.
There is a very good motivation behind the fingerprinting codes. For example, a software distributor adds fingerprint
each copy of her software to protect the IP. A coalition of malicious users can compare their copies and find the digits that differ which belong to the fingerprint. For other locations they can't 't decide and won't It change them, which is called the marking condition. This is the reason that we requires E F(Cs).
The two properties of fingerprinting codes demonstrate that one can identify least one malicious user among all with high probability, Bun et al. (2018) extends the definition that the codes can tol- erate a small fraction errors in the marking condition. We further modify this definition, requiring the codes to have biased means, see below.
3.2 OUR RESULT
We modify the definition of fingerprinting code instead for our analysis.
Definition 3.2 (Error Robust Biased Mean Fingerprinting Codes). Given n.
N, 3,,,a,,, a,, 022, 03 E (0, 1]. We say pair of (random) algorithms (Gen, Trace) is an (n,p)- fingerprinting code with security and (ar,, (22 abb-aas mean, robust to a 3 fraction of errors Gen outputs code-book C E {0, 1)axp and for any (possibly randomized) adversary AFp and any coalition S _ [n], if we set c + AFp(Cs), then
Pr[c e Fs(C's A Trace(C,c) = SE
Pr [Trace (C, E [n][S] S
Pr[Ga, 2 (1- a2)] S a3
where Fs (Cs) = EcE 10. Prjenie -c 3}.
Ga(Cs) = Kii :
at is the number of slightly biased columns in Cs and the probability is taken over the coins of Gen, Trace and App.
Eies S/
We use the fingerprinting code in Bun et al. (0018) for the construction of our lower bound, see Algorithm 1 in the appendix. We utilize an loss and the fingerprinting code in Bun et al.

---

Under review as a conference paper at ICLR 2022
2018 'hard case'. To proceed, we first introduce few lemmas which would be of use later. Similar to Bun et al. (2018), we have the following standard lemma which allows us to reduce any < 1 to 1 case without loss of generality, using the well-known 'secrecy of the sample' lemma from Kasiviswanathan et al. (201T).
Lemma 3.1. A condition Q has sample complexity for algorithms with (1]n)) -iifeerrnt privacy (n" is the smallest sample size that there exists ())((/))-differentinn private algo- rithm which satisfies Q), if and only if it also has sample complexity O(n" /e) for algorithms with privacy.
(E,
Notice that Lemma 3.1 discusses the sample complexity of the algorithm, therefore independent of the (01, 022 0z)) ( mean appeared in the above definition which only concerns the construction of the fingerprinting code. The following lemma verifies that the fingerprinting code Algorithm indeed has biased mean in definition 3.2 bound multiple times.
The proof is straightforward by using the Chernoff
Lemma 3.2. Algorithm (the fingerprinting code) has (1/100, 999/1000, exp(-SOp))-biasee mean.
Directly combining Lemma 3.2 and Theorem 3.4 from Bun et al. 2018), we have the following lemma, which states that for the fingerprinting code Algorithm which we will use in proving main theorem to satisfy the error robust biased mean property in definition 3.2 one needs roughly
((VP) samples.
Lemma 3.3. For every p E and & E (0, 1], there exists an (n, p) fungrrpriiinnngg code (Algorithm 1) with security & and (1/100, 999/999990000 (xp())(pp))- ((p)--))))biieeeee -biased mean, robust to 1/75 fraction of error for
n = n(; = -//
We are ready to prove the main result of this section by using Lemma 3.3 to reach a contradiction. Consider the following l norm loss function. Define
{(0; d) |10 d|1,, e R
(3)
For any data-set D {d1, ..., ) we define L(0: Ei,,
Theorem 3.4 (Lower bound for (e, ddifferreetl private algorithms). Let p be large enough and 1 2 0, 20x)) < < o(1 /n). For every (e, -differrentl private algorithm with output
gprio E IRP, there is data-set = (dl,..,,dl dn3 C {0, 13" U (2 such that
(( D) L(0"; D)) 2mmin(1, Vplog(1/5) GGC) TEE
)GC)
(4)
where & is G-Lipschitz, 8" is a minimizer of L(0; D), and C is the diameter of the set {arg ming L(0; D) c (0, 1]xx), which contains all possible true minimizers.
Due to the space limit, we leave the proof of the Theorem 4 in the appendix.
The dependence on the diameter C makes sense as one can minimize a substitute loss function ((xx) = E(ax) where E (0, 1) is constant instead, which decreases Lipschitz constant G' but increases the diameter C. Note also that C. > whenever all possible D don't share the same minimizer of I., which is often the case. This bound improves log factor over [Bassily et al. (204)) by combining the the group privacy technique in Steinke and Ullman (015) and our modified definition of fingerprinting code.
We leave several remarks discussing slight generalizations of Theorem 3.4
Remark 3.5. Our lower bound can be directly extended to the constrained setting, by setting the constrained domain to be [0, 1 pxxp which contains the convex hull of all possible minimizers (arg ming L(0; D) {0, 13 [xxp].
y (og(/)) ally assume the rank of gradient subspace. The analysis remains the same except we first apply orthogonal transformation then set the complement of the gradient subspace to be all O's in D.
Remark 3.6. Similarly,
derive an M(min(1,
lower bound when we addition-
at
7

---

Under review as a conference paper at ICLR 2022
Remark 3.7. The third property of definition 3.2 serves the group privacy analysis further im- prove a (1/() term over Bassily et al. (2014). One can simplify the proof by setting k and borrow the lower bound for 1-way marginals from Bun al. (2018), at the cost of losing this log(1/5 /8) term. See appendix for details.
4 PURE DP
In this section, we give a lower bound for c-(pure) differentially private algorithms for minimizing unconstrained convex Lipschitz loss function L(0: D). In the construction of lower bounds for constrained DP-ERM (Bassily et al. (2014)), they chose linear function 8(;; d) (0, d) as their objective function which isn't applicable in the unconstrained setting because it could decrease to negative infinity. Instead, we use a novel Ey norm loss function to over come this problem:
(5) For any dataset D = (dd,,..,dh, we define L(0;D) = -ー E(0; d.). Clearly, both and convex and 1- I-Lipschitz. The structure of the proof is similar to that in Bassily et al. (2014), while technical details are quite different as we need to handle non-linear objective function. Different from the simple average of points in Bassily et al. (2014), we need to consider the Fermat point instead, which is the minimizer of the Eg norm loss function.
E(0; d) = 10 - 412,, 0, d R
4.1 FERMAT POINT
Definition 4.1 (Fermat point). The set of Fermat points P(D) of dataset D {di,.... ...; dn) contains points minimizing its & distance to all points in D:
P(D) {aag min
Σ 10 d:l12)
ZER"
One obstacle of using & norm loss is that Fermat points aren't unique in the worst case. Given a (finite) dataset D. we can easily see that P(D) is compact subset of the convex hull of D, which encourages us to define unique "maximum" element in P(D). To do so, introduce the following well-order on R?.
Definition 4.2 (Coordinate dictionary order). A point x is said to be larger than y in coordinate dictionary order and only if there exists index E [ri] such that > yi. and for any < we have that x;- = yj-
It's straightforward verify that CDO (coordinate dictionary order) is well-order. Next CDO to select a unique member from the set P(D) of all Fermat points. Definition 4.3 (Ordered Fermat point). The Ordered Fermat point q(D) of a dataset D {d).... d,) is defined as:
(D) = =arg max CDO(r) xEP(D)
Such ((D) must exist for finite dataset as long as P(D) is compact and non-empty, because there can't be an ordered infinite sequence with its limit outside of P(D) which contradicts compactness. The technical proof of the following proposition is deferred to appendix.
Proposition 4.1. (D) always exists for a finite dataset D.
Note that (D) is unique by definition and always minimizer of L(e; D) over Rº. In the fol- lowing subsection we are going to show that any pure DP algorithm can't 't estimate g(D) with good accuracy, then prove that large error in estimating (D) will lead large error in the excess risk of E2 norm loss as well, establishing the main lower bound of this section.
4.2 LOWER BOUND
In this subsection, we prove lower bound on the excess risk incurred by any e-differentially private algorithm whose output is denoted by (prie IRP. We first introduce the following lemma showing
8

---

Under review as a conference paper at ICLR 2022
that it's impossible to find the location of the ordered Fermat point (D) with good accuracy using a pure DP algorithm.
The proof follows the spirit of Bassily et al. (2014). constructing datasets 'frr away' from each other such that the events of estimating the Fermat point of each dataset accurately are mutually disjoint. Then by differential privacy as long as can estimate other one with certain probability as well. The sum of all these probabilities is no more than 1 due to the disjointness, which leads the desired bound.
dataset accurately, one estimate any
We denote 61 _ (1,0,-., 0)T and let @ denote the direct sum of vectors, i.e. = (a,, (3) where a E RR.3 E R are both vectors. For a vector a and a set S, we denote a @ S {(o, 9) B E ES. There is a number M 12( (n, 2) such
Lemma 4.4. Let n.p 2 2 and e that for any e-differentially private algorithm A. there is dataset D = {di..... dnf c (0 - - U (f1,- -e1, O} with |I Ei= dell2 S M such that, with probability at least 1/2 (laken over the algorithm random coins), we have
[|A(D) - q(D)ll2 = 9(min(1, P. ne
(8)
The classic analysis of Bassily et al. (2014) contains an 'adding dummy points' which will perturb the location of the minimizer. In the constrained case, such perturbation won't 't change the direction of the minimizer (seen as a vector), but in the unconstrained case non-lineat loss functions no longer enjoy such good properties. To oversome this issue, we introduce the auxiliary dimension and the dummy points we add have support only in this dimension. The benefit of doing so that the Fermat point (D) will also only change along its direction after we add dummy points, which simplifies the computation.
Lemma 4.4 implies that it's impossible to estimate the ordered Fermat point with good accuracy using a pure DP algorithm. the following theorem we are going to show that a bad estimate on the ordered Fermat point leads to higher lg norm loss. As the fermat point is minimizer of Eg norm loss, we can naturally translate the discrepancy in estimating (D) to the excess risk.
Theorem 4.5 (Lower bound for e-differentially private algorithms). Let n, 2 2 and > O. For ev- ery e-differentially private algorithm with output (prie E IRP, there is a dataset D = {d1,-., dx C (o ( -/-)"") U {er, -c1, 03 such that, with probability at least 1/2 (over the algo- rithm random coins), we must have that
L(prriv D) - min L(0; D) (mmin(1,
P ne
The proof is based on calculation in the two-dimensional subspace spanned by ((D) and the auxil- iary dimension. By observing that (D) is perpendicular to the auxiliary dimension, we can parame- terize geriv by these two unit vectors and write down the expression of L(pnrie; (D) ming L(0; D) explicitly. Then by elementary inequality scaling we get the desired result.
Remark 4.6. In fact the lower bound Theorem 4.5 also holds for the case p The only difference is that the case = 1 doesn't need the auxiliary dimension because the perturbation of the minimizer is always along its direction. We can simply use dummy points {1, 11,00 and a similar analysis to Bassily et al. (2014) to achieve this result.
5 CONCLUSION
In this paper, we study differentially private convex ERM in the unconstrained case and give the first tight lower bounds for approximate-DP ERM for general loss functions. Our results also directly imply same lower bound for the constrained case, improving the classic lower bound in Bassily ct al. 22014) by log(1/5). We also give an Ω d lower bound for unconstrained pure-DP ERM which recovers the result in the constrained case. Our techniques enrich the quite limited tools in constructing lower bounds in the private setting and we hope they can find future use, especially for those problems which are not (casily) reducible from one-way marginals. Designing better algorithms for general (un)constrained DP-ERM based on our insights would also be an interesting and meaningful direction, which we leave future work.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in geometry. arXiv preprint arXiv:2103.01576, 2021.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473, IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pages 11282-11291, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. arXiv preprint arXiv:2006.069) 06914, 2020.
Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochas- tic convex optimization. arXiv preprint arXiv:2/03.0/278, 2021.
Dan Bonch and James Shaw. cellusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory, 44(5):1897-1905, 1998.
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing,
2018.
Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In NIPS, vol- ume 8, pages 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.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of cryptography conference, pages 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 93344:211--00 2014.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439 449, 2020.
Kazuto Fukuchi, Quang Khai Tran, and Jun Sakuma. Differentially private empirical risk minimiza- tion with input perturbation. In International Conference on Discovery Science, pages 82-90. Springer, 2017.
Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705-714, 2010.
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. To- wards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pages 299-316. IEEE, 2019.
Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differen- tially private learning. In International Conference on Machine Learning, pages 484. PMLR, 2014.
Peter Kairouz, Mónica Ribero, Keith Rush. and Abhradeep Thakurta. Dimension independence in unconstrained private erm via adaptive preconditioning. arXiv preprint arXiv:2008 06570, 2020.
Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization for high-dimensional learning. In International Conference Machine Learning, pages 488-497. PMLR, 2016.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What we learn privately? SIAM Journal Computing, 40(3):793-826, 2011.
10

---

Under review as a conference paper at ICLR 2022
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and -igh-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Work- shop and Conference Proceedings, 2012.
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu, Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprini arXiv:2103. 15352, 2021.
Benjamin IP Rubinstein, Peter L Bartlett, Ling Huang, and Nina Taft. Learning in large function space: Trivacy-preservee mechanisms for svm learning. arXiv preprint arXiv:0911.577 1.5708, 2009.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pages 245-248. IEEE, 2013.
Shuang Song. Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimen- sionality unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages 2638-2646. PMLR, 2021.
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. arXiv preprint 150I 00005, 2015.
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, pages 0033,, 2015.
Gábor Tardos. Optimal probabilistic fingerprint codes. Journal of the ACM (JACM), 55(2):1-24, 2008.
Neal R Wagner. Fingerprinting. In 1983 IEEE Symposium on Security and Privacy, pages 18-18. IEEE, 1983,
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, pages 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. Proceedings of the 2017 ACM International Conference on Management of Data, pages 1307-1322, 2017.
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objec- tives. arXiv preprint arXiv: 1703.09973 2017.

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL BACKGROUND KNOWLEDGE
A. GENERALIZED LINEAR MODEL (GLM)
The generalized linear model (GLM) is a flexible generalization of ordinary linear regression that allows for response variables that have error distribution models other than a normal distribution. To be specific,
Definition A.1 (Generalized linear model (GLM)), The generalized linear model (GLM) is special class of ERM problems where the loss function É(O, d) takes the following inner-proe unner-product form:
E(0; d) (((0,x);;)
(10)
for d (I.y). Here, x E R usually called the feature vector and y E R is called the response.
A.2 PROPERTIES OF DIFFERENTIAL PRIVACY
In this subsection we introduce several very basic properties of differential privacy without proving them (refer Dwork et al. (2014) for details). Readers familiar with the field differential privacy can feel free skip this section.
Proposition A.1 (Group privacy). M : X" + Y is (e, diiffeerret private mechanism, then for all pairs of datasets z, x' X", then M(z), are (ke, " -indistinguiihhbbl when I, . differs on exact k locations.
Proposition A.2 (Post processing). If M X" + is (e, 8) -)diifferentially private and A: + Z any randomized functioo then A M X + Z is also (.6))differenttallly private.
Proposition A.3 (Composition). Let M; be an (Ei, dii-fifferryt private mechanism for all E [k). If Maj defined be
Ma
Ma(x)))
(11)
then Mis is (Et Co Eie diddiffferettially private.
B FINGERPRINTING CODE
In this section we briefly introduce the mechanism of the fingerprinting code Algorithm | The sub-procedure part is the original fingerprinting code in Tardos (2008), with a pair of randomized algorithms (Gen, Trace). The code generator Gen outputs a codebook C E {0,1) 1]mxP, The ith row of C is the codeword of user i. The parameter p is called the length of the fingerprinting code.
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, there tracing algorithm Trace that takes as inputs the codebook C' and the combined codeword e' and outputs one of the malicious users with high probability.
The 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 1 with probability Pj according to its location. The sub-procedure Trace' computes a threshold value Z and 'score function' Si(c)) for each user then report when its score is higher than the threshold.
The main-procedure was introduced Bun et al. (2018), where Gen adds dummy columns to the original fingerprinting code and applies random permutation. Trace first 'undo' the permu- tation and remove the dummy columns, then use Trace' as black box. This procedure makes the fingerprinting code more robust in that it tolerates small fraction of errors the marking condition.
C OMITTED PROOFS
C.I PROOF OF LEMMA 3.1
Proof. The proof uses a black-box reduction, therefore doesn't depend on Q. The direction that O(n"/ /e) samples are sufficient is equal to proving the assertion that given (1,o(1/n))
12

---

Under review as a conference paper at ICLR 2022
Algorithm The Fingerprinting Code (Gen, Trace)
1: Sub-procedure Gen':
2: Let d = 100n² 2 log(n// (n/E) be the length of the code.
3: Let t 1/300n be parameter and let t' be such that sin?t' t.
4: for = 1, ,...,, d: do
5: Choose random uniformly from [t', x t'] and let Py sin?rz. Note that Pý E [t, t].
6: For each ,,.,, n, set Cit with probability pj independently.
7: end for
8: return C
9: Sub-procedure Trace' (C, Tr,ce'(C,c)):
10: Let Z 20n (ng(n/E)
parameter.
11: For each j 1, ..., d, let q3 = (111Pas)1 Pp)/pj-
12: For each 1, .... d. and each 1,.... n, let U2 qi if Cj = 1 and U2 -1/g; else wise.
13: for each i 1,... do Let S,(c') ビE= U/UY
Output if (c()) ) 2 Z/2.
16: Output 1 if Si(c') < 2/2 for every i I,
17: end for
18: Main-procedure Gen:
19: Let C/ be the (random) output of Gen', C' {0, 1
20: Append 2d O-marked columns and 2d 1-marked columns to C.
21: Apply a random permutation и to the columns of the augmented codebook.
22: Let the codebook be C" {0, 1 nnx6d
23: return C
24: Main-procedure Trace(C,d'):
25: Obtain C" from the shared state with Gen.
Obtain C' by applying π the columns of C' and removing the dummy columns.
27: Obtain by applying -1 to e' and removing the symbols corresponding to fake columns.
28: return i randomly from Trace' (C,
differentially private algorithm A, we can get a new algorithm A' with (c.o(L/n))-differennte pri- vacy the cost of shrinking the size of the dataset by a factor of e.
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 and two neighboring datasets X1, X2 that differs by a single element i. Consider running A on X1. If i is not included the sample T, then the output is distributed the same as a run on X2. On the other hand, if
included in the sample T, then the behavior of A on T is only a factor of off from the behavior
of 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,
(S) = (1 - e),x, (S)i & 7') + epx, e TT)
< (1 c) (S) e(e Px, (S) 0
< Exxp(2e)xxx (5)+ +
A lower bound of px, (S) 2 exp(-e)px, (S) - c6/e can be obtained similarly. To conclude, since eδ = o(1/n) as the sample size n decreases by a factor of e, A' has (2e, privacy. The size of X is roughly 1/c times larger than T, combined with the fact that A has sample complexity n² and fed to A. A' has sample complexity least O(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, -ddffferrentll private algorithms to get (1, 8/c) one and notice that if 5 = o(1/n), then 8/c = o(1/)) as well because the sample size n is scaled by a factor of at the same time, offsetting the increase in 8.
13

---

Under review as a conference paper at ICLR 2022
C.2
PROOF OF LEMMA 3.2
Proof. In line 5 of algorithm
every column j is assigned a probability independently where Pr(Pp, - 2
0.002] <
(12)
400
by straightforward calculation. By the Chernoff bound (with u < p/ 1), with probability at least
2 (exp(-p/800)
(13)
1 fraction of the columns have |p, - -/2 2 0.002. Denote my to be the mean of at least - 200 entries of column j. then by using the Chernoff bound again (with 5 0.001), we have that with probability at least
1 2exp(=n/800000)
(14)
column j actually satisfies my 1 2 0.001. Again by the Chernoff bound (with u I exp(-xpp -n |0/800000)) and ud 0.01p) together with the union bound, at least 0.99 fraction of all columns have [m 1 2 0.001 with probability at least
1 1-2exp(-22 pp/000) 2 exp(-- -pee" pem/800000/ /40000) = 1 -Oe ((()))))
(15)
C.3 PROOF OF THEOREM
Proof. Let (a1, 02, 03) = (1/100, 999/1000, exp(-9(pp) be the parameters in the statement of Lemma 3.3 Let k = ((log (1/o)) be a parameter be determined later and nıg = [nnkk].
Consider the case when p 2 Pn. first, where Pn; O log(1 (1))) Without loss of generality, we assume e = 1 first, and Pnt (n log(1/))) corresponds to the number in Lemma 3.3 where we set Ş = 8. We will use contradiction to prove that for any (c, d)-differentially private mechanism M, there exists some D {0, 1)xP with Ga -1) S 022 such that
B[L(M(D): D) - L(0"; D)] 2 a(p)
(16)
Assume for contradiction that M 1)xP + 10, 1|" is (randomized) (e, d)diffferentially private mechanism such that
B[L(MDD): - D)) < a102p
1000
for all D E 10x1) with -I.-1/R(2 S (1 - 02). We then construct mechanism Ma
{0, 1)m1)mm with respect to .M as follows: with input D* E (0.1)**xP, M will copy D for times and append enough O's to get dataset D {0, (),1)xXX, The output is M₂ MMD).
Mr is (k, e-11 diiffeerrnt private by the group privacy. According to the construction above, we know that if Ga, (D+) < a2, then G., 1/1- < 1 02 as well.
e-1
We consider algorithm App P be the adversarial algorithm the fingerprinting codes, which rounds the the output M& (D+) to the binary vector, i.c. rounding those coordinates with values no less than 1/2 to 1 and the remaining O, and let e AFP(M(D)) be the vector after rounding. As Mr is (k,
e وات e 6) -iiffereetiill private, AFP is also (k, اات -iiiffrrrenyially private.
If for some D E {0, 1) with Ga,(Di < 022 D (constructed from D above) further satisfies
BLL(M(D):)) L(O"; < 0102P
1000
As we are considering the & loss, we can consider the loss caused by each coordinate indepen- dently. Recall that MD M(D). The fraction of those nearly unbiased columns (the mean close to 1/2) is at most azz, and we treat the worst-case error for them. For other "az biased columns (coordinates) which take least ag fraction of all, if M(D) is right for the prediction, then appending O's can't change the prediction and MR(DA) is also right. Thus we have that
BLL(Me(DD)) ) :(0"; DD) <B(L(M(D): - L(O"; D) + (1 02)p < 900
11

---

Under review as a conference paper at ICLR 2022
By Markov Inequality we know that
L(0"; -
180 1 1/5.
c É Fa(D*) means that there is at least Bp all-one all-zero columns D³ but is inconsistent in those coordinates. Thus if & (D(D)), ). we have that ((M) D*) L(0"; D z Bp/2
p/ 150 p/180 for the D by Lemma 3.3 implying
Pr|ce E Fa(D*)] 2 4/5.
(17)
By the first property of the codes, one also has
Pr(L(M((D*): L(0"; D S p/180 A Trace(D' c) =1] S Pric Fs((D)) A Traco(D' c) = =1] S 8.
Recall that the arguments above are for those Dé E {0, 10 with Go, (D+) I 1 - 02, which happens with probability at least 1 - a3 by the third property of fingerprinting codes. By union bound, we can upper bound the probability Pr[Trace(D') .) =T] s 1/5 + ô 8 ag 1 1/2. As a result, there exists i E [nw] such that
Pr|i" E Traco(D*, cc) 2 1/(2m)).
(18)
Consider the database with 1" removed, denoted by D Let d' = AFp App(M(DE...) denote the vector after rounding. By the second property of fingerprinting codes, we have that
Pr[i" E Traco(D" ,,, c')] S 5.
By the differential privacy and post-processing property of M,,
e² - Pr[i" Trace(D*; c)] S e e Trace(D* ,, c')] E
8.
which implics that
1
++18.
(19)
2nk
Recall that (m)(n) < o(1/n), and Equation 19) suggests k/n < 2e* /0 for all valid k but is easy to see there exists k = O(og (1/5)) to make this inequality false, which is contraction. As result, there exists some E {0. 10.11mx n with Ga--1/k (/x(D) 2 (1 a²) subject
BLL(M(D): D) - L() N 01102 2(p).
1000
For the (e, -ddifferrnnt privacy case, setting Q to be the condition
E[L(M(D): D) - L(0"; D)] = O(p).
in Lemma 3.1
we have that any (c, differrenttal private mechanism M which satisfies Q for all D E 10,1)*X xxp with G..-1/x(D) 2 1 - a2 must have n 2 22( /l
Now we consider the case when p Png. i.e. when > n A R( plo/o/((//)))) Given any dataset 'D E 10"1"""'pp xp with G - > 1 02 we will construct
dataset D' based on D by appending dummy points to D like in Lemma 4.4 Specifically, if n n is even, we append n n² rows among which half are 0 and half are {1) If n - n is odd, we append n-n"- points -- points { and one point (1/2}².
Denote the new dataset after appending by D', we will draw contradiction if there is an (c. 6)- differentially private algorithm M' such that E B[L(M(D"): - D')] o(n" for all D'. by reducing M' to an (e, -ifffeereentillll private algorithm M which satisfies ([L(M T(0";; D)] o(p) for all D with (D) > 02.
15

---

Under review as a conference paper at ICLR 2022
We construct M by first constructing D', and then use M' as black box to get M(D) (D') It's clear that such algorithm for D preserves (c, dddffferent privacy. It suffices to show that if [[L(M'(D'):
: p/n).
(20)
then L(M(D); D) D) o(p), which contradicts the previous conclusion for the case n S n². Specifically, if - n² is even, we have that
n n"BLL(M(D)) - L(O D)] -
and if n² is odd we have that n'E[L(M(D); YD -( D((0:)
nE(L((M(D'); ((00 -= p/2.
both leading to the desired reduction. We try to explain the above two cases in more detail. If n n² is even, then the minimizer of L.; D) and I( DD) are the same. And the distributions of the M(D) and (D') are the same and indistinguishable. Multiplying n²" or depends on the number rows (recall that we normalize the objective function in ERM). The second inequality is
because append one point (1/2}P, which can only increase the loss (11/22 0*]l,) by p/2 in the worst case.
Combining results for both cases have the following:
E E[L((OprVV D) ;()";))] = [mmin(p, pr²
(21)
To conclude, observe that G = vp and C' Cp.p. In particular, let D (d, (d.... d) E {0, 1)xp contain n identical copies of rows d E 10, fr = d. Going over all such D. we find that the set (arg ming (0: DD C 1]xxp] contains {0, 1)" with diameter least vp. Meanwhile, its diameter can't exceed vD obviously.
C.4 DETAILS OF REMARK
We give a sketch of Remark 3.7 In Bun al. (2018) they prove the following lower bound for I-way marginals:
Proposition C.1 (Corollary 3.6 in Bun et al. 2018 ) The family of 1-way marginals on {0,1)" 1jd has sample complexity at least ((vd) for (1/3, 75) accuracy and (()))))(1 privacy.
Inspecting the proof we find that the constant 1/3 the above proposition is chosen casually, and can be replaced by any constant с < 1/2 for free, as the proof only requires - e is rounded to and is rounded
respectively.
The third property of the fingerprinting code implies that with high probability, at most 0.01 fraction of all columns have mean with bias smaller than 0.001. When we assume the opposite for the sake of contradiction, by union bound, at least 1/75 1/100 1/000 fraction of columns have both 'large error on 1-way marginal' and 'large bias on mean'.
For any such column j. the algorithm is forced to predict wrongly on the question 'Is there more 0's than I's in column j' as the range of prediction is restricted in [0, and choose e c 0.001 1/2, thus leading to error on E norm loss.
C.5 PROOF OF PROPOSITION 4.1
Proof. We assume P(D) * without loss of generality. To verify P(D) is compact, we first observe that P(D) is bounded. To prove P(D) is closed, notice that when P(D) * 0, the function f(x) = Σn || - d:l12 is continuous and non negative, which implies its image is of the form la, Therefore the pre-image of the open set (a, oo) is also open, whose complement is exactly P(D).
To find the ordered Fermat point, we reduce the dimension of P(D) one after another. Because P(D) is compact, the largest value of the first coordinate ai 2 argmaz.e 2(D) exists, and the ordered Fermat point must lie the restriction of P(D) on {a æ1 a1 } which is also compact and non-empty. We continue this process until all dimensions are peeled and there is one point left because the only non-empty set with zero dimension is single point.
16

---

Under review as a conference paper at ICLR 2022
C.6 PROOF OF LEMMA 4.4
Proof. By using standard packing argument we can construct K = 2" points d(), ... d(k) 00 Vp- } such that for every distinct pair d(e), d(5) of these points, we have
in
|| 1 8
(22)
is easy to show the existence of such set of points using the probabilistic method (for example, the Gilbert- Varshamov construction of a linear random binary code).
Fix > 0 and define n" Te0 Let's first consider the case where S 4n². We construct K datasets D(1), ..... D(K) where for each E [K], D( contains copies of d()) Note that g(D(i))
d(+), we have that for all i + j.
(a((D()) ((DG)))
(23)
Let A be any e-differentially private algorithm. Suppose that for every D(t), [K]. with probability
at least 1/2, ||A(D()) -D(( tे PrA(P(())(( E B(D())] 2 where for any dataset D, B(D) is defined as
B(D) (x E nP: || a(D)llp <
(24)
16
Note that for all i + j. D(1) and D(j) differs in all their n entries. Since A is e-differentially private, for all E [K], we have Pr[A(D(U) B(D())) 2 -e- Since all B(D(9) are mutually disjoint, then
K 2
Pr(A(D()) B(D())) 1
(25)
which implies that > 4n for sufficiently large p. contradicting the fact that S 4n". Hence, there must exist dataset D(t) which A makes an fz-error on estimating ((D) which is at least /16 with probability at least 1/2. Note also that the &g norm of the sum of the entries of such D n..
Next, we consider the case where > 4n As before, we construct K = 2 datasets D(1), .... DDKK of size n where for every [K]. the first n' entries of each dataset DD) are the same as dataset D( from before whereas the remaining n n entries are constructed as fol- lows. The first -ー" of those entries are all copies of el whereas the following p-n" are copies of -e-- The last entry is set to be O when n² is odd.
Note that any two distinct datasets D DGG in this collection differ in exactly n² entries. Let A be any c-differentially private algorithm for answering q. Suppose that for every i [K], with probability at least 1/2, we have that
[[A(D()) - q((()))) <
n²
(26)
32n
Note that for all E [K]. we have that (D(()) >q(D(ii) where \ Vn= n n=" even and
n²* -1
A n- (n+ 1)2
(27)
n and is independent of the choice of i. Now, we n n²* is odd. We notice that D¹ < 5 2n define an algorithm Á for answering on datasets D of size n² as follows. First, Á computes À and appends C1, - 0 as above to get dataset DD of size n. Then, it runs A on D and outputs = Hence, by the post-processing propertry of differential privacy, Á e-differentially private since A is e-differentially private. Thus for every i E [K], with probability at least 1/2, have that (((())) ((D()))2 < Tg- However, this contradicts result in the first part of the proof.
A(D),
17

---

Under review as a conference paper at ICLR 2022
Therefore, there must exist dataset (( in the above collection such that, with probability least 1/2,
||A(D()) g
n1
P
(28)
32n 5120en
Note that the & norm of the sum of entries of such ( is always n².
C.7 PROOF OF THEOREM 4.5
Proof. Let A an e-differentially private algorithm for minimizing and let @eriv denote its output. We choose the dataset D (with corresponding d,) constructed in Lemma 4.4. When contains only identical elements d, so that ming [(0; D) = 0, and
4n', D
L(Gpriv D) min L(0;D) = L(grriv D) = |10 g(D))l2 = (miin(1, P) n2
(29)
by Lemma 4.4 When n > 4n*, we denote r ||@priv (D) = Mmiin )). Notice that d, e1, -1, U all lie in 2-dimensional subspace and ||d:112 = is perpendicular to e1, we may assume d; = 02 without loss of generality. Because (D) = Xe2, we parameterize garin as follows
gariv = (α1, X 22, IT.....
(30)
where Di=1 nt? = = Now the excess loss satisfies
L(Qurio D) min L(0:D)
2 (n' 2 (A 1)2 2(A 1)02 n n
1v + 2λx² + 2x1
+ +1 n
r + x 2λ02 2r1)/n
(opening up the expression)
n
11 71
2
22
+
1V 22 (1 1)2 1)2-2))) 1/11
2
2
(dropping the first term)
2 n1 n²
1v + -A-1)33//
2
(max { [1,, -x1) 20)
n n²
r = 1[mii(1 P) )) nc
2
2 n
(n 4m Q(min(1,
_) 2))
on
18


Reviews:
[{"review_id": "TbH9iCwK8Ns", "reviewer": "Reviewer_rseh", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Private ERM is a very basic problem in private machine learning, and it’s worth understanding completely the trade off between different parameters. The prior work of Bassily et al. gave an almost complete picture, and the results in this paper are meant to fill some gaps in that work. However, a number of the results are, unfortunately, not new, and have been published before. In particular, the authors seem to not be aware of the journal version of Steinke and Ullman’s paper, which appeared in the Journal of Privacy and Confidentiality (volume 7, no 2, 2016). Theorem 5.1 there gives the tight dependence on $\\delta$ for constrained ERM with linear losses. Theorem 5.2 shows a similar lower bound for $\\ell_2^2$ loss, and it’s trivial to see that the theorem holds for unconstrained ERM. Theorem 5.2 thus nearly matches one of the main results in this paper, and matches it exactly when the error $\\alpha$ is required to be constant. The only shortcoming of Theorem 5.2 form Steinke-Ullman compared to the present paper is that the sample complexity is shown to depend on $\\alpha$ as $1/\\sqrt{\\alpha}$, which is a result of them taking a strongly convex loss.\n\nAnother weakness is that, even where the results were not published before, the techniques are very similar to prior work.", "summary_of_the_paper": "The paper describes some lower bounds for differentially private empirical risk minimization (DP ERM). The main results are:\n\n* An $\\Omega(\\sqrt{p \\log(1/\\delta)}/\\epsilon n)$ lower bound for unconstrtained ERM under approximate differential privacy. This improves on prior work of Bassily et al. in the presence of the $\\log(1/\\delta)$ term, and in the optimization being unconstrained.\n\n* An $\\Omega(p/\\varepsilon n)$ lower bound for pure differential privacy.\n\nThe proofs use now standard techniques from the literature: fingerprinting codes for approximate DP and a packing argument for pure DP.", "summary_of_the_review": "The paper proves some good-to-know lower bounds on private ERM, but a significant portion of the results have been published before. At the very least these prior results need to be discussed. I am not convinced there is enough novel material here to warrant publication. ", "strength_and_weaknesses": "", "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": "OsgsP0wJT7E", "reviewer": "Reviewer_bqs4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths:\n--This paper is the first to give tight lower bounds for approximate DP ERM for general loss functions.\n\n--Its lower bound for the constrained case improves an existing lower bound.\n\n--New techniques were developed as a modification of the regular fingerprinting codes, which are of independent interest as well, especially for those problems that are not easily reducible from one-way marginals.\n\n--The pure DP ERM lower bounds for the unconstrained setting seem tight.", "summary_of_the_paper": "This paper studies differentially private empirical risk minimisation (ERM) in the unconstrained setting. It gives tight lower bounds for approximate DP ERM for general loss functions, which also implies the same lower bound for the constrained case, which is an improvement over a classic lower bound by Bassily et al 2014. It also gives a lower bound for unconstrained pure DP ERM that recovers the result in the constrained case.", "summary_of_the_review": "--The work appears technically strong and non-trivial.\n\n--The contributions may be viewed as incremental, but the techniques developed could be useful for other problems as well.\n\n--This is a lower bounds paper, so my score for its empirical contribution is not relevant.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "317zmjKpPvE", "reviewer": "Reviewer_FRcE", "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": "**Strengths:**\n\n- The main strength of this paper is that it gives tight lower bounds for a topic that has been well studied in the literature. The bounds are presumably the last word on the subject. \n- The lower bounds are proved via a use of fingerprinting codes. These have been used in the DP lower bound literature before. Here they introduce a new notion known as Error robust biased mean fingerprinting codes. As a non-expert in the area, it is unclear to me how much novelty exists in their definition and application here. But given the results are strong, I am not overtly concerned. I would suggest that the authors perhaps come up with a shorter name. \n\n**Weaknesses:**\nThe central weakness is that the paper is very poorly written, starting from the choice of notation. For instance:\n1. In the abstract, none of the quantities appearing in the lower bound have been defined.\n2. One page 1, $\\epsilon, \\delta$ are not defined before the discussing of the gap in existing bounds in terms of $\\delta$.\n3. In discussing other paper's results in the introduction, terms like $\\theta$ and $\\alpha$ are used without any indication of what they stand for.\n4. In the definition of Fingerprinting codes (Def 3.1), the quantity $d$ appears without any prior definition in specifying $F(C_S)$. A bit of digging around shows that this is really meant to be $p$. \n\nNumerous typos like this together with the quality of exposition make this paper impossible for anyone who is not already and expert in the area, and can error-correct for the inaccuracies here. \n\n\n\n ", "summary_of_the_paper": "This paper presents tight lower bounds on differentially private ERM, a well-studied topic in the DP literature. It obtains tight bounds for both the constrained and unconstrained settings. The exact quantitative improvements are stated precisely in the abstract, and I won't repeat them here. The improvements are not staggering, but they are tight, and are presumably the final word on this topic.   ", "summary_of_the_review": "It is a strong paper based on the results, but the current version is only going to make sense to experts in the area. It is not a bad paper to accept, but it seems like it would benefit from a substantial rewrite. I would label it borderline.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-NuAPgqVHiG", "reviewer": "Reviewer_E1tY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "## Strengths\n- ERM is a fundamental (and ubiquitous) problem and this paper essentially closes the gap left in literature for DP ERM.\n- The proof requires non-trivial extensions of previous works (e.g. the mean-biased property of fingerprinting codes) which may be useful elsewhere.\n\n## Weaknesses\n- The proof of the pure-DP lower bound does not seem correct as the authors drop some terms that should be there. (More details in \"Detailed Comments\" below.)\n- The quantitative improvements for the approximate-DP case is pretty small, i.e. $\\sqrt{\\log(1/\\delta)}$ and furthermore, it seems to be known among the experts that this follows from literature. (E.g. [Song et al., AISTATS 2021] states in footnote 5 that \"dependence on the $\\delta$ parameter can be introduced into the lower bound by a generic group privacy reduction [Steinke and Ullman, 2015]\".) I still think it is helpful to be written down formally but it does question the novelty of the technique a bit.\n\n## Detailed Comments\n- *Issue with pure-DP proof*: I do not believe that the proof of Theorem 4.5 in Appendix C.7 is correct. Specifically, in the expression after $L(\\\\theta^{priv}; \\\\mathcal{D}) - \\\\min_{\\\\theta} L(\\\\theta; \\\\mathcal{D})$, you seem to completely drop the second term $\\\\min_{\\\\theta} L(\\\\theta; \\\\mathcal{D})$, which is *not* equal to zero. (E.g. since $q(\\mathcal{D}) = \\lambda e_2$, clearly the loss w.r.t. the points $e_1$ is non-zero.) It is not clear to me whether the proof would work if this term is not incorrectly drop.\n\n### Other More Minor Comments\n- I do find the entire discussion about uniqueness of Fermat point to be pretty unhelpful and misleading. Specifically, you just want the usual \"packing\" property that no solution can be good (i.e. has low excess empirical loss) for two distinct databases $\\mathcal{D}^{(i)}, \\mathcal{D}^{(j)}$. Please consider just stating it in this form.\n- You have stated in several places that the best known lower bound in the unconstrained approximate-DP case is $\\Omega\\left(\\frac{\\sqrt{p}}{\\epsilon n \\log p}\\right)$ from [Asi et al., 2021]. I'm not sure why the lower bound of [Song et al., AISTATS 2021]  doesn't give $\\Omega\\left(\\frac{\\sqrt{p}}{\\epsilon n}\\right)$ here; can you please explain more? (In particular, can't you just set $rank = p$ in their paper?)\n- Another high-level comment regarding unconstrained ERM: it is never made clear in the paper what the assumption is when you state e.g. that there is an algorithm that gives $O\\left(\\frac{\\sqrt{p \\log(1/\\delta)}}{\\epsilon n}\\right)$. My understanding is that $\\|\\theta^* - \\theta^{initial}\\|_2$ can be at most $O(1)$ for this to hold. Please consider stating this more carefully (and also emphasize that such assumption holds for your lower bound instances).\n- I would also recommend checking out the papers \"Robust traceability from trace amounts\" by Dwork et al. and \"Tight Lower Bounds for Differentially Private Selection\" by Steinke and Ullman. These two papers extend the fingerprinting code approach of Bun et al. and has results that might be closer to what you use in the approximate-DP lower bound. For example, Theorem 3 of Steinke-Ullman actually has a lower bound of the form of the correlation between the output vector and the bias of the mean; I'm suspecting that this might help simplify your approximate-DP proof a bit.\n- Page 7 Lemma 3.1: Don't you need $\\epsilon \\leq 1$ here?\n- Page 8: \"Coordinate dictionary order\" -> \"lexicographic order\"?\n- Page 9 typo: \"oversome\" -> \"overcome\"", "summary_of_the_paper": "## Summary of Contributions\n\nThis paper studies the unconstrained empirical risk minimization (ERM) under differential privacy (DP). In this setting, there is a loss function $\\ell: \\mathbb{R}^p \\times \\mathcal{X} \\to \\mathbb{R}$ and we are given $x_1, \\dots, x_n \\in \\mathcal{X}$; the goal is to output $\\theta$ that minimizes the empirical loss $L(\\theta; X) := \\frac{1}{n} \\sum_{i=1}^n \\ell(\\theta; x_i)$. The goal is to minimize the excess empirical loss $\\mathbb{E}[L(\\theta; X) - \\min_{\\theta^* \\in \\mathbb{R}^p} L(\\theta^*; X)]$. We want our algorithm to satisfies $(\\epsilon, \\delta)$-DP. Recall that the case $\\delta > 0$ is referred to as *approximate-DP* whereas the case $\\delta = 0$ is referred ti as *pure-DP*. Here we assume that $\\ell$ is 1-Lipchitz; the results easily extends to $C$-Lipchitz functions with an extra multiplicative factor of $C$ in the excess empirical loss.\n\nThe main contributions of the paper are:\n1. In the approximate-DP setting, the authors show a lower bound of $\\Omega\\left(\\frac{\\sqrt{p \\log(1/\\delta)}}{\\epsilon n}\\right)$. This improves upon the best known bound of $\\Omega\\left(\\frac{\\sqrt{p}}{\\epsilon n \\log p}\\right)$ in the unconstrained case from [Asi et al., 2021] and $\\Omega\\left(\\frac{\\sqrt{p}}{\\epsilon n}\\right)$ in the constrained case [Bassily et al., FOCS 2014]. The new lower bound also matches the known upper bound in both cases [Bassily et al., FOCS 2014].\n2. In the pure-DP setting, the authors show a lower bound of $\\Omega\\left(\\frac{p}{\\epsilon n}\\right)$.\n\nTo prove 1., the authors reduce from the 1-way marginal problem (similar to previous work). Recall that in 1-way marginal, we are given $x_1, \\dots, x_n \\in \\\\{-1, 1\\\\}^p$ and the goal is to approximate $\\frac{1}{n} \\sum_{i=1}^n x_i$; a lower bound of $\\Omega(\\frac{\\sqrt{p \\log(1/\\delta)}}{\\epsilon n})$ is known for the problem [Bun et al., STOC 2014]. The authors use an $\\\\ell_1$-distance loss function, i.e., $\\\\ell(\\\\theta; x_i) = ||\\\\theta - x_i||\\_1$. Notice that here the optimal solution is $\\\\theta^*\\_j = sign(\\sum\\_{i} z\\_{i, j})$. This in spirit is very similar to 1-way marginal but not exactly the same. Specifically, if $\\sum_{i} z_{i, j}$ is roughly around zero, then taking $\\theta_j = -1$ or $\\theta_j = 1$ does *not* effect the loss too much. Therefore, a direct \"blackbox\" reduction from 1-way marginal does not seem to work. To overcome this, the authors observe that actually in the construction of [Bun et al., STOC 2014] most of the coordinates' means are not close to zero (formalized as \"biased mean\" property in the current paper) and thus the hard instance gives the desired lower bound for DP ERM.\n\nTo prove 2., the authors use a standard packing-style construction together with the $\\\\ell_2$-distance loss function", "summary_of_the_review": "## Recommendation\n\nOverall, although the techniques are somewhat similar to previous work, I still think that the problems considered in this paper are important enough that the contributions of the paper (i.e. closing the gaps in excess empirical loss) are above the bar for ICLR. However, due to the potential correctness issue with the pure-DP lower bound, I have to give a weak reject for now. (I'm opening to changing this score depending on whether this issue can be fix and how easy the fix is.)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Meta-review: This paper gives sample complexity lower bounds for differentially private empirical risk minimization (ERM). While the reviewers agreed that the results are non-trivial, the general consensus was that the proofs are tweaks of previously developed techniques and that the main result is actually new in a rather narrow setting (specifically, for unconstrained ERM and sub-constant error parameter). Another concern was that one of the proofs (the one on pure differential privacy) was incorrect in the submission; a different proof was provided subsequently (which also closely follows prior work). Finally, the reviewers pointed out several issues with the clarity of the presentation and comparison to prior work. Given the above, this work is below the acceptance threshold.
Decision: Reject