Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.   
main_review: **Strengths:**

- 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. 
- 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. 

**Weaknesses:**
The central weakness is that the paper is very poorly written, starting from the choice of notation. For instance:
1. In the abstract, none of the quantities appearing in the lower bound have been defined.
2. One page 1, $\epsilon, \delta$ are not defined before the discussing of the gap in existing bounds in terms of $\delta$.
3. In discussing other paper's results in the introduction, terms like $\theta$ and $\alpha$ are used without any indication of what they stand for.
4. 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$. 

Numerous 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. 



 
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 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.
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.

Another weakness is that, even where the results were not published before, the techniques are very similar to prior work.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: ## 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
main_review: ## Strengths
- ERM is a fundamental (and ubiquitous) problem and this paper essentially closes the gap left in literature for DP ERM.
- The proof requires non-trivial extensions of previous works (e.g. the mean-biased property of fingerprinting codes) which may be useful elsewhere.

## Weaknesses
- 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.)
- 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.

## Detailed Comments
- *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.

### Other More Minor Comments
- 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.
- 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?)
- 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).
- 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.
- Page 7 Lemma 3.1: Don't you need $\epsilon \leq 1$ here?
- Page 8: "Coordinate dictionary order" -> "lexicographic order"?
- Page 9 typo: "oversome" -> "overcome"
summary_of_the_review: ## Recommendation

Overall, 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.)
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Strengths:
--This paper is the first to give tight lower bounds for approximate DP ERM for general loss functions.

--Its lower bound for the constrained case improves an existing lower bound.

--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.

--The pure DP ERM lower bounds for the unconstrained setting seem tight.
summary_of_the_review: --The work appears technically strong and non-trivial.

--The contributions may be viewed as incremental, but the techniques developed could be useful for other problems as well.

--This is a lower bounds paper, so my score for its empirical contribution is not relevant.
review_title: null

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