Florentin Goyens
email: goyensflorentin@gmail.com

Clément W Royer
email: clement.royer@lamsade.dauphine.fr.

Riemannian trust-region methods for strict saddle functions with complexity guarantees

Keywords: Riemannian optimization, strict saddle function, second-order method, complexity guarantees. MSC: 49M05, 49M15, 65K05, 90C60

The difficulty of minimizing a nonconvex function is in part explained by the presence of saddle points. This slows down optimization algorithms and impacts worst-case complexity guarantees. However, many nonconvex problems of interest possess a favorable structure for optimization, in the sense that saddle points can be escaped efficiently by appropriate algorithms. This strict saddle property has been extensively used in data science to derive good properties for first-order algorithms, such as convergence to second-order critical points. However, the analysis and the design of second-order algorithms in the strict saddle setting have received significantly less attention.

In this paper, we consider second-order trust-region methods for a class of strict saddle functions defined on Riemannian manifolds. These functions exhibit (geodesic) strong convexity around minimizers and negative curvature at saddle points. We show that the standard trust-region method with exact subproblem minimization finds an approximate local minimizer in a number of iterations that depends logarithmically on the accuracy parameter, which significantly improves known results for general nonconvex optimization. We also propose an inexact variant of the algorithm that explicitly leverages the strict saddle property to compute the most appropriate step at every iteration. Our bounds for the inexact variant also improve over the general nonconvex case, and illustrate the benefit of using strict saddle properties within optimization algorithms.

Introduction

We consider the optimization problem

min x∈M f (x) (P)
where M is an n-dimensional Riemannian manifold, and f : M → R is twice continuously differentiable and nonconvex. A popular way to solve Problem (P) is to use Riemannian optimization techniques, that use differential geometry to generalize unconstrained optimization methods to the Riemannian setting [START_REF] Absil | Optimization Algorithms on Matrix Manifolds[END_REF][START_REF] Boumal | An Introduction to Optimization on Smooth Manifolds[END_REF]. Theoretical guarantees for such methods have historically focused on the behavior close to minimizers (local convergence). These results usually rely on the objective function being convex (or strongly convex) around minimizers, thereby enabling the derivation of local convergence rates [START_REF] Absil | Optimization Algorithms on Matrix Manifolds[END_REF][START_REF] Nocedal | Numerical Optimization[END_REF]. Meanwhile, the past decade has seen a growing interest in global convergence results for nonconvex optimization, where one quantifies the rate of convergence towards a stationary point independently of the starting point [START_REF] Cartis | Evaluation complexity of algorithms for nonconvex optimization[END_REF]. These rates can be stated in the form of complexity results, which bound the number of iterations necessary to satisfy approximate first-or second-order necessary conditions for optimality. Second-order stationary points for Problem (P) have a zero Riemannian gradient and positive semidefinite Riemannian Hessian: gradf (x) = 0 and λ min (Hessf (x)) ≥ 0, (1.1)

where λ min (•) is the smallest eigenvalue of a symmetric operator. Given positive tolerances (ε g , ε H ), complexity results bound the cost of satisfying an approximate version of (1.1), given by gradf (x) ≤ ε g and λ min (Hessf (x)) ≥ -ε H .

(1.2)

In the unconstrained or Euclidean setting (i.e., when M = R n ), it is well established that classical second-order trust-region methods [START_REF] Conn | Trust Region Methods[END_REF] reach an iterate satisfying (1.2) in at most O(max(ε -2 g ε -1 H , ε -3 H )) iterations [START_REF] Cartis | Complexity bounds for second-order optimality in unconstrained optimization[END_REF]. Although this complexity can be improved to O(max(ε -2 g , ε -3 H )) without changing the essence of the algorithm [START_REF] Curtis | Concise complexity analyses for trust region methods[END_REF][START_REF] Curran Associates | A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds[END_REF], the resulting bound remains suboptimal among a large class of second-order methods [START_REF] Cartis | Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization[END_REF]. Indeed, techniques such as cubic regularization enjoy a O(max(ε -3/2 g , ε -3 H )) complexity bound, that strictly improves over standard trust-region methods and is optimal among the class of second-order algorithms. Similar bounds were obtained for the Riemannian counterparts of trust-region methods [START_REF] Boumal | Global rates of convergence for nonconvex optimization on manifolds[END_REF] and cubic regularization [START_REF] Agarwal | Adaptive regularization with cubics on manifolds[END_REF]. Modifications of the trust-region scheme have been proposed to achieve the optimal complexity of cubic regularization [START_REF] Curtis | A trust region algorithm with a worst-case iteration complexity of O( -3/2 ) for nonconvex optimization[END_REF](Curtis et al., , 2021)).

These worst-case results are pessimistic in nature and do not reflect the good behaviour of second-order methods on many practical problems. In an effort to reconcile theoretical guarantees with practical performances, it becomes necessary to leverage additional structure from the function f . Numerous problems of the form (P) have the property that the nonconvexity is benign, meaning that second-order critical points-Equation (1.1)-are global minimizers [START_REF] Sun | When are nonconvex problems not scary?[END_REF][START_REF] Wright | High-Dimensional Data Analysis with Low-Dimensional Models: Principles, Computation, and Applications[END_REF]. Data analysis tasks with this property include Burer-Monteiro factorizations of semidefinite programs [START_REF] Boumal | Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs[END_REF][START_REF] Luo | Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective[END_REF], phase retrieval [START_REF] Sun | A geometric analysis of phase retrieval[END_REF], matrix completion and factorization [START_REF] Ge | Matrix Completion has No Spurious Local Minimum[END_REF][START_REF] Li | The non-convex geometry of low-rank matrix optimization[END_REF], dictionary learning (Sun et al., 2017a;[START_REF] Qu | Analysis of the optimization landscapes for overcomplete representation learning[END_REF] and others.

Benign nonconvexity implies that the Hessian possesses a negative eigenvalue at every saddle point. This strict saddle property allows first-and second-order methods to provably avoid saddle points and converge towards minimizers. First-order methods escape strict saddle points almost surely [START_REF] Lee | First-order methods almost always avoid strict saddle points[END_REF], and complexity bounds can even be derived for randomized first-order techniques, in both the Euclidean and Riemannian setting [START_REF] Criscitiello | Efficiently escaping saddle points on manifolds[END_REF][START_REF] Sun | Escaping from saddle points on Riemannian manifolds[END_REF]. In addition, second-order methods, that leverage directions of negative curvature of the Hessian, escape strict saddle points by design, and are thus particularly suitable for strict saddle problems (Wright and Ma, 2022, Chapter 9).

Adaptations of complexity analysis to strict saddle problems have recently begun to appear in the literature. On one hand, complexity results were established for specific instances satisfying a strict saddle property, such as phase retrieval [START_REF] Sun | A geometric analysis of phase retrieval[END_REF] or dictionary learning [START_REF] Sun | Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method[END_REF]. More recently, O'Neill and [START_REF] O'neill | A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees[END_REF] considered low-rank matrix optimization problems under a strict saddle property, and designed a line-search method that made explicit use of the strict saddle structure. In these works, the analysis is tailored to specific problems, and its generalization to a broader strict saddle setting is not straightforward.

On the other hand, general analyses based on dividing the feasible set into regions of interest yielded complexity bounds that improved over the general nonconvex setting, in the sense that the dependencies with respect to ε g and ε H were only logarithmic rather than polynomial [START_REF] Paternain | A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points[END_REF]Curtis and Robinson, 2021). [START_REF] Carmon | Accelerated Methods for Non-Convex Optimization[END_REF] showed that an accelerated gradient technique tailored to nonconvex problems would enjoy improved complexity when applied to a function satisfying the strict saddle property. These general results apply to unconstrained strict saddle problems, and do not cover optimization problems on manifolds, a popular source of strict saddle problems [START_REF] Wright | High-Dimensional Data Analysis with Low-Dimensional Models: Principles, Computation, and Applications[END_REF].

Contributions and outline

In this work, we analyze a trust-region framework for minimizing strict saddle functions over Riemannian manifolds. The strict saddle problems we consider are strongly convex near minimizers, which leads to connections with Riemannian optimization of geodesically strongly convex functions. In particular, we leverage local convergence results for Newton's method in order to derive complexity results for our framework. We show that the standard trust-region method [START_REF] Absil | Trust-Region Methods on Riemannian Manifolds[END_REF] with exact subproblem minimization applied to a strict saddle function benefits from improved complexity guarantees compared to the general nonconvex setting. Indeed, our complexity bound possesses a logarithmic dependency in the optimality tolerances, thanks to the local quadratic convergence of the method, which improves over polynomial dependencies from the general case. We also derive similar results for an inexact version of our algorithm based on inexact solutions of the trust-region subproblem, that makes explicit use of the strict saddle structure. Our analysis builds on recent advances in the complexity of (Euclidean) trustregion methods by relying on iterative linear algebra routines. This yields complexity bounds in terms of iterations as well as Hessian-vector products.

To the best of our knowledge, we provide the first strict saddle analysis of a generic secondorder trust-region method, and the first strict saddle analysis that applies to a generic manifold M. All our results apply naturally to the unconstrained case M = R n . Overall, our results advocate for further use of the strict saddle structure in the design and analysis of nonconvex optimization methods.

The rest of the paper is organized as follows. In Section 2, we describe the class of strict saddle functions on Riemannian manifolds that we investigate throughout the paper. This is prefaced by background material on Riemannian optimization and geodesic convexity. In Section 3, we analyze the global complexity of the Riemannian trust-region with exact subproblem minimization. This is a well-known algorithm for which we show an improved complexity when applied to strict saddle functions. In Section 4, we design a new Riemannian trust-region method with inexact subproblem minimization that uses landscape parameters to compute directions which are appropriate for the local landscape. The guarantees for the inexact algorithm account for the cost of solving the subproblem.

Strict saddle functions on Riemannian manifolds

In this section, we define a class of strict saddle functions on Riemannian manifolds. We first present background material on Riemannian optimization in Section 2.1, with a focus on retractions. We then discuss the notion of geodesic strong convexity in Section 2.2, which plays a role in our definition of strict saddle functions. This definition is provided along with several examples in Section 2.3.

Retractions and derivatives on Riemannian manifolds

Recall that problem (P) considers the minimization of a smooth function f over a Riemannian manifold M. We cover the basic ideas that allow to build feasible algorithms for (P).

At every x ∈ M, the linear approximation of the manifold M is called the tangent space, written T x M. Each tangent space is equipped with an inner product •, • x , which defines the norm of a tangent vector as v x := v, v x for v ∈ T x M. (We often write •, • and • when the reference point is clear from context.) For smooth functions, the metric defines a Riemannian gradient and Riemannian Hessian of f at x ∈ M, which we denote by gradf (x) ∈ T x M and Hessf (x) : T x M → T x M, respectively. By contrast, we use the symbols ∇ and ∇ 2 for the gradient and Hessian of a function defined over a Euclidean space.

Riemannian optimization algorithms use tangent vectors to generate search directions. Following a tangent direction in a straight line may lead outside the manifold, which is undesirable. Therefore, we need a tool to travel on the manifold in a direction prescribed by a tangent vector. This can be done by following the geodesic associated with a tangent vector. On manifolds, geodesics are curves with zero acceleration that generalize the notion of straight line in Euclidean spaces. Formally, a geodesic is a smooth curve c : I → M defined on an open interval I ⊂ R such that c (t) = 0 for all t ∈ I, where c (t) is the intrinsic acceleration of c (Boumal, 2023, Chapter 5). The exponential map travels along the manifold by following geodesics, but optimization algorithms commonly use first-order approximations of the exponential map, called retractions (Absil et al., 2008, §4.1). A retraction at x is a map from the tangent space to the manifold, denoted by R x : T x M → M. For many manifolds of interest, practical and popular retractions are defined globally (Absil et al., 2008, Chapter 4). However, the retraction at x ∈ M may only be defined locally, in a ball of radius (x) > 0 centered around 0 x in T x M. In that case the size of the step at x ∈ M must be limited to (x). We discuss this further in Section 3.1.

Given a retraction, one can lift the function f to the tangent space through the following composition.

Definition 2.1. For any x ∈ M, the pullback of f to the tangent space T x M is the function

fx : T x M → R defined by fx (s) := f • R x (s) for all s ∈ T x M.
In particular, given x ∈ M and s ∈ T x M, we consider the gradient of the pullback function ∇ fx (s) ∈ T x M as well as its Hessian ∇ 2 fx (s) : T x M → T x M. Note the distinction between these derivatives and the Riemannian derivatives of f at R x (s), denoted by gradf (R x (s)) and Hessf (R x (s)). The identities fx (0) = f (x) and ∇ fx (0) = gradf (x) hold by definition (Boumal, 2023, Proposition 3.59) and additional assumptions on the retraction allow to relate the secondorder derivatives. To benefit fully from second-order methods, we require that the retraction be a second-order approximation of geodesics.

A1. The retraction mapping is a second-order retraction: for any x ∈ M and s ∈ T x M, the curve c : t ∈ [0, 1] → R x (ts) has zero acceleration at t = 0, that is, c (0) = 0.

If R x is a second-order retraction, it holds that

