A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems

This paper presents a proximal bundle (PB) framework based on a generic bundle update scheme for solving the hybrid convex composite optimization (HCCO) problem and establishes a common iteration-complexity bound for any variant belonging to it. As a consequence, iteration-complexity bounds for three PB variants based on different bundle update schemes are obtained in the HCCO context for the first time and in a unified manner. While two of the PB variants are universal (i.e., their implementations do not require parameters associated with the HCCO instance), the other newly (as far as the authors are aware of) proposed one is not but has the advantage that it generates simple, namely one-cut, bundle models. The paper also presents a universal adaptive PB variant (which is not necessarily an instance of the framework) based on one-cut models and shows that its iteration-complexity is the same as the two aforementioned universal PB variants.


Introduction
Let f, h : R n → R ∪ {+∞} be proper lower semi-continuous convex functions such that dom h ⊆ dom f and h − µ · 2 /2 is convex for some µ ≥ 0, and consider the optimization problem It is said that (1) is a HCCO problem if there exist nonnegative scalars M f and L f and a first-order oracle f ′ : dom h → R n (i.e., f ′ (x) ∈ ∂f (x) for every x ∈ dom h) satisfying the (M f , L f )-hybrid condition, namely: The main goal of this paper is to study the complexity of proximal bundle methods for solving the HCCO problem (1) based on different bundle update schemes. Instead of focusing on a particular proximal bundle method, our unified approach considers a framework of proximal bundle methods based on a generic bundle update scheme (referred to as the GPB framework) and establishes a common iterationcomplexity bound for all variants belonging to it.
Method outline. Like all other proximal bundle methods, an iteration of a GPB variant solves the prox bundle subproblem where λ is the prox stepsize, and x c and Γ are the current prox-center and bundle function, respectively. Moreover, it also performs two types of iterations, i.e., serious and null ones. In a serious iteration, the prox-center is updated to x c ← x and the updated bundle function Γ + is chosen so as to satisfy Γ + ≥ ℓ f (·; x) + h where ℓ f (·; x) = f (x) + f ′ (x), · − x . In a null iteration, the prox-center does not change but Γ is updated according to a certain bundle update scheme (which is usually more restrictive than the ones in the serious iterations).
In order to illustrate the use of the generic bundle update scheme, this paper considers three specific well-known bundle update schemes and shows that they can all be viewed as special cases of the generic one. We now briefly describe the specific ones in the next three itemized paragraphs.
(E1) one-cut scheme: This scheme obtains Γ + as where x is as in (2) and τ ∈ (0, 1) depends on (L f , M f , µ). Clearly, if Γ is the sum of h and an affine function underneath f , then so is Γ + .
(E2) two-cuts scheme: Assume that Γ = max{A f , ℓ f (·; x − )} + h where A f is an affine function satisfying A f ≤ f and x − is the previous iterate. This scheme sets the next bundle function Γ + to one similar to Γ but with (x − , A f ) replaced by (x, A + f ) where A + f = θA f +(1−θ)ℓ f (·; x − ) for some θ ∈ [0, 1] which does not depend on (L f , M f , µ).
This scheme obtains Γ + as Γ + = Γ(·; C + ) where C + is the updated bundle set obtained by possibly removing some points from C and then adding the most recent x to the resulting set.
Throughout out the paper, we refer to the GPB variants based on (E1), (E2) and (E3) as 1C-PB, 2C-PB and MC-PB, respectively. Contribution. Regardless of the parameter triple (L f , M f , µ), it is shown that the iterationcomplexity for any GPB variant to obtain aε-solution of the HCCO problem (1) (i.e., a point x ∈ dom h satisfying φ(x) − φ * ≤ε) is for a large range of prox stepsizes λ. Since 2C-PB and MC-PB methods do not rely on (L f , M f , µ), a sharper iteration-complexity bound can be obtained for them by replacing µ and (M f , L f ) in (5) byμ and (M f ,L f ), respectively, whereμ is the largest µ such that h − µ · 2 /2 is convex and (M f ,L f ) is the unique pair which minimizes M 2 f +εL f over the set of pairs (M f , L f ) satisfying the (M f , L f )-hybrid condition of f ′ . Moreover, even though this sharper complexity bound can not be shown for 1C-PB, Section 5 presents an adaptive version of this variant where τ in (3), instead of being chosen as a function of (L f , M f , µ), is adaptively searched so as to satisfy a key inequality condition. Finally, Section 5 also shows that this adaptive variant has the same iteration-complexity as that of 2C-PB and MC-PB. Related literature. Proximal bundle methods are known to be efficient algorithms for solving nonsmooth convex composite optimization (NCCO) problems, i.e., instances of (1) for which there exists M f ≥ 0 such that the hybrid condition holds with L f = 0. Some preliminary ideas towards the development of the proximal bundle method were first presented in [11,23] and formal presentations of the method were given in [12,15]. Convergence analysis of the proximal bundle method for NCCO problems has been broadly discussed in the literature and can be found for example in the textbooks [19,21]. Different bundle management policies in the context of proximal bundle methods are discussed for example in [6,7,9,18,19,22].
Iteration-complexity bounds have been established for some proximal bundle methods in the context of the NCCO problem with µ = 0 (see for example [1,5,9,14]). Papers [1,9] both consider the NCCO problem where h is the indicator function of a nonempty closed convex set, and [5] considers the NCCO problem where h is identically zero. Moreover, paper [9] obtains the first O(ε −3 ) complexity bound, and [1,5] subsequently also derive an O(ε −3 ) bound. On the other hand, a previous authors' paper [14] proposes a proximal bundle variant using a novel condition to decide whether to perform a serious or null iteration which does not necessarily yield a function value decrease. More importantly, [14] establishes the first O(ε −2 ) complexity bound for a large range of prox stepsizes, and shows that the bound is indeed optimal.
More specialized iteration-complexity bounds in the context of the NCCO problem with µ > 0 have also been established for the proximal bundle methods studied in [9,14]. More specifically, papers [5,6] derive an O(ε −1 ) iteration-complexity bound for the proximal bundle method of [9], and [14] also establishes an O(ε −1 ) iteration-complexity bound for its proximal bundle method which, in contrast to the first one, is optimal with respect to the parameter pair (M f , µ) for a large range of prox stepsizes.
The current paper improves [14] in the following aspects: 1) it deals with the more general HCCO problem; 2) in contrast to [14], it nowhere assumes that h is Lipschitz continuous nor imposes any condition on the parameter µ, and shows that the iteration-complexity bound (5) holds for prox stepsize ranges which are larger than the ones in [14]; 3) while the proximal bundle variant of [14] is based on the bundle update scheme (E3), GPB uses a generic bundle update scheme which potentially includes many other schemes presented in the literature (such as (E1)-(E3)) and the unified analysis presented here for GPB applies to all the different proximal bundle variants contained on it; and 4) as far as the authors are aware of, it presents and analyzes for the first time a one-cut proximal bundle method for both NCCO and HCCO problems and also presents a universal variant of such method.
Another method related, and developed subsequently, to the proximal bundle method is the bundle-level method, which was first proposed in [13] and extended in many ways in [3,8,10]. These methods have been shown to have optimal iteration-complexity in the setting of the NCCO problem with h being the indicator function of a compact convex set. Since their generated subproblems do not have a proximal term, and hence do not use a prox stepsize, they are different from the ones studied in this paper. Finally, paper [4] presents a doubly stabilized bundle method for solving NCCO problems whose prox subproblems combine elements from both proximal bundle and bundlelevel methods and analyzes its asymptotic convergence (but not its iteration-complexity).
Organization of the paper. Subsection 1.1 presents basic definitions and notation used through-out the paper. Section 2 formally describes the assumptions on the HCCO problem (1), reviews the constant stepsize composite subgradient (CS-CS) method and discusses its iteration-complexity. Section 3 presents a generic bundle update scheme, describes the GPB framework and states the main results of the paper, namely, the iteration-complexity of GPB. Section 4 contains three subsections, and they provide the analysis of bounds on the number of the serious, null and total iterates, respectively. Section 5 presents the adaptive variant of 1C-PB and establishes the iterationcomplexity of it. Section 6 presents some concluding remarks and possible extensions. Appendix A provides a few useful technical results. Appendix B presents two recursive formulas and their related results. Appendix C provides the proof of the iteration-complexity for the CS-CS method, and describes an adaptive variant of CS-CS and establishes its iteration-complexity. Finally, Appendix D provides the proofs of properties of bundle update schemes (E2) and (E3).

