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

Jiaming Liang Renato D.C. Monteiro 11footnotemark: 1 School of Industrial and
Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332-0205.
(email<EMAIL_ADDRESS>and renato.monteiro@isye.gatech.edu). This
work was partially supported by ONR Grant N00014-18-1-2077.

(October 3, 2021)

###### Abstract

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.

Key words. hybrid convex composite optimization, iteration-complexity,
proximal bundle method, universal method

AMS subject classifications. 49M37, 65K05, 68Q25, 90C25, 90C30, 90C60

##  1 Introduction

Let $f,h:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ be proper lower
semi-continuous convex functions such that
$\mathrm{dom}\,h\subseteq\mathrm{dom}\,f$ and $h-\mu\|\cdot\|^{2}/2$ is convex
for some $\mu\geq 0$, and consider the optimization problem

$\phi_{*}:=\min\left\\{\phi(x):=f(x)+h(x):x\in\mathbb{R}^{n}\right\\}.$ (1)

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^{\prime}:\mathrm{dom}\,h\to\mathbb{R}^{n}$ (i.e., $f^{\prime}(x)\in\partial
f(x)$ for every $x\in\mathrm{dom}\,h$) satisfying the $(M_{f},L_{f})$-hybrid
condition, namely: $\|f^{\prime}(u)-f^{\prime}(v)\|\leq 2M_{f}+L_{f}\|u-v\|$
for every $u,v\in\mathrm{dom}\,h$. 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 iteration-complexity 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

$x=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma(u)+\frac{1}{2{\lambda}}\|u-x^{c}\|^{2}\right\\}$
(2)

where ${\lambda}$ is the prox stepsize, and $x^{c}$ and $\Gamma$ 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}\leftarrow x$ and the updated
bundle function $\Gamma^{+}$ is chosen so as to satisfy
$\Gamma^{+}\geq\ell_{f}(\cdot;x)+h$ where $\ell_{f}(\cdot;x)=f(x)+\langle
f^{\prime}(x),\cdot-x\rangle$. In a null iteration, the prox-center does not
change but $\Gamma$ 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 $\Gamma^{+}$ as

$\Gamma^{+}=\Gamma^{+}_{\tau}:=\tau\Gamma+(1-\tau)[\ell_{f}(\cdot;x)+h]$ (3)

where $x$ is as in (2) and $\tau\in(0,1)$ depends on $(L_{f},M_{f},\mu)$.
Clearly, if $\Gamma$ is the sum of $h$ and an affine function underneath $f$,
then so is $\Gamma^{+}$.

  * (E2)

two-cuts scheme: Assume that $\Gamma=\max\\{A_{f},\ell_{f}(\cdot;x^{-})\\}+h$
where $A_{f}$ is an affine function satisfying $A_{f}\leq f$ and $x^{-}$ is
the previous iterate. This scheme sets the next bundle function $\Gamma^{+}$
to one similar to $\Gamma$ but with $(x^{-},A_{f})$ replaced by
$(x,A_{f}^{+})$ where $A_{f}^{+}=\theta A_{f}+(1-\theta)\ell_{f}(\cdot;x^{-})$
for some $\theta\in[0,1]$ which does not depend on $(L_{f},M_{f},\mu)$.

  * (E3)

multiple-cuts scheme: The current bundle function $\Gamma$ is of the form
$\Gamma=\Gamma(\cdot;C)$ where $C\subset\mathbb{R}^{n}$ is a finite set (i.e.,
the current bundle set) and $\Gamma(\cdot;C)$ is defined as

$\Gamma(\cdot;C):=\max\\{\ell_{f}(\cdot;c):c\in C\\}+h.$ (4)

This scheme obtains $\Gamma^{+}$ as $\Gamma^{+}=\Gamma(\cdot;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},\mu)$, it is
shown that the iteration-complexity for any GPB variant to obtain a
$\bar{\varepsilon}$-solution of the HCCO problem (1) (i.e., a point
$\bar{x}\in\mathrm{dom}\,h$ satisfying
$\phi(\bar{x})-\phi^{*}\leq\bar{\varepsilon}$) is

