Etienne De Klerk
email: deklerk@uvt.nl.

AND Adrien B Taylor
email: adrien.taylor@inria.fr.

WORST-CASE CONVERGENCE ANALYSIS OF INEXACT GRADIENT AND NEWTON METHODS THROUGH SEMIDEFINITE PROGRAMMING PERFORMANCE ESTIMATION *

Keywords: performance estimation problems, gradient method, inexact search direction, semidefinite programming, interior point methods AMS subject classifications. 90C22, 90C26, 90C30

. To illustrate the applicability of the tools, we demonstrate a novel complexity analysis of short step interior point methods using inexact search directions. As an example in this framework, we sketch how to give a rigorous worst-case complexity analysis of a recent interior point method by Abernethy and Hazan [PMLR, 48:2520[PMLR, 48: -2528[PMLR, 48: , 2016]].

1. Introduction. We consider the worst-case convergence of the gradient and Newton methods (with or without exact linesearch, and with possibly inexact search directions) for certain smooth and strongly convex functions.

Our analysis is computer-assisted 1 and relies on semidefinite programming (SDP) performance estimation problems, as introduced by Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF]. As a result, we develop a set of tools that may be used to design or analyse a wide range of interior point (and other) algorithms. Our analysis is in fact an extension of the worst-case analysis of the gradient method in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF], combined with the fact that Newton's method may be viewed as a gradient method with respect to a suitable local (intrinsic) inner product. As a result, we obtain worst-case convergence results for a single iteration of a wide range of methods, including Newton's method and the steepest descent method.

Related work. Our work is similar in spirit to recent analysis by Li et al [START_REF] Li | Inexact proximal Newton methods for self-concordant functions[END_REF] of inexact proximal Newton methods for self-concordant functions, but our approach and results are different. Their approach is oriented toward inexactness from the difficulty of computing the proximal Newton step, whereas ours is oriented toward the difficulty of computing the Hessian. Also, the authors of [START_REF] Li | Inexact proximal Newton methods for self-concordant functions[END_REF] do not use SDP performance estimation.

Since the seminal work by Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF], several authors have extended the SDP performance estimation framework. The authors of [START_REF] Taylor | Smooth strongly convex interpolation and exact worst-case performance of first-order methods[END_REF] introduced tightness guarantees for smooth (strongly) convex optimization, and for larger classes of problems in [START_REF] Taylor | Exact worst-case performance of first-order methods for composite convex optimization[END_REF] (where a list of sufficient conditions for applying the methodology is provided). It was also used to deal with nonsmooth problems [START_REF] Drori | An optimal variant of Kelley's cutting-plane method[END_REF][START_REF] Taylor | Exact worst-case performance of first-order methods for composite convex optimization[END_REF], monotone inclusions and variational inequalities [START_REF] Gu | Optimal nonergodic sublinear convergence rate of proximal point algorithm for maximal monotone inclusion problems[END_REF][START_REF] Gu | On the optimal ergodic sublinear convergence rate of the relaxed proximal point algorithm for variational inequalities[END_REF][START_REF] Kim | Accelerated proximal point method for maximally monotone operators[END_REF][START_REF] Ryu | Operator splitting performance estimation: Tight contraction factors and optimal parameter selection[END_REF], and even to study fixed-point iterations of non-expansive operators [START_REF] Lieder | On the convergence rate of the Halpern-iteration[END_REF]. Fixed-step gradient descent was among the first algorithms to be studied with this methodology in different settings: for (possibly composite) smooth (possibly strongly) convex optimization [START_REF] Drori | Contributions to the Complexity Analysis of Optimization Algorithms[END_REF][START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF][START_REF] Taylor | Smooth strongly convex interpolation and exact worst-case performance of first-order methods[END_REF][START_REF] Taylor | Exact worst-case performance of first-order methods for composite convex optimization[END_REF], and its line-search version was studied using the same methodology in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF]. The performance estimation framework was also used for obtaining new methods with optimized worstcase performance guarantees in different settings [START_REF] Drori | An optimal variant of Kelley's cutting-plane method[END_REF][START_REF] Drori | Efficient first-order methods for convex minimization: a constructive approach[END_REF][START_REF] Kim | Optimized first-order methods for smooth convex minimization[END_REF][START_REF] Kim | Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions[END_REF]. In particular, such new methods were obtained by optimization of their algorithmic parameters in [START_REF] Drori | An optimal variant of Kelley's cutting-plane method[END_REF][START_REF] Kim | Optimized first-order methods for smooth convex minimization[END_REF][START_REF] Kim | Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions[END_REF], and by analogy with conjugate-gradient type methods (doing greedy span-searches) in [START_REF] Drori | Efficient first-order methods for convex minimization: a constructive approach[END_REF]. Performance estimation is also related to the line of work on integral quadratic constraints started by Lessard, Recht, and Packard [START_REF] Lessard | Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints[END_REF], which also allowed designing optimized methods, see [START_REF] Cyrus | A Robust Accelerated Optimization Algorithm for Strongly Convex Functions[END_REF][START_REF] Van Scoy | The fastest known globally convergent first-order method for minimizing strongly convex functions[END_REF]. The approach in [START_REF] Lessard | Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints[END_REF] may be seen as a (relaxed) version of an SDP performance estimation problem where Lyapunov functions are used to certify error bounds [START_REF] Taylor | Lyapunov functions for first-order methods: Tight automated convergence guarantees[END_REF].

Outline and contributions of this paper. The contribution of this work is two-fold:

1. We extend the SDP performance estimation framework to include smooth, strongly convex functions that are not defined over the entire R n . By considering arbitrary inner products, we unify the analysis for gradient descent-type methods and Newton's method, thus extending the results in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF] in a significant way. In particular, we are able to give a new error analysis of inexact Newton methods for self-concordant functions. Thus we provide the first extension of SDP performance estimation to second order methods. 2. As an application of the tools we develop, we give an analysis of inexact short step interior point methods.

As an example of how our analysis may be used, we sketch how one may give a rigorous analysis of a recent interior point method by Abernethy and Hazan [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF], where the search direction is approximated through sampling. This particular method has sparked recent interest, since it links simulated annealing and interior point methods. However, no detailed analysis of the method is provided in [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF], and we supply some crucial details that are missing there. In Section 2, we review some basics on gradient descent methods, coordinate-free calculus, and convex functions. Thereafter, in Section 3, we describe inequalities for various classes of convex functions that will be used in performance estimation problems. A novel aspect here is that we allow the convex domain to be arbitrary in the study of smooth, strongly convex functions. Section 4 introduces the SDP performance estimation problems for various classes of convex functions and domains, and the error bounds from the analytical solutions of the performance estimation are given in Section 5. In Section 6 we show that our general framework for smooth, strongly convex functions includes self-concordant functions, and we are thus able to study inexact Newton(-type) methods for self-concordant functions. We then switch to an application of the tools we have developed, namely the complexity analysis of short step interior point methods that use inexact search directions (Section 7). As an example of inexact interior point methods, we consider a recent algorithm by Abernethy and Hazan [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF], that uses inexact Newton-type directions for the so-called entropic (self-concordant) barrier; see Section 7.1. We stress that this example only serves to illustrate our results, and we do not give the full details of the analysis, which is beyond the scope of our paper. The additional analysis on how sampling may be used in the method by Abernethy and Hazan [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF] to compute the inexact Newton-type directions is given in the separate work [START_REF] Badenbroek | Complexity analysis of a sampling-based interior point method for convex optimization[END_REF].

Preliminaries.

Throughout f denotes a differentiable convex function, whose domain is denoted by D f ⊂ R n , whereas D is used to denote open sets that may not correspond to the domain of f . We will indicate additional assumptions on f as needed. We will mostly use the notation from the book by Renegar [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF], for easy reference.

Gradients and Hessians.

In what follows we fix a reference inner product •, • on R n with induced norm • . DEFINITION 2.1 (Gradient and Hessian). If f is differentiable, the gradient of f at x ∈ D f with respect to •, • is the unique vector g(x) such that

lim ∆x →0 f (x + ∆x) -f (x) -g(x), ∆x ∆x = 0.
If f is twice differentiable, the second derivative (or Hessian) of f at x is defined as the (unique) linear operator H(x) that satisfies

lim ∆x →0 g(x + ∆x) -g(x) -H(x)∆x ∆x = 0.
Note that g(x), and therefore also H(x), depend on the reference inner product. If

•, • is the Euclidean dot product then g(x) = ∇f (x) = ∂f (x) ∂xi i=1,...,n
, and the Hessian, when written as a matrix with respect to the standard basis, takes the familiar form

[H(x)] ij =: [∇ 2 f (x)] ij = ∂ 2 f (x) ∂xi∂xj (i, j ∈ {1, . . . , n}). If B : R n → R n
is a self-adjoint positive definite linear operator, we may define a new inner product in terms of the reference inner product as follows: •, • B via x, y B = x, By ∀x, y ∈ R n . (Recall that all inner products in R n arise in this way.) If we change the inner product in this way, then the gradient changes to B -1 g(x), and the Hessian at x changes to B -1 H(x).

