Camille Castera

Inertial Newton Algorithms Avoiding Strict Saddle Points

We study the asymptotic behavior of second-order algorithms mixing Newton's method and inertial gradient descent in non-convex landscapes. We show that, despite the Newtonian behavior of these methods, they almost always escape strict saddle points. We also evidence the role played by the hyper-parameters of these methods in their qualitative behavior near critical points. The theoretical results are supported by numerical illustrations.

Introduction

With the ever-growing size of machine learning problems, the design of algorithms for solving large-scale optimization problems remains a major challenge. In particular, many of these problems amount to the unconstrained minimization of a so-called loss functions,

min θ∈R P J (θ), (1)
where P ∈ N >0 and J : R P → R. Throughout this paper, we consider a loss functions J that is twice continuously differentiable and lower bounded on R P . Lots of efforts are put into building algorithms exploiting second-order derivatives in frameworks where both storage and computational cost are limited. In this context, [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF] recently proposed an inertial Newton algorithm (INNA) relying only on the computation of first-order derivatives, making it practical for large-scale applications such as the training of deep neural networks.

One of the assets of this algorithm is that it is built upon the following ordinary differential equation (ODE), introduced by [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF],

d 2 θ dt 2 (t) + α dθ dt (t) + β∇ 2 J (θ(t))
dθ dt (t) + ∇J (θ(t)) = 0, for all t > 0.

(2)

