OPTIMAL ROBUST MEMORIZATION WITH RELU NEURAL NETWORKS
Authors: Lijia Yu
Xiao-Shan Gao
Lijun Zhang
Venue: ICLR 2024 spotlight (2024)
Keywords: Memorization
expressive power of network
optimal robust memorization
computation complexity
Lipschitz constant
Primary area: learning theory
TL;DR: The difficulty and possibility of implementing robust network are demonstrated from the perspective of memorization and computation complexity.

Abstract: Memorization with neural networks is to study the expressive power of neural networks to interpolate a finite classification data set, which is closely related to the generalizability of deep learning. However, the important problem of robust memorization has not been thoroughly studied. In this paper, several basic problems about robust memorization are solved. First, we prove that it is NP-hard to compute neural networks with certain simple structures, which are robust memorization. A network hypothesis space is called optimal robust memorization for a data set if it can achieve robust memorization for any budget less than half the separation bound of the data set. Second, we explicitly construct neural networks with O(N n) parameters for optimal robust memorization of any data set with dimension n and size N . We also give a lower bound for the width of networks to achieve optimal robust memorization. Finally, we explicitly construct neural networks with
O(N n log n) parameters for optimal robust memorization of any binary classification data set by controlling the Lipschitz constant of the network.

Published as conference paper ICLR 2024
OPTIMAL ROBUST MEMORIZATION WITH RELU NEURAL NETWORKS
Lijia Yu
Institute of Software, Chinese Academy of Sciences Academy of Mathematics and Systems Science, Chinese Academy Sciences yuli jia@:ai@e ioss ac.cm
Xiao-Shan Gao*
Academy of Mathematics and Systems Science, Chinese Academy Sciences University of Chinese Academy of Sciences xgao@mmre., i isssssa.... ac. cn
Lijun Zhang
Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences zhangl j0 jiios... ac.cn
ABSTRACT
Memorization with neural networks is to study the expressive power of neural networks to interpolate finite classification dataset, which is closely related to the generalizability of deep learning. However, the important problem of robust memorization has not been thoroughly studied. In this paper, several basic problems about robust memorization are solved. First, we prove that it is NP-hard to compute neural networks with certain simple structures, which are robust memorization. A network hypothesis space is called optimal robust memorization for a dataset if it can achieve robust memorization for any budget less than half the separation bound of the dataset. Second, explicitly construct neural networks with O (Nn) parameters for optimal robust memorization of any dataset with dimension and size N. We also give a lower bound for the width of networks to achieve optimal robust memorization. Finally, we explicitly construct neural networks with ( log 2) parameters for optimal robust memorization of any binary classification dataset by controlling the Lipschitz constant of the network.
INTRODUCTION
Memorization with neural networks is study the expressive power of neural networks to interpolate given dataset. The main focus of the study is to determine the number parameters that neural network needs to memorize the dataset. To be precise, for classification dataset D {(x, 1:)) with data x; E R and
labels V/ [L] {1, L}, network F Rd IR is called memorization for D if F(x,) = for all
i e [N]. Many important advances have been made in the memorization with neural networks by Huang
Babri 1998) Yun et al. (2019); Huang (2003); Vershynin (220); Daniely (2020); Bubeck et al. (2020); Park et al. 2021 Zhang et al. 2021 Vardi et al. (001). Memorization has been shown to help generalization on
"Corresponding author.

---

Published as a conference paper at ICLR 2024
complex learning tasks (Ma al. 2018 Belkin al. 2019 Feldman & Zhang 2020), because data with the same label have quite diversified features and need to be nearly memorized.
However, in many fields, the required neural networks must not only be able to interpolate the dataset, but also be robust on the dataset. For example, in the field of automatic driving, the automatic driving system must be able to accurately recognize all road traffic signs, but many traffic signs may have noise on themselves, such as graffiti, stickers, and dirty, and networks that lack strong robustness will generate incorrect classification results on them, which can lead to traffic accidents. Therefore, the field of autonomous driving, a robust network that can withstand all kinds of noise is crucial. The same is true in some other areas, such as autonomous aviation and safety monitoring systems.
Another area closely related to network security is adversarial examples (Szegedy et al. 2013 Goodfellow et al.
2014]; that is, is possible to intentionally make imperceptible modifications to a standard sample so that the network outputs a wrong label. Unfortunately, adversarial examples are hard to eliminate for commonly used networks (Azulay & Weiss] 2019) Shafahi et al. 2019 Bastounis et al., 2021 Gao et al.)
2022
Yu et al., 2023). The existence of adversarial examples makes it vulnerable
neural networks in
safety-critical systems, which provides another reason to find robust networks.
So, some natural questions are raised: How many parameters does a network need to give a correct answer for given dataset even if certain noises exist, and what is the computational complexity to find such a robust R x [L] with separation bound Ap # ||x; - 2ol and a robust budget μ < xp/2, a neural network F R" + R is called robust
network? Strictly speaking, for a classification dataset D {1ra 11)
memorization of 'D with budget μr F(x) = argmin [F()) [] = ys for all x satisfying ||x - 2: S μ.. Furthermore, hypothesis space H of neural networks is called an optimal robust memorization (with respect to the robust radius) of D. if for any < XD/ 2 there exists an F E H that is a robust memorization of 'D with budget μ.. Notice that if μ 2 XD/2 then B(T,, p)) n B(z,, (b) * 0 for some y; F yj- and thus there exist networks that can robustly memorize D with robust budget μu, so μ \D/2 2 is always assumed.
There exist significant works on robust memorization. The existence of robust memorization was proved by Yang et al. (2020) [Bastounis et al. (202I). which may have an exponential number of parameters, since the universal approximation theorem was used. In a recent work (Li et al. 2022).. a robust memorization was constructed, but this result limits the robust budget < X/4 which is not optimal compared to the largest possible budget /2. A lower bound for the number of parameters for robust interpolation was also given by (Li al. 2022p. In this paper, a systematic study of robust memorization is presented by answering the following three questions.
Question Q1: What is the computational complexity decide whether fixed structure neural network is a robust memorization of a given dataset DD? This problem is often encountered in reality because we usually train pre-designed networks, such as VGG16 (Simonyan & Zisserman 2014) and ResNet18 (He al. 2016).
For this question, we show that, for certain small networks, robust memorization is NP-hard. Theorem 1.1 (Informal). For R+ and a classification dataset D. it is NP- NP-hard to decide whether there exists a network of depth 2 and width 2, which is a robust memorization of D with budget a.
This theorem shows that it is computationally difficult to find robust memorization of given dataset using a network of certain simple structure. To our knowledge, this theorem is the first result on computational complexity for robust memorization. It has been proven that finding memorization for given dataset using a certain small networks NP-hard (refer to Section 2 for details). However, the NP-hardness of computing robust memorization for non-zero budget and the hardneessss of computing memorization cannot be deduced from each other as shown below. For a given dataset D and a given robust radius μa, the existence of memorization of D does not mean the existence or absence of robust memorization of D with budget μı; the absence of robust memorization of D with budget μ does not mean the existence or absence of memorization of D.
2

---

Published as a conference paper at ICLR 2024
A natural question is: Can the network structure in Theorem I.1 This problem is very challenging because it is difficult to relate the problem to NP-hard problems. It should be noted that all NP-hardness results for computing memorization are also for small networks.
be replaced by a general network structure?
As said in question Q1, for given dataset D and robust radius ps, it is NP-hard to find robust memorization of 'D with budget 1s within a given small network structure, so we want to know what kind of structure (can relate to D and ju) of network can be robust memorization of 'D with budget μ..
Question Q2:
To answer this question, we give some necessary conditions of robust memorization, and we also give a network structure that can be robust for any P < Xp/2, as following:
Theorem 1.2 (Informal). Let D C. In X [L] be dataset of size N and μa < XD/2 the robust budget. A network with width smaller than n cannot be robust memorization for some 'D and p. Furthermore, we can explicitly construct a network in polynomial time, which has width 3n + 1, depth 2N + 1, O(N)) non-zero parameters, and is a robust memorization of D with budget μ.
This result shows that the networks with constant width used in many works of memorization such as (Vardi et al., 2021) cannot guarantee robustness, and a network with O(Nn) parameters is enough to reach robustness for any D and μ.. In (Li et al. 2022), it was shown that for a binary classification dataset D, there exists a robust memorization network with budget μ < Ap/4, which has O(Nr log( X Noolylog(55) Xp )) parameters. This result has several differences compared to Theorem 1.2 First, their robust memorization does not reach optimal robust budget, since the budget is < Xp/4, while our theorem does not have such a limit. Second, the number of parameters O(N)) given by us is smaller, which does not have factors log log Ap and polylog( X Third, our conclusions are not limited to binary classification. Also note that the number of parameters of this robust memorization does not depend on the AD. L and μa, and these values affect the parameter value of the network.
N.
N
Question Q3: As said in question Q2, network with O(Nn) parameters is enough to ensure robustness for any given dataset D and μ < Xp/2. Unfortunately, when μ is very close to /2/2, the value of parameters of such network will be very large and tend toward oc, which will be far beyond the scale of the computation. So, a natural question is can we find a robust networks with limited parameter value? We try to control the Lipschitz constant of the network to answer this question in the case of binary classification problem.
Theorem 1.3 (Informal). Let D C R" x { be dataset of size N. Then we can explicitly construct a network F : R. - R in polynomial time, which has width (n)) depth O log(n)). O log(n)) non-zero parameters, and is a memorization D. Furthermore, the Lipschitz constant of F is optimal to guarantee robust memorization and the value of its parameters is (mmax(..9)ED |a||oo + 1/Ap).
This theorem requires more parameters compared to Theorem 1.2 but is more practical when the budget is close to 2D/2 2 because the values of the parameters are much smaller. Two necessary conditions for robust memorization via Lipschitz are also given.
2 RELATED WORK
Memorization, Baum 1988) showed that =networks with depth 2 and width ) can memorize a generic
binary dataset in l with size N. Huang & Huang (1990); /aartori & Antsaklis (1991); Bubeck et al. (2020) showed that networks with depth 2 and O(N) ) parameters can memorize an arbitrary dataset. Huang Babri (1998;; ; Zhang et al. (202I): Huang (2003) Yun al. (2019); Vershynin (2020); Hardt & Ma 2016); Nguyen & Hein 2018) further showed that networks with O(N) (ignoring some small quantities) parameters can be a
memorization for various networks and activation functions. Park et al. (202T) gave the first sub-linear result
by showing that a network with ( parameters is enough for memorization under certain assumptions.
Vardi al. 2021) ) further gave the optimal number of parameters Ö(VN). Since the VC dimension of
3

---

Published as a conference paper ICLR 2024
neural networks with N parameters and with ReLU as activation function is O(N2) (Goldberg & Jerrum 1993;
Bartlett et al. 1998 Goldberg & Jerrum 1993: Bartlett et al., 2019), memorizing datasets of size N
requires at least Q N) parameters. Bartlett et al.
2019 showed that depth helps in memorization; that is, a
network with depth L need (
[n( parameters for memorization under certain assumptions. Properties of
N
memorization were studied in (Daniely 2020
Patel & Sastry 2021
Xu al. 2021).
Robust Memorization, Existence of accurate and robust networks was proved based on the approximation of functions (Yang et al. 20200] Bastounis et al., (021). In a recent work (Li et al. 2022), a robust interpolation
network was constructed and a lower bound was given for the number of parameters for robust interpolation.
Furthermore, it was shown that robust memorization of two disjoint infinite sets requires exponential
number of parameters.
Computational Complexity. The first NP-hardness result was given in (Blum & Rivest, 1992), which
showed that it is No-complete to train certain networks with three nodes and with step activation function.
The computational complexities for networks with step activation functions were further studied in (Klivans)
& Sherstov] 2009 /Sai & Shai, (014). The computational complexities of networks with the ReLJU activation
function studied (DasGupta et al.. 1994 Livni al. 2014 Arora al. 2016, Boob et al. 2022
Froese et al. 2022). Recently, it was proven that even training a single ReLU node is NP-hard (Manurangsi
& Reichman 2018: Dey et al., 2020 Goel et al.) 2020). It is worth noting that all NP-hard results for memorization with neural networks are for simple networks.
3 PRELIMINARIES
For L E N4, denote [L] = (I...., , L}. For matrix W and a vector b, denote by Wijk the element of W at the j-th row and the k-th column and by (D the j-th element of For μ E R4, and x E R", denote B (25, p1) = { R" | - 2/|b0 S n.
We consider feedforward neural networks F R - R with D hidden layers and with a Relu as the activation function. The (-th hidden layer of F can be written
X, (Wi + b)) E IR,, E [D],
(I)
and the output is F(X,) = X + X, + +b++1 E RR where nig = n, Wi E - by E R", and DD-1 = F is said to have depth depth(FF Fi())) = Xi as the output of the (-th hidden layer of F(Xo) and F/ (Xo) the j-th element of (Xo).. The classification result of the network F(x) argmin [F(x) 1). that is, the label closest to F(x).
+ and width width(FF = max
D+1 n,, Denote
In this paper, will explicitly construct networks from the following hypothesis space. Definition 3.1. Denote the set of neural networks with depth d, width w, and p parameters by
(2) where para(F) = means that there exist two fixed sets In C N3 and Ia C N2 such that In U I, has p elements, wh1 * O for (I,i,)) E Iw. (()) # 0 for (4, s) E I. and all other parameters are zero. For brevity, we do not explicitly give the sets In and Ie, when we say para(F) = p. We use denote an arbitrary number in N. For example, Hn,d,+,+ {F R + I depth(FF) = d} is the set of networks with depth d, and the width and number of parameters can be any number in N4.
Hn,d,w,p (F; R= + R dF) d, width(F) = w. para(F) - P)},
Definition 3.2. Let N, L E N.. and D = { b:) C R" x [L] a dataset in R" with size N and label set [Z]. Denote D,, L.N to be the set of all such datasets. We exclude non-interesting cases by assuming n > 9 and L > 2. All datasets in this paper are considered to be in D,,L,N unless otherwise mentioned. The separation bound for a dataset defined as
Ap min fla; x,yloo (I, V.), U5) E D and y # U₁
4

---

