The Implicit Bias of Structured State Space Models Can Be Poisoned With Clean Labels

Thank you for your review. Below we address each of your points. In light of our response, we would greatly appreciate it if you would consider raising your score.

The result shown in this paper comes from an extremely contrived example and the reviewer has strong concerns regarding its practical significance.

Please note that (as stated in the introduction, line 67) our theory comprises two main results:

1. Dynamical characterization (Section 3.1): This result applies to a very broad range of settings (including ones where the SSM is trained as part of a non-linear neural network). Dynamical characterizations have proven to be central to the theory of various deep learning models (see, e.g, [1,2,3]), and we believe our dynamical characterization may similarly become central to the theory of SSMs.
2. Demonstration of clean-label poisoning (Section 3.2): This theoretical demonstration indeed applies to a specific setting. Its purpose is to prove existence of clean-label poisoning in SSMs, similarly to numerous existence proofs in deep learning theory (see, e.g, [4,5,6]). Moreover, at least part of the analyzed setting—namely, the cleanly labeled training example leading generalization to fail—is expected to be specific, as in practice, coming up with such examples requires substantial computational efforts (see, e.g., [7,8,9,10]). Following your feedback, we will generalize other aspects of the analyzed setting, in particular the training examples with which generalization succeeds—see details below.

Theorem 1 states that the learned student SSM generalizes "under various choices of training sequence" (line 258), the truth is these training sequences are $\lbrace p_i\mathbf{e_1},p_i\rbrace_{i=1}^n$, where $p_i∈\mathbb{R}$ (line 857, Definition 2 in Appendix), i.e., the input sequences to the teacher SSM are the same up to some scaling. Since the SSM to be learned is linear, these $n$ training sequences are effectively single sequences.

Note that Theorem 1 applies to a generic (odd) $\kappa$, thus it actually implies generalization under any training sequence $\mathbf{e}_j$ where $j$ is odd and no greater than $\kappa - 6$. Moreover, Theorem 1 can easily be extended to establish generalization under any set of training sequences with positive entries that hold zeros in their last two entries. We are now adding this extension to the paper.

It is not a big surprise if student SSM generalizes when this single training trajectory is crafted to guide the GF to the generalizing solutions, and then it is even less surprising if another crafted training trajectory is added to steer GF to other solutions. There are effectively only two training trajectories, after all.

We respectfully disagree, and believe there may be a misunderstanding.

First of all, showing that a training sequence such as $\mathbf{e}_1$ leads to generalization is non-trivial, and requires our dynamical characterization (Section 3.1). Secondly, we cannot “add a trajectory” to GF, we can only add a training sequence, and that leads to the GF trajectory changing in a highly non-trivial manner. Indeed, in Theorem 1, adding the training sequence $\mathbf{x}^\dagger$ changes the GF trajectory in a way that is highly complex (e.g., as discussed in the proof sketch of Theorem 1, it leads the trajectory to encounter saddle points)—far more complex than “adding” a trajectory associated with $\mathbf{x}^\dagger$. Finally, there are not only two training trajectories: any scaling of a training sequence, or a slight shift in the initialization (our proof accounts for infinitely many initializations), lead to highly non-trivial changes in the GF trajectory.

We fear you may be underestimating the complexity of the correspondence between training sequences and the GF trajectories they lead to. As the proof sketch of Theorem 1 emphasizes, this correspondence is extremely non-trivial.

Another reason this example is contrived is that there is no persistence of excitation (Green&Moore, 1986) in the input sequence used for training, which is fundamentally needed to identify linear systems.

Here too, we believe there may be a misunderstanding.

When studying implicit bias in a teacher-student setting, the whole point is that the training data will not support identifying the teacher. Rather, there should be multiple solutions that fit the training data, some generalize (recover the teacher), while others do not. The question of interest is then whether there is some implicit bias leading to generalization. Please let us know if this point is not clear and we will happily elaborate.

Thank you for your review, and for highlighting the solidity of our theory and the clarity of our writing. Thank you also for your constructive suggestions! We address your comments and questions below.

The assumptions in Theorem 1 are overly restrictive, particularly as the structures of $A^*$, $B^*$, and $C^*$ seem to be very simple, and there is a lack of detailed explanation as to why such a simplified setup is justified in this context.

The setting of Theorem 1 is indeed specific and relatively simple. The importance of the theorem is that it formally proves existence of clean-label poisoning, analogously to various existence proofs in deep learning theory (see, e.g, [1,2,3]).

Despite the specificity and relative simplicity of its setting, proving Theorem 1 is highly non-trivial. Indeed, our proof spans nearly 40 pages (Appendix C), and employs advanced tools from dynamical systems theory (see proof sketch, lines 288-323). It is nonetheless possible to extend Theorem 1 in several ways, including accommodation of other values for $A^*$, $B^*$ and $C^*$. We are now adding these extensions to the paper. Thank you for raising the matter!