Problem of interest and a review of the CS-CS method
This section consists of two subsections. The first one describes the main problem and the assumptions imposed on it. The second one reviews the CS-CS method and an adaptive variant of it, and describes their iteration-complexity bounds for obtaining aε-solution of the main problem.

Main problem and assumptions
The problem of interest in this paper is (1) which is assumed to satisfy the following conditions for some triple (L f , M f , µ) ∈ R 3 + : (A1) f, h ∈ Conv (R n ) are such that dom h ⊂ dom f , and a subgradient oracle, i.e., a function f ′ : dom h → R n satisfying f ′ (x) ∈ ∂f (x) for every x ∈ dom h, is available; (A2) the set of optimal solutions X * of problem (1) is nonempty; Throughout this paper, an instance of (1) means a triple (f, f ′ ; h) satisfying conditions (A1)-(A4) for some triple of parameters (L f , M f , µ) ∈ R 3 + . We now add a few remarks about assumptions (A1)-(A4). First, the set Ω ⊂ R 2 + consisting of the pairs (M f , L f ) satisfying (A3) is easily seen to be a (nonempty) closed convex set. Moreover, for a given toleranceε > 0, it is easily seen that there exists a unique pair (M f (ε),L f (ε)) which minimizes M 2 f +εL f over Ω and, without any loss of clarity, we denote this pair simply by (M f ,L f ) and define Tε Second, if there exists a pair (M f , 0) satisfying (A3), then the smallest M f with this property is denoted byM f,0 ; otherwise, if no such pair exists, then we setM f,0 := ∞. Third, it is easily seen thatM f,0 ≥ Tε ≥M f and that any one of these two inequalities can hold strictly. For example, if f = · + · 2 /2 and h ≡ 0, then we can easily see thatM f,0 = ∞,M f = 1, and Tε ∈ (1, ∞) for anyε > 0. Fourth, letting then it is well-known that (A3) implies that for every u, v ∈ dom h, In addition to the above quantities, two other ones which are used to express the complexity bounds obtained in this paper are:μ which denotes the largest quantity µ satisfying (A4), and; the distance of a given initial point x 0 to X * , i.e., Finally, for given initial point x 0 ∈ dom h and toleranceε > 0, it is said that an algorithm for solving an instance (f, f ′ ; h) of (1) hasε-iteration complexity O(T ) if its total number of iterations until it obtains aε-solution is bounded by CT where C > 0 is a universal constant.