Published as conference paper ICLR 2024
We assume Ap 0. Otherwise, D does not have proper classification.
The robust accuracy of network F on dataset D with respect to given robust budget μ E R4 is
RAD
1
Σ (R.y)ED
1( Bo (2, y).
D
The problem of memorization for dataset E L.N is to construct a neural network F RR" - R, such that F(a) y. V(z, y) D. In this paper, consider the problem of robust memorization.
Definition 3.3. The problem of robust memorization for a given dataset 'D Dn.L.N with a robust budget is to build a network F RR" - R satisfying RAp ()) 1. A network hypothesis space H is said be an optimal robust memorization for a dataset DD if for any μs < >p/2, there exists F E H such that RAD(F, (u)
4 OPTIMAL ROBUST MEMORIZATION
this section, we investigate the existence and computation robust memorization from three perspectives. First, show that the computation of robust memorization for certain networks is NP-hard. Second, provide some necessary conditions for the existence optimal robust networks. Finally, we show that for any given dataset, optimal robust memorization exists and can be computed in polynomial time. Note that Theorem [.1 follows from Theorems 4.1 and Theorem 1.2 follows from Theorems 4.3 and 4.8
4.1 ROBUST MEMORIZATION FOR CERTAIN SIMPLE NETWORK IS NP-HARD
this section, we prove that computing robust memorization with certain simple structures is NP-hard. For a E R4 and dataset D C Dn,L.N, denote by RobM(D, a) the decision problem for the existence of an E 22,,2,x, which is robust memorization of D with budget a. We have the following result.
Theorem 4.1. RobM (D, o:) is NP-hard. As consequence, it is NP-hard to compute F E H,,,22,,, which is a robust memorization of with budget a.
We prove the theorem by showing that RobM(D, a) is computationally equivalent to the following NPC problem. The proof details Definition 4.2. Let yp be a Boolean formula and & the formula obtained from y by negating each variable. The Boolean formula sp is called reversible if either both yo and satisfiable or both are not satisfiable. The reversible satisfibility problem to recognize the satisfiability reversible formulae in conjunctive normal form (CNF). By the reversible 6-SAT, mean the reversible satisfiability problem for CNF formulac with six variables per clause. In Megiddo 1988), it was shown that the reversible 6-SAT is NPC.
Appendix [.I
4.2 NECESSARY CONDITIONS FOR THE EXISTENCE OF ROBUST NETWORKS
In this section, give two necessary conditions for the existence of robust neural networks, which imply that robust memorization essentially harder than memorization that more complex networks and more parameters needed. These results are in line with the theoretical and experimental observations that, in order to increase the robustness, the network needs more expressive power, even the original set is linearly separable (Madry et al. 2017 Gao et al. 2019 Li al. 2022).
The first necessary condition is in terms of the width of the network.
Theorem 4.3. For any d and N
an optimal robust memorization for Dn.L,N- In other words, there exist a dataser E Dn.L,N and a μ. < XD/2 such that any F with width smaller than n is not robust memorization of 'D with radius μ.
Hn,dd,
5

---

Published as a conference paper ICLR 2024
Proof Sketch. Let F: + R be a network and let W be the weight matrix of the first layer of F. Then Wi E RR** If F has a width smaller than n. then K < n. that is, W1 is not of full-row rank. Based on this property, we can construct a dataset DD such that FF is not an optimal robust memorization of D. Details of the proof are in B.2
Remark 4.4. It was widely observed that the width of the network plays key role in robustness. Gao et al. (2019) showed that increasing the width of the network is necessary for robust memorization. In (Allen-Zhu et al. 2019 Du al. 2019a Li & Liang 2018 Zou et al. 2018). was shown that when the width large enough, the gradient descent converges to a global minimum point. Theorem 4.3 gives more evidence of the importance of width in robustness, that is, to be a robust memorization for an arbitrary dataset, the width of the network must be at least equal to the dimension of the data.
The lower bound of width given in Theorem 4.3 is still necessary even in more general cases, shown by the following proposition whose proof is similar to that of Theorem 4.3 and is given in Appendix B.3
Proposition 4.5. For any À > 2μ > O, there exists a dataset D E Dn.L,N such that Xp 2 X and any network in x,,, is not a robust memorization of 'D with budget if < n.
The following proposition shows that depth 2 networks are optimal robust memorization for any dataset. Furthermore, necessary condition for depth networks to be an optimal robust memorization of D Dn,L.N that the width of the network must be greater than N.
Proposition 4.6. For neural networks with depth 2, we have the following results.
(1) 2 is an optimal robust memorization for Da.L.N-
(2) For any L 2 5 and N > 9, Hn,,N,, is not an optimal robust memorization for Do.L,NN In other words, there exist a dataset D E Ln,, and a μ < >x//2 2 such that any F. with depth 2 and width is not robust memorization of DD with radius μ.
Proof Sketch. For dataset D E D,,,N. and a budget μ AD//2, since D is finite, we can assume that 'D is [-C, C for some C R. There clearly exists continuous function c.6 can be obtained using the universal approximation theorem (Cybenko 1989 Leshno et al. 1993 to function E. The proof for (2) of Proposition
[-C, C + IR such that
E(i) y for è E [xx, μ1) and (I, y) E D. Then (1) of Proposition 4.6
4.6
can can be found in Appendix B.4
Remark 4.7. We give detailed comparison with memorization networks, In (Vardi et al. 2021 was shown that for any dataset D E Dn,L,N, there exists a network F E Н n,, 12.00 which can memorize D; that is, networks with width 12 are enough for memorization. By Theorem width cannot be optimal robust memorization. Here, Ō(.) hides certain logarithmic factors. In (Zang et al. 2021), it was shown that for any dataset D E L,N, there exists a network F E H,,2,N O(N+)))) which can memorize D; that is, networks with depth width N are enough for memorization. By (2) of Proposition 4.6) networks with depth 2 width N cannot be optimal robust memorization. In summary, robust memorization is essentially harder than memorization.
networks with fixed
4.3 OPTIMAL ROBUST MEMORIZATION WITH NEURAL NETWORK
The following theorem gives an optimal robust memorization for any given dataset. Notice that the network is constructed explicitly.
Theorem 4.8. The hypothesis space More precisely, for any D E DI,L.,N and μ. < Ap/ 2, there exists a robust memorization network F of D with
is an optimal robust memorization for D L.,L,N-
budget μ such that wJdth(FF 3n + I, (F) 2N + 1, para(F) = (N 1)(12n + +5) 2, and the absolute values of the parameters (w)) ||>||| 0o XD-
L
6

---

Published as a conference paper ICLR 2024
RR [4]. suffices show that for any μ Xp/2, there exists a network F= Rn + R with depth 2N + 1, width 3n + 1, and O(Nn) parameters, which can robustly memorize with robust budget μ.. From equation I a neural network F RR + can be constructed as follows: starting from the input E IR", performing affine transformations over Il and taking the activation function a recursively. what follows, we will give a sketch of the construction of F. The details the proof are given in Appendix B.5
Proof sketch. Let D (( 3:
Let E I be the input and C R, satisfy C> |-, + μl > for all e [N] and j [n]. First, we need to know in each layer of the network, which can be achieved with neural networks by the fact (xx()) + C) x(6) + C' for j E [n]. x E (0, 11), and E [N].
Second, for each i [M], we construct neural network Ex(x): R R:
(x(3) = AD 24
Vi
E J=1 (a
()) x00
(n) + oxx - (1) k1)
which satisfies the following properties: (1) Ex(x) yi for Boo u); (2) Ex(x) for x
(2 ();; (3) (x) S 0 for x E Boo (Th, (4) and ye + yi.
Finally, the output is F(x) [ (.,x,), 0}, which can be achieved with neural networks by the property: ma, =} = y + a( y) for y. E R.
Now we show that F is the required network. Let x (x, (1) for [N]. Then (x) ys- For i & s. there exist two cases: if y: = Vs. then Ex(r) < ye: if y: * Ys, then Ex(x) S 0. In summary, F(x) [ (x, 0} E, = ys that is, F is robust at H, with budget μ.
Remark 4.9. Note that the network constructed in the proof of Theorem 4.8 satisfies F(I) ys for all
I E ( ()) and [NT, which is a special type of robust memorization. The following proposition shows that these two types of robust memorization essentially need the same number of parameters. More details on the number of parameters and the proof of the proposition are given Appendix [B.6]
Ln,L.N- If the network F is robust memorization of D with budget μs then there exists a network G R + R with (g) = 2, width (g) = 2L, and para(g) = 6L, such that Fi (F))F) satisfies Fi (z) Yi for all z g0 (i) and i [N]
Proposition 4.10. Let { yi) Fi- }
Remark 4.11. In this paper, we focus on robust memorization under the norm Loo. because adversarial attacks with the norm Loe are the most widely used attacking methods in the image classification problem. Theorem 4.8 can be generalized to any norm 2 1; see Appendix B.7
5
OPTIMAL ROBUST MEMORIZATION VIA LIPSCHITZ
In this section, we construct optimal memorization networks by controlling the Lipschitz constant of the network. Theorem 1.3 follows from Theorem 5.2
The To norm Lipschitz constant for F R >> is defined as
[F(x)- -1
Lip (F)
max 2 ayti
In this section, we consider binary classification problems and the dataset has the following form
D = (1x, 1:) C R" x 1),
(3)
Denote B, to be the set of all D of the form in equation 3 In order achieve robust memorization by controlling the Lipschitz constant of F, the classification result of F is defined as F(x) = Sgn(F(r)),, which is the commonly used setting for binary classification data in equation 3
7

---

Published as a conference paper ICLR 2024
Because there exist (z,, 1), (zj, D such that Li (F) [F(x)) (ox)) -zylo> = which motivates the following definition.
AD. if JF memorizes D, then
Definition 5.1. A network F is called a robust memorization of a dataset via Lipschitz with budget J AD/2, if F is memorization of DD and (F) S 1/p. Furthermore, F is called an optimal robust memorization of "D via Lipschitz, if J is memorization of D and Lip (F) = 2/AD.
5.1 OPTIMAL ROBUST MEMORIZATION VIA LIPSCHITZ
The following theorem gives optimal robust network via Lipschitz for any binary classification dataset.
Theorem 5.2. For any dataset D E Ba,N, the hypothesis space HN Ol) O(N) lug(n]) contains network F that is an optimal robust memorization of DD via Lipschitz, and the values of parameters of F are (2,)
|| Ap)-
3 Let E R be the input and C E R satisfy C > |z|5| + | 0.5Ap > for all i [N] and E [n]. The construction of the network F has three main gradients.
Proof Sketch. Let
defined equation
First, we need know x in each layer the network, which can be achieved with neural networks by the property (z C)) xا5 C for j E [n]. E B (z,, p)), and [N]]
Second, for each & E [A), we construct neural network (x) = || Ixlloo which can be achieved by the properties (2x) + ( (-x) = | and max sr, y) = + ( x) for æ, E R, since ||=||oo = max (z())
Finally, the network is F(x) = Vuu 0 be computed by the property min y) = x ofx < y) for x,, y E I.
2 || Twn (oo)) where wN = argmin [x -; 2:lloo. WN can
Am
We now show that F satisfies the condition of the theorem, that is, F memorization of D and satisfies (F) Lip
So, F(xx) yk. that is, F is a memorization of D. I B( 0.5Ap) ) for some k E [N], then = k and F(x) = V/ -1
2. A
Zk, then WN argmin [ || 2 2:/loc
Lip (F) 2. over (xx,, 0.5Ap), since y; [-1,1]. If not B U 1B, 0.5Ap), then || Twx 1b00 > 0.5Ap and hence F(x)= = O. As a consequence, we have Lip (F) -S2 Thus, F is an optimal robust memorization of DD via Lipschitz. Details of the proof are given in Appendix C.2
Xo
Remark 5.3. We compare robust memorization with robust memorization via Lipschitz. By Theorem it requires O(N)) parameters for optimal robust memorization. By Theorem 5.2 optimal robust memorization via Lipschitz needs O log n1) parameters. Therefore, to achieve optimal robust memorization via Lipschitz, more parameters are required according to these results. However, robust memorization via Lipschitz also has advantages. First, there indeed exists network that is optimal robust memorization via Lipschitz, while for robust memorization according to Definition 3.3 optimal robust memorization exists for a hypothesis space of networks. Second, robust networks via Lipschitz have controlled parameter values.
5.2 NECESSARY CONDITIONS FOR ROBUST MEMORIZATION VIA LIPSCHITZ
easy to see that robust memorization via Lipschitz implies robust memorization, so the necessary conditions given in Section 4.2 are also valid for robust memorization via Lipschitz. In this section, give more necessary conditions for robust memorization via Lipschitz. In the following proposition, we show that necessary condition for F be an optimal robust memorization via Lipschitz is that (epth(F) > whose proof is given in Appendix
Proposition 5.4. Assume N n There exists a dataset T E Ba,N, such that any network F with depth 2 is not an optimal robust memorization for T via Lipschitz.
8

---

Published as conference paper ICLR 2024
networks of depth 2 is an optimal robust memorization for any dataset, so Proposition 5.4 implies that robust memorization via Lipschitz is harder than robust memorization. The following proposition shows that this fact also true in more relaxed case which does not reach optimal robustness. The proof of the proposition is given in Appendix C.4
By (1) of Theorem 4.6
Proposition 5.S. Let H = =F:R² - I: depth( = 2, width(FF = 4ml 4m|m=]) and assume N 11+
Then there exists a dataset D & Ba,N such that the following results hold.
(1) H an optimal robust memorization, for D; that is, for any μ < XD/2, there exists a network F H. which is a robust memorization, for 'D with budget j..
(2) There exists j 2p/2 such that any F H is not robust memorization for 'D via Lipschitz with budget μi: that is, if F is a memorization for DD then oo > 1/p.
Note that (2) of Proposition 5.5 cannot be deduced from Proposition 5.4 because in Proposition B.5 must satisfy both (1) and (2), and the robust budgets for Propositions 5.4 and 5.5 are AD 2 and fr, respectively.
6 CONCLUSION
This paper extends previous work on memorization with neural networks to robust memorization. We study robust memorization in three aspects. First, we prove that for depth and width neural networks, is NP- hard to compute robust memorization. Second, give explicit construction of optimal robust memorization networks for a given dataset in polynomial time and several necessary conditions for the existence robust memorization. Third, give explicit construction of optimal robust memorization networks for any binary classification dataset by controlling the Lipschitz constant of the network.
Problems for further study. In this paper, consider the Lee norm due to the fact that the L. norm is the most widely used norm in adversarial attacks for image classification. is interesting to consider robust memorization for other norms. We already have partial results on this problem. In Appendix B.7 extend Theorem 4.8 to the case of Lp norm with 2 1.
In (i et al. 2022). a lower bound Q Nn) is given for the number of parameters of robust memorization network. There exists a gap hetween the current best result O(Nn) of Theorem 4.8 and the lower bound. An open problem is to find the optimal number of parameters needed for optimal robust memorization.
this paper, we consider the expressive power of the network for robust memorization, and generalizability is not studied. In (Li et al., (022). it was shown that exponential number of parameters is needed to robustly memorize a manifold, which was closely related with generalizability. However, the result not the standard form of generalization bound, which gives an upper bound for the difference between the loss over the whole data distribution and the loss over a finite training set. The generalizability memorization networks needs to be studied.
Theorem L.3 is for binary classification problem, it seems a challenge problem to extend such a result to multiple classification problems.
Acknowledgments. This work is supported by CAS Project for Young Scientists in Basic Research, Grant and ISCAS Basic Research ISCAS-
No. YS40- ISCAS New Cultivation Project ISCAS- JCZD-202302. This work is partially supported by the NSFC grant No. I 1688101 and NKRDP grant N.2018YFA0306702. The authors thank anonymous referees for their valuable comments.
9

---

Published as a conference paper ICLR 2024
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference on Machine Learning, pp. 242-252.
PMLR, 2019.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint 1tti::v611.014999 2016.
Aharon Azulay and Yair Weiss. Why do deep convolutional networks generalize so poorly to small image transformations? Journal of Machine Learning Research, 20(184))1-25, 2019.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems, 1998.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20 (1):2285-2301, 2019.
Alexander Bastounis, Anders C Hansen, and Verner Vlačíé. The mathematics of adversarial attacks in ai-why deep learning is unstable despite the existence of stable neural networks. arXiv preprint 1xX.::200900609 2021.
Eric B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity 4(3):193-23) 215, 1988.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32); 15849-15854, 2019.
Avrim Blum and Ronald Rivest. Training 3-node neural network is np-complete. Neural Networks, 5(1):
117-127, 1992.
Digvijay Boob, Santanu S. Dey, and Guanghui Lan. Complexity of training relu neural network, Discrete Optimization, 40:0006,0, 2022.
Sebastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. In Advances in Neural Information Processing Systems, volume 33, pp. 4977-4986, 2020.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989.
Amit Daniely. Neural networks learning and memorization with (almost) no over-parameterization. In Advances in Neural Information Processing Systems, volume 33. pp. 9007-9016, 2020.
Bhaskar DasGupta, Hava T. Siegelmann, and Eduardo Sontag. On learnability question associated neural networks with continuous activations (extended abstract). In Proceedings of the Seventh Annual Conference on Computational Learning Theory, pp. 47-56, 1994.
Santanu S. Dey, Guanyi Wang, and Yao Xie. Approximation algorithms for training one-node relu neural networks. IEEE Transactions on Signal Processing, 68:6696-6706, 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 1675-1685, 2019a.
10

---

Published as a conference paper ICLR 2024
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2019b.
Dennis Elbrächter, Dmytro Perekrestenko, Philipp Grohs, and Helmut Bölcskei. Deep neural network approximation theory. IEEE Transactions on Information Theory, 67(5):2511-2623, 2021.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In Advances in Neural Information Processing Systems, pp. 2881-2891, 2020.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775-1790, 2022.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. In Advances in Neural Information Processing Systems, 2019.
Xiao-Shan Gao, Shuang Liu, and Lijia Yu. Achieving optimal adversarial accuracy for adversarial deep learning using stackelberg games. Acta Mathematica Scientia, 42B66)))339-24118 2022.
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training depth-2 relu networks. arXiv preprint arXiv:201 1.13550 2020.
Paul Goldberg and Mark Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes param- eterized by real numbers. In Proceedings of the sixth conference on computational learning theory, pp. 361-369, 1993.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint
2014.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning, arXiv preprint arXiv:1611.0423/ 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Guang-Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE Transactions on Neural Networks, 1 14(2):274-281, 2003.
Guang-Bin Huang and H.A. Babri. Upper bounds on the number of hidden neurons in feedforward networks with arbitrary bounded nonlinear activation functions. IEEE Transactions Neural Networks, 9(1): 224-229, Jan 1998.
Shih-Chi Huang and Fih-Fang Huang. Bounds on number of hidden neurons multilayer perceptrons in classification and recognition. In Proceedings 1990 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2500-2503, 1990.
Adam R. Klivans and Alexander A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, 75(1):2-12, 12, 2009.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with nonpolynomial actívation function approximate any function. Neural networks, 6(6):861-867, 1993.
Binghui Li, Jikai Jin, Han Zhong, John E Hoperoft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. In Advances in Neural Information Processing Systems, 2022.
11

