# Universal subgradient and proximal bundle methods for
convex and strongly convex hybrid composite optimization

Vincent Guigues Jiaming Liang Renato D.C. Monteiro School of Applied
Mathematics FGV/EMAp, 22250-900 Rio de Janeiro, Brazil. (email:
vincent.guigues@fgv.br).Goergen Institute for Data Science and Department of
Computer Science, University of Rochester, Rochester, NY 14620 (email:
jiaming.liang@rochester.edu).School of Industrial and Systems Engineering,
Georgia Institute of Technology, Atlanta, GA 30332. (email:
renato.monteiro@isye.gatech.edu). This work was partially supported by AFOSR
Grant FA9550-22-1-0088.

(July 14, 2024)

###### Abstract

This paper develops two parameter-free methods for solving convex and strongly
convex hybrid composite optimization problems, namely, a composite subgradient
type method and a proximal bundle type method. Both functional and stationary
complexity bounds for the two methods are established in terms of the unknown
strong convexity parameter. To the best of our knowledge, the two proposed
methods are the first universal methods for strongly convex optimization
problems that do not rely on any restart scheme nor require the knowledge of
the optimal value.

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

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

##  1 Introduction

This paper considers convex hybrid composite optimization (HCO) problem

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

where $f,h:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ are proper
lower semi-continuous convex functions such that
$\mathrm{dom}\,h\subseteq\mathrm{dom}\,f$ and the following conditions hold:
there exist scalars $M_{f}\geq 0$ and $L_{f}\geq 0$ 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 that $\|f^{\prime}(x)-f^{\prime}(y)\|\leq 2M_{f}+L_{f}\|x-y\|$ for
every $x,y\in\mathrm{dom}\,h$. Moreover, assume that $\mu\geq 0$ is the
largest scalar such that $\phi(\cdot)-\mu\|\cdot\|^{2}/2$ is convex, i.e.,
$\mu$ is the intrinsic convex parameter of $\phi$.

This work is concerned with parameter-free (PF) methods for solving (1), i.e.,
ones that do not require knowledge of any of parameters associated with the
instance $(f,h)$, such as the parameter pair $(M_{f},L_{f})$ or the intrisic
convexity parameter $\mu$ of $\phi$. More specifically, it considers PF
methods whose complexities for solving (1) are expressed in terms of $\mu$ (in
addition to other parameters associated with $(f,h)$). We refer to them as
$\mu$-universal methods. PF methods whose (provable) complexities do not
depend on $\mu$ are called universal ones (even if $\mu>0$). Moreover, PF
methods whose complexities are given in terms of the intrinsic convex
parameter $\mu_{f}$ for $f$ (resp., $\mu_{h}$ for $h$) are called
$\mu_{f}$-universal (resp., $\mu_{h}$-universal). It is worth noting that
$\mu$ can be substantially larger than $\mu_{f}+\mu_{h}$ (e.g., for $\alpha\gg
0$, $f(x)=\alpha\exp(x)$, and $h(x)=\alpha\exp(-x)$, we have $\mu=2\alpha\gg
0=\mu_{f}+\mu_{h}$). Hence, complexities for $\mu$-universal methods are
usually better than $\mu_{f}$-universal and $\mu_{h}$-universal methods, and
even (universal or non-universal) methods whose complexities depend on
$\mu_{f}+\mu_{h}$.

Related literature. We divide our discussion here into universal and
$\mu$-universal methods.

Universal methods: The first universal methods for solving (1) have been
presented in [18], which develops universal variants of the primal gradient,
the dual gradient, and the accelerated gradient methods, and in [10], which
shows that acceleration versions of the bundle-level and the prox-level
methods are universal. Additional universal methods for solving (1) have been
studied in [13, 14, 15]. The methods in [14, 15] are also shown to be
universal with respect to $\mu_{h}$.

$\mu$-Universal methods: Under the assumption that $f$ is a smooth function
(i.e., $M_{f}=0$), various works [1, 2, 3, 4, 5, 6, 8, 12, 17, 20] have
developed $\mu$-universal (or $\mu_{f}$-universal) methods for (1) with a
$\tilde{\cal O}(\sqrt{L_{f}/\mu})$ (or $\tilde{\cal O}(\sqrt{L_{f}/\mu_{f}})$)
iteration complexity bound. For the sake of our discussion, we refer to a
convex (resp., strongly convex) version of an accelerated gradient method as
ACG (resp., S-ACG). Among papers concerned with finding an
$\varepsilon$-solution of (1), [17] proposes the first $\mu_{f}$-universal
method based on a restart S-ACG scheme where each iteration adaptively updates
an estimate of $\mu_{f}$ and calls S-FISTA (see also [8] for a $\mu$-universal
variant along this venue); moreover, using restart ACG schemes motivated by
previous works such as [11, 19, 21], paper [20] develops $\mu$-universal
methods under the assumption that $\phi_{*}$ is known.

Among papers concerned with finding an $\varepsilon$-stationary solution of
(1), [1, 2, 3, 4, 6] (resp., [12]) develop $\mu$-universal (resp.,
$\mu_{f}$-universal) methods based on restart ACG (resp., S-ACG) schemes that
estimate the condition number $L_{f}/\mu$ (resp., $\mu_{f}$), or some related
quantity; [3, 4, 6] then use the estimation to determine the number of
iterations of each ACG call while the SCAR method of [12] uses a stationary
termination to end each S-ACG call. Moreover, under the assumption that
$\phi_{*}$ and $L_{f}$ are known, [5] develops a $\mu$-universal method that
performs only one call to an ACG variant (for convex CO).

Under the assumption that $f$ is non-smooth (i.e., $M_{f}>0$), [20] (see also
[9] for an extension) proposes $\mu$-universal methods under the assumption
that $\phi_{*}$ is known. Specifically, the $\mu$-universal method of [20]
repeatedly invokes a universal oracle that halves the primal gap
$\phi(x)-\phi_{*}$ on each call.111Paper [20] removes the assumption that
$\phi_{*}$ is known but forces its method to make multiple parallel calls to
the universal oracle.

Our contribution. The goal of this work is to present two $\mu$-universal
methods for problem (1), namely: a composite subgradient (U-CS) type method
and a proximal bundle (U-PB) type method. The first method is a variant of the
universal primal gradient method of [18] (see also Appendix C.2 of [15]),
which is still not known to be $\mu$-universal. The second one is a variant of
the generic proximal bundle (GPB) method of [15] that bounds the number of
consecutive null iterations and adaptively chooses the prox stepsize under
this policy. Both methods are analyzed in a unified manner using a general
framework for strongly convex optimization problems (1) (referred to as FSCO)
which specifies sufficient conditions for its PF instances to be
$\mu$-universal. Both functional and stationary complexities are established
for FSCO in terms of $\mu$, which are then used to obtain complexity bounds
for both U-CS and U-PB. Interestingly, in contrast to previous $\mu$-universal
methods, both U-CS and U-PB do not perform any restart scheme nor require
$\phi_{*}$ to be known.

Organization of the paper. Subsection 1.1 presents basic definitions and
notation used throughout the paper. Section 2 formally describes FSCO and the
assumptions on the problem of interest, and provides both functional and
stationarity complexity analyses of FSCO. Section 3 presents U-CS and U-PB, as
two instances of FSCO, for solving problem (1) and establishes their
corresponding complexity bounds. Section 4 presents some concluding remarks
and possible extensions. Finally, Appendix A provides technical results of
FSCO and U-PB.

###  1.1 Basic definitions and notation

Let $\mathbb{R}$ denote the set of real numbers. Let $\mathbb{R}_{+}$ (resp.,
$\mathbb{R}_{++}$) denote the set of non-negative real numbers (resp., the set
of positive real numbers). 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.

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

$\Phi(\alpha
x+(1-\alpha)y)\leq\alpha\Phi(x)+(1-\alpha)\Phi(y)-\frac{\alpha(1-\alpha)\mu}{2}\|x-y\|^{2}$

for every $x,y\in\mathrm{dom}\,\Phi$ and $\alpha\in[0,1]$. Let
$\overline{\mbox{\rm Conv}}_{\mu}\,(\mathbb{R}^{n})$ denote the set of all
proper lower semicontinuous $\mu$-convex functions. We simply denote
$\overline{\mbox{\rm Conv}}_{\mu}\,(\mathbb{R}^{n})$ by $\overline{\mbox{\rm
Conv}}\,(\mathbb{R}^{n})$ when $\mu=0$. For $\varepsilon\geq 0$, the
_$\varepsilon$ -subdifferential_ of $\Phi$ at $x\in\mathrm{dom}\,\Phi$ is
denoted by

$\partial_{\varepsilon}\Phi(x):=\left\\{s\in\mathbb{R}^{n}:\Phi(y)\geq\Phi(x)+\left\langle
s,y-x\right\rangle-\varepsilon,\forall y\in\mathbb{R}^{n}\right\\}.$

We denote the subdifferential of $\Phi$ at $x\in\mathrm{dom}\,\Phi$ by
$\partial\Phi(x)$, which is the set $\partial_{0}\Phi(x)$ by definition. For a
given subgradient $\Phi^{\prime}(x)\in\partial\Phi(x)$, we denote the
linearization of convex function $\Phi$ at $x$ by $\ell_{\Phi}(\cdot,x)$,
which is defined as

$\ell_{\Phi}(\cdot,x)=\Phi(x)+\langle\Phi^{\prime}(x),\cdot-x\rangle.$ (2)

##  2 A framework for strongly convex optimization

This section presents a general framework, namely FSCO, for convex
optimization problems and establishes both functional and stationary
complexity bounds for any of its instances. These results will then be used in
Subsections 3.1 and 3.2 to analyze the complexities of two specific
algorithms, namely: U-CS and U-PB. This section is divided into two
subsections. Subsection 2.1 focuses on the functional complexity analysis,
while Subsection 2.2 provides the stationary complexity analysis.

FSCO is presented in the context of the convex optimization problem

$\phi_{*}:=\min\left\\{\phi(x):x\in\mathbb{R}^{n}\right\\}$ (3)

for which the following conditions are assumed:

  * (A1)

the set of optimal solutions $X_{*}$ of problem (3) is nonempty;

  * (A2)

$\phi\in\overline{\mbox{\rm Conv}}_{\mu}\,(\mathbb{R}^{n})$ for some $\mu\geq
0$.

Clearly, the HCO problem (1) with the assumptions described underneath it is a
special case of (3) where $\phi=f+h$.

We now describe FSCO.

FSCO

  * 0.

Let $\chi\in[0,1)$, $\varepsilon>0$, and $\hat{x}_{0}\in\mathrm{dom}\,\phi$ be
given, and set $k=1$;

  * 1.

Compute $\lambda_{k}>0$, $\hat{\Gamma}_{k}\in\overline{\mbox{\rm
Conv}}\,(\mathbb{R}^{n})$, $\hat{\Gamma}_{k}\leq\phi$, and
$\hat{y}_{k}\in\mathrm{dom}\,\phi$ satisfying

$\displaystyle\phi(\hat{y}_{k})+\frac{\chi}{2\lambda_{k}}\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2}-\underset{u\in\mathbb{R}^{n}}{\min}\left\\{\hat{\Gamma}_{k}(u)+\frac{1}{2{\lambda}_{k}}\|u-\hat{x}_{k-1}\|^{2}\right\\}\leq\varepsilon,$
(4)

and set

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

  * 2.

Check whether a termination criterion holds and if so stop; else go to step 3;

  * 3.

Set $k\leftarrow k+1$ and go to step 1.

FSCO does not specify how sequences $\\{\hat{x}_{k}\\}$ and
$\\{\hat{y}_{k}\\}$ are generated, how models $\\{\hat{\Gamma}_{k}\\}$ are
updated, and how stepsizes $\\{\lambda_{k}\\}$ are computed. Rather, it
provides sufficient conditions on these sequences to ensure that its instances
are $\mu$-universal.

The complexity analysis of FSCO requires two additional assumptions, namely:

  * (F1)

there exists $\nu\in[0,\mu]$ such that $\hat{\Gamma}_{k}\in\overline{\mbox{\rm
Conv}}_{\nu}\,(\mathbb{R}^{n})$;

  * (F2)

there exists $\underline{\lambda}>0$ such that
$\lambda_{k}\geq{\underline{\lambda}}$ for every iteration $k$ of the FSCO.

###  2.1 Functional complexity analysis

This subsection studies the iteration complexity for the framework FSCO to
obtain an iterate $\hat{y}_{k}$ such that
$\phi(\hat{y}_{k})-\phi_{*}\leq\bar{\varepsilon}$. Its main result is stated
in Theorem 2.3.

The following lemma will be useful in the sequel.

###### Lemma 2.1

Consider sequences $\\{\hat{x}_{k}\\}$, $\\{\hat{y}_{k}\\}$,
$\\{\hat{\Gamma}_{k}\\}$, and $\\{\lambda_{k}\\}$ generated by FSCO. Define
for $k\geq 1$,

$\displaystyle\tilde{s}_{k}$
$\displaystyle:=\frac{\hat{x}_{k-1}-\hat{x}_{k}}{{\lambda}_{k}}-\nu\hat{x}_{k},$
(6) $\displaystyle\tilde{\eta}_{k}$
$\displaystyle:=\tilde{\phi}(\hat{y}_{k})-\tilde{\Gamma}_{k}(\hat{x}_{k})-\langle\tilde{s}_{k},\hat{y}_{k}-\hat{x}_{k}\rangle,$
(7)

where

$\tilde{\phi}:=\phi-\frac{\nu}{2}\|\cdot\|^{2},\quad\tilde{\Gamma}_{k}:=\hat{\Gamma}_{k}-\frac{\nu}{2}\|\cdot\|^{2}.$
(8)

Then for $k\geq 1$, we have:

  * a)

$\tilde{s}_{k}\in\partial\tilde{\Gamma}_{k}(\hat{x}_{k})$ and for every
$u\in\mathbb{R}^{n}$,

$\tilde{\Gamma}_{k}(u)\geq\tilde{\Gamma}_{k}(\hat{x}_{k})+\langle\tilde{s}_{k},u-\hat{x}_{k}\rangle;$
(9)

  * b)

$\tilde{s}_{k}\in\partial_{\tilde{\eta}_{k}}\tilde{\phi}(\hat{y}_{k})$ and

$0\leq 2{\lambda}_{k}\tilde{\eta}_{k}\leq
2{\lambda}_{k}\varepsilon-(1+\nu{\lambda}_{k})\|\hat{y}_{k}-\hat{x}_{k}\|^{2}+(1-\chi)\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2};$
(10)

  * c)

for any $\chi\in[0,1)$ and every $u\in\mathrm{dom}\,\phi$, we have

$\tilde{\phi}(u)\geq\tilde{\phi}(\hat{y}_{k})+\langle\tilde{s}_{k},u-\hat{y}_{k}\rangle+\frac{\chi(\mu-\nu)}{2}\|u-\hat{y}_{k}\|^{2}-\frac{\tilde{\eta}_{k}}{1-\chi}.$
(11)

Proof: (a) The optimality condition of (5) yields
$0\in\partial\hat{\Gamma}_{k}(\hat{x}_{k})+(\hat{x}_{k}-\hat{x}_{k-1})/\lambda_{k}$.
This inclusion and the fact that
$\partial\hat{\Gamma}_{k}(u)=\partial\tilde{\Gamma}_{k}(u)+\nu u$ for every
$u\in\mathbb{R}^{n}$ imply that

$0\in\partial\tilde{\Gamma}_{k}(\hat{x}_{k})+\nu\hat{x}_{k}+\frac{\hat{x}_{k}-\hat{x}_{k-1}}{{\lambda}_{k}}\stackrel{{\scriptstyle\eqref{defsb}}}{{=}}\partial\tilde{\Gamma}_{k}(\hat{x}_{k})-\tilde{s}_{k}$

