Universal Sequence Preconditioning
This work addresses the problem of sequential prediction for users of various prediction algorithms, including recurrent neural networks, providing an incremental yet significant improvement.
The authors tackled the problem of preconditioning in sequential prediction and achieved sublinear and hidden-dimension-independent regret bounds, with up to logarithmic factors, resulting in improved performance for various algorithms. Their approach yielded significant gains in both synthetic and real-world experiments.
We study the problem of preconditioning in sequential prediction. From the theoretical lens of linear dynamical systems, we show that convolving the target sequence corresponds to applying a polynomial to the hidden transition matrix. Building on this insight, we propose a universal preconditioning method that convolves the target with coefficients from orthogonal polynomials such as Chebyshev or Legendre. We prove that this approach reduces regret for two distinct prediction algorithms and yields the first ever sublinear and hidden-dimension-independent regret bounds (up to logarithmic factors) that hold for systems with marginally table and asymmetric transition matrices. Finally, extensive synthetic and real-world experiments show that this simple preconditioning strategy improves the performance of a diverse range of algorithms, including recurrent neural networks, and generalizes to signals beyond linear dynamical systems.