---

Published as a conference paper ICLR 2024
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, 2018.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in Neural Information Processing Systems, 2014.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. In Proceedings of the 35th International Conference on Machine Learning, pp. 3325-333333 -334,,34,22 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2017.
Pasin Manurangsi and Daniel Reichman. The computational complexity of training relu (s). arXiv preprint A.N0:0881000207, 2018.
Nimrod Megiddo. On the complexity of polyhedral separability. Discrete & Computational Geometry, 3: 325-337, 1988.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho. and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems, 2014.
Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 3730-3739, 2018.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Proceedings of Thirty Fourth Conference on Learning Theory, pp. 3627-3661, 2021.
Deep Patel and P. S. Sastry. Memorization in deep neural networks: Does the loss function matter? In Advances Knowledge Discovery and Data Mining, pp. 131-142, 2021.
Michael A. Sartori and Panos J. Antsaklis. A simple method to derive bounds on the size and to train multilayer neural networks. IEEE Transactions on Neural Networks, 244)4677-471, 1991.
Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? In International Conference on Learning Representations, 2019.
Shai and Ben- Ben-David Shai. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint orXiv:/409 /556, 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of relu neural networks. arXiv preprint 2 2021.
Roman Vershynin. Memory capacity of neural networks with threshold and relu activations. arXiv preprint arXiv:2001.06938, 2020.
12

---

Published as conference paper ICLR 2024
Han Xu, Xiaorui Liu, Wentao Wang, Anil K. Jain, Jiliang Tang, Wenbiao Ding, Zhongqin Wu, and Zitao Liu. Towards the memorization effect of neural networks in adversarial training. arXiv preprint (exxx::206604777 2021.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaudhuri. A closer look accuracy vs. robustness. In Advances in Neural Information Processing Systems, pp. 3588-8601, 2020.
Lijia Yu, Yihan Wang, and Xiao-Shan Gao. Adversarial parameter attack on deep neural networks. In Proceedings of the 40th International Conference on Machine Learning, volume 202. pp. 40354-40372 PMLR, 2023.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021. 2021.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- parameterized deep relu networks. arXiv preprint arXiv: 1.08888, 2018.
13

---

Published as conference paper ICLR 2024
A PRELIMINARY RESULTS ABOUT LINEAR REGIONS OF DEPTH 2 NETWORK
In the proofs for Sections and 5 we need results on the linear regions of neural networks with depth 2, which will be given this section. Note that ReI.U.
Let F Rn - R be network with depth 2 and width k. Since a(-z) a(x) and ((x)) = (z for a E R,, F(x) can written as the following normal form
F(t)= - - == 0,0(U, + b.) + Qz +
(4)
where a; (-1,1},b, E UR R and U. f Q Rlxn and there exist i 4 such that U; qU3 and b; = زbj for B I..
For network F in normal-form equation
we define the concept of linear region. Let H = for E
R" UA + b > 0} and H; = {x R" U + b < 0). If
R R= H +0,
then R is called linear region F, where 8; E (+, }.. The interior linear region R is the set of points r E R such that Uaa + b; + for all i [k). An edge of R is the set of points E R such that Uer + b 0 for some
Definition A.1. Let R be linear region. Define S:(Rt) if there exists an interior point of R such that Upo+hz h > 0; and S:(R) = -1 in the opposite case. Two linear regions RS and R2 are said to be neighboring linear regions, if there exists only one such that (, S, (R2) = -1. For two neighboring linear regions R1 and R2, the boundary of Rı and R2 is R₁ n R2 n {x U, + b, 0}. which is said to be defined by (U,.b.).
We give several properties for linear regions that will be used in this paper.
Lemma A.2 (Montufar et al. (2044). Let be a linear region of F.
(1) Over R F(x) = Ei Q]x + Eiesaibe WRx bR is an linear function, where {i (k): 13, WR R2 bR ER
(2) R is a closed and n-dimensional convex polyhedron. The set of interior points of R is an open set of dimension n.. An edge of R is of dimension S n 1.
(3) R is the union of all linear regions.
(4) For two linear regions Rı and Rg, Rı O R2 has dimension S n. 1 and the sets of interior points of R and R2 are disjoint. The boundary of two neighboring linear regions has dimension n
Lemma A.3. Let TR. satisfy Uęæ + b, 0 for some E [k]. Then for any >> 0, there exist two linear regions R2, R2, and two points and satisfying
(1) || ælloc S c and || x 2/ S
(2) æ; is the interior of R2 for i 1,2;
(3) Rí and R2 are neighboring linear regions and their boundary defined by (Ua, bz).
Proof. Let H; be the hyperplane defined by U, b, 0. Consider cases.
Case 1. If satisfies that U,æ + by = 0 if and only if j = s; that is s is the only element of [k] such that U. bg 0. Let 17 minje(M]/(a) |U, byl and
14

---

Published as conference paper ICLR 2024
21 x + m-min 2max
U2y
22 min 2maxje 10,
0
10.
For any 1: = (1, I 01100= I 1
ø112 S c/2, so (1) is proved.
Note that U, + min(c/2, 2 and 22 are on the opposite sides of H. Furthermore, for j + and 2x E {1,2}, we have
0. Similarly,
show U,02 + bg O. Thus, 21
Uy + bU] U8 by - ( 2max mmaxx11 ) TTC. U, U31
WNN
11 (w Uj U
n/2.
Therefore, Ty is an interior point of linear region Rg. By Lemma A.2 (2) is proved.
Since for any j o s and l E 2), |0,: + bj U, byو - n/2 < |U + byl. we have U,01 + by and Uyz² + bj have the same sign with U,z by. so (3) proved.
Case 2. Uy + bj- = 0 for more than one j E [k]. We claim that there exists an ã such that ||x x|1xx < e/2 and U, + by = 0 implies
8.
Let 5 = [j E U&] + bj = 0}. Since for j E 5, H, are hyperplanes passing x, any two of them cannot be parallel, or equivalently, U, & qU's for any E R and j E S, j + 8. Let V = {u E R² :Uن 0} for
j E [k]] Let c V, \ (UJES,J V)t). and let 1j minje ())s |U + byl-
Define ly min(e/2, 2max, mM |00 T 0 and
x 1. Then || 2//00 S || 2112
||6,0112 < e/2. We have U.Ō + b 0 and Uj b/ = Uyh.v + Us bb UgloU u + 0 when j E S/{s).
10,ā + byl = |0 + U,æ byl 2 2m U a 2|ll|12 U,U 2 1 when j E [4] S. So H,
and only if j Now, combining Case I for I, we can construct the required ω and 22. The lemma is proved.
T2 + V
4/2
21
T22 0
Figure 1: An illustration for Lemma A.4 The blue line is H, U,æ + b,. The green lines are H2 Uz + by (z + + and λzι + (1 A)(22 - v).
(j + s). The red segments are Ax
Lemma A.4. Let I1, TD E I² satisfy UaIi + b. 0 and U,z0 + b, -ffor some 8 E [k]. Then for any 6 0 and 1) 0, there exist x2, R2 such that
(1) ||ح| zolloc |101|00 S n
(2) U322 by 0 if and only if s:
15

---

Published as conference paper ICLR 2024
(3) Px Yoy (1- ()
u) and qA the set of X, such that is in the interior of a linear region RI,, 9x is in the interior of a linear region R2,2, and R1,x and R2.x are neighhoring linear regions with boundary (Us,by) bg). Then is a set of intervals with total length [1] 2 0.5.
(1-A((22 - v), where À E 0, Let 1 C [0, 1] be
Proof. Since H, = Urz + b, = 0} is an (n 1) dimeessiona hyperplane in R" and Hi o H2 for i + j. H, H, of dimension at most (n 2). Let 22 point in oo (To, 6) H, \ (UjzsH) Hz). Then ||.- rollso S and U, + by 0 if and only if j
such that Ary (1 N)æ² E Hy and let xy be such For j 7 8, since 22 $ Hj, there exists most one a value it exists.
Let r = [0, \ ((1
TE: (U te X3 + +))) Then r C [0, 1) is a closed set with length
least k 2x = 0.5.
Let W max4e[1] ||U:||2, 1A λ + +11 +(1-))22 0j minxer + |J and 0 = minjza Since I is closed set and A $ T, we have 0 > 0.
Let up E <Rix satisfy UDU; # 0 for all j E [k]] and min 2w ||all2 It is easy to see that ||0||oo n Then for all À E T, have that
0
(al) 2 + (1 A)U PA and ZA (1 A)e = 92-
(a2) (xx + (1 ^)e) + b, and (2 (1 Aju) + b, have different signs for all À I, because
Ug + bg = 0 and U2V + O.
(a3) |U,u| S 2W so A)E) by have the same sign.
, 0 1U, for all j * s and E T, which means that (2 + (11A)e) bby
and (I
(a2) and (a3) show that if I, then RI and R2, are neighboring lincar regions with boundary (U,, bz). So 22 and satisfy the properties in the lemma, and T C I has length at least 0.5.
B PROOFS FOR SECTION
B.1 PROOF OF THEOREM
Denote Hn,2 = H Then an F(x) E Hn, can be written as
F == == +b) + s22 + b2) + c
(5)
where 8; [[1,1]] ER b, E CER.
For i [n], let 1, E R", whose i-th entry and all other entries are 0.
Denote F(x) = ([F(x)) where vp is the sign function. First, we prove a lemma.
Lemma B.1. Let F Ha.2 be of the form equation and z; il, E R.. Ff((z) F(2_1) -1 and F(22) F(2_2) = 1, then 8182 < when 2 0 and 8182 > when < O.
Proof. Let F be of the form equation 5 We just need to prove the lemma for n 1. Consider two cases.
(cl): Assume e 2 0. Since 11 = F(zn) ( + b,) + (22 + bz) + c) 2 ( +
b,) + $20 (U, b2)), at least of l -1 82 -1 holds. Assume that $2 -1. We will show that
16

---