where the identity is due to the definition of $\tilde{s}_{k}$ in (6). Hence,
the inclusion in a) holds. Relation (9) immediately follows from the inclusion
in a) and the definition of the subdifferential.

(b) It follows from the relation $\phi\geq\hat{\Gamma}_{k}$ (see step 1 of
FSCO) and the definition of $\tilde{\phi}$ and $\tilde{\Gamma}_{k}$ in (8)
that $\tilde{\phi}\geq\tilde{\Gamma}_{k}$. This inequality, (9), the
definition of $\tilde{\eta}_{k}$ in (7) imply that for every
$u\in\mathrm{dom}\,\phi$,

$\tilde{\phi}(u)\geq\tilde{\Gamma}_{k}(u)\stackrel{{\scriptstyle\eqref{eq:subdifb}}}{{\geq}}\tilde{\Gamma}_{k}(\hat{x}_{k})+\langle\tilde{s}_{k},u-\hat{x}_{k}\rangle\stackrel{{\scriptstyle\eqref{defetab}}}{{=}}\tilde{\phi}(\hat{y}_{k})+\langle\tilde{s}_{k},u-\hat{y}_{k}\rangle-\tilde{\eta}_{k},$

which yields the inclusion in b). Taking $u=\hat{y}_{k}$ in the above
inequality gives $\tilde{\eta}_{k}\geq 0$, and hence the first inequality in
(10) holds. Using the definitions of $\tilde{s}_{k}$ and $\tilde{\eta}_{k}$ in
(6) and (7), respectively, the definitions of $\tilde{\phi}$ and
$\tilde{\Gamma}_{k}$ in (8), and (4) and (5), we have

$\begin{array}[]{lcl}\tilde{\eta}_{k}&\stackrel{{\scriptstyle\eqref{defetab},\eqref{def:t-phi}}}{{=}}&\displaystyle\phi(\hat{y}_{k})-\hat{\Gamma}_{k}(\hat{x}_{k})+\frac{\nu}{2}\left(\|\hat{x}_{k}\|^{2}-\|\hat{y}_{k}\|^{2}\right)-\langle\tilde{s}_{k},\hat{y}_{k}-\hat{x}_{k}\rangle\\\
&\stackrel{{\scriptstyle\eqref{propyb},\eqref{defxhatk}}}{{\leq}}&\displaystyle\left[\varepsilon-\frac{\chi}{2{\lambda}_{k}}\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2}+\frac{1}{2{\lambda}_{k}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}\right]+\frac{\nu}{2}\left(\|\hat{x}_{k}\|^{2}-\|\hat{y}_{k}\|^{2}\right)-\langle\tilde{s}_{k},\hat{y}_{k}-\hat{x}_{k}\rangle\\\
&\stackrel{{\scriptstyle\eqref{defsb}}}{{=}}&\displaystyle\varepsilon-\frac{\chi}{2{\lambda}_{k}}\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2}+\frac{1}{2{\lambda}_{k}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}+\frac{\nu}{2}\left(\|\hat{x}_{k}\|^{2}-\|\hat{y}_{k}\|^{2}\right)+\left\langle\frac{\hat{x}_{k}-\hat{x}_{k-1}}{{\lambda}_{k}}+\nu\hat{x}_{k}\,,\hat{y}_{k}-\hat{x}_{k}\right\rangle\\\
&=&\displaystyle\varepsilon+\frac{1-\chi}{2{\lambda}_{k}}\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2}-\frac{1}{2{\lambda}_{k}}\|\hat{y}_{k}-\hat{x}_{k}\|^{2}-\frac{\nu}{2}\|\hat{y}_{k}-\hat{x}_{k}\|^{2}.\end{array}$

Hence, the second inequality in (10) holds.

(c) Using the inclusion in b), the fact that $\tilde{\phi}$ is
$(\mu-\nu)$-convex, and Lemma A.1 of [16], we have for any
$\zeta\in(0,\infty]$ and every $u\in\mathrm{dom}\,\phi$,

$\tilde{\phi}(u)\geq\tilde{\phi}(\hat{y}_{k})+\langle\tilde{s}_{k},u-\hat{y}_{k}\rangle+\frac{\mu-\nu}{2(1+\zeta)}\|u-\hat{y}_{k}\|^{2}-(1+\zeta^{-1})\tilde{\eta}_{k}.$

Now, (11) follows from the above inequality with $\zeta=(1-\chi)/\chi$ where
$\chi$ is as in step 0 of FSCO.

Before showing Theorem 2.3 on the complexity of FSCO, we also need the
following Proposition 2.2.

###### Proposition 2.2

Consider sequences $\\{\hat{x}_{k}\\}$, $\\{\hat{y}_{k}\\}$, and
$\\{\lambda_{k}\\}$ generated by FSCO. For every $u\in\mathbb{R}^{n}$, we have
for every $k\geq 1$, $u\in\mathbb{R}^{n}$, and $\chi\in[0,1)$, we have:

$\chi(1+\nu{\underline{\lambda}})\|\hat{x}_{k}-\hat{y}_{k}\|^{2}\leq(1-\chi)\|\hat{x}_{k-1}-x_{*}\|^{2}+2{\lambda}_{k}\varepsilon.$
(12)

and

$2\lambda_{k}\left[\phi(\hat{y}_{k})-\phi(u)\right]\leq\frac{2{\lambda}_{k}\varepsilon}{1-\chi}+\left\|\hat{x}_{k-1}-u\right\|^{2}-(1+\sigma)\|\hat{x}_{k}-u\|^{2},$
(13)

where

$\sigma=\sigma(\underline{{\lambda}}):=\frac{\underline{{\lambda}}[\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)]}{1+\mu{\underline{\lambda}}+\chi{\underline{\lambda}}(\nu-\mu)}.$
(14)

Proof: Let
$A(u):=\|\hat{x}_{k-1}-u\|^{2}-(1+\nu{\lambda}_{k})\|\hat{x}_{k}-u\|^{2}$.
Since $A(u)$ is a quadratic function in $u$, its Taylor’s expansion gives

$A(u)=A(\hat{y}_{k})+\langle\nabla
A(\hat{y}_{k}),u-\hat{y}_{k}\rangle+\frac{1}{2}\langle\nabla^{2}A(\hat{y}_{k})(u-\hat{y}_{k}),u-\hat{y}_{k}\rangle,$

where $\nabla^{2}A(\hat{y}_{k})=-2\nu{\lambda}_{k}I$ and

$\nabla
A(\hat{y}_{k})=2(\hat{y}_{k}-\hat{x}_{k-1})-2(1+\nu{\lambda}_{k})(\hat{y}_{k}-\hat{x}_{k})\stackrel{{\scriptstyle\eqref{defsb}}}{{=}}-2\nu{\lambda}_{k}\hat{y}_{k}-2{\lambda}_{k}\tilde{s}_{k}.$

Using the above formulas, we have for $A(u)-A(\hat{y}_{k})$ the expresssion

$\displaystyle\|\hat{x}_{k-1}-u\|^{2}-(1+\nu{\lambda}_{k})\|\hat{x}_{k}-u\|^{2}-\left(\|\hat{x}_{k-1}-\hat{y}_{k}\|^{2}-(1+\nu{\lambda}_{k})\|\hat{x}_{k}-\hat{y}_{k}\|^{2}\right)$
$\displaystyle=-2{\lambda}_{k}\langle\nu\hat{y}_{k}+\tilde{s}_{k},u-\hat{y}_{k}\rangle-\nu{\lambda}_{k}\|u-\hat{y}_{k}\|^{2}=-2{\lambda}_{k}\langle\tilde{s}_{k},u-\hat{y}_{k}\rangle-\nu{\lambda}_{k}(\|u\|^{2}-\|\hat{y}_{k}\|^{2})$
$\displaystyle\stackrel{{\scriptstyle\eqref{qphi-1}}}{{\geq}}2\lambda_{k}\left[\tilde{\phi}(\hat{y}_{k})-\tilde{\phi}(u)+\frac{\chi(\mu-\nu)}{2}\|u-\hat{y}_{k}\|^{2}-\frac{\tilde{\eta}_{k}}{1-\chi}\right]-\nu{\lambda}_{k}(\|u\|^{2}-\|\hat{y}_{k}\|^{2})$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:t-phi}}}{{=}}2\lambda_{k}\left[\phi(\hat{y}_{k})-\phi(u)\right]+\chi(\mu-\nu){\lambda}_{k}\|u-\hat{y}_{k}\|^{2}-\frac{2{\lambda}_{k}\tilde{\eta}_{k}}{1-\chi},$
(15)

where the inequality is due to (11) and the last identity is due to the
definition of $\tilde{\phi}$ in (8). Rearranging the terms in (15) and using
Lemma 2.1(b), we have

$\displaystyle\left\|\hat{x}_{k-1}-u\right\|^{2}-(1+\nu{\lambda}_{k})\|\hat{x}_{k}-u\|^{2}-2\lambda_{k}\left[\phi(\hat{y}_{k})-\phi(u)\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:long}}}{{\geq}}\|\hat{x}_{k-1}-\hat{y}_{k}\|^{2}-(1+\nu{\lambda}_{k})\|\hat{x}_{k}-\hat{y}_{k}\|^{2}+\chi(\mu-\nu){\lambda}_{k}\|u-\hat{y}_{k}\|^{2}-\frac{2{\lambda}_{k}\tilde{\eta}_{k}}{1-\chi}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineqetab}}}{{\geq}}-\frac{2{\lambda}_{k}\varepsilon}{1-\chi}+\frac{\chi(1+\nu{\underline{\lambda}})}{1-\chi}\|\hat{x}_{k}-\hat{y}_{k}\|^{2}+\chi(\mu-\nu){\underline{\lambda}}\|u-\hat{y}_{k}\|^{2},$

where in the last inequality we have used Assumption (F1).

Rearranging the terms and using Assumption (F1), we have

$\displaystyle 2\lambda_{k}\left[\phi(\hat{y}_{k})-\phi(u)\right]\leq$
$\displaystyle\frac{2{\lambda}_{k}\varepsilon}{1-\chi}+\left\|\hat{x}_{k-1}-u\right\|^{2}-(1+\nu{\underline{\lambda}})\|\hat{x}_{k}-u\|^{2}$
$\displaystyle-\chi\left(\frac{1+\nu{\underline{\lambda}}}{1-\chi}\|\hat{x}_{k}-\hat{y}_{k}\|^{2}+(\mu-\nu){\underline{\lambda}}\|u-\hat{y}_{k}\|^{2}\right).$
(16)

It is clear that (12) follows from (16) with $u=x_{*}$ and observing that
$\phi(\hat{y}_{k})-\phi(x_{*})\geq 0$. Using the triangle inequality and the
fact that
$(a_{1}+a_{2})^{2}\leq(b_{1}^{-1}+b_{2}^{-1})(a_{1}^{2}b_{1}+a_{2}^{2}b_{2})$
with $(a_{1},a_{2})=(\|\hat{x}_{k}-\hat{y}_{k}\|,\|u-\hat{y}_{k}\|)$ and
$(b_{1},b_{2})=((1+\nu{\underline{\lambda}})/(1-\chi),(\mu-\nu){\underline{\lambda}})$
we have

$\|\hat{x}_{k}-u\|^{2}\leq\left(\frac{1-\chi}{1+\nu{\underline{\lambda}}}+\frac{1}{(\mu-\nu){\underline{\lambda}}}\right)\left(\frac{1+\nu{\underline{\lambda}}}{1-\chi}\|\hat{x}_{k}-\hat{y}_{k}\|^{2}+(\mu-\nu){\underline{\lambda}}\|u-\hat{y}_{k}\|^{2}\right).$
(17)

Plugging the above ineqaulity into (16), we have

$2\lambda_{k}\left[\phi(\hat{y}_{k})-\phi(u)\right]\leq\frac{2{\lambda}_{k}\varepsilon}{1-\chi}+\left\|\hat{x}_{k-1}-u\right\|^{2}-\left[1+\nu{\underline{\lambda}}+\chi\left(\frac{1-\chi}{1+\nu{\underline{\lambda}}}+\frac{1}{(\mu-\nu){\underline{\lambda}}}\right)^{-1}\right]\|\hat{x}_{k}-u\|^{2},$

which is the same as (13) after simplification.

Before giving the first main complexity result for FSCO, namely, a complexity
bound for obtaining a $\bar{\varepsilon}$-solution of (3), we first introduce
some terminology used throughout our analysis. Let $x_{*}$ denote the closest
solution of (3) to the initial point $\hat{x}_{0}$ of FSCO and let $d_{0}$
denote its distance to $\hat{x}_{0}$, i.e.,

$\|\hat{x}_{0}-x_{*}\|=\min\\{\|x-\hat{x}_{0}\|:x\in X_{*}\\},\quad
d_{0}=\|\hat{x}_{0}-x_{*}\|.$ (18)

###### Theorem 2.3

For a given tolerance $\bar{\varepsilon}>0$, consider FSCO with
$\varepsilon=(1-\chi)\bar{\varepsilon}/2$, where $\chi\in[0,1)$ is as in step
0 of FSCO. Then, the number of iterations of FSCO to generate an iterate
$\hat{y}_{k}$ satisfying $\phi(\hat{y}_{k})-\phi_{*}\leq\bar{\varepsilon}$ is
at most

${\cal
C}_{\text{func}}(\bar{\varepsilon}):=\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right),1+\frac{1}{\underline{{\lambda}}\nu}\right]\log\left(1+\frac{\lambda_{0}\mu
d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right),\frac{d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right\\}.$
(19)

Proof: It is easy to see that (13) with $u=x_{*}$ where $x_{*}$ is given by
(18) satisfies (93) with $\sigma$ is as in (14) and

$\gamma_{k}=2{\lambda}_{k},\quad\eta_{k}=\phi(\hat{y}_{k})-\phi_{*},\quad\alpha_{k}=\|\hat{x}_{k}-x_{*}\|^{2},\quad\delta=\frac{\varepsilon}{1-\chi}.$
(20)

Also, note that

${\underline{\gamma}}=2{\underline{{\lambda}}},\quad
2\delta=\frac{2\varepsilon}{1-\chi}=\bar{\varepsilon}.$

It follows from Lemma A.1(c) with the above parameters and the definition of
$\sigma$ in (14) that the complexity to find a $\bar{\varepsilon}$-solution is

$\min\left\\{\frac{1+\sigma}{\sigma}\log\left(1+\frac{\sigma
d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right),\frac{d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right\\}\stackrel{{\scriptstyle\eqref{def:sigma}}}{{=}}\min\left\\{\frac{(1+\nu\underline{{\lambda}})(1+\mu\underline{{\lambda}})}{\underline{{\lambda}}[\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)]}\log\left(1+\frac{\sigma
d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right),\frac{d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right\\}.$
(21)

Since $\chi\in[0,1)$, it is easy to verify that

$\frac{1+\nu\underline{{\lambda}}}{\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)}\leq\frac{1}{\chi\mu},$

and hence that

$\frac{(1+\nu\underline{{\lambda}})(1+\mu\underline{{\lambda}})}{\underline{{\lambda}}[\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)]}\leq\frac{1+\mu\underline{{\lambda}}}{\chi\underline{{\lambda}}\mu}=\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right).$

Moreover, noting that $\chi\in[0,1)$ and $\mu\geq\nu$, we also have

$\frac{(1+\nu\underline{{\lambda}})(1+\mu\underline{{\lambda}})}{\underline{{\lambda}}[\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)]}\leq
1+\frac{1}{\underline{{\lambda}}\nu}.$

Combining the above two inequalities, we obtain

$\frac{(1+\nu\underline{{\lambda}})(1+\mu\underline{{\lambda}})}{\underline{{\lambda}}[\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)]}\leq\min\left\\{\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right),1+\frac{1}{\underline{{\lambda}}\nu}\right\\}.$

