OPTIMAL ROBUST MEMORIZATION WITH RELU NEURAL NETWORKS

Thanks for your valuable comments and questions. We give a detailed answer to them and hope that you could re-evaluate our paper based on these answers.

1. The term “optimal robust memorization” is inappropriate. This comment consists of two major issues.

1.1 ``Robust memorization with radius $\lambda/2$ is not significantly different from $\lambda/4$, except that it is a bit larger neighborhood''

Answer: Please note that the difference between $\lambda/2$ and $\lambda/4$ is not only in the size of the robust neighborhood. Radius $\lambda/2$ is the largest possible robust neighborhood that can be achieved, if using the same radii for all samples, and it is in this sense we call our robust memorization optimal.

1.2 ``$\lambda/2$ is just the minimal distance, not necessarily the distance for every pair of data samples.''

Answer: To the best of our knowledge, all papers that work on adversarial robustness use the same robust radius for all samples. It is a nice idea to use different radii for different samples, but this needs to consider $O(N^2)$ radii for $N$ samples and the number of parameters of the memorization network is expected to be larger.

In summary, {\bf our optimal robust memorization is not indeed absolute optimal, but it is a type of optimal}. To make it more clear, we will change 'optimal' to 'optimal with respect to robust radius'.

2. It seems to me that some results are not consistent. Proposition 4.7 part 2 already infers that depth 2 width 2 network is not a robust memorization. However, Theorem 4.1 claims that it is NP-hard.

Answer: These two results are not contradictory.

Proposition 4.7 part 2 shows that, {\bf there exists a dataset D}, all networks with depth 2 and width 2 are not robustness memorizations for D.

Th 4.1 shows that, there is no polynomial-time algorithm to decide whether there exists a robustness memorization with depth 2 and width 2 {\bf for any given dataset D}. Note that there do exist data sets D such that networks of depth 2 and width 2 are robustness memorizations for D.

3: The discussion below Theorem 1.1 is not quite correct. It somehow avoided the case that the absence of memorization implies the absence of robust memorization.

Answer: We believe that The Discussion is correct. The purpose of this part is to show ``NP-hardness of computing robust memorization for a non-zero budget and the NP-hardness of computing memorization cannot be deduced from each other:'' The two cases listed subsequently in the paper already serve our purpose.

The reviewer is correct that we did not list the case ``absence of memorization implies the absence of robust memorization''. We will discuss this case in the revised version. But this case does not affect the correctness of our conclusion.

4: Intuition on why the number of non-zero parameters does not depend on $\lambda,\mu,L$.

Answer: The conclusion of Li2022 is based on some approximate results of the Relu network for polynomials and $1/x$. However, it is obvious that Relu network is locally linear, its growth rate is lower than polynomial or $1/x$ when $x\to \infty$ or $x\to 0$, so this approximation must be within a certain range, and the number of parameters required for approximation is related to this range, so their conclusions need to be based on $\lambda,\mu$.

Our work does not use the classical approximation theorem. We make full use of every parameter of the network and make the meaning of these parameter clear. For example, some parameters are used to measure the distance between the input and the point in the training set, so that $\lambda,\mu$ only affects the value of these parameters, but not the number of parameters; some parameters are used to predict the label of inputs, so that $L$ only affect the value of these parameters, but not the number of parameters.

Thanks for your valuable comments. We give a detailed answer to them and hope that you could re-evaluate our paper based on these answers.

1. It is highly technical and requires a strong background in readers to grasp the meaning of this paper. The authors may think about the organization of this paper.

Answer: Indeed, our paper is technical and we tried our best to organize the paper to improve readability. For instance, we give informal description of the main results in Introduction Section; give proof sketches for most of the main results; and give remarks/explanations/comparisons after the main results. We believe that {\bf the main text of the paper should be understandable without difficulty}. We admit that the proofs in the Appendix are quite technical and tried our best to make the proofs more easily readable, including separate the long proofs into several parts and use figures for illustrations.

2. ICLR may not be a suitable conference for this paper.

Answer: Note that ``Learning theory'' is one of the official topics of ICLR and our paper fits this topic very well.

Sorry, I mistakenly posted something here just now. Please ignore it.

Thanks for your valuable comments and questions. We give a detailed answer and hope that we have addressed your concerns. The review is focused on four issues and we will answer them separately.

1. The main theorems 4.8 and 5.2 only guarantee the existence of optimal robust memorization. These results would be more useful if an optimization or constructive algorithm is given to find the optimal memorization.

Answer: We did give constructive algorithms for the optimal robust memorization networks. Please see Appendix B.5 on page 28 (proof for Theorem 4.8) and Appendix C.2 on page 33 (proof for Theorem 5.2). We will make this clear in the revised version of the paper.

2. Given that the existence of optimal robust memorization is guaranteed under a ReLU network with bounded size, would it be possible to arrive at such a solution using any optimization algorithm? What would be the complexity of such an algorithm?

Answer: As said in 1, we give direct constructive algorithms for the optimal robust memorization networks, and these are polynomial-time algorithms.

To the best of our knowledge, all works that can give memorization with polynomial number of parameters are direct construction of the networks from the data sets, and no one used optimization methods such as SGD. This is because using SGD cannot in general to give theoretically guaranteed memorization networks.

3. Robust generalization. It is not clear in the paper that the constructions of ReLU networks for robust memorization would lead to robust generalization. I know the authors acknowledge this in the conclusion, but I think this is a very serious question.

Answer:

3.1. Having memorization neural networks with theoretically guaranteed robust generalization ability is one of the most important problems in adversarial learning, and worth studying. To the best of our knowledge, this is still an open problem, and all existing works on memorization do not have theoretical results on generalization.

3.2 Indeed, this work is primarily focused on the expressive power of neural networks, and no theoretical result on generalization is given. In our ongoing work, we link generalization to memorization. Under the assumption that the samples in the dataset are i.i.d. selected from the data distribution, we give generalization analysis of memorization networks. Moreover, for data distributions that satisfy certain assumptions, our Theorems 4.8 and 5.2 also guarantee generalization if the sample in dataset is sufficient.

4. The Theorem 2.2 in (Li et al., 2022) is derived for $p\ge2$ (actually it is $p\in\\{2, \infty\\}$). However, the bound given in Theorem 4.8 is only valid for the infinity norm. The authors may want to point out that in the paper. The bound given by Theorem B.3 seems to be a bit worse than the bound given by Theorem 2.2 in (Li et al., 2022). I think it would be also helpful to compare such a case in the main text. What are the main difficulties for deriving bounds under p-norm?

Answer: We are grateful that you read our Appendix. We answer this question in three parts.

4.1 It is not difficult to give an upper bound of robust memorization under the $L_p$ norm. Theorem B3 shows that the required number of parameters in relation to $p$ is no more that $O(Nnp^2\log(n/\gamma))$. For the case of $p=1$, Theorem B2 gives a good bound similar to Theorem 1.1. But it is desirable and difficult to have a bound which is not essentially dependent on p.

4.2 To come up with that in Li2022. When $p=2$ and $\gamma=\lambda_D^p/4$, our bound in Theorem B.3 becomes $O(Nn\log(n/\lambda_D^p))$, but the result in Li2022 is $O(Nn\log(n/\lambda_D^p)+O(Npoly\log(N/\lambda_D^p)))$. Our result is better than that of Li2022.

4.3 We focus mainly on the $L_\infty$ norm in this work, so the results on other norms are not mentioned in the main text. We will add these comparisons in the revised version.