Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper extends previous work on linear state space models (SSM), where the state transition matrix is fixed to be a highly structured _HiPPO_ matrix, which has provably beneficial properties for memorizing long-term information from continuous-time signals. The main contribution of the paper is regarding the computational aspect of the model. Namely, a novel approach is proposed for computing the convolutional kernel associated to the discretized SSM unrolled over time. This is done by first showing that the state transition matrix can be decomposed as the sum of a normal (i.e. diagonalizable with orthonormal eigenvectors) and a low-rank (rank 1 or 2) matrix, and this representation is then combined with techniques from numerical linear algebra to reduce the problem to computing the Cauchy kernel (i.e. a well-studied problem). The resulting structured state space model (S3) is then placed into a deep neural network setting, and extensive experiments are carried out on various tasks, such as: 1) Long Range Arena, a benchmark collection for scalable transformers, 2) raw speech classification (length-16k audio signals), 3) generative modelling on CIFAR-10 and WikiText-103, 4) sequential image classification on sMNIST, pMNIST and sCIFAR. Overall, the model seems to perform very well on each task either performing close to SoTA or setting a new high score.
main_review: The paper seems well written both regards to clarity and citations. Contentwise, the theoretical and experimental parts are interesting and relevant. The novel contribution, which is efficient computation of the discretized convolution kernel, is highly technical with details given in the appendix, but the authors did a good job at summarizing the key ideas. On the LRA benchmark, which was originally introduced to benchmark scalable transformer variants, the model sets a new high score on all problems, outperforming transformers on their home turf. The model also outperforms competitors on a raw audio dataset, including a SoTA CNN variant specialized to audio. Overall, the performance is compelling on all considered tasks, in respect of both accuracy and efficiency.

I have just a few questions/remarks:

1) The authors mention in Section 2.2 that linear SSMs can perform poorly due to vanishing/exploding gradients. The given HiPPO matrix is given by the sum of a normal and a low-rank (i.e. NPLR) matrix, and in particular it is not unitary. I wonder then how it gets around the aforementioned problem? I expect the answer can be found by looking up the cited papers, but if there is a short answer to this, it might be good to include it in the discussion.
2) Related to the previous question, it turns out the authors only use the HiPPO matrix as an initialization (although as a very sensible one), but then the algorithm is free to learn any NPLR matrix. Is it true in general for NPLR matrices that they result in well-behaved SSMs in the previous sense, or does that only hold for a neighborhood around the HiPPO matrix? Additionally, I would be interested in what happens (e.g. how performance changes) when a) the HiPPO matrix  $\mathbf{A}$ is fixed throughout the training, and only the parameters $\mathbf{B}, \mathbf{C} \in \mathbb{R}^N$ are trainable, and b) if the model is initialized from a random NPLR matrix, but not the HiPPO?
3) Is the model able to handle multidimensional input signals $\mathbf{u}(t) \in \mathbb{R}^d$?
4) In Section 3.4, it is mentioned that a multidimensional feature map of size H is created by defining H independent copies of S3. I am wondering if it would be more efficient if these copies shared the input-to-state ($\mathbf{B}$) and state-to-state ($\mathbf{A}$) mappings, and only differed in the state-to-feature mapping ($\mathbf{C}$)? Do the authors expect this would negatively affect the results? Somehow it seems wasteful to me for each feature-coordinate $y^i(t)$ to have its own separate $N$-dimensional state representation, instead of sharing a common one (perhaps with a larger state size $N^\prime >> N$).
5) The S3 itself seems to be a linear model, which made me wonder where the nonlinearities are introduced into the deep model? Perhaps, is there an activation placed on the feature map after linearly mixing H independent copies of S3?
6) In Section 4.3 paragraph _Irregularly sampled data_, it seems what the authors really mean is a resolution change. As far as I know, irregular sampling means the data is sampled on a highly non-uniform time grid, which means that in eq.(3) the step size $\Delta_t$ would become time dependent. It looks like this might make the computation of the convolution kernel in eq.(5) a bit problematic (the discretized $\bar{\mathbf{A}}_{\Delta_t}$ matrices might not commute with eachother).
summary_of_the_review: This is a solid paper with a novel technical contribution that utilizes nontrivial insights for efficient matrix computations, and with a strong experiments section. The experiments demonstrate not only that the model can be an efficient alternative to transformers on tasks requiring long-range reasoning, but that it also shows promise as a generic sequence model that can be applied across a broad range of tasks. Overall, there are not many drawbacks of the paper for me, other than some unanswered questions in my mind.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a novel parameterization for the established state-space models (SSM), which tackles the scalability problem in linear state-space layers (LSSL) in modeling long-range dependencies for very long sequences. The proposed technique reparameterizes the structured state matrix in LSSL that allows the state to memorize the past, a key component following the continuous-time memorization theory. A complete theoretical description of this reparameterization and empirical evaluations on a diverse set of benchmarks are presented. The proposed model, S3, achieves astonishing results both in terms of performance and computational efficiency. 
main_review: The paper presents a strong and clear theory for the proposed reparameterization. Its advantages over the prior work linear state-space layers (LSSL) are explained very well theoretically and presented empirically. 
The convolutional kernel defined by LSSL is a convolutional interpretation to unrolling SSMs over time, granting parallelization to SSMs during training. The proposed model S3 resolves the bottleneck in this formulation by reducing it to a Cauchy kernel, resulting in a significant improvement in the space and computation complexity. 
The model is also compared against the state-of-the-art models in a diverse set of benchmarks. Especially the performance in the Long Range Arena (LRA) benchmark is superior. 

