Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies sample complexity for estimating quantiles in high dimensions, which is called the convex floating body (Turkey depth at least 1-q). It shows polynomial sample complexity of a differentially private algorithm for querying generic Holder statistics of the floating body with respect to the \delta_q norm. The result is under mild distributional assumptions. The general approach relies on the appropriate use of Extension Lemma to ensure privacy on all possible inputs rather than only the typical inputs. Following the general results, it gives three applications: private many-quantiles estimation, private interior point, and private sampling from the floating body. 
strengths_and_weaknesses: Strengths: The studied problem is interesting and important. It's a well-written paper and I enjoyed reading it. I appreciate the general results along with the three examples to make it more accessible. I'm not very familiar with private high-dimensional estimation literature. The paper provides a detailed discussion with relevant papers so that it makes it easier for me to understand the contribution. Moreover, I think the technical contribution is strong. I didn't read the appendix but the proof sketch is sound to me. In all three examples, the results improve upon the best-known previous results. 

Weaknesses: I have one question listed below.



questions: For the three applications, the theorems statement are like ``There exists an \epsilon-DP algorithm ...''. Can you elaborate on how to design the algorithm to achieve these bounds?
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper looks at the problem of privately estimating the properties of the convex float body. Three different properties are considered: 1. privately estimating many-quantiles estimation; 2. private interior point; 3. private uniform sampling from the floating body. Furthermore, a nice framework of estimating approximate holder queries is proposed, which should be of own interest. 
strengths_and_weaknesses: Strengths:
1. This paper looks at the problem of estimating properties of the convex body. Several upper bounds have been provided, which strictly improve the previous result.
2. A framework of estimating approximate holder queries is proposed, which may have other applications.
3. I like the idea of designing a Lipschitz estimator on a "typical dataset" and then extending it to all the possibilities of datasets by Lipschitz extension.

Weakness:
1. No lower bounds have been provided, making it hard to evaluate how "well" the estimators are.
2. Many mathematical definitions are used in this work, making it a bit hard to follow. I understood that it was unavoidable in proposing a general framework. But adding more languages and intuitions will be more friendly to the readers.
questions: Is Proposition 1 technically correct? Do not we need some condition on Lipschitz?
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper is on estimation of multivariate and high-dimensional quantiles under differential privacy constraints. Authors have considered the floating body representation of multivariate quantiles, which is related to Tukey depth. There are two streams of papers on differential privacy: one that considers worst-case scenario and the other that uses strong probabilistic assumptions. Unlike these mainstream lines of work, in this paper authors have attempted to use minimal probabilistic assumptions. Authors also propose privacy preserving interior point estimation and privacy preserving sampling from the floating body. 

strengths_and_weaknesses: Strengths:


This is a study that has several interesting directions. The problem is important, and the paper and the supplementary materials are clearly written. While I did not check the technical details carefully, the arguments seem very transparent and clear in the portions of the proof of Theorem 7 that I glanced over. I think authors focus on moving away from both the stringent worst case scenario and also the strong assumption scenario is much welcome, and this is a significant contribution from that perspective. The comparison with related works from the literature shows both authors' understanding of the challenges and the areas that need further development. 


Weaknesses:

While the technical assumptions are clearly stated, I could not find any discussion on them. For the assumptions in lines 71-77, does $R_{max}, R_{min}$ etc depend on $\theta$ or are these constants valid uniformly for al values of $\theta$? Depending on how it is interpreted, Assumption-2 (line 74) of Definition-2 in particular  seems a bit strange, and might be vacuously true. 


There are quite a few typos, in particular with capitalization (or lack of capitalization) of proper nouns. 

Also, I could not find any discussions on the limitations of this work, but since this is a purely theoretical work, this is less important. 
In practice, running computations for all possible vectors on the unit ball $S_{d -1}$ is not a viable alternative. Hence there has to be some more modifications when this work extends to algorithms and practical implementations. 
questions: Is it possible for the authors to discuss the technical assumptions more carefully and thoroughly, perhaps in the supplementary materials? Also provide a few examples of distributions and quantiles that satisfy these assumptions. 

limitations: This is a theoretical work. In practice, running computations for all possible vectors on the unit ball $S_{d -1}$ is an impossible choice. Hence there has to be some more modifications when this work extends to algorithms and practical implementations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper makes several contributions to the theory of private estimation from high-dimensional distributions, with a main focus on a) quantile estimation for $M$ marginals (where $M$ can be larger than the dimension $d$) and b) privately reporting an interior point in the so-called "floating body" of the distribution. 
Past work either makes relatively strong assumptions on the underlying distribution (e.g. subgaussian) or deal with worst-case distributions resulting in substantially worse sampling complexity. In this paper the authors seek a middle ground, identifying "minimal" sufficient assumptions under which $\varepsilon$-DP sampling bounds can be shown.
strengths_and_weaknesses: Strengths:
- The paper addresses an important type of questions in private statistics
- The technical contribution over past work appears solid (based on the authors' own description, I am not familiar with the past work)
- The simplified versions of the main results (Theorems 3 and 4) are appealing
- Uses tools from convex geometry (Steiner point of the floating body) that are novel in this context and may be useful more generally in private estimation
- The paper is well-written and clear

Weaknesses:
- The distributional assumptions made may be natural (given enough thought), but it is not clear in what sense they are "minimal" or "needed"
- For problem b) the improvement over worst-case distributions lies only in replacing approximate DP with pure DP, which is arguably mainly of theoretical interest
- The bound is on sample complexity only, there is no efficient algorithm; in particular, there is no empirical evidence that the new estimators can outperform existing ones in practice
questions: Questions:
- Can you elaborate on the sense in which you are making "minimal assumptions"?
- Can you present, at least theoretically, a class of distributions on which your estimators outperform existing ones?

Smaller questions (no need to address in rebuttal):
- Please clarify two things concerning Definition 2: Can $c$ depend on $\theta$? Can poly$(n,d)$ depend on $\theta$?
- Line 91-93: I don't get this. Can't the same sample work with high probability for all $M$ directions, giving logarithmic dependence on $M$?
- Line 106: Are you assuming $M\geq d$ and ignoring polylogarithmic factors?

Comments:
- Lines 141: Typos
- Line 195: Missing last part of sentence
limitations: As far as I can tell the authors have done a good job at discussing limitations
review_title: null

Meta-review: metareview: Estimating quantiles of a dataset is a fundamental problem. This is a challenging and interesting question in high dimensions. The authors use convex geometry to obtain algorithms for private estimation of quantiles. The reviewers all liked the work and the presentation. 

A comment from me: In the second paragraph of the abstract, you use "relies upon deep robustness results". The word deep here is highly subjective, and while one can use it in a talk, it does not fit nicely in the abstract. 
confidence: Certain
Decision: Accept