The result now immediately follows from (21), the above inequality, and the
fact that

$\sigma\leq\frac{\underline{{\lambda}}[\nu(1+\mu\underline{{\lambda}})+\chi(\mu-\nu)]}{1+\mu{\underline{\lambda}}}\leq\underline{{\lambda}}\left(\nu+\frac{\chi(\mu-\nu)}{1+\mu\underline{{\lambda}}}\right)\leq{{\lambda}_{0}}\left(\nu+\frac{\chi(\mu-\nu)}{1+\mu{{\lambda}_{0}}}\right)\leq{{\lambda}_{0}}\left(\nu+{(\mu-\nu)}\right)\leq{\lambda}_{0}\mu.$

We now comment on the complexity bound obtained in Theorem 2.3. First, the
bound

$\min\left\\{\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right),1+\frac{1}{\underline{{\lambda}}\nu}\right\\}\log\left(1+\frac{\lambda_{0}\mu
d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right)$ (22)

implied by (19) is meaningful only when $\chi>0$ or $\nu>0$ (otherwise, it
should be understood as being infinity). Second, the validity of the second
bound in (22) is well-known and can be found for example in [7, 14]. Third, if
$\mu\gg\nu$ (see the assumption (F2) in Section 1) and $\chi$ is sufficiently
close to one, the smallest term in (22) is the first one, in which case (19)
reduces to

$\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right)\log\left(1+\frac{\lambda_{0}\mu
d_{0}^{2}}{{\underline{\lambda}}{\bar{\varepsilon}}}\right)=\tilde{\cal
O}\left(\frac{1}{\underline{{\lambda}}\mu}\right).$

Fourth, since the second bound does not depend on $\nu$, $\mu$ and $\chi$, it
holds for any parameters $\mu\geq\nu\geq 0$ and $\chi\in[0,1)$.

The drawback of using the termination criterion
$\phi(\bar{x})-\phi_{*}\leq\bar{\varepsilon}$ is that it requires knowledge of
$\phi_{*}$. The next subsection presents the complexity of FSCO to obtain a
point satisfying a stopping criterion that is easily checkable for any
instance of (3).

###  2.2 Stationarity complexity analysis

This subsection studies the iteration complexity for FSCO to obtain a near-
stationary solution of (3) (see the definition below). Its main result is
stated in Theorem 2.8.

We start by defining the notion of near-stationary solutions considered in
this subsection.

###### Definition 2.4

A triple $(x,v,\eta)$ is called $\phi$-compatible if it satisfies the
inclusion $v\in\partial_{\eta}\phi(x)$. For a given tolerance pair
$(\hat{\rho},\hat{\varepsilon})$, a $\phi$-compatible triple $(x,v,\eta)$ is
called a $(\hat{\rho},\hat{\varepsilon})$-stationary solution of (3) if it
satisfies $\|v\|\leq\hat{\rho}$ and $\eta\leq\hat{\varepsilon}$.

We now comment on the benefits of using near-stationary solutions as a way to
terminate an algorithm. First, many algorithms, including the ones considered
in this paper, naturally generate a sequence of $\phi$-compatible triples
$\\{(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})\\}$ where the sequence of
residual pairs $\\{(\bar{s}_{k},\bar{\varepsilon}_{k})\\}$ can be made
arbitrarily small (see Proposition 2.7 below). As a consequence, some
$(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ will eventually become a
$(\hat{\rho},\hat{\varepsilon})$-stationary solution of (3). Moreover,
verifying this only requires checking whether the two inequalities
$\|\bar{s}_{k}\|\leq\hat{\rho}$ and
$\bar{\varepsilon}_{k}\leq\hat{\varepsilon}$ hold as the inclusion
$\bar{s}_{k}\in\partial_{\bar{\varepsilon}_{k}}\phi(\bar{y}_{k})$ is
guaranteed to hold for every $k\geq 1$. Second, this notion is related to the
one considered in Subsection 2.1 as follows. If
$(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ is a
$(\hat{\rho},\hat{\varepsilon})$-stationary solution and $\mathrm{dom}\,\phi$
has a finite diameter $D$, then it follows that $\bar{y}_{k}$ is a
$(\hat{\varepsilon}+D\hat{\rho})$-solution of (3).

The following lemma will be useful to derive such complexity for stationary
conditions:

###### Lemma 2.5

For every $k\geq 1$, define

$\bar{y}_{k}=\mathrm{argmin}\,\\{\phi(y):y\in\\{\hat{y}_{1},\dots,\hat{y}_{k}\\}\\}$
(23)

and

$S_{k}=\sum_{j=1}^{k}(1+\sigma)^{j-1}\lambda_{j}$ (24)

where $\sigma$ is as in (14). Then, for every $u\in\mathrm{dom}\,\phi$, we
have:

$\displaystyle\phi(\bar{y}_{k})-\phi(u)$
$\displaystyle\leq\frac{\|\hat{x}_{0}-u\|^{2}-(1+\sigma)^{k}\|\hat{x}_{k}-u\|^{2}}{2S_{k}}+\frac{\varepsilon}{1-\chi},$
(25) $\displaystyle\|\hat{x}_{k}-x_{*}\|^{2}$
$\displaystyle\leq\frac{d_{0}^{2}}{(1+\sigma)^{k}}+\frac{2\varepsilon
S_{k}}{(1-\chi)(1+\sigma)^{k}},$ (26)

where $x_{*}$ and $d_{0}$ are as in (18).

Proof: First note that (13) is a special case of (93) with

$\gamma_{k}=2{\lambda}_{k},\quad\eta_{k}=\phi(\hat{y}_{k})-\phi(u),\quad\alpha_{k}=\|\hat{x}_{k}-u\|^{2},\quad\delta=\frac{\varepsilon}{1-\chi}.$

Then, (25) follows from Lemma A.1(a). It is also easy to verify that (13) with
$u=x_{*}$ satisfies (93) with parameters as in (20). Then, (26) follows from
Lemma A.1(b).

###### Lemma 2.6

For every $k\geq 1$, we have

$\displaystyle\|\hat{x}_{0}-\hat{x}_{k}\|^{2}$ $\displaystyle\leq
4\left(d_{0}^{2}+\frac{S_{k}\varepsilon}{1-\chi}\right),$ (27)
$\displaystyle\|\hat{x}_{0}-\bar{y}_{k}\|^{2}$
$\displaystyle\leq\frac{1}{\chi}\left(5d_{0}^{2}+\frac{8S_{k}\varepsilon}{1-\chi}\right).$
(28)

Proof: Using (26) and the fact that $\sigma\geq 0$, we have for every
$i\in\\{1,2,\ldots,k\\}$,

$\displaystyle\|\hat{x}_{i}-x_{*}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:result-2}}}{{\leq}}\frac{d_{0}^{2}}{(1+\sigma)^{i}}+\frac{2\varepsilon
S_{i}}{(1-\chi)(1+\sigma)^{i}}\leq d_{0}^{2}+\frac{2\varepsilon
S_{i}}{1-\chi}\leq d_{0}^{2}+\frac{2\varepsilon S_{k}}{1-\chi}.$ (29)

It follows from the triangle inequality that

$\|\hat{x}_{0}-\hat{x}_{k}\|^{2}\leq(\|\hat{x}_{0}-x_{*}\|+\|\hat{x}_{k}-x_{*}\|)^{2}\leq
2\left[d_{0}^{2}+\|\hat{x}_{k}-x_{*}\|^{2}\right].$

which together with (29) implies (27). Using the triangle inequality and the
fact that
$(a_{1}+a_{2})^{2}\leq(b_{1}^{-1}+b_{2}^{-1})(a_{1}^{2}b_{1}+a_{2}^{2}b_{2})$
with
$(a_{1},a_{2})=\left(\|\hat{x}_{0}-\hat{x}_{k}\|,\|\hat{x}_{k}-\hat{y}_{k}\|\right)$
and $(b_{1},b_{2})=\left(1,\chi(1+\nu{\underline{\lambda}})/(1-\chi)\right)$,
we have

$\displaystyle\|\hat{x}_{0}-\hat{y}_{k}\|^{2}$
$\displaystyle\leq(\|\hat{x}_{0}-\hat{x}_{k}\|+\|\hat{x}_{k}-\hat{y}_{k}\|)^{2}$
$\displaystyle\leq\left(1+\frac{1-\chi}{\chi(1+\nu{\underline{\lambda}})}\right)\left[\|\hat{x}_{0}-\hat{x}_{k}\|^{2}+\frac{\chi(1+\nu{\underline{\lambda}})}{1-\chi}\|\hat{x}_{k}-\hat{y}_{k}\|^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:bound}}}{{\leq}}\frac{1}{\chi}\left(\|\hat{x}_{0}-\hat{x}_{k}\|^{2}+\|\hat{x}_{k-1}-x_{*}\|^{2}+\frac{2{\lambda}_{k}\varepsilon}{1-\chi}\right),$
(30)

where the last inequality is due to (12). Noting that
$\bar{y}_{k}=\hat{y}_{i}$ for some $i\in\\{1,2,\ldots,k\\}$, and using (27),
(29), and (30), we have

$\displaystyle\|\hat{x}_{0}-\bar{y}_{k}\|^{2}$
$\displaystyle=\|\hat{x}_{0}-\hat{y}_{i}\|^{2}\stackrel{{\scriptstyle\eqref{ineq:x0-yk}}}{{\leq}}\frac{1}{\chi}\left[\|\hat{x}_{0}-\hat{x}_{i}\|^{2}+\|\hat{x}_{i-1}-x_{*}\|^{2}+\frac{2{\lambda}_{i}\varepsilon}{1-\chi}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:xk},\eqref{ineq:nl}}}{{\leq}}\frac{1}{\chi}\left(4d_{0}^{2}+\frac{4\varepsilon
S_{k}}{1-\chi}+d_{0}^{2}+\frac{2\varepsilon
S_{k}}{1-\chi}+\frac{2{\lambda}_{i}\varepsilon}{1-\chi}\right)\leq\frac{1}{\chi}\left(5d_{0}^{2}+\frac{8\varepsilon
S_{k}}{1-\chi}\right),$

where the last inequality is due to the fact that
$S_{k}\geq(1+\sigma)^{i-1}\lambda_{i}\geq\lambda_{i}$. Hence, (28) is proved.

The following results shows that FSCO naturally generates a sequence of
residual pairs $\\{(\hat{v}_{k},\hat{\varepsilon}_{k})\\}$ such that
$(\hat{z}_{k},\hat{v}_{k},\hat{\varepsilon}_{k})$ is $\phi$-compatible for
every $k\geq 1$ and provides suitable bounds for it.

###### Proposition 2.7

For every $k\geq 1$, define

$\bar{s}_{k}=\frac{\hat{x}_{0}-\hat{x}_{k}}{S_{k}},\quad\bar{\varepsilon}_{k}=\frac{\|\hat{x}_{0}-\bar{y}_{k}\|^{2}-\|\hat{x}_{k}-\bar{y}_{k}\|^{2}}{2S_{k}}+\frac{\varepsilon}{1-\chi}$
(31)

where $\bar{y}_{k}$ is as in (23). Then, the following statements hold for
every $k\geq 1$:

  * a)

$\bar{s}_{k}\in\partial\phi_{\bar{\varepsilon}_{k}}(\bar{y}_{k})$;

  * b)

the residual pair $(\bar{s}_{k},\bar{\varepsilon}_{k})$ is bounded by

$\|\bar{s}_{k}\|\leq\frac{2d_{0}}{S_{k}}+\frac{\sqrt{2\varepsilon}}{\sqrt{(1-\chi)S_{k}}},\quad\bar{\varepsilon}_{k}\leq\frac{\|\hat{x}_{0}-\bar{y}_{k}\|^{2}}{2S_{k}}+\frac{\varepsilon}{1-\chi},$
(32)

where $S_{k}$ is as in (24).

Proof: (a) Using (25) and the fact that $\sigma\geq 0$, we have for every
$u\in\mathbb{R}^{n}$,

$\displaystyle\phi(\bar{y}_{k})-\phi(u)$
$\displaystyle\leq\frac{\|\hat{x}_{0}-u\|^{2}-\|\hat{x}_{k}-u\|^{2}}{2S_{k}}+\frac{\varepsilon}{1-\chi}$
$\displaystyle=\frac{\|\hat{x}_{0}-\bar{y}_{k}\|^{2}-\|\hat{x}_{k}-\bar{y}_{k}\|^{2}+2\langle\hat{x}_{0}-\hat{x}_{k},\bar{y}_{k}-u\rangle}{2S_{k}}+\frac{\varepsilon}{1-\chi}$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:sk-
ek-1}}}{{=}}\langle\bar{s}_{k},\bar{y}_{k}-u\rangle+\bar{\varepsilon}_{k},$

where the last identity is due to the definitions of $\bar{s}_{k}$ and
$\bar{\varepsilon}_{k}$ in (31). Hence, the statement holds.

(b) Using the triangle inequality, (26), and the fact that
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, we have

$\|\bar{s}_{k}\|\leq\frac{d_{0}+\|\hat{x}_{k}-x_{*}\|}{S_{k}}\stackrel{{\scriptstyle\eqref{ineq:result-2}}}{{\leq}}\frac{d_{0}}{S_{k}}+\frac{1}{S_{k}}\left(\frac{d_{0}}{\sqrt{(1+\sigma)^{k}}}+\frac{\sqrt{2\varepsilon
S_{k}}}{\sqrt{(1-\chi)(1+\sigma)^{k}}}\right).$

Hence, the first inequality in (32) follows from the fact that $\sigma\geq 0$.
Moreover, the second inequality in (32) follows immediately from the
definition of $\bar{\varepsilon}_{k}$ in (31).

The following Theorem 2.8 provides the complexity for stationary conditions
announced in the beginning of this section.

###### Theorem 2.8

For a given tolerance pair
$(\hat{\varepsilon},\hat{\rho})\in\mathbb{R}^{2}_{++}$, FSCO with

$\chi\in(0,1),\quad\varepsilon=\frac{\chi(1-\chi)\hat{\varepsilon}}{10},$ (33)

generates a triple $(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$
satisfying

$\bar{s}_{k}\in\partial\phi_{\bar{\varepsilon}_{k}}(\bar{y}_{k}),\quad\|\bar{s}_{k}\|\leq\hat{\rho},\quad\bar{\varepsilon}_{k}\leq\hat{\varepsilon}$
(34)

in at most

$\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right),1+\frac{1}{\underline{{\lambda}}\nu}\right]\log\left[1+\lambda_{0}\mu\beta(\hat{\varepsilon},\hat{\rho})\right]\,,\,\beta(\hat{\varepsilon},\hat{\rho})\right\\}$
(35)

iterations where

$\beta(\hat{\varepsilon},\hat{\rho})=\frac{1}{\underline{\lambda}}\left(\frac{4\chi\hat{\varepsilon}}{5\hat{\rho}^{2}}+\frac{5d_{0}^{2}}{\chi\hat{\varepsilon}}\right).$
(36)

Proof: First, it follows from Proposition 2.7(a) that the inclusion
$\bar{s}_{k}\in\partial\phi_{\bar{\varepsilon}_{k}}(\bar{y}_{k})$ holds for
every $k\geq 1$. We next show that the number of iterations required for (34)
is at most

$k_{0}:=\min\left\\{\frac{1+\sigma}{\sigma}\log\left[1+\sigma\beta(\hat{\varepsilon},\hat{\rho})\right],\beta(\hat{\varepsilon},\hat{\rho})\right\\}.$
(37)

Hence, it suffices to show that $\|\bar{s}_{k}\|\leq\hat{\rho}$ and
$\bar{\varepsilon}_{k}\leq\hat{\varepsilon}$ for every $k\geq k_{0}$. Using
the definition of $S_{k}$ in (24), assumption (F2), and (98), we have