${\cal
O}_{1}\left(\min\left\\{\frac{(M_{f}^{2}+\bar{\varepsilon}L_{f})d_{0}^{2}}{\bar{\varepsilon}^{2}},\left(\frac{M_{f}^{2}+\bar{\varepsilon}L_{f}}{\mu\bar{\varepsilon}}+1\right)\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\right)$ (5)

for a large range of prox stepsizes ${\lambda}$. Since 2C-PB and MC-PB methods
do not rely on $(L_{f},M_{f},\mu)$, a sharper iteration-complexity bound can
be obtained for them by replacing $\mu$ and $(M_{f},L_{f})$ in (5) by
$\bar{\mu}$ and $(\bar{M}_{f},\bar{L}_{f})$, respectively, where $\bar{\mu}$
is the largest $\mu$ such that $h-\mu\|\cdot\|^{2}/2$ is convex and
$(\bar{M}_{f},\bar{L}_{f})$ is the unique pair which minimizes
$M_{f}^{2}+\bar{\varepsilon}L_{f}$ over the set of pairs $(M_{f},L_{f})$
satisfying the $(M_{f},L_{f})$-hybrid condition of $f^{\prime}$. Moreover,
even though this sharper complexity bound can not be shown for 1C-PB, Section
5 presents an adaptive version of this variant where $\tau$ in (3), instead of
being chosen as a function of $(L_{f},M_{f},\mu)$, 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}\geq 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 $\mu=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
${\cal O}(\bar{\varepsilon}^{-3})$ complexity bound, and [1, 5] subsequently
also derive an ${\cal O}(\bar{\varepsilon}^{-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 ${\cal O}(\bar{\varepsilon}^{-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 $\mu>0$ have also been established for the proximal bundle
methods studied in [9, 14]. More specifically, papers [5, 6] derive an ${\cal
O}(\bar{\varepsilon}^{-1})$ iteration-complexity bound for the proximal bundle
method of [9], and [14] also establishes an ${\cal O}(\bar{\varepsilon}^{-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},\mu)$
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 $\mu$, 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 bundle-level
methods and analyzes its asymptotic convergence (but not its iteration-
complexity).

Organization of the paper. Subsection 1.1 presents basic definitions and
notation used throughout 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 iteration-
complexity 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).

###  1.1 Basic definitions and notation

Let $\mathbb{R}$ denote the set of real numbers. Let $\mathbb{R}_{+}$ and
$\mathbb{R}_{++}$ denote the set of non-negative real numbers and the set of
positive real numbers, respectively. Let $\mathbb{R}^{n}$ denote the standard
$n$-dimensional Euclidean space equipped with inner product and norm denoted
by $\left\langle\cdot,\cdot\right\rangle$ and $\|\cdot\|$, respectively. Let
$\log(\cdot)$ denote the natural logarithm.

Let $\Psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ be given. Let
$\mathrm{dom}\,\Psi:=\\{x\in\mathbb{R}^{n}:\Psi(x)<\infty\\}$ denote the
effective domain of $\Psi$ and $\Psi$ is proper if
$\mathrm{dom}\,\Psi\neq\emptyset$. Moreover, a proper function
$\Psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ is $\mu$-convex for some
$\mu\geq 0$ if

$\Psi(\alpha
z+(1-\alpha)z^{\prime})\leq\alpha\Psi(z)+(1-\alpha)\Psi(z^{\prime})-\frac{\alpha(1-\alpha)\mu}{2}\|z-z^{\prime}\|^{2}$

for every $z,z^{\prime}\in\mathrm{dom}\,\Psi$ and $\alpha\in[0,1]$. The set of
all proper lower semicontinuous convex functions
$\Psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ is denoted by
$\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$. For $\varepsilon\geq 0$, the
_$\varepsilon$ -subdifferential_ of $\Psi$ at $z\in\mathrm{dom}\,\Psi$ is
denoted by
$\partial_{\varepsilon}\Psi(z):=\left\\{s\in\mathbb{R}^{n}:\Psi(z^{\prime})\geq\Psi(z)+\left\langle
s,z^{\prime}-z\right\rangle-\varepsilon,\forall
z^{\prime}\in\mathbb{R}^{n}\right\\}$. The subdifferential of $\Psi$ at
$z\in\mathrm{dom}\,\Psi$, denoted by $\partial\Psi(z)$, is by definition the
set $\partial_{0}\Psi(z)$. A convex function $\Gamma$ is called a bundle
function (with respect to $\phi$) if $\Gamma\leq\phi$ and $\Gamma$ is
$\mu$-convex. Let ${\cal C}_{\mu}(\phi)$ denote the class of bundle functions
$\Gamma$.

##  2 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 $\bar{\varepsilon}$-solution of the main problem.

###  2.1 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},\mu)\in\mathbb{R}_{+}^{3}$:

  * (A1)

$f,h\in\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$ are such that
$\mathrm{dom}\,h\subset\mathrm{dom}\,f$, and a subgradient oracle, i.e., a
function $f^{\prime}:\mathrm{dom}\,h\to\mathbb{R}^{n}$ satisfying
$f^{\prime}(x)\in\partial f(x)$ for every $x\in\mathrm{dom}\,h$, is available;

  * (A2)

the set of optimal solutions $X^{*}$ of problem (1) is nonempty;

  * (A3)

for every $u,v\in\mathrm{dom}\,h$,

$\|f^{\prime}(u)-f^{\prime}(v)\|\leq 2M_{f}+L_{f}\|u-v\|;$

  * (A4)

$h$ is $\mu$-convex.

Throughout this paper, an instance of (1) means a triple $(f,f^{\prime};h)$
satisfying conditions (A1)-(A4) for some triple of parameters
$(L_{f},M_{f},\mu)\in\mathbb{R}_{+}^{3}$.

We now add a few remarks about assumptions (A1)-(A4). First, the set
$\Omega\subset\mathbb{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 $\bar{\varepsilon}>0$, it is easily seen that there
exists a unique pair
$(\bar{M}_{f}(\bar{\varepsilon}),\bar{L}_{f}(\bar{\varepsilon}))$ which
minimizes $M_{f}^{2}+\bar{\varepsilon}L_{f}$ over $\Omega$ and, without any
loss of clarity, we denote this pair simply by $(\bar{M}_{f},\bar{L}_{f})$ and
define

$T_{\bar{\varepsilon}}:=\left(\bar{M}_{f}^{2}+\bar{\varepsilon}\bar{L}_{f}\right)^{1/2}.$
(6)

Second, if there exists a pair $(M_{f},0)$ satisfying (A3), then the smallest
$M_{f}$ with this property is denoted by $\bar{M}_{f,0}$; otherwise, if no
such pair exists, then we set $\bar{M}_{f,0}:=\infty$. Third, it is easily
seen that $\bar{M}_{f,0}\geq T_{\bar{\varepsilon}}\geq\bar{M}_{f}$ and that
any one of these two inequalities can hold strictly. For example, if
$f=\|\cdot\|+\|\cdot\|^{2}/2$ and $h\equiv 0$, then we can easily see that
$\bar{M}_{f,0}=\infty$, $\bar{M}_{f}=1$, and
$T_{\bar{\varepsilon}}\in(1,\infty)$ for any $\bar{\varepsilon}>0$. Fourth,
letting

$\ell_{f}(\cdot;x):=f(x)+\langle f^{\prime}(x),\cdot-x\rangle\quad\forall
x\in\mathrm{dom}\,h,$ (7)

then it is well-known that (A3) implies that for every
$u,v\in\mathrm{dom}\,h$,

$f(u)-\ell_{f}(u;v)\leq 2M_{f}\|u-v\|+\frac{L_{f}}{2}\|u-v\|^{2}.$ (8)

In addition to the above quantities, two other ones which are used to express
the complexity bounds obtained in this paper are: $\bar{\mu}$ which denotes
the largest quantity $\mu$ satisfying (A4), and; the distance of a given
initial point $x_{0}$ to $X^{*}$, i.e.,

$d_{0}:=\|x_{0}-x_{0}^{*}\|,\ \ \mbox{\rm where}\ \ \
x_{0}^{*}:=\mathrm{argmin}\,\\{\|x_{0}-x^{*}\|:x^{*}\in X^{*}\\}.$ (9)

Finally, for given initial point $x_{0}\in\mathrm{dom}\,h$ and tolerance
$\bar{\varepsilon}>0$, it is said that an algorithm for solving an instance
$(f,f^{\prime};h)$ of (1) has $\bar{\varepsilon}$-iteration complexity ${\cal
O}(T)$ if its total number of iterations until it obtains a
$\bar{\varepsilon}$-solution is bounded by $CT$ where $C>0$ is a universal
constant.

###  2.2 Review of the CS-CS method

We start by reviewing the CS-CS method. The CS-CS method with initial point
$x_{0}\in\mathrm{dom}\,h$ and constant prox stepsize ${\lambda}>0$, denoted by
CS-CS$(x_{0},{\lambda})$, recursively computes its iteration sequence
$\\{x_{j}\\}$ according to

$x_{j+1}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\ell_{f}(u;x_{j})+h(u)+\frac{1}{2{\lambda}}\|u-x_{j}\|^{2}\right\\}\qquad\forall
j\geq 0.$ (10)

For any given universal constant $C>1$, pair $(M_{f},L_{f})$ satisfying (A3),
and tolerance $\bar{\varepsilon}>0$, it follows from Proposition C.1 with
$\mu=\bar{\mu}$ that CS-CS$(x_{0},{\lambda})$ with any stepsize ${\lambda}$
such that
$\bar{\varepsilon}/[4C(M_{f}^{2}+\bar{\varepsilon}L_{f})]\leq{\lambda}\leq\bar{\varepsilon}/[4(M_{f}^{2}+\bar{\varepsilon}L_{f})]$,
has $\bar{\varepsilon}$-iteration complexity given by

${\cal
O}_{1}\left(\min\left\\{\frac{(M_{f}^{2}+\bar{\varepsilon}L_{f})d_{0}^{2}}{\bar{\varepsilon}^{2}},\left(\frac{M_{f}^{2}+\bar{\varepsilon}L_{f}}{\bar{\mu}\bar{\varepsilon}}+1\right)\log\left(\frac{\bar{\mu}d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\right)$
(11)

with the convention that the second term is equal to the first one when
$\bar{\mu}=0$. (It is worth noting that the second term converges to the first
one as $\bar{\mu}\downarrow 0$.)

In order to obtain the $\bar{\varepsilon}$-iteration complexity (11), the CS-
CS method requires the knowledge of $(M_{f},L_{f})$ satisfying (A3) to compute
a suitable ${\lambda}$. 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 ${\lambda}_{0}>0$, employs a backtracking
procedure to compute a nonincreasing sequence $\\{{\lambda}_{j}\\}$ such that
each ${\lambda}_{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_{\bar{\varepsilon}}$, the adaptive variant of CS-CS has
$\bar{\varepsilon}$-iteration complexity given by

${\cal
O}_{1}\left(\min\left\\{\frac{T_{\bar{\varepsilon}}^{2}d_{0}^{2}}{\bar{\varepsilon}^{2}},\left(\frac{T_{\bar{\varepsilon}}^{2}}{\bar{\mu}\bar{\varepsilon}}+1\right)\log\left(\frac{\bar{\mu}d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\right).$
(12)

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_{\bar{\varepsilon}}^{2}$ instead of the estimate
$M_{f}^{2}+\bar{\varepsilon}L_{f}$.

##  3 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.

###  3.1 Bundle update schemes

Bundle methods discussed in the literature rely on different bundle management
schemes, i.e., schemes for updating the bundle function $\Gamma$ 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
$(\Gamma,x^{c},{\lambda},\tau)\in{\cal
C}_{\mu}(\phi)\times\mathbb{R}^{n}\times\mathbb{R}_{++}\times(0,1)$ where
${\cal C}_{\mu}(\phi)$, the generic bundle update scheme returns
$\Gamma^{+}\in{\cal C}_{\mu}(\phi)$ satisfying

$\tau\bar{\Gamma}+(1-\tau)[\ell_{f}(\cdot;x)+h]\leq\Gamma^{+}$ (13)

where $x$ is as in (2), $\ell_{f}(\cdot;x)$ is as in (7), and
$\bar{\Gamma}\in{\cal C}_{\mu}(\phi)$ is such that

$\bar{\Gamma}(x)=\Gamma(x),\quad
x=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\bar{\Gamma}(u)+\frac{1}{2{\lambda}}\|u-x^{c}\|^{2}\right\\}.$
(14)

For the sake of shortness, we denote the class of functions $\Gamma^{+}$
satisfying the above conditions as ${\cal
C}_{\phi}(\Gamma,x^{c},{\lambda},\tau)$. Clearly, the above update scheme does
not completely determine $\Gamma^{+}$ 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.

  * (E1)

one-cut scheme: Given $(\Gamma,x^{c},{\lambda},\tau)\in{\cal
C}_{\mu}(\phi)\times\mathbb{R}^{n}\times\mathbb{R}_{++}\times(0,1)$, this
scheme obtains $\Gamma^{+}$ as in (3). It can be easily seen that
$\Gamma^{+}=\Gamma^{+}_{\tau}\in{\cal C}_{\mu}(\phi)$ and $\Gamma^{+}$
satisfies (13) with $\bar{\Gamma}=\Gamma$, and hence $\Gamma^{+}\in{\cal
C}_{\phi}(\Gamma,x^{c},{\lambda},\tau)$. It is easy to see that if this update
is used recursively then $\Gamma$ is always of the form

$\Gamma(\cdot)=\sum_{x\in X}\alpha_{x}\ell_{f}(\cdot;x)+h(\cdot)$ (15)

for some scalars $\\{\alpha_{x}:x\in X\\}\subset\mathbb{R}_{++}$ such that
$\sum_{x\in X}\alpha_{x}=1$.

  * (E2)

two-cuts scheme: Given
$(x^{c},x^{-},{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}_{++}$
and a function $\Gamma$ of the form
$\Gamma=\max\\{A_{f},\ell_{f}(\cdot;x^{-})\\}+h$ where $A_{f}$ is an affine
function satisfying $A_{f}\leq f$, this scheme computes $x\in\mathrm{dom}\,h$
as in (2) and sets

$\Gamma^{+}=\max\\{A_{f}^{+},\ell_{f}(\cdot;x)\\}+h$ (16)

where $A_{f}^{+}=\theta A_{f}+(1-\theta)\ell_{f}(\cdot;x^{-})$ and

$\theta\left\\{\begin{array}[]{ll}=1,&\text{ if
}A_{f}(x)>\ell_{f}(x;x^{-}),\\\ =0,&\text{ if }A_{f}(x)<\ell_{f}(x;x^{-}),\\\
\in[0,1],&\text{ if }A_{f}(x)=\ell_{f}(x;x^{-}).\end{array}\right.$ (17)

It will be shown in Lemma D.1 that $\Gamma^{+}\in{\cal C}_{\mu}(\phi)$ and
that, for any $\tau\in(0,1)$, the function $\Gamma^{+}$ satisfies (13) with
$\bar{\Gamma}=A_{f}^{+}+h$, and hence that $\Gamma^{+}\in{\cal
C}_{\phi}(\Gamma,x^{c},{\lambda},\tau)$.

  * (E3)

multiple-cuts scheme: Given
$(x^{c},{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}_{++}$ and a function
$\Gamma$ of the form $\Gamma=\Gamma(\cdot;C)$ where $C\subset\mathbb{R}^{n}$
is a finite set (i.e., the current bundle set) and $\Gamma(\cdot;C)$ is
defined as in (4). This scheme computes $x$ as in (2), chooses a bundle set
$C^{+}$ satisfying

$C(x)\cup\\{x\\}\subset C^{+}\subset C\cup\\{x\\},\quad C(x):=\\{c\in
C:\ell_{f}(x;c)+h(x)=\Gamma(x)\\},$ (18)

and then sets $\Gamma^{+}=\Gamma(\cdot;C^{+})$. It will be shown in Lemma D.2
that $\Gamma^{+}\in{\cal C}_{\mu}(\phi)$ and that, for any $\tau\in(0,1)$, the
function $\Gamma^{+}$ satisfies (13) with $\bar{\Gamma}=\Gamma(\cdot;C(x))$,
and hence that $\Gamma^{+}\in{\cal C}_{\phi}(\Gamma,x^{c},{\lambda},\tau)$.

###  3.2 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.

GPB

  * 0.

Let $x_{0}\in\mathrm{dom}\,h$, $\lambda>0$, $\bar{\varepsilon}>0$ and
$\tau\in[\bar{\tau},1)$ be given where

$\bar{\tau}=\left[1+\frac{(1+{\lambda}\bar{\mu})\bar{\varepsilon}}{8{\lambda}T_{\bar{\varepsilon}}^{2}}\right]^{-1}$
(19)

where $T_{\bar{\varepsilon}}$ is as in (6), and set $y_{0}=x_{0}$, $t_{0}=0$
and $j=0$;

  * 1.

if $t_{j}\leq\bar{\varepsilon}/2$, then perform a serious update, i.e., set
$x^{c}_{j+1}=x_{j}$ and find $\Gamma_{j+1}\in{\cal C}_{\mu}(\phi)$ such that
$\Gamma_{j+1}\geq\ell_{f}(\cdot;x_{j})+h$; else, perform a null update, i.e.,
set $x^{c}_{j+1}=x^{c}_{j}$ and find $\Gamma_{j+1}\in{\cal
C}_{\phi}(\Gamma_{j},x_{j}^{c},{\lambda},\tau)$;

  * 2.

compute

$x_{j+1}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma_{j+1}^{\lambda}(u):=\Gamma_{j+1}(u)+\frac{1}{2{\lambda}}\|u-x_{j+1}^{c}\|^{2}\right\\},$
(20)

choose $y_{j+1}\in\\{x_{j+1},y_{j}\\}$ such that

$\phi_{j+1}^{\lambda}(y_{j+1})=\min\left\\{\phi_{j+1}^{\lambda}(x_{j+1}),\phi_{j+1}^{\lambda}(y_{j})\right\\}$
(21)

where $\phi_{j}^{\lambda}$ is defined as

$\phi_{j}^{\lambda}:=\phi+\frac{1}{2{\lambda}}\|\cdot-x^{c}_{j}\|^{2},$ (22)

and set

$m_{j+1}=\Gamma_{j+1}^{\lambda}(x_{j+1}),\quad
t_{j+1}=\phi^{\lambda}_{j+1}(y_{j+1})-m_{j+1};$ (23)

  * 3.

set $j\leftarrow j+1$ and go to step 1.

An iteration index $j$ for which the inequality $t_{j}\leq\bar{\varepsilon}/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 $\Gamma_{j+1}$ in a serious update are: 1)
$\Gamma_{j+1}=\ell_{f}(\cdot;x_{j})+h$, and 2)
$\Gamma_{j+1}=\max\\{\Gamma_{j},\ell_{f}(\cdot;x_{j})+h\\}$. Third, three
possible concrete ways of choosing $\Gamma_{j+1}$ in a null update have been
discussed in (E1)-(E3). Fourth, $y_{j+1}$ is the best (in terms of
$\phi_{j+1}^{\lambda}$ value) among the set of points
$\\{y_{\ell_{0}},x_{\ell_{0}+1},\ldots,x_{j+1}\\}$ where $\ell_{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 $\bar{\varepsilon}$-solution of (1). Finally, although
iteration-complexity 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 $\tau$ of GPB. First, $\tau$
is only used in step 1 for determining the class ${\cal
C}_{\phi}(\Gamma_{j},x_{j}^{c},{\lambda},\tau)$ where $\Gamma_{j+1}$ is chosen
from. Second, $\tau$ has to be sufficiently close to one, i.e.,
$\tau\in[\bar{\tau},1)$ where $\bar{\tau}$ is as in (19). Third, even though
some variants do not depend on the scalar $\tau$ as mentioned in the above two
remarks, the analysis of GPB does. Fourth, 2C-PB and MC-PB do not depend on
$\tau$ 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 $\tau=\bar{\tau}$ but
since their implementation do not depend on the choice of $\tau$, they do not
need to compute or estimate $\bar{\tau}$. Fifth, on the other hand, 1C-PB
requires knowledge of a scalar $\tau$ as mentioned in the first and second
remarks since the update (E1) depends on $\tau$ (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}\leq
m_{j}^{*}\leq\phi_{j}^{\lambda}(y_{j})$ where
$m_{j}^{*}:=\min\\{\phi_{j}^{\lambda}(u):u\in\mathbb{R}^{n}\\}$, and hence
that $\phi_{j}^{\lambda}(y_{j})-m_{j}^{*}\leq t_{j}$ in view of (23). Hence,
if $j$ is a serious index, and hence $t_{j}\leq\bar{\varepsilon}/2$, it
follows that $y_{j}$ is a ($\bar{\varepsilon}/2$)-solution of the proximal
subproblem $\min\\{\phi_{j}^{\lambda}(u):u\in\mathbb{R}^{n}\\}$. The sequence
of consecutive null iterations between two serious ones can be regarded as an
iterative procedure to compute the aforementioned
($\bar{\varepsilon}/2$)-solution. More details of such an interpretation can
be found in Subsection 3.1 of [14].

###  3.3 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^{\prime};h)$
being an instance of (1), a triple $(L_{f},M_{f},\mu)$ satisfying (A1)-(A4) is
also known, and derives a $\bar{\varepsilon}$-iteration complexity bound for
GPB variants, with a scalar $\tau$ obtained from $(L_{f},M_{f},\mu)$, for a
large range of prox stepsizes ${\lambda}$.

######  Theorem 3.1.

Let universal constant $C>0$, initial point $x_{0}\in\mathrm{dom}\,h$,
tolerance $\bar{\varepsilon}>0$, and instance $(f,f^{\prime};h)$ of (1)
satisfying (A1)-(A4) for some parameter triple
$(L_{f},M_{f},\mu)\in\mathbb{R}^{3}_{+}$ be given. Then, if ${\lambda}$
satisfies

$\frac{\bar{\varepsilon}}{C(M_{f}^{2}+\bar{\varepsilon}L_{f})}\leq{\lambda}\leq\frac{Cd_{0}^{2}}{\bar{\varepsilon}},$
(24)

and $\tau$ is given by

$\tau=\left[1+\frac{(1+{\lambda}\mu)\bar{\varepsilon}}{8{\lambda}(M_{f}^{2}+\bar{\varepsilon}L_{f})}\right]^{-1},$
(25)

then any variant of GPB with input ($x_{0},{\lambda},\bar{\varepsilon},\tau$)
obtains a $\bar{\varepsilon}$-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
$\tau$-free GPB subclass, which do not depend on $\tau$ (and hence do not need
$\tau$ as input), and derives an improved iteration-complexity bound for it.
Since 2C-PB and MC-PB do not depend on $\tau$, the result below applies to
both of them.

######  Corollary 3.2.

Let universal constant $C>0$, initial point $x_{0}\in\mathrm{dom}\,h$, and
tolerance $\bar{\varepsilon}>0$ be given, and consider an instance
$(f,f^{\prime};h)$ of (1). Then, any variant of the $\tau$-free GPB subclass
with input $(x_{0},{\lambda},\bar{\varepsilon})$ satisfying

$\frac{\bar{\varepsilon}}{CT_{\bar{\varepsilon}}^{2}}\leq{\lambda}\leq\frac{Cd_{0}^{2}}{\bar{\varepsilon}}$
(26)

where $T_{\bar{\varepsilon}}$ is as in (6) obtains a
$\bar{\varepsilon}$-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 $\tau$-free GPB subclass can be viewed
as instance of GPB with input $\tau=\bar{\tau}$ and $\mu=\bar{\mu}$ since it
does not depend on neither $\tau$ nor $\mu$. Hence, it follows from (12) and
Theorem 3.1 with $(L_{f},M_{f},\mu)$ replaced by
$(\bar{L}_{f},\bar{M}_{f},\bar{\mu})$ 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
$\bar{\varepsilon}$-iteration complexity for $\tau$-free GPB variants applied
to instances of (1) with $\bar{M}_{f,0}$ finite. (Recall the definition of
$\bar{M}_{f,0}$ is in the line below (6).)

######  Corollary 3.3.

Let universal constant $C>0$, initial point $x_{0}\in\mathrm{dom}\,h$, and
tolerance $\bar{\varepsilon}>0$ be given, and consider an instance
$(f,f^{\prime};h)$ of (1) such that $\bar{M}_{f,0}$ is finite. Then, any
variant of the $\tau$-free GPB subclass with input
$(x_{0},{\lambda},\bar{\varepsilon})$ satisfying

$\frac{\bar{\varepsilon}}{C(\bar{M}_{f,0})^{2}}\leq{\lambda}\leq\frac{Cd_{0}^{2}}{\bar{\varepsilon}},$
(27)

obtains a $\bar{\varepsilon}$-solution of the above instance in a number of
iterations bounded (up to a logarithmic term) by

${\cal
O}_{1}\left(\min\left\\{\frac{(\bar{M}_{f,0})^{2}d_{0}^{2}}{\bar{\varepsilon}^{2}},\left(\frac{(\bar{M}_{f,0})^{2}}{\bar{\mu}\bar{\varepsilon}}+1\right)\log\left(\frac{\bar{\mu}d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\right).$
(28)

Proof: Observe that any variant of the $\tau$-free GPB subclass can be viewed
as instance of GPB with input
$\tau=[1+(1+{\lambda}\bar{\mu})\bar{\varepsilon}/(8{\lambda}\bar{M}_{f,0}^{2})]^{-1}$
and $\mu=\bar{\mu}$ since it does not depend on either $\tau$ or $\mu$. Since
the triple $(0,\bar{M}_{f,0},\bar{\mu})$ satisfies conditions (A1)-(A4), it
then follows from (12) with $T_{\bar{\varepsilon}}$ replaced by
$\bar{M}_{f,0}$ and Theorem 3.1 with $(L_{f},M_{f},\mu)$ replaced by
$(0,\bar{M}_{f,0},\bar{\mu})$ that the conclusion of the corollary holds.

Before comparing the RPB method of [14] with the $\tau$-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 $\delta=\bar{\varepsilon}/2$
can be viewed as a special case of $\tau$-free GPB since: RPB uses the
inequality $t_{j}\leq\bar{\varepsilon}/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 that
$\bar{M}_{f,0}$ is finite (i.e., the nonsmooth setting), the analysis
presented in this paper for $\tau$-free GPB applies to the larger class of
instances of (1) such that $T_{\bar{\varepsilon}}$ 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},\mu)=(\bar{M}_{f,0},\bar{\mu})$ that RPB has
$\bar{\varepsilon}$-iteration complexity given by (28) as long
$d_{0}/\bar{M}_{f,0}\leq{\lambda}\leq Cd_{0}^{2}/\bar{\varepsilon}$ and
$\bar{\mu}\leq C\bar{M}_{f,0}/d_{0}$. On the other hand, Corollary 3.3 of this
paper establishes complexity bound (28) for any ${\lambda}$ lying in the
larger range (27) without imposing any condition on $\bar{\mu}$.

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}=\bar{M}_{f,0}$ that RPB has
$\bar{\varepsilon}$-iteration complexity ${\cal
O}_{1}((\bar{M}_{f,0})^{2}d_{0}^{2}/\bar{\varepsilon}^{2})$ as long (27) holds
and $h$ is $(C\bar{M}_{f,0})$-Lipschitz continuous. On the other hand,
Corollary 3.3 of this paper establishes the (possibly sharper)
$\bar{\varepsilon}$-iteration complexity (28) for any ${\lambda}$ in the same
range without imposing any condition Lipschitz continuity on $h$.

Even though 1C-PB depends on $\tau$, it can be easily seen that its iteration-
complexity is similar to the one of Corollary 3.2 if $\tau$ lies in
$[\bar{\tau},(1+\bar{\tau})/2]$. Section 5 describes an adaptive variant of
1C-PB which: i) computes a nondecreasing $\tau$-sequence
$\\{\tau_{j}\\}\subset[\tau_{0},(1+\bar{\tau})/2]$ such that each $\tau_{j}$
satisfies a key condition; and ii) has the same $\bar{\varepsilon}$-iteration
complexity as that of Corollary 3.2.

##  4 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 ${\lambda}$ arbitrarily
chosen. Moreover, it also provides the proof of Theorem 3.1 as a consequence
of this general complexity result.

###  4.1 Bounding the number of serious iterates

We start by introducing some notation and definitions. Let
$0=j_{0}<j_{1}<j_{2}<\ldots$ denote the serious indices of the GPB framework,
and define $\hat{x}_{0}:=x_{0}$, $\hat{y}_{0}:=x_{0}$ and

$\displaystyle\hat{x}_{k}$
$\displaystyle:=x_{j_{k}},\quad\hat{y}_{k}:=y_{j_{k}},\quad\hat{\Gamma}_{k}:=\Gamma_{j_{k}},\quad\hat{m}_{k}:=m_{j_{k}}$
(29)

for every $k\geq 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 $\\{\hat{x}_{k}\\}$,
$\\{\hat{y}_{k}\\}$ and $\\{\hat{\Gamma}_{k}\\}$ satisfying the basic
properties stated below.

######  Lemma 4.1.

The following statements about GPB hold for every $k\geq 1$:

  * a)

$\hat{\Gamma}_{k}\in{\cal C}_{\mu}(\phi)$;

  * b)

$(\hat{x}_{k},\hat{m}_{k})$ is the pair of optimal solution and optimal value
of

$\min\left\\{\hat{\Gamma}_{k}(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}:u\in\mathbb{R}^{n}\right\\};$

  * c)

there holds $\phi(\hat{y}_{k})-\hat{m}_{k}\leq\bar{\varepsilon}/2$.

Proof: We first note that the definition of $\hat{x}_{k}$ in (29) and the
prox-center update policy in step 2 of GPB imply that

$\hat{x}_{k-1}=x^{c}_{j},\quad\forall j=j_{k-1}+1,\ldots,j_{k}.$ (30)

a) This statement directly follows from the definition of $\hat{\Gamma}_{k}$
in (29) and the fact that $\Gamma_{j_{k}}\in{\cal C}_{\mu}(\phi)$.

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}}\leq\bar{\varepsilon}/2$. Using this conclusion, (29) and the
definitions of $t_{j}$ and $\phi^{\lambda}$ in (23) and (22), respectively, we
conclude that

$\phi(\hat{y}_{k})+\frac{1}{2{\lambda}}\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2}-\hat{m}_{k}\leq\frac{\bar{\varepsilon}}{2},$

and hence that c) holds.