Published as a conference paper ICLR 2024
$1 1. If this is not true, then 81 s2 11, Since -0(0)/4-30440) 2 -o(a/4 36/4), we have
0
< +
(-o(U - olU222 + b2) - h|000:/hhhhhhhhghh/.////////a/h0
b2) + c)/4
(-o + b1) - 3 (- b2) - 30 + b2))/ +
S -0 -U122-1 b2) +c
F(z-1)<00 <0,
which is contradiction.
(c2): Assume e < O. Since 1 = F(22) = ( +b) + S22 + b2) +c) (U10 + b)) +
(U222 + 62)), at least one of $1 = or s2 = 1 holds. Assume 81 = 1. We will show that 82 = 1. If this is not true, then 52 = =1 Then
1 =
= (o
(U222 b2) +c) (0 + b1) + c).
so (U1 + bi) +c> 0. From c 0, we have U1 0. Similarly, we have U1 bı > 0. It is easy to see that U1 + bj 2 min + bj U1 +1 so 0 + b1) + > 0, and hence U1 + b1 > 0. Similarly, we have -1 b2 > 0. From F(=)) = -1 and 0U1 + b2) + c > 0, we have
0 (()) ạU + h) (U2=1 + b2) + - - + b2),
so U221 + by > 0. Similarly, we have U2--1 + b2 > 0. Now consider the linear function L(x) (U1x+ + bi) ) -
(U2x + b2) c
Since < 0, U1 2 + b, > 0, U2 + b 0, and F(21) -1, we have T.(21) = (U121 + b,) - (U221 + 12) + c = (U1 + +b) - (U221 + b2) +c= F(z1) < Similarly, I(=-1) <.
Since < 0, 21 + b > 0, and F(22) 1, we have L(z2) (U122 + b1) (U222 + b2) +
@U112 22 + bi) - (U222 + b2) + o(U122 +b) - oU2222 + 62) + > 0. Similarly, we have L(z_2) >
Hence L(0) = (L(=)) + (==1)))/2 < 0 and L(O) (1(z2) 2(=-2))/2 > 0, contradiction, so 82 =1
We now give the proof of Theorem 4.1
Proof. Let skk, m) = Iiis, m) be 6-SAT for k variables, where si(k, m) = 3 and ã.i is either v. or mx for some & E [k] (see Definition 4.2).
For i [m]. define of E R as follows: Q if xy occurs in p. (k, m): O - if -x, occurs in (pi(k, Q 0 otherwise. Then six entries in Q are 1 or - and all other entries are zero
We define binary classification dataset D(p) = [1x, 3)) c. R x [2] as follows.
(1) For i
[k], x. k1,, V/: 1.
(2) For i E [k + 1, k + 2,..., 2k Tj- = kk = 1.
(3) For i (2k 1, 2,
3k), xg 22k 2-k,, 1/1 2.
(4) For i E [3k + 1,3k + 2, 2
= -2k1, 3k: = 2.
(5) For i E (4k + 1, 2,...,
4k 4 m). D4 k/4 Q. 46- V: = 1.
17

---

Published as a conference paper ICLR 2024
((p)) has separation bound 2 k/4 > 1, because & 2 6 for 6-SAT problem. Let the robust radius be a = 0.5 7 where < 10k It is clear that both D and a require poly(m, k) byte representation.
We claim that RobM(D(p), a:) has a solution F Hn,,,2, if and only if the reversible 6-SAT ( m) has a solution J {z, = u21ÿ=1. Furthermore, FF and J can be deduced from each other in polynomial time; that is, RobM(D(p)), a)) is computationally equivalent to sok,, m). Since reversible 6-SAT is NPC Megiddo 1988). by the claim, RobM(D(p). a) is NPC, which implies that RobM a) is NP-hard for D D L.,L.N This proves the theorem.
Before proving the claim, we first introduce a notation. Let J = {ry my be a solution to the reversible 6-SAT problem yp and (A, m) = V clause of yo, where E (-1,1). Then denote by q(J, (ps) the number of øt, which has value 1 on the solution J. If (J{ O, then you is not true. If q( spa) 6, then -ii is not true. Since J is a solution to the reversible 6-SAT problem yp, we have S (JJ,p)) S 5. It is easy that q(J, p.)
I( [R]] Qf [b] 2/Hl.
The claim will be proved in two steps.
Step 1. We prove that if (okk, m) has a solution J = {2y wン}グーı then RDbM 0.5 7 has solution F, where 8, (11, Let U1 = (1,, (2, ......, ok), U2 (u1, 02,-.., uk)....kk).. Define F E H4.2 + be F(z) = [U1x - + - 1.5k) 1.5 - -y. It is clear that F can be obtained from J in poly(k). We will show that F(x) is robust memorization of ((p) with budget a 0.5 7,
It suffices to show that for any i E [4k + m]. F is robust at xi with budget a. For x E B((a, a), there exists [-a,a]] af* such that x xg + e. The proof will be divided into three cases: (c1) (c3).
(c1). Assume E [2k]] It suffices to prove the result for i E [k] and the result for i = k + 1,... 2k can be proven similarly. Since 24 E {-1, 1). we have ||U||| k. Then for E [k], we have 2; k1, and hence U1 (z; + e) 1.5k S k/u; + <||U1ll 1.5k < k/oa + (0.5 - 1) - 1.5k = -nk < 0. Similarly, we have (21 + c) 1.5k < Then,
F(x) = F(z; + E) = (z + - 1.5k) + (U2(1; (z: + - 1.5k) + 1.5 - , < 1.5.
Therefore, [xx) 1| < [(x) - 2). Thus F(x) = and F is robust at x; with budget a = 0.5 - -% Case
(c1) is proved.
(c2). Assume E (2k + 1,....,443) 4k}. We need only prove E (2k + 1.... 3k), and the other cases
be proved similarly. Since U1 - U2 at least of the following two equations U1æ; 1.5k
(E-26) - 1.5k = 0.5k is truc, say the first is true. Then, U o ((-2k) 1.5k = 0.5k and U2z, - 1.5k = Ug9 x;
for any ||e||oo I 0.5 7. we have
F(z; + +c) (1, + 1.5k) + (U2(2z + 1.5k) - + (Ui + 1.5k) - + 1.5.
We have U1 (x; +) - 1.5k = 0.5k + Uie 2 0.5k - (0.5 - 7) pk. So F(x +c) 2 7k - 1.5 1.5, since k > 1. Therefore, [F(x) - 2| < [F(x) 1). Thus F(r) = so F is robust at with budget 0.5 7-
Case (c2) is proved.
(c3). Assume i E {4k + 1, 4k + 2, . 4k + m}. is clear that g(J, p pk) + q(J, 8 pi- = 6.
Then
SUIQi =
Ej $ f0
Ejery E Sg-=ae
k/4 Ej;ay 9i-s2, Sga(Qr Spin h/4
q(J. si 2k//4 q(,, kk/4
e (0, k. -k/2.- -k],
18

---

Published as a conference paper ICLR 2024
which means | u. & k. Similarly, we also have |U2Q S k. As a consequence, Ujz; 1.5k U1QT-4r k/4 1.5k 1 -0.5k. Since ||ú]|| = k. for any ||c| I 0.5 - we have U1 (z, + 1.5k Σ
-0.5k + +11011 -7) 7) -n < Similarly, (z + 1.5k We thus have
F(a, +C) o(Ui(z, +) -.5k) + o (U2(2 + 1.5k) 7 1.5 S 0
7 1.5 1.5.
Thus F(x) and F is robust at 2; with budget 0.5 7
From (c1) to (c3), F a robust memorization of ((p) with budget a = 0.5 - 7, and Step is proved.
Step 2. We prove that if RobM(D((p). 0.5 has solution F(x) s (20
Ha.2 which a robust memorization of D(p)) with budget a 0.5 - 7, then (kk, m) has a solution J. (Ia(b), we can assume that $1, 82 (-1,1)-
Since az (b)
Let c 1.5 + C, which means F(x) - 1.5 11 + b1) + $20 (U2a b2) + c. Therefore, we have F(x) if F(x) 1.5 < 0, and F(x) = 2 F(r) - 1.5 > 0.
The proof of Step is divided into two sub-steps, and we prove Step 2.1 in cases.
Step 2.1. Assuming 2 O, we will show that J = {z; = Sgn(U) ||= is the solution to the reversible 6-SAT problem (k:: m). We will prove Step 2.1 by proving six properties: (d1) (d6).
(dI): We have 81 = 1. Without loss of generality, we let 81 = and $2 = -1 Since F(z1) 1.5
F(x++1) 1.5 0 and F(x22++1) 1.5 F(ras+1) 1.5 > 0, (dI) consequence of Lemma B.1
(d2): We have - - + b2 + pl 1/2/1 > 0 for any E [-0. + y, 0.5 - > and g E [k]]. We just need to prove the case q 1. We first assume U. < 0. Since F is robust memorization of D(p) with budget
a = 0.5 7, we have F(m + PSgn(U22) < 1.5, so
0 > (U1(11 + pSn U2)) + b1) - (U2(21 + (Sg((U))) + b2) +
2 (U2((11 + pSgn (U2) + b2)+cc +
= 1 + + U2/11 + b2) +c
2 -o -- 1 p| + b2) (by c 2 0)
which means a( x p|1U211 (2) 0. Then have -kIU p||U2111 b2 0. For the case
U 2 0, we only need to consider 1++1 instead of 21. So property (d2) is proved.
(d3): We have U (:(0) and | > - for any q [k]. We just need to prove it for q 1. First,
we show that U # 0. If uf = O, we first assume ui)) < 0. Since F(x1) < 1.5 and F(æ2441) > 1.5, we have
0
F(x1) - 1.5
(U121 + b1) - (U221 + b2) +c
( + +b, - o(b2) to (by Uz = =)
z (22U( +b) a(b2) to (by U( 50)
((2kU(") +b) - (2kU, + bz) + (by U()) = 0)
a(U)#2441+ + b1) (U2224411 + b2) te
F(824+1)-15
O,
19

---

Published as a conference paper ICLR 2024
a contradiction, and thus U22 + 0. If U() 2 O. we only need to consider 24+11 and r3k+1-
Now we prove (d3). Let h = 1 if t > 0, and h = k + 1 if U/ < 0. Because F4+2k = =2r and F(xh+2x)
> 0 -.5
F(x)) 1.5, we have
F(en+28) 1.5
aU1 + b1) o aU22T1+2 + b2) +
12U + +b) - 0 (2 + b2) +
" Sgn(U()) + b1) (2k (1 + b2) +
o (by F(#n+2)) - 1.5 0)
oU11n + b1) - OU22n + b2) + (by F( - 1.5 < 0)
= Se(U2) (1)) + b,)
-k(U2 (1) + b2) +
which means o (2kU (2 + b1) (2 + b2) > a (kU1 (1) Sgn(U, + b1) - o + b2).
we have
o22U Sgn(t(f)) + bi) (2 + bn) - (a(kU( Sgm(t(( (c(k) + b1)
(X(US + ba))
(a(2k Sgn (Unl + bı) (kUt Sgn (10) +b)) (o(2k) + b2) okii b2))
(a(2kU Sgn (1 + bi) ( Sgn U2 (1) +b))) - ((2N)]))) + b2) - -K]U?" +b)) (by (d2))
(a(2kU Sgn ( + bi) <(KU Sgn (1))) +b)) kU
Then (2kU S bb)) ( Sgn(Un)) (1) +b) kUL" 2 0, which means 2kU, (1) (gn( +
by > 0. And according to that, we have:
0 < ( (1) + b1) alku
( S (1) + +.)) 1
Sgn U11) (2
+ +b1)
(gn(U:))) (1) + b1)) -
s (22R (g
(1)
) + +b) (KU Sgn(U: (2) + b2)) -
) 1
So get Uf Sgn(U("))>
|لا > 0, which means Sgn(U(") Sgn(U, and |1(T) > |1 (d3)
is proved.
(d4): We have 2 bj - 1|111 0 for any p [-0.5 + 7.5. 7] and q [k]]
We just need to prove it for 4 = 1. Let 1 if g()) > 0, and = A + if U(") < 0. Because
F(zn+2k pSgn(U1)) 1.5 0> F( + pSgn(U:)) - 1.5, we have that:
Flan-2x + PSgn(U:) 1.5
+ = ( + pSgn (U1)) + b.) - + + b2) +
= (2 +b + - (2k(U; + b2 + p1UU211)++++++ + (by (d3))
= ((2 + + +((Ull)) - (2k + b2 - p|112111) + (by (d2))
(by Flrn+2k + DSgn(U))) - -1.5
> (2n + + + b,) (U2 + (Ug))))) + b2) + (by (d3))
(by 0 > F(zn + pSgn(U:)) 1.5)
+
b2 + pl p c
b2 -(K(U!") b2 2l1 + (by (d2))
20

---

Published as a conference paper ICLR 2024
which means (22k:(]]] | bj plluill1) - 12 + + (x +b + pl(Uill1)
(M/ + b2 pl 112 [11 + so we have
a22 11 + + 0(H
+ > 0.
(d4) is proved.
(d5): We have max (10{3) | < 2(1 - - 1(U2111).
For any E [K], let if > 0, and h + < 0. We have ( -1.5
0, which means
0
(UI(IA (0.5 -) ()nn(())) + b1) (U22(M (0.5 (0.5--))n0(((()))0 (Ung) b2) +
[k||U[*)) (0.5 >)]|U]]11 + b1) [A|UU, + (0.5 7)1[U111 +b2) + c (by (d3))
a(k[U[*)| (0.5 7)]|U + 61) (A|1// (0.5 2)///11 + +b2) +
(by (d2))
(M|U{*) (0.5 +)|| + b1) - (1/U/= (0.5 - >)) + +b2)
1 - (0.5 (11 -1122|11
+b - b2 +c.
We thus have 1| -|U < -b, b1 b2 (0.5 7) (1 112 Then we have F(Th+22
(0.5 Sgn( - 1.5 > 0, which means
< (12 - (0.5 >)Sgn(U1)) + b1) - (U2((222+ (0.5 (0.0--7)SSpm (ggnn)) b2) c
(by (d3)) (2x|U[4) (0.5 +)]|//|| + 61) - (22A|U]-) (0.5 U211 +2) + (by (d4))
(2 - (0.5 7)]lU/11 + b1) - o (2k(U (0.5 - U2] + 62) +
s (2 (0.5 +) + 61) - (2A|U:/-) 100-(00 - >)111221 + b2) +
21/ (3) 1 (0.5
7/ 11 + b1 b2
So, we have { - k > 66 c+
and thus
2
k(u(1) x|
bb + b2 - c- (0.5 18.5-711 ( (|U2|11)
2
- (1 27) - ([0]]b)
21|U(11| -2 (1-2+) - 1112)
which means b|1(10) - (1
(1Uill - 11122)2) for any 2 e [k)]. Using this inequality, we have |(((1)| 1
A(|[U||) ||U2/h) - (KUF'
(k- - (1)-2))(- 1))((IU]l) 1|U2|])
L.I(|Ui])- - -1(U2]1) (by (d3) and 7 < 1/(10k))
2* (1 1 U11)21 -|Ublll) (by (d3))
which proves (d5).
21

---

Published as conference paper ICLR 2024
(d6): We have that {ar )) a solution to the reversible 6-SAT problem ((k,m).
If this is not valid, then there exists an E [m] such that a ({(Snn(U (X) ) ) (x) 6 or "((Sgn(U{())) --== th)
0. We just need to consider the first case, because when o( (Sgn(U((m)) } )==1, 0:) = O. there exists a j E [m]] such that Φj = th. so a (( j== U5) 6.
Without loss of generality, we assume that the index of the six entries in Φbs are 1, 2, 4,5, 5, 6. By the definition of Tak-i, we know that U1 Ej=1 |0(1)1, and by (d3), we know that U2 E [
Using (d2), we know that
+ 0 < 12 (0.5 -111111111111111111111111111111 < E 11 (3) + + (0.5 (0,5
(6)
Without loss of generality, we assume U!!) > O. Since F(12x-1 - - (0.5-7)Sen(Ui))) - 1.5 > 0, we have
0
< (U - ( 083 (0.5-(()ss())))) + b2) +
(0.5
= (2k(U[") + bj - (0.5 r)]l/]]11) (2 b2 (0.5 -2]1(2)11)+ + (by (d3))
(7)
s (2 + b1 - (0.5 r)]l)/]11) - (2k) U2 11) + b2 (0.5 +)(((2111)
= (2K|U1") + b - (0.5 [11) - (211032) + b2 -0.5 - 7)](U2(11) (by (d4))
So 0 < (2 + b, - (0.5 7) [U]]])) (2A| - (0.5 - (255-)) + U < We only
need to consider 1 and the others are the same. The conclusions are the same for U i = I,..., 6.
Then because F(xs++ (0.5 S))gn(U)) 1.5 < 0, we have
> (0--0(((-0000--000(())))-----010 (0.5 ((5g-)))sn()))) b2)+ +
+
b2 (0.5 7)][U2]11) + (by (d3))
=
[1(0 + by + -0.5- -)) +
=
= a -(EE)=11 1+h --0---+-00--00 - + ( (0.5 - >)]lU>l1)) +c (by 66
z 4E 1 - 1 (0)+000))))(33)33 [U2]])+ +
= E (200)) (0.5 - >))1[1] -
2 b2 (0 +
A _ Σ
-10)) (1
(1-2)) -
M N
(U (1-2)))))) [[0])) 1110:/11111111 -
(by 7
(by (d5))
a contradiction, and Step 2.1 is proved.
Step 2.2. Assuming e < 0, will show that J = {x; Sgn(U Sg 2 solution to the reversible
6-SAT problem m). The proof is divided into six steps: (el) (e6).
(el): There must be 81 82 1.
Just use Lemma B.1
(e2): V( for any q [b].
22

---

Published as conference paper ICLR 2024
We just need to prove for q = 1. First we prove that U14 o 0. not, that is U14) 0. Without loss of generality, let U/4) s 0. Since F(z1) 1.5 < 0 and F(x2x+1) - 1.5 >> O, we have
0
F(m1) - 1.5
oU12 + bi) + +Uuu + b2) +o
o(b)) + =okk? bb) tc (by U11) =0)
2 a(bi) + (2ku +b) +c (by U2 5
+bi
+ bb) +c (by U = 0) (1110++++b) o (U202411 + b2) +c
F(12+11)-1 1
0
which is contradiction, and hence U 0. When U/4 0, we just need to consider #&+1 and #3k+1-
Now we prove (c2), let = lf and F(xn) 1.5 < 0, which means
(1) > 0, or = ( < O. Then, we have that F(xR+2R) - 1.5 > 0
bb2 -c of 11= + Sen(U(")) b2))
b1)
(8)
0
and
o(Ui + +b + +b2 -2)
= a-- (2) + bn) + o (gn(U(+)) + (2)
(9)
< 0.
These two inequalities illustrate that or (- + b,) + t Sgn(U (1 Sg
+ b2) < o--2k|110)
b1) + 2 (((=2("""nnn(((")) + b2). Furthermore, since af o- bn) 2 2- + b2), we have
af al-kUp () b2) < af a(-2kU "(-2AUU"Sgn(U"""" (gn(U(") + b2). which means (- Sgn(((")) + bz)
(-2kU2 (gn(U(")) b2). Then U. " Sgn(U(") O, that U1"h 11" O. which what we want.
(i)
(e3):
| > (1 - 27) for any q [k.].
We just need to prove for q 1. Let h if ((()) > 0, or h + if U F(#n428 - (0.5 S)2) - 1.5 > 0 and F(z, + (0.5 - (005-)() 1.5 < O, which means
We have
+ b1) = af o(-2k|11") (0.5 -11l) +
a(U1(Tn+24 (0.5-7)558 -
(0.5 - ((5=))) + b2) - -00 (0ll + b2) - (by (c2))
> 0
(10)
and
(U (0.5- (0) - (0.5 (0.5--)56 (005-))Sgn(mj))) + b2)
= a(-b|U(") (0.5 - 7)11 b,) + (1: (0.5 1)2111 be) - c (by (c2)) (11)
<
23

---

Published as a conference paper ICLR 2024
Next, consider two situations:
(e3.1): If 2 + (0.5 -7)[|(il + 6, S 0, then we can prove that k > (1 - 27)
By equation 10 and the fact -2k] - 10 +b S O, we have (2k ()) | (0.5-7)
b2) c <>6 0.
By equation
we have a (k|u
(0.5 - >) + b2) - - o< (0.5 7) + +
| (0.5 (1-- <<0.
So (0.5- > + b2) < (2k|U (0.5 >)1 + b2). Then we get (1 2>) |12l| k| This
< <c< (2k - -0.55 -0.5->) + b2), which means (A)1;-)
is what we want.
(0.5 (e3.2): If 2 (10 b > 0, then we can prove 22 U2_1 (0.5 >) U1 + +b2 00 and k > (1 --)))
Since F(2 (0.5 - ()gnn(()
< 0, we have that
(U1(22) - - (0.5- b.) (U2(EE (0.5 - (0.5--))Sp0 ())gn(U)) (2)) + by) -c
= o- - (00
(0.5 - >)1/11111 + b2) - c (by (c2)) (12)
< O.
Since 12 + (0.5 - || hodd - (0.5- - 1)1 + b, > 0. Then by
it
equation 10 and equation 12 and -2K(U/ (05->)]
+ > 0, we have that
a (-x|o1") -b) (0.5 7) 1211 + b2)
- (1 (0.5 7) 112 + b2)
0
(13)
o (-2k - (1
2)111111 + b2) (-2k|u1-) | (0.5- +] (0.5 2) + 62)
which means < (10 (Use (xx) (g) $ |z y/ here). So (1(1 < - < (1)
- (0 1 + bb) S 1
Similarly, if 2 + (0.5 [ + b. > 0, then we have |014) > |0 |. But انانح 10 11) and
| > | cannot stand simultaneously. so -2k + (0.5 - -2]1 + b2 > 0 can not stand. Then
we have- - 2 + (0.5 >>||U2/11 + b2 < O.
Now using equation 10 and equation 11 we have
o( o-22k + (0.5 >)]| + b.) ( (0.5 >)|[11|1 + b2) c 2)11U1 + (2) - e
(-2k (0.5 - -000--))([[1>111) +
(0.5 +
a--x|o(1) (0) (0.5 1)2111 + bb2)
(0.5 2)1 + b2)
24

---

Published as conference paper ICLR 2024
which means (01-)) -02--01 + -005--)110 (0.5 (0.5 - 7) 2 + b2) (A/U2) (0.5->)1122111 b2)) Since - 22/UU2 + (0.5 >))111 +b2 50
(-2M(t)))
+ +b, < <22
similar to (e3.1), 1), we have (1 - 22) < k/1,%
So can obtain
0
< -1 + (by equc3)
(- -
+ b1) (0.--)))]llll
(-2k U1 (0.5 >)11U1111 + b1)
< (224) (0.5 - - + +b2) -k(U22 +0.5 - -0)12111 + b2)
which implies o 12 - (0.5- - -))--1) + +
0. Then we have
(2k (0.5 >)1 + +b) - a(KIU, (0.5- [0ll>)] + b2)
(2K - (0.5 7)1162211 + +b2) - |+ - >)1 + b2)
S (2K 91 - -0..5 >) + I >) + +b2)
1 -11- 22))1
This is what we want.
(c4): 1 > (1 271l for any q [k].
Similar to (e3).
(e5): J = {.. = Sgn | is the solution to the reversible 6-SAT problem (ok,,
If not, said in (d6), there is an i [m]] such that g( ({) )1= 0b) 6. And there is j [k] such that Φ, - 6
Without loss of generality, we assume that the indexes of the six entries in Φi are 1,2,3, 5,6. By the definition of Fak+i, know that U1 - and by (e2), know that U2 n [T(a), and by (e2),
- Ei 1. By the definition of Tak+jo we know that U144k+y know that U2344445 $ ンラ (.)
As said in (e3.2), have - 24: 2 + >) + 0r - ( (055 +b <0 standing for any [k). Let the last stand for 2 = 7. If the first one stands, it is similar.
Now we will show that
a (2 (0.5 - - +b)
a 3 u10) (05- bı) o0- Ej (154 +
+ (0.5 >) + +b) (14)
< (2 (05--
which lead to a contradiction.
(e5.1): We prove o Ej= ( +03-) ( (0.5-)))[(i]]]
(2k) 1 (0.5 U1 b,).
25

---

Published as conference paper ICLR 2024
Let h = 7 > 0, and = k k < Because F(I2k-n (0.5 (S)nn(U)) 1.5 and
1 + (0.5 >)1 b2 1.5 < O, we have
(U1(44422 (0.5 ->)Sgn(U1)) b1) + -0.55 o2k (0.5 +)]1(i]l+++
b2)
+ - + (00.505))((1))) 2)1111 b2) tc (by (e2))
1(2k|u] (0.5 +b)
O.
(15)
Because F(Eskts + (0.5 >)ggn(U)) - 1.5 < 0, we have that:
d(Ui(ZIN+: + (0.5 - -))gm(( + b)) + (U2 + (0.5 - r)Sgn(Ui)) +b) +
= |4 (0]5 + b1) + a(- E, 11===11;))
(0.5
(16)
+(0.5 - 1) (by (e2))
< 0.
By equation 15 and equation 16 it holds o Eラ= (7|5 (0.5 - + b.) + (1-=1111 (1,40
(0.5 ?) + b1) < (2k (0.5 )) + +b1). This is what we want.
(e5.2) We prove that 0 k: 25 (05-)) +o(- E I0 1 (0.5-))) o (2k - (0.5 - >) + b1).
By (e4), have that:
2x|U(T7) (0.5 - 1
2k(|Ui]|| E 10(01)
(0.5 ||
2A([|Ui|| (k 11)(1 -2))((1ll1/k) - -0.5 U1l
(by (e4))
(1.5+44k - -3>)1
(1.5(1 -2) + (0.5 ((.5-7))) (|/1=l (by < 1/(10k))
Σ |u|*) (0.5 >> (by (e4)).
O(2 |100--~~||(66-aa1000200000000110 (0.5 - [ull + 61) + 10 + (0.5 11 +,6 > )(2k - (0.5-2)]| + b1).
So ( Eg 1 10|
(0.5-)))111 +b)) Then o Ej 10/2)
(e5.2) proved.
From (e5.1) and (e5.2), the assumption is wrong and (e5) is proved.
B.2 PROOF OF THEOREM
Proof. It suffices show that there exists dataset D such that if F has width less than n and memorizes D (that is F(x) = y for (z, 3) D), then RAp(F, (F,,0..))))) - that F is not robust memorization of D with budget 0.4Xp.
Denote by 1 the vector all whose entries are and 1 the vector whose k-th entry is and all other entries are 0. Without loss of generality, let satisfy (n + 1)|N. We define dataset D {zx, yi 1= bound 1 as follows:
N-1 with separation
26

---

Published as a conference paper at ICLR 2024
(1) zo = 01 and yo = 24 1, and y 1 for i E [n]]
(2) for: i k(n 1),............... k(n + 1) + and k 1, N 34 x7 and yi y/. where i i mod (n + 1). It is easy to see that Ap 1.
R be network that memorizes the dataset D defined above and let W be the weight matrix of the first layer of F. Then W1 RK**. Since F has a width smaller than n, we have K n. We will show that there exists an s in [n] such that 36,, 5g E RR,, satisfying ||ōullo < 0.4,,16&lls < 0.4, and Wi W1 + 60) W1 (I' + 5z).
Let F; F -
Since K- < W1 IR *x*x is not of full row rank and, therefore, there exists a vector E I" such that W and ||a|| oo 1. For such a v, let |o(*) = for some & E [n]] We define 6o 8, E IR" as follows:
56 = 1/3 and %% = (+) / /3 for k # s;
81:)) = 0 and 0.²² = (()) /3 for k # s.
It is clear that |1ō0|loc - < 0.4 and | oo0
< 0.4. Also, H. + 8, - I1 - ó0 vl) Thus,
Wi + 6 - Wi( + 6,) WI + d0 Is 6,) Wi v) 0.
It is easy to see that for any x, = E R", Wiz = Wia implies F(x) = F(z). Since W (x + 00) = WI
d.), we have F(zo + 60) = F(x, + 5.). Since F memorizes D, we have F(zo) = 0, F(x.) = 1. Therefore, F(zu + +ō)) + or F(z. +.) + must be valid. In other words, F cannot be robust at 2o or F. for the robust 1((+ for E {L....... n+1
budget 0.4. Similarly, F cannot be robust for at least one point in {2;) (mn++=)(n+1)
1}.
N In summary, F cannot be robust for at least n+1 points in D, so RAD 0.4) S m+I
B.3 PROOF OF PROPOSITION 4.5
Proof. It is easy to construct a dataset { C R" such that B,
p)) = B (21, 2p + A)
B (x1, A). Then, we let D {(x1, 1)) ((x2, 2)] is easy to see that satisfies \n 2 X, so the first part of the proposition is proved.
The rest of the proof is similar to that of Theorem so we just give a sketch of the proof. Let F H,, be network and let Wi be the weight matrix of the first layer of F. If d < then W1 is not of full row rank, so there exists a U E Rn such that F(x) = F(x + kv) for any x E I and E R. We take memorization of D with budget μr. then must hold [F(z1) < 0.5 and [F(11 + kk) - < 0.5, because Bo (Mi, (4) B (x1, (x1,2 + A) (I1, A), which is in contradiction to F(m) = F(m + kv). So F
I1 and kv E (0, 2p + A) (0, A), 5o F(z1)
F(z1 + kv). If F is robust
is not a robustness memorization of F with budget μ. The proposition is proved.
B.4 PROOF OF (2) OF PROPOSITION 4.6
Proof. Let us first consider n = 1. Let D be {(x; ,)) where x; = i R² and y1 = 1, 3/2 = 3, y/3 = 5;
y/ 2 i 1 and i are even; otherwise y; 4. Let μ = 0.4. It is easy to see that XD 1 > 2μ. Let
F(x) = (U1 + B1) + by be a network with depth 2 and width w, where U1 = (u1...., uw."" E RR nx1
B, (bI, bm)) E R R U2 E R B₂ E R.
lxw
It suffices to show that if F is a robust memorization of D with radius 14, then w > N.
We will show that, for any {4,6, 14..,..., N 1) there exist i E [w] and i j so that u, + b, 0 and u. + by = 0 have solutions in (ks k + 1). Also note that for different k. the corresponding i,j must be different. Thus w 2 2(N 4) N. which is what we want. The proof of such conclusion is given below.
27

---

Published as a conference paper ICLR 2024
We prove only the case k == 4, and other cases can be proved similarly. We know that F(5+ E (3.5,
and +(4+c) E (1.5, 2.5) when E [-0.4, 0.4), because F is a robust memorization of D. Thus, we have
so there exists interval A C (4.4,4.6) such that the slope of F in A is least 5. We consider four cases.
F(4.6) F(4.4) 2 3.5
4.6 4,4
4.6-4.4
(cl); The intervals (4, 4.4) and (4.6, 5) are linear regions of F.
Since | ((4)- < 2.5-115 2.5, the absolute value of the slope of F in (4,4.4) is at most 2.5. Similarly, the absolute value of the slope of F in (4.6,5) 5) is at most 2.5.
Note that A= (4, C (4.4, 4.6) and that the slope of F in in the same linear region, A and (4, 4.4) are not in the same linear region, which means that there exists an i E [w]] such that the active states of (u,a + b.) are different in A and (4, 4.4). In other words, u,T + by = 0 has solution in (4.4, a:). Similarly, there is a j E [w] such that uy bj 0 has solution in (a,, 4.6). This is what we want.
at least 5. Since F has the same slope
(c2): The interval (4, 4.4) is linear region of F and the interval (4.6, 5) is not linear region of F. Because (4.6, 5) is not linear region of F, there must be a j E [w] that makes uyz + by = 0 have a solution in (4.6, 5). As proved in case cl, there exists such that u,2 + by has solution in (4.4,a.) This is what we want.
(c3): The interval (4.6, is linear region of F and the interval (4, 4.44 is not linear region of F. This case can be proved similar to case (c2).
(c4): Both the intervals 54 and (4, 4.4) not linear regions of F. This be proved similar case (c2).
For 1, we just need to take x; (i,0, ..... 0) E RR, and the proof is the same.
B.5 PROOF OF THEOREM 4.8
Proef. It suffices to show that for any < 0.5Ap, there exists network with depth 2/ + 1, width 3n + 1, and (NN) non-zero parameters, which can robustly memorize with robust budget Jr.
Let D = [xx ) R" x [L]. Let C E R., satisfy C' will be defined in three steps for an input x E R".
|x. 1 + μ 0 for all E [N] and j [n]. F
Step 1. The first layer has width 3n + 1 and is used to check whether E [BI1, pA). Specifically, B. (21,14 14) if and only if Fi (x) 0 for all [2m]. The second layer has width n + 2 and computes (x) in Property 2 given below. The two layers are given below.
(1-1.1) (x)) 0:
(1-1.2) (z) = o (2 - -0) - Fr Fx) = (xx() x(6) - -M), where j E [n];
(1-1.3) (2) = =((()) + +O), where j E [n]:
(1-2.1) (x))) 0:
(1-22) (x) (
v1 2n F (r)):
(1-23) P/ (x) ofFnnts (x)),, where j E [n].
28

---

Published as a conference paper ICLR 2024
Step 2. For i -.,,..., the (2i 11 layer has width 3n + and is used to check whether ( p)) Specifically, x E (x, (4) if and only if 1 = for all j E [2n]. The 2i-th layer has width n + 2 and is used calculate (z) in Property given below.
(i-1.1) (-1.1) (x) o 2
(i-1.2) F2 o + 0) - F - pu) and (x - ( - (x! +C) - 1).
where j E [n]:
(i-1.3) 2nt (x) = o o (z)), where j E [n];
(i-2.1) (x) = o - (x));
(i-2.2) (x) (リ λp 2p -
2 F2 21-1 (x) -
(i-2.3) F (x) = o 1 (I)),, where E [m].
Step 3. The output layer is F(x) = F2N (z) + F2l (z)
Next, we will show that JF has the following properties.
Property 1. Far (x) وهبر + +C for E [N]. e [n], and x E ( (t), that is, Fints( (x) for j E [n] are used to maintain the value r(0),
From (1-1.3) and (1-2.3), since C + x2 (5) > / 0 for all i E [N] and j E [n]. we have Fi+t(())
Finti (x) ox + C) xd + C. From (i-2.3) and (i-1.3), we have Fat (x) = o oF
of (F))2()) = ..... -...= [F
+l (x)) = x()) + C, for all i E [M] j E [n]. Property is proved.
Property 2.
Let Fx(1:) yi xp-24 2h J for i [N]. Then Fx(x) y: for x E Bo u), and
E,(x) < ys for x & (I;. po).
Due to Property 1, for j E [n]. step (i-1.2) becomes
(a) (z) ( ((x (1) +C) -C)- - m) = =2 x16) - 4)
F ( ( (xl +C- n) (x x111 p).
Then x E Box (1z, n) if only if l (1z
())
- -ا(ي) -1) = [x((6 -x(-0
1,,50~ -1) = 0, equivalently F3j 2 (1) =0
for j E [2m]. Thus, Ex(x) = Ys for x E (oo 11). If x & B 11), then || - σ pa| l0 0 or
|| x, /l/xx > O, which means that (x) > 0 for at least one j E [2n]. Since F/ (x) 2 0 for all i and j. we have Fx(x)) < Vi-
Property If Bo (1ke p)) for yk # Ui. then (x) S 0.
Since x E (oo ()) and yk F yr. we have || - 111100 00 2 2p-2p 2p > 0or |x=Ix--lle 2 >x Ap-2pp 2p > 0.
because the separation bound is Ap. Then F (z) > AD 2/ for at least one j E [2m] and thus
E,(z) S y/ - Ap-
21 Fr (I) S 3/4
#1 2p (AD 24) = O.
Property 4. F(x) = max Ex)), 0} for x E Rd.
Since max(x, [r, y} o I) for x, R and F (x) for all and j. we have that
29

