# The Power of Second Order Methods for Sequence Preconditioning

arXiv: https://arxiv.org/abs/2605.08390 · HTML: https://mlsanity.com/paper/2605.08390/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 15 of 15)

- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [No-Regret Prediction in Marginally Stable Systems](https://mlsanity.com/paper/2002.02064/) (2020)
- [Improved rates for prediction and identification of partially observed linear dynamical systems](https://mlsanity.com/paper/2011.10006/) (2020)
- [SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory](https://mlsanity.com/paper/2010.05899/) (2020)
- [Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples](https://mlsanity.com/paper/2010.04015/) (2020)
- [Universal Sequence Preconditioning](https://mlsanity.com/paper/2502.06545/) (2025)
- [Universal Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2508.11990/) (2025)
- [Spectral Filtering for Complex Linear Dynamical Systems](https://mlsanity.com/paper/2601.22400/) (2026)

## Built on by (most cited first, 1 of 1)

- [Sharp Minimax Regret for Infinite-Memory Logistic Prediction](https://mlsanity.com/paper/2608.26515/) (2026)

## Abstract (arXiv)

Sequence prediction methods for linear dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows linearly with the hidden dimension of the underlying generative model. While many methods have been developed to address this regime with varying success, we show that simply using the second-order Vovk-Azoury-Warmuth (VAW) algorithm to learn a short autoregressive-with-inputs (ARX) model achieves astoundingly strong results: for bounded sequential data from a marginally-stable linear dynamical system with spectra in the complex disk except for angular wedge of width δ around the negative real axis, this algorithm achieves dimension-free regret Oleft( δ-4 log2 T right). These bounds are state-of-the-art to our knowledge. The key components for our result come from 1) using the theory of ``Universal Sequence Preconditioning'' (USP) citemarsdenuniversal to prove the existence of an optimal setting of autoregressive coefficients, 2) the application of VAW which takes better advantage of the memory compression provided by USP, and 3) the analysis of Faber polynomials on circular sectors to extend these results to systems with complex spectra.