# Aggregating regular norms

Anatoli Juditsky 111LJK, Université Grenoble Alpes, 700 Avenue Centrale, 38401
Domaine Universitaire de Saint-Martin-d’Hères, France, anatoli.juditsky@univ-
grenoble-alpes.fr Arkadi Nemirovski222Georgia Institute of Technology,
Atlanta, Georgia 30332, USA<EMAIL_ADDRESS>
This work was supported by MIAI @ Grenoble Alpes (ANR-19-P3IA-0003).

###### Abstract

The subject of this paper is regularity-preserving aggregation of regular
norms on finite-dimensional linear spaces. Regular norms were introduced in
[5] and are closely related to “type 2” spaces [9, Chapter 9] playing
important role in 1) high-dimensional convex geometry and probability in
Banach spaces, see [15, 12, 13, 9, 8], and in 2) design of proximal first
order algorithms for large-scale convex optimization with dimension-
independent, or nearly so, complexity. Regularity, with moderate parameters,
of a norm makes applicable, in a dimension-independent fashion, various
geometric, probabilistic, and optimization-related results, thus motivating
the subject of this paper—aggregations of regular norms resulting in
controlled (and moderate) inflation of regularity parameters.

##  1 Introduction

This paper focuses on regular norms on (finite-dimensional) linear spaces—the
notion introduced in [5] in connection with developing dimension-independent
bounds on large deviations of sums of i.i.d. random vectors or vector-valued
matringales in normed spaces. Postponing definition of regularity till Section
2, right now it suffices to say that this property is quantified by a pair of
reals $(\varkappa\geq 1,\varsigma\geq 1)$, the smaller the better, and is one
of numerous existing “measures of deviation” of the norm in question from the
standard Euclidean norm (for the latter, $\varkappa=\varsigma=1$).

There are two broad application areas where regularity of norms is of
significant interest. The first is high-dimensional convex geometry and
probability in Banach spaces, see [15, 12, 13, 9, 8] and references therein.
Numerous results in these applications assume that the normed space in
question is of “type $p$” (see [9, Chapter 9]), the case of $p=2$ being, in a
sense, the best. The qualitative property of a normed space $X$ to be of type
2 (which is trivially true for finite-dimensional spaces we are working with)
has numerical characteristics $T(X)$ which enters the quantitative components
of the associated geometric and probabilistic results, the smaller is this
constant, the better. It is immediate to see that when the norm on $X$ is
$(\varkappa,\varsigma)$-regular,one has
$T(X)\leq\varsigma^{2}\sqrt{\varkappa}$. That is, regularity of the norm in
question with “moderate” constant makes applicable, in a dimension-independent
fashion, numerous powerful geometric and probabilistic results. Another
application domain is that of first order proximal type algorithms for large-
scale deterministic and stochastic convex optimization (see, e.g., [1, 2, 7,
11]). It turns out that regularity of a norm allows to equip the ball of the
conjugate norm with a “good proximal setup” resulting in dimension-independent
iteration complexity of associated proximal algorithms for minimizing convex
functions over these balls.

Basic examples of regular norms ([5]) are:

  1. 1.

$\|\cdot\|_{2}$ on ${\mathbf{R}}^{n}$ is $(1,1)$ regular. The norm
$\|\cdot\|_{p}$ on ${\mathbf{R}}^{n}$, $2\leq p\leq\infty$, is
$(\varkappa,\varsigma)$-regular with $\varkappa=O(1)\min[p,\ln(n+1)]$ and
$\varsigma=O(1)$ (here and in what follows $O(1)$ stands for an absolute
constant).

  2. 2.

When $2\leq p\leq\infty$, the Schatten norm $\|\sigma(x)\|_{p}$ on the space
${\mathbf{R}}^{m\times n}$ of $m\times n$ matrices, $\sigma(x)$ being the
singular spectrum of matrix $x$, is $(\varkappa,\varsigma)$-regular with
$\varkappa=O(1)\min[p,\ln(\min(m,n))+1]$ and $\varsigma=O(1)$.

It should be stressed that parameters of regularity in these examples are
either dimension-independent, or deteriorate only logarithmically as the
dimension grows.

The potential applications of regular norms outlined above motivate the goal
of this paper—investigating regularity-preserving “aggregation” of regular
norms.

The main body of the paper is organized as follows: We recall the notion of
regular norm in Section 2.1 and then present our principal
contributions—Theorems 2.1 and 2.2—in Section 2.2; preliminary versions of
these results can be found in our preprint [5]. Then in Section 3 we apply
these results to prove the regularity of ellitopic and spectratopic norms, as
defined in [6, 4]. All proofs are postponed to the appendix.

##  2 Problem statement and main results

###  2.1 Regular norms

Let $\varkappa\geq 1$ and $\varsigma\geq 1$ be two reals. We refer to the norm
${\mathfrak{n}}(\cdot)$ on ${\mathbf{R}}^{n}$ as $\varkappa$-smooth if the
function $\Phi(x)={\mathfrak{n}}^{2}(x)$ is continuously differentiable and
satisfies the relation

$\forall x,h:\Phi(x+h)\leq\Phi(x)+[\Phi^{\prime}(x)]^{T}h+\varkappa\Phi(h),$

or, which is the same (see Lemma A.4), the gradient of $\Phi$ is Lipschitz
continuous with Lipschitz constant $2\varkappa$:

${\mathfrak{n}}_{*}(\nabla\Phi(x)-\nabla\Phi(y))\leq
2\varkappa{\mathfrak{n}}(x-y)$

where ${\mathfrak{n}}_{*}(\cdot)$ is the norm conjugate to
${\mathfrak{n}}(\cdot)$.

Following [5], we say that a norm $\|\cdot\|$ on ${\mathbf{R}}^{n}$ is
$(\varkappa,\varsigma)$-regular if there exists a $\varkappa$-smooth norm
${\mathfrak{n}}(\cdot)$ on ${\mathbf{R}}^{n}$ such that $\|\cdot\|$ is within
factor $\varsigma$ from ${\mathfrak{n}}(\cdot)$:

$\varsigma^{-1}{\mathfrak{n}}(\cdot)\leq\|\cdot\|\leq\varsigma{\mathfrak{n}}(\cdot).$

Clearly, if $\|\cdot\|$ is $\varkappa$-smooth (or
$(\varkappa,\varsigma)$-regular) and $x\mapsto Ax$ is a linear embedding of
${\mathbf{R}}^{m}$ into ${\mathbf{R}}^{n}$ (so that $\mathop{\hbox{\rm
Ker}}A=\\{0\\}$), then the norm $\|y\|_{A}=\|Ay\|$ on ${\mathbf{R}}^{m}$ is
$\varkappa$-smooth (resp., $(\varkappa,\varsigma)$-regular). Besides this, if
$\|\cdot\|^{\prime}$ is within factor $\alpha\geq 1$ from
$(\varkappa,\varsigma)$-regular norm $\|\cdot\|$, that is,

$\alpha^{-1}\|\cdot\|^{\prime}\leq\|\cdot\|\leq\alpha\|\cdot\|^{\prime},$

then $\|\cdot\|^{\prime}$ is $(\varkappa,\alpha\varsigma)$-regular.

The examples of regular norms presented in the introduction stem
straightforwardly from the following facts ([5]; in proximal minimization
context, these facts are reproduced in [10, 3]) which are important in what
follows and in their own right: when $2\leq p<\infty$,

  * •

The norm $\|\cdot\|_{p}$ on ${\mathbf{R}}^{n}$ is $(p-1)$-smooth [5, Example
3.2, Section 4.1.1].

  * •

The Schatten norm $\|\sigma(X)\|_{p}$ on the space ${\mathbf{R}}^{m\times n}$
of $m\times n$ matrices ($\sigma(x)\in{\mathbf{R}}^{\min[m,n]}$ stands for the
singular spectrum of $X$) is $\max[2,p-1]$-smooth [5, Example 3.3, Section
4.1.1].

###  2.2 Main results

Our main results on aggregation of regular norms are as follows:

###### Theorem 2.1

Let $\theta(\cdot):{\mathbf{R}}^{K}\to{\mathbf{R}}$ be a continuous
homogeneous, of degree 1, function which is monotone on ${\mathbf{R}}^{K}_{+}$
and positive outside of the origin. Let $\|\cdot\|_{i}$ be
$(\varkappa,\varsigma)$-regular norms on ${\mathbf{R}}^{n_{i}}$, $1\leq i\leq
K$. Then the aggregated norm

$\|[x_{1};...;x_{K}]\|=\theta^{1/2}(\|x_{1}\|_{1}^{2},...,\|x_{K}\|_{K}^{2})$
(1)

(clearly, this indeed is a norm on ${\mathbf{R}}^{n_{1}+...+n_{K}}$) is
$(c_{1}[\ln(K+1)+\varkappa],c_{2}\varsigma)$-regular, for properly selected
absolute constants $c_{1},c_{2}$.

Our next result is the refinement of Theorem 2.1 in the situation where the
“aggregating function” $\theta$ is a regular absolute norm:

###### Theorem 2.2

Let $\theta$ be an absolute norm on ${\mathbf{R}}^{K}$ which is
$(\overline{\varkappa},\overline{\varsigma})$-regular, and let $\|\cdot\|_{i}$
be $(\varkappa^{\prime},\varsigma^{\prime})$-regular norms on
${\mathbf{R}}^{n_{i}}$, $i\leq K$. Then the norm

$\|[x_{1};...;x_{K}]\|=\theta^{1/2}(\|x_{1}\|_{1}^{2},...,\|x_{K}\|_{K}^{2})$

is $(\varkappa,\varsigma)$-regular on ${\mathbf{R}}^{n_{1}+...+n_{K}}$, with
$\varkappa=2\overline{\varkappa}+\varkappa^{\prime}$ and
$\varsigma=\varsigma^{\prime}\sqrt{\overline{\varsigma}}.$

Finally, we have

###### Proposition 2.1

Let $\|\cdot\|$ be a $(\varkappa,\varsigma)$-regular norm on
${\mathbf{R}}^{n}$ and $x\mapsto Px:{\mathbf{R}}^{n}\to{\mathbf{R}}^{p}$ be an
onto mapping. Then the factor-norm

$\|u\|^{\prime}=\min_{x}\\{\|x\|:Px=u\\}$

induced on ${\mathbf{R}}^{p}$ by $\|\cdot\|$, $P$, is
$(\varkappa,\varsigma)$-regular.

##### Remark:

Theorems 2.1, 2.2 and Proposition 2.1 are formulated as existence results
stating that under such and such assumptions such and such norm $\|\cdot\|$ is
regular with such and such parameters $\varkappa$, $\varsigma$, so that there
exists a $\varkappa$-smooth norm $\|\cdot\|^{\prime}$ which is within factor
$\varsigma$ from $\|\cdot\|$. However, in some applications, e.g., in
proximal-type minimization, “simple existence” of $\|\cdot\|^{\prime}$ is not
enough—we should know what this norm is. In this respect, it should be
stressed that, as is seen from the proofs, the above statements are
“constructive.” For example, in the context of Theorem 2.1, given
$\kappa$-smooth norms which are within the factor $\varsigma$ from the norms
$\|\cdot\|_{i}$, we know how to convert these norms and $\theta(\cdot)$ into a
$(c_{1}[\ln(K+1)+\varkappa])$-smooth norm which is within factor
$c_{2}\varsigma$ of the aggregated norm (1), and similarly for Theorem 2.2 and
Proposition 2.1.

##  3 Illustration: regularity of ellitopic and spectratopic norms

###  3.1 Ellitopes and spectratopes

##### Ellitopes.

A basic ellitope [6, Section 4.2.1] in ${\mathbf{R}}^{n}$ is a set ${\cal X}$
given as

${\cal X}=\\{x\in{\mathbf{R}}^{n}:\exists t\in{\cal T}:x^{T}T_{i}x\leq
t_{i},\,1\leq i\leq K\\},$ (2)

where $T_{i}\succeq 0$, $\sum_{i}T_{i}\succ 0$, and ${\cal T}$ is a convex
compact set in ${\mathbf{R}}^{K}_{+}$ which contains a positive vector and is
monotone: whenever $0\leq t^{\prime}\leq t\in{\cal T}$, we have
$t^{\prime}\in{\cal T}$. Here $A\succeq B\Leftrightarrow B\preceq A$ ($A\succ
B\Leftrightarrow B\prec A$) mean that $A,B$ are symmetric matrices of the same
size such that $B-A$ is positive semidefinite (resp., positive definite).