Review of the CS-CS method
We start by reviewing the CS-CS method. The CS-CS method with initial point x 0 ∈ dom h and constant prox stepsize λ > 0, denoted by CS-CS(x 0 , λ), recursively computes its iteration sequence {x j } according to For any given universal constant C > 1, pair (M f , L f ) satisfying (A3), and toleranceε > 0, it follows from Proposition C.1 with µ =μ that CS-CS(x 0 , λ) with any stepsize λ such that , hasε-iteration complexity given by with the convention that the second term is equal to the first one whenμ = 0. (It is worth noting that the second term converges to the first one asμ ↓ 0.) In order to obtain theε-iteration complexity (11), the CS-CS method requires the knowledge of (M f , L f ) satisfying (A3) to compute a suitable λ. Subsection C.2 presents an adaptive variant of the CS-CS method which does not require such knowledge. More precisely, this adaptive variant starts with any stepsize λ 0 > 0, employs a backtracking procedure to compute a nonincreasing sequence {λ j } such that each λ j satisfies a key condition, and recursively performs iterations similar to (10). It is shown in Proposition C.3 that, without the prior knowledge of Tε, the adaptive variant of CS-CS hasε-iteration complexity given by It is worth noting that bound (12) is better than the one for the CS-CS method (i.e., (11)) due to the fact that it is expressed in terms of the tighter quantity T 2 ε instead of the estimate M 2 f +εL f .

The GPB Framework
This section contains three subsections. Subsection 3.1 describes a generic bundle update scheme that is used to perform the null iterations of a method in the GPB framework. Subsection 3.2 presents the GPB framework and Subsection 3.3 describes the main complexity results about it.