It is worth noting that a), b), and c), can be viewed only as properties about
the sequences $\\{\hat{\Gamma}_{k}\\}$ and $\\{\hat{y}_{k}\\}$, and the
initial point $\hat{x}_{0}$, since $\\{\hat{x}_{k}:k\geq 1\\}$ is uniquely
determined by $\\{\hat{\Gamma}_{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\in\mathrm{dom}\,h$ be given and define

${\lambda}_{\mu}=\frac{{\lambda}}{1+{\lambda}\mu}.$ (31)

Then, the following statements hold:

  * a)

for every $k\geq 1$, we have

$\phi(\hat{y}_{k})-\phi(u)\leq\frac{1}{2{\lambda}}\|\hat{x}_{k-1}-u\|^{2}-\frac{1}{2{\lambda}_{\mu}}\|\hat{x}_{k}-u\|^{2}+\frac{\bar{\varepsilon}}{2};$
(32)

  * b)

we have $\min_{1\leq k\leq
K}\\{\phi(\hat{y}_{k})-\phi(u)\\}\leq\bar{\varepsilon}$ for every index $K$
satisfying

$K\geq\min\left\\{\frac{\|x_{0}-u\|^{2}}{{\lambda}\bar{\varepsilon}},\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{\mu\|x_{0}-u\|^{2}}{\bar{\varepsilon}}+1\right)\right\\};$

  * c)

for every $k\geq 1$, we have
$\|\hat{x}_{k}-u\|^{2}\leq\|x_{0}-u\|^{2}+{\lambda}k\bar{\varepsilon}$.

Proof: a) It follows from Lemma 4.1(a) and the definition of ${\cal
C}_{\mu}(\phi)$ that $\hat{\Gamma}_{k}$ is $\mu$-convex, and hence that the
objective function in Lemma 4.1(b) is $(\mu+1/{\lambda})$-strongly convex.
Using this observation, Lemma 4.1(b) and Theorem 5.25(b) of [2] with
$f=\hat{\Gamma}_{k}+\|\cdot-\hat{x}_{k-1}\|^{2}/(2{\lambda})$,
$x^{*}=\hat{x}_{k}$ and $\sigma=\mu+1/{\lambda}$, we have for the given
$u\in\mathrm{dom}\,h$ and every $k\geq 1$,

$\hat{m}_{k}+\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)\|u-\hat{x}_{k}\|^{2}\leq\hat{\Gamma}_{k}(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}.$

Using the above inequality, Lemma 4.1(c), and the fact that Lemma 4.1(a) and
the definition of ${\cal C}_{\mu}(\phi)$ imply that
$\hat{\Gamma}_{k}\leq\phi$, we conclude that

$\displaystyle\phi(\hat{y}_{k})$
$\displaystyle-\phi(u)+\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)\|\hat{x}_{k}-u\|^{2}\leq\phi(\hat{y}_{k})-\hat{\Gamma}_{k}(u)+\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)\|\hat{x}_{k}-u\|^{2}$
$\displaystyle\leq\phi(\hat{y}_{k})-\hat{m}_{k}+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}\leq\frac{\bar{\varepsilon}}{2}+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}$

and hence that a) holds.

b)-c) Since (32) satisfies (58) with

$\eta_{k}=\phi(\hat{y}_{k})-\phi(u),\quad\alpha_{k}=\frac{1}{2{\lambda}}\|\hat{x}_{k}-u\|^{2},\quad\theta=1+{\lambda}\mu,\quad\delta=\frac{\bar{\varepsilon}}{2},$