Recall that H(x) is self-adjoint with respect to the reference inner product if f is twice continuously differentiable. Assuming that H(x) is positive definite and self-adjoint at a given point x, define the intrinsic (w.r.t.

f at x) inner product u, v x := u, v H(x) ≡ u, H(x)v .
The definition is independent of the reference inner product •, • . The induced norm for the intrinsic inner product is denoted by: u x = u, u x . For the intrinsic inner product, the gradient at y is denoted by g x (y) := H(x) -1 g(y), and the Hessian at y by H x (y) := H(x) -1 H(y).

Fundamental theorem of calculus.

In what follows, we will recall coordinate-free versions of the fundamental theorem of calculus. Our review follows Renegar [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF], and all proofs may be found there. THEOREM 2.2 (Theorem 1.5.1 in [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF]). If x, y ∈ D f , then

f (y) -f (x) = 1 0 g(x + t(y -x)), y -x dt.
Next, we recall the definition of a vector-valued integral.

DEFINITION 2.3. Let t → v(t) ∈ R n where t ∈ [a, b]. Then u is the integral of v if u, w = b a v(t), w dt for all w ∈ R n .
Note that this definition is in fact independent of the reference inner product. We will use the following bound on norms of vector-valued integrals. THEOREM 2.4 (Proposition 1.5.4 in [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF]).

Let t → v(t) ∈ R n where t ∈ [a, b]. If v is integrable, then b a v(t)dt ≤ b a v(t) dt.
Finally, we will require the following version of the fundamental theorem for gradients. THEOREM 2.5 (Theorem 1.5.6 in [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF]). If x, y ∈ D f , then

g(y) -g(x) = 1 0 H(x + t(y -x))(y -x)dt.
2.3. Inexact gradient and Newton methods. We consider approximate gradients d i ≈ g(x i ) at a given iterate x i (i = 0, 1, . . .); to be precise we assume the following for a given ε ∈ [0, 1):

(2.1) d i -g(x i ) ≤ ε g(x i ) i = 0, 1, . . .
Note that ε = 0 yields the gradient, i.e. d i = g(x i ).

Algorithm 2.1 Inexact gradient descent method Input:

f : R n → R, x 0 ∈ R n , 0 ≤ ε < 1 for i = 0, 1, . . . Select any d i that satisfies (2.1) Choose a step size γ > 0 Update x i+1 = x i -γd i
We will consider two ways of choosing the step size γ: 1. Exact line search: γ = argmin γ∈R f (x i -γd i ); 2. Fixed step size: γ takes the same value at each iteration, and this value is known beforehand. We note once more that, at iteration i, we obtain the Newton direction by using the •, • xi inner product (if ε = 0). More generally, by using an inner product •, • B for some positive definite, self-adjoint operator B, we obtain the direction -B -1 g(x i ), which is the Newton direction when B = H(x i ), a quasi-Newton direction if B ≈ H(x i ), and the familiar steepest descent direction -∇f (x i ) if B = I.

Classes of convex functions.

In this section we review two classes of convex functions, namely smooth, strongly convex functions and self-concordant functions. We also show that, in a certain sense, the latter class may be seen as a special case of the former, by extending some known results on the first class.

(3.1) f (y) ≥ f (x) + g(x), y -x ∀x, y ∈ D.
Also recall that a twice continuously differentiable function is convex on D if and only if H(x) 0 for all x ∈ D.

3.2. Smooth strongly convex functions. A differentiable function f with D f = R n is called L-smooth and µ-strongly convex if it satisfies the following two properties:

(a) L-smoothness: there exists some L > 0 such that 1 L g(u) -g(v) ≤ u -v holds for all pairs u, v and corresponding gradients g(u), g(v). (b) µ-strong convexity: there exists some µ > 0 such that the function x → f (x) -µ 2 x 2 is convex. The class of such functions is denoted by F µ,L (R n ). Note that this function class is defined in terms of the reference inner product and its induced norm. In particular, it is not invariant under a change of inner product: under a change of inner product a smooth, strongly convex function remains smooth, strongly convex, but the parameters µ and L depend on the inner product. For our purposes, it is important not to fix the inner product a priori.

If D ⊆ R n is an open, convex set, then we denote the set of functions that satisfy properties (a) and (b) on D by F µ,L (D). The following lemma refines and extends well-known results from the literature on smooth convex functions. The novelty here is that we allow for arbitrary inner products, and any open, convex domain D. Similar results, are given, for example in the textbook by Nesterov [27, Chapter 2], and we only prove the results not covered there. We will use the Löwner partial order notation: for symmetric matrices (or self-adjoint linear operators) A and B, 'A B' means that B -A is positive semidefinite. We will denote the identity matrix (or operator) by I.

g(y) -g(x), y -x = y -x, 1 0 H(x + t(y -x))(y -x)dt = 1 0 y -x, H(x + t(y -x))(y -x) dt ≥ 1 0 y -x, 1 L H 2 (x + t(y -x))(y -x) dt = 1 L 1 0 H(x + t(y -x))(y -x) 2 dt ≥ 1 L 1 0 H(x + t(y -x))(y -x) dt 2 (Jensen inequality) ≥ 1 L 1 0 H(x + t(y -x))(y -x)dt 2 (Theorem 2.4) = 1 L g(y) -g(x) 2 (Theorem 2.5).
(c) ⇒ (a): Condition (c), together with the Cauchy-Schwartz inequality, immediately imply L-smoothness. To show convexity, note that, by Theorem 2.2,

f (y) -f (x) -g(x), y -x = 1 0 1 t g(x + t(y -x)) -g(x), t(y -x) dt ≥ 1 0 1 tL g(x + t(y -x)) -g(x) 2 dt ≥ 0,
where the first inequality is from condition (c). Thus we obtain the convexity inequality (3.1).

An interesting question is to understand the class of functions where the following inequality holds

(3.2) f (y) -f (x) -g(x), y -x ≥ 1 2L g(y) -g(x)
2 for all x, y in a given open convex set D, where L > 0 is fixed. (Note that (3.2) implies condition (c) in the lemma, by adding (3.2) to itself after interchanging x and y.) Indeed, for performance estimation problems, one attempts to find a function from a specific class that corresponds to the worst-case input for a given iterative algorithm. It is therefore of both practical and theoretical interest to understand the function class that satisfies (3.2).

The inequality (3.2) is known to hold for D = R n if, and only if, f ∈ F 0,L (R n ), by results of Taylor, Glineur and Hendrickx [START_REF] Taylor | Smooth strongly convex interpolation and exact worst-case performance of first-order methods[END_REF] (see also Azagra and Mudarra [START_REF] Azagra | An Extension Theorem for convex functions of class C 1,1 on Hilbert spaces[END_REF]). In an earlier version of this paper, we asked if this is true for more general open convex sets D ⊂ R n , but this turns out not to be the case: Drori [START_REF] Drori | On the Properties of Convex Functions over Open Sets[END_REF] recently constructed an example of a bivariate function with open domain, say D, such that f ∈ F 0,L (D) with L = 1, but where (3.2) does not hold for all x, y ∈ D. For this reason, item (c) in Lemma 3.1, cannot be changed to the stronger condition (3.2). Lemma 3.1 allows us to derive the following necessary and sufficient conditions for membership of F µ,L (D). The condition (d) below is new, and will be used extensively in the proofs that follow.

(3.3) g(x) -g(y), x -y ≥ 1 1 -µ L 1 L g(x) -g(y) 2 + µ x -y 2 -2 µ L g(x) -g(y), x -y .
Proof. The equivalences (a) ⇔ (b) ⇔ (c) follow directly from Lemma 3.1 and the relevant definitions.

(c) ⇔ (d): Requiring h(x) = f (x) -µ 2 x
2 to be convex and (L -µ)-smooth on D can equivalently be formulated as requiring h to satisfy

g h (x) -g h (y), x -y ≥ 1 L -µ g h (y) -g h (x)
2 for all x, y ∈ D, where g h is the gradient of h. Equivalently:

(L -µ) g f (x) -g f (y), x -y -µ x -y 2 ≥ g f (y) -g f (x) 2 + µ 2 x -y 2 -2µ g f (y) -g f (x), y -x ,
which is exactly condition (d) in the statement of the theorem.

We note once more that the spectrum of the Hessian is not invariant under change in inner product, thus the values µ and L are intrinsically linked to the reference inner product. If D = R n , a stronger condition than condition (d) in the last theorem holds, namely

(3.4) f (y) -f (x) -g(x), y -x ≥ 1 2(1 -µ L ) 1 L g(y) -g(x) 2 + µ x -y 2 -2 µ L g(x) -g(y), x -y .
For the reasons discussed after Lemma 3.1, the inequality (3.4) does not hold in general if D = R n , due to the results by Drori [START_REF] Drori | On the Properties of Convex Functions over Open Sets[END_REF].

3.3. Self-concordance. Self-concordant functions are special convex functions introduced by Nesterov and Nemirovski [START_REF] Nesterov | Interior point polynomial algorithms in convex programming[END_REF], that play a certral role in the analysis of interior point algorithms. We will use the (slightly) more general definition by Renegar [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF].

DEFINITION 3.3 (Self-concordant functional). Let f : D f → R be such that H(x) 0 for all x ∈ D f , and let B x (x, 1) denote the open unit ball centered at x ∈ D f for the • x norm. Then f is called self-concordant if: 1. For all x ∈ D f one has B x (x, 1) ⊆ D f ; 2. For all y ∈ B x (x, 1) one has 1 -y -x x ≤ v y v x ≤ 1 1 -y -x x for all v = 0.
An equivalent characterization of self-concordance, due to Renegar [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF], is as follows.

