Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors consider a specific sketching method, CountSketch, and three objective functions defined over the data design matrix: multiple-response regression (MMR), low-rank approximation (LRA), and k-means clustering. They compare the classical CountSketch with a random choices of the {-1,+1}-valued sketching matrix against: (1) Gradient descent optimization of the CountSketch weights. This was previously introduced for LRA and the authors extend it to MMR and k-means. (2) Greedy optimization of the positions of the CountSketch non-zero entries.

In order to avoid losing the worst-case guarantees of the original (non-optimized) sketch, a wrapper algorithm guarantees that the optimized sketch is considered only if it is not worse than the optimized sketch.

There are theoretical and empirical results. The first two theoretical results show that for MMR and LRA the wrapper algorithm can be implemented without having to solve the problem twice on the full dataset. Theorem 4.3 shows that greedy optimization produces a strictly better result for the LRA objective than CountSketch alone when data are sampled from a certain distribution. Theorem 4.4 finally shows that a different wrapping technique (used in a previous result for LRA), can be applied to the k-means objective.

Experiments are performed on three real-world datasets comparing CountSketch, gradient optimization, and greedy+gradient optimization on the three objectives. The bottom line is that the greedy optimization step helps significantly.

The paper is not an easy read and the clarity can be significantly improved. There is not a lot of conceptual novelty compared to previous works: just the introduction of the greedy optimization step. There is technical work to extend gradient optimization and prove the theoretical results. However, the extent of the overall technical novelty remains unclear.

It is not explicitely written that the greedy optimization step is performed only on the training part of the data.

Is greedy+gradient optimization fully deterministic?

Standard deviations are not reported in the expertiments.
review_title: Novelty unclear

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper introduces a general framework for learning and applying input-independent sparse sketches.  Then this paper instantiates this framework with three sketching applications: least-squares regression, low-rank approximation (LRA), and k-means clustering. Numerical experiments are given to demonstrate that the approach substantially decreases approximation error compared to classical and naively learned sketches. 

The idea of learning sketches and the proposed greedy algorithms are simple. They are closely related to some of the existing related works on dictionary learning. The numerical results look promising. I would suggest to give more numerical results on different datasets to exemplfy the proposed approach, as that the main contribution of the paper is on algorithmic aspect. 
review_title: The idea of learning sketches and the proposed greedy algorithms are simple. More numerical results on different datasets are needed to exemplify. 

final_score: rating: 7: Good paper, accept
review_content: Summary: 

The authors consider the problem of ``"sketching" – a popular compression technique in machine learning - used for reducing the size of the data enabling one to quickly compute an approximate solution using this compressed input. This paper introduces a general framework for learning and applying sparse sketching matrices. A two-stage procedure for learning sketches with the same sparsity pattern as CountSketch is proposed which involves first learning the sketch’s non-zero entries, and then optimizing their values. They then show how to apply the obtained sketch so that it has worst case approximation error guarantees. This procedure is applied to three applications, namely least squares regression, low rank approximation (LRA) and k-means clustering. Experimental results demonstrate a substantial reduction in the approximation error compared to other baseline approaches (including classically learned sketches). On the theoretical front, it is shown for regression and LRA that the proposed approach obtains improved error guarantees for fixed time complexity.  Additionally, it is shown for LRA (under certain input distributions) that including the first stage is strictly better than not including it. Finally, a more straightforward way of retaining worst case approximation guarantees for k-means is shown. 

----------------------------------------------------------
Reasons for score: 

Overall, I vote for accepting the paper. The procedure for learning and applying the sketching matrix seems novel and interesting, and the empirical results (Especially for LRA and least squares regression) on real datasets suggest that the proposed method does substantially improve over other baseline methods, including the classical CountSketch. The theoretical results for least squares regression and LRA also imply that their algorithm achieves a better accuracy than the classical CountSketch approach (given the same time complexity). I do have some questions mentioned in “Cons” and “Further remarks” below which I would like the authors to clarify in the rebuttal phase. 

------------------------------------------------------------------------------------
Pros:

-	Paper is in general written well barring some notational issues and explanations which were not clear to me (explained later in “Cons”)
-	The two-stage idea of learning a sketching matrix with the same sparsity pattern as in CountSketch is interesting. Instantiating the framework to problems such as: least squares regression, LRA and k-means is done nicely, and the theoretical results appear to be strong.
-	The empirical evaluation on real datasets makes a convincing case for the proposed algorithm and demonstrates that learning the CountSketch matrix can indeed be substantially better than using the classical CountSketch, on real data.

----------------------------------------------------------------------------------
Cons:

-	The sketching matrices considered in the paper are restricted to Count Sketches which have a particular sparsity pattern. So, the framework is not as general as is claimed in the abstract. 
-	Some of the notation and explanations in Section 3 are quite unclear. For example, the loss function symbol is sometimes used as L(X), sometimes as L(S, I) etc. In Algorithm 1, I don’t understand what range(n) means, and also the summation over A_i \in A_{train} seems strange. Algorithms 1,2 have a training set \mathcal{A}_{train} as input but I don’t see how this appears for the examples in Section 4; is N =1 there? In stage 2, what does the operation S[p, range(n)] = v do? In Algorithm 3, it would be helpful to explain (with an example perhaps) what the symbol \mathcal{M}(S,I) could look like. At the beginning of page 4, it is mentioned that learned sketches can encounter out of distribution inputs etc. But some of the guarantees in Section 4 (Theorems 4.1,4.2) apply for arbitrary inputs, isn’t it?
-	Theorems 4.1, 4.2 assume that the learned sketch matrices are affine \beta embeddings and hence attain a (1+\beta) approximation for the respective problems. But it is not mentioned whether this assumption can be satisfied.

---------------------------------------------------------------------
Further remarks:

-	I don’t understand why in page 2 (“Our results” para) it is written that the sketches are input-independent, aren’t the sketches derived in the paper a function of the input data (for e.g. in Alg. 1)?  
-	For theorems 4.1 and 4.2, it will be helpful to state the corresponding guarantee for the classical algorithm in the main text to enable a direct comparison.
-	In the abstract and the introduction, it is mentioned that for LRA it strictly better to include the first optimization stage. But this is shown for a couple of specific input distributions, hence should be clearly specified as such.
-	In Algorithms 1,2, sometimes "\mathcal{A}_{train}" is used and sometimes "A_{train}". If sets are being denoted with calligraphic symbols, then mention this in the notations paragraph.

----------------------------------------------------------
Post rebuttal: I have read the authors response and will go with my original score for this paper.
review_title: Recommendation to accept

Meta-review: The work falls under the setting of learning-based sketching/compressive subsampling. It extends the work of Indyk et al 2019 (including sparsity pattern optimization and some theoretical enhancements).  The reviewers agree that while the conceptual novelty including the greedy optimization step is not too much, it is nonetheless interesting and is non-trivial. However, given the highly competitive submissions at ICLR, the current scores are not sufficient for acceptance. 
Decision: Reject