it follows from Corollary B.2, the fact that $\hat{x}_{0}=x_{0}$ and the
definition of ${\lambda}_{\mu}$ 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
$\bar{\varepsilon}$-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 $\hat{y}_{K}$ such that
$\phi(\hat{y}_{K})-\phi^{*}\leq\bar{\varepsilon}$ is bounded by

$\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}+1$ (33)

where ${\lambda}_{\mu}$ is as in (31). Moreover,

$\|\hat{x}_{k}-x_{0}^{*}\|\leq\sqrt{2}d_{0}\qquad\forall
k\in\\{0,1,\ldots,K-1\\}.$ (34)

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\leq
d_{0}^{2}/({\lambda}\bar{\varepsilon})$. This conclusion, together with Lemma
4.2(c) with $u=x_{0}^{*}$, then implies (34).

We note that Proposition 4.3 holds for any $\mu\in[0,\bar{\mu}]$ and
${\lambda}>0$.

###  4.2 Bounding the number of consecutive null iterates

We assume throughout this subsection that $\ell_{0}$ denotes an arbitrary
serious index (and hence $\ell_{0}$ is possibly equal to zero) and let
$B(\ell_{0})$ denote the set of all consecutive null indices
$j\geq\ell_{0}+1$. Our goal in this subsection is to show that the set
$B(\ell_{0})$ is finite and bound its cardinality in terms of
$(\bar{M}_{f},\bar{L}_{f})$, ${\lambda}$, $\bar{\varepsilon}$, $d_{0}$ and
$\tau\in[\bar{\tau},1)$ where $\bar{\tau}$ is as in (19).

We start by making some simple observations that immediately follow from the
description of GPB. For any $j\in B(\ell_{0})$, it follows from the prox-
center update policy of $x_{j+1}^{c}$ in step 2 of GPB that
$x^{c}_{j}=x_{\ell_{0}}$, and hence that

$\displaystyle\phi^{\lambda}_{j}$
$\displaystyle=\phi+\frac{1}{2{\lambda}}\|\cdot-x_{\ell_{0}}\|^{2},$ (35)
$\displaystyle\Gamma_{j}^{\lambda}$
$\displaystyle=\Gamma_{j}+\frac{1}{2{\lambda}}\|\cdot-x_{\ell_{0}}\|^{2},$
(36)

in view of the definitions of $\Gamma_{j}^{\lambda}$ and $\phi^{\lambda}_{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
$\phi^{\lambda}_{j}$ remains the same whenever $j\in B(\ell_{0})$ and
$\ell_{0}$ remains fixed throughout the analysis of this section, we will
simply denote the function $\phi_{j}^{\lambda}$ for $j\in B(\ell_{0})$ by
$\phi^{{\lambda}}$, i.e.,

$\phi^{{\lambda}}=\phi^{\lambda}_{j}\quad\forall j\in B(\ell_{0}).$ (37)

Moreover, we define $\ell_{\phi}(\cdot;x):=\ell_{f}(\cdot;x)+h$ where
$\ell_{f}(\cdot;x)$ is as in (7), and

$\ell_{\phi}^{\lambda}:=\ell_{\phi}+\frac{1}{2{\lambda}}\|\cdot-
x_{\ell_{0}}\|^{2}.$ (38)

Second, in view of the definition of $y_{j}$ in (21) and the above relation,
it then follows that

$y_{j}\in\mathrm{Argmin}\,\left\\{\phi^{\lambda}(x):x\in\\{y_{\ell_{0}},x_{\ell_{0}+1},\ldots,x_{j}\\}\right\\}.$

Third, $\ell_{1}$ is characterized as the first index $j>\ell_{0}$ satisfying
condition (23).

The next result presents a few basic properties of the auxiliary bundle
function $\bar{\Gamma}_{j}$ which is useful in the analysis.

######  Lemma 4.4.

For every $j\in B(\ell_{0})$ and $u\in\mathrm{dom}\,h$, the following
statements hold:

  * a)

there exists $\bar{\Gamma}_{j}\in{\cal C}_{\mu}(\phi)$ such that

$\displaystyle\tau\bar{\Gamma}_{j}+(1-\tau)\ell_{\phi}(\cdot;x_{j})\leq\Gamma_{j+1},$
(39) $\displaystyle\bar{\Gamma}_{j}(x_{j})=\Gamma_{j}(x_{j}),\quad
x_{j}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\bar{\Gamma}_{j}(u)+\frac{1}{2{\lambda}}\|u-x_{\ell_{0}}\|^{2}\right\\};$
(40)

  * b)

$\bar{\Gamma}_{j}(u)+\|u-x_{\ell_{0}}\|^{2}/(2{\lambda})\geq
m_{j}+\|u-x_{j}\|^{2}/(2{\lambda}_{\mu})$ where ${\lambda}_{\mu}$ is as in
(31).

Proof: a) This statement immediately follows from the facts that
$\Gamma_{j+1}\in{\cal C}_{\phi}(\Gamma_{j},x_{j}^{c},{\lambda},\tau)$ (see the
null update in step 1) and $x_{j}^{c}=x_{\ell_{0}}$, and the definition of
${\cal C}_{\phi}(\Gamma,x_{0},{\lambda},\tau)$ in Subsection 3.1 (see (13) and
(14)).

b) It follows from the fact that $\bar{\Gamma}_{j}\in{\cal C}_{\mu}(\phi)$ and
the definition of ${\cal C}_{\mu}(\phi)$ that $\bar{\Gamma}_{j}+\|\cdot-
x_{\ell_{0}}\|^{2}/(2{\lambda})$ is ${\lambda}_{\mu}^{-1}$-strongly convex in
view of (19). Using (40) and Theorem 5.25(b) of [2] with
$f=\bar{\Gamma}_{j}+\|\cdot-x_{\ell_{0}}\|^{2}/(2{\lambda})$, $x^{*}=x_{j}$
and $\sigma={\lambda}_{\mu}^{-1}$, we have for every $u\in\mathrm{dom}\,h$,

$\bar{\Gamma}_{j}(u)+\frac{1}{2{\lambda}}\|u-x_{\ell_{0}}\|^{2}\geq\bar{\Gamma}_{j}(x_{j})+\frac{1}{2{\lambda}}\|x_{j}-x_{\ell_{0}}\|^{2}+\frac{1}{2{\lambda}_{\mu}}\|u-x_{j}\|^{2}=\Gamma_{j}^{\lambda}(x_{j})+\frac{1}{2{\lambda}_{\mu}}\|u-x_{j}\|^{2}.$

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 $\tau$ is chosen in the interval $[\bar{\tau},1)$ where
$\bar{\tau}$ is as in (19).

######  Lemma 4.5.

For every $\tau\in[\bar{\tau},1)$ and $j\in B(\ell_{0})$, we have

$m_{j+1}\geq\tau
m_{j}+(1-\tau)\left[\ell_{\phi}^{\lambda}(x_{j+1};x_{j})+\left(\frac{\bar{L}_{f}}{2}+\frac{4\bar{M}_{f}^{2}}{\bar{\varepsilon}}\right)\|x_{j+1}-x_{j}\|^{2}\right].$

Proof: First, it immediately follows from $\tau\in[\bar{\tau},1)$ and the
definition of $\bar{\tau}$ in (19) that

$\frac{\tau}{1-\tau}\geq\frac{8{\lambda}_{\mu}T_{\bar{\varepsilon}}^{2}}{\bar{\varepsilon}}\geq{\lambda}_{\mu}\left(\bar{L}_{f}+\frac{8\bar{M}_{f}^{2}}{\bar{\varepsilon}}\right).$
(41)

Using (39) and Lemma 4.4(b) with $u=x_{j+1}$, and the definitions of
$m_{j+1}$, $\Gamma_{j+1}^{\lambda}$ and $\ell_{\phi}^{\lambda}$ in (23), (36)
and (38), respectively, we have

$\displaystyle m_{j+1}$
$\displaystyle=\Gamma_{j+1}^{\lambda}(x_{j+1})\geq(1-\tau)\ell_{\phi}^{\lambda}(x_{j+1};x_{j})+\tau\left(\bar{\Gamma}_{j}(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-x_{\ell_{0}}\|^{2}\right)$
$\displaystyle\geq(1-\tau)\ell_{\phi}^{\lambda}(x_{j+1};x_{j})+\tau\left(m_{j}+\frac{1}{2{\lambda}_{\mu}}\|x_{j+1}-x_{j}\|^{2}\right)$

which, together with (41), implies the conclusion of the lemma.

The next result establishes a key recursive formula for $\\{t_{j}\\}$ which
plays an important role in the analysis of the null iterates.

######  Lemma 4.6.

For every $\tau\in[\bar{\tau},1)$ and $j\in B(\ell_{0})$, we have
$t_{j+1}-\bar{\varepsilon}/4\leq\tau(t_{j}-\bar{\varepsilon}/4)$ where $t_{j}$
is as in (23).

Proof: Using (8) with
$(M_{f},L_{f},u,v)=(\bar{M}_{f},\bar{L}_{f},x_{j+1},x_{j})$, and the
definitions of $\phi^{\lambda}$ and $\ell_{\phi}^{\lambda}$ in (37) and (38),
respectively, we have

$\phi^{\lambda}(x_{j+1})-2\bar{M}_{f}\|x_{j+1}-x_{j}\|\leq\ell_{\phi}^{\lambda}(x_{j+1};x_{j})+\frac{\bar{L}_{f}}{2}\|x_{j+1}-x_{j}\|^{2}.$

This inequality, together with Lemma 4.5 and the fact that
$m_{j}=\phi^{\lambda}(y_{j})-t_{j}$ (see (23)), then implies

$\displaystyle m_{j+1}$ $\displaystyle\geq\tau\phi^{{\lambda}}(y_{j})-\tau
t_{j}+(1-\tau)\left[\ell_{\phi}^{\lambda}(x_{j+1};x_{j})+\left(\frac{\bar{L}_{f}}{2}+\frac{4\bar{M}_{f}^{2}}{\bar{\varepsilon}}\right)\|x_{j+1}-x_{j}\|^{2}\right]$
$\displaystyle\geq\tau\phi^{\lambda}(y_{j})+(1-\tau)\phi^{\lambda}(x_{j+1})-\tau
t_{j}+\frac{1-\tau}{\bar{\varepsilon}}\left(4\bar{M}_{f}^{2}\|x_{j+1}-x_{j}\|^{2}-2\bar{M}_{f}\bar{\varepsilon}\|x_{j+1}-x_{j}\|\right)$
$\displaystyle\geq\phi^{\lambda}\left(y_{j+1}\right)-\tau
t_{j}-\frac{(1-\tau)\bar{\varepsilon}}{4}$

where the last inequality is due to (21), (37) and the inequality
$a^{2}-2ab\geq-b^{2}$ with $a=2\bar{M}_{f}\|x_{j+1}-x_{j}\|$ and
$b=\bar{\varepsilon}/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_{\ell_{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_{\ell_{0}}-x_{\ell_{0}+1}\|$ is obtained.

######  Lemma 4.7.

We have $t_{\ell_{0}+1}\leq\bar{t}$ where

$\bar{t}:=\bar{M}_{f}^{2}+4(\bar{L}_{f}+2)(\max\\{1,2{\lambda}\bar{L}_{f}\\}d_{0}+{\lambda}\bar{M}_{f})^{2}.$
(42)

Proof: Using both (21) and (23) with $j=\ell_{0}$, and the facts that
$\phi=f+h$ and $\Gamma_{\ell_{0}+1}\geq\ell_{f}(\cdot;x_{\ell_{0}})+h$ (see
the serious update in step 1), we have

$\displaystyle t_{\ell_{0}+1}$
$\displaystyle=\phi^{{\lambda}}(y_{\ell_{0}+1})-\Gamma_{\ell_{0}+1}^{{\lambda}}(x_{\ell_{0}+1})\leq\phi(x_{\ell_{0}+1})-\Gamma_{\ell_{0}+1}(x_{\ell_{0}+1})\leq
f(x_{\ell_{0}+1})-\ell_{f}(x_{\ell_{0}+1};x_{\ell_{0}})$ $\displaystyle\leq
2\bar{M}_{f}\|x_{\ell_{0}+1}-x_{\ell_{0}}\|+\frac{\bar{L}_{f}}{2}\|x_{\ell_{0}+1}-x_{\ell_{0}}\|^{2}\leq\bar{M}_{f}^{2}+\left(\frac{\bar{L}_{f}}{2}+1\right)\|x_{\ell_{0}+1}-x_{\ell_{0}}\|^{2}$

where the third inequality is due to (8) with
$(M_{f},L_{f},u,v)=(\bar{M}_{f},\bar{L}_{f},x_{\ell_{0}+1},x_{\ell_{0}})$, and
the last inequality is due to the fact that $2ab\leq a^{2}+b^{2}$ for every
$a,b\in\mathbb{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(\ell_{0})|$ is obtained in terms of $\tau$, $\bar{t}$ and
$\bar{\varepsilon}$.

######  Proposition 4.8.

The set $B(\ell_{0})$ is finite and

$|B(\ell_{0})|\leq\frac{1}{1-\tau}\log\left(\frac{4\bar{t}}{\bar{\varepsilon}}\right)$

where $\bar{t}$ is as in (42) and $\tau$ is as in step 0 of GPB.

Proof: Using the inequality $\tau\leq e^{\tau-1}$, and Lemmas 4.6 and 4.7, we
then conclude that for every $j\in B(\ell_{0})$,

$t_{j}-\frac{\bar{\varepsilon}}{4}\leq\tau^{j-\ell_{0}-1}\left(t_{\ell_{0}+1}-\frac{\bar{\varepsilon}}{4}\right)\leq\tau^{j-\ell_{0}-1}t_{\ell_{0}+1}\leq
e^{(\tau-1)(j-\ell_{0}-1)}\bar{t}.$

Using this observation, and noting that step 1 of GPB and the definition of
$B(\ell_{0})$ imply that $t_{j}>\bar{\varepsilon}/2$ for every $j\in
B(\ell_{0})$, it is now easy to see that the conclusion of the proposition
follows.

###  4.3 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 ${\lambda}$.

######  Proposition 4.9.

Let input quadruple
$(x_{0},{\lambda},\bar{\varepsilon},\tau)\in\mathrm{dom}\,h\times\mathbb{R}_{++}\times\mathbb{R}_{++}\times[\bar{\tau},1]$
be given. Then, any variant of GPB with input
($x_{0},{\lambda},\bar{\varepsilon},\tau$) obtains a
$\bar{\varepsilon}$-solution of the above instance in a number of iterations
bounded (up to a logarithmic term) by

$\left[\frac{1}{1-\tau}\log\left(\frac{4\bar{t}}{\bar{\varepsilon}}\right)+1\right]\left[\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}+1\right]$ (43)

where $\bar{t}$ is as in (42). Moreover, if $\tau$ is as in (25), then the
total iteration-complexity becomes

$\left[\left(1+\frac{8{\lambda}_{\mu}(M_{f}^{2}+\bar{\varepsilon}L_{f})}{\bar{\varepsilon}}\right)\log\left(\frac{4\bar{t}}{\bar{\varepsilon}}\right)+1\right]\left[\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}+1\right].$ (44)

Proof: It follows from Propositions 4.3 and 4.8 that the first conclusion
holds. Using bound (43) with $\tau$ as in (25), we conclude that the second
conclusion holds.

Since $\tau$-free GPB variants do not depend on $\tau$, we can choose
$\tau=\bar{\tau}$ in (43). Hence, the $\bar{\varepsilon}$-iteration complexity
for $\tau$-free GPB variants is (44) with $M_{f}^{2}+\bar{\varepsilon}L_{f}$
replaced by $T_{\bar{\varepsilon}}$.

Proposition 4.9 allows us to make one additional remark about Theorem 3.1,
namely, in the unusual case where the range of ${\lambda}$ (26) is empty,
i.e.,
$C^{2}(M_{f}^{2}+\bar{\varepsilon}L_{f})d_{0}^{2}/\bar{\varepsilon}^{2}<1$, it
can be easily seen that (44), up to a logarithmic term, reduces to ${\cal
O}([\kappa+1][C^{-2}\kappa^{-1}+1])$ where
$\kappa:={\lambda}(M_{f}^{2}+\bar{\varepsilon}L_{f})/\bar{\varepsilon}$.
Hence, the $\bar{\varepsilon}$-iteration complexity of GPB with
${\lambda}=\bar{\varepsilon}/[C(M_{f}^{2}+\bar{\varepsilon}L_{f})]$ becomes
${\cal O}((1+C^{-1})^{2})$, 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

$a=\frac{{\lambda}_{\mu}(M_{f}^{2}+\bar{\varepsilon}L_{f})}{\bar{\varepsilon}},\quad
b=\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\},$ (45)

and using (44), we conclude that ${\cal O}((a+1)(b+1))$ is a
$\bar{\varepsilon}$-iteration complexity bound for GPB up to a logarithmic
term. We break the proof into two cases: 1) $\mu\leq
C(M_{f}^{2}+\bar{\varepsilon}L_{f})/\bar{\varepsilon}^{2}$; and 2) $\mu\geq
C(M_{f}^{2}+\bar{\varepsilon}L_{f})/\bar{\varepsilon}^{2}$.