THEOREM 3.4 (Theorem 2.2.1 in [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF]). Assume f such that for all x ∈ D f one has B x (x, 1) ⊆ D f . Then f is self-concordant if, and only if, for all x ∈ D f and y ∈ B x (x, 1):

(3.5) max H x (y) x , H x (y) -1 x ≤ 1 (1 -y -x x ) 2 .
This alternative characterization allows us to establish a new link between self-concordant and L-smooth, µstrongly convex functions.

COROLLARY 3.5. Assume f : D f → R is self-concordant, x ∈ D f , and δ < 1. Then f ∈ F µ,L (D) with respect to the inner product •, • x , if D = {y | y -x x < δ} = B x (x, δ), µ = (1 -δ) 2 , and L = 1 (1-δ) 2 . Conversely, assume f : D f → R is twice continuously differentiable, and H(x) 0 for all x ∈ D f . If, for all x ∈ D f and δ ∈ (0, 1), it holds that 1. D := B x (x, δ) ⊂ D f , 2. f ∈ F µ,L (D) with respect to the inner product •, • x , and µ = (1 -δ) 2 and L = 1 (1-δ) 2 , then f is self-concordant.
Proof. For the first implication, observe that for a self-concordant f , Theorem 3.4 implies the spectrum of H x (y)

is contained in the interval (1 -y -x x ) 2 , 1 (1-y-x x ) 2 , which in turn is contained in (1 -δ) 2 , 1
(1-δ) 2 for all y ∈ B x (x, δ). Theorem 3.2 now yields the required result.

To prove the converse, assume y ∈ B x (x, 1) and set δ = x -y x , D = B x (x, δ), µ = (1 -δ) 2 , and

L = 1 (1-δ) 2 . Since f ∈ F µ,L (D)
by assumption, it holds that µI H x (y) LI, which is the same as the condition (3.5) that guarantees self-concordance.

4. Performance estimation problems. Performance estimation problems, as introduced by Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF], are semidefinite programming (SDP) problems that bound the worst-case performance of certain iterative optimization algorithms. Essentially, the goal is to find the objective function from a given function class, that exhibits the worst-case behavior for a given iterative algorithm.

In what follows, we list the SDP performance estimation problems that we will employ to study worst-case bounds for one iteration of gradient methods, applied to a smooth, strongly convex f that admits a minimizer, denoted by x * . These performance estimation problems have variables that correspond to (unknown) iterates x 0 and x 1 , the minimizer x * , as well as the gradients and function values at these points, namely g i correspond to g(x i ) (i ∈ { * , 0, 1})), and f i correspond to f (x i ) (i ∈ { * , 0, 1})). We may assume x * = g * = 0 and f * = 0 without loss of generality.

The objective is to identify the worst-case after one iteration is performed, namely to find the maximum value of either f 1 -f * , g 1 , or x 1 -x * , given an upper bound on the initial value of one of the quantities f 0 -f * , g 0 , or x 0 -x * (this upper bound will be denoted R below).

Note again that the norm may be any induced norm on R n . Note that we only consider one iteration, i.e. the transition from x 0 to x 1 , whereas SDP performance estimation is typically used to study several iterations; see e.g. [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF][START_REF] Taylor | Smooth strongly convex interpolation and exact worst-case performance of first-order methods[END_REF]. For our purposes, it suffices to consider one iterationwe will elaborate on this later on. For the time being, we consider functions where the domain is all of R n , and will move to restricted domains later on.

Performance estimation with exact line search.

• Parameters:

L ≥ µ > 0, R > 0; • Variables: {(x i , g i , f i )} i∈S (S = { * , 0, 1}).
Worst-case function value. (4.1)

max f 1 -f * s.t. f i -f j -g j , x i -x j ≥ 1 2(1-µ/L) 1 L g i -g j 2 + µ x i -x j 2 -2 µ L g j -g i , x j -x i ∀i, j ∈ S g * = 0 x 1 -x 0 , g 1 = 0 g 0 , g 1 ≤ ε g 0 g 1 f 0 -f * ≤ R                 
The first constraint corresponds to (3.4), and models the necessary condition for f ∈ F µ,L (R n ). The second constraint corresponds to the fact that the gradient is zero at a minimizer. The third constraint is the well-known property of exact line search, while the fourth constraint is satisfied if the approximate gradient condition (2.1) holds. Finally, the fifth constraint ensures that the problem is bounded.

Note that the resulting problem may be written as an SDP problem, with 4 × 4 matrix variable given by the Gram matrix of the vectors x 0 , x 1 , g 0 , g 1 with respect to the reference inner product. In particular the fourth contraint may be written as the linear matrix inequality:

(4.2) ε g 0 2 g 0 , g 1 g 0 , g 1 ε g 1 2 0.
Also note that the optimal value of the resulting SDP problem is independent of the inner product. The SDP problem (4.1) was first studied in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF].

Worst-case gradient norm. The second variant of performance estimation is to find the worst case convergence of the gradient norm.

(4.3) max g 1 2 s.t. g i -g j , x i -x j ≥ 1 1-µ L 1 L g i -g j 2 + µ x i -x j 2 -2 µ L g i -g j , x i -x j ∀i, j ∈ S g * = 0 x 1 -x 0 , g 1 = 0 g 0 , g 1 ≤ ε g 0 g 1 g 0 2 ≤ R               
Worst-case distance to optimality. The third variant of performance estimation is to find the worst case convergence of the distance to optimality. (4.4)

max x 1 -x * 2 s.t. g i -g j , x i -x j ≥ 1 1-µ L 1 L g i -g j 2 + µ x i -x j 2 -2 µ L g i -g j , x i -x j ∀i, j ∈ S g * = 0 x 1 -x 0 , g 1 = 0 g 0 , g 1 ≤ ε g 0 g 1 x 0 -x 2 ≤ R               
In what follows we will give upper bounds on the optimal values of these performance estimation SDP problems.

PEP with fixed step sizes. For fixed step sizes, the performance estimation problems (4.1), (4.3), and (4.4) change as follows:

1. for given step size γ > 0, the condition x 1 = x 0 -γd is used to eliminate x 1 , where d is the approximate gradient at x 0 . 2. The vector d is viewed as a variable in the performance estimation problem. 3. The exact line search condition, x 1 -x 0 , g 1 = 0, is omitted. 4. The condition d -g 0 2 ≤ ε 2 g 0 2 is added, that corresponds to (2.1), and g 0 , g 1 ≤ ε g 0 g 1 is omitted.

Error bounds from performance estimation.

The optimal values of the performance estimation problems in the last section give bounds on the worst-case convergence rates of the gradient method for different performance measures. In this section, we provide bounds that were obtained using the solutions to the previously presented performance estimation problems. As the bounds we present below are not always the tightest ones, each result is provided with comments regarding tightness.

To the best of our knowledge, there are no results dealing with the exact same settings in the literature. Among others, one can find detailed analyses of first-order method under deterministic uncertainty models in [START_REF]Smooth optimization with approximate gradient[END_REF][START_REF] Devolder | First-order methods of smooth convex optimization with inexact oracle[END_REF][START_REF] Schmidt | Convergence rates of inexact proximal-gradient methods for convex optimization[END_REF]. Related results involving relative inaccuracy (as in this work) can be found in older works by Polyak [29] where the focus is on smooth convex minimization.

To give some meaningful comparison, we will compare our results to standard ones for the simpler case ε = 0.

5.1. PEP with exact line search. The first result concerns error bounds for the inexact gradient method with exact line search when no restriction is applied on the domain. This problem, originally due to Cauchy, was studied in detail in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF] using SDP performance estimation. Here we will generalize the main result from [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF]

f ∈ F µ,L (R n ). If κ := µ L (the inverse condition number: κ ∈ (0, 1]) and ε ∈ 0, 2 √ κ 1+κ , one has f (x 1 ) -f (x * ) ≤ 1 -κ + ε(1 -κ) 1 + κ + ε(1 -κ) 2 (f (x 0 ) -f (x * )), g(x 1 ) ≤ ε + 1 -ε 2 1 -κ 2 √ κ g(x 0 ) , x 1 -x * ≤ ε + 1 -ε 2 1 -κ 2 √ κ x 0 -x * .
Proof. The three inequalities in the statement of the theorem follow from corresponding upper bounds on the optimal values of the SDP performance estimation problems (4.1), (4.3), and (4.4), respectively.

The first of the SDP performance estimation problems, namely (4.1), is exactly the same as the one in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF] (see [START_REF] Cyrus | A Robust Accelerated Optimization Algorithm for Strongly Convex Functions[END_REF] there). The first inequality therefore follows from Theorem 1.2 in [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF].

It remains to demonstrate suitable upper bounds on the SDP performance estimation problems (4.3), and (4.4). This is done by aggregating the constraints of these respective SDP problems by using suitable (Lagrange) multipliers. 2 To this end, consider the following constraints from (4.3) and their associated multipliers:

