Technical Summary: The Power of Second Order Methods for Sequence Preconditioning

Problem Statement

The central challenge in sequence prediction for dynamical systems with long memory (specifically, marginally stable linear dynamical systems) is the simultaneous presence of long memory and high hidden dimension. While Universal Sequence Preconditioning (USP) [16] offers a method to compress such sequences into representations requiring exponentially shorter memory (logarithmic in the horizon $T$), it introduces a critical trade-off. The USP transformation, which relies on convolving signals with Chebyshev polynomial coefficients, results in a "preconditioned" sequence with exponentially large optimal diameters and gradient norms.

This exponential growth in parameter magnitude creates a mismatch with standard first-order online learning methods (e.g., Online Gradient Descent), whose regret bounds scale linearly with the diameter of the decision set. Consequently, previous applications of USP yielded suboptimal polynomial regret bounds (e.g., $\tilde{O}(T^{11/13})$), failing to unlock the potential for optimal regret despite the memory compression.

Methodology

The authors resolve this tension by reframing the problem through the lens of the Minimum Description Length (MDL) principle. They posit that the most efficient representation balances the structural complexity (effective memory) against the cost of describing the parameters (magnitude of coefficients).

To exploit this balance, the paper proposes replacing first-order optimizers with the Vovk-Azoury-Warmuth (VAW) forecaster, a second-order online learning algorithm. The key methodological insights are:

1. Algorithmic Shift: Unlike first-order methods, the VAW algorithm's regret bound scales linearly with the dimension of the parameter space but only logarithmically with the norm of the comparator (the optimal parameter vector). This property allows VAW to absorb the exponential explosion of the Chebyshev preconditioning coefficients without suffering a corresponding explosion in regret.
2. Preconditioning Formulation: The sequence prediction problem is transformed into a linear prediction task of dimension $2n$ (where $n \approx \log T$). The feature vector $a_t$ consists of recent outputs and inputs, while the target weight vector $x^*$ concatenates the fixed Chebyshev coefficients and the system-specific parameters $\theta^{USP}_s$.
3. Complex-Analytic Extension: The authors derive new, tighter bounds for monic Chebyshev polynomials on the complex plane. This allows the USP framework to handle systems where the eigenvalues of the transition matrix have constant complex arguments, relaxing the previous requirement that the imaginary part of eigenvalues must vanish as $O(1/\log^2 T)$.

Key Contributions

1. Polylogarithmic Regret for Asymmetric Systems

The primary theoretical contribution is an algorithm that achieves polylogarithmic regret $O(\log^3 T)$ for marginally stable linear dynamical systems, even in the presence of asymmetric hidden transition matrices.

• Improvement: This exponentially improves upon the previous best bound of $\tilde{O}(T^{11/13})$ from [16].
• Generality: The result holds for systems with eigenvalues having constant complex arguments, a broader class than previously covered.
• Mechanism: The regret bound depends on the effective memory (dimension) and the logarithm of the parameter norm, effectively neutralizing the "exponential blowup" inherent in Chebyshev preconditioning.

2. New Complex-Analytic Bounds

The paper establishes new, tight bounds for monic Chebyshev polynomials (Lemma 1). These bounds prove that the approximation error of the preconditioner remains exponentially vanishing even when the system's eigenvalues have a constant complex argument, rather than requiring the argument to shrink with the polynomial degree.

3. Empirical Validation

Experiments on synthetic data demonstrate that the Chebyshev-preconditioned VAW forecaster significantly outperforms first-order methods (OGD, Adam) and adaptive polynomial learning approaches.

• High-Dimensional Regimes: In high-dimensional settings ($d=100$), first-order methods fail to converge when attempting to learn the necessary polynomial coefficients, whereas the fixed Chebyshev preconditioning combined with VAW achieves superior steady-state error reduction.
• Robustness: The VAW method remains stable as the polynomial degree increases, whereas first-order methods degrade after a certain degree due to sensitivity to large coefficients.

Results and Significance

The paper claims to resolve a fundamental tension in sequence prediction: the trade-off between memory compression and parameter magnitude. By aligning the USP regime with the VAW algorithm, the authors demonstrate that:

• Optimal Regret is Achievable: It is possible to achieve regret that is polylogarithmic in both the time horizon ($T$) and the hidden dimension ($d$), eliminating polynomial dependencies that plagued prior work.
• MDL as a Guiding Principle: The work validates the hypothesis that second-order methods are naturally matched to the MDL principle in this context, where the "cost" of large parameters is logarithmic rather than linear.
• Broader Applicability: The theoretical guarantees now extend to a strictly broader class of dynamical systems, including those with asymmetric matrices and constant complex eigenvalue arguments.

The authors note limitations, specifically that their theoretical analysis requires learning the autoregressive coefficients (unlike a purely offline transformation) and that the VAW algorithm has a larger memory footprint (polylogarithmic in $T$) compared to first-order methods. However, they argue that the exponential improvement in regret bounds and the ability to handle high-dimensional, long-memory systems represent a significant advancement in the field of online learning for dynamical systems.