$S_{k}\geq{\underline{\lambda}}\sum_{j=1}^{k}(1+\sigma)^{j-1}\stackrel{{\scriptstyle\eqref{ineq:theta}}}{{\geq}}{\underline{\lambda}}\max\left\\{\frac{e^{\sigma
k/(1+\sigma)}-1}{\sigma},k\right\\}.$ (38)

It is easy to verify that for every $k\geq k_{0}$, we have

$S_{k}\geq{\underline{\lambda}}\beta(\hat{\varepsilon},\hat{\rho}).$ (39)

It immediately follows from the inequality that $a^{2}+b^{2}\geq 2ab$ and the
definition of $\beta(\hat{\varepsilon},\hat{\rho})$ in (36) that

$\beta(\hat{\varepsilon},\hat{\rho})\geq\frac{4d_{0}}{{\underline{\lambda}}\hat{\rho}}.$
(40)

Using Lemma 2.6, Proposition 2.7(b), (33), the definition of
$\beta(\hat{\varepsilon},\hat{\rho})$ in (36), and the above observation, we
have

$\displaystyle\|\bar{s}_{k}\|$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:sk},\eqref{eq:eps}}}{{\leq}}\frac{2d_{0}}{S_{k}}+\frac{\sqrt{\chi\hat{\varepsilon}}}{\sqrt{5S_{k}}}\stackrel{{\scriptstyle\eqref{def:beta},\eqref{ineq:observation}}}{{\leq}}\frac{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}\hat{\rho}}{2S_{k}}+\frac{\sqrt{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}}\hat{\rho}}{2\sqrt{S_{k}}},$
(41) $\displaystyle\bar{\varepsilon}_{k}$
$\displaystyle\stackrel{{\scriptstyle\eqref{xoytk},\eqref{ineq:sk}}}{{\leq}}\frac{5d_{0}^{2}}{2\chi
S_{k}}+\frac{4\varepsilon}{\chi(1-\chi)}+\frac{\varepsilon}{1-\chi}\stackrel{{\scriptstyle\eqref{eq:eps}}}{{\leq}}\frac{5d_{0}^{2}}{2\chi
S_{k}}+\frac{\hat{\varepsilon}}{2}\stackrel{{\scriptstyle\eqref{def:beta}}}{{\leq}}\frac{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}\hat{\varepsilon}}{2S_{k}}+\frac{\hat{\varepsilon}}{2}.$
(42)

Finally, plugging (39) into (41) and (42), we conclude that
$\|\bar{s}_{k}\|\leq\hat{\rho}$ and
$\bar{\varepsilon}_{k}\leq\hat{\varepsilon}$ for every $k\geq k_{0}$, where
$k_{0}$ is as in (37). It follows from the same argument as in the proof of
Theorem 2.3 that (35) is an upper bound on $k_{0}$. Finally, we conclude that
the theorem holds.

We now make some remarks about Theorem 2.8. In contrast to Theorem 2.3, it
does not apply to the case where $\chi=0$ because the quantity
$\beta(\hat{\varepsilon},\hat{\rho})$ that appears in (35) depends on
$\chi^{-1}$ (see in (36)). The following result considers two special cases
which cover the case $\chi=0$.

###### Theorem 2.9

For a given tolerance pair
$(\hat{\varepsilon},\hat{\rho})\in\mathbb{R}^{2}_{++}$, the following
statements hold for FSCO with $\chi\in[0,1)$:

  * a)

if $\mathrm{dom}\,\phi$ is bounded with diameter $D>0$, then FSCO with
$\varepsilon=(1-\chi)\hat{\varepsilon}/2$ generates a triple
$(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ satisfying (34) within a
number iterations bounded by (35) but with
$\beta(\hat{\varepsilon},\hat{\rho})$ now given by

$\beta(\hat{\varepsilon},\hat{\rho})=\frac{2}{\underline{\lambda}}\left(\frac{2\hat{\varepsilon}}{\hat{\rho}^{2}}+\frac{d_{0}^{2}+D^{2}}{\hat{\varepsilon}}\right);$
(43)

  * b)

the special case of FSCO, where $\varepsilon=(1-\chi)\hat{\varepsilon}/6$ and
$\hat{y}_{k}=\hat{x}_{k}$ for every $k\geq 1$, generates a triple
$(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ satisfying (34) within a
number iterations bounded by (35) but with
$\beta(\hat{\varepsilon},\hat{\rho})$ now given by

$\beta(\hat{\varepsilon},\hat{\rho})=\frac{4}{{\underline{\lambda}}}\left(\frac{\hat{\varepsilon}}{3\hat{\rho}^{2}}+\frac{d_{0}^{2}}{\hat{\varepsilon}}\right).$
(44)

Proof: a) Since $\hat{y}_{k}$ and $x_{*}$ are in $\mathrm{dom}\,\phi$, it
follows from the boundedness assumption that $\|\hat{y}_{k}-x_{*}\|\leq D$.
Using the inequality and the triangle inequality, we have

$\|\hat{x}_{0}-\bar{y}_{k}\|^{2}\leq(\|\hat{x}_{0}-x_{*}\|+\|x_{*}-\bar{y}_{k}\|)^{2}\leq
2(d_{0}^{2}+D^{2}).$

Thus, it follows the second inequality in (32) and the fact that
$\varepsilon=(1-\chi)\hat{\varepsilon}/2$ that

$\bar{\varepsilon}_{k}\stackrel{{\scriptstyle\eqref{ineq:sk}}}{{\leq}}\frac{d_{0}^{2}+D^{2}}{S_{k}}+\frac{\hat{\varepsilon}}{2}\stackrel{{\scriptstyle\eqref{def:beta-1}}}{{\leq}}\frac{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}\hat{\varepsilon}}{2S_{k}}+\frac{\hat{\varepsilon}}{2},$

where the last inequality is due to the definition of
$\beta(\hat{\varepsilon},\hat{\rho})$ in (43). Similarly, using the first
inequality in (32), the fact that $\varepsilon=(1-\chi)\hat{\varepsilon}/2$,
and (43), we have

$\|\bar{s}_{k}\|\stackrel{{\scriptstyle\eqref{ineq:sk}}}{{\leq}}\frac{2d_{0}}{S_{k}}+\frac{\sqrt{\hat{\varepsilon}}}{\sqrt{S_{k}}}\stackrel{{\scriptstyle\eqref{def:beta-1}}}{{\leq}}\frac{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}\hat{\rho}}{2S_{k}}+\frac{\sqrt{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}}\hat{\rho}}{2\sqrt{S_{k}}},$

where the second inequality is also due to the observation that
$\beta(\hat{\varepsilon},\hat{\rho})\geq
4d_{0}/(\underline{\lambda}\hat{\rho})$ in view of (43). Finally, the rest of
the proof follows from the same argument as in the proof of Theorem 2.8.

b) Since $\hat{y}_{k}=\hat{x}_{k}$ for every $k\geq 1$, we know
$\bar{y}_{k}=\hat{y}_{i}=\hat{x}_{i}$ for some $i\in\\{1,2,\ldots,k\\}$. This
observation, (27), and the second inequality in (32) imply that

$\bar{\varepsilon}_{k}\stackrel{{\scriptstyle\eqref{ineq:sk}}}{{\leq}}\frac{\|\hat{x}_{0}-\hat{x}_{i}\|^{2}}{2S_{k}}+\frac{\varepsilon}{1-\chi}\stackrel{{\scriptstyle\eqref{ineq:xk}}}{{\leq}}\frac{2d_{0}^{2}}{S_{k}}+\frac{2\varepsilon
S_{i}}{(1-\chi)S_{k}}+\frac{\varepsilon}{1-\chi}\leq\frac{2d_{0}^{2}}{S_{k}}+\frac{3\varepsilon}{1-\chi},$

where the last inequality is due to the fact that $S_{i}\leq S_{k}$ for $i\leq
k$. It follows from the fact that $\varepsilon=(1-\chi)\hat{\varepsilon}/6$
and the definition of $\beta(\hat{\varepsilon},\hat{\rho})$ in (44) that

$\bar{\varepsilon}_{k}\leq\frac{2d_{0}^{2}}{S_{k}}+\frac{\hat{\varepsilon}}{2}\stackrel{{\scriptstyle\eqref{def:beta-2}}}{{\leq}}\frac{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}\hat{\varepsilon}}{2S_{k}}+\frac{\hat{\varepsilon}}{2}.$

Similarly, using the first inequality in (32), the fact that
$\varepsilon=(1-\chi)\hat{\varepsilon}/6$, and (44), we have

$\|\bar{s}_{k}\|\stackrel{{\scriptstyle\eqref{ineq:sk}}}{{\leq}}\frac{2d_{0}}{S_{k}}+\frac{\sqrt{\hat{\varepsilon}}}{\sqrt{3S_{k}}}\stackrel{{\scriptstyle\eqref{def:beta-2}}}{{\leq}}\frac{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}\hat{\rho}}{2S_{k}}+\frac{\sqrt{\beta(\hat{\varepsilon},\hat{\rho}){\underline{\lambda}}}\hat{\rho}}{2\sqrt{S_{k}}},$

where the second inequality is also due to the observation that
$\beta(\hat{\varepsilon},\hat{\rho})\geq
4d_{0}/(\underline{\lambda}\hat{\rho})$ in view of (44). Finally, the rest of
the proof follows from the same argument as in the proof of Theorem 2.8.

Compared to the complexity result of Theorem 2.8 (which does not apply to
$\chi=0$) where term $\chi$ appears in the denominator, the one of Theorem 2.9
(which applies to $\chi=0$) involves a term
$\beta(\hat{\varepsilon},\hat{\rho})$ where the term $\chi$ is now removed
from the denominator.

##  3 Universal composite subgradient and proximal bundle methods

This section presents the two $\mu$-universal methods for solving (1), namely,
U-CS in Subsection 3.1 and U-PB in Subsection 3.2. We prove that both methods
are instances of FSCO and establish their iteration complexities in terms of
function value and stationarity based on the analysis in Section 2.

We assume that conditions (A1) and (A2) hold for (1). We also assume that

  * (A3)

$h\in\overline{\mbox{\rm Conv}}_{\nu}\,(\mathbb{R}^{n})$ for some
$0\leq\nu\leq\mu$;

  * (A4)

$f\in\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$ is 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;

  * (A5)

there exists $(M_{f},L_{f})\in\mathbb{R}^{2}_{+}$ such that for every
$x,y\in\mathrm{dom}\,h$,

$\|f^{\prime}(x)-f^{\prime}(y)\|\leq 2M_{f}+L_{f}\|x-y\|.$

It is well known that (A5) implies that for every $x,y\in\mathrm{dom}\,h$,

$f(x)-\ell_{f}(x;y)\leq 2M_{f}\|x-y\|+\frac{L_{f}}{2}|x-y|2.$ (45)

Also, for a given tolerance $\varepsilon>0$, the fact that the set
$\Omega:=\\{(M_{f},L_{f})\in\mathbb{R}^{2}_{+}:\mbox{(A5) holds with
}(M_{f},L_{f})\\}$ is a (nonempty) closed convex set implies that there exists
a unique pair
$(\overline{M}_{f},\overline{L}_{f}):=(\overline{M}_{f}(\varepsilon),\overline{L}_{f}(\varepsilon))$
that minimizes $M_{f}^{2}+\varepsilon L_{f}$ over $\Omega$ (referred to as the
$\varepsilon$-best pair).

###  3.1 A universal composite subgradient method

The U-CS method is a variant of the universal primal gradient method of [18]
by introducing a parameter $\chi\in[0,1)$. It can also be shown as an instance
of FSCO, and we thus establish its complexity using the analysis in Section 2.
The method is described below.

U-CS

  * 0.

Let $\hat{x}_{0}\in\mathrm{dom}\,h$, $\chi\in[0,1)$, ${\lambda}_{0}>0$, and
$\varepsilon>0$ be given, and set ${\lambda}={\lambda}_{0}$ and $j=1$;

  * 1.

Compute

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

  * 2.

If
$f(x)-\ell_{f}(x;\hat{x}_{j-1})-(1-\chi)\|x-\hat{x}_{j-1}\|^{2}/(2{\lambda})\leq\varepsilon$
does not hold, then set ${\lambda}={\lambda}/2$ and go to step 1; else, go to
step 3;

  * 3.

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

We now make some remarks about U-CS. First, no stopping criterion is added to
it since our goal is to analyze its iteration-complexity for obtaining two
types of approximate solutions, i.e., either a $\bar{\varepsilon}$-solution
(see Theorem 3.2 below) or a $(\hat{\rho},\hat{\varepsilon})$-stationary
solution (see Theorem 3.3 below). Second, U-CS with $\chi=0$ and
$\varepsilon=\bar{\varepsilon}/2$ is exactly the universal primal gradient
method analyzed in [18]. Hence, with the introduction of the damping parameter
$\chi$, U-CS can be viewed as a generalization of the method of [18].

The following result shows that U-CS is an instance of FSCO and that
assumptions (F1) and (F2) of Section 2 are satisfied.

###### Proposition 3.1

The following statements hold for U-CS:

  * a)

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

  * b)

for every $k\geq 1$, we have

$\displaystyle\hat{x}_{k}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\ell_{f}(u;\hat{x}_{k-1})+h(u)+\frac{1}{2{\lambda}_{k}}\|u-\hat{x}_{k-1}\|^{2}\right\\},$
(46) $\displaystyle
f(\hat{x}_{k})-\ell_{f}(\hat{x}_{k};\hat{x}_{k-1})+\frac{\chi-1}{2\lambda_{k}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}\leq\varepsilon,$
(47)
$\displaystyle{\lambda}_{k}\geq\underline{{\lambda}}(\varepsilon):=\min\left\\{\frac{(1-\chi)\varepsilon}{4\left({\overline{M}}_{f}^{2}+\varepsilon{\overline{L}}_{f}\right)},{\lambda}_{0}\right\\}.$
(48)

  * c)

U-CS is a special case of FSCO where:

    * i)

$\hat{y}_{k}=\hat{x}_{k}$ and
$\hat{\Gamma}_{k}(\cdot)=\ell_{f}(\cdot;\hat{x}_{k-1})+h(\cdot)$ for every
$k\geq 1$;

    * ii)

assumptions (F1) and (F2) are satisfied with
$\underline{{\lambda}}={\underline{\lambda}}(\varepsilon)$ given by (48) and
$\nu$ from assumption (A3).

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

b) Relations (46) and (47) directly follow from the description of U-CS. Using
(45) with
$(M_{f},L_{f},u,v)=(\overline{M}_{f},\overline{L}_{f},\hat{x}_{k},\hat{x}_{k-1})$
and the inequality $a^{2}+b^{2}\geq 2ab$ for $a,b\in\mathbb{R}$, we have

$\displaystyle
f(\hat{x}_{k})-\ell_{f}(\hat{x}_{k};\hat{x}_{k-1})+\frac{\chi-1}{2\lambda_{k-1}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:est}}}{{\leq}}2\overline{M}_{f}\|\hat{x}_{k}-\hat{x}_{k-1}\|+\frac{\overline{L}_{f}}{2}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}+\frac{\chi-1}{2\lambda_{k-1}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}$
$\displaystyle=2\overline{M}_{f}\|\hat{x}_{k}-\hat{x}_{k-1}\|-\frac{1-\chi-{\lambda}_{k-1}\overline{L}_{f}}{2{\lambda}_{k-1}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}$
$\displaystyle\leq\frac{2{\lambda}_{k-1}\overline{M}_{f}^{2}}{1-\chi-{\lambda}_{k-1}\overline{L}_{f}}.$
(49)