First, assume that case 1 holds. Using the definition of ${\lambda}_{\mu}$ in
(19), the fact that $\mu\leq
C(M_{f}^{2}+\bar{\varepsilon}L_{f})/\bar{\varepsilon}^{2}$, and the first
inequality in (24), we have

$\frac{1}{{\lambda}_{\mu}}=\frac{1}{{\lambda}}+\mu\leq\frac{2C(M_{f}^{2}+\bar{\varepsilon}L_{f})}{\bar{\varepsilon}},$
(46)

and hence $a\geq 1/(2C)$. Moreover, it follows from the definition of $b$ in
(45) and the second inequality in (24) that

$b\geq\min\left\\{\frac{1}{C}\,,\,\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{{\lambda}\mu}{C}+1\right)\right\\}.$
(47)

Using the fact that $\log(1+t)\geq t/(1+t)$ for every $t>0$, we easily see
that $\log(1+t)\geq t/2$ if $t\leq 1$ and $\log(1+t)\geq\log 2>0$ if $t\geq
1$. This observation with $t={\lambda}\mu/C$ and the definition of
${\lambda}_{\mu}$ in (31) then imply that

$\frac{1}{\mu{\lambda}_{\mu}}\log\left(\frac{{\lambda}\mu}{C}+1\right)\geq\min\left\\{\frac{{\lambda}}{2{\lambda}_{\mu}C}\,,\,\left(1+\frac{1}{{\lambda}\mu}\right)\log
2\right\\}\geq\min\left\\{\frac{1}{2C}\,,\,\log 2\right\\},$

and hence that $b\geq\min\\{1/(2C),\log 2\\}$. This inequality and the fact
that $a\geq 1/(2C)$ imply that ${\cal O}((a+1)(b+1))$ is equal to ${\cal
O}(ab+1)$. Using this observation, the definitions of $a$ and $b$ in (45), and
the fact that ${\lambda}_{\mu}\leq{\lambda}$, we then conclude that the bound
${\cal 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
${\lambda}_{\mu}$ in (19) and the first inequality in (24) that

$\frac{1}{{\lambda}_{\mu}}=\mu+\frac{1}{{\lambda}}\geq\mu\geq\frac{C(M_{f}^{2}+\bar{\varepsilon}L_{f})}{\bar{\varepsilon}},\quad{\lambda}\mu\geq
1.$ (48)

The first inequality then implies that $a\leq 1/C$ in view of the first
identity in (45), and hence that ${\cal O}((a+1)(b+1))$ is ${\cal O}(b+1)$. We
will now derive a bound on $b$. Indeed, using the definitions of $b$ and
${\lambda}_{\mu}$ in (45) and (19), respectively, we have

$b=\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\left(1+\frac{1}{{\lambda}\mu}\right)\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\leq\min\left\\{\frac{C(M_{f}^{2}+\bar{\varepsilon}L_{f})d_{0}^{2}}{\bar{\varepsilon}^{2}}\,,\,2\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}$ (49)

where the inequality is due to the second inequality in (48) and the first
inequality in (24). Hence, the bound ${\cal O}(b+1)$ becomes

${\cal
O}_{1}\left(\min\left\\{\frac{(M_{f}^{2}+\bar{\varepsilon}L_{f})d_{0}^{2}}{\bar{\varepsilon}^{2}},\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\right).$

Finally, it is easy to see that bound (5) becomes the above bound when
$\mu\geq C(M_{f}^{2}+\bar{\varepsilon}L_{f})/\bar{\varepsilon}^{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).

##  5 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},\mu)$ satisfying (A3) and (A4), and
which has the same $\bar{\varepsilon}$-iteration complexity as described in
Corollary 3.2 for an arbitrary $\tau$-free GPB variant.

We start by stating the 1C-APB method.

1C-APB

  * 0.

Let $x_{0}\in\mathrm{dom}\,h$, $\lambda>0$ and $\bar{\varepsilon}>0$ be given,
and set $y_{0}=x_{0}$, $t_{0}=0$, $\tau_{0}=0$, and $j=0$;

  * 1.

set $\tau=\tau_{j}$;

  * 2.

if $t_{j}\leq\bar{\varepsilon}/2$, then perform a serious update, i.e., set
$x^{c}_{j+1}=x_{j}$ and $\Gamma_{j+1}=\ell_{f}(\cdot;x_{j})+h$; else, perform
a null update, i.e., set $x^{c}_{j+1}=x^{c}_{j}$ and
$\Gamma_{j+1}=\tau\Gamma_{j}+(1-\tau)[\ell_{f}(\cdot;x_{j})+h]$;

  * 3.

compute $x_{j+1}$, $y_{j+1}$, $m_{j+1}$ and $t_{j+1}$ as in step 2 of GPB;

  * 4.

if $t_{j}>\bar{\varepsilon}/2$ and $t_{j+1}>\tau
t_{j}+(1-\tau)\bar{\varepsilon}/4$, then set $\tau=(1+\tau)/2$ and go to step
2; else, set $\tau_{j+1}=\tau$ and $j\leftarrow j+1$, and go to step 1.

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 $\Gamma_{j+1}$ in both the
serious and null updates, the latter of which computes $\Gamma_{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

$t_{j+1}-\frac{\bar{\varepsilon}}{4}\leq\tau_{j+1}\left(t_{j}-\frac{\bar{\varepsilon}}{4}\right)$
(50)

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
$\tau$ and (with some abuse of notation) are all denoted by $\Gamma_{j+1}$,
$x_{j+1}$, $y_{j+1}$, $m_{j+1}$ and $t_{j+1}$. Third, since
$\tau_{0}=0<\bar{\tau}$, it may happen that many $\tau_{j}$’s (possibly even
the last one) will also be less than $\bar{\tau}$. Hence, 1C-APB can not be
viewed as a special case of GPB since the latter one requires its constant
$\tau$ to be greater than or equal to $\bar{\tau}$.

The following lemma summarizes some basic properties of the sequence
$\\{\tau_{j}\\}$ generated by 1C-APB.

######  Lemma 5.1.

The following statements about the 1C-APB method hold:

  * a)

$\\{\tau_{j}\\}$ is a non-decreasing sequence such that
$\tau_{j}\leq(1+\bar{\tau})/2$ for every $j\geq 0$;

  * b)

if $\ell_{0}$ is a serious index, then $t_{\ell_{0}}\leq\bar{\varepsilon}/2$
and (50) holds for every $j\in B(\ell_{0})$.

Proof: a) This statement follows immediately from Lemma 4.6 and the way the
sequence $\\{\tau_{j}\\}$ is generated.

b) This statement follows immediately from steps 2 and 4 of 1C-APB.

The following result is similar to Proposition 4.8 and establishes a bound on
the maximum number of consecutive null iterates generated by 1C-APB.

######  Proposition 5.2.

The following statements about 1C-APB hold:

  * a)

the total number of times $\tau$ is updated in step 4 is at most

$\left\lceil\log\left(1+\frac{8{\lambda}_{\bar{\mu}}T_{\bar{\varepsilon}}^{2}}{\bar{\varepsilon}}\right)\right\rceil;$
(51)

  * b)

if $\ell_{0}$ is a serious index of the 1C-APB method, then the next serious
index $\ell_{1}$ happens and satisfies

$\ell_{1}-\ell_{0}\leq
2\left(1+\frac{8{\lambda}_{\bar{\mu}}T_{\bar{\varepsilon}}^{2}}{\bar{\varepsilon}}\right)\log\left(\frac{4\bar{t}}{\bar{\varepsilon}}\right)+1$

where ${\lambda}_{\bar{\mu}}:={\lambda}/(1+{\lambda}\bar{\mu})$, and
$T_{\bar{\varepsilon}}$ and $\bar{t}$ are as in (6) and (42), respectively.

Proof: a) It follows from the way $\tau$ is updated in step 4 that
$1-\tau^{+}=(1-\tau)/2$ where $\tau^{+}$ is the updated $\tau$. It follows
from Lemma 4.6 that if $\tau_{j}\geq\bar{\tau}$ then $\tau_{\ell}=\tau_{j}$
for every $\ell>j$. Using the above two observations, we then easily conclude
that the number of times $\tau$ changes is bounded by
$\lceil\log\left(1/(1-\bar{\tau})\right)\rceil$. The conclusion in b) now
follows from the last conclusion and the definition of $\bar{\tau}$ in (19).

