First-order methods with inexact oracle: the strongly convex case

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 gradient 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 sensitivity with respect to oracle errors. We also prove that the notion of (δ, L, μ)-oracle can be used in order to model exact first-order information but for functions with weaker level of smoothness and different level of convexity. This observation allows us to apply methods, originally designed for smooth strongly convex function, to weakly smooth uniformly convex functions and to derive corresponding performance guarantees.