Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper propose utilizing the existing "lottery ticket" result for constructing binary neural networks. This work has some novelty, in the sense that I haven't seen any other papers on untrained binary neural networks. The experimental results looks good.

However, I have some concerns on this paper.
1. This paper, at least the main text, is not self-contained. The writing needs significant improvement. The main contribution of the paper, section 2, is only one-page long. Neither the theory nor the algorithm are well explained in the main text. Moreover, the algorithm relies heavily on the edge-popup algorithm, which is not explained even in the supplementary material. The title is also somewhat too long.
2. Though the proposed algorithm achieves excellent results in terms of parameter count and accuracy, I think the comparison is somewhat unfair. The subnetwork is sparse, and can be much slower on real hardware. Moreover, pruning from a larger network is known to achieve better result than training a smaller network from scratch, but the baselines does not utilize this.
3. There lacks any discussion on the real time consumption of the proposed network.
4. Time consumption of training should also be reported.

Post rebuttal
====

Thanks the authors for clarifying and revising the paper. The updated version does look much clearer to me, so I updated my ratings. 

I am still wondering the difference of biprop vs. a classical quantization-aware training for ternary networks. I did read the response to R3. From my understanding it seems that:
1. biprop doesn't count 0 as a parameter, while TWN does;
2. biprop prunes a larger network (WRN50), while TWN trains a network of the original size (ResNet-50);
I am not sure if the superiority of biprop comes from these reasons, instead of LTH itself. biprop still looks more like a QAT algorithm than a LT-finding algorithm in the sence that
1. it does not train the pruned network after finding the LT as the original LTH paper;
2. it directly learns the binary weights.
Just out of curiosity, but I think clarifying these concerns would make the paper stronger.
review_title: This paper has some good results, but the writing needs to be improved

final_score: rating: 7: Good paper, accept
review_content: The authors propose a stronger lottery ticket hypothesis in this paper – the multi-prize lottery ticket hypothesis. In particular, the new hypothesis seeks answer to the required amount of over-parameterization for a randomly initialized network to become able to compress to a sparse untrained binary subnetwork with on-par accuracy. The authors prove the existence of such subnetwork and show the bounds on over-parameterization. The paper proposes new methods to get the binary-weight tickets and the binary-activation tickets, where binary-weight tickets are subnetworks with weights as binary, and binary-activation tickets have the activation function in the forward propagation as binary. As binary networks can largely reduce the computational complexity for inference, this work has practical importance especially for applications with constraints for memory and power. The paper has many simulation results to support the theoretical guarantees, and the proposed approach on binary-weight networks has advantages over existing methods.

The paper has sufficient and novel contributions, both for the theoretical results on binary subnetworks and the empirical evaluations that reveal the efficiency of the algorithm on binary-weight subnetworks, so that I recommend this paper for publication. 

Here are some minor concerns.

[a] It would be more convincing if the authors could further highlight the technical novelty of this work for the proof of Theorem 1. Compared with Malach 2020 “Proving the lottery ticket hypothesis: pruning is all you need”, the authors can highlight what key differences are needed for proof of the binary network.

[b] For the comparison of full precision network and the MPT from this paper, it can be useful if the computational complexity is shown, where the complexity for MPT would be for the algorithm to find the mutli-prize tickets in an over-parameterized network.

[c] The MPT 1/1 seems not to perform as well compared to trained binary activation network, which may reduce the quality of paper. It is good that the authors mention future work for MPT 1/1 network to attain state-of-art results of binary activation network.

[d] Some of the references seem to lack information, e.g. Malach 2020, Orseau 2020, both of which do not have the venue or journal names.

[e] A question: for the binary weights subnetworks, what does it mean by 20 million parameters? The weights can only be -1 or 1, so the network has 20 million of -1 or 1, but they do not require any multiplication at the inference stage?

review_title: Review Paper 738

final_score: rating: 7: Good paper, accept
review_content: This work investigated a method of finding a subnetwork of redundant binary networks to gain an overall advantage over pruned or quantized networks.

One main concern of the reviewer is the similarity between the paper's approach---training a mask over a binary network---and the conventional ternary network.  Are the masked weights analogous to the 0 of the ternary networks, while the unmasked weights are in {-1, 1}? In that case, it's fairer to compare with ternary networks with 0 counted into the total params.

Following this analogy, it is also misleading to claim that the network is "untrained", as to minimize the loss, any binarized weights can be updated to 0(masked), although indeed the weight update across 0 is forbidden. 

The theory works of this paper are strong and prove that the expressive power of redundant binary(or ternary?) networks can match their denser counterpart.  Still, the question to clarify here is that whether "subset (lottery ticket) + binary network" equals to "ternary network". 

In general, the paper is well written and the theoretical and experimental works support the authors' claim. The reviewer would recommend accepting the paper on the condition that the authors can address the comparison with the ternary network fairly.


review_title: lottery mask + binary = Ternary ?

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes an innovate method based on lottery ticket hypothesis to prune a BNN (parameters are only -1(0) and +1, it can be viewed as an extreme case of quantization) from a dense NN. It focuses on learning a mask to prune the NN instead of the traditional method (pruning on an already trained network). In addition, not only experiments but theortical proof are given and have a highly brief result.

Pro:
The way to find the mask iteratively is innovate and has a mathematical support.
The result of MPT is amazing because the untrained network can be pruned to a BNN with comparable accrancy of some trained SOTA NN on CIFAR dataset.
The experiments show it can be generized to deeper and wider network.
It has better accurancy than other BNN methods but network parameters still high.
Con:
The main article spends little word to describe how to find the mask, and it is not a trivial way.
The experiments of generization are only done on the very small NN (e.g. Conv2/4/6/8).

Clarity: Very low. Pros: The authors try to express in a way that every step of logical connections in this paper can be clearly understood by readers. To reduce complexity, many parts are settled in the appendix. Cons: Many sentences in this paper are quite long and sometimes using nesting clauses, which makes the text to be obscure. Besides, since many parts are moved into the appendix, the whole structure of the main body is kind of empty and shallow. Some summative and conclusive paragraphs are the simple repetition of previous “claims” since the demonstrations are in the appendix. All of these make a lower clarity. 
Finally, I find that this paper has narrower page margins, which means each line can contain more characters. Besides, the header “Under review as a conference paper at …” is missing. These modifications of the submit template may volatile the conference rule and should be considered a cheating behavior. So I give the “very low” score on clarity.

Originality: Medium. Pros: They apply the Lottery Ticket Hypothesis to quantization/BNN. They give proof of their rationality. Cons: The success essentials of their algorithm “biprop” contains two-part: edge-popup and gradient estimator. Both of them are take-away from other works. I regard this work as a new application of LTH to binary neural networks.

review_title: Good motivation and findings with seem-solid but actually weak theory. unclear paper writing, difficult to follow

Meta-review: The authors present a new theoretical framework that establishes that any network can be approximated by pruning a polynomially larger random binary networks, and also an algorithm for pruning binary nets. The results are important in the general context of the "strong" lottery ticket hypothesis, and are of both theoretical and practical interest. Although some of the ideas and technical contributions can be seen as a combination of prior tools and algorithms, the experimental findings are very novel.  Some further concerns of clarity and novelty were addressed by the authors.
Decision: Accept (Poster)