Ellitope $\overline{X}\subset{\mathbf{R}}^{p}$ is a linear image of basic
ellitope:

$\overline{{\cal X}}=P{\cal X}\hbox{\ with ${\cal X}$ given by (\ref{eeq1})},$
(3)

where $P\in{\mathbf{R}}^{p\times n}$.

The simplest examples of basic ellitopes are

  * •

Bounded intersections ${\cal X}=\\{x:x^{T}T_{k}x\leq 1,k\leq K\\}$,
$T_{k}\succeq 0$, of centered at the origin ellipsoids/elliptic cylinders.

  * •

$\|\cdot\|_{p}$-balls, $p\geq 2$: $\\{x\in{\mathbf{R}}^{n}:\|x\|_{p}\leq
1\\}=\\{x\in{\mathbf{R}}^{n}:\exists t\in{\cal T}:x_{i}^{2}\leq t_{i},\,i\leq
n\\}$, ${\cal T}=\\{t\in{\mathbf{R}}^{n}_{+}:\|t\|_{p/2}\leq 1\\}$.

##### Spectratopes.

A basic spectratope [6, Section 4.3.1] in ${\mathbf{R}}^{n}$ is a set ${\cal
X}$ given as

${\cal X}=\\{x\in{\mathbf{R}}^{n}:\exists t\in{\cal T}:S_{i}^{2}[x]\preceq
t_{i}I_{d_{i}},\,1\leq i\leq K\\},$ (4)

where $S_{i}[x]=\sum_{j=1}^{n}x_{j}S^{ij}$, $S^{ij}\in{\mathbf{S}}^{d_{i}}$,
are linear mappings taking values in the spaces ${\mathbf{S}}^{d_{i}}$ of
$d_{i}\times d_{i}$ symmetric matrices and such that $S_{i}[x]=0$ for all
$i\leq K$ if and only if $x=0$, and ${\cal T}\subset{\mathbf{R}}^{K}_{+}$ is
of the same type as in the definition of a basic ellitope.

Spectratope $\overline{X}\subset{\mathbf{R}}^{p}$ is a linear image of basic
spectratope:

$\overline{{\cal X}}=P{\cal X}\hbox{\ with ${\cal X}$ given by
(\ref{eeq143})},$ (5)

where $P\in{\mathbf{R}}^{p\times n}$.

The simplest examples of basic spectratopes are

  * •

The unit ball of spectral norm $\|\cdot\|_{2,2}$ in the space
${\mathbf{S}}^{m}$ of symmetric $m\times m$ matrices:

$\\{x\in{\mathbf{S}}^{m}:\|x\|_{2,2}\leq 1\\}=\\{x\in{\mathbf{S}}^{m}:\exists
t\in{\cal T}:=[0,1]:S^{2}[x]\preceq tI_{m}\\},\,\,S[x]\equiv x.$

  * •

The unit ball of the spectral norm $\|\cdot\|_{2,2}$ in the space
${\mathbf{R}}^{m\times n}$ of $m\times n$ matrices:

$\\{x\in{\mathbf{R}}^{m\times n}:\|x\|_{2,2}\leq
1\\}=\\{x\in{\mathbf{R}}^{m\times n}:\exists t\in{\cal
T}:=[0,1]:S^{2}[x]\preceq
tI_{m+n}\\},\,S[x]=\left[\begin{array}[]{c|c}&x\cr\hline\cr
x^{T}&\cr\end{array}\right].$

##### Calculus of ellitopes/spectratopes.

Families of ellitopes and of spectratopes are rather rich: as shown in [6,
Section 4.6], each family is closed w.r.t. taking finite intersections, direct
products, arithmetic sums, images under linear mappings and inverse images
under linear embeddings. Furthremore, ellitopic description (2), (3) and
spectratopic description (4), (5) of the results of these operations are
readily given by ellitopic and, respectively, spectratopic descriptions of the
operands. It should also be mentioned that every ellitope is a spectratope as
well.

##### Ellitopic and spectratopic norms.

The sets ${\cal T}\subset{\mathbf{R}}^{K}_{+}$ participating in the definition
of ellitopes and spectratopes are exactly sets of the form

${\cal T}=\\{t\in{\mathbf{R}}^{K}_{+}:\theta(t)\leq 1\\}$ (6)

stemming from functions $\theta(\cdot):{\mathbf{R}}^{K}_{+}\to{\mathbf{R}}$
which are

  1. 1.

convex, continuous, positive outside of the origin, and positively
homogeneous, of homogeneity degree 1,

  2. 2.

monotone on ${\mathbf{R}}^{K}_{+}$: $0\leq t\leq
t^{\prime}\Rightarrow\theta(t)\leq\theta(t^{\prime}).$

Next, basic ellitopes and spectratopes in ${\mathbf{R}}^{n}$ are convex
compact sets which are symmetric w.r.t. the origin and have the origin in
their interior. Consequently, such a set ${\cal X}$ is the unit ball of a norm
$\|\cdot\|_{\cal X}$ on ${\mathbf{R}}^{N}$; this norm is

$\displaystyle\theta^{1/2}\Big{(}[\|T_{1}^{1/2}x\|_{2}^{2};...;\|T_{K}^{1/2}x\|_{2}^{2}]\Big{)},\quad\hbox{when
${\cal X}$ is the ellitope (\ref{eeq1})}$ (7a)
$\displaystyle\theta^{1/2}\Big{(}[\|S_{1}[x]\|_{2,2}^{2};...;\|S_{K}[x]\|_{2,2}^{2}]\Big{)},\quad\hbox{when
${\cal X}$ is the spectratope (\ref{eeq143})}$ (7b)

where $\theta(\cdot)$ is given by (6).

Finally, if $\overline{{\cal X}}$ is an ellitope (a spectratope) given by (3)
(resp., by (5)) and the corresponding mapping $x\mapsto Px$ is an onto one,
$\overline{{\cal X}}$ also is the unit ball of certain norm
$\|\cdot\|_{\overline{{\cal X}}}$ which is nothing but the factor-norm induced
by ${\cal X}$ and $P$:

$\|u\|_{\overline{{\cal X}}}=\min_{x}\left\\{\|x\|_{\cal X}:Px=u\right\\}.$
(8)

##### The result

of this section is as follows:

###### Theorem 3.1

There exist absolute constants $c_{1}$, $c_{2}$ such that

Whenever $\overline{{\cal X}}$ is given by (2), (3), and (6) with ${\hbox{\rm
Rank}}(P)=p$, the ellitopic norm $\|\cdot\|_{\overline{{\cal X}}}$ given by
(7a) and (8) is $(c_{1}\ln(K+1),c_{2})$-regular.

Whenever $\overline{{\cal X}}$ is given by (4), (5), and (6) with ${\hbox{\rm
Rank}}(P)=p$, the spectratopic norm $\|\cdot\|_{\overline{{\cal X}}}$ given by
(7b) and (8) is $(c_{1}[\ln(K+1)+\max_{i\leq K}\ln(d_{i})],c_{2})$-regular.

##  Appendix A Appendix

###  A.1 Proof of Theorem 2.1

####  A.1.1 Preliminary step

Let us show first that in order to prove Theorem 2.1 “as is,” it suffices to
prove it in the case where function $\theta$, in addition to the properties
postulated in theorem’s premise (which are continuity on
${\mathbf{R}}^{K}_{+}$, homogeneity of degree 1, monotonicity, and positivity
outside of the origin), possesses two additional properties, namely,

  1. (a)

is continuously differentiable outside of the origin, and

  2. (b)

satisfies the relation

$t>0\Rightarrow 1/K\leq[\nabla\theta(t)]_{i}\leq(1+1/K),\,1\leq i\leq K.$ (9)

Indeed,

##### 1o.

Let ${\mathfrak{n}}(t)=\theta({\mathrm{abs}}[t])$, where
${\mathrm{abs}}[[t_{1};...;t_{K}]]=[|t_{1}|;...;|t_{K}|]$, so that
${\mathfrak{n}}(t)$ is an absolute norm on ${\mathbf{R}}^{K}$. Denoting by
${\mathfrak{n}}_{*}(\cdot)$ the Fenchel conjugate of ${\mathfrak{n}}(\cdot)$,
the Fenchel conjugate $\vartheta_{\epsilon}$ of the function
$\tfrac{1}{2}{\mathfrak{n}}_{*}^{2}(\cdot)+\tfrac{\epsilon}{2}\|\cdot\|_{2}^{2}$
is a function of the form
$\tfrac{1}{2}\theta_{\epsilon}^{2}({\mathrm{abs}}[\cdot])$ where
$\theta_{\epsilon}:\,{\mathbf{R}}^{K}_{+}\to{\mathbf{R}}$ is convex
homogeneous of degree 1 monotone and positive outside of the origin with
Lipschitz continuous gradient; along with $\vartheta_{\epsilon}$,
$\theta_{\epsilon}$ is continuously differentiable outside of the origin.
Taking $\epsilon>0$ small enough, we can make $\theta_{\epsilon}(\cdot)$ to be
within the factor, say, 1.1, from $\theta(\cdot)$. It clearlty suffices to
prove Theorem 2.1 with $\theta_{\epsilon}$ in the role of $\theta$, so that
from now on let us assume that $\theta$, in addition to what is postulated in
the premise of Theorem 2.1, satisfies (a).

##### 2o.

Now let $s_{i}=\max\\{t_{i}:\,t\geq 0,\,\theta(t)\leq 1\\}$. By diagonal
scaling of ${\mathbf{R}}^{K}$—passing from $\theta(t)$ to $\theta({\cal D}t)$
with positive definite diagonal ${\cal D}$—we can assume that $s_{i}=1$, and
such scaling does not affect the statement we want to prove. Thus, in addition
to what has been already assumed, from now on we assume that
$s_{i}:=\max_{t}\\{t_{i}:\theta(t)\leq 1\\}=1$ for all $i$. Monotonicity of
$\theta(\cdot)$ implies that the basis orths $e_{i}$ belong to the set
$\Theta=\\{t\geq 0:\theta(t)\leq 1\\}$, whence $\theta(t)\leq\sum_{i}t_{i}$,
$t\geq 0$. Besides this, under the assumption that $s_{i}=1$, $i\leq K$,
$\Theta$ is contained in the box $\\{t:\,0\leq t_{i}\leq 1,\,i\leq K\\}$, and
thus is contained in the set $\\{t\geq 0:\sum_{i}t_{i}\leq K\\}$, implying
that $\theta(t)\geq K^{-1}\sum_{i}t_{i}$, $t\geq 0$. Now let
$\overline{\theta}(t)=\theta(t)+K^{-1}\sum_{i}t_{i}$; by the above,
$\theta(\cdot)\leq\overline{\theta}(\cdot)\leq 2\theta(\cdot)$. At the same
time, for $t\geq 0$, $t\neq 0$, one has $[\nabla\overline{\theta}(t)]_{i}\geq
K^{-1}$ for all $i$. Aside of this, we have
$\overline{\theta}(t)\leq(1+1/K)\sum_{i}t_{i}$ for all $t\geq 0$, implying
that for all $s\geq 0$

$(1+1/K)[\sum_{j}t_{j}+s]\geq\overline{\theta}(t+se_{i})\geq\overline{\theta}(t)+s[\nabla\overline{\theta}(t)]_{i}.$

We conclude that $[\nabla\overline{\theta}(t)]_{i}\leq 1+1/K$ for all $i$ and
all nonzero $t\geq 0$. The bottom line is that $\overline{\theta}$ is shares
all properties mentioned in the beginning of Section A.1.1, while
$\theta(\cdot)$ is within factor 2 from $\overline{\theta}(\cdot)$. As a
result, the norms ${\theta(\|x_{1}\|_{1}^{2},...,\|x_{K}\|_{K}^{2})^{1/2}}$
and
${\overline{\theta}(\|x_{1}\|_{1}^{2},...,\|x_{K}\|_{K}^{2})^{1/2})^{1/2}}$
are within factor $\sqrt{2}$ from each other. We conclude that in order to
prove Theorem 2.1 it suffices to prove it in the case when $\theta$, in
addition to what is stated in the premise of the theorem, possesses properties
(a) and (b), which we assume from now on.

####  A.1.2 Proving Theorem 2.1 in the case of (a), (b)