Bundle update schemes
Bundle methods discussed in the literature rely on different bundle management schemes, i.e., schemes for updating the bundle function Γ in (2) which approximates the objective function of (1). Instead of focusing on a specific bundle update scheme, we describe in this subsection a generic scheme which includes most (if not all) of the ones considered in the literature. This subsection also gives the details of the three concrete examples (E1)-(E3) of the generic bundle update scheme. We start by describing the generic bundle update scheme. For a given quadruple (Γ, where x is as in (2), ℓ f (·; x) is as in (7), andΓ ∈ C µ (φ) is such that For the sake of shortness, we denote the class of functions Γ + satisfying the above conditions as C φ (Γ, x c , λ, τ ). Clearly, the above update scheme does not completely determine Γ + but rather gives minimal conditions on it which are suitable for the complexity analysis of this paper. We now elaborate on schemes (E1)-(E3) which are members of the above class.

The GPB framework
This subsection states the GPB framework based on the generic bundle update scheme presented in Subsection 3.1. It also gives several remarks about GPB and discusses how it relates to the classical proximal point method. We start by stating GPB.
An iteration index j for which the inequality t j ≤ε/2 in step 1 is satisfied is called a serious index in which case x j (resp., y j ) is called a serious iterate (resp., auxiliary serious iterate); otherwise, j is called a null index. Moreover, we assume throughout our presentation that j = 0 is also a serious index.
We make some basic remarks about GPB. First, we refer to it as a framework since it does not completely specify how some algorithmic quantities are generated. The framework rather gives minimal conditions on these quantities which enable us to establish complexity bounds for all algorithms contained on it in a unified manner. Second, two possible ways of choosing the bundle function Γ j+1 in a serious update are: 1) Γ j+1 = ℓ f (·; x j ) + h, and 2) Γ j+1 = max{Γ j , ℓ f (·; x j ) + h}. Third, three possible concrete ways of choosing Γ j+1 in a null update have been discussed in (E1)-(E3). Fourth, y j+1 is the best (in terms of φ λ j+1 value) among the set of points {y ℓ 0 , x ℓ 0 +1 , . . . , x j+1 } where ℓ 0 denotes the largest serious index less than or equal to j + 1. Fifth, although GPB does not specify a termination criterion for the sake of shortness, all iteration-complexity bounds established in this paper are relative to the effort of obtaining aε-solution of (1). Finally, although iterationcomplexity bounds for GPB can also be established for other termination criteria (see for example Section 6 of [14]), we have omitted the details of their derivation for the sake of shortness.
We now discuss the role played by the parameter τ of GPB. First, τ is only used in step 1 for determining the class C φ (Γ j , x c j , λ, τ ) where Γ j+1 is chosen from. Second, τ has to be sufficiently close to one, i.e., τ ∈ [τ , 1) whereτ is as in (19). Third, even though some variants do not depend on the scalar τ as mentioned in the above two remarks, the analysis of GPB does. Fourth, 2C-PB and MC-PB do not depend on τ since the updates (E2) and (E3) do not. (Recall the meaning of 1C-PB, 2C-PB and MC-PC given in the sentence following (E3).) Moreover, both of these variants can be viewed as special cases of GPB with τ =τ but since their implementation do not depend on the choice of τ , they do not need to compute or estimateτ . Fifth, on the other hand, 1C-PB requires knowledge of a scalar τ as mentioned in the first and second remarks since the update (E1) depends on τ (see (3)).
We finally briefly argue that GPB can be viewed as an inexact proximal point method for solving (1). Indeed, it is easy to see that m j ≤ m * j ≤ φ λ j (y j ) where m * j := min{φ λ j (u) : u ∈ R n }, and hence that φ λ j (y j ) − m * j ≤ t j in view of (23). Hence, if j is a serious index, and hence t j ≤ε/2, it follows that y j is a (ε/2)-solution of the proximal subproblem min{φ λ j (u) : u ∈ R n }. The sequence of consecutive null iterations between two serious ones can be regarded as an iterative procedure to compute the aforementioned (ε/2)-solution. More details of such an interpretation can be found in Subsection 3.1 of [14].

Iteration-complexity results for GPB
This subsection presents the main complexity results for GPB.
The first complexity result assumes that, in addition to (f, f ′ ; h) being an instance of (1), a triple (L f , M f , µ) satisfying (A1)-(A4) is also known, and derives aε-iteration complexity bound for GPB variants, with a scalar τ obtained from (L f , M f , µ), for a large range of prox stepsizes λ.
and τ is given by then any variant of GPB with input (x 0 , λ,ε, τ ) obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by (5).
The corollary below considers the subclass of GPB methods, referred to as the τ -free GPB subclass, which do not depend on τ (and hence do not need τ as input), and derives an improved iteration-complexity bound for it. Since 2C-PB and MC-PB do not depend on τ , the result below applies to both of them.
Corollary 3.2. Let universal constant C > 0, initial point x 0 ∈ dom h, and toleranceε > 0 be given, and consider an instance (f, f ′ ; h) of (1). Then, any variant of the τ -free GPB subclass with input (x 0 , λ,ε) satisfyingε where Tε is as in (6) obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by (12).
Proof: Observe that any variant of the τ -free GPB subclass can be viewed as instance of GPB with input τ =τ and µ =μ since it does not depend on neither τ nor µ. Hence, it follows from (12) and Theorem 3.1 with (L f , M f , µ) replaced by (L f ,M f ,μ) that the conclusion of the corollary holds.
For the sake of comparing the results of this paper with the ones obtained in [14], we now state another consequence of Theorem 3.1 in which an alternativeε-iteration complexity for τ -free GPB variants applied to instances of (1) withM f,0 finite. (Recall the definition ofM f,0 is in the line below (6).) Corollary 3.3. Let universal constant C > 0, initial point x 0 ∈ dom h, and toleranceε > 0 be given, and consider an instance (f, f ′ ; h) of (1) such thatM f,0 is finite. Then, any variant of the τ -free GPB subclass with input (x 0 , λ,ε) satisfyinḡ obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by Proof: Observe that any variant of the τ -free GPB subclass can be viewed as instance of GPB with input τ = [1 + (1 + λμ)ε/(8λM 2 f,0 )] −1 and µ =μ since it does not depend on either τ or µ. Since the triple (0,M f,0 ,μ) satisfies conditions (A1)-(A4), it then follows from (12) with Tε replaced bȳ M f,0 and Theorem 3.1 with (L f , M f , µ) replaced by (0,M f,0 ,μ) that the conclusion of the corollary holds.
Before comparing the RPB method of [14] with the τ -free GPB variants of the paper, we first make two remarks about the first one in regards to the latter ones. First, the RPB method of [14] with δ =ε/2 can be viewed as a special case of τ -free GPB since: RPB uses the inequality t j ≤ε/2 to decide whether to perform a serious or null update; and, its serious and null updates, the latter of which are based on (E3), fulfill the requirements of step 1 of GPB (see Lemma D.1). Second, while the RPB method of [14] deals with instances of (1) such thatM f,0 is finite (i.e., the nonsmooth setting), the analysis presented in this paper for τ -free GPB applies to the larger class of instances of (1) such that Tε is finite (i.e., the hybrid or smooth/nonsmooth setting).
We now compare Corollary 3.3 of this paper with Corollary 3.2 of [14]. Indeed, it follows from Corollary 3.2 of [14] with (M f , µ) = (M f,0 ,μ) that RPB hasε-iteration complexity given by (28) as On the other hand, Corollary 3.3 of this paper establishes complexity bound (28) for any λ lying in the larger range (27) without imposing any condition onμ.
We now compare Corollary 3.3 of this paper with Corollary 3.3 of [14]. Indeed, it follows from Corollary 3.3 of [14] with M f =M f,0 that RPB hasε-iteration complexity O 1 ((M f,0 ) 2 d 2 0 /ε 2 ) as long (27) holds and h is (CM f,0 )-Lipschitz continuous. On the other hand, Corollary 3.3 of this paper establishes the (possibly sharper)ε-iteration complexity (28) for any λ in the same range without imposing any condition Lipschitz continuity on h.

