  This work presents a new algorithm for empirical risk minimization. The
algorithm bridges the gap between first- and second-order methods by computing
a search direction that uses a second-order-type update in one subspace,
coupled with a scaled steepest descent step in the orthogonal complement. To
this end, partial curvature information is incorporated to help with
ill-conditioning, while simultaneously allowing the algorithm to scale to the
large problem dimensions often encountered in machine learning applications.
Theoretical results are presented to confirm that the algorithm converges to a
stationary point in both the strongly convex and nonconvex cases. A stochastic
variant of the algorithm is also presented, along with corresponding
theoretical guarantees. Numerical results confirm the strengths of the new
approach on standard machine learning problems.