I have the following questions for the authors.
- The base LSSL model is not included in most of the benchmarks, particularly in the LRA. Is it due to the scalability problem of LSSL? 
- Is it expected to get improved results over the LSSL (see Tab. 4 and 5)? Does the proposed reparameterization guarantee a “more” optimal state matrix A? 
- The diagonal matrix $\Lambda$ and the vectors $p$ and $q$ are trainable parameters that construct the state matrix A which is initialized to be a HiPPO matrix (Section 3.4). Do these trainable parameters preserve the structure of the matrix A to be HiPPO during and after training? Is it necessary? 
- In autoregressive generation tasks (i.e., the model is fed with its own prediction), the sequence models (RNNs, TCNs, etc.) are likely to suffer from error accumulation problem as the prediction horizon increases. Could the authors comment on S3’s performance in a similar task? Can S3 alleviate this problem? 


-- Post-rebuttal edit --

I thank the authors for their rebuttal. I read other reviews and the author responses. It is clear that this is both empirically and theoretically a strong paper. The improvements over the baselines are substantial. Looking forward to seeing the follow-up work.
summary_of_the_review: This is theoretically and empirically a solid paper. The evaluations show that its superior performance is not limited to modeling long-term dependencies only, but it can be a strong alternative to the established sequence models.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a sequence modeling approach called the structured state space model (S3) which parameterized the SSM in a more computationally efficient manner.  This is done through decomposing the structured state matrices A into a low-rank and skew-symmetric term and expanding the SSM in frequency space and using a multipole-like evaluation.  This approach maintains much of the gains and efficiencies of past SSM approaches while being more computationally stable and efficient as demonstrated on several tasks across broad domains (speech, images, text).  The paper first steps through the theoretical motivations and justifications of this approach and then performs a number of experiments to demonstrate the competitive or superior performance on a wide range of LRD tasks.  
main_review: Strengths:
* The motivation for the approach is clear both from a high-level as well as mathematical viewpoint.  The authors do a good job walking through the theoretical justification and solution of the approach and proposed algorithm.

* The discussion and analysis is performed on a broad domain of tasks.  As the authors discuss, many approaches today are narrowly focused around a single task/domain which limits our broader understanding of LRD modeling.  By using such a varied set of experiments, the usefulness of this approach is well highlighted.

* The introduction is very well written.  The general reader may be less familiar with some of these past works and the authors do an excellent job highlighting the motivation and current status of efforts in this line of study.  Similarly the background is clear and detailed without being unnecessarily complicated or verbose.  

* The performance is compelling from both an efficiency and accuracy standpoint across a number of tasks.

------------------------

Weaknesses:
* Limitations and next steps aren’t explicitly discussed.  It would be helpful for the authors to include even a few sentences on this.

* A known issue with approaches like transformers is the need for huge datasets (even by deep learning standards). How does the performance of this approach vary as a function of dataset size?  Does this method work in a low-data regime?

* The results section is more difficult to follow, especially compared to the rest of the text.  Many of the results are included in the appendix (which is fine especially given their extensiveness).  However, some of the table references are strange.  Table 4 is given, but not directly referenced in the main text (should go with Raw Speech Classification on p.8).  Table 5 is not referenced until after Table 6.  The section "Irregularly Sampled Data" doesn't explicitly reference where those results can be found (i.e. Table 4).  This makes the results section a little bit unclear as the reader has to the text-to-table mapping.   Table 4 caption is a bit unclear (i.e. requires going to the text to interpret what things mean).

* Figure 2 (feature visualization): the authors state that the visualization of the low-level features shows that context over a small area is being learned and the rest of the image is ignored.  However, two of the activations seem to span the entire kernel.  Similarly, one of the higher-level filters is over only a small area.  This seems to be more of a general trend (low learns mostly, but not completely localized, high learns mostly, but not completely global), but not a hard and fast rule.  Is there a hypothesis as to why only some, but not all filters in these layers follow these trends?  With the current visualization, a number of the filters appear identical (just a few solid rows at the top)- are these degenerate or is this a limitation of the visualization?  There is less “hierarchical” structural differences in the convolutional filters (Figure 5 appendix).  Could the authors explain this?

* Minor: Figure 1, I missed the green K several times (spent a while looking for the green in the figure).  Perhaps altering the perceptual qualities of the font could help draw attention to these variables more.   

summary_of_the_review: My recommendation is to accept this work.  This paper proposes a novel parameterization for solving SSM which provides computational efficiency and accuracy gains.  The approach is explained and justified theoretically and the performance is evaluated on a number of tasks across different domains.  The text is clear and well written.  The authors explicitly state the goal of finding general methods that work on a broad range of tasks and this approach offers a good step toward solving that problem under realistic computational constraints.
review_title: null

Meta-review: All reviewers agreed this was a very strong submission: it was clearly written, was theoretically and experimentally interesting, and had excellent motivation. A clear accept. Authors: you've already indicated that you've updated the submission to respond to reviewer changes, if you could double check their comments for any recommendation you may have missed on accident that would be great! The paper will make a great contribution to the conference!!
Decision: Accept (Oral)