# Complementary Composite Minimization, Small Gradients in General Norms, and
Applications to Regression Problems

Jelena Diakonikolas
University of Wisconsin-Madison
<EMAIL_ADDRESS>Supported by the NSF grant CCF-2007757 and by the Office of
the Vice Chancellor for Research and Graduate Education at the University of
Wisconsin–Madison with funding from the Wisconsin Alumni Research Foundation.
Cristóbal Guzmán
Pontificia Universidad Católica de Chile
<EMAIL_ADDRESS>Partially supported by INRIA through the INRIA Associate
Teams project, CORFO through the Clover 2030 Engineering Strategy -
14ENI-26862, and ANID – Millennium Science Initiative Program – NCN17_059.

###### Abstract

Composite minimization is a powerful framework in large-scale convex
optimization, based on decoupling of the objective function into terms with
structurally different properties and allowing for more flexible algorithmic
design. In this work, we introduce a new algorithmic framework for
complementary composite minimization, where the objective function decouples
into a (weakly) smooth and a uniformly convex term. This particular form of
decoupling is pervasive in statistics and machine learning, due to its link to
regularization.

The main contributions of our work are summarized as follows. First, we
introduce the problem of complementary composite minimization in general
normed spaces; second, we provide a unified accelerated algorithmic framework
to address broad classes of complementary composite minimization problems; and
third, we prove that the algorithms resulting from our framework are near-
optimal in most of the standard optimization settings. Additionally, we show
that our algorithmic framework can be used to address the problem of making
the gradients small in general normed spaces. As a concrete example, we obtain
a nearly-optimal method for the standard $\ell_{1}$ setup (small gradients in
the $\ell_{\infty}$ norm), essentially matching the bound of Nesterov (2012)
that was previously known only for the Euclidean setup. Finally, we show that
our composite methods are broadly applicable to a number of regression
problems, leading to complexity bounds that are either new or match the best
existing ones.

##  1 Introduction

_No function can simultaneously be both smooth and strongly convex with
respect to an $\ell_{p}$ norm
and have a dimension-independent condition number, unless $p=2$._

This is a basic fact from convex analysis111More generally, it is known that
the existence of a continuous uniformly convex function with growth bounded by
the squared norm implies that the space has an equivalent $2$-uniformly convex
norm (Borwein et al., 2009); furthermore, using duality (Zalinescu, 1983), we
conclude that the existence of a smooth and strongly convex function implies
that the space has equivalent $2$-uniformly convex and $2$-uniformly smooth
norms, a rare property for a normed space (the most notable examples of spaces
that are simultaneously $2$-uniformly convex and $2$-uniformly smooth are
Hilbert spaces; see e.g., Ball et al. (1994) for related definitions and more
details). and the primary reason why in the existing literature smooth and
strongly convex optimization is normally considered only for Euclidean (or,
slightly more generally, Hilbert) spaces. In fact, it is not only that moving
away from $p=2$ the condition number becomes dimension-dependent, but that the
dependence on the dimension is polynomial for all examples of functions we
know of, unless $p$ is trivially close to two. Thus, it is tempting to assert
that dimension-independent linear convergence (i.e., with logarithmic
dependence on the inverse accuracy $1/\epsilon$) is reserved for Euclidean
spaces, which has long been common wisdom among optimization researchers.

Contrary to this wisdom, we show that it is in fact possible to attain linear
convergence even in $\ell_{p}$ (or, more generally, in normed vector) spaces,
as long as the objective function can be decomposed into two functions with
complementary properties. In particular, we show that if the objective
function can be written in the following _complementary composite_ form

$\bar{f}(\mathbf{x})=f(\mathbf{x})+\psi(\mathbf{x}),$ (1)

where $f$ is convex and $L$-smooth w.r.t. a (not necessarily Euclidean) norm
$\|\cdot\|$ and $\psi$ is $m$-strongly convex w.r.t. the same norm and
“simple,” meaning that the optimization problems of the form

$\min_{\mathbf{x}}\left\langle\mathbf{z},\mathbf{x}\right\rangle+\psi(\mathbf{x})$
(2)

can be solved efficiently for any linear functional $\mathbf{z},$ then
$\bar{f}(\mathbf{x})$ can be minimized to accuracy $\epsilon>0$ in
$O\Big{(}\sqrt{\frac{L}{m}}\log(\frac{L\phi(\bar{\mathbf{x}}^{*})}{\epsilon})\Big{)}$
iterations, where
$\bar{\mathbf{x}}^{*}=\operatorname*{argmin}_{\mathbf{x}}\bar{f}(\mathbf{x})$.
As in other standard first-order iterative methods, each iteration requires
one call to the gradient oracle of $f$ and one call to a solver for the
problem from Eq. (2). To the best of our knowledge, such a result was
previously known only for Euclidean spaces (Nesterov, 2013).

This is the basic variant of our result. We also consider more general setups
in which $f$ is only weakly smooth (with Hölder-continuous gradients) and
$\psi$ is uniformly convex (see Section 1.2 for specific definitions and
useful properties). We refer to the resulting objective functions $\bar{f}$ as
_complementary composite objective functions_ (as functions $f$ and $\psi$
that constitute $\bar{f}$ have complementary properties) and to the resulting
optimization problems as _complementary composite optimization problems._ The
algorithmic framework that we consider for complementary composite
optimization in Section 2 is near-optimal (optimal up to logarithmic or poly-
logarithmic factors) in terms of iteration complexity in most of the standard
optimization settings, which we certify by providing near-matching oracle
complexity lower bounds in Section 4. We now summarize some further
implications of our results.

#### Small gradients in $\ell_{p}$ and $\mathscr{S}_{p}$ norms.

The original motivation for complementary composite optimization in our work
comes from making the gradients of smooth functions small in non-Euclidean
norms. This is a fundamental optimization question, whose study was initiated
by Nesterov (2012) and that is still far from being well-understood. Prior to
this work, (near)-optimal algorithms were known only for the Euclidean
($\ell_{2}$) and $\ell_{\infty}$ setups.222In the $\ell_{\infty}$ setup, a
non-Euclidean variant of gradient descent is optimal in terms of iteration
complexity.

For the Euclidean setup, there are two main results: due to Kim and Fessler
(2020) and due to Nesterov (2012). The algorithm of Kim and Fessler (2020) is
iteration-complexity-optimal; however, the methodology by which this algorithm
was obtained is crucially Euclidean, as it relies on numerical solutions to
semidefinite programs, whose formulation is made possible by assuming that the
norm of the space is inner-product-induced. An alternative approach, due to
Nesterov (2012), is to apply the fast gradient method to a regularized
function
$\bar{f}(\mathbf{x})=f(\mathbf{x})+\frac{\lambda}{2}\|\mathbf{x}-\mathbf{x}_{0}\|_{2}^{2}$
for a sufficiently small $\lambda>0,$ where $f$ is the smooth function whose
gradient we hope to minimize. Under the appropriate choice of $\lambda>0,$ the
resulting algorithm is near-optimal (optimal up to a logarithmic factor).

As discussed earlier, applying fast gradient method directly to a regularized
function as in Nesterov (2012) is out of question for $p\neq 2,$ as the
resulting regularized objective function cannot simultaneously be smooth and
strongly convex w.r.t. $\|\cdot\|_{p}$ without its condition number growing
with the problem dimension. This is where the framework of complementary
composite optimization proposed in our work comes into play. Our result also
generalizes to normed matrix spaces endowed with $\mathscr{S}_{p}$
(Schatten-$p$) norms.333$\mathscr{S}_{p}$ norm of a matrix $\mathbf{A}$ is
defined as the $\ell_{p}$ norm of $\mathbf{A}$’s singular values. As a
concrete example, our approach leads to near-optimal complexity results in the
$\ell_{1}$ and $\mathscr{S}_{1}$ setups, where the gradient is minimized in
the $\ell_{\infty}$, respectively, $\mathscr{S}_{\infty}$, norm.

It is important to note here why strongly convex regularizers are not
sufficient in general and what motivated us to consider the more general
uniformly convex functions $\psi$. While for $p\in(1,2]$ choosing
$\psi(\mathbf{x})=\frac{1}{2}\|\cdot\|_{p}^{2}$ (which is $(p-1)$-strongly
convex w.r.t. $\|\cdot\|_{p};$ see Nemirovskii and Yudin (1983); Juditsky and
Nemirovski (2008)) is sufficient, when $p>2$ the strong convexity parameter of
$\frac{1}{2}\|\cdot\|_{p}^{2}$ w.r.t. $\|\cdot\|_{p}$ is bounded above by
$1/d^{1-\frac{2}{p}}$. This is not only true for
$\frac{1}{2}\|\cdot\|_{p}^{2}$, but for any convex function bounded above by a
constant on a unit $\ell_{p}$-ball; see e.g., (d’Aspremont et al., 2018,
Example 5.1). Thus, in this case, we work with
$\psi(\mathbf{x})=\frac{1}{p}\|\cdot\|_{p}^{p}$, which is only uniformly
convex.

#### Lower complexity bounds.

We complement the development of algorithms for complementary composite
minimization and minimizing the norm of the gradient with lower bounds for the
oracle complexity of these problems. Our lower bounds leverage recent lower
bounds for weakly smooth convex optimization from Guzmán and Nemirovski
(2015); Diakonikolas and Guzmán (2020). These existing results suffice for
proving lower bounds for minimizing the norm of the gradient, and certify the
near-optimality of our approach for the smooth (i.e., with Lipschitz
continuous gradient) setting, when $1\leq p\leq 2$. On the other hand, proving
lower bounds for complementary convex optimization requires the design of an
appropriate oracle model; namely, one that takes into account that our
algorithm accesses the gradient oracle of $f$ and solves subroutines of type
(2) w.r.t. $\psi$. With this model in place, we combine constructions from
uniformly convex nonsmooth lower bounds (Srebro and Sridharan, 2012; Juditsky
and Nesterov, 2014) with local smoothing (Guzmán and Nemirovski, 2015;
Diakonikolas and Guzmán, 2020) to provide novel lower bounds for complementary
composite minimization. The resulting bounds show that our algorithmic
framework is nearly optimal (up to poly-logarithmic factors w.r.t. dimension,
target accuracy, regularity constants of the objective, and initial distance
to optimum) for all interesting regimes of parameters.

#### Applications to regression problems.

The importance of complementary composite optimization and making the
gradients small in $\ell_{p}$ and $\mathscr{S}_{p}$ norms is perhaps best
exhibited by considering some of the classical regression problems that are
frequently used in statistics and machine learning. It turns out that
considering these regression problems in the appropriate complementary
composite form not only leads to faster algorithms in general, but also
reveals some interesting properties of the solutions. For example,
applications of our framework to the complementary composite form of bridge
regression (a generalization of lasso and ridge regression; see Section 5)
leads to an interesting and well-characterized trade-off between the “goodness
of fit” of the model and the $\ell_{p}$ norm of the regressor.

Section 5 highlights a number of interesting regression problems that can be
addressed using our framework, including lasso, elastic net, (b)ridge
regression, Dantzig selector, $\ell_{p}$ regression (with standard and
correlated errors), and related spectral variants. It is important to note
that a single algorithmic framework suffices for addressing all of these
problems. Most of the results we obtain in this way are either conjectured or
known to be unimprovable.

###  1.1 Further Related Work

Nonsmooth convex optimization problems with the composite structure of the
objective function $\bar{f}(\mathbf{x})=f(\mathbf{x})+\psi(\mathbf{x})$, where
$f$ is smooth and convex, but $\psi$ is nonsmooth, convex, and “simple,” are
well-studied in the optimization literature (Beck and Teboulle, 2009;
Nesterov, 2013; Scheinberg et al., 2014; He et al., 2015; Gasnikov and
Nesterov, 2018, and references therein). The main benefit of exploiting the
composite structure lies in the ability to recover accelerated rates for
nonsmooth problems. One of the most celebrated results in this domain are the
FISTA algorithm of Beck and Teboulle (2009) and a method based on composite
gradient mapping due to Nesterov (2013), which demonstrated that accelerated
convergence (with rate $1/k^{2}$) is possible for this class of problems.

By comparison, the literature on complementary composite minimization is
scarce. For example, Nesterov (2013) proved that in a Euclidean space
complementary composite optimization attains a linear convergence rate. The
algorithm proposed there is different from ours, as it relies on the use of
composite gradient mapping, for which the proximal operator of $\psi$
(solution to problems of the form
$\min_{\mathbf{x}}\\{\psi(\mathbf{x})+\frac{1}{2}\|\mathbf{x}-\mathbf{z}\|_{2}^{2}\\}$
for all $\mathbf{z};$ compare to Eq. (2)) is assumed to be efficiently
computable. In addition to being primarily applicable to Euclidean spaces,
this assumption further restricts the class of functions that can be
efficiently optimized compared to our approach (see Section 2.2 for a further
discussion). Another composite algorithm where linear convergence has been
proved is the celebrated method by Chambolle and Pock (2011), where proximal
steps are taken w.r.t. both terms in the composite model ($f$ and $\psi$). In
the case where both $f$ and $\psi$ are strongly convex, a linear convergence
rate can be established. Notice that this assumption is quite different from
our setting, and that this method was only investigated for the Euclidean
setup.

Beyond the realm of Euclidean norms, linear convergence results have been
established for functions that are _relatively smooth and relatively strongly
convex_ (Bauschke et al., 2017, 2019; Lu et al., 2018). The class of
complementary composite functions does not fall into this category. Further,
while we show accelerated rates (with square-root dependence on the
appropriate notion of the condition number) for complementary composite
optimization, such results are likely not attainable for relatively smooth
relatively strongly convex optimization (Dragomir et al., 2019).444Lower
bounds from (Dragomir et al., 2019) show the impossibility of acceleration for
the relatively smooth setting. This is strong evidence of the impossibility of
acceleration in the relatively smooth and relatively strongly convex setting.

The problem of minimizing the norm of the gradient has become a central
question in optimization and its applications in machine learning, mainly
motivated by nonconvex settings, where the norm of the gradient is useful as a
stopping criterion. However, the norm of the gradient is also useful in
linearly constrained convex optimization problems, where the norm of the
gradient of a Fenchel dual is useful in controlling the feasibility violation
in the primal (Nesterov, 2012). Our approach for minimizing the norm of the
gradient is inspired by the regularization approach proposed by Nesterov
(2012). As discussed earlier, this regularization approach is not directly
applicable to non-Euclidean settings, and is where our complementary composite
framework becomes crucial.

Finally, our work is inspired by and uses fundamental results about the
geometry of high-dimensional normed spaces; in particular, the fact that for
$\ell_{p}$ and $\mathscr{S}_{p}$ spaces the optimal constants of uniform
convexity are known (Ball et al., 1994). These results imply that powers of
the respective norm are uniformly convex, which suffices for our
regularization. Moreover, those functions have explicitly computable convex
conjugates (problems as in Eq. (2) can be solved in closed form), which is
crucial for our algorithms to work.

###  1.2 Notation and Preliminaries

Throughout the paper, we use boldface letters to denote vectors and italic
letters to denote scalars.

We consider real finite-dimensional normed vector spaces $\mathbf{E},$ endowed
with a norm $\|\cdot\|,$ and denoted by $(\mathbf{E},\|\cdot\|).$ The space
dual to $(\mathbf{E},\|\cdot\|)$ is denoted by
$(\mathbf{E}^{*},\|\cdot\|_{*}),$ where $\|\cdot\|_{*}$ is the norm dual to
$\|\cdot\|,$ defined in the usual way by
$\|\mathbf{z}\|_{*}=\sup_{\mathbf{x}\in\mathbf{E}:\|\mathbf{x}\|\leq
1}\left\langle\mathbf{z},\mathbf{x}\right\rangle,$ where
$\left\langle\mathbf{z},\mathbf{x}\right\rangle$ denotes the evaluation of a
linear functional $\mathbf{z}$ on a point $\mathbf{x}\in\mathbf{E}.$ As a
concrete example, we may consider the $\ell_{p}$ space
$(\mathbb{R}^{d},\|\cdot\|_{p}),$ where
$\|\mathbf{x}\|_{p}=\big{(}\sum_{i=1}^{d}|x_{i}|^{p}\big{)}^{1/p},$ $1\leq
p\leq\infty.$ The space dual to $(\mathbb{R}^{d},\|\cdot\|_{p})$ is
isometrically isomorphic to the space $(\mathbb{R}^{d},\|\cdot\|_{p_{\ast}}),$
where $\frac{1}{p}+\frac{1}{p_{\ast}}=1.$ Throughout, given $1\leq
p\leq\infty$, we will call $p_{\ast}=\frac{p}{p-1}$ the conjugate exponent to
$p$ (notice that $1\leq p_{\ast}\leq\infty$, and
$\frac{1}{p}+\frac{1}{p_{\ast}}=1$). The (closed) $\|\cdot\|$-norm ball
centered at $\mathbf{x}$ with radius $R>0$ will be denoted at ${\cal
B}_{\|\cdot\|}(\mathbf{x},R)$.

We start by recalling some standard definitions from convex analysis.

######  Definition 1.1.

A function $f:\mathbf{E}\to\mathbb{R}$ is said to be $(L,\kappa)$-weakly
smooth w.r.t. a norm $\|\cdot\|$, where $L>0$ and $\kappa\in(1,2],$ if its
gradients are $(L,\kappa-1)$ Hölder continuous, i.e., if

$(\forall\mathbf{x},\mathbf{y}\in\mathbf{E}):\quad\|\nabla
f(\mathbf{x})-\nabla f(\mathbf{y})\|_{*}\leq
L\|\mathbf{x}-\mathbf{y}\|^{\kappa-1}.$

We denote the class of $(L,\kappa)$-weakly smooth functions w.r.t. $\|\cdot\|$
by ${\cal F}_{\|\cdot\|}(L,\kappa)$.

Note that when $\kappa=1,$ the function may not be differentiable. Since we
will only be working with functions that are proper, convex, and lower
semicontinuous, we will still have that $f$ is subdifferentiable on the
interior of its domain (Rockafellar, 1970, Theorem 23.4). The definition of
$(L,\kappa)$-weakly smooth functions then boils down to the bounded variation
of the subgradients.

######  Definition 1.2.