---

The upper bound given in the proof of Theorem 4.8 is for PR P.,N.L- Proposition 4. implies that PR N,N.L and Published as conference paper ICLR 2024
+
+
- + +o -R)
(c),
max F 2x)) E.(r))
Using the above equation repeatedly, we have F(x) o oF (z) + F2N (2)) (P(0), max 1 (z)
We now show that F satisfies the conditions of the theorem. Let x E B (T (1) be E [N]. By Property 2, (x)) Ysi and if and y, V/s then (x) < Vs- By Property 3, if y: F Ys- then (x S By Property 4, Fxx) max Ex 0} E, (x) = ys: that is, F is robust at J, with budget
The network F has width 3n and depth 2N. We now estimate the number of non-zero parameters. For i E [ constructions (i-1.1) and (i-2.1) need 3 parameters; (i-1.2) needs 8n parameters; (i-1.3) and (i-2.3) need 2n parameters; (i-2.2) need 2n 2 parameters. In total, (N 1)(12n 5) parameters needed. Finally, F can clearly be constructed in polynomial time.
B.6 MORE ON THE NUMBER OF PARAMETERS AND PROOF OF PROPOSITION 4.10
this subsection, we give more detailed explanation on Remark 4.9
Definition B.2. Let PG N.N.L be the minimum K such that the hypothesis space {F : R
R: (F) = K} is an optimal robust memorization for any dataset in D,,L,N- PR,, can be defined similarly for the following strict optimal robust memorization networks that satisfy F(x) for all I E Box (rt, (1) and E [N].
PL,N, are essentially the same, as shown by the following proposition and Corollary B.4 Proposition B.3. We have that 0 S
PR N.,NLL
PG N.N.L S 6I.
Proef. It is easy to see that PR it is also a robust memorization for the same dataset and the same μ.. This proves the left side inequality in Proposition B.3 The right side follows from Proposition 4.10 whose proof is given below.
RR.NL... 2 PGG Ln,N.L.J because if network is strict robust memorization, then
By Theorem 4.8 and et al. dataset, Proposition
2022), J. we have that O(vNn) S PR P. S O(Nn). Since < Nn for most
B33 implies
Corollary B.4. P
M.N.L ~ PC
n.N.L O(Nm). i & Nn.
We now prove Proposition 4.10
Proof. Since is a robust memorization D with budget μ., it holds that F(x) E (y) - 0.5, y: + 0.5) for all E (2, μ) and i [N]. Since BB (Zt, μ) is a closed set, there exists an > such that F(x) E [y: 0.5 + + + 0.5 - t) for all x E B (z; E [N], and a small E Ryn-
We claim that there exists network G with depth(g)
and width(g) 2L, such that g + v) = k for any E [N] and u E [-0.5 + 0.5 - c]. As a consequence, we have ((r(F())) = ((F(x)) = y: for all
E Bo (Ze, (1) and E [N], and the proposition follows.
30

---

Published as conference paper ICLR 2024
G is given below
((x)
1
Σ
(0 0.5 i+)) a(x 0.5 e)) +1.
2e
t=1
It is easy to see that:
(cl) ox - 0.5 - i e) [(z 0.5 - - when r 20.+i-
(c2) (z - 0.5 - + o(z 0.5 1-5---66 2e when æ 2 0.5 + - i
So for k E [L]] and xi E - 0.5 +,, 0.5 o]. we have
(d1) (20 - 0.5 i + c) < - 0.5 - - c) when h: i;
(d2) (20 - 0.5 - c) (20 0.5 c) 2c when h 2 1
and thus
(
(o - 0.5 -5
1
+1
2. ==
1 Σ
=1 (0 - 0.5 - i o(2. 0.5 <)) +1
2c
1
EE= (2c) +1
2c
k +-1+1=1 k.
Thus, G(k + v) = k for any & E [N] and v E |-0.5 + e, 0.5 - c). The claim and hence the proposition is proved.
B.7 OPTIMAL ROBUST MEMORIZATION FOR POSITIVE NORM
In this section, compute the optimal robust memorization networks for the Lp norm with p 2 1, that is, we extend Theorem 4.8 from oo-norm to Lp norm.
For any p > 1, p > O, and E R", let (2, p) = {I E R" || ø|pp = EE lz - -,,"" s 1). The robust accuracy of network J D with respect given robust budget μ R.
RA 11) = P (( E (B, (F(() - < 0.5).
The p-separation bound for dataset D is defined be
X min [|| - z, (zt, vi), (r), Uy) D and * y,}.
The problem of p-robust memorization for a given dataset D DR with budget y is construct network F IR" + R satisfying RA*(F, μ4) = 1. A network hypothesis space H is said to be an p-optimal robust memorization for dataset D, if for any μ 22. there exists an F H such that (F. Then, we have:
Theorem B.5, For any dataset E DA,L,N, the hypothesis space HO.. a 1-optimal robust memorization for D.
Proof Sketch. The proof is similar to that of Theorem 4.8
Step 1: For any i [N], calculate (x(3)) r((ii for all [n]] at first and then calculate (x()) 21!²) for all
j E [n]. Let z be given robustness radius and < X//2.
Step 2: Calculate Σj (x(t) 2152 (2b/2 + m2/2.
31

---

Published as a conference paper ICLR 2024
Step 3: Use ma) 3xb-60 6f Lo (o 100 -
(2//2 +
n2/2]} as the label of z.
Let B1 (F 1.) Since μ N2/2,, we have Yo 31 6p 1
Lo [o (z()) - -2001 (2b/2+ p)/2) z
Yw bxp-6u 6u Lo (2 + 22/2) Yw-
For all yj * yw, there must be || - =zy11 2 || - T1el11
|| - x|11 2 1/2 14, so
4
Lo (o j= (z60 - = - (A//2 + 22/2)
V/-
3A 6p
< 4//
Lo - p
3x5-
= V/
3x
by
433///44-
133///4 3//2)
3x 6y
= f/
I 0
We thus have you Yu
1 Lo ( f=1 (z00) -1001 - (Nb/2 + 1)/2) S maxic(N] 13/
3 6p
325 -1 To(E) (266) - (5)
/2//2 2 + 11) /)) = max,e (v:- 321 Lo E) j= (z(60) x1-
(ab/2+1)/2) S M fue} Yuu which means max 3xb-6p 6p (bb/2 p)/2)} - you The theorem proved.
Lo
وー= (x:(1) -1,0011
Theorem B.6. For any dataset D E Dn.L.N satisfies D C I-A, A XL/2 7 > 0, there is a network with width O(n), depth O ((Np(log(#) + plog A + log p)), and O O(Nnp(log(n//) + p plog A + logp)) parameters, which a p-robust memorization for 'D with radius X5/2- 7
where A 2 1, 1. p N and
The proof of this theorem needs the following lemma.
Lemma B.7 (Proposition 3.5 of Elbrächter et al. 2021 ). For all p E N+ A 1, and < 0.5, there is a network G IR- - IR with width 9 and depth O(pl log (1/e) plog( A) + log(p))) such that (g(x) x² S 6
for all x E []
Proof Sketch The proof is similar to that of Theorem 4.8
Step 1: For any i [N]. calculate (z:(0) - [(1 for all j E [n]] at first and then calculate (((x())>(( -,,"1 for allj E [n], where (ax) is obtained from Lemma B.7 and satisfies (z) - x01 S for all x E 10A, 104]
and = (X /2 /3 (Xp.2->)) Since (25/2-7/3)) (AA5/2-2) (2/3<)) by Lemma B.7 G has depth
O(p(log( + + plog( () + log(p))).
Step 2: Calculate Σド (((x0)) - -x." (XB/2-7/33- We will show that if | x: 11 S 12/22 7 then ΣØ= ((xx(() - x. (/1) 1) -///2 <0; if |ar 10-20
x.. 1p 2 X2/2 + y. then Σ/= 01 =001
(Ag/2 2 7/3)p 2 2( 37 P. Thus, Step 2 follows from (2.1) and (2.2) to be proved in the following.
(2.1): Assume ||0| x; 12:1z S X2//2 7. Since Σ 0( .æ,) ne S ||x xz lp. we have that
-1(0))=)((0)1- -1,0)) 2 < - (X5/22233333 S (25/2-2)) 7) ne -1100-18////0 2006/227331 7/3) = O.
32

---

Published as conference paper ICLR 2024
(2.2): Assume - - 2 12/2+ + Since E G[1x z,() + ne 2 | 2; 1.. we have
Ej=1 0(1z01)) - 11 ( -
|/2 - zilß - ne - (1//2 --3/1
(Ap/2 + 7)p me -N 7/3)p
+//2+>>"* + (Ap/2 - -1p- - -
N 2(12/2)
N 2
Step Use max (y (37)² Lo 1 - - -X (28/2-7/3))) the label of
Let E B2 Nb/2 By (2.1), we have you (3 (>
(1) (X, -1-
yoi
and for all f/ # ywu there must be || 23 2 || knol lp 11000 x11p 2 22/2+ 7, s0 by (2.2), we
have y, (3y) Lo()) -((x(0) 2/ (00 - (2p/2 7/3)²) 0.
Therefore, yu Yu (37) Lo ((1(0) D (2//2 - 7/3})) < maxie
{v: (37) La (E== g((x0) Yw. which means max {8) (3y) ( [oj= -((x(1) 21 (0) - -W2//2 7/3)²) Bwu and the theorem is proved.
(37) (((26)) 11 (Nb/2 7/3)9) max
1 (ND/2 /2 7/3)p)} S [N, {3
Remark B.8. When p= 2 and 7= AAp/4. our bound for the number of parameters in Theorem B.6 becomes
O(Nn log(n/AD) The result in ei al. 2022) is O(Nn log(n/ (p))) + Nooly log( (g/Ap)) Our result better.
C PROOFS FOR SECTION 5
C.I LEMMA
The following lemma given in Li et al. (2022), but without explicit information width and depth, we give an explicit construction.
Lemma C.1. There exists a network F E Hm.22opp..(m).005 such that F(x) = || that is, there exists a network F R with depth log n, width O(n), and (n)) non-zero parameters such that F(z) ||
Proof. Let [og, n1]. Without loss generality, we assume that n 2 Then F has depth 2e and for i [e+1], the (2i 1) layer has width 2--1+2 and the 2i-th layer has width 2--i+1.
Denote W; and b, as the weight matrix and the bias of the i-th layer of F. The first and second layers will change x to (z). The first layer has width 2 and the second layer has width 2 which are defined below.
2 1 and 22i+ -1; 1; other entries of W1 are O. by 0.
Wr.2i and W 1; other entries of W2 are 0. by 0.
Since (z) + a (-x)) = |a|| for any x E R, is easy to check that F2(x) = ((W2o(W1x)) = |z]
For i [c], the (2i + 1)-th and the (2i + 2)-th layers are defined below.
33

---

Published as conference paper ICLR 2024
Fi F2 (z) (F (z)), where m 0, h...., 20 1.
22t1 (x) = of (x) 21 (z))), where m 0, 0,1,...,2 28-1 1. 12)((2) = o (x) + mm (o)), where m = 0,1,..., - 1.
For [e + 1], using o - y) + = max y for any x, E R, we have that
F2)
of (2) + F (x))
2i+1
F (2) 2i+1 (x)
(F + o o (2) FF
F + 0 ( (x) - F (x))
max F (z), 24 Fam+ (x)}.
The (2e + 2)-th layer has width 1 and is the output
F(x)
(x)
max (x)
max F (z), (Z) 1 2x))
max F2 (,),,
||ا||
We now estimate the number of parameters. The first two layers need 4d non-zero parameters. For E [e]. the (2i + 1) layer and the (2i + 2)-th layer need 5 2 parameters. Therefore, we need > 5 2 ((2") (n)) parameters. Then the lemma is proved.
C.2 PROOF OF THEOREM 5.2
Proof. Let 'D be defined in equation 3 and C E R4 satisfy C x. 0.5Ap for all i E [N], k [n].
The network has N(2 Iog(n) 5) hidden layers which will be defined below.
Step 1. The first layer has width + 1: Fz)))
and F((x) = a(x(1) + C) z(i) - C. where j E [n].
Step 2. For A E [N], let s; (2 [n]]] + 5) 1) + and will use the sy-th layer to the
(sk + 2[]lo(()] + 4)-th layer to check if | xx|lox < 0.5Ap. Step 2 consists of three sub-steps.
Step 2a. We use the sx-th layer and the (sx 1)-th layer calculate zzl. The sæ-th -th layer has width
3n + and is defined below.
Fl. (I) o (FF
(x) (FF.
- -
xx
()) - C), where j E [n]:
(x) = or ( - (I) + x + O), where j E [n]: (x))
(j)
SN fz)+i(x) - where j e [n].
The (sk 1) layer has width 2n 1 and is defined below.
34

---

Published as conference paper ICLR 2024
Fa 11)+(()) oFF (x)):
+1)+ -
oF (x) + (x))())), where j E [n]:
(x) (() oF (z)), where j E [n).
The st-th layer needs 5n non-zeros parameters and (sk: 1)-th layer needs 3n + non-zeros parameters.
Step 2b. Lemma C.1 is used to calculate || 2x lao- According to Lemma C.1 there exists a network
H. : R - R with [n) hidden layers, width O(n), and O(n) non-zero parameters to compute H(z) |>>||0 for x E IR". Since H has 2 2[log(n)] hidden layers, we set the output of the (#), + 2[log(n)] + 1
layer to be
(x));;
Sx +2 =
Fl * *2 (2) H(F! + (I)) -...)........................... Fb +++1(())) sn - (2)
zd+1 +1+2|log(m]++1 (z) = o (F (I)), where E [n].
to the (s (log(()) +4)-th layers to check if ||r-| xxllo < 0.5AD. The (sk + 2[log(n) th layer has width n + and is defined below.
Step 2c. Use the (sk (2o+2
F0
4x +2 o (F
*x (llo
84 +2 = ol Ao 2 +2 (x) + 1);
Fl
F2 44 +x+2|log(0)] o (F*) *x +x 2l 2):
F3 2 = o o 2 (z) + 2);
xd+3 +1+2[log(m]]+ = a ( +1 (z)), where j E [n].
The (sk 2[log [n] th layer has width and is defined below.
F +x+2[lo(())+3 (x) = o (+) + + M.FF (222 (x));
Fl (1+ = a (F) cか +2 (llg(()))11)
F2 +1 = o (F)
s4 + 1log(1 (F2 (2 + F3 +2++
Fi+2 +x+2[1oz(x)1+3 + 1a (x)), where j E [n].
(Fi+3
The (*x + [1) + th layer has width n + and is defined as
F0 4x
(F)
ax *x + (FF " +2[lo((m)]++a - F2 ax *x+2[lom(m]] +2] +x()))
F +x = a (F
+1[log((]]+++ where j [n].
+ 2[[lo(())]]+++++
It is easy check that if F) su+1 (z) (zاا) .r _,(,7]1 Then
2
Fl sy +2
Fi
(2 +
AD
if and only if || 2xlls 0.5Ap. These three layers need + 16 non-zeros parameters.
Step 3. The output is F(x) = F + (x)) 2. The network F has width O(n), depth O(N log(n)),
and log(n)) non-zeros parameters.
35

---

Published as a conference paper ICLR 2024
We now show that F satisfies the condition of the theorem; that is, F memorizes D and satisfies Lip (F) Ap The proof will be given by proving four properties.
Property 1. F2 (2)) = x00 + C' for j E [n] and & [M]. When A: 1, 34 1 = 1. By Step 1, we have F (2) = (x) = =x00 + C. When 1, we have
F 1x)) = s0 = o (F
a1 (x))
= =F 2, = o (Fiit [x (x))
=F (I)) oFFa (I)) o (x)) F (x).
Then, Fi sk+1 11 = F (1)) = ... =F (z) = F (x) = x(1) + +C.
Property 2. F (z)) = =1x000 - xx and F1 (log()) +1 (x) = |||r - lx for j E [n].
Since (x) + (-x)) = |x|| for any E R. from Step 2a, F1 x (x) = -1x) I
( CI for j E [x].
By Property 1, F (z) = z00) + C for j [n]. Then, F (1)) = |z(() - =11) for j E [n]. From Step
2b, we have that F
*c +2 (log)(m)) +1 (x) | xx for j E [m].
Property 3. F
sc+T[log(m]1+ (x) = 2 + you o01 2 | Twa )l,)), where wy = argmin (e || - x looo
We prove the property by induction on k. We first show that the statement valid for k = 1. We have that
4% 1 and F +==+ F0 20 (x) Fo +1 Fa, (x) = Fo (2) = 2. From Step
2c and Property
F Fo (1
= aF +2 (x) +1 a1 210g((()))2))
= a(2 + 11 - 2 Fl
Ar +1 [zxx0)
= 2 ++ylo(
An 2 11 (x) 1)
= 2 2+11o(1 Xn | 2o 2011,0)
Since F2
22 = o(F
sy 21 (x) - 2) = =0 - 2) = 0 and F3 2
a( a- -= (2) + 2) al2 - 2) we have F² F2 (x) oF +12
(F2
+122 21 (x))) = = #1 1og(m)) = F1 +1 Then
Fo s1+2[log(n)) -1 (x)
(FF s1+2[log(n)] - y1 (1(F)) #1+2 (og(n))+33 - #1 [og(n) [og(m)+)(())
= F +1+2(log(m))-9((1
= 2 + (1
Am |z zo oc).
We have proved the statement for k: = 1. Assume that the statement is valid for k- 1; that is, F s2 (og(n) ( (1) = 2 yon 1 a01 2 |
Twe- lloo). We have F +2+2[log(m]]+2 = F st +2 (z) F0
(x)) = =F = F F2) = 2 +
Yuu O01 2 xx Twn (loo) 2 1, and we also have Fl sv 22 = =o(- 2 Fl
A + (z) +
36

---

Published as conference paper ICLR 2024
1) E Then
F (1
o oF su 22 + F1 +2[[)og())]+2222)
of 11+7
(x) yn Xo F1 +122log(0011111111
(17)
F +4+22logg()1+221 (z) yu Ap Fl F (1
(x) vko da Fl +2+1 (z)) Fl
F (x) a +2
Since F2
a +2 2) and
F3 (lgg)
a- +2(bg(())] (x) + 2), we have
F² 133
o 3u +x +2
(F2 2loo F33 [ +2[
(F
2 -
Then
F 12
(F sy +2[log(n)]++3331 yk (F)
s +2 F2 +2log((())) +3())))))))))
oF - yk F 4
-yk (0 oFF) +222 - F (x) -())))
We divide the proof into two cases.
Case 1. If x: & B ( 0.5Ap), then wx wi-1 and F1
ex [Do(())) +2(()) a0- Fl
[1
1) = o(1 - Ap || xxlloo) = 0 and
F Fo 11
*
(FF (F) + yk Fl 2222
(F 2 +22[0g(n)]++21) oFF +22 - - - -1(2) 2))))
(
(x))
F
S4 [4-1+t[log(m)]+a42
2 Veu (01 An | Fwee I1loo)
2 o( to
1|15 Img |1o))-
Case 2. If x E B. (mk. 0.5Ap), then 2 Tog (1) (+) = o0-22_
No +2 (
(x)) = o(1
Am || oxlloo) 2 0 and using equation 17
37