∇ 2 fx (0) = Hessf (x) ∀x ∈ M, (2.1)
i.e., the Hessian of the pullback function is the Riemannian Hessian of f (Boumal, 2023, Proposition 5.45).

Remark 2.1. In this paper, we choose to use a general retraction over the more restrictive exponential map. This requires certain smoothness assumptions on the pullback function (see A3), but has the advantage of resembling the Euclidean setting. Using the exponential map typically leads to a different analysis that relies on parallel transport along geodesics, where the curvature of the manifold appears explicitly [START_REF] Sun | Escaping from saddle points on Riemannian manifolds[END_REF][START_REF] Criscitiello | Efficiently escaping saddle points on manifolds[END_REF], Section 4).

Geodesic convexity

We now provide the key definitions behind geodesic convexity, a concept that generalizes convexity in Euclidean spaces to Riemannian manifolds. Geodesically convex sets and functions are defined with respect to geodesics of M as follows.

Definition 2.2. A subset S of M is geodesically convex if, for every x, y ∈ S, there exists a geodesic segment c :

[0, 1] → M such that c(0) = x, c(1) = y and c(t) is in S for all t ∈ [0, 1].
A function is geodesically convex on S ⊂ M if it is convex in the usual sense along all geodesics on S.

Definition 2.3. Given a subset S of M, the function f : M → R is geodesically convex on S (resp. geodesically strongly convex) if S is geodesically convex and for every geodesic c :

[0, 1] → M such that c(0) = c(1) and c([0, 1]) ⊂ S, the function f •c : [0, 1] → R is convex (resp. strongly convex).
For smooth functions, geodesic strong convexity is determined by the eigenvalues of the Riemannian Hessian.

Proposition 2.1 (Theorem 11.23 in [START_REF] Boumal | An Introduction to Optimization on Smooth Manifolds[END_REF]). A function f : M → R is geodesically γ-strongly convex on the set S ⊂ M if S is a geodesically convex set and λ min (Hessf (x)) ≥ γ for every x ∈ S.

Since we are interested in nonconvex problems, we consider functions that are geodesically strongly convex over a subset of the manifold (near minimizers). Functions with geodesic convexity over the entire manifold have also been studied, with most interesting applications arising on Hadamard manifolds [START_REF] Zhang | First-order Methods for Geodesically Convex Optimization[END_REF].

Strict saddle property

We are now ready to define our problem class of interest, robust strict saddle functions on M. The definition is based on [START_REF] Ge | Escaping from saddle points -online stochastic gradient for tensor decomposition[END_REF][START_REF] Sun | When are nonconvex problems not scary?[END_REF].

Definition 2.4. Let f : M → R be twice differentiable and let α, β, γ, δ be positive constants.

The function f is (α, β, γ, δ)-strict saddle if the manifold M satisfies M = R 1 ∪ R 2 ∪ R 3 , where R 1 = {x ∈ M : gradf (x) ≥ α} R 2 = {x ∈ M : λ min (Hessf (x)) ≤ -β} R 3 = {x ∈ M : there exists x * ∈ M, a local minimizer of f such that dist(x, x * ) ≤ δ and
f is geodesically γ-strongly convex over the set {y ∈ M : dist(x * , y) < 2δ}} .

Definition 2.4 has the following interpretation. If f is a strict saddle function on M, then, at any x ∈ M, either the norm of the Riemannian gradient is sufficiently large, the Riemannian Hessian has a sufficiently negative eigenvalue, or x is close to a local minimum of f on M and f is geodesically strongly convex in the neighborhood of this local minimum. Note that the last two cases are mutually exclusive, but that the first case may occur simultaneously with one of the other two.

Remark 2.2. Other definitions of strict saddle functions exist in the literature, and the main differences appear in the definition of the region R 3 , where strong convexity is not always required [START_REF] Liu | A Newton-MR algorithm with complexity guarantees for nonconvex smooth unconstrained optimization[END_REF][START_REF] O'neill | A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees[END_REF]. Our definition excludes non-isolated minimizers, where strong convexity cannot hold. Nevertheless, non-isolated minimizers can arise due to rotational symmetries in the problem [START_REF] Wright | High-Dimensional Data Analysis with Low-Dimensional Models: Principles, Computation, and Applications[END_REF]. We note that recent work has focused on reformulating such problems on a quotient set induced by the symmetry, leading to problems where minimizers are isolated [START_REF] Luo | Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective[END_REF].

We conclude this section with two simple examples of strict saddle functions in the sense of Definition 2.4. Our first example is a strongly convex function over R n .

Example 2.1. Let f : R n → R be a (geodesically) γ-strongly convex function with global minimizer x * . For any α > 0, f is (α, 1, γ, 2α γ )-strict saddle. The region R 2 is empty, and for any x / ∈ R 1 (i.e., ∇f (x) < α), we show that x ∈ R 3 . Strong convexity gives

γ 2 x -x * 2 ≤ f (x) -f (x * ) ≤ -∇f (x) T (x -x * ) ≤ ∇f (x) x -x * ≤ α x -x * , hence x -x * ≤ 2α γ =: δ. Clearly, f is γ-strongly convex on {x : x -x * < 2δ} ⊂ R n .
Our second example, previously introduced in [START_REF] Sun | When are nonconvex problems not scary?[END_REF], illustrates the interest of the region R 2 in the presence of nonconvexity.

Example 2.2. Let M be the unit sphere in R n , denoted by S n-1 , and let f :

S n-1 → R be defined by f (x) = x T Ax, where A ∈ R n×n is a symmetric matrix with eigenvalues λ 1 > λ 2 ≥ • • • ≥ λ n-1 > λ n . Then, there exists an absolute constant c > 0 such that f is (c(λ n-1 -λ n )/λ 1 , c(λ n-1 -λ n ), c(λ n-1 -λ n ), 2c(λ n-1 -λ n )/λ 1 )-strict saddle on S n-1 .
To end this section, we state our key assumption about Problem (P).

A2. There exist positive constants (α, β, γ, δ) such that the function f is (α, β, γ, δ)-strict saddle on the manifold M and R 3 is a compact subset of M.

The compactness assumption on R 3 merely prevents the function from having infinitely many minimizers on M, and is made to simplify the presentation. It is possible to extend our analysis to an unbounded region R 3 , but this lengthens the argument considerably. Note that Assumption 2 holds for both examples above. The boundedness assumption also allows to control the distance between iterates of our algorithms.

Lemma 2.2 (Lemma 6.32 in [START_REF] Boumal | An Introduction to Optimization on Smooth Manifolds[END_REF]). Under A2, there exists positive constants ν S , κ S such that for all x ∈ R 3 and s

∈ T x M, if s x ≤ ν S , then dist(x, R x (s)) ≤ κ S s x , where dist(•, •) is the Riemannian distance on M.
3 Riemannian trust-region method with exact subproblem minimization

In this section we analyze the classical Riemannian trust-region algorithm (RTR) with exact subproblem minimization. Our goal is to leverage the strict saddle property to obtain better complexity bounds than those existing for general nonconvex functions [START_REF] Boumal | Global rates of convergence for nonconvex optimization on manifolds[END_REF].

The algorithm is perfectly standard, yet the analysis borrows from recent results on Newtontype methods for the Euclidean setting (Curtis et al., 2021). In particular, our improved complexity bounds rely on a good understanding of the local convergence of the algorithm. Note that using the exponential map would simplify the analysis, as noticed for Riemannian cubic regularization [START_REF] Agarwal | Adaptive regularization with cubics on manifolds[END_REF].

Section 3.1 describes the exact trust-region algorithm, along with key assumptions. Standard decrease lemmas are provided in Section 3.2. A local convergence analysis of the algorithm in the region of geodesic strong convexity is provided in Section 3.3. This analysis allows to derive our global convergence result, that is established in Section 3.4.

Algorithm and assumptions

The Riemannian trust-region method with exact subproblem minimization is described in Algorithm 1. At every iteration, a step s k is computed by minimizing a quadratic model of (the pullback of) the function over the tangent space corresponding to the current iterate x k . In this section, we assume that the subproblem (3.1) is solved exactly using standard approaches [START_REF] Moré | Computing a trust region step[END_REF][START_REF] Absil | Trust-Region Methods on Riemannian Manifolds[END_REF] (the inexact case is addressed in Section 4). The algorithm computes the step s k , then evaluates f at the point R x k (s k ) ∈ M to measure the change in function value. If the function decrease is at least a fraction of the model decrease, the iteration is successful, and the candidate point R x k (s k ) becomes the new iterate. The trust-region radius is either unchanged (successful iteration) or can be increased (very successful iteration). If the iteration is unsuccessful, the algorithm remains at the current iterate and the trust-region radius is decreased.

Algorithm 1 RTR with exact subproblem minimization

1: Inputs: Initial point x 0 ∈ M, initial and maximal trust-region radii 0 < ∆ 0 < ∆, constants 0 < η 1 < η 2 < 1 and 0 < τ 1 < 1 < τ 2 . 2: for k = 1, 2, . . . do 3:
Compute s k as a solution to the trust-region subproblem

s k ∈ arg min s∈Tx k M m k (s) subject to s ≤ ∆ k , (3.1)
where m k is the model defined by (3.2).

4:

5:

Compute

ρ k = f (x k ) -f (R x k (s k )) m k (0) -m k (s k ) and set x k+1 = R k (x k ) if ρ k ≥ η 1
x k otherwise.

6:

7:

Set ∆ k+1 =      min τ 2 ∆ k , ∆ if ρ k > η 2 [very successful] ∆ k if η 2 ≥ ρ k ≥ η 1 [successful] τ 1 ∆ k otherwise. [unsuccessful] 8: end for
The model is a second-order Taylor expansion of the pullback function fx k , namely

m k : T x M → R : s → m k (s) = f (x k ) + s, g k + 1 2 s, H k s , (3.2)
where

g k = ∇ fx k (0) = gradf (x k ) and H k = ∇ 2 fx k (0)
, which gives a second-order accurate model. Although we do not consider it here, we belive that our analysis can be extended to approximate second-order accurate models, under the condition that H k is a suitable approximation of ∇ 2 fk (0) (Absil et al., 2008, Eq. (7.36)). When the retraction is second-order (A1),

we have H k = Hessf (x k ) by (2.1).

In order to derive complexity results for Algorithm 1, we make a standard Lipschitz-type assumption on the Hessian of the pullback [START_REF] Boumal | Global rates of convergence for nonconvex optimization on manifolds[END_REF]. Recall that if the retraction at x k is defined locally, we write (x k ) > 0 for the radius of the ball centered around 0 x k in T x k M in which it is defined.

A3. There exists L H > 0 such that for all iterates x k generated by Algorithm 1, the pullback

fk = f • R x k satisfies f (R x k (s)) ≤ f (x k ) + s, gradf (x k ) + 1 2 s, ∇ 2 fk (0)[s] + L H 6 s 3 . (3.3) for all s ∈ T x k M such that s ≤ (x k ).
We further assume ∆ k ≤ (x k ), so that the property (3.3) holds in the entire trust region produced by Algorithm 1.

A simple strategy to ensure (x k ) ≥ ∆ k in the assumption above is to set ∆ below inf x∈M : f (x)≤f (x 0 ) (x), which is positive if the injectivity radius of the manifold is positive (Boumal et al., 2019, Remark 2.2). Throughout we work implicitly under the assumption that this is satisfied. We additionally make the following assumption on the Hessian operators considered throughout the algorithm.

A4. There exists κ H > 0 such that for all iterates x k generated by Algorithm 1, we have

H k := sup s∈Tx k M s ≤1 | s, H k (s) | ≤ κ H . (3.4)

Preliminary lemmas

In this section, using standard arguments from the theory of trust-region methods, we bound the model decrease in the regions R 1 , R 2 , R 3 defined by the strict saddle property . We also provide a lower bound on the trust-region radius.

Our first result handles the case of an iterate with large gradient norm (i.e., in R 1 ).

Lemma 3.1. Under A2 and A4, consider the kth iterate of Algorithm 1 and suppose that

x k ∈ R 1 . Then, m k (0) -m k (s k ) ≥ 1 2 min ∆ k , α κ H α. (3.5)
Proof. Define s C k as the Cauchy point associated with the trust-region subproblem (3.1), i.e.

s C k = -tg k with t = arg min t≥0, t g k ≤∆ k m k (-t g k ).
A straightforward application of Boumal (2023, Lemma 6.15) gives

m k (0) -m k (s C k ) ≥ 1 2 min (∆ k , g k /κ H ) g k ≥ 1 2 min (∆ k , α/κ H ) α.
The desired result follows from the optimality of

s k , since m k (s k ) ≤ m k (s C k ).
Our second result considers an iterate at which the Hessian possesses significant negative curvature (i.e., in R 2 ). Lemma 3.2. Under A1 and A2, consider the kth iterate of Algorithm 1 and suppose that

x k ∈ R 2 . Then, m k (0) -m k (s k ) ≥ 1 2 β∆ 2 k . (3.6) Proof. Define s E k = ∆ k u k , where u k ∈ T x k M satisfies u k x k = 1, g k , u k x k ≤ 0 and u k , H k u k x k ≤ -β.
The vector s E k -called an eigenstep-exists because x k ∈ R 2 . By Boumal (2023, Lemma 6.16), it satisfies