A function $\psi:\mathbf{E}\to\mathbb{R}$ is said to be $q$-uniformly convex
w.r.t. a norm $\|\cdot\|$ and with constant $\lambda$ (and we refer to such
functions as $(\lambda,q)$-uniformly convex), where $\lambda\geq 0$ and $q\geq
2$, if $\forall\alpha\in(0,1):$

$(\forall\mathbf{x},\mathbf{y}\in\mathbf{E}):\quad\psi((1-\alpha)\mathbf{x}+\alpha\mathbf{y})\leq(1-\alpha)\psi(\mathbf{x})+\alpha\psi(\mathbf{y})-\frac{\lambda}{q}\alpha(1-\alpha)\|\mathbf{y}-\mathbf{x}\|^{q}.$

We denote the class of $(\lambda,q)$-uniformly convex functions w.r.t.
$\|\cdot\|$ by ${\cal U}_{\|\cdot\|}(\lambda,q)$.

With the abuse of notation, we will often use $\nabla\psi(\mathbf{x})$ to
denote an arbitrary but fixed element of $\partial\psi(\mathbf{x}).$ We also
make a mild assumption that the subgradient oracle of $\psi$ is consistent,
i.e., that it returns the same element of $\partial\psi(\mathbf{x})$ whenever
queried at the same point $\mathbf{x}.$

Observe that when $\lambda=0,$ uniform convexity reduces to standard
convexity, while for $\lambda>0$ and $q=2$ we recover the definition of strong
convexity. We will only be considering functions that are lower
semicontinuous, convex, and proper. These properties suffice for a function to
be subdifferentiable on the interior of its domain. It is then not hard to
show that if $\psi$ is $(\lambda,q)$-uniformly convex w.r.t. a norm
$\|\cdot\|$ and $\mathbf{g}_{\mathbf{x}}\in\partial\psi(\mathbf{x})$ is its
subgradient at a point $\mathbf{x},$ we have

$(\forall\mathbf{y}\in\mathbf{E}):\quad\psi(\mathbf{y})\geq\psi(\mathbf{x})+\left\langle\mathbf{g}_{\mathbf{x}},\mathbf{y}-\mathbf{x}\right\rangle+\frac{\lambda}{q}\|\mathbf{y}-\mathbf{x}\|^{q}.$
(3)

######  Definition 1.3.

Let $\psi:\mathbf{E}\to\mathbb{R}\cup\\{+\infty\\}.$ The convex conjugate of
$\psi,$ denoted by $\psi^{*}$, is defined by

$(\forall\mathbf{z}\in\mathbf{E}^{*}):\quad\psi^{*}(\mathbf{z})=\sup_{\mathbf{x}\in\mathbf{E}}\\{\left\langle\mathbf{z},\mathbf{x}\right\rangle-\psi(\mathbf{x})\\}.$

Recall that the convex conjugate of any function is convex. Some simple
examples of conjugate pairs of functions that will be useful for our analysis
are: (i) univariate functions $\frac{1}{p}|\cdot|^{p}$ and
$\frac{1}{p_{\ast}}|\cdot|^{p_{\ast}},$ where $1<p<\infty$ (see, e.g., Borwein
and Zhu (2004, Exercise 4.4.2)) and (ii) functions $\frac{1}{2}\|\cdot\|^{2}$
and $\frac{1}{2}\|\cdot\|_{*}^{2},$ where norms $\|\cdot\|$ and
$\|\cdot\|_{*}$ are dual to each other (see, e.g., Boyd and Vandenberghe
(2004, Example 3.27)). The latter example can be easily adapted to prove that
the functions $\frac{1}{p}\|\cdot\|^{p}$ and
$\frac{1}{p_{\ast}}\|\cdot\|_{\ast}^{p_{\ast}}$ are conjugates of each other,
for $1<p<\infty$.

The following auxiliary facts will be useful for our analysis.

######  Fact 1.4.

Let $\psi:\mathbf{E}\to\mathbb{R}\cup\\{+\infty\\}$ be proper, convex, and
lower semicontinuous, and let $\psi^{*}$ be its convex conjugate. Then
$\psi^{*}$ is proper, convex, and lower semicontinuous (and thus
subdifferentiable on the interior of its domain) and
$\forall\mathbf{z}\in\mathrm{int\,dom}(\psi^{*})$:
$\mathbf{g}\in\partial\psi^{*}(\mathbf{z})$ if and only if
$\mathbf{g}\in\operatorname*{argsup}_{\mathbf{x}\in\mathbb{R}^{d}}\\{\left\langle\mathbf{z},\mathbf{x}\right\rangle-\psi(\mathbf{x})\\}.$

The following proposition will be repeatedly used in our analysis, and we
prove it here for completeness.

######  Proposition 1.5.

Let $(\mathbf{E},\|\cdot\|)$ be a normed space with
$\|\cdot\|^{2}:\mathbf{E}\rightarrow\mathbb{R}$ differentiable, and let
$1<q<\infty$. Then

$\Big{\|}\nabla\Big{(}\frac{1}{q}\|\mathbf{x}\|^{q}\Big{)}\Big{\|}_{*}=\|\mathbf{x}\|^{q-1}=\|\mathbf{x}\|^{q/q_{\ast}},$

where $q_{\ast}=\frac{q}{q-1}$ is the exponent conjugate to $q$.

###### Proof.

We notice that $\|\cdot\|^{2}$ is differentiable if and only if
$\|\cdot\|^{q}$ is differentiable (Zalinescu, 2002, Thm. 3.7.2). Since the
statement clearly holds for $\mathbf{x}=\textbf{0},$ in the following we
assume that $\mathbf{x}\neq\textbf{0}.$ Next, write $\frac{1}{q}\|\cdot\|^{q}$
as a composition of functions $\frac{1}{q}|\cdot|^{q/2}$ and $\|\cdot\|^{2}.$
Applying the chain rule of differentiation, we now have:

$\displaystyle\nabla\Big{(}\frac{1}{q}\|\mathbf{x}\|^{q}\Big{)}=\frac{1}{2}\Big{(}\|\mathbf{x}\|^{2}\Big{)}^{\frac{q}{2}-1}\nabla\big{(}\|\mathbf{x}\|^{2}\big{)}=\|\mathbf{x}\|^{q-2}\nabla\Big{(}\frac{1}{2}\|\mathbf{x}\|^{2}\Big{)}.$

It remains to argue that
$\Big{\|}\nabla\Big{(}\frac{1}{2}\|\mathbf{x}\|^{2}\Big{)}\Big{\|}_{*}=\|\mathbf{x}\|.$
This immediately follows by Fact 1.4, as $\frac{1}{2}\|\cdot\|^{2}$ and
$\frac{1}{2}\|\cdot\|_{*}^{2}$ are convex conjugates of each other. ∎

We also state here a lemma that allows approximating weakly smooth functions
by weakly smooth functions of a different order. A variant of this lemma (for
$p=2$) first appeared in (Devolder et al., 2014), while the more general
version stated here is from d’Aspremont et al. (2018).

######  Lemma 1.6.

Let $f:\mathbf{E}\to\mathbb{R}$ be a function that is $(L,\kappa)$-weakly
smooth w.r.t. some norm $\|\cdot\|$. Then for any $\delta>0$ and

$M\geq\Big{[}\frac{2(p-\kappa)}{p\kappa\delta}\Big{]}^{\frac{p-\kappa}{\kappa}}L^{\frac{p}{\kappa}}$
(4)

we have

$(\forall\mathbf{x},\mathbf{y}\in\mathbf{E}):\quad f(\mathbf{y})\leq
f(\mathbf{x})+\left\langle\nabla
f(\mathbf{x}),\mathbf{y}-\mathbf{x}\right\rangle+\frac{M}{p}\|\mathbf{y}-\mathbf{x}\|^{p}+\frac{\delta}{2}.$

Finally, the following lemma will be useful when bounding the gradient norm in
Section 3 (see also (Zalinescu, 2002, Section 3.5)).

######  Lemma 1.7.

Let $f:\mathbf{E}\to\mathbb{R}$ be a function that is convex and
$(L,\kappa)$-weakly smooth w.r.t. some norm $\|\cdot\|$. Then:

$(\forall\mathbf{x},\mathbf{y}\in\mathbf{E}):\frac{\kappa-1}{L^{\frac{1}{\kappa-1}}\kappa}\|\nabla
f(\mathbf{y})-\nabla f(\mathbf{x})\|^{\frac{\kappa}{\kappa-1}}\leq
f(\mathbf{y})-f(\mathbf{x})-\left\langle\nabla
f(\mathbf{x}),\mathbf{y}-\mathbf{x}\right\rangle.$

###### Proof.

Let $h(\mathbf{x})$ be any $(L,\kappa)$-weakly smooth function and let
$\mathbf{x}^{*}\in\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d}}h(\mathbf{x}).$
As $h$ is $(L,\kappa)$-weakly smooth, we have for all
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{d}:$

$h(\mathbf{y})\leq h(\mathbf{x})+\left\langle\nabla
h(\mathbf{x}),\mathbf{y}-\mathbf{x}\right\rangle+\frac{L}{\kappa}\|\mathbf{y}-\mathbf{x}\|^{\kappa}.$

Fixing $\mathbf{x}\in\mathbb{R}^{d}$ and minimizing both sides of the last
inequality w.r.t. $\mathbf{y}\in\mathbb{R}^{d}$, it follows that

$h(\mathbf{x}^{*})\leq
h(\mathbf{x})-\frac{L^{1-\kappa_{\ast}}}{\kappa_{\ast}}\|\nabla
h(\mathbf{x})\|_{*}^{\kappa_{\ast}},$ (5)

where we have used that the functions $\frac{1}{\kappa}\|\cdot\|^{\kappa}$ and
$\frac{1}{\kappa_{\ast}}\|\cdot\|_{*}^{\kappa_{\ast}}$ are convex conjugates
of each other.

To complete the proof, it remains to apply Eq. (5) to function
$h_{\mathbf{x}}(\mathbf{y})=f(\mathbf{y})-\left\langle\nabla
f(\mathbf{x}),\mathbf{y}-\mathbf{x}\right\rangle$ for any fixed
$\mathbf{x}\in\mathbb{R}^{d},$ and observe that $h_{\mathbf{x}}(\mathbf{y})$
is convex, $(L,\kappa)$-weakly smooth, and minimized at
$\mathbf{y}=\mathbf{x}.$ ∎

##  2 Complementary Composite Minimization

In this section, we consider minimizing complementary composite functions,
which are of the form

$\bar{f}(\mathbf{x})=f(\mathbf{x})+\psi(\mathbf{x}),$ (6)

where $f$ is $(L,\kappa)$-weakly smooth w.r.t. some norm $\|\cdot\|$,
$\kappa\in(1,2],$ and $\psi$ is $(\lambda,q)$-uniformly convex w.r.t. the same
norm, for some $q\geq 2$, $\lambda\geq 0$. We assume that the feasible set
$\mathcal{X}\subseteq\mathbf{E}$ is closed, convex, and nonempty.

###  2.1 Algorithmic Framework and Convergence Analysis

The algorithmic framework we consider is a generalization of AGD+ from Cohen
et al. (2018), stated as follows:

Generalized AGD+ $\displaystyle\mathbf{x}_{k}$
$\displaystyle=\frac{A_{k-1}}{A_{k}}\mathbf{y}_{k-1}+\frac{a_{k}}{A_{k}}\mathbf{v}_{k-1}$
(7) $\displaystyle\mathbf{v}_{k}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{u}\in\mathcal{X}}\Big{\\{}\sum_{i=0}^{k}a_{i}\left\langle\nabla
f(\mathbf{x}_{i}),\mathbf{u}-\mathbf{x}_{i}\right\rangle+A_{k}\psi(\mathbf{u})+m_{0}\phi(\mathbf{u})\Big{\\}}$
$\displaystyle\mathbf{y}_{k}$
$\displaystyle=\frac{A_{k-1}}{A_{k}}\mathbf{y}_{k-1}+\frac{a_{k}}{A_{k}}\mathbf{v}_{k},$
$\displaystyle\mathbf{y}_{0}$
$\displaystyle=\mathbf{v}_{0},\;\mathbf{x}_{0}\in\mathcal{X},$

where $m_{0}$ and the sequence of positive numbers $\\{a_{k}\\}_{k\geq 0}$ are
parameters of the algorithm specified in the convergence analysis below,
$A_{k}=\sum_{i=0}^{k}a_{i},$ and we take $\phi(\mathbf{u})$ to be a function
that satisfies
$\phi(\mathbf{u})\geq\frac{1}{q}\|\mathbf{u}-\mathbf{x}_{0}\|^{q}.$ For
example, if $\lambda>0,$ we can take
$\phi(\mathbf{u})=\frac{1}{\lambda}D_{\psi}(\mathbf{u},\mathbf{x}_{0}).$ When
$\lambda=0$, we take $\phi$ to be $(1,q)$-uniformly convex.

The convergence analysis relies on the approximate duality gap technique
(ADGT) of Diakonikolas and Orecchia (2019). The main idea is to construct an
upper estimate
$G_{k}\geq\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})$ of the true
optimality gap, where
$\bar{\mathbf{x}}^{*}=\operatorname*{argmin}_{\mathbf{x}\in\mathcal{X}}\bar{f}(\mathbf{u}),$
and then argue that $A_{k}G_{k}\leq A_{k-1}G_{k-1}+E_{k}$, which in turn
implies:

$\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})\leq\frac{A_{0}G_{0}}{A_{k}}+\frac{\sum_{i=1}^{k}E_{i}}{A_{k}}.$

I.e., as long as $A_{0}G_{0}$ is bounded and the cumulative error
$\sum_{i=1}^{k}E_{i}$ is either bounded or increasing slowly compared to
$A_{k}$, the optimality gap of the sequence $\mathbf{y}_{k}$ converges to the
optimum at rate $(1+\sum_{i=1}^{k}E_{i})/A_{k}.$ The goal is, of course, to
make $A_{k}$ as fast-growing as possible, but that turns out to be limited by
the requirement that $A_{k}G_{k}$ be non-increasing or slowly increasing
compared to $A_{k}$.

The gap $G_{k}$ is constructed as the difference $U_{k}-L_{k},$ where
$U_{k}\geq\bar{f}(\mathbf{y}_{k})$ is an upper bound on
$\bar{f}(\mathbf{y}_{k})$ and $L_{k}\leq\bar{f}(\bar{\mathbf{x}}^{*})$ is a
lower bound on $\bar{f}(\bar{\mathbf{x}}^{*}).$ In this particular case, we
make the following choices:

$U_{k}=f(\mathbf{y}_{k})+\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}\psi(\mathbf{v}_{i}).$

As $\mathbf{y}_{k}=\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}\mathbf{v}_{i},$ we have,
by Jensen’s inequality: $U_{k}\geq
f(\mathbf{y}_{k})+\psi(\mathbf{y}_{k})=\bar{f}(\mathbf{y}_{k}),$ i.e., $U_{k}$
is a valid upper bound on $\bar{f}(\mathbf{y}_{k}).$ For the lower bound, we
use the following inequalities:

$\displaystyle\bar{f}(\bar{\mathbf{x}}^{*})$
$\displaystyle\geq\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}f(\mathbf{x}_{i})+\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}\left\langle\nabla
f(\mathbf{x}_{i}),\bar{\mathbf{x}}^{*}-\mathbf{x}_{i}\right\rangle+\psi(\bar{\mathbf{x}}^{*})+\frac{m_{0}}{A_{k}}\phi(\bar{\mathbf{x}}^{*})-\frac{m_{0}}{A_{k}}\phi(\bar{\mathbf{x}}^{*})$
$\displaystyle\geq\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}f(\mathbf{x}_{i})+\frac{1}{A_{k}}\min_{\mathbf{u}\in\mathcal{X}}\Big{\\{}\sum_{i=0}^{k}a_{i}\left\langle\nabla
f(\mathbf{x}_{i}),\mathbf{u}-\mathbf{x}_{i}\right\rangle+A_{k}\psi(\mathbf{u})+m_{0}\phi(\mathbf{u})\Big{\\}}-\frac{m_{0}}{A_{k}}\phi(\bar{\mathbf{x}}^{*})$
$\displaystyle=:L_{k},$

where the first inequality uses
$f(\bar{\mathbf{x}}^{*})\geq\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}f(\mathbf{x}_{i})+\frac{1}{A_{k}}\sum_{i=0}^{k}a_{i}\left\langle\nabla
f(\mathbf{x}_{i}),\bar{\mathbf{x}}^{*}-\mathbf{x}_{i}\right\rangle,$ by
convexity of $f.$

We start by bounding the initial (scaled) gap $A_{0}G_{0}.$

######  Lemma 2.1 (Initial Gap).

For any $\delta_{0}>0$ and
$M_{0}=\Big{[}\frac{2(q-\kappa)}{q\kappa\delta_{0}}\Big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}},$
if $A_{0}M_{0}=m_{0},$ then

$A_{0}G_{0}\leq m_{0}\phi(\bar{\mathbf{x}}^{*})+\frac{A_{0}\delta_{0}}{2}.$

###### Proof.

By definition, and using that $a_{0}=A_{0}$,

$\displaystyle A_{0}G_{0}=$
$\displaystyle\;A_{0}\Big{(}f(\mathbf{y}_{0})+\psi(\mathbf{v}_{0})-f(\mathbf{x}_{0})-\left\langle\nabla
f(\mathbf{x}_{0}),\mathbf{v}_{0}-\mathbf{x}_{0}\right\rangle-\psi(\mathbf{v}_{0})-\frac{m_{0}}{A_{0}}\phi(\mathbf{v}_{0})\Big{)}+m_{0}\phi(\bar{\mathbf{x}}^{*})$
$\displaystyle=$
$\displaystyle\;A_{0}(f(\mathbf{y}_{0})-f(\mathbf{x}_{0})-\left\langle\nabla
f(\mathbf{x}_{0}),\mathbf{y}_{0}-\mathbf{x}_{0}\right\rangle)-m_{0}\phi(\mathbf{y}_{0})+m_{0}\phi(\bar{\mathbf{x}}^{*})$

where the second line is by $\mathbf{y}_{0}=\mathbf{v}_{0}$.

By assumption,
$\phi(\mathbf{u})\geq\frac{1}{q}\|\mathbf{u}-\mathbf{x}_{0}\|^{q},$ for all
$\mathbf{u},$ and, in particular,
$\phi(\mathbf{y}_{0})\geq\frac{1}{q}\|\mathbf{y}_{0}-\mathbf{x}_{0}\|_{q}^{q}.$
On the other hand, by $(L,\kappa)$-weak smoothness of $f$ and using Lemma 1.6,
we have that (below
$M_{0}=\big{[}\frac{2(q-\kappa)}{q\kappa\delta_{0}}\big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}}$):

