ACCELERATED REGULARIZED NEWTON METHODS FOR MINIMIZING COMPOSITE CONVEX FUNCTIONS

摘要

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 Holder-continuous Hessian, and the other is a simple closed convex function. For the case in which the Holder parameter nu is an element of[0, 1] is known, we propose methods that take at most O(1/epsilon(1)/(2+nu)) 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 O(1/epsilon(2)/[3(1+nu)]) iterations without using nu explicitly in the scheme.