Learning deep neural networks with hard-threshold activation has recently become an important problem due to the proliferation of resource-constrained computing devices. In order to circumvent the inability to train with backpropagation in the present of hard-threshold activations, Friesen & Domingos (2018) introduced a discrete target propagation framework for training hard-threshold networks in a layer-by-layer fashion. Rather than using a gradient-based target heuristic, we explore the use of search methods for solving the target setting problem. Building on both traditional combinatorial optimization algorithms and gradient-based techniques, we develop a novel search algorithm Guided Random Local Search (GRLS). We demonstrate the effectiveness of our algorithm in training small networks on several datasets and evaluate our target-setting algorithm compared to simpler search methods and gradient-based techniques. Our results indicate that combinatorial optimization is a viable method for training hard-threshold networks that may have the potential to eventually surpass gradient-based methods in many settings.
Summary:
The paper presents a novel combinatorial search algorithm for the discrete target propagation framework developed in Friesen & Domingos (2018). Experiments on small datasets with small models demonstrate some potential for the proposed approach; however, scalability remains a concern.
  Pros:
-	I like the goal of the work and think that if the targeted problem were to be solved it would be an interesting contribution to the field.
-	The proposed search algorithm is reasonable and works OK.
-	The paper is mostly well written and clear.
-	The experiments are reasonably thorough.
  Cons:
-	The paper states that it is a feasibility study on search methods for learning hard-threshold networks, however, it only evaluates the feasibility of one combinatorial search method. 
-	It’s not made clear whether other approaches were also investigated or what the authors learned from their exploration of this approach.
-	The actual algorithm is not very well explained, despite being the main contribution of the paper.
-	The datasets and models are small and not necessarily representative of the requirements of the field.
-	Scalability remains a serious concern with the proposed approach.
-	It’s not clear to me that the paper presents a sufficient enough contribution to warrant acceptance.
Overall, I like the direction but do not feel that the paper has contributed enough to warrant acceptance. The authors should use the experiments they’ve run and also run more experiments in order to fully analyze their method and use this analysis to improve their proposed approach. 
Questions and comments:
1.	Did you try alternative local search algorithms or did you just come up with a single approach and evaluate it? What did you learn from the experiments and the development of this algorithm that will let you create a better algorithm in the next iteration?
2.	I think that it is unfair to say that “it suggests a simpler, independent justification for the performance improvements obtained by their method.” in reference to the work of Friesen & Domingos (2018), given that the straight-through estimator is not well justified to begin with and their work in fact provides a justification for it. I do agree that it is important to investigate alternative heuristics and approaches within the discrete target propagation framework, however.
3.	Sections 2 and 3 do not clearly define what L_i is and where it comes from. Since these do not normally exist in a deep network they should be clearly defined.
4.	“step 2(b)” is not well defined in section 3.1.1. I assume that this refers to lines 4-8 of Algorithm 1? The paper should explain this procedure more clearly in the text. Further, I question the locality of this method, as it seems capable of generating any possible target setting as a neighbor, with no guarantee that the generated neighbors are within any particular distance of the uniform random seed candidate. Please clarify this.
5.	I believe that a negative sign is missing in the equation for T_i in ‘Generating a seed candidate’. For example, in the case where |N| = 1, then T_i = sign(dL/dT_i) would set the targets to attain a higher loss, not lower. Further, for |N|=1, this seems to essentially reduce to the heuristic method of Friesen & Domingos (2018). 
6.	In the ‘Setting the probabilities’ section:
(a) All uses of sign(h) can be rewritten as h (since h \in {-1, +1}), which would be simpler.
(b) The paper contradicts itself: it says here ‘flip entries only when sign(dL/dh) = sign(h)’ but Algorithm 1 says ‘flip entries only when sign(dL/dh) != sign(h)’. Which is it?
(c) What is the value of a_h in the pseudocode? (i.e., how is this computed in the experiments)
7.	In the experiments, the paper says that ‘[this indicates] that the higher dimensionality of the CIFAR-10 data manifold compared to MNIST may play a much larger role in inhibiting the performance of GRLS.’ How could GRLS overcome this? Also, I don’t agree with the claim made in the next sentence – there’s not enough evidence to support this claim as the extra depth of the 4-layer network may also be the contributing factor.
8.	In Table 2, why are some numbers missing? The paper should explain what this means in the caption and why it occurs. Same for the bolded numbers.
9.	The Loss Weighting, Gradient Guiding, Gradient Seeding, and Criterion Weighting conditions are not clearly defined but need to be to understand the ablation experiments. Please define these properly.
10.	The overall structure of the algorithm is not stated. Algorithm 1 shows how to compute the targets for one particular layer but how are the targets for all layers computed? What is the algorithm that uses Algorithm 1 to set the targets and then set the weights? Do you use a recursive approach as in Friesen & Domingos (2018)?
11.	In Figure 2, what dataset is this evaluation performed on? It should say in the caption. It looks like this is for MNIST, which is a dataset that GRLS performs well on. What does this figure look like for CIFAR-10? Does increasing the computation for the heuristic improve performance or is it also flat for a harder dataset? This might indicate that the initial targets computed are useful but that the local search is not helping. It would be helpful to better understand (via more experiments) why this is and use that information to develop a better heuristic.
12.	It would be interesting to see how GRLS performs on other combinatorial search tasks, to see if it is a useful approach beyond this particular problem.
13.	In the third paragraph of Section 4.2, it says ‘The results are presented in Table 3.’ I believe this should say Figure 3. Also, the ordering of Figure 3 and Table 3 should be swapped to align with the order they are discussed in the text. Finally, the caption for Table 3 is insufficiently explanatory, as are most other captions; please make these more informative.
14.	In Section 4.3:
(a), the paper refers to Friesen & Domingos (2018) indicating that zero loss is possible if the dataset is separable. However, what leads you to believe that these datasets are separable? A more accurate comparison would be the loss for a powerful non-binarized baseline network. 
(b) Further, given the standard error of GRLS, it’s possible that its loss could be substantially higher than that of FTPROP as well. It would be interesting to investigate the cases where it does much better and the cases where it does much worse to see if these cases are informative for improving the method.
15.	Why is there no discussion of training time in the experiments? While it is not surprising that GRLS is significantly slower, it should not be ignored either. The existence of the Appendix should also be mentioned in the main paper with a brief mention of what information can be found in it.
16.	In Algorithm 1, line 2 is confusingly written. Also, notationally, it’s a bit odd to use h both as an element and as an index into T.
17.	There are a number of capitalization issues in the references.
18.	The Appendix refers to itself (“additional hyperparameter details can be found in the appendices”).