$f(\mathbf{y}_{0})-f(\mathbf{x}_{0})-\left\langle\nabla
f(\mathbf{x}_{0}),\mathbf{y}_{0}-\mathbf{x}_{0}\right\rangle\leq\frac{M_{0}}{q}\|\mathbf{y}_{0}-\mathbf{x}_{0}\|_{q}^{q}+\frac{\delta_{0}}{2}.$

Therefore:

$A_{0}G_{0}\leq\big{(}A_{0}M_{0}-m_{0}\big{)}\frac{\|\mathbf{y}_{0}-\mathbf{x}_{0}\|^{q}}{q}+m_{0}\phi(\bar{\mathbf{x}}^{*})+\frac{A_{0}\delta_{0}}{2}=m_{0}\phi(\bar{\mathbf{x}}^{*})+\frac{A_{0}\delta_{0}}{2},$
(8)

as $m_{0}=A_{0}M_{0}$. ∎

The next step is to bound $A_{k}G_{k}-A_{k-1}G_{k-1},$ as in the following
lemma.

######  Lemma 2.2 (Gap Evolution).

Given arbitrary $\delta_{k}>0$ and
$M_{k}=\Big{[}\frac{2(q-\kappa)}{q\kappa\delta_{k}}\Big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}}$,
if $\frac{{a_{k}}^{q}}{{A_{k}}^{q-1}}\leq\frac{\max\\{\lambda
A_{k-1},m_{0}\\}}{M_{k}}$ then

$A_{k}G_{k}-A_{k-1}G_{k-1}\leq\frac{A_{k}\delta_{k}}{2}.$

###### Proof.

To bound $A_{k}G_{k}-A_{k-1}G_{k-1}$, we first bound
$A_{k}U_{k}-A_{k-1}U_{k-1}$ and $A_{k}L_{k}-A_{k-1}L_{k-1}.$ By definition of
$U_{k},$

$\displaystyle A_{k}U_{k}-A_{k-1}U_{k-1}$
$\displaystyle=A_{k}f(\mathbf{y}_{k})-A_{k-1}f(\mathbf{y}_{k-1})+a_{k}\psi(\mathbf{v}_{k})$
(9)
$\displaystyle=A_{k}(f(\mathbf{y}_{k})-f(\mathbf{x}_{k}))+A_{k-1}(f(\mathbf{x}_{k})-f(\mathbf{y}_{k-1}))+a_{k}f(\mathbf{x}_{k})+a_{k}\psi(\mathbf{v}_{k}).$

For the lower bound, define the function under the minimum in the definition
of the lower bound as
$h_{k}(\mathbf{u}):=\sum_{i=0}^{k}a_{i}\left\langle\nabla
f(\mathbf{x}_{i}),\mathbf{u}-\mathbf{x}_{i}\right\rangle+A_{k}\psi(\mathbf{u})+m_{0}\phi(\mathbf{u}),$
so that we have:

$A_{k}L_{k}-A_{k-1}L_{k-1}=a_{k}f(\mathbf{x}_{k})+h_{k}(\mathbf{v}_{k})-h_{k-1}(\mathbf{v}_{k-1}).$
(10)

Observe first that

$h_{k}(\mathbf{v}_{k})-h_{k-1}(\mathbf{v}_{k})=a_{k}\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{v}_{k}-\mathbf{x}_{k}\right\rangle+a_{k}\psi(\mathbf{v}_{k}).$
(11)

On the other hand, using the definition of Bregman divergence and the fact
that Bregman divergence is blind to constant and linear terms, we can bound
$h_{k-1}(\mathbf{v}_{k})-h_{k-1}(\mathbf{v}_{k-1})$ as

$\displaystyle h_{k-1}(\mathbf{v}_{k})-h_{k-1}(\mathbf{v}_{k-1})$
$\displaystyle=\left\langle\nabla
h_{k-1}(\mathbf{v}_{k-1}),\mathbf{v}_{k}-\mathbf{v}_{k-1}\right\rangle+D_{h_{k-1}}(\mathbf{v}_{k},\mathbf{v}_{k-1})$
$\displaystyle\geq
A_{k-1}D_{\psi}(\mathbf{v}_{k},\mathbf{v}_{k-1})+m_{0}D_{\phi}(\mathbf{v}_{k},\mathbf{v}_{k-1}),$

where the second line is by $\mathbf{v}_{k-1}$ being the minimizer of
$h_{k-1}$. Combining with Eqs. (10) and (11), we have:

$\displaystyle A_{k}L_{k}-A_{k-1}L_{k-1}\geq
a_{k}f(\mathbf{x}_{k})+a_{k}\psi(\mathbf{v}_{k})+a_{k}\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{v}_{k}-\mathbf{x}_{k}\right\rangle+A_{k-1}D_{\psi}(\mathbf{v}_{k},\mathbf{v}_{k-1})-m_{0}D_{\phi}(\mathbf{v}_{k},\mathbf{v}_{k-1}).$
(12)

Combining Eqs. (9) and (12), we can now bound $A_{k}G_{k}-A_{k-1}G_{k-1}$ as

$\displaystyle A_{k}G_{k}-A_{k-1}G_{k-1}\leq$
$\displaystyle\;A_{k}(f(\mathbf{y}_{k})-f(\mathbf{x}_{k}))+A_{k-1}(f(\mathbf{x}_{k})-f(\mathbf{y}_{k-1}))$
$\displaystyle-a_{k}\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{v}_{k}-\mathbf{x}_{k}\right\rangle-
A_{k-1}D_{\psi}(\mathbf{v}_{k},\mathbf{v}_{k-1})-m_{0}D_{\phi}(\mathbf{v}_{k},\mathbf{v}_{k-1})$
$\displaystyle\leq$
$\displaystyle\;A_{k}(f(\mathbf{y}_{k})-f(\mathbf{x}_{k})-\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{y}_{k}-\mathbf{x}_{k}\right\rangle)-A_{k-1}D_{\psi}(\mathbf{v}_{k},\mathbf{v}_{k-1})-m_{0}D_{\phi}(\mathbf{v}_{k},\mathbf{v}_{k-1}),$

where we have used
$f(\mathbf{x}_{k})-f(\mathbf{y}_{k-1})\leq\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{x}_{k}-\mathbf{y}_{k-1}\right\rangle$ (by convexity
of $f$) and the definition of $\mathbf{y}_{k}$ from Eq. (7). Similarly as for
the initial gap, we now use the weak smoothness of $f$ and Lemma 1.6 to write:

$\displaystyle f(\mathbf{y}_{k})-f(\mathbf{x}_{k})-\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{y}_{k}-\mathbf{x}_{k}\right\rangle$
$\displaystyle\leq\frac{M_{k}}{q}\|\mathbf{y}_{k}-\mathbf{x}_{k}\|^{q}+\frac{\delta_{k}}{2}$
$\displaystyle=\frac{M_{k}}{q}\frac{{a_{k}}^{q}}{{A_{k}}^{q}}\|\mathbf{v}_{k}-\mathbf{v}_{k-1}\|^{q}+\frac{\delta_{k}}{2},$

where
$M_{k}=\Big{[}\frac{2(q-\kappa)}{q\kappa\delta_{k}}\Big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}}$
and the equality is by
$\mathbf{y}_{k}-\mathbf{x}_{k}=\frac{a_{k}}{A_{k}}(\mathbf{v}_{k}-\mathbf{v}_{k-1})$,
which follows by the definition of algorithm steps from Eq. (7).

On the other hand, as $\psi$ is $(\lambda,q)$-uniformly convex, we have that
$D_{\psi}(\mathbf{v}_{k},\mathbf{v}_{k-1})\geq\frac{\lambda}{q}\|\mathbf{v}_{k}-\mathbf{v}_{k-1}\|^{q}$.
Further, if $\lambda=0,$ we have that
$D_{\phi}(\mathbf{v}_{k},\mathbf{v}_{k-1})\geq\frac{1}{q}\|\mathbf{v}_{k}-\mathbf{v}_{k-1}\|^{q}$.
Thus:

$\displaystyle A_{k}G_{k}-A_{k-1}G_{k-1}$
$\displaystyle\leq\Big{(}M_{k}\frac{{a_{k}}^{q}}{{A_{k}}^{q-1}}-\max\\{\lambda
A_{k-1},m_{0}\\}\Big{)}\frac{\|\mathbf{v}_{k}-\mathbf{v}_{k-1}\|^{q}}{q}+\frac{A_{k}\delta_{k}}{2}$
$\displaystyle\leq\frac{A_{k}\delta_{k}}{2},$

as $\frac{{a_{k}}^{q}}{{A_{k}}^{q-1}}\leq\frac{\max\\{\lambda
A_{k-1},m_{0}\\}}{M_{k}}.$ ∎

We are now ready to state and prove the main result from this section.

######  Theorem 2.3.

Let $\bar{f}(\mathbf{x})=f(\mathbf{x})+\psi(\mathbf{x}),$ where $f$ is convex
and $(L,\kappa)$-weakly smooth w.r.t. a norm $\|\cdot\|$, $\kappa\in(1,2],$
and $\psi$ is $q$-uniformly convex with constant $\lambda\geq 0$ w.r.t. the
same norm for some $q\geq 2$. Let $\bar{\mathbf{x}}^{*}$ be the minimizer of
$\bar{f}.$ Let $\mathbf{x}_{k},\mathbf{v}_{k},\mathbf{y}_{k}$ evolve according
to Eq. (7) for an arbitrary initial point $\mathbf{x}_{0}\in\mathcal{X},$
where $A_{0}M_{0}=m_{0}$,
${{a_{k}}^{q}}\leq\frac{\max\\{\lambda{A_{k-1}}^{q},m_{0}{A_{k}}^{q-1}\\}}{M_{k}}$
for $k\geq 1,$ and
$M_{k}=\Big{[}\frac{2(q-\kappa)}{q\kappa\delta_{k}}\Big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}}$,
for $\delta_{k}>0$ and $k\geq 0.$ Then, $\forall k\geq 1:$

$\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})\leq\frac{2A_{0}M_{0}\phi(\bar{\mathbf{x}}^{*})+\sum_{i=0}^{k}A_{i}\delta_{i}}{2A_{k}}.$

In particular, for any $\epsilon>0,$ setting
$\delta_{k}=\frac{a_{k}}{A_{k}}\epsilon$, for $k\geq 0,$ and $a_{0}=A_{0}=1,$
and
${{a_{k}}^{q}}=\frac{\max\\{\lambda{A_{k-1}}^{q},m_{0}{A_{k}}^{q-1}\\}}{M_{k}}$
for $k\geq 1,$ we have that
$\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})\leq\epsilon$ after at
most

$\displaystyle k=O\bigg{(}\min\bigg{\\{}$
$\displaystyle\Big{(}\frac{1}{\epsilon}\Big{)}^{\frac{q-\kappa}{q\kappa-q+\kappa}}\Big{(}\max\Big{\\{}\frac{L^{\frac{q}{\kappa}}}{\lambda},1\Big{\\}}\Big{)}^{\frac{\kappa}{q\kappa-q+\kappa}}\log\Big{(}\frac{L\phi(\bar{\mathbf{x}}^{*})}{\epsilon}\Big{)},$
$\displaystyle\Big{(}\frac{L}{\epsilon}\Big{)}^{\frac{q}{q\kappa-q+\kappa}}\big{(}\phi(\bar{\mathbf{x}}^{*})\big{)}^{\frac{\kappa}{q\kappa-q+\kappa}}\bigg{\\}}\bigg{)}$

iterations.

###### Proof.

The first part of the theorem follows immediately by combining Lemma 2.1 and
Lemma 2.2.

For the second part, we have

$\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})\leq\frac{A_{0}M_{0}\phi(\bar{\mathbf{x}}^{*})}{A_{k}}+\frac{\epsilon}{2},$

so all we need to show is that, under the step size choice from the theorem
statement, we have
$\frac{A_{0}M_{0}\phi(\bar{\mathbf{x}}^{*})}{A_{k}}\leq\frac{\epsilon}{2}.$

As $A_{0}=a_{0}=1,$ we have that $\delta_{0}=\epsilon$ and

$M_{0}=\Big{[}\frac{2(q-\kappa)}{q\kappa\epsilon}\Big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}}.$
(13)

It remains to bound the growth of $A_{k}.$ In this case, by theorem
assumption, we have
${{a_{k}}^{q}}=\frac{\max\\{\lambda{A_{k-1}}^{q},m_{0}{A_{k}}^{q-1}\\}}{M_{k}}$.
Thus, (i) $\frac{{a_{k}}^{q}}{{A_{k-1}}^{q}}\geq\frac{\lambda}{M_{k}}$ and
(ii) $\frac{{a_{k}}^{q}}{{A_{k}}^{q-1}}\geq\frac{m_{0}}{M_{k}}$, and the
growth of $A_{k}$ can be bounded below as the maximum of growths determined by
these two cases.

Consider $\frac{{a_{k}}^{q}}{{A_{k-1}}^{q}}\geq\frac{{\lambda}}{M_{k}}$ first.
As $\delta_{k}=\frac{a_{k}}{A_{k}}\epsilon$ and
$M_{k}=\Big{[}\frac{2(q-\kappa)}{q\kappa\delta_{k}}\Big{]}^{\frac{q-\kappa}{\kappa}}L^{\frac{q}{\kappa}}$,
the condition
$\frac{{a_{k}}^{q}}{{A_{k}}^{q-1}A_{k-1}}\geq\frac{\lambda}{M_{k}}$ can be
equivalently written as:

$\frac{{a_{k}}^{q-\frac{q}{\kappa}+1}}{{A_{k-1}}^{q-\frac{q}{\kappa}+1}}\geq\Big{[}\frac{2(q-\kappa)}{q\kappa\epsilon}\Big{]}^{-\frac{q-\kappa}{\kappa}}\frac{\lambda}{L^{\frac{q}{\kappa}}}.$

Hence,

$\frac{{a_{k}}}{A_{k-1}}\geq\Big{[}\frac{2(q-\kappa)}{q\kappa\epsilon}\Big{]}^{-\frac{q-\kappa}{q\kappa-q+\kappa}}\Big{(}\frac{\lambda}{L^{\frac{q}{\kappa}}}\Big{)}^{\frac{\kappa}{q\kappa-q+\kappa}}.$

As $a_{k}=A_{k}-A_{k-1},$ it follows that $\frac{A_{k}}{A_{k-1}}\geq
1+\Big{[}\frac{2(q-\kappa)}{q\kappa\epsilon}\Big{]}^{-\frac{q-\kappa}{q\kappa-q+\kappa}}\Big{(}\frac{\lambda}{L^{\frac{q}{\kappa}}}\Big{)}^{\frac{\kappa}{q\kappa-q+\kappa}},$
further leading to

$\displaystyle
A_{k}\geq\bigg{(}1+\Big{[}\frac{2(q-\kappa)}{q\kappa\epsilon}\Big{]}^{-\frac{q-\kappa}{q\kappa-q+\kappa}}\Big{(}\frac{\lambda}{L^{\frac{q}{\kappa}}}\Big{)}^{\frac{\kappa}{q\kappa-q+\kappa}}\bigg{)}^{k}.$

On the other hand, the condition
$\frac{{a_{k}}^{q}}{{A_{k}}^{q-1}}\geq\frac{m_{0}}{M_{k}}$ can be equivalently
written as:

$\frac{{a_{k}}^{\frac{q\kappa-q}{\kappa}+1}}{A_{k}^{\frac{q\kappa-q}{\kappa}}}\geq\frac{m_{0}}{L^{\frac{q}{\kappa}}}\Big{[}\frac{q\kappa\epsilon}{2(q-\kappa)}\Big{]}^{\frac{q-\kappa}{\kappa}}=1,$

where we have used the definition of $m_{0},$ which implies

$A_{k}=\Omega\Big{(}k^{\frac{q\kappa-q+\kappa}{\kappa}}\Big{)},$ (14)

and further leads to the claimed bound on the number of iterations. ∎

Let us point out some special cases of the bound from Theorem 2.3. When $f$ is
smooth ($\kappa=2$) and $\psi$ is $q$-uniformly convex, assuming
$L^{q/2}\geq\lambda,$ the bound simplifies to

$k=O\bigg{(}\min\bigg{\\{}\Big{(}\frac{1}{\epsilon}\Big{)}^{\frac{q-2}{q+2}}\Big{(}\frac{L^{\frac{q}{2}}}{\lambda}\Big{)}^{\frac{2}{q+2}}\log\Big{(}\frac{L\phi(\bar{\mathbf{x}}^{*})}{\epsilon}\Big{)},\;\Big{(}\frac{L}{\epsilon}\Big{)}^{\frac{q}{q+2}}\big{(}\phi(\bar{\mathbf{x}}^{*})\big{)}^{\frac{2}{q+2}}\bigg{\\}}\bigg{)}.$
(15)

In particular, if $\psi$ is strongly convex ($q=2$), we recover the same bound
as in the Euclidean case:

$k=O\bigg{(}\min\bigg{\\{}\sqrt{\frac{L}{\lambda}}\log\Big{(}\frac{L\phi(\bar{\mathbf{x}}^{*})}{\epsilon}\Big{)},\;\sqrt{\frac{L\phi(\bar{\mathbf{x}}^{*})}{\epsilon}}\bigg{\\}}\bigg{)}.$
(16)

Note that this result uses smoothness of $f$ and strong convexity of $\psi$
with respect to the same but arbitrary norm $\|\cdot\|$. Because we do not
require the same function to be simultaneously smooth and strongly convex
w.r.t. $\|\cdot\|$, the resulting “condition number” $\frac{L}{\lambda}$ can
be dimension-independent even for non-Euclidean norms (in particular, this
will be possible for any $\ell_{p}$ norm with $p\in(1,2]$).

Because $\bar{f}$ is $q$-uniformly convex, Theorem 2.3 also implies a bound on
$\|\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\|$ whenever $\lambda>0,$ as follows.

######  Corollary 2.4.

Under the same assumptions as in Theorem 2.3, and assuming, in addition, that
$\lambda>0,$ we have that
$\|\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\|\leq\bar{\epsilon}$ after at most