Complexity Analysis of GPB
This section consists of three subsections. The first one provides a bound on the number of serious iterates generated by the GPB framework. The second one derives a preliminary complexity bound on the number of possible consecutive null iterates. Finally, the last subsection combines the aforementioned bounds to obtain a complexity bound on the total number of iterations performed by any algorithm in the GPB framework with prox stepsize λ arbitrarily chosen. Moreover, it also provides the proof of Theorem 3.1 as a consequence of this general complexity result.

Bounding the number of serious iterates
We start by introducing some notation and definitions. Let 0 = j 0 < j 1 < j 2 < . . . denote the serious indices of the GPB framework, and definex 0 := x 0 ,ŷ 0 := x 0 and x k := x j k ,ŷ k := y j k ,Γ k := Γ j k ,m k := m j k for every k ≥ 1.
The following result summarizes the basic properties of the above "hat" entities that follow as an immediate consequence of their definitions and the description of the GPB framework. It is worth noting that the complexity results developed in this subsection apply not only to the sequences defined in (29), but also to arbitrary sequences {x k }, {ŷ k } and {Γ k } satisfying the basic properties stated below.
Lemma 4.1. The following statements about GPB hold for every k ≥ 1: is the pair of optimal solution and optimal value of c) there holds φ(ŷ k ) −m k ≤ε/2.

Proof:
We first note that the definition ofx k in (29) and the prox-center update policy in step 2 of GPB imply thatx a) This statement directly follows from the definition ofΓ k in (29) and the fact that Γ j k ∈ C µ (φ). b) It follows from both (20) and the first identity in (23) with j = j k − 1, and relations (29) and (30) that b) holds. c) Since j k is a serious index, we have t j k ≤ε/2. Using this conclusion, (29) and the definitions of t j and φ λ in (23) and (22), respectively, we conclude that and hence that c) holds. It is worth noting that a), b), and c), can be viewed only as properties about the sequences {Γ k } and {ŷ k }, and the initial pointx 0 , since {x k : k ≥ 1} is uniquely determined by {Γ k }.
The next result provides an important recursive formula for the sequences in (29) and derives some important consequences that follow from it. Lemma 4.2. Let u ∈ dom h be given and define Then, the following statements hold: a) for every k ≥ 1, we have Proof: a) It follows from Lemma 4.1(a) and the definition of C µ (φ) thatΓ k is µ-convex, and hence that the objective function in Lemma 4.1(b) is (µ + 1/λ)-strongly convex. Using this observation, Lemma 4.1(b) and Theorem 5.25(b) of [2] with f =Γ k + ·−x k−1 2 /(2λ), x * =x k and σ = µ+1/λ, we have for the given u ∈ dom h and every k ≥ 1, Using the above inequality, Lemma 4.1(c), and the fact that Lemma 4.1(a) and the definition of C µ (φ) imply thatΓ k ≤ φ, we conclude that and hence that a) holds. b)-c) Since (32) satisfies (58) with it follows from Corollary B.2, the fact thatx 0 = x 0 and the definition of λ µ in (19) that b) and c) hold.
We are now ready to present the main result of this subsection which provides a bound on the number of serious iterates generated by GPB until it obtains aε-solution of (1). Proposition 4.3. The number of serious iterations K performed by GPB until it obtains for the first time an auxiliary serious iterateŷ K such that φ(ŷ K ) − φ * ≤ε is bounded by where λ µ is as in (31). Moreover, Proof: Lemma 4.2(b) with u = x * 0 and the definition of d 0 in (9) imply the first conclusion of the proposition, and hence that K − 1 ≤ d 2 0 /(λε). This conclusion, together with Lemma 4.2(c) with u = x * 0 , then implies (34). We note that Proposition 4.3 holds for any µ ∈ [0,μ] and λ > 0.