When proving the theorem, we lose nothing when assuming that $\varsigma=1$.
Indeed, replacing $\|\cdot\|_{i}$ with norms which are within some factor of
$\|\cdot\|_{i}$, the aggregation of the new norms is within the same factor of
the aggregation of $\|\cdot\|_{i}$. Thus, from now on we assume that the
squares

$\omega_{i}(x_{i})=\|x_{i}\|_{i}^{2}$

of the norms $\|\cdot\|_{i}$ are continuously differentiable and satisfy the
relation

$[\omega_{i}(x)+[\omega^{\prime}_{i}(x_{i})]^{T}h_{i}\leq]\,\,\,\omega_{i}(x_{i}+h_{i})\leq\omega_{i}(x)+[\nabla\omega_{i}(x_{i})]^{T}h_{i}+\varkappa\omega_{i}(h_{i})\;\forall
x_{i},h_{i}\in{\mathbf{R}}^{n_{i}},\,1\leq i\leq K.$

Note that $\|\nabla\omega(x)\|_{i,*}\leq 2\sqrt{\omega_{i}(x)}$ where
$\|\cdot\|_{i,*}$ is the norm conjugate to $\|\cdot\|_{i}$, thus

$|[\nabla\omega_{i}(x_{i})]^{T}h_{i}|\leq
2\sqrt{\omega_{i}(x_{i})\omega_{i}(h_{i})}.$ (10)

Let $p$ be positive integer, and let

$\displaystyle\overline{{\cal T}}$ $\displaystyle=\\{t\geq 0:\theta(t)=1\\},$
$\displaystyle f(x,t)$
$\displaystyle=\sum_{i=1}^{K}\omega_{i}^{p+1}(x_{i})/t_{i}^{p}:{\mathbf{R}}^{n_{1}+...+n_{K}}\times{\mathbf{R}}^{K}_{+}\to{\mathbf{R}}\cup\\{+\infty\\}$
$\displaystyle F(x,t)$ $\displaystyle=f^{{1\over p+1}}(x,y)$
$\displaystyle\phi(x)$ $\displaystyle=\min_{t\in{\cal T}}f(x,t)$
$\displaystyle\Phi(x)$ $\displaystyle=\min_{t\in{\cal T}}F(x,t)=\phi^{{1\over
p+1}}(x)$

(here, by convention, $a/0$ is 0 when $a=0$ and is $+\infty$ when $a>0$,
making $f(x,t)$ lower semicontinuous on
${\mathbf{R}}^{n_{1}+...+n_{K}}\times{\mathbf{R}}^{K_{+}}$).
0o. Let $q=p/(p+1)$. The function $s^{2}/\tau^{q}$ is convex in $s,\tau$ on
$\\{[s;\tau]:\tau\geq 0\\}$, and
$F(x,t)=\|[\omega_{1}(x_{1})/t_{1}^{q};...;\omega_{K}(x_{K})/t_{K}^{q}]\|_{p+1}$,
that is, $F(x,t)$ is convex in
$[x;t]\in{\mathbf{R}}^{n_{1}+...+n_{K}}\times{\mathbf{R}}^{K}_{+}$.
Consequently, $\phi$ and $\Phi$ are real-valued convex functions on
${\mathbf{R}}^{n_{1}+...+n_{K}}$. Besides this, the convex and positive
outside of the origin function $\Phi$ is homogeneous of degree 2 and as such
is the square of a norm. Our goal in what follows is to demonstrate that with
properly selected $p$ this norm can be taken as regular approximation of
$\|[x_{1};...;x_{K}]\|$ announced in Theorem 2.1.
1o. For evident reasons, minimizers of $f(x,t)$ over $t\in{\cal T}$ do exist
for every $x$. We claim that given $x\neq 0$, the minimizer $t(x)$ of $f(x,t)$
over $t\in{\cal T}$ (or, which clearly is the same, over $t\in\overline{{\cal
T}}$) is unique and is continuous in $x\neq 0$. Indeed, assuming w.l.o.g. that
the nonzero blocks in $x$ are $x_{1},...,x_{m}$, if $t$ and $t^{\prime}$ are
two distinct minimizers of $f(x,t)$ over $t\in\overline{{\cal T}}$, then
$t_{i}=t^{\prime}_{i}=0$ when $i>m$ and the initial blocks
$\overline{t}=[t_{1};...;t_{m}]$,
$\overline{t}^{\prime}=[t_{1}^{\prime};...;t_{m}^{\prime}]$ of $t$ and
$t^{\prime}$ are two distinct minimizers of the function
$\sum_{i=1}^{m}\omega_{i}^{p+1}(x_{i})/\tau_{i}^{p}$ over $\tau$ running
through the set
$\\{\tau:\in{\mathbf{R}}^{m}:[\tau_{1};...;\tau_{m};0;...;0]\in\overline{{\cal
T}}\\}$, which is impossible, since on the latter set the function in question
is strongly convex. To prove that $t(x)$ is continuous on the set $x\neq 0$,
let $\bar{x}\neq 0$ and let $x^{s}\to\bar{x}$ as $s\to\infty$. We should lead
to contradiction the assumption that the vectors $t^{s}=t(x^{s})$ do not
converge to $t(\bar{x})$. Assuming that the latter is the case and taking into
account that $\overline{{\cal T}}$ is compact, we can assume without loss of
generality that $t^{s}$ converge to some $t\neq t(\bar{x})$,
$t\in\overline{{\cal T}}$, as $s\to\infty$. Since $f(x,t)$ is lower
semicontinuous on ${\mathbf{R}}^{n_{1}+...+n_{K}}\times{\mathbf{R}}^{K}_{+}$
and $\phi(x)$ is convex real valued and thus continuous on
${\mathbf{R}}^{n_{1}+...+n_{K}}$, we have
$\phi(x^{s})=f(x^{s},t^{s})\to\phi(\bar{x})$ as $s\to\infty$ and therefore
$f(\bar{x},t)\leq\lim_{s\to\infty}f(x^{s},t^{s})=\phi(\bar{x})$, implying
$f(\bar{x},t)\leq\phi(\bar{x})=\min\limits_{\tau\in\overline{{\cal
T}}}f(\bar{x},\tau)$. Thus, $t$ and $t(\bar{x})$ are two distinct minimizes of
$f(\bar{x},\tau)$ over $\tau\in\overline{{\cal T}}$, which, as we already
know, is impossible when $\bar{x}\neq 0$.
2o. Observe that when $x\neq 0$, $t=t(x)$ if and only if there exists
$\lambda(x)\geq 0$ such that $t$ is the unique solution to the system of
equations

$\displaystyle t$ $\displaystyle\geq 0,\;\;\theta(t)=1,$ $\displaystyle x_{i}$
$\displaystyle=0\Rightarrow t_{i}=0,$ $\displaystyle x_{i}$ $\displaystyle\neq
0\Rightarrow
p\omega_{i}^{p+1}(x_{i})/t_{i}^{p+1}=\lambda(x)\underbrace{[\nabla\theta(t)]_{i}}_{\theta_{i}(x)}$
(11)

in variable $t$. Consequently, when $x\neq 0$, we have $\lambda(x)>0$. Setting
$I(x)=\\{i:x_{i}\neq 0\\}$, for $i\in I(x)$ we have $\theta_{i}(x)>0$ and
$t_{i}(x)=\big{[}\lambda(x)\theta_{i}(x)/p\big{]}^{-{1\over
p+1}}\omega_{i}(x_{i})$, whence

$1=\theta(t(x))=\sum_{i}t_{i}(x)\big{[}\nabla\theta(t(x))\big{]}_{i}=[\lambda(x)/p]^{-{1\over
p+1}}\sum_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over p+1}}(x).$

Thus, when $x\neq 0$, we have

$\displaystyle\lambda(x)$
$\displaystyle=p\left[\sum_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over
p+1}}(x)\right]^{p+1}>0$ $\displaystyle t_{i}(x)$
$\displaystyle=\left\\{\begin{array}[]{ll}{\omega_{i}(x_{i})\theta_{i}^{-{1\over
p+1}}(x)\over\sum_{j}\omega_{j}(x_{j})\theta_{j}^{{p\over p+1}}(x)},&i\in
I(x)=\\{i:x_{i}\neq 0\\}\\\ 0,&i\not\in I(x)\\\ \end{array}\right.$ (12c)
$\displaystyle\phi(x)$
$\displaystyle=\left[\sum_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over
p+1}}(x)\right]^{p+1}.$ (12d)

30. Let $x\neq 0$. For $[x;t]\in{\mathrm{Dom}\,}f$ let