$k=O\bigg{(}\Big{(}\frac{q}{\lambda\bar{\epsilon}^{q}}\Big{)}^{\frac{q-\kappa}{q\kappa-q+\kappa}}\Big{(}\frac{L^{\frac{q}{\kappa}}}{\lambda}\Big{)}^{\frac{\kappa}{q\kappa-q+\kappa}}\log\Big{(}\frac{qL\phi(\bar{\mathbf{x}}^{*})}{\bar{\epsilon}^{q}\lambda}\Big{)}\bigg{)}$

iterations.

###### Proof.

By $q$-uniform convexity of $\bar{f}$ and $\textbf{0}\in\partial
f(\bar{\mathbf{x}}^{*})$ (as $\bar{\mathbf{x}}^{*}$ minimizes $\bar{f}$), we
have

$\|\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\|^{q}\leq\frac{q}{\lambda}(\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})).$

Thus, it suffices to apply the bound from Theorem 2.3 with the accuracy
parameter ${\epsilon}=\frac{\lambda\bar{\epsilon}^{q}}{q}.$ ∎

###  2.2 Computational Considerations

At a first glance, the result from Theorem 2.3 may seem of limited
applicability, as there are potentially four different parameters
($L,\kappa,\lambda,q$) that one would need to tune. However, we now argue that
this is not a constraining factor. First, for most of the applications in
which one would be interested in using this framework, function $\psi$ is a
regularizing function with known uniform convexity parameters $\lambda$ and
$q$ (see Section 5 for several interesting examples). Second, the knowledge of
parameters $L$ and $\kappa$ is not necessary for our results; we presented the
analysis assuming the knowledge of these parameters to not over-complicate the
exposition.

In particular, the only place in the analysis where the $(L,\kappa)$
smoothness of $f$ is used is in the inequality

$f(\mathbf{y}_{k})\leq f(\mathbf{x}_{k})+\left\langle\nabla
f(\mathbf{x}_{k}),\mathbf{y}_{k}-\mathbf{x}_{k}\right\rangle+\frac{M_{k}}{q}\|\mathbf{y}_{k}-\mathbf{x}_{k}\|^{q}+\frac{\delta_{k}}{2}.$
(17)

But instead of explicitly computing the value of $M_{k}$ based on $L,\kappa,$
one could maintain an estimate of $M_{k}$, double it whenever the inequality
from Eq. (17) is not satisfied, and recompute all iteration-$k$ variables.
This is a standard trick employed in optimization, due to Nesterov (2015).
Observe that, due to $(L,\kappa)$-weak smoothness of $f$ and Lemma 1.6, there
exists a sufficiently large $M_{k}$ for any value of $\delta_{k}$. In
particular, under the choice $\delta_{k}=\frac{a_{k}}{A_{k}}\epsilon$ from
Theorem 3.1, the total number of times that $M_{k}$ can get doubled is
logarithmic in all of the problem parameters, which means that it can be
absorbed in the overall convergence bound from Theorem 2.3.

Finally, the described algorithm (Generalized AGD+ from Eq. (7)) can be
efficiently implemented only if the minimization problems defining
$\mathbf{v}_{k}$ can be solved efficiently (preferably in closed form, or with
$\tilde{O}(d)$ arithmetic operations). This is indeed the case for most
problems of interest. In particular, when $\psi$ is uniformly convex, we will
typically take $\phi(\mathbf{u})$ to be the Bregman divergence
$D_{\psi}(\mathbf{u},\mathbf{x}_{0}).$ Then, the computation of
$\mathbf{v}_{k}$ boils down to solving problems of the form (2), i.e.,
$\min_{\mathbf{u}\in\mathcal{X}}\\{\left\langle\mathbf{z},\mathbf{x}\right\rangle+\psi(\mathbf{x})\\},$
for a given $\mathbf{z}.$ Such problems are efficiently solvable whenever the
convex conjugate of $\psi+I_{\mathcal{X}}$, where $I_{\mathcal{X}}$ is the
indicator function of the closed convex set $\mathcal{X},$ is efficiently
computable, in which case the minimizer is
$\nabla(\psi+I_{\mathcal{X}})^{*}(\mathbf{z})$. In particular, for
$\mathcal{X}=\mathbf{E}$ and $\psi(\mathbf{x})=\frac{1}{q}\|\cdot\|^{q}$,
$q>1,$ (a common choice for our applications of interest; see Section 5), the
minimizer is computable in closed form as
$\nabla\big{(}\frac{1}{q_{\ast}}\|\mathbf{z}\|_{*}^{q_{\ast}}\big{)},$ where
$q_{\ast}=\frac{q}{q-1}$ is the exponent dual to $q.$ This should be compared
to the computation of proximal maps needed in Nesterov (2013), where the
minimizer would be the gradient of the infimal convolution of $\psi$ and the
Euclidean norm squared, for which there are much fewer efficiently computable
examples. Note that such an assumption would be sufficient for our algorithm
to work in the Euclidean case (by taking
$\phi(\mathbf{u})=\frac{1}{2}\|\mathbf{u}-\mathbf{x}_{0}\|_{2}^{2}$); however,
it is not necessary.

##  3 Minimizing the Gradient Norm in $\ell_{p}$ and $\mathrm{Sch}_{p}$ Spaces

We now show how to use the result from Theorem 2.3 to obtain near-optimal
convergence bounds for minimizing the norm of the gradient. In particular,
assuming that $f$ is $(L,\kappa)$-weakly smooth w.r.t. $\|\cdot\|_{p},$ to
obtain the desired results, we apply Theorem 2.3 to function
$\bar{f}(\cdot)=f(\cdot)+\lambda\psi_{p}(\cdot),$ where

$\psi_{p}(\mathbf{x})=\begin{cases}\frac{1}{2(p-1)}\|\mathbf{x}-\mathbf{x}_{0}\|_{p}^{2},&\text{
if }p\in(1,2],\\\ \frac{1}{p}\|\mathbf{x}-\mathbf{x}_{0}\|_{p}^{p},&\text{ if
}p\in(2,+\infty).\end{cases}$ (18)

Function $\psi_{p}$ is then $(1,\max\\{2,p\\})$-uniformly convex. The proof of
strong convexity of $\psi_{p}$ when $1<p\leq 2$ can be found, e.g., in Beck
(2017, Example 5.28). For $2<p<+\infty$, $\psi_{p}$ is a separable function,
hence its $p$-uniform convexity can be proved from the duality between uniform
convexity and uniform smoothness (Zalinescu, 1983) and direct computation.
These $\ell_{p}$ results also have spectral analogues, given by the Schatten
spaces $\mathscr{S}_{p}=(\mathbb{R}^{d\times d},\|\cdot\|_{\mathscr{S},p})$.
Here, the functions below can be proved to be $(1,\max\\{2,p\\})$-uniformly
convex, which is a consequence of sharp estimates of uniform convexity for
Schatten spaces (Ball et al., 1994; Juditsky and Nemirovski, 2008)

$\Psi_{\mathscr{S},p}(\mathbf{x})=\begin{cases}\frac{1}{2(p-1)}\|\mathbf{x}-\mathbf{x}_{0}\|_{\mathscr{S},p}^{2},&\text{
if }p\in(1,2],\\\
\frac{1}{p}\|\mathbf{x}-\mathbf{x}_{0}\|_{\mathscr{S},p}^{p},&\text{ if
}p\in(2,+\infty).\end{cases}$ (19)

Finally, both for $\ell_{1}$ and $\mathscr{S}_{1}$ spaces, our algorithms can
work on the equivalent norm with power $p=\ln d/(\ln d-1).$ The cost of this
change of norm is at most logarithmic in $d$ for the diameter and strong
convexity constants. Similarly, our results also extend to the case
$p=\infty$, by similar considerations (here, using exponent $p=\ln d$).

To obtain the results for the norm of the gradient in $\ell_{p}$ spaces, we
can apply Theorem 2.3 with $\phi(\mathbf{x})=\psi_{p}(\mathbf{x}),$ where
$\psi_{p}$ is specified in Eq. (18). The result is summarized in the following
theorem. The same result can be obtained for $\mathscr{S}_{p}$ spaces, by
following the same argument as in Theorem 3.1 below, which we omit for
brevity.

######  Theorem 3.1.

Let $f$ be a convex, $(L,\kappa)$\- weakly smooth function w.r.t. a norm
$\|\cdot\|_{p}$, where $p\in(1,\infty).$ Then, for any $\epsilon>0,$
Generalized AGD+ from Eq. (7), initialized at some point
$\mathbf{x}_{0}\in\mathbb{R}^{d}$ and applied to $\bar{f}=f+\lambda\psi_{p},$
where $\psi_{p}$ is specified in Eq. (18),

$\lambda=\begin{cases}\frac{\epsilon(p-1)}{2\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}},&\text{
if }p\in(1,2],\\\
\frac{\epsilon}{2\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}^{p-1}},&\text{ if
}p\in(2,\infty),\end{cases}$

and with the choice $\phi=\psi_{p},$ constructs a point $\mathbf{y}_{k}$ with
$\|\nabla f(\mathbf{y}_{k})\|_{p_{\ast}}\leq\epsilon$ in at most

$k=\begin{cases}O\bigg{(}\Big{(}\frac{2L}{\epsilon}\Big{)}^{\frac{\kappa}{(\kappa-1)(3\kappa-2)}}\Big{(}\frac{\kappa^{2\kappa}}{(\kappa-1)^{2\kappa}}\cdot\frac{\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}^{2}}{(p-1)^{{\kappa}}}\Big{)}^{\frac{1}{3\kappa-2}}\log\Big{(}\frac{L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}}{(p-1)\epsilon}\Big{)}\bigg{)},&\text{
if }p\in(1,2],\\\
O\bigg{(}\Big{(}\frac{2L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}}{\epsilon}\Big{)}^{\frac{\kappa(p-1)}{p\kappa-p+\kappa}}\Big{(}\frac{\kappa}{\kappa-1}\Big{)}^{\frac{p}{p\kappa-p+\kappa}}\log\Big{(}\frac{L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}^{p}}{\epsilon}\Big{)}\bigg{)},&\text{
if }p\in(2,\infty),\end{cases}$

iterations. In particular, when $\kappa=2$ (i.e., when $f$ is $L$-smooth):

$k=\begin{cases}\widetilde{O}\bigg{(}\sqrt{\frac{L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}}{\epsilon}}\bigg{)},&\text{
if }p\in(1,2],\\\
\widetilde{O}\bigg{(}\Big{(}\frac{L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}}{\epsilon}\Big{)}^{\frac{2(p-1)}{p+2}}\bigg{)},&\text{
if }p\in(2,\infty),\end{cases}$

where $\widetilde{O}$ hides logarithmic factors in $L$,
$\|\mathbf{x}-\mathbf{x}_{0}\|_{p}$, $\frac{1}{p-1}$ and $1/\epsilon$.

###### Proof.

Let us first relate $\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{p}$ to
$\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p},$ where
$\bar{\mathbf{x}}^{*}=\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d}}\bar{f}(\mathbf{x}),$
$\mathbf{x}^{*}\in\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d}}{f}(\mathbf{x}).$
By the definition of $\bar{f}$:

$\displaystyle 0$
$\displaystyle\leq\bar{f}(\mathbf{x}^{*})-\bar{f}(\bar{\mathbf{x}}^{*})$
$\displaystyle=f(\mathbf{x}^{*})-f(\bar{\mathbf{x}}^{*})+\lambda\psi_{p}(\mathbf{x}^{*})-\lambda\psi_{p}(\bar{\mathbf{x}}^{*})$
$\displaystyle\leq\lambda\psi_{p}(\mathbf{x}^{*})-\lambda\psi_{p}(\bar{\mathbf{x}}^{*}).$

It follows that

$\psi_{p}(\bar{\mathbf{x}}^{*})\leq\psi_{p}(\mathbf{x}^{*}).$

Thus, using the definition of $\psi_{p},$

$\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{p}\leq\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}.$
(20)

By triangle inequality and
$\bar{\mathbf{x}}^{*}=\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d}}\bar{f}(\mathbf{x})$
(which implies $\nabla\bar{f}(\mathbf{x}^{*})=\textbf{0}$),

$\displaystyle\|\nabla f(\mathbf{y}_{k})\|_{p_{\ast}}$
$\displaystyle\leq\|\nabla f(\mathbf{y}_{k})-\nabla
f(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}+\|\nabla
f(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}$ $\displaystyle=\|\nabla
f(\mathbf{y}_{k})-\nabla
f(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}+\|\nabla\bar{f}(\bar{\mathbf{x}}^{*})-\lambda\nabla\psi_{p}(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}$
$\displaystyle=\|\nabla f(\mathbf{y}_{k})-\nabla
f(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}+\lambda\|\nabla\psi_{p}(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}.$
(21)

As $f$ is convex and $(L,\kappa)$ weakly smooth, using Lemma 1.7, we also
have:

$\displaystyle\frac{\kappa-1}{L^{\frac{1}{\kappa-1}}\kappa}\|\nabla
f(\mathbf{y}_{k})-\nabla
f(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}^{\frac{\kappa}{\kappa-1}}$
$\displaystyle\leq
f(\mathbf{y}_{k})-f(\bar{\mathbf{x}}^{*})-\left\langle\nabla
f(\bar{\mathbf{x}}^{*}),\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\right\rangle$
$\displaystyle=\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})-\lambda\psi_{p}(\mathbf{y}_{k})+\lambda\psi_{p}(\bar{\mathbf{x}}^{*})-\left\langle\nabla\bar{f}(\bar{\mathbf{x}}^{*})-\lambda\nabla\psi_{p}(\bar{\mathbf{x}}^{*}),\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\right\rangle$
$\displaystyle=\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})-\lambda\big{(}\psi_{p}(\mathbf{y}_{k})-\psi_{p}(\bar{\mathbf{x}}^{*})-\left\langle\nabla\psi_{p}(\bar{\mathbf{x}}^{*}),\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\right\rangle\big{)}$
$\displaystyle\leq\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*}),$ (22)

where the second line uses $\bar{f}=f+\psi_{p}$, the third line follows by
$\nabla\bar{f}(\bar{\mathbf{x}}^{*})=0$ (as
$\bar{\mathbf{x}}^{*}=\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d}}\bar{f}(\mathbf{x})$),
and the last inequality is by convexity of $\psi_{p}.$

From Eqs. (21) and (22), to obtain $\|\nabla
f(\mathbf{y}_{k})\|_{p_{\ast}}\leq\epsilon,$ it suffices that
$\lambda\|\nabla\psi_{p}(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}\leq\frac{\epsilon}{2}$
and
$\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})\leq\big{(}\frac{\epsilon}{2}\big{)}^{\frac{\kappa}{\kappa-1}}\frac{\kappa-1}{L^{\frac{1}{\kappa-1}}\kappa}.$

The first condition determines the value of $\lambda.$ Using Proposition 1.5,
$\lambda\|\nabla\psi_{p}(\bar{\mathbf{x}}^{*})\|_{p_{\ast}}\leq\frac{\epsilon}{2}$
is equivalent to

$\begin{cases}\frac{\lambda}{p-1}\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{p}\leq\frac{\epsilon}{2},&\text{
if }p\in(1,2]\\\
{\lambda}\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{p}^{p-1}\leq\frac{\epsilon}{2},&\text{
if }p\in(2,\infty).\end{cases}$

Using Eq. (20), it suffices that:

$\lambda=\begin{cases}\frac{\epsilon(p-1)}{2\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}},&\text{
if }p\in(1,2],\\\
\frac{\epsilon}{2\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}^{p-1}},&\text{ if
}p\in(2,\infty).\end{cases}$ (23)

Using the choice of $\lambda$ from Eq. (23), it remains to apply Theorem 2.3
to bound the number of iterations until
$\bar{f}(\mathbf{y}_{k})-\bar{f}(\bar{\mathbf{x}}^{*})\leq\big{(}\frac{\epsilon}{2}\big{)}^{\frac{\kappa}{\kappa-1}}\frac{\kappa-1}{L^{\frac{1}{\kappa-1}}\kappa}.$
Applying Theorem 2.3, we have:

$k=O\bigg{(}\Big{(}\frac{2^{\frac{\kappa}{\kappa-1}}L^{\frac{1}{\kappa-1}}\kappa}{\epsilon^{\frac{\kappa}{\kappa-1}}(\kappa-1)}\Big{)}^{\frac{q-\kappa}{q\kappa-q+\kappa}}\Big{(}\frac{L^{\frac{q}{\kappa}}}{\lambda}\Big{)}^{\frac{\kappa}{q\kappa-q+\kappa}}\log\Big{(}\frac{2^{\frac{\kappa}{\kappa-1}}L^{2}\kappa\psi_{p}(\bar{\mathbf{x}}^{*})}{\epsilon^{\frac{\kappa}{\kappa-1}}(\kappa-1)}\Big{)}\bigg{)}.$

It remains to plug in the choice of $\lambda$ from Eq. (23),
$q=\max\\{p,2\\},$ and simplify. ∎

######  Remark 3.2.

Observe that, as the gradient norm minimization relies on the application of
Theorem 2.3, the knowledge of parameters $L$ and $\kappa$ is not needed, as
discussed in Section 2.2. The only parameter that needs to be determined is
$\lambda,$ which cannot be known in advance, as it would require knowing the
initial distance to optimum $\|\mathbf{x}^{*}-\mathbf{x}_{0}\|.$ However,
tuning $\lambda$ can be done at the cost of an additional
$\log(\frac{\lambda}{\lambda_{0}})$ multiplicative factor in the convergence
bound. In particular, one could start with a large estimate of $\lambda$ (say,
$\lambda=\lambda_{0}=1$), run the algorithm, and halt and restart with
$\lambda\leftarrow\lambda/2$ each time
$\|\nabla\bar{f}(\mathbf{y}_{k})\|_{*}\leq 2\epsilon$ but $\|\nabla
f(\mathbf{y}_{k})\|_{*}>\epsilon.$ This condition is sufficient because, when
$\lambda$ is of the correct order,
$\lambda\|\nabla\psi(\mathbf{y}_{k})\|_{*}=O(\lambda\|\nabla\psi(\bar{\mathbf{x}}^{*})\|_{*})=O(\epsilon)$,
$\|\nabla f(\mathbf{y}_{k})\|_{*}\leq\epsilon,$ and
$\|\nabla\bar{f}(\mathbf{y}_{k})\|_{*}\leq\|\nabla
f(\mathbf{y}_{k})\|_{*}+\lambda\|\nabla\psi(\mathbf{y}_{k})\|_{*}\leq
O(\epsilon).$

