After discussing and considering the rebuttal, all reviewers agreed that this paper makes a nice contribution to NeurIPS and recommend acceptance. While the practical significance of the work is unclear, the reviewers agreed that its theoretical contribution was interesting. The reviewers made several important suggestions about the write-up that should be implemented in the camera-ready version of the paper (among others, fixing the abstract, and some of the claims). The authors should carefully implement them, as promised in their rebuttal.