$\begin{array}[]{rcl}[f^{\prime}_{x}(x,t)]_{i}&=&\left\\{\begin{array}[]{ll}0,&x_{i}=0,\\\
(p+1)\omega_{i}^{p}(x_{i})\nabla\omega_{i}(x_{i})/t_{i}^{p}(x),&x_{i}\neq
0,\cr\end{array}\right.\\\
{[f^{\prime}_{t}(x,t)]_{i}}&=&\left\\{\begin{array}[]{ll}-p\omega_{i}^{p+1}(x_{i})/t_{i}^{p+1}(x),&x_{i}\neq
0,\cr 0,&x_{i}=0,\cr\end{array}\right.\\\
f^{\prime}(x,t)&=&[f^{\prime}_{x}(x,t);f^{\prime}_{t}(x,t)],\end{array}$ (13)

so that $f^{\prime}(x,t)\in\partial f(x,t)$ for all
$[x;t]\in{\mathrm{Dom}\,}f$; let also $\phi^{\prime}(0)=0$. We claim that
$\phi^{\prime}(x);=f^{\prime}_{x}(x,t(x))$ is continuous vector field which is
the subgradient (and due to continuity – gradient) vector field of $\phi(x)$
on ${\mathbf{R}}^{n}$. Indeed, by (12d) for $x\neq 0$ we have

$[\phi^{\prime}(x)]_{i}=\left\\{\begin{array}[]{ll}(p+1)\theta_{i}^{{p\over
p+1}}(x)\left[\sum_{j}\omega_{i}(x_{i})\theta_{j}^{{p\over
p+1}}(x)\right]^{p}\nabla\omega_{i}(x_{i}),&x_{i}\neq 0\\\ 0,&x_{i}=0\\\
\end{array}\right.,$

and $\theta_{i}(x)=[\theta^{\prime}(t(x))]$ is continuous in $x$ along with
$t(x)$; continuity of $\phi^{\prime}(x)$ is evident. To prove that
$\phi^{\prime}(x)$ is the gradient field of $\phi(x)$, due to continuity of
the field it suffices to verify that $\phi^{\prime}(x)\in\partial\phi(x)$
whenever $x$ has no zero blocks. For such an $x$, setting $t=t(x)$, we obtain
for $t^{\prime}\in\overline{{\cal T}}$

$\displaystyle f(x^{\prime},t^{\prime})+\lambda(x)(\theta(t^{\prime})-1)$
$\displaystyle\geq\underbrace{[f^{\prime}_{x}(x,t)]^{T}(x^{\prime}-x)}_{[\phi^{\prime}(x)]^{T}(x^{\prime}-x)}$
$\displaystyle+\underbrace{[f^{\prime}_{t}(x,t)]^{T}(t^{\prime}-t)+\lambda(x)[\theta^{\prime}(t)]^{T}(t^{\prime}-t)}_{=0\hbox{\tiny\
by ~{}(\ref{eeq0.c})}}+f(x,t)+\lambda(x)(\theta(t)-1)$

whence

$f(x^{\prime},t^{\prime})\geq\phi(x)+[\phi^{\prime}(x)]^{T}(x^{\prime}-x)$

and

$\phi(x^{\prime})=\min_{t^{\prime}\in\overline{{\cal
T}}}f(x^{\prime},t^{\prime})\geq\phi(x)+[\phi^{\prime}(x)]^{T}(x^{\prime}-x),$

as claimed.
4o. We need the following

###### Lemma A.1

Let $G$ be an open convex domain in ${\mathbf{R}}^{n}$,
$g(\cdot):G\to{\mathbf{R}}$ be a continuously differentiable convex function,
$\|\cdot\|$ be a norm on ${\mathbf{R}}^{n}$ and $\gamma$ be a positive real.
Assume that for every $x\in G$ there exists $r=r_{x}>0$ such that the ball
$V_{x}=\\{u:\|u-x\|<r\\}$ is contained in $G$ and for every $u,v\in V_{x}$ one
has

$g(v)\leq g(u)+[g^{\prime}(u)]^{T}(v-u)+\tfrac{\gamma}{2}\|u-v\|^{2}.$

Then $g^{\prime}(u)$ is Lipschitz continuous with constant $\gamma$ on $G$
w.r.t. $\|\cdot\|$:

$\forall y,z\in G:\|g^{\prime}(y)-g^{\prime}(z)\|_{*}\leq\gamma\|y-z\|,$ (14)

where $\|\cdot\|_{*}$ is the norm conjugate to $\|\cdot\|$.

Proof. Let us fix $x\in G$. Applying Lemma A.4 to $V=V_{x}$ and
$f$—restriction of $g$ on $V$, we conclude that (14) holds true when $y,z\in
V_{x}$; since $x\in G$ is arbitrary, (14) holds true for all $y,z\in G$.
$\Box$

Lemma A.1 admits the following immediate

###### Corollary A.1

Let $g(x)$ be a continuously differentiable convex function on
${\mathbf{R}}^{n}$, and let ${\mathbf{R}}^{n}_{o}$ be the set of all vectors
from ${\mathbf{R}}^{n}$ with all entries different from 0. Let $\|\cdot\|$ be
a norm on ${\mathbf{R}}^{n}$ and $\gamma>0$ be a real. Assume that for every
$x\in{\mathbf{R}}^{n}_{o}$ there exists $r_{x}>0$ such that for the centered
at $x$ $\|\cdot\|$-ball $V_{x}$ of radius $r_{x}$,
$V_{x}\subset{\mathbf{R}}^{n}_{o}$, it holds

$\forall u,v\in V_{x}:g(v)\leq
g(u)+[g^{\prime}(u)]^{T}(v-u)+\tfrac{\gamma}{2}\|u-v\|^{2}.$

Then

$\forall
x,y\in{\mathbf{R}}^{n}:\|g^{\prime}(x)-g^{\prime}(y)\|_{*}\leq\gamma\|x-y\|.$
(15)

Indeed, since $g$ is continuously differentiable and ${\mathbf{R}}^{n}_{o}$ is
dense in ${\mathbf{R}}^{n}$, it suffices to verify (15) for
$x,y\in{\mathbf{R}}^{n}_{o}$. In this case, setting $x_{t}=x+t(y-x)$, $0\leq
t\leq 1$, we can find points $t_{1}<t_{2}<...<t_{k}$ in $(0,1)$ such that
setting $t_{0}=0$, $t_{k+1}=1$, the intervals
$\Delta_{s}=\\{x_{t}:t_{s}<t<t_{s+1}\\}$, $s=0,1,...,k$, belong to
${\mathbf{R}}^{n}_{o}$, that is,
$\mathrm{sign}([x_{t}]_{i})=\epsilon_{i}(s)\in\\{-1,1\\}$, $t_{s}<t<t_{s+1}$.
Then $G_{s}=\\{x\in{\mathbf{R}}^{n}:\mathrm{sign}(x_{i})=\epsilon_{i}(s),i\leq
n\\}$ is an open convex domain containing $\Delta_{s}$. By Lemma A.1, when
$t_{s}<t^{\prime}<t^{\prime\prime}<t_{s+1}$ we have

$\|g^{\prime}(x_{t^{\prime\prime}})-g^{\prime}(x_{t^{\prime}})\|_{*}\leq\gamma\|x_{t^{\prime\prime}}-x_{t^{\prime}}\|=\gamma[t^{\prime\prime}-t^{\prime}]\|y-x\|.$

Passing to limit as $t^{\prime}\to t_{s}+0$ and $t^{\prime\prime}\to
t_{s+1}-0$ and taking into account that $g$ is C1 on ${\mathbf{R}}^{n}$, we
get

$\|g^{\prime}(x_{t_{s+1}})-g^{\prime}(x_{t_{s}})\|_{*}\leq\gamma[t_{s+1}-t_{s}]\|y-x\|,$

whence
$\|g^{\prime}(x_{t_{k+1}})-g^{\prime}(x_{t_{0}})\|_{*}\leq\gamma\|y-x\|$.
$\Box$

50. Let now $x\in{\mathbf{R}}^{n_{1}+...+n_{K}}$ be a vector with all entries different from 0 and $h\in{\mathbf{R}}^{n_{1}+...+n_{K}}$ be a vector with

$\displaystyle\omega^{1/2}_{i}(h_{i})<\omega^{1/2}_{i}(x_{i})/[{(2p+2)}^{2}(1+\varkappa)],\;\;i\leq
K.$ (16)

One has

$\omega_{i}(x_{i})+[\nabla\omega_{i}(x_{i})]^{T}h_{i}\leq\omega_{i}(x_{i}+h_{i})\leq\omega_{i}(x_{i})+[\nabla\omega_{i}(x_{i})]^{T}h_{i}+\varkappa\omega_{i}(h_{i}).$

Thus, when setting

$\Delta_{i}=[\omega_{i}(x_{i}+h_{i})-\omega_{i}(x_{i})]/\omega_{i}(x_{i})$

we have

$\Delta_{i}=[\nabla\omega_{i}(x_{i})^{T}h_{i}]/\omega_{i}(x_{i})+\delta_{i},\quad|\delta_{i}|\leq\varkappa\omega_{i}(h_{i})/\omega_{i}(x_{i}),$

and taking into account (10) and (16),

$|\Delta_{i}|\leq
2\sqrt{\omega_{i}(h_{i})/\omega_{i}(x_{i})}+\varkappa\omega_{i}(h_{i})/\omega_{i}(x_{i})\leq
3\sqrt{\omega_{i}(h_{i})/\omega_{i}(x_{i})}\leq 3/(2p+2)^{2}.$

We have

$\displaystyle\phi(x)+[\phi^{\prime}(x)]^{T}h\leq\phi(x+h)\leq\sum_{i}\left[\sum_{i}\omega_{i}^{p+1}(x_{i}+h_{i})\right]/t_{i}^{p}(x)=\sum_{i}\omega_{i}^{p+1}(x_{i})(1+{\Delta_{i}})^{p+1}$
$\displaystyle\leq\sum_{i}\omega_{i}^{p+1}(x_{i})\left[1+(p+1)\Delta_{i}+{p(p+1)\over
2}\Delta_{i}^{2}\left[1+\sum_{j=1}^{p-1}{|(p-1)\Delta_{i}|^{j}\over
j!}\right]\right]t_{i}^{-p}(x)$
$\displaystyle\leq\sum_{i}\omega_{i}^{p+1}(x_{i})\left[1+(p+1)\Delta_{i}+{{p(p+1)\over
2}\exp\left\\{(p-1)|\Delta_{i}|\right\\}}\Delta_{i}^{2}\right]t_{i}^{-p}(x)$
$\displaystyle\leq\sum_{i}\omega_{i}^{p+1}\bigg{[}1+(p+1)\left[{\nabla\omega_{i}(x_{i})^{T}h_{i}\over\omega_{i}(x_{i})}+\varkappa{\omega_{i}(h_{i})\over\omega_{i}(x_{i})}\right]+{5p(p+1)}{\omega_{i}(h_{i})\over\omega_{i}(x_{i})}\bigg{]}t_{i}^{-p}(x)$
$\displaystyle=\phi(x)+[\phi^{\prime}(x)]^{T}h+{(p+1)(5p+\varkappa)}\sum_{i}\omega_{i}(h_{i})\omega_{i}^{p}(x_{i})t_{i}^{-p}(x)$
$\displaystyle=\phi(x)+\underbrace{[\phi^{\prime}(x)]^{T}h+{(p+1)(5p+\varkappa)}\left[{\sum}_{i}\omega_{i}(h_{i})\theta_{i}^{{p\over
p+1}}(x)\right]\left[{\sum}_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over
p+1}}(x)\right]^{p}}_{\delta}$

where the concluding equality is due to (12c).

Note that for

$\psi(s)=\left\\{\begin{array}[]{ll}s^{{1\over p+1}}&s\geq 0,\\\
-\infty&s<0,\end{array}\right.$

$\bar{s}>0$ and $\delta\in{\mathbf{R}}$ one has

$\psi(\bar{s}+\delta)\leq\psi(\bar{s})+{1\over p+1}\bar{s}^{-{p\over
p+1}}\delta=\psi(\bar{s})+{1\over p+1}{\delta\over\psi^{p}(\bar{s})}.$

Hence,

$\displaystyle\Phi(x)+[\Phi^{\prime}(x)]^{T}h\leq\Phi(x+h)=\psi(\phi(x+h))\leq\psi(\phi(x)+\delta)\leq\psi(\phi(x))+{1\over
p+1}\delta/\psi^{p}(\phi(x))$ $\displaystyle=\Phi(x)+{1\over
p+1}[\phi^{\prime}(x)]^{T}h/\psi^{p}(\phi(x))$
$\displaystyle\quad\quad+{(5p+\varkappa)}\left[{\sum}_{i}\omega_{i}(h_{i})\theta_{i}^{{p\over
p+1}}(x)\right]\left[{\sum}_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over
p+1}}(x)\right]^{p}\psi^{-p}(\phi(x))$
$\displaystyle=\Phi(x)+[\Phi^{\prime}(x)]^{T}h+{(5p+\varkappa)}\left[{\sum}_{i}\omega_{i}(h_{i})\theta_{i}^{{p\over
p+1}}(x)\right]\left[{\sum}_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over
p+1}}(x)\right]^{p}\psi^{-p}(\phi(x))$
$\displaystyle=\Phi(x)+[\Phi^{\prime}(x)]^{T}h+{(5p+\varkappa)}\left[{\sum}_{i}\omega_{i}(h_{i})\theta_{i}^{{p\over
p+1}}(x)\right],$ (17)

due to $\psi^{p}(\phi(x))=\phi^{{p\over
p+1}}(x)=\left[\sum_{i}\omega_{i}(x_{i})\theta_{i}^{{p\over
p+1}}(x)\right]^{p}$ by (12d).

60. Now, for $x\in{\mathbf{R}}^{n_{1}+...+n_{K}}$, let us set $\omega[x]=[\omega_{1}(x);...;\omega_{K}(x)]$ and $\|x\|=\theta^{1/2}(\omega[x])$. Clearly, $\|\cdot\|$ indeed is a norm, and the set $\\{x:\|x\|=1\\}$ is nothing but the set $\\{x:\omega[x]\in\overline{{\cal T}}\\}$.

Given $\beta\geq 1$, we say that two nonnegative reals $a,b$ are within factor
$\beta$, if $\beta^{-1}a\leq b\leq\beta a$, or, which is the same,
$\beta^{-1}b\leq a\leq\beta b$. Let us say that two block vectors
$u,v\in{\mathbf{R}}^{n_{1}+...+n_{K}}$ are within factor $\beta$, if
$\sqrt{\omega_{i}(u_{i})}$ and $\sqrt{\omega_{i}(v_{i})}$ are within factor
$\beta$ for every $i$.

Let us make the following observation

> Let $x\in{\mathbf{R}}^{n_{1}+...+n_{K}}$ be a vector with nonzero blocks
> such that $\|x\|=1$. Then there exists vector $z$ with nonzero blocks such
> that $\phi(z)=1/p$ and $z$ is within factor
>
> $\kappa=[pK]^{{1\over 2(p+1)}}$
>
> from $x$. Vice versa, if $z$ is a vector with nonzero blocks such that
> $\phi(z)=1/p$, then there exists vector $x$ with nonzero blocks such that
> $\|x\|=1$ and $x$ is within factor $\kappa$ from $z$.

Indeed, let $x$ be vector with nonzero blocks such that $\|x\|=1$, and let
$t=\omega[x]$, so that $t\in\overline{{\cal T}}$ and $t>0$. Let now $z$ be
with nonzero blocks $z_{i}\in{\mathbf{R}}^{n_{i}}$ such that
$\sqrt{\omega_{i}(z_{i})}=\left[p^{-1}t_{i}^{p+1}[\nabla\theta(t)]_{i}\right]^{{1\over
2(p+1)}}$, so that

$\omega_{i}(z_{i})=t_{i}[p^{-1}[\nabla\theta(t)]_{i}]^{{1\over
p+1}}=\omega_{i}(x_{i})[p^{-1}[\nabla\theta(t)]_{i}]^{{1\over p+1}}.$

