Venue: ICLR 2017 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Sketching is a powerful tool that has found application in a number of classical machine learning methods like least squares, kernel learning and tensor methods. It is very exciting that such application can be extended to deep neural networks, which represent the state-of-the-art for numerous learning tasks.

However, I have doubts on some aspects of the experimental and analytical settings adopted in this paper, which (in my opinion) might limit its impact in both theoretical understanding and practical applicability.

1. On the theoretical side, I found the sparse linear/polynomial classifiers assumption very troublesome. If the classifier that one wishes to learn is indeed sparse linear or sparse polynomial, why should neural networks be a good option compared to, say, Lasso or sparse logistic regression models, which are theoretically sound and even optimal for the particular function class to be learnt?

I think a more relevant setting is where one wants to learn a feedforward neural network, with perhaps sparse weights on each of its layers. It is an interesting question of whether dimensionality reduction preserves the richness of such sparse weight networks, and how aggressively one can reduce the dimension into (i.e., t in the paper), which leads to much smaller parameter space.

Also, from a learning theoretical perspective, the existence of a small neural network that approximates a sparse linear/polynomial classifier does not mean such a network can be effectively learnt. It would be good that some VC dimension /generalization aspects are analyzed as well. For example, intuitively network that operates on sketched inputs should have smaller model complexity. Does it lead to improved generalization, and how such improvement should be traded off for the richness of the network (which desires *larger* sketch length)?

2. On the practical side, it seems the most relevant application would be in NLP where inputs are naturally sparse high-dimensional vectors. Reducing the input dimension indeed reduces the size of the model and at least save storage cost. However, in practice the high dimensionality is typically dealt with using a LookupTable structure (encoding), which is not difficult to train at all, because the gradient for each data point only involves one entry in the LookupTable. I think the experiments should include comparison with such traditional approaches and comment on both accuracy and training/testing time. Also, if the argument is that the vocabulary size is so large that LookupTable cannot be stored in GPU memory, such an example should be demonstrated and show how sketching helps. 
review_title: I think the paper presents interesting ideas but some theoretical and experimental settings have room for improvement

final_score: rating: null
review_content: The paper presents some nice ideas on learning over sketched data.

- Corr3.2 is stated for a fixed x and w. Th.4.1 and Th 4.2 are stated uniformly for all x , I would expect a dependency of m and t on 
 k log(d/k) to be uniform on B_{d,k}. same thing for w . or the statement in Th 4.1 etc  should be like corr 3.2 , meaning not for all x and all w?

- Sparse linear function: If I understand correctly matrix V is a binary matrix with fixed weights and is not learned, then there is a weight w , that is learned, under a regression or classification cost.  so it seems the paper learns a linear function and not a neural network. N_{Relu} is a deterministic implementation of D^{AND}? or is V learned also in the experiments by back propagation?

Many citations on work on random projections and polynomial kernel approximations are missing and worth the comparison theoretically and practically for instance:

*Random Projections for Linear Support Vector Machines 
https://arxiv.org/pdf/1211.6085v5.pdf

* Spherical Random Features for Polynomial Kernels
https://papers.nips.cc/paper/5943-spherical-random-features-for-polynomial-kernels.pdf

- Experiments:  would be interesting to try other datasets than AG news , such as Amazon reviews, to see how m and t depends on the training size and vocabulary size (dimension) in an NLP application. 
also might be interesting to have some bounds  for m and t taking in account training size and vocabulary size.

- Minor comments:
 proper learning and improper learning are not defined in a clear way in the paper.


review_title: Uniformity of the results in Corr 3.2 Theorem 4.1,4.2 and 5.1

final_score: rating: null
review_content: Overall, I like the paper and the ideas. 

The paper is about a better dimensionality reduction techniques for sparse binary data using count sketches. The nice thing about sketching is the possibility of reconstruction, and hence any function approximation can be build using NN (as NN are universal approximator on a reconstructed vector). The arguments in the paper can be simplified for general audiences deferring the math. You can add the equation for gradient descent update (of sketches) for wider appeal.  

