  Popular machine learning approaches forgo second-order information due to the
difficulty of computing curvature in high dimensions. We present FOSI, a novel
meta-algorithm that improves the performance of any base first-order optimizer
by efficiently incorporating second-order information during the optimization
process. In each iteration, FOSI implicitly splits the function into two
quadratic functions defined on orthogonal subspaces, then uses a second-order
method to minimize the first, and the base optimizer to minimize the other. We
formally analyze FOSI's convergence and the conditions under which it improves
a base optimizer. Our empirical evaluation demonstrates that FOSI improves the
convergence rate and optimization time of first-order methods such as
Heavy-Ball and Adam, and outperforms second-order methods (K-FAC and L-BFGS).