m k (0) -m k (s E k ) ≥ 1 2 β∆ 2 k .
The desired result follows from the optimality of s k , as

m k (s k ) ≤ m k (s E k ).
Our last decrease lemma is based on the strong convexity constant, and proceeds similarly to the previous two results.

Lemma 3.3. Under A1 and A2, consider the kth iterate of Algorithm 1 and suppose that x k ∈ R 3 . Then, the step s k is uniquely defined, and satisfies

m k (0) -m k (s k ) ≥ 1 2 γ s k 2 . (3.7) Proof.
Since s k is a solution of the trust-region subproblem (3.1), there exists λ k ≥ 0 such that the following optimality conditions hold (Absil et al., 2008, Proposition 7.3.1):

(H k + λ k Id) s k = -g k (3.8) s, (H k + λ k Id) [s] ≥ 0 ∀s ∈ T x k M (3.9) s k ≤ ∆ k (3.10) λ k (∆ k -s k ) = 0. (3.11)
Moreover, if the inequality in (3.9) is strict for nonzero s, then the solution is unique. To establish a decrease guarantee for s k , we combine (3.8) and λ k ≥ 0 to obtain

m k (0) -m k (s k ) = -s k , g k - 1 2 s k , H k s k = s k , (H k + λ k Id)s k - 1 2 s k , H k s k = 1 2 s k , H k s k + λ k s k 2 ≥ 1 2 s k , H k s k ≥ 1 2 γ s k 2 .
The last line follows from H k = Hessf (x k ) and x k ∈ R 3 , i.e., s, H k s ≥ γ s 2 for any s ∈ T x k M. This also implies that H k + λ k Id is positive definite, hence s k is uniquely defined.

The three lemmas above, together with the Lipschitz-type assumptions on the pullback, yield a lower bound on the trust-region radius.

Lemma 3.4. Let A1, A2, A3 and A4 hold. Then, for any iteration of index k, the trust-region radius ∆ k in Algorithm 1 satisfies

∆ k ≥ ∆ min := c ∆ min ∆ 0 , α 1/2 , α 2/3 , β, γ ,
(3.12)

where c ∆ = min 1, τ 1 3(1 -η 1 ) L H , τ 1 3 3(1 -η 1 ) κ H L H , 3τ 1 (1 -η 1 ) L H .
Proof. We begin by showing that if the trust-region radius drops below a certain threshold, then the iteration must be successful. We consider the quantity

1 -ρ k = 1 - f (x k ) -f (R x k (s k )) m k (0) -m k (s k ) = f (R x k (s k )) -m k (s k ) m k (0) -m k (s k ) (3.13)
for the three regions defined by the strict saddle property. First note that for any x k ∈ M, a second-order retraction (A1) and Lipschitz continuity of the Hessian (A3) give the following bound on the numerator of (3.13):

f (R x k (s k )) -m k (s k ) = f (R x k (s k )) -f (x k ) -g k , s k - 1 2 s k , H k s k ≤ L H 6 s k 3 ≤ L H 6 ∆ 3 k . (3.14)
For x k ∈ R 1 , the denominator of (3.13) satisfies (3.5). It follows that

1 -ρ k ≤ L H ∆ 3 k 3 min (∆ k α, α 2 /κ H ) ≤ L H 3 max ∆ 2 k α , κ H ∆ 3 k α 2 .
As a result, if

x k ∈ R 1 and ∆ k ≤ min   3(1 -η 1 ) L H α 1/2 , 3 3(1 -η 1 ) κ H L H α 2/3   , then 1 -ρ k ≤ 1 -η 1 and iteration k is successful. If x k ∈ R 2
, the denominator of (3.13) satisfies (3.6), which we combine with (3.14) to give

1 -ρ k ≤ L H ∆ 3 k 3β∆ 2 k = L H 3β ∆ k . Thus, if x k ∈ R 2 and ∆ k ≤ 3(1 -η 1 )β/L H , we have ρ k ≥ η 1 and iteration k is successful.
Finally, for x k ∈ R 3 , the upper bound (3.14) together with the model decrease (3.7) gives

1 -ρ k ≤ L H s k 3 3γ s k 2 ≤ L H 3γ ∆ k . As a result, if x k ∈ R 3 and ∆ k ≤ 3(1 -η 1 )γ/L H , then ρ k ≥ η 1 and iteration k is successful.
Overall, we have shown that the iteration k is successful as long as

∆ k ≤ min   3(1 -η 1 ) L H α 1/2 , 3 3(1 -η 1 ) κ H L H α 2/3 , 3(1 -η 1 ) L H β, 3(1 -η 1 ) L H γ   , in which case ∆ k+1 ≥ ∆ k .
It follows from the updating rule on ∆ k that the trust-region radius is lower bounded for any k ≥ 0:

∆ k ≥ min   ∆ 0 , τ 1 3(1 -η 1 ) L H α 1/2 , τ 1 3 3(1 -η 1 ) κ H L H α 2/3 , τ 1 3(1 -η 1 ) L H β, τ 1 3(1 -η 1 ) L H γ   ≥ c ∆ min ∆ 0 , α 1/2 , α 2/3 , β, γ .
For x k ∈ R 1 ∪R 2 , it is straightforward to combine Lemma 3.4 with the results of Lemmas 3.1 and 3.2 to guarantee a model decrease that is independent of k. For x k ∈ R 3 , deriving a uniform lower bound on the decrease based on Lemma 3.3 is more involved, and is the topic of the next section.

Region of geodesic strong convexity and local convergence

In this section, we analyze the behavior of Algorithm 1 in the region of strong convexity R 3 . The global subproblem minimizer is a regularized Newton step-Equation (3.8)-and thus our approach mimics the study of Newton's method applied to strongly convex functions [START_REF] Boyd | Convex Optimization[END_REF]. For sufficiently large gradients, we provide a lower bound on the decrease achieved by the step; and for small gradients, we show that a local convergence phase begins, during which the iterates converge quadratically towards a local minimizer of (P). To establish local convergence, we quantify how small the gradient norm needs to be so that the following occurs: the full Newton step is the solution of the subproblem, it is successful, it produces a new iterate that is also in R 3 , and the sequence of gradient norms converges quadratically towards zero.

Before stating those results, we establish several consequences of the boundedness assumption on R 3 (A2) that are helpful in analyzing (regularized) Newton steps, starting with a Lipschitz-type inequality on the gradient of the pullback.

Lemma 3.5. Under A2, there exists LH > 0 such that for all iterates x k ∈ R 3 produced by Algorithm 1, we have

∇ fk (s k ) -∇ fk (0) -∇ 2 fk (0)[s k ] ≤ LH 2 s k 2 . (3.15)
Proof. The constant LH exists by continuity of the derivatives over R 3 (a compact set) and boundedness of the steps (Boumal, 2023, Lemma 10.57). The compactness of R 3 comes from A2, while the boundedness of the steps s k follows from

s k ≤ ∆ k ≤ ∆.
The next result describes a non-singularity condition for the differential of the retraction on small steps. This allows to relate the gradient of the pullback and the gradient at the next iterate. This property was introduced in [START_REF] Absil | Trust-Region Methods on Riemannian Manifolds[END_REF], and further analyzed in the context of cubic regularization of Newton's method [START_REF] Agarwal | Adaptive regularization with cubics on manifolds[END_REF].

Lemma 3.6. Let κ R > 1, under A2 there exists ν R > 0 such that for any x k ∈ R 3 and

s ∈ T x k M with s ≤ ν R , we have gradf (R x (s)) x k+1 ≤ κ R ∇ f (s) x k .
(3.16)

Proof. We apply (Agarwal et al., 2021, Theorem 7) to R 3 as a non-empty compact subset of M. This ensures that for any κ R > 1, there exists a constant ν R > 0 such that, at each

x k ∈ R 3 , s ≤ ν R ⇔ σ min (DR x k (s)) ≥ 1 κ R ,
where DR x k denotes the differential of R x k . The desired conclusion follows by combining this result with [START_REF] Agarwal | Adaptive regularization with cubics on manifolds[END_REF], Equation 22), which states that

∇ fx k (s) ≥ σ min (DR x k (s)) gradf (R x k (s)) .
Combining the previous two lemmas, we bound the change in gradient norm for Newton steps.

Lemma 3.7. Under A1 and A2, let x k ∈ R 3 be an iterate produced by Algorithm 1 such that s k is the Newton step, i.e., H k s k = -g k , and s k ≤ ν R where ν R is the constant from Lemma 3.6. Then, if the iteration is successful, we have

gradf (x k+1 ) x k+1 ≤ κ R LH 2 s k 2 x k (3.17)
where LH comes from Lemma 3.5.

Proof. By assumption, x k+1 = R x k (s k ). Using successively Lemma 3.6, A1 and Lemma 3.5, we obtain gradf (x k+1 )

x k+1 ≤ κ R ∇ fx k (s k ) x k = κ R ∇ fx k (s k ) -gradf (x k ) + gradf (x k ) x k = κ R ∇ fx k (s k ) -gradf (x k ) -H k s k x k = κ R ∇ fx k (s k ) -∇ fx k (0) -∇ 2 fk (0)[s k ] x k ≤ κ R LH 2 s k 2 x k .
Remark 3.1. Using the exponential map rather than a general retraction significantly simplifies the analysis above. Indeed, with the exponential map, Lemma 3.5 can be replaced by

P -1 s gradf (Exp x (s)) -gradf (x) -Hessf (x)[s] ≤ L H 2 s 2 (3.18)
where P -1 s is the parallel transport from T Exp x (s) M to T x M, and L H is the Lipschitz constant of Hessf from (3.3), see (Boumal, 2023, Corollary 10.56). As a result, the proof of Lemma 3.7 is also simplified, and no longer requires the decomposition in short and long steps induced by Lemma 3.6.

We are equipped to prove a decrease guarantee for Newton steps.

Lemma 3.8. Under the assumptions of Lemma 3.7, we have

m k (0) -m k (s k ) ≥ γ LH κ R gradf (x k+1 ) x k+1 .
Proof. By combining (3.17) with (3.7), we obtain

m k (0) -m k (s k ) ≥ γ 2 s k 2 x k ≥ γ LH κ R gradf (x k+1 ) x k+1 .
We now turn to local convergence results. Our goal is to show that Newton steps are eventually accepted by the algorithm, and that they produce iterates with decreasing gradient norm. We begin with a bound on the norm of the subproblem minimizer in R 3 . Lemma 3.9. Suppose that Algorithm 1 produces an iterate x k ∈ R 3 . Then,

s k ≤ g k γ . (3.19)
Proof. The result holds trivially if s k = 0. Otherwise, using the definition of R 3 together with λ k ≥ 0 and (3.8), we get

γ s k 2 ≤ s k , H k s k ≤ s k , (H k + λ Id)s k = -s k , g k ≤ s k g k ,
and division by s k gives (3.19).

Lemma 3.9 is an elementary identity that we use throughout. We use it in the next proposition to show that iterations in R 3 with a small enough gradient are successful.

Proposition 3.10. Under A1 and A3, suppose that Algorithm 1 generates

x k ∈ R 3 such that gradf (x k ) < 3(1 -η 1 )γ 2 L H . (3.20)
Then, the kth iteration is successful.

Proof. First, we note that the condition for a successful step ρ k ≥ η 1 is equivalent to

f (R k (s k )) -m k (s k ) + (1 -η 1 )(m k (s k ) -m k (0)) ≤ 0. (3.21)
The proof then consists in finding an upper bound for the left-hand side that is negative. From Lemma 3.3, we have that

(1 -η 1 ) (m k (s k ) -m k (0)) ≤ (1 -η 1 )(- γ 2 s k 2 ).
Combining this property with (3.14) and (3.19) gives

f (R k (s k )) -m k (s k ) + (1 -η 1 )(m k (s k ) -m k (0)) ≤ L H 6 s k 3 - γ 2 (1 -η 1 ) s k 2 = s k 2 L H 6 s k - γ 2 (1 -η 1 ) ≤ s k 2 L H 6 g k γ - γ 2 (1 -η 1 ) .
The right-hand side is negative by (3.20), from which we conclude that (3.21) holds, and the iteration is successful.

We now show that if the gradient norm is small enough, the Newton step decreases the gradient norm.

Proposition 3.11. Under A1 and A2, let x k ∈ R 3 be an iterate produced by Algorithm 1 such that s k is the Newton step, i.e., H k s k = -g k , with s k ≤ ν R where ν R is the constant from Lemma 3.6. If

gradf (x k ) < 2γ 2 κ R LH , (3.22)
and the iteration is successful, then gradf (x k+1 ) x k+1 < gradf (x k ) x k .

Proof. Combining (3.17), (3.19) and (3.22) gives

g k+1 ≤ κ R LH 2 s k 2 ≤ κ R LH 2 g k 2 γ 2 ≤ κ R LH 2γ 2 g k • g k < g k .
In order to derive a local convergence result, we show that, if x k ∈ R 3 and the gradient norm is small enough, the Newton step remains in the neighborhood of the same minimizer.

Proposition 3.12. Under A1 and A2, let x k ∈ R 3 be an iterate produced by Algorithm 1 such that s k is the Newton step, and s k ≤ ν R where ν R is the constant from Lemma 3.6, and that

