{'fraction_non_alphanumeric': 0.05672325518728106, 'fraction_numerical': 0.015225006736728644, 'mean_word_length': 4.062063086104007, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Composite convex minimization involving self-concordant-like cost functions

The self-concordant-like property of a smooth convex function is a new analytical structure that generalizes the self-concordant notion. While a wide variety of important applications feature the self-concordant-like property, this concept has heretofore remained unexploited in convex optimization. To this end, we develop a variable metric framework of minimizing the sum of a"simple"convex function and a self-concordant-like function. We introduce a new analytic step-size selection procedure and prove that the basic gradient algorithm has improved convergence guarantees as compared to"fast"algorithms that rely on the Lipschitz gradient property. Our numerical tests with real-data sets shows that the practice indeed follows the theory.


Introduction
In this paper, we consider the following composite convex minimization problem: where f is a nonlinear smooth convex function, while g is a "simple" possibly nonsmooth convex function. Such composite convex problems naturally arise in many applications of machine learning, data sciences, and imaging science. Very often, f measures a data fidelity or a loss function, and g encodes a form of low-dimensionality, such as sparsity or low-rankness.
To trade-off accuracy and computation optimally in large-scale instances of (1), existing optimization methods invariably invoke the additional assumption that the smooth function f also has an L-Lipschitz continuous gradient (cf., [11] for the definition). A highlight is the recent developments on proximal gradient methods, which feature (nearly) dimension-independent, global sublinear convergence rates [3,9,11]. When the smooth f in (1) also has strong regularity [15], the problem (1) is also within the theoretical and practical grasp of proximal-(quasi) Newton algorithms with linear, superlinear, and quadratic convergence rates [5,8,17]. These algorithms specifically exploit second order information or its principled approximations (e.g., via BFGS or L-BFGS updates [13]).
In this paper, we do away with the Lipschitz gradient assumption and instead focus on another structural assumption on f in developing an algorithmic framework for (1), which is defined below.
for t ∈ R and M f > 0, where ϕ(t) := f (x + tu) for any x ∈ dom(f ) and u ∈ R n . Definition 1 mimics the standard self-concordance concept ([10, Definition 4.1.1]) and was first discussed in [1] for model consistency in logistic regression. For composite convex minimization, self-concordant-like functions abound in machine learning, including but not limited to logistic regression, multinomial logistic regression, conditional random fields, and robust regression (cf., the references in [2]). In addition, special instances of geometric programming [6] can also be recast as (1) where f ∈ F scl .
The importance of the assumption f ∈ F scl in (1) is twofold. First, it enables us to derive an explicit step-size selection strategy for proximal variable metric methods, enhancing backtracking-line search operations with improved theoretical convergence guarantees. For instance, we can prove that our proximal gradient method can automatically adapt to the local strong convexity of f near the optimal solution to feature linear convergence under mild conditions. This theoretical result is backed up by great empirical performance on real-life problems where the fast Lipschitz-based methods actually exhibit sublinear convergence (cf. Section 4). Second, the self-concordant-like assumption on f also helps us provide scalable numerical solutions of (1) for specific problems where f does not have Lipschitz continuous gradient, such as special forms of geometric programming problems.
Contributions. Our specific contributions can be summarized as follows: 1. We propose a new variable metric framework for minimizing the sum f +g of a self-concordant-like function f and a convex, possibly nonsmooth function g. Our approach relies on the solution of a convex subproblem obtained by linearizing and regularizing the first term f , and uses an analytical step-size to achieve descent in three classes of algorithms: first order methods, second order methods, and quasi-Newton methods. 2. We establish both the global and the local convergence of different variable metric strategies. We pay particular attention to diagonal variable metrics since in this case many of the proximal subproblems can be solved exactly. We derive conditions on when and where these variants achieve locally linear convergence. When the variable metric is the Hessian of f at each iteration, we show that the resulting algorithm locally exhibits quadratic convergence without requiring any globalization strategy such as a backtracking linesearch. 3. We apply our algorithms to large-scale real-world and synthetic problems to highlight the strengths and the weaknesses of our variable-metric scheme.
Relation to prior work. Many of the composite problems with self-concordantlike f , such as regularized logistics and multinomial logistics, also have Lipschitz continuous gradient. In those specific instances, many theoretically efficient algorithms are applicable [3,5,8,9,11,17]. Compared to these works, our framework has theoretically stronger local convergence guarantees thanks to the specific step-size strategy matched with f ∈ F scl . The authors of [18] consider composite problems where f is standard self-concordant and proposes a proximal Newton algorithm optimally exploiting this structure. Our structural assumptions and algorithmic emphasis here are different. Paper organization. We first introduce the basic definitions and optimality conditions before deriving the variable metric strategy in Section 2. Section 3 proposes our new variable metric framework, describes its step-size selection procedure, and establishes the convergence theory of its variants. Section 4 illustrates our framework in real and synthetic data.

Preliminaries
We adopt the notion of self-concordant functions in [10,12] to a different smooth function class. Then we present the optimality condition of problem (1).

Basic definitions
Let g : R n → R be a proper, lower semicontinuous convex function [16] and dom(g) denote the domain of g. We use ∂g(x) to denote the subdifferential of g at x ∈ dom (g) if g is nondifferentiable at x and ∇g(x) to denote its gradient, otherwise. Let f : R n → R be a C 3 (dom(f )) function (i.e., f is three times continuously differentiable). We denote by ∇f (x) and ∇ 2 f (x) the gradient and the Hessian of f at x, respectively. Suppose that, for a given x ∈ dom (f ), , we define the local norm of a given vector u ∈ R n as u

Composite self-concordant-like minimization
Let f ∈F scl (R n ) and g be proper, closed and convex. The optimality condition for (1) can be concisely written as follows: Let us denote by x ⋆ as an optimal solution of (1). Then, the condition (3) is necessary and sufficient. We also say that x ⋆ is nonsingular if ∇ 2 f (x ⋆ ) is positive definite. We now establish the existence and uniqueness of the solution x ⋆ of (1), whose proof can be found in the appendix.
Lemma 1. Suppose that f ∈F scl (R n ) satisfies Definition 1 for some M f > 0. Suppose further that ∇ 2 f (x) ≻ 0 for some x ∈ dom(f ). Then the solution x ⋆ of (1) exists and is unique.
For a given symmetric positive definite matrix H, we define a generalized proximal operator prox H −1 g as: Due to the convexity of g, this operator is well-defined and single-valued. If we can compute prox H −1 g efficiently (e.g., by a closed form or by polynomial time algorithms), then we say that g is proximally tractable. Examples of proximal tractability convex functions can be found, e.g., in [14]. Using prox H −1 g , we can write condition (1) as: This expression shows that x ⋆ is a fixed point of R H (·) := prox H −1 g ((·) − H −1 ∇f (·)). Based on the fixed point principle, one can expect that the iterative sequence x k k≥0 generated by x k+1 := R H (x k ) converges to x ⋆ . This observation is made rigorous below.

Our variable metric framework
We first present a generic variable metric proximal framework for solving (1). Then, we specify this framework to obtain three variants: proximal gradient, proximal Newton and proximal quasi-Newton algorithms.

Generic variable metric proximal algorithmic framework
Given x k ∈ dom (F ) and an appropriate choice H k ∈ S n ++ , since f ∈ F scl , one can approximate f at x k by the following quadratic model: Our algorithmic approach uses the variable metric forward-backward framework to generate a sequence x k k≥0 starting from x 0 ∈ dom (F ) and update: where α k ∈ (0, 1] is a given step-size and d k is a search direction defined by: In the rest of this section, we explain how to determine the step size α k in the iterative scheme (6) optimally for special cases of H k . For this, we need the following definitions:

Proximal-gradient algorithm
When the variable matrix H k is diagonal and g is proximally tractable, we can efficiently obtain the solution of the subproblem (7) in a distributed fashion or even in a closed form. Hence, we consider H k = D k := diag(D k,1 , · · · , D k,n ) with D k,i > 0, for i = 1, · · · , n. Lemma 2, whose proof is in the appendix, provides a step-size selection procedure and proves the global convergence of this proximal-gradient algorithm.

Algorithm 1 (Proximal-gradient algorithm with a diagonal variable metric)
Initialization: Given x 0 ∈ dom(F ), and a tolerance ε > 0. for k = 0 to kmax do 1. Choose D k ∈ S n ++ (e.g., using D k := L k I, where L k is given by (11)). 2. Compute the proximal-gradient search direction d k as (7).
and update x k+1 := Otherwise, set x k+1 := x k and update D k+1 from D k . end for By our condition, the second term on the right-hand side of (10) is always positive, establishing that the sequence F (x k ) is decreasing. Moreover, as It is easy to verify that this is satisfied whenever D k ∇ 2 f (x k ). In such cases, our step-size selection ensures the best decrease of the objective value regarding the self-concordant-like structure of f (and not the actual objective instance). When β k > λ k , we scale down D k until β k ≤ λ k . It is easy to prove that the number of backtracking steps to find D k,i is time constant. Now, by using our step-size (9), we can describe the proximal-gradient algorithm as in Algorithm 1.
We combine the above analysis to obtain the following proximal gradient algorithm for solving (1). The main step in Algorithm 1 is to compute the search direction d k at Step 2, which is equivalent to the solution of the convex subproblem (7). The second main step is to compute This quantity requires the product of Hessian ∇ 2 f (x k ) of f and d k , but not the full-Hessian. It is clear that if β k = 0 then d k = 0 and x k+1 ≡ x k and we obtain the solution of (1), i.e., x k ≡ x ⋆ . The diagonal matrix D k can be updated as D k+1 := cD k for a given factor c > 1.
We now explain how the new theory enhances the standard backtracking linesearch approaches. For simplicity, let us assume D k := L k I, where I is the identity matrix. By a careful inspection of (10), we see that L k = σ max (∇ 2 f (x k )) achieves the maximum guaranteed decrease (in the worst case sense) in the objective. There are many principled ways of approximating this constant based on the secant equation underlying the quasi-Newton methods. In Section 4, we use Barzilai-BenTal's rule: We then deviate from the standard backtracking approaches. As opposed to, for instance, checking the Armijo-Goldstein condition, we use a new analytic condition (i.e., Step 5 of Algorithm 1), which is computationally cheaper in many cases. Our analytic step-size then further refines the solution based on the worst-case problem structure, even if the backtracking update satisfies the Armijo-Goldstein condition. Surprisingly, our analysis also enables us to also establish local linear convergence as described in Theorem 1 under mild assumptions. The proof can be found in the appendix.
k≥0 be a sequence generated by Algorithm 1. Suppose that the sub-level set for k sufficiently large then the sequence x k locally converges to x ⋆ at a linear rate, where σ * min and σ * max are the smallest and the largest eigenvalues of ∇ 2 f (x ⋆ ), respectively.
Linear convergence: According to Theorem 1, linear convergence is only possible when the condition number κ of the Hessian at the true solution satisfies κ = σ * max /σ * min < 3. While this seems too imposing, we claim that, for most f and g , this requirement is not too difficult to satisfy (see also the empirical evidence in Section 4). This is because the proof of Theorem 1 only needs the smallest and the largest eigenvalues of ∇ 2 f (x ⋆ ), restricted to the subspaces of the union of x ⋆ − x k for k sufficiently large, to satisfy the conditions imposed by ρ * . For instance, when g is based on the ℓ 1 -norm/the nuclear norm, the differences x ⋆ − x k have at most twice the sparsity/rank of x ⋆ near convergence. Given such subspace restrictions, one can prove, via probabilistic assumptions on f (cf., [1]), that the restricted condition number is not only dramatically smaller than the full condition number κ of the Hessian ∇ 2 f (x ⋆ ), but also it can even be dimension independent with high probability.

Proximal-Newton algorithm
The case H k ≡ ∇ 2 f (x k ) deserves a special attention as the step-size selection rule becomes explicit and backtracking-free. The resulting method is a proximal-Newton method and can be computationally attractive in certain big data problems due to its low iteration count.
The main step of the proximal-Newton algorithm is to compute the proximal-Newton search direction d k as: Then, it updates the sequence x k by: where α k ∈ (0, 1] is the step size. If we set α k = 1 for all k ≥ 0, then (13) is called the full-step proximal-Newton method. Otherwise, it is a damped-step proximal-Newton method. First, we show how to compute the step size α k in the following lemma, which is a direct consequence of Lemma 2 by taking H k ≡ ∇ 2 f (x k ).
k≥0 be a sequence generated by the proximal-Newton scheme (13) starting from x 0 ∈ dom (F ). Let λ k and r k be as defined by (8). If we choose the step-size α k = r −1 k ln (1 + r k ) then: Moreover, this step-size α k is optimal (w.r.t. the worst-case performance).
Next, Theorem 2 proves the local quadratic convergence of the full-step proximal-Newton method, whose proof can be found in the appendix.
Theorem 2 rigorously establishes where we can take full steps and still have quadratic convergence. Based on this information, we propose the proximal-Newton algorithm as in Algorithm 2.

Algorithm 2 (Prototype proximal-Newton algorithm)
Initialization: Given x 0 ∈ dom (F ) and σ ∈ (0, σmin(∇ 2 f (x 0 )) ln(4/3)]. for k = 0 to kmax do 1. Compute s k by (12). Then, define d k := s k − x k and λ k : The most remarkable feature of Algorithm 2 is that it does not require any globalization strategy such as backtracking line search for global convergence. Complexity analysis. First, we estimate the number of iterations needed when λ k ≤ σ to reach the solution x k such that λ k √ σ k ≤ ε for a given tolerance ε > 0. Based on the conclusion of Theorem 2, we can show that the number of iterations of Algorithm 2 when λ k > σ does not exceed k max := log 2 ln(2M f ε) ln(2σ) . Finally, we estimate the number of iterations needed when λ k > σ. From Lemma 3, we see that for all k ≥ 0 we have λ k ≥ σ and r k ≥ σ. Therefore, the number of

Proximal quasi-Newton algorithm
In many applications, estimating the Hessian ∇ 2 f (x k ) can be costly even though the Hessian is given in a closed form (cf., Section 4). In such cases, variable metric strategies employing approximate Hessian can provide computation-accuracy tradeoffs. Among these approximations, applying quasi-Newton methods with BFGS updates for H k would ensure its positive definiteness. Our analytic stepsize procedures with backtracking automatically applies to the BFGS proximalquasi Newton method, whose algorithm details and convergence analysis are omitted here.

Numerical experiments
We use a variety of different real-data problems to illustrate the performance of our variable metric framework using a MATLAB implementation. We pick two advanced solvers for comparison: TFOCS [4] and PNOPT [8]. TFOCS hosts accelerated first order methods. PNOPT provides a several proximal-(quasi) Newton implementations, which has been shown to be quite successful in logistic regression problems [8]. Both use sophisticated backtracking linesearch enhancements. We benchmark all algorithms with performance profiles [7].
A performance profile is built based on a set S of n s algorithms (solvers) and a collection P of n p problems. We first build a profile based on computational time. We denote by T p,s := computational time required to solve problem p by solver s. We compare the performance of algorithm s on problem p with the best performance of any algorithm on this problem; that is we compute the performance ratio r p,s := Tp,s min{T p,ŝ :ŝ∈S} . Now, letρ s (τ ) := 1 np size {p ∈ P : r p,s ≤τ } forτ ∈ R + . The functionρ s : R → [0, 1] is the probability for solver s that a performance ratio is within a factorτ of the best possible ratio. We use the term "performance profile" for the distribution functionρ s of a performance metric. In the following numerical examples, we plotted the performance profiles in log 2 -scale, i.e. ρ s (τ ) := 1 np size {p ∈ P : log 2 (r p,s ) ≤ τ := log 2τ }.

Sparse logistic regression
We consider the classical logistic regression problem of the form [19]: where x ∈ R p is an unknown vector, µ is an unknown bias, and y (j) and w j are observations where j = 1, · · · , N . The logistic term in (16) is self-concordant-like with M f := max w (j) 2 [1]. In this case, the smooth term in (16) has Lipschitz gradient, hence several fast algorithms are applicable. Figure 1 illustrates the performance profiles for computational time (left) and the number of prox-operations (right) using the 36 medium size problems 1 . For comparison, we use TFOCS-N07, which is Nesterov's 2007 two prox-method; and TFOCS-AT, which is Auslender and Teboulle's accelerated method, PNOPT with L-BFGS updates, and our algorithms: proximal gradient and proximal-Newton. From these performance profiles, we can observe that our proximal gradient is the best one in terms of computational time and the number of proxoperations. In terms of time, proximal-gradient solves upto 83.3% of problems with the best performance, while these numbers in TFOCS-N07 and PNOPT-LBFGS are 2.7%. Proximal Newton algorithm solves 11.1% problems with the best performance. In prox-operations, proximal-gradient is also the best one in 75% of problems.
We now show an example convergence behavior of our proximal-gradient algorithm via two large-scale problems with ρ = 0.1. The first problem is rcv1 train.binary with the size p = 20242 and N = 47236 and the second one is real-sim with the size p = 72309 and N = 20958. For comparison, we use TFOCS-N07 and TFOCS-AT. For this example, PNOPT (with Newton, BFGS, and L-BFGS options) and our proximal-Newton do not scale and are omitted. Figure 2 shows that our simple gradient algorithm locally exhibits linear convergence whereas the fast method TFOCS-AT shows a sublinear convergence rate. The variant TFOCS-N07 is the Nesterov's dual proximal algorithm, which exhibits oscillations but performs comparable to our proximal gradient method   , 568), respectively. For these data sets, the relative performance of the algorithms is surprisingly consistent across various regularization parameters.

Restricted condition number in practice
The convergence plots in Figure 2 indicate that the linear convergence condition in Theorem 1 may be satisfied. In fact, in all of our tests, the proximal gradient algorithm exhibits locally linear convergence. Hence, to see if Remark 1 is grounded in practice, we perform the following test on the a#a dataset 1 , consisting of small to medium problems. We first solve each problem with the proximal-Newton method up to 16 digits of accuracy to obtain x ⋆ , and we calculate ∇ 2 f (x ⋆ ). We then run our proximal gradient algorithm until convergence, and during its linear convergence, we record , and take the ratios of the maximum and the minimum to estimate the restricted condition number for each problem. Figure 3 illustrates that while the condition number of the Hessian ∇ 2 f (x ⋆ ) can be extremely large, as the algorithm navigates to the optimal solution x ⋆ through sparse subspaces, the restricted condition number estimates are in fact very close to 3. Given that algorithm still exhibit linear convergence for the Pr oble ms ( a 1, · · ·, a 9) R e s t r ic t e d c ondit ion numb e r e s t imat e Fig. 3. Restricted condition number (left), and condition number (right) estimates cases # = 2, 3, 4, 5, 6, 8 (where our condition cannot be met), we believe that the tightness of our convergence condition is an artifact of our proof and may be improved.

Sparse multinomial logistic regression
For sparse multimonomial logistic regression, the underlying problem is formulated in the form of (1), which the objective function f is given as: where X can be considered as a matrix variable of size m × p formed from X (1) , · · · , X (m) . Other vectors, y (j) and w (j) are given as input data for j = 1, . . . , N . The function f has closed form gradient as well as Hessian. However, forming a full hessian matrix ∇ 2 f (x) is especially costly in large scale problems when N ≫ 1. In this case, proximal-quasi-Newton methods are more suitable. First, we show in Lemma 4 that f satisfies Definition 1, whose proof is in the appendix. The performance profiles of 20 small-to-medium size problems 1 are shown in Figure 4 in terms of computational time (left) as well as number of proxoperations (right), respectively. Both proximal-gradient method and proximal-Newton method with BFGS have good performance. They can solve unto 55% and 45% problems with the best time performance, respectively. These methods are also the best in terms of prox-operations (70% and 30%).

A sytlized example of a non-Lipschitz gradient function for (1)
We consider the following convex composite minimization problem by modifying one of the canonical examples of geometric programming [6]: where Ω is a simple convex set, a i , c ∈ R n and b i ∈ R are random, and g is the ℓ 1 -norm. After some algebra, we can show that f satisfies Definition 1 We implement our proximal-gradient algorithm and compare it with TFOCS and PNOPT-LBFGS. However, TFOCS breaks down in running this example due to the estimation of Lipschitz constant, while PNOPT is rather slow. Several tests on synthetic data show that our algorithm outperforms PNOPT-LBFGS.
As an example, we show the convergence behavior of both these methods in Figure 5 where we plot the accuracy of the objective values w.r.t. the number of prox-operators for two cases of ε = 10 −6 and ε = 10 −12 , respectively. As we can see from this figure that our prox-gradient method requires many fewer proxoperations to achieve a very high accuracy compared to PNOPT. Moreover, our method is also 20 to 40 times faster than PNOPT in this numerical test.

Conclusions
Convex optimization efficiency relies significantly on the structure of the objective functions. In this paper, we propose a variable metric method for minimizing the sum of a self-concordant-like convex function and a proximally tractable convex function. Our framework is applicable in several interesting machine learning problems and do not rely on the usual Lipschitz gradient assumption on the smooth part for its convergence theory. A highlight of this work is the new analytic step-size selection procedure that enhances backtracking procedures. Thanks to this new approach, we can prove that the basic gradient variant of our framework has improved local convergence guarantees under certain conditions while the tuning-free proximal Newton method has locally quadratic convergence. While our assumption on the restricted condition number in Theorem 1 is not deterministically verifiable a priori, we provide empirical evidence that it can hold in many practical problems. Numerical experiments on different applications that have both self-concordant-like and Lipschitz gradient properties demonstrate that the gradient algorithm based on the former assumption can be more efficient than the fast algorithms based on the latter assumption. As a result, we plan to look into fast versions of our gradient scheme as future work.

A Appendix: Composite convex minimization involving self-concordant-like cost functions
We derive some fundamental properties of self-concordant-like functions, introduce the notion of scaled proximal operators, and provide the full-proofs of the technical results in the main text.

A.1 Properties of self-concordant-like functions
We define u, u , following the notations in [10,12]. An equivalent definition of self-concordant-like functions is provided by the following theorem [1].
and only if for any x, u 1 , u 2 , u 3 ∈ R n , we have: Let f : R n → R be an M f -self-concordant-like function. Then: a) The function f q (x) := α+ a, x +(1/2) Ax, x +f (x) is M f -self-concordantlike, for any α ∈ R, a ∈ R n , and positive symmetric matrix A : We will repeatedly use the following inequalities in the rest of this appendix.
Next, we prove (20). Consider the function ψ(t) := ∇ 2 f (y t )u, u = u 2 yt for some u ∈ R n . We have ψ(0) = u 2 x and ψ(1) = u 2 y . By Theorem 3, we obtain: We get (20) by integrating both sides over [0, 1]. Now, we prove (21). By the mean-value theorem, we have: Applying the right-hand side of (20), we obtain: which leads to the right-hand side of (21). Similarly, we can prove the left-hand side of (21). Finally, (22) is a direct consequence of (21), since: Hence, all the statements of Theorem 4 are proved.
A.2 Proof of Lemma 1: The existence and uniqueness of x ⋆ Consider the level set L F (x) := {y ∈ dom (F ) : F (y) ≤ F (x)}. By (22) and the convexity of g, for any y ∈ L F (x) and v ∈ ∂g(x), we have: where we use the notations r x (y) and λ x (y) in Theorem 4. Applying the Cauchy-Schwarz inequality and we obtain: Note that λ x (y) ≥ σ min x − y 2 , where σ min is the smallest eigenvalue of ∇ 2 f (x). This inequality implies that: The function ψ(t) := tω * (t) is increasing in [0, +∞) and its values are also in [0, +∞), so its inverse ψ −1 is also increasing in [0, +∞). This implies that the level set L f (x) is bounded, and thus problem (1) has a solution x ⋆ . Let y = x ⋆ be a point in dom (f ). By (22) and the optimality condition (3), for any v ⋆ ∈ ∂g(x ⋆ ), we have: Summing up the two inequalities, we obtain By (20) and the non-singularity of ∇ 2 f (x) for some x ∈ dom (f ), the function f is strictly convex, and the uniqueness of x ⋆ follows.

