Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of private mean estimation and attempts to develop algorithms that are instance-optimal, that is, adapting to the difficulty of the underlying instance. The authors modify the existing instance-optimality definition in differential privacy, and develop an algorithm that is nearly instance-optimal. The caveat here is that nearly instance-optimal here hides factors that depend on the dimension and privacy parameters, hence making the optimality guarantee less strong than what claimed by the authors.
main_review: The paper has two main contributions: first, a new definition of instance optimality, and second a new algorithm for mean estimation that satisfies this definition of instance-optimality. I think the algorithm is nice and the experiments show some advantages in practice (although more experiments are needed; see below). However, I don't think the instance-optimality guarantees are strong enough as they hide a factor of c=\sqrt{d}/epsilon where d is the dimension. Hence it is misleading to say the algorithm enjoys strong instance-optimality guarantees when there is a sub-optimality factor of \sqrt{d}/epsilon, which are important problem parameters. More detailed comments below.

1. Instance-optimality: one of my main concerns about this paper is the fact that the algorithms are not really instance-optimal, having a sub-optimal factor of \sqrt{d}/epsilon which is an artifact of the way the authors define instance-optimality. Therefore I would first suggest the authors to clarify this in the paper. However, this doesn't rule out the possibility that the algorithm is really instance-optimal. It would help strengthen the paper if the authors show strong instance-optimality guarantees (up to constant factors) even in the 1-dimensional setting (using for example the instance-optimality notion of local minimax based on the hardest alternative of [1]). This will at least show that the algorithm has an instance-optimal dependence on the privacy parameter.

2. Clarity: overall the paper could use more work to make it more easily readable, especially in describing the algorithms; the authors currently write the algorithms in a standard text paragraph and I strongly recommend write them in the standard way as most papers do (in a box with pseudocode).

3. Binary search algorithm: the binary search algorithm may be losing a little because of it's iterative nature and a possible candidate here is the exponential mechanism\inverse sensitivity mechanism for quantiles [1,4].

4. Bound for Gaussian mean estimation: I like the bound for Gaussian mean estimation in corollary 1 in the appendix and I would recommend to have it in the main paper too as it shows some adaptivity to the covariance matrix. Some of the experiments were unnecessary and this bound can be added instead.

5. Experiments:  first, I suggest checking larger values of epsilon in the experiments to verify the same results hold in the low privacy regime. Moreover, the algorithms seems to have good performance in practice and so it is worth trying it with different applications of mean estimation such as DP-SGD. Finally, following on the comment above for instance-optimality at least in 1-dimensional setting, I recommend doing a 1-dimensional experiment in a similar setting to [3] and compare to the following baselines: the trimmed mean algorithm of [3] and the inverse sensitivity algorithm as in [2]. 



References

[1] Hilal Asi, John Duchi, Near Instance-Optimality in Differential Privacy, arXiv 2020 

[2] Hilal Asi, John Duchi, Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms, Neurips 2020 

[3] Mark Bun, Thomas Steinke, Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation, Neurips 2019

[4] Jorg Drechsler et al., Non-parametric Differentially Private Confidence Intervals for the Median, arXiv, 2021

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new algorithm for the mean estimation problem that gets around the "curse of global sensitivity" and achieves the so-called instance optimality. Experiments including a real-data one are carried out to verify the practicality. The results are also extended to the shuffle and local models of DP.
main_review: It is always exciting to see that new DP algorithms can get around global sensitivity and most importantly, it works in practice and improves on previous algorithms.

I have one philosophical and one rigorousness/correctness criticism. Beginning with the philosophical one, the idea is that the error is a function of the dataset $D$, so why not compare it to something also depends on $D$. I agree with everything so far. My question is, why does comparing to the so-called "in-neighbors" make more sense than comparing to the diameter. The only appearance of the in-nbr after the introduction is to explain how it must be larger than the diameter. So it seems to me than in-nbr is just a story after the authors have the results regarding the diameter, which in my opinion is not more convincing than the diameter story.