gradf (x k ) < min ν S γ, γδ 2κ S , γδ 2 , 2γ 2 κ R LH . (3.23)
Let x * ∈ M be a local minimum of problem (P) such that dist (x k , x * ) ≤ δ and f is geodesically γ-strongly convex on {y ∈ M : dist(y, x * ) < 2δ}. If the iteration is successful, then dist (x k+1 , x * ) < δ.

Proof. We first show that dist (x k+1 , x * ) < 2δ. Using (3.19) and (3.23), we have that

s k ≤ g k γ < ν S γ γ = ν S . It follows from Lemma 2.2 that dist(x k+1 , x k ) ≤ κ S s k ≤ κ S g k γ ≤ κ S γ γδ 2κ S = δ 2 ,
where the last inequality is due to (3.23). As a result,

dist(x k+1 , x * ) ≤ dist(x k+1 , x k ) + dist(x k , x * ) ≤ δ 2 + δ < 2δ.
By definition of x * , we know that f is geodesically γ-strongly convex over S ⊆ M, a subset of M that includes x * and x k+1 . Consider a geodesic c : [0, 1] → S contained in S with c(0) = x k+1 and c(1) = x * , such that dist(x k+1 , x * ) ≤ L(c) where L(c) = c (0) c( 0) is the length of the geodesic path. From (Boumal, 2023, Theorem 11.21), we have

f (x * ) ≥ f (x k+1 ) + gradf (x k+1 ), c (0) x k+1 + γ 2 L(c) 2 . Using f (x * ) ≤ f (x k+1 ) gives γ 2 L(c) 2 ≤ gradf (x k+1 ), -c (0) x k+1 ≤ gradf (x k+1 ) x k+1 c (0) x k+1 = gradf (x k+1 ) x k+1 L(c).
Therefore, we have L(c) ≤ 2 γ gradf (x k+1 ) x k+1 . To conclude, recall that we have

s k ≤ ν R
by assumption, thus Proposition 3.11 applies, and we obtain

dist(x k+1 , x * ) ≤ L(c) ≤ 2 γ gradf (x k+1 ) x k+1 < 2 γ gradf (x k ) x k < 2 γ γδ 2 = δ.
We now characterize the local convergence of Algorithm 1. The quadratic convergence rate stems from the following proposition.

Proposition 3.13. Under A1 and A2, let x k ∈ R 3 be an iterate produced by Algorithm 1 such that s k is a Newton step, and s k ≤ ν R where ν R is the constant from Lemma 3.6. Suppose further that the kth iteration is successful. Then,

κ R LH 2γ 2 gradf (x k+1 ) x k+1 ≤ κ R LH 2γ 2 gradf (x k ) x k 2 .
Proof. Using Lemma 3.7 and Lemma 3.9 gives

gradf (x k+1 ) x k+1 ≤ κ R LH 2 s k 2 x k ≤ κ R LH 2γ 2 gradf (x k ) 2 x k ,
and multiplying both sides by κ R LH 2γ 2 yields the desired conclusion.

Proposition 3.13 guarantees that the gradient norm decreases quadratically along Newton steps, provided that the gradient norm is small enough. In Proposition 3.14, we show that the local phase of Algorithm 1 begins once the trust-region method generates a point in R 3 with a small enough gradient.

Proposition 3.14 (Local convergence of Algorithm 1). Suppose that A1, A2 and A3 hold. Let x k ∈ R 3 be an iterate produced by Algorithm 1, and let x * ∈ M be a local minimum of (P) such that dist(x k , x * ) ≤ δ and f is geodesically γ-strongly convex on {y ∈ M : dist(y, x * ) < 2δ}. Finally, suppose that

gradf (x k ) < min c Q min γ, γ 2 , γδ , γ∆ k (3.24)
where

c Q = min 3(1 -η 1 ) L H , ν R , 1 κ S , 1 2 , 1 κ R LH
. Then, all subsequent iterations are successful Newton steps that remain in R 3 . Moreover, the sequence of gradient norms ( gradf (x k ) ) k converges quadratically to zero.

Proof. Lemma 3.9 and (3.24) give s k ≤ gradf (x k ) /γ < ∆ k , and thus s k is the Newton step. In addition, the condition (3.24) also implies (3.20), thus the kth iteration is successful by Proposition 3.10. Similarly, (3.24) implies (3.22), (3.23), and s k ≤ ν R , which yields g k+1 < g k (Proposition 3.11) and dist(x k+1 , x * ) < δ (Proposition 3.12). Since g k+1 < g k < γ∆ k ≤ γ∆ k+1 , the same reasoning applies at iteration k + 1, and at every subsequent iteration by induction, proving the first part of the result. Finally, quadratic convergence follows from repeated application of Proposition 3.13, as (3.24) implies gradf (x k ) < γ 2 /(κ R LH ). Indeed, for any index l ≥ k, we have

LH κ R 2γ 2 gradf (x l ) ≤ LH κ R 2γ 2 gradf (x k ) 2 l-k ≤ 1 2 2 l-k , (3.25)
which characterizes quadratic convergence.

We emphasize that the local convergence property is an integral part of our global convergence analysis. Deriving global rates of convergence (i.e., complexity results) is the subject of the next section.

Complexity bounds

In this section, we combine the results from Sections 3.2 and 3.3 to obtain complexity bounds. More precisely, we seek a bound on the number of iterations Algorithm 1 requires to reach an iterate x K ∈ M that is an (ε g , ε H )-second-order critical point-defined in Equation (1.2).

Following Section 3.3, we can bound the number of iterations in the local phase necessary to satisfy (1.2). The result below is a direct corollary of Proposition 3.14.

Theorem 3.15. Let the assumptions of Proposition 3.14 hold for x k ∈ R 3 generated by Algorithm 1. Then, the algorithm returns an iterate satisfying (1.2) in at most

log 2 log 2 2γ 2 κ R LH ε g (3.26)
iterations following iteration k.

Proof. For any l ≥ k, it follows from Equation (3.25) that if gradf (x l ) ≥ ε g , it must be that

l -k ≤ log 2 log 2 2γ 2 LH κ R ε g .
Our main complexity result comes under the assumption that f is lower bounded on M.

A5. There exists f * > -∞ such that f (x) ≥ f * for all x ∈ M.

We first give an upper bound on the number of successful steps for Algorithm 1.

Theorem 3.16 (Number of successful iterations of Algorithm 1). Suppose that A1-A5 hold. Algorithm 1 produces an iterate satisfying (1.2) in at most

C min α 2 , α 4/3 β, α 4/3 γ, α 2/3 γ 2 , β 3 , β 2 γ, βγ 2 , γ 3 , γ 2 δ + 1 + log 2 log 2 2γ 2 κ R LH ε g
successful iterations, where the constant C > 0 depends on κ H , c ∆ , ∆ 0 , ν R , κ R , LH , η 1 , c Q , and for any θ ∈ {α, β, γ, δ}, we define θ = min(1, θ).

Proof. Let K ∈ N such that Algorithm 1 has not produced an iterate satisfying (1.2) by iteration K. Let S = {k ≤ K : ρ k ≥ η 1 } denote the set of indices corresponding to successful (and very successful) iterations up to index K. We partition the set of iterations as follows:

S 1 = {k ∈ S : x k ∈ R 1 } S 2 = {k ∈ S : x k ∈ R 2 \ R 1 } S 3 = {k ∈ S : x k ∈ R 3 \ R 1 }.
We now bound the decrease in function value for all three sets. Let k ∈ S 1 , using Lemma 3.1 and Lemma 3.4, we obtain

f (x k ) -f (x k+1 ) ≥ η 1 (m k (0) -m k (s k )) ≥ η 1 2 min α κ H , ∆ k α ≥ η 1 2 min α κ H , ∆ min α. (3.27)
For k ∈ S 2 , combining Lemma 3.2 with Lemma 3.4 gives

f (x k ) -f (x k+1 ) ≥ η 1 (m k (0) -m k (s k )) ≥ η 1 2 ∆ 2 k β ≥ η 1 2 ∆ 2 min β.
(3.28)

We partition S 3 into iterations with long steps, short steps on the boundary of the trust region, and short steps inside the trust region: S 3 := S l 3 ∪ S s,b 3 ∪ S s,i 3 , where

S l 3 = {k ∈ S 3 : s k > ν R } S s,b 3 = {k ∈ S 3 : s k ≤ ν R , s k = ∆ k } S s,i 3 = {k ∈ S 3 : s k ≤ ν R , s k < ∆ k } where ν R > 0 is defined in Lemma 3.6. If k ∈ S l 3 , Lemma 3.3 yields f (x k+1 ) -f (x k ) ≥ η 1 2 γ s k 2 ≥ η 1 2 γν 2 R . (3.29) If k ∈ S s,b
3 , we use Lemma 3.3 together with Lemma 3.4 to obtain

f (x k+1 ) -f (x k ) ≥ η 1 2 γ s k 2 = η 1 2 γ∆ 2 k ≥ η 1 2 γ∆ 2 min . (3.30)
Finally, if k ∈ S s,i 3 , we partition further S s,i 3 into S s,i,s 3 ∪ S s,i,l 3 , where

S s,i,l 3 = k ∈ S s,i 3 : g k+1 ≥ min c Q min γ, γ 2 , γδ , γ∆ k , S s,i,s 3 = S s,i 3 \ S s,i,l 3 .
If k ∈ S s,i,l 3 , Proposition 3.8 implies

f (x k ) -f (x k+1 ) ≥ η 1 γ g k+1 LH κ R ≥ η 1 LH κ R min c Q min γ 2 , γ 3 , γ 2 δ , γ 2 ∆ k ≥ η 1 LH κ R min c Q min γ 2 , γ 3 , γ 2 δ , γ 2 ∆ min . (3.31)
Finally, if k ∈ S s,i,s

3

, either x k+1 ∈ S 3 and the local convergence phase begins at x k+1 according to Proposition 3.14; which produces an iterate that satisfies (1.2) in a number of iterations given by (3.26). Otherwise, we must have x k+1 ∈ S 1 ∪ S 2 , and as a result we have

S s,i,s 3 ≤ |S 1 | + |S 2 | + 1 + log 2 log 2 2γ 2 κ R LH ε g . (3.32)
It thus suffices to bound the cardinality of S 1 and S 2 to bound S s,i,s 3 . Thanks to A5, we have

f (x 0 ) -f * ≥ f (x 0 ) -f (x K ) ≥ k∈S f (x k ) -f (x k+1 ) ≥ k∈S 1 f (x k ) -f (x k+1 ) + k∈S 2 f (x k ) -f (x k+1 ) + k∈S l 3 f (x k ) -f (x k+1 ) + k∈S s,b 3 f (x k ) -f (x k+1 ) + k∈S s,i,l 3 f (x k ) -f (x k+1 ).
Putting (3.27), (3.28), (3.29), (3.30) and (3.31) together, we obtain

f (x 0 ) -f * ≥ |S 1 | η 1 2 min (α/κ H , ∆ min ) α + |S 2 | η 1 2 ∆ 2 min β + S l 3 η 1 2 ν 2 R γ + S s,b 3 η 1 2 ∆ 2 min γ + S s,i,l 3 η 1 LH κ R min c Q min γ 2 , γ 3 , γ 2 δ , γ 2 ∆ min .
Since all quantities on the right-hand side are nonnegative, we can bound each cardinality independently as follows:

|S 1 | ≤ 2(f (x 0 ) -f * ) η 1 max κ H α -2 , ∆ -1 min α -1 |S 2 | ≤ 2(f (x 0 ) -f * ) η 1 ∆ -2 min β -1 |S l 3 | ≤ 2(f (x 0 ) -f * ) η 1 ν -2 R γ -1 |S s,b 3 | ≤ 2(f (x 0 ) -f * ) η 1 ∆ -2 min γ -1 |S s,i,l 3 | ≤ κ R LH (f (x 0 ) -f * ) η 1 max c -1 Q max γ -2 , γ -3 , γ -2 δ -1 , γ -2 ∆ -1 min .
Using that ∆ min = c ∆ min ∆ 0 , α 1/2 , α 2/3 , β, γ ≥ c ∆ min(∆ 0 , 1)min α 2/3 , β, γ yields the follow-ing upper bounds

|S 1 | ≤ 2(f (x 0 ) -f * ) η 1 max κ H , c -1 ∆ ∆ -1 0 , c -1 ∆ max α -2 , α -1 β -1 , α -1 γ -1 |S 2 | ≤ 2(f (x 0 ) -f * ) η 1 max c -2 ∆ ∆ -2 0 , c -2 ∆ max α -4/3 β -1 , β -3 , β -1 γ -2 |S l 3 | ≤ 2(f (x 0 ) -f * ) η 1 ν -2 R γ -1 |S s,b 3 | ≤ 2(f (x 0 ) -f * ) η 1 max c -2 ∆ ∆ -2 0 , c -2 ∆ max α -4/3 γ -1 , β -2 γ -1 , γ -3 |S s,i,l 3 | ≤ κ R LH (f (x 0 ) -f * ) η 1 max c -1 Q , c -1 ∆ ∆ -1 0 , c -1 ∆ max α -2/3 γ -2 , β -1 γ -2 , γ -3 , γ -2 δ -1 .
Combining these bounds with (3.32), the total number of successful iterations is bounded as

