Keywords: Simultaneous Perturbation Stochastic Approximation (SPSA); Symmetric Indefinite Matrix Factorization; Factorization Update; Quasi-Newton Method; Modified-Newton Method; Computational Complexity
Stochastic approximation (SA) has been widely applied in minimization and/or root-finding problems, where only noisy function evaluations and/or noisy gradient observations are accessible. For example, in machine learning, the backpropagation algorithm in training neural networks is essentially a first-order SA method. The simultaneous perturbation (SP) idea provides a convenient scheme to extend the algorithms to the second-order fashion. Unfortunately, in second-order simultaneous perturbation stochastic approximation (SPSA), two critical steps incur a cost of O(p^3) per iteration where p is the parameter dimension. One pertains the pre-conditioning step of making the estimated Hessian estimate positive-definite, and the other is inverting the Hessian estimate. We propose an efficient implementation of second-order SPSA, via the indefinite symmetric matrix factorization and the corresponding factorization update for rank-one modifications. Such an implementation technique streamlines second-order SPSA’s computation procedure, and achieves a per-iteration cost of O(p^2) in lieu of O(p^3). Numerical results show the superiority of this simple yet advantageous numerical improvement, in terms of complexity cost, stability and accuracy. This saving in computational cost demonstrates the potential of the second-order SPSA algorithm in high-dimensional machine learning.