Learning in dynamical systems is a fundamental challenge underlying modern sequence modeling. Despite extensive study, efficient algorithms with formal guarantees for general nonlinear systems have remained elusive. This talk presents a provably efficient framework for learning in any bounded and Lipschitz nonlinear dynamical system, establishing the first sublinear regret guarantees in a dimension-free setting. Our approach combines Koopman lifting, Luenberger observers, and, crucially, spectral filtering to show that a broad class of nonlinear dynamics are learnable. These insights motivate a new neural architecture, the Spectral Transform Unit (STU), which we will describe and present preliminary experiments on open benchmarks of language modelling and dynamical systems.