|S| = |S 1 | + |S 2 | + |S l 3 | + |S s,b 3 | + |S s,i,l 3 | + |S s,i,s 3 | ≤ 2|S 1 | + 2|S 2 | + |S l 3 | + |S s,b 3 | + |S s,i,l 3 | + 1 + log 2 log 2 2γ 2 κ R LH ε g . ≤ C min α 2 , α 4/3 β, α 4/3 γ, α 2/3 γ 2 , β 3 , β 2 γ, βγ 2 , γ 3 , γ 2 δ -1 + 1 + log 2 log 2 2γ 2 κ R LH ε g , where C = (f (x 0 ) -f * ) η 1 4 max κ H , c -1 ∆ ∆ -1 0 , c -1 ∆ + 6 max c -2 ∆ ∆ -2 0 , c -2 ∆ +2ν -2 R + κ R LH max c -1 Q , c -1 ∆ ∆ -1 0 , c -1 ∆ .
Theorem 3.16 bounds the number of successful iterations required to satisfy (1.2), which corresponds to the number of gradient and Hessian evaluations. To account for the total number of iterations-the number of function evaluations, we follow a common strategy and show that this number is at most a constant multiple of the number of successful iterations.

Lemma 3.17. Under the assumptions of Lemma 3.4, let K ∈ N and let S denote the set of successful iterations of index k ≤ K. Then,

|S| ≥ log τ 2 (1/τ 1 ) 1 + log τ 2 (1/τ 1 ) (K + 1) - 1 1 + log τ 2 (1/τ 1 ) max 0, log τ 2 1 c ∆ , log τ 2 ∆ 0 c ∆ α 1 2 , log τ 2 ∆ 0 c ∆ α 2 3 , log τ 2 ∆ 0 c ∆ β , log τ 2 ∆ 0 c ∆ γ .
Proof. The proof follows verbatim (Boumal, 2023, Lemma 6.23) with (3.12) replacing (Boumal, 2023, Eq. (6.36)) and τ 1 , τ 2 replacing 1 4 and 2, respectively. Since c ∆ ≤ 1 by definition, the maximum is always a nonnegative quantity.

Combining Theorem 3.16 with Lemma 3.17 gives the total iteration complexity.

Theorem 3.18 (Iteration complexity of Algorithm 1). Under the assumptions of Theorem 3.16, Algorithm 1 produces a point that satisfies (1.2) in at most

1 + log τ2 (1/τ 1 ) log τ2 (1/τ 1 ) C min α 2 , α 4/3 β, α 4/3 γ, α 2/3 γ 2 , β 3 , β 2 γ, βγ 2 , γ 3 , γ 2 δ + 1 + log 2 log 2 2γ 2 κ R LH ε g (3.33) + 1 log τ2 (1/τ 1 ) max log τ2 1 c ∆ , log τ2 ∆ 0 c ∆ α 1 2 , log τ2 ∆ 0 c ∆ α 2 3 , log τ2 ∆ 0 c ∆ β , log τ2 ∆ 0 c ∆ γ
iterations, where C, α, β, γ, δ are defined as in Theorem 3.16.

The bound of Theorem 3.18 holds for any values ε g > 0 and ε H > 0, but it is especially relevant when ε g < α and ε H < β. In that case, the iteration complexity (3.33) is an improvement over the O max(ε -2 g ε -1 H , ε -3 H ) bound of Riemannian trust-region methods for generic nonconvex functions [START_REF] Boumal | Global rates of convergence for nonconvex optimization on manifolds[END_REF]. Perhaps surprisingly, our bound does not depend on ε H . This is because every iterate x k such that gradf (x k ) ≤ g and λ min (Hessf (x k )) < -ε H belongs to R 2 , where the function decrease depends on β. In fact, if ε g < α and ε H < β, Algorithm 1 necessarily reaches some

x k ∈ R 3 such that gradf (x k ) ≤ ε g and λ min (Hessf (x k )) ≥ γ.
This ensures that the algorithm finds an approximate minimizer, which is not guaranteed in the general nonconvex case. In that sense, the strict saddle property allows to obtain stronger guarantees of optimality and improved complexity bounds.

On the other hand, if

ε g ≥ α or ε H ≥ β, an (ε g , ε H )-critical point (1.
2) need not belong to R 3 . The following table indicates the possible regions in which Algorithm 1 can terminate depending on the values of ε g and ε H :

Convergence of Algorithm 1 α > ε g α ≤ ε g β > ε H R 3 R 1 ∪ R 3 β ≤ ε H R 2 ∪ R 3 R 1 ∪ R 2 ∪ R 3
When the strict saddle parameters α and β are known, one can always select ε g and ε H to ensure that the method reaches an iterate in R 3 . In that case, the value of ε g only affect the complexity through a logarithmic factor, and ε H is irrelevant.

To end this section, we apply our complexity result to the examples of strict saddle functions from Section 2.

Example 3.1. As a continuation of Example 2.1, let f : R n → R be a γ-strongly convex function, choose α = 1 so that f is (1, 1, γ, 2 γ )-strict saddle, and let ε g ∈ (0, 1). Then, by Theorem 3.18, Algorithm 1 computes an iterate such that ∇f

(x k ) ≤ ε g in at most O(γ -3 ) + log log(γ 2 ε -1 g ) iterations.
In comparison, a standard analysis of Newton's method with Armijo backtracking linesearch gives at most O(γ -5 )+log log(γ 3 ε -1 g ) iterations to find such a point [START_REF] Boyd | Convex Optimization[END_REF]. Although our bound has a better dependency on γ, we believe that this is an artefact of the line-search analysis, which could be improved by changing the line-search condition.

Example 3.2. As a continuation of Example 2.2, let f : S n-1 → R be defined by f (x) = x T Ax, where A ∈ R n×n is a symmetric matrix with eigenvalues λ 1 > λ 2 ≥ • • • ≥ λ n-1 > λ n . Then, by Theorem 3.18, Algorithm 1 computes an iterate satisfying (1.2) in at most

O max 1, λ 2 1 (λ n-1 -λ n ) 2 , λ 4/3 1 (λ n-1 -λ n ) 7/3 , λ 2/3 1 (λ n-1 -λ n ) 8/3 , 1 (λ n-1 -λ n ) 3 , λ 1 (λ n-1 -λ n ) 3 +O log log (λ n-1 -λ n ) 2 ε -1 g iterations.

Riemannian trust-region method with inexact subproblem minimization

In this section, we design an inexact variant of the Riemannian trust-region algorithm, that is tailored to strict saddle functions. In each region of M, some landscape-aware step is appropriate and ensures good convergence rates: gradient-like steps in R 1 , negative curvature steps in R 2 , and (regularized) Newton steps in R 3 . Our goal is to compute these steps approximately, without computing the entire spectrum of the Hessian to determine the region of the current point. The natural choice for this is the well-known truncated conjugate gradient algorithm [START_REF] Toint | Towards an Efficient Sparsity Exploiting Newton Method for Minimization[END_REF][START_REF] Steihaug | The Conjugate Gradient Method and Trust Regions in Large Scale Optimization[END_REF], and its recent adaptations that yield second-order complexity guarantees (Curtis et al., 2021). We make minimial adjustements to the standard truncated conjugate gradient (tCG), in order to leverage the strict saddle structure and ensure convergence to second-order critical points. In a departure from the exact setting, we explicitly use the strict saddle parameters α, β, γ in the inexact algorithm. This idea appears in a recent proposal for nonconvex matrix factorization problems, which satisfy a different strict saddle property (O'Neill and Wright, 2023).

Inexact algorithm and subroutines

Recall that, at every iteration k, the trust-region subproblem is given by min

s∈Tx k M m k (s) subject to s ≤ ∆ k , (4.1)
where m k is the quadratic model defined in (3.2). For nonzero g k , we apply a truncated conjugate gradient method to find an approximate solution of the subproblem. Our variant of truncated conjugate gradient, described in Algorithm 2, is a Riemannian adaptation of (Curtis et al., 2021)-a nonconvex trust-region method with complexity guarantees; which we further adapt to strict saddle problems. The main differences between Algorithm 2 and (Curtis et al., 2021, Algorithm 3.1) lie in the tolerance on the curvature and the stopping criterion. For the former, we use the strict saddle constant γ (the strong convexity constant in R 3 ) instead of an arbitrary tolerance on the smallest eigenvalue of the Hessian. Throughout the iterations of Algorithm 2, we monitor the curvature of the Hessian along the directions generated by CG. Any curvature less than γ indicates that the current iterate does not belong to R 3 , and triggers termination of tCG. We also strengthen the stopping criterion of tCG from (Curtis et al., 2021), and use

r j+1 ≤ ζ min g k 2 , g k , γ y j+1 , (4.2)
where r j = ∇m k (y j ) is the residual of the CG algorithm after j iterations, and ζ ∈ (0, 1). The term g k 2 in (4.2) ensures a local quadratic convergence, as we show in Section 4.3.

The remaining terms on the right-hand side of (4.2) are used to certify a good decrease when the current iterate belongs to R 1 or R 3 . Importantly, when H k is positive definite, the residual condition (4.2) is satisfied in min n, O γ -1/2 iterations. This property is intrinsic to the conjugate gradient algorithm.

Lemma 4.1. Suppose that we apply the conjugate gradient algorithm to g k ∈ T x k M with g k > ε g and H k such that γ Id H k κ H Id. Then, given a tolerance ζ ∈ (0, 1), CG finds a vector y ∈ T x k M such that

H k y + g k ≤ ζ min g k 2 , g k , γ y (4.3)
in at most

J CG := min n, 1 2 κ H γ ln 2 √ κ H ζ √ γ max ε -2 g , ε -1 g , κ H /γ (4.4)
iterations or, equivalently, Hessian-vector products.

Proof. The result follows from (Royer and Wright, 2018, Lemma 11), and in particular the inequality

H k y j + g k ≤ 2 κ H γ κ H /γ -1 κ H /γ + 1 j g k
that holds for any j ≤ n. The model is also minimized in at most n steps, H k y n + g k = 0.

Lemma 4.1 implies that one can use a cap on the number of iterations, along with checks on the curvature of H k , to monitor the convergence of tCG. In particular, if λ min (H k ) ≥ γ, then Algorithm 2 satisfies (4.2) in J CG iterations, which may be smaller than n in large dimensions. When this is not the case, and that x k / ∈ R 1 , the Hessian is guaranteed to have negative curvature, and we compute (an approximation of) the smallest eigenvalue.

To this end, we rely on a minimum eigenvalue oracle (MEO), that either computes a direction of sufficient negative curvature, or certifies that such direction does not exist [START_REF] Royer | A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization[END_REF]Curtis et al., 2021). One possible implementation of this procedure consists in constructing a full eigenvalue decomposition of the Hessian, which deterministically guarantees the desired outcome but requires access to the entire Hessian matrix (or, equivalently, n Hessian-vector products). Cheaper variants rely on Krylov subspace methods, such as Lanczos' method, that provide the desired guarantee with high probability using potentially less than n Hessian-vector products (Royer et al., 2020, Appendix B). For the sake of generality, we describe the MEO as a probabilistic method in Algorithm 3. Similarly to Algorithm 2, a key difference with previous minimum eigenvalue oracles is that the strict saddle constant β (associated with the region of negative curvature R 2 ) replaces an a priori optimality tolerance on the minimum eigenvalue of the Hessian.

Algorithm 3 Minimum eigenvalue oracle (MEO)

Inputs: Matrix H k , trust-region radius ∆ k , failure probability tolerance p ∈ (0, 1), bound κ H ∈ [ H , ∞), strict saddle parameter β.

Outputs: Either a certificate that λ min (H k ) ≥ -β valid with probability at least 1 -p, or a vector s ∈ T x k M such that

g k , s ≤ 0, s, H k s ≤ - 1 2 β s 2 , and s = ∆ k . (4.5)
Our inexact trust-region method (Algorithm 4) combines tCG (Algorithm 2) and the MEO (Algorithm 3). We first attempt to use tCG to solve subproblem (4.1) approximately. If the current iterate has a large enough gradient (x k ∈ R 1 ) or tCG hits the boundary of the trust region, we use the step given by tCG. Otherwise, we call the MEO to estimate the minimum eigenvalue of the Hessian. If the MEO finds a direction of sufficient negative curvature, we use it as an approximate model minimizer. Otherwise, we proceed with the tCG step.

Algorithm 4 Strict saddle RTR with inexact subproblem minimization 1: Inputs: Initial point x 0 ∈ M, initial and maximal trust-region radii 0 < ∆ 0 < ∆, constants 0 < η 1 < η 2 < 1 and 0 < τ 1 < 1 < τ 2 , failure probability tolerance p ∈ [0, 1), strict saddle parameters (α, β, γ).

2: for k = 1, 2, . . . do 3: if g k > 0 then 4:
Call Algorithm 2 on the subproblem (4.1) to obtain s CG k and outCG.

5:

end if

6: if g k ≥ α or outCG=boundary step then 7: Set s k = s CG k . 8:
else if g k = 0 or (outCG ∈ {max iter,not strongly convex,small residual} and g k < α) then.

