First-order methods with inexact oracle: the strongly convex case
Olivier Devolder, François Glineur, Yurii E. Nesterov · Digital Access to Libraries · 2013
The goal of this paper is to study the effect of inexact first-order information on the first-order methods designed for smooth strongly convex optimization problems. It can be seen as a generalization to the strongly convex case of our previous paper [1]. We introduce the notion of (δ, L, µ)-oracle, that can be seen as an extension of the (δ, L)-oracle (previously introduced in [1]), taking into account strong convexity. We consider different examples of (δ, L, µ)-oracle: strongly convex function with first-order information computed at a shifted point, strongly convex function with approximate gra-dient and strongly convex max-function with inexact resolution of subproblems. The core of this paper is devoted to the behavior analysis of three first-order methods, respectively the primal, the dual and the fast gradient method, when used with a (δ, L, µ)-oracle. As in the smooth convex case (studied in [1]), we obtain that the simple gradient methods can be seen as robust but relatively slow, whereas the fast gradient method is faster but more sensitive to oracle errors. However, the strong convexity leads to much faster convergence rates (linear instead of sublinear) for every method and to a reduced