Research map / Bandits and online learning / Online convex optimization and games
Universal Sequence Preconditioning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Universal Sequence Preconditioning, which convolves the target sequence with monic Chebyshev (or Legendre) polynomial coefficients, and proves sublinear, hidden-dimension-independent regret for regression and a new spectral filtering variant on marginally stable, mildly asymmetric linear dynamical systems.
Problem
Learning linear dynamical systems and sequence prediction with online regret guarantees that are sublinear, independent of hidden dimension, valid for marginally stable systems, and applicable to asymmetric transition matrices.
Approach
Convolving the target sequence with coefficients of a polynomial (Chebyshev or Legendre) corresponds to applying that polynomial to the hidden transition matrix, so a Chebyshev choice shrinks the residual term exponentially in degree while keeping the learnable coefficient norm controlled; combined with regression or a new spectral filtering basis (eigenvectors of an integral over the complex spec
Key results
- Regression with USP achieves regret O~(T^{-2/13}) versus vacuous O(T^{5/2}) for vanilla regression on marginally stable systems.
- USP with a new spectral filtering basis achieves O~(T^{-3/13}) regret for mildly asymmetric systems, improving on regression's exponent.
- On synthetic linear dynamical system data, Chebyshev degree-5 preconditioning reduces regression error from 0.74 (baseline) to 0.15 at tau=0.01.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Chebyshev degree 5 preconditioning | Regression · Linear LDS, τ_thresh=0.01 | absolute error: 0.74 -> 0.15 | Helped |
| Add Chebyshev degree 5 preconditioning | Regression · Linear LDS, τ_thresh=0.1 | absolute error: 1.92 -> 0.66 | Helped |
| Add Chebyshev degree 5 preconditioning | Spectral Filtering · Linear LDS, τ_thresh=0.01 | absolute error: 5.94 -> 0.69 | Helped |
| Add Chebyshev degree 5 preconditioning | Spectral Filtering · Linear LDS, τ_thresh=0.1 | absolute error: 0.89 -> 0.34 | Helped |
| Add Chebyshev degree 2 preconditioning | 2-layer DNN · Linear LDS, τ_thresh=0.01 | absolute error: 4.49 -> 2.31 | Helped |
| Add Chebyshev degree 10 preconditioning | Spectral Filtering · Nonlinear data, τ_thresh=0.01 | absolute error: 153.8 -> 0.26 | Helped |
| Add Chebyshev degree 5 preconditioning | 2-layer DNN · Nonlinear data, τ_thresh=0.01 | absolute error: 10.46 -> 0.19 | Helped |
| Add Chebyshev degree 5 preconditioning | 10-layer DNN · 10-layer DNN-generated data | absolute error: 0.54 -> 0.08 | Helped |
| Use higher-degree Chebyshev preconditioning (degree 10 rather than degree 5) (ablation) | Regression · Linear LDS, τ_thresh=0.01 | absolute error: 0.15 -> 0.77 | Hurt |
| Use higher-degree Chebyshev preconditioning (degree 10 rather than degree 5) (ablation) | Spectral Filtering · Linear LDS, τ_thresh=0.01 | absolute error: 0.69 -> 3.25 | Hurt |
| Learn coefficients jointly instead of using fixed coefficients (ablation) | 2-layer DNN · Nonlinear data, τ_thresh=0.01 | absolute error: 0.19 -> 45.40 | Hurt |
| Learn coefficients jointly instead of using fixed coefficients (ablation) | 10-layer DNN · 10-layer DNN-generated data | absolute error: 0.08 -> 2.13 | Hurt |
Surprising findings
- Learned preconditioning coefficients destabilize the DNN on nonlinear and RNN-generated data.
- Chebyshev/Legendre performance degrades for degrees above 5-10 because the coefficient l1-norm grows exponentially.
Limitations
- Theoretical guarantees hold only for eigenvalues whose imaginary part is bounded by O(1/log T), and the spectral filtering bound (T^{-1/39}) is described by the authors as rather weak.
- Chebyshev coefficient norms grow exponentially with degree, so performance degrades at high degree in experiments.
Experimental setup
Datasets: ETTh1
Benchmarks: ETTh1
Metrics: absolute prediction error on final 200 predictions regret
Baselines: Regression without preconditioning Spectral Filtering without preconditioning 2-layer DNN without preconditioning 10-layer LSTM without preconditioning
Builds on: spectral filtering online gradient descent differencing (ARIMA)
Closest papers by meaning
- The Power of Second Order Methods for Sequence Preconditioning (NeurIPS 2026 · similarity 0.95)
- Provable Length Generalization in Sequence Prediction via Spectral Filtering (ICML 2025 · similarity 0.88)
- The Expected Loss of Preconditioned Langevin Dynamics Reveals the Hessian Rank (AAAI 2024 · similarity 0.87)
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances (ICLR 2024 · similarity 0.87)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.87)
- Preconditioned Langevin Dynamics with Score-based Generative Models for Infinite-Dimensional Linear Bayesian Inverse Problems (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.