g 0 -g 1 , x 0 -x 1 ≥ 1 1 -µ L 1 L g 0 -g 1 2 + µ x 1 -x 0 2 -2 µ L g 0 -g 1 , x 0 -x 1 : (L -µ)λ, g 1 , x 1 -x 0 = 0 : L + µ, ||g 0 || 2 g 0 , g 1 g 0 , g 1 ||g 1 || 2 0 : S, 2
The multipliers used in the proof were obtained by solving the SDP problems (4.3) and (4.4) numerically for different values of µ and L (one may assume w.l.o.g. that R = 1), and subsequently guessing the correct analytical expressions of the multipliers by looking at the optimal solution of the dual SDP problem. For example it quickly became clear that the second multiplier was (L + µ), and that the matrix S always had rank one. The correctness of these expressions for the multipliers is verified in the proof. Thus numerical computations were only used to find the proof of Theorem 5.1, i.e. to guess the correct analytical expressions for the multipliers, and play no role in the proof itself. , and:

λ = 2ε √ κ √ 1 -ε 2 (1 -κ) + 1,
s 11 = 3ε 2 - ε κ + 1 κ 4 + 1 -κ 2 κ(1 -ε 2 ) - ε 2 (1 -κ) κ(1 -ε 2 ) , s 22 = 2 κ(1 -ε 2 ) -ε (1 -κ) (1 -ε 2 ) (1 -κ) + 2ε κ(1 -ε 2 ) , s 12 = ε (1 -κ) 2 κ(1 -ε 2 ) -1.
Assuming the corresponding multipliers are of appropriate signs (see discussion below), the proof consists in reformulating the following weighted sum of the previous inequalities (the validity of this inequality follows from the signs of the multipliers):

(5.1)

0 ≥(L -µ)λ 1 1 -µ L 1 L g 0 -g 1 2 + µ x 1 -x 0 2 -2 µ L g 0 -g 1 , x 0 -x 1 -g 0 -g 1 , x 0 -x 1 + (L + µ) [ g 1 , x 1 -x 0 ] -Trace s 11 s 12 s 12 s 22 ||g 0 || 2 g 0 , g 1 g 0 , g 1 ||g 1 || 2 .
We first show that multipliers are nonnegative (resp. positive semidefinite) where required; that is, (L -µ)λ ≥ 0 and S 0. The nonnegativity of the first term is clear from 0 < µ ≤ L and λ ≥ 0. Concerning S, let us note that

s 22 ≥ 0 ⇔ ε ∈ -2 √ κ 1+κ , 2 √ κ 1+κ . When ε < 2 √ κ
1+κ , s 22 ensures that there exists a positive eigenvalue for S, since s 22 > 0. In order to prove that both eigenvalues of S are nonnegative, one may verify:

det S = s 11 s 22 -s 2 12 = 0.
Therefore, one eigenvalue of S is positive and the other one is zero when ε < 2 √ κ 1+κ , and in the simpler case ε = 2 √ κ 1+κ , we have S = 0, and hence the inequality (5.1) is valid.

Reformulating the valid inequality (5.1) yields:

g 1 2 ≤ ε + 1 -ε 2 1 -κ 2 √ κ 2 g 0 2 -κ 2ε √ κ + (1 -κ) √ 1 -ε 2 (1 -κ) √ 1 -ε 2 ε(1 + κ) √ κ √ 1 -ε 2 (1 -κ) + 2ε √ κ g 1 - 1 + κ 2κ g 0 + L(x 0 -x 1 ) 2 , ≤ ε + 1 -ε 2 1 -κ 2 √ κ 2 g 0 2 ,
where the last inequality follows from the sign of the coefficient:

κ 2ε √ κ + (1 -κ) √ 1 -ε 2 (1 -κ) √ 1 -ε 2 ≥ 0.
Next, we prove the exact same guarantee as for the gradient norm, but in the case of distance to optimality

x 1 -x * 2 .
Let us consider the following constraints from (4.4) with associated multipliers:

1 1 -µ L 1 L g 0 2 + µ x 0 -x * 2 -2 µ L g 0 , x 0 -x * + g 0 , x * -x 0 ≤ 0 : λ 0 , 1 1 -µ L 1 L g 1 2 + µ x 1 -x * 2 -2 µ L g 1 , x 1 -x * + g 1 , x * -x 1 ≤ 0 : λ 1 , g 1 , x 1 -x 0 ≤ 0 : λ 2 , ||g 0 || 2 g 0 , g 1 g T 0 g 1 ||g 1 || 2 0 : S, with S = s 11 s 12 s 12 s 22
, and:

λ 0 = 1 -κ µ 1 -2ε 2 + ε √ 1 -ε 2 2 √ κ(1 -κ) (-1 -κ 2 + 6κ) , λ 1 = 1 µ - 1 L , λ 2 = 1 µ + 1 L , Lµs 11 = 3ε 2 - ε κ + 1 κ 4 + 1 -κ 2 κ(1 -ε 2 ) - ε 2 (1 -κ) κ(1 -ε 2 ) , Lµs 22 = 2 κ(1 -ε 2 ) -ε (1 -κ) (1 -ε 2 ) (1 -κ) + 2ε κ(1 -ε 2 ) , Lµs 12 = ε (1 -κ) 2 κ(1 -ε 2 ) -1.
As in the case of the gradient norm, we proceed by reformulating the weighted sum of the constraints. For doing that, we first check nonnegativity of the weights λ 0 , λ 1 , λ 2 ≥ 0 and S 0.

Similarly to the previous case,

s 22 ≥ 0 ⇔ ε ∈ -2 √ κ 1+κ , 2 √ κ 1+κ .
We therefore only need to check the sign of λ 0 in order to have the desired results (the S 0 requirement is the same as for the convergence in gradient norm, and the others are easily verified). Concerning λ 0 , we have

λ 0 ≥ 0 ⇔ κ -1 κ + 1 ≤ ε ≤ 2 √ κ κ + 1 ,
with κ-1 κ+1 ≤ 0, and hence λ 0 ≥ 0 in the region of interest.

Aggregating the constraints with the corresponding multipliers yields:

x 1 -x * 2 ≤ ε + 1 -ε 2 1 -κ 2 √ κ 2 x 0 -x * 2 - 2ε (1 -ε 2 ) κ + 1 -ε 2 (1 -κ) κ(1 -κ) × 1 - ε(1 -κ) 2 (1 -ε 2 ) κ g 0 L - 1 + κ 2 (x 0 -x * ) + 1 -κ 2ε (1 -ε 2 ) κ + (1 -ε 2 ) (1 -κ) g 1 L 2 , ≤ ε + 1 -ε 2 1 -κ 2 √ κ 2 x 0 -x * 2 ,
where the last inequality follows from the sign of the coefficient

2ε (1 -ε 2 ) κ + 1 -ε 2 (1 -κ) κ(1 -κ) ≥ 0.
This completes the proof.

Theorem 5.1 provides both tight and non-tight results, as follows:

1. the result in function values cannot be improved, by [22, Example 5.2]; 2. likewise, the result in gradient norm cannot be improved; we give an example proving this in Appendix A.

3. The result in distance to optimality is not tight. Our bounds on the rates satisfy

1 -κ + ε(1 -κ) 1 + κ + ε(1 -κ) 2 ≤ ε + 1 -ε 2 1 -κ 2 √ κ 2 ,
where the left hand term is the optimal value of (4.1) and the right hand term is the optimal value of (4.3).

We may compare our results to known (classical) results with ε = 0. In that case, we have that the best possible rate for function value is given by (see [START_REF] De Klerk | On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions[END_REF]Theorem 5.2]),

f (x 1 ) -f (x * ) ≤ 1 -κ 1 + κ 2 (f (x 0 ) -f (x * )).
By smoothness and strong convexity, we derive in a standard way for the gradient norm (the exact same reasoning holds for the distance to optimum)

||g(x 1 )|| ≤ 1 √ κ 1 -κ 1 + κ ||g(x 0 )||,
whereas Theorem 5.1 provides the strictly better guarantee for κ ∈ (0, 1), namely:

||g(x 1 )|| ≤ 1 2 √ κ (1 -κ) ||g(x 0 )||.
The above rates are valid when performing one iteration. Better rates can be guaranteed if more than one iteration is performed, which can be done in the same framework. However, we do not pursue our investigations in that direction, as the subsequent analysis of Newtons method only requires the best possible one-iteration inequalities, as provided by the above new improved bounds.

One has the following variation on Theorem 5.1 that deals with the case where f ∈ F µ,L (D) for some open convex set D ⊂ R n . THEOREM 5.2. Consider the inexact gradient method with exact line search applied to some twice continuously differentiable f ∈ F µ,L (D) where D ⊂ R n is open and convex, from a starting point x 0 ∈ D. Assume that

{x ∈ R n | f (x) ≤ f (x 0 )} ⊂ D. If κ := µ L ∈ (0, 1] and ε ∈ 0, 2 √ κ 1+κ , one has g(x 1 ) ≤ ε + 1 -ε 2 1 -κ 2 √ κ g(x 0 ) , x 1 -x * ≤ ε + 1 -ε 2 1 -κ 2 √ κ x 0 -x * .
Proof. The proof follows from the proof of Theorem 5.1 after the following observations:

1. The proof of the last two inequalities in Theorem 5.1 only relies on the inequality (3.3), which holds for any open, convex D ⊂ R n , i.e. not only for D = R n , by Theorem 3.2. 2. By the assumption on the level set of f , exact line search yields a point x 1 ∈ D, as required.