9:

Call Algorithm 3 on the Hessian H k .

Compute ρ k = f (x k ) -f (R x k (s k )) m k (0) -m k (s k ) and set x k+1 = R k (x k ) if ρ k ≥ η 1
x k otherwise.

17:

18:

Set ∆ k+1 =      min τ 2 ∆ k , ∆ if ρ k > η 2 [very successful] ∆ k if η 2 ≥ ρ k ≥ η 1 [successful] τ 1 ∆ k otherwise.
[unsuccessful] 19: end for Note that when g k = 0, the trust-region method calls Algorithm 3 directly, and terminates if it certifies that λ min (H k ) ≥ -β, since this implies x k ∈ R 3 is a local minimum. This corner case is not central to our complexity analysis.

For the rest of Section 4, we consider the following assumption on the MEO (Algorithm 4).

A6. For any iteration of Algorithm 4, if Algorithm 3 is called during this iteration, it outputs the correct answer, i.e., a certificate that λ min (H k ) > -β or a step of curvature less than -β 2 , in at most

J MEO := min n, 1 + 1 2 ln(2.75n/p 2 ) κ H β (4.6)
iterations, with probability at least 1 -p.

Computing a full eigenvalue decomposition for Algorithm 3 ensures that A6 holds for any p ≥ 0, with J MEO = n. The bound (4.6) also applies to Krylov subspace methods, such as Lanczos' method with an initial vector uniformaly distributed on the unit sphere [START_REF] Royer | A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization[END_REF].

Properties of inexact steps

In this section, we provide several decrease lemmas for the steps produced by Algorithms 2 and 3. Our proof technique follows earlier works on Euclidean trust-region methods for general nonconvex functions (Curtis et al., 2021).

We first consider iterations of Algorithm 2 where x k ∈ R 1 (large gradient norm).

Lemma 4.2. Under A2 and A4, consider the kth iteration of Algorithm 4. Suppose that g k ≥ α, so that Algorithm 2 is called. Suppose that it outputs s k with outCG = boundary step. Then, we have

m k (0) -m k (s k ) ≥ 1 2 min ∆ k , α κ H α. (4.7)
Proof. By assumption, the step generated by tCG is taken, and it guarantees at least as much model decrease as the Cauchy step s C k , defined in the proof of Lemma 3.1. Indeed, the Cauchy step corresponds to the first iterate of tCG [START_REF] Boumal | An Introduction to Optimization on Smooth Manifolds[END_REF][START_REF] Conn | Trust Region Methods[END_REF]. Applying Lemma 3.1 gives

m k (0) -m k (s k ) ≥ m k (0) -m k (s C k ) ≥ 1 2 min ∆ k , α κ H α.
The following lemma gives a model decrease when x k ∈ R 2 and the MEO is called.

Lemma 4.3. Under A1 and A2, consider the kth iteration of Algorithm 4. Suppose that Algorithm 3 is called with x k ∈ R 2 . Then,the method outputs a vector

s k ∈ T x k M satisfying m k (0) -m k (s k ) ≥ 1 4 β∆ 2 k . (4.8)
with probability at least 1 -p.

Proof. Since x k ∈ R 2 , Algorithm 3 is called with H k such that λ min (H k ) ≤ -β.
Algorithm 4 then outputs a step satisfying (4.5) with probability 1 -p. Reasoning as in the proof of Lemma 3.2, we bound the model decrease as

m k (0) -m k (s k ) ≥ - 1 2 s k , H k s k ≥ β 4 s k 2 = β 4 ∆ 2 k .
Note that Lemma 4.3 is a probabilistic result, because it depends on the minimum eigenvalue oracle, but this oracle is only called for small gradients.

We now consider an iteration at which tCG terminates with a small residual, which satisfies (4.2).

Lemma 4.4. Under A1 and A2, consider the kth iteration of Algorithm 4. Suppose that Algorithm 2 is called and outputs s k with outCG=small residual. Then,

m k (0) -m k (s k ) ≥ 1 4 γ s k 2 .
(4.9)

In addition, if s k ≤ ν R , we have

m k (0) -m k (s k ) ≥ 1 2(κ 2 R + 2 LH κ R ) min gradf (R x k (s k )) 2 γ -1 , γ 3 . (4.10) Proof.
By assumption, we have s k = y j+1 , where y j+1 is the first iterate of tCG that satisfies the residual condition (4.2). As a result, (4.11) where the last line follows from the standard properties of CG iterates y j = j-1 i=0 σ i p i and p j , H k p i = 0 for i = j, which implies p j , H k y j = 0 (see, e.g., (Nocedal and Wright, 2006, Chapter 5) or (Royer et al., 2020, Appendix A)). In addition, Algorithm 2 ensures that p j , H k p j ≥ γ p j 2 and y j , H k y j ≥ γ y j 2 , hence

s k , H k s k = y j + σ j p j , H k (y j + σ j p j ) = y j , H k y j + σ j y j , H k p j + σ j p j , H k y j + σ 2 j p j , H k p j = y j , H k y j + σ 2 j p j , H k p j ,
s k , H k s k ≥ γ y j 2 + γ σ j p j 2 ≥ γ 2 s k 2 , (4.12)
where the last inequality follows from u 2 + v 2 ≥ 1 2 u + v 2 for all vectors u, v ∈ T x k M. Meanwhile, the model decrease satisfies

m k (0) -m k (s k ) = -s k , g k - 1 2 s k , H k s k = -s k , -H k s k + r j+1 - 1 2 s k , H k s k = 1 2 s k , H k s k -r j+1 , s k = 1 2 s k , H k s k ,
using that r j+1 = H k y j+1 + g k = H k s k + g k and r j+1 , y j+1 = 0 by the orthogonality property of the CG residual. Combining the last equality with (4.12), we obtain

m k (0) -m k (s k ) ≥ 1 4 γ s k 2 , (4.13)
which proves the first part of the proposition. Now assume s k ≤ ν R and let g + k = gradf (R x k (s k )). Using the proof of Lemma 3.7 gives

g + k ≤ κ R ∇ fk (s k ) -gradf (x k ) + gradf (x k ) = κ R ∇ fk (s k ) -gradf (x k ) -H k s k + r j+1 ≤ κ R ∇ fk (s k ) -gradf (x k ) -H k s k + κ R r j+1 (4.14) ≤ LH κ R 2 s k 2 + κ R γ s k ,
where the last line follows from the small residual condition (4.2). The inequality

LH κ R 2 s k 2 + κ R γ s k -g + k ≥ 0 (4.15)
involves a univariate quadratic function of s k ≥ 0, and thus (4.15) holds as long as

s k ≥ -κ R γ + κ 2 R γ 2 + 2 LH κ R g + k LH κ R =   -κ R + κ 2 R + 2 LH κ R g + k γ -2 LH κ R   γ ≥   -κ R + κ 2 R + 2 LH κ R LH κ R   min g + k γ -2 , 1 γ =   2 κ R + κ 2 R + 2 LH κ R   min g + k γ -1 , γ ≥ 1 κ 2 R + 2 LH κ R min g + k γ -1 , γ ,
where we used that -a

+ √ a 2 + bt ≥ (-a + √ a 2 + b) min(t, 1) with a = κ R , b = 2 LH κ R and t = g k+1 γ -2 and that 2 1 + √ 1 + c ≥ 1 √ 1 + c
for any c > 0. Combining the above with (4.13),

we get

m k (0) -m k (s k ) ≥ 1 4 γ s k 2 ≥ 1 2(κ 2 R + 2 LH κ R ) min gradf (R x k (s k )) 2 γ -1 , γ 3 ,
proving (4.10).

The next lemma considers steps that lie on the boundary of the trust region. Note that our proof differs from the general nonconvex setting (Curtis et al., 2021, Lemma 4.3), because we do not add an artificial regularizer in the subproblem.

Lemma 4.5. Under A1 and A2, consider the kth iteration of Algorithm 4. Suppose that Algorithm 2 is called and outputs s k together with outCG=boundary step. Then,

m k (0) -m k (s k ) ≥ 1 4 γ∆ 2 k . (4.16)
Proof. Since outCG=boundary step, the step has the form s k = y j + σj p j with s k = ∆ k and

0 ≤ σj ≤ σ j = r j 2 p j , H k p j = - g k , p j p j , H k p j , (4.17)
where the last equality holds by definition of the CG residual. Since p j , H k p j ≥ γ p j 2 > 0, Equation (4.17) implies -σ j g k , p j ≥ σ2 j p j , H k p j , from which we obtain

m k (0) -m k (σ j p j ) = -σ j g k , p j - σ2 j 2 p j , H k p j ≥ σ2 j p j , H k p j - σ2 j 2 p j , H k p j = σ2 j 2 p j , H k p j ≥ γ 2 σj p j 2 . (4.18)
The reasoning used to prove (4.9) can be applied to m k (0) -m k (y j ) (recall that y j , H k y j ≥ γ y j 2 ), which gives

