constant $r^{t}_{\rho}$ and a sum
$\sum^{k}_{k^{\prime}=1}{z}^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{x}})$
of linear functions of $\boldsymbol{{y}}$. Such minimum is thus a concave
function of $\boldsymbol{{y}}$. Therefore, the gain in Eq. (16) is a weighted
sum with positive weights of concave functions in $\boldsymbol{{y}}$, which is
concave. ∎

###  E-B Strong convexity of the Mirror Map

######  Lemma E.2.

The global mirror map
$\Phi(\boldsymbol{{y}})=\sum_{v\in\mathcal{V}}\Phi(\boldsymbol{{y}}^{v})=\sum_{v\in\mathcal{V}}\sum_{m\in\mathcal{M}}s^{v}_{m}y^{v}_{m}\log(y^{v}_{m})$
defined over the domain
$\mathcal{D}=\mathbb{R}_{>0}^{|\mathcal{M}|\times|\mathcal{V}|}$ is
$\theta$-strongly convex w.r.t. the norm
$\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$ over
$\mathcal{Y}\cap\mathcal{D}$, where

$\displaystyle\theta$
$\displaystyle\triangleq\frac{1}{s_{\max}|\mathcal{V}||\mathcal{M}|},$ (85)
$\displaystyle\textstyle\norm{\boldsymbol{{y}}}_{l_{1}(\boldsymbol{{s}})}$
$\displaystyle\triangleq\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}{s}^{v}_{m}|y^{v}_{m}|\quad\text{(weighted
$l_{1}$ norm)},$ (86)

and
$s_{\max}\triangleq\left\\{s^{v}_{m}:(v,m)\in\mathcal{V}\times\mathcal{M}\right\\}$
is the maximum model size. In words, this means that the mirror map $\Phi$’s
growth is lower bounded by a quadratic with curvature
$\frac{1}{s_{\max}|\mathcal{V}||\mathcal{M}|}$.

###### Proof.

We extend the proof of the strong convexity of the negative entropy w.r.t. to
the $l_{1}$ norm over the simplex given in [69, Lemma 16]. The map
$\Phi(\boldsymbol{{y}})$ is differentiable over $\mathcal{Y}\cap\mathcal{D}$,
so a sufficient (and also necessary) condition for $\Phi(\boldsymbol{{y}})$ to
be $\theta$-strongly convex w.r.t.
$\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$ is:

$\displaystyle(\nabla\Phi(\boldsymbol{{y^{\prime}}})-\nabla\Phi(\boldsymbol{{y}}))^{T}(\boldsymbol{{y^{\prime}}}-\boldsymbol{{y}})\geq\theta\norm{\boldsymbol{{y^{\prime}}}-\boldsymbol{{y}}}^{2}_{l_{1}(\boldsymbol{{s}})},\quad\forall\boldsymbol{{y^{\prime}}},\boldsymbol{{y}}\in\mathcal{Y}\cap\mathcal{D}.$
(87)

We have

$\displaystyle(\nabla\Phi(\boldsymbol{{y^{\prime}}})-\nabla\Phi(\boldsymbol{{y}}))^{T}(\boldsymbol{{y^{\prime}}}-\boldsymbol{{y}})=\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}s^{v}_{m}(\log({y^{\prime}}^{v}_{m})-\log({y}^{v}_{m}))({y^{\prime}}^{v}_{m}-y^{v}_{m}).$
(88)

Take $\mu^{v}_{m}\triangleq
s^{v}_{m}(\log({y^{\prime}}^{v}_{m})-\log(y^{v}_{m}))({y^{\prime}}^{v}_{m}-y^{v}_{m})$,
and note that $\mu^{v}_{m}\geq 0$ (because $\log$ is an increasing function).

$\displaystyle\norm{\boldsymbol{{y^{\prime}}}-\boldsymbol{{y}}}^{2}_{l_{1}(\boldsymbol{{s}})}$
$\displaystyle=\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}s^{v}_{m}|{y^{\prime}}^{v}_{m}-y^{v}_{m}|\right)^{2}=\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}\sqrt{\mu^{v}_{m}}\frac{s^{v}_{m}|{y^{\prime}}^{v}_{m}-y^{v}_{m}|}{\sqrt{\mu^{v}_{m}}}\right)^{2}$
$\displaystyle\leq\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}\mu^{v}_{m}\right)\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}(s^{v}_{m})^{2}\frac{({y^{\prime}}^{v}_{m}-y^{v}_{m})^{2}}{\mu^{v}_{m}}\right)$
$\displaystyle=\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}s^{v}_{m}(\log({y^{\prime}}^{v}_{m}){-}\log(y^{v}_{m}))({y^{\prime}}^{v}_{m}{-}y^{v}_{m})\right)\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}s^{v}_{m}\frac{{y^{\prime}}^{v}_{m}-y^{v}_{m}}{\log({y^{\prime}}^{v}_{m})-\log(y^{v}_{m})}\right).$

The inequality is obtained using Cauchy–Schwarz inequality. Take
${s^{v}_{m}}\leq s_{\max},\forall(v,m)\in\mathcal{V}\times\mathcal{M}$, we
obtain:

$\displaystyle\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}{s^{v}_{m}}\frac{{y^{\prime}}^{v}_{m}-y^{v}_{m}}{\log({y^{\prime}}^{v}_{m})-\log(y^{v}_{m})}$
$\displaystyle\leq
s_{\max}\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu^{v}_{m}\neq
0}\frac{{y^{\prime}}^{v}_{m}-y^{v}_{m}}{\log({y^{\prime}}^{v}_{m})-\log(y^{v}_{m})}$
$\displaystyle=s_{\max}\sum_{v\in\mathcal{V}}\sum_{m\in\mathcal{M}:\mu^{v}_{m}\neq
0}\frac{{y^{\prime}}^{v}_{m}-y^{v}_{m}}{\log({y^{\prime}}^{v}_{m})-\log(y^{v}_{m})}$
$\displaystyle\leq
s_{\max}\sum_{v\in\mathcal{V}}\sum_{m\in\mathcal{M}}\frac{{y^{\prime}}^{v}_{m}+y^{v}_{m}}{2}$
$\displaystyle\leq s_{\max}|\mathcal{V}||\mathcal{M}|.$

The second inequality is shown in [69, Eq. (A.16)]. We find that
$\forall\boldsymbol{{y^{\prime}}},\boldsymbol{{y}}\in\mathcal{Y}\cap\mathcal{D}$:

$\displaystyle\frac{1}{s_{\max}|\mathcal{V}|U}\norm{\boldsymbol{{y^{\prime}}}-\boldsymbol{{y}}}^{2}_{l_{1}(\boldsymbol{{s}})}\leq\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}:\mu_{m}^{v}\neq
0}{s^{v}_{m}}^{v}(\log({y^{\prime}}_{m}^{v})-\log(y_{m}^{v}))({y^{\prime}}_{m}^{v}-y_{m}^{v})=(\nabla\Phi(\boldsymbol{{y^{\prime}}})-\nabla\Phi(\boldsymbol{{y}}))^{T}(\boldsymbol{{y^{\prime}}}-\boldsymbol{{y}}).$
(89)

The strong convexity constant $\theta$ is
$\frac{1}{s_{\max}|\mathcal{V}||\mathcal{M}|}$. ∎

###  E-C Subgradient Bound

######  Lemma E.3.

For any $(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t})\in\mathcal{A}$, the
subgradients $\boldsymbol{{g}}_{t}$ of the gain function in Eq. (16) at point
$\boldsymbol{{y}}_{t}\in\mathcal{Y}$ are bounded under the norm
$\norm{\,\cdot\,}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$ by
$\sigma=\frac{RL_{\max}\Delta_{C}}{s_{\min}}$, where
$s_{\min}\triangleq\min\\{s^{v}_{m}:\forall(v,m)\in\mathcal{V}\times\mathcal{M}\\}$,
$L_{\max}\triangleq\max\\{L^{v}_{m}:\forall(v,m)\in\mathcal{V}\times\mathcal{M}\\}$,
$R=|\mathcal{R}|$, and
$\Delta_{C}\triangleq\max\left\\{\left(\sum_{m\in\mathcal{M}}\omega^{\nu(\boldsymbol{{p}})}_{m^{\prime}}C^{\nu(\boldsymbol{{p}})}_{\boldsymbol{{p}},m^{\prime}}\right)-C^{v}_{\boldsymbol{{p}},m}:\forall(i,\boldsymbol{{p}})\in\mathcal{R},(v,m)\in\boldsymbol{{p}}\times\mathcal{M}\right\\}$
is the maximum serving cost difference between serving at a repository node
$\nu(\boldsymbol{{p}})$ and at any other node $v\in\boldsymbol{{p}}$. The norm
$\norm{\,\cdot\,}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$ is defined as

