summaries: 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.    The paper describes some lower bounds for differentially private empirical risk minimization (DP ERM). The main results are:  * 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.  * An $\Omega(p/\varepsilon n)$ lower bound for pure differential privacy.  The proofs use now standard techniques from the literature: fingerprinting codes for approximate DP and a packing argument for pure DP. ## Summary of Contributions  This 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.  The main contributions of the paper are: 1. 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]. 2. In the pure-DP setting, the authors show a lower bound of $\Omega\left(\frac{p}{\epsilon n}\right)$.  To 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.  To prove 2., the authors use a standard packing-style construction together with the $\\ell_2$-distance loss function 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.
abstractText: 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( √ p log(1/δ) n ), which is believed to be tight. However, current lower bounds are off by some logarithmic terms, in particular Ω( √ p n ) for constrained case and Ω( √ p n log p ) for unconstrained case. We achieve tight Ω( √ p log(1/δ) n ) lower bounds for both cases by introducing a novel biased mean property for fingerprinting codes. As for pure-DP, we utilize a novel `2 loss function instead of linear functions considered by previous papers, and achieve the first (tight) Ω( p n ) lower bound. We also introduce an auxiliary dimension to simplify the computation brought by `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.
references.authors: Hilal Asi Vitaly Feldman Tomer Koren Kunal Talwar
references.title: Private stochastic convex optimization: Optimal rates in `1 geometry
references.venue: arXiv preprint arXiv:2103.01516,
references.authors: Raef Bassily Vitaly Feldman Kunal Talwar Abhradeep Guha Thakurta
references.title: Private stochastic convex optimization with optimal rates
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Raef Bassily Vitaly Feldman Cristóbal Guzmán Kunal Talwar
references.title: Stability of stochastic gradient descent on nonsmooth convex losses
references.venue: arXiv preprint arXiv:2006.06914,
references.authors: Raef Bassily Cristóbal Guzmán Anupama Nandi
references.title: Non-euclidean differentially private stochastic convex optimization
references.venue: arXiv preprint arXiv:2103.01278,
references.authors: Dan Boneh James Shaw
references.title: Collusion-secure fingerprinting for digital data
references.venue: IEEE Transactions on Information Theory,
references.authors: Mark Bun Jonathan Ullman Salil Vadhan
references.title: Fingerprinting codes and the price of approximate differential privacy
references.venue: SIAM Journal on Computing,
references.authors: Kamalika Chaudhuri Claire Monteleoni
references.title: Privacy-preserving logistic regression
references.venue: In NIPS,
references.authors: Kamalika Chaudhuri Claire Monteleoni Anand D Sarwate
references.title: Differentially private empirical risk minimization
references.venue: Journal of Machine Learning Research,
references.authors: Cynthia Dwork Frank McSherry Kobbi Nissim Adam Smith
references.title: Calibrating noise to sensitivity in private data analysis
references.venue: In Theory of cryptography conference,
references.authors: Cynthia Dwork Aaron Roth
references.title: The algorithmic foundations of differential privacy
references.venue: Foundations and Trends in Theoretical Computer Science,
references.authors: Vitaly Feldman Tomer Koren Kunal Talwar
references.title: Private stochastic convex optimization: optimal rates in linear time
references.venue: In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,
references.authors: Kazuto Fukuchi Quang Khai Tran Jun Sakuma
references.title: Differentially private empirical risk minimization with input perturbation
references.venue: In International Conference on Discovery Science,
references.authors: Moritz Hardt Kunal Talwar
references.title: On the geometry of differential privacy
references.venue: In Proceedings of the forty-second ACM symposium on Theory of computing,
references.authors: Roger Iyengar Joseph P Near Dawn Song Om Thakkar Abhradeep Thakurta Lun Wang
references.title: Towards practical differentially private convex optimization
references.venue: IEEE Symposium on Security and Privacy (SP),
references.authors: Prateek Jain Abhradeep Guha Thakurta
references.title: near) dimension independent risk bounds for differentially private learning
references.venue: In International Conference on Machine Learning,
references.authors: Peter Kairouz Mónica Ribero Keith Rush Abhradeep Thakurta
references.title: Dimension independence in unconstrained private erm via adaptive preconditioning
references.venue: arXiv preprint arXiv:2008.06570,
references.authors: Shiva Prasad Kasiviswanathan Hongxia Jin
references.title: Efficient private empirical risk minimization for high-dimensional learning
references.venue: In International Conference on Machine Learning,
references.authors: Shiva Prasad Kasiviswanathan Homin K Lee Kobbi Nissim Sofya Raskhodnikova Adam Smith
references.title: What can we learn privately
references.venue: SIAM Journal on Computing,
references.authors: Daniel Kifer Adam Smith Abhradeep Thakurta
references.title: Private convex empirical risk minimization and high-dimensional regression
references.venue: In Conference on Learning Theory,
references.authors: Janardhan Kulkarni Yin Tat Lee Daogao Liu
references.title: Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps
references.venue: arXiv preprint arXiv:2103.15352,
references.authors: Benjamin IP Rubinstein Peter L Bartlett Ling Huang Nina Taft
references.title: Learning in a large function space: Privacy-preserving mechanisms for svm learning
references.venue: arXiv preprint arXiv:0911.5708,
references.authors: Shuang Song Kamalika Chaudhuri Anand D Sarwate
references.title: Stochastic gradient descent with differentially private updates
references.venue: IEEE Global Conference on Signal and Information Processing,
references.authors: Shuang Song Thomas Steinke Om Thakkar Abhradeep Thakurta
references.title: Evading the curse of dimensionality in unconstrained private glms
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Thomas Steinke Jonathan Ullman
references.title: Between pure and approximate differential privacy
references.venue: arXiv preprint arXiv:1501.06095,
references.authors: Kunal Talwar Abhradeep Thakurta Li Zhang
references.title: Nearly-optimal private lasso
references.venue: In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume
references.authors: Gábor Tardos
references.title: Optimal probabilistic fingerprint codes
references.venue: Journal of the ACM (JACM),
references.authors: Di Wang Minwei Ye Jinhui Xu
references.title: Differentially private empirical risk minimization revisited: Faster and more general
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Puyu Wang Yunwen Lei Yiming Ying Hai Zhang
references.title: Differentially private sgd with non-smooth loss
references.venue: arXiv preprint arXiv:2101.08925,
references.authors: Xi Wu Fengan Li Arun Kumar Kamalika Chaudhuri Somesh Jha Jeffrey Naughton
references.title: Bolt-on differential privacy for scalable stochastic gradient descent-based analytics
references.venue: In Proceedings of the 2017 ACM International Conference on Management of Data,
references.authors: Jiaqi Zhang Kai Zheng Wenlong Mou Liwei Wang
references.title: Efficient private erm for smooth objectives
references.venue: arXiv preprint arXiv:1703.09947,
references.authors: Bun
references.title: The family of 1-way marginals on
sections.text: is O( √ p log(1/δ)
  n ), which is believed to be tight. However, current lower bounds are off by some logarithmic terms, in particular Ω( √ p
  n ) for constrained case and
  Ω( √ p n log p ) for unconstrained case. We achieve tight Ω( √ p log(1/δ)
  n ) lower bounds for both cases by introducing a novel biased mean property for fingerprinting codes. As for pure-DP, we utilize a novel `2 loss function instead of linear functions considered by previous papers, and achieve the first (tight) Ω( p n ) lower bound. We also introduce an auxiliary dimension to simplify the computation brought by `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.
sections.heading: 1 INTRODUCTION
sections.text: 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 fundamental ones are based on empirical risk minimization (ERM). Motivated by this, private ERM becomes one of the most well-studied problem in the DP literature, e.g. Chaudhuri and Monteleoni (2008); Rubinstein et al. (2009); Chaudhuri et al. (2011); Kifer et al. (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 al. (2021); Bassily et al. (2021); Wang et al. (2021).
  Roughly speaking, in the ERM setting, we are given a convex function family defined on a convex set C ⊆ Rp and a sample setD = {d1, · · · , dn} drawn i.i.d from some unknown distribution P with the objective to minimize the loss function
  L(θ;D) = 1 n n∑ i=1 `(θ; di),
  and the value L(θ;D)−minθ′∈C L(θ′;D) is called the excess empirical loss with respect to solution θ, 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 to this case. More specifically, the constrained case considers convex loss functions defined on a bounded convex set C ( Rp. Assuming the functions are 1-Lipschitz over the convex set of diameter 1, the Ω( √ p
  n ) lower bound of private ERM is given by Bassily et al. (2014), even for (special and simpler) generalized linear model (GLM).
  However, there are still several aspects that existing works don’t cover. First, existing upper bounds are off by at least a logarithmic term √ log(1/δ). For example in Wang et al. (2017); Bassily et al.
  (2019) they give upper bounds like O(L||θ0−θ ∗||2 √ p log(1/δ)
  n ), which are believed to be tight. In Bassily et al. (2014), they present a lower bound Ω( √ p
  n ) by reducing linear loss to one-way marginal results in Hardt and Talwar (2010); Bun et al. (2018). In Steinke and Ullman (2015) they achieve the tight lower bound for answering one-way marginals with respect to `1 norm, but it does not imply tight lower bounds for general loss functions by the methods in Bassily et al. (2014) directly.
  Another aspect is DP-ERM in the unconstrained case which was neglected before and gathered people’s attention recently, see Jain and Thakurta (2014); Song et al. (2021). The unconstrained case is interesting in that we can’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 = Ω(n2), the lower bound is Ω(1) and any private algorithm can not get meaningful bounds on the excess empirical loss. Song et al. (2021) proves an dimension-independentO( √ rank n ) 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 functions. As for the lower bound, Asi et al. (2021) give Ω( √ p
  n log p ) lower bound by considering `1 loss as the objective functions and reducing the results also from one-way marginals.
sections.heading: 1.1 OUR CONTRIBUTIONS
sections.text: In this paper, we fill up the two gaps together by proving an Ω(min(1, √ p log(1/δ)
  n )) tight lower bound for the excess risk of unconstrained 1-Lipschitz convex loss functions for approximate differentially private algorithms. This bound is automatically applicable in the constrained case, which improves previous results and achieve a tight lower bound for both constrained and unconstrained case. We summarize our main results as follows:
  • We prove an Ω(min(1, √ p log(1/δ)
  n )) tight lower bound for the excess risk of unconstrained 1-Lipschitz convex loss functions for approximate differentially private algorithm. This bound improves Asi et al. (2021) by a log(p) √ log(1/δ) factor in the unconstrained case
  and matches the upper bound in Kairouz et al. (2020). • We also prove an Ω(min(1, pn )) 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/δ) multiplicative better than the wellknown bound in Bassily et al. (2014) with the help of group privacy technique in Steinke and Ullman (2015).
  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 marginals.
