On the theoretical limit of gradient descent for Simple Recurrent Neural Networks with finite precision
Authors: Volodimir Mitarchuk
Rémi Emonet
Remi Eyraud
Amaury Habrard
Venue: Accepted by TMLR ()

Abstract: Despite their great practical successes, the understanding of neural network behavior is still
a topical research issue. In particular, the class of functions learnable in the context of a
finite precision configuration is an open question. In this paper, we propose to study the
limits of gradient descent when such a configuration is set for the class of Simple Recurrent
Networks (SRN). We exhibit conditions under which the gradient descend will provably fail.
We also design a class of SRN based on Deterministic finite State Automata (DFA) that
fulfills the failure requirements. The definition of this class is constructive: we propose an
algorithm that, from any DFA, constructs a SRN that computes exactly the same function,
a result of interest by its own.

Published in Transactions on Machine Learning Research (12/2024)
On the theoretical limit of gradient descent for Simple Re- current Neural Networks with finite precision *
Volodimir Mitarchuk
volodimór mitarchuk@unioo-t etienne. fr remi, emonet@@mioo-sttt etienne. fr remi, www.ed etienne. fr hanoury.habardd@uiie etienne. Université Jean Monnet Saint-Etiemee CNRS, Institut d' d'Optique Graduate School, Inria, Laboratoire Hubert Curien
Rémi Emonet.
Rémi Eyraud
Amaury Habrard
UMR 5516, F-42023, Saint-Elienen France
and Institut Universitaire de France (IUF)
Reviewed OpenReview: https: o/tp::///peenrvveee. net/ ret.//eviiisssoddeoooe (drp:
Abstract
Despite their great practical successes, the understanding of neural network behavior is still a topical research issue. In particular, the class of functions learnable in the context of finite precision configuration is an open question. In this paper, we propose to study the limits of gradient descent when such a configuration set for the class of Simple Recurrent Networks (SRNs). We exhibit conditions under which the gradient descent will provably fail. We also design a class of SRN based on Deterministic finite State Automata (DFA) that fulfills the failure requirements. The definition of this class is constructive: propose algorithm that, from any DEA, constructs an SRN that computes exactly the same function, result of interest on its own.
1 Introduction
One of the main challenges Machine Learning is facing is the lack of theoretical understanding of the reasons of the practical successes of deep learning. Indeed, whole research fields have been revolutionized by the boom of deep neural networks, from signal (Mchrish et al. 2023) to image processing (Li et al. 2024) including finance (Zhang et al. 2021 for instance, but much remains to be done to fully understand their capabilities and limits.
In this paper, we propose study this issue in the context of Recurrent Neural Networks (RNN). As with neural networks in general, we can identify at least two ways of interpreting capabilities and limits. The first one is to analyze the expressivity, that is, the class of functions class of models can compute. Within this direction of research a notorious theoretical result states that vanilla RNN, the SRN (Elman) 1990), are able to compute any Turing machine (Siegelmann & Sontag. 1992). Though of great interest, this theorem says little about the models used nowadays: its proof relies on the use of unbounded time and requires neurons of has been shown (Chung Siegelmann, 2021) that possible to maintain the Turing infinite precision. SRN in finite precision if the algorithm has access to potentially unbounded amount completeness for an of neurons. A similar result. is proposed by Stogin et al. (2024) with particular emphasis on the provable stability of the proposed architecture. When it comes to conventional RNN architectures, those with fixed number of neurons, Weiss et al. (2018) practically shows that the expressivity drastically decreases for all types of RNNs, most of them fall in classes equivalent to the expressivity of finite state machines. Merrill et al. (2020) theorize the phenomenon of saturation and derive a hierarchy of RNN architectures. The saturation in RNN occurs when the bounded activation function composing the RNN (the sigmoidal function of tanh) are pushed to their boundaries and thus produce binary outputs. Despite the interest of such a result, the saturation formalized by Merrill et al. (2020) unrealistic because it is based on the notion of limit to be performed at every iteration.
*This work supported part by the ANR TAUD (ANR-20-CF22-0020)

---

