Research map / Bandits and online learning / Online convex optimization and games

The Power of Second Order Methods for Sequence Preconditioning

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online decision-making with feedback structure · 0 citations (OpenAlex)

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.

Shows that running second-order VAW on a short ARX feature vector gives polylogarithmic-in-T, dimension-free regret for marginally stable LDSs, extending USP via Faber polynomials to spectra in a wedge around the negative real axis.

Problem

Sequence prediction for marginally stable linear dynamical systems with long memory: prior methods have regret polynomial in horizon or linear in hidden dimension, and Universal Sequence Preconditioning requires complex arguments to shrink with T.

Approach

Apply the second-order Vovk-Azoury-Warmuth forecaster directly to a short autoregressive-with-inputs feature vector; its regret depends logarithmically on comparator norm, absorbing the exponentially large USP preconditioner coefficients. Faber polynomials on circular sectors extend the comparator existence to spectra in W_{pi-delta}.

Key results

• Theory: VAW on raw ARX features achieves cumulative squared loss O(delta^-4 log^2(TYL)) for spectra in W_{pi-delta}, versus O(T^{11/13}) for first-order USP on real spectra.
• Chebyshev-preconditioned VAW gives O(log^2 T) cumulative loss for real spectra in [-1,1] (Corollary on Chebyshev instantiation).
• Experiments on synthetic LDS (d=100, T=5000): VAW continues to benefit up to degree ~20 while OGD and Adam stop improving after degree ~14.

Surprising findings

• Empirically, the Chebyshev-preconditioned signal has much smaller norm than the raw signal in many regimes, suggesting learning the autoregressive coefficients may be unnecessary.

Limitations

• The analyzed VAW algorithm must learn the autoregressive coefficients, departing from USP's offline preconditioning.
• VAW has a much larger memory footprint than first-order methods.
• Angular-gap dependence delta^-4 is not tight relative to the delta^-1 memory lower bound; the flat-polynomial coefficient conjecture is only partially proved.

Experimental setup

Datasets: synthetic linear dynamical system data

Benchmarks: synthetic LDS sequences (d=100 and d=10)

Metrics: normalized prediction error maximum signal norm

Baselines: Online Gradient Descent (OGD) Adam Universal Sequence Preconditioning (first-order)

Builds on: Universal Sequence Preconditioning Vovk-Azoury-Warmuth forecaster Online Newton Step Faber polynomials

Closest papers by meaning

• Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.95)
• Provable Length Generalization in Sequence Prediction via Spectral Filtering (ICML 2025 · similarity 0.89)
• A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems (NeurIPS 2026 · similarity 0.87)
• Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances (ICLR 2024 · similarity 0.86)
• SpectraLDS: Provable Distillation for Linear Dynamical Systems (NeurIPS 2025 · similarity 0.85)
• MaRK: Markov-adapted Recurrent Kernels for Dynamic Operator Conditioning in State Space Models (NeurIPS 2026 · similarity 0.85)