b) It follows from Lemma 5.1 that for every $j\in B(\ell_{0})$,

$t_{j+1}-\frac{\bar{\varepsilon}}{4}\leq\frac{1+\bar{\tau}}{2}\left(t_{j}-\frac{\bar{\varepsilon}}{4}\right).$

Using the inequality above, the fact that
$t_{\ell_{1}}\leq\bar{\varepsilon}/2$ (see Lemma 5.1(b)) and Proposition 4.8,
we conclude that

$\ell_{1}-\ell_{0}\leq\frac{2}{1-\bar{\tau}}\log\left(\frac{4\bar{t}}{\bar{\varepsilon}}\right)+1.$

The above inequality, the fact that
${\lambda}_{\bar{\mu}}:={\lambda}/(1+{\lambda}\bar{\mu})$ and the definition
of $\bar{\tau}$ in (19) immediately imply b).

We now discuss the $\bar{\varepsilon}$-iteration complexity of 1C-APB.

######  Theorem 5.3.

Let initial point $x_{0}\in\mathrm{dom}\,h$, tolerance $\bar{\varepsilon}>0$
and prox stepsize ${\lambda}>0$ be given, and consider an instance
$(f,f^{\prime};h)$ of (1) satisfying conditions (A1)-(A4). Then, the
$\bar{\varepsilon}$-iteration complexity for 1C-APB is

$\left[2\left(1+\frac{8{\lambda}_{\bar{\mu}}T_{\bar{\varepsilon}}^{2}}{\bar{\varepsilon}}\right)\log\left(\frac{4\bar{t}}{\bar{\varepsilon}}\right)+1\right]\left[\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1}{\bar{\mu}{\lambda}_{\bar{\mu}}}\log\left(\frac{\bar{\mu}d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}+1\right].$
(52)

As a consequence, if in addition the instance $(f,f^{\prime};h)$ and the input
triple $(x_{0},{\lambda},\bar{\varepsilon})$ satisfy (26), then the
$\bar{\varepsilon}$-iteration complexity for 1C-APB is (up to a logarithmic
term) given by (12).

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 $\mu=\bar{\mu}$. Hence,
this conclusion and Proposition 5.2(b) imply that the
$\bar{\varepsilon}$-iteration complexity for 1C-APB is given by (52). Letting
$a={\lambda}_{\bar{\mu}}T_{\bar{\varepsilon}}^{2}/\bar{\varepsilon}$ and $b$
be as in (45), and using (52), we have ${\cal O}((a+1)(b+1))$ is the
$\bar{\varepsilon}$-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 $\bar{\varepsilon}$-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 $\partial h$, i.e., an evaluation of
the point-to-point operator $(I+\alpha\partial h)^{-1}(\cdot)$ for some
$\alpha>0$. Observe first that the computation of $x_{j+1}$ in step 3 of
1C-APB requires one resolvent evaluation of $\partial h$ due to (20) and the
fact that $\Gamma_{j+1}$ has the form (15). Hence, the total number of
resolvent evaluations of $\partial h$ is bounded by the sum of the total
number of iterations performed by 1C-APB and the total number of times $\tau$
is updated. Thus, it follows from Theorem 5.3 and Proposition 5.2(a) that the
total number of resolvent evaluations of $\partial 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 $\partial h$ is on the order of (52).

##  6 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 $\mu$-convex.
A natural question is whether, under the weaker assumption that $\phi$ is
$\mu$-convex, which includes the case where $f$ is $\mu_{f}$-convex, $h$ is
$\mu_{h}$-convex and $\mu=\mu_{f}+\mu_{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 $\mu_{f}$. Second,
the $\bar{\varepsilon}$-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.

## References

  * [1] A. Astorino, A. Frangioni, A. Fuduli, and E. Gorgone.  A nonmonotone proximal bundle method with (potentially) continuous step decisions.  SIAM Journal on Optimization, 23(3):1784–1809, 2013.
  * [2] A. Beck.  First-order methods in optimization, volume 25.  SIAM, 2017.
  * [3] A. Ben-Tal and A. Nemirovski.  Non-euclidean restricted memory level method for large-scale convex optimization.  Mathematical Programming, 102(3):407–456, 2005.
  * [4] W. de Oliveira and M. Solodov.  A doubly stabilized bundle method for nonsmooth convex optimization.  Mathematical programming, 156(1-2):125–159, 2016.
  * [5] M. Díaz and B. Grimmer.  Optimal convergence rates for the proximal bundle method.  Available on arXiv:2105.07874, 2021.
  * [6] Y. Du and A. Ruszczyński.  Rate of convergence of the bundle method.  Journal of Optimization Theory and Applications, 173(3):908–922, 2017.
  * [7] A. Frangioni.  Generalized bundle methods.  SIAM Journal on Optimization, 13(1):117–156, 2002.
  * [8] K. C. Kiwiel.  Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities.  Mathematical Programming, 69(1-3):89–109, 1995.
  * [9] K. C. Kiwiel.  Efficiency of proximal bundle methods.  Journal of Optimization Theory and Applications, 104(3):589–603, 2000.
  * [10] G. Lan.  Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization.  Mathematical Programming, 149(1-2):1–45, 2015.
  * [11] C. Lemaréchal.  An extension of davidon methods to non differentiable problems.  In Nondifferentiable optimization, pages 95–109. Springer, 1975\.
  * [12] C. Lemaréchal.  Nonsmooth optimization and descent methods.  1978\.
  * [13] C. Lemaréchal, A. Nemirovski, and Y. Nesterov.  New variants of bundle methods.  Mathematical programming, 69(1-3):111–147, 1995.
  * [14] J. Liang and R. D. C. Monteiro.  A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes.  To appear in SIAM Journal on Optimization, available on arXiv:2003.11457, 2020.
  * [15] R. Mifflin.  A modification and an extension of Lemaréchal’s algorithm for nonsmooth minimization.  In Nondifferential and variational techniques in optimization, pages 77–90. Springer, 1982.
  * [16] R. D. C. Monteiro and B. F. Svaiter.  Iteration-complexity of a newton proximal extragradient method for monotone variational inequalities and inclusion problems.  SIAM J. Optim., 22(3):914–935, 2012.
  * [17] Y. Nesterov.  Primal-dual subgradient methods for convex problems.  Mathematical programming, 120(1):221–259, 2009.
  * [18] W. de Oliveira, C. Sagastizábal, and C. Lemaréchal.  Convex proximal bundle methods in depth: a unified analysis for inexact oracles.  Mathematical Programming, 148(1-2):241–277, 2014.
  * [19] A. Ruszczyński.  Nonlinear optimization.  Princeton university press, 2011.
  * [20] J.-B. H. Urruty and C. Lemaréchal.  Convex analysis and minimization algorithms I.  Springer-Verlag, 1993.
  * [21] J.-B. H. Urruty and C. Lemaréchal.  Convex analysis and minimization algorithms II.  Springer-Verlag, 1993.
  * [22] W. van Ackooij, V. Berge, W. de Oliveira, and C. Sagastizábal.  Probabilistic optimization via approximate p-efficient points and bundle methods.  Computers & Operations Research, 77:177–193, 2017.
  * [23] P. Wolfe.  A method of conjugate subgradients for minimizing nondifferentiable functions.  In Nondifferentiable optimization, pages 145–173. Springer, 1975\.

##  Appendix A Technical Results

The main result of this section is Lemma A.3 which was used in the proof of
Lemma 4.7.

Before stating and proving Lemma A.3, we first present two technical results.

######  Lemma A.1.

Let $x\in\mathbb{R}^{n}$, $0<\tilde{\lambda}<{\lambda}$ and
$\Gamma\in\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$ be given, and define

$x^{+}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma(u)+\frac{1}{2{\lambda}}\|u-x\|^{2}\right\\},\quad\tilde{x}^{+}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma(u)+\frac{1}{2\tilde{\lambda}}\|u-x\|^{2}\right\\}.$

Then, we have $\|x^{+}-x\|\leq({\lambda}/\tilde{\lambda})\|\tilde{x}^{+}-x\|$.

Proof: Denote $\partial\Gamma$ by $A$, and define

$y_{A}({\lambda};x):=(I+{\lambda}A)^{-1}(x),\quad\varphi_{A}({\lambda};x):={\lambda}\|y_{A}({\lambda};x)-x\|.$

It is easy to see that

$\|x^{+}-x\|=\|y_{A}({\lambda};x)-x\|=\frac{1}{{\lambda}}\varphi_{A}({\lambda};x),\quad\|\tilde{x}^{+}-x\|=\|y_{A}(\tilde{\lambda};x)-x\|=\frac{1}{\tilde{\lambda}}\varphi_{A}(\tilde{\lambda};x).$

The conclusion of the lemma now follows from the above observation and the
second inequality in (39) of [16] which claims that

$\varphi_{A}({\lambda};x)\leq\frac{{\lambda}^{2}}{\tilde{\lambda}^{2}}\varphi_{A}(\tilde{\lambda};x).$

######  Lemma A.2.

Let $(\Gamma,z_{0},{\lambda})\in{\cal
C}_{\mu}(\phi)\times\mathbb{R}^{n}\times(0,1/\bar{L}_{f})$ be a triple such
that $\Gamma\geq\ell_{f}(\cdot;z_{0})+h$, and define

$z:=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma(u)+\frac{1}{2{\lambda}}\|u-z_{0}\|^{2}\right\\}.$
(53)

Then, for every $u\in\mathrm{dom}\,h$, we have

$\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)\|u-z\|^{2}+\phi(z)-\phi(u)\leq\frac{1}{2{\lambda}}\|u-z_{0}\|^{2}+\frac{2{\lambda}\bar{M}_{f}^{2}}{1-{\lambda}\bar{L}_{f}}.$
(54)

Proof: It follows from the assumption that $\Gamma\in{\cal C}_{\mu}(\phi)$ and
the definition of ${\cal C}_{\mu}(\phi)$ that $\Gamma\leq\phi$ and the
function $\Gamma+\|\cdot-z_{0}\|^{2}/(2{\lambda})$ is
$(\mu+{\lambda}^{-1})$-strongly convex. These conclusions, (53) and Theorem
5.25(b) of [2] with $f=\Gamma+\|\cdot-z_{0}\|^{2}/(2{\lambda})$, $x^{*}=z$ and
$\sigma=\mu+{\lambda}^{-1}$, then imply that for every $u\in\mathrm{dom}\,h$,

$\displaystyle\phi(u)+\frac{1}{2{\lambda}}\|u-z_{0}\|^{2}$
$\displaystyle\geq\Gamma(u)+\frac{1}{2{\lambda}}\|u-z_{0}\|^{2}$
$\displaystyle\geq\Gamma(z)+\frac{1}{2{\lambda}}\|z-z_{0}\|^{2}+\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)\|u-z\|^{2}$
$\displaystyle\geq\ell_{f}(z;z_{0})+h(z)+\frac{1}{2{\lambda}}\|z-z_{0}\|^{2}+\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)\|u-z\|^{2}$

where the last inequality follows from the assumption that
$\Gamma\geq\ell_{f}(\cdot;z_{0})+h$. The above inequality, the fact that
$\phi=f+h$ and (8) with $(M_{f},L_{f},u,v)=(\bar{M}_{f},\bar{L}_{f},z,z_{0})$
then imply that

$\displaystyle\frac{1}{2}\left(\mu+\frac{1}{{\lambda}}\right)$
$\displaystyle\|u-z\|^{2}+\phi(z)-\phi(u)\leq\frac{1}{2{\lambda}}\|u-z_{0}\|^{2}+\phi(z)-\ell_{f}(z;z_{0})-h(z)-\frac{1}{2{\lambda}}\|z-z_{0}\|^{2}$
$\displaystyle\leq\frac{1}{2{\lambda}}\|u-z_{0}\|^{2}+2\bar{M}_{f}\|z-z_{0}\|-\frac{1-{\lambda}\bar{L}_{f}}{2{\lambda}}\|z-z_{0}\|^{2}.$

The lemma now follows from the above inequality, the fact that
${\lambda}\bar{L}_{f}<1$ and the inequality $2ab-a^{2}\leq b^{2}$ with
$a^{2}=(1-{\lambda}\bar{L}_{f})\|z-z_{0}\|^{2}/(2{\lambda})$ and
$b^{2}=2{\lambda}\bar{M}_{f}^{2}/(1-{\lambda}\bar{L}_{f})$.

We are now ready to prove the main technical result of this section which
provides a bound on the distance between a serious iterate generated by GPB
and its consecutive (possibly null or serious) iterate. It is worth noting
that this result is quite general and makes no use of the generic bundle
update scheme of Subsection 3.1 since the step from $x_{\ell_{0}}$ to
$x_{\ell_{0}+1}$ does not use this update.