$\displaystyle\textstyle\norm{\boldsymbol{{y}}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$
$\displaystyle\triangleq\max\left\\{\frac{|y^{v}_{m}|}{{s}^{v}_{m}}:(v,m)\in\mathcal{V}\times\mathcal{M}\right\\}.$
(90)

###### Proof.

We have for any $t\in[T]$

$\displaystyle\norm{\boldsymbol{{g}}_{t}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$
$\displaystyle=\max\left\\{\frac{|g^{v}_{t,m}|}{s^{v}_{m}},\forall(v,m)\in\mathcal{V}\times\mathcal{M}\right\\}\leq\max\left\\{\frac{|g^{v}_{t,m}|}{s_{\min}},\forall(v,m)\in\mathcal{V}\times\mathcal{M}\right\\}$
(91)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:subgradient_expression}}}{{\leq}}\frac{L_{\max}}{s_{\min}}\max\left\\{\sum_{\rho\in\mathcal{R}}\left(\gamma^{K^{*}_{\rho}(\boldsymbol{{y}}_{t})}_{\rho}-C^{v}_{\boldsymbol{{p}},m}\right)\cdot\mathds{1}_{\\{\kappa_{\rho}(v,m)<K^{*}_{\rho}(\boldsymbol{{y}}_{t})\\}},\forall(v,m)\in\mathcal{V}\times\mathcal{M}\right\\}$
(92) $\displaystyle\stackrel{{\scriptstyle\eqref{eq:several-
definitions}}}{{\leq}}\frac{L_{\max}R}{s_{\min}}\max\\{\gamma_{\rho}^{K_{\rho}}-\gamma_{\rho}^{1},\forall\rho\in\mathcal{R}\\}\leq\frac{L_{\max}R\Delta_{C}}{s_{\min}}=\sigma.$
(93)

∎

###  E-D Dual Norm

######  Lemma E.4.

$\norm{\,\cdot\,}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$ is the dual norm
of $\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$ defined in (90) and (86),
respectively.

###### Proof.

The dual norm $\norm{\,\cdot\,}_{*}$ of
$\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$ is defined as (e.g., [59])

$\displaystyle\norm{\boldsymbol{{z}}}_{*}\triangleq\sup_{\boldsymbol{{y}}\in\mathbb{R}^{\mathcal{V}\times\mathcal{M}}}\left\\{\boldsymbol{{z}}^{T}\boldsymbol{{y}}:\norm{\boldsymbol{{y}}}_{l_{1}(\boldsymbol{{s}})}\leq
1\right\\},\forall\boldsymbol{{z}}\in\mathbb{R}^{\mathcal{V}\times\mathcal{M}}.$
(94)

We thus need to show that
$\norm{\boldsymbol{{z}}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}=\sup_{\boldsymbol{{y}}\in\mathbb{R}^{\mathcal{V}\times\mathcal{M}}}\left\\{\boldsymbol{{z}}^{T}\boldsymbol{{y}}:\norm{\boldsymbol{{y}}}_{l_{1}(\boldsymbol{{s}})}\leq
1\right\\},\forall\boldsymbol{{z}}\in\mathbb{R}^{\mathcal{V}\times\mathcal{M}}.$

Consider any two vectors $\boldsymbol{{y}}$ and $\boldsymbol{{z}}$ in
$\mathbb{R}^{\mathcal{V}\times\mathcal{M}}$. We have

$\displaystyle\boldsymbol{{z}}^{T}\boldsymbol{{y}}$
$\displaystyle=\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}y^{v}_{m}z^{v}_{m}=\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}(s^{v}_{m}y^{v}_{m})\left(\frac{z^{v}_{m}}{s^{v}_{m}}\right)\leq\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}(s^{v}_{m}\cdot|y^{v}_{m}|)\left(\frac{|z^{v}_{m}|}{s^{v}_{m}}\right)$
(95)
$\displaystyle\leq\textstyle\left(\sum_{(v,m)\in\mathcal{V}\times\mathcal{M}}s^{v}_{m}|y^{v}_{m}|\right)\max\left\\{\frac{|z^{v}_{m}|}{s^{v}_{m}}:(v,m)\in\mathcal{V}\times\mathcal{M}\right\\}=\norm{\boldsymbol{{y}}}_{l_{1}(\boldsymbol{{s}})}\norm{\boldsymbol{{z}}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}.$
(96)

Observe that

$\displaystyle\boldsymbol{{y}}^{T}\boldsymbol{{z}}\leq\norm{\boldsymbol{{z}}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})},\,\,\,\,\forall\boldsymbol{{y}}:\norm{\boldsymbol{{y}}}_{l_{1}(\boldsymbol{{s}})}\leq
1.$ (97)

Let
$(v_{*},m_{*})=\underset{{}_{(v,m)\in\mathcal{V}\times\mathcal{M}}}{\operatorname*{\arg\max}}\left\\{\frac{|z^{v}_{m}|}{s^{v}_{m}}\right\\}$.
The equality is achieved in (97) when
$\boldsymbol{{y}}_{*}=\left[\frac{\mathrm{sign}(z^{v}_{m})}{s^{v}_{m}}\mathds{1}_{\\{(v,m)=(v_{*},m_{*})\\}}\right]_{(v,m)\in\mathcal{V}\times\mathcal{M}}$.
Note that $\norm{\boldsymbol{{y}}_{*}}_{l_{1}(\boldsymbol{{s}})}=1\leq 1$,
then the supremum in (94) is attained for
$\boldsymbol{{y}}=\boldsymbol{{y}}_{*}$ and has value
$\norm{\boldsymbol{{z}}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$; therefore,
$\norm{\,\cdot\,}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$ is the dual norm
of $\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$.

∎

###  E-E Bregman Divergence Bound

######  Lemma E.5.

The value of the Bregman divergence
$D_{\Phi}(\boldsymbol{{y}},\boldsymbol{{y}}_{1})$ in Eq. (53) associated with
the mirror map
$\Phi(\boldsymbol{{y}})=\sum_{v\in\mathcal{V}}\Phi^{v}(\boldsymbol{{y}}^{v})=\sum_{v\in\mathcal{V}}\sum_{m\in\mathcal{M}}s^{v}_{m}y^{v}_{m}\log(y^{v}_{m})$
is upper bounded by a constant

$\displaystyle
D_{\max}\triangleq\sum_{v\in\mathcal{V}}\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}\log\left(\frac{\norm{\boldsymbol{{s}}^{v}}_{1}}{\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}}\right)\geq
D_{\Phi}(\boldsymbol{{y}},\boldsymbol{{y}}_{1}).$ (98)

where
$y^{v}_{1,m}=\frac{\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}}{\norm{\boldsymbol{{s}}^{v}}_{1}},\forall(v,m)\in\mathcal{V}\times\mathcal{M}$
and $\boldsymbol{{s}}^{v}=[s^{v}_{m}]_{m\in\mathcal{M}}$ for every
$v\in\mathcal{V}$.

###### Proof.

We prove that $\boldsymbol{{y}}^{v}_{1}$ is the minimizer of $\Phi^{v}$ over
$\mathcal{Y}^{v}$. As $\Phi^{v}$ is convex over $\mathcal{Y}^{v}$ and
differentiable in $\boldsymbol{{y}}^{v}_{1}$, $\boldsymbol{{y}}^{v}_{1}$ is a
minimizer if and only if
${\nabla\Phi^{v}(\boldsymbol{{y}}^{v}_{1})}^{T}(\boldsymbol{{y}}^{v}_{1}-\boldsymbol{{y}})\leq
0,\forall\boldsymbol{{y}}^{v}\in\mathcal{Y}^{v}$ [59, Proposition 1.3] (first
order optimality condition). Note that from the definition of
$\mathcal{Y}^{v}$ (see Sec. IV) we have for any
$\boldsymbol{{y}}^{v}\in\mathcal{Y}^{v}$

$\displaystyle\sum_{m\in\mathcal{M}}s^{v}_{m}y^{v}_{m}=\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}.$
(99)

Let
$c=\frac{\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}}{\norm{\boldsymbol{{s}}^{v}}_{1}}$,
we get

$\displaystyle{\nabla\Phi^{v}(\boldsymbol{{y}}^{v}_{1})}^{T}(\boldsymbol{{y}}^{v}_{1}-\boldsymbol{{y}})$
$\displaystyle=\sum_{m\in\mathcal{M}}s^{v}_{m}(\log(c)+1)(c-y^{v}_{m})=(\log(c)+1)(c\norm{\boldsymbol{{s}}^{v}}_{1}-\sum_{m\in\mathcal{M}}s^{v}_{m}y^{v}_{m})$
(100)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:def2_repeated}}}{{=}}(\log(c)+1)\left(c\norm{\boldsymbol{{s}}^{v}}_{1}-\sum_{m\in\mathcal{M}}s^{v}_{m}y^{v}_{m}\right)=(\log(c)+1)\left(\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}-\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}\right)$
(101) $\displaystyle=0.$ (102)

