  Stochastic optimization methods have become a class of popular optimization
tools in machine learning. Especially, stochastic gradient descent (SGD) has
been widely used for machine learning problems such as training neural networks
due to low per-iteration computational complexity. In fact, the Newton or
quasi-newton methods leveraging second-order information are able to achieve a
better solution than the first-order methods. Thus, stochastic quasi-Newton
(SQN) methods have been developed to achieve the better solution efficiently
than the stochastic first-order methods by utilizing approximate second-order
information. However, the existing SQN methods still do not reach the best
known stochastic first-order oracle (SFO) complexity. To fill this gap, we
propose a novel faster stochastic quasi-Newton method (SpiderSQN) based on the
variance reduced technique of SIPDER. We prove that our SpiderSQN method
reaches the best known SFO complexity of $\mathcal{O}(n+n^{1/2}\epsilon^{-2})$
in the finite-sum setting to obtain an $\epsilon$-first-order stationary point.
To further improve its practical performance, we incorporate SpiderSQN with
different momentum schemes. Moreover, the proposed algorithms are generalized
to the online setting, and the corresponding SFO complexity of
$\mathcal{O}(\epsilon^{-3})$ is developed, which also matches the existing best
result. Extensive experiments on benchmark datasets demonstrate that our new
algorithms outperform state-of-the-art approaches for nonconvex optimization.