Observe that
${\lambda}_{k-1}\leq(1-\chi)\varepsilon/(2(\overline{M}_{f}^{2}+\overline{L}_{f}\varepsilon))$
implies that
${\lambda}_{k-1}\leq(1-\chi)\varepsilon/(2\overline{M}_{f}^{2}+\overline{L}_{f}\varepsilon)$,
and hence that

$\frac{2{\lambda}_{k-1}\overline{M}_{f}^{2}}{1-\chi-{\lambda}_{k-1}\overline{L}_{f}}\leq\varepsilon.$

The above inequality and (49) thus imply that (47) holds with ${\lambda}_{k}$
replaced by $\lambda_{k-1}$. This indicates that if ${\lambda}$ is small
enough, then it will remain unchanged. Therefore, following from the update
scheme of ${\lambda}$ in step 2 of U-CS, there is a lower bound
$\underline{{\lambda}}(\varepsilon)$ as in (48).

c) Relations (46) and (47) are the analogues of relations (4) and (5) of FSCO
with $\hat{y}_{k}=\hat{x}_{k}$ and $\hat{\Gamma}_{k}$ as in (i). Inequality
(48) shows that Assumption (F2) is satisfied with
$\underline{{\lambda}}={\underline{\lambda}}(\varepsilon)$. Finally, in the
$k$-th iteration of U-CS, the model $\hat{\Gamma}_{k}$ for $\phi=f+h$ being
simply the linearization $\ell_{f}(\cdot,\hat{x}_{k-1})+h(\cdot)$ with
$h\in\overline{\mbox{\rm Conv}}_{\nu}\,(\mathbb{R}^{n})$ for some
$0\leq\nu\leq\mu$ (from Assumption (A3)), we obtain that Assumption (F1) is
satisfied.

We are now in a position to state the main result for the functional
complexity of U-CS.

###### Theorem 3.2

Let $\bar{\varepsilon}>0$ be given and consider U-CS with
$\varepsilon=(1-\chi)\bar{\varepsilon}/2$, where $\chi\in[0,1)$ is as in step
0 of U-CS. Then, the number of iterations of U-CS to generate an iterate
$\hat{x}_{k}$ satisfying $\phi(\hat{x}_{k})-\phi_{*}\leq\bar{\varepsilon}$ is
at most

$\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{Q_{f}({\bar{\varepsilon}})}{\mu{\bar{\varepsilon}}}\right),1+\frac{Q_{f}({\bar{\varepsilon}})}{\nu{\bar{\varepsilon}}}\right]\log\left(1+\frac{\lambda_{0}\mu
Q_{f}(\bar{\varepsilon})d_{0}^{2}}{\bar{\varepsilon}^{2}}\right)\,,\,\frac{d_{0}^{2}Q_{f}({\bar{\varepsilon}})}{{\bar{\varepsilon}}^{2}}\right\\}+\displaystyle\left\lceil
2\log\frac{\lambda_{0}Q_{f}({\bar{\varepsilon}})}{\bar{\varepsilon}}\right\rceil$
(50)

where

$Q_{f}({\bar{\varepsilon}})=\frac{8\overline{M}_{f}^{2}}{(1-\chi)^{2}}+{\bar{\varepsilon}}\left({\lambda}_{0}^{-1}+\frac{8\overline{L}_{f}}{(1-\chi)^{2}}\right)$
(51)

Proof: Define

$\bar{k}=\left\lceil
2\log\max\left\\{\frac{4\lambda_{0}(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}{(1-\chi){\varepsilon}},1\right\\}\right\rceil.$
(52)

Observe that $\lambda_{0}/2^{k}\leq{\underline{\lambda}}(\varepsilon)$ for
$k\geq\bar{k}$, and from Lemma 3.1 that we cannot halve $\lambda$ more than
$\bar{k}$ iterations. It follows from $\varepsilon\leq{\bar{\varepsilon}}$
that
$\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f}\leq\overline{M}_{f}^{2}+{\bar{\varepsilon}}\overline{L}_{f}$,
which together with $\varepsilon=(1-\chi)\bar{\varepsilon}/2$ implies that

$\bar{k}\leq\displaystyle\left\lceil
2\log\frac{\lambda_{0}Q_{f}({\bar{\varepsilon}})}{\bar{\varepsilon}}\right\rceil.$

Therefore, the second term on the right-hand side of (50) gives an upper bound
on the number of iterations with backtracking of $\lambda$. We now provide a
bound on the number of remaining iterations to obtain a
$\bar{\varepsilon}$-solution with U-CS. Theorem 2.3 (which can be applied
since we have shown that U-CS is a special case of FSCO) gives for U-CS the
upper bound

$\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{1}{\underline{\lambda}(\varepsilon)\mu}\right),1+\frac{1}{\underline{\lambda}(\varepsilon)\nu}\right]\log\left(1+\frac{\lambda_{0}\mu
d_{0}^{2}}{{\underline{\lambda}(\varepsilon)}\bar{\varepsilon}}\right),\frac{d_{0}^{2}}{\underline{\lambda}(\varepsilon){\bar{\varepsilon}}}\right\\}$
(53)

on the number of the remaining iterations (where $\lambda$ is not halved)
required to find an $\varepsilon$-optimal solution of (1) with
${\underline{\lambda}}(\varepsilon)$ given by (48). Using the inequality

$\frac{1}{\underline{{\lambda}}(\varepsilon)}=\max\left\\{\frac{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}{(1-\chi)\varepsilon},\frac{1}{\lambda_{0}}\right\\}\leq\frac{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}{(1-\chi)\varepsilon}+\frac{1}{\lambda_{0}},$
(54)

the assumption that $\varepsilon=(1-\chi)\bar{\varepsilon}/2$, and the
definition of $Q_{f}(\bar{\varepsilon})$ in (51), we conclude that
$1/\underline{{\lambda}}(\varepsilon)\leq
Q_{f}(\bar{\varepsilon})/\bar{\varepsilon}$. This observation and (53) thus
imply that the first term in (50) is an upper bound on the number of the
remaining iterations (where $\lambda$ is not halved). This completes the
proof.

We now make some comments about Theorem 3.2. First, Theorem 3.2 applies to any
$\chi\in[0,1)$, and hence to the universal primal gradient method of [18]. In
this case, if $\lambda_{0}^{-1}={\cal O}(1)$, then the strong convexity part
of the bound in (50) is

$\tilde{\cal
O}\left(\frac{Q_{f}(\bar{\varepsilon})}{\nu{\bar{\varepsilon}}}\right)=\tilde{\cal
O}\left(\frac{\overline{M}_{f}^{2}}{\nu{\bar{\varepsilon}}}+\frac{\overline{L}_{f}}{\nu}\right),$
(55)

which is identical to the one in Proposition C.3 of [15]. Second, if $\chi>0$
and $\lambda_{0}^{-1}={\cal O}(1)$, then the complexity bound (50) is also

$\tilde{\cal
O}\left(\frac{Q_{f}(\bar{\varepsilon})}{\chi\mu{\bar{\varepsilon}}}\right)=\tilde{\cal
O}\left(\frac{\overline{M}_{f}^{2}}{\chi\mu{\bar{\varepsilon}}}+\frac{\overline{L}_{f}}{\chi\mu}\right),$
(56)

which is smaller than (55) whenever $\chi\mu\geq\nu$. For example, if
$\chi=1/2$ and $\mu\gg\nu$, then (56) is quite smaller than (55). In summary,
the performance of the U-CS with the damping parameter $\chi>0$ depends on the
strong convexity parameter $\mu$ of the overall objective function $\phi$ and
hence is potentially more universal than the universal primal gradient method
of [18] whose complexity bound depends only on the strong convexity parameter
$\nu$ of the composite function $h$.

The following result states the complexity of stationary complexity of U-CS.

###### Theorem 3.3

For a given tolerance pair
$(\hat{\varepsilon},\hat{\rho})\in\mathbb{R}^{2}_{++}$, consider U-CS with
$\chi\in[0,1)$ and $\varepsilon=(1-\chi)\hat{\varepsilon}/6$. Define
$\bar{y}_{k}$ as in (23) with sequence $\\{\hat{y}_{k}\\}$ replaced by
$\\{\hat{x}_{k}\\}$, and let $\bar{s}_{k}$ and $\bar{\varepsilon}_{k}$ be as
in (31) where the sequence $\\{\hat{x}_{k}\\}$ is generated by U-CS. Then for
every $k\geq 1$, U-CS generates a triple
$(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ satisfying (34) within a
number of iterations bounded by

$\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{Q_{s}({\hat{\varepsilon}})}{\mu{\hat{\varepsilon}}}\right),1+\frac{Q_{s}({\hat{\varepsilon}})}{\nu{\hat{\varepsilon}}}\right]\log
C(\hat{\varepsilon},\hat{\rho})\,,\,\frac{4Q_{s}(\hat{\varepsilon})}{\hat{\varepsilon}}\left(\frac{\hat{\varepsilon}}{3{\hat{\rho}}^{2}}+\frac{d_{0}^{2}}{\hat{\varepsilon}}\right)\right\\}+\displaystyle\left\lceil
2\log\frac{\lambda_{0}Q_{s}({\hat{\varepsilon}})}{\hat{\varepsilon}}\right\rceil$
(57)

where

$C(\hat{\varepsilon},\hat{\rho})=1+\frac{4\lambda_{0}\mu
Q_{s}(\hat{\varepsilon})}{\hat{\varepsilon}}\left(\frac{\hat{\varepsilon}}{3{\hat{\rho}}^{2}}+\frac{d_{0}^{2}}{\hat{\varepsilon}}\right),\quad\displaystyle
Q_{s}({\hat{\varepsilon}})=\frac{24{\overline{M}}_{f}^{2}}{(1-\chi)^{2}}+{\hat{\varepsilon}}\left(\frac{1}{{\lambda}_{0}}+\frac{24{\overline{L}}_{f}}{(1-\chi)^{2}}\right).$

Proof: Same as in the proof of Theorem 3.2, integer $\bar{k}$ given by (52)
gives an upper bound on the number of iterations where $\lambda$ is halved.
Using $\varepsilon=(1-\chi)\hat{\varepsilon}/6$ and
$\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f}\leq\overline{M}_{f}^{2}+{\hat{\varepsilon}}\overline{L}_{f}$,
we have that

$\bar{k}\leq\displaystyle\left\lceil
2\log\frac{\lambda_{0}Q_{s}({\hat{\varepsilon}})}{\hat{\varepsilon}}\right\rceil,$

which gives the second term on the right-hand side of (57). Next, using
Theorem 2.9(b) (observe that this theorem can be applied to U-CS since we have
$\hat{y}_{k}=\hat{x}_{k}$ for U-CS and we consider the possibility for $\chi$
to be 0), the number of remaining iterations to satisfy (34) is upper bounded
by

$\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}(\varepsilon)\mu}\right),1+\frac{1}{\underline{{\lambda}}(\varepsilon)\nu}\right]\log\left[1+\lambda_{0}\mu\beta(\hat{\varepsilon},\hat{\rho})\right]\,,\,\beta(\hat{\varepsilon},\hat{\rho})\right\\}$
(58)

where

$\beta(\hat{\varepsilon},\hat{\rho})=\frac{4}{{\underline{\lambda}(\varepsilon)}}\left(\frac{\hat{\varepsilon}}{3\hat{\rho}^{2}}+\frac{d_{0}^{2}}{\hat{\varepsilon}}\right)$

with ${\underline{\lambda}}(\varepsilon)$ given by (48). Now, using the
inequality (54), the assumption that
$\varepsilon=(1-\chi)\hat{\varepsilon}/6$, and the definition of
$Q_{s}(\hat{\varepsilon})$ in (51), we conclude that
$1/\underline{{\lambda}}(\varepsilon)\leq
Q_{s}(\hat{\varepsilon})/\hat{\varepsilon}$. This observation and (58) then
imply that the first term in (57) is an upper bound on the number of the
remaining iterations (where $\lambda$ is not halved) required to satisfy (34).
This completes the proof.

It is easy to see that when $\lambda_{0}$ is large, $\chi$ is close to $1$,
and $\mu\gg\nu$, the upper bound (57) on the number of iterations for U-CS to
generate a triple $(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ satisfying
(34) reduces again to (56).

###  3.2 A universal proximal bundle method

This subsection describes the U-PB method and establishes its iteration
complexities. More specifically, § 3.2.1 describes U-PB and states the main
results, namely Theorems 3.6 and 3.7, and § 3.2.2 is devoted to the proof of a
technical result (i.e., Proposition 3.4) that is crucial to the proof of the
main results. Conditions (A1)-(A5) are assumed to hold in this subsection.

####  3.2.1 Description of U-PB and related complexity results

The U-PB method is an extension of the GPB method of [15]. In contrast to GPB,
we use an adaptive stepsize and introduce a maximal number $\overline{N}$
(which can be as small as one) of iterations for all cycles. Similarly to
U-CS, U-PB is another instance of FSCO and we establish both functional and
stationary complexities for U-PB using the results of Section 2. Compared with
the complexity results in [15], those obtained in this paper are sharper,
since they are expressed in terms of $\mu=\mu_{\phi}$ instead of $\mu_{h}$.

U-PB is based on the following bundle update (BU) blackbox which builds a
model $f_{M}^{+}+h$ for $f+h$ on the basis of a previous model $f_{M}$ of $f$
and of a new linearization $\ell_{f}(\cdot,x)$ of $f$. This blackbox
BU$(x^{c},x,f_{M},\lambda)$ is given below and takes as inputs a prox-center
$x^{c}$, a current approximate solution $x$, an initial model $f_{M}$ for $f$,
and a stepsize $\lambda>0$.

BU$(x^{c},x,f_{M},\lambda)$

Inputs: ${\lambda}\in\mathbb{R}_{++}$ and
$(x^{c},x,f_{M})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times{\overline{\mbox{Conv}}}(\mathbb{R}^{n})$
such that $f_{M}\leq f$ and

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

Find function $f_{M}^{+}$ such that

$f_{M}^{+}\in{\overline{\mbox{Conv}}}(\mathbb{R}^{n}),\qquad\max\\{{\overline{f}},\ell_{f}(\cdot;x)\\}\leq
f_{M}^{+}\leq f,$ (59)

where $\ell_{f}(\cdot;\cdot)$ is as in (2) and $\overline{f}$ is such that

$\overline{f}\leq
f,\quad\overline{f}\in{\overline{\mbox{Conv}}}(\mathbb{R}^{n}),\quad\overline{f}(x)=f(x),\quad
x=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\overline{f}(u)+h(u)+\frac{1}{2{\lambda}}\|u-x^{c}\|^{2}\right\\}.\\\
$ (60)

Output: $f_{M}^{+}$.

In the following, we give two examples of BU, namely two-cuts and multiple-
cuts schemes. The proofs for the two schemes belonging to BU can be provided
similarly to Appendix D of [15].

  * (E1)

two-cuts scheme: We assume that $f_{M}$ is of the form
$f_{M}=\max\\{A_{f},\ell_{f}(\cdot;x^{-})\\}$ where $A_{f}$ is an affine
function satisfying $A_{f}\leq f$. The scheme then sets
$A_{f}^{+}(\cdot):=\theta A_{f}(\cdot)+(1-\theta)\ell_{f}(\cdot;x^{-})$ and
updates $f_{M}^{+}$ as
$f_{M}^{+}(\cdot):=\max\\{A_{f}^{+}(\cdot),\ell_{f}(\cdot;x)\\}$, where
$\theta\in[0,1]$ satisfies

$\displaystyle\frac{1}{{\lambda}}(x-x^{c})+\partial h(x)+\theta\nabla
A_{f}+(1-\theta)f^{\prime}(x^{-})\ni 0,$ $\displaystyle\theta
A_{f}(x)+(1-\theta)\ell_{f}(x;x^{-})=\max\\{A_{f}(x),\ell_{f}(x;x^{-})\\}.$

  * (E2)

