Universal Sequence Preconditioning

We thank the reviewer for their thougthful review!

Weakness 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.

Weakness 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.

Questions

1. 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.

2. 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!

3. 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!

4. 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.

We thank the reviewer for their thougthful review! First we respond to the two weaknesses and then the questions.

Weakness 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!

Weakness 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.

Questions 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.

Question 5) We appreciate the reviewer finding a missing factor of 2 and we will propagate this change.

Question 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!

Question 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.

We thank the reviewer for their thoughtful review! First we respond to some of the items mentioned regarding clarity:

1. 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!

2. 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?” First, 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.

3. 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). The 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.

4. 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. [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.

5. 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.

Question 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.

Question 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.

We thank the reviewer for their thoughtful review!

Question/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.

Question 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!

Thank you for your insightful review! Our responses are below.

Weakness 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.

Weakness 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).

Weakness 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. Because 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!

Weakness 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. [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

Question 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.

Question 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.

Question 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.