Published in Transactions on Machine Learning Research (12/2024)
Another way of establishing RNN limitations and capabilities is to investigate what can be achieved in the context of statistical learning. In this area of research the most notorious phenomenon to be studied is the one of vanishing gradient. [engiio et al. (1994) and HHchreiter (1998) demonstrate that long dependencies in the SRN computations are very difficult to be learned by gradient descent. Issues with the vanishing/ (xxpooiin///ppoiing gradient were so common that Hochreiter & Schmidhuber (1997) proposed the LSTM, a RNN architecture designed to bypass these issues. Algorithmic solutions such as gradient clipping or smoothing were also considered in the literature (Pascanu et al. 2013) as well as avoiding particular regions of the parameter space [Ribeiro et al. 2020).
Our work fills a theoretical gap at the intersection of the above-mentioned fields of research. We explore the limitations of training RNNs by Gradient Descent (GD) in the context of finite precision. To the best of our knowledge, this is the first study of its kind for RNNs. We built on the saturation assumption and the finite precision arithmetic's ' to explicitly delimit regions of parameter space that camnot be reached by classical GD with bounded learning rate. We thus theoretically prove that it is impossible to learn saturated SRNs. We also demonstrate that in finite precision the saturation in RNNs (based on sigmoidal or hyperbolic tangent function) can be defined without any notion of limit, hence RNNs can exhibit binary behavior with bounded parameters. And finally, leveraging the saluration in finite precision we exhibit a way of accurately defining SRN parameters, allowing the SRN to simulate a finite state machine. Therefore, in this way we demonstrate that the non-learnable region by GD for SRNs contains an interesting and expressive class of functions, the one of Deterministic Finite State Automaton (DFA). More formally our contributions are:
We prove a theorem stating that saturated SRNs cannot be learned by gradient descent. The theorem shows that a subset of gradient parameters will be too small to have an effect during the gradient descent and thus prevent the algorithm to reach the optimum.
We conduct experiments that validate the theorem, and that show that the task of learning saturated SRN is even harder than predicted by the theory.
We provide an algorithm that, given a Deterministic Finite State Automaton (DFA), constructs a saturated SRN that will simulate the DFA. The algorithm is an extension of the algorithm provided by Minsky 1967 to SRN in finite precision.
The article is structured as follows: Section 2 of this paper is devoted for notations and the introduction of different necessary notions for the proofs. Section 3 contains the secondary but necessary result on the stability to noise in saturated SRNs. In Section I we develop the arguments towards the gradient descent failure in finite precision, as well as a detailed example of the application of the theorem on a small SRN. Section 5 details the algorithm that for a given DFA outputs a saturated SRN capable of simulating the DFA. Section f is the experimental section where we provide empirical evidence that our theory is valid. And the final S
contains the conclusive discussion with possible extensions of our result, future works and related works on the limitation of gradient descent in finite precision.
2 Preliminaries
In this section are enumerated all the notations and elementary operations that are used in this paper.
2.1 Elements of Linear Algebra
Numbers, besides properly defined constants, are noted by lowercase italic letter, e.g., x E R; the vectors of dimension higher than by bold lowercase letter, e.g., x E Bd for d > 1; the matrices by bold uppercase letter, e.g., M Rdi For E Rdd x[j] represents the 7th coordinate of the vector x. L Diag(1...., 1) E Rddd is the identity matrix of dimension d. Given x E R and M E Rdixda, x M denotes multiplication of all values of M by x.
Given two vectors u, V E Rd we note [u v] the matrix of R whose columns are the original vectors. We exlend this definition to matrices in an obvious way.
For a matrix M E Id xd2 we will denote the row vectors of M by m, for 1 S i S d1, and we denote the column vectors of M by m² for 1 < j S dz.
2

---

Published in Transactions on Machine Learning Research (12/2024)
For x.y R", yx is the usual scalar product in R If we fix E R the function (m, R (m, x) E IR is a linear form.
For M E Rdixd we define the transposition operation by M E Iddaads where the rows of M are columns
of M For x E IR, in this paper ||x|| V x[s]2.
@ the Hadamard product between vectors: if x E R and y E Id we have xO = 2, with z/jl =
for j
+ the concatenation operation on vectors. For RR and y Rd we have x + y Rditda (where di and d2 might be different): if x (21.....,22) Ra,) and y (y1,..., Vd,) then x x (........ Fdy Vi..... Vdz).
2.2 Elements of arithmetic
In this part, we introduce the definitions considered for modeling the finite precision configuration. We begin with the concept of centered integer representation related to finite basis representation.
Definition 1 (Centered integer representation) Let B,X > two positive integers. We define
E B 1))
the set of inlegers in basis B encoded on X digils. We define centered inleger representation as the image of the set [X] by a bijective function shift defined as follows:
B
[x] 3 x shif((x)
where [-] is the floor function. We represent centered integer representation by the couple of integers XB.
The definition above will help us to define in a rigorous way the floating numbers and a finite precision configuration.
Definition 2 (Finite precision configuration) finite precision configuration is defined by a tuple of posilive inlegers (B,M, X), B being the basis, M and X representing the number of digils allocated for the "mnntissa" and the 'exponent', respectively. We define two sets:
[M] {x RM E 1-1]}
[X] = (A1 - A (O..... ......... 1}}
In this configuration float number x is represented as triplet:
float = (sign, mantissa, exponent)
where sign (-1,1), mantissa [M] and expooent [X] In order go from the representation the number ilself, one needs lo:
x (sign) (mantissa) x (eaion(eapo)eet)
where shift is the function of Definition 1
For example in the configuration (B,M, M, X) (10,5, 5,4) 4) the number -12.35 is represented by the triplet 12350 4997) and when we switch to the actual number we get.
x 12350 x 10shsf((1997)
12350 10 10
where in this case the function shift is defined by shi (())
10a
5000.
3

---

Published in Transactions on Machine Learning Research (12/2024)
One can remark that this notation allows multiple representations for the same number, indeed both repre- sentations (-1, 12350, 4997) and (-1,01235, 4998) will produce the same float number -12.35 in the finite precision configuration (10,5,4) Therefore to avoid all ambiguities, we say that a non zero float number is in its normal form (sign, mantissa, exponent) if the mantissa = 21 is such that 21 7 0.
The setting (B, M, X) generates the set G(B,M.)) composed of all numbers reprosentable following these restrictions. We will abusively use the notation G instead of G(B.M.) for the sake of simplicity when there is no ambiguity.
As an example, in the IEEE 754 norn D the simple floats are encoded in base B = 2 on 32 bits, with 1 bit for the sign, M = 23 for the mantissa and X = for the exponent.
Arithmetic's 's operations in finite precision configuration might sometimes be counter intuitive. For instance, suppose one wants to compute the addition of two numbers and 8. Tet x = (signy) X ... x Bezponent, and s = (sign,) X 81 SM x Bexponent, such that exponent, < exponentz. In order to compute I + s, one first needs to match the exponents of a and 8. Without loss of generality, we can fix the highest exponent and modify the magnitude of the other number, however since we can represent the mantissa of s with only M digits we have to compromise and replace the s mantissa 81 8M by an approximation 0..-0 81 MM-
D zeros
and therefore obtaining an approximation of
0..-0 $1 .... SM-D B perpoeent,
D zeros
with D exponentyy exponents. We obtain that the operation x in fact 5.
This illustrates the consequences of rounding in finite precision, since the last digits of s are not taken into account in the addition. Worse, if D 2 M, the operation x will output x. In the following Lemma (proved in Appendix D) we discuss another phenomenon, the saturation of the bounded activation function. In infinite precision, functions as the sigmoidal function and the hyperbolic tangent, never reach their boundaries when evaluated on real numbers. However in finite precision they do reach the boundaries, and the following lemma characterizes the smallest float number to saturate the sigmoidal function.
Lemma 3 (Underflow boundary) Let XX) the finite precision configuration and let a I Ite _x
be the sigmoidal function. We define 1 and 1 x If M min(u,) 1} then there crists J E G(B.M.X) such that o(J) and a)- and for all positive float numbers such that J < J we have af (--(J- - 8)) #
The proof of this result is in Appendix D
2.3 Elements of Deep Learning
In the following we focus on a single Recurrent Neural Network architecture, and therefore we set the activation function to be σ.
In deep learning the same notation is usually used for the activation function as one variable scalar function and for whole activation layer. To avoid any confusion, in this paper o' will refer to the derivative of the function I + R and VV IRd dd its element counterpart defined by:
(fn,..,,zaa) Ia) =
(xa)).
In this work we focus on just one RNN archilecture: the Simple Recurrent Networks (SRNs) (Elman 1990 However, we would like to emphasize that we are studying SRNs in finite precision, so to formalize this point, we introduce the definition FP-SRNs where FP stands for Finite Procision.
The current version defined according to the following reference: IEEE Computer Socicty (2019-07-22). IEEE Staudard Floating- Point Arithmetic. IEFE STD 754-2019. IEFE. pp. 1-84. 100:10.100///EFFSTDDD... 876622.. ISBN 978-1-5044- 5924-2. IEFE Std 754-2019.
4

---

Published in Transactions on Machine Learning Research (12/2024)
Definition 4 (FP-SRN) Let (B, be a finite precision configuration, set G (B,,, A Finite Precision Simple Recurrent Network (PP-SRN) R is a triplet (ho, E.D) where he Gh is the initial hidden state vector, and &, 'D functions called encoder, decoder respectively and are defined by:
8: G" G (x, + (Ma(xx D: G h a (M G
The values h and o are positive integers representing the imput dimension, the hidden dimension and the output dimension respectivcly. M, E G x Guth+1 and M. E G x Gh+l are matrices. And a is the sigmoidal logislic function.
For a finite sequence {x G" with T an integer, the execution of R on the sequence {xx]kmm is given by the sequence ya) where h2 and Va defined recursively following the rule:
h E(x hg-1) Yk D(b)).
In this definition, we have chosen to group the parameters together in single matrix as far as possible. However, in this work it will also be useful to have definition that makes & clear distinction between parameters of different types, we give the following definition, perfectly equivalent to the one above.
Definition 5 (FP-SRN version 2) A Finite Precision Simple Recurtent Network (FP-SRN) R. is triplet (bo, D) where ho E hh is the initial hidden state vector, and E, D are functions called encoder, decoder respectively and are defined by:
E: x G 3 (x, + a (Ux+ Wh + b) E G*
D: hhho
where is the activation function, U is a matriz with rows and columns, W is a matriz with rows and h columns, V is matrix with and h columns, and b, с vectors of dimension h and respectively. Execution sequence is defined eruclly as in Desinition 4
We call the matrix W the transition kernel, U the input kernel and V the output kernel. Clearly, the two definitions are equivalent, because
M = UU Wb M. - IV cl.
Another handy notation is the one of the parameter vector. Indeed, when we need to consider parameters in FP-SRN R independently of their function, it is convenient to group all the paramcters together in a vector of parameters denoted 0. So, to underline the distinction between two FP-SRN which differ by their parameters we will note them respectively Rs and Rg.
Depending on the context and the problem we are treating, we will prefer one to the other definition. Notably, Definition will be handy to define neuron:
Definition 6 (Neuron) Let m E Gd be vector and the sigmoidal function. A newron is function defined as:
Gd a x + a((m, x)) G.
In this work, the definition of the gradient requires the notion of differentiated neuron.
Definition 7 (Differentiated Neuron) Let m E Gd be a vector and a the sigmoidal function. We define a differentiated newron as:
o'm Gd x d'm x)) GG
We intentionally defined neuron as composition linear form and a non linear activation function (in our the sigmoidal function). If we refer to Definition 4 then by looking at the encoder decoder coordinate
5

---

Published in Transactions on Machine Learning Research (12/2024)
by coordinate we find the definition of neuron. If we take FP-SRN R and a decoder coordinate $ S h, we have that:
(Mi(x x
In the following, the integer u, and will represent the input dimension, the hidden dimension and the output dimension, respectively.
Definition 8 (3-saturated SRN) Let R be FP-SRN and X' = {xx) 721, X E Rd) a set of
input sequences, we say that R. is 3-saturated for 0 05 0 11,, if for all input sequence {xx]kmi> we have:
(UX++ + Wh + b) >BKEE
min Isich
In other words, a 3-saturated FP-SRN lincar part of the encoder will always produce vector that is RA \1-3,33 i.e. whose coordinates always at distance 3 from zero. An interesting fact about 8-saturated SRNs is that for all input sequences (xx ) for all 1s k S T, we have:
| v (UXX Wh + +b)l S od(
This inequality derives from the properties of o, and the 3-saturation hypothesis. Indeed, by hypothesis we are sure to have (Ux+ + Wh:-1 + b) [i] 2 8 for all coordinates 1 < S h, on the other side o' is a decreasing function on the interval [0, too and symmetric. Hence for all 1 S j < h we have:
v [UXA + Wh + +bbbl (
This incquality is discussed more detail in the beginning of Appendix A In supervised machine learning, the training of a neural network requires the use of loss function defined as follows.
Definition 9 A loss function is a function C : Go G G that compares compulationally the output of model on a given training data and the expected target value. The Binary Cross entropy is example for p.q E)0, 1[:
-0--)----100 (1 4) 1n-nn(11))
In a practical context of deep learning one could, during early phases of the training, encounter situation where the prediction of a noural network the opposite of the target label i.e. p = 0 and g q= 1. In this kind of situation we obtain L(p, -q In(p) In(p), value unstable and potentially undefined. Moreover, the gradient of such calculation is 1 >> in the case of p O. Therefore in order to prevent instability, common practice is to add small constant and define a numerically stable loss function:
(p = In(p +c) - (1 9) In(1 c).
(1)
We will assume 10-7, corresponding to usual practice in the tensorfl sooorfloowkerrss platforn 2 This small change will have a profound impact in this work when we discuss the back propagation of the gradient, because the function 0p (p.4) becomes bounded on [0, 1) x 10.
Definition 10 (Fixed step Gradient Descent) Let Rdd - TR be differentiable function, un Rd initial point and > positive real number. The fixed step gradient descent of f starting at xy is the sequence (g:h20 C IRd defined as follows:
go
g: gi-1 ---1-aV/(g-11 for 1> 0
where (g(g:))) is the vector of partial derivatives of f at the point gi-1-
This definition naturally extends to a variable learning rate ai.

---

Published in Transactions on Machine Learning Research (12/2024)
2.4 Elements of Language Theory
Let Σ be finite set of symbols called an alphabet. Σ" represents all the finite sequences E and is the empty sequence. Any subset I. of Σ" is called a language.
For w E ,", | represents its length, that is, its number of symbols. The concatenation of two sequences is denoted by: w-w. w-w.
Definition 11 (DFA) Deterministic Finite State Automata (DFA) is entirely defined by (2, where: Σ is finite alphabet; Q is the finite set of states; qi the initial state; 8 Q E - Q the transition function; Q is the set of accepting states.
F)
The language represented by DFA is the set L E E' (0 F), where 8 is the transitive exlension of the transition function: 8" (y, 9, 8* (q 8 (6(1, for q Q, E,w E E'.
E':
Definition 12 (One~hot encoding) Let E = a2,,0,,..., be finâte and ordered alphabet of size Let ee,,,e,...ee e be the canonical basis of the veclor space Rk,, defined by: eibil= = if = and 0 otherwise. We define a one-hot encoding as a bijective map:
Φ: E th E e...
The definition of a one-hot encoding is naturally extended to the elements of Ex by the bijectice map o² E' + emm "" with o" a. an) + (δ(a1), ((a2), ... ,(a,))
One-hot encoding is a bijective correspondence between an ordered set of symbols K = {aI,... an and the canonical basis of IR", fei,e2,... e,,,.,, cu)- In order to simplify notations, we take advantage of the bijective correspondence and from now on we consider that Σ = (e), , e.).
3 Stability to Noise in Parameters
Our main goal is to prove that there are regions of the parameter space that are not accessible by gradient descent. Our strategy is to exhibit points in the parameter space such that FP-SRNs with those param- eters will experience a stationary gradient. The notion of stationary gradient is formally defined later in Definition 15 Nevertheless, intuitively a FP-SRN Ro will experience a stationary gradient when there is a non empty set of coordinates in the parameter vector 0 such that for any element of the training set the gradient for these parameters is negligible with respect to the parameters. We will demonstrate that some 3-saturated FP-SRNs experience a stationary gradient, but in this section exhibit. another particular feature of 3-saturated FP-SRNs, the one of stability to noise. Indeed, Mitarchuk et al. (2024) prove that it is possible to disturb the parameter of a A-saturated SRN (and thus of a FP-SRNs) and have guarantees that the disturbed FP-SRN is ß-saturated, for 3 proportional to 3 and to the perturbation. We will build on this perturbation property of f-saturated SRNs to expand the stationary gradient experience around the saturated FP-SRN, and hence obtain a region of parameter space where FP-SRNs experience a stationary gradient. In our work, we have slightly reformulated their result and their definition of 3-saluration, but the theorem stated below and the definition remain perfectly equivalent. Before stating the result we introduce the notion of perturbed SRN.
Definition 13 (Perturbed FP-SRN) ) Let Rs be a FP-SRN and & E Rdim((), we define a perturbed FP-
SRN Rots as follows:
&: x (( W
+ (b+ 0b)) G
D.G h AaHo((VVVl) (c+ 0c)) G
The hidden and the output vectors produced by the perturbed FP-SRN Roto are denoted by h and ÿ. The following theorem makes it possible, under certain conditions, to limit the deviation between SRN and its perturbed version.
+ and Č In (I for some î > Theorem 14 Let Rs be a Ō satuuuarte FP-SRN, with z = TWT
We assume that Ro is operating on one-hot encoded data. We select any real namber such that 0 < < 1,

---

Published in Transactions on Machine Learning Research (12/2024)
then for all = vec(Ou, ow; iv, bb, 0c) (Rdmm(0) such that ||i||| S (1 1)r (1- Will with á d' and for all w E E" with [w] = T we have:
(2+vh)
1. lhg hollo S (2+v1) T-AIWT]le ||ol| where ISKST.
2. Roto is (5+ (t)) salturaeed.
The sequence of hidden state vectors h2 is produced by the perturbed FP-SRN Rp+0-
We recall all the proofs of this theorem in Appendix B The idea is that it is possible to express h& as sum of h& and G(Ø,k) k), where G(O, k) is a function of the perturbation & and the iteration and takes the form of a sum & elements. Mitarchuk et al. (2024) exploit the saturation assumption to upper-bound G(D, k) with a convergent series and hence show that the perturbation injected at every step cannot be endlessly amplified. This proves the first claim, after what the sccond claim is deduced from the first one.
4 Finite Precision SRN and Learnability
In this section, we discuss gradient failure for RNNs training. First, we describe the algorithm of gradient propagation in RNNs called Back Propagation Trough Time (BPTT) and derive a representation of the gradient as sum of products. Then, we formally define the stationary gradient, after what state central result. Finally apply this theorem to concrete case and discuss the different variables involved in the theorem.
Encoder
Encoder
Encoder
Decoder
x
One
small
step
for
man
mankind
Figure 1: Illustration of the Encoder Decoder architecture.
4.1 Back Propagation Trough Time
To train neural networks the usual approach is the one of Gradient Descent (GD). Its classical implementation for RNNs is called Back Propagation Trough Time (BPTT) which we detail in this section. There are many ways from which one can consider neural networks and BPTT. Switching from one representation to another provides an in-depth and intuitive understanding of the mechanics of BPTT. We start by setting out the machine learning framework within which we will develop our arguments, and then use the various neural network representations to obtain gradient representation that will enable to prove assertion.
We place ourselves in the context of binary classification on sequences. Let Ro be FP-SRN and 5 = (W1,,1)),.. (wN.BN) a labeled training set with N samples and where = [x C C" is finite sequence vectors (the vectors X can represent. vector embedding of words) with 1 I N and T> an G to be a differentiable loss function.
integer representing the length the word wr. We set L: G
For (w, v) E we update the parameters of Rg using (w, v), by computing VoL(R(w),)) y) stated in Definition 10 In order to obtain the output of the FP-SRN w, Ro(w), have to compute recursively hy

---

Published in Transactions on Machine Learning Research (12/2024)
Encoder Layer 1
Encoder Layer
Encoder Layer T
Decoder Layer T+1
Loss
y, y
output
label
Initial hidden state vector
Figure 2: Illustration of the unrolling of the RNN for the BPTT.
and then D(hr), with h&+1 = Exx+1, h2) for 15 <. A way of secing the recursive computation of the RNN is to unroll the calculation that we oblain pseudo leed-forward neural network R derived from the evaluation of Ra with (T' 1) layers, which includes the decoder layer and the loss function layer C (D(hr), Each parameter of this pscudo foed-forward network R" is then updated by back propagating the gradient. The difference between R" and a real feed-forward network is that the parameters do not change from one layer to the other. To give more formal definition what we mean by pseudo feed- forward network R", let us consider the notations of Definition allowing us to write hy as the output of T layer feed-forwand neural network:
hr
Wo
Wo (.... (..oo Uxi + b)...) -XT-I+ +bb) UxT + +b)
Wo Wo (..oo(Win + bi)...) + br-1) +br br
The second equality has the form of a regular architccture of feed-forward neural network where we alternate between affine function and the activation function. In this representation, we have encoded the sequential input (x1, X2,...,... XT), in the vectors bę which defined by Ux+ b. Obviously, during the training the parameters of the matrix U and those of the bias vector b will be taken into account by the algorithm.
In Figure we have made distinction between the parameters of the transition kernel, which are represented by full arrows, and the parameters of the input kernel, which are represented by dotted arrows. We also represented the embedding of the sentence "One small step for man humanity' with a color code representing the order of the words in the sentence. Thus in Figure 2 we have represented the integration of the input kernel evaluated on the words in the pseudo feed-forward network parameters by representing the neurons by full and dotted concentric circles with the coloration of the embedding of the words. Figure rates the unrolling procedure of an SRN of hidden dimension 4 evaluated on sentence.
Figures and 2 represent the neural network as a graph where the circles are the activation function a and the arrows represent the weighted connections realized by the matrix M,. Rojas Rojas (9966) explain the back propagation for deep neural networks with sigmoidal activation. They build on the graph represontation of the neural network construct the back propagation algorithm. The first phase is the forward pass, í.e. the computation of L(R", y). Secondly, compute, recursively, the gradient for the parameters involved in

---

Published in Transactions on Machine Learning Research (12/2024)
every layer of the network. The gradient propagation can be seen tracking the impact of parameter the final result L(R",v) .v). In the context of gradient calculation in directed graph, tracing the impact of a parameter is achieved by observing all the paths in the graph that link the loss to the parameter in question and assessing the impact of the parameter on cach of these paths. We emphasize that every layer, except the last one, of the nelwork R uses the same set of parameters, what we called the pseudo feed-forward network. This implics that every parameter of M, will produce partial derivative composed of a variety of different impacts that the parameter may have had on the computation of L(R", .y. Our goal is to derive convenient representation of the gradient that leads us to consider the fact that the network is composed G One can deduce from the chain rule, that the partial derivative of L(R", y) with respect to a parameter ma, can be represented as a sum of products, where we sum over the set of paths linking the result L(R and the parameter mij within the network, and the products are composed of the weighted differentiated activations on a path. More formally for a paramcter mij we define a path y = (7,..., 7k) of length & for we have 71 Mo[i], for k
of weighted sums and differentiable scalar functions (building blocks of the neuron in Definition
we have 71 = M. and 1/2 miii for some 1 S v I h. For the case & 2 3 we define y such that ikk m.çi for some 1 S S h, for all 1 < s < k 7--1 M1,1, Y Myr and Na+1 Mr.w. In other words y is an ordered sequence that contains the information about path followed within the network R" from the loss to the neuron hosting the parameter ma,j- We can gather all such path y for the parameter ma.j in the set Pig, what allows us to define a partial derivative aC(R",)) wn follows: Omuy
1 ST T as finite sequence such that for k
OC(R" .v) AC(R" .)) 0mij
& Σ II To oy (XT- 2 h-- @1). TETT,
(2)
where aC(R%.)) .V)
dz represents the partial derivative of L with respect to the first variable. We abuse a little bit the notation of the neuron here because Y refers to a parameter in the matrix M, and not to a row vector, but since a unique row vector contains the parameter 7 we allow ourselves to denote a neuron in this manner. Equation is not new, in fact it can be deduced from the back propagation algorithm of Rojas & Rojas 1996). We recall that our goal is to show that some regions of the parameter space of FP-SRN cannot be reached by gradient descent. The idea is to exhibit regions of the parameter space where some coordinates of the gradient V VL(((w),,) v) will have negligible value with respect to the parameters, leading to 0 - a VL(((w),)) = 0 in finite precision. To achieve this we will use Equation 2 to prove an upper bound on @C(R" .v) that we can exploit in finite precision arithmetic's. We have used a lot of formalism for 8m...
the definition of the gradient, which is necessary for the rigor of our work but will not really be used in the proofs, because will state hypotheses on RR that will allow to derive bound that does not depend on T, vectors XT 2 hr- @ 1 and parameters mi,--
We define the notion of stationary gradient in finite precision. A condition characterized by the fact that, for some paramcters, adding the gradient will not change the paramcter duc to rounding in finite precision.
Definition 15 (Stationary Gradient) Let (B, X) be a fouile precision configuration, Ra be a RNN with parameter vector 0, loss function C, a training set S ((wI.B1)..... (WN, yr)) with N 2 1 training samples and a > 0 positive real number called the learning rate. We say that Ro experiences stationary gradient if there is non emply subset P of coordinates in 0 such that for all ma. E P and for all (w, () E S we have in finite precision arithmetic: majj a 0m.,
JL (R(w).v) = =maji
4.2 A Condition for BPTT Failure
In this subsection we develop argument of BPTT failure in finite precision framework. The idea of this theorem is: if the parameters that we try to reach by GD have the properties stated by the theorem (we will show that fully saturated FP-SRNs fulfill these properties) then the gradient will fail to update the parameters before reaching the target.
10

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 16 Let G be the set of all float numbers representable in given finite precision configuration (B, M, X). Let S = ((w1: (NN yN)) be training set with N samples. For 1 < 1 N, Wi = {x C G" is a fonite sequence of length T where Xk are vectors verifying ||x||| < 1 for k and T 221 1 is the integer representing the length of the word wi. We set C :: G x - G to be a differentiable loss function. Lel a > 0 the learning rale as used in Defonition T0, Let Ro be on FP-SRN with hidden dimension h imput dimension u and output dimension strings. We recall that the row vectors of the matrix MA are denoted m; for S i S h, and that since the output dimension = 1 it means that the matrix M. is of dimension (1, k). We set
i.c. Rs shaped for binary classification on
m² == max {Im] m {}
m == min {mm]= m E O and |mm] > 0}.
that is m² is the lurgest parumeter in absolute value and in is the smallest, in absolute value, non zero parameter. We set BD with D [logg(m) (M + 1). We suppose that:
1. For all y E 10 the function [0 z de ()) is bounded by constant PL.
2. 3 17 > O such that Ro is (S + 17) sotturated where
v 42
4
E 1b == a max + +n/)), In/2),|[W]]
In
42 ,2 whpL 1 e
= Then with ;= d'(5 + 3) and with W (the transition kernel extracted from M.) for all 1 E RRdim(()) such
(1-AIW1) the FP-SRN Rot0 will experience a stationary gradient for all non zero
that Eneoderl S 2 (2+vh) paramelers on the training data set S.
Note that this result does not include the parameters in the decoder's part of the FP-SRN. The assumptions on S overcome the information transmitted through the decoder's gradient. The consequence of this is that one can change the decoders parameters completely, it will have no effect on the encoder parameters gradient.
A few words to comment on the assumptions and quantities used in the theorem. The idea behind this result is that a FP-SRN R satisfying hypotheses and 2 will have at least two behaviors of interest to us: A) robustness to noise, B) stationary gradient. The robustness to noise is essential in this result, as we aim to exhibit whole population of RNNs that have similar behavior to R. Quite naturally, when it comes to perturbation, we have to make assumptions about the Lipschitzian constants PL of functions that form the networks. This explains assumption number 1, which ensures that the loss function will not explode if the networks parameters are perturbed. Assumption 2 is more central to this work. This is the assumption of saturation of the activation function, f.e. how close the activation function is to its bounds. This assumption is essential, as it both demonstrates the stability of the RNNN with respect of the noise injection, and squashes the gradient to zero. The Ç quantity acts as a threshold below which the guarantee of behaviors A) and B) e_ are lost. More precisely, Ç is the solution to the equation a' o²( whoz I4s- Since o'xx) (x)(11 oa))
i.e. an equation of second degree in (I)) and that a is a function defined with the exponential function, one can deduce the appearance of a square root and the application of the logarithm function in the definition of Ç. For a formal proof please refer to Lemma 18 in Appendix
A The desired quantity whop ite to achieve with dC) is built such that, it possible to bound Equation 2 by E. On the other hand, the constant 1) has to be seen as budget for the perturbation that Rs can handle without loosing the saturation property. All the proofs articulate around well-defining the border 5, and wisely managing the budget 17.
For readability reasons, the complete proof of the theorem is in Appendix A of this paper. Nevertheless, we propose sketch of the proof. At first, we prove that a (S -)atturrad FP-SRN is stable to perturbations with Theorem 14 proven in Appendix B Indeed, one can disturb the parameter of Rs by adding a noise vector to the parameter vector and be sure that the output of Roto will remain within a controllable distance of Rg. On top of that, for a well chosen i we can be sure that Rot0 will be (c+ (/2)s)))saturattt (í.e. for Encoderll < n 1-Al|WIl), ). After this first step, we proceed to prove that the gradient will be rounded to zero (the stationary gradient property), by using the gradient expression in Equation 2 In the following subsections we provide some concrete examples based on set of parameters.
11

