Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper studies learning in deep neural networks with hard activation functions, e.g. step functions like sign(x). Of course, backpropagation is difficult to adapt to such networks, so prior work has considered different approaches. Arguably the most popular is straight-through estimation (Hinton 2012, Bengio et al. 2013), in which the activation functions are simply treated as identity functions during backpropagation. More recently, a new type of straight-through estimation, saturated STE (Hubara et al., 2016) uses 1[|z|<1] as the derivative of sign(z).

The paper generalizes saturated STE by recognizing that other discrete targets of each activation layer can be chosen. Deciding on these targets is formulated as a combinatorial optimization problem. Once the targets are chosen, updating the weights of each layer to minimize the loss on those targets is a convex optimization. The targets are heuristically updated through the layers, starting out the output using the proposed feasibility target propagation. At each layer, the targets can be chosen using a variety of search algorithms such as beam search.

Experiments show that FTP often outperforms saturated STE on CIFAR and ImageNet with sign and quantized activation functions, reaching levels of performance closer to the full-precision activation networks.

This paper's ideas are very interesting, exploring an alternative training method to backpropagation that supports hard-threshold activation functions. The experimental results are encouraging, though I have a few questions below that prevent me for now from rating the paper higher.

Comments and questions:

1) How computationally expensive is FTP? The experiments using ResNet indicate it is not prohibitively expensive, but I am eager for more details.

2) Does (Hubara et al., 2016) actually compare their proposed saturated STE with the orignal STE on any tasks? I do not see a comparison. If that is so, should this paper also compare with STE? How do we know if generalizing saturated STE is more worthwhile than generalizing STE?

3) It took me a while to understand the authors' subtle comparison with target propagation, where they say "Our framework can be viewed as an instance of target propagation that uses combinatorial optimization to set discrete targets, whereas previous approaches employed continuous optimization." It seems that the difference is greater than explicitly stated, that prior target propagation used continuous optimization to set *continuous targets*. (One could imagine using continuous optimization to set discrete targets such as a convex relaxation of a constraint satisfaction problem.) Focusing on discrete targets gains the benefits of quantized networks. If I am understanding the novelty correctly, it would strengthen the paper to make this difference clear.

4) On a related note, if feasible target propagation generalizes saturated straight through estimation, is there a connection between (continuous) target propagation and the original type of straight through estimation?

5) In Table 1, the significance of the last two columns is unclear. It seems that ReLU and Saturated ReLU are included to show the performance of networks with full-precision activation functions (which is good). I am unclear though on why they are compared against each other (bolding one or the other) and if there is some correspondence between those two columns and the other pairs, i.e., is ReLU some kind of analog of SSTE and Saturated ReLU corresponds to FTP-SH somehow?
review_title: An interesting way of explaining and generalizing approaches for learning neural nets with hard activation

final_score: rating: 7: Good paper, accept
review_content: This paper examines the problem of optimizing deep networks of hard-threshold units. This is a significant topic with implications for quantization for computational efficiency, as well as for exploring the space of learning algorithms for deep networks. While none of the contributions are especially novel, the analysis is clear and well-organized, and the authors do a nice job in connecting their analysis to other work. 
review_title: Well-organized analysis of the hard-threshold networks

final_score: rating: 7: Good paper, accept
review_content: The paper discusses the problem of optimizing neural networks with hard threshold and proposes a novel solution to it. The problem is of significance because in many applications one requires deep networks which uses reduced computation and limited energy. The authors frame the problem of optimizing such networks to fit the training data as a convex combinatorial problems. However since the complexity of such a problem is exponential, the authors propose a collection of heuristics/approximations to solve the problem. These include, a heuristic for setting the targets at each layer, using a soft hinge loss, mini-batch training and such. Using these modifications the authors propose an algorithm (Algorithm 2 in appendix) to train such models efficiently. They compare the performance of a bunch of models trained by their algorithm against the ones trained using straight-through-estimator (SSTE) on a couple of datasets, namely, CIFAR-10 and ImageNet. They show superiority of their algorithm over SSTE. 

I thought the paper is very well written and provides a really nice exposition of the problem of training deep networks with hard thresholds. The authors formulation of the problem as one of combinatorial optimization and proposing Algorithm 1 is also quite interesting. The results are moderately convincing in favor of the proposed approach. Though a disclaimer here is that I'm not 100% sure that SSTE is the state of the art for this problem. Overall i like the originality of the paper and feel that it has a potential of reasonable impact within the research community. 

There are a few flaws/weaknesses in the paper though, making it somewhat lose. 
- The authors start of by posing the problem as a clean combinatorial optimization problem and propose Algorithm 1. Realizing the limitations of the proposed algorithm, given the assumptions under which it was conceived in, the authors relax those assumptions in the couple of paragraphs before section 3.1 and pretty much throw away all the nice guarantees, such as checks for feasibility, discussed earlier. 
- The result of this is another algorithm (I guess the main result of the paper), which is strangely presented in the appendix as opposed to the main text, which has no such guarantees.  
- There is no theoretical proof that the heuristic for setting the target is a good one, other than a rough intuition
- The authors do not discuss at all the impact on generalization ability of the model trained using the proposed approach. The entire discussion revolves around fitting the training set and somehow magically everything seem to generalize and not overfit. 

review_title: Nice discussion and solution to optimizing neural networks with hard thresholds but with some flaws

Meta-review: The submission proposes optimization with hard-threshold activations.  This setting can lead to compressed networks, and is therefore an interesting setting if learning can be achieved feasibly.  This leads to a combinatorial optimization problem due to the non-differentiability of the non-linearity.  The submission proceeds to analyze the resulting problem and propose an algorithm for its optimization.

Results show slight improvement over a recent variant of straight-through estimation (Hinton 2012, Bengio et al. 2013), called saturated straight-through estimation (Hubara et al., 2016).  Although the improvements are somewhat modest, the submission is interesting for its framing of an important problem and improvement over a popular setting.
Decision: Accept (Poster)