A.3 Proof of Lemma 2: Step-size selection strategy
Since s k is the solution of the convex subproblem (7), we have 0 ∈ ∇f (x k ) + D k d k + ∂g(s k ), or, equivalently: Using (25) and (22), we can derive: Since x k+1 = (1 − α k )x k + α k s k , it follows by the convexity of g and (25) that: Summing up (26) and (27), we obtain the following estimate: It is easy to check that the function ψ k is concave, and attains the maximum at τ * k = 1 r k ln 1 + with the maximum value: Moreover, τ * k ≤ 1 due to the condition β 2 k r k ≤ (e r k − 1)λ 2 k . By choosing α k = τ * k , we obtain (10). Since α k maximizes ψ k , it is optimal in the sense of the worst-case performance.
which implies: From (32), we can easily show that: Therefore, with a proper choice of L k such that ρ * ∈ [0, 1/2), and forr k sufficiently small such that γ k < 1, the sequence x k k≥0 generated by Algorithm 1 converges linearly to x ⋆ .

A.5 Proof of Theorem 2: Local quadratic convergence
Let us define P x k (u) := P g ∇ 2 f (x k ) (u) with H k := ∇ 2 f (x k ), S x k (u) := ∇ 2 f (x k )u− ∇f (u), and e x k (u, v) := ∇ 2 f x k − ∇ 2 f (u) (v − u). Since s k is the minimizer of (12), we have 0 ∈ ∇f x k + ∇ 2 f x k s k − x k + ∂g s k . Using this optimality condition and the condition α k = 1, we can write: We defineλ k+1 := s k+1 − x k+1 x k . It follows by Lemma 5 and the triangle inequality that: x k + e x k s k+1 , s k+1 − e x k x k , s k * x k (37) We can prove, in a similar way as in the proof of (31), that the first term of (37) can be upper-bounded as: By using (20) and the fact that e x k (x k , s k ) = 0, the second term of (37) can be upper-bounded as: Combining (37), (38), and (39) and assuming that e r k < 2, we have: By using (20), we estimate λ k+1 as: x k+1 ≤ e r kλ 2 k+1 , and thus, provided that r k ≤ ln (2), we obtain an upper bound for λ k+1 as: λ k+1 ≤ e r k /2 (e r k − r k − 1) r k (2 − e r k ) λ k .
Furthermore, we note that λ k ≥ σ k min (r k /M f ). Substituting these estimates into (40) we obtain the conclusions of Theorem 2.
A.6 Proof of Lemma 4: Self-concordant-like property The concavity of f is straightforward. We now prove that f is self-concordantlike. Consider the function ψ(t) := log ( m i=1 e ait+µi ), where a := (a 1 , · · · , a m ) is a fixed m-dimensional real vector. We define the polynomial P (t; a k ) := a k 1 e a1t+µ1 + · · · + a k n e ant+µn . Then we have ψ(t) = log P (t, a 0 ), and for any k ≥ 0, P (t; a k ) ′ t := dP (t;a k ) dt = P (t, a k+1 ). Applying the definition of P (t, a k ), it is straightforward to obtain the following expressions.