m k (0) -m k (y j ) ≥ γ 2 y j 2 . (4.19) Finally, using m k (s k ) -m k (0) = m k (y j ) -m k (0) + m k (σ j p j ) -m k (0) (
m k (0) -m k (s k ) = m k (0) -m k (y j ) + m k (0) -m k (σ j p j ) ≥ γ 2 y j 2 + γ 2 σj p j 2 ≥ γ 2 y j 2 + σj p j 2 ≥ γ 4 s k 2 ,
where the last line holds because

u 2 + v 2 ≥ 1 2 u + v 2 for all u, v ∈ T x k M.
We end this section with a lower bound on the trust-region radius based on the decrease lemmas above, akin to the exact setting.

Lemma 4.6. Let A1, A2, A3 and A4 hold. For any index k ≥ 0, assume that all calls to the MEO (Algorithm 3) up to iteration k with an iterate in R 2 succeed in finding a direction of sufficient negative curvature. Then, the trust-region radius ∆ k in Algorithm 4 satisfies

∆ k ≥ ∆ min := c∆ min ∆ 0 , α 1/2 , α 2/3 , β, γ , (4.20)
where c∆ = min 1,

τ 1 3(1 -η 1 ) 2L H , τ 1 3(1 -η 1 ) 2L H , τ 1 3 3(1 -η 1 ) 2κ H L H .
Proof. The proof follows the lines of the exact case (Lemma 3.4) by considering the quantity 1 -ρ k . However, rather than partitioning the iterates according to the strict saddle regions, we consider the various steps that can be produced by the trust-region algorithm. Consider first that tCG (Algorithm 2) is called and outputs s k with flag outCG=small residual. Per Lemma 4.4, we know that the model decrease satisfies (4.9). Using A3, we combine this with the bound (3.14

) on f (R x k (s k )) -m k (s k ) to give 1 -ρ k = f (R x k (s k )) -m k (s k ) m k (0) -m k (s k ) ≤ (L H /6) s k 3 (γ/4) s k 2 = 2 L H 3γ s k ≤ 2 L H 3γ ∆ k .
Therefore, if outCG=small residual and ∆ k ≤ 3(1-η 1 ) 2 L H γ , then ρ k ≥ η 1 and the iteration is successful.

Suppose now that tCG outputs a boundary step, i.e., outCG=boundary step. Lemma 4.5 combined with (3.14) gives

1 -ρ k ≤ (L H /6)∆ 3 k (γ/4)∆ 2 k ≤ 2 L H 3γ ∆ k ,
hence the same conclusion than in the previous case holds.

If the MEO is called with x k ∈ R 2 , then by assumption it succeeds in finding a direction of curvature at most -β/2. Lemma 4.3 combined with (3.14) gives

1 -ρ k ≤ (L H /6)∆ 3 k (β/4)∆ 2 k ≤ 2L H 3β ∆ k .
If g k ≥ α and s k is not a boundary step, Lemma 4.2 combined with (3.14) gives

1 -ρ k ≤ (L H /6)∆ 3 k 1 2 min ∆ k , α κ H α ≤ L H 3 max ∆ 2 k α , κ H ∆ 3 k α 2 .
We have thus established that the kth iteration is successful as long as

∆ k ≤ min   3(1 -η 1 ) 2L H γ, 3(1 -η 1 ) 2L H β, 3(1 -η 1 ) L H α 1/2 , 3 3(1 -η 1 ) κ H L H α 2/3   .
holds, in which case ∆ k+1 ≥ ∆ k . Applying the updating rule on ∆ k , we find that the trust-region radius is lower bounded for any k ≥ 0 by

∆ k ≥ min   ∆ 0 , τ 1 3(1 -η 1 ) 2L H γ, τ 1 3(1 -η 1 ) 2L H β, τ 1 3(1 -η 1 ) 2L H α 1/2 , τ 1 3 3(1 -η 1 ) 2κ H L H α 2/3   ≥ c∆ min ∆ 0 , α 1/2 , α 2/3 β, γ .
The result of Lemma 4.6 relies on the MEO not failing to detect sufficient negative curvature if present. In the upcoming analysis, we bound the probability of such failure while deriving our main complexity result.

Complexity bounds

We now derive complexity bounds for our inexact trust-region method (Algorithm 4), and show that they depend logarithmically on the optimality tolerances, similarly to those established in Section 3.4 for the exact algorithm.

We begin by describing the local convergence of Algorithm 4. The reasoning follows the exact setting detailed in Section 3.3, and uses several results from that section.

Theorem 4.7. Suppose that A1 and A2 hold. Let x k ∈ R 3 be an iterate produced by Algorithm 4, and let x * ∈ M be a local minimum of (P) such that dist(x k , x * ) ≤ δ and f is geodesically γ-strongly convex on {y ∈ M : dist(y, x * ) < 2δ}. Finally, suppose that either gradf (x k ) = 0 or that gradf (x k ) < min cQ min 1, γ, γ 2 , γδ , γ∆ k , (4.21)

where cQ = min 3(1 -η 1 ) 2L H , ν R , 1 κ S , 1
s k ≤ s * k < ∆ k . (4.23)
We show that this step leads to a successful iteration. As in Proposition 3.10, we obtain from (4.21) along with the decrease (4.9) and (3.14) that

f (R x k (s k )) -m k (s k ) + (1 -η 1 )(m k (s k ) -f (x k )) ≤ L H 6 s k 3 -(1 -η 1 ) γ 4 s k 2 ≤ s k 2 L H 6 g k γ - γ 4 (1 -η 1 ) < 0,
showing that ρ k ≥ η 1 and thus the iteration is successful. Because H k γ Id and the model minimizer is inside the trust-region, tCG terminates with a vector s k that satisfies the small residual condition (4.2). We combine Lemma 3.5, Lemma 3.6, Lemma 3.9 and (4.21) to obtain

g k+1 x k+1 ≤ κ R g k x k ≤ κ R ∇ fk (s k ) -g k -H k s k x k + κ R r j+1 x k ≤ κ R LH 2 s k 2 x k + κ R g k 2 x k ≤ κ R 1 γ 2 + LH 2 g k 2 x k ≤ κ R 2 + LH 2 min(1, γ 2 ) g k 2 x k < 1 2 g k x k . (4.24)
As a result, we have g k+1 < g k < γ∆ k ≤ γ∆ k+1 . Applying Proposition 3.12 ensures that dist(x k+1 , x * ) ≤ δ (note that cQ < c Q and thus (3.23) holds). We can apply the above reasoning to x k+1 , which guarantees that either the method terminates or all subsequent iterates correspond to successful iterations with truncated CG steps that satisfy (4.2). Finally, to bound the number of iterations before reaching some x such that gradf (x ) < ε g , we rewrite (4.24) as

κ R ( LH + 2) 2 min(1, γ 2 ) g k+1 ≤ κ R ( LH + 2) 2 min(1, γ 2 ) g k 2 .
This shows the iteration bound (4.22) for the local phase, using the proof of Theorem 3.15.

Having characterized the local convergence behavior of our method, we can now derive global convergence results. As in the exact setting, we first bound the number of successful iterations.

Theorem 4.8 (Number of successful iterations for Algorithm 4). Suppose that A1-A6 hold. Algorithm 4 either terminates or produces an iterate satisfying (1.2) in at most

K S := C min α 2 , α 4/3 β, α 4/3 γ, β 3 , β 2 γ, β γ 2 , γ 3 , γδ 2 + 1 + log 2 log 2 2γ 2 κ R LH ε g
successful iterations with probability (1 -p) K S , where the constant C > 0 depends on κ H , c∆ , ∆ 0 , ν R , κ R , LH , η 1 , cQ , and α, β, γ, δ are defined in Theorem 3.16.

Proof. Let K ∈ N such that Algorithm 4 has not produced an iterate satisfying (1.2) by iteration K. Then the method cannot terminate before iteration K, and tCG is called at every iteration. We partition the set S = {k ≤ K : ρ k ≥ η 1 } of successful iterations based on properties of the steps, i.e., we define S0 = k ∈ S : outCG=boundary step ,

S1 = k ∈ S \ S0 : x k ∈ R 1 , S2 = k ∈ S \ S0 : x k ∈ R 2 \ R 1 , Sl 3 = k ∈ S \ S0 : x k ∈ R 3 \ R 1 , outCG=small residual, s k > ν R , Ss 3 = k ∈ S \ S0 : x k ∈ R 3 \ R 1 , outCG=small residual, s k ≤ ν R .
First consider k ∈ S0 . We obtain through Lemma 4.5 that

f (x k ) -f (x k+1 ) ≥ η 1 4 γ∆ 2 k ≥ η 1 4 γ ∆ 2 min . (4.25)
For k ∈ S1 , we have g k ≥ α and Lemma 4.2 gives

f (x k ) -f (x k+1 ) ≥ η 1 2 min ∆ k , α κ H α ≥ η 1 2 min α 2 κ H , α ∆ min . (4.26) Consider now k ∈ S2 , Lemma 4.3 gives f (x k ) -f (x k+1 ) ≥ η 1 4 β∆ 2 k ≥ η 1 4 β ∆ 2 min , (4.27)
with probability 1 -p.

For any k ∈ Sl 3 , Lemma 4.4 guarantees that

f (x k ) -f (x k+1 ) ≥ η 1 4 γ s k 2 ≥ η 1 ν 2 R 4 γ. ( 4
= k ∈ Ss 3 : g k+1 ≥ min cQ min(1, γ, γ 2 , γδ), γ∆ k , Ss,s 3 = Ss 3 \ Ss,l 3 . If k ∈ Ss,l 3 , Equation (4.10) implies that f (x k ) -f (x k+1 ) ≥ η 1 2(κ 2 R + 2 LH κ R ) min g k+1 2 γ -1 , γ 3 ≥ η 1 2(κ 2 R + 2 LH κ R ) min c2 Q min(γ -1 , γ, γ 3 , γδ 2 ), γ∆ 2 k , γ 3 ≥ η 1 2(κ 2 R + 2 LH κ R ) min c2 Q min(γ -1 , γ, γ 3 , γδ 2 ), γ ∆ 2 min , γ 3 . (4.29)
Finally, if k ∈ Ss,s 3 , we discuss based on the region of x k+1 . If x k+1 ∈ R 3 , the local phase begins at x k+1 per Theorem 4.7. If x k+1 ∈ R 1 \ R 3 , we have g k+1 ≥ α and k + 1 ∈ S0 ∪ S1 . Finally, if x k+1 ∈ R 2 , it must be that k + 1 ∈ S0 ∪ S2 . Thus, Ss,s

f (x 0 ) -f * ≥ k∈ S0 f (x k ) -f (x k+1 ) + k∈ S1 f (x k ) -f (x k+1 ) + k∈ S2 f (x k ) -f (x k+1 ) + k∈ Sl 3 f (x k ) -f (x k+1 ) + k∈ Ss,l 3 f (x k ) -f (x k+1 ).
Combining this inequality with (4.25), (4.26), (4.27), (4.28) and (4.29), and considering each sum individually, we obtain

S0 ≤ 4(f (x 0 ) -f * ) η 1 γ -1 ∆ -2 min , S1 ≤ 2(f (x 0 ) -f * ) η 1 max κ H α -2 , α -1 ∆ -1 min , S2 ≤ 4(f (x 0 ) -f * ) η 1 β -1 ∆ -2 min , Sl 3 ≤ 4(f (x 0 ) -f * ) η 1 ν -2 R γ -1 , Ss,l 3 ≤ 2(κ 2 R + 2 LH κ R )(f (x 0 ) -f * ) η 1 max (c Q ) -2 min γ -1 , γ, γ 3 , γδ 2 -1 , γ -1 ∆ -2 min , γ -3 .
Using the definition of ∆ min (4.20) as well as α, β,γ,δ, we obtain S0 ≤ 4(f (x 0 ) -f * ) η 1 max ∆ -2 0 , 1 min α 4/3 γ, β 2 γ, γ 3 -1 ,

S1 ≤ 2(f (x 0 ) -f * ) η 1 max κ H , (c ∆ ∆ 0 ) -1 , (c ∆ ) -1 × min α 2 , αβ, αγ -1 , S2 ≤ 4(f (x 0 ) -f * ) η 1 max ∆ -2 0 , 1 min α 4/3 β, β 3 , γ 2 β -1 , Sl 3 ≤ 4(f (x 0 ) -f * ) η 1 ν -2 R γ -1 , Ss,l 3 ≤ 2(κ 2 R + 2 LH κ R )(f (x 0 ) -f * ) η 1 max (c ∆ ∆ 0 ) -2 , (c Q ) -2
× min α 4/3 γ, β 2 γ, γ 3 , γδ 2 -1 .

Combining these bounds with (4.

η 1 max ∆ -2 0 , 1 + max κ H , (c ∆ ∆ 0 ) -1 , (c ∆ ) -1 + ν -2 R + (κ 2 R +2Lκ R ) 2 max (c ∆ ∆ 0 ) -2 , (c Q ) -2 .
Thus we have K ≤ K S if none of the calls to the MEO with x k ∈ R 2 fail to find sufficient negative curvature. The probability of all calls succeeding is bounded below by (1 -p) | S2 | ≥ (1 -p) K ≥ (1 -p) K S , hence the conclusion.

As in the exact setting, we can express the number of total iterations as a function of the number of successful iterations. This leads to the following result.

Theorem 4.9. Under the assumptions of Theorem 4.8, Algorithm 4 produces a point that satisfies (1.2) in at most iterations with probability at least (1 -p) K .

Proof. Let K ∈ N be an iteration index satisfying the same assumptions than in the proof of Theorem 4.8, and let S be defined according to K as in that proof. By the same argument as in Lemma 3.17, we have that | S| ≥ log τ 2 (1/τ 1 ) 1 + log τ 2 (1/τ 1 ) (K + 1)

- 1 1 + log τ 2 (1/τ 1 ) max 0, log τ 2 1 c∆ , log τ 2 ∆ 0 c∆ α 1 2 , log τ 2 ∆ 0 c∆ α 2 3
, log τ 2 ∆ 0 c∆ β , log τ 2 ∆ 0 c∆ γ .

Combining this result with Theorem 4.9 gives the desired bound, that holds with probability at least (1 -p) K if Algorithm 3 can be called at every iteration, and (1 -p) K S if it is called only on successful iterations.

Remark 4.1. While implementing Algorithm 4, one may avoid repeated calls to the MEO if a negative curvature direction was found at iteration k and the iteration is unsuccessful (Curtis et al., 2021, Implementation strategy 4.1). Such an approach can improve the probability bounds in Theorems 4.8 and 4.9 to (1 -p) K S2 , where K S2 is a bound on the number of iterations in S2 as defined in the proof of the theorem. In this paper, we focus on the improvement brought by the strict saddle properties of f , and therefore use a simpler, albeit suboptimal bound on the probability.

Since Algorithm 4 relies on an iterative procedure to solve the subproblems, we also provide a bound on the number of Hessian-vector products required to reach an approximate stationary point. The bound is obtained by accounting for both the inner iterations of tCG and the cost of the MEO. The former is bounded by J CG in the algorithm, while the latter follows directly from Assumption 6. Combining these properties with the result of Theorem 4.9, we obtain the following result.

Corollary 4.10. Under the assumptions of Theorem 4.9, the total number of Hessian-vector products performed by Algorithm 4 and its subroutines before producing an iterate satisfying (1.2) is at most max(J CG , J MEO ) K = O max n, ln max ε -2 g γ -1/2 , ε -1 g γ -1/2 , γ -3/2 γ -1/2 , ln(n)β -1/2 × min α 2 , α 4/3 β, α 4/3 γ, β 3 , β γ 2 , β 2 γ, γ 3 , γδ 2 -1 + log 2 log 2 γ 2 ε g (4.31)

with probability (1 -p) K , where K is defined in Theorem 4.9.

As a final comment, we note that the operation complexity bound (4.31) exhibits an additional logarithmic factor in ε g compared to the iteration complexity bound of Theorem 4.9, but no additional dependency on ε H , unlike in the case of general nonconvex functions. Overall, the complexity guarantees of inexact variants also improve thanks to the strict saddle property.

Conclusions

We show that worst-case complexity guarantees of Riemannian trust-region algorithms on nonconvex functions improve significantly when the function satisfies a strict saddle property. The guarantees we provide only depend logarithmically on the prescribed optimality tolerances, and, as such, are a better reflection of how problem-dependent quantities affect the performance. In particular, an algorithm with exact subproblem minimization does not require any modification from its standard version in order to benefit from these improved guarantees. Our analysis relies on the local quadratic convergence of Newton's method, and can be adapted to inexact subproblem minimizations by incorporating knowledge of the strict saddle constants in the problem. Although those parameters are known for a variety of problems, adaptive schemes have been proposed to estimate them as the algorithm unfolds [START_REF] O'neill | A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees[END_REF]. Investigating the numerical performance of these algorithms, along with their multiple possibilities for implementation, will be the subject of future work. Extending our results to a broader class of strict saddle functions which includes non-isolated minimizers would also be valuable.

if

  Algorithm 3 certifies that λ min (H k ) > -β then 11: Set s k = s CG k if g k > 0, otherwise terminate and return x k .

  to bound | S0 |, | S1 |, | S2 |, | Sl 3 |, and | Ss,l 3 | to bound | S|. The rest of the proof is similar to the proof of Theorem 3.16 for the exact case. The following inequality holds by A5:

≤

  C min α 2 , α 4/3 β, α 4/3 γ, β 3 , β γ 2 , β 2 γ, γ 3 , γδ 2 -1 +1 + log 2 log 2 2γ 2 κ R ( LH + 2)ε g , with C := 4(f (x 0 )-f * )

  Since x k ∈ R 3 , we know that λ min (H k ) ≥ γ > 0. If gradf (x k ) is zero, then Algorithm 4 calls Algorithm 3, which deterministically outputs a certificate that λ min (H k ) > -β since no negative curvature direction exists, hence the algorithm terminates.Consider now gradf (x k ) > 0. Since x k ∈ R 3 , Lemma 3.9 and (4.21) imply that the global minimizer of the trust-region subproblems * k satisfies s * k ≤ g k /γ < ∆ k .As a result, s * k is the minimizer of the quadratic model, and lies inside the trust region. The iterates of CG have a norm not greater than the model minimizer, thus we have

	2	,	1 κ R (2 + LH )	. Then, either Algorithm 4 terminates or
	computes an iterate satisfying (1.2) in at most
	log 2 log 2	2 min(1, γ 2 ) κ R ( LH + 2)ε g	(4.22)
	iterations.
	Proof.

Acknowledgments The authors are grateful to Coralia Cartis for useful discussions regarding local convergence of trust-region methods and for sharing reference (Shek, 2015). This research was partially funded by the Agence Nationale de la Recherche through program ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

Algorithm 2 Truncated Conjugate Gradient (tCG) for subproblem (4.1)

Input: Nonzero gradient g k , Hessian matrix H k , trust-region radius ∆ k , accuracy parameter

Output: trial step s and flag outCG indicating termination type

Set d = ∆ k y j / y j and terminate with outCG = not strongly convex end if if p j , H k p j < γ p j 2 then Set d = ∆ k p j / p j and terminate with outCG = not strongly convex end if σ j ← r j 2 / p j , H k p j Begin standard tCG procedure

Compute σj ≥ 0 such that y j + σj p j = ∆ k return s ← y j + σj p j and outCG = boundary step end if r j+1 ← r j + σ j H k p j if condition (4.2) holds then return s ← y j+1 and outCG = small residual end if τ j+1 ← r j+1 2 / r j 2 p j+1 ← -r j+1 + τ j+1 p j end standard tCG procedure j ← j + 1 end while return s ← y kmax and outCG = max iter


Sung Hyun Yoo

Jeremie Buratto

Arup Roy

Morgane Pasco

Karolina Pulka-Ziach

Gavin William Collie

Gilles Guichard

Jérémie Buratto

Oligourea helix bundle binds detergents with diverse polar head groups

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

There is currently significant interest in the design and synthesis of oligomers able to mimic (and build upon) the folding and functions of natural polymers such as peptides and nucleic acids. [1][2][3] Such molecules, termed foldamers, 1,4 are expected to find application in a broad range of areas including biosensing, biomedicine and as functional nanomaterials. [START_REF] Hecht | Foldamers: Structure, Properties, and Applications[END_REF][START_REF] Pasco | Comprehensive Supramolecular Chemistry II[END_REF][START_REF] Guichard | [END_REF][8][9][10][11][12][13][14][15] One particular area of focus within the foldamer field, and the subject of this current work, involves the design of aqueous self-assembling systems with the ultimate goal of creating functional, proteinlike architectures with tuneable properties such as selective substrate recognition or catalysis. [16][17][18][19][20] Recently, we have reported the ability of amphiphilic oligourea foldamers to selfassemble in aqueous conditions into precise, protein-like helix bundles, [21][22][23] and furthermore, that one of these assemblies is able to adaptively bind (that is, conformationally rearrange upon ligand binding) a series of alkyl glycosides. 24 Here, we set out to explore (and expand) the repertoire of lipidic guests able to be recognised by the oligourea helix bundle, as step towards adding further functionality to the system, such as selective guest recognition. Crystallographic screening of a broad set of chemically diverse detergents resulted in the identification of five additional chemotypes able to adaptively bind to the oligourea helix bundle, with circular dichroism studies providing insight into the contribution of the lipidic tails in the binding process. These findings increase our understanding of aqueous encapsulation by artificial folded self-assemblies and provide further design principles that will hopefully aid the creation of improved oligourea-based assemblies with bespoke properties such as selective ligand recognition or catalysis.

Results and Discussion

We have previously reported the ability of an amphiphilic oligourea foldamer (termed H1) to self-assemble into a stable six-helix bundle in aqueous conditions (Figure 1). 21 It was then shown that this foldamer helix bundle is able to recognise and encapsulate simple primary alcohols, and further, to be able to adaptively bind a series of n-alkyl glycosides (Figure 1c). 23,24 In an effort to explore whether detergent-type molecules with non-glycosidic polar head groups (including ionic, zwitterionic and non-ionic) could be recognised by and bind to the H1 helix bundle, we screened a set of commercially available detergents, [START_REF]Crystallisation screening was performed using HR2-406 detergent screen HT supplied by Hampton Research[END_REF] by X-ray crystallography. Detergents were screened by co-crystallisation with H1 using previously reported crystallisation conditions and procedures. 24 These efforts yielded five new crystal structures, revealing ligand-complexes for H1 bound by detergents with a diverse array of polar head groups including a linear saccharide (Mega-10), oligo ethylene glycols (C8E6 and C12E9), trimethyl ammonium bromide (CTAB) and a phospho zwitterion (F6OPC) (Figure 1d -h). All five complexes reveal H1 to form a six-helix bundle highly isomorphous to that reported previously for the H1-OGP complex 24 (R.M.S.D. of alignments = 0.144 Å) (Figure Please do not adjust margins Please do not adjust margins S1). Each complex involves six H1 helices associating primarily through hydrophobic side chains to form a hydrophobic core, with six guest detergent molecules binding per six-helix bundle. Similar to H1-OGP, the binding of all guest molecules to H1 resulted in a bundle with a more compressed shape compared to apo-H1. Curiously, while the electron density for the lipid tails of the detergents (which bind to the hydrophobic interior of the bundles) is of sufficient strength to allow these regions to be modelled, the polar head groups are noticeably less stable (Figure 1i and S2), suggesting none of the five detergents form stable polar interactions with the bundle, and thus implying the primary driving force for host-ligand binding to be the hydrophobic effect.

In order to investigate this further we performed circular dichroism (CD) experiments for all detergents for which we had obtained crystal structures. CD spectra recorded for H1 (at a concentration of 200 μM) in the presence of 200 μM of each detergent revealed C8E6, Mega-10 and F6OPC to exert a negligible effect on the helicity of H1 (as indicated by a peak at 204 nm), with CTAB and C12E9 significantly increasing the helicity of H1 (Figure 2a and Table S2). CD-monitored variabletemperature experiments revealed a similar trend, with T1/2 increases (relative to apo-H1 (i.e. H1 in the absence of guests)) in the range of 0.5 -1.6 °C for C8E6, Mega-10 and F6OPC, and 8.8 °C and 7.4 °C for C12E9 and CTAB, respectively (Figure 2b, S3 and Table S2). Interestingly, the largest increase in T1/2 was observed for the detergents with the longest lipid tails (CTAB and C12E9), further indicating hydrophobic effect to be the primary force driving the H1-detergent binding process.

In order to further explore the influence of the length of the detergent lipid tail on binding, we obtained and studied analogues of CTAB with alkyl tails composed of 14 (TTAB), 12 (DoTAB), 10 (DTAB) and 8 carbons (OTAB). CD-monitored addition of these analogues into solutions of H1 (at equimolar concentrations) revealed a clear trend: that increasing the length of the alkyl chain increases bundle stability, as measured by changes (increases) in % folding (Figure 3a and Table 1), with % folding increases in the range of 3 -4 % for OTAB, DTAB and DoTAB, and of 24 % and 29 % for TTAB and CTAB, respectively. CD-monitored variable-temperature studies revealed a similar trend, with increases in alkyl chain length increasing thermal stability of the helix bundle (Figure 3b). With the aim of assessing the H1-detergent binding properties in more detail, OTAB, DTAB, DoTAB, TTAB and CTAB were sequentially titrated into solutions of apo-H1 (Figure S4). Hill plot fitting of the CDmonitored titration data revealed a good fit for the H1-TTAB and H1-CTAB combinations. For the two well-fitted combinations, we extracted [L]1/2 -i.e. the ligand concentration required to occupy half of the binding sites -by assuming that the receptor state is the 6-helix bundle. [L]1/2 values of 7.78 mM and 0.25 mM were determined for TTAB and CTAB, respectively (Figure S4). The [L]1/2 value determined for Please do not adjust margins Please do not adjust margins CTAB (and previously for F6OM 24 ) indicates that oligourea helix bundles such as H1 are amenable to bind detergent guests with promising affinity, but through a mechanism which yet appears to be based largely if not exclusively on the hydrophobic components of the guests and bundle (interior). We thus anticipate that through rational engineering and optimisation of the H1 bundle -focussing on the currently under-exploited (with respect to guest binding) solvent-exposed residues of the bundle -we will be able to further increase the affinity, and potentially even selectivity, of host-guest binding of this aqueous foldamer helix-bundle.

Conclusions

In conclusion, we have demonstrated detergents of diverse polar chemotypes (a linear saccharide, oligo ethylene glycols, a quaternary ammonium, and a phospho zwitterion) can adaptively bind to the H1 oligourea helix bundle in water. Investigation of a series of detergents displaying a shared polar chemotype but varying alkyl tails suggested the primary driving force for the binding to be the hydrophobic effect, which is consistent with our previous observation of oligourea-sequence dependent binding for the homologous system. 24 Further studies exploiting structure-activity relationship-based optimization of the aqueous foldamer helix-bundle assembly may lead to the creation of protein mimics with tailor-made recognition properties for amphipathic guests with selectivity for distinct polar head groups and carbon chains. b The midpoint of the transition (T1/2) values was estimated by fitting temperature-dependent CD data to a simple two-state Boltzmann unfolding model using OriginPro 9.0 (See Figure S3).

Figure 1

 1 Figure 1 (a) Chemical structure of the oligourea motif. (b) Sequence of amphiphilic oligourea foldamer H1 and its pentad repeat structure. (c -h) Crystal structures of the H1 6-helix bundle bound by six ligand molecules (i.e. H1-Ligand complex) (ligands: (c) OGP 24 , (d) Mega-10, (e) C8E6, (f) C12E9, (g) CTAB and (h) F6OPC). H1 helices (in cartoon (left) or in surface (right) models) are colored green and white for clarity. Ligands are shown as stick models with carbons coloured magenta. Hydrogens are omitted for clarity. Nitrogen, Oxygen, Fluorine and Phosphorus are coloured blue, red, cyan and orange, respectively. (i) Electron density map (2mFo -DFc) at a σ level of 1.0 of the H1-CTAB complex focused on the CTAB.

Figure 2

 2 Figure 2 (a) CD spectra and (b) temperature-dependent CD spectra of H1 ([H1] = 200 μM) in the absence (i.e. apo-H1) or presence of ligands ([Ligand] = 200 μM). MRE, molar residual ellipticity (deg cm 2 dmol -1 residue -1 ); MRE204, MRE at 204 nm.

Figure 3

 3 Figure 3 (a) CD spectra and (b) temperature-dependent CD spectra of H1 ([H1] = 200 μM) in the absence (i.e. apo-H1) or presence of ligands ([Ligand] = 200 μM).

Table 1

 1 Biophysical analysis based on CD experiments of H1-CTAB analogue complexes.

	Ligand	% increase in folding a	T1/2 (°C) b	Temperature-dependent adj. R 2
	No ligand	-	46.9	0.9958
	OTAB	3	46.8	0.9937
	DTAB	4	47.1	0.9950
	DoTAB	4	47.4	0.9929
	TTAB	24	49.7	0.9971
	CTAB	29	54.3	0.9974

a % increase in folding values (% increase of MRE204 of interest versus MRE204 of H1 alone) at a ligand concentration of 200 μM and H1 concentration of 200 μM.

This journal is © The Royal Society of Chemistry 20xx J. Name., 2013, 00, 1-3 | 3

Acknowledgements

This work was supported in part by the Agence Nationale de la Recherche (ANR) grants ANR-17-CE07-0020. Post-doctoral fellowships to S.H.Y. from IdEx Bordeaux (ANR-10-IDEX-03-02), a program of the French government managed by the ANR, from ANR-17-CE07-0020, and from Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2021R1A6A3A03040187) are gratefully acknowledged. A Marie Skłodowska-Curie postdoctoral fellowship (H2020-MSCA-IF-2014, project #661247) to A.R. is also gratefully acknowledged. We thank the SOLEIL and ESRF synchrotrons for providing access to data collection facilities. This work has benefited from the facilities and expertise of IECB Biophysical and Structural Chemistry platform (BPCS), CNRS UAR3033, Inserm US001, Univ. Bordeaux Notes and references

Conflicts of interest

The authors declare no conflict of interest.

Please do not adjust margins

Table of Contents (graphics and text)

Detergents bearing diverse polar head groups including ionic, zwitterionic and non-ionic can adaptively bind to oligourea helix bundle through hydrophobic effect in water.