Note that $z$ and $x$ are within the factor $\kappa$. We have
$t\in\overline{{\cal T}}$ and
$p\omega_{i}^{p+1}(z_{i})/t_{i}^{p+1}=[\nabla\theta(t)]_{i}$, implying that
$t=t(z)$ by (11). Consequently,

$\phi(z)=\sum_{i}\omega_{i}^{p+1}(z_{i})/t_{i}^{p}=p^{-1}\sum_{i}t_{i}[\nabla\theta(t)]_{i}=p^{-1}\theta(t)=p^{-1},$

as claimed. Vice versa, let $z$ be a vector with nonzero blocks such that
$\phi(z)=1/p$, so that for $t=t(z)\in\overline{{\cal T}}$ and
$\lambda=\lambda(z)\geq 0$ we have

$\displaystyle\omega_{i}^{p+1}(z_{i})$
$\displaystyle=(\lambda/p)t_{i}^{p+1}[\nabla\theta(t)]_{i},$ $\displaystyle
1/p=\phi(z)$
$\displaystyle=\sum\omega_{i}^{p+1}(z_{i})/t_{i}^{p}=(\lambda/p)\sum_{i}t_{i}[\nabla\theta(t)]_{i}=(\lambda/p)\theta(t)=\lambda/p.$

We see that $\lambda=1$, and therefore $\omega_{i}(z_{i})$ are within factor
$\kappa^{2}$ from $t_{i}$. Selecting $x_{i}\in{\mathbf{R}}^{n_{i}}$ such that
$\omega_{i}(x_{i})=t_{i}$, we get vector with nonzero blocks such that
$\|x\|=\theta(t)=1$ and $z$ is within factor $\kappa$ from $x$. $\Box$

Next, $\Phi(x)$ is convex positive outside of the origin homogeneous, of
degree 2, function and thus ${\mathfrak{n}}(x):=\sqrt{\Phi(x)}=\phi^{{1\over
2(p+1)}}(x)$ is a norm. By construction ${\mathfrak{n}}(\cdot)$ is an
“absolute block-norm,” meaning that ${\mathfrak{n}}(x)$ depends solely and
monotonically on the norms $\|x_{i}\|_{i}=\sqrt{\omega_{i}(x_{i})}$ of the
blocks $x_{i}$. As an immediate corollary, if $u,v$ are two vectors with
nonzero blocks which are within some factor from each other, then
${\mathfrak{n}}(u)$ and ${\mathfrak{n}}(v)$ are within the same factor from
each other as well. Given vector $x$ with nonzero blocks and such that
$\|x\|=1$, there exists vector $z$ within factor $\kappa$ from $x$ with
$\phi(z)=1/p$ and thus with ${\mathfrak{n}}(z)=\pi:=p^{-{1\over 2(p+1)}}$, so
that ${\mathfrak{n}}(x)$ is within factor $\kappa$ from $\pi$. Thus,
$\|\cdot\|$ is within factor $\overline{\kappa}=\kappa/\pi$ from
${\mathfrak{n}}(\cdot)$.
7o. Our next observation is as follows:

> Let $t\in\overline{{\cal T}}$ and $h\in{\mathbf{R}}^{n}$. Then
>
> $\sum_{i}\omega_{i}(h_{i})[\nabla\theta(t)]_{i}^{{p\over p+1}}\leq
> K^{{1\over p+1}}\|h\|^{2}.$

Indeed, by (9) we have ${}{[\nabla\theta(t)]_{i}^{{p\over p+1}}}\leq
K^{{1\over p+1}}[\nabla\theta(t)]_{i}$, whence

$\displaystyle\sum_{i}\omega_{i}(h_{i})[\nabla\theta(t)]_{i}^{{p\over p+1}}$
$\displaystyle\leq K^{{1\over p+1}}[\nabla\theta(t)]^{T}\omega[h]\leq
K^{{1\over p+1}}\left[\theta(t+\omega[h])-\theta(t)\right]$ $\displaystyle\leq
K^{{1\over p+1}}[\theta(t)+\theta(\omega[h])-\theta(t)]=K^{{1\over
p+1}}\|h\|^{2}.$

As a consequence, we have

$\sum_{i}\omega_{i}(h_{i})[\nabla\theta(t)]_{i}^{{p\over p+1}}\leq K^{{1\over
p+1}}(\kappa/\pi)^{2}{\mathfrak{n}}^{2}(h)$

Finally, invoking (17), we conclude that for every vector $x$ with nonzero
blocks and all $h$ such that

$\omega_{i}^{1/2}(h_{i})\leq\omega_{i}^{1/2}(x_{i})/[(2p+2)^{2}(1+\varkappa)],\;\;i\leq
K,$

one has

${\mathfrak{n}}^{2}(x+h)\leq{\mathfrak{n}}^{2}(x)+[\nabla{\mathfrak{n}}^{2}(x)]^{T}h+\tfrac{\gamma}{2}{\mathfrak{n}}^{2}(h),\;\;\gamma={2K^{{1\over
p+1}}(\kappa/\pi)^{2}(5p+\varkappa)}.$

We arrive at the following conclusion:

> In the situation in question, for every positive integer $p$ there exists a
> norm ${\mathfrak{n}}(\cdot)$ on ${\mathbf{R}}^{n_{1}+...+n_{K}}$ such that
>
>   * •
>
> $\Phi(x)={\mathfrak{n}}^{2}(x)$ is continuously differentiable with
> Lipschitz continuous gradient and satisfies
>
> $\forall
> x,h\in{\mathbf{R}}^{n}:\Phi(x+h)\leq\Phi(x)+[\nabla\Phi(x)]^{T}h+{[pK]^{{2\over
> p+1}}(5p+\varkappa)}\Phi(h)$
>
>   * •
>
> ${\mathfrak{n}}(\cdot)$ is within the factor $\kappa/\pi=K^{{1\over
> 2(p+1)}}p^{{1\over p+1}}$ from the norm
> $\|x\|=\sqrt{\theta(\omega[x^{2}])}$.
>
>

Setting $p=\lceil\ln(K+1)\rceil$111Here $\lceil a\rceil$ stands for the upper
integer part of $a$—the smallest integer greater or equal to $a$. we complete
the proof of Theorem 2.1. $\Box$

###  A.2 Proof of Proposition 2.1

As is immediately seen, we lose nothing when assuming that the mapping $z\to
Pz$ in (3) is just the natural projection
${\mathbf{R}}^{n}={\mathbf{R}}^{p+q}\ni[u;y]\mapsto u\in{\mathbf{R}}^{p}$. In
this case, factor-norm induced by this projection and the norm $\|\cdot\|$ on
${\mathbf{R}}^{p+q}$:

$\|u\|^{\prime}=\min_{y}\|[u;y]\|.$

Observe that when two norms on ${\mathbf{R}}^{p+q}$ are within some factor
from each other, their factor-norms induced by $P$ are within the same factor
as well. Thus, it suffices to prove Theorem 2.1 in the case when the function
$\Phi(x)=\|x\|^{2}$ if continuously differentiable and such that

$\|\nabla\Phi(x)-\nabla\Phi(x^{\prime})\|_{*}\leq
2\varkappa\|x-x^{\prime}\|\,\,\forall x,x^{\prime};$

where, as always, $\|\cdot\|_{*}$ is the norm conjugate to $\|\cdot\|$. In
this situation the statement of Proposition 2.1 is readily given by the
following

###### Lemma A.2

Let $\Psi(u,y):{\mathbf{R}}^{p+q}$ be a convex function, $\|\cdot\|$ be a norm
on ${\mathbf{R}}^{p+q}$, and let $\|\cdot\|^{\prime}$ be the factor-norm:

$\|h\|^{\prime}=\min_{d\in{\mathbf{R}}^{q}}\|[h;d]\|.$

induced by the natural projection of ${\mathbf{R}}^{p+q}$ onto
${\mathbf{R}}^{p}$. Assume that $\Psi$ is smooth with Lipschitz continuous
with constant $L$ w.r.t. $\|\cdot\|$ gradient, i.e.,

$\|\nabla\Psi(z)-\nabla\Psi(z^{\prime})\|_{*}\leq
L\|z-z^{\prime}\|\quad\forall z,z^{\prime},$

and let the set

$Y(u)={\mathrm{Argmin}}_{y\in{\mathbf{R}}^{q}}\Psi(u,y)$

be nonempty for every $u\in{\mathbf{R}}^{p}$. Then

$\overline{\Psi}(u)=\min_{y}\Psi(u,y)$

is convex and smooth with Lipschitz continuous with constant $L$ w.r.t.
$\|\cdot\|^{\prime}$ gradient on ${\mathbf{R}}^{p}$.

Proof of the lemma. Convexity of $\overline{\Psi}$ is evident. Let
$u\in{\mathbf{R}}^{p}$, and let $y\in Y(u)$. Then for all
$(u^{\prime},y^{\prime})$,

$\Psi(u^{\prime},y^{\prime})\geq\Psi(u,y)+[\Psi^{\prime}_{u}(u,y)]^{T}(u^{\prime}-u)+[\Psi^{\prime}_{y}(u,y)]^{T}(y^{\prime}-y)=\Psi(u,y)+[\Psi^{\prime}_{u}(u,y)]^{T}(u^{\prime}-u),$

that is
$\Psi(u^{\prime},y^{\prime})\geq\overline{\Psi}(u)+[\Psi^{\prime}_{u}(u,y)]^{T}(u^{\prime}-u)$
for all $u^{\prime},y^{\prime}$; hence,

$\overline{\Psi}(u^{\prime})\geq\overline{\Psi}(u)+[\Psi^{\prime}_{u}(u,y)]^{T}(u^{\prime}-u)\,\forall
u^{\prime}\in{\mathbf{R}}^{p}.$ (18)

Denoting for brevity $g=\Psi^{\prime}_{u}(u,y)$, for every
$h\in{\mathbf{R}}^{p}$, selecting $d\in{\mathbf{R}}^{q}$ such that
$\|[h;d]\|=\|h\|^{\prime}$, we get

$\overline{\Psi}(u+h)\leq\Psi(u+h,y+d)\leq\Psi(u,y)+g^{T}h+\tfrac{L}{2}\|[h;d]\|^{2}=\Psi(u,y)+g^{T}h+\tfrac{L}{2}[\|h\|^{\prime}]^{2},$

implying that

$\overline{\Psi}(u)+g^{T}h\leq\overline{\Psi}(u+h)\leq\overline{\Psi}(u)+g^{T}h+{L\over
2}[\|h\|^{\prime}]^{2}$ (19)

with the first inequality given by (18). Consequently, $g$ is the Frechet
derivative of $\overline{\Psi}$ at $u$ and is independent of how $y\in Y(u)$
is selected. Next, $\overline{\Psi}$ is convex on ${\mathbf{R}}^{p}$ and thus
is locally Lipschitz continuous. We claim that
$\overline{\Psi}^{\prime}(\cdot)$ is continuous. Indeed, from local Lipschitz
continuity of $\overline{\Psi}$ it follows that
$\overline{\Psi}^{\prime}(\cdot)$ is locally bounded. Thus, to prove the
continuity of $\overline{\Psi}^{\prime}(\cdot)$, it suffices to lead to the
contradiction the assumption that for some sequence $u_{i}\to u$,
$i\to\infty$, such that $g_{i}=\overline{\Psi}^{\prime}(u_{i})$ converge to
some $e$, one has $e\neq g:=\overline{\Psi}^{\prime}(u)$. But this is evident:
$e$ clearly is a subgradient of $\overline{\Psi}$ at $u$, and since
$\overline{\Psi}$ is differentiable, we get $e=g$, which is a contradiction.

Thus, $\overline{\Psi}$ is continuously differentiable convex function
satisfying (19), implying by Lemma A.1 that the gradient of $\overline{\Psi}$
is Lipschitz continuous, with constant $L$, w.r.t. $\|\cdot\|^{\prime}$.
$\Box$

###  A.3 Proof of Theorem 2.2

Since $\theta$ is $(\overline{\varkappa},\overline{\varsigma})$-regular and
$\|\cdot\|_{i}$ are $({\varkappa}^{\prime},{\varsigma}^{\prime})$-regular,
there exist $\overline{\varkappa}$-smooth norm $\vartheta(\cdot)$ and
${\varkappa}^{\prime}$-smooth norms $\vartheta_{i}$ such that