We confirmed that $\boldsymbol{{y}}^{v}_{1}$ is a minimizer of $\Phi^{v}$ over
$\mathcal{Y}^{v}$. We have $\Phi^{v}(\boldsymbol{{y}}^{v})\leq
0,\forall\boldsymbol{{y}}^{v}\in\mathcal{Y}^{v}$, and using the first order
optimality condition we obtain

$\displaystyle D_{\Phi^{v}}(\boldsymbol{{y}}^{v},\boldsymbol{{y}}^{v}_{1})$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:bregman_local_mirrormap}}}{{=}}\Phi^{v}(\boldsymbol{{y}}^{v})-\Phi^{v}(\boldsymbol{{y}}^{v}_{1})+{\nabla\Phi^{v}(\boldsymbol{{y}}^{v}_{1})}^{T}(\boldsymbol{{y}}^{v}_{1}-\boldsymbol{{y}}^{v})\leq\Phi^{v}(\boldsymbol{{y}}^{v})-\Phi^{v}(\boldsymbol{{y}}^{v}_{1})\leq-\Phi^{v}(\boldsymbol{{y}}^{v}_{1})$
(103)
$\displaystyle=\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}\log\left(\frac{\norm{\boldsymbol{{s}}^{v}}_{1}}{\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}}\right).$
(104)

Thus, we obtain

$\displaystyle\sum_{v\in\mathcal{V}}D_{\Phi^{v}}(\boldsymbol{{y}}^{v},\boldsymbol{{y}}^{v}_{1})\stackrel{{\scriptstyle\eqref{eq:sum_divergences}}}{{=}}D_{\Phi}(\boldsymbol{{y}},\boldsymbol{{y}}_{1})\leq\sum_{v\in\mathcal{V}}\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}\log\left(\frac{\norm{\boldsymbol{{s}}^{v}}_{1}}{\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}}\right).$
(105)

∎

###  E-F Bounds on the Gain Function

Upper and lower bounds on the gain function in Eq. (16) will be established
using the following bounding function

$\displaystyle\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},$
$\displaystyle\boldsymbol{{y}})\triangleq\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)r^{t}_{\rho}\left(1-\prod_{k^{\prime}=1}^{k}\left(1-z_{\rho}^{k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})/r^{t}_{\rho}\right)\right)\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}},\forall\boldsymbol{{y}}\in\mathcal{X}\cup\mathcal{Y},$
(106)

where

$\displaystyle\mathrm{supp}(\boldsymbol{{r}}^{t})\triangleq\left\\{\rho\in\mathcal{R}:r^{t}_{\rho}\neq
0\right\\}$ (107)

is the set of request types for which there is a non-zero number of requests
in the request batch $\boldsymbol{{r}}^{t}$.

######  Lemma E.6.

The gain function in Eq. (16) can be equivalently expressed as

$\displaystyle
G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})=\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}},\forall\boldsymbol{{y}}\in\mathcal{X}\cup\mathcal{Y}.$
(108)

###### Proof.

Remember from the definition in Eq. (15) that
${Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}=\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}$.
We observe that
$Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})$
is not a function of $\boldsymbol{{y}}$ and it is equal to $0$, when there is
no repository with model’s rank smaller or equal to $k$, and to
$r^{t}_{\rho}$, otherwise; therefore,
$Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})\in\\{0,r^{t}_{\rho}\\}$.

When
$Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})\neq
0$, and thus
$Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=r^{t}_{\rho}$,
the following holds

$\displaystyle{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}$
$\displaystyle=\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}$
(109)
$\displaystyle=\min\left\\{0,\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})-Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})\right\\}=0.$
(110)

The last equality holds because
$\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})-Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})\geq
0,\forall\boldsymbol{{y}}\in\mathcal{X}\cup\mathcal{Y}$ from Eq. (3).
Otherwise, when
$Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0$,
we have
${Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}={Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}\stackrel{{\scriptstyle\eqref{eq:sum_of_auxvars}}}{{=}}\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}$.

Hence, we can succinctly write, for any value of
$Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})$,
that

$\displaystyle{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}=\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}.$
(111)

Since
$\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})$
is non negative, the previous formula implies that

$\displaystyle{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}=0,\
\ \ \ \text{if }r^{t}_{\rho}=0.$ (112)

By combining Eq. (111) and (112) that

$\displaystyle{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}=\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\,\,\land\,\,r^{t}_{\rho}\neq
0\\}}.$ (113)

Hence, applying the above equalities on the gain expression we get

$\displaystyle G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:gain-
compact}}}{{=}}\sum_{\rho\in\mathcal{R}}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)\left({Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})}-{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})}\right)$
(114)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:shortcut_a}}}{{=}}\sum_{\rho\in\mathcal{R}}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\,\,\land\,\,r^{t}_{\rho}\neq
0\\}}$ (115)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:supp_def}}}{{=}}\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}.$
(116)

∎

######  Lemma E.7.

Consider $n\in\mathbb{N}$, $\boldsymbol{{y}}\in[0,1]^{n}$,
$\boldsymbol{{q}}\in\mathbb{N}^{n}$, and $c\in\mathbb{N}$. We assume that
$q_{i}\leq c,\forall i\in[n]$. The following holds

$\displaystyle\min\left\\{c,\sum_{i\in[n]}y_{i}q_{i}\right\\}\geq
c-c\prod_{i\in[n]}(1-y_{i}q_{i}/c).$ (117)

###### Proof.

We define $a_{n}\triangleq c-c\prod_{i\in[n]}(1-y_{i}q_{i}/c)$ and
$b_{n}\triangleq\min\left\\{c,\sum_{i\in[n]}y_{i}q_{i}\right\\}$.

We first show by induction that, if $a_{n}\leq b_{n}$, then this inequality
holds also for $n+1$.

_Base case ( $n=1$)._

$\displaystyle a_{1}$
$\displaystyle=c-c+y_{1}q_{1}=y_{1}q_{1}=\min\\{c,q_{1}y_{1}\\}=b_{1}.$ (118)

_Induction step._

$\displaystyle a_{n+1}$ $\displaystyle=c-c\prod_{i\in[n+1]}(1-y_{i}q_{i}/c)$
(119) $\displaystyle=c-c\prod_{i\in[n]}(1-y_{i}q_{i}/c)(1-y_{n+1}q_{n+1}/c)$
(120)
$\displaystyle=c-c\prod_{i\in[n]}(1-y_{i}q_{i}/c)+(cy_{n+1}q_{n+1}/c)\prod_{i\in[n]}(1-y_{i}q_{i}/c)$
(121) $\displaystyle=a_{n}+y_{n+1}q_{n+1}\prod_{i\in[n]}(1-y_{i}q_{i}/c)$
(122) $\displaystyle\leq a_{n}+y_{n+1}q_{n+1}.$ (123)

The last inequality holds since by construction $q_{i}\leq c$ and thus $0\leq
y_{i}q_{i}/c\leq 1$, and
$0\leq\prod_{i\in[n]}\left(1-{y_{i}q_{i}}/{c}\right)\leq 1$. For the same
reason, $0\leq\prod_{i\in[n+1]}(1-y_{i}q_{i}/c)\leq 1$ and thus, by (119), we
have $a_{n+1}\leq c$. Moreover, note that if $b_{n}=c$ then $b_{n+1}=c$.
Therefore:

$\displaystyle a_{n+1}$
$\displaystyle\leq\min\left\\{c,a_{n}+y_{n+1}q_{n+1}\right\\}\leq\min\left\\{c,b_{n}+y_{n+1}q_{n+1}\right\\}$
(124)
$\displaystyle=\begin{cases}\min\left\\{c,\sum^{n+1}_{i=1}y_{i}q_{i}\right\\}=b_{n+1},&\text{
if}\quad b_{n}\leq c,\\\
\min\left\\{c,c+y_{n+1}q_{n+1}\right\\}=c=b_{n+1},&\text{ if}\quad
b_{n}=c,\end{cases}$ (125)

and the proof by induction is completed.

∎

######  Lemma E.8.

Consider $\boldsymbol{{y}}\in[0,1]^{n}$, $\boldsymbol{{q}}\in\mathbb{N}^{n}$,
$c\in\mathbb{N}$ and $n\in\mathbb{N}$. We assume that $q_{i}\leq c,\forall
i\in[n]$. The following holds

$\displaystyle
c-c\prod_{i\in[n]}(1-y_{i}q_{i}/c)\geq(1-1/e)\min\left\\{c,\sum_{i\in[n]}y_{i}q_{i}\right\\}.$
(126)

###### Proof.

Our proof follows the same lines of the proof of [70, Lemma 3.1]. We use the
arithmetic/geometric mean inequality [71] on the non-negative variables
$1-y_{i}q_{i}/c,i\in[n]$ to obtain:

