Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Given n points in R^d, the goal is to compute a center x in R^d that minimizes the sum (dist(p,x))^z of distance to the power of z over every input point p. The main (sub-linear time) algorithm uniformly sample ~1/eps^z points and use smart processing to obtain a (1+epsilon) approximation to the desired center x. Nice application is differential privacy. Lower bounds are also provided. More generally, the authors suggest such coreset that approximates every query center.



main_review: I already reviewed a previous version of this paper. Corrections and references were added. 
There are still some concerns.

Strengths:
- Fundamental problem in machine learning and optimization
- Clear writing
- Open Python code which is not so common these days and will be appreciated by the non-theory guys
- Interesting non-trivial algorithm
- Novel approach with potential many applications.

Weaknesses:
I am mainly concern with relation to existing work and novelty.
For example, it is claimed that their coreset of size ~O(1/eps^2) improves the coreset of ~O(d/eps^2) by Feldman and Langberg  [STOC'11]. However, [STOC'11] also suggested how to remove the d using the fact that the optimal center can be approximated by ~1/epsilon points, which implies a VC-dimension that is independent of d.
Also, when the authors write O(1/eps^2) instead of 2^{100z}*O(1/eps^2) that should mention that z is fixed.


limitations_and_societal_impact: OK
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper gives sub-linear time algorithms for approximating ($1+\epsilon$ approximation) the centroid of a set of points in $d$-dimensional real space, under a distance function which is a power $z$ of the Euclidean distance. So, in particular, for $z=1$ the problem is estimating the Fermat-Weber point, and for $z=2$ the problem is estimating the mean. The algorithms use a random sample of the point set. Moreover, the paper also gives a probabilistic construction of a coreset of size independent of the dimension $d$ that estimates well the cost of any candidate center. The algorithms employ an interesting modification of an algorithm by Chen, as well as dimension reduction and a probabilistic analysis using chaining.
main_review: The sub-linear time algorithms for $z=1$ and for $z=2$ in fact do not improve upon previous work (the authors note that). In fact, for $z=2$ a rather simple probabilistic analysis would show that sampling (with replacement) uniformly at random $O(1/\epsilon^2)$ points yields a good estimate of the mean. Thus, the main contribution here is for $z > 2$. It would be useful to point out applications of larger $z$. That there exists a coreset of size $\tilde{O}(\exp(z)/\epsilon^2 )$ I believe was not known (but independence of the dimension was known). So may take is that this is the main contribution of the paper, improving the coreset size from $\tilde{O}(\exp(z)/\epsilon^4)$ to $\tilde{O}(\exp(z)/\epsilon^2)$. This contribution is substantial and thus the paper is interesting.
limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies sublinear algorithms for Power means i.e., given a set of $n$ points $a_1,\ldots, a_n$, compute a center $c$ that minimizes (upto $1+\varepsilon$) factor the objective $\sum_{i = 1}^n d(a_i, c)^z$ for any $z \ge 1$. The authors show that $\varepsilon^{-z-3}$ uniformly random samples is enough to achieve a $1+\varepsilon$ approximation. They also construct coresets of size $\varepsilon^{-2}$.
main_review: They proceed to prove that the uniform sampling works as follows:
- $q$ be an approximate solution
- Divide the $n$ points into rings based on their distance from $q$
- They argue that if the rings are very sparse, then they can be ignored as they won't contribute to the cost much
- For rings that are dense enough, uniform sampling for that ring approximates the cost well.
- To prove that uniform sampling from a ring works to approximate cost well, they consider a net over the vector of distances from a point $c$ to the set of points in $R$. They only require that the net-vectors approximate the distances of points $p$ in the ring such that $d(p, c)$ is comparable to $d(p, q)$. They then obtain a bound on the size of the net and then argue using a chaining argument that uniform sampling from the ring approximates cost of the ring with respect to any potential center $c$.

Strengths:
- Important problem for which algorithms weren't known for general $z$
- Obtain sizes that are close to optimal using a simple and nice lowerbound

Weaknesses:
- Paper is very poorly written which makes it harder to understand what is actually going on. For example, I don't understand what is happening in the expectation in line 191. The authors take expectation of supremum over all the centres $c$, but then use $v$ in the expectation and then say for every $v$ in the net. Do you have to prove the bound for every $v$ in the net or only for $v$  in the net that is close to distance vector of center $c$ or is it a typo?
- There definitely is novelty in their algorithms and proof techniques but the paper in its current form is very hard to be reviewed and check for bugs which makes me recommend not accepting the paper.

Suggestions:
- I believe once the paper is written well and easy to comprehend, the results are definitely strong enough to be accepted at a top place. I'd suggest you rewrite the Techniques section to give a much better overview of the algorithms and better explain how various lemmas help in proving the theorems.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper handles the following problem: Given a set of $n$ points in $R^d$, the goal is to compute in sublinear time an approximation for the point that minimizes the sum of euclidian distances to the power of $z$ over the input points.

Also, it suggests a coreset for this problem.

main_review: The paper provider a solid theoretical contribution. It suggests a sublinear time algorithm for approximating the point that minimizes the sum of euclidian distances to the power of $z$ over a given input set of points.
The required number of points (samples) in order to obtain with probability at least $1-\delta$ a $1+\varepsilon$ approximation to the optimal solution is $O(\varepsilon^{-z-3}log^2(1/\delta)polylog(\varepsilon^{-1}))$ (generalization over prior works)

The paper also shows that we can compute a coreset for such a problem, where the size of the coreset is $O(\varepsilon^{-2}2^{O(z)})$.

Finally, they show that the exponential dependency in $z$ is necessary for computing an approximation.

To do so, they used and improve the technique introduced by Chen [7] (i.e.,  given a fine initial guess, partition the points into rings that grow exponentially according to their costs) by showing that it is sufficient to only consider O(log \varepsilon^ {−1}) rings.

They suggest an improved analysis of sampling from rings. The state-of-the-art analysis by Feldman and Langberg [15] reduces the problem of computing a coreset to sampling in a (weighted) range space of bounded VC dimension.  They improve over the previous analyses via the chaining technique.

I liked the paper, it has a solid theory and novel ideas, it's written well. 
However, the experimental results section is very weak see Limitations section. 

Note: I couldn't check the proofs due to time constraints and since they are long.


limitations_and_societal_impact: 
1. Experimental results:
   a. The paper should have experimental results in its main body. 

   b. Why there are no graphs at all? the reader is interested in understanding the phenomena not just looking at the numbers.
  
 c.  You should compare yourself to other methods, e.g.,  
         --- to uniform sampling in all cases, 
         --- Feldman and Langberg in the relevant cases, 
         --- and many other results in the cases of z=2 (e.g., median of means).
  
 d. Also, when comparing your results to other methods (e.g., uniform sampling), the x-axis of the graph can be the time took to compute the approximation (including the time took to compute the small subset) not the size of the coreset. 
   
 e. More discussion needed, e.g., when your coreset performs better in practice (at what z values), when it is better than uniform sampling and why? 

2. Can you explain why it is interesting to solve the problem when z is not 2,1 or inf?

3. No conclusion or future work was provided.
review_title: null

Meta-review: This is a strong paper making contributions to sublinear time algorithms and coresets for power means clustering. All reviewers agree it should be accepted, and I think it is a candidate spotlight paper.
Decision: Accept (Spotlight)