Concerning tightness and comparisons with known results, the same remarks as for Theorem 5.1 apply here. Although the setting is nonstandard for first-order methods, comparisons made for the case D = R n are still valid as the worst-case bounds for gradient and distance are the same (i.e., results of Theorem 5.2 already improve upon the literature/folklore knowledge in the simpler setting D = R n ).

Note that the first inequality in Theorem 5.1 (convergence in function value) does not extend readily to all convex D, since its proof requires the inequality (3.4).

PEP with fixed step sizes.

We now state a result that is similar to Theorem 5.1, but deals with fixed step sizes instead of exact line search. THEOREM 5.3. Consider the inexact gradient method with fixed step size γ applied to some

f ∈ F µ,L (R n ). If ε ∈ 0, 2µ
L+µ , and γ ∈ 0, 2µ-ε(L+µ) (1-ε)µ(L+µ) , one has

f (x 1 ) -f (x * ) ≤ (1 -(1 -ε)µγ) 2 (f (x 0 ) -f (x * )), g(x 1 ) ≤ (1 -(1 -ε)µγ) g(x 0 ) , x 1 -x * ≤ (1 -(1 -ε)µγ) x 0 -x * .
Proof. The proof is similar to that of Theorem 5.1, and is sketched in Appendix B.

In Theorem 5.3, all results are provably tight. Indeed, one can easily verify that those bounds are achieved with equality (for all three cases: function, distance and gradient) on the one-dimensional minimization problem min x∈R f (x) with the quadratic function f (x) = µ 2

x 2 and the search direction -g(x 0 )(1 -ε) = -µ(1 -ε)x 0 (that satisfies the relative accuracy criterion (2.1)). Note that, in the case ε = 0, one can therefore also recover all standard convergence guarantees that are tight on quadratics (see e.g., [START_REF] Taylor | Exact worst-case convergence rates of the proximal gradient method for composite convex minimization[END_REF] and the references therein).

Note that, if

γ = 2µ-ε(L+µ) (1-ε)µ(L+µ) , the factor (1 -(1 -ε)µγ) that appears in the inequalities in Theorem 5.3 reduces to 1 -(1 -ε)µγ = 1 -κ 1 + κ + ε,
x 0 ∈ D so that B(x 0 , 2 x 0 -x * ) ⊂ D. If x 1 = x 0 -γd, with d -g(x 0 ) ≤ ε g(x 0 ) , ε ∈ 0, 2κ 1+κ
, and

γ = 2µ -ε(L + µ) (1 -ε)µ(L + µ) , then g x0 (x 1 ) ≤ 1 -κ 1 + κ + ε g x0 (x 0 ) , x 1 -x * ≤ 1 -κ 1 + κ + ε x 0 -x * ,
where κ = µ/L.

Proof. Note that the result follows from the proof of Theorem 5.3, provided that x 1 ∈ D. In other words, we need to show that the condition x 1 ∈ D is a consequence of the hypotheses. This follows from:

x 1 -x 0 ≤ x 1 -x * x0 + x * -x 0 (triangle inequality) ≤ 1 -κ 1 + κ + ε x 0 -x * + x * -x 0 (by Theorem 5.3) ≤ 2 x * -x 0 (by ε ≤ 2κ 1+κ ), which implies x 1 ∈ D due to the assumption B(x 0 , 2 x 0 -x * ) ⊂ D.
The same remarks as for Theorem 5.3 apply here: the results are tight on quadratics, as the worst-case bounds match those in the case D = R d .

6. Implications for Newton's method for self-concordant f . Theorem 5.4 has interesting implications when minimizing a self-concordant function f with minimizer x * by Newton's method. The implications become clear when fixing a point x 0 ∈ D f , and using the inner product •, • x0 . Then the gradient at x 0 becomes g x0 (x 0 ) = H -1 x0 (x 0 )g(x 0 ), which is the opposite of the Newton step at x 0 . We will consider approximate Newton directions in the sense of (2.1), i.e. directions -d that satisfy d -g x0 (x 0 ) x0 ≤ ε g x0 (x 0 ) x0 , where ε > 0 is given. We only state results for the fixed step-length case, for later use. Similar error bounds can be obtained using Theorem 5.2 for inexact Newton methods with exact line search, that are used, e.g. in long step interior point methods with inexact search directions; see, e.g. [30, §2.5.3]. COROLLARY 6.1. Assume f is self-concordant with minimizer x * . Let 0 < δ < 1 be given and x 0 ∈ D f so that

x 0 -x * x0 ≤ 1 2 δ. If x 1 = x 0 -γd, where d -g x0 (x 0 ) x0 ≤ ε g x0 (x 0 ) x0 with ε ∈ 0, 2(1-δ) 4 1+(1-δ) 4
, and

γ = 2(1 -δ) 4 -ε(1 + (1 -δ) 4 ) (1 -ε)(1 -δ) 2 ((1 -δ) 4 + 1) , then g x0 (x 1 ) x0 ≤ 1 -κ δ 1 + κ δ + ε g x0 (x 0 ) x0 , x 1 -x * x0 ≤ 1 -κ δ 1 + κ δ + ε x 0 -x * x0 ,
where κ δ = (1 -δ) 4 .

Proof. By Corollary 3.5, if we fix the inner product

•, • x0 , then f ∈ F µ,L (B x0 (x 0 , δ)) with (6.1) µ = (1 -δ) 2 , L = 1 (1 -δ) 2 .
As a consequence κ δ := κ = µ/L = (1 -δ) 4 . (We use the notation κ = κ δ to emphasize that κ depends on δ (only).) The required result now follows from Theorem 5.4.

In view of our earlier remarks on tightness of the bounds in Theorem 5.4, it is important to note that the bounds in Corollary 6.1 are not tight in general. The reason is that we only used the fact that, for a given x 0 ∈ D f and δ ∈ (0, 1), one has f ∈ F µ,L (B x0 (x 0 , δ)) for the values of µ and L as given in (6.1). This is weaker than requiring self-concordance of f , as the following example shows. EXAMPLE 6.2. Consider the univariate f (x) = 1 12 x 4 with D f = (0, ∞). At x 0 = 1, one has H(x 0 ) = 1. If we set δ = 1 2 , (6.1) yields µ = 1 4 and L = 4, and we have

B x0 (x 0 , δ) = 1 2 , 3 2 . Since H x0 (y) = y 2 for all y ∈ R, one has µ < H x0 (y) < L if y ∈ B x0 (x 0 ,
δ), and therefore f ∈ F µ,L (B x0 (x 0 , δ)). On the other hand, f is not self-concordant on its domain, since it does not satisfy the condition |f (x)| ≤ 2f (x) 3/2 if x ∈ (0, 1).

A final, but important observation is that the results in Corollary 6.1 remain valid if we use the •, • x * inner product, as opposed to •, • x0 . This implies that we (approximately) use the direction -g x * (x 0 ) = -H -1 (x * )g(x 0 ). Such a direction may seem to be of no practical use, since x * is not known, but in the next section we will analyze an interior point method that uses precisely such search directions.

For easy reference, we therefore state the worst-case convergence result when using the •, • x * inner product. COROLLARY 6.3. Assume f is self-concordant with minimizer x * . Let δ ∈ (0, 1) be given and x 0 ∈ D f so that

x 0 -x * x * ≤ 1 2 δ. If x 1 = x 0 -γd, where d -g x * (x 0 ) x * ≤ ε g x * (x 0 ) x * with ε ∈ 0, 2(1-δ) 4
1+(1-δ) 4 , and step size

(6.2) γ = 2(1 -δ) 4 -ε(1 + (1 -δ) 4 ) (1 -ε)(1 -δ) 2 ((1 -δ) 4 + 1) , then g x0 (x 1 ) x * ≤ 1 -κ δ 1 + κ δ + ε g x0 (x 0 ) x * , x 1 -x * x * ≤ 1 -κ δ 1 + κ δ + ε x 0 -x * x * ,
where κ δ = (1 -δ) 4 .

We may compare Corollaries 6.1 and 6.3 to the following results that may be obtained from standard interior point analysis. THEOREM 6.4 (Based on Theorems 1.6.2 and 2.2.3 in [START_REF] Renegar | A Mathematical View of Interior-Point Methods in Convex Optimization[END_REF]). Let f be a self-concordant function with minimizer x * , and let x 0 ∈ B x0 (x * , 1). Define x 1 = x 0 -γ[H(x 0 ) -1 g(x 0 ) + e(x 0 )] for some γ ∈ (0, 1), where e(x 0 ) denotes an error in the Newton direction at the point

x 0 . If e(x 0 ) x0 ≤ ε H(x 0 ) -1 g(x 0 ) x0 , then (6.3) x 1 -x * x0 ≤ (1 -γ + γ 2 ε) x 0 -x * x0 + γ x 0 -x * 2 x0 γ(1 -x 0 -x * x0
) .

Similarly, if we define instead

x 1 = x 0 -γ[H(x * ) -1 g(x 0
) + e(x 0 )], i.e. replace H(x 0 ) by H(x * ) in the definition of x 1 , then (6.4)

x 1 -x * x * ≤ (1 -γ + γ 2 ε) x 0 -x * x * + γ x 0 -x * 2 x * γ(1 -x 0 -x * x * ) ,
under the assumption x 0 ∈ B x * (x * , 1).

Note that the only difference between the inequalities (6.3) and (6.4) is the choice of local norm.