######  Lemma A.3.

If $\ell_{0}$ is a serious index, then

$\|x_{\ell_{0}}-x_{\ell_{0}+1}\|\leq
2\sqrt{2}(\max\\{1,2{\lambda}\bar{L}_{f}\\}d_{0}+{\lambda}\bar{M}_{f}).$ (55)

Proof: For the sake of this proof only, we define the auxiliary stepsize
$\tilde{\lambda}:=\min\\{{\lambda},1/(2\bar{L}_{f})\\}$ and auxiliary point

$w_{\ell_{0}}:=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma_{\ell_{0}+1}(u)+\frac{1}{2\tilde{\lambda}}\|u-x_{\ell_{0}}\|^{2}\right\\}.$

Since $j=\ell_{0}$ is a serious index, it follows from step 1 of GPB that
$\Gamma_{\ell_{0}+1}\geq\ell_{f}(\cdot;x_{\ell_{0}})+h$, and hence that
$(\Gamma,z_{0},{\lambda})=(\Gamma_{\ell_{0}+1},x_{\ell_{0}},\tilde{\lambda})$
and $z=w_{\ell_{0}}$ satisfy the assumptions of Lemma A.2. The conclusion of
Lemma A.2 with
$(u,z,z_{0},{\lambda})=(x_{0}^{*},w_{\ell_{0}},x_{\ell_{0}},\tilde{\lambda})$
and the fact that $\tilde{\lambda}\leq 1/(2\bar{L}_{f})$ then imply that

$\displaystyle\frac{1}{2}\left(\mu+\frac{1}{\tilde{\lambda}}\right)\|x_{0}^{*}-w_{\ell_{0}}\|^{2}+\phi(w_{\ell_{0}})-\phi(x_{0}^{*})\leq\frac{1}{2\tilde{\lambda}}\|x_{0}^{*}-x_{\ell_{0}}\|^{2}+4\tilde{\lambda}\bar{M}_{f}^{2}$

which in turn, in view of the facts that
$\phi(w_{\ell_{0}})\geq\phi^{*}=\phi(x_{0}^{*})$ and $\mu\geq 0$, and the
inequality $(a+b)^{1/2}\leq a^{1/2}+b^{1/2}$ for any $a,b\geq 0$, yields

$\|x_{0}^{*}-w_{\ell_{0}}\|\leq\|x_{\ell_{0}}-x_{0}^{*}\|+2\sqrt{2}\tilde{\lambda}\bar{M}_{f}.$

This inequality and the triangle inequality then imply that

$\|x_{\ell_{0}}-w_{\ell_{0}}\|\leq\|x_{\ell_{0}}-x_{0}^{*}\|+\|x_{0}^{*}-w_{\ell_{0}}\|\leq
2\|x_{\ell_{0}}-x_{0}^{*}\|+2\sqrt{2}\tilde{\lambda}\bar{M}_{f}\leq
2\sqrt{2}(d_{0}+\tilde{\lambda}\bar{M}_{f})$ (56)

where the last inequality is due to (34) and the fact that $x_{\ell_{0}}$ is
equal to one of serious iterates $\hat{x}_{k}$ preceding the last one
generated by GPB. On the other hand, since $0<\tilde{\lambda}<{\lambda}$ and
$\Gamma_{\ell_{0}+1}\in\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$, it
follows from Lemma A.1 with $(\Gamma,x)=(\Gamma_{\ell_{0}+1},x_{\ell_{0}})$
that

$\|x_{\ell_{0}+1}-x_{\ell_{0}}\|\leq\frac{{\lambda}}{\tilde{\lambda}}\|w_{\ell_{0}}-x_{\ell_{0}}\|.$

This inequality together with (56) and the fact that
${\lambda}/\tilde{\lambda}=\max\\{1,2{\lambda}\bar{L}_{f}\\}$ clearly implies
(55).

##  Appendix 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.

######  Lemma B.1.

Assume that sequences of nonnegative scalars $\\{\theta_{j}\\}$,
$\\{\delta_{j}\\}$, $\\{\eta_{j}\\}$ and $\\{\alpha_{j}\\}$ satisfy for every
$j\geq 1$, $\theta_{j}\geq 1$, $\delta_{j}>0$ and

$\eta_{j}\leq\alpha_{j-1}-\theta_{j}\alpha_{j}+\delta_{j}.$ (57)

Let $\Theta_{0}:=1$ and $\Theta_{j}:=\Pi_{i=1}^{j}\theta_{i}$ for every $j\geq
1$, then we have for every $k\geq 1$,

$\sum_{j=1}^{k}\Theta_{j-1}\eta_{j}\leq\alpha_{0}-\Theta_{k}\alpha_{k}+\sum_{j=1}^{k}\Theta_{j-1}\delta_{j}.$

Proof: Multiplying (57) by $\Theta_{j-1}$ and summing the resulting inequality
from $j=1$ to $k$, we have

$\sum_{j=1}^{k}\Theta_{j-1}\eta_{j}\leq\sum_{j=1}^{k}\Theta_{j-1}\left(\alpha_{j-1}-\theta_{j}\alpha_{j}+\delta_{j}\right)=\alpha_{0}-\Theta_{k}\alpha_{k}+\sum_{j=1}^{k}\Theta_{j-1}\delta_{j}.$

Hence, the lemma holds.

The next result discusses a special case of the previous lemma in which
$\theta_{j}=\theta$ and $\delta_{j}=\delta$ for every $j\geq 1$.

######  Corollary B.2.

Assume that scalars $\theta\geq 1$ and $\delta>0$, and sequences of
nonnegative scalars $\\{\eta_{j}\\}$ and $\\{\alpha_{j}\\}$ satisfy

$\eta_{j}\leq\alpha_{j-1}-\theta\alpha_{j}+\delta\quad\forall j\geq 1.$ (58)

Then, the following statements hold:

  * a)

$\min_{1\leq j\leq k}\eta_{j}\leq 2\delta$ for every $k\geq 1$ such that

$k\geq\min\left\\{\frac{\alpha_{0}}{\delta},\frac{\theta}{\theta-1}\log\left(\frac{\alpha_{0}(\theta-1)}{\delta}+1\right)\right\\}$

with the convention that the second term is equal to the first term when
$\theta=1$ (Note that the second term converges to the first term as
$\theta\downarrow 1$.);

  * b)

$\alpha_{k}\leq\alpha_{0}+k\delta$ for every $k\geq 1$.

Proof: a) It follows from Lemma B.1 with $\theta_{j}=\theta$ and
$\delta_{j}=\delta$ for every $j\geq 1$ that

$\sum_{j=1}^{k}\theta^{j-1}\left[\min_{1\leq j\leq
k}\eta_{j}\right]\leq\sum_{j=1}^{k}\theta^{j-1}\eta_{j}=\alpha_{0}-\theta^{k}\alpha_{k}+\sum_{j=1}^{k}\theta^{j-1}\delta.$
(59)

Using the fact that $\theta\geq e^{(\theta-1)/\theta}$ for every $\theta\geq
1$, we have

$\sum_{j=1}^{k}\theta^{j-1}=\max\left\\{k,\frac{\theta^{k}-1}{\theta-1}\right\\}\geq\max\left\\{k,\frac{e^{(\theta-1)k/\theta}-1}{\theta-1}\right\\}.$

This inequality, (59) and the fact that $\alpha_{k}\geq 0$ imply that for
every $k\geq 1$,

$\min_{1\leq j\leq
k}\eta_{j}\leq\alpha_{0}\min\left\\{\frac{1}{k},\frac{\theta-1}{e^{(\theta-1)k/\theta}-1}\right\\}+\delta,$

which can be easily seen to imply a).

b) This statement follows from (59), the fact that $\eta_{j}\geq 0$, and the
assumption that $\theta\geq 1$.

##  Appendix C The Composite Subgradient Method

This section contains two subsections. The first one provides the analysis of
the CS-CS method, which is used to derive the $\bar{\varepsilon}$-iteration
complexity of CS-CS in Subsection 2.2. The second one presents an adaptive
variant of CS-CS and establishes the $\bar{\varepsilon}$-iteration complexity
of it.

###  C.1 Analysis of CS-CS

######  Proposition C.1.

Let an initial point $x_{0}\in\mathrm{dom}\,h$,
$(L_{f},M_{f})\in\mathbb{R}_{+}^{2}$ and instance $(f,f^{\prime};h)$
satisfying conditions (A1)-(A4) be given. Then, for any $\mu\in[0,\bar{\mu}]$,
the number of iterations performed by CS-CS$(x_{0},{\lambda})$ with
${\lambda}\leq\bar{\varepsilon}/[4(M_{f}^{2}+\bar{\varepsilon}L_{f})]$ until
it finds a $\bar{\varepsilon}$-solution is bounded by

$\left\lfloor\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1+{\lambda}\mu}{{\lambda}\mu}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}\right\rfloor+1.$

Proof: Recall that an iteration of CS-CS$(x_{0},{\lambda})$ is as in (10).
Noting that (10) satisfies (53) with
$(z_{0},z,\Gamma)=(x_{j},x_{j+1},\ell_{f}(\cdot;x_{j})+h)$, and using the
facts that
${\lambda}\leq\bar{\varepsilon}/[4(M_{f}^{2}+\bar{\varepsilon}L_{f})]\leq\bar{\varepsilon}/(4T_{\bar{\varepsilon}}^{2})<1/\bar{L}_{f}$
and $\ell_{f}(\cdot;x_{j})+h\in{\cal C}_{\mu}(\phi)$, we conclude that the
assumptions of Lemma A.2 is satisfied. Hence, it follows from (54) with
$(u,z,z_{0})=(x_{0}^{*},x_{j+1},x_{j})$ that

$\phi(x_{j+1})-\phi^{*}-\frac{1}{2{\lambda}}\|x_{0}^{*}-x_{j}\|^{2}+\frac{1+{\lambda}\mu}{2{\lambda}}\|x_{0}^{*}-x_{j+1}\|^{2}\leq\frac{2{\lambda}\bar{M}_{f}^{2}}{1-{\lambda}\bar{L}_{f}}\leq\frac{\bar{\varepsilon}}{2}$

where the last inequality is due to the facts that
$2{\lambda}\bar{M}_{f}^{2}/(1-{\lambda}\bar{L}_{f})$ is an increasing function
in ${\lambda}$ and
${\lambda}\leq\bar{\varepsilon}/(4T_{\bar{\varepsilon}}^{2})$. Since the above
inequality with $j=j-1$ satisfies (58) with

$\eta_{j}=\phi(x_{j})-\phi^{*},\quad\alpha_{j}=\frac{1}{2{\lambda}}\|x_{j}-x_{0}^{*}\|^{2},\quad\theta=1+{\lambda}\mu,\quad\delta=\frac{\bar{\varepsilon}}{2},$

it follows from Corollary B.2(a) and the fact that
$\alpha_{0}=d_{0}^{2}/(2{\lambda})$ that $\min_{1\leq j\leq
k}\phi(x_{j})-\phi^{*}\leq\bar{\varepsilon}$ for every index $k\geq 1$ such
that

$k\geq\min\left\\{\frac{d_{0}^{2}}{{\lambda}\bar{\varepsilon}},\frac{1+{\lambda}\mu}{{\lambda}\mu}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\},$

and hence that the lemma holds.

###  C.2 An adaptive CS method

This subsection present an adaptive variant of the CS-CS method, namely, the
A-CS method, and establish $\bar{\varepsilon}$-iteration complexity of the
adaptive method. The proposed method is a universal method for solving the
HCCO problem (1) since it does not rely on any problem parameters.

A-CS

  * 0.

Let $x_{0}\in\mathrm{dom}\,h$, ${\lambda}_{0}>0$ and $\bar{\varepsilon}>0$ be
given, and set ${\lambda}={\lambda}_{0}$ and $j=0$;

  * 1.

compute

$x=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\ell_{f}(u;x_{j})+h(u)+\frac{1}{2{\lambda}}\|u-x_{j}\|^{2}\right\\};$

  * 2.

if $f(x)-\ell_{f}(x;x_{j})-\|x-x_{j}\|^{2}/(2{\lambda})>\bar{\varepsilon}/2$,
then set ${\lambda}={\lambda}/2$ and go to step 1; else, go to step 3;

  * 3.

set ${\lambda}_{j+1}={\lambda}$, $x_{j+1}=x$ and $j\leftarrow j+1$, and go to
step 1.

######  Lemma C.2.

The following statements hold for A-CS(${\lambda}_{0},\bar{\varepsilon}$):

  * a)

for every $j\geq 0$, we have

