Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Optimizing sparse neural networks is an important topic due to their
computational and space savings.  Building on the work of the lottery ticket
hypothesis, others have shown there exist hidden subnetworks within randomly
initialized NN that have good performance. The authors extend this definition
to disguised subnetworks, which contain hidden subnetworks as a subclass.
Moreover, the authors present a novel combination of existing methods 
into a single algorithm they call Peek-a-Boo (PaB) which can efficiently
find such networks.

main_review: Strengths:
The paper is well written, and does a fair job covering recent works. 
The definition of disguised subnetworks is clear and properly motivated.
The presentation of the PaB is clear and well motivated with good context.
The results are quite convincing that PaB scaled well to larger networks,
something other methods lack, while providing good accuracy for much smaller
and easier to train models.

Weakness:

1. I would have liked to see some more theoretical discussion, though the authors
admit this work is primarily empirical.

2. It would be nice to discussion of other weight transformations U in the unmasking phase,
    that may be useful.

3. Though the definition of disguised subnetworks is new, and the generalized
approach is novel, and the results speak to the validity of the approach, the
PaB algorithm is a relatively straightforward application of two existing
methods.

summary_of_the_review: The paper is well written, and does a good job covering all the related material.
The definition of disguised subnetworks is novel and will be useful for future researchers.
The PaB algorithm clearly yields good results on larger NN, something other methods lack.
More exploration of theoretical understanding as well as other weight transformations would be 
useful.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper extends the definition of the hidden subnetworks in randomly initiated neural networks. The new notion of subnetworks, namely the disguised subnetworks, apply a transformation on the hidden subnetwork weights to obtain final weights (a posteriori finding the hidden subnetwork). 

Mathematically speaking, the main decision variable of the underlying optimisation problem of finding “hidden subnetworks” is the so-called masking variable that is a binary vector, the variable that decides which components of the randomly initiated weights will be zero, constrained to a desired level of sparsity. On the other hand, the underlying optimisation problem of “disguised subnetworks” has an additional variable U that applies a transformation on the set of weights after being ‘sparsified’. The selection of U = I, for I being the identity transformation, recovers the problem of hidden subnetworks, showing that the latter is a generalisation.

The author(s) present a heuristic algorithm that solves the forenamed optimisation problem. The idea is to first find a solution for the masking variable where (i) U = I is taken, (ii) the objective function is independent of a training set. Afterward, the algorithm proceeds by solving the problem for U given the solution of the previous step, where the space of U is restricted to the class of transformations where only sign-flips are allowed. If we think of the above solution process as a two-phase problem, the author(s) use the literature on sparse neural networks for the first phase and use the literature on binary neural networks for the sign flipping phase.
main_review: I think the paper is extremely well-written. There are no typos, the language and the presentation are very strong, and the flow is very fluent. Moreover, the literature is summarised very precisely and it includes most of the relevant papers to discuss, to the best of my knowledge. The algorithm is described well, and the contribution is discussed in a fair way without unrealistic claims.

My major concerns are as follows:

1 - **Contribution.** Problem (2) formally describes the “optimal hidden subnetwork” problem, and it immediately follows from the definition of problem (1) that what the authors suggest will be an ‘improvement’ over the training data. This is not unimaginable, that is, it is already known that any transformation of weights we optimise over the training data will be an improvement. 

2 - **Novelty.** As discussed above, rather than the definition of disguised subnetworks, what matters most here is, (i) the classes of “U” (transformation) that can be handled in this work, and (ii) novelty of the solution algorithm the work proposes. Regarding these two points: 
-  (i) the class of U is constrained to sign flips, which is already well-studied and being applied in similar settings; 
- (ii) the solution algorithm splits the problem into two sub-problems. The first sub-problem solves for “m” (the masking variable) by using existing training data-independent methods (cf. SynFlow). After fixing “m”, the algorithm simply proceeds with the Bop method from the BNN optimisation literature. My concern here is that, since in the loss function the order of these variables is loss [ U( .. m ) ], first solving for "m" and then for "U" is the most trivial way, and while doing this using all of the well-known results is not bringing much novelty. 

