We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems. Despite the non-convex optimization problem, using improper learning and convex relaxation our algorithm comes with provable guarantees: it has near-optimal regret bounds compared to the best LDS in hindsight, while overparameterizing by only a small logarithmic factor. Our analysis brings together ideas from improper learning by convex relaxations, online regret minimization, and the spectral theory of Hankel matrices.