On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences
Authors: Alireza Fathollah Pour
Hassan Ashtiani
Venue: NeurIPS 2023 poster (2023)
Keywords: PAC Learning
Recurrent Neural Networks
Noise
Sample Complexity
TL;DR: We prove that the sample complexity of PAC learning noisy recurrent neural networks is logarithmic in the sequence length T while for the non-noisy networks the sample complexity grows at least linearly with T.

Abstract: We consider the class of noisy multi-layered sigmoid recurrent neural networks with $w$ (unbounded) weights for classification of sequences of length $T$, where independent noise distributed according to $\mathcal{N}(0,\sigma^2)$ is added to the output of each neuron in the network. Our main result shows that the sample complexity of PAC learning this class can be bounded by $O (w\log(T/\sigma))$. For the non-noisy version of the same class (i.e., $\sigma=0$), we prove a lower bound of $\Omega (wT)$ for the sample complexity. 
  Our results indicate an exponential gap in the dependence of sample complexity on $T$ for noisy versus non-noisy networks. Moreover, given the mild logarithmic dependence of the upper bound on $1/\sigma$, this gap still holds even for numerically negligible values of $\sigma$.

On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences
Alireza F. Pour
Hassan Ashtiani
Cheriton School of Computer Science
Department of Computing and Software McMaster University
University of Waterloo
@2fathol@uvater
zokaeiammmcmaster
Abstract
We consider the class of noisy multi- lulti-layered sigmoid recurrent neural networks with w (unbounded) weights for classification of sequences of length T, where independent noise distributed according to N(00, o²) added to the output of each neuron in the network. Our main result shows that the sample complexity of PAC learning this class can be bounded by O(w log(T/o)) For the non-noisy version of the same class (i.e., = 0), we prove lower bound of Q(wT)) for the sample complexity. Our results indicate an exponential gap in the dependence sample complexity on T for noisy versus non-noisy networks. Moreover, given the mild logarithmic dependence of the upper bound on 1/o, this gap still holds even for numerically negligible values of o
Introduction
Recurrent Neural Networks (RNNs) are effective tools for processing sequential data. They are used in numerous applications such speech recognition (Graves et al., 2013), computer vision (Karpathy and Fei-Fei 2013), translation (Sutskever et al.) 2014). modeling dynamical systems (Hardt et al. 2018) and time series (Qin al. 2011)). Recurrent models allow us design classes of predictors that can be applied to (i.e., take input values from) sequences of arbitrary length. For processing a sequence of 7 elements, a predictor / (e.g.. neural network) "consumes" the input elements by one, generating an output at each step. This output is then used in the next step (as another input to along with the next element in the input sequence). Defining recurrent models formally takes some effort, and we relegate it to the next sections. In short, the function f is (recursively) applied I times order generate the ultimate outcome.
Let us fix a base class Fu of all multi-layered feed-forward sigmoid neural networks with w weights. We can create recurrent version of this class, which will denote RECIF... 7], for classifying sequences of length T. One can study the sample complexity of PAC learning RECIF T] with respect different loss functions. Koiran and Sontag (1998) studied the binary-valued version of this class by applying a threshold function at the end, and proved a lower bound of M(wT)) for its VC. dimension.
There has also been efforts for proving upper bounds on the sample complexity of PAC learning REC[ 7] for various base classes F and different loss functions. Given the above lower bound, gold standard has been achieving a linear dependence on T' in the upper bound, Koiran and Sontag (1998) proved upper bound of O Dw on the VC dimension of RECIF... 7' discussed above. More recent papers have considered the more realistic setting of classification with continuous-valuue
For the full version of this paper see F. Pour and Ashtiani 2023
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