3 - **Generality.** The paper is defining a very general problem of optimal disguised subnetworks and mentioning this in the title/abstract/ and throughout the paper. However, in my view, this work is more like a case-study where heuristic methods are being used iteratively. Namely, the contribution is actually: “taking a recent paper that finds a masking variable, and just flipping the signs w.r.t. the training loss”. This is still an interesting result, but I also would like to highlight the distinction from my perspective. Finally, I would like to highlight that, although the optimization formulation of "disguised subnetworks" finds U (transformation) and m (masking) jointly, the relaxation proposed (PaB) first splits the problem so that the solution algorithm first finds a sub-network (i.e., m is found) and then changes the weights. So this algorithm does not find a disguised subnetwork (as claimed in the introduction), rather finds a subnetwork and then re-assigns the weights, which is *a* disguised subnetwork, but not a new architecture. I believe the problem definition of disguised networks is very general but PaB first finds the hidden architecture so this is not a new way of finding subnetworks.

4 - **Numerical Experiments.** This is a question for the author(s) rather than a direct concern: some of the algorithms in the numerical experiments, where PaB is being compared with, are training-independent algorithms. The fact that they are training-independent (or sometimes called “without training methods”) is the main focus in the literature around them. Malach et al. (2020), on the work(Ramanujan et al., 2019) comment: “within a sufficiently overparameterized neural network with random weights (e.g. at initialization), there exists a subnetwork that achieves competitive accuracy”. Is this mentioned in the paper? Otherwise, the fact that here there is an optimisation procedure after fixing the sparsity structure based on the training set already changes the setting of the problem here and introduces a bias in comparison?

However, I still think the idea of combining these existing methods to find a solution for the optimal disguised subnetwork problem (and hopefully a good one), can pave the way for a new research direction. Here the key standpoint is, rather than the generality or the novelty of solutions, to demonstrate that instead of solving a dense network and “transforming the weights”, or to mask for a sparse network, one can combine these methods to have a sparse network that also performs better than the alternatives. The numerical experiments are conducted and reported carefully, and the results look promising. Hence, despite the lack of theoretical contributions, I would like to give my decision as "marginally below the acceptance threshold".

Minor comments:
- Page 2: “Even worse is” maybe better to re-write?
- Page 3: “Unfortunately, the original experiments in (Zhou et al., 2019)” maybe change ‘unfortunately’?
- Page 5: In the first sentence, “s” is not capital but previously it was. The same happens again in the “Unmasking phase” part of S3.2.
- “Computationally infeasible” -> “computationally intractable”
- “ = argmin “ -> “ \in argmin” (or prove that argmin set is a singleton) 
- Page 5: “For example, one sparse NN of k non-zero elements  […]” is this called an example because k is named? Maybe it is better to connect with before “, that is, if a sparse NN …”?
- Page 5: Optimisation over 2^k many vectors is called “NP-hard”. I am not sure but this terminology may be misleading. The optimisation problem itself can be tractable but there the input is just intractably large in “k”.  I am not very sure about whether it is common to say the problem is NP-hard. For example, with that logic, max{a_1, a_2, … , a_n }, that is found in linear time, is NP-hard in log(n)? 
- Page 7: “and the PSG variant,.” There is an additional comma (,) before the full stop (.)

summary_of_the_review: **Pros**
- The paper has a very clear overview of the relevant research, and in general, the paper is written very well
- The numerical experiments are very thorough
- The idea of generalizing the notion of hidden subnetworks is relevant
**Cons**
- The contribution is limited -- the definition of disguised networks is straightforward and the solution method comprises a subsequent application of existing algorithms (not parallelized or nested, but applied sequentially)
- The optimal disguised networks problem is restricted iteratively so that the end result is not very interesting anymore
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes the idea of a "disguised subnetwork", which are hidden random subnetworks that can be transformed into a well-performing subnetwork. The paper introduces PaB as a way to uncover these subnetworks, by first searching for a mask over the random weights using pruning-at-initialization techniques, and then learning a transformation on the subnetwork. The paper further shows that this PaB process can be efficiently implemented, offering significant advantage over prior work.
main_review: **Strength:**
- This paper is very well written and a pleasure to read.

- The paper tackles an important question, which is to rethink the optimization strategies of sparse neural networks, especially when using the idea of masking as training. The observation that when we are only looking to flip signs of random weights during training, we can tolerate much coarser gradients is insightful. The results are significant as it reduces training cost compared to fully trained networks while maintaining competitive performance.

- The method is compared to an appropriate set of baselines over a reasonable set of model architectures. 

**Weakness:**
- How exactly is the compression ratio calculated? The authors mention that this is due to the fact that the random initialization can be stored using a single seed. While this may be true in some cases, I would be hesitant to rely on this attribute as the seed may not result in the same parameters in different machines. It would be more reasonable to assume that the weight values must be stored for a more conservative estimate.