##  4 Lower Bounds

In this section, we address the question of the optimality of our algorithmic
framework, in a formal oracle model of computation. We first study the
question of minimizing the norm of the gradient, which follows from a simple
reduction to the complexity of minimizing the objective function and for which
nearly tight lower bounds are known. In this case, the lower bounds show that
our resulting algorithms are nearly optimal when $q=\kappa=2$. In cases where
either we have weaker smoothness ($\kappa<2$) or larger uniform convexity
exponent ($q>2$), we observe the presence of polynomial gaps in the complexity
w.r.t. $1/\epsilon$.

One natural question regarding the aforementioned gaps is whether this is due
to the suboptimality of the complementary composite minimization algorithm
used, or the reduction from the solution obtained by this method to obtain a
small gradient norm. In this respect, we discard the first possibility,
showing sharp lower bounds for complementary composite optimization in a new
composite oracle model. Our lower bounds show that the complementary composite
minimization algorithms are optimal up to factors which depend at most
logarithmically on the initial distance to the optimal solution, the target
accuracy, and dimension.

Before proceeding to the specific results, we provide a short summary of the
classical oracle complexity in convex optimization and some techniques that
will be necessary for our results. For more detailed information on the
subject, we refer the reader to the thorough monograph of Nemirovskii and
Yudin (1983). In the oracle model of convex optimization, we consider a class
of objectives ${\cal F}$, comprised of functions $f:\mathbf{E}\to\mathbb{R}$;
an oracle ${\cal O}:{\cal F}\times\mathbf{E}\to\mathbf{F}$ (where $\mathbf{F}$
is a vector space); and a target accuracy, $\epsilon>0$. An algorithm ${\cal
A}$ can be described by a sequence of functions $({\cal
A}_{k})_{k\in\mathbb{N}}$, where ${\cal
A}_{k+1}:(\mathbf{E}\times\mathbf{F})^{k+1}\to\mathbf{E}$, so that the
algorithm sequentially interacts with the oracle querying points

$\mathbf{x}^{k+1}={\cal A}_{k+1}(\mathbf{x}^{0},{\cal
O}(f,\mathbf{x}^{0}),\ldots,\mathbf{x}^{k},{\cal O}(f,\mathbf{x}^{k})).$

The running time of algorithm ${\cal A}$ is given by the minimum number of
queries to achieve some measure of accuracy (up to a given accuracy
$\epsilon>0$), and will be denoted by $T({\cal A},f,\epsilon)$. The most
classical example in optimization is achieving additive optimality gap bounded
by $\epsilon$:

$T({\cal A},f,\epsilon)=\inf\\{k\geq 0:f(\mathbf{x}^{k})\leq
f^{\ast}+\epsilon\\},$

but other relevant goal for our work is achieving a (dual) norm of the
gradient upper bounded by $\epsilon$

$T({\cal A},f,\epsilon)=\inf\\{k\geq 0:\|\nabla
f(\mathbf{x}^{k})\|_{\ast}\leq\epsilon\\}.$

Given a measure of efficiency $T$, the worst-case oracle complexity for a
problem class ${\cal F}$ endowed with oracle ${\cal O}$, is given by

$\mbox{Compl}({\cal F},{\cal O},\epsilon)=\inf_{\cal A}\sup_{f\in{\cal
F}}T(\mathcal{A},f,\epsilon).$

###  4.1 Lower Complexity Bounds for Minimizing the Norm of the Gradient

We provide lower complexity bounds for minimizing the norm of the gradient.
For the sake of simplicity, we can think of these lower bounds for the oracle
${\cal O}(f,x)=\nabla f(\mathbf{x})$, but we point out they work more
generally for arbitrary local oracles (more on this in the next section).

In short, we reduce the problem of making the gradient small to that of
approximately minimizing the objective.

######  Proposition 4.1.

Let $f:\mathbf{E}\to\mathbb{R}$ be a convex and differentiable function, with
a global minimizer $\mathbf{x}^{\ast}$. Then, if $\|\nabla
f(\mathbf{x})\|_{\ast}\leq\epsilon$ and $\|\mathbf{x}-\mathbf{x}^{\ast}\|\leq
R$, then $f(\mathbf{x})-f(\mathbf{x}^{\ast})\leq\epsilon R$.

###### Proof.

By convexity of $f$,

$f(\mathbf{x})-f(\mathbf{x}^{\ast})\leq\langle\nabla
f(\mathbf{x}),\mathbf{x}-\mathbf{x}^{\ast}\rangle\leq\|\nabla
f(\mathbf{x})\|_{\ast}\|\mathbf{x}-\mathbf{x}^{\ast}\|\leq\epsilon R,$

where the second inequality is by duality of norms $\|\cdot\|$ and
$\|\cdot\|_{*}.$ ∎

For the classical problem of minimizing the objective function value, lower
complexity bounds for $\ell_{p}$-setups have been previously studied in both
constrained (Guzmán and Nemirovski, 2015) and unconstrained (Diakonikolas and
Guzmán, 2020) settings. Here we summarize those results.555More precisely, to
obtain this result one can use the $p$-norm smoothing construction from Guzmán
and Nemirovski (2015, Section 2.3), in combination with the norm term used in
Diakonikolas and Guzmán (2020, Eq. (3)). This would lead to a smooth objective
over an unconstrained domain that provides a hard function class.

######  Theorem 4.2 ((Guzmán and Nemirovski, 2015; Diakonikolas and Guzmán,
2020)).

Let $1\leq p\leq\infty$, and consider the problem class of unconstrained
minimization with objectives in the class ${\cal
F}_{\mathbb{R}^{d},\|\cdot\|_{p}}({\kappa},L)$, whose minima are attained in
${\cal B}_{\|\cdot\|_{p}}(0,R)$. Then, the complexity of achieving additive
optimality gap $\epsilon$, for any local oracle, is bounded below by:

  * •

$\Omega\Big{(}\Big{(}\frac{LR^{\kappa}}{\epsilon[\ln
d]^{\kappa-1}}\Big{)}^{\frac{2}{3\kappa-2}}\Big{)}$ if $1\leq p<2$;

  * •

$\Omega\Big{(}\Big{(}\frac{LR^{\kappa}}{\epsilon\min\\{p,\ln
d\\}^{\kappa-1}}\Big{)}^{\frac{p}{\kappa p+\kappa-p}}\Big{)}$, if $2\leq
p<\infty$; and,

  * •

$\Omega\Big{(}\Big{(}\frac{LR^{\kappa}}{\epsilon[\ln
d]^{\kappa-1}}\Big{)}^{\frac{1}{\kappa-1}}\Big{)}$, if $p=\infty$.

The dimension $d$ for the lower bound to hold must be at least as large as the
lower bound itself.

By combining the reduction from Proposition 4.1 with the lower bounds for
function minimization from Theorem 4.2, we can now immediately obtain lower
bounds for minimizing the $\ell_{p}$ norm of the gradient, as follows.

######  Corollary 4.3.

Let $1\leq p\leq\infty$, and consider the problem class with objectives in
${\cal F}_{\mathbb{R}^{d},\|\cdot\|_{p}}({\kappa},L)$, whose minima are
attained in ${\cal B}_{\|\cdot\|_{p}}(0,R)$. Then, the complexity of achieving
the dual norm of the gradient bounded by $\epsilon$, for any local oracle, is
bounded below by:

  * •

$\Omega\Big{(}\Big{(}\frac{LR^{\kappa-1}}{\epsilon[\ln
d]^{\kappa-1}}\Big{)}^{\frac{2}{3\kappa-2}}\Big{)}$ if $1\leq p<2$;

  * •

$\Omega\Big{(}\Big{(}\frac{LR^{\kappa-1}}{\epsilon\min\\{p,\ln
d\\}^{\kappa-1}}\Big{)}^{\frac{p}{\kappa p+\kappa-p}}\Big{)}$, if $2\leq
p<\infty$; and,

  * •

$\Omega\Big{(}\Big{(}\frac{LR^{\kappa-1}}{\epsilon[\ln
d]^{\kappa-1}}\Big{)}^{\frac{1}{\kappa-1}}\Big{)}$, if $p=\infty$.

The dimension $d$ for the lower bound to hold must be at least as large as the
lower bound itself.

Comparing to the upper bounds from Theorem 3.1, it follows that for
$p\in(1,2]$ and $\kappa=2$, our bound is optimal up to a
$\log(d)\log(\frac{LR}{(p-1)\epsilon})$ factor; i.e., it is near-optimal.
Recall that the upper bound for $p=1$ can be obtained by applying the result
from Theorem 3.1 with $p=\log(d)/[\log d-1].$ When $p>2$ and $\kappa=2$, our
upper bound is larger than the lower bound by a factor
$\Big{(}\frac{LR}{\epsilon}\Big{)}^{\frac{p-2}{p+2}}\log(\frac{LR}{\epsilon})(\min\\{p,\log(d)\\})^{\frac{p}{p+2}}$.
The reason for the suboptimality in the $p>2$ regime comes from the polynomial
in $1/\epsilon$ factors in the upper bound for complementary composite
minimization from Section 2, and it is a limitation of the regularization
approach used in this work to obtain bounds for the norm of the gradient. In
particular, we believe that it is not possible to obtain tighter bounds via an
alternative analysis by using the same regularization approach. Thus, it is an
interesting open problem to obtain tight bounds for $p>2$, and it may require
developing completely new techniques. Similar complexity gaps are encountered
when $\kappa<2;$ however, it is reasonable to suspect that here the lower
bounds are not sharp. In particular, when $\kappa=1$ points with small
subgradients may not even exist, which is not at all reflected in the lower
bound. Therefore, it is an interesting open problem to investigate how to
strengthen these lower bounds for weakly smooth function classes.

###  4.2 Lower Complexity Bounds for Complementary Composite Minimization

We investigate the (sub)optimality of the composite minimization algorithm in
an oracle complexity model. To accurately reflect how our algorithms work
(namely, using gradient information on the smooth term and regularized
proximal subproblems w.r.t. the uniformly convex term), we introduce a new
problem class and oracle for the complementary composite problem. We observe
that existing constructions in the literature of lower bounds for nonsmooth
uniformly convex optimization (e.g., Juditsky and Nesterov (2014); Srebro and
Sridharan (2012)) apply to our composite setting for $\kappa=1$. The main idea
of the lower bounds in this section is to combine these constructions with
local smoothing, to obtain composite functions that match our assumptions.

######  Assumptions 4.4.

Consider the problem class ${\cal P}({\cal F}_{\|\cdot\|}(L,\kappa),{\cal
U}_{\|\cdot\|}(\lambda,q),R)$, given by composite objective functions

$(P_{f,\psi})~{}~{}~{}\min_{\mathbf{x}\in\mathbf{E}}[\bar{f}(\mathbf{x})=f(\mathbf{x})+\psi(\mathbf{x})],$

with the following assumptions:

  1. (A.1)

$f\in{\cal F}_{\|\cdot\|}(L,\kappa)$;

  2. (A.2)

$\psi\in{\cal U}_{\|\cdot\|}(\lambda,q)$; and,

  3. (A.3)

the optimal solution of $(P_{f,\psi})$ is attained within ${\cal
B}_{\|\cdot\|}(0,R)$.

The problem class is additionally endowed with oracles ${\cal O}_{\cal F}$ and
${\cal O}_{\cal U}$, for function classes ${\cal F}_{\|\cdot\|}(L,\kappa)$ and
${\cal U}_{\|\cdot\|}(\lambda,q)$, respectively; which satisfy

  1. (O.1)

${\cal O}_{\cal F}$ is a local oracle: if $f,g\in{\cal
F}_{\|\cdot\|}(L,\kappa)$ are such that there exists $r>0$ such that they
coincide in a neighborhood ${\cal B}_{\|\cdot\|}(\mathbf{x},r)$, then ${\cal
O}_{\cal F}(\mathbf{x},f)={\cal O}_{\cal F}(\mathbf{x},g)$; and,

  2. (O.2)

${\cal U}_{\|\cdot\|}(\lambda,q)$ is any oracle (not necessarily local).

In brief, we are interested in the oracle complexity of achieving
$\epsilon$-optimality gap for the family of problems $(P_{f,\psi})$, where
$f\in{\cal F}_{\|\cdot\|}(L,\kappa)$ is endowed with a local oracle,
$\psi\in{\cal U}_{\|\cdot\|}(\lambda,q)$ is endowed with any oracle, and the
optimal solution of problem $(P_{f,\psi})$ lies in ${\cal
B}_{\|\cdot\|}(0,R)$. A simple observation is that in the case $\lambda=0$,
our model coincides with the classical oracle mode, which was discussed in the
previous section. The goal now is to prove a more general lower complexity
bound for the composite model.

Before proving the theorem, we first provide some building blocks in this
construction, borrowed from past work of Guzmán and Nemirovski (2015);
Diakonikolas and Guzmán (2020). In particular, our lower bound works generally
for $q$-uniformly convex and locally smoothable spaces.

######  Assumptions 4.5.

Given the normed space $(\mathbf{E},\|\cdot\|)$, we consider the following
properties:

  1. 1.

$\psi(\mathbf{x})=\frac{1}{q}\|\mathbf{x}\|^{q}$ is $q$-uniformly convex with
constant $\bar{\lambda}$ w.r.t. $\|\cdot\|$.

  2. 2.

The space $(\mathbf{E},\|\cdot\|)$ is $(\kappa,\eta,\eta,\bar{\mu})$-locally
smoothable. That is, there exists a mapping ${\cal S}:{\cal
F}_{(\mathbf{E},\|\cdot\|)}(0,1)\to{\cal
F}_{(\mathbf{E},\|\cdot\|)}(\kappa,\overline{\mu})$ (denoted as the smoothing
operator in (Diakonikolas and Guzmán, 2020, Definition 2)), such that $\|{\cal
S}f-f\|_{\infty}\leq\eta$, and this operator preserves the equality of
functions when they coincide in a ball of radius $2\eta$; i.e., if $f|_{{\cal
B}_{\|\cdot\|}(0,2\eta)}=g|_{{\cal B}_{\|\cdot\|}(0,2\eta)}$ then ${\cal
S}f|_{{\cal B}_{\|\cdot\|}(0,\eta)}={\cal S}g|_{{\cal
B}_{\|\cdot\|}(0,\eta)}.$

  3. 3.

There exists $\Delta>0$ and vectors
$\mathbf{z}^{1},\ldots,\mathbf{z}^{M}\in\mathbf{E}$ with
$\|\mathbf{z}^{i}\|_{\ast}\leq 1$, such that for all
$s_{1},\ldots,s_{M}\in\\{-1,+1\\}^{M}$

$\inf_{\bm{\alpha}\in\bm{\Delta}_{M}}\Big{\|}\sum_{i\in[M]}\alpha_{i}s_{i}\mathbf{z}^{i}\Big{\|}_{\ast}\geq\Delta,$
(24)

where
$\bm{\Delta}_{M}=\\{\bm{\alpha}\in\mathbb{R}_{+}^{M}:\sum_{i}\alpha_{i}=1\\}$
is the discrete probability simplex in $M$-dimensions.

The three assumptions in Assumption 4.5 are common in the literature, and can
be intuitively understood as follows. The first is the existence of a simple
function that we can use as the uniformly convex term in the composite model.
The second appeared in (Guzmán and Nemirovski, 2015), and provides a simple
way to reduce the complexity of smooth convex optimization to its nonsmooth
counterpart. We emphasize there is a canonical way to construct smoothing
operators, which is stated in Observation 4.6 below. Finally, the third
assumption comes from the hardness constructions in nonsmooth convex
optimization in Nemirovskii and Yudin (1983), which are given by piecewise
linear objectives that are learned one by one by an adversarial argument. The
fact that the resulting piecewise linear function has a sufficiently negative
optimal value (for any adversarial choice of signs) can be directly obtained
by minimax duality from Eq. (24).

We point out that $\ell_{p}^{d}$ satisfies the assumptions above when $2\leq
p<\infty$.

######  Observation 4.6 ((Guzmán and Nemirovski, 2015)).

Let $2\leq p<\infty$ and $\eta>0$, and consider the space
$\ell_{p}^{d}=(\mathbb{R}^{d},\|\cdot\|_{p})$. We now verify the Assumptions
4.5 for $q=p$, $\bar{\lambda}=1$, $\bar{\mu}=2^{2-\kappa}(\min\\{p,\ln
d\\}/\eta)^{\kappa-1}$ and $\Delta=1/M^{1/p}$. Indeed,

  1. 1.

The $p$-uniform convexity of $\psi$ was discussed after Eq. (18).

  2. 2.

