The Power of Second Order Methods for Sequence Preconditioning

Annie Marsden, Elad Hazan · 2026

Read The Power of Second Order Methods for Sequence Preconditioning by Annie Marsden, Elad Hazan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08390.txt.

Introduction

Annie Marsden and Elad Hazan show that a classic second-order online learning algorithm handles long-memory sequence prediction far better than expected. For marginally stable linear systems, most methods pay regret that grows with the hidden state dimension, and a shelf of specialized fixes has grown up around the problem.

Feeding a short autoregressive model to the Vovk-Azoury-Warmuth algorithm instead gives dimension-free regret, logarithmic in the time horizon, as long as the system's spectrum avoids a wedge around the negative real axis. The proof leans on universal sequence preconditioning to show a good short model exists. The authors present the bounds as state of the art for this regime.

Catalog record

CREATORAnnie Marsden, Elad Hazan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.08390

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Power of Second Order Methods for Sequence Preconditioning Annie Marsden, Elad Hazan Abstract Sequence prediction methods for dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows polynomially with the hidden dimension of the underlying generative model. Universal Sequence Preconditioning (USP) 16 is a method that compresses any sequence which comes from a linear dynamical system into a “preconditioned” sequence which requires exponentially shorter memory for accurate prediction. However, the preconditioned sequence yields exponentially larger diameters and gradients, hindering USP from unlocking optimal regret bounds. Inspired by the minimum description length principle, we show that the Vovk-Azoury-Warmuth (VAW) algorithm is naturally matched to the USP regime. Indeed, it takes advantage of the memory compression while remaining robust to the exponential explosion of the diameter. We prove that combining USP with VAW achieves astoundingly strong results: for any marginally-stable linear dynamical system, this algorithm achieves polylogarithmic regret 𝒪 ⁡ ( log 3 ⁡ T ) \mathcal{O}\left(\log^{3}T\right) even in the presence of asymmetric hidden transition matrices. Finally, we extend the applicability of USP beyond bounded-spectrum systems by providing new complex-analytic bounds on Chebyshev polynomials, allowing for systems with constant complex arguments. 1 Introduction The central challenge in sequence prediction is the simultaneous presence of long memory and high hidden dimension of the underlying generative process. Universal Sequence Preconditioning (USP) 16 addresses this challenge by transforming the sequence into one that can be predicted with short memory, without sacrificing predictive accuracy. USP is “universal” because its transformation is signal-agnostic, and should provide a clear benefit to any downstream learning algorithm. This sounds too good to be true. However, previous work 16 showed that such reductions are possible for signals that arise from certain linear dynamical systems. The method they develop is to convolve the original signal with the coefficients of the Chebyshev polynomial. This construction achieves an exponential compression of memory, reducing the effective memory to be logarithmic in sequence length (or horizon). However, this comes at a cost: the Chebyshev coefficients grow exponentially large with the degree, resulting in large optimal diameter. This creates a mismatch with first-order learning methods, which scale linearly with optimal diameter, yielding suboptimal regret. In this work, we resolve this tension using second order online learning methods. At a high level, the effectiveness of a preconditioner is governed by two quantities: the effective memory of the transformed representation (number of parameters) and the magnitude of the optimal diameter. In the setting of USP, we can think of the preconditioned signal as a compressed representation of the original signal. The compressed representation requires a history which is linear in the degree of the Chebyshev polynomial, however the coefficient magnitude grows very large. This evokes the Minimum Description Length (MDL) principle 18 ; 8 , which seeks to minimize the combined cost of a model’s structural complexity and the bit-length required to represent its parameters. For polynomials, the minimum description length principle suggests that the most efficient representation balances the degree of the polynomial and the logarithm of the coefficients magnitude. Inspired by this principle, we observe that the regret of the Vovk–Azoury–Warmuth (VAW) forecaster 1 ; 22 matches this balance: it grows linearly with the effective memory and only logarithmically with the the optimal diameter. Applying VAW to USP results in an astoundingly strong algorithm– its regret is polylogarithmic with respect to the horizon and the hidden dimension, and applies to systems with asymmetric transition matrices. This greatly improves upon the original regret bound \mathcal{O}(T^{11/13}) of 16 which only applies to systems with eigenvalues with vanishing complex component. Moreover, by proving new complex-analytic bounds for monic Chebyshev polynomials, we weaken the original restriction for USP that the argument of the complex eigenvalues vanish at the rate o(1/\log^{2}T) . We can now tolerate complex eigenvalues with constant argument. 1.1 Our Results We resolve the fundamental tension between universal sequence preconditioning and the exponentially large gradient norms it induces by using second-order online learning methods. Our main contributions are as follows: Logarithmic Regret for Sequence Prediction: We propose a novel algorithm that applies the Vovk-Azoury-Warmuth (VAW) forecaster to raw sequences while concurrently learning the preconditioning coefficients. We obtain cumulative prediction error guarantee of \mathcal{O}\left(Y^{2}\log^{3}(1+TYS)\right) , where Y is the maximum norm of the output, T is the horizon, and S represents terms specific to the generative linear dynamical system (the norms of the input and output projection matrices and the “condition number” of the diagonalization of the hidden transition matrix). For the formal statement of our main result, see Theorem 2 . Because the regret of VAW scales only logarithmically with the norm of the comparator, it successfully absorbs the exponential parameter blowup inherent in Chebyshev preconditioning. While previous first-order approaches achieved a polynomial cumulative regret bound of \tilde{\mathcal{O}}(T^{11/13}) , our second-order VAW approach exponentially improves this to optimal polylogarithmic \mathcal{O}(\log^{3}(T)) regret. Extension to Systems with Constant Complex Arguments: We extend the theoretical guarantees of Universal Sequence Preconditioning (USP) to a strictly broader class of dynamical systems. We establish new, tight complex-analytic bounds for monic Chebyshev polynomials (Lemma 1 ), proving that the preconditioner’s approximation error remains exponentially vanishing even when the underlying system’s eigenvalues have a constant complex argument. Dependence on T Dependence on d Complex Angle Methods Direct prediction methods: Hazan et al. (2018) 10 , Cayley-Hamilton and regret minimization (folklore, e.g. 13 ; 4 ; 12 ) T^{O(1)} d^{O(1)} \pi Recovery methods: Simchowitz et al. (2019) 19 ; Tsiamis & Pappas (2019) 20 ; Lee (2022) 14 ; Bakshi et al. (2023) 2 . T^{O(1)} (\log d)^{O(1)} 1/\log(T)^{O(1)} Marsden & Hazan (2025) 15 . (\log T)^{O(1)} (\log d)^{O(1)} O(1) Ours Table 1: Cumulative prediction error bounds for marginally stable linear dynamical systems with asymmetric transition matrices. “Complex Angle” denotes the required bound on the absolute value of the angular component of complex eigenvalues which ranges from 0 to \pi . 1.2 Related Work Our work is most closely related to the literature on prediction in latent linear dynamical systems, rather than recovery. Early spectral-filtering results demonstrated online competitiveness with the best LDS predictor without explicit system identification, but relied on strong spectral structure like symmetry 11 . 10 later extended spectral filtering to general latent LDSs using a convex relaxation that accommodates phases and no longer requires a symmetric transition matrix. However, in the asymmetric setting their guarantee still has polynomial dependence on the horizon and polynomial dependence on the hidden dimension, so it does not yield a polylogarithmic cumulative prediction error bound in the regime we study. Polynomial in d and T bounds are also a classical consequence of the Cayley–Hamilton theorem and realization theory; see, e.g., 13 ; 4 . A second line of work studies marginally stable systems more directly. 7 proved no-regret prediction guarantees for marginally stable systems with polynomial system parameter dependence. In the fully observed adversarial setting their bounds remain polynomial in the horizon, while their stronger polylogarithmic-in- T results rely either on stochastic assumptions or on a reduction to finite-memory autoregressive prediction. These results aren’t direct comparators since our focus is absolute cumulative prediction error for a noiseless input–output LDS. There is also a body of work on partially observed prediction through the Kalman filter.

Read the complete text