multiple-cuts scheme: We assume that $f_{M}$ has the form
$f_{M}=f_{M}(\cdot;B)$ where $B\subset\mathbb{R}^{n}$ is the current bundle
set and $f_{M}(\cdot;B)$ is defined as
$f_{M}(\cdot;B):=\max\\{\ell_{f}(\cdot;b):b\in B\\}$. This scheme selects the
next bundle set $B^{+}$ so that $B(x)\cup\\{x\\}\subset B^{+}\subset
B\cup\\{x\\}$ where $B(x):=\\{b\in B:\ell_{f}(x;b)=f_{M}(x)\\}$, and then
outputs $f_{M}^{+}=f_{M}(\cdot;B^{+})$.

Before giving the motivation of U-PB, we briefly review the GPB method of
[15]. GPB is an inexact proximal point method (PPM, with fixed stepsize) in
that, given a prox-center $\hat{x}_{k-1}\in\mathbb{R}^{n}$ and a prox stepsize
${\lambda}>0$, it computes the next prox-center $\hat{x}_{k}$ as a suitable
approximate solution of the prox subproblem

$\hat{x}_{k}\approx\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{(f+h)(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}\right\\}.$
(61)

More specifically, a sequence of prox bundle subproblems of the form

$x_{j}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{(f_{j}+h)(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}\right\\},$
(62)

where $f_{j}\leq f$ is a bundle approximation of $f$, is solved until for the
first time an iterate $x_{j}$ as in (62) approximately solves (61), and such
$x_{j}$ is then set to be $\hat{x}_{k}$. The bundle approximation $f_{j}$ is
sequentially updated, for example, according to either one of the schemes (E1)
and (E2) described above.

U-PB is also an inexact PPM but with variable prox stepsizes (i.e., with
${\lambda}$ in (61) replaced by ${\lambda}_{k}$) instead of a constant one as
in GPB. Given iteration upper limit $\overline{N}\geq 1$ and prox-center
$\hat{x}_{k-1}$, it adaptively computes ${\lambda}_{k}>0$ as follows: starting
with ${\lambda}={\lambda}_{k-1}$, it solves at most $\overline{N}$ prox
subproblems of the form (62) in an attempt to obtain an approximate solution
of (61) and, if it fails, repeats this procedure with ${\lambda}$ divided by
$2$; otherwise, it sets ${\lambda}_{k}$ to be the first successful ${\lambda}$
and $\hat{x}_{k}$ as described in the previous paragraph.

U-PB is given below.

U-PB

  * 0.

Let $\hat{x}_{0}\in\mathrm{dom}\,h$, $\lambda_{1}=\lambda>0$, $\chi\in[0,1)$,
$\varepsilon>0$, and integer $\overline{N}\geq 1$ be given, and set
$y_{0}=\hat{x}_{0}$, $N=0$, $j=1$, and $k=1$. Find
$f_{1}\in\overline{\mbox{Conv}}(\mathbb{R}^{n})$ such that
$\ell_{f}(\cdot;{\hat{x}}_{0})\leq f_{1}\leq f$;

  * 1.

Compute $x_{j}$ as in (62);

  * 2.

Choose $y_{j}\in\\{x_{j},y_{j-1}\\}$ such that

$\phi(y_{j})+\frac{\chi}{2{\lambda}}\|y_{j}-\hat{x}_{k-1}\|^{2}=\min\left\\{\phi(x_{j})+\frac{\chi}{2{\lambda}}\|x_{j}-\hat{x}_{k-1}\|^{2},\phi(y_{j-1})+\frac{\chi}{2{\lambda}}\|y_{j-1}-\hat{x}_{k-1}\|^{2}\right\\},$
(63)

and set $N=N+1$ and

$t_{j}=\phi(y_{j})+\frac{\chi}{2{\lambda}}\|y_{j}-\hat{x}_{k-1}\|^{2}-\left((f_{j}+h)(x_{j})+\frac{1}{2{\lambda}}\|x_{j}-\hat{x}_{k-1}\|^{2}\right);$
(64)

  * 3.

If $t_{j}>\varepsilon$ and $N<\overline{N}$ then
perform a null update, i.e.: set
$f_{j+1}=\mbox{BU}(\hat{x}_{k-1},x_{j},f_{j},\lambda)$;
else
if $t_{j}>\varepsilon$ and $N=\overline{N}$
perform a reset update, i.e., set $\lambda\leftarrow\lambda/2$;
else (i.e., $t_{j}\leq\varepsilon$ and $N\leq\overline{N}$)
perform a serious update, i.e., set $\hat{x}_{k}=x_{j}$,
$\hat{\Gamma}_{k}=f_{j}+h$, $\hat{y}_{k}=y_{j}$, $\lambda_{k}=\lambda$, and
$k\leftarrow k+1$;
end if
set $N=0$ and find $f_{j+1}\in\overline{\mbox{Conv}}(\mathbb{R}^{n})$ such
that $\ell_{f}(\cdot;{\hat{x}}_{k-1})\leq f_{j+1}\leq f$;

end if

  * 4.

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

We now give further explanation about U-PB. U-PB performs three types of
iterations, namely, null, reset, and serious, corresponding to the types of
updates performed at the end. A reset (resp., serious) cycle of U-PB consists
of a reset (resp., serious) iteration and all the consecutive null iterations
preceding it. The index $j$ counts the total iterations including null, reset,
and serious ones. The index $k$ counts the serious cycles which, together with
the quantities $\hat{x}_{k}$, $\hat{y}_{k}$, and $\hat{\Gamma}_{k}$ computed
at the end of cycle $k$, is used to cast U-PB as an instance of FSCO. All
iterations within a cycle are referred to as inner iterations. The quantity
$N$ counts the number of inner iterations performed in the current cycle. Each
cycle of U-PB performs at most $\overline{N}$ iterations. A serious cycle
successfully finds $t_{j}\leq\varepsilon$ within $\overline{N}$ iterations,
while a reset cycle fails to do so. In both cases, U-PB resets the counter $N$
to $0$ and starts a new cycle. The differences between the two cases are: 1)
the stepsize ${\lambda}$ is halved at the end of a reset cycle, while it is
kept as is at the end of a serious cycle; and 2) the prox-center is kept the
same at the end of a reset cycle, but it is updated to the latest $x_{j}$ at
the end of a serious cycle.

We now make some remarks about U-PB. First, it follows from the fact that
$f_{j}\leq f$ and the definition of $t_{j}$ in (64) that the primal gap of the
prox subproblem in (61) is upper bounded by
$t_{j}+(1-\chi)\|y_{j}-\hat{x}_{k-1}\|^{2}/(2{\lambda})$. Hence, if
$t_{j}\leq\varepsilon$, then $y_{j}$ is an $\varepsilon_{j}$-solution of (61)
where
$\varepsilon_{j}=\varepsilon+(1-\chi)\|y_{j}-\hat{x}_{k-1}\|^{2}/(2{\lambda})$.
Second, the GPB method of [15] (resp., [14]) computes $y_{j}$ using (63) with
$\chi=0$ (resp., $\chi=1$). In the case where $\chi=1$, it can be easily seen
that $t_{j}$ is an upper bound on the primal gap of the prox subproblem in
(61), and hence that $y_{j}$ is an $\varepsilon$-solution of (61) if
$t_{j}\leq\varepsilon$. Third, the iterate $y_{j}$ computed in step 2 of U-PB
satisfies

$y_{j}\in\mathrm{Argmin}\,\left\\{\phi(x)+\frac{\chi}{2{\lambda}}\|x-\hat{x}_{k-1}\|^{2}:x\in\\{\hat{y}_{k-1},x_{\ell_{0}},\ldots,x_{j}\\}\right\\},$
(65)

where $\ell_{0}$ denotes the first iteration index of the cycle containing
$j$. In other words, $y_{j}$ is the best point in terms of
$\phi(\cdot)+\chi\|\cdot-\hat{x}_{k-1}\|^{2}/(2{\lambda})$ among all the
points obtained in the course of solving (62) and the point $\hat{y}_{k-1}$
obtained at the end of the previous cycle.

The next proposition shows some useful relations about the sequences
$\\{\hat{x}_{k}\\}$, $\\{\hat{y}_{k}\\}$ and $\\{\lambda_{k}\\}$ generated at
the end of the serious cycles of U-PB. This proposition will be proved in §
3.2.2.

###### Proposition 3.4

Define

${\overline{U}}(\varepsilon)=\displaystyle\varepsilon\left[\frac{1}{\lambda_{0}}+\frac{40{\overline{L}}_{f}}{1-\chi}\right]+\frac{32{\overline{M}}_{f}^{2}}{(1-\chi){\overline{N}}}\left(1+\log({\overline{N}})\right).$
(66)

The following statements hold for U-PB:

  * a)

every cycle in U-PB has at most $\overline{N}$ inner iterations;

  * b)

each stepsize $\lambda_{k}$ generated by U-PB satisfies

$\displaystyle\lambda_{k}\geq\frac{\varepsilon}{{\overline{U}}(\varepsilon)};$
(67)

  * c)

the number of reset cycles is upper bounded by

$\displaystyle\left\lceil
2\log\frac{\lambda_{0}{\overline{U}}(\varepsilon)}{\varepsilon}\right\rceil;$
(68)

  * d)

for a serious cycle, the pair $(\hat{x}_{k},\hat{y}_{k})$ of U-PB satisfies

$\displaystyle\hat{x}_{k}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\hat{\Gamma}_{k}(u)+\frac{1}{2{\lambda}_{k}}\|u-\hat{x}_{k-1}\|^{2}\right\\},$
(69)
$\displaystyle\phi(\hat{y}_{k})+\frac{\chi}{2\lambda_{k}}\|\hat{y}_{k}-\hat{x}_{k-1}\|^{2}-\left[\hat{\Gamma}_{k}(\hat{x}_{k})+\frac{1}{2{\lambda}_{k}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}\right]\leq\varepsilon.$
(70)

The following result shows that serious iterations of U-PB generate sequences
$\\{\hat{x}_{k}\\}$, $\\{\hat{y}_{k}\\}$, $\\{\lambda_{k}\\}$, and
$\\{\hat{\Gamma}_{k}\\}$ satisfying the requirements of FSCO.

###### Proposition 3.5

U-PB is a special case of FSCO where:

  * a)

the pair $(\hat{x}_{k},\hat{y}_{k})$ satisfies relations (4) and (5);

  * b)

conditions (F1) and (F2) used in the analysis of FSCO are satisfied.

Proof: a) Relations (4) and (5) are given in Proposition 3.4(d).

b) By Assumption (A3) we have that $\hat{\Gamma}_{k}\in\overline{\mbox{\rm
Conv}}_{\nu}\,(\mathbb{R}^{n})$ and therefore Assumption (F1) of FSCO is
satisfied for U-PB. Assumption (F2) is given for U-PB in Proposition 3.4(b).

We now state the first main result of this subsection where the functional
iteration complexity of U-PB is established.

###### Theorem 3.6

Given tolerance $\bar{\varepsilon}>0$, consider U-PB and
$\varepsilon=(1-\chi)\bar{\varepsilon}/2$, where $\chi\in[0,1)$ is as in step
0 of U-PB. Let $\\{\hat{x}_{k}\\}$ and $\\{\hat{y}_{k}\\}$ be the sequences
generated by U-PB. Then, the number of iterations of U-PB to generate an
iterate $\hat{y}_{k}$ satisfying
$\phi(\hat{y}_{k})-\phi_{*}\leq\bar{\varepsilon}$ is at most

$\min\left\\{\min\left[\frac{1}{\chi}\left({\overline{N}}+\frac{R_{f}({\bar{\varepsilon}})}{\mu{\bar{\varepsilon}}}\right),{\overline{N}}+\frac{R_{f}({\bar{\varepsilon}})}{\nu{\bar{\varepsilon}}}\right]\log\left(1+\frac{\lambda_{0}\mu
R_{f}({\bar{\varepsilon}})d_{0}^{2}}{\bar{\varepsilon}^{2}{\overline{N}}}\right)\,,\,\frac{d_{0}^{2}R_{f}({\bar{\varepsilon}})}{\bar{\varepsilon}^{2}{\overline{N}}}\right\\}+{\overline{N}}\displaystyle\left\lceil
2\log\frac{\lambda_{0}R_{f}({\bar{\varepsilon}})}{{\bar{\varepsilon}}{\overline{N}}}\right\rceil$
(71)

where

$\displaystyle
R_{f}({\bar{\varepsilon}})=\displaystyle{\bar{\varepsilon}}{\overline{N}}\left[\frac{1}{\lambda_{0}}+\frac{40{\overline{L}}_{f}}{1-\chi}\right]+\frac{64{\overline{M}}_{f}^{2}}{(1-\chi)^{2}}\left(1+\log({\overline{N}})\right).$

Proof: Since every serious cycle of U-PB has at most $\overline{N}$ inner
iterations (by Proposition 3.4(a)), the complexity of serious cycles of U-PB
is that of FSCO, given by (19) in Theorem 2.3, multiplied by $\overline{N}$
(observe that the functional complexity of FSCO can be applied to U-PB since
we have shown in Proposition 3.5 that serious iterates of U-PB follow the FSCO
framework). In this expression, by Proposition 3.4(b), we can bound from above
$1/{\underline{\lambda}}$ by ${\overline{U}}(\varepsilon)/\varepsilon\leq
R_{f}(\bar{\varepsilon})/({\bar{\varepsilon}}{\overline{N}})$ which gives the
first term in (71). By Proposition 3.4(c), the number of reset cycles is at
most (68) which is bounded from above by

$\left\lceil
2\log\frac{\lambda_{0}{\overline{U}}(\varepsilon)}{\varepsilon}\right\rceil\leq\left\lceil
2\log\frac{\lambda_{0}R_{f}({\bar{\varepsilon}})}{\bar{\varepsilon}{\overline{N}}}\right\rceil,$

and each of these cycles also has at most $\overline{N}$ inner iterations (by
Proposition 3.4(a)). This gives the second term in (71) and the result
follows.

The complexity result of Theorem 3.6 for the case where $\lambda_{0}$ is not
too small, $\chi$ is neither close to one nor to zero, and $\mu\gg\nu$ reduces
to

$\tilde{\cal
O}\left(\frac{R_{f}(\bar{\varepsilon})}{\mu{\bar{\varepsilon}}}\right)=\tilde{\cal
O}\left(\frac{\overline{M}_{f}^{2}}{\mu{\bar{\varepsilon}}}\right)$ (72)

and we obtain the functional complexity (56) of U-CS. For the case where
$\overline{L}_{f}=0$, the above complexity is optimal up to logarithmic terms.

We now state the second main result of this subsection where the stationary
iteration complexity of U-PB is established.

###### Theorem 3.7

For a given tolerance pair
$(\hat{\varepsilon},\hat{\rho})\in\mathbb{R}^{2}_{++}$, U-PB with

$\chi\in(0,1),\quad\varepsilon=\frac{\chi(1-\chi)\hat{\varepsilon}}{10},$ (73)