$\displaystyle\frac{1}{n}\sum_{i\in[n]}(1-y_{i}q_{i}/c)\geq\left(\prod_{i\in[n]}(1-y_{i}q_{i}/c)\right)^{\frac{1}{n}}.$
(127)

We reformulate the above as:

$\displaystyle 1-\prod_{i\in[n]}(1-y_{i}q_{i}/c)$ $\displaystyle\geq
1-\left({\frac{1}{n}}\sum_{i\in[n]}\left(1-y_{i}q_{i}/c\right)\right)^{n}=1-\left(1-{\frac{1}{n}}\sum_{i\in[n]}y_{i}q_{i}/c\right)^{n}$
(128) $\displaystyle\geq
1-\left(1-{\frac{1}{n}}\min\left\\{1,\sum_{i\in[n]}y_{i}q_{i}/c\right\\}\right)^{n}.$
(129)

To obtain the last inequality, consider that, for any number $z$, we have
$z\geq\min\\{1,z\\}$, and thus
$\sum_{i\in[n]}y_{i}q_{i}/c\geq\min\left\\{1,\sum_{i\in[n]}y_{i}q_{i}/c\right\\}$.

The function $f(z)=1-(1-z/n)^{n}$ is concave for $z\in[0,1]$, then, for
$z\in[0,1]$, $f(z)\geq f(0)+z\frac{f(1)-f(0)}{1-0}=zf(1)$, as $f(0)=0$.
Setting $z=\min\left\\{1,\sum_{i\in[n]}y_{i}q_{i}/c\right\\}$ , we obtain the
following:

$\displaystyle
1-\prod_{i\in[n]}(1-y_{i}q_{i}/c)\stackrel{{\scriptstyle\eqref{eq:ineq-1}}}{{\geq}}1-\left(1-{\frac{1}{n}}z\right)^{n}\geq\left(1-(1-1/n)^{n}\right)z\geq(1-1/e)z.$
(130)

The last inequality is obtained since $1-(1-1/n)^{n}$ decreases in $n$, and it
is lower bounded by $1-1/e$. By multiplying both sides of the above inequality
by $c\in\mathbb{N}$, and replacing $z$ with its value we conclude the proof. ∎

######  Lemma E.9.

for any request batch $\boldsymbol{{r}}_{t}$ and potential available capacity
$\boldsymbol{{l}}_{t}$ such that
$(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t})\in\mathcal{A}$, the allocation
gain $G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$ has the
following lower and upper bounds

$\displaystyle\left(1-\tfrac{1}{e}\right)^{-1}\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})\geq
G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$
$\displaystyle\geq\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}),$
$\displaystyle\forall\boldsymbol{{y}}\in\mathcal{X}\cup\mathcal{Y}.$ (131)

###### Proof.

We have the following

$\displaystyle G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:equivalent_gain_for_proof}}}{{=}}\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}$
(132)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:lower_bound_piece}}}{{\geq}}\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)r^{t}_{\rho}\left(1-\prod_{k^{\prime}=1}^{k}\left(1-z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})/r^{t}_{\rho}\right)\right)\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}$
(133) $\displaystyle\stackrel{{\scriptstyle\eqref{eq:gain-
surrogate}}}{{=}}\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}),\forall\boldsymbol{{y}}\in\mathcal{X}\cup\mathcal{Y},$
(134)

and

$\displaystyle(1-1/e)G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:equivalent_gain_for_proof}}}{{=}}(1-1/e)\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)\min\left\\{r^{t}_{\rho},\sum^{k}_{k^{\prime}=1}z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})\right\\}\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}$
(135)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:upper_bound_piece}}}{{\leq}}\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)r^{t}_{\rho}\left(1-\prod_{k^{\prime}=1}^{k}\left(1-z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})/r^{t}_{\rho}\right)\right)\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}$
(136) $\displaystyle\stackrel{{\scriptstyle\eqref{eq:gain-
surrogate}}}{{=}}\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}),\forall\boldsymbol{{y}}\in\mathcal{X}\cup\mathcal{Y}.$
(137)

Inequalities in Eq. (133) and Eq. (136) follow from Eq. (117) and Eq. (126),
respectively, by replacing $c=r^{t}_{\rho}$,
$q_{k^{\prime}}=\lambda^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t})$,
$x_{k^{\prime}}=z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})/\lambda^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t})$,
and $n=k$. ∎

######  Lemma E.10.

Let the allocation $\boldsymbol{{x}}^{v}$ be the random output of DepRound on
node $v\in\mathcal{V}$ given the fractional allocation
$\boldsymbol{{y}}^{v}\in\mathcal{Y}^{v}$. For any subset of the model catalog
$S\subset\mathcal{M}$ and any number $c_{m}\in[0,1],\forall m\in S$, DepRound
satisfies the following:

$\displaystyle\mathbb{E}\left[\prod_{m\in
S}(1-x^{v}_{m}c_{m})\right]\leq\prod_{m\in S}(1-y^{v}_{m}c_{m}).$ (138)

###### Proof.

DepRound uses a subroutine Simplify, which, given input variables
$y_{m},y_{m^{\prime}}\in(0,1)$, outputs $x_{m},x_{m^{\prime}}\in[0,1]$ with at
least one of them being integral ($0$ or $1$). Note that the input to Simplify
is never integral since it is only called on fractional and yet unrounded
variables. The property (B3) in [61, Lemma 2.1] implies that the output
variables $x_{m}$ and $x_{m^{\prime}}$ satisfy the following inequality:

$\displaystyle\mathbb{E}[x_{m}x_{m^{\prime}}]$ $\displaystyle\leq
y_{m}y_{m^{\prime}}.$ (139)

We have for any $c_{m},c_{m^{\prime}}\in[0,1]$:

$\displaystyle\mathbb{E}[(1-x_{m}c_{m})(1-x_{m^{\prime}}c_{m^{\prime}})]$
$\displaystyle=\mathbb{E}[1-x_{m}c_{m}-x_{m^{\prime}}c_{m^{\prime}}+x_{m}x_{m^{\prime}}c_{m}c_{m^{\prime}}]$
(140)
$\displaystyle=1-y_{m}c_{m}-y_{m^{\prime}}c_{m^{\prime}}+\mathbb{E}[x_{m}x_{m^{\prime}}]c_{m}c_{m^{\prime}}$
(141) $\displaystyle\leq
1-y_{m}c_{m}-y_{m^{\prime}}c_{m^{\prime}}+y_{m}y_{m^{\prime}}c_{m}c_{m^{\prime}}$
$\displaystyle=(1-y_{m}c_{m})(1-y_{m^{\prime}}c_{m^{\prime}}).$ (142)

where the second equality is obtained recalling that, by construction,
$\mathbb{E}[x^{v}_{m}]=y_{m},\forall m\in\mathcal{M}$ (Sec. IV-C).

Thus, the two fractional inputs $y_{m}$ and $y_{m^{\prime}}$ to the Simplify
subroutine, return $x_{m}$ and $x_{m^{\prime}}$ satisfying the property (142).
By induction as in the proof in [61, Lemma 2.2], we obtain for any
$S\subset\mathcal{M}$:

$\displaystyle\mathbb{E}\left[\prod_{m\in
S}(1-x_{m}c_{m})\right]\leq\prod_{m\in S}(1-y_{m}c_{m}).$ (143)

Note that the above property is satisfied with equality if the components of
$\boldsymbol{{x}}\in\\{0,1\\}^{|\mathcal{M}|}$ are sampled independently with
$\mathbb{E}[x_{m}]=y_{m}$. ∎

######  Lemma E.11.

Let the allocation $\boldsymbol{{x}}^{v}$ be the random output of DepRound on
node $v\in\mathcal{V}$ given the fractional allocation
$\boldsymbol{{y}}^{v}\in\mathcal{Y}^{v}$. The following holds

$\displaystyle\mathbb{E}\left[\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})\right]\geq\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{t}).$
(144)

###### Proof.

For any $k^{\prime}$, assume $m\in\mathcal{M}$ and $v\in\mathcal{V}$ are such
that $\kappa_{\rho}(v,m)=k^{\prime}$ (Sec. III-E). Since
$z^{k^{\prime}}_{\rho}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})=y^{v}_{m}l^{t,v}_{\rho,m}$
for a given $(m,v)\in\mathcal{M}\times\mathcal{V}$, then
$z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})/r^{t}_{\rho}$ can
be written as:

$\displaystyle
z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}})/r^{t}_{\rho}=\frac{l^{t,v}_{\rho,m}}{r^{t}_{\rho}}y_{m}^{v}.$
(145)