Bounding the number of consecutive null iterates
We assume throughout this subsection that ℓ 0 denotes an arbitrary serious index (and hence ℓ 0 is possibly equal to zero) and let B(ℓ 0 ) denote the set of all consecutive null indices j ≥ ℓ 0 + 1. Our goal in this subsection is to show that the set B(ℓ 0 ) is finite and bound its cardinality in terms of (M f ,L f ), λ,ε, d 0 and τ ∈ [τ , 1) whereτ is as in (19).
We start by making some simple observations that immediately follow from the description of GPB. For any j ∈ B(ℓ 0 ), it follows from the prox-center update policy of x c j+1 in step 2 of GPB that x c j = x ℓ 0 , and hence that in view of the definitions of Γ λ j and φ λ j in (20) and (22), respectively. We now make a few immediate observations that will be used in the analysis of this subsection. First, since (35) implies that the function φ λ j remains the same whenever j ∈ B(ℓ 0 ) and ℓ 0 remains fixed throughout the analysis of this section, we will simply denote the function φ λ j for j ∈ B(ℓ 0 ) by φ λ , i.e., Moreover, we define ℓ φ (·; x) := ℓ f (·; x) + h where ℓ f (·; x) is as in (7), and Second, in view of the definition of y j in (21) and the above relation, it then follows that Third, ℓ 1 is characterized as the first index j > ℓ 0 satisfying condition (23). The next result presents a few basic properties of the auxiliary bundle functionΓ j which is useful in the analysis.
b) It follows from the fact thatΓ j ∈ C µ (φ) and the definition of C µ (φ) thatΓ j + · −x ℓ 0 2 /(2λ) is λ −1 µ -strongly convex in view of (19). Using (40) and Theorem 5.25(b) of [2] with f =Γ j + · −x ℓ 0 2 /(2λ), x * = x j and σ = λ −1 µ , we have for every u ∈ dom h, The statement now follows from the above inequality and the definition of m j in (23). The following technical result provides an important recursive formula for {m j } which is used in Lemma 4.6 to give a recursive formula for {t j }. It is worth observing that its proof uses for the first time the condition that τ is chosen in the interval [τ , 1) whereτ is as in (19).
Proof: Using (8) with (M f , L f , u, v) = (M f ,L f , x j+1 , x j ), and the definitions of φ λ and ℓ λ φ in (37) and (38), respectively, we have This inequality, together with Lemma 4.5 and the fact that m j = φ λ (y j )−t j (see (23)), then implies where the last inequality is due to (21), (37) and the inequality a 2 −2ab ≥ −b 2 with a = 2M f x j+1 − x j and b =ε/2. The lemma now follows from the above inequality and the definition of t j+1 in (23). The next lemma gives a uniform bound on t ℓ 0 +1 which is used in Proposition 4.8 to derive a uniform bound on the maximum number of consecutive null iterates generated by GPB. Its proof uses Lemma A.3 in Appendix A where a crucial bound on x ℓ 0 − x ℓ 0 +1 is obtained.
Proof: Using both (21) and (23) with j = ℓ 0 , and the facts that φ = f +h and Γ ℓ 0 +1 ≥ ℓ f (·; x ℓ 0 )+h (see the serious update in step 1), we have where the third inequality is due to (8) with , and the last inequality is due to the fact that 2ab ≤ a 2 + b 2 for every a, b ∈ R. The conclusion of the lemma now follows from the above inequality and Lemma A.3 in Appendix A.
We are now ready to present the main result of this subsection where a bound on |B(ℓ 0 )| is obtained in terms of τ ,t andε.
wheret is as in (42) and τ is as in step 0 of GPB.
Proof: Using the inequality τ ≤ e τ −1 , and Lemmas 4.6 and 4.7, we then conclude that for every j ∈ B(ℓ 0 ), Using this observation, and noting that step 1 of GPB and the definition of B(ℓ 0 ) imply that t j >ε/2 for every j ∈ B(ℓ 0 ), it is now easy to see that the conclusion of the proposition follows.

