Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2012-006 (June 19, 2012)

Accelerated Regularized Newton Method for Unconstrained Convex Optimization
by Kenji Ueda, and Nobuo Yamashita

pdf File

We consider a global complexity bound of regularized Newton methods for the unconstrained convex optimization. The global complexity bound is an upper bound of the number of iterations required to get an approximate solution $x$ such that $f(x)- \inf f(y)\leq \varepsilon$, where $\ varepsilon$ is a given positive constant. Recently, Ueda and Yamashita proposed the regularized Newton method whose global complexity bound is $O(\varepsilon^{-2/3})$. In this paper, we propose an accelerated version of the regularized Newton method and show that its global complexity bound is $O(\ varepsilon^{-7/3})$.