---

Published in Transactions on Machine Learning Research (12/2024)
4.3 An example of non learnable FP-SRN
In this section apply our results small example. DFA suit particularly well our case, because they model binary functions sequences. Figure 3 is representation of a DFA accepting the language of all words that contain an odd number of a's on the alphabet E = {a, bJ (the initial state is 1, the sole accepting state is 2).
b
b
a a
2
Figure 3: A DFA accepting the language composed of words containing an odd number of a's. The initial state is drawn with an incoming arrow with no starting state, the finale state by a double circle, and the transitions with labelled arrows.
Let (B, M, be the finite precision configuration. We prove Appendix D Lemma that there exists positive float number J such that a(-J) 0, oJJ 1 and for all positive float number such that J 7-8 < J have a--(J- 8)) > The number J is called the underflow barrier float.
Then we define:
ho
w
w
.M. :- J. [-1-1 -1 11
3
and:
AV
A
0
0
U 2J
W -J.
1 0
0 1
3
3
W
W2
We consider the computation of the FP-SRN the word and the word b. Their one-hot. encoding is 0
d(a)= = 0) and ((b) = i
We have:
Ud(a) Who (2 0 2 0) (3
1 10131
=J JJ (-1
-1 1 3) T
After applying the activation function we obtain h
(0 0 1 0)" due to the overflow and underflow.
The vector h is accepting vector because (M,hi) aJ) 1. If we do the same computation for we
12

---

Published in Transactions on Machine Learning Research (12/2024)
obtain h/ = (0 1 0 0 0)". The vector h is not an accepting vector because (M,h)) = =[-)) = 0 due to the underflow. We draw the readers attention to fact that this FP-SRN is J-saturated by construction. In Section 5 we propose an algorithm that for any DFA, will return FP-SRN that is J-saturated and that simulates the DFA. But first we propose to study the example above from the perspective of Theorem 16
4.4
On the learnability of this FP-SRN
In the following subsections we apply Theorem I6 to the FP-SRN defined just above. We will gradually show that the FP-SRN of the example respects the assumptions of Theorem 16 and explain the magnitude of cach variable involved in that thcorem.
At first we assume to have XX) numbers, that we convert to base 10, in order to have readable constants. In this configuration we have J 38.7228391117. When we switch from base B = 2 to base B = 10, the number of digits needed to encode all the floats in M(). does not exceed 15, so when we switch to base B = 10 we get that M = 15. In other words, we have G(2,23,8) C (10,15 The constant M is necessary for the definition of e, the value that must upper bound the coordinates of the gradient in order for it to be rounded to zero. Therefore, in the following, since we switched to basis 10, we will use M = 15 to define E. The FP-SRN presented above in Section 4.3 J-saturated by definition. By taking a closer look to the matrix MA- = [U W] one can deduce that for all S h and all 1 S j S + h we have |maJl I 3J. Also the smallest non zero parameter in M,, M, is m = J, Therefore obtain:
(3) the usual finite precision configuration of 32 bit float
m = J. ~ 2.7 10
1oo (m) = 1oo (J) = logio (102) (00)== =
(102-(15+1) 10-14.
We remind that E defined above represents the threshold such that for all float numbers m S e will have no effect when added to non zero parameters of the FP-SRN Rg.
4.5
How h, E, and PL affects Ç
16 the quantity& S has central role, it delimits region where we have the guarantee that Ro is stable to noise and will experience stationary gradient. In the case that consider now, Ro is J-saturated with + J, knowing Ç allows us to know exactly (a constant that represents the budget for the perturbation) and thus the size of the Euclidean ball containing FP-SRNs with stationary gradient. The variable Ç is directly linked to m², 8, PL and a the learning rate. In our case m = 267. For this study we will represent the size of the hidden state vector h 10" for n E [0, 11], because h that will mostly impact the computations. We assume to use C. as the loss function with, e 10-7, a default quantity in tensorflow .eras platform for numerical stability. It comes that we have PL 10?, and for simplicity assume to have = 1.
In Theorem
the magnitude of
The first quantity we want to discuss is sb:
/ a max ((m* + n/22, [W])
max{(m² + n//2,, [|]]]
S m" vh for h 2 2
(267- 10 < 2.7 102 +2
The inequality above comes from |||| < || < m Vh, and we assume that mn* 2 n/2. In the case of the variable vp an upper bound is enough for us because it will give us an upper bound for Ç. This allows us to estimate the magnitude of the quantity = = Jhpt Ite, First we have 1 te = 10-1 v 1, hence I+F
4 &
e R s.
Then we have:
4
3n
1.48 10
ShpL 2.7 102 +2 10"107
13

---

Published in Transactions on Machine Learning Research (12/2024)
4
1.10-14
1.48 10 16-
3n
2
hhpr
+ 2.7 102 10"
By using the Taylor expansion of + x/2 o(2²) for x = O, we deduce that
+ /1 42
5 = In
vI 4z
2z
In
2%
In
+ (16 +
3n (n)n(()) + In 1.48
3n 10-1--1----0 2
10 16-
1.48
2
23 In
1.48
+ (16
+
3n In(00) +0
2
1 1.48
1
$ (16 + 3n In(10) because
< 0.
2
If we consider cases where h 10 S 10 then we have that the boundary Ç is in the interval Ç E [38, 72). We recall that Ç represents boundary beyond which we have the guarantce that Rg is stable noise parameters and that this FP-SRN will experience stationary gradient. It is important to note that even with very hard requirements on the gradient (í.e. the coordinates of the gradient have to be smaller than 10-2 10-21), ), it is sufficient for a FP-SRN to be saturated with values under 72. In other words, by Theorem 16 it is impossible to train FP-SRN by gradient descent such that the linear part will output vectors with coordinates further than 72 from zero.
4.6 How big is the perturbation radius 2 1-AIW]? 2-Vh
L-AI|WI All the computations are based the In this part we discuss the quantities W| and Y 2+/h
hypothesis that Rg is defined as in Section 1.3 Our goal here is to estimate how these quantities affect the radius the Euclidean ball around the parameters M,, that fulfill the assumptions of Theorem [6] We recall that the matrix W is the transition kernel extracted from M,, and that A := o'(ς + n/2), where (+ 1 J R 88.72. We start by analyzing the quantity A||W|| o'(g + n/2) W| Lemma 19 in Appendix A tells us that
d'(5 + 2/2) S (() + (S22))-((-n12))
This result is based on the Taylor expansion of o'. From the computations above one can deduce that:
< x (16 + )n) In(00)
1 1/2 / (J-
25.68
3n
4 (10))
We have also ||||| m² 2.7 10-+2 leading to:
W = d'(5 + 7/2) W
S < + m" hhn/22e
(S-9/2) ((-0/))-(6-001)
By Lemma 17 have that d'(C)
_
We recall that s max((m" + nn/2), [[]] Therefore:
Shpt Itc
4
4E
d' hhp, 1+E
|
S hpr. 1+
4.10 10-21- 21
hpr.
m The quantity m h((n2)ee (C ((-n/2) requires to plug into the exponential function the value of Ç n/2 that
we have introduced above. We obtain that:
3n In(10)) (10 11.151 9n
m h((n/2)e (6 n/2) 2.7 +2 (25.68-
4
3n
2.7. (25.68
In(10)) 10
9.15
4
4
14

---

Published in Transactions on Machine Learning Research (12/2024)
Clearly the quantity |||W|| is upper bounded by sum of quantities negligible with respect to 1. Therefore we can assume that W|| = 1, hence ? WIl
2 24 4+2VE
The previous results lead the conclusion that the quantity that influences the most 2 2+vh From the proviously established representations /. we can deduce that:
W-I is h 10".
7/2 2 Vh
25.68 In(10)
+ 102
In order visualize the evolution of the perturbation radius with respect h, define the radius function r(n) 25.68- 3n ln(10) and plot this function with n E R4 in Figure 4 We have highlighted the particular
2+10
value of the radius function at 0.602 for the reason that for this value of n we have 10t 4 í.e. the number of neurons that the FP-SRN presented in Section 4.3 has. Hence the reader can see that with our results we obtain that the perturbation radius this example is 6.16. We will see a next paragraph how such perturbation can impact the network performance. Finally, nole that SRNs with more than 100 neurons are rarely observed, so this last constraint on the number of neurons is realistic. Indeed, based the survey of Laraa-Beniie Benitez et al. (2021) identified 3 works published between 2012 and 2018 that employ SRNs ((Chandra & Zhang 2012), (Rueda & Pegalajar 2018), and (Mohammadi et al. 2018) ). The information about the number of neurons is missing in (Mohammadi et al. 2018), while the number of hidden neurons is less than 10x in the two other papers. The most recent use of SRNs, dating from 2023, is in the TAYSIR competition (Eyraud et al.) 2023). where a benchmark already trained models was presented to competitors. The benchmark is composed of different RNN architectures and in particular, SRNs were proposed whose number of hidden neurons did not exceed 512.
12 r(n)
rO.602)) 6.16
8
1006002
-2.5
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Figure 4: This figure displays the radius function r(n) where = Inlo(d) the logarithm in base 10 of the number of hidden neurons. The yellow dot represents the perturbation radius for the example 4.3
4.7 Stationary gradient even with L. +
Just above we established that the FP-SRN Ra from Section 4.3 within the requirement of Theorem [6 has a perturbation radius of 6.16. In other words, for all 9 Rdim(0) such that || Encoder || S 6.16 the FP-SRN Rot0 will experience stationary gradient. In Table we present the variables of interest for Ro. Theorem 16 does not. depend on how the perturbation is spread among the parameters of the FP-SRN
15

---

Published in Transactions on Machine Learning Research (12/2024)
h
?
r(n)
4 R3 38.92
R 49.8
R 6.16
Figure 5: Statistics of the FP-SRN from Section
4.3 in usual 32 bit float precision
and does not depend the decoders parameters. We present here example where the noise is spread randomly across the parameters of the transition kernel:
1
3.07
2.90
1.15
0.71
0 = U=
W
0.49
1.06
3.0
2.88
M, : 2. [-1 1
0.86
0.79
2.93
3.43
1
3.09
3.24
1.33
0.59
By design of the perturbation we have IW -
W |ro = 6.16.
We execute this perturbed FP-SRN on the
word a that one-hot encoded as follows ((a) =
We obtain:
Üo(a) + Who = J.
( ((2 0 0) (3.07
0.49
0.86 3.09)
=J- (-1.07 -0.49 0.86
-3.09)*
After applying the activation function we obtain the hidden state vector h, (0 1 0)², with a R 1.316 10-19. Now we apply the decoder on h,, and obtain:
(M,h, = o2 (1 a))
0.88
By definition of the DFA in the example, it accepts all the words with an odd number of a's, Therefore the word is labeled with 1. One can compute the loss in this particular case and obtain that:
=-1 - -1,,og(((M,,)))) + 10 x - log(0.88 10-?) 0.1269
This means that the FP-SRN Ro+0 can experience stationary gradient even though the loss is not 0. In this example, the classification is still correct if one sets a threshold of 0.5, indeed 0.88 > 0.5 thus the classification would be correct. However, since Theorem I6 does not depend on the Encoder parameters, one could set all the Encoder's parameters 0 while maintaining the theorem's 's validity. In this extreme case, the SRN outputs would be constantly 0.5, f.e. no classification and the gradient would be stationary.
5 A non learnable class
In the previous sections we have developed series of arguments Lowards the fact that saturated FP-SRNs cannot be learned by gradient descent with a fixed learning rate, In order to exemplify the result we have exhibited FP-SRN that simulates the DFA accepting all words containing alphabet {a, bJ. In this section, argue that the example of Section 4.3 is not an isolated case. We present an algorithm that, for any given DFA, outputs saturated FP-SRN that simulates the DFA. We call this algorithm DFA2SRN, and it is an adaptation of the algorithm proposed by Minsky (1967) to FP-SRNs. Indeed, the author of (Minsky 1967) works with RNNs based on a non differentiable activation function H: > {0, 1) with ((x) = 1 x 2 O and otherwise. This algorithm demonstrates that the non attainable region by gradient descent for FP-SRN contains large class of interesting functions.
odd number of a's the
5.1 DFA2SRN
Let D = (E, Q, 91, 6, F) be a DEA. We suppose that the alphabet Σ = (ei.... e.. } is a set of one-hot vectors. We recall that Q = .qi...... . the set of states, di the initial state, 8: Σ Q - Q the transition function, and F C Q is the set of final states. In order to simulate the DFA by a FP-SRN we have to: 1) simulate the transition function, encode every state such that it be read by the FP-SRN, 3) simulate
16

---

Published in Transactions on Machine Learning Research (12/2024)
the function discriminating between elements of F and Q F. The encoding of the states of the DFA follows the spirit of one-hot encoding. The transition function is simulated by the encoder and the discrimination function will be simulated by the decoder.
The main idea is to make the hidden states h, t 2 1, be an encoding the state q reached in the DFA while parsing a sequence up to its tt element. Thus, M2 has to encode the transition function, and M. has encode the q E F relation. In the rest of this scction we will refer the FP-SRN of Definition p and we will use formalism W, the transition kernel U, the input kernel and v, the output kernel (the output kernel is vector because the output that need is scalar in {0, 1}).
We set [ = Qard(Q), | == Card(E). We assumne that Q {qi, 001,92.... .... UQQI and we define IF C {1..... [|] with:
( 1..... (1+ (1+ 1 LF = E F).
The linear parts of the SRN are defined by:
W E G [ UE [
ho E G with ho ho[1] 1, -
ve G | with víj] J if I and - J if Ip.
J is the smallest float number saturating the activation function as defined in Lemma 3
T
We define U = 2J.
[QI identity matrices |ز=] piled up.
For the construction of W, we start by defining for every state qk, 1 k S [Q], a column vector w G/ by the following rules:
R1: For 1 < s $ if 0(gk, a.) = qú then w [r] = --1 with r = (j 1) + s,
R2: All the other coordinates of w are set -3
Note that by definition of a DFA every vector w has exactly |Σ| coordinates set -1 and (IQ) - 1)| coordinates set to -3. The rule R1 defines encoding for (gk, as 8(1k,a)) Therefore the vector w contains all the transitions starting at 9k.
Afterward we generate, for every Ok E Q, the matrix:
W J. [wl W wiol E GIQ1E
where for I5 [Q]
(3)
W
k
w
w G Q|E|*E]]
times
In the definition of W the vector w is repeated [X] times.
In Appendix C we give a formal proof that this construction simulates the given DFA on one-hot encoded symbols. The pseudo-code of the DFA2SRN algorithm given in Algorithm T In this pseudo-code we used the numpy notation convention for matrix coordinates, meaning that Uk, s represents the coordinate of matrix U at row k and column 8, and U(k, I] represents set of coordinates that are located al k and ranging from to t.
6 Experimental validation
This section is dedicated to the experiments we carried in order to observe the theory on a practical case. This section can be broken down into two parts: the first is series of experiments in which attempt to train
17

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 1 DEA2SRN
Require: = (E, Q. 21,6, F) a DFA, with Q = (9o.................. :0....-------111 -101-1 and = fwi,.... } ; J the saturating
integer
U [] Q by [|| matrix of zeros.
W + [-] [2] by [Q matrix of -3's
V+ |Q]
matrix of -
for j = [...[Q]]o
if Ø5 E F then
ViA A+ Σ|| +
end if
for
k = 1.. |حا] do
B - /, [Σ] where & E (o....1Q, |Q] - -1 defined by a: 5(wxx 43)
Uík + k + 2
W + B, A + ||| +-
end for
end for
J U
W 4 J. W
V J.V
FP-SRNs in the classical way, in the sense that we provide training data and apply the SGD algorithm. The second part is a more synthetic experiment. The reason for this dichotomy is that the classical experiments did not allow us to draw any conclusions concerning Theorem 16 we had to imagine a different setting.
6.1 Learning regular languages
As stated above, in this section we seek to learn regular languages in the classical way of deep learning practices. Our aim is to gather statistics about gradients in the hope of observing the stationary gradient phenomenon. Learning a regular language is learning a binary classification task on strings.
First we tried to learn the DFA of the example given in Section of characters on the alphabet {a, 6] that have an odd number of a's. To do this, we randomly generated 458 labeled strings with 50 + 2% of positive labels. What is meant by positive labeling are the character strings that are part of the language and are labeled by 1, the other character strings are labeled by 0. The training sample is made up of character strings of lengths ranging from to 10. The loss function used is the one we dealt with in the theorem (see Definition D The DFA2SRN algorithm was used as guide for choosing the hidden dimension of the FP-SRN, we randomly initialized an FP-SRN with hidden dimension d = 4, slightly deviated
4.3 whose language corresponds to the string
trained by stochastic gradient descent on 20,000 mini-batches of 32 strings. Indeed, from the usual SGD, where data is split into banibbachhes that will not change until the end of the training. 20000. The statistics we tracked during training are: the value of the Loss, the Euclidean distance between two consecutive parameter vectors, the infinite norm of the gradient and the distance to the target parameters (i.e. the parameters given by the DFA2SRN algorithm) The results of this experiment are presented in Figure
In our setup, we randomly draw a mini-batch at each iteration i i= 1,2..... 2,000..
This experiment does not allow us to validate or invalidate Theorem 16. The FP-SRN did not learn the behavior of the DFA. By observing the distance graph between two consecutive parameter vectors, we do not observe any convergence behavior. However, despite the apparent simplicity of the DFA that we tried to learn (two states and alphabet composed of two symbols), this DFA belongs to the most complex subclass of regular languages. According to van der Pocl et al. (2024) the subclass in question is called Zp. Morcover, the training set is quite small (only 458 sequences). For this reason, we conducted the same experiment on languages from lower complexity classes in order to ensure that there is no bias in the experience of SGD learning from Figure X In addition to the classification of sub-regular languages, van der Poel et al. (2024) provides a benchmark of 1,800 languages covering all levels of complexity. To carry out this experiment, we selected languages that closely match the benchmark's complexity spectrum. The training on these 9
18

---

Published in Transactions on Machine Learning Research (12/2024)
Otargel
R0006
0.25
5.22
544
0522
0123
0.10
0500-
4-4
0.95
0665
500006
0.00
2108
2931 ViE W9 TRIITTII (100)10011111
999 986371022990
706 1991 PED INNEIIITT
Figure 6: Regular SGD training where the four statistics of the learning experience of the odd a's language. The curves in blue correspond to the statistics recorded during training, and the curves in orange are the rolling averages.
languages led us to the same conclusion than the first experiment. The details of this experiment can be found in Appendix F.
As we have already stated, these experiments do not validate Theorem 16, but neither do they invalidate it. We did not observe the stationary gradient phenomenon in these experiments, but the parameters of the FP-SRN remained far from the zone where saturation could be observed. All that can be concluded is that the task and/or the context of the learning is too hard for SGD learning. To better fit the context of our theorem, we designed another type of experiments.
6.2
The Synthetic experiment
The failure of the previous experiment may come from the fact that the direction of the gradient fluctuates constantly, which does not allow the parameters to converge. Some cases have been reported where this fluctuation is not too important because on average the direction of the gradient is constant constant. In our case, however, it would appear that the fluctuations are too important. We have therefore built a setup in which the direction of the gradient is constant and points lowards the target parameters. We recall that the target parameters are those given by the DFA2SRN algorithm. This is fairly simple to set up, as all we need to do to define a straight line between the parameters randomly initialized and the target parameters. By moving along this segment, we obtain a vector of parameters 6g which we can use evaluate the gradient of the network Re,- This is exactly what did with two variants. In the first one, all the parameters were evolving while, in the second one, we froze the decoder parameters after a single iteration. The aim of the second variant was to observe the impact of the decoder on the gradient.
almost
We used the data from the first experiment to evaluate the gradient, i.e., used the data set of 458 words on the alphabet {a, b} labeled to correspond to the language of strings with an odd number of a's. We initialized On parameters of FP-SRN at the origin, according to common practices in Deep Learning. Using these On parameters and the Or goal parameters, we constructed the segment [0o, 0r] as well as its subdivision {0o, 01....,0pp } containing 10 points on the segment distributed equidistantly. For i 0, I,.., we evaluated the gradient of Rø, over the training set, with a stopping criterion (R,))) < 10 If the stopping criterion is satisfied for i < T' we end up with rough approximation of where the norm of the gradient has dropped below 10-14, So, in order to find better approximation of where the norm of the gradient falls below this threshold, repeat the same procedure on the segmnett [0,-1, 0:]. Then, once the stopping criterion is satisfied again, we start a further refinement.
The statistics in Figure are the value of the Loss, the distance to the target parameters, the infinite norm of the gradient and the proportion of the paramcters affected by the stationary gradient. All this statistics (beside the pie chart) are computed for every single word in the training set. One can observe some varialions in the thickness in the plots, this is due to oscillations in the statistics caused by the computation of the gradient for every word individually and that all the data are disposed on relatively small graphs. Note that the horizontal axis reflects the number of data points collected for the statistics, in the first variant over 60,000 data points for each statistic were collected, and in the second variant just above 30,000.
19

---

Published in Transactions on Machine Learning Research (12/2024)
Loss
||0] Brarget
|VC[Ra
107
900
850
10-1
10-2
000
10-3
Unaffacter
750
10
10
650
64. 9%
600
10:11
550
15
500
2000
4000
6000
2000
4000
6000
0
2000
4000
6000
Loss
110p 0 rargett
[VC(Re))]
900
10-1
850
800
10"4
750
45.0%
Unaffect:
10-1
Affected 54.1%
650
10-11
600
550
10
500
1000
2000
3000
1000
2000
3000
0
1000
2000
3000
Figure 7: Two variants the synthetic experiment, the first row represents the experiment where all the parameters are updated. The second row is the variant where the decoder's parameters are frozen after one update.
In the first version of this experiment we observe the stationary phenomenon occurring at distance to the target parameters over 500. In this configuration, the loss converges to zero even if the FP-SRN parameters have not reached the target parameters. Given the experimental setting, this cannot come from over-fitting the impact of the data on the change of parameters is small. It be the case that the learned FP-SRN corresponds to finite part of the language, already observed by Weiss al. (201)). But it can also be the case that the learned FP-SRN corresponds the correct language since there may be several combinations of parameters that can be used to simulate the operation of the same DFA. Though of general interest, this FP-SRN is not saturated, which puts it out of the scope of this work: the fact that the loss converges does not invalidate our assertion about the impossibility to learn saturated FP-SRN.
In the second variant, we have frozen the decoder's parameters after just one update. In this case, we observe that the loss does not converge to zero, and this can be explained by the fact that the decoder does not dispose of suitable parameters for the required task. Nevertheless, frozen decoder does not affect the encoders gradient, just as predicted by Theorem 16 Moreover, il seems that the stationary gradient is reached in less iterations than in the first variant, fact that we do not explain, but which is an interesting question by its own. Finally, the proportion of affected parameters by the stationary gradient is smaller in the second variant because, despite having no effect on the encoder's ' gradient, the frozen decoder's parameters did not grow and thus can be affected by a gradient. with coordinates smaller than 10-14
Figure 7 reveals that the synthetic experiment validates Theorem 16 in the sense that by heading towards parameters that will saturate the FP-SRN the gradient will experience the stationary phenomenon. More- over, this experiment shows that learning saturated FP-SRN by gradient descent is even harder than what is predicted by Thcorem 16 since for this particular example the theorem predicts a stationary behavior at distance 6.16 to the larget parameters, and we observe here that all the gradients parameters are below the rounding error threshold (i.e. below 10-14) at distance over 500. We illustrate this fact in Figure g This discrepancy with what predicts Theorem 16 can be explained by the use of loosed upper bounds Theorem 14 (a triangle incquality involving lot of elements) and the consideration of the worst case scenario with the Lipschitz constant, Pr, of the Loss function fe- We discuss this further in the Discussion (Section 7
20

---

Published in Transactions on Machine Learning Research (12/2024)
700
600
500
Target
400
300
Empirical failure
200
Theoretical failure
100
400
600
800
Figure 8: Representation of the synthetic experiment in 2D. The initial parameters 0g are randomly chosen around the origin, and the OTarget parameters represent the target parameters provided by the DFA2SRN algorithm. During the experiment, the parameters are selected on the blue line and the gradient of these parameters are evaluated. The orange disk represents the Fuclidean ball centered at OTarget whose radius is predicted by Theorem I6 and the red disk represents the zone from which the gradient is empirically stationary.
7 Discussion
In this work we studied theoretically and experimentally the behavior of SRNs subjected to finite precision gradient descent training. We have shown that it is not possible obtain saturated SRNs by gradient descent, in finite precision, with a fixed training step. We discuss in the next paragraph that this result is easily transferable to the case of evolutionary but bounded learning steps. Our approach consists in: exhibiting set of parameters that will induce, in finite precision, saturation in FP-SRNs and a stationary gradient, 2) showing that this behavior persists in a sufficiently close neighborhood of This result shows that finite precision induces the existence of areas the parameter space that are not accessible by gradient descent. We then show that the parameters that saturate the SRN produce functions of interest bocause it is possible to simulate the operation of any DEA. This the result of the algorithu.
A first clement of discussion is that result stands only for the gradient descent algorithm with fixed learning rate a. In fact, it is automatically extendable to the case of a variable learning rate (ot) where D > 1, as long as {a is bounded. By setting == maxigigD aj the result remains true for any aj. A second element of discussion is that our result, though stated for a classical gradient descent, is applicable to the widely used stochastic gradient descent: as all gradients are null under the assumptions of Theorem 16 so their mean on any batch. In this work we have considered the case of binary classification which can effortlessly be extended to multilogit classification. Indeed, Decoder with output dimension 1 can be seen independently from the Decoders parameters none of the Sub-Decoder's gradient will influence the Encoder's parameters. Another straightforward extension of our result concerns other activation functions. Indeed, a similar argument can be made concerning any bounded function, like the hyperbolic tangent: the only difference being the value that saturates the activation, and a different expression of the boundary Ç. The same goes for the algorithm DFA2SRN, the modifications realize are in matrices W and V. The saturation of the tanh will produce vectors in f-1, 1 so instead of having a one-hot encoded vector the decoder will produce vectors with unique 1, and -1. This family F(-1,13 of vectors forms basis in RA hence
concatenation of different Sub-Decodes of dimension 1. Since result stands
21

---

Published in Transactions on Machine Learning Research (12/2024)
can define an invertible matrix O that maps F(-1.1) to the canonical basis formed of one-hot encoded vectors. By defining W = We and V ve we will obtain a FP-SRN with tanh activation function and that will simulate the DFA. A potential line of research would be to reduce the gap between theory and empirical results. In fact, in Section 0 we found significant discrepancy between the prediction of Theorem 16 regarding the appearance of the stationary gradient phenomenon and its effective appearance. This difference can be explained by the use of loose upper bounds in the proofs of Theorems 14 and 16. The first one is in the ipplication of a triangle inequality in the proof of Theorem [4] A second non-optimal upper bounding is applied when considering the Lipschitz constant of the Loss function. This constant, denotes PL: plays an important role in Thcorem 16 It represents the worst possible case in the deviations between Ra and its neighbors Rg. We think it is possible to remove the constant pr. by leveraging the 3-saturation assumption. Indeed, we have guaranties on the deviation between Rg and Rot0, which could allow to avoid the worst-case scenario represented by the Lipschitz constant PL.
One can wonder the interest of the class of SRNs that we exhibit an example of non-learnable class. Notice first that any RNN behaves like finite state machine in finite precision configuration (Pozarlik) 1998): its hidden state can only store a (huge) finite number of configurations. It is thus relevant to use the simplest finite state machines, the DFA, as a starting point. Then, even if its construction is not trivial, it covers a large class of functions thus assessing the interest of the theorem. Finally, the algorithm constructing an SRN from any DFA is of interest by itself. The algorithu of Minsky (1967) is designed for RNNs with non continuous activation functions, í.e. RNNs that are not used nowadays. The closest paper on the subject (Siegelmann, 1996) shows that for a given DFA with [Q] states operating on an alphabet of size |Σ] there exists an SRN with 3 Q||[] neurons that simulates the computation of the DFA. However, its proof is not constructive and thus does not provide an algorithm to build such model.
After discussing some direct extensions to our work, would like to discuss the perspectives. The first direction is to relax the saturation hypothesis. Indeed, as it is formulated, the 3-saturation is a strong hypothesis. Mitarchuk et al. (2024) propose a relaxation to the 3-saturation that they call DS-B-saturation standing for Desynchronised Sliding 3-saturation. The idca of this definition is that within a sliding window of F elements, every Encoder neurons has to saturate al least once. The authors demonstrate that with this hypothesis a SRN can sill be robust to perturbations. Hence, we want to explore potential extension our work in this direction. Another direction of work would be to extend this result that stands for sequence classification corresponding to many-to-one, to problems where we need to produce sequences many-to-many situations. Finally, since our work shows that gradient descent with a bounded learning rate is not well- suited to achieve saturation in finite precision, despite the proven interest of this notion for learning long term dependencies, an advice to practitioncrs could be to look cither for new regularization terms forcing saturation in the loss or even for other learning algorithms than gradient descent. This research direction ochocs current efforts in low-precision learning and the determination of optimal hyper-parameters (Blake)
et al. 2024).
Related works
Sum et al. 2019) study the gradient descent algorithm for feod-forward networks. They study the behavior of the algorithm when the network weights are noisy. They assume that the network weights and the arithmetic are based on finite precision, and two cases are distinguished: 1) fixed-point arithmetic, 2) meating--oint arithmetic. They show that even slight noise in the case of floating-point arithmetic can deviate the learning algorithm. Karner et al. (2024) consider training a feed-forward network with ReLU activation under the assumption of finite precision. Since the type of network studied in this paper is a piece-wise affine function, they tackle the established fact that network depth causes an exponential increase in affine parts. They show that it is highly unlikely that the network obtained after training exhibits an exponential amount of affine parts if the network is trained in finite precision. Colbrook et al. (002 consider the class of inverse problems, and show that for any finite precision set up with M digits of precision there exists an infinity of inverse problems that cannot be learned by neural nelworks. Their work is of a greater scope, because they do not focus on a specific learning algorithm. Fono et al. (2022) address the problem of the limits of artificial neural network with an even higher standpoint. The authors go back to the limits of Turing machines as digital machines, thus positioning neural networks as a subset of digital machines unable to cope with non-computable signals.
22

---

Published in Transactions on Machine Learning Research (12/2024)
References
Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
C. Blake, C. Eichenberg, J. Dean, L. Balles, L. Y Prince, B. Deiscroth, A. F. Cruz-Salinas, C. Luschi, Weinbach, and D. Orr. u-y p: The unit-scaled maximal update parametrization. arXiv preprint arXiv:240..17465, 2024.
R. Chandra and M. Zhang. Cooperative cocvolution of elman recurrent neural networks for chaotic time series prediction. Neurocomputing, 86:116 123, 2012.
S. Chung and H. Siegelmann. Turing completeness of bounded-precision recurrent neural networks. Advances in Neural Information Processing Systems, 34, 2021.
M. Colbrook, V. Antun, and A. Hansen. The difficulty of computing stable and accurate neural networks: On the barriers of deep learning and smale's 18th problem. Proceedings of the National Academy of Sciences, 119(12):02107151111, 2022.
J. L. Elman. Finding structure in lime. Cognitive Science, 14(2):179 211, 1990.
R. Eyraud, D. Lambert, B. T. Joutei, A. Gaffarov, M. Cabanne, J. Heinz, and C. Shibata. Taysir compe- tition: Transformer -nn: Algorithms to yield simple and interpretable representations. In International Conference on Grammatical Inference, pp. 290- PMLR, 2023.
A Fono, Boche, and G Kutyniok. Limitations of deep learning for inverse problems on digital hardware. In Sth International Conference Computation Harmonic Analysis. 2022.
S. Hochreiter. The vanishing gradient problem during learning recurrent neural nets and problem solutions. International Journal of Uncertainty, Fuzziness and Howleede-Baseed Systems, 6(02):107-116, 1998.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 983): 1997.
C. Karner, V. Kazeev, and P. C. Petersen. Limitations of neural network training due to numerical instability of backpropagation. Adv. Comput. Math., 50(1), February 2024. ISSN 1019-7168.
P. Lara-Benitez, M. Carranza-Garcia, and J. C. Riquelme. An experimental review on deep learning archi- tectures for lime series forecasting. International journal of neural systems, 31 (03):22130001, 2021.
J. Li, Z. Pei, W. Li, G. Gao, L. Wang, Y. Wang, and T. Zeng. A systematic survey of deep learning based single-image super-resolution ACM Computing Surveys, 56(10):1-40, 2024.
A. Mchrish, N. Majumder, R. Bharadwaj, R. Mihalcca, and S. Poria. A review of deep learning techniques for speech processing, Information Fusion, pp. 101869, 2023.
W. Merrill, G. Weiss, Y. Goldberg, R. Schwartz, N. A. Smith, and E. Yahav. A formal hicrarchy of RNN architectures. D. Jurafsky, J. Chai, N. Schluter, and J. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 443 443-459, Online, July 2020. Association for Computational Linguistics.
M. Minsky. Computation. Prentice-Hall Englewood Cliffs, 1967.
V. Mitarchuk, C. Lacroce, R. Eyraud, R. Emonet, A. Habrard, and G. Rabusseau. Length independent PAC-Bayes bounds for simple RNNs. In S. Dasgupta, S. Mandt, and Y. Li (eds.). Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238, pp. 3547-3555, PMLR, 02 May 2024.
M. Mohammadi, F. Talebpour, E. Saface, N. Ghadimi, and O. Abedinia. Small-scale building load forecast based hybrid forecast engine. Neural Processing Letters, 48:329 18:329-351, 2018.
23

---

Published in Transactions on Machine Learning Research (12/2024)
R. Pascanu, T Mikolov, and Y Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on Machine Learning, ICML, 2013.
R. Pozarlik. What type of finite computations do recurrent neural networks perform? In L. Niklasson, M. Bodén, and T. Ziemke (eds.), ICANN 98, pp. 1065-1070, London, 1998. Springer London. ISBN 978-1-4471-1599-1.
Ribeiro, K. Tiels, L. Aguirre, and T. Schön. Beyond exploding and vanishing gradients: analysing RNN training using attractors and smoothness. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS, 2020.
R. Rojas and R. Rojas. The backpropagation algorithm. Neural nelworks: a systematic introduction, pp- 149-182, 1996.
R Rueda and MC Pegalajar. Energy consumption forecasting based on elman neural networks with evolutive optimization. Expert Systems with Applications,
2018.
Siegelmann. Recurrent neural networks and finite automata. Computational intelligence, 12(4):567 574, 1996.
H. T. Siegelmann and E. D. Sontag. On the computational power of neural nets. COLT, pp. 440 449, 1992.
J. Stogin, A. Mali, and L. Giles. A provably stable neural network turing machine with finite precision and time. Information Sciences, 658:120034, 2024.
J. Sum, C. Leung, and K. Ho. A limitation of gradient descent learning. IEEE Transactions Neural Networks and Learning Systems, 31(6):2227-285 2232, 2019.
S. van der Poel, D. Lambert, K. Kostyszyn, T. Gao, R. Verma, D. Andersen, J. Chau, E. Peterson, C. St. Clair, Fodor, C. Shibata, and Heinz. Miregtest: A benchmark for the machine learning of regular languages. Journal of Machine Learning Research, 25(283):1-45, 2024.
G. Weiss, Y. Goldberg, and E. Yahav. On the practical computational power of finite precision RNNs for language recognition. I. Gurevych and Y. Miyao (eds.), Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, pp. 740- Melbourne, Australia, July 2018. Association for Computational Linguistics.
J. Zhang, J. Zhai, and H. Wang. A survey on deep learning in financial markets. Proc. of the First International Forum on Financial Mathematics and Financial Technology. Springer, 2021.
24

---

Published in Transactions on Machine Learning Research (12/2024)
A General results on and proof of Theorem 16
A.1 General results about o
In this section we state and prove series of results about the sigmoidal function
Lemma 17 Let o ReI Ite-a. For all 2 1/4 we have d'(x) S e and for 1/4 2 > 0 such that
In
1+vT=4 1- we have: S
Proof Of the lemma
At first we recall some properties of the functions a and o'. We have:
V=E
o' is symmetric:
VxERo(()) d-xx
and
= ( - oz))
Moreover the maximum of o' attained on x 0 and equal to 1/4, thus the first claim of the lemme is trivial. Now we assume that <<c 1/4 and going solve the equation:
(z) (x))
This is quadratic equation if we substitute (xx by y and write the equation as:
1タa - c 0.
By hypothesis 0 0/c51/4, thus the above equation admits two solutions:
v1
4c
1 -
V1
2
The sign the dominant factor is negative thus all the real numbers y that satisfy:
Sc
are outside the open interval | 1+ In our case we have supplementary restriction on that
is E [o, 1], since = azx). In order to obtain a bound for æ, it is sufficient. to apply a on 1+vI-1 Hence:
2
1+ v1 4c
I+VI- 2
2
=
1 1+vl-
2
1 v - 4e
= In
vI
Thus if In
1+ 1+V1-1c de
then o'(x) <
The symmetry of a' extends the result: for all such that
4c
|
In
14
T+VT=4
have o'(z)
1-
The following lemma a more specific version of the previous lemma.
Lemma 18 Let 1, 2 and s S 1 tree real numbers. For all |x| 2 In
s be
we have:
xm(1+))
(x)
zao' (x) < 1 and 1- 1-zao'())) Se
25

---

Published in Transactions on Machine Learning Research (12/2024)
1 1tyl- de
Proof Let 2 > 1, 2 4 and 0 < E 1 be three real numbers and r 2 In
sa(l+e)
By Lemma 17
just above, we have that:
E d'(x)
zu(1 1 + +)
because < S 1 and za 2 4. And we obtain that:
zao (x) = E <1.
(1 +
We set c: ax)()) and from the previous equality one can deduce:
- (1 + E)2c
(1 (1+
20 EZC
20 = 6(1 2c)
20
8
- 2C
Lemma 19 is a result about the convergence rate and the approximation of o'
Lemma 19 Let æ, a E R4 two positive real numbers such that a S x - 1.5, and a IR x + Ite the sigmoidal function. Then:
S d' ae (x-a)
Proof Let x, E R. two positive real numbers such that S - 1.5, and let o R D I#e- We recall that the sigmoidal function is at least twice differentiable, with for all
(t) = att((1o((t) d'(1) = o' (20(t))
-
One can observe that (f) < 0 for t > 0, because o' > and (1 (t) < 0 on positive real numbers t. Morcover, it is casy to see that (1 - 2t)()) E [-1,1] for all real numbers t. Hence 0 S --11- 2x)()) s 1. On the other side, from the definition of (t) have another expression of its derivative
dt) (1+e-1)2 e-
From the mean value theorem we obtain that there exists E|æ æ1 such that:
o'lx (x a) = d') aaaaaa"00 (c))..
The function o" reaches its global minimum in the interval 11, 1.5l, and by assumption we have x- 2 1.5, Therefore by summoning the fact that o" is strictly incrcasing function on the interval 11.5, +ool (i.e. -o" is a strictly decreasing function on 11.5, +oo we can deduce that:
d' dxr-a) - a) S oz( o"(x a)
= o' d'xx a)
1 - 20 a)
<d'(x) a..aa d' a)
S 5o((2) (2) + + (x-a)
We finish this subsection with result about the convergence of geometric series involving o'. This lemma is very handy for the proof of Theorem T6 and Theorem
26

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma 20 Let a > 1, = a, ( = In
1tv1-42 and σ R x + Ite E [0,1] the sigmoidal function. 1-VI-13
Then for all 0 we have:
d'(stt)<<l <
Proof Let a > 1, == a 5 In 1+V1-1 dC( = 2, thus d'({) = 1. To conclude, we know that a strictly decreasing function on the interval [0, -of Thercfore, for any > we can assert that:
1-VI-1 and R x it Ite== E [0, By Lemma 17 we know that
d'(s+ + <1
A.2 Proof of Theorem 16
Definition 21 (Recall of section 3)
Let Ry be a SRN with M,. | SUWb, bj M - and T an integer. For parameter ma,j in the matrix M, define path 7 (,...., 7k) of length for < < T finile sequence of (M,, M.) parameters, such that for k = we have
Moli), for k = 2 we have my,i for some 1 S 2 I h. For the case k 2 3 we define 7 such that 7 = me, for
" Mo[e] and some 1 1 e S h, for all 1 < < k 7/-1 = my,t, = myr and 7s+1 mr,,0- Finally, we define the set Fig containing all such paths.
This section is dedicated to the proof of the criterion for BPTT failure. To do this we are going to prove that, under the hepotheses of Theorem I6 the update generated by GD rounded to zero for every parameter in the SRN. We position ourselves in the context of binary classification ((W1.))).... (WN. ]N)} is the labeled training dataset where w; = {x | C G f.c. the data is vector embedded in dimension 2 1. Ro is FP-SRN with in hidden dimension h 2 1, input dimension and output dimension o = 1. We fix parameter ma,j in the encoder weight matrix M,, and compute recursively the gradient on the word w with |w| T. We already established in Equation that:
sequences, $
OC(R" v) OC(R", .v) Or
o' (bT)
Σ NELr a=1
II
7s d'y, (XT 2 hy
(4)
8mi.
By the BPTT technique aC(R" 0z MM (hr) Exer., II. 7/- of (XT-a hT 1) contains the update
for parameter ma,j in every layer of the unrolled neural network R", The following lemma deals with the number of paths in Tig depending on their length.
Lemma 22 Let R be FP-SRN and w word of length T 2 1. Let mij be a parameter in M,. and Fi the set of all paths as in Definition 21 Then we have:
T
Fo = U #}
==1
T
Card(T..)) Σ
Card(fy ET: hl === m))
==1
h
Proof Let R be FP-SRN and w word of length T 2 1. Let may be a parameter in M, and Tij the set of all paths as in Definition 21 The identity
Fú UbEr:
m=1
27

---

Published in Transactions on Machine Learning Research (12/2024)
is trivially true. It is clear the for # w, we have
tr hl= -
because path cannot have two distinct lengths. This proves that:
T Card(Tis)) = Σ Card(fy h1=
= =
Now let i be path of length w we know that Yo ma,i for some 1 S f S h mcaning that we have h possible choices for the index t. Once we have fixed t, we know that Yw-1 = My, for some 1 Ir S h. Once again we have possible choices for the variable r. This argument is true for all Ys in 7, hence we have h possible choices for ry of length w.
Now we proceed to prove the claim of Theorem but first, for convenience, we recall the statement:
Theorem 16 Let G be the set of all float numbers representable in a given finite precision configuration X... Let S = {(w) vi)...... (wN,yx)) be a labeled training set with N samples and where w/ = {xx]==1 c G is a finite sequence of vectors such that all vector X respect ||x&|| for 1 I N and T an integer representing the length of the word wy. We set L G G G to be differentiable loss function, Let 0 the learning rate used in Definition TO Let Ro be an FP-SRN with hidden dimension h, input dimension u and output dimension = 1 i.e. Rs is shaped for binary classification strings. We recall that the row vectors of the matrix M, are denoted m, for 1 I i S h, and that since the output dimension it means that the matrix M. is of dimension h1 We set
m max [m] m E 0}
min {Im]
0 and |m| > 0},
Le. m² is the largest parameter in absolute value and m the smallest, in absolute value, non zero parameter.
We set E = BD with D [log [m)] - (M + 1). We suppose that:
1. For all E {0, 1} the function [0, 1] = + 1 v) is bounded by a constant PL.
2. 3 > 0 such that Rs is (S + sattuaadd where
In 1 I 4z
4
whpr. 1 e 1b = a max((m" + n [|
1 42
Then with A == d'(S + 3) and W the transition kernel extracted from Ma for all 2 Iddi(()) such that
|| Eneoder! || < 7 (1~A|l Alll) the FP-SRN Rato will experience stationary gradient for all non zero parameters
(2+vh)
on the training data set S.
We assume that Rp is FP-SRN satislying the assumptions 1 and 2 of Theorem 16 By Theorem 14 we know that for (0) such that ||]| S (1-A/WII) the FP-SRN Roto is (( + 1/2)-
Proof [Theorem 16
(2+v7) saturated. Indeed we are applying Thcorem 14 in the case where = 1/2. We seloct a vector E dd) such that || < y (1-AA/WI) and will prove that Ro40 will experience Stationary Gradient all one-hot-encoded sequences. We recall that for sequence (w.y) v) E S, |ا|| T, the gradient back propagated in order to update the parameter fu can be expressed as follows:
(2+vh)
(C(Ro-o(w),)) aC(Ro+o(w). oMm (hr) Oma.
Σ TET.,, s=1
II
7s o'y, (WT-s @ hr $ 1).
Or
28

---

Published in Transactions on Machine Learning Research (12/2024)
We set F : @C(Re)o(W))) o (hr). We will discus the variable F later. As stated above the FP-SRN M.
Ro= is 7/2 -/ttssatdaddddd Therefore, meaning that for all 1 S 8 I h and for all S k & we have:
(m,, wk @ h 2 1/2
implying by the properties of o' that:
d' d' hi-1)) S d'(s + n/22).
Moreover, by hypothesis on 0, for all parameters my,t in the matrix M, have
mnrl S m + 1 (1 (1-A|
2 (2+vh) S m² +
Let 7 E Fig be path, from the (6 + 7/ 2) 2) saturation of Ro+0 we can deduce that:
hl
by
To oy (et + hir + 1) S
II (m + /n/2)- o'(S + n/2)
s=1
= ((m* + 11/2) d'(S + n hrl
This allows us to derive a bound on (()))),
0m,,,
h EI 7o o' (cr-, -
Σ ((m* + +n/2) o + 1/22) yET
YET
By Lemma 22 we know the exact number of paths Ta.-- We set C ((m* + n/22 o' (()). The function o' is strictly decreasing on [0, oo| Therefore one can derive the following bound:
Σ ((m* n/2) ds + ( ,
Σ EE.
(Im* +n/2) d(())
CF
h C
CT
= hC
1- hC
We know that C max((m"* +n/2), o())) Therefore in virtue of Assumption and with the application of Lemma 17 we can assort that:
hc
hC <1 1
and
1- hC
apLPo
This leads us to the fact that:
hC 1 - 1.CT
hC
hC
1 hC
apLPa
By definitions of F = @C(Ro=a(w)al) (w)xv)
a'ms. (hr)) we have on one side that
8m
d' (hr)
1/4
29

---

Published in Transactions on Machine Learning Research (12/2024)
because for all x E R (z) s 1/4. And on the other side by Assumption 1 we have:
@L(Ro+o(w), S PL
We can conclude that:
ÖL ( Om.,
8
<
Hence Ro+o will experience a stationary gradient on all of its non zero parameters in the gradient descent with a as learning rate.
B Stability of saturated SRNs
Our reasoning is based on certain facts concerning the saturation of the sigmoidal function. Indeed, a FP- SRN R. respecting the assumptions of Theorem [6 found be stable perturbations. These may well be perturbations in the data, or perturbations in the paramcters. We are interested in parameter perturbations, because want to exhibit an Euclidean ball in the parameter space centered on the parameters of R such that all FP-SRN R whose parameters come from this ball, will behave closely to R. This stability is due to the fact that the tanh and sigmoidal functions have small variations near the edges of their target sets. Moreover, because of the exponential in the definition of these functions, they reach the edges of their target sets rapidly.
The aim of this section is to show that it is sufficient to noise only the bias of the parameters. This simplifies the proofs in the sequel, as fewer parameters need to be controlled.
B.1 Propagation of the noise through the iterations.
Definition 23 (Perturbed SRN) Given SRN RR as in Equalion and o Rddem(0), we define the perturbed SRN Ro40 by the following set of equations:
hgg (U+ + de)xx + (W + (w) +b +b+ 0b)
8v (V 0v 0v) + +c 0e)
where 0 = vec(Oy, Ow, Ov, tb, tc), and ho ho-
Perturbed SRNs are central to analysis.
Lemma 24 (Vector variant of the mean value theorem) Let E Rd and let f .dd - Rd be differentiable function such that f(y) = (aa))). where every ft is differentiable. We define Vf = (fi..... S2). Then there exists c E I2d such that:
fly +T) f(y) + (c)
and E y(j] c(j < (y + +) for all S S d.
Proof Let y, Rd, and let j d. By the mean value theorem there exists ej vbil oj (y + such that:
f(y + +)) = fy((()) + f((5) r/j].
We can repeat this operation for any coordinate J < d and create a vector c (cI,..., ca) such that:
f(y f(y) + (c)
The following lemuna is very handy in the expression of the hidden state vector of a fuzzy SRN.
Lemma 25 Let y,y E Rdd for d 2 1, then:
Diag(x)y
30

---

Published in Transactions on Machine Learning Research (12/2024)
Proof Let y, E Rd for d 1, and let 1 d. We define D Diag(x), we have:
d Dyli = Σ D payld
i=1
= Disylil by definition of a diagonal matrix
= x[Sly[
(xOy)]
Lemma 26 (Expression of the perturbed hidden state vector) Let Rs be a SRN and Rp40 a per- turbed SRN with 0 Rddi(()) For all {xx)k=1 X there erists sequence {ck]k=z R such that for 1
4-1
k-s
hg h4 + Σ A(a)
II (A(C--)) n. + A(cx)
where
A(cx)= Diag(o' with cs provided by Lemma 24
1 WA(C=-1) WM(cs-))A((c-))) WA(c.).
n. = -ouxxuux + w
Proof Following the notations introduced in the statement of the lemmaa, we prove the result by induction We analyze the execution of the perturbed SRN Rz. By Lemma 24 there exists 0₁ R such that:
h ((Ux: dux)) (Wh; + b + (b+ 06))
=o ((Ux: + Who + b) (duxi + two + 0b))
(Ux, Wh, + b) + v (c,) o (dux: ww 0p).
By definition of the perturbed FP-SRN we have hu ho which gives the following equality:
(JUXI + twho + Ub) (duxI + uwho + 0b) =: n1
Hence we deduce the equality:
h h + A(ci)ni,
where in the last line set A(c) Diag(o V (c)) and leverage the linearity of the Hadamard product proved
by Lemma 25
We proved the initialization step (i.e. &o 1) but for comprchensibility prove the statement for k 2. By reapplying the same argument we can find vector E R such that:
h ((U Ou)x2+ + (W + @h + A(c,) + (b+ 0p))
(Ux: + W(h; + A(ci)m) + (fuxi + Owh 0n))
- (Ux, + Wh + b) + o (c2) 3 (WA(c))n) + to ( 2 (Uixi + owh, + 0,)
W + AAc2)
h2 + WA(ci)m
2-1
2-s
-h2 Σ A(c2)
II WA(22-))
+ A(c2)n2
31

---

Published in Transactions on Machine Learning Research (12/2024)
Let us assume that for k 2 we have the following expression:
Kmm
HWAca-)) n. A(ce)
hR ha ((s)
II
1=1
By Lemma 24 there exists a vector ck+1 E TR'h such that:
k-1
Ri-s II
IwAcc--)) + ((cx)))) + (b + 0b))
h = (U (0+00)xx + (W + (w)
hes
Σ A(ck)
s=l
1=1
k-1
R-8
=0 Uxx+11+ + W h Σ A(cs)
II
[AACC=)))
n, + A(cx)ms))
+b +1+11111
where nk+1 == Owh + Ub. Now by applying Lemma 24
obtain:
k-1
k-
h =0 (UX+++ + Wh: + + o (cx+1)
W Σ
A(Ca)
II
WAACk)-)) n. + WA(cs) + n
==1
k-s+1
- + A(CR+1)
Σ
II
WA(C [=1
n. + +((c++] 1-A((=+)W((c))m + ((C++))B4
a=l
k-st1
-b +
Σ A(CH+1)
WA(Ck-141)
n, AcC++1)mk41
Thus by induction Lemma 26 is truc for all (xi,...,xrr E X.
The following result is the resilience to noise that saturated FP-SRNs exhibit. This result is based saturation, but the C border is different from the one defined in Theorem 16 To avoid confusion in this result, we have chosen to write Ç and 7j.
Theorem 27 Let Rs be a Č + ia-saturated FP-SRN, with = [WT and Č= In (ト=\-=;) for some f > We assume that Ry is operating one-hot encoded data. We select any real number such that 0 < << 1, then for all = vec(Ou, Ow, Uv. Db, 0c)) (Rdim(0) such that ||l|| s (1 t)ß (1-A (W])) with A o (5 tii) and for all (x1, (x1:-..,TT)
(2+Vh)
X
have:
(2+vB) 1. lle hollo S 1-AIWTT ||01| where ISKST.
2. Roto is ( trī) saturrted
The sequence of hidden state vectors h2 is produced by the perturbed FP-SRN Rp49- This theorem proves, by induction, that saturated FP-SRNs can be stable to parameter perturbations.
Proof Let Ro be Č ij-saturated FP-SRN, with |[W and Č= In 1+VI-1 n 0. We assume 1-VI-1;
that Rs operates on one-hot-encoded data. Let == vec(Ou, Ow, 0v, Ub, 0o) E Rdim(() such that ||]|| < (1-t)n) (1-A]|WII) with A == o'Lā tîj). We also fix a sequence ..x E X. Before we start with the induction proof, we summon Lemma 20 in order to validate the assertion that 0 A
(2+Vh)
W < 1. We start the
proof by induction naturally with = f.e. h h1ll < [I WT [10]] By Lemma 26 we know that one can find C₁ E R such that:
(2+
h h A(c))
(5)
32

---

Published in Transactions on Machine Learning Research (12/2024)
with n1 duxi th ub. We will prove that ||(c))]l I A and || || $ (1 t) and start with the second inequality. One can observe:
n1
||ux + who + 0bll
| || 1100@ww holl + ||*b||
|00||||a||| 0 || + ||b|l..
We have assumed that RS operates on one me-hoot-nnoodd data, thus ||x+|| |l I 1 for all elements of the alphabet.
Moreover, by definition of FP-SRNs and SR.s the norm of the hidden state vector always bounded by hh, leading us to the bound:
mnll s |100l| X1 + [[0 II]bbll| + 1bb1l
|0ul| + v/lwwwl + ||0b||
- | + -/|l dw |nr + |0blI
S ||0|| v ||]|||
= (2 + |1
(2 + vh)
$ (1 - |/ ||||| because 0 <
1
Since by definition ||0|| - -- (2+vh)
assert that ||n|] || s (1-18 t)rj. Consequently for J s h:
mm///ll S 9. We bring the Readers attention on the fact that the bound:
mill S | + Vhlldw// + ||bbIl
is independent of the iteration, dee. for all (x xT} E X' know that for k S ||x||| S because X5 are onc-hot encodings of finite alphabet, and hg E - 1, thus ||hg || S vh. By extension we are able to bound all || by (2 + 10]1 Now we discus the inequality [|A(c)) )ll S A. Lemma 24 describes the location of the vector C1, which is for 1 S - h, cıli] is in the interval x. + m1]b]] x being defined by
= [Ux] + Who b)ll Therefore Jx + n, |i|l 2 Č + tr because |n1l]]| s tij, thus by extension:
न. - -
tn [[]3 + tū. + T|.
We draw the Reader's attention to the fact that
10 (hbli)) 2 5 tî
In order to bound ||(()))], the quantity of interest for us is:
supo'(x) S n- - un -
-ES
which is casy to determine because o' is symmetric and is strictly decrcasing on the interval [0, +oo%. We obtain, quite simply, that:
supo (x)= (č + tri)
z
This reasoning does not depend on 1 5 < h, Therefore we can assert that:
[[A(c:)] | (ci)llo s < + 17).
To up, we have proved that:
33