The total iteration-complexity of GPB
This subsection establishes the total iteration-complexity of GPB. We start by providing a more general version of Theorem 3.1 which does not impose any condition on λ. Proposition 4.9. Let input quadruple (x 0 , λ,ε, τ ) ∈ dom h × R ++ × R ++ × [τ , 1] be given. Then, any variant of GPB with input (x 0 , λ,ε, τ ) obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by wheret is as in (42). Moreover, if τ is as in (25), then the total iteration-complexity becomes Proof: It follows from Propositions 4.3 and 4.8 that the first conclusion holds. Using bound (43) with τ as in (25), we conclude that the second conclusion holds.
Proposition 4.9 allows us to make one additional remark about Theorem 3.1, namely, in the unusual case where the range of λ (26) is empty, i.e., C 2 (M 2 f +εL f )d 2 0 /ε 2 < 1, it can be easily seen that (44), up to a logarithmic term, reduces to O([κ , which shows that the instances of (1) for which (26) does not hold can be trivially solved by GPB with a proper choice of the prox stepsize.
We are now ready to prove Theorem 3.1. Proof of Theorem 3.1 Defining and using (44), we conclude that O((a + 1)(b + 1)) is aε-iteration complexity bound for GPB up to a logarithmic term. We break the proof into two cases: 1) µ ≤ C(M 2 f +εL f )/ε 2 ; and 2) µ ≥ C(M 2 f +εL f )/ε 2 . First, assume that case 1 holds. Using the definition of λ µ in (19), the fact that µ ≤ C(M 2 f + εL f )/ε 2 , and the first inequality in (24), we have and hence a ≥ 1/(2C). Moreover, it follows from the definition of b in (45) and the second inequality in (24) that Using the fact that log(1 + t) ≥ t/(1 + t) for every t > 0, we easily see that log(1 + t) ≥ t/2 if t ≤ 1 and log(1 + t) ≥ log 2 > 0 if t ≥ 1. This observation with t = λµ/C and the definition of λ µ in (31) then imply that and hence that b ≥ min{1/(2C), log 2}. This inequality and the fact that a ≥ 1/(2C) imply that O((a + 1)(b + 1)) is equal to O(ab + 1). Using this observation, the definitions of a and b in (45), and the fact that λ µ ≤ λ, we then conclude that the bound O((a + 1)(b + 1)) reduces to (5), and hence that the theorem holds for case 1. Assume now that case 2 holds. Then, it follows from the definition of λ µ in (19) and the first inequality in (24) that The first inequality then implies that a ≤ 1/C in view of the first identity in (45), and hence that O((a + 1)(b + 1)) is O(b + 1). We will now derive a bound on b. Indeed, using the definitions of b and λ µ in (45) and (19), respectively, we have where the inequality is due to the second inequality in (48) and the first inequality in (24). Hence, the bound O(b + 1) becomes Finally, it is easy to see that bound (5) becomes the above bound when µ ≥ C(M 2 f +εL f )/ε 2 , and hence that the theorem holds for case 2.
It is worth pointing out how condition (24) on the prox stepsize is used in the proof of Theorem 3.1. Indeed, the first inequality in (24) is used to obtain the inequality in (46), the last inequality in (48), and the inequality in (49), while the second inequality in (24) is used to obtain (47).

A One-Cut Adaptive Proximal Bundle Method
This section presents an adaptive version of the 1C-PB method, referred to as the 1C-APB method which, in contrast to 1C-PB, does not require the availability of a triple (L f , M f , µ) satisfying (A3) and (A4), and which has the sameε-iteration complexity as described in Corollary 3.2 for an arbitrary τ -free GPB variant.
We start by stating the 1C-APB method.
We now make some remarks about the 1C-APB method. First, in contrast to the GPB framework which does not specify how some quantities are generated, 1C-APB is a well-determined method since it specifies Γ j+1 in both the serious and null updates, the latter of which computes Γ j+1 based on the one-cut bundle update scheme (E1). Second, the iteration count j is only increased in step 4 and when that happens the key inequality is satisfied. Before that happens, 1C-APB can loop a few times between steps 2 and 4 and, in the process, computes intermediate quantities which depends on τ and (with some abuse of notation) are all denoted by Γ j+1 , x j+1 , y j+1 , m j+1 and t j+1 . Third, since τ 0 = 0 <τ , it may happen that many τ j 's (possibly even the last one) will also be less thanτ . Hence, 1C-APB can not be viewed as a special case of GPB since the latter one requires its constant τ to be greater than or equal tō τ .
The following lemma summarizes some basic properties of the sequence {τ j } generated by 1C-APB. b) if ℓ 0 is a serious index of the 1C-APB method, then the next serious index ℓ 1 happens and satisfies where λμ := λ/(1 + λμ), and Tε andt are as in (6) and (42), respectively.
Proof: a) It follows from the way τ is updated in step 4 that 1 − τ + = (1 − τ )/2 where τ + is the updated τ . It follows from Lemma 4.6 that if τ j ≥τ then τ ℓ = τ j for every ℓ > j. Using the above two observations, we then easily conclude that the number of times τ changes is bounded by ⌈log (1/(1 −τ ))⌉. The conclusion in b) now follows from the last conclusion and the definition ofτ in (19). b) It follows from Lemma 5.1 that for every j ∈ B(ℓ 0 ), Using the inequality above, the fact that t ℓ 1 ≤ε/2 (see Lemma 5.1(b)) and Proposition 4.8, we conclude that The above inequality, the fact that λμ := λ/(1 + λμ) and the definition ofτ in (19) immediately imply b). We now discuss theε-iteration complexity of 1C-APB.
Proof: First, the same analysis as in Subsection 4.1 shows that the number of serious iterations of 1C-APB is bounded by (33) with µ =μ. Hence, this conclusion and Proposition 5.2(b) imply that theε-iteration complexity for 1C-APB is given by (52). Letting a = λμT 2 ε /ε and b be as in (45), and using (52), we have O((a + 1)(b + 1)) is theε-iteration complexity for 1C-APB up to a logarithmic term. Using the assumption (26) and following a similar argument as in the proof of Theorem 3.1, we conclude that theε-iteration complexity for 1C-APB is (up to a logarithmic term) given by (12).
We end this section by discussing the complexity of 1C-APB in terms of the total number of resolvent evaluations of ∂h, i.e., an evaluation of the point-to-point operator (I + α∂h) −1 (·) for some α > 0. Observe first that the computation of x j+1 in step 3 of 1C-APB requires one resolvent evaluation of ∂h due to (20) and the fact that Γ j+1 has the form (15). Hence, the total number of resolvent evaluations of ∂h is bounded by the sum of the total number of iterations performed by 1C-APB and the total number of times τ is updated. Thus, it follows from Theorem 5.3 and Proposition 5.2(a) that the total number of resolvent evaluations of ∂h is bounded by the sum of (52) and (51). Since (52) is larger than (51), we then conclude that the total number of resolvent evaluations of ∂h is on the order of (52).

