Stochastic optimization is the computational engine of modern machine learning. Yet the classical toolbox---stochastic gradient descent and its first-order relatives---largely treats the objective as a black box, leaving unused a great deal of structure that is available in practice and that, when exploited, provably accelerates training. This thesis develops algorithms and convergence theory for nonconvex stochastic optimization organized around three such forms of structure: auxiliary information, curvature, and composition.

We begin with auxiliary information. We formalize a setting in which, alongside the main objective, one has access to a related helper function, and we show how the helper can be used to reduce the cost of optimizing the main objective. This helper-function viewpoint is the conceptual seed of the thesis.

We then turn to second-order structure, where the natural helpers are approximate gradients and Hessians. We first study lazy Hessians---reusing a Hessian across several iterations to amortize its cost. We then give a unified convergence theory for stochastic and variance-reduced cubic Newton methods, introducing a lazy variance-reduction scheme and identifying an obstacle to the convergence of stochastic cubic Newton in the small-batch regime. We resolve that obstacle with momentum, and finally recast Hessian reuse as an asynchronous, delay-adaptive problem, which removes the need to hand-tune the Hessian update frequency.

Finally, we study momentum-driven methods that exploit cheap structured information. We show that a first-order method using only Hessian--vector products to correct its momentum attains improved rates, and we treat fully composite objectives with possibly nonsmooth outer functions by feeding a function-and-gradient momentum estimate to a generalized linear minimization oracle.

Across these settings a single theme recurs: identifying and exploiting the structure of a problem---rather than treating it as a black box---yields algorithms that are both provably faster and practical.