Regarding the special sequence data, Theorem 1 only provides an existence result without specifying a concrete construction method or offering a more detailed characterization, making it difficult for me to understand why the introduction of these clean data points leads to a failure in generalization.

We refer as special sequences to ones in which the last elements are relatively large. As discussed in the interpretation of our dynamical characterization (Section 3.1), such sequences can disrupt greedy low rank learning—a sufficient condition for generalization with a low dimensional teacher. This is the intuition behind Theorem 1: the added cleanly labeled sequence $\mathbf{x}^\dagger$ has a large penultimate element, thus disrupts greedy low rank learning, which in turn can be shown to fail generalization. Following your feedback, we will make this point clearer in the text. Thank you!

The experiments in the paper seem to be conducted solely on synthetic datasets, which greatly limits their persuasiveness. The authors should consider using more real-world datasets to demonstrate the generality of the phenomenon they describe.

We are now adding to the paper experiments demonstrating clean-label poisoning of SSMs in real-world scenarios. Thank you for the feedback!

Thank you for your review, and for highlighting the strength of our theory and experiments!

Thank you for your review, and for highlighting the strength of our theory and experiments, as well as the clarity of our writing. Thank you also for your constructive suggestions! We address your comments below.

Is it possible to separately decompose and plot $γ^{ (0) }(t)$ along with Figure 2? If so, I think it could give a more concrete explanation to aid the Interpretation part of Section 3.1.

We are adding to the paper plots of $\gamma^{ (0) } ( t )$ in the context of Figure 2. Thank you for the suggestion!

Can the authors come up with a measure to qualitatively distinguish between the scenarios of the (leftmost) and (second) subplot of Figure 2? I'm aware that this might be an abrupt question, but it could be seen that the (second) subplot does not correspond to the case of 'not greedy', maybe close to 'less greedy' (especially for the case of Figure 4 in the supplementary material).

For assessing the extent to which greedy low rank learning occurs, one may apply to the state transition matrix $A$ the measure of effective rank, which can be seen as a continuous version of rank [1]. For a given teacher model, the stronger the effect of greedy low rank learning is, the lower the effective rank throughout learning will be. This becomes apparent when plotting the effective rank in the context of Figures 2 and 4. Following your feedback, we are adding such plots to the paper. Thank you very much for the suggestion!

(Slightly related to 2.) Adding results of more individual runs/seeds for Figure 2 could more strengthen the authors' explanation. Could be an indirect way to show this, but showing only one trial as confirmation to the theory seems less sufficient.

We are adding to the appendix additional demonstrations of our dynamical characterization, obtained with different random seeds. Thank you!

Out of the scope of the teacher-student setting (i.e. in the real-world scenario), what could be the interpretation or example for $(x^\dagger,y^\dagger)$ of Theorem 1 that harms the student from generalization?

In real-world scenarios, it is often very difficult to interpret cleanly labeled training examples that lead generalization to fail. Indeed, coming up with such examples typically requires substantial computational efforts (see, e.g., [2,3,4,5]). While our theory identifies sequences in which the last elements are relatively large to be ones that alter the implicit bias (Section 3.1), we prove that such sequences can lead generalization to fail only in teacher-student settings, not in real-world scenarios. To gain insight into the kind of sequences leading generalization to fail in real-word scenarios, we are adding to the paper real-world experiments demonstrating clean-label poisoning of SSMs. Thank you for raising the matter!

Adding a short discussion of the limitations with respect to the corresponding results from the supplementary materials would make the paper more complete. In addition, could the authors provide more experimental results beyond the limitation setting made in the supplementary materials (i.e., results for the teacher dimension greater than 2)? Providing these additional results is not necessary, and I do not want this point to be an extensive burden. But I believe that effectively showing such limitations is indeed important from a completeness perspective.

We are adding to the appendix an account of its limitations, as well as additional experiments (e.g., with a teacher of dimension greater than two, and with real-world data).

References

[1] O. Roy and M. Vetterli, "The effective rank: A measure of effective dimensionality," 2007 15th European Signal Processing Conference, Poznan, Poland, 2007, pp. 606-610.

[2] Huang, W. Ronny, et al. "Metapoison: Practical general-purpose clean-label data poisoning." Advances in Neural Information Processing Systems 33 (2020): 12080-12091.

[3] Geiping, Jonas, et al. "Witches' brew: Industrial scale data poisoning via gradient matching." arXiv preprint arXiv:2009.02276 (2020).

[4] Shafahi, Ali, et al. "Poison frogs! targeted clean-label poisoning attacks on neural networks." Advances in neural information processing systems 31 (2018).

[5] Aghakhani, Hojjat, et al. "Bullseye polytope: A scalable clean-label poisoning attack with improved transferability." 2021 IEEE European symposium on security and privacy (EuroS&P). IEEE, 2021.

I apologize for the late response. First of all, thank you for clarifying my questions with additional experiments. After reading the comment from the authors, including the additional results and the updated manuscript, I'm glad to see that the newly added results stay align to the authors original claims. I have updated my score accordingly.