This paper was very much a borderline paper, with two accept scores and one reject score. One of the concerns raised by the negative reviewer was that, while the algorithm can achieve an approximation to the best merge at each step, it is unclear how the final clustering results would compare to the standard algorithm. The authors addressed this in their rebuttal, which helped. Also, there were some issues raised about experiments as well as various minor suggestions (typos etc.). In general it seems that the concerns are mostly minor, and on the whole this paper seems to make an interesting and worthwhile contribution, so I am recommending that the paper is accepted.

Additional Feedback: EDIT: I am satisfied by the response of the reviewers that they will address the issues of clarity, after which I believe the paper represents a valuable contribution. I commend the authors for what appears to be an innovative algorithm with extremely good practical performance. I believe the paper could be a very influential one, but I feel the presentation of the work needs to be modified and improved. I think there are a few too many concessions which are made. For example, you begin with ratio cut, then change to normalised cut when you assert that the affinity matrix is made doubly stochastic.

The authors present an efficient algorithm for the sum-of-square objective. The proposed method has very impressive experimental performances and could be of interest for a broad audience. The paper contains a number of typos that should be fixed before publication.

Summary and Contributions: This work initiates the study of the following generalization of 1-bit compressed sensing. There are some unknown k-sparse vectors w_1,...,w_{ell} in R d, and one can query any vector v and get back sgn( v,w_i) for random index i. The goal is to recover the w_i's while minimizing the number of queries. This problem should not be confused with the problem of learning mixtures of halfspaces in the sense of distribution learning, as here the learner gets to pick the design vectors. A similar model in the context of regression has been studied before by Krishnamurthy et al. and Yin et al., as the authors acknowledge.

Implementations of the exponential mechanism in differential privacy often require sampling from intractable distributions. When approximate procedures like Markov chain Monte Carlo (MCMC) are used, the end result incurs costs to both privacy and accuracy. Existing work has examined these effects asymptotically, but implementable finite sample results are needed in practice so that users can specify privacy budgets in advance and implement samplers with exact privacy guarantees. In this paper, we use tools from ergodic theory and perfect simulation to design exact finite runtime sampling algorithms for the exponential mechanism by introducing an intermediate modified target distribution using artificial atoms. We propose an additional modification of this sampling algorithm that maintains its \epsilon -DP guarantee and has improved runtime at the cost of some utility.

Originality: This paper provides a clear and deep analysis of a multi-stage accelerated SGD algorithm. The results show that the expected function value gap is bounded by an exponential decay term plus a sublinear decay term related to noise. They recover the deterministic case in the single stage and zero noise special case, while reaching the lower bound O(\sigma 2/n) in the noise term. The paper contains sufficient novel results and is competitive comparing with related work. In particular, the main results reveal how to choose the right time to switch from constant stepsize to decaying stepsize, a crucial choice for the overall performance of stochastic algorithms.

This paper designs a multistage SGD algorithm that does not need to know noise and optimality gap at initialization and yet obtain optimal convergence rates. This is a well written paper with good results.

Weaknesses: It is not clear what are the main technical contributions of the paper. The paper oversells it theoretical results and the motivation for the proposed regularizer is weak. The paper misrepresents its contributions in terms of cosmetic theorems and lemma. See the points (i) - (iv) below. In the Appendix Line 70, it is written that After extending it to the case when Y is a deterministic function of X, we get the bound in Theorem 3''.

The paper was extensively discussed among the reviewers. The final outcome was that all the reviewers agreed that the theoretical part of the paper is not significantly novel and the authors have to rewrite that part (please see the updated reviews), however, the approach is novel and experimental part is strong. To evaluate the experimental part further, a new reviewer was added after the rebuttal who has a good understanding on the experimental side of the topic of adversarial data augmentation. The new reviewer confirmed that the usefulness of the entropy-based regularization term toward providing robustness against unseen shifts is significant.

Additional Feedback: Restricted to the studied problem, I would love to see more comments on the advantage of VB over frequentist approaches using, say, penalized MLE. It is my understanding that the main advantage of VB is not on estimation/prediction but on inference (e.g., establishing confidence intervals)? If so, would establishing validity of the confidence interval derived by VB (i.e., Bernstein-von Mises type results) be more interesting? They are exceedingly clear to me, and combined with the other referees' comments on novelty, made me to accordingly raise my score further. Speaking about Bernstein-von Mises type results, in case the authors missed it, V. Spokoiny had some very exciting progresses to extend them to high dimensions in a general M-estimation framework; cf.