where $\frac{l^{t,v}_{\rho,m}}{r^{t}_{\rho}}$ is a constant in $[0,1]$
($l^{t,v}_{\rho,m}\leq\min\\{r^{t}_{\rho},L_{m}^{v}\\}$ \- see Sec. III-D)
that scales variable $y^{v}_{m}$ ;therefore, by applying Lemma E.10, we obtain
the following upper bound on the bounding function. Consider for all
$v\in\mathcal{V}$ and $t\in[T]$ that $\boldsymbol{{x}}^{v}_{t}$ is the random
allocation obtained by running DepRound on the fractional allocation
$\boldsymbol{{y}}^{v}_{t}$, then

$\displaystyle\mathbb{E}\left[\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:gain-
surrogate}}}{{=}}\mathbb{E}\left[\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)r^{t}_{\rho}\left(1-\prod_{k^{\prime}=1}^{k}\left(1-z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})/r^{t}_{\rho}\right)\right)\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}\right]$
(146)
$\displaystyle=\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)r^{t}_{\rho}\left(1-\mathbb{E}\left[\prod_{k^{\prime}=1}^{k}\left(1-z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})/r^{t}_{\rho}\right)\right]\right)\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}$
(147)
$\displaystyle\geq\sum_{\rho\in\mathrm{supp}(\boldsymbol{{r}}^{t})}\sum_{k=1}^{K_{\rho}-1}\left(\gamma^{k+1}_{\rho}-\gamma^{k}_{\rho}\right)r^{t}_{\rho}\left(1-\prod_{k^{\prime}=1}^{k}\left(1-z_{\rho,k^{\prime}}(\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{t})/r^{t}_{\rho}\right)\right)\mathds{1}_{\\{Z^{k}_{\rho}(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{\omega}})=0\\}}$
(148)
$\displaystyle=\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{t}).$
(149)

The equality is obtained using the linearity of the expectation, and the
inequality is obtained by applying directly Lemma E.10. ∎

##  Appendix F Proof of Theorem V.1

###### Proof.

To prove the $\psi$-regret guarantee: _(i)_ we first establish an upper bound
on the regret of the INFIDA policy over its fractional allocations domain
$\mathcal{Y}$ against a fractional optimum, then _(ii)_ we use it to derive a
corresponding $\psi$-regret guarantee over the integral allocations domain
$\mathcal{X}$.

Fractional domain regret guarantee. To establish the regret guarantee of
running Algorithm 1 at the level of each computing node $v\in\mathcal{V}$, we
showed that the following properties hold:

  1. 1.

The function $G$ is concave over its domain $\mathcal{Y}$ (Lemma E.1).

  2. 2.

The mirror map $\Phi:\mathcal{D}\to\mathbb{R}$ is $\theta$-strongly convex
w.r.t. the norm $\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$ over
$\mathcal{Y}\cap\mathcal{D}$, where $\theta$ is equal to Eq. (85) (Lemma E.2).

  3. 3.

The gain function $G:\mathcal{Y}\to\mathbb{R}$ is $\sigma$-Lipchitz w.r.t
$\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$: the subgradients are bounded
under the norm $\norm{\cdot}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$ by
$\sigma$, i.e., the subgradient of
$G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$ at point
$\boldsymbol{{y}}_{t}\in\mathcal{Y}$ is upper bounded
($\norm{\boldsymbol{{g}}_{t}}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}\leq\sigma$)
for any $(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t})\in\mathcal{A}$ (Lemma
E.3).

  4. 4.

$\norm{\,\cdot\,}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}$ is the dual norm
of $\norm{\,\cdot\,}_{l_{1}(\boldsymbol{{s}})}$ (Lemma E.4).

  5. 5.

The Bregman divergence $D_{\Phi}(\boldsymbol{{y}}_{*},\boldsymbol{{y}}_{1})$
in Eq. (53) is upper bounded by a constant $D_{\max}$ where
$\boldsymbol{{y}}_{*}={\arg\max}_{\boldsymbol{{y}}\in\mathcal{Y}}\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}})$
and
$\boldsymbol{{y}}_{1}=\underset{\boldsymbol{{y}}\in\mathcal{Y}\cap\mathcal{D}}{\arg\min}\,\Phi(\boldsymbol{{y}})$
is the initial allocation (Lemma E.5).

Because of properties 1–5 above, the following bound holds for the regret of
INFIDA over its fractional domain $\mathcal{Y}$ (vector field point of view of
Mirror Descent in [59, Sec. 4.2] combined with [59, Theorem 4.2]):

$\displaystyle\mathrm{Regret}_{T,\mathcal{Y}}$
$\displaystyle=\underset{{{\\{(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t})\\}_{t=1}^{T}\in\mathcal{A}^{T}}}}{\sup}\left\\{\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{*}){-}\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{t})\right\\}$
(150)
$\displaystyle\leq\frac{D_{\Phi}(\boldsymbol{{y}}_{*},\boldsymbol{{y}}_{1})}{\eta}+\frac{\eta}{2\theta}\sum^{T}_{t=1}\norm{\boldsymbol{{g}}_{t}}^{2}_{l_{\infty}(\frac{1}{\boldsymbol{{s}}})}\leq\frac{D_{\max}}{\eta}+\frac{\eta\sigma^{2}T}{2\theta}.$
(151)

where $\eta$ is the learning rate of INFIDA (Algorithm 1, line 6). By
selecting the learning rate $\eta=\frac{1}{\sigma}\sqrt{\frac{2\theta
D_{\max}}{T}}$ giving the tightest upper bound we obtain

$\displaystyle\mathrm{Regret}_{T,\mathcal{Y}}\leq\sigma\sqrt{\frac{2D_{\max}}{\theta}T}.$
(152)

Integral domain regret guarantee. Note that, by restricting the maximization
to the subset of integral allocations $\boldsymbol{{x}}\in\mathcal{X}$, the
optimal allocation
$\boldsymbol{{x}}_{*}={\arg\max}_{\boldsymbol{{x}}\in\mathcal{X}}\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}})$
can only lead to a lower gain, i.e.,

$\displaystyle\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{*})\leq\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{*}).$
(153)

By taking $\psi=1-\frac{1}{e}$, and using the bounding function $\Lambda$
defined in Eq. (106), with the expectation taken over the random choices of
the policy (DepRound at line 8 in Algorithm 1) we obtain

$\displaystyle\mathbb{E}\left[\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:gain_lower_upper_bound}}}{{\geq}}\mathbb{E}\left[\sum^{T}_{t=1}\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})\right]\stackrel{{\scriptstyle\eqref{eq:El_lowerbound}}}{{\geq}}\sum^{T}_{t=1}\Lambda(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{t})\stackrel{{\scriptstyle\eqref{eq:gain_lower_upper_bound}}}{{\geq}}\psi\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{t})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:fractional_regret_bound}}}{{\geq}}\psi\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{y}}_{*})-\psi\sigma\sqrt{\frac{2D_{\max}}{\theta}T}\stackrel{{\scriptstyle\eqref{eq:optimality_in_convx}}}{{\geq}}\psi\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{*})-\psi\sigma\sqrt{\frac{2D_{\max}}{\theta}T}.$
(154)

Thus, we have

$\displaystyle\psi\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{*})-\mathbb{E}\left[\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})\right]\leq\psi\sigma\sqrt{\frac{2D_{\max}}{\theta}T}.$
(155)

The above inequality holds for any sequence
$\\{(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t})\\}_{t=1}^{T}\in\mathcal{A}^{T}$.
Thus, the $\psi$-regret is given by

$\displaystyle\psi\text{-}\mathrm{Regret}_{T,\mathcal{X}}\stackrel{{\scriptstyle\eqref{eq:regret-
definition}}}{{=}}\underset{{{\\{\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t}\\}_{t=1}^{T}\in\mathcal{A}^{T}}}}{\sup}\left\\{\psi\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{*})-\mathbb{E}\left[\sum^{T}_{t=1}G(\boldsymbol{{r}}_{t},\boldsymbol{{l}}_{t},\boldsymbol{{x}}_{t})\right]\right\\}\leq
A\sqrt{T},$ (156)

where

$A=\psi\sigma\sqrt{\frac{2D_{\max}}{\theta}}=\psi\frac{RL_{\max}\Delta_{C}}{s_{\min}}\sqrt{s_{\max}|\mathcal{V}||\mathcal{M}|}\sqrt{2\sum_{v\in\mathcal{V}}\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}\log\left(\frac{\norm{\boldsymbol{{s}}^{v}}_{1}}{\min\\{b^{v},\norm{\boldsymbol{{s}}^{v}}_{1}\\}}\right)},$

using the upper bounds on $\theta$, $\sigma$, and $D_{\max}$ determined in
Lemmas E.2, E.3, and E.5, respectively.

This proves Theorem V.1. ∎

##  Appendix G Proof of Proposition V.1.1

###### Proof.

