Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper gives a meta algorithm for speeding up coreset constructing algorithms for the distribution compression problem.

The benefit of this meta algorithm is that its running time is faster by a square-root factor (e.g. quadratic to linear) while keeping the error rate roughly the same: only a factor of 4 worse.

The method is very simple: split the input into four pieces of size n/4 each, recursively solve each of them, then combine all four answers into a set and take a coreset of this set.

The speed-up in running time is immediate (just because of how recursive formulas work) and the error bounds are also rather clear.
main_review: The strength of the paper is obvious: it gives a substantial improvement in the running time for a natural and important problem.

The main new idea is very simple. One could even say obvious. In my opinion it's only obvious in hindsight, or obvious to experts in fine-grained complexity (a subfield of theoretical computer science where one tries to classify problems into linear vs quadratic vs cubic, etc.). Therefore, I think this paper is valuable to the broader community.
summary_of_the_review: While simple in hindsight, I think the new idea of this paper deserves being published in this venue.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The topic of the study is distribution-compression/thinning algorithms for Monte-Carlo estimation of functions in RKHS, i.e., given a set of $n$ points, such that uniform distribution on these n points approximates an underlying distribution (with respect to integration over functions in a RKHS) with a certain error, output a set of $m$ points $(m \ll n)$ that has a similar error.
The paper proposes three reductions/meta-algorithms to speed up existing distribution-compression algorithms while maintaining the error guarantee of the original algorithms.
The main result is that the proposed reduction improves the runtime of existing algorithms (with quadratic runtime or more) by a quadratic factor without increasing the corresponding error by a polylog factor.
main_review: I believe the paper makes a good contribution to the field by proposing a general reduction scheme that improves the runtime of existing algorithms at cost of minimal increase in error.
The underlying idea is clear and simple (in hindsight), which adds to the strength of the contribution. Thus I recommend accept. I have following suggestions/comments, and look forward to hearing back from authors.

## Major Remarks

1. I think the proof sketch of MMD guarantees should be added to the main text because I found this result to be more fundamental than Theorem 1, which focuses on a single $f$. 

	+ I also found the full proof of Theorem 2 (in Appendix) difficult to follow. It would be helpful to the reader if additional details are provided. For example, how is the $\lambda_{max}$ related to $\||\psi_{CP}\||\_k$, how does one get $u_{\tilde{\psi}_k,j}$? etc.

2. (Page 7, fourth line) why one should not use RecHalve directly? 
3. (Example 1) What is the main difference between the recursion-based reduction proposed in this paper and the recursion-based thinning (KT-SPLIT) of Dwivedi and Mackey?

## Minor Remarks

1. I believe the clarity and presentation of the paper can be significantly improved by fixing the following: grammatical issues, omitted words, defining concepts *before* using them in text. I suggest the paper should be proofread carefully to improve the clarity. I am listing a subset of errors that I found: 
	+ (appendix) $ell$ in the text before Lemma 3. 
	+ (abstract) The sentence containing "quadratic-time input" did not parse for me.
	+ Some expressions that were used before defining them:  KT ("Our contributions"), 2-thinning  ("Overview of Compress++"), $\sigma^2,c,r_{CP}$ (Page 3, last line)
	+ KT should be KT-SPLIT in last line of Example 1?
	+ space is missing between several words, for example, "simpleyet" (page 6).
	+ $\Gamma_+^{\mathcal F}$ instead of $\Gamma_+^{\mathcal f}$ at several places.
	+ Theorem 4 statement: "is" 
	

2.  Please add citation for the claim of $\Omega(n^{-1/4})$ error in the second paragraph on Page 1.

3. Page 3, Line 1: I suggest changing "closed under multiplication" to "closed under scaling".

4. At several points, the paper uses that $\sigma(\cdot)$ and $c(\cdot)$ are monotonic. It is explicitly mentioned for one calculation (Remark 1)  but not everywhere. Either it should be mentioned everywhere or change the definition to include monotonicity.

5. (Section 3, 1st paragraph) What does "significantly improved error rate" mean?


----
Update: I thank the authors for their response. I am satisfied with the response and continue to recommend accept.

summary_of_the_review: As mentioned earlier, the paper makes a good contribution and thus I recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces meta algorithms "Compress" and "Compress++" that take existing thinning algorithm as a subroutine and improves on their runtime while incurring marginally more error. 

The algorithm "Compress" runs in recursive fashion: divides input set into four parts, runs Compress on each part independently, combines the resulting sets and halves the combined set using "HALVE" algorithm. As an example, the authors demonstrate that one can use KT-SPLIT as HALVE algorithm and get faster runtimes to compress albeit suffering extra error (upto log factors). Compress ensures that KT-SPLIT runs on sets of much smaller size.

 They build on Compress to obtain better error rates while sacrificing on runtimes (upto log factors). For this, they use the thinning algorithm on much smaller set obtained after running Compress. The runtimes are quite easy to derive based on recursion of algorithms. They use sub-gamma property to prove the error guarantees of the algorithms. They demonstrate the faster runtimes of their algorithms using high dimensional Monte Carlo samples.
main_review: The paper introduces a new framework to improve on runtime of existing thinning procedures. The framework is quite simple and analysis is quite straight forward (except error analysis using Sub-Gamma) . Eventhough the framework is simple, it helps improve the runtime of existing thinning algorithms (from magnitude of days to hours). The runtime improvements are only pronounced for higher input size (10^3) (not sure if mentioned applications have such high sample size requirements).

summary_of_the_review: Even though the framework and analysis is simple, I believe community can benefit from these faster thinning meta algorithms. I am not sure how well "distribution compression" fits ICLR.
review_title: null

Meta-review: This paper proposes a simple meta algorithm to speed up data thinning algorithms with good theoretical guarantees. The method is both theoretically interesting and useful for practical applications.
Decision: Accept (Poster)