Putting aside the philosophy, the in-nbr "shell" story may have some correctness issue. The main upper and lower bound seem to be Theorem 3 and 5 respectively. However, they are all stated in terms of the diameter. The statement about in-nbr is only partially supported by a one-sided inequality (Theorem 4). If in-nbr is much smaller than the diameter, then does your algorithm provide any guarantee w.r.t. in-nbr?

In my opinion, if the in-nbr thing is removed from the main story and treated as a potentially interesting connection, the paper is more correct and makes more sense.

Regarding the experiments, why not compare with other works in the line of "beyond global sensitivity"? Is coinpress the absolute best so far? More importantly, all the figures miss the comparison with the diameter $w(D)$, which is the main result. From the proof (if I understand correctly) for some specific non-Gaussian data (e.g. MNIST), the optimal factor can actually be smaller than the lower bound. If that's true, I wonder how much smaller the optimal factor can be.

Overall, I think it is a good and solid paper. However, I'd like to hear the explanation especially regarding the correctness issue before the final decision.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies instance-optimal mean estimation in the central model of differential privacy, with straightforward extensions to the shuffle and local models. The specific notion of instance optimality used is, I believe, original to this paper: the goal is to find an algorithm minimizing error over a given database D and a restricted neighborhood of databases that are neighbors and only include elements also present in D. The algorithm consists of four steps:

1) randomly rotate the database,
2) center it using a privately estimated component-wise median,
3) privately estimate a certain quantile of the L_2 norm of the resulting database and clip data to that estimated L_2 norm,
4) take a noisy empirical mean of the clipped data and de-bias.

The paper gives instance-specific upper and lower bounds that are nearly matching, up to logarithmic factors in the dimension and a discretization parameter. Experiments suggest that the algorithm performs well against existing methods.

main_review: —Originality— 

The most original theoretical component of the work might be its restricted-support definition of instance optimality. I don’t think I’ve seen that anywhere else. The algorithmic contributions are largely combinations of methods that have appeared elsewhere in the literature. 

Two specific comments:
1) The discussion of other papers about the clipped mean estimator in the related work section is not quite accurate. For example, the Amin et al. paper not only uses a quantile as the clipping norm, but attempts to select an optimal one (not the median). Their setting is certainly different, since they are attempting to bound the number of contributions, not clip the actual samples, but the idea of truncating using an optimal quantile is there.
2) It would be interesting to see how a different private quantile algorithm affects the experimental results. As far as I know, the empirically strongest private quantile algorithms are based on the exponential mechanism (http://cs-people.bu.edu/ads22/pubs/2011/stoc194-smith.pdf, Algorithm 2), not binary search.

—Quality— 

I did not check the proofs, but the algorithms and results seem believable, and proofs appear to be given when appropriate.

One omission: the submission does not provide any experimental code. Since I think the experiments are one of this paper’s strong point, the lack of code is disappointing.

—Clarity— 

In general, the paper is well-written and easy to follow. 

Some exceptions:
1) The initial presentation of the algorithm (erroneously, if I understand correctly) makes it sound like the L_2 clipping step is the first step of the algorithm. It wasn’t until I got to the section about local privacy that I realized I had it backward.
2) I think the lower bound section is missing a final statement that actually puts the separate lemmas together.
3) The experiment plots are hard to read. For example, the lines for Coinpress t= 4 and t = 10 are indistinguishable to me. Maybe make the lines thicker, or put some of these plots in the Appendix.
4) As far as I can tell, the main version of the paper doesn’t explain what the point of the random rotation step is. Some explanation appears in the proof of Theorem 3. I think this intuition should be more prominent.

—Significance— 

To me, the strongest point of this paper is that the proposed algorithm, according to the experiments, achieves better results than the existing state of the art with fewer parameters to tune, and a pretty simple algorithm overall. I think the choice of things like clipping norms is a bit of a blind spot in the existing DP literature, so it’s good to see an application to a basic problem like mean estimation — it’s actually plausible that people would implement something like this in practice. The optimality result is also nice, though the proposed notion R_{in-nbr} does seem a little too restrictive to attach that much importance to it.

