Generalization and Estimation Error Bounds for Model-based Neural Networks
Authors: Avner Shultzman
Eyar Azar
Miguel R. D. Rodrigues
Yonina C. Eldar
Venue: ICLR 2023 poster (2023)
Keywords: Model based neural networks
Generalization error
Estimation error
Local Rademacher complexity.

Abstract: Model-based neural networks provide unparalleled performance for various tasks, such as sparse coding and compressed sensing problems. Due to the strong connection with the sensing model, these networks are interpretable and inherit prior structure of the problem. In practice, model-based neural networks exhibit higher generalization capability compared to ReLU neural networks. However, this phenomenon was not addressed theoretically. Here, we leverage complexity measures including the global and local Rademacher complexities, in order to provide upper bounds on the generalization and estimation errors of model-based networks. We show that the generalization abilities of model-based networks for sparse recovery outperform those of regular ReLU networks, and derive practical design rules that allow to construct model-based networks with guaranteed high generalization. We demonstrate through a series of experiments that our theoretical insights shed light on a few behaviours experienced in practice, including the fact that ISTA and ADMM networks exhibit higher generalization abilities (especially for small number of training samples), compared to ReLU networks.

Published as a conference paper at ICLR 2023
GENERALIZATION AND ESTIMATION ERROR BOUNDS FOR MODEL-BASBE NEURAL NETWORKS
Avner Shultzman' Eyar , R. D. Rodrigues" & Yonina C. Eldar' Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Israel Faculty of Engineering Science, University College London, UK² {avner. shult zman, eyar. azar, yonina eldarr emaizaan. ac. m. roeroougees@uuu @ucl. ac.
ABSTRACT
Model-based neural networks provide unparalleled performance for various tasks, such as sparse coding and compressed sensing problems. Due the strong nection with the sensing model, these networks are interpretable and inherit prior structure of the problem. In practice, model-based neural networks exhibit higher generalization capability compared to ReLU neural networks. However, this phe- nomenon was addressed theoretically. Here, we leverage complexity measures including the global and local Rademacher complexities, in order to provide upper bounds on the generalization and estimation errors of model-based networks. We show that the generalization abilities of model-basee based networks for sparse recovery outperform those of regular ReLUU networks, and derive practical design rules that allow to construct model-based networks with guaranteed high generalization. We demonstrate through a series of experiments that our theoretical insights shed light a few behaviours experienced in practice, including the fact that ISTA and ADMM networks exhibit higher generalization abilities (especially for small number of training samples), compared to ReLU networks.
INTRODUCTION
Model-based neural networks provide unprecedented performance gains for solving sparse coding problems, such as the learned iterative shrinkage and thresholding algorithm (ISTA) (Gregor & LeCun 2010) and learned alternating direction method of multipliers (ADMM) (Boyd et 2011). In practice, these approaches outperform feed-forward neural networks with ReLU nonlincarities.
These neural networks are usually obtained from algorithm unrolling (or unfolding) techniques, which were first proposed by Gregor and LeCun (Gregor & LeCun 2010), to connect iterative algorithms to neural network architectures. The trained networks can potentially shed light on the problem being solved. For ISTA networks, each layer represents iteration of gradient-descent procedure. As a result, the output of each layer is a valid reconstruction of the target vector, and we expect the reconstructions improve with the network's depth. These networks capture original problem structure, which translates in practice to lower number of required training data (Monga et al.) 2021). Moreover, the generalization abilities of model-based networks tend improve over regular feed-forward neural networks (Bchboodi et al., 2020: [Schnoor et al. 202I).
Understanding the generalization of deep learning algorithms has become an important open question. The generalization етrоr of machine learning models measures the ability of a class of estimators to generalize from training to unseen samples, and avoid overfitting the training (Jakubovitz al.) 2019). Surprisingly, various deep neural networks exhibit high generalization abilities, even for increasing networks' complexities (Neyshabur et al. 2015b Belkin al., 2019). Classical machine learning
"This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research, innovation programme (grant agreement No. 101000967), and Israel Science Foundation under Grant 536/22. Y. C. Eldar and M. R. D. Rodrigues are supported by The Weizmann UK Making Connections Programme (Ref. 129589). M. R. D. Rodrigues is also supported by the Alan Turing Institute. The authors wish to thank Dr. Gholamali Aminian from the Alan Turing Institute, UK for his contribution the proofs' correctness.

---