generates a triple $(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$
satisfying (34) in at most

$\min\left\\{\min\left[\frac{1}{\chi}\left({\overline{N}}+\frac{R_{s}(\hat{\varepsilon})}{{\hat{\varepsilon}}\mu}\right),{\overline{N}}+\frac{R_{s}(\hat{\varepsilon})}{{\hat{\varepsilon}}\nu}\right]\log
C(\hat{\varepsilon},\hat{\rho}),\,\frac{R_{s}(\hat{\varepsilon})}{\hat{\varepsilon}{\overline{N}}}\left(\frac{4\chi\hat{\varepsilon}}{5\hat{\rho}^{2}}+\frac{5d_{0}^{2}}{\chi\hat{\varepsilon}}\right)\right\\}+{\overline{N}}\displaystyle\left\lceil
2\log\frac{\lambda_{0}R_{s}({\hat{\varepsilon}})}{\hat{\varepsilon}{\overline{N}}}\right\rceil$
(74)

iterations where

$\begin{array}[]{l}\displaystyle
C(\hat{\varepsilon},\hat{\rho})=1+\frac{\lambda_{0}\mu
R_{s}(\hat{\varepsilon})}{\hat{\varepsilon}{\overline{N}}}\left(\frac{4\chi\hat{\varepsilon}}{5\hat{\rho}^{2}}+\frac{5d_{0}^{2}}{\chi\hat{\varepsilon}}\right)\;\emph{
and }\\\
R_{s}(\hat{\varepsilon})=\displaystyle{\hat{\varepsilon}}{\overline{N}}\left[\frac{1}{\lambda_{0}}+\frac{40{\overline{L}}_{f}}{1-\chi}\right]+\frac{320{\overline{M}}_{f}^{2}}{\chi(1-\chi)^{2}}\left(1+\log({\overline{N}})\right).\end{array}$
(75)

Proof: The complexity of serious cycles of U-PB to satisfy stationarity
conditions (34) is that of FSCO, given by (35) in Theorem 2.8, multiplied by
$\overline{N}$. In this expression

$\min\left\\{\min\left[\frac{1}{\chi}\left(1+\frac{1}{\underline{{\lambda}}\mu}\right),1+\frac{1}{\underline{{\lambda}}\nu}\right]\log\left[1+\lambda_{0}\mu\beta(\hat{\varepsilon},\hat{\rho})\right]\,,\,\beta(\hat{\varepsilon},\hat{\rho})\right\\}$

where

$\beta(\hat{\varepsilon},\hat{\rho})=\frac{1}{\underline{\lambda}}\left(\frac{4\chi\hat{\varepsilon}}{5\hat{\rho}^{2}}+\frac{5d_{0}^{2}}{\chi\hat{\varepsilon}}\right),$
(76)

using the expression (73) for $\varepsilon$, we can bound from above
$1/{\underline{\lambda}}$ by ${\overline{U}}(\varepsilon)/{\varepsilon}\leq
R_{s}(\hat{\varepsilon})/({\hat{\varepsilon}}{\overline{N}})$ which gives the
first term in (74). By Proposition 3.4(c), the number of reset cycles is at
most (68) which is bounded from above by

$\left\lceil
2\log\frac{\lambda_{0}R_{s}({\hat{\varepsilon}})}{\hat{\varepsilon}{\overline{N}}}\right\rceil,$

and each of these cycles also has at most $\overline{N}$ inner iterations (by
Proposition 3.4(a)). This gives the second term in (74) and the result
follows.

Theorem 3.7 does not hold for $\chi=0$ since the definitions of
$C(\hat{\varepsilon},\hat{\rho})$ and $R_{s}(\hat{\varepsilon})$ in (75)
depend on $\chi^{-1}$. However, if $\chi=0$ and the domain of $\phi$ is
bounded with diameter $D$, then we can apply Theorem 2.9(b) to conclude that
U-PB with $\varepsilon=(1-\chi)\hat{\varepsilon}/2$ generates a triple
$(\bar{y}_{k},\bar{s}_{k},\bar{\varepsilon}_{k})$ satisfying (34) within a
number iterations bounded by (35) but with
$\beta(\hat{\varepsilon},\hat{\rho})$ now given by (43) and
$1/{\underline{\lambda}}$ bounded from above by
$W_{s}(\hat{\varepsilon})/{\hat{\varepsilon}}$ where

$W_{s}(\hat{\varepsilon})=\displaystyle{\hat{\varepsilon}}\left[\frac{1}{\lambda_{0}}+\frac{40{\overline{L}}_{f}}{1-\chi}\right]+\frac{64{\overline{M}}_{f}^{2}}{(1-\chi)^{2}{\overline{N}}}\left(1+\log({\overline{N}})\right).$

####  3.2.2 Proof of Proposition 3.4

To prove Proposition 3.4, we first state Lemmas 3.8 and 3.9. Lemma 3.8 will be
used to show Lemma 3.9. Lemma 3.9 plays an important role in the analysis of
the null iterates and establishes a key recursive formula for the sequence
$\\{t_{j}\\}$ defined in (64).

###### Lemma 3.8

For the $j$-th iteration of a cycle with prox stepsize $\lambda$ and prox-
center $\hat{x}_{k-1}$, define

$m_{j}:=(f_{j}+h)(x_{j})+\frac{1}{2\lambda}\|x_{j}-\hat{x}_{k-1}\|^{2}.$ (77)

If $j$ is not the last iteration of the cycle, then

$\displaystyle m_{j+1}-\tau m_{j}$
$\displaystyle\geq(1-\tau)\left[\ell_{f}(x_{j+1};x_{j})+h(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-\hat{x}_{k-1}\|^{2}+\left(\frac{\overline{L}_{f}}{2}+\frac{2\overline{M}_{f}^{2}}{\varepsilon}\right)\|x_{j+1}-x_{j}\|^{2}\right],$
(78)

where

$\tau=1-\left(1+\frac{4{\lambda}({\overline{M}}_{f}^{2}+\varepsilon{\overline{L}}_{f})}{\varepsilon}\right)^{-1}.$
(79)

Proof: It follows from the definitions of $\tau$ in (79) that

$\frac{\tau}{2{\lambda}(1-\tau)}\stackrel{{\scriptstyle\eqref{deftauk}}}{{=}}2\overline{L}_{f}+\frac{2\overline{M}_{f}^{2}}{\varepsilon}\geq\frac{\overline{L}_{f}}{2}+\frac{2\overline{M}_{f}^{2}}{\varepsilon}.$
(80)

Using the definition of $m_{j}$ in (77), and relations (99) and (101) with
$u=x_{j+1}$, we have

$\displaystyle m_{j+1}$
$\displaystyle\overset{\eqref{defmj}}{=}(f_{j+1}+h)(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-\hat{x}_{k-1}\|^{2}$
$\displaystyle\overset{\eqref{eq:Gamma_j}}{\geq}(1-\tau)\left[\ell_{f}(x_{j+1};x_{j})+h(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-\hat{x}_{k-1}\|^{2}\right]+\tau\left((\overline{f}_{j}+h)(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-\hat{x}_{k-1}\|^{2}\right)$
$\displaystyle\overset{\eqref{ineq:Gammaj}}{\geq}(1-\tau)\left[\ell_{f}(x_{j+1};x_{j})+h(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-\hat{x}_{k-1}\|^{2}\right]+\tau\left(m_{j}+\frac{1}{2{\lambda}}\|x_{j+1}-x_{j}\|^{2}\right).$

This inequality and (80) then imply (78).

###### Lemma 3.9

The following statements about U-PB hold:

  * a)

for every iteration $j$ that is not the last one of the cycle, we have

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

where $\tau$ is as in (79);

  * b)

if $i$ is the first iteration of the cycle and
$\lambda\leq(1-\chi)/(2{\overline{L}_{f}})$, then

$t_{i}\leq\frac{4{\lambda}\overline{M}_{f}^{2}}{1-\chi}.$ (82)

Proof: a) In what follows, we use the notation

$\psi(\cdot):=\phi(\cdot)+\frac{\chi}{2{\lambda}}\|\cdot-\hat{x}_{k-1}\|^{2}.$
(83)

It follows from the above notation and the definitions of $t_{j}$ and $m_{j}$
in (64) and (77), respectively, that

$t_{j}=\psi(y_{j})-m_{j}\ \mbox{ and }\
\psi(y_{j+1})\stackrel{{\scriptstyle\eqref{def:philam},\eqref{def:txj}}}{{=}}\min\\{\psi(x_{j+1}),\psi(y_{j})).$
(84)

Using (45) with
$(M_{f},L_{f},u,v)=(\overline{M}_{f},\overline{L}_{f},x_{j+1},x_{j})$ and the
fact that $\phi=f+h$, we have

$\ell_{f}(x_{j+1};x_{j})+h(x_{j+1})+\frac{\overline{L}_{f}}{2}\|x_{j+1}-x_{j}\|^{2}\geq\phi(x_{j+1})-2\overline{M}_{f}\|x_{j+1}-x_{j}\|.$
(85)

This inequality, the definition of $\psi$ in (83), and relation (78), imply
that

$\displaystyle m_{j+1}-\tau m_{j}$
$\displaystyle\overset{\eqref{ineq:mj}}{\geq}(1-\tau)\left[\ell_{f}(x_{j+1};x_{j})+h(x_{j+1})+\frac{1}{2{\lambda}}\|x_{j+1}-\hat{x}_{k-1}\|^{2}+\left(\frac{\overline{L}_{f}}{2}+\frac{2\overline{M}_{f}^{2}}{\varepsilon}\right)\|x_{j+1}-x_{j}\|^{2}\right]$
$\displaystyle\overset{\eqref{ineq:ellphi}}{\geq}(1-\tau)\Big{(}\phi(x_{j+1})+\frac{1}{2\lambda}\|x_{j+1}-\hat{x}_{k-1}\|^{2}\Big{)}+\frac{1-\tau}{\varepsilon}\Big{(}2\overline{M}_{f}^{2}\|x_{j+1}-x_{j}\|^{2}-2\overline{M}_{f}\varepsilon\|x_{j+1}-x_{j}\|\Big{)}$
$\displaystyle\overset{\eqref{def:philam}}{=}(1-\tau)\Big{(}\psi(x_{j+1})+\frac{1-\chi}{2\lambda}\|x_{j+1}-\hat{x}_{k-1}\|^{2}\Big{)}+\frac{1-\tau}{\varepsilon}\Big{(}2\overline{M}_{f}^{2}\|x_{j+1}-x_{j}\|^{2}-2\overline{M}_{f}\varepsilon\|x_{j+1}-x_{j}\|\Big{)}$
$\displaystyle\geq(1-\tau)\psi(x_{j+1})-\frac{(1-\tau)\varepsilon}{2},$ (86)

where the last inequality follows from the fact that $\chi<1$ and the
inequality $a^{2}-2ab\geq-b^{2}$ with $a=2\overline{M}_{f}\|x_{j+1}-x_{j}\|$
and $b=\varepsilon$. Using relations (84) and (86), we conclude that

$\displaystyle t_{j+1}-\tau t_{j}$
$\displaystyle\overset{\eqref{eq:tj}}{=}\psi(y_{j+1})-m_{j+1}-\tau t_{j}$
$\displaystyle\overset{\eqref{ineq:mj2b}}{\leq}\psi(y_{j+1})-\tau(m_{j}+t_{j})-(1-\tau)\psi(x_{j+1})+\frac{(1-\tau)\varepsilon}{2}$
$\displaystyle\overset{\eqref{eq:tj}}{=}\psi(y_{j+1})-\tau\psi(y_{j})-(1-\tau)\psi(x_{j+1})+\frac{(1-\tau)\varepsilon}{2}$
$\displaystyle\overset{\eqref{eq:tj}}{\leq}\frac{(1-\tau)\varepsilon}{2},$

and hence that (81) holds.

b) Using relations (77), (83), and (84), we have

$\displaystyle t_{i}$
$\displaystyle\stackrel{{\scriptstyle\eqref{defmj},\eqref{eq:tj}}}{{=}}\psi(y_{i})-\Gamma_{i}(x_{i})-\frac{1}{2\lambda}\|x_{i}-{\hat{x}}_{k-1}\|^{2}\stackrel{{\scriptstyle\eqref{eq:tj}}}{{\leq}}\psi(x_{i})-\Gamma_{i}(x_{i})-\frac{1}{2\lambda}\|x_{i}-{\hat{x}}_{k-1}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:philam}}}{{=}}\phi(x_{i})-\Gamma_{i}(x_{i})+\frac{\chi-1}{2\lambda}\|x_{i}-{\hat{x}}_{k-1}\|^{2}=f(x_{i})-f_{i}(x_{i})+\frac{\chi-1}{2\lambda}\|x_{i}-{\hat{x}}_{k-1}\|^{2},$

where the last equality follows from the facts that $\phi=f+h$ and
$\Gamma_{i}=f_{i}+h$. It follows from U-PB that if $i$ is the first iteration
of the cycle, then

$f_{i}(\cdot)\geq\ell_{f}(\cdot;{\hat{x}}_{k-1}).$ (87)

Combining the above two inequalities and using (45), we obtain

$\displaystyle t_{i}$
$\displaystyle\stackrel{{\scriptstyle\eqref{lbfxj}}}{{\leq}}f(x_{i})-\ell_{f}(x_{i};{\hat{x}}_{k-1})+\frac{\chi-1}{2\lambda}\|x_{i}-{\hat{x}}_{k-1}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ineq:est}}}{{\leq}}2\overline{M}_{f}\|x_{i}-\hat{x}_{k-1}\|+\frac{\overline{L}_{f}}{2}\|x_{i}-{\hat{x}}_{k-1}\|^{2}+\frac{\chi-1}{2\lambda}\|x_{i}-{\hat{x}}_{k-1}\|^{2}$
$\displaystyle=2\overline{M}_{f}\|x_{i}-{\hat{x}}_{k-1}\|-\frac{1-\chi-{\lambda}\overline{L}_{f}}{2{\lambda}}\|x_{i}-{\hat{x}}_{k-1}\|^{2}.$

By maximizing the right-hand side with respect to $\|x_{i}-\hat{x}_{k-1}\|$ we
deduce
$t_{i}\leq(2\lambda_{k}{\overline{M}}_{f}^{2})/(1-\chi-\lambda{\overline{L}}_{f})$
and using the fact that $\lambda\leq(1-\chi)/(2{\overline{L}_{f}})$, we obtain
(82).

Before presenting the proof of Proposition 3.4, we also need the following
technical lemma.

###### Lemma 3.10

Assume that the prox stepsize $\lambda$ of some cycle of U-PB is such that
${\lambda}\leq{\tilde{\lambda}}(\varepsilon)$ where

${\tilde{\lambda}}(\varepsilon)=\left\\{\begin{array}[]{cl}\min\displaystyle\left\\{\frac{({\overline{N}}-1)\varepsilon}{8({\overline{M}}_{f}^{2}+\varepsilon{\overline{L}}_{f})\log({\overline{N}})},\frac{(1-\chi)\exp(-1/2){\overline{N}}\varepsilon}{8\overline{M}_{f}^{2}},\frac{1-\chi}{2{\overline{L}}_{f}}\right\\}&\mbox{if
}{\overline{N}}\geq 2,\\\
\displaystyle\min\left\\{\frac{(1-\chi)\varepsilon}{4{\overline{M}}_{f}^{2}},\frac{1-\chi}{2{\overline{L}}_{f}}\right\\}&\mbox{if
}{\overline{N}}=1.\end{array}\right.$ (88)

Then, this cycle must be a serious one.

Proof: Let $i$ denote the first iteration of a cycle whose prox stepsize
$\lambda$ satisfies (88). It suffices to prove that $t_{\ell}\leq\varepsilon$
where $\ell=i+{\overline{N}}-1$ is the last iteration of the cycle. We
consider two cases: $\overline{N}=1$ and $\overline{N}\geq 2$. If
$\overline{N}=1$, using Lemma 3.9(b) (which can be applied since
$\lambda<(1-\chi)/(2{\overline{L}_{f}}$)) and (88), we have

$t_{\ell}=t_{i}\leq\frac{4{\lambda}\overline{M}_{f}^{2}}{1-\chi}\stackrel{{\scriptstyle\eqref{ublambdak}}}{{\leq}}\varepsilon$

which shows that the cycle is a serious one (with one iteration only). Let us
now consider the case ${\overline{N}}\geq 2$. Lemma 3.9 implies that

$t_{\ell}-\frac{\varepsilon}{2}\stackrel{{\scriptstyle\eqref{ineq:tj-
recur}}}{{\leq}}\tau^{{\overline{N}}-1}\left(t_{i}-\frac{\varepsilon}{2}\right)\leq\tau^{{\overline{N}}-1}t_{i}\stackrel{{\scriptstyle\eqref{ineq:ti}}}{{\leq}}\frac{4{\lambda}\overline{M}_{f}^{2}}{1-\chi}\tau^{{\overline{N}}-1}.$
(89)

It then suffices to show that the right-hand side of (89) is bounded above by
$\varepsilon/2$, or equivalently, that

$\log\left(\frac{8\lambda{\overline{M}}_{f}^{2}}{(1-\chi)\varepsilon}\right)\leq({\overline{N}}-1)\log(\tau^{-1}).$
(90)

Using (88), we have

$\displaystyle\lambda\leq\frac{\varepsilon}{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}\left(\frac{{\overline{N}}-1}{2\log(\overline{N})}\right)$
$\displaystyle\leq\frac{\varepsilon}{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}\left(\frac{{\overline{N}}-1}{2\log(\overline{N})-1}\right)$
$\displaystyle=\frac{\varepsilon}{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}\left(\frac{{\overline{N}}-1}{2\log(\exp(-1/2){\overline{N}})}\right)$
$\displaystyle\leq\frac{\varepsilon}{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})}\left(\frac{{\overline{N}}-1}{\log(\exp(-1/2){\overline{N}})}-1\right)$
(91)

