Timezone: »

 
Poster
Second-Order Optimization with Lazy Hessians
Nikita Doikov · El Mahdi Chayti · Martin Jaggi

Thu Jul 27 01:30 PM -- 03:00 PM (PDT) @ Exhibit Hall 1 #607
in Poster Session 5 »
We analyze Newton's method with lazy Hessian updates for solving general possibly non-convex optimization problems. We propose to reuse a previously seen Hessian for several iterations while computing new gradients at each step of the method. This significantly reduces the overall arithmetic complexity of second-order optimization schemes. By using the cubic regularization technique, we establish fast global convergence of our method to a second-order stationary point, while the Hessian does not need to be updated each iteration. For convex problems, we justify global and local superlinear rates for lazy Newton steps with quadratic regularization, which is easier to compute. The optimal frequency for updating the Hessian is once every $d$ iterations, where $d$ is the dimension of the problem. This provably improves the total arithmetic complexity of second-order algorithms by a factor $\sqrt{d}$.

Author Information

Nikita Doikov (EPFL)
El Mahdi Chayti (Swiss Federal Institute of Technology Lausanne)
Martin Jaggi (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors