{'fraction_non_alphanumeric': 0.05689052015828411, 'fraction_numerical': 0.009692034180191546, 'mean_word_length': 3.782638507953922, 'pattern_counts': {'":': 0, '<': 0, '<?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': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An optimal variant of Kelley's cutting-plane method

We propose a new variant of Kelley's cutting-plane method for minimizing a nonsmooth convex Lipschitz-continuous function over the Euclidean space. We derive the method through a constructive approach and prove that it attains the optimal rate of convergence for this class of problems.


Introduction
In this paper, we focus on unconstrained nonsmooth convex minimization problems, where information on the objective can only be gained through a first-order oracle, which returns the value of the objective and an element in its subgradient at any point in the problem's domain. Problems of this type often arise in real-life applications either as the result of a transformation that was applied on a problem (such as Benders' decomposition [5]) or by some inherent property of the problem (e.g., in an eigenvalue optimization problem).
One of the earliest and most fundamental methods for solving nonsmooth convex problems is Kelley's cutting plane method (or, the Kelley method, for short), which was introduced by Kelley in [11] and also independently by Cheney and Goldstein [6]. The method maintains a polyhedral model of the objective, and at each iteration updates this model according to the first-order information at a point where the model predicts that the objective is minimal. Despite the elegant and intuitive nature of this method, the Kelley method suffers from very poor performance, both in practice and in theory [22]. The source of the poor performance seems to be the instability of the solution, where the iterates of the method tend to be far apart and at locations where the accuracy of the model is poor.
The main objective of this work is to present a new method for minimizing a nonsmooth convex Lipschitz-continuous function over the Euclidean space, which is surprisingly similar to the Kelley method, yet attains the optimal rate of convergence for this class of problems. We derive this method and its rate of convergence through a constructive approach which further develops the recent framework we introduced in [8]. In the later work, a novel approach was developed to derive new complexity bounds for a broad class of first order schemes for smooth convex minimization. The approach is based on the observation that the efficiency estimate of a method can be formulated as an optimization problem and once this is done, it is possible to optimize the parameters of the method to achieve the best possible efficiency estimate (this can be viewed as some kind of a "meta-optimization" approach, where we optimize the parameters of an optimization method). Very recently, these results were further analyzed in [12] to derive optimized first-order methods for smooth convex minimization.
Although the main contribution of this work is entirely theoretical, it should be noted that the resulting method also offers some practical advantages over existing bundle methods. One of the main advantages is that the method allows the implementation to choose at each iteration between two types of steps: a "standard" step, which, as in all bundle methods, requires solving an auxiliary convex optimization program, and an "easy" step which involves only a subgradient step with a predetermined step size. The efficiency estimate of the method remains valid regardless of the choices a specific implementation makes, thereby allowing the implementation to find a balance between accuracy and speed (without performing aggregation on the iterates, which affects the accuracy of the model).
One limitation of the method is that it requires choosing the number of iterations to be performed in advance. However, this limitation is not severe since the "standard" steps provide as a by-product a bound on the worst-case absolute inaccuracy at the end of the method's run, hence once the desired accuracy has been achieved, the implementation can choose to perform only "easy" steps thereby quickly ending the execution of the method.
Literature The first successful approach for overcoming the instability in the Kelley method, known as the bundle method, was introduced by Lemaréchal [17] and also independently by Wolfe [25]. In the bundle approach, the instability in the Kelley method is tackled by introducing a regularizing quadratic term in the objective, thereby forcing the next iterate to remain in close proximity to the previous iterates, where the model is more accurate. The bundle approach proved to be very fruitful, and yielded many variations on the idea, see for instance [1,14,19] and references therein. The bundle method and its variants also proved to perform very well in practice, however, a theoretical rate of convergence is not available for most variants, and for the variants where a rate of convergence was established, it was shown to be suboptimal [16]. Another fundamental approach is the level bundle method, introduced by Lemaréchal et al. [18]. The idea behind this approach is that the level sets of the polyhedral model of the objective are "stable", and therefore they should be used instead of the complete model. Building on this idea, at each iteration the method performs a projection of the previous iterate on a carefully selected level set of the model, then updates the model according to the first-order information at the resulting point. Several extensions to the method were proposed, including a restricted memory variant [15] and a variant for handling non-Euclidean metrics [3]. The method was shown to possess an optimal rate of convergence, however, note that the constant factor in the bound is not optimal, and leave room for improvement.
Finally, let us mention that quite a few additional approaches were proposed. Among them are trust-region bundle methods [24] and the bundle-newton method [20], where the objective is approximated by a combination of polyhedral and quadratic functions. For a comprehensive survey, we refer the reader to [21].
Outline of the paper. The paper is organized as follows. In Section 2, we present the new Kelley-Like Method (KLM), and state our main result: an optimal rate of convergence (Theorem 2.1). The motivation for the method and our approach is described in Section 3. In Sections 4-6, we provide a detailed description of the construction of the proposed method and prove its rate of convergence. We conclude the main body of the work, in Section 7, were we discuss a limited-memory version of the method and present some additional cases where the approach presented here is applicable. Finally, in Appendix A, we give a new lower-complexity bound for the class of convex and Lipschitz-continuous minimization problems, which shows that the KLM attains the best possible rate of convergence for this class of problems.
Notation. For a convex function f , its subgradient at x is denoted by ∂f (x) and we use f ′ (x) to denote some element in ∂f (x). We also denote f * = min x f (x) and x * = x * f ∈ argmin x f (x). The Euclidean norm of a vector x is denoted as x . We use e i for the i-th canonical basis vector, which consists of all zero components, except for its i-th entry which is equal to one. For an optimization problem (P ), val(P ) stands for its optimal value. For a symmetric matrix A, A 0 means A is positive semidefinite (PSD).
To simplify some expressions, we often write A 0 for a non-symmetric matrix A: this should be interpreted as 1 2 (A + A T ) 0.

The Algorithm and its Rate of Convergence
In this section we present our main results, namely the new proposed algorithm and its rate of convergence.

The Algorithm: a Kelley-Like Method (KLM)
Consider the minimization problem min{f (x) : x ∈ R p }, where f : R p → R is convex and Lipschitz-continuous with constant L > 0. The method described below assumes that x * ∈ argmin x f (x) is located inside a ball of radius R > 0 around a given point x 0 ∈ R p and requires knowing in advance the number of iterations to be performed, N. The method proceeds as follows: Algorithm KLM Initialization: (The zeroth iteration.) Set Iteration #M: At the Mth iteration (1 ≤ M ≤ N − 1), the method arbitrarily chooses between two types of steps: In the first type (the "standard step"), we set m ∈ argmin 1≤i≤M f (x i ) and solve Let y * , ζ * and t * be an optimal solution to the primal variables of problem (B M ), and let β * be the optimal dual multiplier that corresponds to the constraint f (x m )−Lζ ≤ t. The second type of step (the "easy step") is a subgradient step with the previously selected step size µ: Output: The output is given by a convex combination of the best step from the first s steps and the ergodic combination of the last N − s steps: Note that if the method chooses to perform an "easy" step at every iteration, it simply reduces to the subgradient method with a constant step size. Also note that the "standard" step shares the computational simplicity of the main step in the Kelley method (cf. next section), where the two iteration rules differ only in the introduction of the optimization variable ζ and in the inclusion of the second constraint in (B M ).

An Optimal Rate of Convergence for KLM
We now state the efficiency estimate of the method, which shows that the new method is optimal for the class of nonsmooth minimization with convex and Lipschitz-continuous functions (see Appendix A and also [22,23]).
Theorem 2.1. Supposex N is generated by Algorithm KLM, and let s be the index of the last iteration where a "standard" step was taken (or zero, when no such step was taken), then f Note that although the rate of convergence is of same order as for the level bundle method [18], which to the best of our knowledge has the best known efficiency estimate on a bundle method, the constant term here is smaller by a factor of two. Hence, the proposed method requires a quarter of the steps in order to the reach the same worst-case absolute inaccuracy.
The rest of this paper is devoted to the detailed construction of the proposed Algorithm KLM and to the proof of Theorem 2.1.

A New Look at the Kelley Method
Consider the problem min x∈R p f (x), where f (x) is convex, nonsmooth, and Lipschitz-continuous with constant L. For a given set of trial points, Assuming that x * f ∈ argmin x f (x) lies inside a compact set, which we take here as {x : x − x 0 ≤ R} for some x 0 ∈ R p and R > 0, the Kelley method chooses the next iterate, x M +1 , by solving (Kelley) x M +1 ∈ argmin Alternatively, we can write the previous rule as the following functional optimization problem: where the two formulations are equivalent since the solution to the inner minimization problem reduces exactly to f M inside the ball x − x 0 ≤ R. The well-known inefficient nature of the method is now apparent: the method chooses the next iterate as one that minimizes the best-case function value, which is not a natural strategy when we are interested in obtaining a bound on the worst-case absolute inaccuracy, f (x M +1 ) − f * . This motivates us to consider the following alternative strategy.

The Proposed Approach
Since we are interested in deriving a bound on the worst-case behavior of the absolute inaccuracy, a natural approach, given a set of trial points, , might be to choose the next iterate in a way that the worst-case absolute inaccuracy is minimized, i.e., It appears, however, that this greedy approach forces the resulting iterates to be too conservative. In fact, numerical tests show that in some cases the sequence generated by this approach does not even converge to a minimizer of f ! We therefore take a global approach and attempt to minimize a bound on the worst-case behavior of the entire sequence, i.e., instead of choosing only the next iterate x M +1 , given some N > M, we look for a sequence x M +1 , . . . , x N for which the absolute inaccuracy at the last iterate, x N , is minimized. In order to accomplish this, we need to assume some form of structure on the sequence {x 1 , . . . , x N }.
Let {v 1 , . . . , v r } be an orthonormal set that spans Hereafter, we consider sequences x M +1 , . . . , x N that are generated according to a firstorder method of the form j,k ∈ R that depend only on the data available at the current stage (i.e., L, R and J M ). Note that the first summation is redundant here and can be expressed using the other terms, however, including it will significantly simplify the following analysis.
For sequences of this form, given h = (h (i) j,k ), the worst-case absolute inaccuracy at x N is, by definition, the solution to Therefore, the problem of finding step sizes h such that the worst-case absolute inaccuracy at x N is minimized can be expressed by Note that obtaining an optimal solution for (P M ) is not necessary. Indeed, suppose that for any h we can find a (preferably easy) upper bound Q M (h) for P M (h), then it follows that hence a method with a "good" worst-case absolute inaccuracy might be found by minimizing Q M (h) with respect to h instead of P M (h). The analysis developed in the forthcoming two sections show how to achieve this, and serves two main goals: • Derive a tractable upper-bound for the worst-case absolute inaccuracy expressed via problem (P M ).
• Show that the derivation of this bound leads itself to the construction of Algorithm KLM.

A Tractable Upper-Bound for (P M )
Problem (P M (h)) (and hence problem (P M )) is a difficult abstract optimization problem in infinite dimension through the functional constraint on ϕ. Inspired by the approach developed in [8], we start by formulating a finite dimensional relaxation of the problem.

A Finite Dimensional Relaxation of (P M )
To relax (P M ) into a finite dimensional problem, we need to tackle the constraint "ϕ ∈ C L , ϕ is convex", which states that for all For that purpose, we introduce the variables and for ease of notation, we set We now relax P M (h) by replacing the function variable ϕ with the new variables and by introducing constraints that follow from the application of the subgradient inequality (4.1) and the Lipschitz-continuity of ϕ (4.2) at the points x 1 , . . . , x N , x * . Minimizing the resulting problem with respect to h, we reach the following minimax problem in finite dimension: Recall that δ j , g j and x j , j = 1, . . . , M, are given in advance (these are the trial points) and are considered as the problem's data.
It appears that this minimax problem (which clearly is not convex-concave) remains nontrivial to tackle. We therefore consider a relaxation obtained by removing some con-straints: The omitted constraints can be shown to be inactive. However, this is not necessary for the following arguments as we are currently only interested in finding an upper bound on the absolute inaccuracy.
As before, the inner maximization problem is denoted by (P I M (h)), and we have Our first main objective is now to derive a tractable convex minimization problem which is an upper-bound for the minimax problem (P I M ). The first step in that direction is the derivation of a semidefinite programming relaxation of the inner maximization problem P I M (h). At this juncture, the reader might naturally be wondering why we do not derive directly a dual problem of the inner maximization to reduce our minimax problem to a minimization problem. It turns out that the SDP relaxation derived below enjoys a fundamental monotonicity property (see Lemma 6.1), which will play a crucial role in the proof of the main complexity result Theorem 2.1.

Relaxing The Inner Maximization Problem to an SDP
We proceed by performing a semidefinite relaxation on P I M (h), the inner maximization problem of ( then it is straightforward to verify that the following identities hold Now, by using (4.4) in (P I M ) and by relaxing the definition of X to v T i Xv j = v i , v j and X 0, we reach the following problem, whose inner maximization problem is an SDP:

Transforming the Minimax SDP to a Minimization Problem
To transform the minimax problem (P II M ) into a minimization problem, we now use duality. More precisely, as shown below, by using Lagrangian duality for the inner maximization problem in (P II M ) we derive a nonconvex (bilinear) semidefinite minimization problem whose optimal value coincides with the one of (P II M ).
Moreover, we have val(P II M ) = val(P III M ). Proof. Consider the inner maximization problem in (P II M ). We attach the dual variables to each of its constraints as follows: Recalling that δ i and g T i Xx i = g i , x i − x 0 are fixed for i = 1, . . . , M, and that the set {v 1 , . . . , v r } is orthonormal, the Lagrangian for this maximization problem is given by The dual objective function is then defined by Since L 1 (δ; a, b) is linear in the variables δ i , i = M + 1, . . . , N, * , the first maximization problem is equal to zero whenever i.e., when (a, b) ∈ Λ, and is equal to infinity otherwise. Likewise, the second maximization is equal to zero whenever W 0, and is equal to infinity otherwise. Therefore, the dual problem of the inner maximization P II M (h) reads as

A Tight Convex SDP Relaxation for (P III M )
At this stage, the minimization problem (P III M ) we have just derived remains a nonconvex (bilinear) problem. Indeed, note that the vectors x i depend on the optimization variable h, hence the terms a i,j (x i − x j ) and b i x i in (P III M ) are bilinear. We will now show that it is possible to derive a tight convex relaxation for this problem. This will be achieved through two main steps as follows.
Step I: Linearizing the bilinear SDP. As just noted, the terms a i,j (x i − x j ) and b i x i in (P III M ) are bilinear. Here we linearize these terms by introducing new variables ξ i,j and ψ i,j such that (4.5) Using (4.5) to eliminate the bilinear terms in (P III M ) yields the following linear SDP: Since any feasible point for (P III M ) can be transformed using (4.5) to a feasible point for (P IV M ) without affecting the objective value, we have val(P IV M ) ≤ val(P III M ). (4.6) As a first step in establishing inequality in the other direction (and therefore equality), we introduce the following lemma, which shows how to recover a feasible point for (P III M ) from a feasible point for (P IV M ) provided that the point satisfies a certain condition. Lemma 4.2. Suppose that (a, b, c, d, ξ, ψ, Φ) is feasible for (P IV M ) and satisfies Then by taking 1 In order to avoid overly numerous special cases, we adopt the convention 0 0 = 0.
we get that (h, a, b, c, d, Φ) is feasible for (P III M ) and attains the same objective value.
Proof. It is enough to verify that the linearization identity (4.5) is satisfied for the chosen values of h. First, when i−1 j=1 a i,j + b i = 0, recalling that we use the convention 0 0 = 0, the identity (4.5) follows immediately from the assumption (4.7) and since the step sizes are all zeros. Suppose i−1 j=1 a i,j + b i > 0, then substituting the term x i in (4.5) by its definition in (4.3), we get that for every i = M + 1, . . . , N where the last equality follows from the choice of h.
In order to establish that the relaxation performed in this step is indeed tight, it is enough to show that condition (4.7) holds for an optimal solution of (P IV M ). However, before we can show how to obtain an optimal solution with the required property, we need to perform an additional transformation on the problem, which in turn will also be very useful when deriving the steps of Algorithm KLM in Section 5.
Step II: Simplifying the problem (P IV M ). An equivalent and significantly simpler form of problem (P IV M ) can be derived using the matrix completion theorem. Consider the PSD constraint in (P IV M ) in its explicit form,  Then by the properties of PSD matrices, Q 0 implies that the principal minors of Q are also PSD. As a result, we get that the problem obtained by replacing Q 0 with constraints of the form Q {1,i}×{1,i} 0, is a relaxation of (P IV M ), and thus val(P V M ) ≤ val(P IV M ). As we shall prove below, it turns out that this relaxation is, in fact tight, i.e., val(P V M ) = val(P IV M ). To establish this result, we need the following lemma, which is a special case of the matrix completion theorem [10].
Then by taking q i,j = q j,i = q 1,i q 1,j q 1,1 , (4.8) for i, j = 2, . . . , n, i = j, we get that the n × n matrix (q i,j ) is positive semidefinite.
Proof. Suppose q 1,1 = 0, then by the properties of PSD matrices, q 1,i and q i,1 must also be equal to zero. By adopting the convention 0 0 = 0, we get that q i,j = q j,i = 0 for i, j = 2, . . . , n, hence the matrix (q i,j ) is diagonal and the result is trivial. Now assume q 1,1 > 0 and let γ = (q 1,1 , . . . , q 1,n ) T , then the claim follows immediately by observing that the matrix (q i,j ) is the sum of the positive semidefinite rank-one matrix q −1 1,1 γγ T and the nonnegative diagonal matrix diag(0, q 2,2 − q 2 1,2 /q 1,1 , . . . , q n,n − q 2 1,n /q 1,1 ). The promised tightness of the relaxation performed in this step now follows.  we get that (a * , b * , c * , d * , ξ * , ψ * , Φ * ) is an optimal solution for (P IV M ). In particular, we have val(P IV M ) = val(P V M ).
Proof. Observing that the minors of Q selected in (P V M ) have the same form as in the premise of Lemma 4.3 with n = 1 + r + (N − M), we get that using the choice (4.9), the relations (4.8) are satisfied, hence Q is PSD and the first constraint in (P IV M ) is satisfied for (a * , b * , c * , d * , ξ * , ψ * , Φ * ). Now, examining (P IV M ), we see that the variables Φ i,j for i = j, ξ i,j and ψ i,j , do not participate in constraints beside the first constraint or in the objective, hence we conclude that (a * , b * , c * , d * , ξ * , ψ * , Φ * ) is feasible for (P IV M ) and furthermore val(P IV M ) ≤ val(P V M ). Since we have already established that val(P V M ) ≤ val(P IV M ), the proof is complete.

Another consequence of Lemma 4.3 is the tightness of the relaxation performed in
Step I, allowing us to complete our main goal of this section. Proof. Let (a * , b * , c * , d * , Φ * i,i ) be an optimal solution for (P V M ). Then from Corollary 4.1 we get that by taking ξ * , ψ * , and Φ * as in (4.9), the point (a * , b * , c * , d * , ξ * , ψ * , Φ * ) is optimal for (P IV M ). Observing that from (4.9) we get that b * i = 0 implies ξ * i,j = 0 and ψ * i,j = 0, then it follows that assumption (4.7) is satisfied, hence Lemma 4.2 is applicable on (a * , b * , c * , d * , ξ * , ψ * , Φ * ). As a result, the optimal value of (P IV M ) is attainable by (P III M ), and since we also have val(P IV M ) ≤ val(P III M ) (see (4.6)), we conclude that val(P III M ) = val(P IV M ), proving the desired claim. where the solution of (P V M ) provides a tractable upper bound. We are now left with our second main goal, namely to derive the steps of algorithm KLM as defined through problem (B M ) in Section 2.

Derivation of Algorithm KLM
At first glance, problem (P V M ) does not seem to share much resemblance to problem (B M ). We now proceed to show that this convex SDP problem admits a pleasant equivalent convex minimization reformulation over a simplex in R M +1 , and that this representation is, in fact, the dual of problem (B M ).

Reducing (P V M ) to a Convex Minimization Problem Over the Unit Simplex
The form (P V M ) allows us to derive analytical optimal solutions to some of the optimization variables. First, for any fixed (a, b, d), it is easy to see that the minimization with respect to Φ and c yields the optimal solutions Therefore, recalling that {v 1 , . . . , v r } is an orthonormal set that spans g 1 , . . . , g M , we get , Next, observe that for any fixed (a, b) the minimization with respect to d is also immediate and yields Plugging this in the last form of the problem, we reach Now, fixing b, the above minimization problem is a linear program in the variable a, which, as shown by the following lemma, can be solved analytically.
where an optimal solution is given by otherwise, Proof. Observe that if we fix a i,j for j > M, the constraints in Λ have the form and we get that the problem is separable into N − M minimization problems over a simplex. This implies that the optimal solution can be attained by setting a * i,j = 0 for all j ∈ {1, . . . , M} \ {m} (i.e., for all indices except for an index for which δ j is minimal). Using this assignment, the objective now reads N i=M +1 a i,m δ m , and Λ is reduced to (taking into account all variables): Summing up the constraints in Λ, we get which means that the optimal value for the objective is M i=1 b i δ m . It is now straightforward to verify that the given solution (5.5) is feasible and attains the optimal value of the problem, hence the proof is complete.
Invoking Lemma 5.1, we can write problem (5.4) in the following form: To complete this step, note that if b * is an optimal solution of the last convex problem then optimality conditions imply that we must have b * M +1 = · · · = b * N . We can therefore assume, without affecting the optimal value of the problem, that b M +1 = · · · = b N , hence, by introducing the variable β Therefore, using this in (5.7), we have shown Proposition 5.1. The convex SDP problem (P V M ) admits the equivalent convex minimization formulation and we have val(P V M ) = val(P V I M ).

Completing the Derivation of KLM
We are now ready to complete the main goal of this section, namely the derivation of Algorithm KLM. Indeed, as shown below, it turns out that the convex problem (P V I M ) is nothing else but a dual representation of problem (B M ) defined in Section 2. More precisely, we establish that strong duality holds for the pair of convex problems (P V I M )-(B M ). Furthermore, as a by-product, we derive the desired output of the method as described in Section 2. To prove this result, we first recall the following elementary fact.
Lemma 5.2. Let D ∈ S l ++ , q ∈ R l and R > 0 be given. Then, From definitions of ξ * and ψ * in (4.9) we get that which, together with (5.11), yields an expression for x i that is independent of ξ * i,j and ψ * i,j : Now, using the definition of a * from (5.5), we reach the expression where m as in (5.6). This rule can be written in a more convenient form using a solution to the pair of convex problems (P V I M )-(B M ). For that, note that by writing x i in terms of x i−1 , breaking the computation of the last step, x N into two parts x N andx N , and applying (5.10) of Proposition 5.2, we obtain x j , (5.13) which is precisely the output of Algorithm KLM after performing a "standard" step followed by N − M − 1 "easy" steps. 6 The Rate of Convergence: Proof of Theorem 2.1 Before we proceed with the proof of Theorem 2.1, we need the following lemma, which establishes that the optimal value of (P II M ) is non-increasing during the run of the method.  + 1, . . . , N), and let (X,δ) be optimal for the inner maximization problem in (P II M +l ) when fixing h =ĥ. We proceed by constructing a matrixX and a vectorδ such that (h;X,δ) is feasible to (P II M ) and achieves the same objective value as (ĥ;X,δ) achieves for (P II M +l ). Denote byv i ,ḡ i andx i the vectors v i , g i and x i as defined for (P II M ) in (4.3), and let v i ,ĝ i andx i be the vectors v i , g i and x i that correspond to (P II M +l ), i.e., v i = e 1+i , i = 1, . . . , r, . . , M + l, j = 1, . . . , M + l, we immediately get from the subgradient inequality and the Lipschitz-continuity of f that these additional constraints hold. We conclude that (h;X,δ) is feasible for (P II M ) and attains the same objective value as does (ĥ;X,δ) for (P II M +l ). For a feasible point (h; X, δ), denote by P II M (h; X, δ) the value of the objective in (P II M ) at the given point, then we have just shown that P II M +l (ĥ;X,δ) = P II M (h;X,δ). As an immediate consequence, we get val(P II M +l ) ≤ P II M +l (ĥ;X,δ) = P II M (h;X,δ) ≤ val(P II M ), where the first inequality follow since (X,δ) is optimal for the inner maximization problem in (P II M +l ) and the last inequality follows sinceh is optimal for the outer minimization problem in (P II M ). We are now ready to give the proof of Theorem 2.1.
Proof. (Theorem 2.1.) First, we need to establish that the initialization step corresponds to the solution of (B 0 ). Indeed, observing that y * = x 0 , it is straightforward to verify that val(B 0 ) = LR/ √ N is attained for ζ * = R/ √ N , and that β * , the dual variable that corresponds to the constraint f (x m ) − Lζ ≤ t, is equal to one.
Recalling that s is the index of the last step where a "standard" step was taken, then by the definition of the "easy" steps, the sequence x s+1 , . . . , x N ,x N satisfies (5.13), where y * , ζ * and β * are given by a solution of (B s ). Leth be the vector of step sizes in (3.2) that matches x s+1 , . . . , x N −1 ,x N , then by the construction of (B s ) from (P II s ), we get thath is optimal for (P II M ), i.e., val(P II s ) = P II s (h) (we use P II s (h) to denote the optimal value of the inner maximization problem in (P II s ) with h set toh). We therefore have where the first two inequalities follow from the construction of (P II s ) and last inequality follow from Lemma 6.1 by a simple inductive argument.
Finally, since we have already established during the construction and analysis of Section 4 that the series of relaxations and transformations preserve the optimal value of the problem, we have val(P II M ) = · · · = val(P V I M ) = val(B M ) for every M, and the claim immediately follows.

Concluding remarks
Through a constructive approach, we have derived a new method for non-smooth convex minimization, which is surprisingly similar to the Kelley method, yet it attains the optimal rate of convergence. We conclude by outlining a refined version of the method, and by briefly discussing how the construction derived in this work can be extended onto some other situations as well, which often arise in nonsmooth optimization schemes/models.
A memory-limited version of Algorithm KLM. The current form of the method requires storing all of the past iterates, which can translate to a significant amount of memory for large values of N. This requirement can be eliminated, as in the aggregation technique described in [13], by observing that Lemma 6.1 makes no assumptions on the way the steps x 1 , . . . , x M are generated, hence Theorem 2.1 still holds if, at any iteration M where a "standard" step is taken, the trial point set is replaced by another set of points in a way that maintains the solution of (B M ). In fact, by a well-known result from convex optimization, if b * 1 , . . . , b * M are the optimal dual variables corresponding to the constraints by replacing these constraint with the conical combination we reach a problem that has the same optimal solution as the original problem. Hence, the trial points set can be aggregated to one scalar, , without affecting the efficiency estimate of the method. The same technique can be applied to any subset of the trial points, hence the cardinality of the trial points set can be maintained at any desired level.
Knowledge of Lower Bound on f * . When a lower bound, f , on f * is known, (e.g., though a dual bound), the constraint f ≤ ϕ * can be added to (P M ) and the analysis can continue with only little change. The resulting method turns out to be nearly the same as the method described above, where the only change is the introduction of the constraint f ≤ t to (B M ). Furthermore, the resulting efficiency estimate remains unchanged.
Extension with Inexact Subgradients. Another situation is the case where, instead of an exact subgradient, an ǫ-subgradient f ′ (x) ∈ ∂ ǫ f (x) is available for some given ǫ ≥ 0, i.e., for any y, instead of the usual subgradient inequality, we have The use of ǫ-subgradients instead of exact subgradients has some practical advantages, see e.g., [2,7] and references therein for motivating examples and for some recent work in this setting. As in the previous case, only minor changes are needed in the analysis we developed, and the resulting method turns out to be identical to the method presented in Section 2, except for the first set of constraint in (B M ), which becomes and for the efficiency estimate of the method (2.1), which turns out to be

A Appendix: a Tight Lower-Complexity Bound
In this appendix, we refine the proof from [23, Section 3.2] to obtain a new lower-complexity bound on the class of nonsmooth, convex, and Lipschitz-continuous functions, which together with the results discussed above form a tight complexity result for this class of problems. More precisely, under the setting of §2.1, we show that for any first-order method, the worst-case absolute inaccuracy after N steps cannot be better than LR √ N , which is exactly the bound attained by Algorithm KLM.
In order to simplify the presentation, and following [23, Section 3.2], we restrict our attention to first-order methods that generate sequences that satisfy the following assumption: Assumption A.1. The sequence {x i } satisfies where f ′ (x i ) ∈ ∂f (x i ) is obtained by evaluating a first-order oracle at x i .
As noted by Nesterov [23,Page 59], this assumption is not necessary and can be avoided by some additional reasoning.
The lower-complexity result is stated as follows.
Theorem A.1. For any L, R > 0, N, p ∈ N with N ≤ p, and any starting point x 1 ∈ R p , there exists a convex and Lipschitz-continuous function f : R p → R with Lipschitz constant L and x * f − x 1 ≤ R, and a first-order oracle O(x) = (f (x), f ′ (x)), such that for all sequences x 1 , . . . , x N that satisfies Assumption A.1.
Proof. The proof proceeds by constructing a "worst-case" function, on which any firstorder method that satisfies Assumption A.1 will not be able to improve its initial objective value during the first N iterations. Let f N : R p → R andf N : R p → R be defined by then it is easy to verify thatf N is Lipschitz-continuous with constant L and that is attained for x * ∈ R p such that We also denote R i,p := {x ∈ R d : x, e j = 0, i + 1 ≤ j ≤ p}.
Now, let x 1 , . . . , x N be a sequence that satisfies Assumption A.1 with f =f N and the oracle O N , where without loss of generality we assume x 1 = 0. Thenf ′ N (x 1 ) = e 1 and we get x 2 ∈ span{f ′ N (x 1 )} = R 1,p . Now, from x 2 , e 2 = · · · = x 2 , e N = 0, we get that min{i : f N (x) = x, e i } ≤ 2 and it follows by (A.1) and (A.2) that f ′ N (x 2 ) ∈ R 2,p andf ′ N (x 2 ) ∈ R 2,p . Hence, we conclude from Assumption A.1 that x 3 ∈ span{f ′ N (x 1 ),f ′ N (x 2 )} ⊆ R 2,p . It is straightforward to continue this argument to show that x i ∈ R i−1,p andf ′ N (x i ) ∈ R i,p for i = 1, . . . , N, thus x N ∈ R N −1,p . Finally, since for every x ∈ R N −1,p we havef N (x) ≥ x, e N = 0, we immediately getf which completes the proof.