The experiments part can be made much better. Only showing why this is approach is superior over Gaussian projections on sparse binary datasets is not quite enough. It is known that for sparse binary datasets, minwise hashing and its variants are much better than random projections (and even space optimal for binary intersection).  See a series of papers.

1) Hashing algorithms for large scale learning NIPS 2011
2) Fast near-neighbor search for high dimensional binary data ECML 2012
3) In Defense of MinHash over SimHash AISTATS 2014
4) Is Min-Wise Hashing Optimal for Summarizing Set Intersection? PODS 14
4) On b-bit min-wise hashing for large-scale regression and classification with sparse data. Arxiv 2016

Of course, the reconstruction and polynomial approximation with minwise hashing are not clear. So there is a good argument for sketching and hence the paper has advantages on its own. However, the experiments to show that Gaussian projections are the best benchmark, for sparse datasets, is little obsolete.

 

review_title: Comparison with better hashing schemes (other than Gaussian projections)

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary of the paper:

The paper introduces sketches that approximates linear and sparse polynomials on binary data. The paper shows that such sketches can be represented as a one layer neural network. Experiments are conducted on some language processing tasks. 

Novelty:

Approximation for linear functions and polynomial have been studied in previous work, hashing here is learned as a neural network which is novel. Although I have some reserves on the connexion between the theory presented and the learning part in the paper (Please see comments below).

The main concern is that the  single layer neural network that is  learned  is not restricted to the class of  hash functions studied, hence it is hard to know if we are really testing the hashing class or just a one layer neural network.

Clarity: 

The paper is  written in a clear way.

Comments :

- The link between neural network and the hashing stems from the implementation of the 'and operation' with a relu and a binary weight V and a bias 1-t. V encodes the support of the linear weight for instance in the linear model. 
When Learning V it is regularized with l_1 norm to encourage sparsity, nevertheless the weights are not restricted to be positive to be faithful to the theory introduced in the paper. When learning V by back propagation when can try projected gradient to restrict V values to be in [0,1]. On a synthetic example where the support of w is known it would be interesting to see if V recovers the support of w. 

- Similarly  for polynomial seems group sparsity is a good regularizer, difficulty being here that the groups are unknown. Many works have tackled that issue see for instance http://www.di.ens.fr/~fbach/IEEE_TSP_shervashidze_bach_2015.pdf

- The experiments are limited to small sets.


review_title: Interesting idea, some mismatch between theory and experiments

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: This paper presents a novel sketching method in solving sparse polynomial function of a sparse binary vector within a single-layer neural network. 

Pros:1. The paper is written clearly. 
     2. I like the idea of using improper learning to reduce the dimensionality.
     3. It's novel to use neural network to do sketching decoding.
Cons:1. The experiments part is kind of weak in comparison with other sketching/projection methods.
     2. Any theoretical analysis to show why this approach needs fewer paramerters than feature hash, etc. My other concern is that since t and m are tunable, how to set these parameter for different problems? 
     3. The authors claim they have faster training. However it's not shown in experiments.
Comments: It may be interesting to compare with sparse feed-forward neural networks.
review_title: Interesting paper

Meta-review: The reviewers present a detailed set of concerns regarding the paper. In particular, the paper lacks comparison to other sketching works. The sketches used in the paper are rudimentary and in practice, there are more sophisticated sketches employed.
 
 Sketching has a different goal from function approximation. Sketching aims to reconstruct (with a certain error). The paper uses sketching in a naive manner, in the sense that the error due to the sketch is incorporated into the overall error. But presumably, networks can be compressed without achieving reconstruction on each instance, while maintaining a guarantee on the overall accuracy. I would find such a framework to be more interesting and practically relevant.
 
 On the other hand, it is important for the ICLR community to be exposed to sketching frameworks. Hence, I would like to invite the paper to be presented in the workshop, in the hope that it can spur further ideas.
Decision: Invite to Workshop Track