The Implicit Bias of Structured State Space  Models Can Be Poisoned With Clean Labels
Authors: Yonatan Slutzky
Yotam Alexander
Noam Razin
Nadav Cohen
Venue: NeurIPS 2025 spotlight ()
Keywords: Neural Networks
Structured State Space Models
Generalization
Adversarial Machine Learning
Primary area: theory

Abstract: Neural networks are powered by an implicit bias: a tendency of gradient descent to fit training data in a way that generalizes to unseen data. A recent class of neural network models gaining increasing popularity is structured state space models (SSMs). Prior work argued that the implicit bias of SSMs leads to generalization in a setting where data is generated by a low dimensional teacher. In this paper, we revisit the latter setting, and formally establish a phenomenon entirely undetected by prior work on the implicit bias of SSMs. Namely, we prove that while implicit bias leads to generalization under many choices of training data, there exist special examples whose inclusion in training completely distorts the implicit bias, to a point where generalization fails. This failure occurs despite the special training examples being labeled by the teacher, i.e., having clean labels! We empirically demonstrate the phenomenon, with SSMs trained independently and as part of non-linear neural networks. In the area of adversarial machine learning, disrupting generalization with cleanly labeled training examples is known as clean-label poisoning. Given the proliferation of SSMs, we believe that delineating their susceptibility to clean-label poisoning, and developing methods for overcoming this susceptibility, are critical research directions to pursue.

