Michel Baes
IFOR, ETHZ
Abstract:
In the early eighties, Yurii Nesterov proposed a new class of optimization schemes to minimize a convex function with a Lipschitz continuous gradient. According to the theory of Yudin and Nemirovski, these optimization schemes are the fastest possible for very large scale convex problems of this nature, provided that the optimizer has only access to first-order information about the instance.
These efficient schemes can be described using the formalism of estimate sequences. We propose in this talk a unified framework for the study of estimate sequence schemes. We show how some of the accelerated schemes developed by Nesterov in his recent papers can be derived from this framework, notably the acceleration procedure for the cubic regularization of Newton's method on constrained convex problems proposed in 2006.
Using our framework, we can extend these results to obtain accelerated schemes of regularizations of any order m. The resulting schemes are running in $O(1/\epsilon^{1/m})$ iterations, where $\epsilon$ is the required absolute accuracy.
At every iteration of an estimate sequence scheme, the gradient of the objective function has to be evaluated and usually two auxiliary optimization problems have to be solved. Our framework allows us to determine how accurately we need to compute the gradient and the solution to these subproblems in order to get a reasonably accurate output of the algorithm.