Accelerated Regularized Newton Methods for Minimizing Composite Convex Functions

Abstract

In this paper, we study accelerated regularized Newton methods for minimizing objectives formed as a sum of two functions: one is convex and twice differentiable with Hölder-continuous Hessian, and the other is a simple closed convex function. For the case in which the Hölder parameter $\nu\in [0,1]$ is known, we propose methods that take at most $\mathcal{O}\big({1 \over \epsilon^{1/(2+\nu)}}\big)$ iterations to reduce the functional residual below a given precision $\epsilon > 0$. For the general case, in which the $\nu$ is not known, we propose a universal method that ensures the same precision in at most $\mathcal{O}\big({1 \over \epsilon^{2/[3(1+\nu)]}}\big)$ iterations without using $\nu$ explicitly in the scheme.