The reviewers agree that this paper presents a novel framework and approach towards robust non-parametric methods. Nevertheless, the authors are encouraged to further improve their empirical study.

Update: I have read the author response and appreciate that they addressed some of my comments. The focus is on obtaining statistical guarantees about the generalization. This is a highly relevant direction to the growing body of work on decentralized training. The paper is generally well written, contains very original ideas, and I was very excited to read it. The main reason I didn't give a higher rating was because of the limitations listed at the beginning of Sec 5. I commend the authors for acknowledging them.

This paper provides a nice and clean characterization of a decentralized learning problem. The result is perhaps unsurprising in its form, but the analysis is far from trivial. There are some nontrivial assumptions for their results to hold which perhaps limit the scope of this result but do suggest interesting avenues for future research in this increasingly important area. Overall, this is a solid contribution and should be of interest to NeurIPS attendees who work in optimization and distributed systems.

The paper considers a Bayesian decision theoretic formulation of the problem of minimizing the number of queries to identify the desired number of positive instances (instances with positive labels), given a probabilistic model of the labels in the dataset. This formulation is motivated by the material and drug discovery problems. The problem is properly formulated and contrasted with the recently suggested budgeted-learning setting, where the goal is to identify the largest number of positive instances given a fixed budget on queries. Further the authors show that the optimal Bayesian policy is hard to compute and hard to approximate. However, further assuming certain conditional independence the policy can be approximated efficiently using the negative-poisson-binomial distribution, for which the authors propose computationally-cheap expectation estimates.The resulting policy is compared to several other alternatives, and it is shown to obtain overall superior performance in both material discovery and drug discovery datasets.

Weaknesses: The authors consider the supremum of absolute deviation \sup_f \hat{E}_x[f]-E_D[f] . In statistical learning theory, it suffices to estimate \sup_{f}[E_D[f]-\hat{E}_x[f]], i.e., there is no absolute value. Therefore, the results in this paper may not be interesting since centralization does not help for a smaller complexity that is sufficient for generalization. The centralization in terms of expectation has been considered in the literature for both Rademacher averages and variances. This paper extends this centralization to empirical centralization.

Additional Feedback: Q1.In the end-to-end training section, do the authors learn embeddings by clustering all points together? As in are train, test, and dev points all clustered together or are each of them clustered separately? If all the points are clustered separately then it might not be a reasonable thing in practice because in practice, we do not have access to test data while training, and nor should any test data be used for doing any sort of training. If authors perform some clustering on test points as well, then it might not be reasonable to assume access to *all* test data at test time. Evaluation on test data should preferably be possible even when test data arrives in an online fashion.

Throughout discussion among reviewers with the author response, all reviewers agree with the novelty and the significance of the theoretical contribution of this paper, which provides approximation guarantees of the proposed embedding. While reviewers raised a concern about empirical performance regarding with computational cost and parameter tuning, they are common problems for other clustering approaches and are not crucial problems of the proposal. Hence I recommend acceptance of this paper.

Weaknesses: * In [71] there are several theoretical guarantees both for convex and non-convex cases. I am wondering why they are not mentioned in Table 2. On the other hand, their analysis also covers the case where the domain doesn't need to be compact. Doesn't this reduce the novelty of this paper? I am willing to increase my grade if this concern is addressed. It would be interesting to see a comparison between the results in this paper and theirs.

After discussion, all reviewers agree that this paper makes a good contribution to the study of clipped sgd.

This paper proposes a new approach to approximating hierarchical agglomerative clustering (HAC) by requiring that at each round, only a gamma-best merge be performed (gamma being the multiplicative approximation factor to the closest pair). Two algorithms are introduced to approximate HAC - one for Ward and one for Average linkage. In both cases, the algorithms rely on using approximate nearest neighbor ANN as a black box. In addition, a bucketing datastructure is used in Wards algorithm and a subsampling procedure in used for Average linkage to guarantee the subquadratic runtime. This is a new contribution to the theoretical literature on HAC, a provable subquadratic algorithm for (an approximation to) HAC cases other than single linkage.