The smoothing operator can be obtained by infimal convolution, with kernel
function $\phi(\mathbf{x})=2\|\mathbf{x}\|_{r}^{2}$ (with $r=\min\\{p,3\ln
d\\}$. We recall that the infimal convolution of two functions $f$ and $\phi$
is given by

$(f\square\phi)(\mathbf{x})=\inf_{h\in{\cal
B}_{p}(0,1)}[f(\mathbf{x}+\mathbf{h})+\phi(\mathbf{h})].$

The infimal convolution above can be adapted to obtain arbitrary uniform
approximation to $f$ and the preservation of equality of functions (see
(Guzmán and Nemirovski, 2015, Section 2.2) for details).

  3. 3.

Letting $\mathbf{z}^{i}=\mathbf{e}_{i}$, $i\in[M]$ be the first $M$ canonical
vectors, we have

$\Big{\|}\sum_{i\in[M]}\alpha_{i}s_{i}\mathbf{z}^{i}\Big{\|}_{p_{\ast}}=\|\bm{\alpha}\|_{p_{\ast}}\geq
M^{1/p_{\ast}-1}\|\bm{\alpha}\|_{1}=M^{-1/p}.$

This bound is achieved when $\alpha_{i}=1/M$, for all $i$.

Before proving the result for $\ell_{p}$-spaces, we provide a general lower
complexity bound for the composite setting, which we will later apply to
derive the lower bounds for $\ell_{p}$ setups.

######  Lemma 4.7.

Let $(\mathbf{E},\|\cdot\|)$ be a normed space that satisfies Assumption 4.5
and let ${\cal P}({\cal F}_{\|\cdot\|}(L,\kappa),{\cal
U}_{\|\cdot\|}(\lambda,q),R)$ be a class of complementary composite problems
that satisfies Assumption 4.4. Suppose the following relations between
parameters are satisfied:

  1. (a)

$2qL\bar{\lambda}/[\lambda\bar{\mu}]\leq R^{q-1}$.

  2. (b)

$(M+3)\eta\leq 4R$.

  3. (c)

$\frac{L}{4\bar{\mu}}(M+7)\eta\leq\frac{1}{2q_{\ast}}\big{(}\frac{L\Delta}{\bar{\mu}}\big{)}^{q_{\ast}}\big{(}\frac{\bar{\lambda}}{\lambda}\big{)}^{\frac{1}{q-1}}$.

Then, the worst-case optimality gap for the problem class is bounded below by

$\frac{1}{2q_{\ast}}\Big{(}\frac{L\Delta}{\bar{\mu}}\Big{)}^{q_{\ast}}\Big{(}\frac{\bar{\lambda}}{\lambda}\Big{)}^{\frac{1}{q-1}}.$

###### Proof.

Given $M\in\mathbb{N}$, scalars $\delta_{1},\ldots,\delta_{M}>0$, and
$s_{1},\ldots,s_{M}\in\\{-1,+1\\}$, we consider the functions

$f_{s}(\mathbf{x})=\frac{L}{\bar{\mu}}{\cal S}\Big{(}\max_{i\in[M]}[\langle
s_{i}\mathbf{z}^{i},\cdot\rangle-\delta_{i}]\Big{)}(\mathbf{x}),$

and
$\bar{f}_{s}(\mathbf{x})=f_{s}(\mathbf{x})+(\lambda/\bar{\lambda})\psi(\mathbf{x})$,
where $\psi$ is given by Assumption 4.5.

We now show the composite objective $\bar{f}_{s}$ satisfies Assumption 4.4.
Properties (A.1) and (A.2) are clearly satisfied. Regarding (A.3), we prove
next that the optimum of these functions lies in ${\cal B}_{\|\cdot\|}(0,R)$.
For this, notice that by Assumption 4.5, Property 2:

$\displaystyle\bar{f}_{s}(\mathbf{x})$ $\displaystyle\geq$
$\displaystyle\frac{L}{\bar{\mu}}\max_{i\in[M]}[\langle
s_{i}\mathbf{z}^{i},\mathbf{x}\rangle-\delta_{i}]-\frac{L\eta}{\bar{\mu}}+\frac{\lambda}{q\bar{\lambda}}\|\mathbf{x}\|^{q}$
$\displaystyle\geq$
$\displaystyle\|\mathbf{x}\|\Big{[}\frac{\lambda}{\bar{\lambda}q}\|\mathbf{x}\|^{q-1}-\frac{L}{\bar{\mu}}\Big{]}-\frac{L}{\bar{\mu}}(\eta+\max_{i}\delta_{i}).$

We will later show that $\eta+\max_{i}\delta_{i}\leq(M+3)\eta/4\leq R$ (the
last inequality by (b)), hence for $\|\mathbf{x}\|\geq R$

$\bar{f}_{s}(\mathbf{x})\geq\Big{(}\frac{\lambda}{\bar{\lambda}q}\|\mathbf{x}\|^{q-1}-\frac{2L}{\bar{\mu}}\Big{)}\|\mathbf{x}\|\geq
0,$

where the last inequality follows from (a). To conclude the verification of
Assumption (A.3), we now prove that
$\min_{\mathbf{x}\in\mathbb{R}}\bar{f}_{s}(\mathbf{x})<0$. Again, by
Assumption 4.5, Property 2:

$\displaystyle\inf_{\mathbf{x}\in\mathbf{E}}\bar{f}(\mathbf{x})$
$\displaystyle\leq$
$\displaystyle\inf_{\mathbf{x}\in\mathbf{E}}\Big{(}\frac{L}{\bar{\mu}}\max_{i\in[M]}[\langle
s_{i}\mathbf{z}^{i},x\rangle-\delta_{i}]+\frac{L}{\bar{\mu}}\eta+\frac{\lambda}{q\bar{\lambda}}\|\mathbf{x}\|^{q}\Big{)}$
$\displaystyle=$
$\displaystyle\max_{\bm{\alpha}\in\bm{\Delta}_{M}}\inf_{x\in\mathbf{E}}\Big{(}\Big{\langle}\frac{L}{\overline{\mu}}\sum_{i\in[M]}\alpha_{i}s_{i}\mathbf{z}^{i},x\Big{\rangle}+\frac{\lambda}{q\bar{\lambda}}\|\mathbf{x}\|^{q}-\frac{L}{\overline{\mu}}\sum_{i\in[M]}\alpha_{i}\delta_{i}+\frac{L}{\overline{\mu}}\eta\Big{)}$
$\displaystyle=$
$\displaystyle\max_{\bm{\alpha}\in\bm{\Delta}_{M}}-\frac{1}{q_{\ast}}\Big{(}\frac{L}{\bar{\mu}}\Big{)}^{q_{\ast}}\Big{(}\frac{\bar{\lambda}}{\lambda}\Big{)}^{\frac{1}{q-1}}\Big{\|}\sum_{i\in[M]}\alpha_{i}s_{i}\mathbf{z}^{i}\Big{\|}_{\ast}^{q_{\ast}}-\frac{L}{\overline{\mu}}\sum_{i\in[M]}\alpha_{i}\delta_{i}+\frac{L}{\overline{\mu}}\eta$
$\displaystyle=$
$\displaystyle-\frac{1}{q_{\ast}}\Big{(}\frac{L}{\bar{\mu}}\Big{)}^{q_{\ast}}\Big{(}\frac{\bar{\lambda}}{\lambda}\Big{)}^{\frac{1}{q-1}}\Delta^{q_{\ast}}+\frac{L}{\overline{\mu}}\eta.$

Notice that the second step above follows from the Sion Minimax Theorem (Sion,
1958). We conclude that the optimal value of $(P_{f,\psi})$ is negative by
(c).

Following the arguments provided in Guzmán and Nemirovski (2015, Proposition
2), one can prove that for any algorithm interacting with oracle ${\cal
O}_{\cal F}$, after $M$ steps there exists a choice of
$s_{1},\ldots,s_{M}\in\\{-1,+1\\}^{M}$ such that

$\min_{t\in[M]}f_{s}(\mathbf{x}^{t})\geq\frac{L}{\bar{\mu}}[-\eta-\max_{i\in[M]}\delta_{i}];$

further, for this adversarial argument it suffices that
$\min_{i\in[M]}\delta_{i}=0$, and $\max_{i\in[M]}\delta_{i}\geq(M-1)\eta/4$.

We conclude that the optimality gap after $M$ steps is bounded below by

$\min_{t\in[M]}\bar{f}_{s}(\mathbf{x}^{t})-\min_{\mathbf{x}\in\mathbf{E}}\bar{f}_{s}(\mathbf{x})\geq-\frac{L}{4\bar{\mu}}(M+7)\eta+\frac{1}{q_{\ast}}\Big{(}\frac{L}{\bar{\mu}}\Big{)}^{q_{\ast}}\Big{(}\frac{\bar{\lambda}}{\lambda}\Big{)}^{\frac{1}{q-1}}\Delta^{q_{\ast}}\geq\frac{1}{2q_{\ast}}\Big{(}\frac{L\Delta}{\bar{\mu}}\Big{)}^{q_{\ast}}\Big{(}\frac{\bar{\lambda}}{\lambda}\Big{)}^{\frac{1}{q-1}},$

where we used the third bound from the statement. ∎

We now proceed to the lower bounds for $\ell_{p}$-setups, with $2\leq
p\leq\infty$.

######  Theorem 4.8.

Consider the space $\ell_{p}^{d}=(\mathbb{R}^{d},\|\cdot\|_{p})$, where $2\leq
p<\infty$. Then, the oracle complexity of problem class ${\cal P}:={\cal
P}({\cal F}_{\|\cdot\|}(L,\kappa),{\cal U}_{\|\cdot\|}(\lambda,p),R)$,
comprised of composite problems in the form $(P_{f,\psi})$ under Assumptions
4.4, is bounded below by

$\mathrm{Compl}({\cal P},({\cal O}_{\cal F},{\cal
O}_{\psi}),\epsilon)\geq\left\\{\begin{array}[]{ll}\Big{\lfloor}\sqrt{\frac{L}{2\lambda}}-7\Big{\rfloor}&\mbox{
if }p=\kappa=2,\,\epsilon<2\sqrt{2\lambda
L}R^{2}\min\\{\frac{2\lambda}{L},1\\}\\\ \frac{C(p,\kappa)}{\min\\{p,\ln
d\\}^{2(\kappa-1)}}\left(\frac{L^{p}}{\lambda^{\kappa}\epsilon^{p-\kappa}}\right)^{\frac{1}{\kappa
p+\kappa-p}}&\mbox{ if }1\leq\kappa<p,\,p\in[2,\infty],\,\mbox{and
}\lambda\geq\tilde{\lambda}.\end{array}\right.$

where
$C(p,\kappa):=\left(\Big{(}\frac{p-1}{p}\Big{)}^{\kappa(p-1)}2^{\frac{(p-\kappa)(1-2p)+(\kappa-1)p(2p-3)}{(p-1)}}\right)^{\frac{1}{\kappa
p+\kappa-p}}$ is bounded below by an absolute constant, and

$\tilde{\lambda}:=C\max\left\\{\min\\{p,\ln
d\\}^{3}\Big{(}\dfrac{\epsilon^{\kappa}}{LR}\Big{)}^{\frac{1}{\kappa-1}},\min\\{p,\ln
d\\}^{5}\left(\dfrac{\epsilon^{p}}{L^{(p+1)}R^{\frac{(p-1)(\kappa
p+\kappa-p)}{(\kappa-1)}}}\right)^{\frac{\kappa-1}{\kappa p+1-p}}\right\\},$
(25)

with $C>0$ is a universal constant.

In particular, our lower bounds show that the algorithm presented in the
previous section –particularly the rates stated in Theorem 2.3– are nearly
optimal. In the case $p=\kappa=2$, the gap between upper and lower bounds is
only given by a factor which grows at most logarithmically in
$L\phi(\bar{\mathbf{x}}^{\ast})/\epsilon$, and in the case $\kappa<p$, the gap
is $O\big{(}\log(L\phi(\bar{\mathbf{x}}^{\ast})/\epsilon)/\min\\{p,\ln
d\\}^{\Theta(1)}\big{)}$. In both cases, the gaps are quite moderate, so the
proposed algorithm is proved to be nearly optimal. Finally, we would also like
to emphasize that the constant $C(p,\kappa)=\Theta(1)$, as a function of
$1<\kappa\leq 2$ and $2\leq p\leq\infty$. Therefore, the lower bounds also
apply to the case $p=\infty$.

###### Proof of Theorem 4.8.

By Observation 4.6, in the case of $\ell_{p}^{d}$, with $2\leq p<\infty$,
Assumption 4.5 is satisfied if $q=p$, $\Delta=1/M^{1/p}$,
$\overline{\lambda}=1$, and $\bar{\mu}=2^{2-\kappa}(\min\\{p,\ln
d\\}/\eta)^{\kappa-1}$ (for given $\eta>0$). This way, hypotheses (a), (b),
(c) in Lemma 4.7 become

  1. (a)

$\eta\leq\frac{\min\\{p,\ln d\\}}{2}\big{(}\frac{\lambda
R^{p-1}}{pL}\big{)}^{\frac{1}{\kappa-1}}$.

  2. (b)

$(M+3)\eta\leq 4R$.

  3. (c)

$\eta^{p-\kappa}\leq\frac{2^{p+\kappa-3}L}{p_{\ast}^{(p-1)}\min\\{p,\ln
d\\}^{(\kappa-1)}\lambda M(M+7)^{(p-1)}}$.

Case 1: $p=\kappa=2$. In order to satisfy (c), it suffices to choose
$M=\Big{\lfloor}\sqrt{\frac{L}{2\lambda}}-7\Big{\rfloor}.$ Given such choice,
to satisfy (a), (b) of the lemma, we can choose

$\eta=\min\Big{\\{}\frac{\lambda R}{2L},\frac{4R}{M+3}\Big{\\}}\geq
R\sqrt{\frac{2\lambda}{L}}\min\Big{\\{}\frac{1}{4}\sqrt{\frac{2\lambda}{L}},4\Big{\\}}.$

Now, under the conditions imposed above, the lemma provides an optimality gap
lower bound of

$\displaystyle\frac{1}{4\lambda}\Big{(}\frac{L\eta}{2\sqrt{M}}\Big{)}^{2}\geq
2\sqrt{2\lambda L}R^{2}\min\Big{\\{}\frac{2\lambda}{L},1\Big{\\}}.$

In conclusion, if $\epsilon<2\sqrt{2\lambda L}R^{2}\min\\{2\lambda/L,1\\}$,
then

$\mathrm{Compl}({\cal P},({\cal O}_{\cal F},{\cal
O}_{\psi}),\epsilon)\geq\Big{\lfloor}\sqrt{\frac{L}{2\lambda}}\Big{\rfloor}-1.$

Case 2: $p>\kappa$ (where $1<\kappa\leq 2,$ $2\leq p<\infty$). Here, to ensure
(a), (b) it suffices that

$\eta\leq\min\Big{\\{}\frac{4R}{M+3},\frac{\min\\{p,\ln
d\\}}{2}\Big{(}\frac{\lambda
R^{p-1}}{p}\Big{)}^{\frac{1}{\kappa-1}}\Big{\\}}.$ (26)

We will later certify these conditions hold. On the other hand, for (c) it
suffices to let

$\eta=\Big{[}\Big{(}\frac{p-1}{p}\Big{)}^{p-1}\frac{2^{p+\kappa-3}L}{\lambda\min\\{p,\ln
d\\}^{\kappa-1}M(M+7)^{p-1}}\Big{]}^{\frac{1}{p-\kappa}}.$

Then by Lemma 4.7 the optimality gap is bounded below as

$\displaystyle\frac{1}{2p_{\ast}}\Big{(}\frac{L^{p}\eta^{p(\kappa-1)}}{2^{p(2-\kappa)}\lambda
M\min\\{p,\ln d\\}^{p(\kappa-1)}}\Big{)}^{\frac{1}{p-1}}$ $\displaystyle=$
$\displaystyle\left[\Big{(}\frac{p-1}{p}\Big{)}^{\kappa(p-1)}2^{\frac{(p-\kappa)(1-2p)+(\kappa-1)p(2p-3)}{(p-1)}}\cdot\frac{L^{p}}{\min\\{p,\ln
d\\}^{\frac{p(\kappa-1)(\kappa
p-2\kappa+1)}{p-1}}\lambda^{\kappa}(M+7)^{\kappa
p+\kappa-p}}\right]^{\frac{1}{p-\kappa}}.$

Let
$C(p,\kappa):=\left(\Big{(}\frac{p-1}{p}\Big{)}^{\kappa(p-1)}2^{\frac{(p-\kappa)(1-2p)+(\kappa-1)p(2p-3)}{(p-1)}}\right)^{\frac{1}{\kappa
p+\kappa-p}}$. In particular, if $\epsilon$ is smaller than the gap above,
resolving for $M$ gives

$\mathrm{Compl}({\cal P},({\cal O}_{\cal F},{\cal O}_{\psi}),\epsilon)\geq
M=\frac{C(p,\kappa)}{\min\\{p,\ln
d\\}^{2(\kappa-1)}}\left(\frac{L^{p}}{\lambda^{\kappa}\epsilon^{p-\kappa}}\right)^{\frac{1}{\kappa
p+\kappa-p}},$ (27)

where we further simplified the bound, noting that $\frac{p(\kappa-1)(\kappa
p-2\kappa+1)}{(p-1)(p\kappa+\kappa-p)}\leq 2(\kappa-1)$.

Now, given the chosen value of $M$, we will verify that (26) holds. For this,
we note that (26) is implied by the following pair of inequalities

$\displaystyle\lambda$ $\displaystyle\geq$ $\displaystyle
C^{\prime}(p,\kappa)\min\\{p,\ln
d\\}^{(\kappa-1)(2\kappa-1)}\Big{(}\dfrac{\epsilon^{\kappa}}{LR}\Big{)}^{\frac{1}{\kappa-1}}$
(28) $\displaystyle\lambda$ $\displaystyle\geq$ $\displaystyle
C^{\prime\prime}(p,\kappa)\min\\{p,\ln
d\\}^{5}\left(\dfrac{\epsilon^{p}}{L^{(p+1)}R^{\frac{(p-1)(\kappa
p+\kappa-p)}{(\kappa-1)}}}\right)^{\frac{\kappa-1}{\kappa p+1-p}}$ (29)

with $C^{\prime}(p,\kappa),C^{\prime\prime}(p,\kappa)\geq C>0$, are bounded
below by a universal positive constant. Therefore, there exists a universal
constant $C>0$ such that if $\lambda$ satisfies Eqs. (28) and (29) where
$C^{\prime}(p,\kappa),C^{\prime\prime}(p,\kappa)$ are replaced by $C$, then
the lower complexity bound from Eq. (27) holds. ∎

######  Remark 4.9.

Observe that the lower bounds from Theorem 4.8 apply only when $\lambda$ is
sufficiently large, which is consistent with the behavior of our algorithm,
which for small values of $\lambda$ obtains iteration complexity matching the
classical smooth setting (as if we ignore the uniform convexity of the
objective).

##  5 Applications

We now provide some interesting applications of the results from Sections 2
and 3 to different regression problems. In typical applications, the data
matrix $\mathbf{A}$ is assumed to have fewer rows than columns, so that the
system $\mathbf{A}\mathbf{x}=\mathbf{b}$, where $\mathbf{b}$ is the vector of
labels, is underdetermined, and one seeks a sparse solution $\mathbf{x}^{*}$
that provides a good linear fit between the data and the labels.

###  5.1 Elastic Net

One of the simplest applications of our framework is to the elastic net
regularization, introduced by Zou and Hastie (2005). Elastic net regularized
problems are of the form:

$\min_{\mathbf{x}\in\mathbb{R}^{d}}f(\mathbf{x})+\frac{\lambda_{2}}{2}\|\mathbf{x}\|_{2}^{2}+\lambda_{1}\|\mathbf{x}\|_{1},$

i.e., the elastic net regularization combines the lasso and ridge
regularizers. Function $f$ is assumed to be $(L,2)$-weakly smooth (i.e.,
$L$-smooth) w.r.t. the Euclidean norm $\|\cdot\|_{2}$. It is typically chosen
as either the linear least squares or the logistic loss.

We can apply results from Section 2 to this problem for $q=\kappa=2,$ choosing
$\psi(\mathbf{x})=\frac{\lambda}{2}\|\mathbf{x}\|_{2}^{2}$ and
$\phi(\mathbf{x})=\frac{1}{2}\|\mathbf{x}-\mathbf{x}_{0}\|_{2}^{2}.$ Observe
that our algorithm only needs to solve subproblems of the form

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\Big{\\{}\left\langle\mathbf{z},\mathbf{x}\right\rangle+\frac{\lambda^{\prime\prime}}{2}\|\mathbf{x}\|_{2}^{2}+\lambda^{\prime}\|\mathbf{x}\|_{1}\Big{\\}},$

for fixed vectors $\mathbf{z}\in\mathbb{R}^{d}$ and fixed parameters
$\lambda^{\prime},\lambda^{\prime\prime}$, which is computationally
inexpensive, as the problem under the min is separable.

Applying Theorem 2.3, the elastic net regularized problems can be solved to
any accuracy $\epsilon>0$ using

$k=O\bigg{(}\min\bigg{\\{}\sqrt{\frac{L}{\lambda_{2}}}\log\bigg{(}\frac{L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{2}}{\epsilon}\Big{)},\;\sqrt{\frac{L\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{2}^{2}}{\epsilon}}\bigg{\\}}\bigg{)}$

iterations, where $\mathbf{x}^{*}\in\mathbb{R}^{d}$ is the problem minimizer.

###  5.2 Bridge Regression

Bridge regression problems were originally introduced by Frank and Friedman
(1993), and are defined by

$\displaystyle\min_{\begin{subarray}{c}\mathbf{x}\in\mathbb{R}^{d}:\\\
\|\mathbf{x}\|_{p}\leq t\end{subarray}}$
$\displaystyle\;\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}$ (30)

where $t$ is a positive scalar, $p\in[1,2],$ $\mathbf{A}$ is the matrix of
observations, and $\mathbf{b}$ is the vector of labels. In particular, for
$p=1,$ the problem reduces to lasso, while for $p=2$ we recover ridge
regression.

Bridge regression has traditionally been used either as an interpolation
between lasso and ridge regression, or to model Bayesian priors with the
exponential power distribution (see Park and Casella (2008) and Hastie et al.
(2009, Section 3.4.3). The problem is often posed in the equivalent (due to
Lagrangian duality) penalized (or regularized) form:

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\Big{\\{}\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}+\frac{\lambda}{p}\|\mathbf{x}\|_{p}^{p}\Big{\\}}.$

Writing the regularizer as $\frac{1}{p}\|\mathbf{x}\|_{p}^{p}$ is typically
chosen due to its separable form. However, using different parametrization,
the problem from Eq. (30) is also equivalent to

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\Big{\\{}\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}+\frac{\lambda}{2}\|\mathbf{x}\|_{p}^{2}\Big{\\}},$
(31)