Let $\bar{\boldsymbol{{y}}}$ be the average fractional allocation
$\bar{\boldsymbol{{y}}}=\frac{1}{\tilde{T}}\sum^{\tilde{T}}_{t=1}\boldsymbol{{y}}_{t}$
of INFIDA, and $\bar{\boldsymbol{{x}}}$ the random state sampled from
$\bar{\boldsymbol{{y}}}$ using DepRound. We take
$G_{T}(\boldsymbol{{y}})=\frac{1}{{T}}\sum^{{T}}_{{t}=1}G(\boldsymbol{{r}}_{{t}},\boldsymbol{{l}}_{{t}},{\boldsymbol{{y}}}),\forall\boldsymbol{{y}}\in\mathcal{Y}$.
We have

$\displaystyle\mathbb{E}\left[G_{T}(\bar{\boldsymbol{{x}}})\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:gain_lower_upper_bound}}}{{\geq}}\mathbb{E}\left[\frac{1}{{T}}\sum^{{T}}_{{t}=1}\Lambda(\boldsymbol{{r}}_{{t}},\boldsymbol{{l}}_{{t}},\bar{\boldsymbol{{x}}})\right]\stackrel{{\scriptstyle\eqref{eq:El_lowerbound}}}{{\geq}}\frac{1}{{T}}\sum^{{T}}_{{t}=1}\Lambda(\boldsymbol{{r}}_{{t}},\boldsymbol{{l}}_{{t}},\bar{\boldsymbol{{y}}})\stackrel{{\scriptstyle\eqref{eq:gain_lower_upper_bound}}}{{\geq}}\psi
G_{T}(\bar{\boldsymbol{{y}}}).$ (157)

Using Jensen’s inequality we get

$\displaystyle\psi
G_{T}(\bar{\boldsymbol{{y}}})\geq\psi\frac{1}{\tilde{T}}\sum^{\tilde{T}}_{t=1}G_{T}(\boldsymbol{{y}}_{t}).$
(158)

∎

It straightforward to check that $G_{T}$ satisfies the same properties 1
(concavity) and 3 (subgradient boundedness) as $G$ and the remaining
properties are preserved under the same mirror map and convex decision set.
With properties 1–5 satisfied, we can apply [59, Theorem 4.2] to obtain

$\displaystyle\sum^{\tilde{T}}_{t=1}G_{T}(\boldsymbol{{y}}_{*})-\sum^{\tilde{T}}_{t=1}G_{T}(\boldsymbol{{y}}_{t})=\tilde{T}G_{T}(\boldsymbol{{y}}_{*})-\sum^{\tilde{T}}_{t=1}G_{T}(\boldsymbol{{y}}_{t})\leq\sigma\sqrt{\frac{2D_{\max}}{\theta}\tilde{T}}.$
(159)

Dividing both sides of the above inequality by $\tilde{T}$ gives

$\displaystyle\frac{1}{\tilde{T}}\sum^{\tilde{T}}_{t=1}G_{T}(\boldsymbol{{y}}_{t})\geq
G_{T}(\boldsymbol{{y}}_{*})-\sigma\sqrt{\frac{2D_{\max}}{\theta\tilde{T}}}.$
(160)

Using the same argument to obtain Eq. (153), i.e., restricting the
maximization to the integral domain gives a lower value, we get

$\displaystyle\frac{1}{\tilde{T}}\sum^{\tilde{T}}_{t=1}G_{T}(\boldsymbol{{y}}_{t})\geq
G_{T}(\boldsymbol{{x}}_{*})-\sigma\sqrt{\frac{2D_{\max}}{\theta\tilde{T}}}.$
(161)

Using Eq. (157), and Eq. (161) we obtain

$\displaystyle\mathbb{E}\left[G_{T}(\bar{\boldsymbol{{x}}})\right]\geq\psi
G_{T}(\boldsymbol{{x}}_{*})-\psi\sigma\sqrt{\frac{2D}{\theta\tilde{T}}}.$
(162)

Thus, $\forall\epsilon>0$ and over a sufficiently large running time
$\tilde{T}$ for INFIDA, $\bar{\boldsymbol{{x}}}$ satisfies

$\displaystyle\mathbb{E}\left[G_{T}(\bar{\boldsymbol{{x}}})\right]\geq\left(1-\frac{1}{e}-\epsilon\right)G_{T}({\boldsymbol{{x}}}_{*}).$
(163)


# A simple criterion for essential self-adjointness of Weyl pseudodifferential
operators

Robert Fulsche, Lauritz van Luijk

###### Abstract

We prove a new criterion for essential self-adjointness of pseudodifferential
operators which does not involve ellipticity type assumptions. Essential self-
adjointness is proved for symbols in $C^{2d+3}$ with derivatives of order two
and higher being uniformly bounded. These results also apply to hermitian
operator-valued symbols on infinite-dimensional Hilbert spaces which are
important to applications in physics. Our method relies on a phase space
differential calculus for quadratic forms on $L^{2}(\mathbb{R}^{d})$,
Calderón-Vaillancourt type theorems and a recent self-adjointness result for
Toeplitz operators.

Self-adjointness of operators is a crucial property appearing in both
mathematical physics and the theory of differential equations. Weyl
pseudodifferential operators are well-known for being formally self-adjoint,
provided their symbol is real-valued. Surprisingly, there are only a few
criteria in the literature for extending formal self-adjointness to essential
self-adjointness. Using methods recently developed in [1], we obtain a new
criterion for essential self-adjointness of Weyl pseudodifferential operators.
The simplest version is the following:

######  Theorem 1.

Let $f\in C^{2d+3}({\mathbb{R}}^{2d},{\mathbb{R}})$ with derivatives of order
$2$ to $2d+3$ being uniformly bounded, i.e.,
$\|\partial^{\gamma}f\|_{\infty}<\infty$ for multi-indices
$\gamma\in\mathbb{N}_{0}^{2d}$ with $2\leq|\gamma|\leq 2d+3$. Then
$\mathrm{op}^{w}(f)$ is an essentially self-adjoint operator on
$L^{2}({\mathbb{R}}^{d})$ with domain ${\mathscr{S}}({\mathbb{R}}^{d})$.

We comment briefly on the assumption of bounded derivatives of second and
higher orders. In classical mechanics, the only general tool for establishing
global existence of the dynamics, which is the classical analogue of essential
self-adjointness, is the Picard-Lindelöf theorem [7, Appendix to Sec. X.I].
Typically there are two scenarios. Either the Hamiltonian function goes off to
infinity in every direction so that all sub-level sets are compact and the
global existence is evident, or one has to assume that the second-order
derivatives are bounded. Therefore, all symbols $f$ that satisfy the theorem
also satisfy the assumptions of the Picard-Lindelöf theorem and the converse
holds up to the additional regularity imposed on the higher-order derivatives.
A naive extension of the theorem where the assumption is relaxed to, say, the
third-order fails as the symbol $f(x,\xi)=\xi^{2}+x^{3}$ readily shows.
Interestingly, it also fails on the classical side [13].

Note that the assumptions on $f$ imply that it is polynomially bounded, so
that $f$ defines a tempered distribution on ${\mathbb{R}}^{2d}$. This already
ensures that $\mathrm{op}^{w}(f)$ makes sense as a continuous quadratic form
on ${\mathscr{S}}({\mathbb{R}}^{d})$. Our method relies on quadratic form
techniques which reduce the problem to a self-adjointness theorem for Toeplitz
operators on the Segal-Bargmann space.

We indeed prove a more general result (4), which weakens the regularity
assumptions on $f$ significantly and allows for operator-valued symbols. We
also want to emphasize that this result is indeed a rather straightforward
consequence of results from [1], in particular Theorem 20 of that paper. The
present work should therefore not be seen as a paper on deep new proof ideas,
but rather as a report on the presented result. Before going into more detail,
let us briefly discuss the few other results concerning essential self-
adjointness of Weyl pseudodifferential operators available in the literature.

Most papers that provide criteria for essential self-adjointness of
pseuodifferential operator either assume ellipticity [5] are restrict
themselves to symbolds that are of a well-motivated but specific form [4, 6]
The paper [12] due to Yamazaki also considers non-elliptic symbols and uses a
more traditional approach. Its conditions are similar in spirit but require
significantly higher regularity and are obtained by completely different
methods. Besides higher regularity, Yamazaki’s results offer some flexibility
in the choice of symbol class that the derivatives of the symbol have to be
contained in. Nevertheless, it seems that, besides all the flexibility,
Yamazaki’s theorem always asks for conditions not present in our result. For
example, for symbols $b=b(x,\xi)$ (i.e., not only depending on one variable),
it is always necessary that the second derivatives of $b$ satisfy some decay
condition at infinity. Besides all this, all the flexibility in the choices of
parameters does not make Yamazaki’s result particularly simple in terms of
applications. Additionally, it seems that our result on essential self-
adjointness is the first to deal with non-elliptic operator-valued symbols.