---

Published as conference paper ICLR 2024
F 11
ofF (z) + yk F1 sx+2
(x s4 4, [2[+
o o [F)
+21] - 2()))
- + 41 Fl
2 +1+2
(miimin # + 11 /2 -
o22 + Muu=1 o 2/ ||
I blo))) + yk - An x - xx|loo)
-yn(min Xp
2 || 0l 2 || Iwe-, 11)
Consider two sub-cases:
Case 2.1. If a
I -w
loc > 0.5Ap, then we k and hence
Fb sq [)o((n)) +1(
o22 + you 1((1
2 | Iny allo) + ya 2 - sxlloo)
(min 211 2사 2x o(1 2/ x Iwe bllx))))
(2 + y - An | - =x
= 2+ yk (1
2 [| - -xxll00
An
= 2+ + you (1
2 |x Jmy 11x0)
Ap
Case 2.2. If ||
T - loc S 0.5AD, then Mhue-1 U/ and hence
F
#k +2gggg))()) (2)
(2 + Yuu- [(1 Ap
2
1111
Twn- ol00) + yk(11 An || zxlloo)
ys (min {1 Xn
2.
||
2 Iwe-, |loe)))
Twr o1 ) X
(2 + Mur-1 (1
mn((1 2/ Al ||ar I& loo))
(min 2011
2
No || Fw 1 bloo)))
2 + y max
2
xxxloo,
|| Imn }
No
2 + ywe (11 A- Twx 11
The property is proved.
Property 4. F is memorization D and has Lip (F)
2
Xx
By Property 3, the output is
F(x) F1 +2 (ly+2oog(m)) 2 =y (1 - =11 I xww)
AD
where wN argmin xiile 11o0
If Ta. then wN s and F(x) yai that is, F memorizes D. If E B(I,, 0.5Ap) for some s E [N]. then wx E [N] and F(x) Yww (1 Ap || - Zw bloo) such that the local Lip (F) Ap over B W 0.5Ap). ). If is not in B(x, 0.5AD). then ||x Iwx Ibx 0.5Ap. Therefore, F(x) 0 and the local Lip (F) 0. It is clear that the global Liptchitz constant is 2,, and the theorem is proved. D
38

---

Published as conference paper ICLR 2024
C.3 PROOF PROPOSITION 5.4
We first define T E BR,N, which is binary classification data.
T = {(zi, M1) )T= C IR" {-1,1}
(18)
where zo = 0, yo = 1, 2, = 1; and yi -1 for i E [n)]. It is easy to see that 'y = 1.
We first prove lemma.
Lemma C.2. If network memorizing T and (J) then F(x) 1 -1 1-2/|aolloo for D
{a R" x0) 0.5, vi
[n]].
Proof. For x E D, let k argmax {= that is, || = (()) Let
where = 1 is
defined in equation 18 Since I = 1x. we have 2(0) = x(1) < 0.5 when i * and (k)) x(k) > 0.5; that is, || (k). Since Lip (F) = 2, we have
F(xo)= - F(xx)
(F(zo) - F(x)) + (F(x)) - F(ax))
S 2|/20- - x1l00 + 2| - 21
(19)
(k) + +2| - =01000
= (h) + +2(1 - (k())
=
Since memorizes T, we have F(ro) - F(xx) which means that the inequality in equation 19 becomes
an equation. Then F(xo) -(x))= 2x ()); that F(x) F(xo)) (k(k) 1 2/|xr|loo-
We now prove Proposition 5.4 Note that \y = 1, which is omitted the proof.
Proof. It suffices to show that if F E H is a memorization of T defined in equation 18 then Lip (F) > 2; that is, H is an optimal robust memorization for T via Lipschitz.
Since memorizes T, we have (F) 2 2. Let F(x) Ei b:) - Qx b have the normal form equation 4
Assume the contrary: Lip (F) = By Lemma C.2 we know that F(x) 1 -122|/// over D {2 R=: < (0) 0.5, E [m]]-
A point t RR called T-point, there exist j E [n] and an c R4 such that c {(K) 0.5 for any
I E [n]] and [+0i] [ > 0 when i # j.
For s E [k], let H, be the hyperplane defined by U.r + b, = 0.
Then one of the following properties must be valid:
(pl) H2 does not intersect D.
(p2) H2 intersects D and there exists T-point / D such that U.l. + b, 0.
(p3) H, intersects D and there does not exist a T-point & E D such that U, + b, = 0.
We first prove the following properties.
39

---

Published as a conference paper at ICLR 2024
(cI) Property (pl) is not valid for some s E [kt].
If (pl) is valid for all E [k], then D is inside linear region of F. This is impossible because, according to Lemma C.2 F(z) = 1 2/1 over D, and || -lso is not linear over D.
(c2) Property (p2) is not valid for any s = [k].
Suppose (p2) is valid for s. Let E D be a T-point satisfying U,t + 6, = 0 and e < ((k) < 0.5 - for all
k E [m]. Let j = argmax:e(mn
|161 - |662| > e > 0 when j' * j. By Lemma A.3 there exist two
linear regions R1 and R2 whose boundary is (U,, b,) and points P E R1, Q E R2 such that P- t||x < c/3 and ||Q - floo= < </33. Then we have
(c2.1) 0.5 2 > p(t) > 2e/3 and 0.5 22/3 > ((k) 2e/3 for any E [n]. which implies P.Q E D.
(c2.2) j = argmax ( = argmax (1(00 }. |plO|| - | 1 > e/3 > 0, |Q - |Q0
f/3 > 0 when j' //+1 j.
By Lemma C.2 and (c2.1), we have F(t)= = 11 21|0010c = 1 - 2x over B (P.e/T) n R1 because for any x E (P, by (c2.2), we have x(5) - x(1') > (P() - e/7) - (p55) + f/7) > (1/3 2/7) > 0 when j' j.
Since F(r) is a linear function on RG, we have F(x) = - (x) on Ri, and the same is true for Rg. Thus, the normal vectors of F are the same for R, and Rg. On the other hand, since Rí and R2 have boundary
(U,, b.) and U. + 0, the normal vectors of F over R₁ and Rg are not the same, a contradiction.
(c3) Property (p3) is not valid for any s E [k].
If (p3) is valid, then find point & E D n H, and let e = 0.5 - ||d|oo. Since & is not a T-point, there exist a, b E [n)] such that ((a) = (1b) = 1|4| = 0.5 - 6. (If a, b do not exist, we just need to take é' min,g[]] kzargmax sejn (1652 (0.5- 14 | 1111 1olloo110 - D. Then is T-poiint for j = argmax je(n) (1/l)
and e
We will find a T-point ( near such that & E D and U,h + b. 0. which means that (p3) is not correct. Three cases are considered.
(c3.1) 0 0 for k E [n]. In this case, let t + (0.5 - e/2)1 1x) We have Usli + b. U, + (0.5 - c/2)1x - -(0) + by U.t + b. = and is easy to see that ((0) = 0.5 c/2 > (()) = (10)
when c + k. so 4 is T-point.
(c3.2) U.!h + 0 for all & E [n] and Sgn(U!")) = Sgn(U. (!))) let | > (1!') In this case, let tı
U(e)
U(a)
U(a)
1 t+1/21
प: / 1/21. Then U,4 + b. U,(t e/21, U (/1,) + b, U. U.(e/21,
U e/21p) = O. We also have 0.5 > ((0) ((0) +e/2= (0) +e/2> > (10) > 110)
Ul*)//2 6/2- _U!
1/2
U(a)
U(aa)
UtoTe/ e/2
( because Sgn (U!0)) = Sgn( and c(a) {(a) e/2 > {(a) 2 (1) = (k)) when k # a, Thus, t
is a T-point.
(c3.3) Uh() * 0 for all k E [n] and (g + Sgn(U! Let U( > 0 > بن: and # a, b, such that
(1()) u > 0. Let + (e/21, e/2 ا 1.) where 17 (0, 1) and make ne/ U
t.. Then U,t1 +b,
U,(t + 7 - 1| - प,,
21.) + b, U,(ne/2 21, ne/2
((())
1e) nnU e/2 nU!
(c) c/2 c/2 o.
U(w)
0. We
U. V(o)
also have 0.5 > ((0) = (0)) + ne/2 2 ((r) + ne/2 > ((() 1
e/2 = (0) because Un() U!!) > 0. and
40

---

Published as conference paper ICLR 2024
( ((() + n//22 > f(a) (( e(x) when l & a, Thus, & T-point. If U we only need let 1 = t n(c/21, c/21.) and the proof the same.
U
By (cl), (pl) is not valid for some i. By (c2) and (c3), (p2) and (p3) are not valid for all i. Thus, reach a contradiction, because for any E [k]. one of (p1). (p2), (p3) must be valid. Therefore, the assumption Lip (F) 2 is wrong. The lemma is proved.
C.4 PROOF PROPOSITION 5.5
Let T be the dataset defined in equation 18 We first give a technical lemma, whose proof is given in Appendix C,4.2
Lemma C.3. Let C E N and e E RR satisfy e1/3 min 120 100m2: 2c) and k s C; and let F(x)
Σk (U +b,)+ Qx + be a network with normal equation 4 which memorizes and Lip (F) S
2 t. Then, for any i,j E [n] and # j. there exists E [k] such that
0.5 + //
U!!
5.5- and
|U!0
1/c 1 2c3 for *
(20)
0.5 1/3
|
0.5
max (IU..) 1U.',,1,''
and the linear equation Ugr + b. 0 has a solution in the (0, 2).
C.4.1 PROOF OF PROPOSITION 5.5
Proof. Let V = (1,2,... n) E RR, M [ n and T be defined in equation 18
We define as:
D To UTI U Ta TM,
where To = ((-V.1), (-2V.1)
(- - (n + V) 1)} and T. = T + 16knV = {(x, y) :
F - 16nkV, y = 9. (2, T for k E [M]. We see that XD and is omitted from the rest of the proof.
We prove Proposition 5.5 (1); that is,
(1) For any μ < 0.5, there exists a network with depth and width 4nM, which is robust memorization of D.
For e < 0.5, define a network G. IR + R:
Ge(z) (( 0.5 e) (z - 0.5
co -
1.5 e) o(x 1.5 E)).
It is easy see that G. has depth width 4, and satisfies
(cl) (x) = 0 if æ < 0.5 e and x 2 1.5
(c2) (I) 2e if 0.5 < x < 1.5 e.
For i [n]. define (x) Ra IR. (x( (x(()()) and define g R" - IR as
2
g(x)
2p
where (0,0. Then G is the network with depth and width 4n. Using (cl) and (c2), we know that G is a robust memorization of T with budget μ.. Let network F: R + be defined as:
M
2
F(x)
G6.- 16njV)) + +.
2p
41

---

Published as conference paper ICLR 2024
Obviously, F has depth 2 and width 4nM For any k E [M] and E Bo (Th: R), since Tx = T + 16knV, there exists an ğ E 30 (T (1) that satisfies x = & + 16knV. Therefore,
F(z)
M 1-2u (i==1 اラ=1 90.5-( 16njV) +
1-2μ (Ei=)
EØ=1 M
- 16n(k: j)V +
1122 Ei=1 - by (cl))
((
Since G is a robust memorization of T with budget μs, F is a robust memorization of Tx E [M]) with budget μ. Now we show that F is robust memorization of To with budget μ. It is easy to see that F(i) = for any I E s0 (To, jo), because all the entries of & are negative, so G (x 16njV) are always for any i [n] and j E [M.] Thus, F is a robust memorization of 'D with budget j and Proposition 5.5 11 is proved.
We now prove Proposition 5.5 2); that is
(2) There exists μ 0.5, such that, for any FF with depth 2 and width 4nM, if F is memorization of D, then 2 (F) > 4.
Let μ and 6 satisfy 1/p = 2 + e//3 and 2/3 < min 120 100 8ndd
Assume F = Wo(Ux + b) + b, is network with depth 2 and width 4nM, which is a memorization of D and Lip_ (F) < 1/p. For any l E [M]. Ta = T + 16knV is contained in B (0, 2) + 16knV. So using
Lemma C.3 Tk. for the any (i,j), i.j [n]. there exists E N4 satisfying
1/5
U
1/5- and
12 2 for ii
5.
10
1.34-1e173
max (1 D
(21)
and U, + b. has zeros in B (0, 2) + 16nkv.
We claim that different combinations (k: j), where &s E [M]. < j. and [n]. correspond different 8, which implies that the width of F is at least n-1 n.M > 4nM since we assumed n > 9, which leads to a contradiction and a proof for Proposition 2)5
We prove the claim below. Let (k, i, and (A1, (1, correspond to the same 8. Firstly, we show that = i and j j1. From e// 1 we can deduce 0.5-5e475 1/8
2/3 and 1/.
1/3. Without loss of generality,
1.5+1e77
1-2c3
assume | | Then, from equation 21 have 10
2/3 and [
1// for q + i,.j. As consequence, for different pairs (i.j), i.j [m]. the corresponding must be different, so = i and j1-
1
We now show lo = k1. If * k1, let k < kj. By equation 21 we have 0 = U2(x + 16nkV) + +b, U,(ū+ + 16nk, V) + bg for some x, B. (0, which implies TU,(I =) 116n V), Firstly, we have
IU.( - 5)1
||U||i|[(= - 1000
4||U,||1
4(I0%" (000(++[1++00111 1/3
(d- max ( (,0 [T) (3) by equation 21 0/5 1/3
<
1-2e
410!5) ((1+ 0.5+
+ 0.5 0.5-5c1/3 1-2 (d 2))
0.5-5c1/3
410!00
(1+1.77
2)) (use 1/3 1/120)
4nl
42

---

Published as conference paper ICLR 2024
Consider that we have assumed i j. then
16 k1 (U.V)
w
16m|Usul
16m(juu!0
1-
E
i 1)
16m(j]u.0
.0..44e1/3
Σ Spiig P 1-273
12.1/3
| 1.10!
5e13-
16m(jlu!5)
1.0.541e
n²
1-2,173 max max
12c
(1U.
| (})
16m(jiu?7
0.5++4.
|
-n² 12c 0.5+4c1/8
(
0..5
56 173
1-2c178 0.5-5c178
16m 16m
(j 1) 0.544
n² 12r1/3
0.5+4c1/3
b.5-
1-2,173
0.5-
16m ui (n 1) 0.5+4/1/3
n² 12c1/3
0.5++421/3
0.5-5e173
0.5-
www
16m (0n [m (n () + 2/3
22
+ 203) (use e//3 < 1/120)
16m [ 203 (n 1) 29m²2113) use el/3 < 1/120)
16m 16m|U
u [1 49/ 100) (use / < 1/100n²)
1
So, it always holds (x,(x =)) ud Un S 116n(k (U, is not valid, and (k: i. and (A1, (1) cannot correspond to the same s. Thus k k1 The claim and hence the proposition are proved.
ky (n))k))) which means UU, (z: - +)]
Remark C.4. From the proof, we see that replacing H in the Proposition 5.5 by H(C)) = (F R R: (F) 2, wFdth(F) Cw where C. NN satisfies 4n| m41 Cwid (n- N Proposition
5.5 is still valid.
C.4.2 PROOF OF LEMMA C.3
Proof. In the proof, the fact \T 1 is used. First, we introduce several notations.
(I) For a linear region It of F, let F(x) = Em + cover It with Ny = (l,,...,4y as the normal vector.
(2) For t E R4, let (t) be the set of linear regions R of F such that the normal vector NE. = (41....,4.) (n)
satisfies |4| 2 and denote
Pt( {a E E 3R R&(t) such that Rt.
(3) For a, E Rd use + to denote the directed segment from to b. For i [m], the H,-length of b is defined as (a( 1(0).
(4) Assume 0; E RR" i .....,k for le 2 3. Use a - a2 - ag to denote the polyline segment a1 02
ag-1 Ok.
Without loss generality, assume = 1,j = 2. For convenience, let
1
0 E + 2 6g 2 c- c/3 -
We will prove a series of properties which will lead to a proof of the lemma.
(pl). For linear region R of F, NF,R (I,,.., satisfies ET-14 I = +
43

---

Published as a conference paper ICLR 2024
There exist _ and y (Nyn)N E =
, E R2o. such that 2 Lip (F) [((e)=((y) >-
E
(( ) Ex=44 4 (o 9-
1 Di-l: (Sgn(h)) (ig(4g)(()) Σ M4l from which
x- Vll
we have 2i=1 14
S 8. (pl) is proved.
A.2 the interior of linear region is an open set of dimension n, but an edge linear region is of dimension S n - 1, so for almost all Vs the polyline segment B 2g To + OV - 21 is in the interior of linear regions of F, except finite number of points. We assume is chosen to satisfy the above condition.
Let V = (1, U1...., 1==1)² E R", where |oy| < T for E [n [n-
1].
By Lemma
(p2). By definition, (i(e - R4 is set of linear regions of F. By Lemma A.2 linear region is convex polyhedron. Denote the directed line segment xo - Io + OV = 0 + OV by D. Then D; = Dn R3 is also directed line segment, and hence D n (r U - D;- Then it holds
1
Heo A D Pi(eo))
Σ -I-eegghh 0 -
2/3
1/3
(22)
6 6
= F(zn + = 4 ((V)) b(V). where Nr = (4 (tV))...,,lll ((V)) for t E R. Then U(t a piecewise linear function in and ((V) is piecewise constant for each i. When the segment D is in the interior of linear regions except a finite number of points, we can calculate the derivatives of U(); that is, U'(L) VFUV)
For linear region R, if (V (()))
Σ (l(VV)())) + (1V).
V
We thus have
- + +VV = - =(0) = U(0)
U()ddt
=
5o (1((V) + 2i
(23)
S 5n ((V)) + +. l. (by lud I T)
S fo (((())++ + +22 by (pl).
Since Lip (F) < 2 and 0 < 0.5, we have =(x) -2 = (2+c)
Thus by equation 23 we have
+( 8)
(F(z)) -00 - 2.
Since T < 1, we have that
(k1) if 4 (tV) 2 eo. then (tV) + (2 (2+e
(k2) 4 (tV) < <o. then (+V)) + +2 S c0 + (2+ Eo)
Note that the Hi-lentth of D is 0. Since the H,-length of Dn Pi is Hep the H -ength of D (eo) is 0 Hey Then we have
( (2+c) < (() (20
< Et
He, + (cu + +2+ (H,,),
so
(2 H) + (co + 6
Ha,) + (2 + ee - 0) 2 2,
from which deduce He, 2 0 (11-)
44

---

Published as a conference paper ICLR 2024
Since 6o 2 + 6 e\/3 and T 1--- el/3, we have that Heo 2 0 (2+r- (1/3
2/3 1-T 2 0 c//3 = 0 - e/ Property (p2) is proved.
2/3
0
Consider the directed segments D1 : 20 - 20 + +E 0 0E, and D2 : 20 2g
P 7" (1-2c1/3, (222/8,1--2//) and |ea| e
where Ej (1, T", ......... En-2) 2)= Eig EI,,,,
for E [n- 2/. Similar to (p2), Ej and Eg are chosen such that Dj and D2 are in the interior of linear regions of F, except a finite number of points.
Let / (112 0 > 1/3, so ||| |
30, + 3/)) and denote the length of 7 as (T]. From e 1/3 < 120 we have
2///3. Let I; be the set of 7 E such that n is in P:(co) for i 1, By property (p2), the -lenggthh of the segment D1 Pi (ca) is at most 2/3 and the total Hz-length of the segments D2 P2(E0) is at most c\/3; that is, |T/4|| I c!/3, Then [71 n I2 = | ((TTT) U (2)) 2 [ |T/Ta| [2l > that is, 1 1n + G. We thus have
>
(p3). There exists an 7) E I O Iz. such that 9; nE, (c( for = 1,2.
Suppose qi is in the linear region R3 and Ny,; is the normal vector of F over R; for i = 1,2. It is easy to see
that [ 2 co. IN S 2/3 | 2 60. and N S 2/3 So || Nr,211x 2 [ N Z
1/3 L.
By Lemma A.2 and the fact that F is of width S C, there exists a U, such that
||N Nx
|00 2
C and S.(R)) + S.(R2),
C
where S, is defined in Definition A.
We will show that U, satisfies the condition of the lemma.
There exists a λo E (0, 1) such that U, + (1 - (o))2) + by = 0. Let gs doq + (1 Ao)g2. It is easy
to check that:
(v1) |00/|/00 S max 1100 S 7
(v2) 143 2 min;=1,2 14 (1) 2 T' for j = 1,2.
Since U.43 + b. 0, U. + b,- = 0 has solution in Bx (0, 2).
Therefore, suffices to prove equation 20 We first prove
(p4). 5.1/5
4/3 ( 1 is not valid.
019) (-840 (2)
(k) 9s
If it is valid, let gr. E R" be defined as 43 + is easy to see that, U.q. b, = O.
= 0, and
when k > 2. It
U11)
By Lemma A.4 there exist fy and such that 1/ - q: |mx < 0.25e 1/30 and |||| l0 < 0.255-/3p Furthermore, set PA = Aas (1 A) u) and Zx = Ag3 + () - b) for X E [0,1] Let T be the set of X E [o, 1), such that Pa is in the interior of a linear region RI,,, dı is in the interior of a linear region R2,x and RI and R are neighboring linear regions with boundary (U,, 6.). Then [// 2 0.5.
We prove the properties (p41) and (p42) before proving (p4).
(p41). The total H2-length of the segments in (93 + 4y v) P2(Eo) is S e/3 The total He-length of the segments (2s + 4y p))))(c)) is < c//
45

---

Published as a conference paper ICLR 2024
We just prove the result for q3 - 4u + v, and the proof for q8 - 94 is the same. Since
19: (1)
43 (1)
(1 (- 0 (
(74)
0.5 0.5-5x
0.5+ 1 93
(2)
0.5-5x 1/3
0.5+44173 10
T' (by (v2))
0.5-5c1/3
(1 (0.5 3c 3/1133(1 2c 2
1/5+
(0.5 5c 1/38
and
l03 1 $ |n/ (by (v1)) & (0.5+ + 30113)0.
we have that
m + (1)) (1)
(1)
43
< () 93
(1) + || + 19e
28 "
s 0.5c + (0.5 - 5c 1/3
= (0.3 - 4.3c /310
and
l0b (
93 (2)
11, 43 ||0||0 19 (1) (2)
(2)
N (0 (0.5 + 3/3 0.5c 1/30
(24)
= -0.5e/3pp + (0.5 36 1/3
= (0.5 - 3.5c
which implies ( + (1)) (1) <
(1)
0.5-4.5c'/3 1/3
+ v22) - 93 S (1 - 26 (2)
(2)
+ + 1/
0.5- 19
For j >> 2, we have
(3) -0() _ < ||0|| + 11 4: 1100 + (j) +19
43 < 0/50 S (1 (1-252
(1)
3/3) $ (1 2c )/9 + (2)
(2)
03 1; that is, for any j * 2, we have
(2)
My + vl1) (i)
(i)
43
$ 1/3
1g + u22) 93
Consider the polyline segment 3i
93 ay
- 21. The segment Q3 - qy + v can be written as
1 400 26
+ + (gy + q3), and because (2)
< 1 - 2e for any j } 2, qy +
can be written
14) +
23)
as (4 + x2)) - 43
(2) (v1, 1, U2
Un TT E R., where = 2 +0(2) - (2) and |/:|
(
(t) (1 25
00 + 45
(2)
1 1/3 for E [n - 1). So similar to Property (p2), we have
= (F(xo) - F(wa) + (F(4a) F(g, + v)) + (F(yg + - F(q2))
< (2 + +)]lg3|| bo +So pllittu-all 12(13 (gg + Q3))
+(1 - 1/33 + -- 12(43 + U(yy + u ga) )dl
+(1 - 11,, + +1lloo)00 x2
Since ()())+. (
< - 1/3 < 1 - 1/3 for any j # 2. Similar to (p2), we find that {gs +
14b +. (2)
45 [3)
by + v)/ (2
2) has Hz-length most 1/3 For qy U. we have the same result. This proves (p41).
46

---

Published as a conference paper ICLR 2024
(p42). There exists a À E [0,1] such that RI, Re((o) are neighboring linear regions with boundary (U,. b,), where i = 1,
Let I C [0, 1] be the set of À such that R1, and R2, are in R2(eo) and are neighboring regions with boundary (Us, b,). First, we prove (wl) and (w2).
(w1). There exists a C [0, 1] with length at least (eo)).
2/3 such that, when À E Is, R1,1
(2) 10a -ub" to00yl
As defined in (p4), R1,2 is the linear region containing PA Ags +1- (1-A) +u) 4y uy+++(-g, u q3 )A, so x E [0, 1] Is if and only if PN E {qz + qv + +2} \ P2(Eo). Then we just need to show that: the
length of [0, 1] \ Is is most 16-1 (ob + which follows from the fact that the Hz-length of set {gs - By + (Co) is at most e//3, shown in (p41).
1/3
(w2). There exists a set of intervals Is C [0, 1] with length at least
2/3
such that, when
145 -(ub" -
À E Lo. R2, is in (EO), which can be proved similar to (wl).
From the definitions of Ia, I4, Is, la, have I4 1g Is
Ia
1 (((0, Is) 1s ( Io)).
By properties (wl), (w2), Lemma A.4, and equation
24 27
14 = 1/3 \ (((O, 1s) ( 16)) Z
1/8
2/3
0.5
+ 0.5
Thus there exists À E 14 and (p42)
195
49 11
2 d6 2
(3.5-3.5e1/30
proved.
We now prove (p4). Let VR, be the normal vector of F over Ra, Then by property (p42), we know that R are neighboring linear regions with boundary (U,, b.), where i = 1, 2, so ||UR, UR lloe = || loo > c.
On the other hand, still by (p42), Ra, are in R2(co), so we have |0]] Ra
< 2/3 /3 t/t when * and [n (2) (2 + e) - (Eo) = 2/3 j. which means ||RR -URalls < J. A contradiction is obtained
(k)
and (p4) is proved.
(p5).
1/3
(
| is not valid. This can proved similar to property (p4).
0.5-56173
(p6). If 0.5442/3
0.5-5,4/3 0.74 then there exists no j > 2 such that
(20
12c4/a
0.5-5e473
max [U
T-2
Assume
U131
>
| and define a point g: di (1)
0, (2)
43 + (1 12c 1/3 21
(2)
(0g
8)
98
(1)
(
+ 2/3
(g. for j > Then (p6) can be proved similar to (p4).
43
0
We now prove equation 20
Since properties (p4), (p5), (p6) are always false, it must hold that 0.5 12.1/3
0.5-5e173
- 1 0.54
0.5 1/33
and
|u
for any j > 2. Then equation 20 and the lemma are 1-227
max
proved.
47


Reviews:
[{"review_id": "1msB3HKXlR", "reviewer": "Reviewer_MXq8", "summary": "The paper studies the complexity and necessary conditions of robust memorization for ReLU networks. Since it is NP-hard to decide whether there exists a small network which is a robust memorization of a given dataset with a robust budget, studying necessary conditions is very important. Two important results are given in the paper. Let n be the input dimension and N be the number of datapoints. First, under a reasonable setting, a network with width smaller than n can not be robust memorization for some dataset and robust budget. Furthermore, there exists a network with width $3n+1$ and depth $2N+1$, and $O(Nn)$ nonzero weights such that a robust memorization is achieved. However, in this case, the values of the parameters can go to infinity when the robust budget is increased. To address this case, the second important result of this paper utilizes a deeper network to guarantee a bounded Lipschitz constant of the network, provided that the underlying classification problems are binary. The depth in this case is increased by a factor of $log(n)$.", "questions": "1. The Theorem 2.2 in (Li et al., 2022) is derived for $p>=2$. 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?\n\n2. 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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Originality: Most existing memorization bounds are derived without optimal robustness. Given that importance of robustness, the proposed necessary conditions for ReLU networks are novel and interesting.\n\n- Quality and clarity: This paper gives a comprehensive presentation on the existence of of ReLU networks that have robust memorization. The background knowledge is well-organized, and the theoretical results are presented in a flow that is easy to follow and understand.\n\n- Significance: The family of ReLU networks is an important architecture and understanding the limitations of memorization is crucial. The new estimate $O(Nn)$ is an improvement over Theorem 2.2 in (Li et at., 2022) in the sense that it achieves stronger robustness with less number of parameters without assuming binary classification.", "weaknesses": "- The paper is mainly dedicated to the existence of robust training. No results on optimization or robust generalization are derived. Given that, the scope seems to be quite limited.\n\n- Since overparameterization can often lead to powerful memorization and good generalization performance, the necessary conditions may have stronger implications if they are connected to generalization bounds. 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "123IEgzmKy", "reviewer": "Reviewer_Sknc", "summary": "The authors study memorization with neural networks and its connection to deep learning. It emphasizes the significance of \"robust memorization,\" which hasn't been thoroughly explored. The passage mentions the NP-hardness of computing certain network structures for robust memorization and introduces the concept of \"optimal robust memorization.\" It highlights the explicit construction of neural networks with specific parameter counts for optimal memorization. There's also a mention of a lower bound on network width and controlling the Lipschitz constant to achieve robust memorization in binary classification datasets. It is a technical paper addressing these aspects of neural network memorization and generalization. However, it does not provide a clear path for interested readers to understand them.", "questions": "The authors may think about the organization of this paper. ICLR may not be a suitable conference for this paper.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The strengths of the provided passage are its technical depth, problem formulation, explicit solutions, and mention of a lower bound. It delves into the complexities of neural network memorization, introduces a significant problem in deep learning, provides practical solutions, and hints at valuable insights for network design.", "weaknesses": "It is highly technical and requires a strong background in readers to grasp the meaning of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JRYR8GiqmQ", "reviewer": "Reviewer_LzNK", "summary": "The paper studies the problem of robust memorization, namely exactly fitting the training data while keeping the same prediction in a small neighborhood of each training data. In its first result, it shows that it is NP-hard to compute a robust memorization of the simple network of depth 2 and width 2. It then provides a necessary condition on the width, depth and number of parameters for the existence of robust memorization. It further constructed a neural network which is a robust memorization.", "questions": "I would like to see some intuition on why the number of non-zero parameters does not depend on $\\lambda_D$, $L$ and $\\mu$. Especially, a comparison with the prior work of Li. et. al. 2022.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "It extends the prior results (Li et al 2022) on robust memorization from $\\lambda/4$ to any value strictly less than $\\lambda/2$.\n\nThe number of parameters in the constructed neural network which is a robust memorization does not depend on the separation bound $\\lambda_D$ or the robust budget $\\mu$.\n\nThe paper is well-organized and clearly written.", "weaknesses": "1. The term “optimal robust memorization” is inappropriate, and might be misleading and over-claims the significance of the work. Note that robust memorization with radius $< \\lambda_D/2$ is not significantly different from that with radius $< \\lambda_D/4$, except it is a bit larger neighborhood. This is because $\\lambda_D$ is just the minimal distance, not necessarily the distance for every pair of data samples. Hence, even in the case of the so-called “optimal” $\\lambda_D/2$-robust memorization, there are still many regions that are not covered by the robust-neighborhoods, and it can be non-robust in those areas. Therefore, $\\lambda_D/2$-robust memorization does not really make much difference than the  $\\lambda_D/4$-robust memorization. (The word “optimal” only reflects it is the largest radius in the minimal separation based analysis, however, as I mentioned above, it is far from an optimal robust memorization). Therefore, I would consider the contribution of this paper is on enlarging the robust memorization region, which is limited.\n\n2. 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. I hope the authors can clarify on this point. \n\n3. 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. Hence, it is not totally “cannot be deduced from each other”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)