which is more convenient for the application of our results, as
$\frac{1}{2}\|\mathbf{x}\|_{p}^{2}$ is $(p-1)$-strongly convex w.r.t.
$\|\cdot\|_{p}$.

Further, looking at the gradient $\nabla
f(\mathbf{x})=\mathbf{A}^{T}\mathbf{A}\mathbf{x}-\mathbf{A}^{T}\mathbf{b}$ of
$f(\mathbf{x})=\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}$, it is
not hard to argue that $f(\mathbf{x})$ is $L_{p}$-smooth w.r.t.
$\|\cdot\|_{p},$ where $L_{p}=\|\mathbf{A}^{T}\mathbf{A}\|_{p\to
p_{\ast}}=\sup_{\mathbf{x}\in\mathbb{R}^{d}:\|\mathbf{x}\|_{p}\neq
0}\frac{\|\mathbf{A}^{T}\mathbf{A}\mathbf{x}\|_{p_{\ast}}}{\|\mathbf{x}\|_{p}}$.
Namely, this follows as

$\|\nabla f(\mathbf{x})-\nabla
f(\mathbf{y})\|_{p_{\ast}}=\|\mathbf{A}^{T}\mathbf{A}(\mathbf{x}-\mathbf{y})\|_{p_{\ast}}\leq\|\mathbf{A}^{T}\mathbf{A}\|_{p\to
p_{\ast}}\|\mathbf{x}-\mathbf{y}\|_{p}.$

An interesting feature of the formulation in Eq. (31) is that it implies a
certain trade-off between the $p_{\ast}$-fit of the data and the $p$-norm of
the regressor. Namely, if $\bar{\mathbf{x}}^{*}$ solves the problem from Eq.
(31), then

$\|\mathbf{A}^{T}(\mathbf{A}\bar{\mathbf{x}}^{*}-\mathbf{b})\|_{p_{\ast}}=\lambda\|\bar{\mathbf{x}}^{*}\|_{p}.$
(32)

This simply follows by setting the gradient of
$\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}+\frac{1}{2}\|\mathbf{x}\|_{p}^{2}$
to zero, and using that
$\big{\|}\nabla\big{(}\frac{1}{2}\|\mathbf{x}\|_{p}^{2}\big{)}\big{\|}_{p_{\ast}}=\|\mathbf{x}\|_{p},$
$\forall\mathbf{x}\in\mathbb{R}^{d}$ (see Proposition 1.5).

More recently, related problems of the form

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\Big{\\{}\sqrt{\ell(\mathbf{x},\mathbf{A},\mathbf{b})}+\lambda^{\prime}\|\mathbf{x}\|_{p}\Big{\\}},$

where $\ell(\mathbf{x},\mathbf{A},\mathbf{b})$ is a more general loss
function, have been used in distributionally robust optimization (see Blanchet
et al. (2019)). Again, a different parametrization of the same problem leads
to the equivalent form

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\Big{\\{}{\ell(\mathbf{x},\mathbf{A},\mathbf{b})}+\frac{\lambda}{2}\|\mathbf{x}\|_{p}^{2}\Big{\\}},$
(33)

and our results can be applied as long as
$\ell(\mathbf{x},\mathbf{A},\mathbf{b})$ is $L_{p}$-smooth w.r.t.
$\|\cdot\|_{p}$.666Note that, by the inequalities relating $\ell_{p}$-norms,
any function that is $L$-smooth w.r.t. $\|\cdot\|_{2}$, is also $L$-smooth
w.r.t. $\|\cdot\|_{p}$ for $p\in[1,2]$. That is, for $p\in[1,2],$ the
smoothness parameter w.r.t. $\|\cdot\|_{p}$ can only be lower than the
smoothness parameter w.r.t. $\|\cdot\|_{2}$, often being significantly lower.

A direct application of our result from Theorem 2.3 tells us that we can
approximate the problem from Eq. (31) with accuracy $\epsilon>0$ using

$k=O\bigg{(}\min\bigg{\\{}\sqrt{\frac{L_{p}}{\lambda(p-1)}}\log\Big{(}\frac{L_{p}\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{p}}{\epsilon}\Big{)},\;\sqrt{\frac{L_{p}\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{p}^{2}}{\epsilon}}\bigg{\\}}\bigg{)}$
(34)

iterations of Generalized AGD+ from Eq. (7).

Further, using Corollary 2.4, we get that within the same number of iterations
the output point $\mathbf{y}_{k}$ of the algorithm satisfies
$\|\mathbf{y}_{k}-\bar{\mathbf{x}}^{*}\|_{p}\leq\sqrt{\frac{2\epsilon}{\lambda(p-1)}}.$
Additionally, for quadratic losses, using triangle inequality and Eq. (32), we
have the following “goodness of fit” guarantee

$\displaystyle\|\mathbf{A}^{T}(\mathbf{A}\mathbf{y}_{k}-\mathbf{b})\|_{p_{\ast}}\leq\|\mathbf{A}^{T}\mathbf{A}(\mathbf{y}_{k}-\bar{\mathbf{x}}^{*})\|_{p_{\ast}}+\lambda\|\bar{\mathbf{x}}^{*}\|_{p}\leq
L_{p}\sqrt{\frac{2\epsilon}{\lambda(p-1)}}+\lambda\|\bar{\mathbf{x}}^{*}\|_{p}.$

Finally, note that it is possible to apply our algorithm to $\ell_{1}$
regularized problems (lasso), applying results from Theorem 2.3 with
$\psi(\mathbf{x})=\lambda\|\mathbf{x}\|_{1}$ and
$\phi(\mathbf{x})=\frac{1}{2}\|\mathbf{x}-\mathbf{x}_{0}\|_{2}^{2}.$ In this
case, as $\psi$ is not strongly convex, the resulting bound is
$k=O\Big{(}\sqrt{\frac{L_{2}\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|_{2}^{2}}{\epsilon}}\Big{)}$,
which matches the iteration complexity of FISTA (Beck and Teboulle, 2009).

###  5.3 Dantzig Selector Problem

Dantzig selector problem, introduced by Candés and Tao (2007), consists in
solving problems of the form

$\min_{\begin{subarray}{c}\mathbf{x}\in\mathbb{R}^{d}:\\\
\|\mathbf{x}\|_{1}\leq
t\end{subarray}}\|\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b})\|_{\infty},\quad\text{
or, equivalently
}\quad\min_{\begin{subarray}{c}\mathbf{x}\in\mathbb{R}^{d}:\\\
\|\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b})\|_{\infty}\leq
t\end{subarray}}\|\mathbf{x}\|_{1},$

where $t$ is some positive parameter.

Similar to other regression problems described in this section, Dantzig
selector problem can be considered in its unconstrained, regularized form. One
variant of the problem that can be addressed with our algorithm is

$\min_{\mathbf{x}\in\mathbb{R}^{d}}\frac{1}{2}\|\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b})\|_{p_{\ast}}^{2}+\frac{\lambda}{2}\|\mathbf{x}\|_{p}^{2},$
(35)

where $p$ is chosen sufficiently close to one so that $\|\cdot\|_{p}$ closely
approximates $\|\cdot\|_{1}$ and $\|\cdot\|_{p_{\ast}}$ closely approximates
$\|\cdot\|_{\infty}$, where $\frac{1}{p}+\frac{1}{p_{\ast}}=1$. In particular,
when $p^{\ast}=[\log d]/\ln(1+\epsilon)$we have that
$(1-\epsilon)\|\mathbf{x}\|_{1}\leq\|\mathbf{x}\|_{p}\leq\|\mathbf{x}\|_{1}$
and
$\|\mathbf{x}\|_{\infty}\leq\|\mathbf{x}\|_{p}\leq(1+\epsilon)\|\mathbf{x}\|_{\infty},$
$\forall\mathbf{x}\in\mathbb{R}^{d}.$

As discussed at the beginning of Section 3, in this case,
$\psi(\mathbf{x})=\frac{\lambda}{2}\|\mathbf{x}\|_{p}^{2}$ is
$\lambda(p-1)=\Theta(\frac{\lambda\epsilon}{\log(d)})$-strongly convex w.r.t.
$\|\cdot\|_{p}$ and, by the relationship between norms, is also strongly
convex w.r.t. $\|\cdot\|_{1}$ with the strong convexity constant of the same
order. Further,
$f(\mathbf{x})=\frac{1}{2}\|\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b})\|_{p_{\ast}}^{2}$
can be shown to be $L_{1}$-smooth w.r.t. $\|\cdot\|_{1}$, for
$L_{1}=(1+\epsilon)(p_{\ast}-1)A_{\max}=\Theta(\frac{\log{d}}{\epsilon}A_{\max}),$
where $A_{\max}=\max_{1\leq i,j\leq d}|(\mathbf{A}^{T}\mathbf{A})_{ij}|.$ This
can be done as follows. Using that $\frac{1}{2}\|\cdot\|_{p_{\ast}}^{2}$ is
$(p_{\ast}-1)$-smooth w.r.t. $\|\cdot\|_{p_{\ast}}$ (as $p>2$), we have,
$\forall\mathbf{x},\mathbf{y}\in\mathbb{R}^{d},$

$\displaystyle\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\|_{\infty}$
$\displaystyle\leq\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\|_{p}$
$\displaystyle\leq(p_{\ast}-1)\|(\mathbf{A}^{T}\mathbf{A})(\mathbf{x}-\mathbf{y})\|_{p_{\ast}}$
$\displaystyle\leq(p_{\ast}-1)\|\mathbf{A}^{T}\mathbf{A}\|_{1\to
p_{\ast}}\|\mathbf{x}-\mathbf{y}\|_{1}$
$\displaystyle\leq(p_{\ast}-1)(1+\epsilon)\|\mathbf{A}^{T}\mathbf{A}\|_{1\to\infty}\|\mathbf{x}-\mathbf{y}\|_{1}$
$\displaystyle=(1+\epsilon)(p_{\ast}-1)\max_{1\leq i,j\leq
d}|(\mathbf{A}^{T}\mathbf{A})_{ij}|\cdot\|\mathbf{x}-\mathbf{y}\|_{1}.$

Hence, applying Theorem 2.3, we have that the problem from Eq. (35) can be
approximated to arbitrary additive error $\bar{\epsilon}$ with
$k=O\Big{(}\sqrt{\frac{A_{\max}}{\lambda}}\frac{\log(d)}{\bar{\epsilon}}\log\Big{(}\frac{\log(d)A_{\max}\|\bar{\mathbf{x}}^{*}-\mathbf{x}_{0}\|}{\bar{\epsilon}}\Big{)}\Big{)}$
iterations of Generalized AGD+ from Section 2.

Similar to bridge regression, there is an interesting trade-off between the
$\ell_{1}$ norm of the regressor and goodness of fit revealed by the
formulation we consider (Eq. (35)). In particular, using that at an optimal
solution $\bar{\mathbf{x}}^{*}$ the gradient of the objective from Eq. (35) is
zero and using Proposition 1.5,

$\displaystyle({1-\epsilon})\lambda\|\bar{\mathbf{x}}^{*}\|_{1}\leq{\lambda}\|\bar{\mathbf{x}}^{*}\|_{p}$
$\displaystyle={\lambda}\Big{\|}\nabla\Big{(}\frac{1}{2}\|\bar{\mathbf{x}}^{*}\|_{p}^{2}\Big{)}\Big{\|}_{p_{\ast}}$
$\displaystyle=\Big{\|}\nabla\Big{(}\frac{1}{2}\|\mathbf{A}^{T}(\mathbf{A}\bar{\mathbf{x}}^{*}-\mathbf{b})\|_{p_{\ast}}^{2}\Big{)}\Big{\|}_{p_{\ast}}$
$\displaystyle\leq\|\mathbf{A}^{T}\mathbf{A}\|_{p\to
p_{\ast}}\|\mathbf{A}^{T}(\mathbf{A}\bar{\mathbf{x}}^{*}-\mathbf{b})\|_{p_{\ast}}$
$\displaystyle\leq\frac{1+\epsilon}{1-\epsilon}A_{\max}\|\mathbf{A}^{T}(\mathbf{A}\bar{\mathbf{x}}^{*}-\mathbf{b})\|_{\infty}.$

Hence,
$\lambda\|\bar{\mathbf{x}}^{*}\|_{1}\leq(1+O(\epsilon))A_{\max}\|\mathbf{A}^{T}(\mathbf{A}\bar{\mathbf{x}}^{*}-\mathbf{b})\|_{\infty}.$
As the $\ell_{1}$ norm of the regressor is considered a proxy for sparsity,
this bound provides a trade-off between the parsimony of the model and the
goodness of fit, as a function of the regularization parameter $\lambda$.

###  5.4 $\ell_{p}$ Regression

Standard $\ell_{p}$-regression problems have as their goal finding a vector
$\mathbf{x}^{*}$ that minimizes $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{p},$
where $p\geq 1.$ When $p=1$ or $p=\infty,$ this problem can be solved using
linear programming. More generally, when $p\notin\\{1,\infty\\},$ the problem
is nonlinear, and multiple approaches have been developed for solving it,
including, e.g., a homotopy-based solver (Bubeck et al., 2018), solvers based
on iterative refinement (Adil et al., 2019a; Adil and Sachdeva, 2020), and
solvers based on the classical method of iteratively reweighted least squares
(Ene and Vladu, 2019; Adil et al., 2019b). Such solvers typically rely on fast
linear system solves and attain logarithmic dependence on the inverse accuracy
$1/\epsilon,$ at the cost of iteration count scaling polynomially with one of
the dimensions of $\mathbf{A}$ (typically the lower dimension, which is equal
to the number of rows $m$), each iteration requiring a constant number of
linear system solves.

Here, we consider algorithmic setups in which the iteration count is
dimension-independent and no linear system solves are required, but the
dependence on $1/\epsilon$ is polynomial. First, for standard
$\ell_{p}$-regression problems, we can use use a non-composite variant of the
algorithm (with $\psi(\cdot)=0$), while relying on the fact that the function
$\frac{1}{q}\|\cdot\|_{p}^{q}$ with $q=\min\\{2,p\\}$ is $(1,p)$-weakly smooth
for $p\in(1,2)$ and $(p-1,2)$-weakly smooth for $p\geq 2.$ Using this fact, it
follows that the function

$f_{p}(\mathbf{x})=\frac{1}{q}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{p}^{q}$

is $(L_{p},q)$-weakly smooth w.r.t. $\|\cdot\|_{p}$, with
$L_{p}=\max\\{p-1,1\\}\|\mathbf{A}\|_{p\to p_{\ast}}^{q-1}.$ On the other
hand, function
$\phi(\mathbf{x})=\frac{1}{\bar{q}\min\\{p-1,1\\}}\|\mathbf{x}-\mathbf{x}_{0}\|_{p}^{\bar{q}}$,
where $\bar{q}=\max\\{2,p\\}$ is $(1,\bar{q})$-uniformly convex w.r.t.
$\|\cdot\|_{p}.$ Thus, applying Theorem 2.3, we find that we can construct a
point $\mathbf{y}_{k}\in\mathbb{R}^{d}$ such that
$f_{p}(\mathbf{y}_{k})-f_{p}(\mathbf{x}^{*}),$ where
$\mathbf{x}^{*}\in\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{d}}f_{p}(\mathbf{x}),$
with at most