$\overline{\varsigma}^{-1}\vartheta(\cdot)\leq\theta(\cdot)\leq\overline{\varsigma}\vartheta(\cdot),\,\,(\varsigma^{\prime})^{-1}\vartheta_{i}(\cdot)\leq\|\cdot\|_{i}\leq\varsigma^{\prime}\vartheta_{i}(\cdot),\,i\leq
K.$ (20)

Since $\theta$ is an absolute norm, these relations hold true when replacing
$\vartheta(\cdot)$ with the absolute norm

$\overline{\vartheta}(y)=2^{-K}\sum_{E\in{{\cal E}}_{K}}\vartheta(Ey)$

where ${\cal E}_{K}$ is the multiplicative group of diagonal $K\times K$
matrices with diagonal entries $\pm 1$, and the norm $\overline{\vartheta}$
clearly is $\overline{\varkappa}$-smooth along with $\vartheta$. Thus, we can
assume, on the top of what was just stated, that $\vartheta$ is an absolute
norm.

Next, the function
$\Psi(x_{1},...,x_{K})={\theta^{1/2}(\|x_{1}\|_{1}^{2},...,\|x_{K}\|_{K}^{2})}$
is positively homogeneous of degree 1, and since $\theta$ is an absolute norm,
function $\Psi^{2}(y)$ is monotone on ${\mathbf{R}}^{K}_{+}$. Consequently,
$\Psi^{2}$ is convex, and therefore the Lebesque sets of $\Psi$ are convex;
together with positive homogeneity of degree 1 of the function this implies
that $\Psi(x_{1},...,x_{K})$ is a norm. By the same argument, function
${\vartheta^{1/2}(\vartheta_{1}^{2}(x_{1}),...,\vartheta_{K}^{2}(x_{K}))}$
also is a norm, so that monotonicity and homogeneity of degree 1 of $\theta$
and $\vartheta$ on ${\mathbf{R}}^{K}_{+}$ combines with (20) to imply that for
$\varsigma={\varsigma}^{\prime}\sqrt{\overline{\varsigma}}$ and all
$[x_{1};...;x_{K}]\in{\mathbf{R}}^{n_{1}+...+n_{K}}$

$\varsigma^{-1}{\vartheta^{1/2}(\vartheta_{1}^{2}(x_{1}),...,\vartheta_{K}^{2}(x_{K}))}\leq{\theta^{1/2}(\|x_{1}\|_{1}^{2},...,\|x_{K}\|_{K}^{2})}\leq\varsigma{\vartheta^{1/2}(\vartheta_{1}^{2}(x_{1}),...,\vartheta_{K}^{2}(x_{K}))}.$

To complete the proof of the theorem, all we need is the following statement.

###### Lemma A.3

Let $F(y)=\|y\|_{o}^{2}$ be the square of an absolute norm on
${\mathbf{R}}^{K}$ such that $\nabla F$ be Lipschitz continuous w.r.t.
$\|\cdot\|_{o}$ with Lipschitz constant $L$. Let also
$\phi_{i}(x_{i})=\|x_{i}\|_{i}^{2}$ be squares of norms on
${\mathbf{R}}^{n_{i}}$ such that $\nabla\phi_{i}$ is Lipschitz continuous with
constant $\ell$ with respect to $\|\cdot\|_{i}$, $1\leq i\leq K$. For
$x=[x_{1};...;x_{K}]\in{\mathbf{R}}^{n_{1}}\times...\times{\mathbf{R}}^{n_{k}}$,
we set $\phi(x)=[\phi_{1}(x_{1});...;\phi_{K}(x_{K})]$ and

$f(x)=F^{1/2}(\phi(x)).$

Then $f$ is the square of a norm $\|\cdot\|$ on
${\mathbf{R}}^{n_{1}+...+n_{K}}$ with gradient $\nabla f$ which is Lipschitz
continuous with constant $2L+\ell$ w.r.t. $\|\cdot\|$.

Proof of Lemma A.3. The fact that $f$ is square of a norm is evident—since $F$
is square of an absolute norm the function $F(\phi(x))$ is convex. Besides
this, the function is continuously differentiable, and is of homogeneity
degree 4; as a result, $F^{1/4}(\phi(x))$ is continuous positively
homogeneous, of degree 1, even function with convex level sets and as such is
convex, and therefore is a norm. Note also that $f$ is continuously
differentiable. All we need to prove is that

$\forall(x,h):f(x+h)\leq
f(x)+[f^{\prime}(x)]^{T}h+\mbox{\small$\frac{1}{2}$}[2L+\ell]f(h).$

Assume for the sake of simplicity that $F$ and $\phi_{i}$ are twice
continuously differentiable outside of the respective origins (we can arrive
at this situation by suitable approximation, see Lemma A.5 below). Invoking
Lemma A.4, it suffices to show that for every $x$ with nonzero $x_{i}$’s and
every $h$ it holds

$D^{2}f(x)[h,h]\leq[2L+\ell]f(h).$ (21)

Let us put

${\cal D}=\\{x\in{\mathbf{R}}^{n_{1}+...+n_{K}}:x_{i}\neq 0,i\leq
K\\},\;\;\;{\cal D}_{o}=\\{y\in{\mathbf{R}}^{K}:y\neq 0\\}.$

$F$ is twice continuously differentiable on ${\cal D}_{o}$ and

$\displaystyle 0$ $\displaystyle\leq D^{2}F(y)[d,d]\leq
LF(d)\;\;\forall(y\in{\cal D}_{o},d\in{\mathbf{R}}^{K}),$ $\displaystyle(a)$
$\displaystyle 0$ $\displaystyle\leq
D^{2}\phi(x)[h,h]\leq\ell\phi(h)\;\;\forall(x\in{\cal
D},h\in{\mathbf{R}}^{n_{1}+...+n_{K}}).$ $\displaystyle(b)$

Besides this, taking into account that $F$ and $\phi_{i}$ are squares of norms
continuously differentiable outside of the origin, we have

$\displaystyle\hbox{abs}[D\phi(x)[h]]$ $\displaystyle\leq
2[\phi(x)]^{1/2}\cdot[\phi(h)]^{1/2},$ $\displaystyle(c)$
$\displaystyle|DF(y)[d]|$ $\displaystyle\leq 2\sqrt{F(y)}\sqrt{F(d)},$
$\displaystyle(d)$ $\displaystyle y\geq 0$ $\displaystyle\Rightarrow
DF(y)[h]\hbox{\ is monotone in $h$}$ $\displaystyle(e)$

where for a nonnegative vector $z$ and $\alpha>0$, $[z]^{\alpha}$ stands for
the vector comprised of $\alpha$-th degrees of the entries of $z$, and $u\cdot
v$ is coordinatewise product of two vectors; $(e)$ stems from the fact that
$F$ is the square of an absolute norm.

Now, let $x\in{\cal D}$ and let $y=\phi(x)$, so that $y\in{\cal D}_{o}$. We
have $f(x)=F^{1/2}(\phi(x))$ with

$Df(x)[h]={1\over 2F^{1/2}(\phi(x))}DF(\phi(x))[D\phi(x)[h]]$

and

$\displaystyle D^{2}f(x)[h,h]$ $\displaystyle={1\over
2F^{1/2}(\phi(x))}\left[D^{2}F(\phi(x))[D\phi(x)[h],D\phi(x)[h]]+DF(\phi(x))[D^{2}\phi(x)[h,h]]\right]$
$\displaystyle\quad-{1\over 4F^{3/2}(\phi(x))}(DF(\phi(x))[D\phi(x)[h]])^{2}$
$\displaystyle\leq{1\over
2F^{1/2}(y)}\left[D^{2}F(y)[D\phi(x)[h],D\phi(x)[h]]+DF(y)[D^{2}\phi(x)[h,h]]\right].$
(22)

By homogeneity, it suffices to verify (21) for $x\in{\cal X}$ such that
$F(\phi(x))=1$. In this case we have

$\begin{array}[]{l}Df(x)[h]={1\over 2}DF(y)[D\phi(x)[h]]\\\
D^{2}f(x)[h,h]\leq{1\over
2}\left[D^{2}F(y)[D\phi(x)[h],D\phi(x)[h]]+DF(y)[D^{2}\phi(x)[h,h]]\right]\\\
\end{array}$

Putting $d=D^{2}\phi(x)[h,h]$, we get by $(d)$,

$\displaystyle DF(y)[D^{2}\phi(x)[h,h]]$ $\displaystyle\leq
2\sqrt{F(D^{2}\phi(x)[h,h])}\leq 2\ell\sqrt{F(\phi(h))}=2\ell f{(h)}$

by $(b)$ and due to homogeneity of degree 2 of $F$ and monotonicity of
$F(\cdot)$ on ${\mathbf{R}}^{K}_{+}$. Besides this,

$\displaystyle D^{2}F(y)[D\phi(x)[h],[D\phi(x)[h]]\leq LF(D\phi(x)[h])\hbox{\
[by $(a)$]}$ $\displaystyle=LF(\hbox{abs}[D\phi(x)[h]])\hbox{\ [since
$F(\cdot)$ is the square of an absolute norm]}$ $\displaystyle\leq
LF(2[\phi(x)]^{1/2}\cdot[\phi(h)]^{1/2})\hbox{\ [by $(c)$ and due to
monotonicity of $F(\cdot)$ on ${\mathbf{R}}^{K}_{+}$]}$ $\displaystyle\leq
LF(\lambda\phi(x)+\lambda^{-1}\phi(h))\,\,\forall\lambda>0\hbox{\ [since $F$
is monotone on ${\mathbf{R}}^{K}_{+}$]}$ $\displaystyle{\leq}L[{\lambda
F^{1/2}(\phi(x))+\lambda^{-1}F^{1/2}(\phi(h))}]^{2}\;\;\forall\lambda>0\hbox{\
[since ${F^{1/2}}(\cdot)$ is a norm on ${\mathbf{R}}^{K}$],}$

whence

$\displaystyle D^{2}F(y)[D\phi(x)[h],D\phi(x)[h]]$ $\displaystyle\leq
L\left[\inf_{\lambda>0}[{\lambda
F^{1/2}(\phi(x))+\lambda^{-1}F^{1/2}(\phi(h))}]\right]^{2}$
$\displaystyle=4L{F^{1/2}(\phi(x))F^{1/2}(\phi(h))}=4Lf{(h).}$

The bottom line is that when $x\in{\cal D}$ and $F(\phi(x))=1$, we have by
(22)

$\displaystyle D^{2}f(x)[h,h]$
$\displaystyle\leq\mbox{\small$\frac{1}{2}$}\left[D^{2}F(y)[D\phi(x)[h],D\phi(x)[h]]+DF(y)[D^{2}\phi(x)[h,h]]\right]$
$\displaystyle\leq\mbox{\small$\frac{1}{2}$}[4Lf{(h)}+2\ell
f{(h)}]=[2L+\ell]f{(h)},$

as required in (21). $\Box$

###  A.4 Proof of Theorem 3.1

(i): By Theorem 2.1 as applied to the (1,1)-regular norms
$\|\cdot\|_{i}=\|\cdot\|_{2}$ on ${\mathbf{R}}^{n}$, the norm

$\|[x_{1};...;x_{K}]\|:=\theta^{1/2}(\|x_{1}\|_{2}^{2},...,\|x_{K}\|_{2}^{2})$

on ${\mathbf{R}}^{nK}$ is $(O(1)\ln(K+1),O(1))$-regular. With ${\cal X}$ given
by (2), the norm

$\|x\|_{+}:=\theta^{1/2}(\|T_{1}^{1/2}x\|_{2}^{2},...,\|T_{k}^{1/2}x\|_{2}^{2})$

is the superposition of $\|\cdot\|$ and linear embedding
$x\mapsto[T_{1}^{1/2}x;...;T_{k}^{1/2}x]$ and therefore is regular with the
same parameters as $\|\cdot\|$, see Section 2.1. Finally,
$\|\cdot\|_{\overline{{\cal X}}}$ is the factor-norm of $\|\cdot\|_{+}$, and
passing from a norm to its factor-norm preserves regularity parameters by
Proposition 2.1.

(ii): The norms $\|\cdot\|_{i}=\|\cdot\|_{2,2}$ on ${\mathbf{S}}^{d_{i}}$ are
$(O(1)\ln(d_{i}+1),O(1))$-regular, see “basic facts” at the end of in Section
2.1. By Theorem 2.1) as applied to these norms, the norm

