Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the problem of "Adversarial Reprogramming" which is a task that is defined as follows. Suppose we have a machine learning model M that takes in inputs from a particular domain X to a label domain Y, while as a malicious actor imagine that we want to accomplish a task that takes in inputs from domain X' and outputs targets in domain Y'. Then the setting of adversarial reprogramming asks the question whether it is possible to find some simple functions h_in: X' -> X and h_out: Y -> Y' such that we can utilize h_out(M(h_in(x))) to solve this task. Note that finding a function h_out mapping from a discrete label space Y to Y' is a well studied problem in combinatorial optimization with several standard algorithms such as the Hungarian algorithm. Therefore, the main crux of the problem is to find the mapping h_in. Furthermore, in Adversarial Reprogramming a further assumption is made about h_in - that it be of the form of additive noise, i.e. h_in(x) = p + x, for some noise p which may depend on the model M. The goal then is to maximize accuracy on the task X' -> Y' without affecting the model parameters M (so one cannot fine-tune).

The authors study this problem for randomly initialized neural networks, i.e. when the model M is random. They show that in the 2-layer setting with the ReLU activation function and on a data distribution defined over the boolean hypercube one can find an adversarial program with arbitrarily high accuracy under several assumptions regarding network width etc. The authors also prove some theorems regarding when the dataset is orthogonally separable which I did not fully follow - e.g., Theorem 3 (are the convergence results about SGD or something else?). The authors also have some experiments which is hard to follow and I am not sure how their Theorems about 2 layer networks on boolean hypercubes translates to EfficientNets, Resnet-50 etc., on which they report experimental results. 
strengths_and_weaknesses: Strengths: The paper seems to be about a topic that appears to be important, i.e. whether one can repurpose a model trained on a certain domain to another (potentially unethical or malicious) domain.

Weaknesses: The major weaknesses of the paper come from the several assumptions made about the Adversarial Reprogramming task:

Typically given a model M and a dataset domain (X, Y) a malicious actor would most likely wish to use M for a specific task (X', Y'): for example consider a scenario where an image classification model is trained to classify everyday objects (such as say Imagenet) but the malicious user wants to use it to predict whether people of a certain group are more criminally inclined than the others. However, the assumption made throughout is that "one can find an adversarial task" and the theorems also seem to work only for specific kinds of adversarial task (e.g., the theorem seems would not go through if the noise added in the boolean dataset task is some other quantity). However, this obtained adversarial task/dataset itself may not be as interesting or even malicious or meaningful to an attacker.

questions: 1) While the assumption about boolean hypercube may be a bit contrived, it is still a reasonable starting assumption in my opinion. However, it is not clear to me why are we interested in Adversarially reprogramming a random neural network? The motivation for that is not clear to me, an attacker would usually be interested in reprogramming an already pre-trained model.
 
2) The presentation of the paper is a little hard to follow, especially in Section 3  where someone not too familiar with the area will find it hard to follow. Moreover the consequence of Theorem 3 and Corollary 4 is not fully clear, what is the implication of this particular training dynamics?

3) The relation of the experimental section with the theoretical contribution of the work is unclear and again difficult to follow. Is it being validated that the theorem's proposed noise function is successfully finding some inputs on which a randomly initialized network has some high accuracy?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper raises a fundamental question: what is the relationship between training and adversarial reprogrammability? The authors provide a theoretical analysis for adversarial reprogramming, where the conclusion shows that training has some but limited impact on reprogramming.
strengths_and_weaknesses: Strengths:

1. Reprogramming can have an important impact on many tasks, e.g. reprogramming for transfer learning, so a solid and fundamental investigation is promising.

2. The conducted experiments provide good support to the theoretical analysis.

Weakness:

1. The authors mention several application scenarios of reprogramming, but the connection between the theoretical analysis and the mentioned applications seems weak.
questions: Please see [Strengths And Weaknesses].
limitations: Please see [Strengths And Weaknesses].
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies adversarial reprogramming (Elsayed et al 2019) that is the adversarial attack setting that can repurpose a network to conduct a task of interest. The paper provide theoretical proofs using simple random network and conclude that random networks can be adversarially repurposed as long as the input dimensionality is >= the network width. Elsayed et al 2019 managed to adversarially reprogram deep networks that are trained originally on ImageNet but failed to reprogram random deep networks. To address the possibility of training random networks in practice, the paper conducts experiments on multiple practical deep network architectures and show that the random networks can be repurposed to perform MNIST classification as long as batch normalization is suitably initialized, thus giving evidence that random networks could be trained in practice. The paper also explores two schemes for adding adversarial program (1) replacing the center by input images and (2) overlapping mixture of input images and adversarial program. The authors finds that the second scheme is more successful.
strengths_and_weaknesses: Strengths:
- Work provide theoretical proofs, though in reduced setting, of conditions where it is possible to adversarially reprogram neural networks.
- Authors explore two schemes of applying adversarial reprogramming of neural networks and demonstrate the superiority of one approach over the other.
- Authors provide empirical study on multiple network architectures


Weaknesses:
- Clarity of presentation: The theory in the paper could be somewhat overwhelming. I encourage the authors to give intuitions in addition to the theoretical proofs. To give an example, the authors prove that the two layer network can be reprogrammed given that the network width <= input dimensions. This conclusion may be confusing to some as a wider network has more capacity and may be regarded as more capable to do adversarial tasks. Maybe an intuition here is that the adversarial program dimensionally scales with input dimensions and in fact a larger input dimension allows more space to explore suitable adversarial programs that can repurpose the network.

- Theory limitations: To be able to provide theoretical proofs the authors needed to make simplifying assumption on the network architecture as well as the task. This although still an interesting contribution limit the impact of the work. I encourage authors can mention this limitation summary list of assumptions they needed to make. Perhaps also provide some suggestion for potential ways to extend the theory to more realistic networks and tasks. 

- Discussion of batch norm: the discussion in the experimental section on batch normalization is not very clear. It is not 100% clear whether batch normalization is trained or left at initialization values. Also, changing the initialization scheme for batch normalization kind of violates the adversarial reprogramming setting where an adversary is given a network as is and one can only design the adversarial program.  

- Experiments limitations: the authors use only one task (MNIST). I think authors needs to provide consistent evidence from at least two datasets to give confidence on the conclusions made. Further, experiments in Figure 2 uses one sample. The experiments need to be repeated from different seeds to get an estimate of variations (eg STD or SEM).

- It is unclear why scheme 2 of mixing adversarial programming with image is more successful. Is this because the dimensionality of useable adversarial program is higher than the scheme where the center of program is replaced with the image? It would be good to provide some explanation here.

questions: Please see my above comments. 
limitations: I think discussion of limitations is somewhat lacking. The authors needs to explain clearly the limitation of the work in a separate section or at the conclusion section. Please consult my comments on the strengths and weaknesses above.
review_title: null

Meta-review: metareview: This paper develops several theoretical results around when adversarial reprogramming will, and will not, be possible. They support these with experiments. As this is the first meaningful theoretical analysis of adversarial reprogramming, the paper is potentially impactful.

All reviewers support paper acceptance. Additionally, the paper appears to have been significantly improved over the course of the rebuttal period. I therefore recommend paper acceptance.
confidence: Certain
Decision: Accept