sections.heading: 1.2 OUR TECHNIQUES
sections.text: 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-continuous at the same time. In the constrained case, the linear loss function is obviously a 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 ‘−∞’ value thus not applicable anymore. We further observe that convexity plus Lipschitzcontinuity means ‘asymptotically linear’: the sub-gradient along any direction must converge. This observation guides us 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-DP and pure-DP separately.
sections.heading: 1.2.1 APPROXIMATE-DP
sections.text: 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 Boneh and Shaw (1998); Tardos (2008).
  From a technical perspective, we change the previously used linear loss and use an `1 norm function instead where `(θ; d) = ‖θ − d‖1. `1 loss has been used in a concurrent work Asi et al. (2021) which proves an Ω( √ p
  n log p ) 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 Steinke and Ullman (2015). We observe a novel biased mean property in the fingerprinting code to successfully combine and adjust these techniques to fit the `1 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 Dk of size nk := bn/kc according to the construction of fingerprinting codes by k times, and append n− knk data points to get a final data-set D of size n. Fix any ( , δ)-differentially private algorithm A for D, if we remove one element i∗ from Dk, we can get Dk−i∗ and D−i∗ where D−i∗ and D can have at most k elements different. Running A on D and D−i∗ respectively, we get an (k , δ′)-differential privacy algorithm for Dk and Dk−i∗ . Setting k 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 to find the removed element i∗, but fingerprinting codes suggest the removed element is traceable as long as Dk satisfies the required properties and A leads to small excess empirical loss with respect to L(θ;Dk). The direct use of the biased mean property is in appending the n − knk 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 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 `1 loss functions anymore. Consider the toy case when p = 1 and Dk = {di}bn/kci=1 where di ∈ {0, 1}. Denote the mean of these bn/kc by Dk. Similarly let D be the mean values of D constructed from Dk by method above. For example, if Dk = 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 `1 loss functions) can be 0, as L(θ;D) = 1n ∑n i=1 ‖θ−di‖1 is a constant function over [0, 1]. So we need the meanDk to be biased. More specifically, we need |Dk − 1/2| should be larger than some value depending on k, then we can append n−knk 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.
