Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper takes the binary projection framework used for LSH-type applications (based on Dasgupta et al. 2017) and given training data from that framework, shows an efficient closed-form solution update for the "projection" matrix, and also derives an alternating minimization algorithm for when training data are not available (note that these are not training data in a typical supervised learning sense, i.e., they are not data features, but rather the output of a projection of the very specific type discussed in the paper).

The idea is interesting, and the recent literature suggest that the overall idea works well. This new paper seems to work much better than recent literature (and a lot faster than some), which is very encouraging. The derivation of the closed-form updates is clever and seems to be correct.  Overall, I am quite favorable for this paper.

My chief critical comment is that given the complexity of the model, is is feasible to compare to PCA-based projections as well. That is, usually PCA is not compared with these methods since a random projection method is faster. But this paper proposes data-dependent projection matrices, which is exactly what PCA does.  This paper has been implicitly assuming d << n and trying to avoid the O(n^2) cost of nearest neighbor search. Given that d << n, the complexity of the algorithm in the paper is, roughly (avoiding some logs), O((#iter) d^2 n ), since the constant "c" depends on d, and presumably d' also scales linearly with d. The (#iter) refers to the number of iterations of the alternating minimization. The actual constants are small, but it is still quadratic in d.  PCA takes O(d^2n + d^3) operations when d<n, so therefore PCA is of roughly the same complexity, and thus I'd expect you to compare to it in the numerical comparisons.

With a valid response to the issue of PCA, I would probably "strongly accept" this paper.

(Another note on comparisons: it seems Johnson-Lindenstrauss projections would be applicable, so I'd suggest running a Fast Johnson-Lindenstrauss (Ailon and Chazelle) to compare with also).

Minor notes:
- In section 3.3, how do you get complexities like d log(c) for finding the top c entries? Please cite an algorithm textbook. I might be rusty on this, but the algorithms I can think of to do this are O(  min( d log(d), d c )) operations. Same for the  d' log(k).

- A good number of sentences were grammatically incorrect or sounded awkward, e.g., paragraph 2, "people's much attention"; second sentence in section 2.2, the phrase "; while the rest get inhibited and remain silent" is not a complete phrase by itself (maybe change the semicolon to a comma). Overall, another round of proof reading would help.
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This paper proposed a Winner-Take-All model that learns a sparse binary representation for dense vectors. The method learns a binary lifting matrix to project low-dimension vectors into higher dimension, and apply WTA to get a final binary embedding with fixed number of 1s. I find this paper interesting and good extension of exiting lifting method. Please see my detailed comments:

1. The assumption of the existence of W seems strong. I understand in reality it may not hold but shouldn't affect the representation learning and downstream applications of the binary vector, but is there any work done to estimate whether it holds in general or only for d' in some range?

2. In experiments, both the supervised and unsupervised methods are compared. For the supervised version and for search accuracy evaluation, what is the ground truth? E.g. what's the label for Glove data?

3. Is the term in equation (3) first proposed in this paper or already used before? 

4. How to choose the value of d' in practice? How to balance the speed and representation quality?

5. Is there an information theoretical way to evaluate whether y has encoded near complete information from the previous vector? Or the high-dimension binary vector only works in practice without deeper theories?
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The authors developed a supervised-WTA model when training samples with both input and output representations are available, from which the optimal projection matrix can be obtained. The authors further extended the model and the algorithm to an unsupervised setting where only the input representation of the samples is available.

Overall I think this paper is clearly presented with some good experiment results. 

I have the following concerns:

1)As for the supervised setting, may I know in what kind of real-world applications we can find the OPTIMAL binary and sparse output representation?  Why can we assume they are optimal?

2)Is this algorithm can really work on a large scale problem? The mnist level dataset is far from giving strong evidence in claiming this point. A larger dataset like ImageNet is preferred. 
review_title: Official Blind Review #1

Meta-review: This paper proposes a WTA models for binary projection.  While there are notable partial contributions, there is disagreement among the reviewers.   I am most persuaded by the concern expressed that the experiments are not done on datasets that are large enough to be state-of-the-art compared to other random projection investigations.
Decision: Reject