We return now to our results. As mentioned above, we will allow for operator-
valued symbols. For a more general discussion on operator-valued symbols and
Hilbert space valued Schwartz spaces we refer to [11]. Given such an operator-
valued symbol
$f\in{\mathscr{S}}^{\prime}({\mathbb{R}}^{2d};\mathcal{B}({\mathcal{K}}))$,
the Weyl pseudodifferential operator
$\mathrm{op}^{w}(f):{\mathscr{S}}({\mathbb{R}}^{d};{\mathcal{K}})\to{\mathscr{S}}^{\prime}({\mathbb{R}}^{d};{\mathcal{K}})$
defines a $\mathcal{B}({\mathcal{K}})$-valued quadratic form on
${\mathscr{S}}({\mathbb{R}}^{d})$ which is jointly continuous for the
${\mathscr{S}}$-topology, i.e., one gets a continuous sesqui-linear map
${\mathscr{S}}({\mathbb{R}}^{d})\times{\mathscr{S}}({\mathbb{R}}^{d})\to\mathcal{B}({\mathcal{K}})$.
We always take quadratic forms to be conjugate-linear in the second entry,
e.g., the quadratic form corresponding to a bounded operator $B$ is
$(\psi,\phi)\mapsto\langle B\psi,\phi\rangle$. To be more precise, the
quadratic form of $\mathrm{op}^{w}(f)$ is given by

$\displaystyle
A_{f}(\phi,\psi)=\int_{{\mathbb{R}}^{d}}\int_{{\mathbb{R}}^{d}}\int_{{\mathbb{R}}^{d}}\phi(y)e^{i(y-x)\cdot\xi}\overline{\psi(x)}f\big{(}\tfrac{x+y}{2},\xi\big{)}\leavevmode\nobreak\
dy\leavevmode\nobreak\ d\xi\leavevmode\nobreak\ dx,$ (1)

for $\phi,\psi\in{\mathscr{S}}({\mathbb{R}}^{d})$, with the natural
interpretation of the above expression if $f$ is not given by an appropriately
integrable function but a proper distribution. [1] gives a sufficient
condition for a continuous quadratic form $A$ on
${\mathscr{S}}({\mathbb{R}}^{d})$ to define an essentially self-adjoint
operator on $L^{2}({\mathbb{R}}^{d})$ with domain
${\mathscr{S}}({\mathbb{R}}^{d})$. To state this condition we introduce some
concepts: Consider the usual vector
$R=(Q_{1},\ldots,Q_{d},P_{1},\allowbreak\ldots,P_{d})$ of position and
momentum operators, where $Q_{j}\psi(x)=x_{j}\psi(x)$ and
$P_{j}\psi(x)=-i\partial_{j}\psi(x)$. $R$ satisfies the canonical commutation
relations $[z\cdot R,w\cdot R]=i\sigma(z,w)\text{1}$,
$z,w\in{\mathbb{R}}^{2d}$, where $\sigma$ is the standard symplectic form on
${\mathbb{R}}^{2d}$:

$\displaystyle\sigma\big{(}(x,\xi),(y,\eta)\big{)}=x\cdot\eta-y\cdot\xi,\quad
x,y,\xi,\eta\in{\mathbb{R}}^{d}.$ (2)

Note that we chose our conventions so that $\mathrm{op}^{w}(x_{j})=Q_{j}$ and
$\mathrm{op}^{w}(\xi_{j})=P_{j}$. We need the Weyl operators
$W_{z}=e^{i\sigma(z,R)}=e^{-i(\xi\cdot Q-x\cdot P)}$,
$z=(x,\xi)\in{\mathbb{R}}^{2d}$, which define a strongly continuous projective
unitary representation of $({\mathbb{R}}^{2d},+)$ on $L^{2}({\mathbb{R}}^{d})$
which leaves ${\mathscr{S}}({\mathbb{R}}^{d})$ invariant. The family $W_{z}$
indeed satisfies these properties, which is clear from the more concrete form
of the Weyl operators,
$W_{z}f(y)=e^{-iy\cdot\xi+\frac{i}{2}{x\cdot\xi}}f(y-x)$, where
$z=(x,\xi)\in\mathbb{R}^{2d}$, cf. also [2, p. 22]. In fact, $W_{z}\phi$ is
smooth in $z$ w.r.t. the topology of ${\mathscr{S}}({\mathbb{R}}^{d})$ for all
$\phi\in{\mathscr{S}}({\mathbb{R}}^{d})$ [1, Prop. 2].

For a continuous quadratic form $A$ on ${\mathscr{S}}({\mathbb{R}}^{d})$ we
define another continuous form $\alpha_{z}A$ on
${\mathscr{S}}({\mathbb{R}}^{d})$ by
$\alpha_{z}A(\phi,\psi)=A(W_{-z}\phi,W_{-z}\psi)$. As an example, for the
quadratic form corresponding to the operator $w\cdot R$ we get
$\alpha_{z}(w\cdot R)=w\cdot R+(w\cdot z)\text{1}$.

For any pair of Schwartz functions
$\phi,\psi\in{\mathscr{S}}({\mathbb{R}}^{d})$, $\alpha_{z}A(\phi,\psi)$ is a
smooth function of $z$ and the derivative is given by

$\nabla_{w}\alpha_{z}A(\phi,\psi)\big{|}_{z=0}=i[\sigma(w,R),A](\phi,\psi)=:\nabla_{w}A(\phi,\psi),$
(3)

where the commutator of quadratic form $A$ and a continuous linear operator
$T:{\mathscr{S}}({\mathbb{R}}^{d})\to{\mathscr{S}}({\mathbb{R}}^{d})$ is the
form $[T,A]=A(\,\cdot\,,T\,\cdot\,)-A(T\,\cdot\,,\,\cdot\,)$. We use the
shorthand $\partial_{j}A=\nabla_{e_{j}}$, $j=1,\ldots,2d$, where $e_{j}$
denotes the $j$th basis vector of ${\mathbb{R}}^{2d}$. The so defined
quadratic forms are called the (phase space) derivatives of $A$. We define
higher order derivatives $\partial^{\gamma}A$,
$\gamma\in{\mathbb{N}}_{0}^{2d}$, in a similar way (which are then given by
nested commutators).

The above also makes sense for continuous $\mathcal{B}({\mathcal{K}})$-valued
quadratic forms on ${\mathscr{S}}({\mathbb{R}}^{d})$, i.e., continuous sesqui-
linear mappings
${\mathscr{S}}({\mathbb{R}}^{d})\times{\mathscr{S}}({\mathbb{R}}^{d})\to\mathcal{B}({\mathcal{K}})$,
where $\mathcal{B}({\mathcal{K}})$ denotes the algebra of bounded operators on
${\mathcal{K}}$. The space of vector-valued Schwartz functions
${\mathscr{S}}({\mathbb{R}}^{d};{\mathcal{K}})$, with ${\mathcal{K}}$ being a
separable Hilbert space, contains those functions
$\psi:{\mathbb{R}}^{d}\to{\mathcal{K}}$ such that
$\langle\psi(\,\cdot\,),\xi\rangle_{\mathcal{K}}\in{\mathscr{S}}({\mathbb{R}}^{d})$
for all $\xi\in{\mathcal{K}}$. An equivalent definition is that
${\mathscr{S}}({\mathbb{R}}^{d};{\mathcal{K}})={\mathscr{S}}({\mathbb{R}}^{d})\otimes{\mathcal{K}}$
(note that ${\mathscr{S}}({\mathbb{R}}^{d})$ is a nuclear Fréchet space so
that the tensor product is uniquely defined [10, Ch. 50]). This equivalence is
of course established by $(\psi\otimes\xi)(x)=\psi(x)\xi$. An operator valued
quadratic form is hermitian if $A(\psi,\psi)$ is an hermitian operator for all
$\psi\in{\mathscr{S}}({\mathbb{R}}^{d})$. For quadratic forms on
${\mathscr{S}}({\mathbb{R}}^{d})$ we write $\lVert A\rVert=\sup\lVert
A(\phi,\psi)\rVert$ where the supremum is over all pairs of Schwartz functions
with unit $L^{2}$-norm. The criterion that we want to apply is the following:

######  Lemma 2 ([1, Thm. 20]).

Let ${\mathcal{K}}$ be a separable Hilbert space. Let $A$ be a hermitian
$\mathcal{B}({\mathcal{K}})$-valued continuous quadratic form on
${\mathscr{S}}({\mathbb{R}}^{d})$ satisfying

$\lVert\partial_{j}A-\alpha_{z}(\partial_{j}A)\rVert\leq c(1+\lvert
z\rvert),\quad\forall j=1,\ldots,2d,$ (4)