---

Published in Transactions on Machine Learning Research (12/2024)
(2+v)) ||ا -illoo & [1+A WIl |0],
the first iteration of Roto is (5 + (ij) li)-sed
|[(c))] & A.
pursue with the induction hypothesis which is
for all 1 E (1 [1....k} we have:
-lhi: he hrlloo
(2+ [I+A[
||0||,
the 1th itcration is (5 + ti))ssaturatdd,
|[A(c)]| <
By Lemma 26 we have an expression of the difference between h and h which is:
+++11
b h&+1
Σ A(C++1)
II
WA(Ca-(11) n. + A(CK+1))gHH
h---1
= =A(c+=1)
Σ
WA(Ck-(+1) n. + D++1 [=1
#=1
To simplify the notations we regrouped all the disturbances in the FP-SRN encoder, before activation, in (2+vB)
g. We have to prove that llgil s (I+A/WII [[0]]. [[]]] We recall that A = o'(š + tūi,, by induction hypothesis we know that ||A(c))ll < A for all / e (k....,k)
k} Therefore can assert that
Igll
Σ
WA(Ck-tt1) + DA-1
[ill || + ||n
|]WI]]
||n=|| + ||allll
( | s+1 |n |m
34

---

Published in Transactions on Machine Learning Research (12/2024)
Since summing from k to 1 is exactly the same as summing from to can write:
|z + n
(AIWWI)* + |
( |n.1| ((I ||
(AIIWII)* v1)]
(AIIWI)) ((2+ v1)l
(22 1 w
yet by hypothesis on 0 we know that
((2 + Vn)lol1) S (1 / () t)7-
Hence one can deduce that:
gg S (1 t)rj
For the location of CÆ+1 apply the exact same argument as for C12 i.e.
h a (Ux++1 + Wh+ + b m)
= (UX++1 + Wh: + b) + ()).
We established that for all 1 j S h, |g0l S |g| (1 1)7, Therefore:
cx+1li] E - - - 7. - 1
17 +
Hence by the properties of a' function, and of the A(C++1) matrix we assert that ||A(c++))| S (š 00'(5 tr). We conclude that the proof by induction is valid.
In Theorem 16 and Theorem 14 we use a notion of thresholds Ç, Č in the saturation of the activation function Ø. Morcover, Theorem 16 these two values are interacting, leaving ambiguity as to whother they can interact. The following lemme there clear this ambiguity.
Lemma 28 Let Ro by (3 + saturratd FP-SRN with Ç In 1+ TII
and O. Let ( 0
1- TWT
and > be two real numbers such that Ç + 11 = ? i and ? S C, then for all 2 E (idim(0) verifying
|| < y (1 [| with A = o'(5 + n/2) the FP-SRN Rot9 is (5 + -stuurdddd
24
14 11+ 1- TWT and 0. Let ( 2 0 and 17 > 0
Proof Let Ra by ( + satuuratd FP-SRN with Č = In
2 be two real numbers such that Ç 1 ट 7 and Č < Ç. Let 0 E (0)
verifying ||0|| < 2 24
(1-AI[W] From
the hypothesis <+1 1 +++ 7j one can deduce that
< = Č + 1j -
n/2 1 + 7j ()
35

---

Published in Transactions on Machine Learning Research (12/2024)
The hypothesis Ç 2 Ç implies that S ny Therefore, there exists E [0, 1] such that = =1 10-)) t) fj. In the same way, the quantity (+ 7/2 can be transformed into Ç t i), indeed:
<+ (+ 1ー 7/2
= - -
= =[+ fj (1 t) -
=Ç+b-
Hence = ( = +( and n/2 = (1 - t) -) with t E]0, 1[, allowing us to conclude by Theorem
that the claim of Lemma 28 is true.
C DFA2SRN algorithm
In this appendix, we provide a proof that the algorithm presented in Section 5 is well defined. We start by recalling the definition of the Euclidean division, then the algorithm DFA2SRN, followed by the proof of its well definition.
Definition 29 (Euclidean division) Let (l,5) two positive integers greater then one. There erists unique couple (a, b) of positive integers such that:
aj + b where 0 < j.j..
We call a the quotient and b the rest. We denote the quotient j == a.
Now we recall the algorithm DFA2SRN.
Let D = (E, Q, 22, 6, F) be a DFA. We suppose that the alphabet E = (ei,.... C.) is set of one-hot vectors. We recall that Q --1,.-....0. .QQ} is the set of states, 9i is the initial state, 5 Σ x Q - Q is the transition function, and F C Q is the set of final states.. In order to simulate the DFA, we have to simulate the transition function, to encode every state such that it can be read by the FP-SRN, and then the model has to simulate the function discriminating between elements the DFA follows the spirit of one-hot encoding. The transition function is simulated by the encoder and the discrimination function will be simulated by the decoder.
and Q F. The encoding of the stales of
The main idea is to make the hidden states h, t 2 be encoding of the state q reached in the DFA while parsing a sequence up to its th element. By construction, using the saturation float J, the FP-SRN R, will produce a One-hot hidden vector at each iteration. In order to perform the simulation we need to set the dimension h of the hidden vector to = | [Q], and groups of Σ One-hot encoded vectors will represent a = {a, b) an alphabet with two symbols, the vector (1
0) 0). More generally, vectors where only one of the first Σ coordinates is equal to 1, and the others are nil, will represent the q1 state. In this construction, M, will encode the transition function, and M, will encode the E relation. In the rest of this section we will refer to the FP-SRN definition version 2 and use the formalism of kernels W the transition kernel U the imput kernel and v the output kernel (the output kernel is vector because the output that we need is scalar in {0, 1)).
unique state q E Q. For example, will correspond to the state QI, but so will (0 1 0
We set [1 == Card(Q), [Σ] = Card(E). We assume that Q = {U1, (21:9.--0 ........... tttee and we define Ip C (.....,QQ[[)) with
(i.i+1,.... (i+ [i]) - 1} c IF + qi E F)
The linear parts of the SRN are defined by:
W e GI Σ U G |[
ho e U with bo! bo[1] = 1, ho [i] = if 1;
E Q with vijl = J if j 1F and Jf 1F
36

---

Published in Transactions on Machine Learning Research (12/2024)
J is the smallest float mumber saturating the activation function as defined in Lemma 3
We define == 2J
Ql identity matrices xx] piled up. For the construction of W, we start by
defining for every state gk. 1 S h = [Q], column vector w E G Q by the following rules:
R1: For 1 I 8 و if 0(g.. a..) = dj then w [r]=-1 with r = (j 1) +
R2: All the other coordinates of w are set -3
Note that by definition of DFA every vector w has exactly | coordinates set -1 and 1)|=) coordinates set to 3. Also, by definition of DFA, every state can be reached by | transitions. The rule RI defines an encoding for (4k, as o(ge, a.)) Therefore, the vector w contains all the transitions starting at 9k-
Afterward we generate, for every qs E Q, the matrix:
W
w
w
w1 E GI
(6)
times
W J. [W]
W
w GIIINIII
In the definition of W the vector w is repeated Σ
limes.
Proof In the following paragraph we prove that the constructed FP-SRN is simulating the functioning of the fixed DFA. For this purpose, in first place, we have to prove that, for any word w = = er E Σ* of length T, there exists a well defined correspondence between
[o(Uei +
who- م (q), (1),0" 8" (q), ele)).... ... 8 w)]
(7)
The correspondence f will be explicitly defined later. Secondly we will prove that we have:
[blan.) E F]] + [v(r)) =
(8)
The proof is by induction on ls E {1....,T), T), and we naturally start with ie = 1. Let e, E E with 1 s [[] and ho the initial hidden state vector as defined above. We are going to compute h = a (Ue, Wh) and show that h will have unique non zero coordinate whose position encodes the state 8* ("1 e,) 8(q) e.). We start with Uc,:
Ue = 2J if (Is = s modulo [Σ]) and 0 otherwise.
We obtain this because of the structure of U ([>)) identity matrices piled up and multiplied by 2J) and e, is a onc-hot encoded vector. Then we proceed to the computation of Why:
Wha J. w by construction of W and definition hg-
Indeed, we have ho = and for 2 < i < [ boli] = O. There is a unique E Q such that 8(91, c.) q.
We assume that 5(g1, e.) = for < j < [Q]- By constouction of w we have:
w
with
1)/2 +
referring to the rule RI. By definition of a DFA, it is not possible to have j E (l,..., QQB + and 5(g1. e.) = qj. Therefore for all e |Q|
such that w [+] = - we have:
(f=s modulo [E]
This last point is important for the computation of Uc, + Who, indeod we will have:
(Uc, Wha) [r] = 2JJ J = J
(Ue, + Who) [t] = 2J 3./ or 0 3. 0 J
37

---

Published in Transactions on Machine Learning Research (12/2024)
with E (I....,/00 [Q]} t t+r. Most importantly, the vector Ue, + Who has only one coordinate with the value J, and the other coordinates are less than -J Hence when we apply in finite precision to Ue, + Who we obtain the vector h with the property:
h [r] 1 and for t + hi -0
Since (i-1)|2]++ s, by Definition 29 we get that r///2] +1= j, corresponding to the state qj = e.).
s, Hence explicitly define the correspondence as follows:
T Q 12 h (+++g(h))) g(h)/ E fL...... 1Q13,
where g is the function that returns the index of the greatest coordinate of the vector h.
We proved that the FP-SRN R successfully simulates the DFA D on all words of length & = 1. We make the induction assumption that for all words w E" such that |w| T S k we have:
We have (hi....,yr) م (
The hidden state vectors hi...., hy are all one-hot encoded.
We are going show that induction hypothesis true for + 1.
Let E Σ" such that |a|| = let (hi...., ha+1) the sequence of hidden state vectors produced by R from the execution on w. We know that w G es, where ä is a prefix of w, of length k. We know for sure that [ 2 1 because by assumption & 2 1. By the induction assumption we have that:
k+
(h.....,h,) hR) م
(41,)))))
and all hidden vectors h,, for 1 S 1 < k; are one-hot encoded. We also know by the induction hypothesis that for j = f(h;) we have q₁ = 8 (q), It sufficient to apply the same arguments as the case k = 1 in order to conclude the proof by induction. Indeed by construction of the matrices U and W we know that there exists a unique F E [Q/E)) such that:
(Ue; + Wh+)[F] =
(Ue; Wh:) S J for *
and by the construction of U and W, and more particularly by construction the vector w', a vector encoding all possible transitions from the state qj we know that := corresponds to 93 = 8* (q1,w. From the identity just above we can deduce that after the application of the activation function a, the saturation will occur and the outputted vector h will be one-hot encoded, with a the position j. We can thus conclude that the proof by induction is valid.
D Finite precision arithmetic's results
Lemma 30 (smallest increment) Let (B,M,X X) be finite precision confiuration and a G(B.MX). We define LM as the largest positive numbers in G(M,M,)). If S < LM there exists G(B,M,)) such that in finäte precision arithmelic:
atr> and 0 15 s<r, a+s=a
Proof Let (B, a finite precision configuration and a E G(B.M.)-- We define LM as the largest positive number in G(B,M.))- We assume that 0 < a < Las and we write the float its normal form:
-0 am Bd
38