sections.heading: 1.2.2 PURE-DP
sections.text: 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 `2-norm loss as a natural substitute, which is both convex and Lipschitzcontinuous. Unlike the constrained case, the `2-norm 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 Bassily et al. (2014) they have an ’adding dummy points’ procedure 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 `2 loss the minimizer might be intractable. To overcome this problem, we define the Fermat point and introduce an auxiliary dimension to simplify the messy calculation brought by `2-norm loss in our analysis. The
  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.
sections.heading: 1.3 CONSTRAINED AND UNCONSTRAINED
sections.text: 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 interest because Jain and Thakurta (2014); Song et al. (2021) found that an O( √
  rank n ) upper bound can be achieved for minimizing the excess risk of GLMs, which evades the
  curse of dimensionality.
  It has been known that the unconstrained condition is necessary for dimension independence, as pointed out by Bassily et al. (2014) in which they prove an Ω( √ p
  n ) lower bound even for minimizing constrained GLMs for the case when “rank ≤ 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 rank-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-independent algorithm in Song et al. (2021) which is based on SGD as an example. The pitfall for the dimension-independent algorithm lies in projection if SGD is modified to projected-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.
  Classic methods, like Bassily et al. (2014) usually connect linear loss to one-way marginals Bun et al. (2018), and then use lower bounds for one-way marginals to imply lower bounds for linear loss. As Bassily et al. (2014) are using results from Hardt and Talwar (2010); Bun et al. (2018) in one-way marginals and Steinke and Ullman (2015) achieves tight Ω( √ p log(1/δ)
  α ) bound by using the novel group privacy technique, one may ask whether combining Steinke and Ullman (2015) and Bassily et al. (2014) can achieve the tight lower bound in the constrained case trivially. Because Steinke and Ullman (2015) considers `1 distance but Bassily et al. (2014) considers `2 distance, there is a √ p gap between them and one can’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 (2015) from `1 norm to `2 norm, then applying the analysis in Bassily et al. (2014).
  As shown in Asi et al. (2021), proving a 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 best 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.
