Nesterov's Acceleration For Approximate Newton
This work addresses a bottleneck in optimization for machine learning practitioners, though it appears incremental as it adapts an existing technique to a specific class of methods.
The paper tackles the problem of poor performance in stochastic second-order optimization methods when Hessian approximation is difficult, by applying Nesterov's acceleration to approximate Newton methods, resulting in an accelerated algorithm that performs much better than the original 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 Nesterov's acceleration technique to improve the convergence performance of a class of second-order methods called approximate Newton. We give a theoretical analysis that Nesterov'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 classical algorithms.