---

Published in Transactions on Machine Learning Research (12/2024)
with a₂ E (0,.... B 1} for 1 isis M and 0. Now define the minimal increment
r == B*--M++ M+1
By hypothesis we have a < Las- Therefore a + rr S L and:
a a+r=ajan aa a^ + B
Σ aBB(-tt) (am 1)B(- Bd.
a
Now if one considers float number 0 < < r with 81.82 ... 8.. BAr from the definition of r one deduce that A < A - M + and Therefore A I Xa M. Hence + s will be rounded to a.
Lemma 31 (Underflow boundary) Let (B, X) the finite. precision configuration. We define
L and m l= Bx - u. If M < min(u,1} 1} then there erists J such that o(J) = and (-J) = 0 and for all positive float numbers s such that J - J we have a- - 5)) #0
Proof The total number of exponents obtainable in this configuration The configuration (B, M. X) allows to have = _ positive exponents and 1 := 8 u negative exponents based on Definition Let because 1 + B-1 will be rounded to in virtue of the Hypothesis 31 we know that M min(u, l]. On the other side we get a(-K) T5
== In (B) we have on one side: o (K) = T+e- I I+
I+B B = B- the smallest number we can have in the finite precision setup (B,M, M, X). Consequently if
WC set = + we get:
K-r B < <-!
Hence we will have o(J) and o(-J) < B-1 Therefore a--J) will be inevitably rounded to zero.
Note that in the EEET 754 norm the exponent of the 32 bit float numbers we have / = 128, u 127, and the assumption M < min u.() I} is satisfied.
E Numerical experiments
This appendix is dedicated to more in-depth explanations of the numerical experiments described in Section 6
For our vanishing gradient experiment we randomly generated a labeled training set of 458 words on the alphabet {a, 6). Words with label 1 are those containing an odd number of a's, and the other words are labeled by We defined a set of goal parameters @arreet corresponding Section 4.3 and we randomly defined initial parameters Ornitiat- In order to simulate the best case scenario where the training of the FP-SRN would lead from Inittial to OTarget in straight line, defined a sequence of parameter vectors {0x [0x) with
the parameters of the example of
0. Oinitial
0 = O2 (0rarget Initial)
where a predefined learning rate. The goal of this setup is caleulate V. (Re, (w). 8) over the whole training dataset, for & 1, until |/ (Ro, (w),v)ll 10-11 for all (w, y) S. Once the stopping criterion was reached at 0s, reproduce the same procedure with more refined sequence of vector {8) Je2o defined by:
8 6--1
0' 0 1 022 + a' (OTarges O1nitiat)
39