$\displaystyle
x_{j+1}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\ell_{f}(u;x_{j})+h(u)+\frac{1}{2{\lambda}_{j+1}}\|u-x_{j}\|^{2}\right\\},$
(60) $\displaystyle
f(x_{j+1})-\ell_{f}(x_{j+1};x_{j})-\frac{1}{2{\lambda}_{j+1}}\|x_{j+1}-x_{j}\|^{2}\leq\frac{\bar{\varepsilon}}{2};$
(61)

  * b)

if ${\lambda}_{j}\leq\bar{\varepsilon}/(4T_{\bar{\varepsilon}}^{2})$ where
$T_{\bar{\varepsilon}}$ is as in (6), then (61) holds with
${\lambda}_{j+1}={\lambda}_{j}$;

  * c)

$\\{{\lambda}_{j}\\}$ is a non-increasing sequence;

  * d)

for every $j\geq 0$,

${\lambda}_{j}\geq\underline{{\lambda}}:=\min\left\\{\frac{\bar{\varepsilon}}{8T_{\bar{\varepsilon}}^{2}},{\lambda}_{0}\right\\}.$
(62)

Proof: a) This statement directly follows from the description of A-CS.

b) Using (8) with $(M_{f},L_{f},u,v)=(\bar{M}_{f},\bar{L}_{f},x_{j+1},x_{j})$
and the inequality that $a^{2}+b^{2}\geq 2ab$ for $a,b\in\mathbb{R}$, we have

$\displaystyle
f(x_{j+1})-\ell_{f}(x_{j+1};x_{j})-\frac{1}{2{\lambda}_{j}}\|x_{j+1}-x_{j}\|^{2}$
$\displaystyle\leq
2\bar{M}_{f}\|x_{j+1}-x_{j}\|-\frac{1-{\lambda}_{j}\bar{L}_{f}}{2{\lambda}_{j}}\|x_{j+1}-x_{j}\|^{2}$
$\displaystyle\leq\frac{2{\lambda}_{j}\bar{M}_{f}^{2}}{1-{\lambda}_{j}\bar{L}_{f}}\leq\frac{\bar{\varepsilon}}{2}$

where the last inequality is due to the assumption that
${\lambda}_{j}\leq\bar{\varepsilon}/(4T_{\bar{\varepsilon}}^{2})$. Hence, (61)
holds with ${\lambda}_{j+1}={\lambda}_{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 ${\lambda}$ is
updated in step 2.

######  Proposition C.3.

Let an initial point $x_{0}$ and a universal constant $C>0$ be given, and
consider an instance $(f,f^{\prime};h)$ of (1) satisfying conditions
(A1)-(A4). Moreover, assume
$({\lambda}_{0},\bar{\varepsilon})\in\mathbb{R}_{++}^{2}$ is such that
${\lambda}_{0}\geq\bar{\varepsilon}/(CT_{\bar{\varepsilon}}^{2})$ where
$T_{\bar{\varepsilon}}$ is as in (6). Then, the following statements hold:

  * a)

A-CS$({\lambda}_{0},\bar{\varepsilon})$ has $\bar{\varepsilon}$-iteration
complexity given by (12);

  * b)

the total number of times ${\lambda}$ is halved in step 2 is bounded by

$\left\lceil\log\left(\max\left\\{\frac{8{\lambda}_{0}T_{\bar{\varepsilon}}^{2}}{\bar{\varepsilon}},1\right\\}\right)\right\rceil.$

Proof: a) It follows from the fact that $h$ is $\mu$-convex (where
$\mu\in[0,\bar{\mu}]$) that the objective function in (60) is
$(\mu+{\lambda}_{j+1}^{-1})$-strongly convex. Using this conclusion, (60) and
Theorem 5.25(b) of [2], we have for every $u\in\mathrm{dom}\,h$,

$\displaystyle\ell_{f}(x_{j+1};x_{j})$
$\displaystyle+h(x_{j+1})+\frac{1}{2{\lambda}_{j+1}}\|x_{j+1}-x_{j}\|^{2}+\frac{1}{2}\left(\mu+\frac{1}{{\lambda}_{j+1}}\right)\|u-x_{j+1}\|^{2}$
$\displaystyle\leq\ell_{f}(u;x_{j})+h(u)+\frac{1}{2{\lambda}_{j+1}}\|u-x_{j}\|^{2}\leq\phi(u)+\frac{1}{2{\lambda}_{j+1}}\|u-x_{j}\|^{2}.$

It follows from the above inequality with $u=x_{0}^{*}$ and (60) that

$\displaystyle(1+{\lambda}_{j+1}\mu)\|x_{0}^{*}-x_{j+1}\|^{2}$
$\displaystyle+2{\lambda}_{j+1}[\phi(x_{j+1})-\phi^{*}]-\|x_{0}^{*}-x_{j}\|^{2}$
$\displaystyle\leq
2{\lambda}_{j+1}\left[f(x_{j+1})-\ell_{f}(x_{j+1};x_{j})-\frac{1}{2{\lambda}_{j+1}}\|x_{j+1}-x_{j}\|^{2}\right]\leq\bar{\varepsilon}{\lambda}_{j+1}.$

Since the above inequality with $j=j-1$ satisfies (57) with

$\eta_{j}=2{\lambda}_{j}[\phi(x_{j})-\phi^{*}],\quad\alpha_{j}=\|x_{j}-x_{0}^{*}\|^{2},\quad\theta_{j}=1+{\lambda}_{j}\mu,\quad\delta_{j}=\bar{\varepsilon}{\lambda}_{j},$

it follows from Lemma B.1 and the fact that $\alpha_{0}=d_{0}^{2}$ that

$\left(\sum_{j=1}^{k}2{\lambda}_{j}\Theta_{j-1}\right)\min_{1\leq j\leq
k}[\phi(x_{j})-\phi^{*}]\leq\sum_{j=1}^{k}2{\lambda}_{j}\Theta_{j-1}[\phi(x_{j})-\phi^{*}]\leq
d_{0}^{2}+\left(\sum_{j=1}^{k}2{\lambda}_{j}\Theta_{j-1}\right)\frac{\bar{\varepsilon}}{2}$
(63)

where $\Theta_{j}=\Pi_{i=1}^{j}(1+{\lambda}_{j}\mu)$ for every $j\geq 1$. Note
that it follows from Lemma C.2(d) that
$\Theta_{j}\geq(1+\underline{{\lambda}}\mu)^{j}$ for every $j\geq 1$. Using
this observation, (63), and Lemma C.2(d), and following the argument in the
proof of Corollary B.2(a), we conclude that $\min_{1\leq j\leq
k}\phi(x_{j})-\phi^{*}\leq\bar{\varepsilon}$ for $k$ satisfying

$k\geq\min\left\\{\frac{d_{0}^{2}}{\underline{{\lambda}}\bar{\varepsilon}},\frac{1+\underline{{\lambda}}\mu}{\underline{{\lambda}}\mu}\log\left(\frac{\mu
d_{0}^{2}}{\bar{\varepsilon}}+1\right)\right\\}$

for any $\mu\in[0,\bar{\mu}]$, and hence that the statement holds in view of
(62) and the assumption that
${\lambda}_{0}\geq\bar{\varepsilon}/(CT_{\bar{\varepsilon}}^{2})$.

b) This statement immediately follows from the update rule in ${\lambda}_{j}$
and Lemma C.2(d).

##  Appendix D Properties of Bundle Update Schemes (E2) and (E3)

This section provides the proofs of the claims about properties of bundle
update schemes (E2) and (E3) in Subsection 3.1.

######  Lemma D.1.

Updating the bundle function $\Gamma^{+}$ as in (E2), then $\Gamma^{+}\in{\cal
C}_{\mu}(\phi)$ and for any $\tau\in(0,1)$, $\Gamma^{+}$ satisfies (13) with
$\bar{\Gamma}=A_{f}^{+}+h$ where $\theta$ is as in (17), and hence
$\Gamma^{+}\in{\cal C}_{\phi}(\Gamma,x_{0},{\lambda},\tau)$.

Proof: First, using the facts that $h$ is $\mu$-convex and
$\ell_{f}(\cdot;z)\leq f$ for any $z\in\mathbb{R}^{n}$, the definitions of
$\Gamma^{+}$ and $\bar{\Gamma}$, and the definition of ${\cal C}_{\mu}(\phi)$,
we have $\Gamma^{+},\bar{\Gamma}\in{\cal C}_{\mu}(\phi)$. It follows from the
fact that $\bar{\Gamma}=A_{f}^{+}+h$ and the definition of $\Gamma^{+}$ in
(16) that

$\Gamma^{+}=\max\\{\bar{\Gamma},\ell_{f}(\cdot;x)+h\\},$

and hence that $\Gamma^{+}$ satisfies (13) with any $\tau\in(0,1)$. Moreover,
using (17) and the definitions of $\Gamma$ and $\bar{\Gamma}$, we obtain the
first identity in (14). Finally, we prove $\bar{\Gamma}$ satisfies the second
identity in (14). The prox subproblem (2) with
$\Gamma=\max\\{A_{f},\ell_{f}(\cdot;x^{-})\\}+h$ can be reformulated as

$\underset{s\in\mathbb{R},u\in\mathbb{R}^{n}}{\min}\left\\{s+\frac{1}{2{\lambda}}\|u-x_{0}\|^{2}:\,A_{f}(u)+h(u)-s\leq
0,\,\ell_{f}(u;x^{-})+h(u)-s\leq 0\right\\}.$

Its optimality condition, together with the definitions of $\bar{\Gamma}$ and
$A_{f}^{+}$, implies that

$\frac{x_{0}-x}{{\lambda}}\in\theta\partial(A_{f}+h)(x)+(1-\theta)\partial[\ell_{f}(\cdot;x^{-})+h](x)=\partial(A_{f}^{+}+h)(x)=\partial\bar{\Gamma}(x)$

where $\theta$ is as in (17), and hence that $\bar{\Gamma}$ satisfies the
second identity in (14). As a consequence, we conclude that
$\Gamma^{+}\in{\cal C}_{\phi}(\Gamma,x_{0},{\lambda},\tau)$ in view of its
definition in Subsection 3.1.

######  Lemma D.2.

Updating the bundle function $\Gamma^{+}$ as in (E3), then $\Gamma^{+}\in{\cal
C}_{\mu}(\phi)$ and for any $\tau\in(0,1)$, $\Gamma^{+}$ satisfies (13) with
$\bar{\Gamma}=\Gamma(\cdot;C(x))$, and hence $\Gamma^{+}\in{\cal
C}_{\phi}(\Gamma,x_{0},{\lambda},\tau)$.

Proof: First, using the facts that $h$ is $\mu$-convex and
$\ell_{f}(\cdot;c)\leq f$ for any $c\in\mathbb{R}^{n}$, and the definition of
$\Gamma(\cdot;C)$ in (4), it is easy to see that for any subset
$C\in\mathbb{R}^{n}$, $\Gamma(\cdot;C)\in{\cal C}_{\mu}(\phi)$ in view of the
definition of ${\cal C}_{\mu}(\phi)$. Since $\Gamma^{+}=\Gamma(\cdot;C^{+})$
and $\bar{\Gamma}=\Gamma(\cdot;C(x))$, we have
$\Gamma^{+},\bar{\Gamma}\in{\cal C}_{\mu}(\phi)$. Also, it is easy to see from
the first inclusion in (18) that

$\Gamma^{+}\geq\max\\{\bar{\Gamma},\ell_{f}(\cdot;x)+h\\},$

and hence that $\Gamma^{+}$ satisfies (13) with any $\tau\in(0,1)$. Moreover,
it follows from the fact that $\Gamma=\Gamma(\cdot;C)$, (4) and the definition
of $C(x)$ in (18) that the first identity in (14) holds. Finally, we prove
$\bar{\Gamma}$ satisfies the second identity in (14). Using the definitions of
$\Gamma(\cdot;C)$ and $C(x)$ in (4) and (18), respectively, and a well-known
formula for the subdifferential of the pointwise maximum of finitely many
convex functions (e.g., see Corollary 4.3.2 of [20]), we conclude that

$\partial\Gamma(x)=\overline{\mbox{co}}\,\left(\cup\\{f^{\prime}(c):c\in
C(x)\\}\right)+\partial h(x).$

Using the same reasoning but with $\Gamma$ replaced by $\bar{\Gamma}$, we
conclude that the above set is also $\partial\bar{\Gamma}(x)$, and hence that

$\frac{1}{{\lambda}}(x_{0}-x)\in\partial\Gamma(x)=\partial\bar{\Gamma}(x)$

where the inclusion is due to (2). Now the second identity in (14) immediately
follows. As a consequence, we conclude that $\Gamma^{+}\in{\cal
C}_{\phi}(\Gamma,x_{0},{\lambda},\tau)$ in view of its definition in
Subsection 3.1.