RNNs, e.g., by removing the threshold function and using bounded Lipschitz surrogate loss. In this setting, Zhang al. 2018 proved an upper bound of Ó(T W ()))()) on the sample complexity
where [ is the spectral norm of the network. Chen et al. (020)) improved over this result by
proving an upper bound of (TTw [ min( Vw, || H) These bounds get close to the gold
standard when the spectral norm of the network satisfies ||Wi| S
The above upper bounds are proved by simply "unfolding" the recurrence, effectively substituting the recurrent class RECIFw, T] with the (larger) class of --oldd compositions Fur Fu...o Fw.- These unfolding techniques do not exploit the fact that the function f (that is applied recursively for T steps to compute the output of the network) is fixed across all the I steps. Consequently, the resulting sample complexity has (super-)lineds dependence on T. Therefore, we would need a prohibitively large sample size for training recurrent models for classifying very long sequences. Nevertheless, this dependence is inevitable in light of the of lower bound of Koiran and Sontag (998)) Or is it?
In this paper, we consider a related class of noisy recurrent neural networks, REC[Fs #1 TJ.. The hypotheses in this class are similar to those in REC[F 7], except that outputs of (sigmoid) activa- tion functions are added with independent Gaussian random variables, /V .V(0, o²). Our main result demonstrates that, remarkably, the noisy class can be learned with a number of samples that is only logarithmic with respect to T.
Theorem 1 (Informal version of Theorem 15}. The sample complexity of PAC learning the class REC[Fa w. T) of noisy recurrent networks with respect to ramp loss is Õ(w (og(T/
One challenge of proving the above theorem is that the analysis involves dealing with random hypotheses. Therefore, unlike the usual arguments that bound the covering number of a set of deterministic maps with respect to the le distance, we study the covering number of a class of random maps with respect to the total variation distance. We then invoke some of the recently developed tools in Fathollah Pour and Ashtiani (2022) for bounding these covering numbers. Another challenge is deviating from the usual "unfolding method" and exploiting the fact that in recurrent models a fixed function/network is applied recursively.
The mere fact that learning REC[FE, 71I requires less samples compared to its non-noisy counterpart is not entirely unexpected. For classification of long sequences, however, the sample complexity gap is quite drastic (i.e., exponential). We argue that a logarithmic dependency on T is actually more realistic in practical situations: for finite precision machines, one can effectively break the ((T) barrier even for non-noisy networks. To see this, let us choose a to be numerically negligible number (e.g., smaller than the numerical precision of our computing device). In this case, the class of noisy and non-noisy networks become effectively the same when implemented on a device with finite numerical precision. But then our upper bound shows a mild logarithmic dependence on 1/a.
One caveat in the above argument is that the lower bound of Koiran and Sontag (1998) is proved for the 0-1 loss and perhaps not directly comparable to the setting of the upper bound which uses Lipeshitz surrogate loss. We address this by showing a comparable lower bound in the same setting.
Theorem 2 (Informal version of Theorem 10 with ramp loss is Ω (wT).
The sample complexity of PAC learning REC[Fu, TI
In the next section we introduce our notations and define the PAC learning problem. We state the lower bound in Section and the upper bound in Section 5 proof of our upper bound.
Sections 6 7 and provide a hige-level
Additional Related Work. Due to space constraints, we postpone the discussion of some additional related work to Appendix 9
2 Preliminaries
2.1 Notations
|| ||,|||2, and || denote the é,, l2, and loo norms of a vector x e Ed respectively. We denote the cardinality of a set S by [S]. The set of natural numbers smaller or equal to m is represented by
ilgnoring the dependence of the sample complexity the accuracy and confidence parameters.

---

[n]. A vector of all zeros is denoted by 02 - [0... oJ" E Rd. We use X C Rd as a domain set. We will study classes of vector-valued functions; a hypothesis is a Borel function Ie R., and hypothesis class is a set such hypotheses.
We find it useful to have an explicit notation here an overline for the random versions of the above definitions: X' is the set of all random variables defined over X' that admit a generalized density functior T E X a random variable in this set. To simplify this notation, we sometimes just write I E Idd rather than I E Rdd
f(x) is the random variable associated with pushforward of x under Borel map / R R.. We use f R' + IR to indicate that the mapping itself is random. Random hypotheses can be applied to both random and non-random inputs e.g.. f(z) and F(x class of random hypotheses is denoted by F.
Definition& 3 (Composition of Two Hypothesis Classes). We denote by h f the function h(f(z)) (assuming the range of f and the domain of h are compatible). The composition of two hypothesis classes F and H is defined by H F = {h f h E H. F). Composition of classes of random hypotheses is defined similarly by H o F = ( a h H. FF.
2.2 Feedforward neural networks
We will first define some classes associated with feedforward neural networks. Let Φ(x) Ite be the centered sigmoid function. & 12" + 1/2, 1/2]" is the element-wise sigmoid activation function defined by (((x(1) ..... (()))) (o(x!"), o(x()))).
Definition 4 (Single-Layer Sigmoid Neural Networks). The class of single-layer signooo neural networks with d inputs and outputs is defined by NETId, p] = {fw : R + 1-1/2,
fw(x) = &( 2), W E Rd
Based on Definition we can define the class of multi-layer (feedforward) neural networks (with w weights) composition of several single-layer networks. Note that the number of hidden neurons can be arbitrary as long as the total number of weights/parameters is w.
Definition (Multi-Layer Sigmoid Neural Networks). class of multi-layer sigmoid networks with Po inputs, Ps outputs, and weights that take inputs in [- 1/2, 1/2 is defined by
MNET(po, Pk, w UNETlPR-I.Dal o... NET/po, Pi]
where union is taken over all choices of (pI, Pon,Pa..... Pk-1) NK-1 that satisfy Di Pi-Pi-1 w. We say MNET[po. Pke w] is well-defined if the union is not empty.
Well-definedness basically means that po: Pk. and w are compatible. For simplicity, in the above definition we restricted the input domain to [-1/2, 1/2]4. This will help in defining the recurrent versions of these networks (since the input and output domains become compatible). However, our analysis can be easily extended to capture any bounded domain [- ))
2.3 Recursive application function and recurrent models
In this section define REC[F, I] which is the recurrent version of class FF for sequences of length T. Let u = (aI...., am) ) E n for m E N. We define First (v) = (a1,..., am-1) E 2 and Last (v) am X' as functions that return the first (T-1) be sequence of inputs, where 2(() E RR, and let f: RR - RR be a hypothesis/mapping. In the context of recurrent models, it is useful to define the recurrent application of f on this sequence. Note that out of the q dimensions of the range of f, q 1 of them are recurrent and therefore are fed back to the model. Basically, f (U, 1) will be the result of applying f on the first l elements of U (with recurrent feedback).
1 and the last dimensions of the
vector respectively. Let (0) (1)
Both discrete (by using Dirac delta function) and absolutely continuous random variables admit a generalized density function.
Technically. we consider 7(x)) to be ](0z). where on is random variable with Dirac delta measure
3

---

--
Fint (RR 1)
Fink (1R
Hest ((..))))
Fast (B(),))
LiMis (0) 13)
Figure 1: An example of a recurrent model in RECIF, T]. The first q dimensions of (U, 1)
concatenated with (t)) to form the input time t. The last dimension of ff f" 1) is taken to be the final output of the recurrent model.
Definition (Recurrent Application of a Function). Let U [
u()) u
(T] E TRPXT be
sequence of inpuls of length T, where (+) E Rp denotes the i-th column of U for 0 S i S T -
Let f be a (random) function from I. to RR, where = p q- 1. Moreover, define f (U,0) = (10n-1 f RexI x - - 129 and is defined as f (U,t) = (IFirst (5" (U,t- u(0] )
= Then, for any S t t T 1, the recursive application of f is denoted by
Now we are ready to define the (recurrent) hypothesis class RECIF,T), Each hypothesis in this class takes sequence of imput vectors, and applics a function f J recurrently on the elements of this sequence. The final output will be real number. We give the formal definition in the following: also see Figure for a visualization.
Definition 7 (Recurrent Class). Let 8,P.q q N. such that = p Let F be a class of functions from TR to IR9, The class of recurrent models with length that use functions in F (which we denote by recurring class) as their recurring block is defined by
REC[F, T = =hh: RPXT - IR ((()(U) Last
For example, REC[MNET(PO- Pke w), T] is the class of (real-valued) recurrent neural networks with length T that use MNET[Po, Pk: w] as their recurring block. We say that REC[MNETIpo Pk: w), 7] well-defined if MNET[p,, Pk, w] is well-defined and also the input/output dimensions are compati- ble (i.e., Po 2 Pk).
2.4 PAC learning with ramp loss
In this section we formulate the PAC learning model for classification with respect to the ramp loss. The use of ramp loss natural for classification (see e.g., [Boucheron al. (2005); Bartlett al.) (2006)) and the main features of the ramp loss that Lipschitzness. We start by introducing the ramp loss.
going exploit are boundedness and
Definition 8 (Ramp Loss). Let J X - R be hypothesis and let D be a distribution over X y Let (r.y) y) E X' x y, where y = {-1,1). The ramp loss of J with respect to margin parameter y is defined (,f,xz T. (-f(x) ((xx).)) where r.y is the ramp function defined by
x < k<ー
(x) = 1 -55050
0.
Definition 9 (Agnostic PAC Learning with Respect Ramp Loss). We say that a hypothesis class F of functions from X to R is agnostic PAC learnable with respect to ramp loss with margin parameter 7 > if there exists a learner and a function m (0. 1)² - N with the following property: For every distribution D over X' x 1-1, 1} and every e, E (0, 1). if S is set of m(c, 8) i.i.d. samples from D, then with probability least 1 (over the randomness of S) we have
B(Zzg)~ M4, (A(S), 3)] S inf B(z,g)D My (A(S), x, v) +
fEF

---

The sample complexity of PAC learning F with respect to ramp loss is denoted by m= (e, 8), which is the minimum number of samples required for learning FF (among all learners A). The definition of agnostic PAC learning with respect to ramp loss works for any value of y and when we are analyzing the sample complexity we consider be a fixed constant.
3 A lower bound for sample complexity of learning recurrent neural networks
In this section, we consider the sample complexity of PAC learning sigmoid recurrent neural networks with respect to ramp loss. Particularly, we state a lower bound on the sample complexity of the class REC|MNET(po: Pk. w), 7] of all sigmoid recurrent neural networks with length T that use multi-layer neural networks with w weights their recurring block. The main message is that this sample complexity grows at least linearly with T.
Theorem 10 (Sample Complexity Lower Bound for Recurrent Neural Networks). For every T
and w 2 19 there exists a well-defined class Hy = REC[MNET[Pu, Pk. w1, TJ and universal
constant > such that for every e, (0, 1/40) we have
m.H,. (c, C. [TT + log(1/8)
22
The proof of the above lower bound is based on similar result due to [Sontag et al. (1998). However, the argument in Sontag et al.] (1998) is for PAC learning with respect to 0-1 loss. To extend this result for the ramp loss, we construct a binary-valued class Fur { ((U) = sign(h(U)),, E Hwr where sign (x:) 1 if 2 O and sign (z) -1 if x < O. We prove that every function J E F... can be related to another function h E Hi. such that the ramp loss of almost equal to the zero-one loss of f. This is formalized in the following lemma, which is a key result in proving Theorem I0 The proof of Theorem 10 and Lemma I can be found in Appendix ??
Lemma 11. Let Hip REC/MNET(PO- Pe, w. T be a well-defined class and let Fw = { [-1 1/2 1/2|xxT + [-1,1} f(U)= = sign (h(U)), h E Hw). Then, for every distribution 'D over [-1/2, 1/2 x (11,1), n > 0, and every function f E Fw there exists a function h E H. such that BuU By (h, v) s Euay> [10-1 (f. U. v) + where 10- (f.U.y) = {f((U) + y).
Noisy recurrent neural networks
In this section, we will define classes of noisy recurrent neural networks. Let first define the singleton Gaussian noise class, which contains a single additive Gaussian noise function.
Definition 12 (The Gaussian Noise Class). The d-dimensional noise class with scale o 2 0 is denoted by Go.d {9r,a). Here, go.d RRd R&d is random function defined by go.d(z) where? & NO, o² La). When it is clear from the context we drop and write Go {go}.
The following is the noisy version of multi-layer networks in Definition 5 Basically, Gaussian noise composed (Definition 3) before each layer.
Definition 13 (Noisy Multi-Layer Sigmoid Neural Networks). The class of all noisy multi-layer sigmoid networks with w weights that take values in 1/2 as input and output values in [-1/2, 1/ defined by
MNET./Po. Pk. w] =
[Nn]=UUNETTNN NNETIPE-1.PPJ
To NET[P1 p2] o To NET(po, o
where 2 0 is scale of the Gaussian noise and the union is taken over all choices of (p1, P2. ... 1k-1) Nk-1 that satisfy Σ Pi-Pi-1 w.
Similar to the deterministic case, MNET Pk. w] said to be well-deffned if the union is not empty (i.e., Po. Ph and w are compatible). We can use Definition 7 to create recurrent versions of the above class. For example, RECIMNET, [yo, Pk: w), 7] is class of recurrent (and random) hypotheses for sequence of length T that use MNET, PR, w] as their recurring block. Again, similar to the deterministic case, we say JICIMNET,(PooP1 Pk. w), T] is well-defined if po: Pk and w compatible and MNET, [Po, Pk. w] is well-defined.
5

---

PAC learning noisy recurrent neural networks
In section 3 established an ((T)) lower bound the sample complexity of learning recurrent networks (I.e., RECIMNETIpo- Pk, w]. TJ)- In this section, we consider a related class (based on noisy recurrent neural networks) and show that the dependence of sample complexity on I is only Oloog T). In particular, Go REC[MNET, [Pu. Pk: w/, T can be regarded REC[MNET[Po Pk. wl, T Since it more standard to define PAC learnability for deterministic hypotheses, define the deterministic version of the above class by derandomizationf
(noisy) sibling of
Definition 14 (Derandomization by Expectation). Let F be a class of (random) functions RexT to R.. The derandomization of a function class F by expectation is defined as E(F) = {(h R
IR h (u) = B (w)] F).
We show that, contrary to Theorem 10 the sample complexity of PAC learning the (derandomized) class of noisy recurrent neural networks, (G, RECIMNET, [pu. Pk, wl. T],, grows at most loga- rithmically with T while still enjoys the same linear dependence on w. This is formalized in the following theorem (sce Appendix ?? for a proof).
Theorem 15 (Main Result). Let Qm Go o RECIMNET ppoo. Pk: w1, T be any well-defined class and assume E N,O < a < 1, e, E (0, 1). Then the sample complexity of learning Hy, (Qw)) is upper bounded by
max (c, 0
w log
wT
log
wT
+ log (1/6)
Ō
(
L/ logg + log((1/))
where Ô hides logarithmic
One feature of the above theorem the mild logarithmic dependence on 1/o. Therefore, we can take to be numerically negligible and still get significantly smaller sample complexity compared to the deterministic case for large T. Note that adding such small values of noise would not change the empirical outcome of RNNS on finite precision computers.
The milder (logarithmic) dependency on T is achieved by novel analysis that involves bounding the covering number of noisy recurrent networks with respect to the total variation distance. Also, instead of "unfolding" the network, we exploit the fact that the same function/typothesis is being used recurrently. We also want to emphasize that the above bound does not depend on the norms of weights of the network. Achieving this is challenging. since little bit of noise in a previous layer can change the output of the next layer drastically. The next few sections are dedicated to give a high-level proof of this theorem.
6 Covering numbers: the classical view
One of the main tools to derive sample complexity bounds for learning a class of functions is studying their covering numbers. In this section we formalize this classic tool.
Definition 16 (Covering Number). Let (X, p) be a metric space. A set A C X is e-covered by a set C. C A with respect to p. if for all A there exists C such that pla, c) < We denote by [ A, p) the cardinality of the smallest set C' that e-covers A and we refer to is as the e-covering number of A with respect to metric p.
The notion of covering number is defined with respect to a metric P. We now give the definition of extended metrics, which will use to define uniform covering numbers. The extended metrics can be seen as measures of distance between two hypotheses on a given input set.
(e.....,amm). (bi,.... bm) E x for m E N. The co-extended and ez-extended metrics over x are defined by poe, (u, v) sup supisism plaz, by) and ff (u, v) V E b.) respectively. We drop m and use 80e or م²a if it is clear from the context.
Definition 17 (Extended Metrics). Let (X, p) be metric space. Let
'One can also detine PAC learnability for a class of random hypotheses and get a similar result without taking the expectation. However, working with a deterministic class helps to contrast the result with that of Theorem 10

---

A useful property about extended metrics is that the oc-extended metric always upper bounds the Ez-extended metric. i.e., p²a v) S (u, v) for all u, v E X. Based on the above definition of extended metrics, we define the uniform covering number of hypothesis class with respect to ||-1|2-
Definition 18 (Uniform Covering Number with Respect to l1-112). Let F be a hypothesis class of functions from X y. For set of inputs S = {21. T2...., Im] X, we define the restriction of F to S as Fis = {(f(x1), f f222)..... f(rm) FFFF F ymm. The uniform e-covering
numbers of hypothesis class F with respect 11-112" 11-1122 are denoted by (e, m, ||- (2) and
(u,e, F, m, I1-1122) and are the maximum values of (e, Fis, 11.112 and (e, Fis, I1-11 ( over all S C with |S| = m, respectively.
The following theorem connects the notion of uniform covering number with PAC learning. It converts bound on the I|-112 uniform covering number of hypothesis class to a bound on the sample complexity of PAC learning the class; see Appendix ?? for more detailed discussion.
Theorem 19. Let be a class of functions from X' R. Then there exists an algorithm A with the following property: For every distribution 'D over X' x {-1,1) 1) and every c, E (0, 1), if S is a set of m Lid, samples from D, then with probability at least 1 (over the randomness of S),
E( Bby (A(S), w)]
24 vm
In 1n(2/8)
S inf (a by (f, v)l 16c + JEF
In Nu F, m. 11-1122) 6V
2m
Moreover, the algorithm that returns the function with the minimum error on S satisfies the above property (ie., Algorithm A such that A(S) = arg minser [S] > (aanes bn
7 Total variation covers for random hypotheses
One idea prove a generalization bound for noisy neural networks is to bound their covering numbers. However, noisy neural networks are random functions, and therefore their behaviours on a sample set cannot be directly compared. Instead, one can compare the output distributions of a random function on two sample sets, We therefore use the recently developed tools from Fathollah Pour and Ashtiani (2022) to define and study covering numbers for random hypotheses. These covering numbers are defined based on metrics between distributions. Specifically, our analysis is based on the notion of uniform covering number with respect to total variation distance.
Definition 20 (Total Variation Distance). Let μ and v denote two probability measures over X and let Ω be the Borel sigma-algebra over X. The TV distance between and v is defined by
dTV(H, = sup In(B) - v(B)..
Ben
Furthermore, if y and v have densities f and g then
/ (f(x) ((())) g(x))dr B
- / 15(x) - ((0) dr -
drv(H,V) sup BER
For two random variables T and ÿ with probability measures μ and sometimes abuse the notation and write drv (z, 8) instead of drv (H, For example, we write dr Fz(x)) in order to refer to the Total Variation (TV) distance between pushforwards of x under mappings fi and (mm))
(Tm)) to refer to the extended TV distance between mappings of the set S (xi,..., Imm by and f2. We use the extended total variation distance to define the uniform covering number for classes of random hypotheses.
f2. We also write der (TT)
Definition 21 (Uniform Covering Number for Classes of Random Hypotheses). Let F. be a class
of random hypotheses from X to y. For sel of random variables S = (II, I2, _Tmm C X, the restriction of F to S is defined as F 13 = [TF(TTT)
fEFI y" Let I' C X.
The uniform e-covering numbers of F with respect to and div is defined by
No F.m.ddy..)) sup SCT,
N diy
7

---

Some hypothesis classes that we analyze (e.g,, single-layer noisy neural networks) may have "global" total variation covers that do not depend on m. This will be addressed with the following notation: No F, 00, ,,, IT) limm-+so Nu J. m. p=, Ir). The set I in Definition 21 is used to define the input domain for which we want to find the covering number of a class of random hypotheses. For instance, some of the covers that we see are derived with respect to inputs with bounded domain or some need the input to be first smoothed by Gaussian noise. In this paper, we will be working with the following choices of
Xy.5,d to - Xa and r = Xz,d: the set of all random variables defined over R and [-B, Bja respectively, that admit a generalized density function. For example, address the set of random variables in |-1/2, 1/2
r = A PXT (U U =
Ou(r-1) (+))) TRP and r A..xT (()) E {- BJr), where 8y60 is the random variable -
I (0,30)
associated with Dirac delta measure on utt), Note that B.px C Apxr.
r = Go,d XB.d = [go.((T) I E xB all members of XB,d after being "smoothed" by adding (convolving the density with) Gaussian noise.
We mentioned in Section 6 that bound on the 11-112 uniform covering number can be connected
to a bound on sample complexity of PAC learning. We now show that a bound on diiv covering
number of a class of random hypotheses can be turned into a bound on the I1-11g covering number of its derandomized version and, thus, PAC learning it.
Theorem 22 (I1-112' Cover of (F) From dif Cover of F (Fathollah Pour and Ashtiani 2022 ). Let F be class of functions from R2XT to [-B, B).. Then for every e > 0 and m E N we have
Ny (2Bc E(F), m. 11 Nu(c,F, m, mm.ff. ApxT) S F,, 00, dF dF, A
8 Bounding the covering number of recurrent models
In Section we mentioned that finding a bound on covering number of hypothesis class is standard approach to bound its sample complexity. In the previous section, we introduced new notion of covering number with respect to total variation distance that was developed by Fathollah Pour and Ashtiani (2022). We showed how this notion can be related to PAC learning for classes of random hypotheses. In the following, we give an overview of the techniques used to find a bound on the divv covering number of the class of noisy recurrent models. We also discuss why this bound results in sample complexity that has a milder logarithmic dependency on T, compared to bounds proved by "unfolding" the recurrence and replacing the recurrent model with the fold composition.
One advantage of analyzing the uniform covering number with respect to TV distance that comes with a useful composition tool. The following theorem basically states that when two classes of hypotheses have bounded TV covers, their composition class has a bounded cover too. Note that such a result does not hold for the usual definition of covering number (e.g., Definition [8] see Fatholla Pour and Ashtiani (2022) for details.
Theorem 23 (TV Cover for Composition of Random Classes, Lemma 18 of Fathollah Pour and Ashtiani (2022). ). Let F. be class of random hypotheses from Rd to R2 and H be class of random hypotheses from Re to IR9, For any 61, 62 > O and m E N, denote N₁ = No (e1, F, m, d2 Xa).
Then we have,
Nu (61 + 62, H. F. m, dr Xs) Nu (E2, H, TV, X,) .N..
An approach to bound the TV uniform covering number of recurrent model RECIF, T) is to consider it as the T-fold composition F.F F.... F. One can then use a similar analysis to that of Fathollah Pour and Ashtiani (2022) to bound the covering number of the T-fold composition. Unfortunately, this approach fails capture the fact that a fixed function f E J applied recursively, and therefore results in sample complexity bound that grows at least linearly with T..
Instead, we take another approach to bound the covering number of recurrent models. Intuitively, notice that any function in the f'ld composite class F Fo... FF -fi ..... o fr fi...., fr
8

---

F} is determined by T functions from F. On the other hand, any function in REC[F, {h ((U)) = Last (U)) is only defined by one function in F and the capacity of this class must not be as large as the capacity of F ..... F. Interestingly, data processing inequality for total variation distance (Lemma ??) suggests that if two functions f and f are "globally" close to each other with respect to TV distance (i.e., drv ((()), S e for every T in the domain), then drv (f)( f(f())) s 2e (i.e., f and f f are also close each other). By applying the data processing inequality recursively, we can see that for the T-fold composition we have drv(fo... of...... f(z).
f(z)) I ET' The above approach results in the following theorem which bounds the e-covering number of noisy recurrent model with respect to TV distance by the covernc number its recurring class. Intuitively, this theorem helps us to bound the covering number of noisy recurrent models using the bounds obtained for their non-recurrent versions. Here, Gaussian noise is added to both the input of the model (i.e., Fo = F Fo 9o) and the output of the model (by composing with 9o).
Theorem 24 (TV Covering Number of To REC[F T) From To Fo). Let N such that + q 1. Let F be class of functions from XB. to Xn.9 and denote by Fa = F Gr, the class of composition with noise. Then we have
Nu (c.9a REC[F T), 00, drv A S No (c/T,gog o Fo, 00, XB.,)
For using this theorem, one needs to have finer c/ -covr for the recurring class. As we will see in the next section, this will translate into a mild logarithmic sample complexity dependence on T.
8.1 Covering noisy recurrent networks
An example of F, is the class MNET, Pk. w] of well-defined noisy multi-layer net- works (Definition 13 Theorem 24 suggests that bound on the covering number of 9, REC[MNET, [Po, pk; w], T' be found from bound for Gr MNET, Pk, w]. We use the following theorem as a bound for the class of single-layer noisy sigmoid networks together with theorem 23 to bound the covering number of Go MoET Pk, w] (see Appendix ??, Theorem ??). Theorem 25 (A TV Cover for Single-Layer Noisy Neural Networks, Theorem of Fathollhh Pour and Ashtiani 2.22)). For every p, d N. 0, < 5d/c we have
(5d-ea) 16/2 In
5c
log (e, Gow NETId, p), co, drv, Go,d o No.5,a) S p(d + 1) log 30
ca
In
6/2022
Interestingly, the above bound (on the logarithm of the covering number) logarithmic with respect to 1/c. We will extend this result to multi-layer noisy networks, and then apply Theorem 24 to obtain the following bound on the covering number noisy recurrent neural networks. Crucially, the dependency (of the logarithm of the covering number) on T is only logarithmic.
Theorem 26 (A TV Covering Number Bound for Noisy Sigmoid Recurrent Networks). Let T E N. For every c, a E (0, 1) and every well- dell-define class REC[MNET o (Po- Pk, w), T) we have
log No (e, o REC/MNETxIPO. Pk, w), U1, 0o, d A0.5.xT)
WT
WT )) = w log
T
=0 w log
log
Finally, we turn the above bound into I1-11/² covering number bound for the derandomized function (go RECIMNET,[Pu, Pk. W), by an application of Theorem 22 We then upper bound the sample complexity by the logarithm of covering number (see Theorem 19 and conclude Theorem [5] Limitations and future work. Our results are derived for sigmoid (basically bounded, monotone, and Lipschitz) activation functions. It is open whether such results can be proved for unbounded activation functions such as RELU. Our results are theoretical and we leave empirical evaluations on the performance of noisy networks to future work.

---

More on related work
There is plethora of work on generalization in neural networks. There a family of approaches
that aim to bound the VC-dimension of neural networks. (Baum and Haussler 1988; Maass
1994
Goldberg and Jerrum 1995 Vidyasagar 1997 Sontag et al. 1998; Koiran and Sontag, 1998
Bartlett et al.] 1998; Bartlett and Maass 2003 Bartlett et al. 2019). These approaches result in generalization bounds that are dependent on the number of parameters. Another family of approaches
are aimed at obtaining generalization bounds that are dependent on the norms of the weights and
Lipschitz continuity properties of the network (Bartlett) [9966 Anthony et al. 1999 Zhang [2022
Neyshabur et al., 2015; Bartlett et al., 2017
et al.
et al. 2018 Arora
et 2018 Nagarajan and Kolter [018]] Long and Sedghi 2020j. has been observed that these
generalization bounds are usually vacuous in practice. One speculation is that the implicit bias of
gradient descent (Gunasekar al. 2017 Arora al.) 2019: Ji et al. 2020 Chizat and Bach 2020 Ji
and Telgarsky 2021) can lead to benign overfitting (Belkin et al., 2018 8 2019 Bartlett et al. 2020 2021). It has also been conjectured that uniform convergence theory may not be able to fully capture the performance of neural networks in practice (Nagarajan and Kolter 2019 Zhang et al. 102T).
has been shown that there are nata-dependent approaches that can achieve non- vacuouys bounds (Dziugaite and Roy 2017 Zhou et al. [2019] Negrea et al., (2019). There are also other approaches that are independent of data (Arora et al. 2018); see Fathollah Pour and Ashtiani (022)) for more
details.
Adding different types of noise such as dropout noise (Srivastava et al. 2014), DropConnect (Wan) et al.] 2013), and Denoising AutoEncoders (Vincent et al. 2008) are shown to be helpful in training neural networks. [Wang et al. (2019) and Gao and Zhou (2016) theoretically analyze the generalization under dropout noise. More recently, Fathollah Pour and Ashtiani (2022) developed framework to study the generalization of classes of noisy hypotheses and show that adding noise to the output of neurons in network can be helpful in generalization. Dim et al. 1996) show that additive and multiplicative noise can help speed up the convergence of RNNs on local minima surfaces. Recently, Lim et al. (2021) showed that noisy RNNs are more stable and robust to input perturbations by formalizing the regularization effects of noise.
Another line of work focuses on the generalization of neural network that are trained with Stochastic Gradient Descent (SGD) or its noisy variant Stochastic Gradient Langevin Descent (SGLD) (Russo)
and Zou, 2016 Xu and Raginsky, [2017, Russo and Zou, 2019; Steinke and Zakynthinou 20200]
Raginsky et al. 2017 Haghiffm et al., 2020 Neu et al. 2021 Zhao et al. (2020) analyze the memory properties of recurrent networks and how well they can remember the input sequence. TTu et al. (2020)
study the generalization of RNN by analyzing the Fisher-Rat Rao norm of weights, which they obtain from the gradients of the network. They offer generalization bounds that can potentially become polynomial in T. Allen-Zhn and Li (2019) analyze the change in output through the dynamics of training RNNs and prove generalization bounds for recurrent networks that are again polynomial in T.
References
Zeyuan Allen-Zhu and Yuanzhi Li. Can sgd learn recurrent neural networks with provable general- ization? Advances in Neural Information Processing Systems, 32, 2019.
Martin Anthony, Peter L Bartlett, Peter L Bartlett, et al. Neural network learning: Theoretical foundations, volume 9. cambridge university press Cambridge, 1999.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 2018
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Peter Bartlett. For valid generalization the size of the weights is more important than the size of the network. Advances in neural information processing systems, 9, 1996.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
10

---

Peter L Bartlett and Wolfgang Maass. Vapnik-chervonenkis dimension of neural nets. The handbook of brain theory and neural networks, pages 1188-1192, 2003.
Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(4)3):38--556 2006.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. ppectrally-normaliin margin bounds for neural networks. Advances in neural information processing systems, 2017.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, (122))222220111 2019.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear
regression. Proceedings of the National Academy of Sciences, 1177449::0033-300777, 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
Eric Baum and David Haussler. What size net gives valid generalization? Advances in neural information processing systems, 1, 1988.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31, 2018.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-377 375, 2005.
Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of family of recurrent neural networks. In International Conference on Artificial Intelligence and Statistics, pages 1233-1243.
PMLR, 2020.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338, PMLR, 2020.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
Alireza F. Pour and Hassan Ashtiani. On the role of noise in the sample complexity of learning recurrent neural networks: Exponential gaps for long sequences. arXiv preprint S1v:2300518423. 2023.
Alireza Fathollah Pour and Hassan Ashtiani. Benefits of additive noise in composing classes with bounded capacity. Advances in Neural Information Processing Systems, 35:32709-32722, 2022.
Wei Gao and Zhi-Hua Zhou. Dropout rademacher complexity of deep neural networks. Science China Information Sciences, (97):1112, 2016.
Paul W Goldberg and Mark R Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18(2):131-148, 1995.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independee sample complexity of
neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018
Alex Graves, Aldel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. 2013 IEEE international conference on acoustics, speech and signal processing, pages 6645-6649, Icce, 2013.
11

---

Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 05:9925-99355 2020.
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19:1-44, 2018.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-804. PMLR, 2021.
Ziwei Ji, Miroslav Dudík, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pages 2109-2136. PMLR, 2020.
Kam-Chuen Jim, C Lee Giles, and Bill G Horne. An analysis of noise in recurrent neural networks: convergence and generalization. IEEE Transactions on neural networks, 766):1224-1438, 1996.
Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descriptions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3128- 3137, 2015.
Pascal Koiran and Eduardo D Sontag. Vapmik-chervonenkis dimension of recurrent neural networks. Discrete Applied Mathematics, 86(1):63-79, 1998.
Soon Hoe Lim, N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney. Noisy recurrent neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Philip M Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. In International Conference on Learning Representations, 2020.
Wolfgang Maass. Neural nets with superlinear vc-dimension. Neural Computation, 6(5):877-884, 1994.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep net- works via generalizing noise-resilience. In International Conference on Learning Representations, 2018.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-theorrtie generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. iilommation-thhorett generalization bounds for stochastic gradient descent. In Conference on Learning Theory, pages 1556--3555. PMLR, 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Repre- sentations, 2018.
Yao Qin, Dongjin Song, Haifeng Cheng, Wei Cheng, Guofei Jiang, and Garrison W Cottrell. A dual-stage attention-based recurrent neural network for time series prediction. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 2627-2633, 2017.
12

---

Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory, In Artificial Intelligence and Statistics, pages 1232- 1240. PMLR, 2016.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions Information Theory, 66(1):302-324 2019.
Eduardo D Sontag al. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96, 1998.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine 2014.
learning research,
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pages 3437-3452. PMLR, 2020.
Ilya Sutskever, Oriol Vinyals, and Quoc Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
Zhuozhuo Tu, Fengxiang He, and Dacheng Tao. Understanding generalization in recurrent neural networks. In International Conference on Learning Representations, 2020.
Mathukumalli Vidyasagar. A theory of learning and generalization: with applications to neural networks and control systems. Springer-Vert Verlag, 1997.
Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pages 1096-1103, 2008.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International conference on machine learning, pages 1058-1066. PMLR, 2013.
Haotian Wang, Wenjing Yang, Zhenyu Zhao, Tingjin Luo, Ji Wang. and Yuhua Tang. Rademacher dropout: An adaptive dropout for deep neural network via optimizing generalization gap. Neuro- computing, 357:177-187, 2019.
Aolin Xu and Maxim Raginsky. information-theorrtie analysis of generalization capability of learning algorithms, Advances in Neural Information Processing Systems, 30, 2017.
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.
Jiong Zhang, Qi Lei, and Inderjit Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In International Conference on Machine Learning, pages 5806-5814. PMLR, 2018.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550, 2002.
Jingyu Zhao, Feiqing Huang, Jia Lv, Yanjie Duan, Zhen Qin, Guodong Li, and Guangjian Tian. Do mn and Istm have long memory? In International Conference Machine Learning, pages 11365-11375. PMLR, 2020.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan Adams, and Peter Orbanz. generalization bounds at the imagenet scale: pac-bayesian compression approach. In International Conference on Learning Representations (ICLR), 2019.
13


Reviews:
[{"review_id": "8BcIKmEVx7", "reviewer": "Reviewer_Ei2R", "summary": "In this paper, the authors consider a class of noisy recurrent neural networks under the ramp loss setting, and prove that the noisy class can be learned with $O(w \\log (T/\\sigma))$, where $w$ is the width, $T$ is the length of the sequence, and $\\sigma$ is noise variance. \n\nThe derived results demonstrate the sample effiency when compared to the standard noiseless case. \nThe proof is based on the result of covering number of a class of random maps under the TV distance.", "questions": "See the above", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the sample complexity $O(w \\log (T/\\sigma))$ is proved for such noise RNN under the ramp loss\n- the covering number under the TV distance is given", "weaknesses": "- The motivation of using ramp loss is unclear to me and quite weak. For example, ramp loss is non-convex and not commonly used in practice. I understand that the ramp loss will be quite close to the 0-1 loss, and thus the derivation would be relatively easier, e.g., Lemma 11. Nevertheless, it decreases the technical difficulty as well as the motivation.\n\n- The used techique is from (Fathollah Pour and Ashtiani 2022) on the covering number of a class of random maps under the TV distance. Their results have already applied to shallow and deeper NNs. The contribution appears not very significant under a somehow RNN with ramp loss. When checking the proof in a high level way, the key part, Lemma 11, aims to build the connection between the ramp loss and the 0-1 loss.\n\n- According to the derived sample complexity, it shows that, under a larger noise level, this noisy class can be learned with fewer samples. It makes sense because noise (gradually become the main component) can be easier to be learned than the data. However, this result somethimes is not enough in my view. Because a larger noise injection would lead to a worse performance. Solely adding noise result in nothing. I think this requires more detailed discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and feedback. In the following, we address the concerns and questions mentioned in the review.\n\n**Response to Weaknesses 1.** As we mentioned in Line 139, the only features of the ramp loss that we use to derive the upper bound are its Lipschitzness and boundedness. Our results are more general and work for any other loss that has these properties. It is also common in the literature to assume these two assumptions for the loss function when the generalization of neural networks are analyzed theoretically. Otherwise, if the loss function is unbounded, it would be impossible to guarantee generalization without making additional assumptions on the norms of the weights of network.\n\nFor the lower bound, we used the specific choice of ramp loss to be concrete in our theorem statements and to be able to contrast it with the upper bound. In fact, the constructions in Lemma 11 and, consequently, the lower bound in Theorem 10 only rely on the above two properties and an additional property that the loss function $l(z)$ converges to $0$ as $z$ goes to $\\infty$ and converges to $1$ as $z$ goes to $-\\infty$, which is again natural in the analysis of neural networks. \n\n**Response to Weaknesses 2.** We would like to emphasize that Theorem 15 (main upper bound result) is based on the result of Theorem 24 which is novel and not present in Fathollah Pour and Ashtiani (2022) (FA22). As we discussed in Lines 312-331, simply using the result of FA22 will give a loose (linear) upper bound in terms of the length of the sequence. Therefore, the bound would not be better than those of the existing literature that simply \"unfold the recurrence\" and analyze the recurrent network as a larger and more complex class. On the other hand, we prove that with a more careful analysis of the noisy function it is possible to take into account the fact that the same fixed function is being applied recursively. Using the new analysis that we offer for any recurrent model, we conclude tighter generalization bound for RNNs which is logarithmic in $T$. When contrasted with our (linear) lower bound, we get the exponential gap as a surprising result. There are other nuances in the proofs that are reflected in the (relatively long) supplementary material.\n\n**Response to Weaknesses 3.** Proving a sample complexity bound for noisy RNNs that is logarithmic in $T$ is one of the main contributions of our paper and it was not, to the best of our knowledge, present in the literature before. We agree that intuitively, it is true and not surprising that adding noise reduces the complexity of the class of networks and results in tighter generalization bounds. However, what is surprising is the fact that even a negligible amount of noise is enough to enable the noisy analysis. For example if the neural network is implemented on a device with finite precision, then one can set $\\sigma=10^{-240}$ and get a generalization bound which is logarithmic in $T$, without sacrificing any accuracy. These discussion are also included in Lines 61-66 and 210-213."}, {"review_id": "DKbnhI1Y63", "reviewer": "Reviewer_hjDk", "summary": "This paper studies learning recurrent neural networks with sigmoid activations, where a small amount of noise of magnitude sigma is added to each layer. This paper shows that there is a log(T/sigma) scaling of the sample complexity with the number of recurrent compositions.\n\n This is surprising because, without the noise, there is a linear in T scaling of the sample complexity. Furthermore, the quantity of noise can be very small, since the log(1/sigma) dependence is mild.", "questions": "* Is the noise $\\mathcal{G}_{\\sigma}$ in Definition 13 reused, or fresh noise on each layer? \n\n\n* There seem to be some minor technical issues with the proof of Theorem 10 as stated. In the proof of Lemma 11 (restated as Lemma 32), the authors on line 604 define $z$. The authors write the definition of $z$ as\n$$z = \\min_b \\arg\\max_{0 < x < 1/2} P[|Last(b^R(U,T-1))| \\geq x] \\geq 1-\\eta.$$\nThis is nonstandard notation and it is unclear how to parse it. The authors state that \"intuitively, z is the largest possible value such that \"\n$$P[-z < Last(b^R(U,T-1)) < z] < \\eta$$ Considering this and the remainder of the proof, I am assuming that the authors meant\n$$z = \\max \\\\{x \\in (0,1/2) :  P[|Last(b^R(U,T-1))| \\geq x] \\geq 1-\\eta \\mbox{ for all } b\\\\}.$$\nHowever, $z$ may not be well-defined because the maximum might not exist. Consider the network $b$ that sends any input to $Last(b^R(U,T-1)) = 0$ almost surely. Then no $x \\in (0,1/2)$ is valid for the above problem -- we would have to take $x = 0$, which would lead to an issue with the proof since then $z = 0$.\n\n* How does the construction for Theorem 10 break if sigma=1/T^C magnitude noise is added for some large constant C? Your Theorem 26 would predict T*polylog(T) sample complexity, ao the construction in Theorem 10 should break, but I don't see exactly how. Could you please provide some intuition?\n\nTypos:\n* Appendix C, Proof of Theorem 10, have [l]^{\\gamma} and [l]^{0-1}, when it should be [l^{gamma}] and [l^{0-1}]\n* Statement of Theorem 23, display math between lines 311 and 312. Why is there \". N_1\" in the expression? Is it supposed to be times N_1?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is notationally heavy, but is clearly written and was therefore easy to follow. The comparison with past works was good, and I felt that the main result was surprising.", "weaknesses": "\nFrom a technical point of view:\n* The proof of Theorem 10 (the sample complexity lower bound for learning with the Ramp Loss) is effectively the same as Koiran and Sontag (1998), who proved it for the 0-1 loss. The main observation is that neural networks with sigmoid activations can be forced to output approximately 0-1 valued functions by rescaling the final layer weights. And therefore the ramp loss is approximately equal to the 0-1 loss.\n\n* Most of the steps in the proof of Theorem 26 draw heavily on the work of \"Benefits of Additive Noise in Composing Classes with Bounded Capacity\" by Fathollah Pour and Ashtiani, 2022. The main technical novelty seems to be in Theorem 24, which gives an inequality for the TV covering number under composition. Did I understand correctly that this is the main new element?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their careful assessment of the paper and we appreciate their helpful comments. The questions and concerns mentioned by the reviewer are discussed in the following.\n\n**Response to Weaknesses.** Yes, the key technical contribution is to prove a general result on the covering number of recurrent models based on the recurring class, and a sample complexity upper bound that is logarithmic in $T$ (hence, the surprising exponential gap). On the other hand, most (if not all) of the techniques used in the literature (for non-noisy networks) are based on \"unfolding the recurrence\" and result in a linear dependence on $T$. In fact, as we showed in the lower bound, for non-noisy networks, getting a (super-)linear upper bound is inevitable.\n\nWe would like to add that simply using the framework of Fathollah Pour and Ashtiani (2022) will again give a linear dependence on $T$. Therefore, we had to use a new proof technique to be able to exploit the fact that in RNNs, a fixed function is being reused recursively. With this and other nuances in the proof (e.g., handling the new data that is inputted to the network in every recurrence) we were able to prove the sub-linear (logarithmic upper) bound.\n\n**Response to Questions 1.** The noise is i.i.d. in and fresh sample is used in each layer.\n\n**Response to Questions 2.**  We thank the reviewer for bringing this to our attention! In fact, there is a mistake in the current proof but can be fixed easily. In short, instead of defining a general value of $c$, we can define a specific value $c_b$ for any given network $b$ to resolve the issue mentioned by the reviewer.\n\nTo see this, we should have defined $z_b$ specifically for any network $b$ as $z_b = \\sup \\\\{ 0\\leq x<1/2:\\mathbb{P}{\\left|\\text{Last}{b^R(U,T-1)}\\right|  \\geq x} \\geq 1-\\eta \\\\}$. For any $b$ and its corresponding $f \\in \\mathcal{F_w}$ if $z_b>0$ we can multiply the last row of the weight matrix of the last layer by $c_b=\\phi^{-1}(\\gamma)/\\phi^{-1}(z_b)$. In case $z_b=0$, we do not need to change any weights and we let $c_b=1$. We can conclude for the same function $b$ and the corresponding $h_b = \\text{Last}(b^R(U,T-1)) \\in \\mathcal{H_w}$ we have $\\\\mathbb{E}_\\{(U,y)\\\\sim \\\\mathcal{D}}{l_\\{\\\\gamma} (h\\_b,U,y)} \\\\leq \\\\mathbb{E}_\\{(U,y)\\\\sim \\\\mathcal{D}}{l^{0-1}(f,U,y)} + \\\\eta$ as desired because the ramp loss and the $0-1$ loss output the same value with probability more than $1-\\eta$. Therefore, the result of Lemma 11 and Theorem 10 are correct and still hold. We make sure to modify the proof of Lemma 11 and make it exact in the next versions of this paper.\n\n**Response to Questions 3.** We hope we have understood the question correctly and if the reviewer is asking why if we set $\\sigma$ to be inverse exponentially in $T$, then the upper bound in Theorem 15 becomes $T*polylog T$ but Theorem 10 suggests a lower bound of $\\Omega(T)$. We want to emphasize that this is not a contradiction and the construction in Theorem 10 does not break. We would only have a loose upper bound that is not better than the lower bound in Theorem 10. The intuition behind having the loose upper bound when $\\sigma\\rightarrow 0$ is that we are analyzing the covering number with respect to TV distance which we show is sufficient for learning but it is not necessary in general. Intuitively, the noise is smoothing out the output and makes sure that with a small change in the weights of network the output distributions do not become very different, i.e., have small TV distance. However, when $\\sigma\\rightarrow 0$, the output distributions are almost close to the Dirac delta measures and the TV distance is almost equal to $1$, so we do not quite get the benefits that we wanted from adding noise. We showed that the sample complexity has mild logarithmic dependence on $1/\\sigma$, so for moderately small values of $\\sigma$ we would still get a tighter generalization bound for noisy networks. However, when $\\sigma$ is set to be so small, one would lose the benefits of additive noise. In this regime, one can basically use the basic (super-)linear bounds for non-noisy RNNs.\n\n**Typos.** Yes, in the statement of Theorem 23 it is supposed to be times $N_1$. We thank the reviewer for noticing the typos and make sure that we will fix it in future versions of the paper."}, {"review_id": "qbkYlgOVse", "reviewer": "Reviewer_KR7t", "summary": "This work studies the sample complexity of PAC learning noisy recurrent neural networks with respect to the ramp loss. Noisy recurrent networks are defined as multi-layered feed forward networks with sigmoid activation where independent mean-zero Gaussian noise is added to the activation.\n\nThe main result is that one can learn these noisy networks with sample complexity $\\tilde{O}(\\frac{w\\log(T/\\sigma) + \\log(1/\\delta)}{\\epsilon^2})$ (Theorem 15). Though different in terms of loss function and noise assumption with prior work, the bound notably avoids any dependence on the norms of the weights, which was common in upper bounds in prior work. These results are much more intriguing once contrasted to its non-noisy counterpart, i.e., the fact that non-noisy PAC learning has a lower bound of $\\Omega(\\frac{wT+\\log(1/\\delta)}{\\epsilon^2})$ (Theorem 10), which exhibits linear dependence on $T$ as opposed to $\\log(T)$ as in the noisy case.\n\nThe techniques used to prove the upper bound may be of independent interest to the PAC learning community. The authors use techniques derived from Fathollah Pour and Ashtiani (2022) to study covering numbers of random hypotheses and extend these tools so that their analysis is based on uniform covering number with respect to total variation distance.", "questions": "- On one hand, learning noisy networks being easier than learning clean networks is surprising since it's noisier. Yet, it may be the case that, by adding noise (smaller signal-to-noise ratio), it becomes easier to learn as more hypotheses may seem to plausible (as if blurring an image). Is this why the noise is helping the learner?\n- What is the main reason for studying the ramp loss?", "limitations": "The paper is clear with limitations and comparison to prior/future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper shows an interesting contrast between learning noisy vs. clean recurrent neural networks. There is surprisingly an exponential gap in sample complexity w.r.t. $T$ and that noisy networks are easier to learn. This gives way to the suggestion that learning clean networks can \"bypass\" the existing hardness result by assuming there is an infinitesimally small noise $\\sigma$ close to 0 for the clean network, allowing the actual sample complexity upper bound be smaller in case of finite precision machines.\n- The proof techniques are interesting as the paper works with random hypotheses and establishing sample complexity via covering numbers under such randomness.", "weaknesses": "- The motivation to study noisy recurrent neural networks, as it is defined in this paper, is unclear to me. The formulation is similar to a noisy dynamical system but it is unclear why such noise assumption would be natural here for neural networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their assessment and feedback. We address the concerns and questions raised by the reviewer in the following.\n\n**Response to Weaknesses.** Using noise in training neural networks is a natural heuristic to avoid overfitting and has been used in various scenarios (e.g., in denoising autoencoders, drop-out noise, noisy RNNs, etc.). For RNNs, the issue of overfitting is more serious especially for learning from long sequences. Our study can quantify the effect of noise for generalization in RNNs.\n\nBut perhaps more importantly, we use noisy RNNs as a \"proof technique\". As discussed in Lines 61-66 and 210-213, in practice we can set the amount of noise so negligible that when implemented on a device with finite precision the network performs almost similar to the natural non-noisy version, without sacrificing the performance. In other words, our analysis shows that there is a stark difference between finite precision machines and true real-valued machines when it comes to training RNNs.\n\nOn a more technical level, adding noise to the network makes it possible to use the TV covering number analysis which comes with a useful composition theorem. It makes it possible to use new techniques and exploit the fact that the same function in being applied recursively and get a sample complexity bound that is exponentially smaller than the non-noisy version. \n\n**Response to Question 1.** Although it may be intuitive that noise makes the class less complex, one of our contributions is actually proving a bound on the complexity of noisy recurrent models by using new techniques and analysis for random functions. It is worth mentioning that we are analyzing the sample complexity of PAC learning this class; we want to find the smallest number of samples required to make sure that, for any data generating distribution, the error of the trained/returned network $\\hat{f}\\in\\overline{\\mathcal{F}}$ is comparable with the smallest expected error that is achievable by a noisy network from the same class $\\overline{\\mathcal{F}}$, i.e., $\\arg\\min_{f\\in\\overline{\\mathcal{F}}}\\mathbb{E}{l^{\\gamma}(f,x,y)}$. It may seem intuitive that by adding noise to a single classifier $f$ we can hope to reduce its overfitting and bound the difference between its empirical and expected error. However, it is not obvious and immediate that the expected error of returned classifier $\\hat{f}$ is close to the minimum possible expected error over the class of noisy networks, i.e., whether $\\mathbb{E}{l^{\\gamma}(\\hat{f},x,y)} \\leq \\min_{f\\in\\overline{\\mathcal{F}}}\\mathbb{E}{l^{\\gamma}(f,x,y)} + \\epsilon$ with high probability, and if we can guarantee PAC learning with smaller sample complexity. Our main contribution is a novel technique for studying the complexity of noisy RNNs and proving that the sample complexity of PAC learning them is logarithmic in $T$.\n\n**Response to Question 2.** As mentioned in Line 139, the main features of the ramp loss that we use are the Lipschitzness and boundedness, which are common in the literature of neural networks for analyzing the sample complexity. Otherwise, if the loss function is unbounded, it would be impossible to guarantee generalization for networks with unbounded weights. Our sample complexity analysis for noisy networks is more general and works for any loss function that has the above properties. We chose to use ramp loss because we wanted to have concrete theorem statements and to be able to contrast the upper bound of noisy network with the lower bound of the non-noisy networks."}, {"review_id": "h9whY1Blre", "reviewer": "Reviewer_9rJ1", "summary": "The authors consider the class of noisy multi-layered sigmoid recurrent neural networks, noisy meaning that noise is added to the output of each neuron in the network. They prove that the sample complexity of noisy is significantly better than non-noisy one with one clean upper bound and one clean lower bound.", "questions": "How much does noise affect expressive power?", "limitations": "The authors adequately addressed most of the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Clear writing\n2. Well organised presentation\n3. Reasonable assumptions on an important model\n4. Studied multilayer neural networks, making a complete story.\n5. Interesting technique TV Cover, handy for composition classes", "weaknesses": "Here are some minor weaknesses.\n\n1. The authors could have discussed more about the practical implications. It occurs to me that adding noise might be one of the keys to next generation AI now that deep learning is currently struggling with sampling complexity.\n2. Would be better if there could be discussion about expressive power.\n3. sigmoid not RELU.\n4. lack of experimental results", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions and comments. We discuss the questions and concerns mentioned by the reviewer in the following.\n\n**Response to weaknesses.** We agree with the reviewer that practical result can back up the results of the paper and we hope to have this as a future work. Also, extending the results to ReLU networks rather than the sigmoid function is a future direction for this work that can increase its generality.\n\n**Response to Question.** This is a very good question. We want to mention that as discussed in the paper our results also work in the regime where we have negligble amounts of noise and the noise is only required to enable the analysis. So if we are considering the current computers with finite precision, the noisy and non-noisy networks perform almost the same when implemented on them and we can get exponential improvements in the sample complexity without losing any expressive power. A related discussion is also included in Lines 61-66 and 210-213. We think analyzing the expressive power for the regime where the noise is not negligible and therefore these two classes may have different performances is an interesting future direction.\n"}]

Author rebuttal:

Meta-review: This paper studies the sample complexity of learning recurrent neural networks. The main claim is that when some noise is added to the output of each neuron, the sample complexity scales logarithmically in the sequence length T instead of linearly in the case of no noise. Although usually neural networks do not have any noise added, there has been interest in the setting with stochastic outputs for various reasons (e.g. related to generalization/pac-bayes theory). Overall the reviewers had a positive view of this contribution, and I recommend acceptance.
Decision: Accept (poster)