sections.heading: 1.4 RELATED WORK
sections.text: The existing lower bounds of excess empirical loss, i.e. the constrained case in Bassily et al. (2014) and the unconstrained case in Song et al. (2021), are all using GLM functions. The objective function used in Bassily et al. (2014) is `(θ; d) = 〈θ, d〉 which can’t be applied in the unconstrained case, otherwise the loss value would be infinite. Considering this limitation, Song et al. (2021) adopts `(θ; d) = |〈θ, 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 `1 norms, thus we can not transfer to oneway 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.
  As for the upper bounds, the private ERM Wang et al. (2017) and private Stochastic Convex Optimization (SCO) Feldman et al. (2020) for convex and smooth functions are extensively studied, where the objective is to minimize the function Ed∼P [`(θ; 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 et al. (2021); Asi et al. (2021) will need more queries (n1.375 in the worst case). Besides, most of the previous works are considering problems in `2 norm, and there are some recent results Bassily et al. (2021); Asi et al. (2021) studying the general `p norm.
sections.heading: 1.5 ROADMAP
sections.text: In section 2 we introduce background knowledge needed in the rest of the paper. In section 3 we prove the main result of this paper, an Ω(min(1, √ p log(1/δ)
  n )) lower bound for approximate DPERM in the unconstrained case. In section 4 we discuss an Ω(min(1, pn )) lower bound for the excess risk of pure DP algorithms for minimizing any unconstrained 1-Lipschitz convex loss function. Section 5 concludes this paper. All missing (technical) proofs can be found in the appendix.
sections.heading: 2 PRELIMINARY
sections.text: We consider minimizing the excess risk of unconstrained Lipschiz convex function with DP algorithms in this paper, where we let n denote the sample size and p 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). A randomized mechanismM is ( , δ)-differentially private if for any event O ∈ Range(M) and for any neighboring databases D and D′ that differ in a single data element, one has
  Pr[M(D) ∈ O] ≤ exp( ) Pr[M(D′) ∈ O] + δ. When δ > 0, we refer to the above condition as approximate differential privacy. The special case when δ = 0 is called pure differential privacy. Definition 2.2 (Empirical Risk Minimization). Given a family of convex loss functions {`(θ, d)}d∈D of θ over K ⊆ Rp and a set of samples D = {d1, · · · , dn} over the universe D, the objective of Empirical Risk Minimization (ERM) is to minimize
  L(θ;D) = 1 n n∑ i=1 `(θ; di).
  The excess empirical loss with respect to a solution θ is defined by
  L(θ;D)− L(θ∗;D) where θ∗ ∈ arg minθ∈K L(θ;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 `2 norm if the following holds for all θ, θ′ ∈ Rp:
  |f(θ)− f(θ′)| ≤ G‖θ − θ′‖2 (1)
  The Chernoff Bound will serve to prove the fingerprinting code constructed in Bun et al. (2018) satisfies our modified definition of fingerprinting code as well. Proposition 2.4 (The Chernoff Bound). Let X = ∑n i=1Xi where Xi = 1 with probability pi and
  Xi = 0 with probability 1−pi. Assume allXi are independent random variables. Let u = ∑n i=1 pi. Then P (|X − u| ≥ δu) ≤ 2exp(−uδ2/2). (2)
sections.heading: 3 APPROXIMATE DP
sections.text: In this section, we consider the lower bound for approximate differential privacy where 2−O(n) < δ < 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:
sections.heading: 3.1 FINGERPRINTING CODES
sections.text: Definition 3.1 (Fingerprinting codes). We are given n, p ∈ N, ξ ∈ (0, 1]. A pair of (random) algorithms (Gen,Trace) is called an (n, p)-fingerprinting code with security ξ ∈ (0, 1] if Gen outputs a code-book C ∈ {0, 1}n×p and for any (possibly randomized) adversary AFP and any subset S ⊆ [n], if we set c←R AFP (CS), then
  • Pr[c ∈ F (CS) ∧ Trace(C, c) =⊥] ≤ ξ
  • Pr [Trace (C, c) ∈ [n]\S] ≤ ξ
  where F (CS) = { c ∈ {0, 1}d | ∀j ∈ [d],∃i ∈ S, cj = cij } , and the probability is 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 a fingerprint to 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 decide and won’t change them, which is called the marking condition. This is the reason that we requires c ∈ F (CS). The two properties of fingerprinting codes demonstrate that one can identify at least one malicious user among all with high probability. Bun et al. (2018) extends the definition that the codes can tolerate a small fraction of errors in the marking condition. We further modify this definition, requiring the codes to have biased means, see below.
sections.heading: 3.2 OUR RESULT
sections.text: We modify the definition of fingerprinting code instead for our analysis. Definition 3.2 (Error Robust Biased Mean Fingerprinting Codes). Given n, p ∈ N, ξ, β, α1, α2, α3 ∈ (0, 1]. We say a pair of (random) algorithms (Gen,Trace) is an (n, p)fingerprinting code with security ξ and (α1, α2, α3)-biased mean, robust to a β fraction of errors if Gen outputs a code-book C ∈ {0, 1}n×p and for any (possibly randomized) adversary AFP and any coalition S ⊆ [n], if we set c←R AFP (CS), then
  • Pr[c ∈ Fβ(CS) ∧ Trace(C, c) =⊥] ≤ ξ
  • Pr [Trace (C, c) ∈ [n]\S] ≤ ξ
  • Pr[Gα1(C) ≥ (1− α2)] ≤ α3
  where Fβ (CS) = { c ∈ {0, 1}p | Prj←R[p][∃i ∈ S, cj = cij ] ≥ 1− β } , Gα(CS) = |{j :
  | ∑ i∈S cij/|S| − 1/2| ≤ α}| is the number of slightly biased columns in CS and the probability is taken over the coins of Gen,Trace and AFP .
  We use the fingerprinting code in Bun et al. (2018) for the construction of our lower bound, see Algorithm 1 in the appendix. We utilize an `1 loss and use the fingerprinting code in Bun et al.
  (2018) as our ’hard case’. To proceed, we first introduce a 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. (2011). Lemma 3.1. A condition Q has sample complexity n∗ for algorithms with (1, o(1/n))-differential privacy (n∗ is the smallest sample size that there exists an (1, o(1/n))-differentially private algorithmA which satisfies Q), if and only if it also has sample complexity Θ(n∗/ ) for algorithms with ( , o(1/n))-differential privacy.
  Notice that Lemma 3.1 discusses the sample complexity of the algorithm, therefore is independent of the (α1, α2, α3)-biased mean appeared in the above definition which only concerns the construction of the fingerprinting code. The following lemma verifies that the fingerprinting code Algorithm 1 indeed has biased mean as in definition 3.2. The proof is straightforward by using the Chernoff bound multiple times. Lemma 3.2. Algorithm 1 (the fingerprinting code) has (1/100, 999/1000, exp(−Ω(p))-biased 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 1 which we will use in proving our main theorem to satisfy the error robust biased mean property in definition 3.2, one needs roughly Ω̃( √ p) samples.
  Lemma 3.3. For every p ∈ N and ξ ∈ (0, 1], there exists an (n, p)-fingerprinting code (Algorithm 1) with security ξ and (1/100, 999/1000, exp(−Ω(p))-biased mean, robust to a 1/75 fraction of error for
  n = n(p, ξ) = Ω̃( √ p/ log(1/ξ)).
  We are ready to prove the main result of this section by using Lemma 3.3 to reach a contradiction. Consider the following `1 norm loss function. Define
  `(θ; d) = ||θ − d||1, θ, d ∈ Rp (3) For any data-set D = {d1, ..., dn}, we define L(θ;D) = 1n ∑n i=1 `(θ; di). Theorem 3.4 (Lower bound for ( , δ)-differentially private algorithms). Let n, p be large enough and 1 ≥ > 0, 2−O(n) < δ < o(1/n). For every ( , δ)-differentially private algorithm with output θpriv ∈ Rp, there is a data-set D = {d1, ..., dn} ⊂ {0, 1}p ∪ { 12} p such that
  E[L(θpriv;D)− L(θ?;D)] = Ω(min(1, √ p log(1/δ)
  n )GC) (4)
  where ` is G-Lipschitz, θ? is a minimizer of L(θ;D), and C is the diameter of the set {arg minθ L(θ;D)|D ⊂ {0, 1}n×p}, which contains all possible true minimizers.
  Due to the space limit, we leave the proof of the Theorem 3.4 in the appendix.
  The dependence on the diameter C makes sense as one can minimize a substitute loss function `′(x) = `(ax) where a ∈ (0, 1) is a constant instead, which decreases Lipschitz constant G but increases the diameter C. Note also that C > 0 whenever all possible D don’t share the same minimizer of L, which is often the case. This bound improves a log factor over Bassily et al. (2014) by combining the the group privacy technique in Steinke and Ullman (2015) 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]n×p which contains the convex hull of all possible minimizers {arg minθ L(θ;D)|D ⊂ {0, 1}n×p}. Remark 3.6. Similarly, we can derive an Ω(min(1, √ rank log(1/δ)
  n ) lower bound when we additionally 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 0’s in D.
  Remark 3.7. The third property of definition 3.2 serves the group privacy analysis to further improve a log(1/δ) term over Bassily et al. (2014). One can simplify the proof by setting k = 1 and borrow the lower bound for 1-way marginals from Bun et al. (2018), at the cost of losing this log(1/δ) term. See appendix for details.
sections.heading: 4 PURE DP
sections.text: In this section, we give a lower bound for -(pure) differentially private algorithms for minimizing unconstrained convex Lipschitz loss function L(θ;D). In the construction of lower bounds for constrained DP-ERM (Bassily et al. (2014)), they chose linear function `(θ; d) = 〈θ, 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 `2 norm loss function to over come this problem:
  `(θ; d) = ||θ − d||2, θ, d ∈ Rp (5) For any dataset D = {d1, ..., dn}, we define L(θ;D) = 1n ∑n i=1 `(θ; di). Clearly, both ` and L are convex and 1-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 a 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 `2 norm loss function.
sections.heading: 4.1 FERMAT POINT
sections.text: Definition 4.1 (Fermat point). The set of Fermat points P (D) of a datasetD = {d1, ..., dn} contains points minimizing its `2 distance to all points in D:
  P (D) = {arg min x∈Rp n∑ i=1 ||x− di||2} (6)
  One obstacle of using `2 norm as our 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 a compact subset of the convex hull of D, which encourages us to define a unique “maximum” element in P (D). To do so, we introduce the following well-order on Rp. Definition 4.2 (Coordinate dictionary order). A point x is said to be larger than y in coordinate dictionary order if and only if there exists an index i ∈ [n] such that xi > yi, and for any j < i we have that xj = yj .
  It’s straightforward to verify that CDO (coordinate dictionary order) is a well-order. Next we use 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 = {d1, ..., dn} is defined as:
  q(D) = arg max x∈P (D) CDO(x) (7)
  Such q(D) must exist for a 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. q(D) always exists for a finite dataset D.
  Note that q(D) is unique by definition and is always a minimizer of L(θ;D) over Rp. In the following subsection we are going to show that any pure DP algorithm can’t estimate q(D) with good accuracy, then prove that a large error in estimating q(D) will lead to large error in the excess risk of `2 norm loss as well, establishing the main lower bound of this section.
sections.heading: 4.2 LOWER BOUND
sections.text: In this subsection, we prove a lower bound on the excess risk incurred by any -differentially private algorithm whose output is denoted by θpriv ∈ Rp. We first introduce the following lemma showing
  that it’s impossible to find the location of the ordered Fermat point q(D) with good accuracy using a pure DP algorithm.
  The proof follows the spirit of Bassily et al. (2014), constructing datasets ’far 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 one can estimate one dataset accurately, one can estimate any other one with certain probability as well. The sum of all these probabilities is no more than 1 due to the disjointness, which leads to the desired bound.
  We denote e1 , (1, 0, ..., 0)> and let ⊕ denote the direct sum of vectors, i.e. α⊕ β = (α, β) where α ∈ Ra, β ∈ Rb are both vectors. For a vector α and a set S, we denote α⊕ S = {(α, β) : β ∈ S}. Lemma 4.4. Let n, p ≥ 2 and > 0. There is a number M = Ω(min(n, p )) such that for any -differentially private algorithm A, there is a dataset D = {d1, ..., dn} ⊂(
  0⊕ { 1√ p−1 ,− 1√ p−1}
  p−1 ) ∪ {e1,−e1, 0} with || ∑n i=1 di||2 ≤ M such that, with probability at
  least 1/2 (taken over the algorithm random coins), we have
  ||A(D)− q(D)||2 = Ω(min(1, p
  n )) (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 change the direction of the minimizer (seen as a vector), but in the unconstrained case non-linear 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 is that the Fermat point q(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. In the following theorem we are going to show that a bad estimate on the ordered Fermat point leads to higher `2 norm loss. As the fermat point is a minimizer of `2 norm loss, we can naturally translate the discrepancy in estimating q(D) to the excess risk. Theorem 4.5 (Lower bound for -differentially private algorithms). Let n, p ≥ 2 and > 0. For every -differentially private algorithm with output θpriv ∈ Rp, there is a dataset D = {d1, ..., dn} ⊂(
  0⊕ { 1√ p−1 ,− 1√ p−1}
  p−1 ) ∪ {e1,−e1, 0} such that, with probability at least 1/2 (over the algo-
  rithm random coins), we must have that
  L(θpriv;D)−min θ L(θ;D) = Ω(min(1, p n )) (9)
  The proof is based on calculation in the two-dimensional subspace spanned by q(D) and the auxiliary dimension. By observing that q(D) is perpendicular to the auxiliary dimension, we can parameterize θpriv by these two unit vectors and write down the expression of L(θpriv;D)−minθ L(θ;D) explicitly. Then by elementary inequality scaling we get the desired result. Remark 4.6. In fact the lower bound in Theorem 4.5 also holds for the case p = 1. The only difference is that the case p = 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,−1, 0} and a similar analysis to Bassily et al. (2014) to achieve this result.
sections.heading: 5 CONCLUSION
sections.text: 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 a same lower bound for the constrained case, improving the classic lower bound in Bassily et al. (2014) by log(1/δ). We also give an Ω( pn ) 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 (easily) 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 as future work.
sections.heading: A ADDITIONAL BACKGROUND KNOWLEDGE
sections.heading: A.1 GENERALIZED LINEAR MODEL (GLM)
sections.text: 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 a special class of ERM problems where the loss function `(θ, d) takes the following inner-product form:
  `(θ; d) = `(〈θ, x〉; y) (10) for d = (x, y). Here, x ∈ Rp is usually called the feature vector and y ∈ R is called the response.
sections.heading: A.2 PROPERTIES OF DIFFERENTIAL PRIVACY
sections.text: 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 of differential privacy can feel free to skip this section. Proposition A.1 (Group privacy). IfM : Xn → Y is ( , δ)-differentially private mechanism, then for all pairs of datasets x, x′ ∈ Xn, then M(x),M(x′) are (k , kδek )-indistinguishable when x, x′ differs on exact k locations. Proposition A.2 (Post processing). IfM : Xn → Y is ( , δ)-differentially private and A : Y → Z is any randomized function, then A ◦M : Xn → Z is also ( , δ)-differentially private. Proposition A.3 (Composition). LetMi be an ( i, δi)-differentially private mechanism for all i ∈ [k]. IfM[k] is defined to be
  M[k](x) = (M1(x), ...,Mk(x)) (11) thenM[k] is ( ∑k i=1 i, ∑k i=1 δi)-differentially private.
sections.heading: B FINGERPRINTING CODE
sections.text: In this section we briefly introduce the mechanism of the fingerprinting code Algorithm 1. 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 ∈ {0, 1}n×p. 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 a user i. Moreover, we require that the fingerprinting code can find one of the malicious users even when they get together and combine their codewords in any way that respects the marking condition. That is, there is a tracing algorithm Trace that takes as inputs the codebook C and the combined codeword c′ and outputs one of the malicious users with high probability.
  The sub-procedure Gen′ first uses a sin2 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 a ’score function’ Si(c′) for each user i, then report i 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 a random permutation. Trace can first ’undo’ the permutation and remove the dummy columns, then use Trace′ as a black box. This procedure makes the fingerprinting code more robust in that it tolerates a small fraction of errors to the marking condition.
sections.heading: C OMITTED PROOFS
sections.heading: C.1 PROOF OF LEMMA 3.1
sections.text: Proof. The proof uses a black-box reduction, therefore doesn’t depend on Q. The direction that O(n∗/ ) samples are sufficient is equal to proving the assertion that given a (1, o(1/n))-
  Algorithm 1 The Fingerprinting Code (Gen,Trace) 1: Sub-procedure Gen′: 2: Let d = 100n2 log(n/ξ) be the length of the code. 3: Let t = 1/300n be a parameter and let t′ be such that sin2t′ = t. 4: for j = 1, ..., d: do 5: Choose random r uniformly from [t′, π/2− t′] and let pj = sin2rj . Note that pj ∈ [t, 1− t].
  6: For each i = 1, ..., n, set Cij = 1 with probability pj independently. 7: end for 8: return C 9: Sub-procedure Trace′(C, c′):
  10: Let Z = 20n log(n/ξ) be a parameter. 11: For each j = 1, ..., d, let qj = √ (1− pj)/pj . 12: For each j = 1, ..., d, and each i = 1, ..., n, let Uij = qj if Cij = 1 and Uij = −1/qj else wise.
  13: for each i = 1, ..., n: do 14: Let Si(c′) = ∑d j=1 c ′ jUij 15: Output i if Si(c′) ≥ Z/2. 16: Output ⊥ if Si(c′) < Z/2 for every i = 1, ..., n. 17: end for 18: Main-procedure Gen: 19: Let C be the (random) output of Gen′, C ∈ {0, 1}n×d 20: Append 2d 0-marked columns and 2d 1-marked columns to C. 21: Apply a random permutation π to the columns of the augmented codebook. 22: Let the new codebook be C ′ ∈ {0, 1}n×5d. 23: return C ′ 24: Main-procedure Trace(C, c′): 25: Obtain C ′ from the shared state with Gen. 26: Obtain C by applying π−1 to the columns of C ′ and removing the dummy columns. 27: Obtain c by applying π−1 to c′ and removing the symbols corresponding to fake columns. 28: return i randomly from Trace′(C, c).
  differentially private algorithm A, we can get a new algorithm A′ with ( , o(1/n))-differential privacy at the cost of shrinking the size of the dataset by a factor of .
  Given input and a dataset X , we construct A′ to first generate a new dataset T by selecting each element ofX with probability independently, then feed T toA. Fix an event S and two neighboring datasets X1, X2 that differs by a single element i. Consider running A on X1. If i is not included in the sample T , then the output is distributed the same as a run on X2. On the other hand, if i is included in the sample T , then the behavior of A on T is only a factor of e 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, pX1(S) = (1− )pX1(S|i /∈ T ) + pX1(S|i ∈ T ) ≤ (1− )pX2(S) + (e · pX2(S) + δ) ≤ exp(2 )pX2(S) + δ
  A lower bound of pX1(S) ≥ exp(− )pX2(S) − δ/e can be obtained similarly. To conclude, since δ = o(1/n) as the sample size n decreases by a factor of , A′ has (2 , o(1/n))-differential privacy. The size of X is roughly 1/ times larger than T , combined with the fact thatA has sample complexity n∗ and T is fed to A, A′ has sample complexity at least Θ(n∗/ ). 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/ independent copies of ( , δ)-differentially private algorithms to get an (1, δ/ ) one and notice that if δ = o(1/n), then δ/ = o(1/n) as well because the sample size n is scaled by a factor of at the same time, offsetting the increase in δ.
sections.heading: C.2 PROOF OF LEMMA 3.2
sections.text: Proof. In line 5 of algorithm 1, every column j is assigned a probability pj independently where
  Pr[|pj − 1 2 | < 0.002] < 1 400 (12)
  by straightforward calculation. By the Chernoff bound (with u < p/400, δ = 1), with probability at least 1− 2 exp(−p/800) (13) , at least 1 − 1200 fraction of the columns have |pj − 1 2 | ≥ 0.002. Denote mj to be the mean of entries of column j, then by using the Chernoff bound again (with δ = 0.001), we have that with probability at least 1− 2 exp(−n/8000000) (14) a column j actually satisfies |mj − 12 | ≥ 0.001. Again by the Chernoff bound (with u ≤ 2 exp(−n/8000000)p and uδ = 0.01p) together with the union bound, at least 0.99 fraction of all columns have |mj − 12 | ≥ 0.001 with probability at least
  1− 2 exp(−p/800)− 2 exp(−pen/8000000/40000) = 1−O(e−Ω(p)) (15)
sections.heading: C.3 PROOF OF THEOREM 3.4
sections.text: Proof. Let (α1, α2, α3) = (1/100, 999/1000, exp(−Ω(p)) be the parameters in the statement of Lemma 3.3. Let k = Θ(log(1/δ)) be a parameter to be determined later and nk = bn/kc. Consider the case when p ≥ pnk first, where pnk = O( 2n2k log(1/δ)). Without loss of generality, we assume = 1 first, and pnk = O(n 2 k log(1/δ)) corresponds to the number in Lemma 3.3 where we set ξ = δ. We will use contradiction to prove that for any ( , δ)-differentially private mechanism M, there exists some D ∈ {0, 1}n×p with Gα1−1/k(D) ≤ 1− α2 such that
  E[L(M(D);D)− L(θ?;D)] ≥ Ω(p) (16) Assume for contradiction that M : {0, 1}n×p → [0, 1]n×p is a (randomized) ( , δ)-differentially private mechanism such that
  E[L(M(D);D)− L(θ?;D)] < α1α2p 1000
  for all D ∈ {0, 1}n×p with Gα1−1/k(D) ≤ (1 − α2). We then construct a mechanism Mk = {0, 1}nk×p with respect to M as follows: with input Dk ∈ {0, 1}nk×p, Mk will copy Dk for k times and append enough 0’s to get a dataset D ∈ {0, 1}n×p. The output is Mk(Dk) = M(D). Mk is (k, e k−1 e−1 δ)-differentially private by the group privacy. According to the construction above, we know that if Gα1(Dk) < 1− α2, then Gα1−1/k(D) < 1− α2 as well. We consider algorithmAFP to be the adversarial algorithm in the fingerprinting codes, which rounds the the outputMk(Dk) to the binary vector, i.e. rounding those coordinates with values no less than 1/2 to 1 and the remaining 0, and let c = AFP (M(D)) be the vector after rounding. As Mk is (k, e
  k−1 e−1 δ)-differentially private, AFP is also (k, ek−1 e−1 δ)-differentially private.
  If for some Dk ∈ {0, 1}nk×p with Gα1(Dk) ≤ 1 − α2, D (constructed from Dk as above) further satisfies
  E[L(M(D);D)− L(θ?;D)] < α1α2p 1000 .
  As we are considering the `1 loss, we can consider the loss caused by each coordinate independently. Recall thatMk(Dk) = M(D). The fraction of those nearly unbiased columns (the mean is close to 1/2) is at most 1 − α2, and we treat the worst-case error for them. For other ’α1-biased’ columns (coordinates) which take at least α2 fraction of all, ifM(D) is right for the prediction, then appending 0’s can’t change the prediction andMk(Dk) is also right. Thus we have that
  E[L(Mk(Dk);Dk)− L(θ?;Dk)] <E[L(M(D);D)− L(θ?;D)] + (1− α2)p < p
  900 .
  By Markov Inequality we know that
  Pr[L(Mk(Dk);Dk)− L(θ?;Dk)] ≥ p
  180 ] ≤ 1/5.
  c /∈ Fβ(Dk) means that there is at least βp all-one or all-zero columns in Dk, but c is inconsistent in those coordinates. Thus if c /∈ Fβ(Dk), we have that L(Mk(Dk);Dk) − L(θ?;Dk) ≥ βp/2 = p/150 > p/180 for the Dk by Lemma 3.3, implying
  Pr[c ∈ Fβ(Dk)] ≥ 4/5. (17)
  By the first property of the codes, one also has Pr[L(Mk(Dk);Dk)− L(θ?;Dk) ≤ p/180 ∧ Trace(Dk, c) =⊥]
  ≤ Pr[c ∈ Fβ(Dk) ∧ Trace(Dk, c) =⊥] ≤ δ.
  Recall that the arguments above are for those Dk ∈ {0, 1}nk×p with Gα1(Dk) ≤ 1 − α2, which happens with probability at least 1 − α3 by the third property of fingerprinting codes. By union bound, we can upper bound the probability Pr[Trace(Dk, c) =⊥] ≤ 1/5 + δ + α3 ≤ 1/2. As a result, there exists i∗ ∈ [nk] such that
  Pr[i∗ ∈ Trace(Dk, c)] ≥ 1/(2nk). (18)
  Consider the database with i∗ removed, denoted by Dk−i∗ . Let c′ = AFP (M(Dk−i∗)) denote the vector after rounding. By the second property of fingerprinting codes, we have that
  Pr[i∗ ∈ Trace(Dk−i∗ , c′)] ≤ δ.
  By the differential privacy and post-processing property ofM,
  Pr[i∗ ∈ Trace(Dk, c)] ≤ ek Pr[i∗ ∈ Trace(Dk−i∗ , c′)] + ek − 1 e− 1 δ.
  which implies that
  1
  2nk ≤ ek+1δ. (19)
  Recall that 2−O(n) < δ < o(1/n), and Equation (19) suggests k/n ≤ 2ek/δ for all valid k, but it is easy to see there exists k = Θ(log(1/δ)) to make this inequality false, which is contraction. As a result, there exists some D ∈ {0, 1}n×p with Gα1−1/k(D) ≥ (1− α2) subject to
  E[L(M(D);D)− L(θ?;D)] ≥ α1α2p 1000 = Ω(p).
  For the ( , δ)-differential privacy case, setting Q to be the condition
  E[L(M(D);D)− L(θ?;D)] = O(p).
  in Lemma 3.1, we have that any ( , δ)-differentially private mechanismM which satisfies Q for all D ∈ {0, 1}n×p with Gα1−1/k(D) ≥ 1− α2 must have n ≥ Ω( √ p log(1/n)/ ).
  Now we consider the case when p < pnk , i.e. when n > n ? , Ω(
  √ p log(1/δ)/ ). Given any
  dataset D ∈ {0, 1}n?×p with Gα1−1/k(D) ≥ 1 − α2, we will construct a new 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}p. If n− n? is odd, we append n−n
  ?−1 2 points
  0, n−n ?−1
  2 points {1} p and one point {1/2}p.
  Denote the new dataset after appending by D′, we will draw contradiction if there is an ( , δ)differentially private algorithmM′ such that E[L(M(D′);D′)−L(θ?;D′)] = o(n?p/n) for all D′, by reducing M′ to an ( , δ)-differentially private algorithm M which satisfies E[L(M(D);D) − L(θ?;D)] = o(p) for all D with Gα1−1/k(D) ≥ 1− α2.
  We constructM by first constructing D′, and then useM′ as a black box to getM(D) =M′(D′). It’s clear that such algorithm for D preserves ( , δ)-differential privacy. It suffices to show that if
  E[L(M′(D′);D′)− L(θ?;D′)] = o(n?p/n), (20) then L(M(D);D) − L(θ?;D) = o(p), which contradicts the previous conclusion for the case n ≤ n?. Specifically, if n− n? is even, we have that
  n?E[L(M(D);D)− L(θ?;D)] = nE[L(M′(D′);D′)− L(θ?;D′)]. and if n− n? is odd we have that
  n?E[L(M(D); )D − L(θ?;D)] ≤ nE[L(M′(D′);D′)− L(θ?;D′)] + 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 L(θ∗;D) are the same. And the distributions of the M(D) and M′(D′) are the same 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}p, which can only increase the loss (‖1/2p − θ∗‖1) by p/2 in the worst case.
  Combining results for both cases we have the following:
  E[L(θpriv;D)− L(θ?;D)] = Ω(min(p, pn ∗
  n )) (21)
  To conclude, observe that G = √ p and C = √ p. In particular, let D = (d, ..., d)> ∈ {0, 1}n×p contain n identical copies of rows d ∈ {0, 1}p, θ∗ = d. Going over all such D, we find that the set {arg minθ L(θ;D)|D ⊂ {0, 1}n×p} contains {0, 1}p, with diameter at least √ p. Meanwhile, its diameter can’t exceed √ p obviously.
sections.heading: C.4 DETAILS OF REMARK 3.7
sections.text: We give a sketch of Remark 3.7. In Bun et al. (2018) they prove the following lower bound for 1-way marginals: Proposition C.1 (Corollary 3.6 in Bun et al. (2018)). The family of 1-way marginals on {0, 1}d has sample complexity at least Ω̃( √ d) for (1/3, 1/75)-accuracy and (O(1), o(1/n))-differential privacy.
  Inspecting the proof we find that the constant 1/3 in the above proposition is chosen casually, and can be replaced by any constant c < 1/2 for free, as the proof only requires 1 − c is rounded to 1 and c is rounded to 0 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/300 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 1’s in column j’ as the range of prediction is restricted in [0, 1] and choose c + 0.001 > 1/2, thus leading to error on `1 norm loss.
sections.heading: C.5 PROOF OF PROPOSITION 4.1
sections.text: Proof. We assume P (D) 6= ∅ 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) 6= ∅, the function f(x) = ∑n i=1 ||x − di||2 is continuous and non negative, which implies its image is of the form [a,∞). Therefore the pre-image of the open set (a,∞) 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 a1 , argmaxx∈P (D)x1 exists, and the ordered Fermat point must lie on the restriction of P (D) on {x|x1 = 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 a single point.
sections.heading: C.6 PROOF OF LEMMA 4.4
sections.text: Proof. By using a standard packing argument we can construct K = 2 p−1 2 points d(1), ..., d(K) in 0⊕ { 1√ p−1 ,− 1√ p−1} p−1 such that for every distinct pair d(i), d(j) of these points, we have
  ||d(i) − d(j)||2 ≥ 1
  8 (22)
  It 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? = p160 . Let’s first consider the case where n ≤ 4n ?. We construct K datasets D(1), ...,D(K) where for each i ∈ [K], D(i) contains n copies of d(i). Note that q(D(i)) = d(i), we have that for all i 6= j,
  ||q(D(i))− q(D(j))||2 ≥ 1
  8 (23)
  LetA be any -differentially private algorithm. Suppose that for everyD(i), i ∈ [K], with probability at least 1/2, ||A(D(i))− q(D(i))||2 < 116 ,i.e.,Pr[A(D
  (i)) ∈ B(D(i))] ≥ 12 where for any dataset D, B(D) is defined as
  B(D) = {x ∈ Rp : ||x− q(D)||2 < 1
  16 } (24)
  Note that for all i 6= j, D(i) and D(j) differs in all their n entries. Since A is -differentially private, for all i ∈ [K], we have Pr[A(D(1)) ∈ B(D(i))] ≥ 12e
  − n. Since all B(D(i)) are mutually disjoint, then
  K
  2 e− n ≤ K∑ i=1 Pr[A(D(1)) ∈ B(D(i))] ≤ 1 (25)
  which implies that n > 4n? for sufficiently large p, contradicting the fact that n ≤ 4n?. Hence, there must exist a dataset D(i) on which A makes an `2-error on estimating q(D) which is at least 1/16 with probability at least 1/2. Note also that the `2 norm of the sum of the entries of such D(i) is n.
  Next, we consider the case where n > 4n?. As before, we construct K = 2 p−1 2 datasets D̃(1), · · · , D̃(K) of size n where for every i ∈ [K], the first n? entries of each dataset D̃(i) are the same as dataset D(i) from before whereas the remaining n − n? entries are constructed as follows. The first bn−n ?
  2 c of those entries are all copies of e1 whereas the following b n−n?
  2 c are copies of −e1. The last entry is set to be 0 when n− n? is odd.
  Note that any two distinct datasets D̃(i), D̃(j) in this collection differ in exactly n? entries. Let A be any -differentially private algorithm for answering q. Suppose that for every i ∈ [K], with probability at least 1/2, we have that
  ||A(D̃(i))− q(D̃(i))||2 < n?
  32n (26)
  Note that for all i ∈ [K], we have that q(D̃(i)) = λq(D(i)) where λ = n ?
  √ n2−2nn? if n− n ? is even and
  λ = n? − 1√
  4bn−n?2 c2 − (n? − 1)2 (27)
  if n − n? is odd. We notice that n ? n ≤ λ ≤ 2n?
  n , and is independent of the choice of i. Now, we define an algorithm Ã for answering q on datasets D of size n? as follows. First, Ã computes λ and appends e1,−e1, 0 as above to get a dataset D̃ of size n. Then, it runs A on D̃ and outputs A(D̃) λ . Hence, by the post-processing propertry of differential privacy, Ã is -differentially private since A is -differentially private. Thus for every i ∈ [K], with probability at least 1/2, we have that ||Ã(D(i)) − q(D(i))||2 < 116 . However, this contradicts our result in the first part of the proof.
  Therefore, there must exist a dataset D̃(i) in the above collection such that, with probability at least 1/2,
  ||A(D̃(i))− q(D̃(i))||2 ≥ n? 32n ≥ p 5120 n (28)
  Note that the `2 norm of the sum of entries of such D̃(i) is always n?.
sections.heading: C.7 PROOF OF THEOREM 4.5
sections.text: Proof. LetA be an -differentially private algorithm for minimizingL and let θpriv denote its output. We choose the dataset D (with corresponding di) constructed in Lemma 4.4. When n ≤ 4n?, D contains only identical elements di so that minθ L(θ;D) = 0, and
  L(θpriv;D)−min θ L(θ;D) = L(θpriv;D) = ||θpriv − q(D)||2 = Ω(min(1,
  p
  n )) (29)
  by Lemma 4.4. When n > 4n?, we denote r , ||θpriv − q(D)||2 = Ω(min(1, p n )). Notice that di, e1,−e1, 0 all lie in a 2-dimensional subspace and ||di||2 = 1 is perpendicular to e1, we may assume di = e2 without loss of generality. Because q(D) = λe2, we parameterize θpriv as follows
  θpriv = (x1, λ+ x2, x3, ..., xp) (30) where ∑p i=1 x 2 i = r 2. Now the excess loss satisfies
  L(θpriv;D)−min θ L(θ;D)
  ≥ (n? √ r2 + (λ− 1)2 + 2(λ− 1)x2 + b n− n? 2 c √ r2 + 1 + λ2 + 2λx2 + 2x1 + bn− n ? 2 c √ r2 + 1 + λ2 + 2λx2 − 2x1)/n
  (opening up the expression)
  ≥ (bn− n ? 2 c √ r2 + (λ− 1)2 + 2x1 + b n− n? 2 c √ r2 + (λ− 1)2 − 2x1)/n
  (dropping the first term)
  ≥ (bn− n ? 2 c √ r2 + (λ− 1)2)/n
  (max{x1,−x1} ≥ 0)
  ≥ bn− n ? 2 c · r n = Ω(min(1, p n ))
  (n > 4n?, r = Ω(min(1, p
  n )))