---

Published in Transactions on Machine Learning Research (12/2024)
Loss
||0] Brarget
|VC[Ra
107
900
10-1
10-2
000
10-3
Unaffacter
750
10
10
650
64. 9%
600
10:11
550
15
500
2000
4000
6000
2000
4000
6000
0
2000
4000
6000
Loss
110p rargett
[VC(Re))]
900
10-1
800
10"4
750
45.0%
Unaffect:
10-1
Affected 54.1%
650
10-11
600
550
10
1000
2000
3000
1000
2000
3000
0
1000
2000
3000
Two variants of the synthetic experiment, the first row represent the experiment where all the parameters are updated. The second row is the variant where the decoders parameters are frozen after one update.
Figure 9:
IVEUR
10240
64
80322
0112
0125
67
0.62
08
68323
0.004
60332
0.804
Figure 10: Regular SGD training where the four statistics of the learning experience of the odd a's language. The curves in blue correspond to the statistics recorded during training, and the curves in orange are the rolling averages.
where a' a a strictly smaller learning rate. The refining, as we repeat it, allows to find better approximation of the point where the gradient becomes stationary. In our experiments we applied the straight line gradient evaluation with learning rates E {0.1, 0.01, 0.0013.
Two version of the strait line gradient evaluation are displayed in Figure g one where all the parameters are updated represented by the blue graphs, and the second one where only the Encoders parameters are updated and the Decoders parameters are frozen after one update. Figure displays, from left to right, the graphs of: the Loss, the distance to the target, the ||Gradient]] infinite norm of the gradient, and the proportion of the parameters affected by the stationary gradient. We recall that parameter my experiences stationary gradient if in finite precision
ac A (w,y) S mi.j Ir dma. (R(w).y) = mm.j-
In other words, for the setup where all the parameters are updated, 64,9% of the parameters are experiencing the stationary gradient once the experiment is halted.
Figure 10 represents our attempt learn a model with the same data by applying regular SGD. We used the same training data set for the previous experiment, and trained SRN 20,000 batches of size 32
40

