  We propose a novel limited-memory stochastic block BFGS update for
incorporating enriched curvature information in stochastic approximation
methods. In our method, the estimate of the inverse Hessian matrix that is
maintained by it, is updated at each iteration using a sketch of the Hessian,
i.e., a randomly generated compressed form of the Hessian. We propose several
sketching strategies, present a new quasi-Newton method that uses stochastic
block BFGS updates combined with the variance reduction approach SVRG to
compute batch stochastic gradients, and prove linear convergence of the
resulting method. Numerical tests on large-scale logistic regression problems
reveal that our method is more robust and substantially outperforms current
state-of-the-art methods.