$\|[y_{1};...;y_{K}]\|:=\theta^{1/2}(\|y_{1}\|_{2,2}^{2},...,\|y_{K}\|_{2,2}^{2})$

on ${\mathbf{S}}^{d_{1}}\times...\times{\mathbf{S}}^{d_{K}}$ is
$(O(1)[\ln(K+1)+\max_{i\leq K}\ln(d_{i})],O(1))$-regular. Similarly to the
case of $(i)$, with ${\cal X}$ given by (5), the norm $\|\cdot\|_{+}$ which is
the superposition of $\|\cdot\|$ and linear embedding
$x\mapsto(S_{1}(x)_{,}...,S_{K}(x))$ is regular with the same parameters as
$\|\cdot\|$, and these parameters are inherited by the factor-norm
$\|\cdot\|_{\overline{{\cal X}}}$. $\Box$

###  A.5 Technical lemmas

###### Lemma A.4

Let $\|\cdot\|$ be a norm on ${\mathbf{R}}^{n}$ with conjugate norm
$\|\cdot\|_{*}$. Let also $\alpha\geq 0$, let $V$ be a nonempty open convex
domain in ${\mathbf{R}}^{n}$ and $f:\,V\to{\mathbf{R}}$ be a continuously
differentiable convex function. The following 3 properties of $f$ are
equivalent:

  1. (1)

$h^{T}[\nabla f(x+h)-\nabla f(x)]\leq\alpha\|h\|^{2}$ $\forall x,x+h\in V$;

  2. (2)

$\|\nabla f(x+h)-\nabla f(x)\|_{*}\leq\alpha\|h\|$ $\forall x,x+h\in V$;

  3. (3)

$f(x+h)\leq f(x)+h^{T}\nabla f(x)+{\alpha\over 2}\|h\|^{2}$ $\forall x,x+h\in
V$.

Proof. Let $V_{o}$ be an open convex domain such that for some
$\epsilon[V_{o}]>0$ the $\|\cdot\|_{2}$-norm $\epsilon$-neighbourhood of
$V_{o}$ is contained in $V$. It suffices to demonstrate that the properties
(1o)–(3o) obtained from respective properties (1)–(3) by replacing the
requirement $x,x+h\in V$ with $x,x+h\in V_{o}$ are equivalent to each other,
whatever be $V_{o}$ of the indicated type. Let us fix such a $V_{o}$ and note
that when $f$ satisfies property ($i$), $i=1,2,3$, then property ($i_{o}$)
holds true for the restrictions onto $V_{o}$ of all shifts $f(\cdot-u)$ of
$f(\cdot)$ with $\|u\|_{2}<\epsilon[V_{o}]$, same as for convex combinations
of these shifts. Selecting a C∞ nonnegative kernel $\delta(\cdot)$ with unit
integral which vanishes outside of the $\epsilon[V_{o}]/2$-neighbourhood of
the origin and setting

$f_{\delta}(x)=\int f(x-u)\delta(u)du:V_{o}\to{\mathbf{R}},$

we obtain a C∞ convex function on $V_{o}$ which possesses properties
($i_{o}$), $i=1,2,3$, provided that $f$ possesses property $(i)$. When
$\delta\to+0$, functions $f_{\delta}$ converge to $f$ uniformly on compact
subsets of $V_{o}$ along with their gradients. Therefore, when $f_{\delta}$
possesses one of the properties $(i_{o})$, so does $f$, and vice versa. The
bottom line is that all we need is to show the equivalence $(1_{o})$ –
$(3_{o})$ in the case when $f$ is a convex C∞ function on $V_{o}$. This is
immediate: when $f$ is convex and smooth, every one of the three properties in
question is equivalent to

$u^{T}\nabla^{2}f(x)v\leq\alpha\|u\|\|v\|\;\;\forall(x\in
V_{o},u,v\in{\mathbf{R}}^{n}).$

Indeed,

$(1_{o})\Leftrightarrow(*_{o})$: When $f$ obeys $(1_{o})$, $x\in V_{o}$ and
$h\in{\mathbf{R}}^{n}$, we clearly have

$h^{T}\nabla^{2}f(x)h=\lim_{t\to+0}t^{-1}h^{T}[\nabla f(x+th)-\nabla
f(x)]=\lim_{t\to+0}t^{-2}\underbrace{[th]^{T}[\nabla f(x+th)-\nabla
f(x)]}_{\leq\alpha\|th\|^{2}}\leq\alpha\|h\|^{2},$

whence, due to the fact that $\nabla^{2}f(x)$ is symmetric positive
semidefinite,

$u^{T}\nabla^{2}f(x)v\leq[u^{T}\nabla^{2}f(x)u]^{1/2}[v^{T}\nabla^{2}f(x)v]^{1/2}\leq\alpha\|u\|\|v\|,$

so that $(*_{o})$ holds. Vice versa, assuming that $f$ obeys $(*_{o})$, for
$x,x+h\in V_{o}$ we have

$h^{T}[\nabla f(x+h)-\nabla
f(x)]=\int_{0}^{1}h^{T}\nabla^{2}f(x+th)hdt\leq\int_{0}^{1}\alpha\|h\|^{2}dt=\alpha\|h\|^{2}.$

as required in $(i_{o})$.

$(2_{o})\Leftrightarrow(*_{o})$: Assuming that $(2_{o})$ holds, for $x\in
V_{o}$ and $u,v\in{\mathbf{R}}^{n}$ we have

$u^{T}\nabla^{2}f(x)v=\lim_{t\to+0}t^{-1}u^{T}[\nabla f(x+tv)-\nabla
f(x)]\leq\varlimsup_{t\to+0}t^{-1}\|u\|\|\nabla f(x+tv)-\nabla f(x)\|_{*},$

and the latter limit is $\leq\alpha\|u\|\|v\|$ by $(2_{o})$. Vice versa, if
$f$ obeys $(*_{o})$, and $x\in V_{o}$, $x+h\in V_{o}$, we have

$\displaystyle\|\nabla f(x+h)-\nabla f(x)\|_{*}$
$\displaystyle=\max_{u:\|u\|\leq 1}u^{T}[\nabla f(x+h)-\nabla
f(x)]=\max_{u:\|u\|\leq 1}\int_{0}^{1}u^{T}\nabla^{2}f(x+th)hdt$
$\displaystyle\leq\max_{u:\|u\|\leq
1}\int_{0}^{1}\alpha\|u\|\|h\|dt=\alpha\|h\|,$

as required in $(2_{0})$.

$(3_{o})\Leftrightarrow(*_{o})$: $(*_{o})$ clearly implies $(3_{o})$. On the
other hand, when $x\in V_{o}$ and $h\in{\mathbf{R}}^{n}$, for properly
selected $C=C(x,h)<\infty$ and $\overline{t}={\overline{t}(x,h)}>0$ we have

$0\leq t\leq\overline{t}\Rightarrow f(x+th)\geq f(x)+th^{T}\nabla
f(x)+{t^{2}\over 2}h^{T}\nabla^{2}f(x)h-Ct^{3}.$

It follows that when $f$ obeys $(3_{o})$, we have

$f(x)+th^{T}\nabla f(x)+{t^{2}\over 2}h^{T}\nabla^{2}f(x)h-Ct^{3}\leq
f(x)+th^{T}\nabla f(x)+{\alpha\over 2}\|th\|^{2}$

for $0\leq t\leq\overline{t}$, implying that
$h^{T}\nabla^{2}f(x)h\leq\alpha\|h\|^{2}$, whence, $(*_{o})$ holds true.
$\Box$

###### Lemma A.5

Let $f(\cdot):{\mathbf{R}}^{n}\to{\mathbf{R}}_{+}$ be a norm such that the
function $F(x)=f^{2}(x)$ is continuously differentiable and for certain
$\alpha>0$ satisfies the relation

$h^{T}[\nabla F(x+h)-\nabla F(x)]\leq\alpha F(h)\,\,\forall
x,h\in{\mathbf{R}}^{n}.$

Then

(i) For every $\epsilon\in(0,1)$ there exists a norm $f^{\epsilon}(\cdot)$ on
${\mathbf{R}}^{n}$ such that

$(1-\epsilon)f(\cdot)\leq f^{\epsilon}(\cdot)\leq(1+\epsilon)f(\cdot)$

and the function $F^{\epsilon}(x):=[f^{\epsilon}(x)]^{2}$ is C∞ outside of the
origin and satisfies the relations

$\displaystyle h^{T}[\nabla F^{\epsilon}(x+h)-\nabla
F^{\epsilon}(x)]\leq(1+\epsilon)\alpha F^{\epsilon}(h)\quad$
$\displaystyle\forall(x,h\in{\mathbf{R}}^{n}),$ $\displaystyle 0\leq
D^{2}F^{\epsilon}(x)[h,h]\leq\alpha F^{\epsilon}(h)\quad$
$\displaystyle\forall(x\neq 0,h).$

Moreover, as $\epsilon\to+0$, functions $F^{\epsilon}$ converge to $F$
uniformly on compact subsets of ${\mathbf{R}}^{n}$ along with their gradients.

(ii) If, in addition, $f$ is an absolute norm, $f^{\epsilon}$ in (i) can be
made absolute norm as well.

Proof. (i) Let $S=\\{x\in{\mathbf{R}}^{n}:\|x\|_{2}=1\\}$ and let $SO_{n}$ be
the group of orthogonal $n\times n$ matrices with determinant 1, both sets
equipped with the natural structures of C∞ manifolds. Let also $\mu(\cdot)$ be
the invariant measure on $SO_{n}$. In the sequel, for $g\in SO_{n}$ and
function $\phi(\cdot)$ on ${\mathbf{R}}^{n}$, $\phi_{g}(\cdot)$ is given by
$\phi_{g}(x)=\phi(gx)$.
1o. Observe that for every $\epsilon\in(0,1)$ there exists
$\delta(\epsilon)>0$ such that

$\|g-I_{n}\|_{2,2}\leq\delta<\delta(\epsilon)\;\Rightarrow\;(1-\epsilon)f(x)\leq
f_{g}(x)\leq(1+\epsilon)f(x)\;\forall x$

where, same as above, $\|\cdot\|_{2,2}$ is the spectral norm. Indeed, for
properly selected $C<\infty$ and any linear mapping $x\mapsto
Hx:{\mathbf{R}}^{n}\to{\mathbf{R}}^{n}$ it holds

$\|H\|_{f}\leq C\|H\|_{2,2}$

where $\|\cdot\|_{f}$ is the norm induced by the norm $f(\cdot)$ on
${\mathbf{R}}^{n}$. Consequently, for $g\in SO_{n}$, by the triangle
inequality, one has for all $x$:

$\displaystyle f(gx)$ $\displaystyle=f([g-I_{n}]x+x)\leq
f(x)+\|g-I_{n}\|_{f}f(x)\leq(1+C\|g-I_{n}\|_{2,2})f(x),$ $\displaystyle f(gx)$
$\displaystyle=f([g-I_{n}]x+x)\geq
f(x)-\|g-I_{n}\|_{f}f(x)\geq(1-C\|g-I_{n}\|_{2,2})f(x),$

so that it suffices to put $\delta(\epsilon)=\epsilon/C$.
2o. Given $\delta>0$, let $\theta(\cdot)$ be a nonnegative C∞ function on
$SO_{n}$ such that $\theta(g)=0$ for $\|g-I_{n}\|_{2,2}\geq\delta$ and
$\int_{SO_{n}}\theta_{\delta}(g)\mu(dg)=1$, and let

$F^{(\delta)}(x)=\int_{SO_{n}}F(gx)\theta_{\delta}(g)\mu(dg).$

Observe that function $F^{(\delta)}$ is continuous, homogeneous of degree 2
and positive outside of the origin, so that function
$f^{(\delta)}(x)=\sqrt{F^{(\delta)}(x)}$ is positive outside of the origin and
satisfies $f^{(\delta)}(\lambda x)=|\lambda|f(x)$. Besides this,

$f^{(\delta)}(x)=\sqrt{\int_{SO_{n}}f_{g}^{2}(x)\theta_{\delta}(g)\mu(dg)},$