That said, the omission of experiment code and the criticisms above keep me from recommending the paper too highly. However, both of those things are fixable, and I look forward to the discussion period.
limitations_and_societal_impact: The paper flatly refuses to discuss potential negative societal impact. But that doesn't seem too unreasonable for something this abstract.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper does differentially private mean estimation for empirical estimation, as opposed to statistical estimation (statistical estimation is an application of their work). It focusses on instance optimal mean estimation by introducing a new target error function of the dataset, $\mathcal{R}_{\text{in-nbr}}$. It shows both and upper bound and a lower bound for this problem. It has both theoretical and empirical results.

The theoretical results say that for this measure of error, the optimal error scales according to the diameter of the dataset in question. To prove the upper bound, the authors first use a clipped-mean-estimator, with the clipping threshold decided via a simple derivative of the error. Since that clipping estimate is a function of the dataset, it could not be used directly. So, they came up with a simple quantile estimator to do the same. They, however, first performed a random rotation, followed by a translation to fix scaling issues. Then they finally use the aforementioned clipped-mean-estimator.

They finally showed application in statistical mean estimation of high-dimensional Gaussians. They showed that they require very weak prior knowledge of the covariance matrix of the Gaussian for this. They finally compared their empirical results with the Coinpress algorithm of Biswas et al.

They extend these results to the local and shuffle models of DP, too.
main_review: Update: Edited my final evaluation based on the authors' comments.

Strengths:
1. The paper has enough theory to support their claims, and enough empirical results on both real and synthetic datasets to verify the validity.
2. They achieve optimal error rates under their notion of error.
3. They achieve the same error for statistical mean estimation of high-dimensional Gaussians as Coinpress [Biswas et al.].
4. Their experimental results show that their algorithm works as well as (and in some instances, better than) Coinpress for a wide range of parameters. This is true for real datasets, too. So, their algorithms seem practical, just in terms of the error.
5. They also extend their results to the stricter models of differential privacy: local and shuffle models.

Weaknesses:
1. I don't understand why their error metric is the "right choice" for instance-optimal mean estimation. Like their algorithm implies good results for statistical mean estimation, but the metric looks a bit contrived. I didn't see any justification in their paper about this.
2. Regarding the choice of their error metric and the optimal error. The optimal error scales with the diameter of the dataset, which could well be $u\sqrt{d}$. Unless I'm missing something, this means that if most vectors in the dataset are "close to" $(0,\dots,0)$, and there is one anomaly of $(u,\dots,u)$, then the error would be pretty bad. It would be the same as adding noise scaled to the global sensitivity. So, how are they avoiding adding large amounts of noise here?
3. The choice of colours in the graphs is quite poor, which makes them hard to understand. Squinting too much while reading a paper is never pleasant.
4. It's nice that they were honest in the checklist, but the paper writing doesn't totally adhere to the prescribed format. Like they didn't discuss the limitations of their work. Is this because they were unaware of them? No code was provided either, so I'm just supposed to "trust their results" regardless of whether I want to run their code or not.
5. I wish they had reported the running times in their experiments, and compared with the state-of-the-art algorithms. It's hard to say how practical their work is without it.
limitations_and_societal_impact: Although the authors did not discuss any of this, I feel that there shouldn't be any negative impact of this work. This is a standard type of work in differential privacy literature, which can only be useful, if not harmful.
review_title: null

Meta-review: This paper studies a fundamental problem in the differential privacy literature, namely mean estimation. It presents a novel algorithm and accompanies this with a theoretical and experimental evaluation. The reviewers all appreciate these contributions as valuable and worth accepting.

There are some reservations about the clarity of the paper. In particular, the algorithm is not clearly explained and the instance optimality claim hides a significant gap between the upper and lower bounds. Hopefully, these presentation issues can be resolved in the camera ready revision.
Decision: Accept (Poster)