- Most of the work in supermasks consider the "signed constant" variant, where the weights are converted to a single signed value for each layer. This parameterization has often shown improved performance over the parameterization using actual weight values, and leads to significant reductions in model complexity and size. How would this variant work under the PaB framework?
summary_of_the_review: The method is novel and achieves better efficiency-performance tradeoff than the various baselines. It tackles the question of rethinking optimization strategies for sparse NN training, which I think is an important research direction. I think the contributions of this paper are significant and would support its acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents an algorithm named peek-a-boo (PaB) to optimize network pruning (at initialization) and optimization (limited within flipping the sign of weights). This setting has not been studied by prior works. A two-step algorithm was designed -- pruning first, optimization second. Experiments show competitive performance compared to prior methods with similar optimization complexity.
main_review: This paper presents an algorithm named peek-a-boo (PaB) to optimize network pruning (at initialization) and optimization (limited within flipping the sign of weights). This setting has not been studied by prior works. A two-step algorithm was designed -- pruning first, optimization second. Experiments show competitive performance compared to prior methods with similar optimization complexity.

Though the setting is new and interesting, I shall say that its value to the community has not been perfectly revealed based on the existing experiments. In the studied cases, the neural networks and datasets are mostly small. The value of this work is supposed to be accelerating large-scale network training, but I am not sure that it scales up well.

Second, it seems that the technical contribution of the proposed algorithm is limited. When I see the objective function (1), I was expecting that pruning and optimization are jointly performed, however, according to Algorithm 1, they were performed separately, and the pruning part follows an existing algorithm. Separate optimization brings the issue that the best pruned architecture may not fit very well in the unmasking setting. Therefore, I am wondering if there is an iterative solution, that pruning is divided into several steps (e.g. one decides to keep 50% weights, so he/she can prune 10% weights every time for 5 rounds), and after each step, the flipping operation is performed. This can align both parts and hopefully improve the final performance. Of course, this may increase the training BitOps, but this shall be a tradeoff -- anyway, showing whether this strategy helps is not a bad trial.

Third, the experiments are performed on CIFAR datasets. Since ImageNet results are missing, I am not sure if the approach can actually scale up. In particular, according to Tables 1 and 2, PaB does not show a significant advantage over SGD, which further limits the application of the proposed approach. I think ImageNet experiments might be a good add-on to this paper.
summary_of_the_review: 1. The setting is new, but the practical value to the community seems unclear.
2. The algorithm is straightforward, joint optimization is not considered.
3. Experiments are promising but not exciting, ImageNet results are absent.

Overall, a bit below the acceptance threshold.
review_title: null

Meta-review: I recommend acceptance. This paper presents an interesting "in-between" of work on lottery tickets and work on supermasks, and I think it is sufficiently novel to merit acceptance even if the significance of the results will need to be left to the judgment of future researchers. The reviewers seem broadly in favor of acceptance, and I defer to their judgment as a proxy for that signal.

For a quick bit of context, work on "supermasks" (Zhou et al., 2019) has shown that randomly initialized networks contain subnetworks that can reach high accuracy without training the weights themselves. That is to say, within randomly initialized networks are high-accuracy subnetworks. This work is interesting in its own right and has had a number of interesting implications for the theoretical community. This work derives from work on the lottery ticket hypothesis (LTH; Frankle & Carbin 2019), which shows that randomly initialized networks contain subnetworks that can train to full accuracy on their own. The key distinctions between these two kinds of work are (1) the LTH trains the subnetworks, while supermask work does not and (2) the LTH work requires that the subnetworks train to full accuracy, while work on supermasks obtain high (but not full) accuracy in many cases. No one approach is "better" than the other; they simply showcase different properties of neural networks.

As far as I understand, this paper creates space for an "in-between:" high-accuracy subnetworks are created by finding subnetworks at random initialization and flipping the signs of some of the weights to improve accuracy. This is a limited modification to the subnetworks that falls short of actually training them (LTH work) but is more than leaving them at their random initializations (supermask work). Doing so appears to produce subnetworks that perform better than in supermask work but with a lighter-weight procedure than LTH work. The procedure for accomplishing this feat is different than either approach (using SynFlow to find the subnetwork and a binary neural network training scheme to find the signs), and there is probably significant room for improvement in this new algorithmic space (just as there was for both LTH and supermasks).

This is novel and interesting, and I defer to the reviewers who find it worthy of acceptance. I have reservations about the eventual significance of the work, but that determination will be made by future researchers.
Decision: Accept (Poster)