so that $f^{(\delta)}$ is convex, since the functional
$\Phi[\phi]=\sqrt{\int_{SO_{n}}\phi^{2}(g)\theta_{\delta}(g)\mu(dg)}$ on the
space of continuous real-valued functions on $SO_{n}$ is convex and satisfies
$\Phi[\psi]\geq\Phi[\phi]$ whenever $\psi(\cdot)\geq\phi(\cdot)\geq 0$. The
bottom line is that $f^{(\delta)}$ is a norm on ${\mathbf{R}}^{n}$. In
addition, taking into account that $\theta_{\delta}(g)\geq 0$,
$\int_{SO_{n}}\theta_{\delta}(g)\mu(dg)=1$, and $\theta_{\delta}(g)=0$ when
$\|g-I_{n}\|_{2,2}\geq\delta$, by 1o we conclude that

$\forall\epsilon\in(0,1),\;0<\delta<\delta(\epsilon):\;(1-\epsilon)f(\cdot)\leq
f^{(\delta)}(\cdot)\leq(1+\epsilon)f(\cdot).$ (23)

3o. Since $F$ is continuously differentiable, we have

$\forall(x,h):\nabla F^{(\delta)}(x)=\int_{SO_{n}}g^{T}\nabla
F(gx)\theta_{\delta}(g)\mu(dg),$

whence

$\displaystyle h^{T}[\nabla F^{(\delta)}(x+h)-\nabla F^{(\delta)}(x)]$
$\displaystyle=\int_{SO_{n}}[gh]^{T}[\nabla F(gx+gh)-\nabla
F(gx)]\theta_{\delta}(g)\mu(dg)$ $\displaystyle\leq\int_{SO_{n}}\alpha
F(gh)\theta_{\delta}(g)\mu(dg),$

that is,

$\forall x,h:\;h^{T}[\nabla F^{(\delta)}(x+h)-\nabla
F^{(\delta)}(x)]\leq\alpha F^{(\delta)}(h).$

4o. Our goal is to prove that $F^{(\delta)}$ is C∞ outside of the origin.

Let $e_{1},...,e_{n}$ be the canonic basis orths of ${\mathbf{R}}^{n}$. For
$u\in S$, let

$S(u)=\\{v\in S:v^{T}u>0\\}=\\{v\in S:\|v-u\|_{2}<\sqrt{2}\\}.$

We claim that there exists mapping $\chi:S(e_{1})\to SO_{n}$ such that
$\chi(e_{1})=I_{n}$ and $\chi(x)e_{1}=x$ for all $x\in S(e_{1})$. Indeed, when
$x\in S(e_{1})$, vectors $x,e_{2},e_{3},...,e_{n}$ are linearly independent.
When applying to this sequence the Gram-Schmidt orthogonalization process, we
obtain an orthonormal system $e_{1}(x)\equiv x,e_{2}(x),...,e_{n}(x)$ with
vector-functions $e_{i}(x)$ which are C∞ on $S(e_{1})$, and we can set
$\chi(x)=[e_{1}(x),e_{2}(x),...,e_{n}(x)]$.

We are now ready to show that $F^{(\delta)}$ is C∞ outside of the origin when
$\epsilon\in(0,1)$ and $0<\delta<\delta(\epsilon)$. Since $F^{(\delta)}$ is
homogeneous of degree 2 and positive outside of the origin, it suffices to
verify that the restriction of $F^{(\delta)}$ onto the sphere $S$ is C∞. To
justify the latter claim, let $\delta>0$, $\bar{x}\in S$, and let $\bar{g}\in
SO_{n}$ be such that $\bar{g}e_{1}=\bar{x}$. Then for all $x\in S(\bar{x})$

$\bar{g}^{-1}x\in
S(e_{1})\Rightarrow\bar{g}^{-1}x=\chi(\bar{g}^{-1}x)e_{1}\Rightarrow
x=\bar{g}\chi(\bar{g}^{-1}x)e_{1},$

whence for such $x$ and $h=g\bar{g}\chi(\bar{g}^{-1}x)$ we get

$F^{(\delta)}(x)=\int_{SO_{n}}F(g\bar{g}\chi(\bar{g}^{-1}x)e_{1})\theta_{\delta}(g)\mu(dg)\\\
=\int_{SO_{n}}F(he_{1})\underbrace{\theta_{\delta}(h\chi^{-1}(\bar{g}^{-1}x)\bar{g}^{-1})}_{\theta_{\bar{x}}(x,h))}\mu(dh)$

due to invariance of $\mu(\cdot)$. Because $\theta(\cdot)$ is C∞ on $SO_{n}$
and $\chi(z)$ is C∞ in $S(e_{1})$, function $\theta_{\bar{x}}(\cdot,h)$ is C∞
in the first argument in the neighbourhood $S(\bar{x})$ with derivatives which
are continuous in $x$ and $h$, implying that $F^{(\delta)}(x)$ is C∞ on $S$.
5o. The bottom line of the above is that for every $\epsilon\in(0,1)$, for
properly selected $\delta(\epsilon)>0$ and all $\delta\in(0,\delta(\epsilon))$
function $F^{(\delta)}(\cdot)$ is the square of some norm
$f^{(\delta)}(\cdot)$ satisfying

$(1-\epsilon)f(\cdot)\leq f^{(\delta)}(\cdot)\leq(1+\epsilon)f(\cdot),$

$F^{(\delta)}$ is C∞ outside of the origin, and

$\forall x,h:h^{T}[\nabla F^{(\delta)}(x+h)-\nabla F^{(\delta)}(x)]\leq\alpha
F^{(\delta)}(h).$ (24)

In particular, when $x\neq 0$, we have

$0\leq h^{T}[\nabla F^{(\delta)}(x+th)-\nabla F^{(\delta)}(x)]\leq
t^{-1}\alpha F^{(\delta)}(th)=t\alpha F^{(\delta)}(h),$

implying that

$D^{2}F^{(\delta)}(x)[h,h]=\lim_{t\to+0}t^{-1}h^{T}[\nabla
F^{(\delta)}(x+th)-\nabla F^{(\delta)}(x)]\leq\alpha
F^{(\delta)}(h)\,\forall(x\neq 0,h).$ (25)

Thus, given $\epsilon\in(0,1)$, the function
$F^{\epsilon}:=F^{(\delta(\epsilon)/2)}$ satisfies all requirements of (i).
(i) is proved.
6o. It remains to prove (ii). To this end, assume that $f$ is an absolute
norm. Let ${\cal E}_{n}$ be the multiplicative group comprised by the $2^{n}$
diagonal matrices with diagonal entries $\pm 1$. Given $\epsilon\in(0,1)$ and
assuming that $\delta\in(0,\delta(\epsilon))$, let us set

$F^{\delta,E}(x):=F^{(\delta)}(Ex)=[f^{(\delta)}(Ex)]^{2},\,E\in{\cal E}_{n}.$

Functions $F^{\delta,E}(x)$ are C∞ outside of the origin functions, while due
to (24) and (25) we have

$\displaystyle\forall x,h:\;\;h^{T}[\nabla F^{\delta,E}(x+h)-\nabla
F^{\delta,E}(x)]$ $\displaystyle\leq\alpha F^{\delta,E}(h),$
$\displaystyle\forall x\neq 0,h:\;\;D^{2}F^{\delta,E}(x)[h,h]$
$\displaystyle\leq\alpha F^{\delta,E}(h).$

We conclude that the function

$\overline{F}^{\delta}(x)=2^{-n}\sum_{E\in{\cal E}_{n}}F^{\delta,E}(x)$

is C∞ outside of the origin and satisfies

$\displaystyle\forall
x,h:\;\;h^{T}[\nabla\overline{F}^{\delta}(x+h)-\nabla\overline{F}^{\delta}(x)]$
$\displaystyle\leq\alpha\overline{F}^{\delta}(h),$ $\displaystyle\forall x\neq
0,h:\;\;D^{2}\overline{F}^{\delta}(x)[h,h]$
$\displaystyle\leq\alpha\overline{F}^{\delta}(h).$

Besides this,

$\left(\overline{F}^{\delta}(x)\right)^{1/2}=\left(2^{-n}\sum_{E\in{\cal
E}_{n}}[f^{(\delta)}(Ex)]^{2}\right)^{1/2},$

so that $\left(\overline{F}^{\delta}(x)\right)^{1/2}$ is a norm along with the
functions $f^{(\delta)}(Ex)$. Furthermore, by construction,
$\overline{F}^{\delta}(Ex)=\overline{F}^{\delta}(x)$ for all $x$, so that
$\left(\overline{F}^{\delta}(x)\right)^{1/2}$ is an absolute norm. Finally, by
(23) and due to $0<\delta<\delta(\epsilon)$ we have

$(1-\epsilon)^{2}F(\cdot)\leq[f^{\delta}(\cdot)]^{2}\leq(1+\epsilon)^{2}F(\cdot),$

and because $f(\cdot)$ is an absolute norm, it follows that

$(1-\epsilon)^{2}F(x)\leq[f^{{\delta}}(Ex)]^{2}\leq(1+\epsilon)^{2}F(x)\;\;\forall
x,\forall E\in{\cal E}_{n}.$

Hence,

$(1-\epsilon)^{2}F(\cdot)\leq\overline{F}^{\delta}(\cdot)\leq(1+\epsilon)^{2}F(\cdot),$

and thus

$(1-\epsilon)f(\cdot)\leq\left({\overline{F}^{\delta}(\cdot)}\right)^{1/2}\leq(1+\epsilon)f(\cdot).$

The bottom line is that to meet all requirements of (ii), it suffices to set
$F^{\epsilon}=\overline{F}^{\delta(\epsilon)/2}$.
7o. Finally, we can ensure that $\delta(\epsilon)\to+0$ as $\epsilon\to+0$,
and in this case, as is immediately seen from the above, functions
$F^{\epsilon}$ converge, along with their gradients, to $F$ uniformly on
bounded subsets of ${\mathbf{R}}^{n}$ as $\epsilon\to+0$. $\Box$

## References

  * [1] Beck, A. (2017) First-Order Methods in Optimization. – MOS-SIAM Series on Optimization, SIAM.
  * [2] Ben-Tal, A., Nemirovski, A. Lectures on Modern Convex Optimization. https://www2.isye.gatech.edu/~nemirovs/LMCOLN2022Fall.pdf
  * [3] Ben-Tal, A. Nemirovski, A. On solving large-scale polynomial convex problems by randomized first-order algorithms. - Mathematics of Operations Research 40:2 (2015), 474–494.
  * [4] Juditsky, A., Kotsalis, G., Nemirovski, A. (2021). Tight Computationally Efficient Approximation of Matrix Norms with Applications. arXiv:2110.04389 https://arxiv.org/pdf/2110.04389.pdf
  * [5] Judistky, A., Nemirovski, A. (2008) Large Deviations of Vector-Valued Martingales in 2-Smooth Normed Spaces. arXiv:0809.0813 https://arxiv.org/pdf/0809.0813.pdf
  * [6] Juditsky, A., Nemirovski, A. (2020). Statistical Inference via Convex Optimization. In Statistical Inference via Convex Optimization. Princeton University Press.
  * [7] Lan, G. (2020) First-order and stochastic optimization methods for machine learning, Springer.
  * [8] Ledoux, M., Talagrand, M. (2002) Probabilities in Banach Spaces. Series of Modern Surveys in Mathematics, v. 23, Springer.
  * [9] Milman, V., Schechtman, G. (2001) Asymptotic Theory of Finite Dimensional Normed Spaces, With an Appendix by M. Gromov “Isoperimetric Inequalities in Riemannian Manifolds”—Lecture Notes in Mathematics v. 1200, Springer.
  * [10] Nesterov, Yu., Nemirovski, A. On first-order algorithms for $\ell_{1}$/nuclear norm minimization. - Acta Numerica 22 (2013), 509-575.
  * [11] Nesterov, Yu. (2018) Lectures on Convex Optimization. Springer Optimization and Its Applications, v. 137, Springer.
  * [12] Pinelis, I. (1992). An approach to inequalities for the distributions of infinite-dimensional martingales. In Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference, 128–134. Birkhäuser, Boston, MA.
  * [13] Pinelis, I. (1994). Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability, 1679-1706.
  * [14] Pinelis, I. (2015). Rosenthal-type inequalities for martingales in 2-smooth Banach spaces. Theory of Probability & Its Applications, 59(4), 699-706.
  * [15] Pisier, G. (1975). Martingales with values in uniformly convex spaces. Israel Journal of Mathematics, 20(3), 326-350.