Universal Sequence Preconditioning
Authors: Annie Marsden
Elad Hazan
Venue: NeurIPS 2025 spotlight ()
Keywords: sequence prediction
time series
pre-conditioning
Primary area: general_machine_learning
TL;DR: We provide a method of preconditioning sequential data and formally prove it improves the regret bound of several methods and experimentally show it improves the performance of many models.

Abstract: We study the problem of preconditioning in the setting of sequential prediction. From the theoretical lens of linear dynamical systems, we show that applying a convolution to the input sequence translates to applying a polynomial to the unknown transition matrix in the hidden space. With this insight, we develop a novel preconditioning method that convolves the input sequence with the coefficients of the Chebyshev or Legendre polynomials. We formally prove that this improves the regret of a wide family of prediction methods. 

We proceed to apply this preconditioning technique to the method of spectral filtering. This gives the first sublinear regret bound that is also hidden-dimension free (up to logarithmic factors) even when the hidden transition matrix is asymmetric.

From rigorous experiments on synthetic data we show that our simple preconditioning method generalizes to both 1) settings where the data is \emph{not} from a linear dynamical system and 2) a broad range of learning algorithms, including recurrent neural networks.

Universal Sequence Preconditioning
Annie Marsden
Elad Hazan"
Abstract
We study the problem of preconditioning in sequential prediction. From the theoret- ical lens of linear dynamical systems, we show that convolving the target sequence corresponds to applying polynomial to the hidden transition matrix. Building on this insight, we propose a universal preconditioning method that convolves the target with coefficients from orthogonal polynomials such Chebyshev Legendre. We prove that this approach reduces regret for two distinct prediction algorithms and yields the first ever sublinear and hidden-dimenssonnnddeeedddd regret bounds (up to logarithmic factors) that hold for systems with marginally stable and asymmetric transition matrices. Finally, extensive synthetic and real- world experiments show that this simple preconditioning strategy improves the performance of diverse range of algorithms, including recurrent neural networks, and generalizes to signals beyond linear dynamical systems.
Introduction
In sequence prediction the goal the learner is to predict the next token accurately according to a specified loss function, such the mean square error cross-entropy. This fundamental problem machine learning has gained increased importance with the rise of large language models, which perform sequence prediction tokens using cross entropy. The focus of this paper is preconditioning, ie. modifying the target sequence to make it easier to learn. A classic example is differencing. introduced by Box and Jenkins in the 1970s 13], which transforms observations y2.... into successive differences,
Y1 Yo. Y2 Y1: Yt Yt-1....
widely acknowledged that learning this sequence can be "easier" than learning the original sequence for large number of modalities. In this work seek a more general framework for sequence preconditioning that captures the same intuition behind differencing and extends it to a broader class of transformations. The question we ask is
What is the general form of sequence preconditioning that enables provably accurate learning?
We address this question by introducing preconditioning method which takes in n fixed coefficients co...., On and converts the sequence of observations y1..... .t..... to the sequence of convolved observations
Σ cayti:
coYo: CoY1 + C1Y0:
From an informmtion-thhoretie perspective, approaches of this kind seem auill--peddccting y. or Σ, Gyt-i equally hard in an adversarial setting. Yet show that when the data arises from a linear dynamical system (LDS), there exists a universal form of preconditioning that provably
"Google Deepmind
'Princeton University
'This recovers differencing when 2, = 1, and C -1.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

improves learnability, independent of the specific system. In the LDS setting, we show that precondi- tioning significantly strengthens existing prediction methods, leading new regret bounds. Here, preconditioning has an elegant effect: the preconditioning filter forms coefficients of an degree polynomial, and the hidden system transition matrix evaluated on this polynomial- potentially shrinking the domain. In this setting, shrinking the learnable domain is akin to making the problem "easier to learn", a relationship that is formalized by [26]. This allows us to prove the first dimension- independent sublinear regret bounds for asymmetric linear dynamical systems that are marginally stable.
1.1
Our results
Our main contribution is Universal Sequence Preconditioning, a novel method of sequence precon- ditioning which convolves the target sequence with the coefficients of the n-th monic Chebyshev polynomial. We give a more general form of preconditioning, allowing arbitrary user-specified coefficients, in Algorithm | and an online version in Algorithm ! (Appendix g. We analyze the effect of Universal Sequence Preconditioning on two canonical sequence prediction algorithms in the online setting: (1) convex regression and (2) spectral filtering. In either case, the results are impressive- yielding the first known sublinear regret bounds as compared to the optimal ground-trumt truth predictor that are simultaneously (1) applicable to marginally stable systems, (2) independent of the hidden dimension (up logarithmic factors), and (3) applicable to systems whose transition matrix
is asymmetrid F (see Table
Algorithm 1 General Sequence Preconditioning (Offline Version)
1: Training
2: Input: training data (u ( where vt) is the t-th input/output pair in the i-th sequence; coefficients co.n: prediction algorithm A.
yl;A)
3: Assert Co
4: for 1 to N do
5: YiT
preconndiiooeed
<- convolution(y Com)
y peeconditooned, = =y¹ + Ei ciyi-s
6: end for
7: Train A preconditioned data (u [ Vi.
precodiiionnd....y
8: Test Time
9: for t = 1 to T do
10: Receive u4,
11: Predict ýt + A (u (u(--))))))) -E cyt-i-
12: Receive y.-
13: end for
First, applying USP to standard convex regression results in regret ((7-2/13) which holds simul- taneously across the three settings above and remains diimension-indeenddenn For comparison, naive analysis of regression yields a vacuous regret bound of (TT522) marginally stable systems. Second, combining USP with a variant of spectral filtering [27] that uses novel filters, the algorithm able learn broader class of linear dynamical systems- in particular systems whose hidden transition
matrix may be asymmetric. The enhanced method achieves regret (373333) the best known rate under the joint conditions of (1)-(3) discussed above: marginal stability, dimension independence, and asymmetry. Both results require that the transition matrix eigenvalues have imaginary parts bounded by O11 log T near-tight condition for achieving dimension- regret. Further discussion on this appears in Appendix B
Empirical results in Section demonssrate that USP consistently improves performance across diverse algorithms- -egerubmm-iinlludingg regression, spectral filtering, and neural networks and across data types extending beyond linear dynamical systems.
"Our results only hold for asymmetric matrices whose eigenvalues have imaginary component bounded above by 0(1/ lo]))) This somewhat tight, see Section B

---

Method
Marginally stable
dhidden free
Asymmetric
Sys-ID
X
Regression (open-loop)
Regression (closed-loop)
X
Spectral Filtering
X
USP + Regression
USP + Spectral Filtering
Table I: Comparison of methods for learning LDS. USP extends learning to mildly asymmetric
matrices with bounded complex eigenvalues.
1.2 Intuition for Universal Sequence Preconditioning
We now give some brief intuition for the result. Linear dynamical systems (LDS) are perhaps most basic and well studied dynamical systems in engineering and control science. Given input vectors u1,... ur E Odo, the system generates a sequence output vectors y1....T E C according to the law
X - Ax, + BuG
Yr = Cx. + Du,,
(1)
where ......, XT Coease is sequence of hidden states and (A, B, C, are matrices which parameterize the LDS. We assume w.l.o.g. that D = O. We can factor out the hidden state x so that the observation at time t is
y:
CA BB,.
Given coefficients Com
(co,-.., Cx) let
P (x)
c
==0
Consider a "preconditioned" target at time to be a linear combination of Yet-n with coefficients C0: key insight the following identity,
Σ Soy-
Σ Σ CCA'IB
B
U1
Σ
Au) -n---
If we take 1 (i.c. monic polynomial), we can we-te y:
Yt
C.y
CA Bu
(A) Bu
S=0
No
This expression highlights our approach as a balance of three terms:
No The universal preconditioning term: it depends only the coefficients co... and not any learning algorithm.
N, A term learnable via convex relaxation and regression, for example by denoting
Q
leamed
Σ
CCAAAAA B.
1=0
The diameter of the coefficient Qe depends on the magnitude of the coefficients Com-
N2 The residual term with polynomial (A)). By a careful choice of coefficients Comss we can force this term to be very small.
The main insight we derive from this expression the inherent tension between two terms Nj, N2. The polynomial Pf (r) and its coefficients co. ..... Cn. control two competing effects:

---