The Implicit Bias of Structured State Space Models Can Be Poisoned With Clean Labels
Yonatan Slutzky* Tel Aviv University Autzzyy@maill tau. ac. i1
Yotam Alexander"
Tel Aviv University yotam al exa.eeerddrgaaaaaao com
Noam Razin
Nadav Cohen
PLI, Princeton University noamrazin@princees pwwpziinnprinneooo... edu edu
Tel Aviv University
cohennadav@tauex tau. ac.
Abstract
Neural networks are powered by an implicit bias: a tendency of gradient descent to fit training data in way that generalizes to unseen data. A recent class of neural network models gaining increasing popularity structured state space models (SSMs). Prior work argued that the implicit bias of SSMs leads to generalization in a setting where data is generated by a low dimensional teacher. this paper, we revisit the latter setting, and formally establish phenomenon entirely undetected by prior work on the implicit bias SSMs. Namely, we prove that while implicit bias leads to generalization under many choices of training data, there exist special examples whose inclusion in training completely distorts the implicit bias, to a point where generalization fails. This failure occurs despite the special training examples being labeled by the teacher, ie., having clean labels! We empirically demonstrate the phenomenon, with SSMs trained independently and as part non-linear neural networks. In the area of adversarial machine learning, disrupting generalization with cleanly labeled training examples is known clean-label poisoning. Given the proliferation of SSMs, we believe that delineating their susceptibility to clcan-label poisoning, and developing methods for overcoming this susceptibility, are critical research directions to pursue.
1 Introduction
Overparameterized neural networks can fit their training data in multiple ways, some of which generalize unseen data, while others do not. Remarkably, when the training data is fit via gradient descent (or variant thereof), generalization tends to occur. This phenomenon one of the greatest mysteries in modern machine learning [91 i often viewed as stemming from an implicil bias: tendency gradient descent, when applied to neural network models, to fit training data in way that complies with common data-generating distributions. The latter view was formalized for several
neural network models and data-generating distributions (55 27 64
A recent class of neural network models gaining significant popularity is structured state space models (SSMs). SSMs often regarded computationally efficient alternative to transformers (85) and underlie prominent neural networks such as S4 [24). Mamba [22]. LRU [58], Mega [48). S5 775
and more [62] [4]. The implicit bias of SSMs, i.e., of gradient descent over SSMs, was formally studied in prior works, e.g., Emami et al. [66] Cohen-Karte
et al. [T] 12. Notable among these
is Cohen- Cohen-Karlik et al. [12], which considered setting where data is generated by a low dimensional
teacher SSM, and gradient flow (gradient descent with infinitesimally small step size) over high
'quual contribution.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

dimensional student SSM fits training data comprising infinitely many sequences of a certain length D In this setting, the student SSM can fit the training data multiple ways, some of which generalize to sequences longer than those seen in training, while others do not. It was shown in Cohen-Karlin et al. [12] that under mild conditions,
implicit bias leads to generalization.
In this paper, we revisit the setting of Kohen-Karlik et al. [1], with one key exception: rather than training data comprising infinitely many sequences, we consider the realistic case where the number of sequences is finite. Surprisingly, our theory and experiments reveal phenomenon entirely undetected by prior works on the implicit bias of SSMs. Namely, we find that while implicit bias leads the student SSM to generalize under many choices of training sequences, there exist special sequences which if included in training completely distort the implicit bias, resulting in the student SSM failing to generalize. This failure to generalize takes place despite the fact that the special sequences are labeled by the teacher SSM, i.e. they have clean labels! In the area of adversarial machine learning, the phenomenon of generalization being disrupted by training instances with clean labels is known clean-label poisoning, and has received significant attention, both empirically 71 33 and theoretically [79] 6) To our knowledge, the current paper is the first to formally prove susceptibility of SSMs to clean-label poisoning.
Our theoretical analysis comprises two contributions. First, is dynamical characterization of gradient flow over an SSM, trained individually or as part of non-linear neural network. The dynamical characterization reveals that greedy low rank learning [43 78 65 66 - sufficient condition for
generalization with a low dimensional teacher SSM is implicitly induced under many, but not all, choices of training sequences. Our second theoretical contribution builds on our dynamical characterization for fine-grained analysis of gradient flow over an SSM, employing an advanced tool from dynamical systems theory: non non-resonance linearization theorem [70]. The analysis proves that there exist situations where: (i) training student SSM on sequences labeled by low dimensional teacher SSM exhibits an implicit bias that leads to generalization; and (ii) adding to the training set special sequences, also labeled by the teacher SSM (i.e., that also have clean labels), entirely distorts the implicit bias, to an extent where generalization fails.
We corroborate our theory via experiments spanning a wide range of settings: from those covered by our theory, to real-world -oon-syythetic) settings comprising SSM-baser $4 (24). Mamba-2 [14] and LRU [58] neural networks trained on the CIFAR-10 dataset 38 The experiments validate both our
dynamical characterization and the susceptibility of SSMs to clean-label poisoning. In light of the growing prominence of SSMs, particularly in large language models, we believe that delineating this susceptibility, and developing methods for overcoming it, are critical research directions to pursue.
2
Preliminaries
2.1 Notation
We non-boldface lowercase letters for denoting scalars (e.g., R. d E N), boldface lowercase letters for denoting vectors (e.g., x E Rd), and non-boldface uppercase letters for denoting matrices (e.g., A E Rd.d). We denote by 1 an all-ones vector and by 0 an all-zeros vector, with their dimensions to be inferred from context. For d E N. we let [d] := {1, 2, .., dd. For d E N and i [d]. we denote by e; the i'th standard basis vector (i.e., a vector holding one in entry i and zeros elsewhere) of dimension d, where the dimension is omitted from the notation and should be inferred from context. We identify scalar sequences of finite lengths with vectors.
2.2 Structured State Space Models (SSMs)
structured state space model (SSM) of dimension d E N is parameterized by three matrices: A E IRddd, a state transition matrix, which conforms a predefined structure (e.g. is constrained to be diagonal); B E [R,,1, an input matrix; and C E IRd,d an output matrix. Given the values of A. B and C, the SSM realizes a mapping (.). that receives as input a length scalar sequence x E RR* for any le e N, and produces as output a scalar y E IR equal to the last element of the sequence y E I defined through the following recursive formula:
ASk + Bay yk = CsE K' E [k].
SW
'More precisely, the training data is formed from continuous (Gaussian) distribution of sequences having certain length, all labeled by the teacher SSM
2

---

where (swr E R ( is a sequence of states, and So = 0. It is straightforward to show that the mapping ((A, is fully determined by the sequence (C.A B) known as the impulse response of the SSM. In particular, for any & E N and E R
y ((A,B,c)(x)) (CA B. B..... CAB,CB)X Ex CA B-Z-K. Z
(2)
For convenience, we often identify an SSM with the triplet (A, B, C) holding its parameter matrices, and regard the (single column) matrices B and CT as vectors.
Perhaps the most common form of structure imposed on SSMs is diagonality 123 Accordingly, unless stated otherwise, we assume that the state transition matrix of an SSM is diagonal.
28 58 48 22
Some of our results will account for SSMs that are part of non-linear neural networks, or more specifically, for SSMs whose output undergoes a transformation a(. w), where: a R x W + R is some differentiable mapping: W is some Euclidean space, regarded as parameter space; and regarded as a parameter vector. Given values for A, B, C and w, such a neural network realizes ((((AA.,C))) w). This architecture (namely, an SSM followed by parametric transformation) is ubiquitous among SSM-based neural networks (see, for example, Gu
W,
the mapping (AA,BC)) w...)).()))) (-)
et al. 24], Gupta et al. (28). Gu et al. 25)).
2.3 Teacher-Student Setting
We consider the teacher-student setting of Karln-Karlik et al. [1), described hereinbelow. Data is
labeled by a teacher SSM (A", B", ,", C*) of dimension d' E N, i.e. the ground truth label of x E RA for any l E N, is Φ( "(A*.B".C*) (x) R. For some N and
N 2d we are given training
set S comprising n labeled sequences of length K, i.e., = ((x(1)
i=1 where x() E R and
g(t) (/t/""BB.))@e) (x()) for every E [n]. A student SSM (A, B, C*) of dimension d E N is
trained by minimizing the square loss over referred to as the training loss:
(v (xx
Optimization is implemented via gradient flow, which is formally equivalent to gradient descent with infinitesimally small step size (learning rate), and was shown well-approximate gradient descent with moderately small step size [15). The dynamics of gradient flow are, for t E 1200
(A(t), B(I),
-Vs((((t) (()))
where (Á(t), B(I), (()) = (A(1), C(t)) and (A()), B()), C()) curve representing the optimization trajectory. Generalization the student at time E R>0 of optimization measured by the extent to which (())).B()),CC)))) of length as used for training. but also over input sequences of other lengths. This accounts not only for in-distribution generalization as considered in classical machine learning theory (72), but also for -ut-of-distributio generalization (extrapolation) as prevalent in modern machine learning [ Formally, in line with Equation 2 generalization is quantified by how close the first & elements of the student's ss impulse response are to the first i elements of the teacher's impulse response, for different values of k:
approximates O(A--B'.Ch (.......))...............). not only over input sequences
Definition 1. The generalization error of the student SSM over sequence length i is:
maxi' E BA C (*A) C*|.
(5)
Clearly, there exist assignments for (A, B, C)) with which the training loss (s(-) is minimized (i.e.. equals zero) and the student SSM perfectly generalizes over any sequence length 1: On the other hand, it was shown in Cohen-Karlik et al. [12 that, regardless of the size of the training set S (ie., of m)) and the input sequences comprises (namely, (x yx)) there exist assignments for (A, B, C*) with which the training loss (s(-) (-) is minimized, and yet the student has arbitrarily high generalization error over sequence lengths beyond K, e.g., over sequence length k + (for completeness, we prove this fact in Appendix C). The latter two facts together imply that if minimization of the training
"This is the case, for example, if A, B and C' are respectively attained by padding A", B" and C" with the right and/or bottom.
3

---

loss (-(-) via gradient flow (Equation (4) produces an assignment for (A, B, C) with which the student generalizes over sequence lengths beyond K. must be an outcome of implicit bias. The main result in Cohen-Karlik et al. 12 states that if the training set S is infinite and each entry of each input sequence x() is independently drawn from the standard normal distribution then under mild conditions the implicit bias of gradient flow is such that it convergences to solution which generalizes over any sequence length k.
In this paper, we focus on the realistic case where the training set S is finite. Surprisingly, our theory and experiments (Sections 3 and 4 respectively) reveal a phenomenon completely undetected by Cohen-Karlik et [12], and any other work we are aware of on the implicit bias of SSMs.
3 Theoretical Analysis
3.1 Dynamical Characterization
In this subsection we derive a dynamical characterization of gradient flow over an SSM, trained individually as part of non-linear neural network. The dynamical characterization reveals that
greedy low rank learning 669 39 4 43
65
66] sufficient condition for generalization with a
low dimensional teacher SSM is implicitly induced under many, but not all, choices of training sequences. Section 3.2 will build on the dynamical characterization to prove that the implicit bias of
SSMs can be poisoned with clean labels.
Our dynamical characterization applies to setting more general than that laid out in Section 2.3 Specifically, it applies to the same setting, with two exceptions: (i) the student SSM potentially embedded in non-linear neural network, i.e., the mapping ((A.B,)) () is replaced by ((A,BC)), as defined in Section 2.2] and (ii) the training labels (²()))== need not be assigned by teacher SSM, i.e. they may be arbitrary. We denote the resulting training loss-a generalization of {s(-) from Equation by {s(-):
: Ws
" :=1 (1-) ( (x()))
(6)
Proposition I beloow establishes our dynamical characterization: equations of motion for the (diagonal)
entries of A during gradient flow over (s(-).
Proposition 1. Consider optimization of the generalized loss (s(+) defined in Equation via gradient flow. That is, consider. for any E Rzo:
(A(t), B(t) wtt)
B(t) w(t),
where (A(t), B(t), Č(t), (t)) == d (A(t), B(t), C(t). w()), and (A(-). B(), (()) di
curve representing the optimization trajectory. For j E [d], denote by a ( the j I'th diagonal entry of A()), by by(.) the thth entry of B(.). and by c²(-) the j I'th entry of C()). Assume that the training sequence length & is greater than or equal to two. For I [K] and i [m]. denote the l'th elemens of the i 'tth training sequence x()) by xi (5) Then, for any E [d] and & E Roo0
áz(t) = at) by))) (1) En (0))) az(1)'
where:
(0))) = 2((+1)
(t))
(8)
with:
-..... -00A00,000000) {()))))))))))))))))))))))))))))) = 8. (z, w(t)) 300
8(0) (t) ==
(9)
Proof sketch (proof in Appendix D}. The result readily follows from differentiation of {s(+) (Equa- tion 6 with respect to each diagonal entry of A.
Formally, this condition means that the training loss (.()) is the expected value of (v (x)) where the entries of are independently drawn from the standard normal distribution, and y (1A),

---

3.1.1 Interpretation
Proposition | Timplies that during gradient flow, the motion of (aaaa)y--i) the j'th diagonal entry of the state transition matrix A(:)-is given by a degree k - 2 potynomial in (.))), where the coefficients of the polynomial are time-varying. In particular, at time E Rgo of optimization, the coefficient of the I'th power in the polynomial, for E {0, ,,..,,,. K - 2]. is product of two factors: (i) (t), which depends on the power but not on the entry index j; and (ii) by (t) (the j'th entry of the input matrix (.) times the j j'th entry of the output matrix C(-)), which does not depend on the power I but does depend on the entry index j.
Different training sets admit greedy learning. Consider the case where A()) emanates from
standard near-zero initialization 20 30, [59. i.e., where (0) ~ 0 for all j. If the factor ())
is small throughout- is the case, e.g., if the penultimate (k - 1 1'th) element of each training sequence x(() is small (see Equation - the constant coefficient (i.e., the coefficient of the zeroth power) in the polynomial determining the motion of a.()) negligible. The dynamics of (a)()) then exhibit greedy learning, similarly to the dynamics of various quantities in various types of neural networks 69 39
66] Namely, (a, (a)())) all progress slowly at first, following near-zero initialization, and then, whenever entry reaches a critical threshold, it starts moving rapidly- see empirical demonstrations in Figure
65
A Appendix [.]] The greedy learning of (1)()) implies greedy low rank learning of the state transition matrix. More specifically, implies tendency to fit training data with A having low rank, meaning a tendency to generalize if data is generated by a low dimensional teacher SSM.
Certain training sequences impede greedy learning. In stark contrast to the above, if the training sequences (x (x are such that the factor (.) is not small-as can be the case, e,g., if there the polynomials determining the motions of (a)( have non-negligible constant coefficients, and greedy low rank
is training sequence x(*) in which the last elements are relatively large-the
learning will generally not take place see empirical demonstrations in Figure 2 and Appendix 1.1
3.2 Clean-Label Poisoning
In this subsection we employ the dynamical characterization from Section 3.1 for a fine-grained anal- ysis of gradient flow over an SSM. The analysis considers teacher-student setting as in Section 2.3 and proves existence of situations where: (i) training a student SSM on sequences labeled by a low dimensional teacher SSM exhibits an implicit bias that leads to generalization; and (ii) adding to the training set certain sequences, also labeled by the teacher SSM (i.e., that also have clean labels), entirely distorts the implicit bias, to an extent where generalization fails. To our knowledge, this constitutes the first formal proof of susceptibility of SSMs to clean-label poisoning. Facilitating the analysis is an advanced tool from dynamical systems theory-a a non-resonance lineurization theorem 70 which may be of independent interest.
The teacher-student setting considered in this subsection is characterized by Assumptions [ and below. While this setting is specific, it fulfillss the purpose of proving existence of situations where SSMs are susceptible to clean-label poisoning. Moreover, as discussed in Appendix B our theory can be adapted account for different extensions of the setting. i.e., for different relaxations of Assumptions
[ [add]] 2 Empirically, we demonstrate in Section 4that SSMs are susceptible to clean- label poisoning in wide range of settings: from the specific setting considered in this subsection, to real-world (non-synthetic) settings comprising SSM-based $4 (24, Mamba-2 [4] and LRU (58)
neural networks trained on the CIFAR- 10 dataset (38].
Assumption 1. The teacher SSM of dimension d' = 2, and its parameter matrices are given by:
^ = 0 0)
B" = (1 va-I) C² C²= Vd-I).
(10)
Assumption The input and output matrices of the student SSM, B and C, are respectively fixed at 1 and 1 throughout training.
Under Assumptions I and 2 generalization is straightforward to attain: all that is needed in order for the student SSM to achieve low generalization error over any sequence length (Definition IT) is that one of the diagonal entries of its state transition matrix A be sufficiently close to one while the rest are sufficiently close to zero.
22ssitiioonbbloo proves that generalization takes place in cases where: each training sequence has zeros in its last two elements and non-negative values elsewhere; and at least one training sequence is
5

---

not identically zero. Underlying the proof is the dynamical characterization from Section 3.1 with the last elements of each training sequence being small, the characterization establishes greedy low rank learning, which in turn implies generalization (see interpretation in Section 3.1.1.
Proposition 2. Consider the teacher-student setting of Section 2.3 subject to Assumptions 7 [and? 2 Suppose that for every i E [n]. the training sequence x(8) has zeros in its last two elements and non-negative values elsewhere. Suppose also that x( + O for some i E [n]] Then, for any l E N, E P-0 and 0 Ry.0 there exists an open set I of arbitrarily small initializations for the student SSM and a corresponding time t. E Ry such that gradient flow initialized in I reaches at time t a point where the training loss is at most 5 and the generalization errors over sequence lengths 1, 2, ..., , are at most E.
Proof sketch (proof in Appendix E. The proof specializes the dynamical characterization from Sec- tion 3.1 per Assumptions] I Jnd and per the conditions posed on the training sequences. Choosing the set I to be sufficiently concentrated around the origin, the specialized characterization implies that gradient flow initialized in I exhibits greedy low rank learning (see interpretation of the charac- terization in Section 3.1.1.. The greedy low rank learning leads single diagonal entry of the state transition matrix to reach the vicinity of one while the rest of the diagonal entries remain near zero. this ensures generalization.
As stated in the text following Assumptions I and 2
As stated in the text following Assumptions I and 2 under these assumptions, generalization is straightforward to attain. Indeed, Proposition 2 above proves that generalization takes place even in cases where the training set entails little information, e.g., in the case where S includes e1 (one followed by zeros) as sole training sequence. Theorem[[]eloov proves that in this latter case, despite generalization being straightforward to attain, adding to a single cleanly labeled example-or or more specifically, single carefully selected sequence x of moderate (Euclidean) norm labeled by the teacher SSM-can entirely disrupt generalization.
In the context of Theorem D disrupting generalization requires preventing greedy low rank learn- ing. This is achieved, in accordance with the dynamical characterization from Section 3.1 (see its interpretation in Section B. by selecting a sequence xf whose last elements are relatively large. To prove that such selection indeed disrupts generalization, Theorem [ relies on an advanced tool
from dynamical systems theory-a non-resonance linearization theorem 770 -which may be of independent interest.
Theorem I albeit specific, constitutes what is to our knowledge the first formal proof of susceptibility
of SSMs to clean-label poisoning. In Appendix B we discuss different extensions of Theorem [ including an extension that allows for any training set S permitted by Proposition 2 (i.e., for any
choice of training sequences (x where: for every i E [m], x(() has zeros in its last two elements and non-negative values elsewhere; and (+)) + 0 for some E (n]). at the expense of the added sequence x' potentially having large norm. Empirically, we demonstrate in Section 4 that the conclusion of Theorem carries over wide range of settings, including ones where an SSM is part of a non-linear neural network.
Theorem 1. Consider the teacher-student setting of Section 2.3 subject to Assumptions 7 and 2 Suppose the training sequence length and the dimension of the student SSM respectively satisfy R E {7, 9, 11....} and d 2 8. Define the sequences x := C1 E R² and xi := Cx-1 E RR. Denote by y and y¹ the labels respectively assigned to x and xt by the teacher SSM, i.e., y == Ó (.-))x(()))
and yi := = (==,c=((x))). Suppose the training set S includes (x, y) as a sole example. Let k E N2x+2 and e E R20. Then, there exists an open set I of arbitrarily small initializations for the student S such that with any initialization in I:
gradient flow converges to a point where the training loss is minimal (i.e., equals zero) and the generalization errors over sequence lengths 1,2...., k are at most e; and
appending S the (cleanly labeled) example (xt, y²) leads gradient flow to converge point where the training loss is minimal and the generalization error over sequence length le is at least m0.1, (9d) (0.6))/(x-1))).
'That is, for any neighborhood N' of the origin in the space of diagonal matrices Rdddd (the latter space is identified with vd), there exists an open subset I CV

---

Trojectory when training on (S.
Main tool: non-resonance linearization theorem
Trajectory when training on [xx.5) (xl,5
Reference trajectory
point
Non-generalizing solutions
Generalizing solutions
Initializations
Figure 1: Illustration of the main ideas behind the proof of Theorem See proot sketch for an annotation.
Proof sketch (proof in Appendix n. Figure Illlustrates the main ideas behind the proof. Below is description of these ideas, along with an annotation of the figure.
As stated in the text following Assumptions and sufficient condition for the student SSM to achieve low generalization errors that one the diagonal entries of its state transition matrix be close to one while the rest are close to zero. The proof shows that this condition is also necessary, thus the set labeled "generalizing solutions" in Figure Tis neighborhood of one-hot assignments for the diagonal entries of A. Next, similarly to the proof of Proposition 2 the dynamical characterization from Section 3.1 is used establish that when training initializations) sufficiently concentrated around the origin, a gradient flow trajectory emanating from I exhibits greedy low rank learning, and thus converges to the set of generalizing solutions as illustrated Figure
(x. y), under choices of I (set of
For analyzing the behavior of gradient flow when training on {(x, (xt,vt) vt)), the proof makes use of the fact that the last elements of x are relatively large. In accordance with the dynamical characterization from Section [3.1 (see its interpretation in Section[311.1] this fact implies that greedy low rank learning does not take place. The proof identifies reference trajectories of gradient flow (when training on {xx y). (xl, }))}) that converge to goneraeeral solutions; one such reference trajectory is illustrated in Figure These reference trajectories emanate from near-zero initializations that cannot be included in I, since they lead gradient flow converge non-generalizing solutions even when training only on (x,y). However, the proof shows that can consist of initializations near those of reference trajectories. since gradient flow emanating from such I: (i) converges to a generalizing solution when training on (x, y); and (ii) closely tracks a reference trajectory non-gene non-generalizing solution as
when training on (xx, y) (xt, y))}, resulting convergence
illustrated in Figure [ This concludes the proof.
The main technical challenge faced by the proof lies in item (ii) above, namely, in establishing that when training on {(x,)) (x1 "d'yy)),, an initialization near that of a reference trajectory leads gradient flow to closely track the reference trajectory. Since the training loss is non-convex, gradient flow trajectories may diverge from one another exponentially fast. Establishing that a reference trajectory is tracked thus requires sharp bounds convergence times. The crux of the challenge derive such bounds, as trajectories pass near saddle points, and a-priori, may not escape these saddle points sufficiently fast. To show that saddle points are escaped swiftly, the proof employs an advanced tool from dynamical systems theory which may be of independent interest: non-resonance linearization theorem 770. Namely, rather than directly analyzing trajectories in the vicinity of a saddle point, the proof constructs linear approximations, and uses the non-resonance lincarization theorem to show that the linear approximations are sufficiently accurate, which in turn implies that the trajectories escape the saddle point sufficiently fast. The non-resonance linearization theorem requires the spectrum of the Hessian of the training loss to be free of certain algebraic dependencies known as resonances. If these resonances are absent-which the proof shows to be the case-the non-resonance linearization theorem provides guarantees the accuracy of linear approximations that are far better than guarantees attainable via standard smoothness arguments.
Experiments
This section presents experiments corroborating our theory. is organized as follows. Section 4.1
demonstrates the dynamical characterization we derived (in Section[.1]] showcasing that optimization of an SSM implicitly induces greedy low rank learning (a sufficient condition for generalization with a low dimensional teacher SSM) under some, but not all, choices of training sequences. Section 4.2 then demonstrates the clean-label poisoning phenomenon established (in Section 3.2 by showing
7

---

S5M
SSM MIP. with special sequencees
Entry magnituale
without sequences
Entry maggituto
2.0
with special sequences
Entry magnitutte
2.0
without spacial sequences
Extry magniuute
8.5
0.5
9.01
0.0
0.5
2.0
Peration
X10
Iteration X30'
Reration x10
Iteration x10*
Figure 2: Demonstration of the dynamical characterization from Section 3.1 optimization of an SSM-traine individually or as part of non-linear neural network- network-inpliente induces greedy learning of the diagonal entries of the state transition matrix A under some, but not all, choices of training sequences. First (leftmost) plot shows the magnitudes of the entrics of A throughout the itcrations of gradient descent, in a case where an overparameterized student SSM dimension d 10 is trained individually on training set labeled by a teacher SSM of dimension d' = 1, and the training set does not include "special" sequences, i.e., sequences which the last elements are relatively large. Second plot portrays a scenario that is identical, except that special sequences are included in the training set. Third and fourth plots adhere to the deseriptions of first and second plots, respectively, except that the student SSM is trained along with successive multi-layer perceptron mon-linear neural network), and the teacher SSM is followed by (fixed) multi-layer perceptron. Notice that, with and without multi-layer perceptron, greedy learning takes place when special sequences are excluded. and does not take place when they are included. For further experiments (including teacher SSMs of higher dimension, and additional variations) and visualizations (including the effective rank of A, and additional quantities, throughout optimization) see Appendix [I]]
For further details see Appendix [.T
that adding special cleanly labeled sequences to the training set of an SSM can completely ruin its generalization. Code for reproducing our experiments can be found at ttttps://github.coo com/ mmnislutzky8/immp bias sam- sssmpoison
4.1 Dynamical Characterization
As discussed in Section 3.1.1 the dynamical characterization in Proposition T (Equations 7 to implies that optimization of an SSM-erained individually or as part of a non-linear neural network implicitly induces greedy learning of the diagonal entries of the state transition matrix A under some, but not all, choices of training sequences. For example, if the last elements of each training sequence are small then greedy learning takes place, and if there are training sequences in which the last elements are relatively large then greedy learning may not take place. Figure Soaureeeennn empirically demonstrates this, for a standalone SSM as well as one included in a non-linear neural network. Further experiments are reported in Appendix LI
4.2 Clean-Label Poisoning
Theorem[p proved existence of situations where clcan-label poisoning of an SSM takes place, i.e., situations where: (i) training student SSM on sequences labeled by low dimensional teacher SSM exhibits an implicit bias that leads to generalization; and (ii) adding to the training set special sequences, also labeled by the teacher SSM (i.e., that also have clean labels), entirely distorts the implicit bias, to an extent where generalization fails. T poisoning of SSMs in three different seacher-studen settings: the setting of Theorem I standalone SSM setting beyond Theorem (meaning it does not satisfy the assumptions of Theorem [ e.g. includes multiple training sequences, and learning of the input matrix B and output matrix C); and a setting where an SSM is part of non-linear neural network.
demonstrates clean-label
We further demonstrate clean poisoning of SSMs in real-world moon-synthetic) settings com- prising SSM-based S4 [24]. Mamba-2 (14) and LRU (58) neural networks trained on the CIFAR-I0 dataset [38]. In these settings do not have access to teacher (i.e., ground truth labeling map- ping). and accordingly, cleanly labeled poisonous examples are generated from CIFAR-10 examples by introducing human-imperceptibne
additive noise to input sequences, while keeping their labels inttct. The noise added to an input sequence is rendered to have relatively large last elements-in line with our theorySl 51 using an adapted version of the Gradient Matching method from Geiping et al. [T8] (see Appendix [I3 for details). Adding to the training set cleanly labeled poisonous examples as described leads to significant deterioration in the generalization of the SSM-based neural networks-sce T
We believe the susceptibility of SSMs clean-label poisoning goes far beyond the demonstrations herein. In light of the growing prominence of SSMs, particularly in large language models, delineating this susceptibility, and developing methods for overcoming it, are of prime importance.
*Our theory does not suggest that relatively large last elements are necessary for clean-label poisoning of SSMs in these real-world settings. Accordingly, may be possible for the noise to have different pattern.
8

---

Table 1: Demonstration of (dean-labe poisoning of SSMs in three different teacher-student settings: the setting of Theorem T. standalone SSM setting beyond Theorem T (meaning it does not satisfy the assumptions of Theorem T e.g., includes multiple training sequences. and learning of the input matrix B and output matrix C); and a sctting where an SSM is part of non-lincar neural network, i.e,, is followed by a multi-layer perceptron. In each setting, a high dimensional student is trained until convergence (namely, until the training loss is lower than 0.01), and data is generated (i.e, sequences are labeled) by a low dimensional teacher of the same architecture as the student. Reported are generalization errors (each averaged over four random seeds) for two training sets per setting: (i) a training set that does not include "special" sequences, Lee, sequences in which the last elements are relatively large; and (ii) training set obtained by adding to the former special sequences along with the (clean) labels assigned to them by the teacher. In the first two settings (SSMs trained independently) generalization emrrrs measured via impulse responses, as defined in Definition] [ setting (SSM trained as part of non-linear neural network) generalization errors are measured using hcld-out test set. All reported generalization errors are normalized (scaled) such that a zero mapping corresponds to a value of one. Notice that across all settings, special training sequences significantly deteriorate generalization. respectively.
In the third
For further experiments and details see Appendices 1.2 and 1.2
Setting
Without special sequences
With special sequences
Per Theorem
1.27 x 10m3 0.194 1.64 x 10-3
5.01 x 10-2
Standalone SSM beyond Theorem SSM in non-lineat neural network
16.62
5.45 x 10 2
Table 2: Demonstration of clcan-label poisoning of SSMs in real-world (non-synthetic) settings comprising
SSM-based $4 [24] Mamba-2 [4] and LRU (58) neural networks trained on the (sequential variant of the)
CIFAR-IO datasct [38. Each row the table summarizes an experiment with a different SSM- neural
network, where cleanly labeled poisonous examples are generated from CIFAR- 10 examples by introducing
human-imperceptible additive noise to input sequences, while keeping their labels intact. The noise added to an input sequence is rendered to have relatively large last elements- in line with our theory theiryflusinn using an adapted version of the Gradient Matching method from Geiping al. [8] The first column the table specifies the MSSs- neural network heing poisoned. The second column reports two cross-entropy losses the
CIFAR-10 test set: one obtained by training the neural network on original CIFAR- 10 training examples, and the other obtained by training the neural network on the same examples along with cleanly labeled poisonous examples as described above. The third column is identical to the second, except that reports classification accuracies rather than cross-entropy losses. Finally, the fourth column in the table reports the relative size of the last elements in the noise introduced for generating clcanly labeled poisonous example, where the relative size is averaged over all such examples, and quantified by the Euclidean norm of the last 3% of elements divided by the Euclidean norm of all elements. Throughout the table, quantities are averaged over three random seeds. Notice that in all experiments, the addition of cleanly labeled poisonous examples deteriorates generalization. For further details see Appendices and D.
SSM-based NN
Loss without with poisoning
Accuracy without with poisoning
Noise tail size
$4 24
0.739/ 0.839
78.8% / 76.9%
0.406
Mamba-2
14
1.005/ 1.178
77.8% 75.1%
0.559
LRU 58
0.892/ 1.111
72.4% 68.3%
0.469
5
Limitations
is important to acknowledge several limitations of this paper. First, while the dynamical characteri- zation derived in [ to a broad setting (e.g.. it allows the SSM to be embedded in non-linear neural network), the proof of generalization in Proposition i]ss restricted a more specific setting (e.g., it requires Assumptions I andd and the proof of clean-label poisoning in Theorem | is restricted to an even more specific setting (e.g., it requires the original training set include single example, in addition to Assumptions Tand 2). Appendix B extends the settings of Proposition 2 and Theorem [] but even under such extension the settings remain fairly restricted. A second limita- tion of this paper relates to the guarantees provided by Proposition and Theorem [] each ensures existence of a set I of initializations with which desired result holds, and while I has positive volume (it is open). this volume may be low. Third, except for the dynamical characterization derived in Proposition aadd the real-world (non-synthetic) experiments reported in Section [42 our theory and experiments pertain near-zero initialization, which is common for neural networks 20) 30] but
does not account for modern SSM initializations designed to alleviate vanishing gradients [2] 25).
Fourth, due to vanishing gradients, maintaining reasonable run-times in experiments with near-zero
9

---

initialization necessitated a relatively small scale (in terms of, e.g, SSM dimension and training sequence length). Addressing these limitations an important set of directions for future work.
6 Conclusion
The proliferation of SSMs, particularly in large language models, renders it crucial to understand their implicit bias. In this paper, we revisited prior belief' by which the implicit bias of SSMs leads to generalization when data is generated by a low dimensional teacher. We formally proved that, in stark contrast to these beliefs, there exist special examples whose addition to training data can completely distort the implicit bias, point where generalization with low dimensional teacher fails. This failure occurs despite the special examples being labeled by the teacher, i.e, having clean labels! We corroborated our theory via experiments spanning a wide range of settings: from those analyzed theoretically, to real-world settings comprising prominent SSM-based neural networks. The experiments confirmed that generalization in SSMs can be disrupted by cleanly labeled training examples, i.e., that SSMs are susceptible to clean-label poisoning.
Our results point to significant challenges in both theory and practice of SSMs. On the theoretical front, our results suggest that generalization in SSMs cannot be explained via the traditional view of implicit complexity minimization [26] 77 90), or through the nascent view by which generalization
is typical [82] [33] [4 7 (2. Indeed, if generalization in SSMs was due to the implicit bias finding solution which, among all solutions fitting training data, minimizes some
complexity measure, then training with additional cleanly labeled examples would not change the solution found, and thus would not disrupt generalization? Moreover, if generalization in SSMs was due to typicality, i.e., to the majority of solutions fitting training data being ones that generalize, then additional cleanly labeled training examples would only improve generalization, as they enhance the dominance of such majority. We believe fundamentally new approaches may be needed in order to theoretically pinpoint the source of generalization in SSMs.
Moving to the practical side, the fact that SSMs are susceptible to clcan-label poisoning raises significant concerns regarding safety, robustness and reliability. For example, large language models, which are becoming more and more reliant on SSMs 19 61 3 are often fine-tuned via supervised learning on public internet data [4] 40 81), and in this process, it may be easy for malicious actor to add cleanly labeled training examples, egg. by adding unlabeled training examples prior to label generation. We believe that delineating the susceptibility of SSMs to clean-label poisoning, and developing methods for overcoming this susceptibility, are critical research directions to pursue.
Our results suggest that learning dynamics may facilitate progress in the foregoing research direc- tions. Indeed, in settings covered by our theory, clean-laber poisoning correlates with a dynamical factor 7( (-) (defined
Proposition I being large during learning, i.e., during optimization (see Section 3.1.1 as well as Figures [6 to 19 in Appendix[] (.. By monitoring 7 (0) throughout learning, one may detect clean-label poisoning and take responsive action (e.g., prevent deployment of poisoned model). Moreover, it is plausible that by adding to the training loss a penalty term that encourages (-) to be small, one may improve resilience to clean-label poisoning. Investigating such methods, and extending them to settings beyond our theory, may promote safer, more robust and more reliable deployment of SSMs.
Acknowledgments and Disclosure of Funding
We thank Eshbal Hezroni for assistance in preparing the illustrative figure, and Itamar Zimerman for contributions to the real-world experiments. This work was supported by the European Research Council (ERC) grant NN4C 101 101664,, Google Research Scholar Award, a Google Research Gift, Meta. the Yandex Initiative in Machine Learning, the Israel Science Foundation (ISF) grant 1780/21, the Tel Aviv University Center for AI and Data Science, the Adelis Research Fund for Artificial Intelligence, Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua. NR is supported in part by the Zuckerman STEM Leadership Program.
'Prior work argued that generalization in different neural networks cannot be explained via implicit com- plexity minimization 883, but to our knowledge, such results do not apply to SSMs.
10

---

References
[1] Hojjat Aghakhani, Dongyu Meng, Yu-Xiang Wang, Christopher Kruegel, and Giovanni Vigna. Bullseye polytope: A scalable clean-label poisoning attack with improved transfcrabilityy. 2021 IEEE European symposium on security and privacy (EuroS&P)) P) pages 159-178. IEEE, 2021.
[2] Yotam Alexander, Yonatan Slutzky. Yuval Ran-Milo, and Nadav Cohen. Do neural networks need gradient descent generalize? a thcoretical study. arXiv preprint arXiv:2506.0324 2025.
[3] Carmen Amo Alonso, Jerome Sieber, and Melanie N Zeilinger. State space models foundation models: A control theoretic overview. arXiv preprint arXiv:2403. 16899, 2024.
[4] Sanjeev Arora, Naday Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in neural information processing systems, 32, 2019.
[5] Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srehro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In International Conference on Machine Learning, pages 468-477. PMLR, 2021.
[6] Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. Robust learning under clean-label attack. In Conference on Learning Theory (COLT), pages 591-634, PMLR, 2021.
[7] Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, and Daniel Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. arxiv preprint arXiv:2402.06322, 2024.
[8] Satrajit Chatterjee and Piotr Zielinski. On the generalization mystery in deep learning. arXiv preprint arXiv:2203. 10036, 2022.
[9] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on learning theory, pages 1305-1338. PMLR, 2020.
[10] François Chollet et al. keras, 2015.
[11] Edo Cohen Cohen-Karlik. Avichai Ben David, Nadav Cohen, and Amir Globerson. On the implicit bias of gradient descent for temporal extrapolation. International Conference on Artificial Intelligence and Statistics, pages 10966-10999 10981. PMLR, 2022.
[12] Edo Cohen-Karlik, Itamar Menuhin Gruman, Raja Giryes, Nadav Cohen, and Amir Globerson. Learning low dimensional state spaces with overparameterized recurrent neural nets. International Conference on Learning Representations (ICLR), 2023.
[13] Alex Damian, Eshaan Nichani, and Jason D Lee. Self-stabilization: The implicit bias of gradient descent at edge of stability, arXiv preprint Xiv: 155944 2022.
[14] Tri Dao and Albert Gu. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality. arXiv preprint 20X1v:2405.21060 2024.
[15] Omer Elkabetz and Nadav Cohen. Continuous vs. discrete optimization of deep neural networks. Advances in Neural Information Processing Systems (NeurIPS), 34:4947-4960, 2021.
[16] Melikasadat Emami, Mojtaba Sahrace-Ardakan Parthe Pandit, Sundeep Rangan, and Alyson K Fletcher. Implicit bias of linear mns. In International Conference on Machine Learning (ICML), pages 2982-2992. PMLR, 2021.
[17] Ji Gao, Amin Karbasi, and Mohammad Mahmoody, Learning and certification under instance- -targetd poisoning. In Conference on Uncertainty in Artificial Intelligence, 2021.
[18] Jonas Geiping, Liam Fowl, Ronny Huang, Wojeicch Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. arXiv preprint wwXiv2209.002777 2020.
[19] Paolo Glorioso, Quentin Anthony, Yury Tokpanov, James Whittington, Jonathan Pilault, Adam Ibrahim, and Beren Millidge. Zamba: A compact 7b ssm hybrid model. arXiv preprint arXiv:2405. 2024.
[20] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics. pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[21] T. H. Gronwall. Note on the derivatives with respect to parameter of the solutions of a system of differential equations. Annals of Mathematics, 20:292, 1919.

---

[22] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00075,, 2023.
[23] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections, 2020.
[24] Albert Gu, Karan Goel, and Christopher Ré, Efficiently modeling long sequences with structured state spaces, arXiv preprint arXiv:2111.00390 2021.
[25] Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models, 2022.
[26] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Im- plicit regularization in matrix factorization. Advances in neural information processing systems (NeurIPS), 30, 2017.
[27] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems (NeurlPS)) 31, 2018.
[28] Ankit Gupta, Albert Gu, and Jonathan Berant, Diagonal state spaces are as effective as structured state spaces, 2022.
[29] Chirag Gupta, Sivaraman Balakrishnan, and Aaditya Ramdas. Path length hounds for gradient descent and flow. Journal of Machine Learning Research, 22(68):1-63, 2021.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 20155
[31] A. C. Hindmarsh. ODEPACK, a systematized collection of ODE solvers. In R. S. Stepleman, editor, Scientific Computing, pages 55-64, 64, Amsterdam, 1983. North-Holland
[32] Roger A. Hom and Charles R. Johnson. Hermitian and symmetric matrices, page 167-256. Cambridge University Press, 1985.
[33] W Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Metapoison: Practical general-purpose clean-lahel data poisoning. Advances Neural Information Processing Systems (NeurlPS), 33:12080-122 12091, 2020.
[34] Ziwei and Matus Telgarsky. Directional convergence alignment deep learning. Advances in Neural Information Processing Systems, 13:17176-17188 2020.
[35] Chi Jin, Rong Ge, Pranceth Netrapalli, Sham M Kakade, and Michael Jordan. How escape saddle points efficiently. International Conference on Machine Learning (ICML), pages 1724-1732. PMLR, 2017.
[36] Diederik Kingma, Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6989, 2014.
[37] Yiwen Kou, Zixiang Chen, and Quanquan Gu. Implicit bias of gradient descent for two-layer relu and leaky relu networks on nearly-orthogonal data, Advances Neural Information Processing Syxtems, 36: 30167-30221, 2023.
[38] Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
[39] Andrew K Lampinen and Surya Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks. arXiv preprint arX9v:1809. 10374, 2018
[40] Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ili,, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvn,, Matthias Gallé, et al. Bloom: A 776b-parameter open-access multilingual language model. 2023.
[41] Quentin Lhoest, Albert Villanova Del Moral, Yacine Jemitee, Abhishek Thakur, Patrick Von Platen. Suraj Patil, Julien Chaumond, Mariama Drame, Julien Plu, Lewis Tunstall, al. Datascts: A community library for natural language processing. arXiv preprint arXiv:2109.0268 09.0009 2021.
[42] Binghui Li, Zhixuan Pan, Kaifeng Lyu, and Jian Li. Feature averaging: An implicit bias of gradient descent leading non-robustness in neural networks. arXiv preprint arXiv:2410.10322 2024.
[43] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839) 2020.
12

---

[44] Soon Hoe Lim. N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney. Noisy recurrent neural networks, Advances in Neural Information Processing Systems (NewrlPS),
2021.
[45] Jiashuo Liu, Zheyan Shen, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-of-distriutiinn generalization: A survey, arXiv preprint arXiv:2108. 130000..3.2.... 2021.
[46] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: /00X:v:99000000 05890, 2019.
[47] Kaifeng Lyu, Zhiyuan Li. Runzhe Wang. and Sanjeev Arora. Gradient descent two-layer nets: Margin maximization and simplicity hias. Advances in Neural Information Processing Systems, 34:12978-12991, 2021.
[48] Xuezhe Ma. Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyer. Mega: Moving average equipped gated attention. International Conference on Learning Representations (ICI.R), 2023.
[49] Saeed Mahloujifar and Mohammad Mahmoody. Can adversarially robust learning leverage computational hardness? In International Conference on Algorithmic Learning Theory, 2018.
[50] Saced Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4536-4543, 2019.
[51] Pierre Marion, Yu-Han Wu, Michael E Sander, and Gérard Biau. Implicit regularization of deep residual networks towards neural odes. arXiv preprint arXiv:2309. 200i02330,,,221,,, 2023.
[52] Hancheng Min, Salma Tarmoun, René Vidal, and Enrique Mallada. On the explicit role of initialization on the convergence and implicit bias of overparametrized linear networks. In International Conference on Machine Learning, pages 7760-7768. PMLR, 2021.
[53] Chris Mingard, Guillermo Valle- Joar Skalse. and Ard A Louis. Is sgd a bayesian sampler? well, almost. Journal of Machine Learning Research, 22(79): 1644, 2021.
[54] Chris Mingard, Henry Rees, Guillermo Valle-Pérez, and Ard A Louis. Do deep neural networks have an inbuilt occam's 's razor? arXiv preprint 27X662230.00677, 2023.
[55] Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv: arXiv: 1709.0/93, 2017.
[56] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614 2014.
[57] Alan V. Oppenheim, Alan S. Willsky, and S. Hamid Nawab. Signals & systems (2nd ed.). Prentice-Hoe Hall, Inc., USA. 1996. ISBN 0138147574.
[58] Antonio Orvieto. Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning (ICML), pages 26670- 226788..668.... PMLR, 2023.
[59] Rom N Parnichkun, Stefano Massaroli, Alessandro Moro, Jimmy TH Smith, Ramin Hasani, Mathias Lechner, Qi An, Christopher Ré, Hajime Asama, Stefano Ermon, et al. State-free inference of state-space models: The transfer function approach. arXiv preprint arXiv:2405.0m
2024.
[60] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[61] Maciej Pióro, Kamil Ciebiera. Krystian Król, Jan Ludziejewski, and Sebastian Jaszezur. Moe-mamba: Efficient selective state space models with mixture of experts. arXiv preprint 244i::2400.0008 2024.
[62] Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. In International Conference on Machine Learning (ICML), pages 28043-28078. PMLR, 2023.
[63] Hrithik Ravi, Clay Scott, Daniel Soudry, and Yutong Wang. The implicit bias of gradient descent on separable multiclass data. Advances in Neural Information Processing Systems, 37:81324 81359, 2024.
[64] Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. Advances in neural information processing systems (NeurIPS), 33:21174 22121174-1117. 2020.
13

---

[65] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In Interna- tional Conference on Machine Learning (ICML), pages 8913 8924, PMLR, 2021.
[66] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization hicrarchical tensor factorization and deep convolutional neural networks. In International Conference on Muchine Learning (ICML), pages 18422-18408 PMLR, 2022.
[67] Olivier Roy and Martin Vetterli. The effective rank: measure of effective dimensionality. 2007 15th European Signal Processing Conference, 2007.
[68] P K Sahoo and T Riedel, Mean Value Theorems and Functional Equations. WORLD SCIENTIFIC, 1998. doi: 10.1 142/3857.
[69] Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv: 2013.
[70] George R Sell. Smooth linearization near fixed point. American Journal of Mathematics, pages 1035 1091, 1985.
[71] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. Advances in neural information processing systems (NeurIPSS, 31, 2018.
[72] Shai Shalev-Shwartz and Shai Ben- Ben-David. Understanding Machine Learning: From Theory to Algorithums.
Cambridge University Press, 2014.
[73] L. Silverman. Realization of linear dynamical systems. IEEE Transactions Automatic Control, 16(6): 554-567, 1971, doi: 10.1 1..110//TC..11
[74] Alex Simpkins. System identification: Theory for the user, 2nd edition (ljung, I,; 1999) [on the shelf). IEEE, 19(2):95-96, 2012. doi: 10.1 W00.///A..212.21922.....
[75] Jimmy TH Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling. In International Conference on Learning Representations (ICIR), 2023.
[76] Eduardo D. Sontag. Mathematical control theory deterministic finite dimensional systems. Texts in applicd mathematics 6. Springer-Verlag. New York, 1990. ISBN 0387973664.
[77] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1 57, 2018.
[78] Shih- Yu Sun, Vimal Thilak, Etai Littwin, Omid Saremi, and Joshua M Susskind. Implicit greedy rank learning in autoencoders via overparameterized linear networks. arXiv preprint wxXivv2107.01300 2021.
[79] Fnu Suya, Saeed Mahloujifar, Anshuman Suri, David Evans, and Yuan Tian. Model-targeted poisoning attacks with provable convergenee. In International Conference on Machine Learning (ICML), pages 10000-10010. PMLR, 2021.
[80] Gerald Teschl Ordinary differential equations and dynamicul systems, volume 140. American Mathemati- cal Society, 2024.
[81] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Maric-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Erie Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arxiv preprint arXiv:2302. 13971, 2023.
[82] Guillermo Valle-Pérez, Ard A Louis, and Chico Q Camargo. Deep learning generalizes because the parameter-function map is biased towards simple functions. In 7th International Conference Learning Representationss ICLR 2019, 2019.
[83] Gal Vardi and Ohad Shamir. Implicit regularization in relu networks with the square loss. In Conference on Learning Theory (COLT), pages
PMLR, 2021.
[84] Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau. Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 1733)261-272, 2020.
[85] Junxiong Wang. Jing Nathan Yan, Albert Gu, and Alexander M Rush. Pretraining without attention, arXiv preprint 221 10544, 2022.
[86] Zheng Wang, Geyong Min, and Wenjie Ruan. The implicit bias of gradient descent toward collaboration between layers: A dynamic analysis of multilayer perceptions. Advances in Neural Information Processing Systems, 37:74868 74898, 2024.
14

---

[87] Johan S Wind. Vegard Antun, and Anders C Hansen. Implicit regularization in ai meets generalized hardness of approximation in optimization- sharp results for diagonal lincar networks. arXiv preprint arXiv:230.004J00 2023.
[88] Blake Woodworth. Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Iay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673, PMLR. 2020.
[89] Jingfeng Wu, Vladimir Braverman, and Jason D Lee. Implicit bias of gradient descent for logistic regression at the edge of stability. Advances in Neural Information P Processing Systems, 01174222--72555 2023.
[90] Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unitying view on implicit bias in training linear neural networks. arXiv preprint arXiv:2010.02500 2020.
[91] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-11 -15111771,,,-1 2021.
[92] Shihao Zhao, Xingjun Ma, Xiang Zheng, James Bailey, Jingjing Chen, and Yu-Gang Jiang. Clcan-label backdoor attacks video recognition models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 14443-14452, 2020.
[93] Chen Zhu, W Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on deep neural nets. In International conference on machine learning (ICML). pages 7614-7623, PMLR, 2019.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All of our theoretical claims and empirical results are clearly presented in Sections PettionstooP to
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
The limitations of work are properly discussed in Section 5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

All of our assumptions are clearly presented before each claim. All claims are rigorously proven in the appendix, with concise proof sketches in the main paper.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all implementation details in Appendix J Code for reproduc- ing the experiments will be made available at hhttts://githhii cwmm Poc//ooniiiiia YYoiilluzzyy98) imp- hupp-bas--senn pop-bbisssssmpossooss
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide all implementation details in Appendix J] Code for reproduc- ing the experiments will be made available at httts://gitthbb wttpaaa..ooo/ooaoaaaaaaa....teee wtw.coo///o/o// com/YonisSutzz2yy8/ imp saa-biassssmms poisonn
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
CCoeee//moeSSSmmeeeee ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
We provide all implementation details in Appendix p Code for reproduc- ing the experiments will made available at imp -is--aassss--osoonn
Justification:
com/ Yon S0nttkyy2998/
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Tables and 5 report the standard deviations for the synthetic clean-label poisoming experiments reported in Tables a respectively. Tables and [8) report the
and
standard deviations for the real-world clean-Tabel poisoning experiments reported in Tables [] respectively. Further demonstrations of the dynamical characterization (as shown in Figure 2). covering additional settings and random seeds, appear in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals. or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide all implementation details in Appendix D Code for reproduc- ing the experiments will made available at
com (ttom/ooonSuuttt888
imp bias-ssm-pooson
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics /ttpehitttte///rrrrpp.....aaaate https//cccpplitt/tttccciiiidddd
Answer:
[Yes]
Justification:
This paper fully conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
We explicitly discuss the broader impacts of our work in Section
Guidelines:
19

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not deal with data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We properly cite the usages of the CIFAR-10 dataset 38 the $4 model 24 and the gradient matching method [18 in Section 4.2
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets Jatasets.paperssi
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide all implementation details in Appendix J Code for reproduc- ing the experiments will be made available at
stmp-baas-ssmmpolse
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:// http://uuuppscccoooffeefeeeeeeee wct.oaafeeeccce//225//////////// for what should or should not be described.
22

---

A Related Work
An SSM can be viewed as a special case a linear dynamical system (LDS); a classic object of study in areas such systems theory [57] and control theory 176). The problem of learning from data an SSM that admits in-distribution and distriibbtittooionn generalization is an instance of what is known in the LDS literature as system identification [74]. Determination of whether a high dimensional SSM realizes a mapping that is also realizable by low dimensional SSM (in our context, these are student and a teacher, respectively) is considered in the LDS literature under the topic of minimal realization theory [73]. Despite these connections, our work is distinct from classic LDS literature: studies the implicit bias of gradient descent, a phenomenon brought to light by the recent rise of overparameterized neural networks [55]
A significant line of research has characterized the implicit bias of gradient descent in over- 56
parameterized neural networks [69
51 633 Several recent works formally studied the implicit bias of gradient descent in the [6 12 a broad class of models that includes SSMs. Some
39
77
27
46
34
9 90
5
52 47
89 87
37
86
42
context of recurrent neural networks [6
of these works [16] 12] focus specifically on SSMs, in particular Cohen-Karlik et al. [12] which we extend (by lifting the unrealistic assumption of infinite training data see Section T.. However, to knowledge, none of the prior works on the implicit bias of gradient descent over SSMs or recurrent neural networks have formally established susceptibility to clean-label poisoning, we do.
Since its demonstration in Shafahi al. 771] clean-label poisoning has received significant empirical attention 193 92 33 I It was also studied theoretically for convex models [79] 6 To our knowl- edge, none of the prior works on clean-label poisoning have formally established the phenomenon for SSMs, whose optimization is non-convex.
B Extensions of Theorem I and Proposition 2
In this appendix, we extend Theorem D to allow for additional training sets, Furthermore, we outline extensions of Theorem and Proposition 2 settings in which: (i) the teacher SSM is of arbitrary dimension d' 2 2: (ii) the input and output matrices the teacher SSM vary; and (iii) the input and output matrices of the student SSM are learned (as opposed to being fixed throughout training).
Clean-label poisoning with additional training sets. Theorem 2 below extends Theorem D to allow for any training set S permitted by Proposition 2 (i.e., for any choice of training sequences (x())) where: for every E [n), x(9) has zeros in its last two elements and non-negative values elsewhere; and x * 0 for some E [n]), at the expense of the added (cleanly labeled poisonous) sequence xf potentially having large norm
Theorem 2. Consider the teacher-student setting of Section 2.3 subject to Assumptions [and] 2 Suppose that for every i E [n] the training sequence x has zeros in its last two elements and non-negative values elsewhere. Suppose also that x(1) + O for some i E [n]. Finally, suppose that the dimension of the student SSM satisfies d 2 5. Then, for any k E N23, 8 E R>0 and E Rzo, there exists scalar E R2:0 and open set I of initializations for the student SSM such that with any initialization I:
there exists time E R2o which gradient flow reaches point where the training loss is at most 6, and the generalization errors over sequence lengths 1, 2....... are at most E; and
appending to S the (cleanly labeled) example (xt y²), where xt == c. c. E R and y' := ((r _B cC- (-)(x)),, ). leads to the existence of time E R:00 at which gradient flow reaches a point where the training loss is at most ö, and the generalization error over sequence length le is at least 0.5 2/d.
Proof. See Appendix G
50 17. but such treatments considered different type of poisoning, namely, one where poisonous examples come instead of (rather than addition to) original training examples.
Non-convex models were theoretically treated well 49
'An additional limitation of Theorem 2 compared to Theorem that its guarantees pertain to some point along the gradient flow trajectory. whereas those of Theorem pertain to the trajectory's 's limit.
23

---

Teacher of arbitrary dimension. For any d" 2 2, consider the following parameter assignments for the teacher SSM:
0
0
0
A"
E R
d''
B
d
ER' -
R
RRIdd
In this setting, the mapping 0 1.-.BB (+) realized by the teacher SSM is the same as the mapping realized by the teacher SSM defined in Equation (TO) (where the teacher has dimension d' = 2). Accordingly, Proposition and Theorem and their proofs apply as stated.
Varying teacher input and output matrices. Given any teacher SSM A*, with which Proposition F Theorem [ (including a high dimensional teacher as described above), similar results hold with the teacher SSM (A", a2 B² B ayyC), where a1, 0g E Rg are arbitrary. Indeed, if likewise scale the values of the (fixed) student parameters B and C, L.e replace B by on B and C by azCC, then for every sequence x:
(A B (x,C)((()) 0,
and likewise:
(,z)(())))) = -a (1..)xA...))
The training loss and its derivatives thus scale by a positive factor, and so do generalization errors (Definition Tb. Accordingly, the proofs of Proposition and Theorem carry through.
Learned student input and output matrices. Below outline modification of Proposition 2 and Theorem that accounts for a setting which the input and output matrices of the student SSM are learned. Suppose these input and output matrices- B and C,, respectively- are learned with a learning rate (step size) that may be different from the learning rate of the student's state transition matrix A. Formally, suppose the optimization trajectory (A()), C()) is governed by the following dynamics:
δ
A(t) Ls (s((t)),
((t)(t)((t),C. C(t))
DA
0
B(I) -1 fs (((t),) B()), C()) E R2o.
(11)
aB
C(t) = - ac a (s(((t), B())
where v) > O represents the ratio between the learning rate of and C, and the learning rate A. Consider trajectory induced by Equation (TT) and corresponding trajectory that emanates from the same initialization, but where only is learned (or equivalently, where 7j in Equation [1I is
replaced by zero). Arguments similar to those used in the proofs of Proposition 2|and Theorem ] can be used to show that the divergence between these two trajectories is upper bounded by quantity that depends on 7), and in particular tends to zero as does, Accordingly, if is sufficiently small, generalization errors attained when A, B and C are learned jointly (i.e., when optimization governed by Equation (T)), are close to those attained when only is learned. Proposition 2 and Theorem which apply to setting where only A is learned-thie translate to results that apply to setting where and C are also learned.
C Low Training Loss with High Generalization Error
As stated in Section 2.3 it was shown in Karll- et al. [12 that, regardless of the size of the training set S (i.e., of r²). and the length k input sequences it comprises (namely, (x(1) E IR* ) ) there exist assignments for the student SSM (A, B, C)) which minimize the training loss (.(.), yet suffer from arbitrarily high generalization error over sequence lengths beyond K, e.g. over sequence length + 1. For completeness, prove this fact below.

---

Proposition 3. For any e E Ry0 there exist assignments for (A, C) with which the generalization error is zero over sequence length k. yet it is at least over sequence length k. + 1.
Proof. Let d > which we will take as the dimension of our student SSM, and let
(A, B, C) = (Diag(ai....., aa), (e,,,,,,.,)
We we will consider the system of equations
where E Rd. First, observe that claim follows if solution (A, B, C) exists for for every Indeed, take such that its first entries coincide with (A") Jogigk-1, and each of its final d - к entries differs from the corresponding entry of (C*(A") B" Jesisd-1 by or more. Then (A, B, C) solving these equations would provide the required assignment. To that this system is indeed solvable for every E gd note that it can be rewritten as V g I, where
1 a1
of
d
1
a2
0
a2
Od 0
and g = (bici,.... baca) V is a Vandermonde matrix, and it is well known that it is invertible as long as 01. Od are all distinct. Therefore for any such r, and fixed, distinct a1,..., Ad, one can solve the equation by setting g (VT)-'n To obtain (B, C)) which satisfy (VT)-1g 'r, simply set B 1 and C g
D Proof of Proposition 1 (Dynamical Characterization)
Fix t 2 0. We use the following shorthands for simplicity:
((x( = (() (x ())
(xx()) = ((008.0).)))))
The objective Es in time t takes the following form:
((())), C(t)) = Σ (0 -(x(0)))) 2)
Fix j E [d]. Deriving w.r.t (t) and consecutively applying the chain rule obtain the following 0 B(),
1
0x(x(1) (v (00--((x') -(x(0)
Day(t) x(x())
(t)
n
2
(x) - (())
da,(1)) o (d(x())) w(t)
-0)()
n
800) (t) 0l, (()) (ty(t) 6(x
O2
=e((())
800 (1) (t,(t)
(4).
"Note that this implies zero training loss, i.e. Es (A, B, C) = 0 for any training set S of sequence length k. regardless of its size.
25

---

Recalling that A is diagonal, we have that C())A()= -0) Hence,
2
8
(1)
(100))a((0
())
Oaz(1)
1=1
1=1 y'=1
2
(t)E
(t)
(k- (0x=
(**).
Reversing the order of summation and reordering we receive the following:
20 1)+1)
(**) = -b)(() Σ az(t)'
( (t) (t)a
n
a The proof concludes by noting that (t) 3ay(1)
(((A))
E Proof of Proposition 2 (Generalization)
Proposition 2 follows from Proposition 4 which is identical up to allowing the non-zero diagonal element of A to be any positive value instead of
Proposition 4. Consider the teacher-student setting of Section 2.3 subject to Assumption 2 and the teacher SSM given by
A == 2)=00).B
a
B" B1
va-1)" =1= Vd-1),
(12)
for some > O. Suppose that for every i [n] the training sequence (6) has zeros last two elements and non-negative values elsewhere. Suppose also that x0) + 0 for some i E [n]. Then, for any k N, E E Rx and E R2 there exists a time R=0 and an open set of initializations for the student SSM, such that gradient flow initialized in I reaches at time point at which the training loss (s(.) is no greater than 5, and the generalization errors over sequence lengths 1,2 ... k are greater than t.
Proof. For k E N and A E Rdd,d, we denote by Geng (A) the generalization error over sequence length is (Definition TT. Note that and C are omitted from this notation, as they are fixed to the values B = 1,C 1 throughout the proof. With slight abuse of notation,
also denote
(s(A) := B, Consider the point A, = (ap, .,....., where 0 < ag < a". We will first show that if we initialize Ao. gradient flow will converge to (a", (a".0..... .0.....0) O), and therefore achieve perfect generalization. Indeed, writing 3 in terms of the entries of A we get:
(s(A(r))
1 Σ
Σ
Σ 1=2
Σ
a5(())
xx--1
The derivative of (A(A) with respect to ap is therefore:
k-1
H-1
d
dap (s(A) =
Σ lap 1- xx-1)
n-1
1=2
For 2, (0) 0 and thus (,( a ls ((()) = 0. Therefore for all j 2, (t) = 0 for
du,
all - > 0. Hence it suffices to show that a1 (7) converges to a" as T - co. To see this, note that
because a, = 0 for all >> 0 the dynamics simplify to
(T(
i daj
ls (s(T)))
2 Σ n
Σ 1=2
22 ((r)'" -(())"((((777)))
Σ (ta
26

---

For E [n], at T = 0 it holds that
Σ aa (t) (t) 20 2
by the non negativity of the entries of x()) Additionally, by the positivity of at least one of the entries of (1) for some i [n]. at least one of the above expressions is positive. Furthermore, this expression can equal zero if and only if 01 a" (in which case (T = 0). Therefore âi (r) > 0 for all 7 > 0, and hence a1 (T) is monotonically increasing. is also bounded from above (by )"), thus it converges. Furthermore, the limit must be point where the derivative vanishes, and therefore it must equal a".
Because A(T) converges to (a" ......,0 0) when initialized at Ao for any e, > O there exists t > 0 such that (s(())) < 2' Genz(A(E)) < 6
2" Now by the continuity of (s(.), Geng(-) and by Lemma 29 there exists an open set such that, if we initialize gradient flow from A(0) E I, resulting in the trajectory A(T), we get that |IA(t) A(t)ll2 is sufficiently small to ensure that (s(A(t)) <8, Geng (A(t)) <c.
required.
F Proof of Theorem | (Clean-Label Poisoning)
The outline of the proof is follows. Appendix F.1 details the setting and additional notation. Appendix [F2 analyzes gradient flow over fs. where the dataset S does not include "poisoned" samples, and shows that it converges to generalizing solution. Appendix [+3 analyzes gradient flow after the addition of "poisoned" samples, establishing that generalization degrades. Appendix [F44 proves that the different initialization sets considered in Appendix F22 and Appendix F.3 intersect, and that one can construct an open set I such that both phenomena occur.
F.1 Setting and Additional Notation
We will slightly change our notation and use L to denote the sequence length, and as an index. For any E Rdd and any 2 0 we use (x) denote
(x) = {z E Rd ||X z||2 < <r}
(13)
and (x) to denote
(x) == (z E Rd: ||x - 2/12 1 rr.
(14)
For any x E IRd and any V y RRd we define the Euclidean distance between x and as
Dist(x, V) = inf zEV |x z/|2-
(15)
We use Wi and W22 to respectively denote
Wi == Span W3 = Se=n ,.,...,e) er - -e
(16)
Note that for any j E {2...., d} it holds that
1 (e) - -e)== - Hence Wi and W2 orthogonal. Additionally, it holds that
Wi W/2 = (0) dim Wi hence Wi U W2 = Rd. Finally, for any sb 2 0 we use Diff(u)) (b) to denote
dim W2 d - 1,
Diff(v) = x Rdd Vi,j E [d] I æ, s tb
(17)
and C denote
0 = { x :Rdd aRd: 3i,J E [d] s.t. |xs xz > 1b
(18)
27

---

Recall that the teacher SSM (Equation
10 is given by C)), where
A
1 0 0
8" =1 vā-1) C²=
(1 va-1).
claim that the teacher is equivalent, i.c. has the same impulse response, as a d-dimensional SSM 0....,00,,
with A = Diag(1, 0, .,..., 0), , Ba
and Cd _
Proposition 5. For all 2 0
=
Proof. It is easy see that both expressions evaluate to d when i 0, and to when 2
We will henceforth abuse notation slightly and redefine the teacher (A", B", C*) to equal this d dimensional teacher, i.e. we set A == A B = Bd, C == =cd
We denote the generalization enror on sequences of length I. (Definition 1 by Genz ie.
(A) == max E00.._E(........111 BA C B (At) c*
For training set S = ((x(0, ())))) ==1" we make a slight abuse of notation and denote the training error of weight matrix A Rd.d to be
==
(s(A) = (s, Bs 1
(y -(A_)=(())))
Note that B and C' are kept implicit in these notations, as they are fixed to the values B = =1,0=1 throughout analysis.
Examining the teacher weights (A", B²,C"), ) one can note that for any j E [L 1] and any 2 it holds that
d
CI (.)) = -
0 2-
To facilitate clearer distinction, we denote S₁ the training set considered in the first case, and Sp the training considered in the second case. We provide below explicit description of the training sets and their induced losses.
Definition 2. The training sets S₁, S2 are defined as follows:
S {(xx)) 3)} {(e BB
S₂ {xx, 3). (xl, v²) {(e) px 8 (er1
The objective (s, (.) takes the following form:
Es. (A) (Ó<A) B. ((aB)c)))))))) = -100)2111111
-(1-
Σ
a
L-1
(19)
For any time / 2 and any index j E [d] the gradient flow update di (1; takes the following form
(I; = Daz (t; S1) ls (A(I; = 2(L = Σ au (I: a,(115))) (a((:_))/-/)a(((..))))- (20)
The objective (.) takes the following form:
(A) 1 (0-r,
1
(1 a 1- + (1
Σ ax)
(21)
2
k=1
1=1
28

---

For any time t 2 and any index E [d] the gradient flow update d, (t; S2) takes the following form δ
dy(t:82) da,(t;S2) S2)
Ls ls (A(t:S2))
d
(22)
Σ (tx (a((tS))(-11 -(
= (L -L-
(t:
+1
Σ
as (t; S2).
Note that by Lemma 23 the above flows are defined for all t > 00 We denote by To a set of initial values for the matrix A which will use throughout the proof
To = a (G........, ..) ERÉ : E (0, 2d - <>>6>
> c020J.
(23)
Throughout Appendix F.2 and Appendix H3 will be concerned with subsets of Tu for which the respective claims hold.
F.2 Gradient Flow Under S Generalizes
Throughout this part, we omit the dependence on S for simplicity. We begin by proving that when initializing at some A(0) E To, the parameters of A converge point where the training loss equals zero.
Lemma 1. Suppose we initialize at A(0) To and evolve A(t) according to the gradient flow dynamics in Equation 19). Then the limit lim, A(t) =: Ai exists and satisfies
((A)) 0.
Proof. We first prove that for any j E [d]] and for any time 2 0 holds that
ac, S ay(1) 1.
Recall that
10(1 ( Σ (n(()=1)) a,(1) )a,0))-)a,000000
d,(1)= =
Hence, by Equation 23 it must hold that diş(1) for any 2 0: Since aci and since L is even we have
(ac 21 d. (aci)=-1 21 dl 1 2d
- - >0. 0.
1=1
we have d0 > For any 0, if the derivative equals zero then either 1 - Edm (-)- or (t) = 0, implying the derivative must remain equal to zero for t' t. Hence, at, S (t) for any 2 0. Additionally, for any time 2 0 it holds that initialization is positive by the above, and again if at some point is equals zero then it must remain zero thereafter. Therefore, a!()) can never reach 1: since L - 1 even and since all entries are strictly positive, if were reach or cross 1 we would reach contradiction to the previous argument. Thus, we have showed that the gradient flow trajectory is contained in the following open and bounded set:
Hence at time
Ex_1 (1) 2
V = (2(
B Bus (0).
Note that the teacher 4 is within V. Next, claim that within y the objective l satisfies the PL. 22L-4 Indeed, for any V and
condition (see Definition 13 with PL coefficient 2(L ()2( 2vd
any E [d] holds that
0 Dag
(()) ((A)=2(L- 2(L 10(111 Σ
L-2
ag
a
10 A is diagonal matrix, treat Io subset of [
29

---

For any A E V there must exist an index j E [d] for which
laye 2
acd 2vd
and thus
V((A))
2(( - 1)(1 Σ
L-1
)a
4-2
4
k=1
4(L -1) 1))aat--((AA) (((A)
add
2L-4
2 2(.. - 1)2
((A).
2vd
Finally, there exists some constant M > such that within V the objective has M-Lipschitz gradients. since l is analytic in R and since V is contained within the compact and bounded (0).
The above conditions allows us to invoke Lemma 25 which states that the limit lim A(t) =: A exists and satisfies {(A(t)) = 0 as required.
O
We now introduce set I1 To, under which we prove the rest the claims in this section.
Definition 3. Let 1/2 > We use I₃ (71) to denote the following subset of Ty:
(1-1--11 d d-1
m1) m1)=- 7
(1)) = AE AeIo:Vie
(1-
(1-
We now prove that if A(0) Iı the first diagonal entry tends 1, while the rest of the entries must remain close to 0.
Proposition 6. Let m > O. Suppose we initialize at A(0) E (m) and evolve A(t) according to the gradient flow dynamies in Equation 19.. For any j E f2.....dl d} and for any time 2 0 it holds that:
0 S a)(1)s 1-
m))-1111 (1-(1--)-1- m
Z
d
Additionally, there exists some time t* 2 0 such that for any time 2 t it holds that:
m S a1)))) 1.
Proof. Per the proof of Lemma 1 (t) 2 for any j E [d] and t 2 and thus the entries (t) are positive and non-decreasing (as Tunctions of 1). Reordering the dynamics, we have the following for any j (2. and for any time 0:
dG(T) a-(7)(122 2
2(1 16--11 (1-11-11 (1-1 [a((t)--1)
di(7) a1(7)1-22 ( -L+2
(T)
L+2 -+2
L+2
Integrating both sides w.r.t time, we receive the following for any time >
(t) (t) -4+3 L+3
(0(33-L+3 L+3
[ (F)
4+2
L 3
-L+
[ di(()a -L)277
(t) L44
a1 -L+3
L 1+
-L+3
Organizing the equation and plugging the initial values, we get that
az 1=113 aa) L+3 + (aC,) L43 L+3
L+3
30

---

Both sides are positive by our first argument and since ac, < and so taking the 1
I-3 root yields
a²(1)
(1(() 1-3 (aG,)
L+3 - a L+3
(n(;) 1
(a{)) ) 1-3
1-
5/
c
aG
1--5/-3
Since A(0) E In (m)) we obtain that
ay(t) v
(1 1111
711
(1
5
1-
d --1
c/-3
m1 1 7
I
as desired. We now show that there exists t* such that for any time 2 8" it holds that
a1 (t) 2 1 771
By Lemma there exists time t" 2 such that for any t 2 ts it holds that
2 S m/
{(((I)) 1 -
(1(1)_11)
Therefore, for any time ta we have
(n(() S a
as (1) s1+
m
k=1
Focusing the left hand side and plugging the bound the rest of the entries, we receive
1 m)
1 1- m S (at) + (d-1)
11 a1(t) -1 11 (1 m)1-1 771
d
Rearranging yields
m S a, (t) - 1 m
Additionally, 01 (f) never cross since L 1 even and since all entries are strictly positive, it were to cross 1 we would reach a contradiction to the argument in Lemma S that the residual 1 Ed_ 0g (t) is always non-negative. With this we complete our proof.
An immediate result from Proposition i the following corollary regarding the student's recovery of the teacher.
Corollary 1. Let m 0. Suppose we initialize at A(O) E Iı (m) and evolve A(t) according to the gradient flow dynamics Equation 19 The limit lim A(I) A satisfies
1 (1 4-1 m
| A²I S
op (d
Proof. By Proposition 6 there exists time l" > 0 such that for any time /. 2 1" it holds that [|A(t)
| 1|2
(1
1 1- 1-1 171
2
(1 a, (1)) Σ (0 (1)))(1)²² < 7 + (d a 1)
2=
The argument follows from Lemma I and from continuity.
31

---

Remark 1. Note that the upper bound in corollary ! satisfies the following
(1 (1 11 ) -- 1/1
lim
rî + (d - 1)
71 -0
d d
1 1- (1 m1 m1)--1 911 221
lim oi + (d -
m +0
Hence, for any recovery threshold 5 > O there exists 17,,5 >> O such that A(0) E Ii (1(1)) then Ai recovers A with error of more than 6.
So far, have argued that the parameters of A converge point which is close A". We conclude by showing that this leads to low generalization error.
Proposition 7. Let L' 2 L ++2 2. For any > 0 there exists open of initializations In == (6.) such that under St, converges to a point such that Gen, y (A) S t.
Proof. Under the dataset S1, have shown above that for any å 0 there exists open set of initializations I (d) such that GF will converge to solution a whose parameters satisfy A|A-A']2 S 5. It follows from the continuity of the length L. impulse response that there is an open set of initializations from which converge to point Gen,' (A) S.
We abuse notation slightly and denote [c) = Ii (71,8, where on is the maximal that guarantees Geng' (Ai) S.
F.3
Gradient Flow Over S₂ Converges but Does Not Generalize
In this section, we show that one can find a of initializations Ig such that gradient flow under Sa converges to a point with high generalization error. The proof shows that gradient flow trajectories initialized in In evolve similarly to reference trajectories which provably stays away from any permutation of A TM| Since the training loss is non-convex, gradient flow trajectories can diverge from one another exponentially fast. Establishing that reference trajectory is tracked thus requires sharp bounds on convergence times. The proof in this section is rather involved and is thus split into several parts.
Appendix F.3.1 defines the reference trajectories and shows their poor ability of generaliza- tion.
characterizes the critical points of the objective focusing on a specific saddle point of interest (which we denote s).
Appendix F33.2
Appendix F.3.3
presents relevant background dynamical systems, introducing lineariza- tion result needed for the rest of the proof.
In Appendix 33.44 we start analyzing the trajectories themselves, showing that they must pass near s.
shows that the trajectories must escape sufficiently fast from using the tools presented E3.3
Appendix
F.3.5
Appendix F33.6 proves that after escaping from s the trajectories converge to global minima.
Appendix F.3.7 shows that the overall divergence between trajectories emanating from Iz and their corresponding reference trajectories can be bounded from above, implying the former trajectories have poor generalization.
Throughout this part, we omit the dependence on Sy for simplicity.
II Any permutation of A" yields system with the same impulse response.
32

---

F.3.1 Reference Trajectories
We begin by proving the following useful lemma which states that gradient flow maintains the order of the entries of A.
Lemma 2. Suppose we initialize at A(O) E I&d and evolve A(t) according Equation 22) Let T: [d] + [d] be permutation such that for any j E [d - 1}:
ax(3) (0) 2 az(++1)(0).
Then for any j E [d 1] and any 2 0 it holds that
(n(s)(1) 2 (x(+1)()).
Proof. Recall the dynamics from Equation
22
dx(t) (L 1)
(L-
(((())-2++1 +1
Σ as (t).
Jem
km
Fix j E [d- 1J. By the linearity of the derivative, we obtain the following equality by plugging the above dynamics
d म (0)))(1) a+(+))((t) (t) - ax(i+1)(t)
d
-1( - 1) -2( 11->a(1))--) -1-1-1(1--a(00))) (aTc))(1)==2
(1)4-))1))22))
Assume the contrary there exists some time 4 2 0 for which ax(z) (41) < ax1++)((1). By the assumption, 1 > O. By continuity, there must exist some time 12 E [0, (1) for which (12) =
(42) This would imply that for any / 2 l2. the derivative di (1()) ax(+u((!) is equal zero, which turn would imply that
(1) (x)-1)(1) (l())((2) - (x(++1)(1)) =0
in contradiction to the assumption on éj.
In what follows, we define the notion of reference initialization. Definition Let A Zo be some initialization the parameters. The corresponding reference initialization Aref is defined
Vj [d]. af 01, j 1,2 agj otherwise
We use Aref (1) denote the gradient flow trajectories emanating from the reference initializations.
We now prove that any point with zero training loss which is sufficiently close reference trajecory has poor generalization.
Lemma 3. Let L' L+2. There exists some 82 O such that any point A (a1, ... oa) Rd which satisfies:
{(A) -0
ai 2 02 2 ... ad
14 || s 82 for some point A (a .......)) Rdd such that a 02
must satisfy Gen, 2 min { 0.1, sd (1- (0.6) --1
1.
33

---

such that L is even. We now show that Proof. Let L' E { ...... L'}
L < cc
for some constant e > which is independent of T." This in turn implies that
Genz' (A) 2 (1 - CA -B) 2
which gives us the desired lower bound. this, we write
Σdp o Σ
O ak
First note that (ugl S for l E [d] this follows from the fact that L. even and from the fact
that ((A) = and hence Σ3 0g
Therefore, for all [d] we have
L -1 1
1- 1. 1a dx 4 11 11 1.- - S dg 1-1
0
Assume first that 01 02 a. Then clearly of -1 + az 1-1 2a S 1 and hence
L
02
L-1
2 al, 01,02 S 2
Now by continuity it follows that for sufficiently small 62 0, we have that if ||A A S 82 then
a1 02 & (0.6)III.
Let J = fr a, S 0}. For such indices we have af 1--1 < 0. Suppose that
Σ
2 0.1. * 1-1
KEJ
Then we have that
Σ
k
k
Σ
0g
L-1
1
L'
0k
1-1
Σ
a
4-1
< 0.9
1=1
kg
kgJ
kg.
kgJ
so we can take 0.1. Otherwise we have that
Σah a
2 0.9
kEJ
so there exists some & J such that a-
On the other hand, have
ag. aa S |a|| (0.6)
Therefore, since ke" & J we have 0 S az.
1-- -L v and so
-'-1
ax.
1- (1 a..
-1 N 9d
ax-)
2 //
1 (1 - (0.6)).)=-.).
9d
This yields the following:
1'
Σ
d
(ak-
a -11=
2 (1 (0.6)z²:)
1
Og
a
9d
which gives argument.
(0.6) T either case we can find constant c proving the
9d
Lemma 3 motivates to find open subset of initializations under which the respective gradient flow trajectories remain close their reference trajectory counterparts, as this would allow us to lower bound generalization error.
34

---

F.3.2 Characterization of Critical Points
In this section we characterize the critical points of the objective L.
Lemma 4, Let A E RR. be a point such that
V((A)= 0.
Then either A is a global minimum, i.e. {( = 0, or exists & E IR such that A = 8 1.
Proof. By Equation 222 for any [d] it holds that
((A) (L (L- Σ k
G -1)0 Σ
1- 0.
Daj
km
>k= 4k
1-1 1 = O, then the above implies that Σd= k=1 Ck
=
This in turn yields that
((A) = 2 ((11
+ (1
a#
=0
1=1
1=1
iee. is a global minimum. Suppose Σ Ek=1 Ox
1--1
1 1 0.
Then we obtain by rearranging that
1- -1
kiml ak
(L 1)
Ei 1-1 -1) OK
L- is odd, and so taking the L 2 root on both sides we obtain that
1 Ed R=1 ak
ag
(I - 1)
Ed Ok 16-1
-1 -1-11-1
completing our proof.
Lemma establishes that critical points of which are not global minima must reside within W1 (1 (Equation (16)). These saddle points pose an obstacle to the convergence of gradient flow global minimum. "The following lemma outlines the type of points gradient flow could encounter assuming we initialize at To or at a reference initialization.
Lemma 5. Suppose we initialize at A(0) E Io and at Aref (0), and evolve A(t) and Are according Equation (2.. Then for any time Z 0 it holds that
((())),(AA))))
1.
Proof. Per Equation 23 the entries initialization are arranged in descending order. Since L 1 is even we have that the initializations satisfy the incqualities
(4)0))
5-1 2 1 2 2(((() 4-1 112((1())
Σ (aCk) 6-1
ref
h-1
k=3
R
and
d
d Σ (a(k)
Σ (0) = - Σ 1=1
(a(k) 1-1((((1))
ref (0)
k=1
A=3
k=1
By Equation 23 holds that aç1 < 1 thus we have that
d - 2(aC)) 1-1 Σ (11 2 1 - d. (a(1)
21-111- dl
L-1
0
21
Am3
35

---

and
1 0.
1 2(aCi) (aCx) 2 - d. (a(i) 2 1 d(
2d
k=3
On the other hand, by Equation 23 also holds that aCa > 0, thus we have that
(oC)) f-1 s d. (a(a)==1 <1
and
1 - Σ
(aCa) s - d. (aSa)) < 1.
k=1
Therefore, the quantities
(0) 1
a
rel (0)2-1
1 Σ ax (0)
1
ref (0) a
k=1
k=1
are all within the interval (0, 1). Thus, the objective at both initializations is no more than 1 since both satisfy
-(A)= = 2 d- a4-1)² (1----110))) a)) - (12 12)
((A)
The proof is completed by the argument in Lemma 22 which states that under gradient flow the objective is -on-increasing.
The following lemma shows that only a specific region Wi can contain critical points with loss lower than that of the initialization points consider. This, along with Lemma 22 implies that only a specific region of Wi is relevant.
Lemma Let E TRd be a point for which there exists E such that = a Ifa & 12 3l then either VE(A) A 0 or ((A)
Proof. We begin by proving that for any E R, a & (0, 3 then must incur loss greater than If then it holds that d 3, hence obtain that
1
d. a))) (1-d. d. d-a)² >.
lla 1) - d d-aadaaae a
The same argument applies when a < - since in that case d-a < -1 = (1 d addaa)2 Next, we show that if hence
1- 4) then Vl(a 1) # O. Suppose a 1
2.2. 0). I, 1 is even and
d. d.a - = (L (L- (L- 1-1 -1j--
(0, 4-- c (..
L-1
gL-2
1-1 is decreasing for I, 2 3 and acheives the value 0.25 when 3, hence The function S(L) == gL
since L 2 3 we get (L) S 0.25. Thus we have for any j E [d] that the gradient's 's jth entry statisfies
Vi(a: 1) = ((L - (d a -at- + (d - 1)) S (0.25 + (d a 1)) < (0.25 1) < 0.
Suppose a E (0, 2). this case, we have that
dt-1 < d
1
d. d.
(L - 1)(d 1-1 - 1)at-2 < 0.
Hence, since d a 1 < we have for any j E [d] that the gradient's 's jthh entry satisfies
Vl(a 1), = ((L - () 4-1 --a²-2 2 - (d a - 1)) 0. Therefore, any critical point which is not global minimum and has value in (0, 1) cannot reside outside of [1, 3).
36

---

Having disqualified most of W1, we now identify the unique critical point on the non-disqualified region of W1 and show that it a global minimum.
Lemma 7. There exists unique E la 3) for which Vl(s 1) 0. Additionally, satisfies
s s.1. argmin ((A)
AEW1
and
{(s) 2 > 0.
Proof.
We focus on the following function:
f(a) (11-d-at--))
- at-1)2
(1 - d. a.)))
Note that f(a) E(a 1). It holds that
f(a): = (L 1-(1)(d-- a 1)a" + a
Note that f() Vi(a 1), for any j E [d], and so f (a) if and only if Vi(a 1) We proceed show that within |- z 11. (a) has root and is monotonic. holds that
f())=
d((L (())=((L--))
(d (0)--1 1)(0)=-2+ (d 0 1)) -
Next, since d 2 8 it holds that
3 )02 < (L. (1. (L - 1) d (2--))
1 -
)=--2= h(L).
d
21.-2
h(L) is decreasing function for L and achieves the value 0.75 when we get hLL) S 1. Therefore,
3, hence since
f ( d(L 1)(d 3 7 1)( 3 2 (d
3 1))
d
d(2 (L - 1)(1 d. 3
(()
2 d(2 1) 0.
Hence by continuity, S (a) has root within 2- 3) Note that by Lemma 4 I (a) doesn't have root within [- 4)) implying the root is actually achieved in 1 .). Next, it holds that 2,
fa) d((L ()L - 3)d 22--4 - (I 1) 2)a² d)
d 1)(L - 2)a
Because d 2 and L - is even, we have for any a E [1 1.1.3 3
(L 1L-1)(1 2) 3 2g00 ( g(L).
(L - 2 -
24-3
g(L) is a decreasing function for L > 4 and achieves the value 2.25 when L = 4, hence since L 2 4 we get g() < 2.25. Therefore
(a) 2 d(22-225)) > 0,
2. 2). Hence, there exists unique s E i1, 3 such that (s)s 0, which implies that Vl(s 1) 0. Note that we showed that is minimizer of I over 1 311 as f's derivative is zero at and the second derivative is positive along the interval. Finally,
implying f' monotonically increasing in 1-
let a E RR \ [- 2 3) By Lemma it holds that
f(a) = lla 1) 2 1.
37

---

On the other hand, it also holds that
1 ((a) < ((2) 2 (11 d () 1
+ +1 (1-d--3)
2
Thus, s is minimizer of/ over IR, meaning that 8. is minimizer of over Wi required. On the other hand, since 2 and 2 4 it holds that
1- d. 1-1 2 d. 2 (7-) = 3 1-3 3.. 1
3
Therefore,
((s) (11 d. 1- (1 - d. 8) (1-d. 12 0
2 8
completing the proof.
In the last two lemmas of this section, we explicitly compute an eigendecooppoittinn E's hessian in and bound its cigenvalues.
Lemma 8. Consider s defined in Lemmal 7 An eigendecompooition of the symmetric hessian matrix (() is the following:
The eigenvector 1 with the eigenvalue
X := (T. - () -3)d 1--1 - (T. - ((.-2)) + d.
jor E (2,...,d) d} the eigenvector C1 - Cj with the eigenvalue
x (1.
2) s 1)
Proof. We begin by computing the hessian matrix (²(((A for general A Rd, which is symmetric since ((A) is analytic. by Equation (22). for any j E [o]] it holds that
((A)= = (L
a
1
+
ak
1.
Dag
k=1
Therefore, for any j E [d] we have that
1j (PP((A)) = = (b- ((22 3)a3 (L - 2)
Σ
ak a
1- 1-3
(L -2)aaaa)) + 1.
km k.
Additionally, for any j, E [d] such that j # i we have that
(P(((A) = o6 +1.
i)
Now we specialize to A = s. For j [d], we obtain
(P((())
= =[ - ()(-1)((2T.)))) 32) 21. (I- (d ( (T. (2)= 2)5 3)+1
ij
(1 - 2 2 (L -2)s 113) +1
L
= -L--)((L-1+
2d 21- (L 222 +1 =: w1
2)
For j, [d] such that j * we obtain that
(v)((s)) ig
=(L -L- - 1)2 25. 1=:1::
Observe that
V2((s) (w) W2 + wa la.d
where La, is the d, d all ones matrix. Hence, by Lemma 26 we obtain that eigendecomposition for ((s) is the following:
38

---

The eigenvector 1 with the eigenvalue x == + (d - 1)
For j E (2.... df the cigenvector e e, with the eigenvalue A_ == w1 - w2.
A takes the following form:
A (L (
- (L- L d 2
2 - (L 2) 1 +1 (d- 1)(1))((- - 1)(( (
(T.-1)(T--1+11.) I. 2d Ld - I 21 (I- (2--2)8--3 2)) +d
= (L (d)
(L 2)s² 1 )
(L (22 1/1 (L 2)) --3 + d.
A_ takes the following form:
A_ (L - 1)((()))(L))))) - L. - 2 21-4 - (L 2)s²
1- 3) ((L 1)232 +1)
(L - 2d L + 1)822-1 (L 2)s -)5
(I. d(
(T. 2) b-3)
(I. () ((I--))d: 8 - (T. - ((-2)) 2) 1-3
(L 1)(L)))))))))) (2) s/d 1)s²~3
We now turn bounding X and A_ Lemma 9. The eigenvalues X4 and X_ from Lemma statisfy
x 2 1>
and
X E (-1,0).
Proof. Since s l2 àl and since 2 we obtain
(6-1)((21) 3)d s (L 2))
2 -(L 1)(L 2)3
2 - (L I) -2) 3 9
d
(L 1)(L - 2)
(2) 1 f(L).
3
2L-3
f(L) is increasing for 2 and achieves value that is > -0.6 for 7. Hence since L 2 7 get f(L) 2 -0.6 > -1. Therefore,
A (L ()2( sh-- 2)) (LL-))) + 3 1>0
Next, since E 1 Y) and since d 2 8 we obtain
()-))(2-))s-- s (L 1) 3 g
(L - 1) 2) 3 3 : g(L).
24-3
g(L) is decreasing and positive for L > 7 and achieves value that is < 0.6 for L = 7. Hence since 1, > we get (T.)) < 0.6 1. Additionally, note that
- - d s 1--1 153 3 gg - 3( 3 -3
Therefore, obtain that
x_ (L 1)(L 2)s 3 (d 1-1 - 1) E (-1,0)
which completes our proof.
39

---

In the first half of F.3.2 we characterized the critical point and established that it is the only critical point that is relevant in our case, since it is not global minimum and since we cannot exclude the possibility that gradient flow would converge to it. In what follows, we give a closed form solution to the dynamies obtained under the linear approximation around to true dynamics. We will show that under these linearized dynamics, any gradient flow trajectory not initialized in W1 will escape at an exponential rate.
Lemma 10. The linear approximation around s of the gradient flow dynamics (see Equation 22 is defined by
( -s)
( - -s).
The solution to the above linear differential equattion system is given by
(lm((1) = =Q (-1. Diag(Da - A....
X-) 1-))))))) Q- (0)m(()) +s,
where X4 and X- are the eigenvalues ((((s) found in Lemma & and Q is an orthogonal matrix whose first column is Val and the rest of its columns are an orthonormal basis of W2 (defined in Equation (16).
Proof. First note that the first order Taylor's expansion around of - -V((A) is given by
-V((s) V (A)()) -s).
Since s is a critical point of (i.e., V((s) = 0), we obtain the following linear approximation
A (f) (A()()))) -s.
Per Lemma 8 an eigendecomposition of (2((s) is given by the eigenvector 1 with the eigenvalue A4 and the eigenvectors (el ....... e₁ ea} with the eigenvalue A. Therefore, may write (²((s) as the orthogonal cigendecomposition
v ((s) Q
where the first column of Q is V 1, and the rest of its columns are an orthonormal basis of Span(e: e ei ea) W2. The proof is completed by invoking Lemma 27 which yields the following solution to the linear system:
A A lin (1) = Q Qexp (-1- , (...,,,......)) 07 (A (m -s) +s. +s.
The following corollary computes the solution of the linear approximation as function of the initialization's 's projections onto Wi and W/ (Equation (16):
Corollary 2. Denote the projection of A (0))(0) to Wi by 3,1 where 31 and the projection of (O) W2 by B2 W2 where Wa a unit vector B2 E R. Then for any ' 0 holds that
(t) (exp(-t- (op(-t-A4)(3.) 5) + 1+ 1 (expl-t- (exp(-t-A_)-Be) --)-tt-A))))) -2)v..
Proof. Plugging the projections of ln to W, and W/, we can write the following:
l (0) (8) - s)1 32v.
Hence per Lemma 27 at time 2 0 the solution Alim takes the following form:
f- Diag(A,, X_ h.... ........  (2) (1A) (8h-s]1- + 32V +s.
Ali (t) exp
40

---

Q is projection matrix to the respective eigenspaces of (2((s), hence since 1 E W/2 and v E W2 we obtain
A Alin (t) = exp(-tt .+))(3) - 5)) 1+ (xxp(-tt- 82) +
exp((- (+)(3) - 5) + (exp( ( --) B2)
as required.
Remark 2. Note that if $2 + 0 (i.e. the initialization A was not in Wi). then the solution to the system diverges from s. Since X_ < 0 < X+ we obtain
lim 1000
exp(-t (31 8) +
1.11-- =
and
lim
(exp(- -t (oxp(-t--)--B2--
- 00.
t0000
On the other hand, if 33 then the solution the system converges
F.3.3
Lincarization of Dynamical Systems
In F33. we characterized the critical point s E 1 and established that it is the only non global minimum that we could converge to given our initialization. We would now like to show that in fact gradient flow will escape s and converge rapidly towards a global minimum. Corollary gives some indication why this may be the case-it shows that the local linearization of the dynanics near will tend to repel any trajectory which is not the line Wi. Intuitively we are sufficiently close to s, the linearized dynamics provide a sufficiently good approximation to ensure that the same conclusion will hold for the nonlinear system as well. Unfortunately, existing results from the optimization literature (e.g. Jin al. (35) give escape times which do not suffice for our purposes [2] from dynamical systems theory. Informally, the idea is that if non linear dynamical system satisfies certain conditions on the spectrum of its linearization (these are sometimes called "non-resonance conditions"), then it is locally smoothly equivalent its linearization. This will allow to bound escape time of gradient flow terms of the closed form dynamics obtained for the linearization in Corollary 2
expects that once
To obtain the required bounds on the escape time we will require some results
We begin by defining the notions of smooth conjugation and smooth linearization of dynamical systems:
Definition 5. Let f.g : TRd + ddd be two C.M vector fields with a common fixed point xn E Rd i... f(xo) (xx)) O. For any K [M] say that f and g are C* -coconjuaate near xo when there exist neighborhoods V. C Rd such that Xo E V1,44 Ui and there exist C -diffeomorphism
I1 V + 14, satisfying the following:
. H(xo)= = X
Whenever x(I) E Vi is solution of x(t) f(((t) for t in some interval I C R then y(t (x(t)) is a solution of yt)) = -ty())) for E I.
Whenever (() E Uz is solution of y() (((()) for t in some interval I C R then x(1) -H-((((t) is solution of x(t== f(()=((x(()) for 1 E I.
The mapping H! is referred to as the C -conjugation between x(t) = f fx(()) and y = (t)))). Consider the first order Taylor's expansion of around xo given by
(t) fx((t) A(x(t) xx)) + F (x(t) xo)
Frecall that our strategy is to bound the divergence between trajectory and the reference one, and this divergence depends the convergence time achieved by gradient flow.
41

---

where A = Df(x)). F(0) = 0 and DF = Od,d is the d, zero matrix. The associated linear equation given by
y()) = A(y(t) - xo)
We say that admits C* -linearization near xo when it is C* -conjugate near with its linear approximation.
We now introduce the Striet Hyperbolicity property and the Non-resonance condition (also known as the Sternberg condition). These sufficient conditions for dynamical system admit smooth linearization and we will later show our system satisfies them.
Definition Let E Rdd be a matrix with eigenvalues A1,..., E R repeated with multiplicities. We that A is strictly hyperbolic when:
For all j E [d] it holds that >3 +
There exist J+.j- [d] such that X,+ > 0 and dラ_ O.
Definition Let Rddd be matrix with eigenvalues A1,...: ... Ad E repeated with multiplicities. For any 2o non-negative integers vector and any À E R we denote ((,, m) as the following quantity:
7(, m == A
my A
For any N N such that N 2 we say that A satisfies the non-resonance condition of order N when for all j E [d] and all m E N such that Ei= my E . it holds that y(>j: m) 7 O.
Finally, we present the property matrix Q-smoothness.
Definition 8. Let Rddd be matrix with eigenvalues Ai..... Ao E R repeated with multiplicities. Suppose A is strictly hyperbolic. Denote the following quantities:
max{/Ayl e [d] 0}
max
|d. 0]
P+
min : E [4,
p-
min j j [d),2, <
Let Q E N We define the Q-mmoothness of A to be the largest integer K E N for which there exist M, E Nso satisfying the following:
Q = M N.
. Kp+ 2
N Kp_ 2 0.
are now ready to present Theorem of 70 which states conditions under which there exists smooth linearization of dynamical system
Theorem 3 (Theorem 1 of [70] (adapted)). Let Q N such that Q 2 2. Let f Rdd - Bd be an analytic vector field with fixed point Xg. Consider the first order Taylor's 's expansion of around xo given by
x(t) f(x(t)) A(x(t) -xo) F Fx((t) xx) xx))
where A = Dx(x)), F(O)= = 0 and DF = O2.d- A is strictly hyperbolic (Definition 6 and
satisfies the non-resonance condition of order Q (Definition 7) then f admits a C.K linearization near X9 where K is the Q-smoothness of A (Definition)) 8
Proof. See proof of Theorem 1 in 77
Having introduced these general results on local lincarization, now show that the dynamical system induced by gradient flow admits smooth linearization near We begin by showing that -v)((s) is strictly hyperbolic and satisfies the non-resonance condition.
We present slightly adapted results that specialized to setting.
42

---

Proposition 8. Consider defined in Lemma 7 The hessian matrix (() is strictly hyperbolic and satisfies the nen-resonance condition of order d
Proof. Per Lemma 9 it holds that
2
and
- <0.
Hence by Definition 6 have that
V=((s) is strictly hyperbolic. Additionally, for any m {O....,, d 2} we
x + m A_ 2 - - m > 0.
Let m E No such that Ex= E , 2}. Per definition Definition we have that
7(4,, m) = (1 - -m)) A_
km
If my [0,1] then since A_ <0 < A and Σ my {l...., d 23 obtain
7(4,, m) - m&
0.
km
Otherwise, since El my E (0....,, d - 4) we obtain by the above that
7(4, S -x A m& S (d +
my 0.
Hence 7(A+, m) # 0. Next, per Definition
we have that
7(_ m)
m X_ mi A+.
k=2
m = 0 then since 1 Ek= my E (1-,.... -d + 3} we obtain
r(~,, m) = Σ mk h=2
d_ 0.
If my = d then 1 - Ed my = 1 and so
7(>,, m) = = (d 2)14 < 0.
Otherwise, since Ed 2k= mik 1 {O....,d 1-33 3) we obtain by the above that
d
d
7),, m) < - Σ m. - 1) < - (d 1) m -
Hence 7(A_, m) * 0. Therefore by Definition order d - 2.
((((s) satisfies the mon-resonance condition of
Next, we turn to lower bound the Q-smoothness of {2((s))
Proposition For any Q Noo, the Q-smoothness of (2)((s) is at least [
Proof. Per Lemma 9 we have the following:
max {
max {}_} =
P+ min (}+}
min [>
Therefore per Definition and since (2((s) is strictly hyperbolic, the --smoothness of - -V(((s) is the largest K Noo for which there exist M, N E Nso such that
43

---

Q M N.
M K 20
N -20
One can easily verify this implies that the Q-smoothness of [ is at least [
Finally, ready prove the following proposition which shows that dynamical system induced by gradient flow admits a linearization which at least C
Proposition 10. The dynamical system induced by gradient flow (see Equation linearization near 8 that is at least C
22 admits a
Proof. First note that the vector field - -V((A) which gradient flow follows is analytic. Next, per Propositions and 9 it holds that (s) is strictly hyperbolic, satisfies the non-resonance condition of order at least 2, and has Q-smoothness of at least [ { for any Q Nyo. Hence, by Theorem
the vector field V A) admits a _²² I --lineriization near s. The proof concludes by noting that 2 8 hence
2 3.
We denote the above linearization by H V1 - U1, where the neighborhoods V1,4 S Rd are such that V1, To the stage for the rest of the proof, prove the following proposition that considers a restriction of to a smaller domain that satisfies a few additional conditions which we will require later.
Proposition 11. There exists ri > 0 which satisfies the following:
1. ri 1 28
2. For any A E (s) it holds that
DAmin (Vi((A))| 2/2
3. H B. is Lipschitz and there exist r2 (0,r1) and r3 > O such that H-1 Lipschitz and it holds that
Brg (8) is
H H (s)] S Bry S H[ (s)).
Proof. We show there exist three non empty intervals of the form (0, b,] for i E [3]. such that E (0, by] then it satisfies the corresponding requirement above. This would imply that the minimal upper limit r1 = min (b,, b2, by) satisfies all requirements. The first condition trivial, with zz. Next, since Vε(A) is analytic it holds that V²((A) is symmetric for any A Rd. Since X_ O. by the continuity of the eigenvalues of (2((A) around s there exists b2 > such that the second requirement is satisfied for all (0, 62]_ Lastly, since H V - U4 is C and since VI, neighborhoods of s, we can invoke Lemma 28 which states that there exists by such that for any b E (0, by] the third and fourth requirements are satisfied.
E33.4 Movement Towards the Saddle
Having established key properties of the loss landscape, are ready to begin the dynamical analysis of the gradient flow trajectories over time. We first give a simple bound on the magnitude of the entries of A(t).
Lemma 11. Suppose we initialize at A(0) E Io and at Are/ (0), and evolve A(t) and Are (t)
according to Equation (22). For any Z 0 and any [d] it holds thut
A,(t), (t) E [-3,3].
44

---

Proof. First, we have shown in Lemma that by gradient flow have loss no larger than 1. Assume on the contrary that there exist and j E [d] for which
that the initialization Zo guarantees all points encountered
A,(t) $ [-3.3]
Since L - 1 is even, obtain that az(t)==1 2 3 > 3 and that any ls [d], # satisfies
ax(t)<-1 2 0. Hence, we obtain that
((A(t))
(1
Σ
ax(t) (()t))-122
Σ as (t))²
k=1
2
Σ
a (1)(
k=1
2 (3 1)2
1.
contradiction to Lemma 22 The proof is identical when we consider the reference trajectory.
The above yields the following useful corollary.
Corollary 3. There exists > such if we initialize at A()) E Io and at Aref (0), and evolve A(I) and Are (1) according to Equation (22 then for any 2 the functions -VE(A(I) and -VE(AreS (t)) are N-Lipschitz.
Proof. As shown Lemma 11 all points encountered by gradient flow are contained in the compact set 3, 3]d The claim thus follows from the fact that ((A) is analytic.
We continue to prove the following lemma which analyzes the trajectories when initializing in an interval of points on the line Wi (Equation (16)).
Lemma 12. Let a1, 02 E 2- 4] {s} such that 01 + a2. Suppose we initialize at A1 a1
and A2 02 1, and evolve A and A²(t) according Equation (22). It holds that:
There exist functions 01, 0g R20 + R such that
(t) (t 1, A²(t) az()) 1.
For any t 2 0 it holds that (2 < an (t) +
For any r > 0 there exists t 2 such that for any t 2 t1 it holds that At,t), E (s)...
and evolving A(t) according to the gradient flow dynamics, all entries evolve according to the same dynamics and therefore must stay equal throughout the optimization. Concretely, all entries obey the following dynamics:
Proof. When initializing at A(0)
a(t) = (L- -d -att----tt---)attt--- -1-d- d ((1--- d-dd())()) a(ti))
Hence, the first claim holds. Rewriting the above terms of Lemma we have
a(t) / (a(t)).
In Lemmas 6 and 7 we showed that the above expression is positive for a(t) E [- s) and equals zero at s. We now show that the above expression is negative for a(t) E (s, 4). Indeed, since d > 8
45

---

we have that
f (
= (L 1)(1
-
12)))) (1 - d. 17)
$ (L 1)
4
3--2-3
d
--1 1
4
1.-2
1,5 53
=ch(1)
$ 0.75 3
<0
where the second to last inequality stems from the fact that h(L) is decreasing for L 2 4, that (44) = 0.75, and that I. 2 7. Next, we also have for any a E (8, ÿ that
1 ( (a) = (L - 1)(22 - - 2h + (L -1)(L (oll-2aa'-3 2)aa-33 d
S -d+ - 1)(L - 2)a
4 م-ا
s --d+ (1-11) 1) 2)(
--d+ (L 1)(L 2)
4 6-3
1.54-3
3
(I)(
15 8
< <-d+ < <0,
where the second to last inequality stems from the fact that gL) is decreasing for 2 7, that 15 and that 2 7. Therefore, since - (s) = O and from monotonicity we obtain that - 1fff (a(t) is negative for a(t) (s, 41. We continue by noting that per Lemma 30 trajectories of the same system of ODEs with different initalizations must never meet, hence by continuity it must hold that 0z (t) < (1 (1) = 02 < for all / 2 O. Finally, since is critical point in the interval and since a1 (t), a2 (t) evolve monotonically (increase if initialized
g(7)
8.
and decrease otherwise), we get by Lemma 30 that aj (t) and a²(t) cannot reach s in any finite time. However, since is the unique critical point in the interval, a1 (t) and 0z (t) must converge to f. co. Hence, there exists
some time 2 0 such that for any 2 t the entries of both A (t) and A²(t) are within (s). O
We use A (t) and A (t) to denote the trajectories generated by initializing at 0 and - respectively and evolving according to Equation 22 Additionally, for any > O we use f (r) 2 0 to denote the minimal time which satisfies
(t(((rr) E B,)s).
Note this means that for (0 we have A
A (ti(r) = V/ 1+s.
We denote the following projections of the trajectory A(t) and the reference trajectory (rrf which will be used in the rest of the proof.
initialize A(0) Iy and Af (0), and evolve A(t) and Are (t) according to Equation (22) For any / 2 0, we denote the projections of A(I) and Are (1) to the subspace Wi using
Definition 9. Suppose
81(1) - 8 (1)
where (1)1), 8T (1) R. Additionally, denote the projections of A(I) and Are to the subspace W/ using
B2(1) v(t) g (t) vf
46

---

for any where (2 (t) E R and v(t), vref (t) E W2 are unit vectors. Per Equation (6 W1 and W2
are orthogonal and span R., hence we may write
A(I) - (t) 1 (()) / (t) = - (0)
Remark 3. Per Equation 16
Wi and W2 are orthogonal therefore since (8((())))((82()))))))))))
and (850) (1) 1) (Ba(t)re) vref (t)) = 0, we obtain
Dist (ist,, Wi) = [t. v(t)l22 112(t)]-
Dist(A (t), Wi) =11.55% (1) (rr(( =185--
and
Dist(A(t)) W2) = ||3/(t) 1112 = (d)3 Dist(A' (t), Wa) 11,) (t) 1112 (a))(((())
Before proving the main claim of this section, we introduce another condition on the initialization which we denote Zz.
Definition 10. Let r > O. We use (r( to denote the following subset of Zo:
A (((()))-A((t00)))
min r,
1 2 exp (-N N (1())),, Sa
Ia(r) = AETo:
6d
for N of Corollary 3 and for (t), AT))
(t) and (r()) of Lemma 12
We now ready to prove the main claim of this section, which states that under the above the initalization, both the original and reference trajectories must enter sufficiently small sphere around s and furthermore they arrive at points that are sufficiently faraway from Wi.
Proposition 12. Let (0,s). Suppose we initialize at A(O) ()) and at Aref (0), and evolve A(t) and Are (t) according to Equation (2) There exist constants D (r), D- (r) 0 such that:
A (t)(G) Bs(s).
(82(4(())) (L1(E)) (a- (_(r), D_(r)).
Proof. Consider the trajectories 2 (L) and A A-(1) introduced in Lemma 12 Per Lemma 12
time 2 O and any index E [d] we have
aj (t) (t) <s
We begin by showing that for A(0) E Iz(1), the distance between A (t)(( and A(ta is at
most 24 First note that per Lemma 12 A never leaves (,)s) 3--3,3] 3]d Thus per Corollary
both A (1) and A(I) always contained in compact domain where the vector field ((A) N-Lipschitz. Therefore, we can invoke Lemma 29 which results the following:
||A² (4))) 11 < (0) A(0)]l2 exp (N 11 ())
= ||A(0)) exp (N - fx(55)
S a d exp (N t1 ()))))
Per Definition 10 a satisfies
min
r 4
A (t)( -A (ti(E))
exp ( - N ts ())
a <
6d
47

---

Hence, we obtain that
A (til -A(()))
min
7t
A² (A
exp(- N (..11)))) d exp(N
b1()) exp(N.tt17))
6d
min
(ttt (A()))
41
6
T
24
Therefore, using the triangle inequality we obtain
|(((G)) < (3 s
+ (())
r r r
24 2
Hence, A(t2) E Bs)s). Next, by Remark we obtain that
32 32(t1 ())
= Dist (A(ti(5)),))
By Lemma 12 we have A (11 (5) Wi, hence
B2(11 G)) <
aa.d. exp (N-
Thus, denoting (r) d exp (N (t)) get the first part of the second claim. We now show
that Bi (L)()) (- 8). 8). Per Lemma 12 we get by definition of 4 that
A (ti (
=
2
and since ||A2 (ti(()) -A(t( و and < it must hold that 31
(t) < s. Since
A A((((2))
A2 -A(())))((((()))) 5
6
it must hold that
3i (/ (1((())))) a (1(())
where A-(4( a- ((1()))) 1. Note that by Lemma 12 we obtain
B ((( (+(())>-2 1
as a (t) is monotonically increasing. Therefore by Lemma 12 and by continuity, there must exist some point a - (1 such that if we initialize A²(0) a and evolve A*
according to the gradient flow dynamics, then it holds that
A (t (t)()))= - 81 ()
48

---

Per Lemma 12
(t) never leaves [-3, 3)2 where the vector field (V((A) is N-Lipschitz. Thus,
invoking Lemma 29
we obtain
Ba (1((()))
B2(11( ( ((((
A(((G))) A (11( (4((
2 1(0) - 10(0) exp (- N 4
As (0) E Wi, we can lower bound the right hand side by the distance between A(0) and Wi and obtain
B2 (e((((()) 2 Dist(A(0), w:) exp ( N t((
Next, observe that Sa S 1 since A(0) E Iz)
hence
E1 Sk
1
1
S1 d
d
2d
2d
Therefore,
(ist(A(),, wi)
a C4
>
a
CR
d
k=1
Σd kmml
Sk
Sk
d
k=1
Σx
k==
Sk
0
C1
d
2d
Hence, meet the second part of the second claim with D_ (r) defined as
(- = 2d exp ( N t1 () > 0.
Note that the proof for the reference case is identical.
We note the following remark which deals with the value of points in sufficiently small sphere around s.
Remark 4. Let μ > O. The objective é is continuous and ((s) there exists F(H) >> 0 such that any A (s) satisfies
((A) 51+ E(s).
We conclude this section by proving the following corollary, which states that when A(0) e Ig. set of additional properties are satisfied.
Corollary Let μ O. Consider F(P) == min(re, F(p)} for the respective ra and F(P) of Proposition 11 and Remark 4 Suppose we initialize at A(0) E Is(T) and at Aref (0), and evolve A(t) and A (t) according to Equation 22).. There exist constants D+ (p), D (p) > such that:
A(ti( Are/ (t1
7()) 1
)) B B (s).
49

---

Be(ti( (00 1. (ta( la D-(p), D+))
( - (1 ((())))
Proof. We consider the constants D-(u)= = D+ (f(n) and D_ (1) == D- D-((())) from Proposi-
tion
12
Per Proposition
12 and since A(0) E Iz( (1() ). we have that:
A(t1( ((اا )), Ares (t1 (+1(=112) )) B
Ba(ti( ((2)) / (tr( E [a D_(p), D+)A)..
As F(1) S r2, F()), immediately obtain that A(t1( F(u) )) AreS (t1 4
T(u) )) B.z
and
A(Li ((w)) )), Arel (1i F(u)
)) Bugi (s).
Finally, recall Remark which combined with the latter argument results
A((t F(()) 1) e (f (ti Fl()))
(1+ ((s)
as required.
F.3.5 Escape From the Saddle
In the previous section, we showed that the gradient flow trajectories must reach sufficiently small sphere around s. Our goal in this section is showing that not only do both trajectories escape it, but they also do it fast enough To begin this section, we prove the following three lemmas regarding the diffcomorphism itself under H.
from Proposition I0 The following lemma proves that W1 is mapped into
Lemma 13. Let A E (s) \ {s} and denote Ä:= H(A). If W1 then Ā W1.
Proof. Since A Wi there exists (s) such that
1. Per Proposition 11 and Lemma 7
it holds that 72 < 71 I 2d and [] 8). Thus we obtain that [0, 2) Assume the contrary that À & W. On the one hand, if we initialize at A(0) = 1 and evolve A(I) according to Equation 22). then per Lemma 12 A(1) E (s) for all / 2 0, and furthermore lim4-100 A(t) S. By continuity H (AAt)) converges to well. On the other hand, if we initialize at A(0) = Á and evolve A()) according to the linear approximation around of the gradient flow dynamics (see Lemma 10). then per Remark 2 the solution Á(I) diverges away from s (since the projection of Á to W2 is not zero). This contradicts our assumption that H is conjugation (see Definition 55).
The following lemma proves the existence of two points W1 that are mapped by И to "opposite sides" of s.
Lemma 14. There exists a1, a2 E [s
2/..5 s 2/a {s} such that there exist ã E [s ra 8)
and ă2 E (s, s + for which either
H(a 1)= 0g H(az 1) = ū2
or
H(1 1) = U2 H(02 1) = āj
"recal that the divergence between the two trajectories depends the convergence time achieved by gradient flow.
50

---

Proof. Consider - 12 and = =+ 4v4 Both 01 1 and d2 1 are within W1 n Br (s) and
4vd
so by Proposition 11 and Lemma 13 it holds that (a1 -1, (az 1) E W1 n (s). Thus we can denote (a 1) di and (a2
02 1 for some 01, d2 E [s V.. 8+ Jil 0i d2 distinct and different than & since d1 02 & s are distinct and since is a homeomorphism with ((s) = S. Assume WLOG that
02 (otherwise flip the indices). Assume on the contrary that 01, 02 (the case where á1, 02 < is symmetric). Per Remark 2 we initialize at A()) ã2 1 and evolve Á(t) according to the linear approximation around s of the gradient flow dynamics, then our trajectory
(which converges to s) must reach ăi 1 after some finite time 22, i.e.we obtain A(t2) = ã1 1. Thus obtain that
N H (A(t2)) = 1- 1) = H ( 1)) = a1 -1.1.
Hence, per Proposition 10 if we initialize A(()) 02 and evolve At) according to the gradient flow dynamics, we would get that
A(tz) - 01 1.
The proof concludes by noting that the above contradiction Lemma 12
The following lemma proves that W is mapped into itself under H Lemma 15. Let À E Bry \ {s} and denote A == H ( E then A E W1.
Proof. Since A W1 n (s) there exists ā Assume WLOG that ā E [s r3, s) (the opposite case is symmetric). Per Lemma 14 there exists a' E 2/d 2vd {s} such that there exists ă' E [s V 8) for which
r3, 8
r3] {s} such that A
H(d 1) 7' 1.
Assume that ā < ब' By Lemma 10 if we initialize A(0) Á and evolve Á(t) according to the linear approximation around s of the gradient flow dynamics, then our trajectory (which converges to 8) must reach ă' after some finite time t2, i.e.
we we obtain A(t2) = 7' 1. Thus we obtain that
H (A(tz)) = 11 (a' 1) 11 11 (H 1)) = . 1.
Hence, per Proposition if if we initialize at A(0) A= (A) and evolve At) according the gradient flow dynamics, we would get that
A(t2) = H H (A(t))==o' = a
Invoking Lemma 2 we conclude that A E W/. Assume that ā > σ'. By Lemma 10 at (0) = Ā' and evolve Á'(1) according to the linear approximation around s of the gradient flow dynamics, then trajectory (which converges s) must reach ă after some finite time 12, i.e. obtain At(tz)
we initialize
1 Á. On the one hand, note that H-11(1) (A) A. On the other hand, if initialize at (0) = a' 1 and evolve A1( according to the gradient flow dynamics (defined in Equation 21 get by Proposition 10 that A'(t2) H-1 (A'(tz)) Thus, A'(tz) A. The proof concludes by invoking Lemma 12 which states that A'(t) E W; for any t 2 0.
The following two lemmas give bounds on the original dynamics in terms of the linearized ones. Lemma 16. Let A E (s) (s). It holds that
Dis((A, Wi) S T. (ist(H(A)) W.)
where G is the Lipschitz coefficient of H "l.g(s))
Proof. First that per Proposition 11 Brg is indeed Lipschitz. Let Ō be its Lipschitz coefficient. Next, by definition of the Dist measure (Equation (15) we have that
Dist (()) W.) = min (H(A) - Āll2-
Aew;
51

---

Since A E (s), it holds by Proposition 11 that ((A) (sy(s). Thus, since (s) is a ball it must hold that
min AeW,
[H(A)) All2 min AewinB,,
[H(A) - Al12-
As H is onto (s), by Proposition
11 there exists A' E Br, (s) such that
((A)) E argmin
[H(AA) - All2.
AeWinBry
Hence by the Lipschitz property of of H obtain
(eWin (A
min
1|2 = (A) H(A))l2
H- (H(A)) --
=
G
|| 221
Since A' = (A) for some À Wi n Brg (s), it holds by Lemma 15 that A' W1. Thus,
द - A'lla
1
min A'W
|| A
Dist(A,
G
Combining the above inequalities and multiplying by G we obtain overall that
G (A), wi) 2 IA A' 2 Dist(A A, Wi)
as required.
Lemma 17. Let A E B,, (s). holds that
Dist (Hs, S Di,ss(AA,,)))
where G is the Lipschitz coefficient of H B.)
Proof. First note that per Proposition 11 (.) is indeed Lipschitz. Let G be its Lipschitz
coefficient. Next, by definition of the Dist measure we have that
Dist(A A, Wi)
min d'EW,
|| A'112
Since A Br, (s) and Br, (s) is ball, must hold that
min A'EW;
||
A'lla
min (e.,inB,
||4 - A'
By the Lipschitz property of H we obtain
min
||A - A'l 2
A'EWinB,, (8) G ((A) - H( 2 (A), Wi).
min
A' A'EWI B., (8)
where the last inequality follows from Lemmal Multiplying by G gives the result.
Before proving the main claims of this section, we introduce another condition on the initialization which we denote Zz.
Definition 11. Let p > We denote G' max (1, G) for G and G from Lemmas 16 We use I4 (p) to denote the following subset of In:
T3
I((p) = A E Io:
4 max exp( 2X_)) G2VdD
for r3, A_ and D+ from Proposition II Lemma and Corollary 4 respectively.
52

---

In the next two propositions, we bound the time it takes to escape the sphere around s under the linearized dynamics, and prove an additional claim that will be utilized later show that the trajectory never returns to a certain sphere around s.
We introduce notation which will be used in both propositions; Let μ > 0. Suppose we initialize at A(0) Iz(" (T())) [i) (for F of Corollary and A (0), and evolve A(t) and (
according Equation 22). Suppose we initialize A(0) H A ( (اا and Aref(0)
H Are (t1( ((())) (for & of Lemma 12). and evolve A(t) and (r=f(t) according the linearized
dynamics (see Lemma 10 For any time 2 denote the representations of A(t) and Aref (t) with the orthogonal subspaces W1 and W2 to be
Ā(L) (() 1+ 12(1) v(()
and
-) - (1) 1+ B gre (1) (1r
where v(1), (1) E W2 are unit vectors.
The following proposition give quantitative bounds on the rate of exponential escape from s of trajectories under the lineaarized dynamics.
Proposition 13. There exist times tz(w), f2e (n) 2 for which it holds
Po(ta(wo) 32 ( (te(m)) 2vd
ra
For G' = max(1, G.G} it holds that
t2(1), ge (n)
(n) E { In (dGrVda
13
X In
G
)
2VdaD
For any [0,t holds that A(t) E Bry
B (s).
For any t E [0, f (4]] it holds that Are (t) (s)
Proof.
We prove the argument for À (the proof is identical for Aref). Recall Corollary which states
that
Dist A(4 F(u) )), mi
((2) )) E - (w), a D+ (m)).
32(11( 4
Thus, applying Lemmas T6 and 17 we obtain
a D_ (4)
< Dist (Ā(0), wi) = (3)(0)) < G. (4)))..
G
Per Lemma 10 for any t 2 0 the solution at time to the linear dynamics initialized at Á(() is given by
eepp Exp(-t.oo (xp(-t.A+))3.000 (3 -) + +0) (exp(-t-AA) (esp(=ttA.)-B((0)))00)
As noted in Remark the coefficient (1) tends zero as grows, while the coefficient
[t)) tends to grows. We first bound the time tz(n) for which (5(2(()) 2/a Since
(0) E (n)), it holds that
I's 4G /do (m)
max(2, exp((22_))) S
53

---

Therefore since A_ 0 (by Lemma 9
we obtain the following positive time t_:
t (c)
r3
- In (exx((exx22_)) = 2.
Thus, time the solution the linear dynamics satisfies the following:
(ist(A(()), Wi) = [32(1-)1
[32(0)] exp( -ttpptt--11 -2)
- G. D+(1) a -t-
-
A In
F3
= = (G-+(H)) exp
x
d (1)
G. CDD+(u) .3
T3
4G'
T3
4vd
where the last two inequalities stem from the fact that G² 2 G, 1. Hence, t_ is a lower bound on tz()). On the other hand, note that
G 12.r3
2v 2vdaD_(p) 4G /doD
and so since x_ < O we obtain the following positive time 14:
G r3
13
4 X_ In (VVdDD
X_ In 4G Vdo (p)
L.
Thus, at time 4 the solution to the linear dynamics statisfies the following:
[3((+)]= = |32(0) exp(- -t4 A_)
2 a: (n) cexp(-ta X_)
G
a. (_(m)
(>_ (>-
G²2.ra r3
In 2V
T exp
G
a D-(H)
G
G
2vdaD-((1
rr
2dd
T3
2/d
where the last two inequalities stem from the fact that G' 2 G, Hence, 44 is an upper bound on te()). Next, we show that (t-(t=) - s| S 2 This will allow us to claim by monotonicity that ((t)(u)) Bry(s), since then we'll have the following:
A(t2 -9 2
3 (ta(())))
(1((2()))) -s)
+
2
vd+
F3
11
2dd
2vd
< r3
54

---

Since A(O) E (s) it holds that (3i(0) a| S 3 Hence, since A= x_ < -1 (by Lemma 9 it holds that
[3i(t_) s|= /|=/|xp(->; - (B) 5) +
< (3)1 s (exp(-An 1-)
1 T3
r3
Vd
4G /dDD)d (1)
F3
2vd
where the last inequality stems from the fact that 2 < /d (x) Finally, since under the linear
dynamics [32( monotonically grows and [3i(t) monotonically tends to s, it must hold that for any t t [0, [p)) we have A(t) E (s).
The next proposition shows that (2(() must be larger than some constant throughout time interval of length before (2()). Proposition 14. For any E [0, 1] it holds that
(12 = 8 10 (12(m) (12())))))))
2 -7) (1)(m)-+) 2Vd
T3 exp(X_
Proof. We prove the argument for À (the proof is identical for Aref). In Proposition 13 've established that (2())) 2 2. Thus, per Lemma 10 for any 7 E [0, 1] the solution at the positive time (2( 2 1 to the linear dynamics initialized at A(0) is given by
exp ( (t2(()) 7) x+) (1)00) s) + 1+ exp ( (t2(m) -T) 2-) (2)
+
Hence, since (2((1N)) =
ry 2v7
we obtain that
(t2(1)) 7) = exp (+(((()) - -7) -))- 32()
exp ( (-))( -2.) -3(0)) -xp(A_ -T)
= (a(t(H)) -exp(A_.))
r3 exp(A_
2/d
The above established that there cxists time which is OIn ((nn where at least one of the lincarized trajectories is at a constant distant from Wi. We complete this section by proving the following corollary, which states that the corresponding non linear dynamics trajectory must also be at constant distance from Wi during time interval of length 1. This will eventually allow us claim that the trajectory must remain trapped within a set where the objective & satistfies satisfies the PL. condition (see Definition] 13). which in turn ensures rapid convergence to global minimum (discussed in the next section).
Corollary 5. Let μ > O. Suppose we initialize at A(0) E Ia( F(()) at Are (0), and evolve A(t) and A (t) according to Equation 22).
I (p) (for F of Corollary 4) and For any J E [0, 1] it holds that
Br (t1 F(()) ) + (2() - -7) DDist A(t1 F(y))
+ t²( - () m) m)
F3 (x
2G vd
and
35e (ti( F(()
+ rel (u) - - = Dist
Are (t1( F(R)
(t((((1))
+ 1 (w) - -T), m)),
33 exp(A_)
4
2G vd
55

---

Proof. We prove the argument for A (the proof is identical for A In Proposition 14 we have shown that for any E [0,1] it holds that A(t2(u) -T) (s), and so the mapping H is conjugation to the original dynamics. Therefore since we' ve initialized A(0) H (A(t(("))) it
must hold that for any E [0, 1]
1-1 (((t(())))) -1) A(ti( F(u) + (T).
Since H Brr) C B, we obtain that A(t A(42(244)) + (2(11) obtain
-T) Br and thus by Lemma 17 we
Dist ((tz)()==),n))
Dist A(ti( F(u)) t2(()) (1(
4
G
Note that by orthgonoality
32(t2(m) - 7) = Dist -t),
-)) w/
hence plugging Proposi-
tion 14 we receive
(1((((4) -T)
Dist A(t1 F(() + t2(m) - -T), wi)
r3 exp(A_ .T)
T3 exp(A_)
2G Vd 2
G
2G vdl
where the last inequality is due to x_ < O. The proof is complete by observing that
Dist A(ti( F(1)) +z(()) 7), v.. s2(t1( F(1))
+ t2(m) - 7)
4
4
F.3.6 Convergence to a Global Minimum
We begin this section by proving the following corollary regarding the difference between different coordinates of the points reached by the gradient flow trajectories. We will later show that this ensures the objective satisfies the PL condition (Definition 13).
Corollary 6. Let p. > O. Suppose we initialize at A(O) E Iz( F(u) and at (r)) and evolve A(t) and Are (1) according to Equation that there exist i, j,e, , E [d] such that
I((H) (for 7 of Corollary
4-)
22
For any E [0, 1] it holds
ass (1
+ 12(11) - -)) -7) F(1) F(2) 4
+ 12(1)
-7)
exp(A-)
4
2G .d..
and
7(11)
F(H) res (N) - -7)
Fa exp()_)
doves (ti(
+ 12
rot (p) - (p) a res (t1(
-)
+ t2
4
2G d1..
Proof. The claim follows from invoking Lemma 31 and plugging the lower bound on |13]| and /oge
provided in Corollary 5
We continue by proving that E satisfies the PI. condition (Definition 13 the subset of points Di (Equation (18)):
Lemma 18. Let b O. The function (lpuro))n(-3.31- satisfies the PL. condition with PL coefficient
1 min 2d, ((L (1)))
# 2
4
b
2
for b = (b) and 2-2
56

---

Proof. Let A E Di n n1-3.3 Recalling the definition of Dif (Equation (18) there exist
i E [d] such that |a: -0-- a,l 2 b. Since a, o aj. at least one is non-zero. Assume WLOG that
aj + 0. Hence, since 0 < - 2 E Nodd we get per proposition 20 that
|a 2
ag 2 1 (2) g =:
and
1--2
a;
1.-2 2
(6) =:b.
(
0j
Denote res, := 1- Ei=n aş and rest == 1 - Σ
-,-1 If res, 0, then it holds that
k=1 Ox
[E([A)]> = EL- - (a
(i-t-1)) 3 = (*).
k=1
By the triangle inequality, either la 2a,-211 2
2 or la 1--2
91 2
In either case,
2.
B2 res) ((L-1)b) (+) 24 1)-
2 =ress)) ((L-1)6 ((A).
2
Tres
+
4
4
((4-1)6))
Lee. the PL condition satisfied with μ
res: = 0, then holds that
d Σ rest = dres² = 2d( G + 2 rrss?) = (d))
1
|((Aa)>
k=1
L.c. the PL condition satisfied with μ = 1/2 2d. Assume rest, res + and denote X = (L-1)res:
Pees +
0. For any 1: E [d] we have
v((A), = (L 1)ak Pres, + ress = (L - (1-1)ak 1) - (L - 1)res: x= = (1 -1(aa))(at- -- x)res
or equivalently
v((A), = =( -L--1)0f 4-2 "res + res, --(a-))a
1)a 2-2 res,
+ res, = (1 - ag res,
(L- 11x
Squaring the above identities we obtain
L-2
VE(A)} = (L - - = (1
Fress
By the triangle inequality we have that either
b
1a/--2
x/
2
or
b
lay xl
Therefore, if res? res? get that
[VE(A)) = Σ (L. (1)=1) () 1.2 - res?
k=1
((I. -1))) rest
(LL 1)8)
1
Tes
+ res?)
4
2
((L 1)8)
2
{(A).
4
57

---

Lee the PL condition is satisfied with == ((L-1)6)² proposition 21 either
On the other hand if res? ress. then by
L-2
b
[1
2
X
b
+
2
1--
b
11
j
2
X
b
+
and therefore
2-2
) 1 (Grrss + 2 =
1
[V((A))12
Σ
ress 2 2
res
((A)
6 6 2
b
6+2
b 2
i.e. the PL condition is satisfied with μ = _ 8 ) Overall, we get that whenever Diff(b)
6+2
[-3,3]4 3| the PL condition is satisfied with μ min
2d, ((L-1)8)
(Bt2 )2) as required.
The above results in the following corollary regarding the PL condition satisfied by E at certain set of points reached by the gradient flow trajectories.
Corollary 7. Let p > O. Suppose we initialize at A(0) E Is( ((m) n Iz(H) (for r of Corollary 4
and at Af (0), and evolve A(t) and A (t) according to Equation 22 For any [0, 1] it holds that & satisfies the PL. condition (Definition) [3) at the points
A(l F(u)
+ 12(1) -)
and
Aref (41( F(1) + 15es (11) -7)
with PL coefficient
((L- - 1)6)
((L
A1 min 2d,
)2
4
b+2
for
T3 exp(1_)
L-2
r3 (exp(__)
L-2
6
b:=
4G d(1.5
12G df1.5
Proof. The claim follows from invoking Lemma 18 and plugging the bound on the coordinate difference provided in Corollary 6
For the rest of the proof, we let f = μi from Corollary 7 We are now ready to prove the following proposition, which states that at time t ((u)) (2(11), the trajectory is at point whose value
improves upon the value of é by constant:
Proposition 15. Consider pr from Corollary 7 Suppose we initialize at A(0) Is( (((a)) n Ia (p1)
(for 7 of Corollary 4 and at Aref (0), and evolve A(t) and Arof (t) according to Equation 22 holds that
((s) - a(A(t(( F(11)) + t2(11)) min
((s))
3p1 {(s)
4
2
4
and
((s) - e( Ares AAArre/ (ti(
((((Fe))))))
F(1z))
(((s)
3p1 {(S)
+ see
(11))
min
4
2
4
58

---

Proof. We prove the argument for A (the proof is identical for A First, suppose that [((ti( ) + t2((1))
die 2
Then it holds that
{(s) (A(tii Flmnd
+ t2(wi)) ((s)
((s)
{(s)
min [(s) 3/1 {(s)
4
2
4
Next, suppose that & AALi( ((يي)) + la(ui)))
Thus per Lemma
22 for any T E [0, 1] it
holds that
1 A((ei F(mm)) + (2(11)) - -1)= (A(((( (la)) 4 ta(1)))
{(s) 2
Next, per Corollary for for any r E [0,1] I] it also holds that satisfies the PL. condition the point A(t1( F(m)) 1 + (21) 7) with PL coefficient M11 Thus, by Lemma 32 it holds that the difference
=e((m)) F(m1), + t2(m1) - -1) - A(ti( F(R1), + te((1)))
((0)))(((())
e A((t(( 4
4
lower bound by
2(t1( F(u1) + tz(m1) - ti F(H1) t2(x1) + +1) +1)-PM P1
((s)
= μt ((s).
4
4
2
On the other hand, recall that by Corollary 4 and since gradient flow is non-increasing we have that
e( A((ta( F(un) + t2(1)) - 11)) e (A(ti( (((n)) s (1+ P1 )((s).
4
4
Thus, we obtain the following:
(1+ + M1 (((s) - e (A(t1(
(l(t)) Flrn), + ta(lz))) 2 p1 ..n-ef e((s)
4
4
Reorganizing thus yields
{(s) - (A(11( Flma),
(A(s(((ue))
+ ba(ri)))
3/1 {(s)
4
4
as required.
We continue to prove the following proposition, which states that after time 4 fluz)) ) + (24)) the 4
points reached by the gradient flow trajectory ones where & satisfies the PI. condition with certain PL coefficient.
Proposition 16. Consider pr from Corollary 7 Suppose we initialize at A(0) Is( ((Hs)) n I (pr)
(for 7 of Corollary 4) and at Aref (0), and evolve A(t) and Are (f) according to Equation 22 There exists > 0 such that for any time t it holds that:
lft 2 t1( (Fluz)) + t2((1) then A(t) E Di
lft 2 t1( (Lun)) + (re(()))) (mn) then Are E S.
Additionally, it holds that satistfies the PL condition at Di with coefficient μ22 for
((L ((L- - 1)0) 2
D
P2 min
2d,
1
where
5 ū: 1y - = 1
59

---

Proof. We prove the argument for A (the proof is identical for A Let t ti (a + (M1).
Denote for any & 2 0 the function
f(v)
min ((4)
A)Dim+nn(-3a 3,3/"
for ()) defined in Equation 17 Per Lemma and since [-3, d holds that
{())
min AEW;
((A)
min
min L ((A) f(0). ((A) AEDI
L
Invoking Lemma 33 it holds that f is right side continuous in O. Hence by continuity, we obtain that there exists such that for any v E [0, it holds that
1
{(s) 3/1 {(s)
f(() 2 f(0) min
2
2
4
((s)
3p1 {(s)
= {(s) min
2
4
{(S)
3/1 {(s)
> ((s) min
2 4
On the other hand, per Proposition 13 and since the objective is non-increasing under gradient flow (see Lemma 22 we obtain the following:
{(s) - (A(+)) ((s) - [A(1(( F(mz), te(mi))) 2 min
(((s)
3/1 {(s)
2
4
Rearranging we thus obtain
{(s) 2
3/1 {(s) ((Att))
f()) ((s)
min
Note that per Lemma 33 f is non increasing w.r.t eh thus it must hold that A(t) & Diff( (since is
in [-3, 3) As this holds for any eb E [0, we obtain that A(t) Dif Hence, the argument follows from Lemma [8
The final proposition of this section proves that the gradient flow trajectory converges global minimum Ag.
7 Suppose we initialize at A(0) Iz( (((l)))) n I (p1) (for of Corollary 4 and evolve A(t) according to Equation (22). There exists Ag IRd such that
Proposition 17. Consider ii from Corollary
lim A(L) A² and ((A2) =
Proof. Per Corollary 7 there exists 0 such that for any 2 4i (((u))) + 12(11) ) it holds that A(t) Di where & satisfies the PL condition with coefficient #4 (defined in Corollary Next, note that per Lemma 11 and Corollary 3 A(t) is always contained in [-3, 3]4, where f's gradient is
N Lipschitz. Therefore, the claim follows from Lemma
F.3.7 Overall Divergence From Reference Trajecory
In this section we show that one can choose a set of initializations such that the divergence between As and some point on the reference trajectory is arbitrarily small. This shows that A₂ must not recover the teacher (per Lemma We begin by proving the following lemma which gives explicit times at which the gradient flow trajectories reach points of arbitrary small value.
Lemma 19. Let 1/2 E (0, Consider in from Corollary Suppose we initialize at A(O) Is( ((m))) n Ia(Uz) (for F of Corollary 4 and evolve A(t) according to Equation Denote
(5()) = min (2(m1), ges (vi) (oe)))
Denote the time (z 2 to be
tz(m2) = In(1z)
G.
)
r'3 4G (p1)
22 (pi)) )
2 x_
=
60

---

It holds that
e (A(ti( ((uu) (21)) + ts((2))) m
Proof. First, note that since X_ < 0 < G² and D-(w)) < D+(1i) (wI) we obtain that
ts(12) = 11(112)
D-(11)
In(11)
In
2p12 x_
22"AAD+
2/12
The right term is positive as 0 < 1/2 < 1 and μ2 > 0. Next per Proposition 13 it holds that
G. 2VdaD_
( 73
(2((1)) 12 12 (11)1
In
+ X
In
X_
4dm
1 In
D-(m1)
x_
which results in
ti F(m1) + +((()) + ta(22) 2 ti(
F(u1), ((((())))
In(n2)
t2(p))
2/12
Hence, per Lemma 22 obtain that
( (A(ta( F(m))
15(m)) (s((2))) < A(A = F(mi)) + (2(11)
In(12)
2/12
Per Proposition 16 there exists 0 such that for any t t1 (F(اn))) + t2 (2()1) it holds that
A(t) Diff C where satisfies the PL condition with coefficient μ22 (defined Corollary 7p. Thus, per Lemma 24 it holds that
{ A((
F(pz), + t2(11) 4
In(nz))
- (
( A(ti( F(mn),
((ti( + te(pi)) exp(2p2
In(12), 2p2
2p12
S ((A(0)) 172
where the second to last inequality stems from Lemma initialization l's value is no more than 1.
The proof follows by noting that at
We continue to the following lemma which proves that there exist times at which the distance between the gradient flow trajectory and Ag (defined in Proposition 17 is arbitrarily small.
Lemma 20 (Distance between gradient flow trajectory and A2). Let (0, 1). Consider pr from
Corollary 7 Suppose we initialize at A(0) E Is( F(ma) (p1) min(tt(un),)) Ete/ (pi)}. (pr)), Then there exists 12.55 such that
4 n (1() (for i of Corollary 4 Denote
A2 A(ti( F(11) ((th(( ((m) + ta(22s)) 58.
4
Proof. Denote A A Rd. ((A) - =0}. Per Corollary there exists μ2 such that for any
t 2 t1( 4 + to (2z) it holds that satisfies the PL condition in A(t) with PL coefficient μzz Next, note that per Lemma I1 and Corollary] 3 holds that l's gradient is Lipschitz in A()). Therefore by Lemma 25 for any / 2 it holds that
((((H))))
Ag - A(ti( F(11), + t2(p1) +
N Dist A(ti( F(p1) + t2(p1) + +).
<
4
u2
4
Additionally, note that since é is continuous and non-negative, when considering its restriction [-3, 3| we obtain that its sub-level set is compact. Therefore obtain by Lemma 35 that there
61

---

exists 72.6 (0, 1) such that for any A 1-3,3 if ((A) S 72,5 then Dist(A,,A)) S V 16.6 It was
shown in Lemma that
41 F(u1)
+ +2((1) + (2(122)) 2 41( F(mz)) + (2(111)
and so we obtain that
A2 - A(ti( F(u)); + (z(1) ts(122s)
4
N
A((1( ((((((i))) + (2(mn) (s(12.)))
Dist
V u2
It was also shown that
e( (A((1( Flui),
+ (5(11) + ta(126))) - 72,6
4
and so we obtain
Ao A(ti( (((m2))))) + ((r t2(m))))
N p2 8 8. U2 N
S
as required.
Before proving the last proposition of this section, we introduce another condition on the initialization which we denote Iz. Definition 12. Let 8, > We use [o( n) to denote the following subset of Iy:
Is(6, = AE Io : (1 (2)
G/2ra 2vaD_(m) (mi)
exp N (f1 ((u2) ta(ni)
for r3, D_, Gi and μr from Proposition
Corollaries
and and Definition 11 respectively.
We proceed to proving the following proposition which upper bounds the divergence between A(I) and (t)
Proposition 18. Let 8 Consider μn from Corollary 7 Suppose we initialize at A(0)
Ia( M n Ie(Mn) n Is( 72.6) (for 12,6 of Lemma 20 and at Aref and evolve A(l) and
( (mi)) }. It holds that Are (t) according to Equation 22 Denote (5()) == min t2(11), get
A(ti( F(11)) + (5()) (2(122))) Are (41 F(11) + (5m) + talmm))) - 8
4
for 12.5 described in Lemma 20
Proof. Per Lemma 11 and Corollary for any 1. 2 0 it holds that A(L), Are are contained in [-3, 3jd, where f's gradient is N Lipschitz. Thus per Lemma 29 it holds that
A(ta( F(mn) (p1) + ta(m2.)) - Are (ti(
((n))
+ (H()) + ta(mes))
4
4
< A(11 F(u1) ) + (01))) rr (11 F(m1) ) (2(11))
exp (N ta (12.)))).
Next, since tz(m) < t2(m1), ) 2 (Mt) we obtain by Proposition
13 that for any e
[t1( F(ra)), ), t1 ( (Fla)) ) +(((1)] it holds that
(((tt), (Are (s).
62

---

Invoking Proposition 11 the above results in
A(t), Are) (t) E B,)
By definitions of rı and Br, (Proposition the above yields the following for any in the interval [41 F((x)) ), 11 4 (2)) and & E [0,
Amin
(2e(k- A(t) + (1 (1-k) k) A Are)(t)
- 2/A-1.
Next, it holds that Amin (V2((A)) = -mxx - <2((A)) for any A E TR.. Therefore, invoking
Lemma 34 and plugging the above we obtain that
A A(1(( f((1) (((m)))-Are1 (11(
F(ui) + (2(x1))
4
4
< <exp (1
2/A_107) A((1(( F(ri))
)) Arees (11( F((1)
4
exp(22 [
Flmn) )) Ares
- (ta F(u1)
Note that A_ and so 1^-1= ->_ Thus, recalling Proposition obtain that
13 we upper bound (11) and
A(t11 F(11) -At (82 F(11)) ) +5((n))) ||
-A
22 ((2z) (2-1) A F((n) 1) Arof (b2( F(um)
C²2r3
sexp
-
G
2
A(ti( 7(11))
Ar (ti( (((1))
2V
Applying Lemma 29 once more, we obtain that
A F(un) ) Aro (4 F(m1) ))
< [[A(0) - (r)(( . exp (N 41 F(un)) 4
))-
Finally, by Equation 23 and Definition we have at initalization that
||A(0)) A (0)ll2 (az(0) (00(((0) (2)
Altogether we obtain the following bound on the divergence:
F(11)
(rres(t)) (ta( F(111) + (21) + ts(126))
A(ti( +t(1))) + t2(112))) -Are/
4
4
G
2 N (41 (lwn) + l2((2.6)))
Sa (1- (2) 2VdaD
exp
The proof concludes by recalling that the initialization satisfies A(0) E Is Is 72.6) and so since 0 we can rewrite and obtain that
a (1)
2
Ga 3VdaD-(())
exp N (((2)) + ls(v2.)))
and so
G²2T3
2
exp N . (ti( F(1e))
a c-(1-6b)
+ to (m (mm22))))
2vdaD_
4
2
63

---

We finish this section by proving the following corollary bounding the distance between Ag (the point to which the gradient flow trajecory converges to) and Aref (t1 (flm)) + (2( (3((2266) point which by Lemma is far away from the teacher.
Corollary 8. Let 8 > O. Consider μi from Corollary
Suppose we initialize at A(0) E Ia (ims (a(M))nia ( 72,5) (for 72,5 of Lemma 20 and at A (0), and evolve A(t) and A (t) according
Equation (22). Denote (11) min t2(11), 12 (11) ). It holds that
12 - Ares (tal F(un)) + (5(m)) + to ts(n2))) S
4
where A(t) converges to A2 (see Proposition 17
Proof. Per Lemma 20 holds that
A2 A(L F(mi)) + (5(m)) (s(22)))
8
Per Proposition 18 it holds that
[|A(tz (((((((())))
F((n)
4 + (p1)) (s(,2))) Are (ta ((((F(1))) ((((1) ts(126)) - 6
The claim thus follows from the triangle inequality.
Let (22) be the initialization subset defined above, i.e.
I2(02) :- Iz( F((1) n (1() n IIss ( 92.62)
82
for 02 of Lemma 3 Invoking the lemma we obtain that for any L," 2 L, + 2 it holds that
1 { 1/9d)) (1- (0-60.6))((411))
Gen (A2)
min
2
which concludes proof of the fact that gradient flow under Sn converges to non-generalizing solution when initialized at (8).
E4 Initialization Subsets Intersect
In Proposition we showed that when initializing at Ii (e) gradient flow converges to point Ai which satisfies Gen,: y (Ai) I In Corollary we showed that when initializing at Iz (62) gradient flow converges to a point A2 which satisfies Genz (A2) 2 2 min 0.1,1/(9d) (1 (0.6))/(L-11)
In this section we show that not only do the initialization subsets (e) and I2(62) intersect but also that their intersection contains an open subset. For convenience of the reader, we rewrite the full requirements as they appear in the statements of Appendices F. to F3 and state their respective arguments. The base initialization set (Equation (23 we consider is
Io = {a (G...... Ta) E Rd a (0,
C1 > > <>>...>>u>>0f SO20
2d
[e( (Definition 3 was defined as
Iı(e) { A E Io :o (2, (2..... d].
m1 4-11 11111
+
)
for 17,6, of Remark
Is( Flun)
(Definition 10 was defined
(( 4
A (t, f(uil )) -A A (t, ((ai))
min
F(11),
4
-N (3يم
1
Isl
A Io:
Sa S
4
6d
64

---

for 7(-) and μl of Corollaries and respectively. I1(11 (Definition
was defined as
{
I((1))= A : Am:
13
max (x G2 (avaa)(())
[6 (2.82) (Definition 12 was defined as
82
Is (ō2, 122622)
A Eo:::
2VdD-(Hs)
G
exp
N
(ta( + to (12.62)))
for 72,62 of Lemma 20
We begin by observing the following simplication:
= = Ion {
AEIo: <
1 -- (1-(1- (1,6,))
11,61
(1- (1-
d
since the right hand side is monotonically decreasing in Ç and since C2 Sj for any j E f3.... d}. Next, we also require that 2 S3. Note that this requirement satisfies the requirement of I3 on the Ca). Moreover, note that I3 and Iạ impose upper bounds on
magnitude of Ça (since (3 Ç1 > a which are not related to C2..... Ca. Therefore, there exists some a* > such that if a E (0, o0) then all of these conditions satisfied. Moving to the conditions that involve and we first observe that there exists constants S, >> such that
S (1
52
equivalent to the condition from Z, and
(1 - (2) Ta
equivalent to the condition from I5. Invoking Lemma 36 we obtain that there exist constants
91, W1 (0, 1) and Q2 W2 E (5.1) 1) such that taking E (q1, W1 and (2 (42, w2) satisfies the two
conditions involving a and (z. The above discussion is summarized in the following proposition.
Proposition 19. For any 0 there exist constants Qı, wt E (0, 1) and q2, w2 E ( 1) such that the set
(a-(1,62. (L..,.....Ca)) (a, E (41, w1) (92, W2),
2 2 Go > ... Sa
contained in the intersection of initialization subsets given by
(e)
Now that we have characterized a set initializations which satisfy all our requirements, we will show that this set contains an open subset.
Lemma 21. The set of initializations satisfying all our requirements, namely
{a. (1..,......a)) (a,, C2) E (q1, w1) (42, W2), 2 C3 ....
contains an open set, namely set of the form (a1, b1) (ag, x (as, ba).
Proof. We begin by restricting Sa...., Sa by requiring that for 3 S S d, Cj E [eg, fyl where the closed intervals {lej, fylbsssa satisfy
1
22
fa > ea > 0.
2
We can restrict a further, by requiring that E (01, b1), where 01 by are chosen such that for all 2 < j S d we have
a1fs > biej
65

---

We now claim that for all 2 2sidd
(bie),aiSi)
n aE(a1,61)
[aes aʃjl
Indeed, for any a E (a1,b, b1) we have b > aej and aj < afj. It follows that we can take aj bie,,by bj = fn and obtain that the set (a1, b1) (02, b2)
(ad, da) is contained within
aall, S2........ Sa) (a, C2) E (g), w1) (02, W2), G3
Sa
as required.
G Proof of Theorem 2
The first part of the Theorem is special case of Proposition We present below the proof for the second part.
For & N and A E RR.,d, denote by Geny(A) the generalization error over sequence length k (Definition T. Note that and C are omitted from this notation, as they are fixed to the values 1.C I throughout the proof. With slight abuse of notation, we also denote (s(A) = (s(A,
B
Our proof's considers augmented objective, given for the training set S" obtained by scaling all sequences by- :
s" x (x,y) (x..)) (x)))
-((
:x (x,))
[(ex-1,1)}
Since SSMs realize linear mappings, for any A E Rd.d we have that
1 d² (s)(A))
(s.
(n (ne (s(A)+
n n ((ee. 1.1)) (A).
We prove the required statement for the gradient flow dynamics (Equation 44h obtained for the set S". from which it follow that it also holds when revert back the set S since the two systems of ODES differ only by a positive scale.
First, consider the objective when the training set consists solely of the sequence
(xx,
(tx²)
(ex-1;
The corresponding training loss (Equation
is given by
1
2 af dllemllh = Σ
d
2
((c)-).)))(A)
ai
1
aj
1=0 1=1
i=1
and the corresponding gradient flow dynamics (Equation
for E Rzo are given by
Vi [d. à,(T) = -2 Σ (.((T) -1)
For any initialization of the student SSM Ao = (at,..., aa), it is straightforward to show that the solution to the above system of ODEs A(T) is given by
1 Σd Σ a;
ΣØ a exp(pp2 -2 .2)d.77) T).
Wi [d], E R2o, (i(T)
d
Specifically, as + oo the solution A(T) converges exponentially fast to the point Ào given by
Vi [d], à 1 - 0i Oj
d
66

---

which satisfies
(1-
d
Σ
d
((c.-
j=1
04
aj
0.
i=1
Consider the open set Z of initializations for the student SSM given by
I: (-1 ---d'' d3 d3
Note that for any c O, the corresponding set of initializations from Proposition and the set intersect, and moreover the intersection contains an open set sufficient for our needs. We next prove that for any initialization Ao = (a1..... ad) E I, the point Ao that the system converges to as - 20 satisfies (Ao) > 1 d.
4 For any index i [d] it holds that
1 d
vj E
agl< <
Σ
04
aj
Σ
03
agl d'
The latter implies that
1 d
1
5 d
1==
04 0j
1
2
<
d
<
+
da
d
which results in
1+
1
-+
d
1
4
d
di
d
Overall, since d 2 5 and h 2 3 we obtain that
d
Gen)(Ao) =
max
1
k'E10,1....b-1
b-1
1=1
j=1
0
d
4d
1
d2
4
d'
By the continuity of (1)-1,,)) (A) and Gen (AA), the above implies that for any initialization Ao E: I there exists a time E R such that when initializing at A(0) Ap and evolving A(T) according to the above dynamics it holds that
e 1()
S
and
3 3 d
Genu(A(t)) >
Now consider the objective for the full set S"
LS (A)
72
(s(A) +
+ I l
1
()),
(n + 1)
67

---

whose corresponding gradient flow dynamics (Equation for T E R20 are given by
Vi E [d], (.()) (n 1)e² da,(T) (s((T))
72
2 n. + Σ Ea(t))-)
Observe that the left terms of both the objective and the dynamics all vanish as c + 0o. Additionally, note that when the left terms of the dynamics vanish, the dynamics differ by positive scale from those discussed above when the training set consists solely of the sequence (cx-1: 1). Therefore by continuity, for any initialization Ao E I and any time t' E IR>u there exists E R>o such that when initializing A(0) Ao (0), evolving A(T) according the dynamics given when the left terms vanish, and evolving A'(r) according to the full dynamics, it holds that || A (t') l|2 is sufficiently small to ensure that both
( (l)e_ - lst (s
n +
and
1
(Gen((((t)) (enn(A(()))GGen(((())))
-
4 d'
The proof follows by invoking the last claim for the time obtained previously.
H Auxiliary Theorems and Lemmas
In this section we provide additional Theorems and Lemmas used throughout our proofs.
Lemma 22. Let f Rd + IR be some differentiable function. Suppose we optimize over f by initializing x(0) : Xo for some xo E Rdd and updating using gradient flow, i.e.:
(1) = x xx))==v((x()))
dt
Then the objective is non-increasing w.n. time, i.e. for any t 2 0 holds that
di fx((t) 0.
Proof. Applying the chain rule, we obtain the following:
dt f(x(t)) = T d
d
dt x(t) f-x(()) = -11f(((t))13 0
Lemma 23. Let f Rdd I. be some continuously differentiable flnntiio which is also coercive, namely
lim f(x) 20. ||=||=>0
Suppose optimize over by initializing x(0) X for some Xy Rdd. and updating using gradient flow, iee.:
x(1) = x x
(24)
Then there exists global solution to the above ODE, namely curve x(t) which satisfies the above equation for all 0.
Proof. By Lemma 22 and the coercivity of f. the trajectories of gradient flow cannot escape from
some compact set K = (xx)). Because f is continuously differentiable V has some finite Lipschitz constant on K. Existence of the solution for / 2 0 now follows from the Picard-Lindelöf theorem (see (80))
Theorem 4. Let V C dd be an open set. Let f V + R be a non-negative differentiable function satisfying the following conditions:
68

---

The set X == E V f(x) 0f is not empry.
There exists μ > O such that for any x E V it holds that
VV [x)]) 2uf(x).
There exists M > such that Vx(() is M-Lipschitz in V.
Suppose we optimize over f by initializing x(0) for some Xo E V and evolving via gradient flow, Le. via the update rule
x(1) = dt -V(()==V((x(t))
Assume the set V is not escaped, i.e. for any time 2 O it holds that x(t) V. Then it holds that
J. [|(()]l2d1 = / [VVS((()))l2d) S
M
Dist(xx; X*).
V
Proof. The theorem is restatement of theorem 9 in 29
Definition 13. Let C IRd be an open set. Let f - R differentiable function. We say that f satisfies the Polyak-Lojasiewicz condition with coefficient > at x E V
[ 2 2x(
min f(y)). yEk
If the above holds for all x E V we say that f satisfies the PI. condition in V.
Lemma 24. Let V C Fd be an open set. Let f V + R be non-negative differentiable function satisfying the following conditions:
The set x" = E f(x) 0} is not empty.
PL condition (Definition) 13 there exists μ > such that for any x holds that
[V 2 2xf(x).
Suppose we optimize over f by initializing x(0) = Xo for some Xa E V and evolving gradient flow, t.e. via the update rule
d
x(t) x(t) -VF)xxx(((()))
dt
Assume the set V is not escaped, i.e. for any time 2 0 it holds that x(t) V. Then for any t 2 0 it holds that
f(x(t)) & fx((0) exp( 2p t).
Namely, it holds that
lim ((x(t) 0.
Proof. Let &. 2 0. By the chain rule, it holds that
di [(x(1) V(((()) d x(11= [x((() (-x())) -11((x00
d
di
By the PL condition and since V is not escaped, we have that
f(x(t) [| -2pf(x(t)).
Therefore, by Grönwall's inequality 21 we have that
f(x(t)) < f(x(0)) exp (L 2pdd = f(x(0)) exp(-22 t).
-2-2
Taking the limit as f - completes the proof.
69

---

Lemma 25. V Rd be open set. Let f f V - R be non-negative differentiable function
satisfying the following conditions:
The set X E f(x) 0} is not empty.
I satisfies the Pl. condition with coefficient p (see Definition T3
Lipschitz gradient there exists M 0 such that fx()) is M M-Lipschitz in V.
Suppose we optimize over f by initializing x(0) Xo, for some Xo E V and evolving via gradient flow, Le. via the update rule
x(1) x(t) V
Assume the set V is not escaped, i.e. for any time 2 O it holds that x(t) E V. Then the limit lim x(t) x" exists and satisfies f(x*) and
M
Ix xool2 S V
Dist(xo, X*).
Proof. Let O. By theorem
4 it holds that
M Dist(xo, X*)
[1x(T S V
which is finite since X not empty. Hence, there exists 2 0 such that for any 2 1* holds that
[x(T]ll2dT Se.
Therefore, for any l2 2 1 2 1r it holds by the fundamental theorem of calculus and by the triangle inequality that
(x((2) - x(1i)l12 = XD 1/' x(T)dr xo L/² x(()
22
x(T)dt
" [|x(T))l2dr
< [x(7)
Jb
6..
Thus, the Cauchy convergence criterion is met and so the limit lim x(1) = x" exists. Plugging f's continuity and lemma 24 yields the following
f(x") f( lim x(1)) lim f(x(t)) 0.
++000
t-000
Finally, by continuity and by the triangle inequality it holds that
x Xool2
x0
x(r)dr X0
x(T)
[|x(t)]l2
M Dist X*)
required.
70

---

Lemma 26. Let a, b E R. An eigendecomposition of the matrix (a b)La + bla.d. where la is the d, all ones matrix, is the following:
The eigenvector 1 with the eigenvalue a + [dd - 1)6.
For j E -2,...,,d .d. the eigenvector e1 ej with the eigenvalue a
Proof. First, it holds that
[aa a + bl.a (a d1 = (d- 1)b)1
hence an eigenvector with the eigenvalue + (d 1)b. Next, note that for any j E (2.....d) we have
I(a ba + bld,al(e) -
e,) -
b)e + b1 (a - b)e, b1 b)(c1 ee,)
hence e1 ej is eigenvector with the eigenvalue
b. Finally, note that the set {1, e1 e2) is linearly independent and thus spans B Therefore, the above eigenvectors and eigenvalues constitute and eigendecomposition of (a b + bla,d.
C1 ........
Lemma 27. Let W E Rd,d be symmetric matrix and b E Rd be vector. The solution of the linear dynamical system
8(1) = -W(y()))))
given by
y(1) exp(-W) =
exp((t A)Q (y(0) b) +
where W = QAQT is any orthogonal eigendeccomposition of W.
Proof. Using the change of variables x(() y() b. the given system simplifies to
2(t) -tt(t)
whose solution is given by
<11) = -x ()z(
Reversing the change of variables and reorganizing yields
(t) exp(-t- () - bb) b.
Let W QAQT be orthogonal eigendecompositiion of the symmetric W. Then have by the definition of matrix exponential that
(t) = Q exp((-t-tee -AQT (y(0) b) +
required.
Lemma 28. Let Xo Rd. Let V1 Rd be neighborhoods of xg. Let H Vi - Ui be C diffeomorphism. There exists r > such that for any T1 (0, there exist r2 E (0,r1) and r3 for which
[s)r S (s) S (s),
HlE,(()) Lipschitz.
-H-"BB,(s)) is Lipschitz.
Proof. Vi and Ui are neighborhoods of x, and so there exist r > 0 for which (xo) S Vi and B, (xo) =: U2 U. Hence, by H's continuity there exists some small enough r >>> 0 for which (xo) C Vi is mapped by H to H (x)()))) C Uz Fix T1 (0. Then it holds that B,, (xo) satisfies
Br, (xo) C (xxx) V
71

---

and is mapped by H to
H[B., (xo)] C ((,)(x))) Cub
Since Br, (Xo) is compact ball and since H is CS, we obtain that H is Lipschitz over Br (Xo), Le. H (xo) is Lipschitz. Similarly, we obtain that H-1 is Lipschitz over U2, iee. H-1 R is Lipschitz. Therefore since H [[,, (xo)] E U2 we obtain that H H BB Br, (xx)] is Lipschitz. Next, note that for any 72 E (0, r1) the compact ball B,,, (xx) satisfies H H (xo)] S H [B, (xo)]. Hence, by taking small enough 72 guarantee by H's continuity that there exists some T3 0 for which Brg (Xo) satisfies
H[,,, S Brg (xo) E H[[ (xo)].
Since H "H- (x,1) is Lipschitz and Brz(xu) C H[Br,(xx) obtain that H Lipschitz.
Brg (xx) is
Lemma 29, Let f I2 + Rd be a vector field and let B C Id be a bounded and compact space. Suppose I is N-Lipschitz within B for some constant N > O. Consider the following system of ODEs:
x(t) = fxx(t))
Consider two initialization points (1) x2) E B. Suppose we evolve (1))), (t according to the above system. for any 2 0 it holds that x1 (t), x2(1)= E B, then
(0) xz(0)]l2 exp( - N t) |x1 (t) x2 (t)ll2 S [0x (0) x2)
exp(N -t..
Proof.
Lett 2 0. Applying the chain rule, we obtain the following: d
d |x| (t) x²(1)]12 dt v (xx xx)()) (t) x2()))
dt
1
d
2 (1)x(() x2(())l2 dt (x)(t) x2())) (x1(t) - xt(())
2
2 2 (t) (2(1l11 (xi(t) xx(t)) de (x((t) - x2(())
X (l) x2(1 (x1 x2(1) (1((((())))) (((x)(0))((xx((0)) /(x2(0))
1
Thus, applying the Cauchy Schwarz inequality we obtain
(xx((t) x2(())22 - (1) - x2(1) [tx - x2 (00)))22)0(((000) (xx((())
dl
= (x) - f(x2(t)lla-
f is N N-Lipschitz within B, and so since x (1), E B we obtain
d
xxx - (1)l2 < (t) fxxx s N [|x((t) x2(1)]l.
Finally, plugging Grönwall's inequality 21 results in
| - (2) S | - (0)l22 (xp(N-t)
Next, consider the following system of ODEs which we coin the reversal of f:
( = - (x()).
Consider the initialization points xi (0) = x1 (t) and x2( = (2). Suppose we evolve xi x)))
according to the reversal of f. Then holds that for any time 7 E [0, t] and any E [2] we have
(1) xt 7)
hence (7) E B. As Lipschitz continuity is invariant sign, -f is N-Lipschitz within B. Therefore, we can apply the above claim on the reversal of f. and obtain that
Xx (0) (0)l2 = (t) xt(1)ll
< (0) (0) exp(N
| (t) - (2) exp(N t).
The proof concludes by rearranging of the left and right hand side.
72

---

Lemma 30. Let f: Rd -t Rd be a Lipschitz continuous vector field. Consider the following system of ODEs:
x(t) = =x((()))
Consider two initialization points x1 (0), x2( E BR. Suppose we evolve X1 (f), (t) according to the above system. x0) 7 xz(0) then for any L holds that X1 (1) + (2))..
Proof. The argument follows from the Picard-Lindells existence and uniqueness theorem, which states that for given initialization x(). there exists unique solution x(t) the ODE system
x(t) fx(())
Lemma 31. Letx Rd. Denote x's representation with the orthogonal subspaces W1 and W2 be
x = B1 + A2 v
where v E W2 is a unil vector. There exist j, E [d] such that
| - 1 132
d
Proof. Denote v's representation with the basis vectors of W/2 to be
Σk= k= Ak
2
d (e1 - -ex)
2=
dd
where , Ad E TR. Denote A= = (A2)..., Ad)_
E Rdd-1
As v is a unit vector, holds that
2
d
2
d
1 1 |/v12 =
A
+
=
+
X2
2=
k=
k 2
k=
Hence,
2
Ax
k=2
Applying the Cauchy-Schwartz inequality we obtain the following:
Σ
AR
Σ
E1-1a
An
|A| = (d - 1) Σ X
k=2
k=2
Therefore, we obtain that
d
2
d
d Σ
Σ = =1 Σ A 2 1 (d 1) Σ x
21
x
2
d'
k=2
Therefore, there exists 8 E (,...., d} for which X 2 Jd- and thus |>=
If there
dddd11)
exists j E (2....,d) d) for which X, has distinct sign than A then it holds that
1
|u:- uy A+- + A1y 2 A4-
/d(d-1) 1)
Otherwise, all entries of share the same sign, and so it holds that for any j E (2.....d)
d 11 .y5 = d (-1,) Σ Dul + 1
v dd(d-1)
Therefore, there must exist i E [d] for which |0o - Vdld-1)"
resulting in the following:
|8cl
| - -x5l = -13, + 32 U; 31 - B2 . uzl = 132l |0: - Uz5 2
Vd(d 1)
73

---

Proposition 20. Let E [-s, s) for some 0 such that |x - vl 2 for some b > 0.
Then for
any k Modd it holds that 1x y²1 (2)². Additionally, if + then g (2x)²
Proof. Suppose WLOG that 2 y. By the triangle inequality it holds that max (zx], 1u13 2 3/2
2 0 2 then since k E Nodd it holds that
|r 10 - |z| + 1y1* 2 (
Now suppose that 2 O. Then we have that
lx
xx (y b)
y¹ 2 8h 2 (2)e
The case of r, y S is identical. As for the second inequality, If y + O, we get
4b x
1rrk
11
( )
yk
yr
1
Since E =[-s, s) we get that l < sh
and so
jk
2 1,20
y
28
Proposition 21. Let 2, U, E R such that y, + 0, and let b 0. If $1
then either
[1
b+2
842'
Proof. Assume to the contrary that both [1 -
and
211
8 642
This implies that
642
b
x
0
1
+
b+2
2
b
b+2
Hence, we get that
b
b
2
b+2
b
6+2
<
1
b+2
6
26 26
6 ++1 1.
6-1 2b+2
b+2+b
+
6
6
6 2 -
2
b42
842
Rearranging we obtain
-6
1 <
T
<<6
b+1
which implies 1 - 1| < b, contradicting our assumption.
Lemma 32. Let ff Rd + R be a differentiable function. Consider the gradient flow dynamics induced by f. namely:
x(1)= x()==v((x())
initialized at some xo E Rdd. Let ln < </2 be times such that
{ S
( f(x)
(x(t): E [t,, E
min f(y) + +c yeRd
for some e 2 0 and f satisfies the PL condition with some coefficient μ > 0 in (x(t) i [1, Then
(fxtt)))((x(t))) 2(tz t1) c.c.
74

---

Proof. By the fundamental theorem for line integrals we have
(<F())))=~((((())))..>>)>>>>>>) Vf(x(()).
dr dr= J. [VV (
f(x(ti)) f(xtt)))-((xt)))---
applying the PL condition and Equation 24 we get the required result.
Lemma 33. Let g R IR be a continuous function and let > and let B be a compact set such that 0 E B. For any & 2 denote the minimum value of g over Diff(()) n B as
f(b)
==
min xEPiflWjnn 9()..
holds that f right side continuous 3b
Proof. Recalling the definition of Diff(() (Equation 17
). we have that for any +b 2 0 the set
Diff( n compact, thus (1(b is properly defined for any vi 2 (as by continuity g attains
minimum over the set). Next, note that ff is non-increasing since for any 4/2 2 1/ 2 0 it holds that
Diff(()1) n B S D2f B = f(/1) x Jn
min
g(x) 2
min x)Di
g(x) = f(V2).
be a non-increasing sequence of non non-negative reals for which Let [1 J
lim v/n = 0. n-000
As f non-increasing, the sequence (f(*a) bounded by f(0). Hence, the limit R == lom (())) exists and satisfies R f(0). For any & 2 we let Xy be a minimizer of g over Diff(e) n i.
is monotonically non-decreasing and upper
X E argmin g(x). xEDiM())nB
The set B is compact and the sequence {x J has convergent subsequence {xung 1.0 Denote its limit
lim Xinng =: =x E (,) A0
Assume on the contrary that x & Diff(O). Hence by definition of Diff(O) it holds that
+ = max i.jE[4]
b 21 > 0.
However, since tim vi = there exists &e E N such that for any k E N such that & 2 Te it holds that iin S 1 3 and thus
X Dinf( S Diff( 2 ) & Diff( 2)
This results in limg-+o0 Nyn * x contradiction. Therefore we obtain x* E Diff(0) n B. By g's continuity and f's definition we thus obtain the following
lim ((x,m,)) g( lim Xw...) = g(x') S(0). k00
Per X 's definition and since lim f(va)) = R we also obtain
lim g(Xe,,,) = lim f( R.
100000
k-000
i.e., R 2 f(0). Overall we obtain that R < f(0) < R. hence R = f(0). The above result is satisfied for any sequence (1)) x=11 hence lim f(}) f(0) required.
Lemma 34. Let f Rd - Rd be a C and Lipschitz vector field. Consider the system of ODEs given by
x(t) f(x(t))
75

---

Consider two initialization points X1 (0) (2(0) E R.. For any t 2 we use Xmaz(t) to denote the maximum over the line segment between X1 (t) and x2(t) of the maximal eigenvalue of the Jacobian of J. i.e
max Amar V. x1(1) + ((1 (1-A) x2(0)) k
Amann (1) =
For any 2 O holds that
-xa(t))x(t)lle I ( (T) xx200)12.
Amaz
Proof. First note that since f is Lipschitz, Amaz (t) is defined for any t 2 O. Next, if x, (0) = (2( then the trajectories coincide and so the claim trivially follows. Suppose x1(0) # x2( By definition, we have that
d (x1(t) (x2(()xx((t) = (xx(()))((x(((t))
dt
As f is C2, we obtain by the mean value theorem (see (68) that there exists & E [0, 1] for which
(xxx))) vs(k x1(() + (1 - k)) xx(()) (12)(((())))))
Additionally, by the chain rule we also have
d dt [t) x2(t)l2 = di (xx(() (())))))))) (x1 x2(())
d
d
(1) x2(())l2 dt (xI(1) x2(1)) (x1 x2(1))
(1 x2(1) (x1(1) x2(()) d
2
dt (x1(1) x2(1))
xxy (t)ll2 (xx(t) xx(1)) T (f
Plugging the above yields
di xx( ((())>x((0)l2= (x1(t) - x2)))) V (t) xx)) - x2))))
d
[1) x2(1)
[1) - x2(1)l22 (x) xx)()) Ví x, (t) + (1 k) X2 (1)) (x1 (f) x2(()) (+).
(x1(t) - xx())) (x) xt)
The right term is bound by the Rayleigh quotient (see h2 ), and so the above can be bound by
(+) < (t) - x2(t) Amar
Vf(l x (t) + (1 - k) x2 xe(()) - (x) x2(t))l2 Aman(
where the last inequality stems from Xmar (1)'s definition. Dividing both sides by ||x| (1) x2(1)ll2 and integrating w.r.t time yields the following
[n([)xi(t) x2()) - (0) - x²(0))2)= L:
- dr S 1/ Amar Xmar (dT
[xx](T) - xz(T)ll2
Reorganizing the inequality and taking exponents yields
(t) xz(t)ll2 s exp (L, Amaz (T) + [n(1|xx(0) - xxx(0)ll))
cxp (%/ "mmae())rr) (|x1 xz(0))l2
required.
76

---

The sub-level set (f) is compact and satisfies x E Li(f) for any E N, hence the sequence {x a Jm is bounded. Therefore, the sequence has convergent subsequence fx "A bk=1 with some Lemma 35. Let f: - + R be continuous non-negative function with min f(x) = 0. Denote
X" == {x E R f(x) = 0}. Suppose that the sub-level set of defined as L (f) ;= {x E R f(x) 1) is compact. Then for any 5 > 0 there exists vj > such that for any x E IR if f(x) S then Dist( X*) S d.
Proof. Assume on the contrary that there exists d >> 0 such that for any > 0 there exists X,y R for which f(x,,) and Dist(X;; X*) 8. Consider the sequence {x "n==== For any n E N it.
holds that f(x:) I 1 and Dist(x .x*) > 6, therefore it holds that
lim f(xy) = 0.
n n-
limit x* == limm-+00 Xnx. By f's continuity we get that
f(x') = f( lim Xm.) = lim f(xm.) = lim (xx) = 0, k0+
k-100
i.e., x" E X This is contradiction since all x must remain at distance at least from x' on the one hand, and x converges to x" the other hand.
Lemma 36. Let Let S O. n N and x² E (0. There exist 9ı, wi E (0, 2*) and q2, we E ($.1) such that for any x E (41, w1) and (92, W2) it holds that and
y Tx
S x S - (1 y*r)
Proof.
First note that since T >>> 0, the first requirement is equivalent to having
1 1-
x.
T
Let E (0, 1). It holds that
lim 8-1 y
S (1 -ー--))}=
lim 8-1 y
S
{(1
(1- y)
= Sn
lim (1 y) 0.
9-1
1=0
Therefore, there exists y' (0, 1) such that for any y I// 1) it holds that
S y²) xx
(1
y
On the other hand, it also holds that
1
5nー1 ( ( 1
(1- vo
S
1
(v+1)
ym
x+1
2TS
1-
2 +
1 y
T
n
2TS
Σ En- (2t
(1 - 1)
y + 1
1 y
Hence, taking the limit as y 17 obtain that
s -
ym
27S
Ei=o
y+ )
(1 y)
lim 1-
lim
1-
1-1
+ 1
y
TS . n (2)
1 x lim
1
(1
y) n-1
77

---

Therefore, there exists y" E (0, 1) such that for any E [y", 1) it holds that
S
ytt
)m
I
2.
2
T
and 8o
1
8
1 -
1+1 ym
Thus, setting '" = mmxx ( 2, ,1,"""" we obtain that the interval
T
L-y"
s
1
y ym
is not empty and upper bounded by x² Additionally, for any
_
y E (y", y +1
the following holds:
1 y
- -
y <
T
T
V" +1
s
(1- 35 + (1-10)
(1-("+1)))
yr)
S (1
(1-
> y
2
y++1
2
y
2
Hence the interval
1-y² 8
(1 ))))
1 1
4 2
is contained within the interval
(1-y
T nt
(
(x*)) Noting that 21+1 < 1, we complete the proof by setting
1- y¹
S
+
1 n
91
W1
T
2
2
and
y"
+1
92 = 4
W2
2
I Further Experimental Results
In this appendix we provide additional experimental results omitted from Section
L1 Dynamical Characterization
The experiments in Section 4.1 corroborate our dynamical characterization (Section 3.1 by demon- strating that greedy low rank learning of the state transition matrix A occurs under some, but not all, choices of training sequences. This appendix reports the following additional experiments.
Figure 3 extends the experiments reported in Figure 2 longer training sequences.
include experiments similar to those in Figure 2 where the training sequences are labeled by teachers of higher dimensions.
Figures 4 to 6
Figures
and report the results achieved with different random seeds in the settings of and
Figures
respectively.
A classical continuous surrogate for the matrix rank is the effective rank 667. Figures 9 to 15 present the effective rank of the transition matrix A throughout optimization in the settings of Figures to g respectively, underlining the low effective rank caused by greedy low rank learning.
Figures 16 to 19 report the values of (0) (as defined in Proposition I observed during optimization in the settings of Figures 2 and R respectively, showcasing that larger absolute values of ((() (t) do not correspond greedy low rank learning, whereas lower absolute values do.
78

---

SSM special sequencess
MLP, without special sequences
SSM MLP.. with spect sequences
special sequences
Entry magniuste
Entry magnitzde
magnitude
Entry magnitzie
2.0
0.5
0.01
0.0
K1P 0.0
0.0
Ieeaaion K10
heration
Iteration K10
Iteration x301
Figure 3: Demonstration of the dynamical characterization derived in Proposition optimization of an SSM. trained individually as part of non-linear neural network, implicitly induces greedy learning of (diagonal) entries the state transition matrix A under some, but not all, choices of training sequences. This figure identical to Figure 2 except that the sequences used to train the models were longer, namely, of sequence length 10 as opposed to 6. For further details see Figure as well as Appendix J.1
5SM length with sequences
SSM length
Entty magnitue
1.0
without
1.0-
Entty mogmtuus
without special
Entry maagnnuuee
with special
0.5
0.5
G5
0.0
3.0
5.0 Iteration
7.5
X10
Ieerttion
Iteration
X10
Iteration
x10
Figure 4: Demonstration of the dynamical characterization derived in Proposition optimization of an individually trained SSM implicitly induces greedy learning of the (diagonal) entries of the state transition matrix A under some, but not all, choices of training sequences. First two plots (left) and last two plots identical the first two plots Figures 3nd respectivey, except that the teacher used to label the training sequences is of dimension Appendix J.1
2 (as opposed d" 1). For further details see Figures [and Bas as well as
1.2 Synthetic Clean-Label Poisoning
The experiments
the theoretical results of Section 3.2 by showcasing synthetic
regimes in which SSMs are susceptible to clean-label poisoning. Table supplements the experiments of Table by including results in which the SSMs were trained on longer sequences. Tables and report the standard deviations of the quantities presented in Tables and respectivvey.
Table 3: Demonstration of clean-lahel poisoning SSMs. The table identical Table except that the sequences used to train the models were longer, namely, of sequence length 10 as opposed to 6. Notice that across all scttings, special training sequences significantly deteriorate generalization. For further details see Table as well as Appendix J.2
Setting
Without special sequences
With special sequences
Per Thcorem
7.34 10-3
3.51 10-2
Standalone SSM beyond Theorem
!
1.22 x 10
1.2
SSM in non-lincar neural network
4.67 x 10-2
8.93 x 10
1.3 World Clean-Label Poisoning
The experiments in Table 2 corroborate the theoretical results of Section 3.2
by demonstrating clean- label poisoning of SSM-based neural networks in real-world settings. Table provides additional context to the experiments of Table 2 by reporting the training performance of the trained models, before and after the inclusion of cleanly labeled poisonous examples. Tables 7 and report the standard deviations of the quantities presented in Tables and o respectivel..
J Implementation Details
We provide implementation details omitted from Section 4 and Appendix Code for reproducing our experiments can be found htthtpp::/ ptetts://githute com http://ttthaa.como/ooo//stttt/// hipp:m//mmmmmmm/m/ bias comm-oossn
79

---

length special sequences
length 6,
SSM length
langth
with special sequences
special sequences
with special sequences
Enery magnitaee
1.00
Entry magnitud
1.0
Entry magnitude
0.5
0.5
3-5
0.0
0.0
0.0
X10
Iteration
x30
Iteration
KIOP
Iteratton
x10
Figure 5: Demonstration the dynamical characterization derived Proposition] Figure except that the leacher used label training sequences is of dimension d' sec Figure 4 and Appendix J.]
|
This figure identical to For further details
length
SSM length
Estry magniudt
2.0
without special
2.0-
without special sequenccss
Enery manggnuuu
0.5
0.5
0.5
Iteration
X10
Iteration
x30*
Iteration
X10*
Iteratton
x1o*
Figure 6: Demonstration of the dynamical characterization derived in Proposition
1
This figure is identical to For further details
Figure except that the teacher used label the training sequences is of dimension d" see Figure 4 and Appendix
J.1 Dynamical Characterization
In this appendix we provide implementation details for the experiments of Section and Ap- pendix [.1 All experiments were implemented using Keras [10] and carried out on single Nvidia RTX 2080 Ti GPU.
J.1.1 Standalone SSM
Models. the experiments reported in Figures 2 7 and 8 we used teacher SSM of dimension d" = with parameters
where a standalone SSM was trained,
A = =1 =1
All parameters of the student SSM (i.e., A, B and C) were trained. We set the student SSM dimension
to d 10 for Figures and 7 and to d = 20 for Figures 3 and
Next, detail the models used in the experiments with teachers of higher dimensions (Figures to (). the experiments reported in Figure 4 we used a teacher SSM model of dimension 2 that was set with the parameters:
(0.99
(0.99
0 =1 C²
A"
0.8)
In the experiments reported in Figure with the parameters
we used teacher SSM model of dimension 3 that was set
00.99
0
A
B" =1, 0³ =1
0.5
In the experiments reported in Figure 6 we used teacher SSM model of dimension 3 that was set with the parameters
70.99
0
0
0
A"
0.8
0
B" 1, 1²=
0
0
0.5
0
0.3
We used student SSM models whose input and output matrices B(-) and C(-) were fixed at 1 and 1 T respectively (due to computational limitations). The student models had dimension d 10 in the
80

---

SSM, without special sequencess
SSM MLP.
SSM M.P. with special sequencess
with special sequences
without special sequences
Entry magnitutte
1.0
Entry magnituds
1.0
Entry megnituele
Entry magnitude
2.5
0.5
0.5
0-5
0.01
0.0
0.0
Iteratoo
X10
Iteration
x30
Reertion
x10
Iteration
X10
Figure 7: Demonstration of the dynamical characterization derived in Proposition] | Figure except that a different random seed was used.
This figure identical to
SSM, without special sequences
SSM, with special sequences
SSM MLP,
SSM MLP. with special sequences 1.0
without special sequences
Entry magnitude
1.a
1.0
1.0
Entry magratude
0.5
0.5
Extry
0.00
025
0.50 0.75
1.00
0.0
0.5
1.5 Iteration
1.5
200
Iteration
K10'
Iteration
Iteration
X10"
Figure 8: Demonstration of the dynamical characterization derived in Proposition Figure except that a different random seed was used.
!
This figure is identical to
experiments of shorter sequence length and dimension d = 20 in the experiments of longer sequence length.
Data. In all experiments we used the respective teachers to generate the labels for training sequences. Additionally, we used training sequences of one two types, referred to as "baseline" and "special", where each type had designated indices of non-zero entries. were present each sequence type for each experiment. Training sequences of both types had their non-zero entries sampled i.i.d. from (O0 1). Table 10 specifies how many training sequences of each type were used in each experiment.
which non-zero indices
Initialization. In all experiments we initialized the student's A. B and parameter matrices in a manner that was inspired by the initialization set I of Theorem I
To initialize (the diagonal) A in each experiment we first sampled d i.i.d. entries from (O sd od_.). took their absolute values and then arranged them in descending order. Then, we set the second entry to have the first entry's 's value minus a constant diff. This was done to reflect the near zero initialization on the one hand and the proximity to the reference trajectory on the other hand. In the experiments reported in Figures 5 and [ we naturally extended this procedure by setting the third entry to have the first entry's value minus 1.01 diff in both experiments, and the fourth entry to have the first entry's 's value minus 1.05 diff in the latter. Table [ableeIreppe report the values of sd_ A and diff used in each experiment.
To initialize B in each experiment first sampled d i.i.d. entries from A(0,, (d_,BdBBB sd_B_Cd B_C), took their absolute values and then arranged them in descending order. Then, we set the second entry to have the first entry's 'ss value minus a constant diff. This was done to reflect the near zero initialization on the one hand and the proximity to the reference trajectory on the other hand. In the experiments reported in Figures 5 and 6 we naturally extended this procedure by setting the third entry to have the first entry's value minus 1.01 diff in both experiments, and the fourth entry have the first entry's 's value minus 1.05- diff in the latter. To initialize C' we followed the same procedure, without modifying the second to potentially fourth entries. Note that in the experiments reported in Figures 4 to 6 the input and output matrices B(-) and C(-) were not trained. Table I1 report the values of sd___o used in each experiment.
Optimization. In all of the experiments trained using the empirical mean squared error as loss function and optimized over full batches of the training sets. In order to facilitate more efficient experimentation in the experiments where standalone SSM is trained, we optimized using gradient descent with an adaptive learning rate scheme, where each iteration a base learning rate is divided by the square root of an exponential moving average of squared gradient norms (see appendix D.2 in Razin et al. (66) for more details). We used weighted average coefficient of B 0.8 and softening constant of 10 6 Note that only the learning rate (step size) is affected by this scheme, not the direction of movement. Comparisons between the adaptive scheme and optimization with fixed
81

---

55M, without special sequenices
SSM,
SSM without special sequences
MLP. with special sequences
with special sequences
Effective rank
Effective rank
Effective rank
Effective
5.00
Iteratton
X10*
Iteration
K1P
Iteration
K19
Ieeraion
x10
Figure 9: Demonstration the dynamical characterization derived Proposition through the lens of effective rank of A introdduction of special sequences the tranining set results significantly larger effective rank, in compliance with the disruption of greedy low rank learning. Each plot shows the effective rank of during the training process reported in Figure 2
SSM
SSM with special sequences
SSM MLP.
SSM MLP. with special sequen.cos
without special sequeniess
without special sequences
Effective rank
Effective 1.
Effective rank
Effective rank
5.00
15
0.0
0.0
0.0
0.5
1.0
Iteration
Iteration
Iteration
Iteration
Figure 10: Demonstration of the dynamical characterization derived in Proposition 1 through the lens of the effective rank of A. This figure is identical to Figure except that the setting considered is that of Figure 7
learning rate showed no significant difference in terms of the dynamics, while run times of the former were considerably shorter. Table 12 specifies the base learning rate used in each experiment.
J.1.2 SSM in a Non-Linear Neural Network
7 and where an SSM was trained as part of non-linear neural network, we used neural networks comprised of an SSM module whose output was fed a hidden layers MLP module. Overall, the models used realize the following function:
Models. the experiments reported in Figures 3
D Dout Driidde (Din (x,n,c(x))
where du E N the hidden MLP width, Din E Rddi., Dhiiden E Rdda.d and Dout E R.d. are the MLP's parameter matrices, ((x) == max(0, x} is the MLP's activation function and @ cx.(())) is the output of an SSM with the parameter matrices A, C. All teacher models used had SSM modules of dimension d" = 1 that were set with the parameters
1
B = C* =1
The teacher models in Figures 2 and 7 had hidden MLP width of d; = 15 while the teacher models in Figures 3 and 8 had hidden MLP width of d; 25. In both cases, the teacher models had MLP modules that were set with the following parameter matrices:
1
D
D Diidden = Is; D
1
2
We trained all of the SSM and MLP parameter matrices of our student models. The student models in Figures 2 and 7 had SSM dimension of d 10 and hidden MLP width of d, 15, while the student models in Figures 3 and had SSM dimension of d = 20 and hidden MLP width of dn, 25.
Data. Data for the experiments were generated in the same manner as in Appendix [.1.I Table 9 specifies which non-zero indices
present in each sequence type for each experiment. Training sequences of both types had their non-zero entries sampled i.i.d. from A( 1). Table 10 specifies how many training sequences of each type were used in each experiment.
initialized the student's A. B and C parameter matrices identically to the standalone SSM experiments (Appendix) J.I.I). Table II Tepport the values of sd_A, sd_B_C and diff used in each experiment.
Initialization. In all experiments
To initialize the MIP layers, initialized all parameter matrices by sampling i.i.d. values from NO, sd_D). We used sd_D = 0.03 in the original experiments (Figures 2 and 7 and sd_D = 0.1 in the experiments with longer sequences (Figures and 8).
82

---

SSM, without special sequences
SSM MLP, special sequences
MLP. with special sequences
special sequences
Effective rank
25.
Effective rank
5
Effective rank
Effective
10
10
12
Iteration
x30
Iteration
KI0
Iteration
K1M
ratioon
x301
Figure 11: Demonstration the dynamical characterization derived in Proposition 1 through lens of effective rank of This figure identical to Figure except that the setting considered that Figure
SSM MLP.
MLP,
special sequences
special sequenicss
special sequences
special sequences
Effective rank
7.-
Effective rank
10-
Effective 10-
Effective
0.00
Iteration
=30
Iteration
x10
Iteration
K10
Iteration
x10
Figure 12: Demonstration of the dynamical characterization derived in Proposition 1 through the lens of the effective rank This figure identical to Figure except the setting considered that Figure
Optimization. To speed up the optimization we trained using the default Keras implementation of Adam [36] with its default hyperparameters. Table 12 report the base learning rates used in each of the experiments.
J.2 Synthetic Clean-Label Poisoning
In this appendix we provide implementation details for the synthetic experiments provided in Sec- tion 4.2 and Appendix [.2] All experiments were implemented using Keras [10] and were carried using a single Nvidia RTX 2080 Ti GPU.
J.2.1
SSM Per Theorem
The main goal of the experiments in the first poisoning setting (standalone SSM per Theorem I was to approximate the solution to the system of ODEs induced by gradient flow (Equation (4) in order to demonstrate the results of [heorem[[ To do so we employed the use of the odeint function of SciPy [84] which is a numerical solver for systems of ODEs based on lsoda from the FORTRAN library odepack [3 odeint's arguments
the initial point parameter space A(O), the timestamps which the solution is required, and a function which specifies the system by intaking timestamp t and point in parameter space A and outputting the derivative in time at A. odeint outputs set of numerical approximations for the solution of the system at the required timestamps.
Models. We use teacher and student models according to the setting described in Section 3.2 We used a teacher SSM of dimension d' 2 that set with the parameters
A"
Q
0 0 00)
B" (1 (1 va-1) C² Vd-I).
We used student SSM models whose input and output matrices BB-) and C(-) were fixed at 1 and 1 respectively. The student models had dimension d = 10 in the original poisoning experiments (Table D.. and dimension d = 20 when training over longer sequences (Table 3.
Data. In all experiments we used the respective teachers to generate the labels for all training sequences. Per Theorem] [ we trained using a single "baseline" sequence of the form e E R and single "special" sequence of the form e E R The relevant experiments reported in Tables and were trained using sequences of lengths 7 and 9 respectively.
Initialization. We initialized the student's diagonal matrix A in a manner that was inspired by the initialization set I of Theorem [ In each experiment we first sampled d i.i.d. entries from (O( sd, A) and then arranged them in descending order. We then set the second entry to have the first's value minus constant diff. This was done to reflect the near zero initialization on the one hand and the
83

---

SSM length
5SM length with special sequences
length 10,
length 10, with special sequences
without special sequencess
without special sequences
Effective rank
Effective rank
Effective rank
10
Iteration
K10
Iteration
K10
Iteration
K19
Iteration
x10
Figure 13: Demonstration the dynamical characterization derived in Proposition 1 through lens of effective rank of A. This figure is identical to Figure except that the setting considered that Figure
SSM length 6, without special sequences
SSM length 6, with special sequences
SSM length 10,
SSM longth 10, with special sequences
without special seq sequences
Effective rank
Effective rank Gr
Effective rank
5.0
2.5
0.003
Iteralion
X10
Iteration
X10
Iteration
X19
Iteration
xte²
Figure 14: Demonstration the dynamical characterization derived in Proposition through lens of the effective rank of A. This figure is identical to Figure 9
except that the setting considered is that of Figure 5
proximity to the reference trajectory on the other hand. Table 13 reports the values of ad and diff used in each experiment.
Optimization. We input odeint a custom function which computes - (A) (Equation (4) given the point A to be used for derivative computations. [aable/T4rrppoo the timestamps simulated in each experiment. All experiments reached training loss values of less than 10 - and stable generalization errors.
Generalization evaluation. Generalization errors were measured via impulse responses of length 40 as defined in Definition I divided by the lo norm of the teacher's length 40 impulse response (such that the zero mapping has error of one). The same evaluation procedures were used in both the original experiments (Table I and in the longer experiments (Table 3).
J.2.2 SSM Beyond Theorem
Models. We used the same teacher models as described in Appendix J.I.I We used student SSM models that were trained end to end (i.e. B-)) and C(-) were not fixed). The student models had dimension d = 10 in the original poisoning experiments (Table T]. and dimension d 20 in the experiments with longer sequences (Table
Data. Data for the experiments were generated in the same manner as in Appendix J.1.1 Table 15 specifies which non-zero indices were present in each sequence type for each experiment. Training sequences of both types had their non-zero entries sampled i..dd from (0 1). Table 16 specifies how many training sequences of each type were used in each experiment.
Initialization. To speed up optimization we modified the initialized employed in Appendix I.1.1 by adding small constant of 10 all entries of A and B initialization. This modification showed no significant differences in terms the generalization error achieved by the models when compared to without it, while run times of the former were considerably shorter. Table 17 report the values of sd_A, sd_B_G C and diff used in each experiment.
Optimization. We followed a training scheme identical to Appendix J.I.I Table 18 report the base learning rates used in each of the experiments.
We optimized all models to reach training loss under 0.01. To verify the generalization errors we report were stable, we trained for additional iterations after reaching sub 0.01 training loss. We trained the standalone SSM models for 1500 more iterations, and the models with additional layers for 5000 more iterations.
Generalization evaluation, Generalization errors were measured via impulse responses of length 40 as defined in Definition I divided by the lx norm of the teacher's length 40 impulse response
84

---

SSM length without special sequencess
5SM length with speciall sequences
length 10,
length 10, with special sequences
without special sequences
Effective rank
Effective rank
Effective rank
7.3
5.0
5
10
2.5
Iteration
K19
Iteration
K1P
Iteration
K19
Iteration
x1o
Figure 15: Demonstration the dynamical characterization derived in Proposition 1 through lens of effective rank of This figure is identical to Figure 9
except that the setting considered that Figure
SSM, without special sequences
SSM
SSM
Gamia magnitude
Ganuma magnittdee
with
Gemmma maggiitude
without
Garmia magritude
with
0.05
0.05
0.00
0.00
05
-0.05
0.0
1.0 Beertion
K10
Reration
X10
Iteration
Iteration
x1o*
Figure 16: Evolution (0) (f) (as defined Proposition during training. Each plot shows the values of (t) during optimization in the setting of Figure 2
As be seen, in compliance with our interpretation of Proposition larger absolute values of (L) do not correspond to greedy low rank learning, whereas lower absolute values do.
(L)
(such that the zero mapping has error of onc). The same evaluation procedures were used in both the original experiments (Table M and in the longer experiments (Table 3).
J.2.3 SSM in Non-Linear Neural Network
Models. We used the same teacher models as described in Appendix J.1.2 We used student SSM models that were trained end to end (Le.. B-)) and C(-) were not fixed). The student models had dimension d = 10 in the original poisoning experiments (Table T). and dimension d 20 in the experiments with longer sequences (Table
Data. The data used is identical to that of Appendix J.2.2 Table 16 specify how many training
sequences of each type were used in each experiment.
To speed optimiza- tion modified the initialized employed in Appendix J.1.2 J.1.2 by adding small constant of 10-3 to all entries of A and at initialization. This modification showed no significant differences in terms of the generalization error achieved by the models when compared to without it, while run times of the former were considerably shorter. Table 17 report the values of sd_A, sd___C and diff used in each experiment.
Initialization. We initialized the student models identically to Appendix J.1.2
Optimization. We followed training scheme identical to Appendix J.1.2 Table 18 report the base learning rates used each of the experiments.
We optimized all models to reach a training loss under 0.01. To verify the generalization errors report were stable, trained for additional iterations after reaching sub 0.01 training loss. We trained the standalone SSM models for 1500 more iterations, and the models with additional layers for 5000 more iterations.
Generalization evaluation. Generalization errors were measured via the root mean square error of a held-out test set of 2000 correctly labeled sequences of length 40, divided by the &g norm of the teacher's s outputs vector (such that the zero mapping has error of one). The same evaluation procedures were used in both the original experiments (Table I and in the longer experiments (Table 3).
J.3
Clean-Label Poisoning
In this appendix provide implementation details for the real-world experiments provided in Section (42 and Appendix [.3] All experiments were implemented using Py PyTorch [60] and were carried out using cluster of 8 Nvidia RTX A6000 GPUs. All experiments consist of three stages: (i)
85

---

SSM, without special sequences
55M
SSM
SSM MLP, with special sequences
Gamma magnitude
Gamino magnitudee
with sperial Sequences
Gemmme magnitude
without special sequences
magnituree
0.05
3.5
0.05
0.6
2.00
04-
0.00
0.2
-0.03
0.2
-0.03
Iteration
K10
Iteration
K10
Iteration
K1
Iteration
x10
Figure 17: Evolution of y 10) (t) (as defined in Proposition except that the setting considered is that of Figure 7
during training, This figure is identical to Figure 16
SSM, without special sequences
SSM with special Sequances
5SM + MLP. without special sequences
S5M + MLP. with special sequances
Gamma magnitute
Gammaa magnitude
Gamma magnitude
Gammaa magnitude nnggt
0.05
3.0
0.05
0.00-
0.00-
0.5
-0.05
0.0
-0.05
Iteration
KL0
iteration
X10
Iteration
x20
Iteration
Figure 18: Evolution of 7 (t) (as defined in Proposition during training, This figure is identical to Figure 16
except that the setting considered is that of F
training the attacked model from scratch on a set of 20000 randomly chosen CIFAR-IO train examples, (ii) generating poisonous noise added to random subset of 10000 train examples using an adapted version of the Gradient Matching method [18] provided in bttttts:///// //gi thub com/ JonasGeiping/ poisoning- -oriiinng-griiid ent cant-maten mout-matching. and (iii) retraining the model on the 30000-examples poisoned train consisting of the original 10000 examples used for poison generation in their clean form and in their poisoned form, as well as the remaining 10000 original examples. Due to computational limitations, the poison generation process chosen test instances, and the poisoning effect carried over to the entire CIFAR-10 test set.
targeted to disrupt the classification of 3000 randomly
To allow for poisoning of the entirety of the test set, we adapted the Gradient Matching method by 5000 examples were used to poison the
strategically partitioning the poisoning 1000 correctly-classifeed test instances for which the original model's loss was the highest, and the remaining 5000 examples were used to poison the remaining 2000 test instances. Additionally, in order to make poisoning more precise we further split the poisoning examples into groups such that the noise trained for each group's 's examples targets 50 test instances and ignores the rest. Our adapted approach also included: (a) reshaping the CIFAR-10 10 image input into compatible sequence format, (b) introducing regularization that encourages the last elements an injected noise sequence to be relatively large [S] and (c) using the untargeted- www.geeeddcross-eee crwss-oooooooooo cotso-ettoooooyy target criterion and pbaach value of 500. Apart from the above adaptations, all hyperparameters were kept at their default values.
The SSM-based S4 neural network adheres to the implementation provided in /attps://gite com/ httr:/stteessacee///aee a4 utilizing the "minimalist S4" configuration available in s4d. py and s4.py. The SaMeb Mamba-2 neural network is an adaptation of the minimal implementa- tion provided in h/ttttss//giiitt ghub. com/ tommy /p 1atmmyiimmmmma22mmmm mwmmaaammaaaaaaaaam.aaaaaaaaaa mimmminini minimal The SSM-based LRU neural network is python adaptation of the JAX-implementation provided in https://githu: thub. com/ We trained all models using the Adam optimizer and the CosineAnnealingla scheduler over 100 epochs. To ensure the models before and after poisoning were comparable, we kept training the latter until reaching the training loss of the former (but no longer than 300 total epochs). Table details the hyperparameters used for each of the models.
"Reegllarzztionn comprised weight decay 32 applied to the noise entries corresponding to the ith row of
input image across all three channels, where E [32] (recall that CIFAR- 10 images are of size 3 x 32 x 32).
86

---

S5M
55M,
5SM MLP,
SSM MLP., with special sequences
Garmma magnitude
0.05
without special sequences
Ganina maanituuk
with special Sequences
Gamma magnituda
0.05
without special sequences
Gamma magnitudk
0.00
0.00
-2
-0.05
.0.05
0.50
Iteration
x10*
Iteration
Iteratoo
x10
Iteration
x30"
Figure 19: Evolution of (0) (as defined in Proposition during training. This figure is identical to Figure 16
except that the setting considered is that of Figure
Table 4: Standard deviations of the quantities presented Table
For further details see Table I and Appen-
dices 1.2 and 1.2
Setting
Without special sequences
With special sequences
Per Theorem
8.2 x 10-5
3.54 x 10-3
Standalone SSM beyond Thcorem 1
0.195 1.88 x 10-3
9.56 3.83 x 10-2
SSM in non-linear neural network
Table 5: Standard deviations of the quantities presented in Table 3
For further details see Table and Appen-
dices 1.2 and 1.2
Setting
Without special sequences
With special sequences
Per Theorem
2.71 x 10-4
1.69 10-4
Standalone SSM beyond Theorem
4.3 10-2
0.635
SSM in non-linear neural network
4.67 x 10
1.99 x 10-2
Table 6: Demonstration of clean-label poisoning of SSMs in real-world (non mnon-synthetic) settings comprising SSM-hased neural networks consisting of the $4, Mambu-2 or LRU layers [2 [4 58 trained on the CIFAR- 10 dataset [38]. This table similar Table except that it reports the training performance of the trained models, before and after the inclusion of cleanly labeled poisonous examples. Notice that across all experiments, the models' training performance remains consistent before and after the inclusion of cleanly labeled poisonous examples. Consequently, the drop test performance reported Table 2 cannot be attributed to change in training performance. For further details see Table 2 and Appendices] and L.3
SSM-based NN
Loss without with poisoning
Accuracy without / with poisoning
$4
0.316/0.311 6.59 x 10-2 2 6.59 x 10-2
88, 88.6% / 38.7%
Mamha-2
97.9% 99.8% 89.1% 990%
LRU
0.334/ 0.299
Table 7: Standard deviations of the quantities presented in Table 2
For further details see Table and Appen-
dices and
SSM-based NN
Loss without with poisoning
Accuracy without with poisoning
Noise tail size
$4 24
1.47 10 1.71 10-2
0.29% 0.18%
1.64 10-2
Mamba-2 14
3.97 x 10 4.38 10-2
1.32% 0.67%
10-2 5.52 10-2
I.RU 58
4.76 10 2.96
10
0.71% 0.53%
Table 8: Standard deviations of the quantities presented in Table 6
For further details see Table fand Appen-
dices 1.3 and J.3
SSM-based
Loss without with poisoning
Accuracy without with poisoning
S4 24
1.25 10 1.35 x 10
0.45% 0.61%
Mamba-2
14
1.95 10 - 1.98 x 10
0.75% 0.68%
LRU 58
0.62 10 0.5 10-2
2.4% 1.76%
87

---

Table 9:
Types of sequences used in dynamics experiments (Figures to the non-zero indices for each sequence type.
8
Last two columns (right) indicate
Sefting
Length
Baseline indices
Special indices
SSM / SSM MLP (Figures and
6
1,2
5,
SSM SSM MLP longer (Figures P and 8
10
.,2,...,7
10
SSM higher dimension (Figures 4 to
1,2
SSM higher dimension longer (Figures
6
10
1,2,...,
Table 10: Amount of sequences each type used dynamics experiments (Figures 2
Setting
Baseline amount
Special amount
SSM (Figures 3
and
SSM + MLP (Figures 2
and SSM higher dimension (Figures to
20
8
10
Table 11: Values of sd_A, sd_B_c and diff used in the dynamics experiments (Figures to
Setting
sd_A
sd_B_C
diff
SSM (Figures and
10
10-2
0.05 x exp 1o (sd_A)
SSM longer (Figures and
10 33
5 x 10-2
0.05 x 22p lo (sd_A)
SSM MLP (Figure
10
10-2
0.05 exp(0.5 1 (sd_A)
SSM + MLP longer (Figure
10
0.05 x exp(2 2 lo [d__)
SSM higher dimension (Figures to
10
0.05 exp 2 (sd_AA
SSM higher dimension longer (Higures to
10
0.05 x exp log
Table 12: Base learning rates used in dynamics experiments (Figures to Last two columns (right) indicate the base learning rate used in the experiments without the addition of "special" sequences and with their addition respectively.
Setting
Without special sequences
With special sequences
SSM (Figures and
0.01
0.01
SSM longer (Figures and
0.01
0.01
SSM MLP (Figures and
0.01
0.001
SSM + MLP longer (Figures and
0.01
x 10-5
SSM higher dimension (Figures to
0.01
0.001
SSM higher dimension longer (Figures
es to
0.001
0.001
Table 13: Values of sd_A and diff used in the experiments of the first poisoning setting (Tables and
Setting
ad_A
diff
Per Theorem
(Table
10-3
0.05 exp (sd
Per Theorem
longer (Table
5 x 10-3
0.05 (10 log (sd_A)
Table 14: Timestamps simulated for the experiments of the first poisoning setting (Tables and 3 The timestamps used for each experiment are the endpoints of intervals obtained by evenly partitioning the range (0, Lass_timmetaat into timestamp_ant amount segments.
Setting
last, timestamp
timestamp_and amount
Per Theorem
(Tblle
w/o special
10
1000
Per Theorem
(Table
w/ special
10a
1000
Per Theorem
longer (Table 3 w/o special
10
10000
Per Theorem
longer (Table w/ special
107
1000
88

---

Table 15: Types sequences used the experiments of the second and third poisoning settings (Tables and Last columns (right) indicate non-zero indices for each sequence type.
Setting
Length
Baseline indices
Special indices
2dd and 3dd settings of Table
6
1,2
2nd and 3rd settings of Table
10
1,2,-...7
Table 16: Amount of sequences of each type used in in the experiments of the second and third poisoning settings (Tables Tand
Setting
Baseline amount
Special amount
Standalone SSM beyond Theorem (Tables and
SSM in non-linear neural network (Tables] and
20
Table 17: Values ad_A, sd_B_C and diff used the experiments second and third poisoning settings (Tables and 3).
Setting
sd_A
sd_B_C
diff
Standalone SSM beyond Theorem (Table
10
10
0.05 x exp(5 logio (nd
Standalone SSM beyond Theorem longer
TTblle
10
10
0.05 x exp(3 (ad_A))
SSM in non-linear neural network (Tbble
10
10
0.05 x exp 1od
SSM in non-linear neural network longer (Table
10-3
10
10
0.05 x exp(2 logio (ad_
learning rales used in the experiments of second third poisoning settings (Tables and 3 Last two columns (right) indicate the base learning rate used in the experiments without the addition "special" sequences and with their addition respectively.
Table 18:
Setting
Without special sequences
With special sequences
Standalone SSM beyond Theorem (Table
0.01
0.01
Standalone SSM beyond Theorem longer TTblle
0.001
0.001
SSM non-linear neural network (Table
0.01
0.01
SSM non-linear neural network longer (lable
0.01
10-5
Table 19: Hyperparameters used the real- wolld poisoning experiments (Tables and 6
Model
Depth
Dropout
d_model
d_atate
Base learning rate
Weight decay
84
0.1
128
64
10-2
10-2
Mamha-2
128
10-3
10-2
LRU
10-3
x 10-2
89


Reviews:
[{"review_id": "NJIF5CpksE", "reviewer": "Reviewer_Y3v5", "summary": "The highlights a challenge in the generalization of an SSM model. The paper demonstrates that the conventional argument of SSM can be generalized, and that implicit bias can be challenged, while also illustrating how clean label poisoning can compromise the model's generalization capabilities. The paper's conclusions are supported by rigorous theoretical analysis.", "questions": "Please refer to the weakness section.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\n\n1. The paper provides a detailed theoretical analysis behind each of the hypotheses and backs them with proofs.\n2. This is the first work to highlight an essential problem of SSM by successfully showing a clean-label poisoning attack on SSM.\n3. The proposed method, backed by each theorem, is novel. A non-resonant linearization theorem yields two critical observations that facilitate the successful creation of a clean label poisoning attack.\n\nWeakness:\n\n1. While the paper is theoretically solid, it indeed has several experimental limitations. I appreciate the author being upfront about the scope of the work being limited; however, without further experimental validation, it is challenging to thoroughly stress-test the proposed theoretical analysis. \n\n2. Two core challenges to the generalization of the proposed method, which the authors have not mentioned, are the choice of architecture and dataset. The evaluation is only conducted on one architecture and one dataset. The experimental setting is minimal. Why not evaluate on a few state space models to show the conclusion holds true across the board, such as Mambas?\n\n3. Even with the current choice, there is no rationale behind the options presented in the result section. First, why only the SSM-S4 model? Second, in Table 2, why are only 10/20 instances being attacked? What is the challenge in attacking all the test samples, similar to any conventional adversarial attack evaluation? Also, this is not a standard way to present results. It is very confusing to look at Table 2 and see the fourth column accuracy without poison to be that low. It takes a lot of work on the reader's part to understand that these are accuracies only on the # of test samples. Furthermore, the actual accuracy of the model is not at all reported in the paper. I would appreciate more results with clarity in the presentation.", "was_revised": true, "final_justification": "I have read the responses of the authors and other reviewers. While I still hold some reservations regarding how the new experiments will look, I am fine with accepting the paper and have increased my score.", "rebuttal": "Thank you for highlighting that our paper “provides a detailed theoretical analysis behind each of the hypotheses” and “is the first work to highlight an essential problem of SSM by successfully showing a clean-label poisoning attack”! We address your reservations below. If you find our responses satisfactory, we would greatly appreciate it if you would consider raising your score.\n\n>While the paper is theoretically solid, it indeed has several experimental limitations. I appreciate the author being upfront about the scope of the work being limited; however, without further experimental validation, it is challenging to thoroughly stress-test the proposed theoretical analysis.\n\n>Two core challenges to the generalization of the proposed method, which the authors have not mentioned, are the choice of architecture and dataset. The evaluation is only conducted on one architecture and one dataset. The experimental setting is minimal. Why not evaluate on a few state space models to show the conclusion holds true across the board, such as Mambas?\n\nThank you for highlighting that our paper is theoretically solid, and that we were upfront about the scope of its experiments being limited.  We would like to note, however, that to our knowledge, compared to formal theoretical papers such as ours, the scope of our experimentation is rather broad.  Nonetheless, following your comments, we are conducting experiments in additional real-world (non-synthetic) settings, including Mamba2 and LRU architectures. While these experiments are still ongoing, all of their results thus far fully align with those of S4 on CIFAR-10. We will add the experiments to the camera-ready version of the paper. Thank you!\n\n>Even with the current choice, there is no rationale behind the options presented in the result section. First, why only the SSM-S4 model? Second, in Table 2, why are only 10/20 instances being attacked? What is the challenge in attacking all the test samples, similar to any conventional adversarial attack evaluation? Also, this is not a standard way to present results. It is very confusing to look at Table 2 and see the fourth column accuracy without poison to be that low. It takes a lot of work on the reader's part to understand that these are accuracies only on the # of test samples. Furthermore, the actual accuracy of the model is not at all reported in the paper. I would appreciate more results with clarity in the presentation.\n\nThank you for the feedback.\n\nRegarding real-world (non-synthetic) experimentation only with S4, please see our response above on experiments in additional settings, including Mamba2 and LRU.\n\nWith regards to your comments surrounding Table 2:\nTo our knowledge, in the area of adversarial machine learning, it is common to employ clean-label poisoning for attacking a small number of specific test instances ([1, 2]). In this case the overall test accuracy is barely impacted by the attack, which is precisely the intent of the attacker (their desire is for the attack to go undetected after training, when test accuracy is being evaluated).  While this regime is (to our knowledge) common, we understand your point about it being different from the regime of our theory and synthetic experiments (namely, the regime in which clean-label poisoning leads to significant deterioration in the overall test accuracy).  Accordingly, we are now extending our real-world (non-synthetic) experiments to include attacks on more test instances. While this extension is still ongoing, initial results confirm that the overall test accuracy indeed deteriorates.  In the camera-ready version of the paper, Table 2 will report overall test accuracies.  We believe this change will address your request for more clarity in its presentation.  Thank you very much!\n\n---\n\n**References**\n\n[1] Huang et al. “MetaPoison: Practical General-purpose Clean-label Data Poisoning”\n\n[2] Geiping et al. “Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching”"}, {"review_id": "a3JM8sNedc", "reviewer": "Reviewer_wYKm", "summary": "This paper prove that while implicit bias leads to generalization under many choices of training data, there exist special examples whose inclusion in training completely distorts the implicit bias, to a point where generalization fails.", "questions": "See Strengths And Weaknesses*", "limitations": "See Strengths And Weaknesses*", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1) This paper proposes a formal proof of clean-label poisoning in SSMs, extending the understanding of implicit bias in overparameterized models.\n2) The use of advanced tools such as the non-resonance linearization theorem brings fresh insights into training dynamics.\n3) The dynamical characterization of gradient flow for SSMs is carefully derived and shows under what conditions greedy low-rank learning occurs.\n4) Theorems clearly illustrate the existence of cases where adding cleanly labeled sequences induces severe generalization failures.\n5) Experiments range from controlled synthetic setups to real-world settings (e.g., CIFAR-10 with S4 models), confirming the theoretical claims.\n\nWeaknesses and Suggestions:\n1) While theoretically elegant, it is not always clear how easily an attacker could craft or inject sequences with the required properties in practice. I suggest including more concrete examples or algorithmic procedures to illustrate the feasibility and cost of such attacks in realistic scenarios.\n\n2) While the experiments are diverse, most are conducted with small SSM dimensions and short sequence lengths due to computational challenges. It remains unclear whether the observed phenomena would persist in large-scale SSMs used for long-context language modeling. \nI understand the author said \"due to vanishing gradients, maintaining reasonable run-times in experiments with near-zero initialization necessitated a relatively small scale (in terms of, e.g., SSM dimension and training sequence length). Addressing these limitations is an important set of directions for future work.\"  I suggest add some experiments using other initialization methods to experiment on large-scale SSMs.\n\n3) Although the paper establishes the existence of clean-label poisoning vulnerabilities, it does not propose mitigation strategies or even partial defenses. For practitioners, it is unclear what safeguards could be applied to SSM training pipelines.\nInclude at least a short discussion of potential countermeasures or research directions for making SSMs more robust in practice.", "was_revised": true, "final_justification": "Overall, I think this paper is well written. But keep some concerns on experimental results with large-scale SSMs. \n\nSo, my final suggestion is 'Borderline accept'", "rebuttal": "Thank you for highlighting the merits of our theory, in particular that it “extend[s] the understanding of implicit bias in overparameterized models” and “brings fresh insights into training dynamics”! Thank you also for noting that our “experiments are diverse,” “confirming the theoretical claims”. We address your reservations below.  If you find our responses satisfactory, we would greatly appreciate it if you would consider raising your score.\n\n>While theoretically elegant, it is not always clear how easily an attacker could craft or inject sequences with the required properties in practice. I suggest including more concrete examples or algorithmic procedures to illustrate the feasibility and cost of such attacks in realistic scenarios.\n\nOur theoretically established cleanly labeled poisonous examples require a teacher (labeling function) in order to be generated, thus are not applicable as-is to most practical scenarios.  However, our real-world (non-synthetic) experiments demonstrate that clean label poisoning can be achieved via addition of human-imperceptible noise whose structure is inspired by our theory. While we defer to future work a thorough empirical exploration of clean-label poisoning techniques born from our theory, we are adding more experiments to the camera-ready version of the paper—see response below.\n\n>While the experiments are diverse, most are conducted with small SSM dimensions and short sequence lengths due to computational challenges. It remains unclear whether the observed phenomena would persist in large-scale SSMs used for long-context language modeling. I understand the author said \"due to vanishing gradients, maintaining reasonable run-times in experiments with near-zero initialization necessitated a relatively small scale (in terms of, e.g., SSM dimension and training sequence length). Addressing these limitations is an important set of directions for future work.\" I suggest add some experiments using other initialization methods to experiment on large-scale SSMs.\n\nFollowing your feedback, we are conducting experiments in additional real-world (non-synthetic) settings, including large-scale SSMs in Mamba2 and LRU architectures. While these experiments are still ongoing, all of their results thus far fully align with those of S4 on CIFAR-10. We will add the experiments to the camera-ready version of the paper. Thank you!\n\n>Although the paper establishes the existence of clean-label poisoning vulnerabilities, it does not propose mitigation strategies or even partial defenses. For practitioners, it is unclear what safeguards could be applied to SSM training pipelines. Include at least a short discussion of potential countermeasures or research directions for making SSMs more robust in practice.\n\nProposition 1 in our paper suggests that training dynamics may be an informative tool for detecting the existence of clean-label poisoning attacks (a capability that can facilitate various countermeasures, the simplest being to prevent deployment of the compromised model). Namely, Proposition 1 implies that if the factor $\\gamma^{(0)}(\\cdot)$ is small throughout training, then generalization (with a low dimensional teacher) takes place, whereas if $\\gamma^{(0)}(\\cdot)$ is not small, then generalization may not take place. Figures 16 to 19 (in Appendix I) empirically demonstrate this phenomenon for a standalone SSM as well as one included in a non-linear neural network. A very promising avenue for future research is to extend this observation to practical scenarios, i.e., to identify, for SSMs in practical scenarios, properties of training dynamics that characterize when clean-label poisoning takes place.\n\nAn expanded version of the above discussion will appear in the conclusion of the camera-ready version of the paper. We view this as a valuable addition to the text. Thank you very much for raising the matter!"}, {"review_id": "EqRB1pJWfD", "reviewer": "Reviewer_XKJx", "summary": "This paper presents an interesting theoretical study stating the susceptibility of clean-label poisoning in distilling structured state space models. The study starts by analyzing and stating the gradient flow convergence in Proposition.1, known as the analysis of dynamical characterization of SSM . Furthermore in Theorem.1, this study shows both bright and down side of distilling from a low-rank teacher model: training a student SSM with a low dimensional teacher SSM can improve implicit bias, which leads to generalization. However if we further add a training time series sample with its last entries carrying large norms, the distilled SSM may end up with being overfitted to the training data and show poor generalization performances.", "questions": "Please discuss if the findings can be used over other model architectures like SSM. Please also provide discussions about how the findings can be used to improve generalization performances.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strong points of this paper**\nThis paper presents a novel and interesting finding: distilled SSM can present poor generalization performances if teacher SSMs have a low-ranked structure, even though the training data samples used are free from poisoning. This study shows the generalization limitation of knowledge distillation in SSMs. I really appreciate the solid theoretical reasoning step by step presented in this paper. \n\n**Weakness of this paper**\n\nIt seems this paper focuses on exclusively on SSMs. I don't know if the conclusion made in this paper can be also applied to other model architectures like transformers (probably it can, but needs further discussions). This, somehow, may limit the practical impact of this work.\nFurthermore, I'd be curious, if the findings unveiled in this paper can be also used to improve the generalization performance. For example, what should we do to ensure the generalization capability of distilled model? Do we need to choose a high-rank teacher or we need to check the training data samples for distillation?", "was_revised": true, "final_justification": "Thanks for the responses and I have also gone through the rebuttal messages to other reviewers' comments. I would recommend to accept this paper as my final justification.", "rebuttal": "Thank you for highlighting that our findings are novel and interesting, and for appreciating their solid theoretical reasoning!  We address your reservations below.\n\n>It seems this paper focuses on exclusively on SSMs. I don't know if the conclusion made in this paper can be also applied to other model architectures like transformers (probably it can, but needs further discussions). This, somehow, may limit the practical impact of this work. \n\nClean‑label poisoning has been demonstrated empirically in several non-SSM neural architectures, most notably in CNN-based image classifiers (see, e.g., [1, 2, 3, 4, 5]). Theoretically, clean-label poisoning was—to our knowledge—only explored in convex settings such as linear or kernel models ([6, 7]), or in settings where poisonous examples come instead of (rather than in addition to) original training examples ([8, 9, 10]). To our knowledge, there are no formal guarantees for clean-label poisoning via added examples in Transformers or other attention-based architectures. Extending our analysis to account for such architectures is an ambitious and interesting direction for future work.\n\n>I'd be curious, if the findings unveiled in this paper can be also used to improve the generalization performance. For example, what should we do to ensure the generalization capability of distilled model? Do we need to choose a high-rank teacher or we need to check the training data samples for distillation?\n\nWith regards to improving generalization in practical scenarios, Proposition 1 in our paper suggests that training dynamics may be an informative tool for detecting the existence of clean-label poisoning attacks (a capability that can facilitate various countermeasures, the simplest being to prevent deployment of the compromised model). Namely, Proposition 1 implies that if the factor $\\gamma^{(0)}(\\cdot)$ is small throughout training, then generalization (with a low dimensional teacher) takes place, whereas if $\\gamma^{(0)}(\\cdot)$ is not small, then generalization may not take place. Figures 16 to 19 (in Appendix I) empirically demonstrate this phenomenon for a standalone SSM as well as one included in a non-linear neural network. A very promising avenue for future research is to extend this observation to practical scenarios, i.e., to identify, for SSMs in practical scenarios, properties of training dynamics that characterize when clean-label poisoning takes place.\n\nAn expanded version of the above discussion will appear in the conclusion of the camera-ready version of the paper.  We view this as a valuable addition to the text. Thank you for your comment!\n\n---\n**References**\n\n[1] Shafahi et al. “Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks”\n\n[2] Zhu et al. “Transferable Clean-Label Poisoning Attacks on Deep Neural Nets”\n\n[3] Zhao et al. “Clean-Label Backdoor Attacks on Video Recognition Models”\n\n[4] Huang et al. “MetaPoison: Practical General-purpose Clean-label Data Poisoning”\n\n[5] Aghakhani et al. “Bullseye Polytope: A Scalable Clean-Label Poisoning Attack with Improved Transferability”\n\n[6] Suya et al. “Model-Targeted Poisoning Attacks with Provable Convergence”\n\n[7] Blum et al. “Robust Learning Under Clean-Label Attack”\n\n[8] Mahloujifar et al. “Can Adversarially Robust Learning Leverage Computational Hardness?”\n\n[9] Mahloujifar et al. “The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of \nMeasure”\n\n[10] Gao et al. “Learning and Certification under Instance-targeted Poisoning”"}, {"review_id": "ovf0zbkIOM", "reviewer": "Reviewer_gug3", "summary": "The paper proves that a single, correctly-labeled “special” sequence can force a structured state-space model trained with gradient descent to memorize rather than generalize, revealing a provable clean-label poisoning vulnerability. It derives this result via a novel polynomial-ODE analysis of the training dynamics and corroborates it with S4 experiments on CIFAR-10 showing a >40× error spike when <12 % of the data are poisoned.", "questions": "### Questions for the Authors\n1. Does the attack persist under HiPPO or identity initializations?  \n2. What happens when \\(B,C\\) are learned with separate learning rates?  \n3. How does the phenomenon change with SGD + momentum or Adam?  \n4. Minimum poison fraction needed for million-sample datasets?  \n5. Can analogous “suffix-heavy” inputs poison language/audio tasks without trailing zeros?  \n6. Do weight decay or spectral-norm regularization mitigate the effect?  \n7. Are attention-plus-SSM hybrids (e.g., Mamba) equally vulnerable?  \n8. Could monitoring the low-rank signal \\(\\gamma^{(0)}(t)\\) act as an early-warning defense?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. **Fills a theoretical gap** – extends clean-label poisoning theory to non-convex SSMs.  \n2. **Mechanistic insight** – ODE factorization offers an intuitive, entry-wise view of dynamics.  \n3. **Finite-sample realism** – avoids infinite-data assumptions of earlier implicit-bias work.  \n4. **Balanced analysis** – provides both success and failure results under the same framework.  \n5. **Concrete experiments** – ties theory to measurable failure on a real SSM benchmark.\n\n### Weaknesses \n- Low-dimensional teacher & diagonal \\(A\\) may not reflect practical high-dim/banded SSMs.  \n- Fixed \\(B,C\\) matrices – real models usually learn these.  \n- Near-zero initialization – differs from HiPPO/identity inits.  \n- Special input padding (trailing zeros) – unnatural for real data.  \n- Gradient-flow analysis – ignores discrete optimizers, momentum, Adam, etc.  \n- Experiments are small-scale; no language or large data regimes.", "was_revised": true, "final_justification": "From my original reading of the paper as after reading others reviews I believe my original assessment was correct. I still hold that this paper should be an acceptable.", "rebuttal": "Thank you for highlighting various strengths of our theory and experiments!  \n\nWhile our paper avoids restrictive assumptions made in prior work (e.g., it avoids infinite data assumptions, as you have mentioned), it is still limited in different ways, including those you mention. We have made a significant effort to be fully transparent about the limitations of the paper, throughout the text and in a dedicated limitations section (Section 5).\n\nBelow we address your questions by their enumeration.\n\nQ1 + Q3:\n\nOur proof of clean-label poisoning does not apply to HiPPO or identity initializations, nor does it apply to SGD with momentum or Adam optimizers. However, our real-world (non-synthetic) experiment demonstrates clean-label poisoning for an SSM-based S4 neural network trained using standard near-identity initialization and AdamW optimization. Extending our proof to account for further initializations and optimizers is an important direction for future work.\n\nQ2:\n\nOur proof of clean-label poisoning requires B and C to either be fixed throughout training (Assumption 2), or be learned with a very small learning rate (Appendix B). However, our real-world (non-synthetic) experiment, as well as most of our synthetic experiments, demonstrate clean-label poisoning where B and C are learned with the same learning rate as A. Extending our proof to account for A, B and C learned with the same learning rate is an important direction for future work.\n\nQ4:\n\nOur theory does not imply what is the minimum amount of cleanly-labeled poisonous examples that can facilitate a successful attack in a practical large-scale scenario. Our real-world (non-synthetic) experiment demonstrates successful attacks with various amounts of cleanly-labeled poisonous examples, but we do not know what is the minimum amount with which this is possible. It is an interesting direction to explore.\n\nQ5:\n\nIn practical scenarios we typically do not have a teacher (labeling function) at hand, and the way in which clean-label poisoning can be achieved is addition of imperceptible noise to training examples. Our real-world (non-synthetic) experiment demonstrates this on a vision task (CIFAR-10), with noise whose structure is “suffix-heavy” and without trailing zeros.\n\nQ6:\n\nAnalyses of implicit bias, i.e., of implicit regularization, typically consider training objectives that do not include explicit regularization (see, for example, [1, 2]). The rationale behind this is that explicit regularization co-mingles with implicit regularization, rendering it difficult to associate phenomena with the latter. Indeed, in the extreme case of very strong explicit regularization (e.g., L2 regularization with a very large coefficient), the training objective will admit a single minimizer, and implicit regularization will have no impact on the solution to which optimization converges.\nHaving said the above, studying implicit regularization does make sense in cases of weak to moderate explicit regularization. Indeed, our real-world (non-synthetic) experiment accounts for such explicit regularization. Extending our theory to do so is an interesting direction for future work.\n\nQ7:\n\nWhile we do not provide a theoretical answer to this question, we are extending our real-world (non-synthetic) experiment to include additional neural architectures, in particular Mamba. The evaluation of Mamba is still ongoing, but thus far, all of its results fully align with those of S4. We will add the extended experimentation to the camera-ready version of the paper. Thank you for raising this question!\n\nQ8:\n\nThis is an excellent question! As you suggest, our Proposition 1 implies that training dynamics may be an informative tool for detecting the existence of clean-label poisoning attacks (a capability that can facilitate various countermeasures, the simplest being to prevent deployment of the compromised model). Namely, Proposition 1 implies that if the factor $\\gamma^{(0)}(\\cdot)$ is small throughout training, then generalization (with a low dimensional teacher) takes place, whereas if $\\gamma^{(0)}(\\cdot)$ is not small, then generalization may not take place. Figures 16 to 19 (in Appendix I) empirically demonstrate this phenomenon for a standalone SSM as well as one included in a non-linear neural network. A very promising avenue for future research is to extend this observation to practical scenarios, i.e., to identify, for SSMs in practical scenarios, properties of training dynamics that characterize when clean-label poisoning takes place.\n\nAn expanded version of the above discussion will appear in the conclusion of the camera-ready version of the paper. We view this as a valuable addition to the text. Thank you for the question!\n\n---\n**References**\n\n[1] Gunasekar et al. \"Implicit Regularization in Matrix Factorization\"\n\n[2] Soudry et al. \"The Implicit Bias of Gradient Descent on Separable Data\""}]

Author rebuttal:

Meta-review: This paper is the first to identify a fundamental problem of SSMs by demonstrating a clean-label poisoning attack. It provides detailed theoretical analysis using mathematical techniques such as Polynomial-ODE analysis and a non-resonant linearization theorem. In addition, convincing experimental results are presented, and the authors further strengthen their case in the rebuttal by adding results on additional architectures.

Overall, this is a very solid paper with strong theoretical foundations. All reviewers expressed positive opinions about this work.
Decision: Accept (spotlight)