Concluding Remarks
We briefly discuss the relationship between GPB variants and other methods. First, it is worth noting that the 1C-PB method has slight similarity with the dual averaging (DA) method of [17] since both methods explore the idea of aggregating cuts into a single one. However, there are essential differences between the two methods: 1) DA uses a fixed prox-center throughout the process, while 1C-PB updates prox-centers during its serious iterations; and 2) DA uses variable prox stepsizes, while GPB uses constant ones. Second, the CS-CS method can be viewed as a special instance of any GPB variant with a relatively small prox stepsize.
We finally discuss some possible extensions of our analysis in this paper. First, throughout the paper, we assume f is convex and h is µ-convex. A natural question is whether, under the weaker assumption that φ is µ-convex, which includes the case where f is µ f -convex, h is µ h -convex and µ = µ f + µ h , the results are still valid for GPB directly applied to the HCCO problem (1). The advantage of this approach, if doable, is that it would not require the knowledge of µ f . Second, theε-iteration complexity of GPB is optimal in the nonsmooth case, however it is not optimal in the hybrid case. It would be interesting to design a variant of GPB which incorporates Nesterov's acceleration scheme and then show that it is optimal for HCCO problems. Third, proximal bundle methods have not been studied in the context of stochastic subgradient oracles, and hence it is interesting to investigate such methods by using the techniques developed in this paper. which in turn, in view of the facts that φ(w ℓ 0 ) ≥ φ * = φ(x * 0 ) and µ ≥ 0, and the inequality (a + b) 1/2 ≤ a 1/2 + b 1/2 for any a, b ≥ 0, yields This inequality and the triangle inequality then imply that where the last inequality is due to (34) and the fact that x ℓ 0 is equal to one of serious iterateŝ x k preceding the last one generated by GPB. On the other hand, since 0 <λ < λ and Γ ℓ 0 +1 ∈ Conv (R n ), it follows from Lemma A.1 with (Γ, x) = (Γ ℓ 0 +1 , x ℓ 0 ) that This inequality together with (56) and the fact that λ/λ = max{1, 2λL f } clearly implies (55).

B Useful recursive formulas
The following two technical results play important roles in the complexity analysis of both GPB and CS-CS. We start by stating the following simple result for general sequences of nonnegative scalars.
Proof: Multiplying (57) by Θ j−1 and summing the resulting inequality from j = 1 to k, we have Hence, the lemma holds. The next result discusses a special case of the previous lemma in which θ j = θ and δ j = δ for every j ≥ 1.
Then, the following statements hold: Proof: a) This statement directly follows from the description of A-CS. b) Using (8) with (M f , L f , u, v) = (M f ,L f , x j+1 , x j ) and the inequality that a 2 + b 2 ≥ 2ab for a, b ∈ R, we have where the last inequality is due to the assumption that λ j ≤ε/(4T 2 ε ). Hence, (61) holds with λ j+1 = λ j . c) This statement clearly follows from steps 2 and 3 of A-CS. d) This statement follows trivially from b) and c), and the way λ is updated in step 2.
Using the same reasoning but with Γ replaced byΓ, we conclude that the above set is also ∂Γ(x), and hence that 1 where the inclusion is due to (2). Now the second identity in (14) immediately follows. As a consequence, we conclude that Γ + ∈ C φ (Γ, x 0 , λ, τ ) in view of its definition in Subsection 3.1.