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.

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.

The reviewers expressed concern on the novelty of the algorithm, but still think it is well written and should be accepted for NIPS. We encourage the authors to carefully revise the work for the final version.

I find the problem to be reasonable well motivated and the work non trivial. Analyzing subgraph counts is usually difficult and this work is no exception. The construction of the family of subgraph is novel and may find applications elsewhere. The paper is well written and the authors do a good job in communicating their ideas in a coherent and understandable fashion. My biggest concern is the disconnect between the theory and experiments.

The reviewers are all positive about the paper. The authors should seriously consider whether Section 5 in the paper as it currently stands is suitable. There is a view among the reviewers that it does more harm than good. Experiments are not really necessary in a NeurIPS paper, and if the gap between the theory set-up and the experimental set-up is large, it is probably worth removing them altogether. In any case, a proper discussion should be added if the section is retained.

Summary and Contributions: The paper considers the possibility of running algorithms directly on the compressed data to obtain significant time savings. In particular, the paper considers the compression with restricted form of grammar compressed strings that capture modern compression tools like Lempel-Ziv. Let N be the input size and T(N) n be the compressed size. The goal would be to create algorithms with running time that depend on n in the same way standard algorithms depend on N. In this paper the authors consider dot product, matrix vector product and matrix matrix product and show conditional lower bounds by reduction from problems assumed to be hard (3SUM, K-SUM) For matrix-matrix product, the authors show that even when the input matrices can be greatly compressed the output (in compresses form) still requires essentially N 2 bits, which means that any algorithm working on compressed data would need at least this time. For dot product of two vectors, the authors show several results for different assumptions.

This paper received overall good reviews and is considered novel and of interest. In terms of technical contribution it seems the improvement over previous work ([2]) is somewhat incremental. Another issue that was raised is relevance to the audience. The authors should better explain and justify the connection between their work and the current research performed in ML. Also, perhaps discussing relevant literature in ML on learning algorithms that work over lossless compressed data and how the aforementioned lower bound relates to existing techniques.

Weaknesses: This paper provides a nice advance in the theory of infeasible-start long-step IPMs, however the novelty of the approach taken and the relation of the work in the paper to prior work could use further clarity. First, solving regression problems in an A in nearly linear time, when A has many more rows than columns has been the subject of a line of research, e.g. These results, including ones based on the subspace embedding result used in this paper, readily extend to solving linear systems in A T A and this has been used by the Theoretical Computer Science papers mentioned for implementing short step IPMs. Consequently, I think it would have been beneficial to state earlier that the paper is using the known linear system solving machinery of subspace embeddings to build preconditioners (rather than just saying that "Randomized Linear Algebra" is used) and put this in the context of prior work. There may be novelty in the particular way in which the paper is using conjugate gradient and subspace embeddings, however the paper would be strengthened if it articulated how this is different than this previous literature; as the appendix points out, conjugate gradient can be replaced with other iterative methods which possibly puts the approach considered closer to the ones from the literature. In light of the previous paragraph, I think more of the novelty in the paper may lie in exactly how they handle the error from approximate linear system solves in a way sensitive to the design of the preconditioner.

The paper was overall well-received, and R4 in particular liked the combination of randomized lin algebra with IPM and the solid technical analysis. R3 brought up some major points and thought of this as a borderline paper, in part because of a narrow scope of applicability. However, overall, the AC and SAC agree this is an interesting paper (as well as well-written and technically solid), and is enough to be over the bar for NeurIPS. R3 presents a concern that some of the presentation relative to past methods is a bit misleading, and this should be addressed in the minor revisions. Please see R3s review for full details.