where the last inequality above is easily checked for ${\overline{N}}\geq 2$.
Using (88), (79), and (91), we have

$\frac{\tau^{-1}}{\tau^{-1}-1}=(1-\tau)^{-1}\stackrel{{\scriptstyle\eqref{deftauk}}}{{=}}1+\frac{4(\overline{M}_{f}^{2}+\varepsilon\overline{L}_{f})\lambda}{\varepsilon}\stackrel{{\scriptstyle\eqref{ineqser3}}}{{\leq}}\frac{{\overline{N}}-1}{\log(\exp(-1/2){\overline{N}})}\stackrel{{\scriptstyle\eqref{ublambdak}}}{{\leq}}\frac{{\overline{N}}-1}{\log\left(\frac{8{\overline{M}}_{f}^{2}\lambda}{(1-\chi)\varepsilon}\right)},$

which, because of the inequality $\log(\tau^{-1})\geq(\tau^{-1}-1)/\tau^{-1}$,
implies inequality (90).

We are now ready to prove Proposition 3.4.

Proof of Proposition 3.4. a) This statement immediately follows from the
description of U-PB.

b) By Lemma 3.10, if for a cycle we have
${\lambda}\leq{\tilde{\lambda}}(\varepsilon)$ with
${\tilde{\lambda}}(\varepsilon)$ given in (88), then the cycle ends with a
serious step and $\lambda$ is kept unchanged for all subsequent cycles and all
subsequent cycles are serious cycles. Therefore, if
$\lambda_{0}\leq{\tilde{\lambda}}(\varepsilon)/2$ we have
$\lambda_{k}=\lambda_{0}=\min\\{\lambda_{0},{\tilde{\lambda}}(\varepsilon)/2\\}\geq(\varepsilon/{\overline{U}}(\varepsilon))$
for all $k$ (where the last inequality can be easily checked using the
definitions of $\tilde{\lambda}(\varepsilon)$ and
${\overline{U}}(\varepsilon)$). Otherwise, if
$\lambda_{0}>{\tilde{\lambda}}(\varepsilon)/2$, we cannot have
$\lambda_{k}<{\tilde{\lambda}}(\varepsilon)/{2}$ for some $k$, i.e.,
$\lambda_{k}\geq{\tilde{\lambda}}(\varepsilon)/{2}=\min\\{\lambda_{0},{\tilde{\lambda}}(\varepsilon)/{2}\\}\geq\varepsilon/{\overline{U}}(\varepsilon)$
for all $k$.

c) This statement immediately follows from (b) and the update rule of
${\lambda}$ in U-PB.

d) Relations (69) and (70) (which are (5) and (4) in FSCO, respectively)
follow from (62) and $t_{j}\leq\varepsilon$ with $\hat{x}_{k}=x_{j}$,
$\hat{\Gamma}_{k}=f_{j}+h$, $\hat{y}_{k}=y_{j}$, and $\lambda_{k}=\lambda$
(see the serious update in step 3 of U-PB).

##  4 Concluding remarks

In this paper, we present two $\mu$-universal methods, namely U-CS and U-PB,
to solve HCO (1). We propose FSCO to analyze both methods in a unified manner
and establish both functional and stationary complexity bounds. We then prove
that both U-CS and U-PB are instances of FSCO and apply the complexity bounds
for FSCO to obtain iteration complexities for the two methods. One interesting
property of our proposed methods is that they do not rely on any restart
scheme based on estimating $\mu$ or knowing $\phi_{*}$.

Some papers about universal methods (see for example [10, 18]) assume that,
for some $\alpha\in[0,1]$, $f$ in (1) has $\alpha$-Hölder continuous gradient,
i.e., there exists $L_{\alpha}\geq 0$ such that $\|\nabla f(x)-\nabla
f(y)\|\leq L_{\alpha}\|x-y\|^{\alpha}$ for every $x,y\in\mathrm{dom}\,h$. It
is shown in [18] that the universal primal gradient method proposed on it
(i.e., the U-CS method with $\chi=0$) finds a $\bar{\varepsilon}$-solution of
(1) in

$\tilde{\cal
O}\left(\frac{d_{0}^{2}L_{\alpha}^{\frac{2}{\alpha+1}}}{\bar{\varepsilon}^{\frac{2}{\alpha+1}}}\right)$
(92)

iterations. This result also follows as a consequence of our results in this
paper. Indeed, first note that the dominant term in the iteration complexity
(50) for the U-CS method is $\tilde{\cal
O}(d_{0}^{2}(\overline{M}_{f}^{2}+\bar{\varepsilon}\overline{L}_{f})/\bar{\varepsilon}^{2})$.
Second, Proposition 2.1 of [15] implies that there exists a pair
$(M_{f},L_{f})$ as in (A5) and that the $\bar{\varepsilon}$-best pair, namely
$(\overline{M}_{f},\overline{L}_{f})$, satisfies that

$\overline{M}_{f}^{2}+\bar{\varepsilon}\overline{L}_{f}\leq
2\bar{\varepsilon}^{\frac{2\alpha}{\alpha+1}}L_{\alpha}^{\frac{2}{\alpha+1}},$

Hence, it follows from these two observations that (50) is sharper than bound
(92) obtained in [18].

We finally discuss some possible extensions of our analysis in this paper.
First, it is shown in Theorems 3.2 and 3.3 (resp., Theorem 3.6) that U-CS
(resp., U-PB) is $\mu$-universal if $\chi>0$ and is $\nu$-universal if
$\chi=0$. It would be interesting to investigate whether they are also
$\mu$-universal for $\chi=0$ too. Note that this question is related to
whether the universal primal gradient of [18] (which is the same as U-CS with
$\chi=0$) is $\mu$-universal. Finally, it would also be interesting to study
whether the general results obtained for the FSCO framework can also be used
to show that other methods for solving the HCO problem (1) are
$\mu$-universal.

## References

  * [1] T. Alamo, P. Krupa, and D. Limon.  Gradient based restart FISTA.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3936–3941. IEEE, 2019.
  * [2] T. Alamo, P. Krupa, and D. Limon.  Restart of accelerated first-order methods with linear convergence under a quadratic functional growth condition.  IEEE Transactions on Automatic Control, 68(1):612–619, 2022.
  * [3] T. Alamo, D. Limon, and P. Krupa.  Restart FISTA with global linear convergence.  In 2019 18th European Control Conference (ECC), pages 1969–1974. IEEE, 2019.
  * [4] J-F Aujol, L. Calatroni, C. Dossal, H. Labarrière, and A. Rondepierre.  Parameter-free FISTA by adaptive restart and backtracking.  arXiv preprint arXiv:2307.14323, 2023.
  * [5] J-F Aujol, C. Dossal, and A. Rondepierre.  FISTA is an automatic geometrically optimized algorithm for strongly convex functions.  Mathematical Programming, pages 1–43, 2023.
  * [6] J-F Aujol, C. H. Dossal, H. Labarrière, and A. Rondepierre.  FISTA restart using an automatic estimation of the growth parameter.  Preprint, 2022.
  * [7] Y. Du and A. Ruszczyński.  Rate of convergence of the bundle method.  Journal of Optimization Theory and Applications, 173(3):908–922, 2017.
  * [8] O. Fercoq and Z. Qu.  Adaptive restart of accelerated gradient methods under local quadratic growth condition.  IMA Journal of Numerical Analysis, 39(4):2069–2095, 2019.
  * [9] B. Grimmer.  On optimal universal first-order methods for minimizing heterogeneous sums.  Optimization Letters, pages 1–19, 2023.
  * [10] G. Lan.  Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization.  Mathematical Programming, 149(1-2):1–45, 2015.
  * [11] G. Lan and R. D. C. Monteiro.  Iteration-complexity of first-order penalty methods for convex programming.  Mathematical Programming, 138(1):115–139, 2013.
  * [12] G. Lan, Y. Ouyang, and Z. Zhang.  Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization.  arXiv: 2310.12139, 2023.
  * [13] T. Li and G. Lan.  A simple uniformly optimal method without line search for convex optimization.  arXiv:2310.10082, 2023.
  * [14] J. Liang and R. D. C. Monteiro.  A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes.  SIAM Journal on Optimization, 31(4):2955–2986, 2021.
  * [15] J. Liang and R. D. C. Monteiro.  A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems.  Mathematics of Operations Research, 49(2):832–855, 2024.
  * [16] J. G. Melo, R. D. C. Monteiro, and H. Wang.  A proximal augmented lagrangian method for linearly constrained nonconvex composite optimization problems.  Journal of Optimization Theory and Applications, pages 1–33, 2023\.
  * [17] Y. Nesterov.  Gradient methods for minimizing composite functions.  Mathematical Programming, 140(1):125–161, 2013.
  * [18] Y. Nesterov.  Universal gradient methods for convex optimization problems.  Mathematical Programming, 152(1):381–404, 2015.
  * [19] B. O’donoghue and E. Candes.  Adaptive restart for accelerated gradient schemes.  Foundations of Computational Mathematics, 15:715–732, 2015.
  * [20] J. Renegar and B. Grimmer.  A simple nearly optimal restart scheme for speeding up first-order methods.  Foundations of Computational Mathematics, 22(1):211–256, 2022.
  * [21] V. Roulet and A. d’Aspremont.  Sharpness, restart and acceleration.  SIAM Journal on Optimization, 30:262–289, 2020.

##  Appendix A Technical results

###  A.1 Technical results for FSCO

###### Lemma A.1

Assume that sequences $\\{\gamma_{j}\\}$, $\\{\eta_{j}\\}$, and
$\\{\alpha_{j}\\}$ satisfy for every $j\geq 1$,
$\gamma_{j}\geq{\underline{\gamma}}$ and

$\gamma_{j}\eta_{j}\leq\alpha_{j-1}-(1+\sigma)\alpha_{j}+\gamma_{j}\delta$
(93)

for some $\sigma\geq 0$, $\delta\geq 0$ and ${\underline{\gamma}}>0$. Then,
the following statements hold:

  * a)

for every $k\geq 1$,

$\min_{1\leq j\leq
k}\eta_{j}\leq\frac{\alpha_{0}-(1+\sigma)^{k}\alpha_{k}}{\sum_{j=1}^{k}(1+\sigma)^{j-1}\gamma_{j}}+\delta;$
(94)

  * b)

if the sequence $\\{\eta_{j}\\}$ is nonnegative, then for every $k\geq 1$,

$\alpha_{k}\leq\frac{\alpha_{0}}{(1+\sigma)^{k}}+\frac{\sum_{j=1}^{k}(1+\sigma)^{j-1}\gamma_{j}\delta}{(1+\sigma)^{k}};$
(95)

  * c)

if the sequence $\\{\alpha_{j}\\}$ is nonnegative, then $\min_{1\leq j\leq
k}\eta_{j}\leq 2\delta$ for every $k\geq 1$ such that

$k\geq\min\left\\{\frac{1+\sigma}{\sigma}\log\left(\frac{\sigma\alpha_{0}}{{\underline{\gamma}}\delta}+1\right),\frac{\alpha_{0}}{{\underline{\gamma}}\delta}\right\\}$

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

Proof: a) Multiplying (93) by $(1+\sigma)^{j-1}$ and summing the resulting
inequality from $j=1$ to $k$, we have

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

Inequality (94) follows immediately from the above inequality.

b) This statement follows immediately from (96) and the fact that
$\eta_{j}\geq 0$.

c) It follows from (94), and the facts that $\alpha_{k}\geq 0$ and
$\gamma_{j}\geq{\underline{\gamma}}$ that

$\min_{1\leq j\leq
k}\eta_{j}\leq\frac{\alpha_{0}}{{\underline{\gamma}}\sum_{j=1}^{k}(1+\sigma)^{j-1}}+\delta.$
(97)

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

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

Plugging the above inequality into (97), we have for every $k\geq 1$,

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

which can be easily seen to imply (c).

###  A.2 Technical results for U-PB

###### Lemma A.2

The following statements hold for a cycle of U-PB with stepsize $\lambda$:

  * a)

for every iteration $j$ that is not the last iteration of the cycle, there
exists a function $\overline{f}_{j}(\cdot)$ such that

$\displaystyle\tau(\overline{f}_{j}+h)+(1-\tau)[\ell_{f}(\cdot;x_{j})+h]\leq
f_{j+1}+h\leq\phi,$ (99)
$\displaystyle\overline{f}_{j}+h\in\overline{\mbox{\rm
Conv}}_{\nu}\,(\mathbb{R}^{n}),\quad\overline{f}_{j}(x_{j})=f_{j}(x_{j}),\quad
x_{j}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\overline{f}_{j}(u)+h(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}\right\\},$
(100)

where $\tau$ is as in (79);

  * b)

for every iteration $j$ of the cycle and $u\in\mathbb{R}^{n}$, we have

$\overline{f}_{j}(u)+h(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}\geq
m_{j}+\frac{1}{2{\lambda}}\|u-x_{j}\|^{2}.$ (101)

Proof: a) Since $j$ is not the last iteration of a cycle, we have
$f_{j+1}=\mbox{BU}(\hat{x}_{k-1},x_{j},f_{j},\lambda)$. Using the properties
of the BU blackbox, it follows that there exists $\overline{f}_{j}$ such that
$\overline{f}_{j}+h\in\overline{\mbox{\rm Conv}}_{\nu}\,(\mathbb{R}^{n})$,
$\overline{f}_{j}(x_{j})=f_{j}(x_{j})$,

$\max\\{{\bar{f}}_{j}+h,\ell_{f}(\cdot;x_{j})+h\\}\leq f_{j+1}+h\leq\phi,$
(102)

and

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

We have therefore checked that (100) holds while (99) is an immediate
consequence of (102).

b) Since the objective function in the last identity of (100) is
${\lambda}^{-1}$-strongly convex, we have

$\overline{f}_{j}(u)+h(u)+\frac{1}{2{\lambda}}\|u-\hat{x}_{k-1}\|^{2}\geq\overline{f}_{j}(x_{j})+h(x_{j})+\frac{1}{2{\lambda}}\|x_{j}-\hat{x}_{k-1}\|^{2}+\frac{1}{2{\lambda}}\|u-x_{j}\|^{2}.$
(103)

The statement follows from (103), the first identity in (100), and the
definition of $m_{j}$ in (77).