In (2), ∇J and ∇ 2 J denote the gradient and the Hessian of J respectively, θ : R + → R P is a twice continuously differentiable function called solution of the ODE, or trajectory, and α and β are non-negative parameters. This ODE, called DIN for dynamical inertial Newton-like system, echos famous optimization algorithms. Indeed, taking β = 0, (2) models the heavy-ball with friction (HBF) method [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] and is linked to the famous Nesterov's accelerated gradient [START_REF] Nesterov | A method for unconstrained convex minimization problem with the rate of convergence o (1/kˆ2)[END_REF][START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights[END_REF]. Similarly, when α = 0 the ODE represents an inertial Newton method [START_REF] Attouch | The second-order in time continuous newton method[END_REF]) so overall (2) models a mix between inertial gradient descent and Newton's algorithm. Additionally, (2) is relevant to tackle (1). Indeed, when the solutions of (2) converge (i.e., when they reach a limit point as t → ∞), [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF] proved that they converge to critical points of J (points where the gradient of J vanishes), similarly, the accumulation points (the limit of sub-sequences of iterations) of INNA with vanishing step-sizes yield critical points of J [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF]). Yet, in many applications-for example in deep learning-the function J is non-convex, and may thus posses spurious critical points (critical points that are not local minima). While it has been proved that gradient descent and HBF are likely to avoid strict saddles (critical points where ∇ 2 J has a negative eigenvalue, [START_REF] Goudou | The gradient and heavy ball with friction dynamical systems: the quasiconvex case[END_REF][START_REF] Lee | Gradient descent only converges to minimizers[END_REF][START_REF] O'neill | Behavior of accelerated gradient methods near critical points of nonconvex functions[END_REF], vanilla Newton's method (with unit step-sizes) is however attracted by any type of critical points, not only minima (see e.g., [START_REF] Dauphin | Identifying and attacking the saddle point problem in high-dimensional non-convex optimization[END_REF], which is problematic when solving minimization problems like (1). Since (2) mixes Newton's method and HBF, the following question remains open: are the solutions of DIN-and the INNA algorithm-likely to avoid strict saddle points? The main contribution of this paper is to answer positively to this question both for DIN and INNA with fixed step-sizes, regardless the choice of the hyper-parameters α > 0 and β > 0. Additionally, we shed light on the link between the choice of α and β and the asymptotic behavior of the solutions of DIN, with in particular the emergence of spirals when αβ < 1, this gives a better understanding of the role played by these hyper-parameters. We also provide numerical experiments illustrating our theoretical results.

Main contributions. To summarize, our main contributions are the following:

-Prove that the solutions of DIN avoid strict saddle points for almost any initialization.

-Prove the convergence of INNA with fixed step-sizes to critical points for loss functions with Lipschitz continuous gradient.

-Provide sufficient conditions such that the limit of INNA is not a strict saddle point, for almost any initialization.

-Connect the choice of the hyper-parameters α and β and the qualitative behavior of the solutions of DIN.

-Produce numerical experiments illustrating the theoretical results.

Organization. The rest of the paper is organized as follows. We recall essential notions and optimality conditions in Section 2. Section 3 states the main results regarding DIN and introduces key theorems for proving the avoidance of strict saddles (Section 3.1). A study of the qualitative asymptotic behavior of DIN is carried out in Section 3.2. The reader only interested in convergence results for the algorithm INNA may skip Section 3 and go directly to Section 4 where we provide convergence guarantees to local minimizers for INNA. Some conclusions are finally drawn. We first review the literature related to this work.

Related work. The DIN system was first introduced by [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF] and was then studied by many, in particular [START_REF] Attouch | A dynamical approach to an inertial forward-backward algorithm for convex minimization[END_REF][START_REF] Attouch | Fast convex optimization via inertial dynamics with Hessian driven damping[END_REF]; [START_REF] Shi | Understanding the acceleration phenomenon via high-resolution differential equations[END_REF] considered extensions of DIN where the hyper-parameters α and β vary over time. As we shall see, a powerful feature of DIN is that it can be written as a first-order system where the Hessian does not appear explicitly, this feature was exploited for example by [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF]; [START_REF] Chen | First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow[END_REF]; [START_REF] Attouch | First-order optimization algorithms via inertial systems with Hessian driven damping[END_REF], these authors also used discretization techniques to build discrete optimization algorithms from DIN, among which INNA, IPAHD, or HNAG to name a few. Regarding the effect of the parameters α and β, [START_REF] Attouch | First-order optimization algorithms via inertial systems with Hessian driven damping[END_REF] recently provided a global understanding of the link between these parameters and quantitative properties such as asymptotic rates of convergence, in particular for convex and strongly-convex settings. In this work we rather study qualitative properties (such as the existence of spiraling solutions) and consider non-convex landscapes. This analysis is based on the Hartman-Grobman theorem [START_REF] Grobman | Homeomorphism of systems of differential equations[END_REF][START_REF] Hartman | A lemma in the theory of structural stability of differential equations[END_REF]. Our analysis mainly relies on results from the theory of dynamical systems, and in particular on the stable manifold theorem [START_REF] Pliss | A reduction principle in the theory of stability of motion[END_REF][START_REF] Kelley | The stable, center-stable, center, center-unstable, unstable manifolds[END_REF]. This theorem can be used to prove that optimization algorithms are likely to avoid strict saddle points, it has been used for example by [START_REF] Goudou | The gradient and heavy ball with friction dynamical systems: the quasiconvex case[END_REF]; [START_REF] Lee | Gradient descent only converges to minimizers[END_REF]; O'Neill and Wright (2019) for gradient descent and HBF. Finally, the convergence of INNA with vanishing step-sizes was proved by [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF] for stochastic optimization, whereas here, we prove the convergence of INNA with fixed step-sizes for deterministic optimization.

Preliminary discussions and definitions

Before analyzing asymptotic behaviors of optimization methods, we recall some fundamental notions which will be important in what follows. Consider a function g : R P → R twice continuously differentiable, a point θ ∈ R P is a called local minimizer of g if there exists a neighborhood of θ such that g(θ ) is the smallest value achieved by g on this neighborhood. It is a global minimizer if g(θ ) is the smallest value achieved by g on R P . Local and global maximizers are defined similarly considering the largest values of g. We now recall the following optimality conditions, see for example [START_REF] Nocedal | Numerical optimization[END_REF].

Proposition 1 (Optimality conditions). Let g : R P → R be a twice continuously differentiable function and let θ ∈ R P . If θ is a local minimizer of g, then the following holds:

-First-order condition: θ is a critical point of g, i.e., ∇g(θ ) = 0.

-Second-order condition: The Hessian matrix ∇ 2 g(θ ) is positive semidefinite. Equivalently, all the eigenvalues of ∇ 2 g(θ ) are non-negative.

Similarly, for any θ ∈ R P , if ∇g(θ ) = 0 and ∇ 2 g(θ ) is positive definite (or equivalently, ∇ 2 g(θ ) has only positive eigenvalues), then θ is a local minimizer of g.

Similar results hold for maximizers but with negativity conditions for the Hessian matrix. The link between the eigenvalues of the Hessian matrix of the loss function J and the nature of its critical points plays a crucial role in the sequel. We distinguish three types of critical points:

-Those where the Hessian of J has only positive eigenvalues. From Proposition 1, these points are local minima.

-The points where the Hessian matrix has at least one negative eigenvalue, which are referred to as strict saddle points. Such a point cannot be a local minimum, it is either a maximum or not an extremum.

-The points where the Hessian matrix has only non-negative eigenvalues and at least one zero eigenvalue, we call them non-strict saddle points. Such points may be maximizers, minimizers, or neither of them. For example, consider the functions (θ

1 , θ 2 ) ∈ R 2 → 1 2 θ 2 1 + 1 2 θ 2 2 + θ 1 θ 2 and (θ 1 , θ 2 ) ∈ R 2 → θ 3 1 + θ 2 2 .
For both functions, (0, 0) is a critical point and the eigenvalues of their Hessian matrices at (0, 0) are 0 and 2. Yet, one can easily check that (0, 0) is a minimizer for the first function and is not an extremum for the second one. These considerations are illustrated on Figure 1.

(θ 1 , θ 2 ) ∈ R 2 → 1 2 θ 2 1 + 1 2 θ 2 2 + θ 1 θ 2 (on the left), the critical point (0, 0) is a minimum. For the function (θ 1 , θ 2 ) ∈ R 2 → θ 3 1 + θ 2 2
(on the right), the critical point (0, 0) is neither a minimum nor a maximum.

Due to the difficulties raised by the existence of non-strict saddle points, some results of this paper hold only for Morse functions, defined next. Definition 1. A twice continuously differentiable function g : R P → R is a Morse function if for any θ ∈ R P such that ∇g(θ ) = 0, the Hessian ∇ 2 g(θ ) has no zero eigenvalues.

Morse functions are functions for which all saddles are strict and other critical points are minima. Some of the following results are restricted to Morse functions, others are more general, yet, in every case we will need the following assumption.

Assumption 1. The loss function J in (1) has isolated critical points: for any θ ∈ R P such that ∇J (θ ) = 0, there exists a neighborhood Ω ⊂ R P of θ such that θ is the only critical point inside Ω.

This assumption guarantees in particular that J has at most a countable (possibly infinite) number of critical points. Note additionally that Assumption 1 holds for Morse functions. Let us now move on to the analysis of DIN.

Asymptotic behavior of the solutions of DIN

We recall that J : R P → R is a twice continuously differentiable function and that we denote by ∇J and ∇ 2 J its gradient and its Hessian respectively. Let α ≥ 0 and β > 0, as mentioned in the introduction, a powerful property of (2) is that it is equivalent to the following first-order system [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF],

   dθ dt (t) = -α -1 β θ(t) -1 β ψ(t) -β∇J (θ(t)) dψ dt (t) = -α -1 β θ(t) -1 β ψ(t)
, for all t > 0,

where (θ, ψ) : R + × R + → R P × R P is differentiable for all t > 0. For a given initial condition (θ 0 , ψ 0 ) ∈ R P × R P , we say that a continuously differentiable function (θ, ψ) is a solution of (3) if (θ(0), ψ(0)) = (θ 0 , ψ 0 ) and (3) holds for all t > 0. We say that (θ, ψ) converges if there exists (θ , ψ ) ∈ R P × R P such that (θ(t), ψ(t)) converges to (θ , ψ ) as t → ∞. Since J is twice continuously differentiable, the existence and uniqueness (with respect to initial conditions) of the solutions of (3) are granted by the Cauchy-Lipschitz theorem, see [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF].

In this work, we focus on the asymptotic behavior of the solutions with respect to the initial conditions.

Necessary condition for being a stationary point. As previously said, one of the main interests of (2) and hence of (3) in optimization, is that stationary points of the solutions (where the solutions stabilize) yield critical points of J . Indeed, a solution (θ, ψ) of (3) reaches a stationary point of (3) if there exists t 0 > 0, such that dθ dt (t 0 ) = 0 and dψ dt (t 0 ) = 0. This is equivalent to ψ(t 0 ) = (1 -αβ)θ(t 0 ) and ∇J (θ(t 0 )) = 0. Hence, the set of stationary points of the solutions of (3) is,

S = (θ , ψ ) ∈ R P × R P ∇J (θ ) = 0, ψ = (1 -αβ)θ .
Bounded solutions (θ, ψ) of (3) converge to points of S, hence the first coordinate θ of a bounded solution converges to a critical point of J , see [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF]; [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF]. We will thus study the type of stationary points which the solutions of (3) are likely to converge to, and then study the qualitative asymptotic behavior of these solutions.

DIN is likely to avoid strict saddle points

We start with our main result regarding the limit (as t → +∞) of the solutions of DIN.

Main convergence results

For convenience, we denote by S <0 ⊂ S the set of stationary points (θ , ψ ) such that θ is a strict saddle point of J , namely, S <0 = (θ , ψ ) ∈ S ∇ 2 J (θ ) has at least one negative eigenvalue .

Theorem 2. Suppose that Assumption 1 holds for J , then for almost any initialization, the corresponding solution of (3) does not converge to a point in S <0 .

Before proving the theorem, the following corollary is an immediate consequence suited for practical applications.

Corollary 3. Assume that J is a twice continuously differentiable Morse function. Assume also that J is coercive (i.e., that lim θ →∞ J (θ) = +∞). Then for any initialization the associated solution of (3) converges. Moreover, let (θ 0 , ψ 0 ) be a non-degenerate random variable on R P × R P , and let (θ, ψ) be the solution of (3) initialized at (θ 0 , ψ 0 ) and converging to (θ , ψ ) ∈ R P × R P . Then with probability one with respect to the draw of (θ 0 , ψ 0 ), θ is a local minimizer of J . This corollary states in particular that for a coercive Morse function, we can pick an initialization sampled from a non-degenerate distribution on R P × R P , for example a Gaussian or uniform distribution, and with probability one, the first coordinate of the limit of the solution (with respect to the initialization) is a local minimizer of J .

Proof of Corollary 3. From Castera et al. (2021, Section 3.2), the coercivity of J guarantees that any solution of (3) remains bounded, and thus from [START_REF] Alvarez | A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics[END_REF], any solution is converging. Then, the limit of any solution belongs to S. Let (θ 0 , ψ 0 ) be a random variable sampled from a non-degenerate distribution on R P × R P , by definition the support of the distribution has non-zero measure. In addition, according to Theorem 2, the set of initializations such that the solutions of (3) converge to S <0 has zero measure. So, almost surely with respect to the random variable (θ 0 , ψ 0 ), the solution of (3) initialized at (θ 0 , ψ 0 ) converges toward S\S <0 . Finally, since J is a Morse function, S \ S <0 is exactly the set of local minimizers.

Remark 1. We could state a more general (but more abstruse) result than Corollary 3 which would not require the coercivity assumption but only that the set of initializations such that the associated solutions of (3) converge has positive Lebesgue measure.

We now introduce the main tool to prove Theorem 2: the stable manifold theorem.

The stable manifold theorem

To simplify the notations we introduce the following mapping,

G : (θ, ψ) ∈ R P × R P →   -α -1 β θ -1 β ψ -β∇J (θ) -α -1 β θ -1 β ψ   , so that (3) can be re-written, d dt θ(t) ψ(t) = G(θ(t), ψ(t)), for all t > 0. (4)
For any (θ, ψ) ∈ R P × R P , we also denote by DG(θ, ψ) ∈ R 2P ×2P the Jacobian matrix of G at (θ, ψ). Remark that for any (θ, ψ) ∈ R P × R P , (θ, ψ) ∈ S ⇐⇒ G(θ, ψ) = 0, so the stationary points of (3) are exactly the zeros of G. We now state the stable manifold theorem which is the keystone to prove Theorem 2.

Theorem 4 (Stable manifold theorem [START_REF] Haragus | Local bifurcations, center manifolds, and normal forms in infinite-dimensional dynamical systems[END_REF][START_REF] Perko | Differential equations and dynamical systems[END_REF]). Let F : R 2P → R 2P be a C 1 mapping and denote by DF the Jacobian of F , consider the autonomous ODE,

dΘ dt (t) = F (Θ(t))
, for all t > 0.

(5)

Let Θ ∈ R 2P such that F (Θ ) = 0. Let E sc (Θ )
be the linear subspace of R 2P spanned by the eigenvalues of DF (Θ ) with non-positive real part. There exists a neighborhood Ω of Θ and a C 1 manifold W sc (Θ ) tangent to E sc (Θ ) at Θ -whose dimension is the number of eigenvalues of DF (Θ ) with non-positive real part-such that, for any solution Θ of (5),

(i) If Θ(0) ∈ W sc (Θ ) ∩ Ω and for T ≥ 0, Θ([0, T ]) ⊂ Ω, then Θ([0, T ]) ⊂ W sc (Θ ). (Invari- ance) (ii) If ∀t ≥ 0, Θ(t) ∈ Ω, then Θ(0) ∈ W sc (Θ ).
We see why this theorem plays an important role in the proof of Theorem 2. It states in particular that all the solutions of (5) converging to Θ must enter inside W sc (Θ ) after some time, and that W sc (Θ ) has zero measure as soon as DF (Θ ) has at least one positive eigenvalue. We will show that this holds true for G and for any point in S <0 . Now that we introduced our main tool, we can prove Theorem 2.

Proof of Theorem 2

We state an elementary lemma that will be useful.

Lemma 5. Let α ≥ 0, β > 0 and λ ∈ R. The quantity (α + βλ) 2 -4λ is non-positive if and only if αβ ≤ 1 and λ ∈ 2-αβ β 2 -2 √ 1-αβ β 2 , 2-αβ β 2 + 2 √ 1-αβ β 2 . Proof of Lemma 5. Let α ≥ 0, and β > 0, the function λ ∈ R → (α+βλ) 2 -4λ = β 2 λ 2 +2(αβ - 2)λ + α 2 is a second-order polynomial in λ whose discriminant is 16(1 -αβ). If αβ > 1 this
discriminant is negative thus the polynomial has no real roots and hence is always positive. If αβ ≤ 1, then the discriminant is positive and the roots of the polynomial are (2-αβ)

β 2 ± 2 √ 1-αβ β 2
.

We now prove Theorem 2.

Proof of Theorem 2. Let (θ , ψ ) ∈ R P × R P such that G(θ , ψ ) = 0. We first compute the eigenvalues of DG(θ , ψ ), in order to apply Theorem 4 to (4) around (θ , ψ ). By differentiating G we obtain the following Jacobian matrix, displayed in four blocks,

DG(θ , ψ ) =   -β∇ 2 J (θ ) -α -1 β I P -1 β I P -α -1 β I P -1 β I P   ,
where I P denotes the identity matrix of R P ×P . We need to compute the eigenvalues of DG(θ , ψ ) and study the sign of their real parts. In particular, we want to show that if ∇ 2 J (θ) has a (strictly) negative eigenvalue (i.e., (θ , ψ ) ∈ S <0 ), then DG(θ , ψ ) has at least one (strictly) positive eigenvalue, and thus according to Theorem 4, the stable manifold associated to (θ , ψ ) has zero measure. First, ∇ 2 J (θ ) is real and symmetric, so the spectral theorem states that there exists an orthogonal matrix V such that V T ∇ 2 J (θ )V is a diagonal matrix. Thus the matrix,

V T 0 0 V T DG(θ , ψ ) V 0 0 V =   -βV T ∇ 2 J (θ )V -α -1 β I P -1 β I P -α -1 β I P -1 β I P   (6)
is a sparse matrix with only 3 non-zero diagonals and whose eigenvalues are the same as those of DG(θ , ψ ). Exploiting the tridiagonal structure, there exists a symmetric permutation U ∈ R 2P ×2P -specified in (19) in Section A of the appendix-such that we can transform (6) into a block diagonal matrix,

U T V T 0 0 V T DG(θ , ψ ) V 0 0 V U =    M 1 . . . M P    , (7)
where for each p ∈ {1, . . . , P }, M p is a 2 × 2 matrix defined as follows. Denote by (λ p ) p∈{1,...,P } the eigenvalues of ∇ 2 J (θ ), for all p ∈ {1, . . . , P },

M p =   -α -1 β -βλ p -1 β -α -1 β -1 β   , up to a symmetric permutation.
The eigenvalues of DG(θ , ψ ) are obtained by computing those of the matrices M p . Let p ∈ {1, . . . , P }, the eigenvalues of M p are the roots of its characteristic polynomial:

χ Mp : X ∈ R → X 2 -trace(M p )X + det(M p ), which gives for any X ∈ R, χ Mp (X) = X 2 + (α + βλ p )X + λ p .
This is a second-order polynomial, whose discriminant is,

∆ Mp = (α + βλ p ) 2 -4λ p . (8)
The eigenvalues of M p depend on the sign of ∆ Mp which is given by Lemma 5. We now show that if λ p < 0, then M p has a positive eigenvalue. First assume that ∆ Mp ≤ 0. Lemma 5 states that in this case, we have αβ ≤ 1 and

λ p ∈ 2-αβ β 2 -2 √ 1-αβ β 2 , 2-αβ β 2 + 2 √ 1-αβ β 2
. An elementary study of the function

x ∈ [0, 1] → 2 -x -2 √ 1 -x shows however that for 0 ≤ αβ ≤ 1, 2-αβ β 2 -2 √ 1-αβ β 2
≥ 0, so ∆ Mp ≤ 0 implies λ p ≥ 0. Thus, we do not need to further investigate the case ∆ Mp ≤ 0 since this case never occurs when λ p < 0.

Suppose now that ∆ Mp > 0, then M p has two real eigenvalues,

   σ p,+ = -(α+βλp) 2 + √ ∆ Mp 2 = -(α+βλp) 2 + √ (α+βλp) 2 -4λp 2 σ p,-= -(α+βλp) 2 - √ ∆ Mp 2 = -(α+βλp) 2 - √ (α+βλp) 2 -4λp 2
.

In this case, assume that λ p < 0. If α + βλ p ≤ 0, then σ p,+ is a sum of a non-negative and a positive term, so σ p,+ > 0. If α+βλ p ≥ 0, then 2σ p,+ = -(α+βλ p )+ (α + βλ p ) 2 + 4(-λ p ) > 0 since 4(-λ p ) > 0. Overall, we showed that in every case, λ p < 0 =⇒ σ p,+ > 0. So whenever there exists p ∈ {1, . . . , P } such that λ p < 0, DG(θ , ψ ) has at least one positive eigenvalue.

We can now apply the stable manifold theorem. Let (θ , ψ ) ∈ S <0 . Let an initialization (θ 0 , ψ 0 ) such that the corresponding solution (θ, ψ) of (4) converges to (θ , ψ ). Denote Φ : R P × R P × R → R P × R P × R the flow of the solutions of (4), so that we have in particular for all t ≥ 0, (θ(t), ψ(t)) = Φ((θ 0 , ψ 0 ), t) and (θ 0 , ψ 0 ) = Φ((θ(t), ψ(t), -t). Consider the manifold W sc (θ , ψ ) and the neighborhood Ω as defined in Theorem 4. The convergence of (θ, ψ) implies that there exists t 0 ≥ 0 such that for all t ≥ t 0 , (θ(t), ψ(t)) ∈ Ω, so according to Theorem 4, ∀t ≥ t 0 , (θ(t), ψ(t)) ∈ Ω∩W sc (θ , ψ ). Expressing this in terms of flows, ∀t ≥ t 0 , Φ((θ 0 , ψ 0 ), t) ∈ Ω ∩ W sc (θ , ψ ) and hence ∀t ≥ t 0 , Φ((θ 0 , ψ 0 ), t)

∈ k∈N Φ (Ω ∩ W sc (θ , ψ ), -k) , (9)
where the right-hand side in (9) corresponds to the union over k ∈ N of initial conditions such that the associated solution has reached

Ω ∩ W sc (θ , ψ ) at time k. Let W(θ , ψ ) = (θ 0 , ψ 0 ) ∈ R P × R P Φ((θ 0 , ψ 0 ), t) ----→ t→+∞ (θ , ψ ) ,
the set of all initial conditions such that the associated solution converges to (θ , ψ ). According to (9), we have proved that,

W(θ , ψ ) ⊂ k∈N Φ (Ω ∩ W sc (θ , ψ ), -k) . (10)
Now, we previously showed that since (θ , ψ ) ∈ S <0 , DG(θ , ψ ) has one or more positive eigenvalues, so according to the stable manifold theorem, the dimension of W sc (θ , ψ ) is strictly less than 2P , hence this manifold has zero measure. Due to the uniqueness of the solutions of (4), for any k ∈ N, Φ(•, -k) is a local diffeomorphism, hence it maps zero-measure sets to zeromeasure sets. Consequently, the right-hand side in ( 10) is a countable union of zero-measure sets, so it has zero measure as well, and the same goes for W(θ , ψ ).

To conclude the proof of the theorem, by Assumption 1, the critical points are isolated so their number is countable. So (θ ,ψ )∈S <0 W(θ , ψ ) is a countable union of zero-measure sets so it has zero measure.

Remark 2. Keeping the notations of the proof of Theorem 2, we proved that for p ∈ {1, . . . , P }, if λ p < 0 then σ p,+ > 0. Looking at the proof, note that we could also show quite easily that λ p > 0 =⇒ σ p,+ < 0, so for any local minimizer with non-singular Hessian, the associated stable manifold does not have zero measure. In particular, the stable manifold associated to any local minima of a twice differentiable Morse functions does not have zero measure.

On the complex eigenvalues of DG

In the proof of Theorem 2 we showed that for any (θ , ψ ) ∈ S, if an eigenvalue λ p of the Hessian ∇J (θ ) is negative, then the associated discriminant ∆ Mp is positive and thus the eigenvalues of DG(θ , ψ ) are real. Note however that when there exists p ∈ {1, . . . , P } such that λ p ≥ 0 (and hence in particular around local minima), we may have ∆ Mp ≤ 0. This is the case whenever αβ ≤ 1, and

λ p ∈ 2-αβ β 2 -2 √ 1-αβ β 2 , 2-αβ β 2 + 2 √ 1-αβ β 2
. When the aforementioned conditions hold, DG(θ , ψ ) has complex eigenvalues,

   σ p,+ = -(α+βλp) 2 + i √ -∆ Mp 2 = -(α+βλp) 2 + i √ 4λp-(α+βλp) 2 2 σ p,-= -(α+βλp) 2 -i √ -∆ Mp 2 = -(α+βλp) 2 -i √ 4λp-(α+βλp) 2 2 . ( 11
)
Overall, we proved that DIN is likely to avoid strict saddle points, and we additionally observed that around local minima, the Jacobian DG may or may not have eigenvalues with non-zero imaginary part. The existence of complex eigenvalues may change the qualitative behavior of the solutions around local minima. Next section is devoted to studying this matter.

Behavior of the solutions of DIN around stationary points

Accordingly to what we just discussed in Section 3.1.4, we wish to characterize the qualitative asymptotic behavior of the convergent trajectories of DIN.

The Hartman-Grobman theorem

To this aim, we introduce the Hartman-Grobman theorem.

Theorem 6 (Hartman-Grobman [START_REF] Perko | Differential equations and dynamical systems[END_REF]). Consider the following dynamical system,

dΘ dt (t) = F (Θ(t)), t ∈ R (12)
where Θ : R → R 2P , F : R 2P → R 2P is C 1 and denote by DF the Jacobian matrix of F . Assume that there exists Θ ∈ R 2P such that F (Θ ) = 0 and DF (Θ ) has only non-zero eigenvalues.

Then, there exists a neighborhood Ω of Θ and a homeomorphism H (a bijective continuous function whose inverse is continuous) such that, for any

Θ 0 ∈ Ω, if Θ is a solution of (12) with Θ(0) = Θ 0 , there exists an open interval of time T ⊂ R containing 0 such that the function Φ = H • Θ is the solution of dΦ dt (t) = DF (Θ )Φ(t), t ∈ T, (13)
with initial condition Φ(0) = H(Θ 0 ). The homeomorphism H preserves the parameterization by time (it does not reverse time).

This theorem essentially states that, in a neighborhood of a stationary point Θ where the Jacobian matrix DF (Θ ) is non-singular the solutions of ( 12) have a qualitative behavior similar to those of the linearized system (13).

Application to DIN

Application of the theorem. Let (θ , ψ ) ∈ S be a stationary point of (3) such that θ is a local minimizer of J and such that ∇ 2 J (θ ) has only non-zero eigenvalues (this is guaranteed for all local minima if J is a Morse function). Consider the differential equation, d dt

θ(t) ψ(t) = DG(θ , ψ ) θ(t) ψ(t) , t ∈ R. ( 14
)
According to Remark 2 and the proof of Theorem 2, all the eigenvalues of DG(θ , ψ ) have strictly negative real parts. So there exists a homeomorphism H and a neighborhood Ω of (θ , ψ ) on which Theorem 6 holds. In particular, for any initial condition (θ 0 , ψ 0 ) ∈ Ω, the associated solution of (4) converges to (θ , ψ ) (because the corresponding solution of ( 14) converges to (θ , ψ ) and H preserves the parameterization by time). So for any initialization in (θ 0 , ψ 0 ) ∈ Ω, the corresponding solution (θ, ψ) of (4) remains in Ω, i.e., ∀t ≥ 0, (θ(t), ψ(t)) ∈ Ω. Thus we can use the Hartman-Grobman around (θ(t), ψ(t)) for any t ≥ 0. As a result, for any initialization in (θ 0 , ψ 0 ) ∈ Ω, and for all t ≥ 0, the associated solution (θ, ψ) of (4) reads, (θ(t), ψ(t)) = H -1 ( θ(t), ψ(t)) where ( θ, ψ) is the solution of ( 14) with initial condition ( θ(t 0 ), ψ(t 0 )) = H(θ(0), ψ(0)).

We give a more precise expression for this solution. As done in the proof of Theorem 2 we can diagonalize DG(θ , ψ ): there exists a matrix Q ∈ R 2P ×2P such that DG(θ , ψ ) = QDQ -1 , where D = diag(σ 1 , . . . , σ 2P ), and (σ p ) {1,...,2P } are the eigenvalues of DG(θ , ψ ). Using the diagonalization, the solution of ( 14) is given for all t ∈ R by θ(t)

ψ(t) = Qe tD Q -1 θ(0) ψ(0)
. So going back to (θ, ψ), we have,

θ(t), ψ(t) = H -1 Qe tD Q -1 H(θ(0), ψ(0)) , for all t ≥ 0. ( 15
)
Finally, let any initialization (θ 0 , ψ 0 ) ∈ R P × R P (not necessarily belonging to Ω), such that the corresponding solution (θ, ψ) of (4), converges to (θ , ψ ). Then there exists t 0 ≥ 0 such that for all t ≥ t 0 , (θ(t), ψ(t)) ∈ Ω, and the arguments above apply after t 0 .

Form of the solutions. We proved that after some time, a solution (θ, ψ) of (4) that converges to (θ , ψ ) ∈ S can be expressed with formula (15) (up to a time shift). If αβ ≤ 1 and all the eigenvalues of ∇

2 J (θ ) are not in 2-αβ β 2 -2 √ 1-αβ β 2 , 2-αβ β 2 + 2 √ 1-αβ β 2
, or if αβ > 1, then all the eigenvalues of DG(θ , ψ ) are real so the coordinates of Q -1 e tD Q in (15) are sums of exponential functions decreasing in time. However, if αβ ≤ 1 and there exists eigenvalues of ∇ 2 J (θ ) belonging to the interval mentioned above, then there exists eigenvalues of DG(θ , ψ ) with non-zero imaginary part. Let p ∈ {1, . . . , P } such that λ p is an eigenvalue of ∇ 2 J (θ ) belonging to the aforementioned interval. From (11), there exists two complex eigenvalues:

-(α+βλp) 2 ± i √ 4λp-(α+βλp) 2 2
, and thus the coordinates of the matrix e tD in (15) contain terms of the form, e -(α+βλp) 2

t (cos(ω p t) ± i sin(ω p t)) ,

where

ω p = √ 4λp-(α+βλp) 2 2
. So in this setting, and in this setting only, the imaginary parts of the eigenvalues of DG(θ , ψ ) generate oscillating terms and the solution of the linearized model t → Qe tD Q -1 (plus initial condition) spirals around (θ , ψ ) as it converges toward it. This is illustrated on Figure 2 where such a behavior is indeed observed for a (numerically approximated) solution of (3). Note finally that ω p is a decreasing function of β, hence increasing the parameter β reduces the oscillations.

Numerical illustration of the spiraling phenomenon

Setting. To illustrate the spiraling phenomenon, we consider a simple quadratic function

J : (θ 1 , θ 2 ) ∈ R 2 → θ 2 1 + 2θ 2 2 . This loss function is C 2 (R 2 )
, and for all (θ 1 , θ 2 ) ∈ R 2 , it has a constant diagonal Hessian:

∇ 2 J (θ 1 , θ 2 ) = 2 0 0 4
. This is a convex function whose unique global minimizer is (θ , ψ ) = (0, 0). Instead of solving exactly (3), we find an approximate solution via the discrete algorithm INNA derived from (3) and presented in next section. To do so, we ran the algorithm with very small step-sizes. The algorithm is initialized at (1, 1). We consider two choices of parameters: (α, β) = (2, 0.1) and (α, β) = (2, 1). The former illustrates the case αβ < 1 while the second corresponds to the case where αβ > 1. According to Section 3.1.4, with the configuration (α, β) = (2, 0.1), the range of eigenvalues for which we should observe spirals is approximately [1, 359] so both eigenvalues of the Hessian of J lie in this interval.

Results. The expected behavior (discussed on Section 3.2.2) can be observed on the left of Figure 2. When αβ < 1 (red curve), the trajectory spirals around the critical point (0, 0). On the contrary, the phenomenon does not occur when αβ > 1 (orange curve). Remark also that when zooming very close to (0, 0), the oscillating behavior is still present. Note however that this qualitative results says nothing about the speed of convergence, as evidenced on the right of Figure 2. Despite the presence of spirals, the setting where αβ < 1 yields a faster algorithm both in terms of loss function values and distance to the minimizer. From a theoretical point of view, the Hartman-Grobman theorem connects the solutions of (3) and those of its linearized approximation through a mapping which is homeomorphic (hence continuous) but not necessarily differentiable. As a consequence, the theorem does not guarantee that the speed of convergence is preserved. Regarding the speed of convergence, we refer to [START_REF] Attouch | First-order optimization algorithms via inertial systems with Hessian driven damping[END_REF][START_REF] Attouch | Convergence of iterates for first-order optimization algorithms with inertia and hessian driven damping[END_REF] in the convex setting and to [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF] for the non-convex case.

Vanishing viscous damping. To finish this section, we empirically investigate the oscillating phenomenon when using an asymptotically vanishing damping. More precisely, we consider a viscous damping α(t) that may vary over time, and in particular that progressively decreases to zero as t → ∞. Such damping has been given a lot of attention after the work of [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights[END_REF] who made a connection between Nesterov's accelerated gradient [START_REF] Nesterov | A method for unconstrained convex minimization problem with the rate of convergence o (1/kˆ2)[END_REF]) and a differential equation with a damping proportional to 1/t. As for DIN, if such a damping is used while keeping β fixed, we eventually have α(t)β ≤ 1 after some time. Our approach is however purely empirical since the Hartman-Grobman theorem holds only for autonomous ODEs 1 (hence with α not decreasing with t). In this setting we do observe spirals (see Figure 2), actually, we see on the blue curve that for (α(t), β) = (2/t, 0.1), the spirals are so large that the algorithm is much slower than it was for fixed values of (α, β). However when taking a

J : (θ 1 , θ 2 ) ∈ R 2 → θ 2 1 + 2θ 2 2 .
Top-left figure displays the evolution of the iterates on the landscape of the loss function with two zooms on bottom-left figures. Right figures show the value of the loss function and the distance to the global minimizer (0, 0) as a function of the iterations. larger β (green curve), these oscillations are damped (although still noticeable), yielding better performances in terms of speed.

Asymptotic behavior of INNA

We now turn our attention to the asymptotic behavior of the algorithm INNA introduced by [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF]. Throughout this section we fix α ≥ 0 and β > 0 the hyper-parameters of INNA. The INNA algorithm is originally designed for non-smooth and stochastic applications, however, in order to study its asymptotic behavior, we consider a simpler framework. We analyze the algorithm for a loss function J that is twice continuously differentiable and consider a deterministic version of the algorithm. In this framework, we may use fixed step-sizes: let γ > 0 be a step-size, in this setting, the INNA algorithm reads,

   θ k+1 = θ k + γ -(α -1 β )θ k -1 β ψ k -β∇J (θ k ) ψ k+1 = ψ k + γ -(α -1 β )θ k -1 β ψ k . ( 16
)
This algorithm is obtained via an explicit Euler discretization of (3), thus, we may hope the asymptotic behavior of INNA to be similar to that of the solutions of DIN. Actually, the set of stationary points of INNA is the same as that of DIN (see Section B.1 of the appendix):

S = (θ, ψ) ∈ R P × R P ∇J (θ) = 0, ψ = (1 -αβ)θ .
In this section, we prove that for almost any initialization, INNA does not converge to strict saddle points. To this aim we recall the definition of the set S <0 , S <0 = (θ, ψ) ∈ S ∇ 2 J (θ) has at least one negative eigenvalue .

INNA generically avoids strict saddles

In order to derive results for INNA similar to those for DIN, we will have to carefully choose the step-size γ > 0. To this aim, we need the following assumption.

Assumption 2. There exists L ∇J > 0 such that the gradient ∇J of the loss function J is L ∇J -Lipschitz continuous on R P (with respect to a given norm • on R P ). In other words, for any θ 1 ∈ R P and θ 2 ∈ R P ,

∇J (θ 1 ) -∇J (θ 2 ) ≤ L ∇J θ 1 -θ 2
This assumption implies that at any point of R P , the eigenvalues of ∇ 2 J are bounded by the constant L ∇J . Under this assumption our main result regarding INNA follows.

Theorem 7. Under Assumption 1 and 2, if α > 0 and the step-size γ is such that,

0 < γ < min β 2 + α 2L ∇J - (α + βL ∇J ) 2 -4L ∇J 2L ∇J , β , (17)
-where the right-hand side in ( 17) is always positive-then for almost any initialization, INNA does not converge to a point in S <0 .

The proof relies on arguments similar to those of Theorem 2 and it thus postponed to Section B of the appendix for the sake of readability. Theorem 7 is particularly relevant if INNA converges (otherwise the statement is trivial). Next result provides sufficient conditions so that convergence holds.

Theorem 8. Assume that α > 0. Let (θ 0 , ψ 0 ) ∈ R P × R P and let (θ k , ψ k ) k∈N be the sequence generated by INNA initialized at (θ 0 , ψ 0 ). Under Assumption 2, if the step-size γ is such that,

0 < γ < min 2α (1 + αβ)L ∇J + α 2 , 1 α + β, 2β , (18)
then the sequence of values (J (θ k )) k∈N converges and

lim k→+∞ ∇J (θ k ) 2 = 0.
If in addition the sequence (θ k ) k∈N is bounded and Assumption 1 holds, then (θ k ) k∈N converges to a critical point of J .

Remark 3 (Comments on Theorem 8).

-Note that in (18), only the condition γ < 2α/ ((1 + αβ)L ∇J + α 2 ) depends on the function J (through the Lipschitz constant L ∇J ), the other two being only related to the hyper-parameters of INNA. This is similar to the well-known condition γ < 2/L ∇J used for gradient descent, see e.g., Bertsekas et al. (1998, Proposition 2.3.2).

-The first part of the theorem states in particular that any accumulation point (the limit of any sub-sequence) is a critical point of J . The additional boundedness assumption is necessary only to guarantee the convergence of (θ k ) k∈N to such critical points. Due to the convergence of (J (θ k )) k∈N , this assumption is valid, for example, when J is coercive, which holds in many problems met in practice.

: (θ 1 , θ 2 ) ∈ R 2 → θ 4 1 -4θ 2 1 + θ 2 2
. This function has two minimizers (-√ 2, 0) and ( √ 2, 0) and one strict saddle point (0, 0). The red and blue surfaces represent the parts where J is locally concave and convex respectively. The stable manifold of J around (0, 0) is represented by the grey curve. Left figure shows the behavior of INNA for two choices of hyper-parameters and for two initializations belonging to the stable manifold of (0, 0). In this setting the algorithm does converge to the strict saddle (0, 0). When initialized near but outside the manifold (right figure), the algorithm avoids the strict saddle and converges to a local minimizer for both choices of hyper-parameters.

The proof relies on a Lyapunov argument and is also postponed to the appendix (see Section C). Combining Theorem 7 and 8, we can formulate a corollary suited for practical applications.

Corollary 9. Assume that J is a twice continuously differentiable coercive Morse function and that Assumption 2 holds. Assume that α > 0, and that the step-size γ > 0 is such that both (17) and (18) hold. Let (θ 0 , ψ 0 ) be a non-degenerate random variable on R P × R P , and let (θ k , ψ k ) k∈N be the iterations of INNA initialized at (θ 0 , ψ 0 ). Then (θ k ) k∈N converges, and with probability one, the limit θ ∈ R P is a local minimizer of J .

The proof follows similar lines as those of Corollary 3 and the practical consequences of Corollary 9 are the same as those discussed for DIN. We conclude the study with numerical illustrations.

Numerical Illustration

We finish the study of INNA with a short empirical illustration of Theorem 7 on a toy example. To this aim we consider the function J

: (θ 1 , θ 2 ) ∈ R 2 → θ 4 1 -4θ 2 1 + θ 2 2 .
This function is twice continuously differentiable on R 2 , non-convex, has a diagonal Hessian and three critical points: Initialization on the stable manifold

INNA αβ < 1 0% 0% 100% - INNA αβ > 1 0% 0% 100% - Gradient Descent 0% 0% 100% - two local minimizers (- √ 2, 0
) and ( √ 2, 0) and one strict saddle point (0, 0). The landscape of J is displayed on Figure 3. The set of initializations such that INNA converges to the strict saddle point (0, 0) is the manifold θ 2 ∈ R → (0, θ 2 ) which has indeed zero measure on R 2 . Figure 3 shows that when initialized on this manifold, the algorithm does converge to (0, 0) but when initialized anywhere else, it avoids the strict saddle.

In addition to this illustration, we ran INNA and gradient descent -which is also known for almost surely escaping strict saddle points [START_REF] Lee | Gradient descent only converges to minimizers[END_REF]-for 1000 random Gaussian initializations sampled from N 2 (0, 10 -24 ), hence extremely close to the saddle point (0, 0). We also perform the same experiment but with a random initialization on the stable manifold. The results reported on Table 1 demonstrate that the algorithm always escapes the saddle point and converges to one of the two local minimizers. This empirically illustrates Theorem 7 and Corollary 9.

Conclusion

In this work, we provided a better understanding of the role played by the hyper-parameters α and β. This could help users of INNA to choose these parameters in practical applications. More importantly, we proved that the asymptotic behaviors of INNA and DIN make them relevant to tackle non-convex minimization problems. In particular, we provided conditions so that INNA converges and so that it is likely to avoid strict saddle points for almost all initializations.

following, for all p ∈ {1, . . . , P }, if P is odd:

     U P -p+1,p = 1 -mod(p, 2) U P +p,2P -p+1 = mod(p, 2) U p,2P -p = mod(p, 2)
, if P is even:

         U p,p = mod(p, 2) U P +p,P +p = 1 -mod(p, 2) U P +p,p = mod(p, 2) U p,P +p = mod(p, 2) . (19)
For example, for P = 3 and P = 4 this yields the following matrices (where the zero coefficients are omitted for the sake of readability),

        • • • • 1 • • 1 • • • • • • 1 • • • • • • • • 1 1 • • • • • • • • 1 • •         and             1 • • • • • • • • • • • 1 • • • • • 1 • • • • • • • • • • • 1 • • 1 • • • • • • • • • • • 1 • • • • • 1 • • • • • • • • • • • 1            
.

B Proof of Theorem 7

In order to prove Theorem 7, we will use a version of the stable manifold theorem suited to the analysis of discrete processes.

B.1 Stable manifold theorem for discrete processes

We introduce a different version of the stable manifold theorem. This version was used by [START_REF] Lee | Gradient descent only converges to minimizers[END_REF][START_REF] O'neill | Behavior of accelerated gradient methods near critical points of nonconvex functions[END_REF][START_REF] O'neill | Behavior of accelerated gradient methods near critical points of nonconvex functions[END_REF] to analyze gradient descent and the HBF methods respectively. For a function F : R P → R P and for all k ∈ N >0 , we introduce the following notation:

F k = F • . . . • F k compisitions
. The result is the following.

Theorem 10 (III.7 [START_REF] Shub | Global stability of dynamical systems[END_REF]). Let Θ ∈ R 2P be a fixed point for the

C 1 local diffeomorphism F : U → R 2P where U ⊂ R 2P is a neighborhood of Θ . Let E sc (Θ )
be the linear subspace spanned by the (complex) eigenvalues of DF (Θ ) with magnitude less than one. There exists a neighborhood Ω of Θ and a C 1 manifold W sc (Θ ) tangent to E sc (Θ ) at Θ -whose dimension is the number of eigenvalues of DF (Θ ) with magnitude less than one-such that, for

Θ 0 ∈ R 2P , (i) If Θ 0 ∈ W sc (Θ ) and F (Θ 0 ) ∈ Ω then F (Θ 0 ) ∈ W sc (Θ ) (Invariance). (ii) If ∀k ∈ N >0 , F k (Θ 0 ) ∈ Ω, then Θ 0 ∈ W sc (Θ ).
Although we study an iterative algorithm and not the solutions of an ODE, the results stated in Theorem 10 are very similar to those of Theorem 4, thus, the proof of Theorem 7 is close to the proof of Theorem 2.

Formulating INNA to use Theorem 10. Proceeding similarly to Section 3.1, for any (θ, ψ) ∈ R P × R P , we redefine the mapping G as,

G θ ψ =   θ + γ -(α -1 β )θ -1 β ψ -β∇J (θ) ψ + γ -(α -1 β )θ -1 β ψ   , (20)
so that an iteration k ∈ N of INNA reads (θ k+1 , ψ k+1 ) = G(θ k , ψ k ). Remark that unlike for (3), we now study the fixed points of G and not its zeros. Indeed, the iterative process INNA consists in successive compositions of the operator G and the set of fixed points of G is exactly S. To prove this statement, let (θ,

ψ) ∈ R P × R P , G(θ, ψ) = (θ, ψ) ⇐⇒ -(α -1 β )θ -1 β ψ -β∇J (θ) = 0 -(α -1 β )θ -1 β ψ = 0 ⇐⇒ ∇J (θ) = 0 ψ = (1 -αβ)θ . So (θ, ψ) is a fixed point of G if and only if ∇J (θ) = 0 and ψ = (1 -αβ)θ.

B.2 Proof of Theorem 7

Block-diagonal transformation. Throughout the proof we use a block-diagonal transformation. Let (θ,

ψ) ∈ R P × R P . Since J is C 2 on R P then G is C 1 on R P × R P and the Jacobian matrix of G at (θ, ψ) (displayed by block) reads, DG(θ, ψ) = (1 -γ(α -1 β ))I P -γβ∇ 2 J (θ) -γ β I P -γ(α -1 β )I P (1 -γ β )I P .
Proceeding like in Section 3.1, their exists an orthogonal matrix V ∈ R P ×P and a permutation U ∈ R 2P ×2P (defined in Section A) such that,

U T V T 0 0 V T DG(θ, ψ) V 0 0 V U =    M 1 . . . M P    , (21)
where for each p ∈ {1, . . . , P },

M p = 1 -γ(α -1 β ) -γβλ p -γ β -γ(α -1 β ) 1 -γ β
-up to a symmetric permutation-and (λ p ) p∈{1,...,P } are the eigenvalues of ∇ 2 J (θ). To apply the stable manifold theorem and prove Theorem 7 we need G to be a local diffeomorphism. This result is nonstraightforward to obtain, so we state it as a theorem before proving Theorem 7.

Theorem 11. Under Assumption 2, for any α > 0, β > 0 and

0 < γ < min β 2 + α 2L ∇J - (α + βL ∇J ) 2 -4L ∇J 2L ∇J , β , the mapping G defined in (20) is a local diffeomorphism from R P × R P to R P × R P .
We finish the proof of Theorem 7 first, and then prove this theorem in Section B.3.

Application of Theorem 10 to prove Theorem 7. We can now prove Theorem 7.

Proof of Theorem 7. Let α > 0, β > 0 and 0 < γ < min

β 2 + α 2L ∇J - √ (α+βL ∇J ) 2 -4L ∇J 2L ∇J , β .
Consider the mapping G defined in (20) with these parameters. By direct application of Theorem 11, G is a local diffeomorphism. Let (θ , ψ ) ∈ R P × R P be a fixed point of G. Our goal is to apply the stable manifold theorem in a neighborhood of this point.

To this aim, we study under which conditions on the eigenvalues of ∇2 J (θ ) the eigenvalues of DG(θ , ψ ) have magnitude less than one. Throughout the proof we consider the same block-diagonal transformation of DG(θ , ψ ) as in ( 21), and we keep the same notations. Let p ∈ {1, . . . , P }, the eigenvalues of M p are the roots of the following polynomial,

χ Mp (X) = X 2 -trace(M p )X + det(M p ) = X 2 -(2 -γ(α + βλ p ))X + 1 -γ(α + βλ p ) + γ 2 λ p . The discriminant of χ Mp is, ∆ Mp = (2 -γ(α + βλ p )) 2 -4(1 -γ(α + βλ p ) + γ 2 λ p ) = 4 + γ 2 (α + βλ p ) 2 -4γ(α + βλ p ) -4 + 4γ(α + βλ p ) -4γ 2 λ p = γ 2 (α + βλ p ) 2 -4λ p .
Remark that up to a factor γ 2 > 0, this is the same discriminant as in (8) from Section 3.1. Therefore, we can once again use Lemma 5 to deduce that ∆ Mp is non-positive if and only if

αβ ≤ 1 and λ p ∈ 2-αβ β 2 -2 √ 1-αβ β 2 , 2-αβ β 2 + 2 √ 1-αβ β 2
. We split the study with respect to the sign of ∆ Mp .

• If ∆ Mp > 0, then M p has two real eigenvalues,

σ p,+ = 1 -1 2 γ(α + βλ p ) + 1 2 γ (α + βλ p ) 2 -4λ p σ p,-= 1 -1 2 γ(α + βλ p ) -1 2 γ (α + βλ p ) 2 -4λ p .
We then study whether the magnitudes of the eigenvalues are smaller or larger than 1, the computations are very similar to those of Section 3.1. If λ p < 0, then |(α + βλ p )| < (α + βλ p ) 2 -4λ p , so σ p,+ > 1 and σ p,-< 1, so we have at least one eigenvalue with magnitude larger than one. If λ p = 0, then σ p,+ = 1 and |σ p,-| = |1 -γα| ≤ 1. 2

In order to be exhaustive, remark that if λ p > 0, then (α + βλ p ) > (α + βλ p ) 2 -4λ p , so 0 ≤ σ p,+ < 1 and -∞ < σ p,-< 1, so the bounds enforced on γ ensure that both eigenvalues have magnitude less than 1. This is indeed the case whenever -σ p,-< 1, which is equivalent to γ α + βλ p + (α + βλ p ) 2 -4λ p < 4 and the latter always holds true. Indeed, when αβ > 1, one can show that the function x > 0 → α + βx + (α + βx) 2 -4x is increasing (by differentiating it). Then, using Assumption 2 and the upper bound enforced on γ it holds,

γ α + βλ p + (α + βλ p ) 2 -4λ p < (α + βL ∇J ) -(α + βL ∇J ) 2 -4L ∇J 2L ∇J (α + βL ∇J ) + (α + βL ∇J ) 2 -4L ∇J < 4L ∇J 2L ∇J = 2 < 4. ( 22
)
On the other hand, when αβ ≤ 1, by studying again the function x > 0 → α + βx + (α + βx) 2 -4x, one can show3 that,

α + βλ p + (α + βλ p ) 2 -4λ p ≤ max 2α, α + βL ∇J + (α + βL ∇J ) 2 -4L ∇J . (23)
Then if the maximum in the right-hand side of ( 23) is 2α, it holds,

γ α + βλ p + (α + βλ p ) 2 -4λ p ≤ 2αγ ≤ 2αβ ≤ 2 < 4,
and if the maximum is the other value, we use ( 22) again. To summarize, when ∆ Mp > 0, λ p ≥ 0 ⇐⇒ |σ p,+ | ≤ 1 and |σ p,-| ≤ 1.

• If ∆ Mp ≤ 0 then this implies that λ p ≥ 0 so (θ , ψ ) ∈ S <0 and we do not need additional arguments. However, for the sake of completeness, we check whether the manifold in Theorem 10 may have positive measure around any local minimizer with non-singular Hessian (in particular around any minimizer of a Morse function). The eigenvalues of M p are,

σ p,+ = 1 -1 2 γ(α + βλ p ) + i 2 γ 4λ p -(α + βλ p ) 2 σ p,-= 1 -1 2 γ(α + βλ p ) -i 2 γ 4λ p -(α + βλ p ) 2 . Both eigenvalues have the same magnitude, |σ p,+ | 2 = |σ p,-| 2 = 1 - 1 2 γ(α + βλ p ) 2 + 1 4 γ 2 (4λ p -(α + βλ p ) 2 ) = 1 -γ(α + βλ p ) + γ 2 λ p , so, |σ p,+ | 2 < 1 ⇐⇒ -γ(α + βλ p ) + γ 2 λ p < 0 ⇐⇒ (γ -β)λ p < α ⇐⇒ γ < β + α λ p .
This is always true since,

γ < 1 2 (β + α L ∇J ) - (α + βL ∇J ) 2 -4L ∇J 2L ∇J ≤ 1 2 (β + α L ∇J ) ≤ β + α λ p .
We just proved that the eigenvalues of DG(θ , ψ ) have magnitude less than one if and only if (θ , ψ ) ∈ S \ S <0 .

We can now use the stable manifold theorem. Let (θ , ψ ) ∈ S <0 . Let an initialization (θ 0 , ψ 0 ) such that the associated realization (θ k , ψ k ) k∈N of INNA converges to (θ , ψ ). Consider the manifold W sc (θ , ψ ) and the neighborhood Ω as defined in Theorem 10. Since (θ k , ψ k ) k∈N converges, there exists k 0 ∈ N such that for all k ≥ k 0 , (θ k , ψ k ) ∈ Ω, so according to Theorem 10,

∀k ≥ k 0 , (θ k , ψ k ) ∈ Ω ∩ W sc (θ , ψ ). Rewriting this with the operator G, ∀k ≥ k 0 , G k (θ 0 , ψ 0 ) ∈ Ω ∩ W sc (θ , ψ ), and hence ∀k ≥ k 0 , G k (θ 0 , ψ 0 ) ∈ j∈N G -j (Ω ∩ W sc (θ , ψ )) , (24)
where G -j (Ω ∩ W sc (θ , ψ )) corresponds to all the initial conditions such that INNA has reached Ω ∩ W sc (θ , ψ ) after j iterations. Let

W(θ , ψ ) = (θ 0 , ψ 0 ) ∈ R P × R P G k (θ 0 , ψ 0 ) ----→ k→+∞ (θ , ψ ) ,
the set of all initial conditions such that INNA converges to (θ , ψ ). From ( 24), it holds that,

W(θ , ψ ) ⊂ j∈N G -j (Ω ∩ W sc (θ , ψ )) . (25)
Then, we showed that since (θ , ψ ) ∈ S <0 , then DG(θ , ψ ) has at least one eigenvalue with magnitude strictly larger than one, so according to the stable manifold theorem, the dimension of W sc (θ , ψ ) is strictly less than 2P , hence this manifold has zero measure. By assumption the step-size γ is chosen such that G is a local diffeomorphism (from Theorem 11), so ∀j ∈ N, G -j is also a local diffeomorphism, hence it maps zero-measure sets to zero-measure sets. As a result, the right-hand side in ( 25) is a countable union of zero-measure sets, so it has zero measure, as well as W(θ , ψ ). This proves the theorem since Assumption 1 guarantees that there is at most a countable number of critical points. So (θ ,ψ )∈S <0 W(θ , ψ ) is a countable union of zero-measure sets so it has zero measure.

B.3 Proof of Theorem 11

To prove Theorem 11, we introduce three technical lemmas.

Lemma 12. For any α > 0 and β > 0 such that αβ > 1, the function

x ∈ R >0 → β 2 + α 2x - (α + βx) 2 -4x 2x
is continuous and decreasing both on R >0 and R <0 .

Proof of Lemma 12. Let α > 0 and β > 0 such that αβ > 1. The function

x ∈ R >0 → β 2 + α 2x - √ (α+βx) 2 -4x 2x is clearly C ∞ (R >0
), and its first-order derivative is the function

x ∈ R >0 → - α √ (βx+α) 2 -4x+(2-αβ)x-α 2 2x 2 √ (βx+α) 2 -4x
. Since the denominator is always positive, we study the numerator of this derivative: define

h : x ∈ R >0 → -α (βx + α) 2 -4x -(2 -αβ)x + α 2 . We will prove that h is negative by differentiating it: for all x ∈ R >0 , ∂h ∂x (x) = - α(2β(βx + α) -4) 2 (βx + α) 2 -4x + αβ -2. ( 26
) ∂ 2 h ∂x 2 (x) = - 4α(αβ -1) ((βx + α) 2 -4x) 3 2 . ( 27
)
Since αβ > 1, for all x ∈ R >0 , ∂ 2 h ∂x 2 (x) < 0 and hence for all x ∈ R >0 , ∂h ∂x (x) < lim t→0 ∂h ∂x (t) = 0. So h is also decreasing on R >0 , and lim x→0 h(x) = 0, so for all x ∈ R >0 , h(x) ≤ 0 and the claim is thus proved on R >0 . The proof is very similar on R <0 except that h is increasing on R <0 but lim x→0 h(x) = 0, hence the result.

Lemma 13. For α > 0, β > 0 such that αβ ≤ 1, the function

x ∈ R <0 → β 2 + α 2x - (α + βx) 2 -4x 2x
is continuous and increasing on R <0 .

Proof of Lemma 13. The proof follows the exact same steps as those of the proof of Lemma 12, except that in (27), ∂ 2 h ∂x 2 is always positive on R <0 , and we use that to deduce that ∂h ∂x defined in ( 26) is negative on R <0 . So h is decreasing on R <0 and since h(0) = 0 we eventually obtain the result. Lemma 14. Let α > 0, β > 0 such that αβ ≤ 1, the function

x ∈ R >0 \ [ 2 -αβ β 2 - 2 √ 1 -αβ β 2 , 2 -αβ β 2 + 2 √ 1 -αβ β 2 ] → β 2 + α 2x - (α + βx) 2 -4x 2x is continuous and increasing for x ∈ 0, 2-αβ β 2 -2 √ 1-αβ β 2
and continuous and decreasing for

x ∈ 2-αβ β 2 + 2 √ 1-αβ β 2 , +∞ . Proof of Lemma 14. Let α > 0, β > 0 such that αβ ≤ 1. Denote by x -= 2-αβ β 2 -2 √ 1-αβ β 2 and x + = 2-αβ β 2 + 2 √ 1-αβ β 2 The function x ∈ R >0 \ (x -, x + ) → β 2 + α 2x - √ (α+βx) 2 -4x 2x is C ∞ on (0, x -)
and on (x + , +∞). Its first-order derivative is

x ∈ R >0 \ (x -, x + ) → - α √ (βx+α) 2 -4x+(2-αβ)x-α 2 2x 2 √ (βx+α) 2 -4x
.

The denominator is positive, so we focus on the numerator, define h :

x ∈ R >0 \ (x -, x + ) → -α (βx + α) 2 -4x -(2 -αβ)x + α 2 . For all x ∈ R >0 \ (x -, x +
), the first and second-order derivatives of h are given by ( 26) and ( 27) respectively. Since αβ < 1, ∂ 2 h ∂x 2 is always positive, so ∂h ∂x is increasing on both intervals. First, when x → 0 with 0 < x < x -, ∂h ∂x (x) → 0, so ∂h ∂x is positive on (0, x -) and h is increasing on (0, x -). Since h(0) = 0 and h is increasing, we proved the first part of the lemma. Then, when x → +∞, ∂h ∂x → -2, so ∂h ∂x is negative on (x + , +∞) and h is decreasing on (x + , +∞). Finally,

h(x + ) = -4(1-αβ) β 2 -2(2-αβ) √ 1-αβ β 2 ≤ 0.
We finally use these lemmas to prove the theorem.

Proof of Theorem 11. Let (θ, ψ) ∈ R P × R P . Since J is C 2 (R P ) then G is C 1 (R 2P ) and the Jacobian matrix DG(θ, ψ) can be transformed into a block diagonal matrix as in (21) where for any p ∈ {1, . . . , P }, M p is a 2 × 2 block of the diagonal and λ p is the associated eigenvalue of J (θ). To prove that G is a local diffeomorphism we prove that DG(θ, ψ) is invertible (i.e., that it has non-zero determinant) and then use the local inversion theorem. It holds that det(DG(θ, ψ)) = P p=1 det(M p ), and for each p ∈ {1, . . . , P },

det(M p ) = (1 -γ(α - 1 β ) -γβλ p )(1 - γ β ) - γ β γ(α - 1 β ) = 1 -γ(α + βλ p ) + γ 2 λ p . (28)
Let p ∈ {1, . . . , P }, we want to choose γ such that det(M p ) = 0 for any (θ, ψ) ∈ R P × R P , hence for any λ p ∈ [-L ∇J , L ∇J ] (since the eigenvalues are bounded by L ∇J from Assumption 2). First, if λ p = 0, from (28), we must take γ = 1/α. From now on, we assume λ p = 0, so (28) is a second-order polynomial in γ and its discriminant is ∆ γ = (α + βλ p ) 2 -4λ p . Notice that ∆ γ is a polynomial in λ p and is exactly the discriminant that we studied in Section 3.1; its sign is given by Lemma 5. When this discriminant is non-negative, there exists two real roots to (28),

   γ + = (α+βλp) 2λp + √ (α+βλp) 2 -4λp 2λp = β 2 + α 2λp + √ (α+βλp) 2 -4λp 2λp γ -= (α+βλp) 2λp - √ (α+βλp) 2 -4λp 2λp = β 2 + α 2λp - √ (α+βλp) 2 -4λp 2λp . ( 29
)
As before, we split the study with respect to the value of αβ.

• If αβ > 1, then ∆ γ ≥ 0 and the roots of det(M p ) are given by ( 29).

-First, when λ p < 0, (α + βλ p ) 2 -4λ p > |α + βλ p |, so γ + < 0 and any positive choice of γ will never be equal to γ + in this case. Then by Lemma 12, γ -is a decreasing function of λ p for λ p < 0 and when λ p → 0, γ -→ 1/α (using L'Hôpital's rule), this yields a first condition γ < 1/α.

-When λ p > 0, observe that γ + ≥ γ -> 0 so we focus the study on γ -. Lemma 12 exactly states that γ -is a decreasing function of λ p > 0. Since J has L ∇J -Lipschitz gradient, λ p ≤ L ∇J , so, for all λ p ∈ (0, L ∇J ], γ -≥ β 2 + α 2L ∇J -√ (α+βL ∇J ) 2 -4L ∇J 2L ∇J . Note in addition that when λ p → 0, γ -→ 1/α, this is a simple way to prove that

1/α > β 2 + α 2L ∇J - √ (α+βL ∇J ) 2 -4L ∇J 2L ∇J
when αβ > 1.

To summarize, we had three conditions, γ = 1/α, γ < 1/α and γ < β 2 + α 2L ∇J -√

(α+βL ∇J ) 2 -4L ∇J 2L ∇J
and we proved that the latter implies the first-two conditions. Remark that the condition γ < β holds but is not necessary in the case αβ > 1, it is present in the statement of the theorem to keep it as simple as possible.

• We now assume that αβ ≤ 1.

-If λ p < 0, then ∆ γ > 0 and the roots are given by (29). As above, , it holds that (α + βλ p ) 2 -4λ p > |α + βλ p |, so γ + < 0. Then Lemma 13 states that γ -is an increasing function of λ p < 0, and when λ p → -∞, γ -→ β. So we need γ < β.

-If λ p > 0, then whenever

λ p ∈ [ 2-αβ β 2 -2 √ 1-αβ β 2 , 2-αβ β 2 + 2 √ 1-αβ β 2
], there are no real roots so det(M p ) = 0 regardless the choice of γ > 0. If λ p does not belong to interval previously mentioned, the roots are given by (29). Remark that γ + > γ -> 0 so we focus on γ -. Using Lemma 14, γ -is increasing on (0, 2-αβ

β 2 -2 √ 1-αβ β 2
) and tends to 1/α when λ p → 0 (using L'Hôpital's rule). The same lemma also state that γ - is decreasing on ( 2-αβ

β 2 + 2 √ 1-αβ β 2
, +∞), so using the L ∇J -Lipschitz gradient of J , , 1 α , β and αβ ≤ 1 =⇒ β ≤ 1/α hence the result.

γ -≤ β 2 + α 2L ∇J - √ (α+βL ∇J ) 2 -
In every case we proved that the conditions mentioned in the theorem are sufficient to ensure that for all (θ, ψ) ∈ R P × R P , det(DG(θ, ψ)) = 0. So by the local inversion theorem, G is a local diffeomorphism from R P × R P to R P × R P .

C Proof of convergence of INNA

The proof of Theorem 8 relies on a Lyapunov argument stated in the following lemma.

Lemma 15. Assume that Assumption 2 holds and α > 0. Let (θ 0 , ψ 0 ) ∈ R P × R P , and let γ > 0 such that (18) holds. Let (θ k , ψ k ) k∈N be a sequence generated by INNA with this step-size and initialized at (θ 0 , ψ 0 ). Then the sequence (E k ) k∈N defined for all k ∈ N by

E k = (1 + αβ -γα)J (θ k ) + 1 2 (α - 1 β )θ k + 1 β ψ k 2 (30)
is decreasing, converges, and there exists C 1 > 0 and C 2 > 0 such that for all K ∈ N,

C 1 K k=0 θ k+1 -θ k 2 + C 2 K k=0 ∇J (θ k ) 2 ≤ E 0 -E K+1 < +∞. ( 31
)
Proof of Lemma 15. Consider INNA with the choice of step-size stated in the lemma, and let (θ k , ψ k ) k∈N be the iterates of INNA introduced in the lemma. We first introduce some notations: define a = α -1 β and b = 1 β . For all k ∈ N, denote also ∆θ k = θ k+1 -θ k and ∆ψ k = ψ k+1 -ψ k . With these notations, for all k ∈ N INNA can be rewritten as follows,

∆ψ k = -γaθ k -γbψ k ∆θ k = ∆ψ k -γβ∇J (θ k ) . ( 32
)
To simplify the notations denote also µ = 1 + αβ -γα, which is positive since γ < 1/α + β. Now, let k ∈ N, we aim to bound the difference E k+1 -E k by some non-positive quantity. First, using the L ∇J -Lipschitz continuity of ∇J , we have a so-called descent lemma (see e.g., Bertsekas et al. 1998, Proposition A.24):

µJ (θ k+1 ) -µJ (θ k ) ≤ µ ∇J (θ k ), ∆θ k + µL ∇J 2 ∆θ k 2 ,
which according to (32), can equivalently be rewritten as,

µJ (θ k+1 ) -µJ (θ k ) ≤ -µ ∆θ k -∆ψ k γβ , ∆θ k + µL ∇J 2 ∆θ k 2 . ( 33
)
We save this for later and now turn our attention to the other term in E k+1 -E k ,

1 2 aθ k+1 + bψ k+1 2 - 1 2 aθ k + bψ k 2 = 1 2 aθ k + a∆θ k + bψ k + b∆ψ k 2 - 1 2 aθ k + bψ k 2 .
We expand this and use the fact that aθ k + bψ k = -∆ψ k /γ,

1 2 aθ k + a∆θ k + bψ k + b∆ψ k 2 - 1 2 aθ k + bψ k 2 = 1 2 aθ k + bψ k 2 + 1 2 a∆θ k + b∆ψ k 2 + aθ k + bψ k , a∆θ k + b∆ψ k - 1 2 aθ k + bψ k 2 = 1 2 a∆θ k + b∆ψ k 2 - 1 γ ∆ψ k , a∆θ k + b∆ψ k = a 2 2 ∆θ k 2 + b 2 2 ∆ψ k 2 + ab ∆θ k , ∆ψ k - a γ ∆θ k , ∆ψ k - b γ ∆ψ k 2 .
(34)

Then, we rewrite (34) only as functions of ∆θ k and ∆θ k -∆ψ k as we did in (33). To do so, we use ∆ψ k 2 = ∆θ k -∆ψ k 2 + ∆θ k 2 -2 ∆θ k , ∆θ k -∆ψ k , and ∆θ k , ∆ψ k = ∆θ k 2 -∆θ k , ∆θ k -∆ψ k .

Figure 1 :

 1 Figure 1: Example of two functions whose Hessian matrices are singular at (0, 0). For the function(θ 1 , θ 2 ) ∈ R 2 → 1 2 θ 2 1 + 1 2 θ 2 2 + θ 1 θ 2 (on the left), the critical point (0, 0) is a minimum. For the function (θ 1 , θ 2 ) ∈ R 2 → θ 3 1 + θ 2 2(on the right), the critical point (0, 0) is neither a minimum nor a maximum.

Figure 3 :

 3 Figure 3: Evolution of the iterates of INNA on the landscape of the toy function J: (θ 1 , θ 2 ) ∈ R 2 → θ 4 1 -4θ 2 1 + θ 2 2. This function has two minimizers (-

Table 1 :

 1 Empirical validation of the results of Theorem 7

	Percentage of convergence	Average number of
	to each critical point	iterations to escape
	(-√	2, 0) ( √	2, 0) (0, 0)	a saddle point

The theorem can be extended to some non-autonomous ODEs[START_REF] Palmer | A generalization of Hartman's linearization theorem[END_REF], which we do not consider for the sake of simplicity.

This is ensured by the boundaries enforced on γ as shown in the proof of Theorem 11 in Section B.3.

The proof is similar to the one of Lemma 14 proved in Section B.3.

Acknoledgments

The author acknowledges the support of the European Research Council (ERC FACTORY-CoG-6681839) and the Air Force Office of Scientific Research (FA9550-18-1-0226). The author deeply thanks Jérôme Bolte, Cédric Févotte, and Edouard Pauwels for their valuable comments and suggestions which helped in the process of writing this article. The numerical experiments were made thanks to the development teams of the following libraries: Python (Rossum, 1995), Numpy (Walt et al., 2011) and Matplotlib (Hunter, 2007).

A Permutation matrices

In this section, we specify the permutations matrices necessary to obtain the block diagonalization in ( 7) and ( 21). Denote by mod the modulo operator and let P ∈ N >0 . We can choose the permutation matrix U ∈ R 2P ×2P as the matrix whose coefficients are all zero except the Using these in (34) we obtain,

We then simplify the factors using the identity a+b = α, as well as

We can finally combine (33) and ( 35),

Then, µ = 1 + αβ -γα is specifically chosen so that the last term in (36) vanishes, so,

To prove the decrease of (E k ) k∈N , it remains to justify that both factors in (37) are negative. First, the condition γ < 2β in ( 18) is equivalent to

A simpler sufficient condition for this to hold is (

, and the latter holds true according to (18). So the sequence (E k ) k∈N is a decreasing. It is also lower-bounded since J is lower-bounded, so it converges.

It remains to prove the second part of the lemma. Let K ∈ N, we sum (37) from 0 to K.

The left-hand side is a telescopic series. As for the right-hand side, from (32) it holds that for all k ∈ N, ∆θ k -∆ψ k = -γβ∇J (θ k ). So,

And the right-hand side is finite since (E k ) k∈N converges.

We also need the following lemma.

Lemma 16 (Lange (2013, Proposition 12.4.1)). If a bounded sequence (u k ) k∈N in R P satisfies,

then the set of accumulation points of (u k ) k∈N is connected. If this set is finite then it reduces to a singleton and (u k ) k∈N converges.

We can now prove Theorem 8.

Proof of Theorem 8. Assume that α > 0. Let (θ 0 , ψ 0 ) ∈ R P ×R P , and consider INNA with stepsize γ > 0 such that (18) holds. Denote (θ k , ψ k ) k∈N the iterations of INNA initialized at (θ 0 , ψ 0 ). By direct application of Lemma 15, and in particular due to (31), K k=0 ∇J (θ k ) 2 < +∞ so lim k→+∞ ∇J (θ k ) 2 = 0 and similarly, lim k→+∞ θ k+1 -θ k 2 = 0. From ( 16), we also have,

From Lemma 15, the sequence (E k ) k∈N defined in (30) converges. Let k ∈ N, since

and we just proved in (38) that the second term in E k converges, this implies that (J (θ k )) k∈N converges as well.

So far we proved the first part of the theorem. In particular since lim k→+∞ ∇J (θ k ) 2 = 0 and ∇J is continuous, any accumulation point (i.e., the limit of any sub-sequence of iterates) is critical. We now assume that the critical points are isolated (Assumption 1) and that the sequence (θ k ) k∈N is uniformly bounded on R P .

According to Lemma 16, since (θ k ) k∈N is bounded and lim k→+∞ θ k+1 -θ k = 0, the set of accumulation points of (θ k ) k∈N is connected. Yet, accumulation points are critical points, which are assumed to be isolated. So the set of accumulation points of (θ k ) k∈N reduces to a singleton and using again Lemma 16, (θ k ) k∈N converges to a critical point.