---

Published in Transactions on Machine Learning Research (12/2024)
Loss
18x+1
0x1l2
|vc[Ro --
|0 -
109
10-1
109
10-2
10
10
10
10
79.0
10
10000
20000
10000
20000
10000
20000
10000
20000
Figure 11: Training with SGD on the language 04.02.TLTT.2.3..
Loss
1 1
0x112
||0 Braggtt
10
10-2
103.4
10
10-1
10-3
103.2
10-
10
103.0
10
10
10-3
10000
20000
0
10000
20000
10000
20000
10000
20000
Figure 12: Training with SGD the language 04.02.TLTT.. T.TT.442.3
words. We adopted a slightly different method from that usually used with pytorch or keras frameworks, since for each iteration between and 20,000 we randomly selected 32 words from the 458-word training dataset. Usually the dataset is shuffled like deck of cards, after which the batches are trained and fixed for the entire training
The statistics observed in this experiment are: the Loss, the Euclidean distance between two consecutive parameter vectors |0 - 0,-1112,2, [V v) and the euclidean distance to the target, the target being the same set of parameters as in the experiment described just above. In gradient descent learning scenario, the nature of the data not known priori, so the distance to the target makes little sense. For this reason, we use the Euclidean distance between two consecutive parameter vectors, order track down some kind of convergence through the Cauchy criterion. Of course, in our experimental context, we know the data precisely, and thus the associated DFA. We therefore also displayed the distance to the goal parameters. With these experiences, parameters into stationary gradient regions.
conclude that SGD cannot even push FP-SRN
As argued in Section 6 the language on the alphabet {a, b} formed of all words containing an odd number of a's falls into the highest complexity subclass of regular languages. To avoid any kind of bias linked to the complexity of the formal language, we have selected set of languages in the van der Pocl et al.] (2024) benchmark. The 9 selected languages cover the entire complexity spectrum of the benchmark. We reproduced the same learning framework, with learning samples for each 1000-word language and the learning algorithm as for the experiment illustrated in Figure [O The 9 figures I
16 18 and 19 are the reproduction of the experiment 6 on 9 MLReg dataset languages van der Poel et al. 2024h. We have reproduced exactly the same experiment setup and collected the same statistics as in the experiment. For these 9 experiments, we can draw the same conclusions as for the G experiment. Wo not observe any convergence within the different statistics, after 20,000 mini batches. We conclude that the complexity of the regular language not impact-ful full in this experimental paradigm. We recall that we randomly drew each mini-batch of the 20,00 20,000, unlike the usual setup where the training set is divided into mini-batches before training which will not change.
41

---

Published in Transactions on Machine Learning Research (12/2024)
Loss
10 1 Ozlla
[
1|0 - -0ragett
2
10
187.5
10:3
100
10
187.0
10-1
10
186.5
10000
20000
0
10000
20000
10000
20000
10000
20000
Figure 13: Training with SGD on the language 04.04.
Loss
10
8.112
[V
||0 -
110
18.90
10
10-3
18.85
10
10
10-1
18.80
10
10-3
110
10000
20000
6
10000
20000
10000
Figure 14: Training with SGD on the language 04.04.Zp.2.1.0
Loss
|0 1 0xl12
[VC[Re]1
||0 - Bragget
10-
363.0
10-1
10-1
10-1
10-
10-3
10
362.0
10-1
10-1
10
361.5
10000
20000
0
10000
20000
10000
20000
10000
20000
Figure 15: Training with SGD the language 16.04.TLT.2.1.
Loss
10 0x112
[V
10: - 12
-10
10-1
10-2
10-1
650.5
10-3
10-2
100-
650.0
10-3
649.5
10000
20000
10000
20000
10000
20000
10000
20000
Figure 16: Training with SGD on the language 16.16.LT.4.1.5
Loss
10 0ellz
[V[(Ra]1-
||0 B
109
10-1
10a
170
10-1
10-2
10-1
10-1
10
10-3
10
110
4
10-3
168
10000
20000
10000
20000
10000
20000
10000
20000
Figure 17: Training with SGD on the language 16. 16.16.SP.2.1.0
42

---

Published in Transactions on Machine Learning Research (12/2024)
Loss
|6
8xll2
[C(R) 1=
||0k
Brarget
10
1256
10
10
10-2
1254
10
-
10-3
10
1252
10
10-3
10-1
1250
10000
20000
10000
20000
10000
20000
10000
20000
Figure 18: Training with SGD on the language 64.64.$F.000.0
Loss
10 0g|12
VC(Ra]1
|00 -rragat l
10a
678
10
10a
10-2
10-1
676
10 3
10
10
10-1
10-3
674
10000
20000
6
10000
20000
10000
20000
10000
20000
Figure 19: Training with SGD on the language 64. 64..4..LL4.1...
43


Reviews:
[{"review_id": "wkKvKdIQHI", "reviewer": "Reviewer_TtPt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThis is a solid theoretical contribution, proving that the celebrated gradient descent algorithm fails in some simple cases. It is important for the deep learning community to know about the failure cases of gradient descent so as to avoid them in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a class of recurrent neural networks that cannot be learned. More precisely, these networks are assumed to have finite precision, and it's assumed that they are saturated. The paper shows that then there is a space of parameters on which the gradient is \"stationary,\" meaning that applying a step of gradient descent doesn't update the network's parameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I understand that Section 2 contains the necessary definitions for the paper, but it's quite a dry, long section. Perhaps some of the less crucial definitions can be moved to the appendix?\n\nThere are a few spelling and grammatical issues that need to be fixed. I found these ones, but a careful proofreading is appreciated:\n1. Page 1, Line -2: \"decent\" -> \"descent\"\n2. Page 4, Line 6: \"lost\" -> \"loss\"\n3. Page 4, Line before Section 2.3: Period is missing. Also, \"Appendix 31\" -> \"Appendix D\"\n4. Definition 8, did you mean 0 <= beta <= 1?", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "W7spGUtd6S", "reviewer": "Reviewer_bmSq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The work addresses the theoretical gap by exploring the limitations of training RNNs via Gradient Descent (GD) in finite precision.\n\n2. The study explicitly identifies regions of the parameter space that are unreachable by classical GD with a bounded learning rate, providing a clearer understanding of the limitations faced in training saturated SRNs.\n\n3. The authors prove a theorem that establishes the impossibility of learning saturated SRNs through GD.\n\n4. The paper introduces an algorithm that constructs a saturated SRN from a Deterministic Finite State Automaton (DFA), extending Minsky's earlier work and offering practical implications for simulating finite state machines.\n\n\nWeaknesses: \n\n1. The study's focus on SRN may limit the generalizability of the findings to other types of neural networks.\n\n2. The proposed algorithm may be complex to implement in practice.\n\n3. The reliance on the saturation assumption may not hold in real-world scenarios, which could affect the applicability of the conclusions drawn.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on understanding neural network behavior regarding the functions learnable in the context of a finite precision configuration. It investigates the limitations of gradient descent in Simple Recurrent Networks (SRN), identifying specific conditions where gradient descent encounters failures. Additionally, the authors introduce a class of SRNs based on Deterministic Finite State Automata (DFA) that illustrate these failure scenarios. They also present a constructive algorithm that converts any DFA into an SRN that computes exactly the same function, contributing valuable insights to the field.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The results seem to solid and novel. My main concern revolves around the practical implications of the findings and how practitioners can leverage these theoretical insights to enhance their work. Could you please provide more detailed explanations?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ihpED5ynVS", "reviewer": "Reviewer_SuQh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper seems to be a decent theoretical contribution to the literature. Although I haven't checked the full proofs in the appendix, the sketch for Theorem 16 appears to make sense.\n\nStrengths:\n1. I like the use of diagrams in the text, though they require more detailed descriptions.\n2. I appreciate that a concrete example is provided to illustrate how Theorem 16 can be applied.\n\nWeaknesses:\n1. The paper, overall, could benefit from greater clarity. For example, I am quite confused about what is being tested in the experimental section. What are the dataset, model, learning rate, etc.?\n   \n2. Most of the figures would benefit from more detailed descriptions. A single short sentence is not sufficient, in my opinion.\n\n3. Do the authors have a solid explanation for why the theory and practice diverge in Section 6? There appears to be a significant discrepancy that isn't adequately discussed. Additionally, the SGD results seem to be entirely orthogonal to the main argument of the paper.\n\n4. There should be a figure label for the image under Figure 3.\n\n5. The take-home messages need to be clearer. Outside of Theorem 16, I'm unsure what other key points I'm meant to take away from the paper.\n\nSpecific weaknesses:\n1. In Section 4.6, it is noted: \"SRNs with more than $10^3$ neurons are rarely observed, so this last constraint on the number of neurons is realistic.\" Can the authors provide more justification for this? It seems to me that 1000 neurons might be quite small, though I'm not deeply familiar with this subfield.\n\n2. The formatting on page 13 seems off.\n\n3. The use of what appear to be Desmos figures makes the paper seem a bit unprofessional. This isn't a major reason for acceptance or rejection, but it's worth noting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors make two significant contributions in this paper:\n\n1. They demonstrate that there are regions in the parameter space of finite-precision simple recurrent neural networks that are (1) robust to noise and (2) exhibit a stationary gradient.\n2. They devise an algorithm to convert any Deterministic Finite State Automaton into a finite-precision simple recurrent network.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As it stands, I believe some audiences may find this paper interesting, but it does not yet meet the *claims and evidence* criterion. Specifically, I don't think Section 6 provides clear evidence to support the theory proposed by the authors. However, I am open to changing my perspective if the authors make some revisions.\n\nProposed Changes:\n1. **Improvement in presentation**: The overall presentation of the paper needs enhancement. There are clear formatting issues throughout, figure descriptions lack sufficient detail, and there are several typographical errors. In my view, this detracts from the \"clarity of evidence\" component, which is part of the selection criteria for TMLR. While this is not an especially precise critique, I feel that the paper doesn't currently have a \"professional\" appearance. I would like to see it reworked to present a more polished and professional tone.\n\n2. **Significant improvements to Section 6**: Currently, none of the results in Section 6 appear to support the theorem presented by the authors. The predicted stagnation distance should be 6.6, but the actual distance is 500. Moreover, the SGD experiments suggest that traditional learning fails which is interesting but seemingly orthogonal to the paper's main message. This section needs to better align with the theoretical claims or include significant discussion to address the discrepancy between the theory and the experiments. I would also be open to the authors removing it entirely and simply making the theoretical claim in theorem 16 although they would need to justify in rebuttal why we should ignore the discrepancy presented in section 6.\n\n3. **Clearer contributions section or conclusion**: I would like to see a more structured and clear contributions section or conclusion to emphasise the key takeaways from the paper.\n\nAdditional Suggestions:\n1. The use of $Ex$ for exponent seems sub-optimal. When I read this, I initially think you are referring to a matrix-vector product between $E$ and $x$. Perhaps you could use $q$ or some other single letter variable instead.\n   \n2. Could the authors adopt the more traditional $\\theta$ for parameters, instead of $p$? This would align better with standard notation in the field.\n   \n3. The notation $p[Encoder]$ for the encoder's parameters is confusing. I think the notation would be clearer if it followed the typical convention of using $\\theta_{\\text{encoder}}$.", "broader_impact_concerns": "I do not think there are any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the highly practical issue of gradient saturation in neural networks with a rigorous theoretical approach. However, its current presentation may be daunting for practitioners. The main result, which highlights a critical failure mode of gradient descent in finite-precision training, is not presented until page 10 after extensive technical groundwork.  To enhance accessibility, I recommend providing a simplified explanation of the core findings and their implications earlier in the paper. This would allow practitioners to quickly grasp the key insights and motivate them to delve deeper into the technical details.


I also recommend the authors explore the growing body of literature on low-precision training of language models (see e.g., https://arxiv.org/abs/2407.17465. ) This could uncover interesting theoretical questions and reveal potential issues with low-precision training that practitioners may not be aware of.  




Typo:  4.1 Back Propagation `Trough` Time
Decision: Accept (poster)