1. The preconditioning coefficients grow larger with the degree n of the polynomial and the magnitude of the coefficients c₁ higher degree polynomial and larger coefficients increase the diameter of the search space over the preconditioning coefficients, and therefore increase the regret bound stemming from the N1 component learning.
2.
On the other hand, larger search space can allow a broader class of polynomials P-x(-) which can better control of the magnitude of pn (A), and therefore reduce the search space of the N2 component.
What choice of polynomial is best? This work considers the Chebyshev polynomial. The reason is the following property of the n-th monic Chebyshev polynomial:
[An(A)] S 2 (n-1)
max 11(1
As an example, consider any LDS whose hidden transition matrix A is diagonalizable and has eigenvalues in 1-1, By the above property, observe that I| (A))l I 2 2-2 therefore shrinking the N2 term rate exponential with the number of preconditioning coefficients. We pause to remark on the universality of this choice of polynomial. Indeed, one could instead have chosen the preconditioning coefficients to depend on A so that P. (+) is the characteristic polynomial of A. By the Cayley-Hamilton theorem, Pm (A) 0. This means that N2 term is canceled out completely. However this would have required knowledge of the spectrum of A. The Chebyshev polynomial, on the other hand, is agnostic to the particular hidden transition matrix. Moreover, even the spectrum of A were known, choosing the preconditioning coefficients to form the characteristic polynomial would result in algorithm which must learn hidden dimension many parameters, which is prohibitive. Instead, the degree of the Chebyshev polynomial must only grow logarithmically with the hidden dimension.
1.3 Related work
Our manuscript is technically involved and incorporates linear dynamical systems, spectral filtering, complex Chebyshev and Legendre polynomials, Hankel and Toeplitz matrix eigendecay, Gaussian quadrature and other techniques. The related work is thus expansive, and due to space limitations we give a detailed treatment in Appendix A Preconditioning in the context of time series analysis has roots in the classical work Box and Jenkins [I3. In their foundational text they propose differencing as method for making the time series stationary, and thus amenable statistical learning techniques such as ARMA (euto-regressive moving average) T. The differencing operator can be applied numerous times, and for different lags, giving rise to the ARIMA family of forecasting models. Identifying the order of an ARIMA model, and in particular the types of differencing needed to make series stationary, is a hard problem. This is special case of the problem we consider: differencing corresponds to certain coefficients of preconditioning the time series, whereas we consider arbitrary coefficients. For thorough introduction to modern control theory and exposition on open loop / closed loop predictors, learning via regression, and spectral filtering, see [26]. The fundamental problem of learning in linear dynamical systems has been studied for many decades, and we highlight several key approaches below:
1. System identification refers to the method of recovering A, B, C from the data. This is non-convex problem and while many methods have been considered in this setting, they depend polynomially the hidden dimension.
2. The (auto) regression method predicts according to y: Et M, The coefficients M; can be learned using convex regression. The downside of this approach is that if the spectral radius of A is 8, it can be seen that ~ terms are needed.
3. The regression method can be further enhanced with "closed loop" components, that regress on prior observations y1-1:1. It can be shown using the Cayley-Haniloon theorem that using this method, d, components are needed to learn the system, where dy is the hidden dimension of A.
4. Filtering involves recovering the state 2, from observations. While Kalman filtering is optimal under specific noise conditions, it generally fails in the presence of marginal stability and adversarial noise.
This work considers broader class of hidden transition matrices.

---

5. Finally, spectral filtering combines the advantages of all methods above. It is an efficient method, complexity does not depend on the hidden dimension, and works for marginally stable systems. However, spectral filtering requires A to be symmetric, or diagonalizable under the real numbers.
2 Main Results
In this section we formally state our main algorithms and theorems. We show that the Universal Sequence Preconditioning method provides significantly improved regret bounds for learning linear dynamical systems than previously known when used in conjunction with two distinct methods. The first method is simple convex regression, and the second is spectral filtering. Both algorithms allow for learning in the case of marginally stable linear dynamical systems and allow for certain asymmetric transition matrices of arbitrary high hidden dimension. The regret bounds are free the hidden dimension (up to logarithmic factors) which significantly extends the state of the art.
2.1 Universal Sequence Preconditioning Applied to Regression
Algorithm is instantiation of Algorithm for the method of convex regression. We set the preconditioning coefficients to be the coefficients of the n-th degree (monic) Chebyshev polynomial.
Algorithm 2 Universal Sequence Preconditioning for Regression
1: Input: initial parameter Q", preconditioning coefficients Co.n from the nith degree (monic) Chebyshev polynomial; convex constraints K. = {(Qo...., Qa-1) s.t. ||Q]|| S Cdomain || [|||
2: Assert that Cy 1.
3: for = 1 to 7" do
4: Receive u,
5: Predict (Q')))
E c.y-+ E -y= 2 Q/
6: Observe true output y, and suffer loss & (Q()) [+' ycll1-
7: Update and project:
Q++1 + projx (Q' T/e Vof+(Q)))
8:
end for
Theorem 2. shows that vanishing loss compared to the optimal ground-truth predictor, at rate that independent of the hidden dimension of the system.
Theorem 2.1. Let (ue) che be any sequence of inputs which satisfy ||uelle s 1 and let {ye)r=1 E Edho the corresponding output coming from some linear dynamical system (A, B, B,C) C) as defined per Eq. Let diagonalize (note exists w.l.o.g)) and let = ||P]||||] Assume that |||||||| S Cáomnin- Let >i,..., Adg, denote the spectrum of A.
Jar(())) < 1/(32 (2T {mma))) jE(da,
then the predictions $1, -1.-... chosen to be the coefficients of the n-th monic Chebyshev polynomial satisfy
. ST from Algorithm where the preconditioning coefficients Co.n.
T 11 velli s ŌŌ [B]||| dont
T
= Σ
T2/13
1=1
where Ö(-) hides polylogarithmic factors in T.
The proof of Theorem 2.1 is in Appendix D For simple baseline comparison, the regret achieved (via the same proof technique) by the vanilla regression algorithm without preconditioning is O (Coomain 1 3/22) which is not sublinear in T.
2.2 Universal Sequence Preconditioning Applied to Spectral Filtering
Our second main result is the application of Universal Sequence Preconditioning to the spectral filtering algorithm 27. Our results more general and apply any choice of polynomial, not

---

just Chebyshev. In addition to applying USP to spectral filtering, we also propose novel spectral filtering basis. Both changes the vanilla spectral filtering algorithm are necessary extend its sublinear regret bounds to the case of underlying systems with asymmetric hidden transition matrices. First we define the spectral domain
= (= [2] I 1, [./arg(2)] 1 8}
Given horizon T and a E C3 let
(a( def (1 a1- [1 a a²-1]",
(4)
and
Zr def [ ( da,
(5)
JaEC,
where E denotes the complex conjugate. The novel spectral filters are the eigenvectors of Zr-n-1, which we denote as 01,..., -T ,1--..0T---1- Note that in the standard spectral filtering literature, the spectral filtering matrix is an integral over the real line and does not involve the complex conjugate. Our new matrix has entirely different structure and although it looks quite similar, it surprisingly upends the proof techniques to ensure exponential spectral decay, a critical property for the method. Future work examines this matrix thoroughly, but in this paper simply provide standard bound on its eigenvalues.
Algorithm 3 Universal Sequence Preconditioning for Spectral Filtering
1: Input: initial Qi.,s Mi horizon T, convex constraints
K- {(Qo, .Q......
Qn M& ||Q I RQ and ||,]l s RM},
parameter n,, coefficients Ci:R-
2: Let pr (x) = Cox" C1r
+ c, and (x)) (1 - x² (x) Let Co.... En+2 be the
coefficients of p% (x)).
3: Let 0I...., 0, be the top n cigenvectors of Z-
4: Assert Cp
5: for = 1 to T do
6: Let U;-n-1:1 be u utn-1:: padded with zeros it has dimension T - dnn
7: Predict (Q'' MD) = h d,y,,; Σド= Qju: + vे Σÿ=1 M) u:-1-1:1-
8: Observe true yı, define loss ( ( M Vell1.
9: Update and project: (Q'+1, MM+1) projæ (Q', M') - - To (',,
10:
end for
Theorem 2.2. Let {ur) E Rd be any sequence of inputs which satisfy ||u:||2 < 1
and let {y:) be the corresponding output coming from some linear dynamical system (A, B. C) as defined per Eq. 0 Let P diagonalize A (note P exists w.l.ogg). and let k P Suppose the radius parameters of Algorithm 3 satisfy RQ 2 ||C|||]]||||| and
RM 2 B|| log(T) (max,e(Aa) aar((>))))
4/3 77/6 (maxaeCa (p%(a))). Further suppose
that the eigenvalues of A have bounded argument:
max [E(da)
arg(()))
< 11133.
Then the predictions ,1,.... YT from Algorithum 3 where the preconditioning coefficients Com are chosen be the coefficients of the n-th monic Chebyshev polynomial satisfy
T
-ella s Ö =((1c) //3
(IICIIBI RRV d
Σ 1=1
T
We remark that the result of Theorem is rather weak. Although the complex eigenvalues of A are not trivially bounded (trivial would bound of 1/T),, they still must be polynomially small T. Moreover we note that the proof technique for the result does not make use of the critical properties of spectral filtering and relies much more on the power of preconditioning. The proof of Theorem in Section [

---

3 Proof Overview
In this section we give a high level overview of the proofs for Theorem 2.1 and Theorem 2.2 We start
by recalling the intuition for Universal Sequence Preconditioning developed in Section 1.2 which shows that if ty)e= evolves as a linear dynamical system parameterized by matrices (A, B, C) with inputs {u 1 then by Equation
I-n-1
Yt =
Gy
C CA
Bu-
Cp)
No
Recall that Ng is the universal preconditioning component, N1 is the term that can easily be learned by convex relaxation and regression, and N2 is the critical term that contains pl, (A). Both Theorem 2. and Theorem 2.2 use the standard result from online convex optimization (Theorem 3.1 from (24 that online gradient descent over convex domain K. achieves regret GGDVT as compared the best point in K., where D denotes the diameter of K. and G denotes the maximum gradient norm.
Regression: Proof of Theorem 2.1 In the case of regression, the domain is chosen so that N₂ may be learned and the proof proceeds by bounding the diameter of such a domain and its corresponding maximum gradient norm to get regret Cn²² /ama ||||| I for a universal constant C > which depends on the norms of matrices B and from the underlying system. Then 83 is treated as an un-learnable error term. Let ((A) denote the set of eigenvalues of A. By the simple magnitude bound of
t-n-1
Σ S=
CA)
S max Ia (A)l T ||C|| |
ΛEA(A)
the error of ignoring this term can be very small if maxx(A) Ipa (A(A)) is small. In the proof of Theorem 2.1 in Appendix D show that the regret for generic polynomial ps, defined by coefficients Co.n is
T
yy Sella S douullllll + max (A))T???
XED
Regret from learning N₂
Unlcarnable Error Torm
where D the region where A is allowed have cigenvalues (see Theorem D.I. Therefore, get sublinear regret, we must choose a polynomial which has bounded & norm of its coefficients, while also exhibits very small infinity norm on the domain of eigenvalues.
Spectral Filtering: Proof of Theorem 2.2 In the case of spectral filtering, the domain is chosen so that both N₂ and N3 may be learned. Because spectral filtering learns N3. is able accumulate less error and hence achieves a better regret bound of 33133) as compared regression's 's 2/113/ At a high level, the proof proceeds by exploiting the fact that pa P.(AA (A) shrinks the size of the learnable domain. However this is not enough, in order extend the result systems where may have complex cigenvalues, the spectral filters must be eigenvalues of new matrix, defined in Eq. 5 whose domain of integration includes the possibly complex eigenvalues of A. To get the dimension- independent regret bounds enjoyed by spectral filtering in this new setting where complex eigenvalues may oceur, the exponential decay of Zy from Eq. 5 must be established. This is nontrivial and
requires several novel techniques inspired by [II] The details are in Appendix E.3.1 Theorem 2.2 gives the main guarantee for the spectral filtering algorithm, which states that Algorithm instantiated with some choice of polynomial p& (.) achieves regret
ò (mlel + 7/66 max (n((())) (n k) doms domnVT vT
aEC,
Both this theorem, as well as our new guarantee for convex regression, leads us the following question: Is there universal choice of polynomial pm((r), where is independent of hidden dimension, which guarantees sublinear regret?

---

3.1 Using the Chebyshev Polynomial over the Complex Plane
For the real line. the answer this question is known be positive using the Chebyshev poly- nomials of the first kind. In general, the nth (monic) Chebyshev polynomial (z) satisfies maxx [M (x)l I 2 (-(m1)), However, we are interested in more general question over the complex plane. Since we care about linear dynamical systems that evolve according to a general asymetric matrix, we need to extending our analysis to C3. This is a nontrivial extension since, in general, functions that are bounded on the real line can grow exponentially on the complex plane. Indeed, 2 MM (az cos(n arccos(x)) and while cos(x) is bounded within [-1, 1] for any E R. over the complex numbers we have cos(z) = 1 [ee + E E=); which unbounded. Thus, we analyze the Chebyshev polynomial on the complex plane and provide the following bound.
Lemma 3.1. Let E C be some complex number with magnitude |al S 1. Let M. denote the n-th monic Chebyshev polynomial. If arg(2)] < 1/64n2, then [M) Σ 1/2n-2
We provide the proof in Appendix We also must analyze the magnitude of the coefficients of the Chebyshev polynomial, which can grow exponentially with n. We provide the following result.
Lemma 3.2. Let (-) have coefficients co....,Cz: Cx- Then maxk=0..... |cal
20.3n
The proof of Lemma 3.2 is in Appendix B Together, these two lemmas are the fundamental building block for universal sequence preconditioning and for obtaining new regret bounds.
4 Experimental Evaluation
We empirically validate that convolutional preconditioning with Chebyshev or Legendre coefficients yields significant online regret improvements across various learning algorithms and data types. Below we summarize our data generation, algorithm variants, hyperparameter tuning, and evaluation metrics.
4.1 Synthetic Data Generation
We generate = 200 sequences of length 2000 via three mechanisms: (i) a noisy linear dynamical system, (ii) noisy nonlinear dynamical system, and (iii) noisy deep RNN. Inputs Ugr ~ (O,
Linear Dynamical System. Sample (A, B, C) with A R x having eigenvalues {2y] drawn uniformly in the complex plane subject to Im(2,) I Tthresh and L 1zyl U, and B, C e R300 Then
X
Ax Bu, Y: Cx, ce, a (0.
Nonlinear Dynamical System. Similarly sample (A1, B1, C) and (Az, B2) with A, E 10x10 B,, C E R10
Then
= Aix.- + Biu, x," = =x x; = A2x (1) + B24; yr Cx: +
Deep RNN. We randomly initialize a sparse 10-layer stack of LSTMs with hidden dimension 100 and ReLU nonlinear activations. Given ui.r we use this network to generate yI.T.
4.2 Algorithms and Preconditioning Variants
(2) Spectral Filtering (Alg. DNN Predictor: n-layer LSTM with dims (d,,..., d,). ReL.U. Each method is applied with one of:
We evaluate the following methods: (1) Regression (Alg. 2
1. Baseline: no preconditioning
2. Chebyshev: Co.a the coefficients for the ttt-Chebbyshv polynomial. Note that when
n = 2 we have ep = and c = - and therefore this the method of differencing discussed in the introduction.
3. Legendre: Com are the coefficients for the ntth-nge polynomial

---

4. Learned: Cum is parameter learned jointly with the model parameters
We test polynomial degrees n. E {2, 10, 20). This choice of degrees shows rough picture of the impact of n.
Hyperparameter Tuning. To ensure fair comparison, for each algorithm and conditioning variant we perform a grid search over learning rates 7j {10-3 10021022000 10--)000000 selecting the one minimizing average regret across the N sequences. In the case of the learned coefficients, we sweep over the pairs of learning rates (7modde /eceffiiionsss E {10-², 10-2, 1-1-1---0000 x {10-t "0-
4.3 Results
Tables 2 report the mean std of the absolute enror over the final 200 predictions, averaged across 200 runs. In the linear and nonlinear cases we train a 2-layer DNN (dims (64, 128)); for RNN-generated data we match the 10-layer (100-dim) generator.
Key observations:
Preconditioning drastically reduces baseline errors for all algorithms and data types.
Chebyshev and Legendre yield nearly identical gains.
For Chebyshev and Legendre, once the degree is higher than 5 10 the performance degrades since ||c|| gets very large (see our Lemma 3.2 which shows that these coefficients grow exponentially fast).
Improvements decay the complex threshold Tthresh increases, consistent with our theoret- ical results which must bound Im (2,).
Learned coefficients excel with regression and spectral filtering but destabilize the DNN nonlinear and ENN-generated data.
Setting
Baseline
Chebyshev Dep.
Legendre
Learned
Dep: 2
Dep
Dep
Dep 5
Deg. 10
Dep:
Dep. 5
Deg 10
Deg:
Regression
0.01
0.74
0,07
0.36
0.64
0.52
Tilnd
0.66
1,90 0.57
0.43
0.14
Silesh 0.9
2447 :: 0.89
1.59 0.56
2.18 0.79
2.68 1.8.2.00 0.48
1.64 :: 0.58
1.94 0.70
2.63 = 0.45
1.73 0.59
0.83 0.25
0.68 a 0.27
0.63 0.26
Spectaal Fibering
Tikreh
Tikmeb 0.1
0.89 : 0.34
0.42 0.11
0.34 : um
0.86 + 0.28
0.54 0.17
6.33
0.76 = 0.24
0.69 0.28
0.31 0/06
0.37 0.08
Thrma 0.9
18.17 = 8:00
9.87 5,90
12.66 8.18
32.90 22
9.42 8:30
11.53 7.46
28.83 19.24
7.90 4.42
6.31 4.39
5.33 380
5.86 4.02
DNN
Tilndd
1.18
262
10:36:1
1:
1.56 0.64
Tikeeh 0.1
9.41 7.344
2.66
1.76
1.52
0.72
4.65
3:08
4.24 3.06
1.44 0.71
4,08 2.64
6.54 a 4.33
3.22
1.9
1.59
0.5 0,80
0.9
2.45 1.31
2.24
1.34
3.49
2.2
11.48 9.15
2.17 1.25
3.10 2.00
9.97
5.005
1.29 0.66 0.71 0.34 0.43 0.18
0.24 a.11
Table Linear dynamical system data (detailed in Sec, 4.1b across varying complex threshold Tthres-
Setting
Buseline
Chebyshev Deg.
Legendre
Deg,
Deg.
Deg
10
Deg.
Deg. 10
Deg. 29
Spectral Fiboring
Trkndh 001
153.8
43.72
0U2: 0.31
78.4
-001
124.11 68.4
3341
2.02: 1.25
0,361 0.31
56.74 908
187
0.36 0.26
2.851 1.13
0.44 0.11
6.12 aat
0.07: 0.t
Trknuh ag
165.51 84.5
43,414 1639
1.7:: 0.37
1990 0.80
76,9%: 29.1
3322 109
1.44 0.0
1.794 0.6
0.101 0.04
0.12 0,05
0.17: 0,07
layer
000
10.461 X.19
3,456:1
0.19 0.16
0.436-031 0:33
3.55
0.18:
0.374
45:401: 11.35
25.34 9.06
12.73 4.00
6.43 1.32
Tannd
4.20
3,38
0.14: 0.5
0.41
3:42
0.25:0.14
0.362 0.15
67.20
25.40
11:99
11.78
15.954:
801 195
1:
0.281:015
3.35
0.34--11
53.651
Table 3: Nonlinear data (detailed Sec.
across varying complex threshold 7thres-

---

Setting
Baseline
Chebyshev
Legendre
Learned
Deg.
Deg.
Deg.
Deg.
Deg.5
Deg.
10Jayer
0.34
0,80
0.37 2014
0.09
0.12:
0.99
2.33
104=051
Table 4: Performance (average absolute error the last 200 predictions) of a 10-layer DNN (detailed
in Sec. 4.2 data generated from the same model (detailed in Sec. 4.1)
4.4 ETTh1 Dataset
To evaluate whether our proposed preconditioning approach generalizes to real-world time series, we conduct experiments on the well-established ETTh1 dataset from the Electricity Transformer Temperature (ETT) benchmark [37. The ETThl dataset consists of continuous hourly measurements of load and oil temperature collected from electricity transformers and has been used in several recent
works 37 35
We study the effect of preconditioning on 10-layer LSTM with hidden dimension 100 per layer using the Adam optimizer. We set the horizon to T 5000 and broader range of learning rates 7) E {10- )== 1,=0,1,2,3444 As before we consider (i) no preconditioning (baseline), (ii) fixed Chebyshev coefficients, (iii) fixed Legendre coefficients, and (iv) coefficients learned jointly with model parameters. As seen in Figure preconditioning with Chebyshev and Legendre for degree 5 the best performance after only the first 1000 iterations, while the performance of jointly learning the coefficients worse this stage. The performance of all three preconditioning methods are roughly on par with each other by 2500 iterations and by the full horizon 1' 5000, jointly learning the coefficients results in the best average prediction error.
32
20
2
36
B1
sweep
of Preemiree
Deppore Necvedoe Aeteend
Depport becrokser
(a) Early Stage: 1000
Middle Stage: T 2500
(c) Final Stage: T 5000
Figure 1: Absolute prediction error on final 200 predictions averaged over 10 independent runs for 10-layer LSTM with layer dimension 100 using Adam optimizer and sweeping over learning rates for each run.
Discussion
There many settings in machine learning where universal, rather than learned, rules have proven very efficient. For example, physical laws of motion can be learned directly from observation data. However, Newton's laws of motion succinetly crystallize very general phenomenon, and have proven very useful for large scale physics simulation engines. Similarly, in the theory of mathematical optimization, adaptive gradient methods have revolutionized deep learning. Their derivation consequence of regularization in online regret minimization is particularly simple [19], and thousands of research papers have not dramatically improved the initial basic ideas. These optimizers are, the very least, a great way to initialize learned optimizers
By analogy, thesis in this paper is that universal preconditioning based the solid theory of dynamical systems can be applicable to many domains or, at the very least, an initialization for other leamning methods.
Acknowledgments and Disclosure of Funding
Elad Hazan gratefully acknowledges funding from the Office of Naval Research and Open Philan- thropy.
10

---

References
[1] Yasin Abbasi-Yadkori, Peter Bartlett, and Varun Kanade. Tracking adversarial targets. In International Conference Machine Learning, pages 369-377. PMLR, 2014.
[2] Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Anmual Conference on Learning Theory, pages 1 1-26, 2011.
[3] Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1948.
[4] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances, In International Conference on Machine Learning, pages 111-119. PMIR, 2019.
[5] Naman Agarwal, Xinyi Chen, Evan Dogariu, Vlad Feinberg, Daniel Suo, Peter Bartlett, and Elad Hazan. Futurefill: Fast generation from convolutional sequence models. arXiv preprint arXiv:2410.03766, 2024.
[6] Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. In Advances Neural Information Processing Systems, pages 10175-10184, 2019.
[7] Naman Agarwal, Daniel Suo, Xinyi Chen, and Elad Hazan. Spectral state space models. arXiv preprint arXiv:2312.06837 2023.
[8] Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. Advances in Neural Information Processing Systems, 28, 2015.
[9] Oren Anava, Elad Hazan, Shie Mannor, and Ohad Shamir. Online learning for time series prediction. In Conference on learning theory, pages 172-184. PMLR, 2013.
[10] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau. A new approach to learning linear dynamical systems. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 335-348, 2023.
[11] Berhaard Beckermann and Alex Townsend. On the singular values of matrices with displacement structure, SIAM Journal on Matrix Analysis and Applications, 38(4):1227-1248, 2017.
[12] Dimitri P Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2007.
[13] George EP Box and Gwilym M Jenkins. Time series analysis. forecasting and control. Holden- Day Series in Time Series Analysis, 1976.
[14] Nicolo Resa-Bianchh and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[15] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference on Learning Theory, pages 1114-1143. PMLR, 2021.
[16] Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In International Conference on Machine Learning, pages 1029-1038, 2018.
[17] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only /T regret. In International Conference on Machine Learning, pages 1300-1309, 2019.
[18] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems, pages 4188-4197, 2018.
[19] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.

---

[20] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476, 2018.
[21] Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. No-regret prediction in marginally stable systems. In Conference on Learning Theory, pages 1714-1751 PMLR, 2020.
[22] Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022.
[23] Rohit Gupta and al. Simplifying long-range modeling with structured state space models. arXiv preprint 1xXi::2208.04933 2022.
[24] Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
[25] Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems. In Advances in Neural Information Processing Systems, pages 1680-1689, 2018.
[26] Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv preprint arXiv:2211.0961 2022.
[27] Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering. In Advances in Neural Information Processing Systems, pages 6702-6712, 2017.
(28) Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82.1:35-4: 1960.
[29] Mark Kozdoba, Jakub Marecek, Tigran Tchrakian, and Shie Mannor. On-line learning of linear dynamical systems: Exponential forgetting in kalman filters. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4098 -108, 2019.
[30] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. In Advances in Neural Information Processing Systems, pages 10154-10164, 2019.
[31] An Nguyen, Yifan Chen, and Jian Li. Preconditioning state-space models for stable long- horizon forecasting, arXiv preprint arXiv:2403.07890 2024.
[32] Yixuan Nie, Nina Narodytska, and Ankit Patel. A time series is worth 64 words: Long-term forecasting with transformers. arXiv preprint arXiv:2209. 13466, 2022.
[33] Max Simehowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[34] Olga Wichrowska, Niru Maheswaranathan, Matthew W Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Nando Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In International conference on machine learning, pages 3751-3760. PMLR, 2017.
[35] Haixu Wu, Jianmin Xu, Jie Wang, and Mingsheng Long. Autoformer: Decomposition transform- ers with auto-correlation for long-term series forecasting. In Advances in Neural Information Processing Systems, 2021.
[36] Ailing Zeng, Muxi Chen, Lei Zhang, and Qiang Xu. Are transformers effective for time series forecasting? In AAAI Conference on Artificial Intelligence, 2023.
[37] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hongyun Xiong, Wancai Zhang, and Yan Li. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[38] Kemin Zhou, John C. Doyle, and Keith Glover. Robust and Optimal Control. Prentice-Hall, Inc., USA, 1996.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We claim a rigorous new method for sequence preconditioning that improves upon the classical differencing method in theory and practice.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Throughout we demonstrate understanding the limitations of our approach. such as restricting our results to linear dynamical systems with bounded imaginary part of the transition matrix.
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]
Justification: Our main theoretical results are Theorems 2.1 and 2.2 in which the assump- tions made are stated. We give only proof overview in main paper, but complete one in appendix.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, we describe algorithms completely in and Our code repository will also be open sourced.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
link to code will be provided in the final version. However, we omit GitHub repository with all of our code at the moment in order not to violated the double blind policy and keep the paper anonymous.
Justification:
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]
Justification: Experiment details are expansively explained in section and the appendix.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: all our graphs include error bars and statistical significance.
8. Experiments compute resources
13

---

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:
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:/ss//earrri....cppp//////aa
Answer: [Yes]
Justification: The paper conforms simply in every respect with the NeurIPS Code of Ethics explained.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
[NA]
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: [NA]
12. Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification: All previous work fully credited and cited throughout.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification: Our new assets are well documented and the documentation provided.
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 details about compensation (if any)?
Answer: [NA]
Justification: [NA]
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
16. Declaration of LLM usage
14

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
15


Reviews:
[{"review_id": "t0S6wG668M", "reviewer": "Reviewer_u5xs", "summary": "This paper investigates the problem of preconditioning for sequential prediction, introducing a universal sequence preconditioning (USP) method grounded in the application of orthogonal polynomial filters (such as Chebyshev and Legendre polynomials) to input sequences. The authors provide a theoretical analysis demonstrating improvement in regret bounds for learning in linear dynamical systems, even in cases with asymmetric and marginally stable transition matrices. The paper applies USP to both convex regression and spectral filtering techniques, with rigorous regret analyses and empirical evaluation on synthetic data generated from linear, nonlinear, and deep RNN-based dynamical systems. Experimental results suggest that polynomial-based preconditioning yields consistent performance improvements across a range of models and data types.", "questions": "1. How the eigenvalue imaginary-part assumption for the transition matrix manifests in commonly encountered real-world time series?\n\n2. What are the main computational bottlenecks?\n\n3. Why analytic polynomial coefficients (Chebyshev/Legendre) are more robust than learned ones? Is it due to optimization landscape, overfitting, or initialization?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper provides regret bounds for sequential prediction methods when combined with the proposed preconditioning, advancing prior work especially for asymmetric, marginally stable linear dynamical systems. Theoretical claims are generally supported by concrete statements. The preconditioning method is mathematically principled, leveraging properties of Chebyshev and Legendre polynomials, and can be applied to a broad class of sequence models, including regression and spectral filtering.\n\n2. The approach provides regret bounds that do not scale with the latent dimension of the dynamical system.\n\n3. The experiments are well designed, evaluating on synthetic linear, nonlinear, and RNN-generated data. Different preconditioning schemes are compared, including learned preconditioning, and a thorough sweep across polynomial degrees and hyperparameters is conducted.\n\nWeaknesses:\n\n1. The assumption on the eigenvalues' arguments in Theorem 2.1 maybe too strong for complex neural networks, as it demands a system behavior with virtually no oscillations. If this assumption holds true, please cite some papers to validate this.\n\n2. Tables 2–4 list results for several polynomial degrees, but the text could provide deeper interpretation of how performance depends on the degree parameter, especially for higher degrees where some results appear inconsistent.\n\n3. While the proof for Algorithm 3 relies on the common theoretical assumption that the system matrix can be diagonalized (justified by density arguments), the paper could more explicitly discuss how “arbitrarily small perturbations” to achieve diagonalizability might accumulate over T steps in an online learning context.\n\n4. The proof of Theorem C.7 misapplies Lemma C.8, which explicitly requires Krylov matrices to have Hermitian arguments. However, the matrix constructed in the proof of Theorem C.7 (diag(z)) is generally not Hermitian, as its diagonal elements are typically complex numbers. Please do not hesitate to correct me if my understanding is inaccurate.\n\nMinor issues:\n\n1. The table number and title always appear before the table. Table 1-4 should be revised.\n\n2. When writing the thesis, there are few citations of related work, which affects the readability of the article. For example, Line 21-22: “It is widely acknowledged that learning this sequence is easier than learning the original sequence for a large number of modalities.”\n\n3. Line 21: “easier\", Line 127: “closed loop\"", "was_revised": true, "final_justification": "The author has addressed most of my concerns, and I will raise my score.", "rebuttal": "Thank you for your insightful review! Our responses are below.\n\n\nWeakness 1)  The assumption is actually very mild since it only depends logarithmically on the horizon T. More importantly, this assumption is somewhat tight, see our discussion on this see Appendix A.3 (page 19 of our supplementary material). It’s true that as the imaginary component is restricted, the oscillatory nature of the signal is restricted. However, to our knowledge, this is the strongest regret bound possible (i.e. that isn’t polynomially dependent on hidden dimension) with the least amount of assumptions, see Appendix A.1 for a better sense of previous assumptions on linear dynamical systems in the literature. Moreover, please note that empirically we show that our method is in fact able to perform well on systems that can have oscillations.\n\n\nWeakness 2) The results are consistent with our paper but we did not make that point as clear as it could have been and we will fix that. Indeed, for Chebyshev and Legendre polynomials, once the degree is higher than 5 − 10, the performance degrades since the $\\ell_1$-norm of the coefficients is very large. This is consistent with our regret bounds– see Lemma 4.2, which shows that these coefficients grow exponentially fast and see Theorem C.1 which shows that the $\\ell_1$-norm of these coefficients adversely affects the regret bounds. We will make this clearer in the main body of the paper (although we do mention it in line 175).\n\n\nWeakness 3) Our results will not depend on the arbitrary small perturbations, since we have no dependence on the distance between eigenvalues, which can be very small if we start with a degenerate matrix. \nBecause of density, given any fixed horizon T and any system matrix A, there is a diagonalizable matrix A’ which is no more than $1/T^{1000}$ away from A (using your favorite metric). Therefore any accumulation over T would introduce error no more than $1/T^{999}$. Note we could have picked a number different from $1000$, we just chose it for an example. Moreover, this is fixed in advance even in an online learning setting– the matrix A does not evolve with time. Does this clarify things? We are happy to add this to the paper!\n\n\nWeakness 4) This is a great catch and we thank the reviewer for finding it! Your understanding is accurate, however we do not actually need to use Lemma C.8 to show exponential decay. We just need to show our matrix satisfies a Sylvester equation like 5.2 in [1] which it does using the same matrix Q as used in the reference. The next change we must make is the argument to bound the Zolotarev number which we can easily do since the spectrum of $\\mathrm{diag}(z)$ does not overlap with Q. This is true because the $z_j$ derived from Gaussian quadrature satisfies $|z_j| \\leq 1 - 1/10T^2$ (this comes from the Gauss-Legendre nodes). This gap means that we will still have exponential decay in the eigenvalues, but it will be a poly log factor slower (which does not meaningfully affect our result). We will edit our proof for this but note that it proceeds exactly the same way. Please let us know if you would like to see the full edit.\n[1] Bernhard Beckermann and Alex Townsend. On the singular values of matrices with displacement 318 structure. SIAM Journal on Matrix Analysis and Applications, 38(4):1227–1248, 2017\n\n\nQuestion 1) This is a good question and it isn't clear. That said, the important take away is that in the previous literature you either must assume that the imaginary part is exactly 0 or that the hidden dimension isn't too large. Instead we loosen both of those assumptions to simply that imaginary part be bounded inverse logarithmically in $T$. Therefore, we broaden the class of linear dynamical systems that can be learned.\n\n\nQuestion 2) One major advantage to our proposed preconditioning method is that it is incredibly fast computationally-- regardless of the complexity of the algorithm being used. Indeed, it involves convolving the output sequence with just 5 scalars and is very fast in practice. \n\n\nQuestion 3) We randomize over initialization and optimization learning rates so it is more likely due to the fact that a) learning the best coefficients jointly with the model parameters is nonconvex and can therefore fail and b) some kind of overfitting. It's an interesting question for future work whether there are better/more robust methods to learn these coefficients."}, {"review_id": "xvmbF0A9x8", "reviewer": "Reviewer_jQGL", "summary": "This paper proposes a method to precondition time series data such as to improve sequential prediction. The main idea relies on taking the convolution of the input sequence with Chebyshev polynomial coefficients. The authors then show that this methodology improves the regret of different sequence prediction models, thereby providing strong theoretical motivations for their approach.\n\nThe authors further show that their methodology can be applied to multiple algorithms such as recurrent neural networks. And they demonstrate the improved performance of their preconditioning method on synthetic data.", "questions": "- Could the author include a non-synthetic dataset to their experiments to validate their approach in a less controlled setup ?\n- The paper takes inspiration from differencing (subtracting each observation with the last one). However, the authors do not compare against this method in the experiments. Could the authors include that comparison ?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "- This paper proposes a very creative approach to improving learning of sequences.\n- The authors provide strong theoretical motivation and guarantees for their preconditioning approach\n- The experimental results show significant improvement of their method over no preconditioning.\n- However, the experimental section is limited to synthetic data alone, which is a pity given the trove of sequence data available. I would encourage the authors to include real-world data experiments to further strengthen the paper.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review! \n\n\nQuestion/weakness regarding nonsynthetic experiments) This is a fair point, we are looking into this! We have done some experiments on LLMs showing the benefit of the method and would be happy to add a small model over FineWeb.edu 10B in the final version. Please note though that the paper is mostly theoretical, and is pretty involved at that. We believe that the paper is of interest even without more experiments, although it does propose a practical method as the reviewer notes.\n\n\nQuestion on comparing to differencing) This method is actually the same as our method when n_coeffs=2, since the first Chebyshev polynomial is [1 -1], so we do compare to it. We will make it clear in the paper!"}, {"review_id": "XObBSe1GWD", "reviewer": "Reviewer_2AEH", "summary": "The paper investigates preconditioning of sequences (of inputs and outputs to linear dynamical systems) for the purpose of improving prediction accuracy. The paper proposes a preconditioning method that convolves the \"input sequence\" (actually the \"output sequence\" according to Algorithm 1) with the coefficients of the Chebyshev polynomial. The paper proves that this \"universal sequence preconditioning\" can improve the regret of two popular prediction algorithms: regression (in which the predictor coefficients are updated online) and (a new variant) of spectral filtering. Numerical examples/experiments are run on synthetic data, coming from (noisy) linear dynamical systems, and nonlinear dynamical systems (including a neural network).", "questions": "Can you please provide a clear and precise description of the problem that this paper addresses? In particular, is T assumed to be known in advance? (It seems so). Can you please comment on this assumption (in many applications, predictors are required to run for arbitrarily long T). \n\nCan you please explain the nonlinear dynamical system in line 220 more clearly?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The main strengths of the work are:\n- importance of problem area (investigation of preconditioning strategies for prediction)\n- mathematical rigor: I did not check all the proofs carefully, but the technical appendices were generally quite well-written and easy to follow.\n- the inclusion of numerical experiments is commendable for a paper that mostly makes theoretical contributions. \n\nIn my view, the main weaknesses of the work are:\n- Clarity of the presentation in the main paper. In contrast to the technical appendices in the supplementary material, the main manuscript is quite poorly written. For example, Line 92 refers to \"Eq: TODO\" (although this equation is given in the supplementary materials). Also, in Section 2.3 the regret of the spectral filtering algorithm is given as $\\tilde{O}(\\sqrt{T})$ whereas in the supplementary material it is given as $\\tilde{O}(T^{2/3})$.\n- Overall, the quality of the supplementary materials seems higher than that of the main submitted manuscript. (If I based my review on the main manuscript alone, I would probably recommend rejection). \n- Clarity: the paper also misses a clear problem statement. Readers familiar with the general problem setting can probably infer the overall goals and assumptions, but in my opinion the problem that the paper addresses should be precisely stated. For example, in the introduction the authors write \"The focus of this paper are not methods for sequence prediction, but rather preconditioning algorithms\", yet it appears that one of the main contributions of the paper is a more broadly applicable spectral filtering algorithm? Also, it's not immediately obvious whether the authors consider online or offline learning. For example, in Algorithm 1, line 7 makes it clear that prediction algorithms are learned offline, based on training data. However, algorithm 2 and 3 appear to update the prediction algorithm online. (Most likely the \"learning\" of the prediction algorithm in line 7 of Algorithm 1 refers to the tuning of hyper-parameters, and actual prediction algorithm is updated online -- still, it would be good to make this clear). \n- Clarity: overall, the main manuscript seems quite hastily written, e.g. \"Eqn: TODO\", sometime they refer to their algorithm as UPS instead of USP (e.g. Table 1). \n- Quality: although the core technical developments seem fairly sound, some of the statements around peripheral aspects are questionable. For example, on line 121, they claim that system identification is difficult. However, in their setting (linear systems with no noise -- which is the setting described in the supplementary material) system identification is easy (e.g. any subspace method should recover the system parameters perfectly). Also, there seems to be some confusion around \"closed-loop\" components. On line 127 they make clear that by \"closed-loop\" they refer to autoregressive terms (e.g. functions of previous outputs), whereas on line 108 they refer to Q as a closed-loop component, even though Algorithm 3: Line 5 shows that Q combines only with past inputs, not past outputs. \n\nOverall, the supplementary material seems relatively sound, but the sloppiness and lack of clarity in the main manuscript casts doubt on the quality of the work.", "was_revised": true, "final_justification": "The authors have addressed my concerns regarding the (lack of) clarity in the original manuscript; I am confident that the revised manuscript will be much improved. I have increased my score accordingly.", "rebuttal": "We thank the reviewer for their thoughtful review! First we respond to some of the items mentioned regarding clarity: \n\n\n1) Regret says $\\sqrt{T}$ in Section 2.3 versus $T^{⅔}$ in the supplementary material: In lines 108-112 of the supplementary material (Section 2.3) we explain that r (the bound on the coefficients of the preconditioning method which appears in front of the sqrt(T)) can be chosen to depend on T. Indeed, for Chebyshev preconditioning we choose the degree of the polynomial to depend logarithmically on T and since we show the maximum norm of the coefficients grows with T, we have a slight dependence which is why you see a regret $T^{⅔}$. If this is unnecessarily confusing we are happy to write it differently!\n\n\n2) Response to “For example, in the introduction the authors write \"The focus of this paper are not methods for sequence prediction, but rather preconditioning algorithms\", yet it appears that one of the main contributions of the paper is a more broadly applicable spectral filtering algorithm?”\nFirst, we apply preconditioning to both 1) spectral filtering and 2) convex regression and prove that it helps both algorithms. Moreover, in the experimental section, we apply preconditioning to a DNN algorithm. That is why we say that the goal is about preconditioning the sequence rather than focusing on one particular learning algorithm. \n\n\n3) Response to offline vs online: In line 41-42 we say “Here we provide the offline train-test version of the method and give the online version in Appendix B as Algorithm 4.” Let us know if you would prefer just observing the online version of the algorithm for clarity, we are happy to remove the offline version or put it in Appendix B instead. All of our theorems are clear on which algorithm they refer to (and they are online just fyi). \nThe learning of the prediction algorithm is typically done through gradient descent on the algorithm’s parameters. The prediction algorithm is not updated online– at test time you use the learned parameters of the algorithm. We are happy to remove Algorithm 1 and replace it with Algorithm 4– it is just there for further clarity for the reader.\n\n\n4) Response to “For example, on line 121, they claim that system identification is difficult”: Thank you for catching this, we didn’t mean it quite as it is as written and will fix this. It’s true that there are many methods for system identification that we don’t mention, for example [2]. What we meant to highlight was that these methods have regret bounds that depend on hidden dimension, which can be prohibitively large whereas the method introduced in our work allows for a regret that depends only logarithmically on hidden dimension. \n[2] Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht Proceedings of the 31st Conference On Learning Theory, PMLR 75:439-473, 2018.\n\n\n5) General response to the clarity/typos: The reviewer is correct, and we apologize for the hasty writing at times. A main author got very sick and it caused the main body writing to be rushed before submission. We appreciate the reviewer’s reading of the supplementary material and seeing through the unpolished writing. Importantly, we hope the reviewer sees that our technical results and experiments were not rushed and are very sound. We promise to fix typos and polish the writing.\n\n\nQuestion 1) We would like to make sure we fully answer the reviewer’s concern regarding the problem statement. Can the reviewer please look at the statement of Theorem C.1 on line 658 and Theorem 2.1 on line 693 and clarify which aspects of the problem they would like to be better fleshed out? With respect to the horizon being known in advance– for spectral filtering the horizon T must be set in advance. T can be arbitrarily large but it does need to be known beforehand. This is a common assumption in online learning. Indeed, Hedge/EXP3/OGD all require knowing T in advance to tune the learning rate appropriately. \n\n\nQuestion 2) Yes. First, $\\sigma$ represents the sigmoid function which we apply elementwise (we will make sure to define this in the text). Next, we sample A_1 and A_2 using the same as for the linear dynamical system. So, to be clear,  given a complex threshold $\\tau_{\\text{threshold}}$ we sample eigenvalues to be drawn uniformly at random to have radius between L and U, which are 0.9 and 0.9999 respectively, and complex part bounded by $\\tau_{\\text{threshold}}$. We then find an asymmetric real valued matrix with this spectrum. We generate B_1, B_2, and C randomly– each entry is an independent Gaussian– and then we renormalize them."}, {"review_id": "Q3y6FNUPB2", "reviewer": "Reviewer_EHYC", "summary": "In this paper, the authors investigate which input sequence modification method would facilitate the learning process of model learning and improve its prediction accuracy, which is referred as the preconditioning problem. Inspired by the theory of linear dynamic systems, they propose a novel and universal preconditioning method that convolves the input sequence with the coefficients of the Chebyshev or Legendre polynomials. They further combine the proposed universal preconditioning method with the spectral filtering method and propose a new spectral filtering algorithm. The authors then provide comprehensive theoretic analysis on the proposed preconditioning method and shown that its regret bound is smaller than that of previous methods. Particularly, the proposed spectral filtering algorithm has a sublinear hidden-dimensional free regret bound, even if the hidden transition matrix is asymmetric. Experiments on synthetic data show that the proposed preconditioning method is applicable to diverse data types and learning algorithms.", "questions": "1. There is no explicit definition of $p _n(\\cdot)$ in the last equation presented on page 5. Its definition only appears in line 2 of algorithm 3, that is, $p _n(x) = \\sum _{i=0}^n c_i x^{n-i}$. It is encouraged to add this definition before the last equation on page 5 to enhance clarity of expression.\n2. In line 670, the correct one should be $G \\leq \\sqrt{d _{\\rm out}}$, according to the inequality between line 669 and 670.\n3. In the equation between line 664 and 665, the authors show that $\\sum _{t=1}^T \\ell _t(\\\\mathbf{Q}^t) - \\min _{\\\\mathbf{Q}^{\\star} \\in \\\\mathcal{K}} \\sum _{t=1}^T \\ell_t (\\\\mathbf{Q}^{\\star}) \\leq \\frac{3}{2} GD \\sqrt{T}$. Also, they show that $D \\leq 2 C _{\\rm domain} n^2 \\Vert \\\\mathbf{c} \\Vert_1 $ and $G \\leq \\sqrt{d _{\\rm out}}$ in line 665 and line 670, respectively. Thus, the correct one should be $\\sum _{t=1}^T \\ell _t(\\\\mathbf{Q}^t) - \\min _{\\\\mathbf{Q}^{\\star} \\in \\\\mathcal{K}} \\sum _{t=1}^T \\ell_t (\\\\mathbf{Q}^{\\star}) \\leq 3 C _{\\rm domain} n^2 \\sqrt{d _{\\rm out}} \\Vert \\\\mathbf{c} \\Vert _1$ in line 671.\n4. In line 682, the authors show that $\\Vert \\hat{\\\\mathbf{y}} _t - \\\\mathbf{y} _t \\Vert_1 = \\Vert \\sum _{s=0}^{t-n-1} \\\\mathbf{C} p^{\\\\mathbf{c}} _n(A) \\\\mathbf{A}^s \\\\mathbf{B} \\\\mathbf{u} _{t-n-s} \\Vert _1$ holds. Then, they further show that $\\Vert \\\\mathbf{C} p^{\\\\mathbf{c}} _n(A) \\\\mathbf{A}^s \\\\mathbf{B} \\Vert _1 \\leq \\max _{\\\\lambda \\in \\\\lambda(\\\\mathbf{A})} \\vert p^{\\\\mathbf{c}} _n(\\\\lambda) \\vert \\cdot \\Vert \\\\mathbf{C} \\Vert \\Vert \\\\mathbf{B} \\Vert$ holds for any $j = 0, \\ldots, t-n-1$. Since $\\Vert \\\\mathbf{u} _j \\Vert _1 \\leq 1$, by triangleq inequality we should have \n$$\n\\begin{aligned}\n\\Vert \\sum _{s=0}^{t-n-1} \\\\mathbf{C} p^{\\\\mathbf{c}} _n(A) \\\\mathbf{A}^s \\\\mathbf{B} \\\\mathbf{u} _{t-n-s} \\Vert _1 \\leq & \\sum _{s=0}^{t-n-1} \\Vert \\\\mathbf{C} p^{\\\\mathbf{c}} _n(A) \\\\mathbf{A}^s \\\\mathbf{B} \\\\mathbf{u} _{t-n-s} \\Vert _1 \\leq \\sum _{s=0}^{t-n-1} \\Vert \\\\mathbf{C} p^{\\\\mathbf{c}} _n(A) \\\\mathbf{A}^s \\\\mathbf{B} \\Vert _1 \\Vert \\\\mathbf{u} _{t-n-s} \\Vert _1 \\leq \\sum _{s=0}^{t-n-1} \\Vert \\\\mathbf{C} p^{\\\\mathbf{c}} _n(A) \\\\mathbf{A}^s \\\\mathbf{B} \\Vert _1 \\\\\\\\\n& \\leq \\sum _{s=0}^{t-n-1} \\max _{\\\\lambda \\in \\\\lambda(\\\\mathbf{A})} \\vert p^{\\\\mathbf{c}} _n(\\\\lambda) \\vert \\cdot \\Vert \\\\mathbf{C} \\Vert \\Vert \\\\mathbf{B} \\Vert = (t-n-1) \\max _{\\\\lambda \\in \\\\lambda(\\\\mathbf{A})} \\vert p^{\\\\mathbf{c}} _n(\\\\lambda) \\vert \\cdot \\Vert \\\\mathbf{C} \\Vert \\Vert \\\\mathbf{B} \\Vert.\n\\end{aligned}\n$$\nTherefore, we should have\n$$\n\\min _{\\\\mathbf{Q}^{\\star} \\in \\\\mathcal{K}} \\sum _{t=1}^T \\ell_t (\\\\mathbf{Q}^{\\star}) \\leq \\sum _{t=1}^T \\ell _t (\\hat{\\\\mathbf{Q}}) = \\sum _{t=1}^T \\Vert \\hat{\\\\mathbf{y}} _t - \\\\mathbf{y} _t \\Vert_1 \\leq \\sum _{t=1}^T (t-n-1) \\max _{\\\\lambda \\in \\\\lambda(\\\\mathbf{A})} \\vert p^{\\\\mathbf{c}} _n(\\\\lambda) \\vert \\cdot \\Vert \\\\mathbf{C} \\Vert \\Vert \\\\mathbf{B} \\Vert.\n$$\nIt seems that it is possible to derive a slightly sharper bound, that is, $\\frac{(1+T)T}{2}$. It is also encouraged to include the above details in the paper enhance clarity of expression.\n5. In Eq. (18), the correct one seems to be $\\Vert U _{n-1}(z) \\Vert \\leq n$. If $n$ is even, we have $\\Vert U _{n-1}(z) \\Vert \\leq 2 \\sum _{j \\geq 0, j even}^n T_j (z) \\leq 2 \\cdot \\frac{n}{2} \\cdot 2 = 2n$, using Eq. (16) that $\\Vert T_j(z) \\Vert \\leq 2$ for any $j$. The case that $n$ is    add is similar.\n6. I am confused about the third line of the equation in line 918. It seems that we can only get \n$$\n\\sum _{k=0}^\\infty a _k \\vert r \\vert^{2k+1} \\min (1,(2k+1)\\vert \\theta \\vert) = \\sum _{k=0}^\\infty a _k \\vert r \\vert^{2k} \\cdot \\vert r \\vert \\min (1,(2k+1)\\vert \\theta \\vert) \\leq \\sum _{k=0}^\\infty a _k \\vert r \\vert \\min (1,2(2k+1)\\vert \\sin(\\theta) \\vert) = \\sum _{k=0}^\\infty a _k \\min (\\vert r \\vert,2(2k+1)\\vert r \\sin(\\theta) \\vert).\n$$\nCould the authors provide more explanations on this?\n7. The polynomials used in this paper include Chebyshev or Legendre polynomials, and both of them are orthogonal polynomials. Since Chebyshev or Legendre polynomials are special cases of Jacobi polynomial, is it possible to directly use the Jacobi polynomial ?", "limitations": "The authors have addressed the limitations of their work in line 278-380.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The motivation of this work is clear and theoretic solid. The inspiration comes from the theory of linear dynamic systems, and the authors provide comprehensive theoretic analysis for the proposed preconditioning method and show that it can achieve smaller regret bound.\n- The experiments on synthetic data verify that the proposed method has universal adaptability. It can be applied on data that do not form a linear dynamic system and various learning algorithms including recurrent neural network.\n\n**Weakness**\n- The major weakness of this paper is the presentation quality. The manuscript has several typographical errors, insufficient contextual details in certain parts, and requires improvement in logical coherence. For example, sentences ''...potentially shrinking the domain'' in line 33 and ''..., is a hard problem'' in line 68 are missing a period. Besides, the derivations of some theoretical results exhibit ambiguities that require clarification. See Question part for more detail.\n- The experiments are conducted only on synthetic data without validation on real-world data, which makes the proposed method less convincing. It is encouraged to conduct experiments on real-world datasets.", "was_revised": true, "final_justification": "My previous concerns about the paper were mainly regarding some mathematical formulas, which the author has explained quite clearly in their rebuttal.", "rebuttal": "We thank the reviewer for their thougthful review! First we respond to the two weaknesses and then the questions. \n\nWeakness 1)  General response to the clarity/typos: The reviewer is correct, and we apologize for the hasty writing at times. A main author got very sick and it caused the main body writing to be rushed before submission. We appreciate the reviewer’s reading of the supplementary material and seeing through the unpolished writing. For most of the ambiguities in the technical details-- the difference is just that we were not concerned with optimizing constants. But we deeply value the reviewer’s time and careful questions and we will make the suggested improvements!\n\nWeakness 2) This is a fair point, we are looking into this! We have done some experiments on LLMs showing the benefit of the method and would be happy to add a small model over FineWeb.edu 10B in the final version. Please note though that the paper is mostly theoretical, and is pretty involved at that.  We believe that the paper is of interest even without more experiments, although it does propose a practical method as the reviewer notes. \n\n\nQuestions 1-4) We thank the reviewer for their incredible/careful attention and time to read through these details. We note that we were not concerned about optimizing the constants for the bound, but it is always a good idea to do so and we will make these edits.\n\nQuestion 5) We appreciate the reviewer finding a missing factor of 2 and we will propagate this change.\n\nQuestion 6) Your equation is upper bounded by our line 3 since $|r| \\leq 1$ so you can replace the LHS of the minimum with 1 and then observe that for any $a,b \\geq 0$, $\\min (a,2b) \\leq 2 \\min(a,b)$. Let us know if you would like further explanation!\n\nQuestion 7) It’s a good idea! However, for the theory, we need the property that 1) the maximum abosolute value of the polynomial over the domain (which represents the eigenvalues of the system transition matrix) be very small and that 2) the coefficients of the polynomial also stay somewhat small. Of the shelf, Jacobi polynomials don’t guarantee this property."}, {"review_id": "FboB7eiMCF", "reviewer": "Reviewer_S8cH", "summary": "This paper aims to solve sequential prediction via preconditioning. Based on Chebyshev polynomials, the authors propose a universal sequence preconditioning methodology that be applied as a convolutional preconditioned regression and convolutional preconditioned spectral filtering. The authors prove the convergence rate for a particular linear dynamic system, and experiment the methods on various settings, including linear dynamic system, non-linear dynamic system, and deep RNN.", "questions": "The questions follow from the \"Weakness\":\n1. Could you fix all the missing references, such as \"Eq.TO DO\" and \"Algorithm 4\"?\n2. Could you clarify all the implicit dependence?\n3. Could you discuss how sharp your theoretical results are?\n4. Could you provide more analysis comparing Chebyshev and Legendre polynomials in terms of their strength and weakness in terms of theoretical guarantee and empirical performance?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. The authors prove the explicit convergence rate.\n2. The authors give intuition behind the proof and the trade-off with respect to parameters (such as the degree of polynomials and the threshold).\n3. The algorithms are tested empirically.\n\nWeakness:\n1. There is unclear implicit dependence: Theorem 2.1 does not seem to be dependent on the degree of the polynomial $n$, which is surprising considered Algorithm 2 heavily depends on the choice of $n$. I would suspect that there is an implicit dependence on $n$ hidden somewhere, for example perhaps like the scaling $n=\\log(T)$ on line 114? If the result is completely independent of $n$, then the authors should explain why that is the case.\n2. Slow convergence rate: The convergence rate in Theorem 2.1 is $T^{-2/13}$ (up to log factors), which is quite slow. It is unclear from this paper whether this is the actual empirical convergence rate, or a pessimistic bound due to proof technique.", "was_revised": true, "final_justification": "The authors adequately address my concerns and discuss the possible improvements on the bound for Chebyshev polynomials. I agree with other reviewers' that experiments beyond synthetic data will strengthen the paper.", "rebuttal": "We thank the reviewer for their thougthful review! \n\nWeakness 1) Thank you so much for finding this. We implicitly choose n to optimally depend on T (line 702 on page 23) and did not make this choice clear in the statement of the theorem. We will change this. If the reviewer is curious, the dependence on degree n is in line 701 and we could include this and discuss it in the main body of the paper if the reviewer thinks it would be a good idea.\n\nWeakness 2) The reason the rate looks slow (i.e. not the typical $O(\\sqrt{T})$)  is that it is independent of hidden dimension and extends to some systems with asymmetric transition matrices. It is unclear if you can hope for better in the worst case (i.e. letting hidden dimension grow very large and the transition matrix having large imaginary component) which we discuss in Section A.3. Importantly, the method shows huge convergence gains empirically as our synthetic experiments show. \n\nQuestions\n1) Yes, we apologize for the typos and thank the author for seeing the merit of the work despite typos. A sudden illness caused the writing of the main body of the paper to be rushed. \n\n\n2) We clarified the implicit dependence above that in the case where $p_n(x)$ is chosen to be the n-th degree monic chebyshev polynomial, we pick $n = (10/13) \\log_2 (8 T^{3/2}/ 3 \\sqrt{d})$. We note that the proof of the theorem starting in line 699 makes all the dependencies explicit. We will include the choice of n in the statement of the theorem and make this clearer. We thank the reviewer for noting it!\n\n\n3) We discuss sharpness in Section A.3 in terms of avoiding polynomial/linear dependence on the hidden dimension of the transition matrix. Please let us know if you have further questions on this and we would be very happy to answer!\n\n\n4) Only Chebyshev polynomials provably give us sublinear regret right now. Our Lemma 4.1 holds for Chebyshev polynomials and we note that a similar theorem (at least on the region [-1,1] we aren’t sure about extending it to the complex plane) for Legendre polynomials exists but is a factor $\\sqrt{\\pi n}$ larger. On the other hand, the coefficients of the Chebyshev polynomial grow slightly faster than the coefficients of the Legendre polynomial. We prove that the maximum absolute value coefficient for the n-th monic Chebyshev can be bounded by $2^0.3n$ and I believe you could show something slightly tighter (ie. $2^{0.28n}$) for Legendre but it isn’t as obvious how to do it. Empirically we don’t see a huge difference between the two but it might be interesting to compare them on more applications in the future."}]

Author rebuttal:

Meta-review: In this paper, the authors consider the preconditioning problem in sequential prediction. They propose Universal Sequence Preconditioning (USP), which applies convolution to the input sequence using coefficients of Chebyshev or Legendre polynomials. 
This operation corresponds to applying a polynomial to the hidden transition matrix. For marginally stable asymmetric linear dynamical systems, the method yields the first sublinear regret bounds independent of the latent dimension (up to logarithmic factors). It also extends spectral filtering to the complex plane with theoretical guarantees.
Through numerical experiments, the authors show that the approach improves prediction across linear and nonlinear settings and learning algorithms, including RNNs. 

After the rebuttal and discussion, reviewers were broadly positive about the paper. Reviewers did note serious presentation issues (for example, an equation referred to as “Eq. TO DO”), but they agreed that the paper could achieve sufficient clarity if the authors incorporate the discussion feedback in the next revision. There was also a consensus that experiments with non-synthetic data would enhance the impact of the paper. The authors appear to have already conducted some such experiments (see, for example, the discussion between Reviewer EHYC and the authors), and it is expected that these results will appear in the final version.

While the writing of the paper requires significant improvement, reviewers did not find these issues to warrant another round of review (several reviewers noted that the supplementary material is written much more clearly). At a minimum, the method provides a strong initialization for other learning methods and could have broad impact across domains. For these reasons, I lean toward acceptance.
Decision: Accept (spotlight)