To compare Theorem 6.4 to Corollaries 6.1 and 6.3, we present a plot of the respective upper bounds in Figure 1 for for different values of ε. The value of the step size γ is as in (6.2) with δ = 2 x 0 -x * x * .

A few remarks on Figure 1: 1. Although the figure only compares inequality (6.4) in Theorem 6.4 to the bound in Corollary 6.3, the exact same plots remain valid when comparing the Newton direction bounds, namely inequality (6.3) in Theorem 6.4 to the bound in Corollary 6.1. The only difference is the scaling on the axes, since one should then switch from the • x * norm to the • x0 norm. In this case the value γ is still given by (6.2), but with δ = 2 x 0 -x * x0 . 2. It is clear that our new bounds in Corollary 6.3 (and Corollary 6.1) improve on the known bounds in most cases. Even when ε = 0, we still improve if x 0 -x * x * is sufficiently large. As ε grows, our bounds clearly improve on those in Theorem 6.4. 3. In the figure, our new error bound remains bounded as the initial distance x 0 -x * x * approaches 1, but this is not the case for the bound from Theorem 6.4. Thus our new results capture a desirable feature of the convergence near the boundary of the Dikin ellipsoid.

7. Complexity of a short step interior point method using inexact search directions. We now sketch a proof of how to bound the worst-case iteration complexity of a short step interior point method using inexact search directions.

Given a convex body K ⊂ R n and a vector θ ∈ R n , we consider the convex optimization problem A subclass of self-concordant functions, that play a key role in interior point analysis, are the so-called selfconcordant barriers. DEFINITION 7.1 (Self-concordant barrier). A self-concordant function f is called a ϑ-self-concordant barrier if there is a finite value ϑ ≥ 1 given by ϑ := sup We will assume that we know a self-concordant barrier function with domain given by the interior of K, say f K .

x∈D f g x (x) 2 x .
The key observation is that one may analyse the complexity of interior point methods by only analysing the progress during one iteration; see e.g. [30, §2.4]. Thus our analysis of the previous section may be applied readily. At each interior point iteration, one approximately minimizes a self-concordant function of the form

(7.2) f (x) = η θ x + f K (x),
where η > 0 is a fixed parameter. We denote its unique minimizer by x(η), and call it the point on the central path corresponding to η. Subsequently, in the next interior point iteration, the value of η is increased, and the process is repeated.

We may now state two variants (A and B) of a short step, interior point method using inexact search directions (see Algorithm 7.1). Variant A corresponds to the short step interior point method analysed by Renegar [30, §2.4.2], but allows for inexact Newton directions. Variant B captures the framework of the interior point method of Abernethy and Hazan [1, Appendix D, supplementary material], to be discussed in Section 7.1.

We will show the following worst-case iteration complexity result. THEOREM 7.2. Consider Algorithm 7.1 with the following input parameter settings: ¯ > 0, 0 ≤ ε ≤ 1 6 , and δ = 1 4 . Both variants of the algorithm then terminate after at most

N = 40 √ ϑ ln 6ϑ 5η 0 ¯ Algorithm 7.
1 Short step interior point method using inexact directions (variants A and B) Tolerances: ε > 0 (for search direction error), ¯ > 0 (for stopping criterion) Proximity to central path parameter: δ ∈ (0, 1) Barrier parameter for f

K : ϑ ≥ 1 Objective vector θ ∈ R n Given an x 0 ∈ K and η 0 > 0 such that x 0 -x(η 0 ) x(η0) ≤ 1 2 δ (variant A) or x 0 -x(η 0 ) x0 ≤ 1 2 δ (variant B). Set the step size γ = 2(1-δ) 4 -ε(1+(1-δ) 4 ) (1-ε)(1-δ) 2 ((1-δ) 4 +1) Iteration: k = 0 while ϑ η k > 5 6 ¯ do compute d that satisfies d-g x k (x k ) x k ≤ ε g x k (x k ) x k (variant A) or d-g x(η) (x k ) x(η) ≤ ε g x(η) (x k ) x(η) (variant B) x k+1 = x k -γd η k+1 = 1 + 1 32 √ ϑ η k k ← k + 1 end while return x k an ¯ -optimal solution to min x∈K θ x iterations. The result is an x N ∈ K such that θ x N -min x∈K θ x ≤ ¯ .
Proof. The proof follows the usual lines of analysis of short step interior point methods; in particular we will repeatedly refer to Renegar [30, §2.4]. We only analyse variant B of Algorithm 7.2, as the analysis of variant A is similar, but simpler.

We only need to show that, at the start of each iteration k, one has

x k -x(η k ) x(η k ) ≤ 1 2 δ.
Since on the central path one has θ x(η) -min x∈K θ x ≤ ϑ/η, the required result will then follow in the usual way (following the proof of relation (2.18) in [30, p. 47]).

Without loss of generality we therefore only consider the first iteration, with a given x 0 ∈ K and η 0 > 0 such that x 0 -x(η 0 ) x(η0) ≤ 1 2 δ, and proceed to show that x 1 -x(η 1 ) x(η1) ≤ 1 2 δ. First, we bound the difference between the successive 'target' points on the central path, namely x(η 0 ) and x(η 1 ), where η 1 = 1 + α √ ϑ η 0 with α = 1/32. By the same argument as in [30, p. 46], one obtains:

x(η 1 ) -x(η 0 ) x(η0) ≤ α + 3α 2 (1 -α) 3 ≤ 0.0345 for α = 1/32.
Moreover, by Corollary 6.3,

x 1 -x(η 0 ) x(η0) ≤ 1 -(1 -δ) 4 1 + (1 -δ) 4 + ε x 0 -x(η 0 ) x(η0) ≤ 0.6860 • 1 2 δ ≤ 0.0857.
Using the triangle inequality,

x 1 -x(η 1 ) x(η0) ≤ x 1 -x(η 0 ) x(η0) + x(η 1 ) -x(η 0 ) x(η0)
≤ 0.0857 + 0.0345 = 0.1202.

Finally, by the definition of self-concordance, one has

x 1 -x(η 1 ) x(η1) ≤ x 1 -x(η 1 ) x(η0) 1 -x(η 0 ) -x(η 1 ) x(η0) ≤ 0.1202 1 -0.0345 ≤ 0.1245 < 1 2 δ,
as required.

It is insightful to note that, in the proof of Theorem 7.2, it would not suffice to use the classical bound from Theorem 6.4. Indeed, we used x 1 -x(η 0 ) x(η0) ≤ 0.0857 in the proof, obtained from our new bound in Corollary 6.3. If we had used Theorem 6.4 instead, we would only obtain x 1 -x(η 0 ) x(η0) ≤ 0.1042 (by using γ = 0.67), which would be too weak to complete the argument. Of course, one could prove a variation on Theorem 7.2 by using Theorem 6.4 and smaller values of δ and ε. Having said that, it is clear that our analysis adds in a meaningful way to the classical interior point analysis, removing the need to use weaker parameter values. This method has generated recent interest, since it is closely related to a simulated annealing algorithm, and may be implemented by only sampling from K. Polynomial-time complexity of certain simulated annealing methods for convex optimization was first shown by Kalai and Vempala [START_REF] Kalai | Simulated annealing for convex optimization[END_REF], and the link with interior point methods casts light on their result.

The interior point method in question used the so-called entropic (self-concordant) barrier function, introduced by Bubeck and Eldan [START_REF] Bubeck | The entropic barrier: a simple and optimal universal self-concordant barrier[END_REF], and we first review the necessary background.

7.1.1. Background on the entropic barrier method. The following discussion is condensed from [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF]. The method is best described by considering the Boltzman probability distribution on K:

P θ (x) := exp(-θ x -A(θ)) where A(θ) := ln K exp(-θ x )dx ,
where θ = η θ for some fixed parameter η > 0. We write X ∼ P θ if the random variable X takes values in K according to the Boltzman probability distribution on K with density P θ .

The convex function A(•) is known as the log partition function, and has derivatives:

∇A(θ) = -E X∼P θ [X] ∇ 2 A(θ) = E X∼P θ [(X -E X∼P θ [X])(X -E X∼P θ [X]) ].
The Fenchel conjugate of A(θ) is A * (x) := sup

θ∈R n θ x -A(θ).
The domain of A * (•) is precisely the space of gradients of A(•), and this is the set int(-K).

The following key result shows that A * provides a self-concordant barrier for the set K.

THEOREM 7.3 (Bubeck-Eldan [START_REF] Bubeck | The entropic barrier: a simple and optimal universal self-concordant barrier[END_REF]). The function

x → A * (-x) is a ϑ-self-concordant barrier function on K with ϑ ≤ n(1 + o(1)).
The function x → A * (-x) is denoted by A * -(•) and called the entropic barrier for K. At every step of the associated interior point method, one wishes to minimize (approximately) a self-concordant function of the form (7.2), where we now have the barrier function f K (x) = A * -(x). In keeping with our earlier notation for performance estimation, we denote the minimizer of f on K by x * (as opposed to x(η)). Thus x * is the point on the central path corresponding to the parameter η. We also assume a current iterate x 0 ∈ int(K) is available so that x * -x 0 x * = 1 2 δ < 1 2 . Abernathy and Hazan [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF]Appendix D,supplementary material] propose to use the following direction to minimize f :

