  Sketching is a dimensionality reduction technique where one compresses a
matrix by linear combinations that are typically chosen at random. A line of
work has shown how to sketch the Hessian to speed up each iteration in a second
order method, but such sketches usually depend only on the matrix at hand, and
in a number of cases are even oblivious to the input matrix. One could instead
hope to learn a distribution on sketching matrices that is optimized for the
specific distribution of input matrices. We show how to design learned sketches
for the Hessian in the context of second order methods, where we learn
potentially different sketches for the different iterations of an optimization
procedure. We show empirically that learned sketches, compared with their
"non-learned" counterparts, improve the approximation accuracy for important
problems, including LASSO, SVM, and matrix estimation with nuclear norm
constraints. Several of our schemes can be proven to perform no worse than
their unlearned counterparts. Additionally, we show that a smaller sketching
dimension of the column space of a tall matrix is possible, assuming an oracle
for predicting rows which have a large leverage score.
