Generalized Random Direction Newton Algorithms for Stochastic Optimization
This work addresses a bottleneck in stochastic Newton methods for optimization, offering incremental improvements in Hessian estimation accuracy.
The paper tackles the problem of Hessian estimation in stochastic optimization using only noisy function measurements, demonstrating that estimators with more measurements have lower-order bias and proving their asymptotic unbiasedness and convergence.
We present a family of generalized Hessian estimators of the objective using random direction stochastic approximation (RDSA) by utilizing only noisy function measurements. The form of each estimator and the order of the bias depend on the number of function measurements. In particular, we demonstrate that estimators with more function measurements exhibit lower-order estimation bias. We show the asymptotic unbiasedness of the estimators. We also perform asymptotic and non-asymptotic convergence analyses for stochastic Newton methods that incorporate our generalized Hessian estimators. Finally, we perform numerical experiments to validate our theoretical findings.