(7.3) -d = -∇ 2 f (x * ) -1 ∇f (x 0 ).
The underlying idea is that ∇ 2 f (x * ) -1 may be approximated to any given accuracy through sampling, based on the following result. LEMMA 7.4 ([6]). One has

∇ 2 f (x * ) -1 = ∇ 2 A(θ) = E X∼P θ [(X -E X∼P θ [X])(X -E X∼P θ [X]) ],
where θ = η θ.

The proof follows immediately from the relationship between the Hessians of a convex function and its conjugate, as given in [START_REF] Crouzeix | A relationship between the second derivatives of a convex function and of its conjugate[END_REF]. Thus we may approximate ∇ 2 f (x * ) -1 by an empirical covariance matrix as follows. If X i ∼ P θ (i = 1, . . . , N ) are i.i.d., then we define the associated estimator of the covariance matrix of the X i 's as (7.4)

Σ := 1 N N i=1 (X i -X)(X i -X) where X = 1 N N i=1 X i .
The estimator Σ is known as the empirical covariance matrix, and it may be observed by sampling X ∼ P θ . This may be done efficiently: for example, Lovász and Vempala [START_REF] Lovasz | The geometry of logconcave functions and sampling algorithms[END_REF] showed that one may sample (approximately) from log-concave distributions on compact bodies in polynomial time, by using the Markov-chain Monte-Carlo sampling method called hit-and-run, introduced by Smith [START_REF] Smith | Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions[END_REF]. The following concentration result (i.e. error bound) is known for the empirical covariance matrix. We state this result to motivate our framework of analysis only -we will not use it. THEOREM 7.5 (cf. Theorems 4.1 and 4.2 in [START_REF] Adamczak | Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles[END_REF]). Assume ∈ (0, 1) and X i ∼ P θ (i = 1, . . . , N ) are i.i.d.,

(7.5) Σ = E X∼P θ (X -E X∼P θ [X])(X -E X∼P θ [X])
is the covariance matrix, and Σ is the empirical covariance matrix in (7.4). Then there exist absolute constants c > 0 and C > 0, such that, for

N ≥ C Σ 2 2 log 2 2 Σ 2 2
n, the following holds with probability at least 1 -exp(-c √ n):

(1 -)y Σy ≤ y Σy ≤ (1 + )y Σy ∀y ∈ R n (7.6)

(

-)y Σ-1 y ≤ y Σ -1 y ≤ (1 + )y Σ-1 y ∀y ∈ R n . (7.7) 1
The exact details of hit-and-run sampling are outside the scope of this paper. For simplicity, we will therefore assume, in what follows, the availability of an approximate covariance matrix Σ that satisfies (7.6) and (7.7). In other words, Theorem 7.5 only serves to motivate our assumption, we will not use it in our analysis. We give a full analysis of the sampling process in the separate work [START_REF] Badenbroek | Complexity analysis of a sampling-based interior point method for convex optimization[END_REF], where we show how to find a sample covariance matrix Σ that satisfies (7.6) and (7.7).

7.1.2. Analysis of the approximate direction in the Abernethy-Hazan algorithm. We can now show that an approximation of the search direction of Abernethy-Hazan (7.3) satisfies our 'approximate negative gradient' condition (2.1). THEOREM 7.6. Let > 0 be given, the covariance matrix Σ as in (7.5), and a symmetric matrix Σ that approximates Σ as in (7.6) and (7.7). Further, let f be as in (7.2) with minimizer x * on a given convex body K. Then the direction -d = -Σ∇f (x 0 ) at x 0 ∈ K satisfies

∇ 2 f (x * ) -1 ∇f (x 0 ) -d x * ≤ 2 1 - ∇ 2 f (x * ) -1 ∇f (x 0 ) x * .
In other words, one has g x * (x 0 ) -d x * ≤ ε g x * (x 0 ) x * where ε = 2 1-, i.e. condition (2.1) holds for the inner product •, • x * , when the reference inner product •, • is the Euclidean dot product.

Proof. We fix the reference inner product •, • as the Euclidean dot product, so that H(x * ) = ∇ 2 f (x * ) = Σ -1 and g(x 0 ) = ∇f (x 0 ). One has

H -1 (x * )g(x 0 ) -d 2 x * = H -1 (x * )g(x 0 ) -Σg(x 0 ), H -1 (x * )g(x 0 ) -Σg(x 0 ) x * = H -1 (x * )g(x 0 ) -Σg(x 0 ), g(x 0 ) -H(x * ) Σg(x 0 )] = g(x 0 ) H -1 (x * )g(x 0 ) -2g(x 0 ) Σg(x 0 ) + [ Σg(x 0 )] H(x * )[ Σg(x 0 )] ≤ (1 + )g(x 0 ) Σg(x 0 ) -2g(x 0 ) Σg(x 0 ) + (1 + )[ Σg(x 0 )] Σ-1 [ Σg(x 0 )] = 2 • g(x 0 ) Σg(x 0 ),
where the inequality is from (7.6) and (7.7). Finally, using (7.6) once more, one obtains

H -1 (x * )g(x 0 ) -d 2 x * ≤ 2 1 - g(x 0 ) H -1 (x * )g(x 0 ) = 2 1 - g x * (x 0 ) 2 x * ,
as required.

We need to consider another variant of the search direction in (7.3), since ∇f (x 0 ) will not be available exactly in general. Indeed, one can only obtain ∇f (x 0 ) approximately via the relation

∇f (x 0 ) = η θ + ∇A * -(x 0 ) = η θ + arg max θ∈R n -θ x 0 -A(θ)
, where the last equality follows from the relationship between first derivatives of conjugate functions.

Thus ∇f (x 0 ) may be approximated by solving an unconstrained concave maximization problem in θ approximately, and, for this purpose, one may use the derivatives of A(θ) as given above.

In particular, we will assume that we have available a g(x 0 ) ≈ ∇f (x 0 ) in the sense that

(7.8) gx * (x 0 ) -g x * (x 0 ) x * ≤ g x * (x 0 ) x * ,
where gx * (x 0 ) := Σg(x 0 ), g x * (x 0 ) = Σ∇f (x 0 ) as before, and > 0 is given. To motivate our assumption, we note that the function θ → -θ x 0 -A(θ) is self-concordant [START_REF] Bubeck | The entropic barrier: a simple and optimal universal self-concordant barrier[END_REF], and we may therefore use Corollary 6.1 to bound the complexity of approximating its maximizer. As with the Hessian approximation, we again omit the (lengthy) details; see Section 8 for a further discussion of our assumptions. Thus we will consider the search direction (7.9) -d := -Σg(x 0 ) ≈ -Σ∇f (x 0 ). COROLLARY 7.7. Under the assumptions of Theorem 7.6, define for a given > 0, the direction -d at x 0 ∈ D f as in (7.9), where g(x 0 ) ≈ ∇f (x 0 ) satisfies (7.8). Then one has

d -g x * (x 0 ) x * ≤ • 1 + 1 - + 2 1 - g x * (x 0 ) x * .
In other words, one has g x * (x 0 ) -d x * ≤ ε g x * (x 0 ) x * where ε = • 1+ 1-+ 2 1-, i.e. condition (2.1) holds for the inner product •, • x * , when the reference inner product •, • is the Euclidean dot product.

Proof. Recall the notation d = Σ∇f (x 0 ) from Theorem 7.6, and note that, by definition, d -d 2

x * = Σ (g(x 0 ) -g(x 0 )) 2