Published as a conference paper at ICLR 2023
measures such as the Hapnik-Chervonen (VC) dimension (Vapnik & Chervonenkis 1991) and Rademacher complexity (RC) (Bartlett & Mendelson 2002). predict an increasing generalization error (GE) with the increase of the models' complexity, and fail to explain the improved generalization observed in experiments. More advanced measures consider the training process and result in tighter bounds the estimation error (EE), were proposed to investigate this gap, such the local Rademacher complexity (LRC) (Bartlett et al., (200). To date, the EE of model based networks using these complexity measures has not been investigated to the best of our knowledge.
1.1 OUR CONTRIBUTIONS
In this work, we leverage existing complexity measures such as the RC and LRC, in order to bound the generalization and estimation errors of learned ISTA and learned ADMM networks.
We provide new bounds the GE of ISTA and ADMM networks, showing that the GE of model-based networks is lower than that of the common ReLU networks. The derivation of the theoretical guarantees combines existing proof techniques for computing the generalization error of multilayer networks with new methodology for bounding the RC of the soft-thresholding operator, that allows a better understanding of the generalization ability of model based networks.
The obtained bounds translate to practical design rules for model-based networks which guarantee high generalization. In particular, we show that a nonincreasing GE as function of the network's depth is achievable, by limiting the weights' norm in the network. This improves over existing bounds, which exhibit logarithmic increase of the GE with depth (Schnoor et al. 202T The GE bounds of the model-based networks suggest that under similar restrictions, learned ISTA networks generalize better than learned ADMM networks.
We also exploit the LRC machinery to derive bounds on the EE of feed-forward networks, such as ReI.U, ISTA, and ADMM networks. The EE bounds depend on the data distribution and training loss. We show that the model-bases networks achieve lower EE bounds compared to ReLU networks.
We focus on the differences between ISTA and ReLU networks, in term of performance and generalization. This is done through series of experiments for sparse vector recovery problems. The experiments indicate that the generalization abilities of ISTA networks are controlled by the soft-threshold value. For a proper choice of parameters, ISTA achieves lower EE along with more accurate recovery. The dependency of the EE as a function and the number of training samples can be explained by the derived EE bounds.
1.2 RELATED WORK
Understanding the GE and EE of general deep learning algorithms an active area of research. A few approaches were proposed, which include considering networks of weights matrices with bounded norms (including spectral and L2,1 norms) (Bartlett et al. 2017 Sokolić et al. 2017). and analyzing the effect of multiple regularizations employed deep learning, such as weight decay, early stopping, or drop-outs, on the generalization abilities (Neyshabur et al. 201 Gao & Zhou 2016 Amjad et al., 202I). Additional works consider global properties of the networks, such of all Frobenius norms of the weight matrices in the network (Golowich et al. 2018). However, these available bounds do not capture the GE behaviour as a function of network depth, where an increase in depth typically results in improved generalization. This also applies to the bounds on the GE of ReLU networks, detailed in Section 2.3
bound on the product
Recently, a few works focused on bounding the GE specifically for deep iterative recovery algorithms (Behboodi et al., 2020) |chnnoor et al. (00TT. They focus on broad class of unfolded networks for sparse recovery, and provide bounds which scale logarithmically with the number of layers (Schnoor ct al. 2021). However, these bounds still do not capture the behaviours experienced in practice.
Much work has also focused on incorporating the networks' training process into the bounds. The LRC framework due to Bartlett, Bousquet, and Mendelson (Bartlett et al.) 2005) assumes that the training process results in a smaller class of estimation functions, such that the distance between the estimator in the class and the empirical risk minimizer (ERM) is bounded. An additional related framework is the effective dimensionality due to Zhang /hang 2002). These frameworks result in
2

---

Published as a conference paper at ICLR 2023
different bounds, which relate the EE to the distance between the estimators. These local complexity measures were not applied to model- basel neural networks.
Throughout the paper use boldface lowercase and uppercase letters to denote vectors and matrices respectively. The L1 and Le norms of vector æ are written as ||>||| and || respectively, and the Lo (which corresponds
the maximal L1 norm over the matrix's 's rows) and spectral norms of matrix X, are denoted by || and |X||, respectively. We denote the transpose operation by (.)². For any function and class of functions H. we define f o H fx + f h(x) h E H}.
2 PRELIMINARIES
2.1 NETWORK ARCHITECTURE
We focus on model-based networks for sparse vector recovery, applicable to the linear inverse problem
y Ax +
(1)
where y Ba is the observation vector with ny entries, E R" is the target vector with n₂ entries, with n2 > ny. A E R", xn= is the linear operator, and e E R"v is additive noise. The target vectors sparse with sparsity rate p. such that most [mn.,] entries nonzero. The inverse problem consists of recovering the target vector æ, from the observation vector
Given that the target vector is assumed to be sparse, recovering from y in (1) can be formulated as an optimization problem, such as least absolute shrinkage and selection operator (LASSO) (Tibshirani & Ryan 2013), that can be solved with well-known iterative methods including ISTA and ADMM. To address more complex problems, such as an unknown linear mapping A, and to avoid having to fine tune parameters, these algorithms can be mapped into model-based neural networks using unfolding or unrolling techniques (Gregor & LeCun 2010; Boyd ct al. 201T Monga et al., 2021 Yang et al. 2018). The network's 's architecture imitates the original iterative method's 's functionality and enables to learn the models' parameters with respect to set of training examples.
We consider neural networks with L layers (referred as the network's depth), which corresponds to the number of iterations in the original iterative algorithm. The layer outputs of an unfolded ISTA network hy, 1 [1, L). are defined by the following recurrence relation, shown Fig.
h' = Sx (w'n) +) hi = Sb
(2)
where W' E Im R"= I E [1, L] are the weights matrices corresponding each of the layers, with bounded norms | |mx < B. We further assume that the L2 norm of W is bounded by Bi- The vector b AT y is constant bias term that depends on the observation y, where we assume that the initial values are bounded, such that ||4 < Bo. In addition, Sx(+) is the elementwise soft-thresholiig operator
Sxh shg max(m/) (h) A,
where the functions sign(-) and max(-) are applied elementwise, and 0 vector of zeros. As (-)- is an elementwise function it preserves the input's dimension, and can be applied scalar or vector inputs. The network's 's prediction given by the last layer in the network ē (z)). We note that the estimators are functions mapping y to ã, h Rey + R= characterized by the weights, i.e. (fW')) (W))) The class of functions representing the output at depth L in an ISTA network. h 3 = (hf ((W")) : W S B, E [1, L), ||W < B1).
Similarly, the /th layer of unfolded ADMM is defined by the following recurrence relation
h' = w' (z [- + u u11 +
z' = S^ (h/2 - u w111),
z = 0
(4)
u' i-1 - (h'a z!),
u
where 0 is vector of zeros, b = A "y constant bias term, and > is the step size derived by the original ADMM algorithm, as shown in Fig. The estimators satisfy h/ IR"v - "== and the class
of functions representing the output at depth in an ADMM network, H = (h ((W()) H2))
|| < B, I e [1, L), ||W'||2 1|2 < },), where we impose the same assumptions on the weights matrices ISTA networks.
3

---

Published as a conference paper at ICLR 2023
For depth-L ISTA or ADMM network, the learnable parameters are the weight matrices {W The weights are learnt by minimizing loss function L on set of m training examples 5 11=1- = {ax 34 B:)) drawn from unknown distribution D, consistent with the model in (I) We consider the case where the per-example loss function is obtained by averaging over the example per-coordinate losses:
1 e (h,(t), Th.
C (h(y),
where (y) and æ denote the jth coordinate of the estimated and true targets, and é: IR + R. is I-Lipschitz in its first argument. This requirement is satisfied in many practical settings, for example with the p-power of Lp norms, and is also required in related work (Xu et al., 2016). The loss of an estimator h H which measures the difference between the true value I and the estimation huy), ). is denoted for convenience by L(h)
(h(y), x)).
There exists additional forms of learned ISTA and ADMM networks, which include learning an additional set of weight matrices affecting the bias terms (Monga et al., 202T). Also, the optimal value of À generally depends on the target vector sparsity level. Note however that for learned networks, the value of À at each layer can also be learned. However, here we focus on more basic architecture with fixed À in order to draw theoretical conclusions.
tth Inyer of unfeldied ISTA network
S
b. (s layer of unfolded ADMM network
Figure 1: A single layer in the unfolded networks. Unfolded ISTA. b. Unfolded ADMM. The learnable parameters are the weight matrices (marked in red).
2.2 GENERALIZATION AND ESTIMATION ERRORS
In this work, we focus on upper bounding the GE and EE of the model-based neural networks of Fig. I The GE of class of estimation functions h E: H. such that h R" - R= defined as
G(HL) Es sup LD (h) Ls(h) heR
(6)
where (D(h) En)(h) is the expected loss with respect to the data distribution D (the joint probability distribution of the targets and observations). (s(h) = 1 average empirical loss with respect to the training set S, and Eg is the expectation over the training datasets. The GE a global property of the class estimators, which captures how the class of estimators H is suited to the learning problem. Large GE implies that there hypotheses in H for which LD deviates much from Ls. on average over S. However, the GE in (6) does not capture how H.
m E ((h(t:). is the
the learning algorithm chooses the estimator
In order to capture the effect of the learning algorithm, we consider local properties of the class of estimators, and focus on bounding the estimation error (BE)
E(L)= LD (ni)
inf LD (h) hER
where h is the ERM satisfying (h(h) = inf (h).. We note that the ERM approximates the learned estimator heeamed which is obtained by training the network on a set of training examples S, using algorithms such as SGD. However, the estimator heammed depends on the optimization algorithm, and can differ from the ERM. The difference between the empirical loss associated with f and the empirical loss associated with Neamed is usually referred to the optimization error.
4

---

Published as a conference paper at ICLR 2023
Common deep neural network architectures have large GE compared to the low EE achieved in practice. This still holds, when the networks are not trained with explicit regularization, such as weight decay, early stopping, or drop-outs (Srivastava et al. 2014 Neyshabur et al. 2013b). This empirical phenomena is experienced across various architectures and hyper-parameter choices (Liang et al. 2019 Novak et al. 2018 Lee al. 2018. Neyshabur et al. 2018).
2.3
RADEMACHER COMPLEXITY BASED BOUNDS
The RC is standard tool which captures the ability of a class of functions to approximate noise, where lower complexity indicates a reduced generalization error. Formally, the empirical RC of class of scalar estimators H. such that h : yy - IR for h H. over m samples is
1 Σ h(()))
Rm (H) = 1e sup NEH m
(8)
where {6:) 1m
Pr (c; - -1) i=1 are independent Rademacher random variables for which Pr =)) 1/2, the samples { are obtained by the model in (T) from m i.i.d. tar- get vectors {æ, J drawn from an unknown distribution. Taking the expectation of the RC of L H with respect to the set of examples S presented in Section[..1 leads to bound on the GE
((H)) S 2m (C 7t)
where C is defined in Section 2.1 and Lo H {(xr y) - (() E 7) (Shalev-Shh Shalev-Shwwrtz. & Ben-David 2014). We observe that the class of functions L 7 consists of scalar functions, such that IR for f L H. Therefore, in order to bound the GE of the class of functions defined by ISTA and ADMM networks, we can first bound their RC.
7: 1
I Ri
Throughout the paper, we compare the model- architectures with feed forward network with ReLU activations, given by ReLU(h) max (h, 0). In this section, we review existing bounds for the generalization error of these networks. The layers of ReLU network h'p. Vl [1. L]. are defined by the following recurrence relation h² = ReLU (W'n'R /-1 + b). and h = Rb),U(b), where W VI E [1, L] are the weight matrices which satisfy the same conditions as the weight matrices of ISTA and ADMM networks. The class of functions representing the output at depth L
R
in ReLU network, is H ((W(( 1=)) || B. [1, L.. || B.). This
architecture leads to the following bound on the GE.
Theorem 1 (Generalization error bound for ReLU networks (Gao & Zhou 2016)). Consider the class of feed forward networks of depth-T, I, with ReL.U activations, H as described in Section 2.3
and m i.ddd training samples. Given a 1-Lipschitz loss function, its GE satisfies g (H4) s 22
where G² = Bo IIk B
mm
Proof. Follows from applying the bound of the RC of ReLU neural networks from (aao & Zhou 2016) and combining it with (9.
The bound in Theorem is satisfied for any feed forward network with 1-Lipschitz nonlinear activations (including ReLU), and can be generalized for networks with activations with different Lipsheitz constants. We show in Theorem 2, that the bound presented in Theorem cannot be substantially improved for ReLU networks with the RC framework.
Theorem 2 (Lower Rademacher complexity bound for ReLU networks (Bartlett et al., 2017 Consider the class of feed forward networks of depth-L with ReLU activations, where the weight matrices have bounded spectral norm || S By, I [1, L). The dimension of the output layer is 1, and the dimension of each non-oulput layer is at least 2. Given m i.i.d. training samples, there exists a e such that Rm (H'2 2 cBo 1I B/, where H ((l((WW))))) Hax): || S B 1 L]]
This result shows that using the RC framework the GE of ReLU networks behaves as the product of the weight matrices' norms I Bi, as captured in Theorem 1 Theorem 2 implies that the dependence on the weight matrices' norms, cannot be substantially improved with the RC framework for ReL.U networks.
5

---

Published as a conference paper at ICLR 2023
3 GENERALIZATION ERROR BOUNDS: GLOBAL PROPERTIES
In this section, we derive theoretical bounds on the GE of learned ISTA and ADMM networks. From these bounds deduce design rules construct ISTA and ADMM networks with GE which does not increase exponentially with the number of layers. We start by presenting theoretical guarantees on the RC of any class of functions, after applying the soft-thresholding operation.
Soft-thresholding is basic block that appears in multiple iterative algorithms, and therefore is used the nonlinear activation in many model-based networks. It results from the proximal gradient of the L1 norm (Palomar & Eldar 2010). We therefore start by presenting the following lemma which expresses how the RC of a class of functions is affected by applying soft-thresholding each function in the class. The proof is provided in the supplementary material.
Lemma 1 (Rademacher complexity of nofttthresholding. Given any class of scalar functions H where h. : IR" + R. h E H for any integer n 2 1, and m i.i.d. training samples,
XI
Rm (Sx H) S R. (H)
(10)
where T = E T; and T = [()) arg NE (h(y1) h' (g)))) 2A + 2 e Sx
(g,) such that h", h
The quantity T' is non-negative value obtained during the proof. which depends on the networks' number of layers, underlying data distribution 'D and soft- threshhe value X. As seen from (0).. the value of T dictates the reduction in RC due to soft-thresholding, where reduction in the RC can also be expected. The value of T increases as decreases. In the case that XT increases with X, higher values of À further reduce the RC of the class of functions H. due to the soft-thresholding.
We now focus on the class of functions representing the output of a neuron at depth an ISTA network, H.F. In the following theorem, we bound GE using the RC framework and Lemma The proof is provided in the supplementary material.
Theorem 3 (Generalization error bound for ISTA networks). Consider the class of learned ISTA networks of depth L described in (2), and m i.i.d. training samples. Then there exist T() for
I ee [1, in the range (1))
0. min
m G.
m such that G (HH)) 2EsG4, where
G = Bo 1= By
I
XT
II J=P-1
Bj
(11)
m
m
Next, we show that for specific distribution, the expected value of ( is greater than 0. Under an additional bound on the expectation value of the estimators (specified in the supplementary material)
Es (Tw) Z max (1 2e- (eB,b6,6 (10B)600-))000)
(12)
where b((+1) Bib > 6(2) Bo, and e (0, 1]. Increasing À or decreasing B, will decrease the bound in 12 since crossing the threshold is less probable. Depending on À and {Bi (specifically that À < (B) In 2), the bound in (12) is positive, and enforces a non-zero reduction in the GE.
Along with Theorem 3 this shows the expected reduction in GE of ISTA networks compared to
ReLU netowrks. The reduction is controlled by the value of the soft threshold.
To obtain a more compact relation, we can choose the maximal matrices' norm max Bi,
and denote min T E [0,m] which leads to g (H/) <
Bo
(Ts(T)
B
Comparing this bound with the GE bound for ReLU networks presented in Theorem I shows the expected reduction due to the soft thresholding activation. This result also implies practical rules for designing low generalization error ISTA networks. We note that the network's 's parameters such as the soft-threshold value and number of samples m., are predefined by the model being solved (for example, in ISTA, the value of chosen according to the singular values of A))
We derive an implicit design rule from 3 for nonincreasing GE, as detailed in Section A.2 This
(Es(T) Moreover, these results can is done by restricting the matrices' norm to satisfy B < 1 1+ /mB,

---

Published as a conference paper at ICLR 2023
be extended to convolutional neural networks. As convolution operations can be expressed via multiplication with a convolution matrix, the presented results are also satisfied in that case.
Similarly, bound the GE of the class of functions representing the output depth L in an ADMM network, A. The proof and discussion are provided in the supplementary material.
Theorem 4 (Generalization enror bound for ADMM networks). Consider the class of learned ADMM networks of depth L as described in 1 and m i.id. training samples. Then there exist
T( for 1 E [1, 1] in the interval T()
0, min
mB. .m]] where G¹ Be Bell By vm
X
Á Σ T(') 11 Xr((11) and (1 + 7) Br = (1 (B) + 2), [1, LJ, such
that 9 (44) - E
We compare the GE bounds for ISTA and ADMM networks, to the bound on the GE of ReLU networks presented in Theorem I We observe that both model-based networks achieve a reduction in the GE, which depends on the soft-threshold, the underlying data distribution, and the bound on the norm of the weight matrices. Following the bound, observe that the soft-thresholding nonlinearity most valuable in the case of small number of training samples. The voft-thresholding nonlinearity is the key that enables reducing the GE of the ISTA and ADMM networks compared to ReLU networks. Next, we focus on bounding the EE of feed derw-fowwrr networks based on the LRC framework.
4 ESTIMATION ERROR BOUNDS: LOCAL PROPERTIES
To investigate the model-based networks' EE, we use the LRC framework (Bartlett et al. 2005). Instead of considering the entire class of functions H. the LRC considers only estimators which are close to the optimal estimator H. = h E H Ep (y) - h" (x))l2 <r). where h" is such that (p(h)) = infne (h). It is interesting to note that the class estimators H. only restricts the distance between the estimators themselves, and not between their corresponding losses. Following the LRC framework, we consider target vectors ranging in [-1, 11 Therefore, we adapt the networks' estimations by clipping them to lie in the interval [-1, _ In our the restricted classes functions representing the output of a neuron at depth in ISTA, ADMM, and ReLU networks. Moreover, corresponding to h E H. and h", respectively. Based on these restricted class of functions, we present the following assumption and theorem (the proof is provided in the supplementary material).
consider
denote by W and W I E [1, L] the weight matrices
Assumption 1. There exists a constant C 2 1 such that for every probability distribution DD and estimator h E H. Ep Σ3= (h, h;)² & CED Σ} (E(h;) E(hz)). where h2 and h denote the jth coordinate of the estimators.
As pointed out in Bartlett & Mendelson, 2002), this condition usually follows from a uniform convexity condition on the loss function &. For instance, if (h(y) æ < for any h E H, y E Rav and x E RT= then the condition is satisfied with C C= (Yousefi et al. 2018).
Theorem 5 (Estimation error bound of ISTA, ADMM, and ReLU networks). Consider the class of functions represented by depth-L ISTA networks H as detailed in Section 2.1 m i.i.d training samples, and per-coordinate loss satisfying Assumption @wth constant C. Let || w loo S avrr for some a > O. Moreover, Z max a rr 1}. Then there exists in the interval T T (,,,in //mB,B"-12"" m where 1J LB" LB -1++++ such that for
An
(B-1)
any 8 with probability at least -
S 41r + 17Ca + 48C
El &(HL7)
(13)
mag
2 XT nn where r* =22a2 Bi Vm
The bound is also satisfied for the class of functions
represented by depth-T, ADMM networks H4, with rr C2
(BaBb-222-1 vm
XT m
where
A= (1+ (1 (B + 2), and 7 functions represented by depth-L ReLU networks H/. with r* = C2a² (BoBh-igh
and for the class of
(B-
(Ba
7

---

Published as a conference paper at ICLR 2023
From Theorem 5 observe that the EE decreases by a factor of O (1/m). instead of factor of O (L/ obtained for the GE. This result complies with previous local bounds which yield faster convergence rates compared to global bounds (Blanchard et al. 2007 Bartlett et al. (005). Also, the value of a relates the maximal distance between estimators in Hr denoted by r. to the distance between their corresponding weight matrices || 1I I ovrr, I E [1, L.. Tighter bounds on the distance between the weight matrices allow us to choose a smaller value for a, resulting in smaller values r" which improve the EE bounds. The value of a could depend on the network's nonlinearity, underlying data distribution D, and number of layers.
Note that the bounds of the model- architectures depend on the soft siitthhrrsholding through the value of (T) As (Es increases, the bound on the EE decreases, which emphasizes the nonlinearity's role in the network's 's generalization abilities. Due to the soft-thresholding. ISTA and ADMM networks result in lower EE bounds compared to the bound for ReL.U networks. It is interesting to note, that as the number of training samples m increases, the difference between the bounds on the model-based and ReLU networks is less significant. In the EE bounds of model-based networks, the parameter By relates the bound to the sparsity level p. of the target vectors. Lower values of p result in lower EE bounds, demonstrated in the supplementary.
NUMERICAL EXPERIMENTS
In this section, we present series of experiments that concentrate on how a particular model-based network (ISTA network) compares to ReI.U network, and showcase the merits of networks. We focus on networks with 10 layers (similar to previous works (Gregor & LeCun 2010
to represent realistic model-based network architectures. The networks are trained on a simulated
dataset to solve the problem in [ with target vectors uniformly distributed in [-1, 1]. The linear mapping A is constructed from the real part of discrete Fourier transform (DFT) matrix rows (Ong eet al. 2019). where the rows are randomly chosen. The sparsity rate is p = 0.15, and the noise's standard deviation is 0.1. To train the networks we used the SGD optimizer with the Lı loss over all neurons of the last layer. The target and noise vectors are generated as element wise independently from a uniform distribution ranging in [-1, All results are reproducible through (Authors (022)
which provides the complete code to execute the experiments presented in this section.
We concentrate on comparing the networks' EE, since in practice, the networks are trained with finite number of examples. In order to empirically approximate the EE of a class of networks H. we use an empirical approximation of h" (which satisfy (D(h") inf (D)) and the ERM h. denoted by hamp and hemp respectively. The estimator homp results from the trained network with 10 samples, and the ERM is approximated by a network trained using SGD with m training samples (where m < 10*). The empirical EE is given by their difference L (hemp))) (h
In Fig. 2 we compare between the ISTA and ReLU networks, in terms of EE and L1 loss, for networks trained with different number of samples (between 10 and 10a samples). We observe that for small number of training samples, the ISTA network substantially reduces the EE compared to the ReLU network. This can be understood from Theorem 5 which results in lower EE bounds on the ISTA networks compared to ReLU networks, due to the term AEs((T) However, for large number of samples the EE of both networks decreases to zero, which is also expected from Theorem 5 This highlights that the contribution of the soft-thresolding nonlinearity to the generalization abilities of the network is more significant for small number of training samples. Throughout the paper, we considered networks with constant bias terms. In this section, we also consider learned bias terms, as detailed in the supplementary material. In Fig. 2 we present the experimental results for networks with constant and learned biases. The experiments indicate that the choice of constant or learned bias is less significant to the EE or the accuracy. compared to the choice of nonlincarity. emphasizing the relevance of the theoretical guarantees. The cases of learned and constant biases have different optimal estimators, as the networks with learned biases have more learned parameters. As result, it is plausible a network with more learnable parameters (the learnable bias) exhibits a lower estimation error since the corresponding optimal estimator also exhibits a lower estimation error. To analyze the effect of the tetethhessooddng value on the generalization abilities of the ISTA network, we show in Fig. 3 the empirical EE for multiple values of X. The experimental results demonstrate that for small number of samples, increasing À reduces the EE. As expected from the EE bounds, for a large number of training samples, this dependency on the nonlinearity vanishes, and the EE is similar for all values
8

---

Published as a conference paper at ICLR 2023
0.000
0.13
(b)
0.925
Estimation 47702
03.23
0.00
02.00
0.08
0.000
Number training samples
Number training samples
Figure 2: Comparing the EE of ISTA and ReLU networks with 10 layers. a. The EE of the networks as function of the training samples. b. The L1 of the networks function of the training samples. The ISTA network achieves lower EE compared the ReLU network, along with lower losses.
of X. In Fig. 3p. we show the Lı loss of the ISTA networks for different values of X. We observe that low estimation error does not necessarily lead to low loss value, For m X 100, increasing reduced the EE. These results suggest that given ISTA networks with different values of À such that all networks achieve similar accuracy, the networks with higher values of À provide lower EE. These results also valid for additional networks' depths. In Section with different number of layers, and show that they exhibit similar behaviour.
B compare the EE for networks
(b)
0.00
0.10
0.05
0.04
0.08
0.02
0.00
0.03
0.00
109
103
20
107
10a
10F
10t
104
10
Figure 3: Estimation eтror and loss of ISTA networks with 10 layers, as a function of the soft- threshold's value A. The experiments indicate that the estimation error decreases as À increases, which demonstrates way to control the networks' generalization abilities through X.
CONCLUSION
We derived new GE and EE bounds for ISTA and ADMM networks, based on the RC and LRC frameworks. Under suitable conditions, the model- networks' GE nonincreasing with depth, resulting in substantial improvement compared to the GE bound of ReLU networks. The EE bounds explain EE behaviours experienced in practice, such as ISTA networks demonstrating higher estimation abilities, compared to ReLU networks, especially for small number of training samples. Through a series of experiments, we show that the generalization abilities of ISTA networks are controlled by the soft-threshold value, and achieve lower EE along with more accurate recovery compared to ReLU networks which increase the GE and EE with the networks' depths.
It is interesting to consider how the theoretical insights be harnessed enforce neural networks with high generalization abilities. One approach to introduce an additional regularizer during the training process that rooted in the IRCC, penalizing networks with high EE (Yang al. 2019)


Reviews:
[{"review_id": "zpsrqA2qJW", "reviewer": "Reviewer_zELY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies model-based networks in the context of sparse coding.\nA model-based network is constructed by unfolding an iterative algorithm, i.e. mapping each iteration of the original algorithm to a layer of the resulting neural network.\nThis allows to have a trainable neural network that can adapt to specific problems, while encoding some stuctural information of the original iterative algorithm.\n\nThe main goal of the paper is to provide rigorous bounds on the generalisation capabilities of two model-based networks inspired by two specific sparse coding algorithms, namely \"iterative shrinkage and thresholding algorithm\" (ISTA) and  \"alternating direction method of multipliers\" (ADMM).\nMoreover, the authors aim to compare model-based neural networks to generic fully-connected ReLU networks in the context of these bounds.\n\nThe authors prove two sets of bounds for fully-connected ReLU networks and ISTA/ADMM-based neural networks:\n- they bound the generalisation error, intended as the gap between empirical and population loss of the worst-performing function in the model class, averaged over training datasets. They find that the bound for model-based networks is better than that of ReLU networks, and this is crucially linked to the effect that component-wise soft-thresholding has on the Rademacher complexity of a given model class.\n- they bound the estimation error, intended as the gap between the population loss of the ERM minimiser and the population loss of the best performing function in the model class. Again, model-based networks enjoy a better bound on estimation error than ReLU networks, and again this is linked to the effect of soft-thresholding on the local Rademacher complexity of a given model class.\n\nThe authors then study numerically the estimation error of ISTA and ReLU networks, finding that ISTA networks perform better. They also show that the dependence of the estimation error on the scale parameter of the soft-thresholding non-linearity is the same as that predicted by the bounds.\n\nQuestions (see also the weak points section):\n- how does the specific model considered (eq 1) affect the results? \n- are all numerical results robust to a change in sparsity, noise level and batch size? Moreover, what is the batch size used in the numerical experiments?\n- the numerical experiments mention a \"learned bias\" setting that is not accurately described in the main text or in the supplementary material. What is that?\n\nMinor points:\n- the authors could add direct links to the proofs of their lemmas and theorems after stating them.\n- the statement of assumption 1 is not completely clear to me. Is there some notation change or notation missing?\n- if at all relevant, the authors could add the performance of the original ISTA algorithm to their numerical experiments as a baseline performance. If not relevant, why is it not relevant?\n- the operative definition of EE (eq 7) is not completely clear. h_hat is the empirical risk minimiser, so it depends on a training set, is this correct? If so, is there some averaging missing?\n\nCuriosities (not relevant for the review process as far as I am concerned):\n- is there a natural interpretation to why soft-thresholding lowers the Rademacher complexity of model classes?\n- the bound presented in theorem 5 is the same for ReLU, ISTA and ADMM based networks. Can one give a \"physical\" interpetation to r*? In some sense, r* encodes some information about the network architecture that could determine some other property and not only the EE bound.\n- is there an explanation to the fact that learning biases seems to improve the EE of ReLU networks while degrading the EE of ISTA networks?", "summary_of_the_review": "My initial recommendation is: accept.\nThe paper is very clearly written, the results are nice, in particular the fact that the bounds obtained seem not vacuous, and, while I did not check the details of the proofs, the theorems seem sound.\n", "strength_and_weaknesses": "Strong points:\n- the bounds that the authors provide seem to be non-vacuous, which I find non-trivial. Indeed, the bounding terms suggests, for example, that the estimation error depends on the soft-thresholding scale parameter, and this is confirmed numerically.\n- I could not check the correctness of the proofs given the short time-frame of this review process. Nonetheless, the relevant appendices are very detailed and I feel that the interested reader could check the proof details easily if needed. Also, the results as well as the overall proof techinque seem reasonable. \n- The paper is extremely well written and clear. I appreciated particularly that formal mathematical concepts were always explained and justified in the discussion text surrounding them, allowing a much broader audience to understand the results.\n\nWeak points:\n- it is not completely clear what role the specific model that the authors consider (eq. 1) plays in the various theorems. This doesn't allow the reader to fully gauge the applicability of the results to different data models.\n- (minor weak point) the numerical experiments have been performed fixing the sparsity level of the signal to be retrieved, the noise level and, I suppose, the batch size of SGD. It is not clear whether the numerical results are robust across the choice of these parameters.\n- (minor weak point) the numerical experiments mention a \"learned bias\" setting that is not accurately described in the main text or in the supplementary material.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nRAq3wXDbDw", "reviewer": "Reviewer_CF5w", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers the theoretical properties of model-based neural networks which are usually interpretable and inherit the prior structure of the problems, such as ISTA and ADMM networks associated with soft thresholding operators. The bounds for both generalization and estimation errors of these networks are derived via the lens of Rademacher complexity and local Rademacher complexity, which are shown to be lower than that of the common ReLU neural networks under mild conditions. Numerical experiments are also provided to verify the theoretical results.", "summary_of_the_review": "The paper derives the generalization and estimation error bounds of model-based neural networks and provides insights into the superiority of ISTA and ADMM compared to ReLU networks, which should be of interest to the ICLR community.", "strength_and_weaknesses": "$\\textbf{Strength}$\n\n1. It is a novel contribution that broadens the understanding of model-based neural networks and their superiority compared to the standard ReLU networks.\n\n2. The Rademacher complexity of function classes after applying the soft-thresholding operation is derived, which further leads to the generalization and estimation errors of model-based neural networks, such as ISTA and ADMM networks.\n\n3. Codes are provided for the numerical experiments.\n\n$\\textbf{Concerns}$\n\n1. The difference between ISTA networks and ReLU networks is that (2) uses a soft-thresholding operator $S_\\lambda$ and (10) uses ReLU. Can we think of $S_\\lambda$ as a special type of activation function? I was wondering if the performance of ISTA networks is also better than that of leaky ReLU networks or ELU networks?\n\n2. In Figure 3, estimation error decreases as $\\lambda$ increases while $L_1$ loss increases as $\\lambda$ increases, especially for large sample sizes. In practice, how to choose the best $\\lambda$?\n\n3. In Figure 2, it is a little bit confusing to me that the estimation error of ISTA with learned bias is larger than that with constant bias, any explanation?\n\n4.  Is it possible to extend the results to convolutional neural networks?\n\nMinor typos:\n\n1. Is the last term in (13) $\\frac{\\lambda T^{(l)}}{m}$\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iEROEDTeyL", "reviewer": "Reviewer_FqeZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work studies the generalisation properties of model-based neural networks which can achieve unparalleled performance on sparse coding and compressed sensing problems. In particular, the authors leverage complexity measures including the global and local Rademacher complexities to provide upper bounds on the generalisation and estimation errors of model-based networks. They show that the generalisation abilities of model-based networks for sparse recovery outperform those of regular ReLU networks. ", "summary_of_the_review": "I understand the context of this work and the results it is trying to convey. If the results of this work are correct, I think this work deserves to be accepted by ICLR.", "strength_and_weaknesses": "**Strength**\n\n* I am not an expert on model-based neural network, but from my perspective, I think this work adopts a suitable theoretical tools to solve an important problem.\n\n* This writing is quite good. It is eazy to follow the main idea of this work.\n\n**Weakness**\n\n* Though the authors provide simulations to verify the proposed theory, it is still not clear how realistic the theory is and what is the gap between the considered scenario and the realistic settings.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "g-C3m6bLAB", "reviewer": "Reviewer_4ojw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies generalization and estimation error bounds for model-based neural networks that employ soft-thresholding activation functions. By re-examining the proof of the contraction lemma (of Rademacher complexity) for soft-thresholding functions, the paper shows that applying soft-thresholding potentially decreases complexity (although the Lipschitz constant of soft-thresholding is 1).\n\nUsing this result, the paper establishes norm-based bounds on generalization error (GE) and estimation error (EE) of these networks for the problem of sparse vector recovery. The manuscript claims that the GE and EE bounds of the soft-thresholding network are better than those of ReLU. These findings are then validated through experiments.", "summary_of_the_review": "The paper addresses a meaningful question and the approach is novel and of broad interest. However, the paper, in its current state, overstates the significance of its results. I believe some significant restructuring and additional estimations need to be done to support the claims.\n\nAfter revision: My main concern about the manuscript have been addressed and I think this is a good paper.", "strength_and_weaknesses": "### Strengths\n\n- The paper provides theoretical insights into the simple (but important) intuition that model-based methods should perform better than model-free approaches. The main ideas and techniques of the work were developed based on well-founded rationales and in general, the paper is well-written with a sufficient literature review.\n- The mathematical analyses of the work are rigorous and seem correct. The results of the work, which relies on directly bounding the Rademacher complexity, are significantly stronger and more accessible (readable) than previous works (which focused on estimating Rademacher complexity through covering numbers).\n- The bound on Rademacher complexity of soft-thresholding is novel and meaningful and could potentially be of interest to a broader audience in the field beyond the context of model-based networks.\n- If the comment below (in the Weakness section) is well addressed, the bound of the Theorem shows that a nonincreasing GE as a function of the network’s depth is achievable, by limiting the weights’ norm in the network. This is an strong improvement over existing bounds, which exhibit a logarithmic increase of the GE with depth.\n\n### Weaknesses\n\n- In my opinion, the paper, in its current state, overstates the significance of its results. I don’t think the results support the claim that their bounds on GE and EE are better than those of ReLU.\n    \n    While Lemma 1 establishes that applying soft-thresholding potentially decreases complexity, it doesn’t come with any estimation of the improvement (T) and it is not even clear that T is non-zero. In fact, the statements of the theorems all specify that T’s could be zero. The only place where T is estimated is in the discussion after the proof of Lemma 1 in the Appendix, which states that in certain scenarios, it is possible to bound T from below by an explicit constant depending on m. However, the result is written in a general context and it is unclear how this result applies to the studied networks.\n    \n    I strongly suggest that these lower bounds on T are rigorously stated and proved to support the main results of the work. Discussions about the dependence of the improvements on lambda, are not correct if we are not certain that T is non-zero. An explicit bound, even if further assumptions are made, would provide more insights about the order of the improvements, which would be of broad interest to the readers.\n    \n- Similarly, in its current state, Lemma 1 is trivial and doesn’t need its complicated proof. To prove its current statement (existence of T in [0, …] such that…), we just need to establish the inequality for T = 0, which can be directly deduced from the contraction lemma (soft-thresholding has Lipschitz constant 1).\n\n### Questions\n\n- In my understanding, the main idea of the proof of Lemma 1 is that although the Lipschitz constant of soft-thresholding is one (it is a translation in certain regions), there are sub-regions of RxR where |S(x) - S(y)| < |x - y| - 2\\lambda, and the “improvement” depends on the measure of such sub-regions, specifically, on\n    \n    \\{ h*(y) > \\lambda) \\text{and} h*’(y) < -lambda\\}\n    \n    My question is, the ReLU function also ‘contract’ on this region, and the contraction is at least lambda, i.e., |S(x) - S(y)| < |x - y| - \\lambda if x>\\lambda and y<-\\lambda. Does that also mean that we can obtain a similar result for ReLU using the same argument?\n    \n- (Optional. This is not a part of my decision assessment) In the classical proof of the contraction lemma (e.g., Lemma 26.9 of Understanding Machine Learning), the absolute value in the bound can be removed and added when convenient because of the symmetry of h and h’. In the proof of Lemma 1, cases (a, b) is treated differently from (b, a). Is there any particular reason for that?\n\n### Additional feedbacks\n\n- Typos: Section 1.1: “logarithnmic”", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster