Nestrov's Acceleration For Second Order Method
This addresses a bottleneck in optimization for machine learning practitioners, offering an incremental improvement to second-order methods.
The paper tackles the problem of poor performance in stochastic second-order methods when Hessian approximation is difficult, by applying Nesterov's acceleration to approximate Newton methods, resulting in an accelerated algorithm that outperforms the original and matches or exceeds state-of-the-art methods in experiments.
Optimization plays a key role in machine learning. Recently, stochastic second-order methods have attracted much attention due to their low computational cost in each iteration. However, these algorithms might perform poorly especially if it is hard to approximate the Hessian well and efficiently. As far as we know, there is no effective way to handle this problem. In this paper, we resort to Nestrov's acceleration technique to improve the convergence performance of a class of second-order methods called approximate Newton. We give a theoretical analysis that Nestrov's acceleration technique can improve the convergence performance for approximate Newton just like for first-order methods. We accordingly propose an accelerated regularized sub-sampled Newton. Our accelerated algorithm performs much better than the original regularized sub-sampled Newton in experiments, which validates our theory empirically. Besides, the accelerated regularized sub-sampled Newton has good performance comparable to or even better than state-of-art algorithms.