x * = Σ(g(x 0 ) -g(x 0 ), Σ -1 Σ(g(x 0 ) -g(x 0 )

≤ (1 + )(g(x 0 ) -g(x 0 )) Σ(g(x 0 ) -g(x 0 )) (by (7.7))

≤ 1 + 1 -gx * (x 0 ) -g x * (x 0 ) 2

x *

(by (7.6))

≤ ( ) 2 1 + 1 -g x * (x 0 ) 2

x *

(by (7.8)).

To complete the proof now only requires the triangle inequality,

g x * (x 0 ) -d x * ≤ g x * (x 0 ) -d x * + d -d x * ,
as well as the inequality from Theorem 7.6.

8. Concluding remarks. In this paper we have extended the SDP performance estimation analysis to second order methods, and demonstrated an example of how to use the resulting error bounds in the complexity analysis of inexact interior point methods. Our analysis of the interior point method of Abernethy and Hazan [START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF] gives an outline of a new proof of the polynomial complexity of the method. Having said that, we have assumed in this paper that the gradient and Hessian of the entropic barrier function may be computed within a fixed relative accuracy through sampling. It is possible to complete the analysis of the sampling process in the spirit of the work of Kalai and Vempala [START_REF] Kalai | Simulated annealing for convex optimization[END_REF] and Lovász and Vempala [START_REF] Lovasz | The geometry of logconcave functions and sampling algorithms[END_REF]. This requires detailed analysis of the hit-and-run sampling method for log-concave distributions on convex bodies, combined with the self-concordance property of the entropic barrier function. Since the resulting analysis is lengthy, and of a very different type than that presented here, we present it in a separate work, namely [START_REF] Badenbroek | Complexity analysis of a sampling-based interior point method for convex optimization[END_REF].

In that case, one can write the weighted sum of the previous constraints in the following form: Therefore, the guarantee ρ 2 ε (γ) g 0 2 ≥ g 1 2 is valid as long as both the Lagrange multipliers, and the coefficients of the norms in the previous expression are nonnegative. That is, under the following conditions:

ρ 2 ε (γ) g 0 2 ≥ g 1 2 + 2 -(1 -ε)γ(L + µ) (1 -ε)γ(L -
-the Lagrange multipliers are nonnegative as long as ρ ε (γ) ≥ 0, that is, when

γ ≤ 1 (1 -ε)µ ,
which is valid for all values of γ in the interval of interest (see below). -The coefficients of the norms are also nonnegative, since

2 -(1 -ε)γ(L + µ) ≥ 0 ⇔ γ ≤ 2 (1 -ε)(L + µ) , ( 1
-(1 -ε)γµ) ≥ 0 ⇔ γ ≤ 1 (1 -ε)µ , -(1 -ε)γµ(L + µ) -ε(L + µ) + 2µ ≥ 0 ⇔ γ ≤ 2µ -ε(L + µ) (1 -ε)µ(L + µ) ,
which are all valid on the interval of interest for γ, as:

2µ -ε(L + µ) (1 -ε)µ(L + µ) = 2 (1 -ε)(L + µ) - ε (1 -ε)µ ≤ 2 (1 -ε)(L + µ) ≤ 1 (1 -ε)µ .
Convergence of distance to optimality. Consider the following inequalities and the associated multipliers:

1 1 -µ L 1 L g 0 2 + µ x 0 -x * 2 -2 µ L g 0 , x 0 -x * + g 0 , x * -x 0 ≤ 0 : λ 0 , d -g 0 2 -ε 2 g 0 2 ≤ 0 : λ 1 .
As in the case of the gradient norm, we use the notation ρ ε (γ) := 1 -(1 -ε)µγ. Let us recall that we want to prove that the rate ρ 2 ε (γ) is valid on the interval γ ∈ 0, 2µ -ε(L + µ) (1 -ε)µ(L + µ) ,

when 2µ-ε(L+µ) (1-ε)µ(L+µ) ≥ 0 ⇔ ε ≤ 2µ
L+µ (we only consider γ ≥ 0). We now use the following values for the multipliers:

λ 0 = 2γ(1 -ε)ρ ε (γ), λ 1 = γ µε ρ ε (γ).
In that case, one can write the weighted sum of the previous constraints in the following form:

(1 -γµ(1 -ε)) 2 x 0 -x * ≥ x 1 -x * + γµ 2 (1 -ε) 2 -γ(1 -ε)(L + µ) L -µ × L -µ (1 -ε)µ 2 (2 -γ(1 -ε)(L + µ)) d - (L + µ)(1 -γµ(1 -ε)) µ 2 (2 -γ(1 -ε)(L + µ)) g 0 + x 0 -x * 2 + γ (1 -γµ(1 -ε))(2µ -ε(L + µ) -γµ(1 -ε)(L + µ)) εµ 2 (1 -ε)(2 -γ(1 -ε)(L + µ)) d -(1 -ε)g 0 2 .
1. Term 1: substituting ρ ε (γ) by its expression, nonnegativity of the coefficient follows from

γ ≤ 1 (1 -ε)µ γ ≤ 2 -ε(L -µ) Lµ(1 -ε 2 ) -1/2 (L + µ) γ ≤ 2 (1 -ε)(L + µ) which hold, as γ ≤ 2-ε(L-µ)(Lµ(1-ε 2 )) -1/2 (L+µ) ≤ 2 (1-ε)(L+µ) ≤ 1
(1-ε)µ on the interval of interest for γ. 2. Term 2: always nonnegative as 0 ≤ ρ ε (γ) ≤ 1 on the interval of interest for γ. 3. Term 3: substituting ρ ε (γ) by its expression, one can easily verify that the coefficient is positive when

γ ≤ 2 (1 -ε)(L + µ) ,
which is true on the interval of interest for γ. 4. Term 4: cancels out by substituting ρ ε (γ) by its expression.

3. 1 .

 1 Convex functions. Recall that a differentiable function f is convex on open convex set D ⊂ R n if and only if

LEMMA 3 . 1 .

 31 Let D be an open convex set and f : D → R be twice continuously differentiable. The following statements are equivalent: (a) f is convex and L-smooth on D, (b) 0 H(x) LI ∀x ∈ D, (c) g(y) -g(x), y -x ≥ 1 L g(y) -g(x) 2 ∀x, y ∈ D. Proof. (a) ⇒ (b): The proof of this implication is similar to that of [27, Theorems 2.1.5 and 2.1.6] (see relation (2.1.16) there), and is therefore omitted here. (b) ⇒ (c): If H(x) ≤ L, then H(x) -1 L H 2 (x) 0 for all x ∈ D, and Theorem 2.5 implies

THEOREM 3 . 2 .

 32 Let D be an open convex set and f : D → R be twice continuously differentiable. The following statements are equivalent: (a) f is µ-strongly convex and L-smooth on D, i.e. f ∈ F µ,L (D), (b) µI H(x) LI ∀x ∈ D, (c) f (x) -µ 2 x 2 is convex and (L -µ)-smooth on D, (d) for all x, y ∈ D we have

with S = s 11 s 12 s 12 s 22

 22

THEOREM 5 . 4 .

 54 where κ = µ/L as before.Next, we again consider a variant constrained to an open, convex set D ⊂ R n . Assume f ∈ F µ,L (D) for some open convex set D, and f twice continuously differentiable. Let

Upper bound on x 1 -x * x * ε = 1 2 ( 1 - 2 4 Thmx0 4 Thmx0 3 2( 1 - 2 3 FIG. 1 .

 12124431231 FIG. 1. Upper bounds on x 1 -x * x * from Theorem 6.4 and Corollary 6.3.

7. 1 .

 1 Analysis of the method of Abernathy-Hazan. Abernathy and Hazan[START_REF] Abernethy | Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier[END_REF] describe an interior point method to solve the convex optimization problem (7.1) if one only has access to a membership oracle for K (see Abernethy and Hazan [1, Appendix D, supplementary material]). As mentioned earlier, it falls within the framework of variant B of Algorithm 7.1 above.

+ g 1 2 +( 1 -- 1 d + g 0 2 .

 2112 µ) γ(L + µ)((ε -1)γµ + 1) (ε -1)γ(L + µ) + 2 d -2((ε -1)γµ + 1) (1 -ε)γ(L + µ) + 2 g 0 ε)γ(1 -(1 -ε)γµ) -(1 -ε)γµ(L + µ) -ε(L + µ) + 2µ ε(2 -(1 -ε)γ(L + µ)) 1 ε

  to include arbitrary inner products. The Cauchy problem remains of enduring interest; see e.g. the recent work by Bolte and Pauwels [5, §5.3]. THEOREM 5.1. Consider the inexact gradient method with exact line search applied to some

Acknowledgement. Etienne de Klerk would like to thank Riley Badenbroek for pointing out the result in Theorem 6.4, and providing its proof, and for also pointing out a mistake in the proof of Theorem 7.2 in an earlier version of this paper.

Franc ¸ois Glineur is supported by the Belgian Interuniversity Attraction Poles, and by the ARC grant 13/18-054 (Communauté franc ¸aise de Belgique). Adrien Taylor acknowledges support from the European Research Council (grant SEQUOIA 724063).

Appendix A. Worst-case example for Theorem 5.1. Here, show that the bound

from Theorem 5.1 cannot be improved on the class of smooth strongly convex functions, by giving an example of a function f ∈ F µ,L (R n ) where the bound holds with equality.

To this end, consider the two triplets (x 0 , g 0 , f 0 ), (x 1 , g 1 , f 1 ) ∈ R 2 × R 2 × R:

and

where κ := µ L is the (inverse) condition ratio, and ≥ 0. The following facts hold: 1. the pair of triplets satisfies the conditions

For this function, one iteration of gradient descent with exact line search starting at x 0 achieves exactly

yielding the desired result.

Appendix B. Proof of Theorem 5.3.

Convergence of gradient norm. As in the proof of Theorem 5.1, consider the following inequalities along with their associated multipliers:

In the following developments, we will also use the form of the algorithm:

and the notation ρ ε (γ) := 1 -(1 -ε)µγ. Recall that we want to prove that the rate ρ 2 ε (γ) is valid on the interval

L+µ (that is, we only consider γ ≥ 0). We use the following values for the multipliers:

Hence, all coefficients and multipliers are positive as long as

We refer to previous discussions for the details leading to the conclusion:

Convergence of function values. As in the previous section, we use the notation ρ ε (γ) := 1 -(1 -ε)µγ, and consider the case

For proving the desired convergence rate in terms of function values, we consider the following set of inequalities (and associated multipliers):

Note that ρ ε (γ) ≤ 1 and that the multipliers are nonnegative in the cases of interest. We can write the weighted sum of the previous constraints in the following form :

+ g 0 ρ ε (γ)(L(ρ ε (γ) -1) -µ(ρ ε (γ) + 1)) L(ρ ε (γ) -1) + µ(ρ ε (γ) + 1) + g 1 2 -ρ ε (γ)((ε + 1)γL -ρ ε (γ) -1)((ε -1)γµ -ρ ε (γ) + 1) L(2εγµ -ρ ε (γ) + 1) -µ(ρ ε (γ) + 1) g 0 2 ≥ f (x 1 ) -f (x * ).

In order to prove the last inequality, we have to show that the coefficients of the norms of the decomposition are nonnegative.