for some $c>0$. Then there is an essentially self-adjoint operator $\hat{A}$
on $L^{2}({\mathbb{R}}^{d};{\mathcal{K}})$ with domain
${\mathscr{S}}({\mathbb{R}}^{d};{\mathcal{K}})$ so that
$\langle\hat{A}\psi\otimes v,\phi\otimes
w\rangle_{L_{2}({\mathbb{R}}^{d};{\mathcal{K}})}=\langle
A(\psi,\phi)\xi,\eta\rangle_{\mathcal{K}}$ for all
$\psi,\phi\in{\mathscr{S}}({\mathbb{R}}^{d})$ and $\xi,\eta\in{\mathcal{K}}$.

In particular, the criterion is fulfilled if
$\lVert\partial^{\gamma}A\rVert<\infty$ for all multi-indices $\alpha$ with
$\lvert\alpha\rvert=2$ [1]. Roughly speaking, Eq. 4 is the condition that the
first-order derivatives of $A$ have bounded oscillation.

We now return to pseudodifferential operators. For every tempered distribution
$f\in{\mathscr{S}}^{\prime}({\mathbb{R}}^{2d};\mathcal{B}({\mathcal{K}}))$,
the Weyl pseudodifferential operator $\mathrm{op}^{w}(f)$ makes sense as a
continuous quadratic form on ${\mathscr{S}}({\mathbb{R}}^{d})$. If we define
$\alpha_{z}f=f(\,\cdot\,+z)$ as the phase space shift of a function or
tempered distribution, we get symbolical covariance in the sense that
$\alpha_{z}\mathrm{op}^{w}(f)=\mathrm{op}^{w}(\alpha_{z}f)$,
$z\in{\mathbb{R}}^{2d}$, where the left-hand side is defined in the sense of
quadratic forms as above. With this, one can see [1] that $\mathrm{op}^{w}$
intertwines the quadratic form derivative (see Eq. 3) with the distributional
derivative on ${\mathscr{S}}^{\prime}({\mathbb{R}}^{2d})$:

$\partial^{\gamma}\mathrm{op}^{w}(f)=\mathrm{op}^{w}(\partial^{\gamma}f).$ (5)

The same holds for operator-valued tempered distributions if we replace
${\mathscr{S}}^{\prime}({\mathbb{R}}^{2d})$ by
${\mathscr{S}}^{\prime}({\mathbb{R}}^{2d};\mathcal{B}({\mathcal{K}}))\equiv{\mathscr{S}}^{\prime}({\mathbb{R}}^{2d})\otimes\mathcal{B}({\mathcal{K}})$
(note that ${\mathscr{S}}^{\prime}({\mathbb{R}}^{2d})$ is nuclear so that this
is well-defined). With this we can now restate 2 for $A=\mathrm{op}^{w}(f)$
as:

######  Lemma 3.

Let $f\in{\mathscr{S}}^{\prime}({\mathbb{R}}^{2d};\mathcal{B}({\mathcal{K}}))$
be a hermitian operator-valued tempered distribution whose first-order
distributional derivatives are such that

$\big{\lVert}\mathrm{op}^{w}(\partial_{j}f-\partial_{j}f(\,\cdot\,+z))\big{\rVert}\leq
c(1+\lvert z\rvert)\quad\forall j=1,\ldots,2d,$ (6)

for some $c>0$. Then
$\mathrm{op}^{w}(f):{\mathscr{S}}({\mathbb{R}}^{s};{\mathcal{K}})\to
L^{2}({\mathbb{R}}^{d};{\mathcal{K}})$ is essentially self-adjoint. In
particular, this holds if the second-order derivatives satisfy
$\lVert\mathrm{op}^{w}(\partial_{i}\partial_{j}f)\rVert<\infty$ for all
$i,j=1,\ldots,2d$.

The condition in Eq. 6, which is essentially a bound on the oscillation of
$\nabla f$, can now be checked using Calderón-Vaillancourt type theorems. With
the theorem [2, Thm. 2.73] we obtain 1 as a corollary of 3 and with its
operator-valued version [9, Thm. A.6] we obtain the analogue of 1 for
operator-valued symbols. One can use more general symbol classes that yield
bounded Weyl pseudodifferential operators, such as Sjöstrand’s class
$M_{\infty,1}$. We do not want to give the precise definition of this class
here, instead we refer to the literature, e.g. [8, Sec. 3] or [3, Thm. 1.1]
for the scalar valued and [11, Cor. 4.9] for the operator valued case.
Instead, we simply want to emphazise that membership in $M_{\infty,1}$ does
not need any form of continuity. Further, $M_{\infty,1}$ contains some well-
known symbol spaces such as the Calderón-Vaillancourt class and the Hölder-
Zygmund classes $\Lambda^{s}({\mathbb{R}}^{2d})$ for $s>2d$, see [3, Prop.
3.6]. Applying the Calderón-Vaillancourt theorem for $M_{\infty,1}$ symbols
yields our final result:

######  Theorem 4.

Let ${\mathcal{K}}$ be a separable Hilbert space. Let
$f\in{\mathscr{S}}^{\prime}({\mathbb{R}}^{2d};\allowbreak\mathcal{B}({\mathcal{K}}))$
be a hermitian-operator valued symbol such that the $\partial^{\alpha}f\in
M_{\infty,1}({\mathbb{R}}^{2d};\allowbreak\mathcal{B}({\mathcal{K}}))$ for all
$|\alpha|=2$.

Then $\mathrm{op}^{w}(f)$ is an essentially self-adjoint operator on
$L^{2}({\mathbb{R}}^{d};{\mathcal{K}})$ with domain
${\mathscr{S}}({\mathbb{R}}^{d};{\mathcal{K}})$.

######  Remark.

The interested reader might wonder if our main result is possibly also
obtainable as a consequence of Nelson’s commutator theorem [7, Thm. X.37], by
comparing with the harmonic oscillator. Indeed, this is one ingredient used in
the proof of Lemma 2 in [1]. Given the fact that the Weyl quantization is not
order-preserving, it seems necessary to the authors to pass from
$\mathrm{op}^{w}(f)$ to $\mathrm{op}^{w}(\widetilde{f})$ when wanting to apply
the commutator theorem, where $\widetilde{f}$ is the _heat transform_ of $f$
at a suitable time. The analysis of this is exactly what has been done in [1].
Nevertheless, there the main result was formulated as a result on Toeplitz
operators on the Segal-Bargmann space. Since such operators are unitarily
equivalent to Weyl pseudodifferential operators with heat-transformed symbols,
the results of [1] can also be understood as results on Weyl
pseudodifferential operators. The phase space formalism presented there and
also in this paper should not be seen as a necessity to obtain our main
result, but as a very convenient framework to work within.

## References

  * [1] W. Bauer, L. van Luijk, A. Stottmeister, and R. F. Werner.  Self-adjointness of Toeplitz operators in the Segal-Bargmann space.  J. Funct. Anal., 284:109778, 2023.
  * [2] G. B. Folland.  Harmonic Analysis in Phase Space. (AM-122).  Princeton University Press, 1989.
  * [3] K. Gröchenig and C. Heil.  Modulation spaces and pseudodifferential operators.  Integr. equ. oper. theory, 34:439–457, 1999.
  * [4] T. Ichinose and T. Tsuchida.  On essential selfadjointness of the Weyl quantized relativistic Hamiltonian.  Forum Math., 5(5):539–560, 1993.
  * [5] M. Nagase and T. Umeda.  On the essential self-adjointness of pseudo-differential operators.  Proc. Japan Acad. Ser. A Math. Sci., 64(4), 1988.
  * [6] F. Qihong.  On the essential self-adjointness of pseudodifferential operators.  Acta Math. Sin., 10(1):72–79, 1994.
  * [7] M. Reed and B. Simon.  Methods of Modern Mathematical Physics 2: Fourier Analysis, Self-Adjointness.  Academic Press, 1975.
  * [8] J. Sjöstrand.  An algebra of pseudodifferential operators.  Math. Res. Lett., 1:185–192, 1994.
  * [9] S. Teufel.  Adiabatic perturbation theory in quantum dynamics.  Springer Science & Business Media, 2003.
  * [10] F. Treves.  Topological Vector Spaces, Distributions and Kernels.  Academic Press, 1967.
  * [11] P. Wahlberg.  Vector-valued Modulation Spaces and Localization Operators with Operator-valued Symbols.  Integr. equ. oper. theory, 59:99–128, 2007.
  * [12] M. Yamazaki.  The essential self-adjointness of pseudodifferential operators associated with non-elliptic Weyl symbols with large potentials.  Osaka J. Math., 29(2):175–202, 1992.
  * [13] C. Zhu and J. R. Klauder.  Classical symptoms of quantum illnesses.  Amer. J. Phys., 61(7):605–611, 1993.

Robert Fulsche
✉<EMAIL_ADDRESS>
Institut für Analysis
Leibniz Universität Hannover
Welfengarten 1
30167 Hannover
GERMANY

Lauritz van Luijk
✉<EMAIL_ADDRESS>
Institut für Theoretische Physik
Leibniz Universität Hannover
Appelstraße 2
30167 Hannover
GERMANY