$k=\begin{cases}O\Big{(}\Big{(}\frac{\|\mathbf{A}\|_{p\to
p_{\ast}}^{p-1}}{\epsilon}\Big{)}^{\frac{2}{3p-2}}\Big{(}\frac{\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}^{2}}{p-1}\Big{)}^{\frac{p}{3p-2}}\Big{)},&\text{
if }p\in(1,2)\\\ O\Big{(}\Big{(}\frac{(p-1)\|\mathbf{A}\|_{p\to
p_{\ast}}}{\epsilon}\Big{)}^{\frac{p}{p+2}}\Big{(}\frac{\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p}^{p}}{p}\Big{)}^{\frac{2}{p+2}}\Big{)},&\text{
if }p\geq 2\end{cases}$

iterations of Generalized AGD+. The same result can be obtained by applying
the iteration complexity-optimal algorithms for smooth minimization over
$\ell_{p}$-spaces (Nemirovskii and Nesterov, 1985; d’Aspremont et al., 2018).

More interesting for our framework is the $\ell_{p}$ regression on correlated
errors, described in the following.

####  $\ell_{p}$-regression on correlated errors.

As argued in Candés and Tao (2007), there are multiple reasons why minimizing
the correlated errors $\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b})$ in
place of the standard errors $\mathbf{A}\mathbf{x}-\mathbf{b}$ is more
meaningful for many applications. First, unlike standard errors, correlated
errors are invariant to orthonormal transformations of the data. Indeed, if
$\mathbf{U}$ is a matrix with orthonormal columns, then
$(\mathbf{U}\mathbf{A})^{T}(\mathbf{U}\mathbf{A}\mathbf{x}-\mathbf{U}\mathbf{b})=\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b})$,
but the same cannot be established for the standard error
$\mathbf{A}\mathbf{x}-\mathbf{b}$. Other reasons involve ensuring that the
model includes explanatory variables that are highly correlated with the data,
which is only possible to argue when working with correlated errors (see
Candés and Tao (2007) for more information).

Within our framework, minimization of correlated errors in $\ell_{p}$-norms
can be reduced to making the gradient small in the $\ell_{p}$-norm; i.e., to
applying results from Section 3. In particular, consider the function:

$f(\mathbf{x})=\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}.$

The gradient of this function is precisely the vector of correlated errors,
i.e., $\nabla f(\mathbf{x})=\mathbf{A}^{T}(\mathbf{A}\mathbf{x}-\mathbf{b}).$
Further, function $f$ is $L_{p_{\ast}}$-smooth w.r.t. $\|\cdot\|_{p_{\ast}}$,
where $L_{p_{\ast}}=\|\mathbf{A}^{T}\mathbf{A}\|_{p_{\ast}\to p}.$

Applying the results from Theorem 3.1, it follows that, for any $\epsilon>0,$
we can construct a vector $\mathbf{y}_{k}\in\mathbb{R}^{d}$ with
$\|\mathbf{A}^{T}(\mathbf{A}\mathbf{y}_{k}-\mathbf{b})\|_{p}\leq\epsilon,$
where $\frac{1}{p}+\frac{1}{p_{\ast}}=1,$ with at most

$k=\begin{cases}\widetilde{O}\bigg{(}\Big{(}\frac{\|\mathbf{A}^{T}\mathbf{A}\|_{p_{\ast}\to
p}\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p_{\ast}}}{\epsilon}\Big{)}^{\frac{2}{3p-2}}\bigg{)},&\text{
if }p\in(1,2)\\\
\widetilde{O}\bigg{(}\sqrt{\frac{\|\mathbf{A}^{T}\mathbf{A}\|_{p_{\ast}\to
p}\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{p_{\ast}}}{\epsilon}}\bigg{)},&\text{ if
}p>2\end{cases}$

iterations of generalized AGD+, where $\widetilde{O}$ hides a factor that is
logarithmic in $1/\epsilon$ and where each iteration takes time linear in the
number of non-zeros of $\mathbf{A}$.

###  5.5 Spectral Variants of Regression Problems

The algorithms we propose in this work are not limited to $\ell_{p}$ settings,
but apply more generally to uniformly convex spaces. A notable example of such
spaces are the Schatten spaces, $\mathscr{S}_{p}:=(\mathbb{R}^{d\times
d},\|\cdot\|_{\mathscr{S},p}),$ where
$\|\mathbf{X}\|_{\mathscr{S},p}=(\sum_{j\in[d]}\sigma_{j}(\mathbf{X})^{p})^{1/p},$
where $\sigma_{1}(\mathbf{X}),\ldots,\sigma_{d}(\mathbf{X})$ are the singular
values of $\mathbf{X}$. In particular, the aforementioned
$\ell_{p}$-regression problems have their natural spectral counterparts, e.g.,
given a linear operator ${\cal A}:\mathbb{R}^{d\times d}\to\mathbb{R}^{k}$,
and $\mathbf{b}\in\mathbb{R}^{k}$,

$\min_{\mathbf{X}\in\mathbb{R}^{d\times d}}\frac{1}{l}\|{\cal
A}\mathbf{X}-\mathbf{b}\|_{q}^{l}+\frac{\lambda}{r}\|\mathbf{X}\|_{\mathscr{S},p}^{r}.$

The most popular example of such a formulation comes from the nuclear norm
relaxation for low-rank matrix completion (Recht et al., 2010; Chandrasekaran
et al., 2012; Nesterov and Nemirovski, 2013). We observe that the exact
formulation of the problem may vary, but by virtue of Lagrangian relaxation we
can interchangeably consider these different formulations as equivalent
(modulo appropriate choice of regularization/constraint parameter choice).

To apply our algorithms to Schatten norm settings, we observe the functions
below are $(1,r)$-uniformly convex, with $r=\max\\{2,p\\}$:

$\Psi_{\mathscr{S},p}(\mathbf{X})=\begin{cases}\frac{1}{2(p-1)}\|\mathbf{X}\|_{\mathscr{S},p}^{2},&\text{
if }p\in(1,2],\\\ \frac{1}{p}\|\mathbf{X}\|_{\mathscr{S},p}^{p},&\text{ if
}p\in(2,+\infty).\end{cases}$

On the other hand, notice that more generally than regression problems, for
composite objectives

$f(\mathbf{X})+\lambda\Psi_{\mathscr{S},p}(\mathbf{X}-\mathbf{X}_{0}),$

if the function $f$ is unitarily invariant and convex, there is a well-known
formula for its subdifferential, based on the subdifferential of its vector
counterpart (there is a one-to-one correspondence between unitarily invariant
functions $\mathbb{R}^{d\times d}$ and absolutely symmetric functions on
$\mathbb{R}^{d}$) (Lewis, 1995). Even if $f$ is not unitarily invariant, in
the case of regression problems the gradients can be computed explicitly. On
the other hand, the regularizer $\Psi_{\mathscr{S},p}$ admits efficiently
computable solutions to problems from Eq. (2), given its unitary invariance
(see, e.g., Beck (2017, Section 7.3.2)).

Iteration complexity bounds obtained with these regularizers are analogous to
those obtained in the $\ell_{p}$ setting. On the other hand, the lower
complexity bounds proved in Section 4 also apply to Schatten spaces by
diagonal embedding from $\ell_{p}^{d}$, hence all the optimality/suboptimality
results established for $\ell_{p}$ carry over into $\mathscr{S}_{p}$.

##  6 Conclusion and Future Work

We presented a general algorithmic framework for _complementary composite
optimization_ , where the objective function is the sum of two functions with
complementary properties – (weak) smoothness and uniform/strong convexity. The
framework has a number of interesting applications, including in making the
gradient of a smooth function small in general norms and in different
regression problems that frequently arise in machine learning. We also
provided lower bounds that certify near-optimality of our algorithmic
framework for the majority of standard $\ell_{p}$ and $\mathscr{S}_{p}$
setups.

Some interesting questions for future work remain. For example, the
regularization-based approach that we employed for gradient norm minimization
leads to near-optimal oracle complexity bounds only when the objective
function is smooth and the norm of the space is strongly convex (i.e., when
the $p_{\ast}$-norm of the gradient is sought for $p_{\ast}\geq 2$). The
primary reason for this result is that these are the only settings in which
the complementary composite minimization leads to linear convergence. As the
bounds we obtain for complementary composite minimization are near-tight, this
represents a fundamental limitation of direct regularization-based approach.
It is an open question whether the non-tight bounds for gradient norm
minimization can be improved using some type of recursive regularization, as
in Allen-Zhu (2018). Of course, there are clear challenges in trying to
generalize such an approach to non-Euclidean norms, caused by the fundamental
limitation that non-Euclidean norms cannot be simultaneously smooth and
strongly convex, as discussed at the beginning of the paper. Another
interesting question is whether there exist direct (not regularization-based)
algorithms for minimizing general gradient norms and that converge with
(near-)optimal oracle complexity.

## References

  * Adil and Sachdeva (2020) Deeksha Adil and Sushant Sachdeva.  Faster $p$-norm minimizing flows, via smoothed $q$-norm problems.  In _Proc. ACM-SIAM SODA’20_ , 2020.
  * Adil et al. (2019a) Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva.  Iterative refinement for $\ell_{p}$-norm regression.  In _Proc. ACM-SIAM SODA’19_ , 2019a.
  * Adil et al. (2019b) Deeksha Adil, Richard Peng, and Sushant Sachdeva.  Fast, provably convergent IRLS algorithm for $p$-norm linear regression.  In _Proc. NeurIPS’19_ , 2019b.
  * Allen-Zhu (2018) Zeyuan Allen-Zhu.  How to make the gradients small stochastically: Even faster convex and nonconvex SGD.  In _Proc. NeurIPS’18_ , 2018.
  * Ball et al. (1994) Keith Ball, Eric A Carlen, and Elliott H Lieb.  Sharp uniform convexity and smoothness inequalities for trace norms.  _Inventiones mathematicae_ , 115(1):463–482, 1994\.
  * Bauschke et al. (2017) Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle.  A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications.  _Mathematics of Operations Research_ , 42(2):330–348, 2017.
  * Bauschke et al. (2019) Heinz H Bauschke, Jérôme Bolte, Jiawei Chen, Marc Teboulle, and Xianfu Wang.  On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity.  _Journal of Optimization Theory and Applications_ , 182(3):1068–1087, 2019.
  * Beck (2017) Amir Beck.  _First-Order Methods in Optimization_.  MOS-SIAM Series on Optimization, 2017.
  * Beck and Teboulle (2009) Amir Beck and Marc Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  _SIAM journal on imaging sciences_ , 2(1):183–202, 2009.
  * Blanchet et al. (2019) Jose Blanchet, Yang Kang, and Karthyek Murthy.  Robust Wasserstein profile inference and applications to machine learning.  _Journal of Applied Probability_ , 56(3):830–857, 2019.
  * Borwein et al. (2009) J. Borwein, A. J. Guirao, P. Hájek, and J. Vanderwerff.  Uniformly convex functions on Banach spaces.  _Proceedings of the AMS_ , 137(3):1081–1091, 2009\.
  * Borwein and Zhu (2004) Jonathan M Borwein and Qiji J Zhu.  _Techniques of Variational Analysis_.  Springer, 2004.
  * Boyd and Vandenberghe (2004) Stephen Boyd and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Bubeck et al. (2018) Sébastien Bubeck, Michael B Cohen, Yin Tat Lee, and Yuanzhi Li.  An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time.  In _Proc. ACM STOC’18_ , 2018.
  * Candés and Tao (2007) Emmanuel Candés and Terence Tao.  The dantzig selector: Statistical estimation when $p$ is much larger than $n$.  _The annals of Statistics_ , 35(6):2313–2351, 2007.
  * Chambolle and Pock (2011) Antonin Chambolle and Thomas Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  _Journal of Mathematical Imaging and Vision_ , 40(1):120–145, 2011.
  * Chandrasekaran et al. (2012) Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky.  The convex geometry of linear inverse problems.  _Found. Comput. Math._ , 12(6):805–849, 2012\.
  * Cohen et al. (2018) Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia.  On acceleration with noise-corrupted gradients.  In _Proc. ICML’18_ , pages 1019–1028, 2018.
  * d’Aspremont et al. (2018) Alexandre d’Aspremont, Cristóbal Guzmán, and Martin Jaggi.  Optimal affine-invariant smooth minimization algorithms.  _SIAM Journal on Optimization_ , 28(3):2384–2405, 2018.
  * Devolder et al. (2014) Olivier Devolder, François Glineur, and Yurii Nesterov.  First-order methods of smooth convex optimization with inexact oracle.  _Mathematical Programming_ , 146(1-2):37–75, 2014\.
  * Diakonikolas and Guzmán (2020) Jelena Diakonikolas and Cristóbal Guzmán.  Lower bounds for parallel and randomized convex optimization.  _Journal of Machine Learning Research_ , 21(5):1–31, 2020.
  * Diakonikolas and Orecchia (2019) Jelena Diakonikolas and Lorenzo Orecchia.  The approximate duality gap technique: A unified theory of first-order methods.  _SIAM Journal on Optimization_ , 29(1):660–689, 2019.
  * Dragomir et al. (2019) Radu-Alexandru Dragomir, Adrien Taylor, Alexandre d’Aspremont, and Jérôme Bolte.  Optimal complexity and certification of Bregman first-order methods.  _arXiv preprint arXiv:1911.08510_ , 2019.
  * Ene and Vladu (2019) Alina Ene and Adrian Vladu.  Improved convergence for $\ell_{1}$ and $\ell_{\infty}$ regression via iteratively reweighted least squares.  In _Proc. ICML’19_ , 2019.
  * Frank and Friedman (1993) LLdiko E Frank and Jerome H Friedman.  A statistical view of some chemometrics regression tools.  _Technometrics_ , 35(2):109–135, 1993.
  * Gasnikov and Nesterov (2018) Alexander Vladimirovich Gasnikov and Yu E Nesterov.  Universal method for stochastic composite optimization problems.  _Computational Mathematics and Mathematical Physics_ , 58(1):48–64, 2018.
  * Guzmán and Nemirovski (2015) Cristóbal Guzmán and Arkadi Nemirovski.  On lower complexity bounds for large-scale smooth convex optimization.  _Journal of Complexity_ , 31(1):1–14, 2015.
  * Hastie et al. (2009) Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  _The elements of statistical learning: data mining, inference, and prediction_.  Springer Science & Business Media, 2009.
  * He et al. (2015) Niao He, Anatoli B. Juditsky, and Arkadi Nemirovski.  Mirror prox algorithm for multi-term composite minimization and semi-separable problems.  _Comput. Optim. Appl._ , 61(2):275–319, 2015\.
  * Juditsky and Nemirovski (2008) Anatoli Juditsky and Arkadii S Nemirovski.  Large deviations of vector-valued martingales in 2-smooth normed spaces.  _arXiv preprint arXiv:0809.0813_ , 2008.
  * Juditsky and Nesterov (2014) Anatoli Juditsky and Yuri Nesterov.  Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization.  _Stoch. Syst._ , 4(1):44–80, 2014.
  * Kim and Fessler (2020) Donghwan Kim and Jeffrey A Fessler.  Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions.  _Journal of Optimization Theory and Applications_ , pages 1–28, 2020\.
  * Lewis (1995) A.S. Lewis.  The convex analysis of unitarily invariant matrix functions.  _Journal of Convex Analysis_ , 2(1/2):173–183, 1995.
  * Lu et al. (2018) Haihao Lu, Robert M Freund, and Yurii Nesterov.  Relatively smooth convex optimization by first-order methods, and applications.  _SIAM Journal on Optimization_ , 28(1):333–354, 2018.
  * Nemirovskii and Nesterov (1985) Arkadi S Nemirovskii and Yu E Nesterov.  Optimal methods of smooth convex minimization.  _USSR Computational Mathematics and Mathematical Physics_ , 25(2):21–30, 1985.
  * Nemirovskii and Yudin (1983) A.S. Nemirovskii and Yudin.  _Problem Complexity and Method Efficiency in Optimization_.  Wiley, 1983.
  * Nesterov (2013) Yu Nesterov.  Gradient methods for minimizing composite functions.  _Mathematical Programming_ , 140(1):125–161, 2013\.
  * Nesterov (2015) Yu Nesterov.  Universal gradient methods for convex optimization problems.  _Mathematical Programming_ , 152(1-2):381–404, 2015.
  * Nesterov (2012) Yurii Nesterov.  How to make the gradients small.  _Optima. Mathematical Optimization Society Newsletter_ , (88):10–11, 2012.
  * Nesterov and Nemirovski (2013) Yurii Nesterov and Arkadi Nemirovski.  On first-order algorithms for $\ell_{1}$/nuclear norm minimization.  _Acta Numerica_ , 22:509, 2013.
  * Park and Casella (2008) Trevor Park and George Casella.  The Bayesian lasso.  _Journal of the American Statistical Association_ , 103(482):681–686, 2008.
  * Recht et al. (2010) Benjamin Recht, Maryam Fazel, and Pablo A Parrilo.  Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.  _SIAM review_ , 52(3):471–501, 2010.
  * Rockafellar (1970) R. Tyrrell Rockafellar.  _Convex analysis_.  Princeton Mathematical Series. Princeton University Press, Princeton, N. J., 1970.
  * Scheinberg et al. (2014) Katya Scheinberg, Donald Goldfarb, and Xi Bai.  Fast first-order methods for composite convex optimization with backtracking.  _Foundations of Computational Mathematics_ , 14(3):389–417, 2014.
  * Sion (1958) Maurice Sion.  On general minimax theorems.  _Pacific Journal of Mathematics_ , 8(1):171–176, 1958.
  * Srebro and Sridharan (2012) Nathan Srebro and Karthik Sridharan.  On convex optimization, fat shattering and learning.  unpublished note, 2012.
  * Zalinescu (1983) C. Zalinescu.  On uniformly convex functions.  _Journal of Mathematical Analysis and Applications_ , 95:344–374, 1983.
  * Zalinescu (2002) Constantin Zalinescu.  _Convex analysis in general vector spaces_.  World scientific, 2002.
  * Zou and Hastie (2005) Hui Zou and Trevor Hastie.  Regularization and variable selection via the elastic net.  _Journal of the royal statistical society: series B (statistical methodology)_ , 67(2):301–320, 2005.