  We propose Sketched Online Newton (SON), an online second order learning
algorithm that enjoys substantially improved regret guarantees for
ill-conditioned data. SON is an enhanced version of the Online Newton Step,
which, via sketching techniques enjoys a running time linear in the dimension
and sketch size. We further develop sparse forms of the sketching methods (such
as Oja's rule), making the computation linear in the sparsity of features.
Together, the algorithm eliminates all computational obstacles in previous
second order online learning approaches.
