thus, Assumption (A5) only holds when $\gamma_{T}=1-o(1)$ for which the
vanishing fairness regret guarantee is attainable. Figure 12 provides a
summary of the connection between the fairness regret under scenarios 1 and 2
and Assumption (A5).

Figure 12. Assumption (A5) and fairness regret (8) under scenarios 1 and 2.

∎

##  Appendix C Proof of Theorem 2

###### Proof.

Note that $\Psi_{\alpha,t}:\Theta\times\mathcal{X}\to\mathbb{R}$ is the
function given by

(73)
$\displaystyle\Psi_{\alpha,t}({\boldsymbol{\theta}},{\boldsymbol{x}})=\left(-F_{\alpha}\right)^{\star}({\boldsymbol{\theta}})-{\boldsymbol{\theta}}\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}),$

where $F_{\alpha}:\mathcal{U}\to\mathbb{R}$ is an $\alpha$-fairness function
(3). From Lemma 4, OGD operating over the set $\Theta$ under the
$\frac{u_{\star,\min}^{1+1/\alpha}}{\alpha}$-strongly convex (Lemma 5) cost
functions
$\Psi_{\alpha,t}(\underline{{\boldsymbol{\theta}}_{t}},{\boldsymbol{x}}_{t})$
has the following regret guarantee against any fixed
${\boldsymbol{\theta}}\in\Theta$

(74)
$\displaystyle\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{t})-\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}},{\boldsymbol{x}}_{t})$
$\displaystyle\leq\frac{1}{T}\,\cdot\,\underset{\mathfrak{R}_{T,\Theta}}{\underbrace{\frac{1}{2}\sum^{T}_{t=1}\frac{\alpha}{u_{\star,\min}^{1+1/\alpha}t}\left\lVert{\boldsymbol{g}}_{\Theta,t}\right\rVert^{2}_{2}}},$

From Lemma 3, it holds

(75)
$\displaystyle\min_{{\boldsymbol{\theta}}\in\Theta}\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}},{\boldsymbol{x}}_{t})$
$\displaystyle=F_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})\right).$

Combine Eq. (74) and Eq. (75) to obtain the lower bound

(76)
$\displaystyle{F_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})\right)}+\frac{\mathfrak{R}_{T,\Theta}}{T}\geq{\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{t})}.$

From Lemma 4, OGD operating over the set $\mathcal{X}$ under the reward
functions $\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}})$ has
the following regret guarantee for any fixed
${\boldsymbol{x}}_{\star}\in\mathcal{X}$:

(77)
$\displaystyle\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{\star})-\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{t})\leq\frac{1}{T}\,\cdot\,\underset{\mathfrak{R}_{T,\mathcal{X}}}{\underbrace{1.5\,\mathrm{diam}\left(\mathcal{X}\right)\sqrt{\sum_{t\in\mathcal{T}}\left\lVert{\boldsymbol{g}}_{\mathcal{X},t}\right\rVert^{2}_{2}}}},$

Hence, we have the following

$\displaystyle{\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{t})}+\frac{\mathfrak{R}_{T,\mathcal{X}}}{T}\geq{\frac{1}{T}\sum^{T}_{t=1}\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{\star})}$
$\displaystyle={\frac{1}{T}\sum^{T}_{t=1}F^{\star}({\boldsymbol{\theta}}_{t})-\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{\theta}}_{t}\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}$
Replace $\Psi_{\alpha,t}({\boldsymbol{\theta}}_{t},{\boldsymbol{x}}_{\star})$
using Eq. (73)
$\displaystyle\geq{F^{\star}\left(\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{\theta}}_{t}\right)-\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{\theta}}_{t}\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}$
Jensen’s inequality & convexity of $F^{\star}$
$\displaystyle\geq{F^{\star}\left(\bar{{\boldsymbol{\theta}}}\right)-\bar{{\boldsymbol{\theta}}}\cdot\left(\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})\right)}-{\frac{1}{T}\sum^{T}_{t=1}({\boldsymbol{\theta}}_{t}-\bar{{\boldsymbol{\theta}}})\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}$
$\displaystyle\geq\min_{{\boldsymbol{\theta}}\in\Theta}\left\\{{F^{\star}\left({{\boldsymbol{\theta}}}\right)-{{\boldsymbol{\theta}}}\cdot\left(\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})\right)}\right\\}-{\frac{1}{T}\sum^{T}_{t=1}({\boldsymbol{\theta}}_{t}-\bar{{\boldsymbol{\theta}}})\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}$
(78)
$\displaystyle=F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right)-{\frac{1}{T}\sum^{T}_{t=1}\left({\boldsymbol{\theta}}_{t}-\bar{{\boldsymbol{\theta}}}\right)\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}.$

We combine the above equation and Eq. (76) to obtain

$\displaystyle{F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right)-F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})}\right)}$
$\displaystyle\leq{\frac{\mathfrak{R}_{T,\mathcal{X}}}{T}+\frac{\mathfrak{R}_{T,\Theta}}{T}+{\frac{1}{T}\sum^{T}_{t=1}\left({\boldsymbol{\theta}}_{t}-\bar{\boldsymbol{\theta}}\right)\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}}$
(79)
$\displaystyle={\frac{\mathfrak{R}_{T,\mathcal{X}}}{T}+\frac{\mathfrak{R}_{T,\Theta}}{T}}+\underset{\Sigma}{\underbrace{{\frac{1}{T}\sum^{T}_{t=1}\left(\bar{\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{t}\right)\cdot{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})}}}$

We provide two approaches to bound the r.h.s. term $\Sigma$ in Eq. (81), and
this gives the two conditions in Assumption (A5):

Bound 1. We can bound the r.h.s. term $\Sigma$ in the above equation as
follows

(80) $\displaystyle\Sigma$
$\displaystyle={\bar{\boldsymbol{\theta}}\cdot\sum^{T}_{t=1}{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})}-{{\sum^{T}_{t=1}{\boldsymbol{\theta}}_{t}\cdot{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})}}={-{\sum^{T}_{t=1}{\boldsymbol{\theta}}_{t}\cdot{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})}}$
(81)
$\displaystyle\leq\frac{1}{u_{\star,\min}}{\sum_{i\in\mathcal{I}}\sum^{T}_{t=1}\delta_{t,i}({\boldsymbol{x}}_{\star})\mathds{1}_{\left\\{\delta_{t,i}({\boldsymbol{x}}_{\star})\geq
0\right\\}}}=\operatorname{\mathcal{O}}\left(\mathbb{V}_{\mathcal{T}}\right).$

Bound 2. We alternatively bound $\Sigma$ as follows

$\displaystyle\Sigma$
$\displaystyle={\sum^{K}_{k=1}\sum_{t\in\mathcal{T}_{k}}\left(\bar{\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{t}\right)\cdot{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})}={\sum^{K}_{k=1}\sum_{t\in\mathcal{T}_{k}}\left(\bar{\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\min\left(\mathcal{T}_{k}\right)}\right)\cdot{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})+\sum^{K}_{k=1}\sum_{t\in\mathcal{T}_{k}}\left({\boldsymbol{\theta}}_{\min\left(\mathcal{T}_{k}\right)}-{\boldsymbol{\theta}}_{t}\right)\cdot{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})}$
(82)
$\displaystyle\leq\Delta_{\alpha}\sum^{K}_{k=1}\left\lVert\sum_{t\in\mathcal{T}_{k}}{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})\right\rVert_{1}+{u_{\max}\sum^{K}_{k=1}\sum_{t\in\mathcal{T}_{k}}\left\lVert{\boldsymbol{\theta}}_{\min\left(\mathcal{T}_{k}\right)}-{\boldsymbol{\theta}}_{t}\right\rVert_{1}},$

where
$\Delta_{\alpha}=\max\left\\{\left\lVert{\boldsymbol{\theta}}-{\boldsymbol{\theta}}^{\prime}\right\rVert_{\infty}:{\boldsymbol{\theta}},{\boldsymbol{\theta}}^{\prime}\in\Theta\right\\}$.
We bound the term
$\sum^{K}_{k=1}\sum_{t\in\mathcal{T}_{k}}\left\lVert{\boldsymbol{\theta}}_{\min\left(\mathcal{T}_{k}\right)}-{\boldsymbol{\theta}}_{t}\right\rVert_{1}$
in the above equation as

(83)
$\displaystyle\sum^{K}_{k=1}\sum_{t\in\mathcal{T}_{k}}\left\lVert{\boldsymbol{\theta}}_{\min\left(\mathcal{T}_{k}\right)}-{\boldsymbol{\theta}}_{t}\right\rVert_{1}$
$\displaystyle\leq
L_{\Theta}\sum^{K}_{k=1}\eta_{\Theta,\,{\min\left(\mathcal{T}_{k}\right)}}\sum_{t\in\mathcal{T}_{k}}(t-\min\left(\mathcal{T}_{k}\right))\leq
L_{\Theta}\sum^{K}_{k=1}\eta_{\Theta,\,{\min\left(\mathcal{T}_{k}\right)}}\left|\mathcal{T}_{k}\right|^{2}$
(84)
$\displaystyle=L_{\Theta}\frac{u_{\star,\min}^{1+\frac{1}{\alpha}}}{\alpha}\sum^{K}_{k=1}\frac{\left|\mathcal{T}_{k}\right|^{2}}{\min\left(\mathcal{T}_{k}\right)},$

and replacing this upper-bound in Eq. (82) gives

(85)
$\displaystyle\Sigma\leq\Delta_{\alpha}\sum^{K}_{k=1}\left\lVert\sum_{t\in\mathcal{T}_{k}}{\boldsymbol{\delta}}_{t}({\boldsymbol{x}}_{\star})\right\rVert_{1}+u_{\max}L_{\Theta}\frac{\alpha}{u_{\star,\min}^{1+\frac{1}{\alpha}}}\sum^{K}_{k=1}\frac{\left|\mathcal{T}_{k}\right|^{2}}{\underset{\sum_{k^{\prime}<k}\left|\mathcal{T}_{k}\right|+1}{\underbrace{\min\left(\mathcal{T}_{k}\right)}}}=\operatorname{\mathcal{O}}\left(\mathbb{W}_{\mathcal{T}}\right).$

We combine Eq. (81), Eq. (85), and Eq. (79) to obtain

(86)
$\displaystyle\mathfrak{R}_{T}\left(F_{\alpha},{\boldsymbol{\mathcal{A}}}\right)$
$\displaystyle\leq\sup_{\left\\{{\boldsymbol{u}}_{t}\right\\}^{T}_{t=1}\in{{\mathcal{U}^{T}}}}\left\\{\frac{1}{T}\left({\mathfrak{R}_{T,\mathcal{X}}+\mathfrak{R}_{T,\Theta}}\right)\right\\}+\operatorname{\mathcal{O}}\left(\frac{\min\left\\{\mathbb{V}_{\mathcal{T}},\mathbb{W}_{\mathcal{T}}\right\\}}{T}\right)$
(87)
$\displaystyle\leq\sup_{\left\\{{\boldsymbol{u}}_{t}\right\\}^{T}_{t=1}\in{{\mathcal{U}^{T}}}}\left\\{\frac{1}{T}\left({1.5\,\mathrm{diam}\left(\mathcal{X}\right)\sqrt{\sum_{t\in\mathcal{T}}\left\lVert{\boldsymbol{g}}_{\mathcal{X},t}\right\rVert^{2}_{2}}+\frac{\alpha}{u_{\star,\min}^{1+\frac{1}{\alpha}}}\sum^{T}_{t=1}\frac{\left\lVert{\boldsymbol{g}}_{\Theta,t}\right\rVert^{2}_{2}}{t}}\right)\right\\}+\operatorname{\mathcal{O}}\left(\frac{\min\left\\{\mathbb{V}_{\mathcal{T}},\mathbb{W}_{\mathcal{T}}\right\\}}{T}\right).$

The following upper bounds hold

$\displaystyle\left\lVert{\boldsymbol{g}}_{\Theta,t}\right\rVert_{2}$
$\displaystyle=\left\lVert\left(\frac{1}{\left(-\theta_{t,i}\right)^{1/\alpha}}-\left({\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})\right)\right)_{i\in\mathcal{I}}\right\rVert_{2}\leq\sqrt{I}\max\left\\{\frac{1}{u_{\star,\min}^{1/\alpha}}-u_{\min},u_{\max}-\frac{1}{u_{\star,\max}^{1/\alpha}}\right\\}=L_{\Theta},$
$\displaystyle\left\lVert{\boldsymbol{g}}_{\mathcal{X},t}\right\rVert_{2}$
$\displaystyle={\left\lVert{\boldsymbol{\theta}}_{t}\cdot\partial_{{\boldsymbol{x}}}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})\right\rVert}_{2}\leq\frac{1}{u_{\star,\min}^{\alpha}}\left\lVert\partial_{{\boldsymbol{x}}}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})\right\rVert_{2}\leq\frac{L_{\mathcal{X}}}{u_{\star,\min}^{\alpha}}.$

Thus, the regret bound in Eq. (87) can be upper bounded as

$\displaystyle\mathfrak{R}_{T}\left(F_{\alpha},{\boldsymbol{\mathcal{A}}}\right)$
$\displaystyle=\frac{1}{T}\sup_{\left\\{{\boldsymbol{u}}_{t}\right\\}^{T}_{t=1}\in{{\mathcal{U}^{T}}}}\left\\{{{1.5\,\mathrm{diam}\left(\mathcal{X}\right)\frac{L_{\mathcal{X}}\sqrt{T}}{u_{\star,\min}^{\alpha}}+\frac{\alpha}{u_{\star,\min}^{1+\frac{1}{\alpha}}}\sum^{T}_{t=1}\frac{L^{2}_{\Theta}}{t}}}\right\\}+\frac{\min{\left\\{\mathbb{V}_{\mathcal{T}},\mathbb{W}_{\mathcal{T}}\right\\}}}{T}$
$\displaystyle\leq\frac{1}{T}\sup_{\left\\{{\boldsymbol{u}}_{t}\right\\}^{T}_{t=1}\in{{\mathcal{U}^{T}}}}\left\\{{1.5\,\mathrm{diam}\left(\mathcal{X}\right)\frac{L_{\mathcal{X}}\sqrt{T}}{u_{\star,\min}^{\alpha}}+\frac{\alpha}{u_{\star,\min}^{1+\frac{1}{\alpha}}}L^{2}_{\Theta}(\log(T)+1)}\right\\}+\frac{\min{\left\\{\mathbb{V}_{\mathcal{T}},\mathbb{W}_{\mathcal{T}}\right\\}}}{T}$
$\displaystyle=\operatorname{\mathcal{O}}\left(\frac{1}{\sqrt{T}}+\frac{\min\left\\{\mathbb{V}_{\mathcal{T}},\mathbb{W}_{\mathcal{T}}\right\\}}{T}\right).$

This concludes the proof. ∎

##  Appendix D Proof of Theorem 3 (Lower Bound)

###### Proof.

Consider a scenario with a single player $\mathcal{I}=\\{1\\}$,
$\mathcal{X}=\left\\{x\in\mathbb{R},\left|x\right|\leq 1\right\\}$, and the
utility selected by an adversary at time slot $t\in\mathcal{T}$ is given by

(88) $\displaystyle
u_{t}(x)=w_{t}x+1,\quad\text{where}~{}w_{t}\in\left\\{-1,+1\right\\}.$

The weight $w_{t}$ is selected in $\\{-1,+1\\}$ uniformly at random for
$t\in\mathcal{T}$. A policy $\mathcal{A}$ selects the sequence of decisions
$\left\\{x_{t}\right\\}^{T}_{t=1}$ and has the following fairness regret

$\displaystyle\mathbb{E}\left[\max_{x\in\mathcal{X}}f_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}u_{t}(x)\right)-f_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}u_{t}(x_{t})\right)\right]\geq\mathbb{E}\left[\max_{x\in\mathcal{X}}f_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}u_{t}(x)\right)\right]-\underset{\text{$=0$}}{\underbrace{f_{\alpha}\left(\mathbb{E}\left[\frac{1}{T}\sum^{T}_{t=1}u_{t}(x_{t})\right]\right)}}$
$\displaystyle=\mathbb{E}\left[f_{\alpha}\left(\max_{x\in\mathcal{X}}\frac{1}{T}\sum^{T}_{t=1}u_{t}(x)\right)\right]=\mathbb{E}\left[f_{\alpha}\left(\frac{1}{T}\left|\sum^{T}_{t=1}w_{t,1}\right|+1\right)\right]\stackrel{{\scriptstyle\mathrm{(a)}}}{{\geq}}{\mathbb{E}\left[\frac{1}{T}\left|\sum^{T}_{t=1}w_{t,1}\right|\right]}\left(\frac{2^{1-\alpha}-1}{1-\alpha}\right)\stackrel{{\scriptstyle\mathrm{(b)}}}{{\geq}}\frac{\left(\frac{2^{1-\alpha}-1}{1-\alpha}\right)}{\sqrt{2T}}$
$\displaystyle=\Omega\left(\frac{1}{\sqrt{T}}\right).$

Inequality (a) is obtained considering $f_{\alpha}(x+1)$ is concave in $x$,
$f_{\alpha}(0+1)=0$, and $f_{\alpha}(x+1)\geq f_{\alpha}(2)x$ for $x\in[0,1]$.
Inequality (b) is obtained through Khintchine inequality. A lower bound on the
fairness regret (8) can be established:

(89)
$\displaystyle\mathfrak{R}_{T}\left(F_{\alpha},{\boldsymbol{\mathcal{A}}}\right)\geq\mathbb{E}\left[\max_{x\in\mathcal{X}}f_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}u_{t}(x)\right)-f_{\alpha}\left(\frac{1}{T}\sum^{T}_{t=1}u_{t}(x_{t})\right)\right]=\Omega\left(\frac{1}{\sqrt{T}}\right).$

This concludes the proof. ∎

##  Appendix E Proof of Corollary 7

###### Proof.

Expected regret. When the utilities are i.i.d., we have the following

(90)
$\displaystyle\mathbb{E}\left[{\boldsymbol{u}}_{t}({\boldsymbol{x}})\right]={\boldsymbol{u}},\forall
t\in\mathcal{T},$

for some fixed utility ${\boldsymbol{u}}\in\mathcal{U}$. In the proof Theorem
C, in particular, in Eq. (79) it holds

(91)
$\displaystyle{F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right)-F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})}\right)}$
$\displaystyle\leq{\frac{\mathfrak{R}_{T,\mathcal{X}}}{T}+\frac{\mathfrak{R}_{T,\Theta}}{T}+{\frac{1}{T}\sum^{T}_{t=1}\left({\boldsymbol{\theta}}_{t}-\bar{\boldsymbol{\theta}}\right)\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}}.$

Taking the expectation of both sides gives

(92)
$\displaystyle\mathbb{E}\left[F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right)-F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})}\right)\right]\leq\mathbb{E}\left[\frac{\mathfrak{R}_{T,\mathcal{X}}}{T}+\frac{\mathfrak{R}_{T,\Theta}}{T}\right]+\mathbb{E}\left[{\frac{1}{T}\sum^{T}_{t=1}\left({\boldsymbol{\theta}}_{t}-\bar{\boldsymbol{\theta}}\right)\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right].$

The variables ${\boldsymbol{\theta}}_{t}$ and ${\boldsymbol{u}}_{t}$ are
independent for $t\in\mathcal{T}$, thus we have

(93)
$\displaystyle\mathbb{E}\left[{\frac{1}{T}\sum^{T}_{t=1}\left({\boldsymbol{\theta}}_{t}-\bar{\boldsymbol{\theta}}\right)\cdot{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right]=\mathbb{E}\left[{\left(\bar{\boldsymbol{\theta}}-\bar{\boldsymbol{\theta}}\right)\cdot{\boldsymbol{u}}({\boldsymbol{x}}_{\star})}\right]=0.$

Through Eq. (C), it holds

(94)
$\displaystyle\mathbb{E}\left[F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{\star})}\right)-F_{\alpha}\left({\frac{1}{T}\sum^{T}_{t=1}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})}\right)\right]=\operatorname{\mathcal{O}}\left(\frac{1}{\sqrt{T}}\right).$

This concludes the first part of the proof.

Almost-sure zero-regret. Let $\Delta=\left(u_{\max}-u_{\min}\right)$,
$\mathcal{T}=\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\dots\cup\mathcal{T}_{K}$
where $K=T^{2/3}$ and $\left|\mathcal{T}_{k}\right|=\kappa=T^{1/3}$ for
$k\in\left\\{1,2,\dots,K\right\\}$, and let $\beta\in(0,1/6)$. Employing
Hoeffding’s inequality we can bound the l.h.s. term in Eq. (9) for
$i\in\mathcal{I}$ as

(95)
$\displaystyle\mathbb{P}\left(\left|\sum_{t\in\mathcal{T}_{k}}\delta_{t,i}({\boldsymbol{x}})\right|\leq\Delta
T^{1/6+\beta}\right)$ $\displaystyle\geq
1-2\exp\left(\frac{-2T^{1/3+2\beta}}{\left((T-\kappa)\kappa^{2}/T^{2}+\kappa(\kappa/T-1)^{2}\right)}\right)=1-2\exp\left(\frac{-2T^{1/3+2\beta}}{\left(\kappa-\kappa^{2}/T\right)}\right)$
(96)
$\displaystyle=1-2\exp\left(\frac{-2T^{1/3+2\beta}}{\left(T^{1/3}-T^{-1/3}\right)}\right).$

Hence, it follows

$\displaystyle\mathbb{P}\left(\sum^{K}_{k=1}\sum_{i\in\mathcal{I}}\left|\sum_{t\in\mathcal{T}_{k}}\delta_{t,i}({\boldsymbol{x}})\right|\leq\Delta
T^{5/6+\beta}\right)$
$\displaystyle\geq\left(1-2\exp\left(\frac{-2T^{1/3+2\beta}}{\left(T^{1/3}-2T^{-1/3}\right)}\right)\right)^{IT^{2/3}}$
$\displaystyle\geq
1-2IT^{2/3}\exp\left(\frac{-2T^{1/3+2\beta}}{\left(T^{1/3}-T^{-1/3}\right)}\right)$
Bernoulli’s inequality $\displaystyle\geq
1-2IT^{2/3}\exp\left(\frac{-2T^{1/3+2\beta}}{{T^{1/3}}}\right)$
$\displaystyle\geq 1-2IT^{2/3}\exp(-2T^{2\beta}).$

It follows from the above equation paired with Eq. (9)

(97)
$\displaystyle\mathbb{W}_{\mathcal{T}}=\operatorname{\mathcal{O}}\left(T^{5/6+\beta}+T^{2/3}\right)=\operatorname{\mathcal{O}}\left(T^{5/6+\beta}\right),\qquad\text{w.p.}\qquad
p\geq 1-2IT^{2/3}\exp(-2T^{2\beta}).$

Thus, for any $\beta\in(0,1/6)$ and $T\to\infty$, it holds

(98) $\displaystyle\frac{\mathbb{W}_{\mathcal{T}}}{T}\leq
0,\qquad\text{w.p.}\qquad p\geq 1.$

Note that given that $\mathbb{W}_{\mathcal{T}}\geq 0$ in Eq. (10), it holds
$\lim_{T\to\infty}\mathbb{W}_{\mathcal{T}}=0$ w.p. $p=1$. Therefore, it
follows from Theorem C for $T\to\infty$

(99)
$\displaystyle\mathfrak{R}_{T}\left(F_{\alpha},{\boldsymbol{\mathcal{A}}}\right)=\operatorname{\mathcal{O}}\left(\frac{1}{\sqrt{T}}+\frac{\min\left\\{\mathbb{V}_{\mathcal{T}},\mathbb{W}_{\mathcal{T}}\right\\}}{T}\right)=\operatorname{\mathcal{O}}\left(\frac{1}{\sqrt{T}}+\frac{\mathbb{W}_{\mathcal{T}}}{T}\right)\leq
0,\qquad\text{w.p.}\qquad 1.$

This concludes the proof. ∎

##  Appendix F Additional Experimental Details

Table 2. Specification of the network topologies used in experiments. Topologies | $\left|\mathcal{C}\right|$ | $\left|\mathcal{E}\right|$ | $k_{c}$ | $\left|\mathcal{Q}_{i}\right|$ | $\left|\cup_{f\in\mathcal{F}}\Lambda_{f}(\mathcal{C})\right|$ | $w$ | Figure
---|---|---|---|---|---|---|---
Cycle | 3 | 3 | 5–5 | 1 | 1 | 1–2 |  Fig. 5 (a)
Tree-1–Tree-3 | 13 | 12 | 1–5 | 2–5 | 1 | 1–9 |  Fig. 5 (b)–(d)
Grid | 9 | 12 | 1–5 | 2 | 1 | 1–7 |  Fig. 5 (e)
Abilene | 12 | 13 | 1–5 | 2 | 2 | 1–8 |  Fig. 5 (f)
GEANT | 22 | 33 | 1–5 | 3 | 2 | 1–9 |  Fig. 5 (g)

(a) Stationary  (b) Non-Stationary

Figure 13. Request traces stationary (a) and non-stationary (b) configured
with $\sigma=1.2$, $T=5000$, $F=20$, $D=100$. Each dot indicates a requested
file.

##  Appendix G Departing and Arriving Agents

The system model in Section 3.3 supports departing and arriving agents.
Consider a population of agents $\mathcal{I}$, the system may only observe a
subset of the agents as the _participating_ agents,
$\mathcal{I}_{t}\subset\mathcal{I}$ at time $t$, and the utility of _absent_
agents is simply $u_{t,i}(\,\cdot\,)=0$. For example, in the extreme scenario
where a single agent $t\in\mathcal{T}$ is participating at a given time slot,
the long-term fairness objective (5) falls back to the slot-fairness objective
(4), i.e.,
$F_{\alpha}\left({\sum_{t\in\mathcal{T}}}{\boldsymbol{u}}_{t}({\boldsymbol{x}}_{t})\right)=\sum_{t\in\mathcal{T}}f_{\alpha}\left(u_{t,t}({\boldsymbol{x}}_{t})\right)$
where the fairness is ensured across the different agents arriving at
different timeslots $t\in\mathcal{T}$. It is easy to verify that even in the
case when the set of agents $\mathcal{I}$ is unknown to the controller in
advance, one could augment the dual space with an extra dimension each time a
new user appears, and the same guarantees hold.

##  Appendix H Time-Complexity of Algorithm 1

Algorithm 1 applied to the virtualized caching system application has a time
complexity $\operatorname{\mathcal{O}}\left(CF^{2}\right)$, where $C$ is
number of caches and $F$ is the number of files in the catalog; the most
expensive operation in Algorithm 1 is the projection step in line 8 that
corresponds to the Euclidean projection onto a capped simplex, and this can be
performed in $\operatorname{\mathcal{O}}\left(F^{2}\right)$ steps (Wang and
Lu, 2015) for each cache state. Despite the high time complexity ($F$ is
typically large), in practice solvers (e.g., CVXPY (Diamond and Boyd, 2016))
support _warm-start_ that speeds up the projection when the warm-start
parameters are close to the ones of obtained by the solution, and since
Algorithm 1 is iterative and the cache states do not severely change,
typically a lower computational cost is achieved. Moreover, the proposed
caching model in Section 6 supports request batching, where a batch includes
the requests arriving between two consecutive cache updates. Batching
amortizes the computational cost of the different policies, reducing the cost
per request by the batch size ($R_{t}$ at time slot $t$).


$\operatorname{ker}(\psi)=\bigcap_{i=1}^{k}\operatorname{ker}(\chi^{\prime}_{i}),$

where each $\chi^{\prime}_{i}$ is irreducible and
$\operatorname{deg}_{\mathbb{R}}(\chi^{\prime}_{i})\leq d$. This establishes
the reverse inclusion of (*). ∎

###  E.3 Symmetry regularization

Here we relate the general symmetry regularization terms $R_{g}$ and $S_{g}$
[Eqs. (21)-(22)] to the first and second regularization terms in Eq. (12) for
1D order observables. This will provide insight into how Eq. (20) generalizes
Eq. (12). We use the notation as in Eqs. (19)-(22).

First, however, we simplify the expression for $S_{g}$ [Eq. (22)] for
arbitrary order dimension $d$.

######  Lemma 8.

The regularization term $S_{g}$ [Eq. (22)] admits the expression

$S_{g}=1-\frac{\|ZZ^{+}Z_{g}\|_{F}^{2}}{\|Z_{g}\|_{F}^{2}}.$

###### Proof.

Recalling the expression [Eq. (19)] for the linear least squares estimator
$\hat{\psi}_{g}$, the squared residual is

$\displaystyle\|Z_{g}-Z\hat{\psi}_{g}\|_{F}^{2}$
$\displaystyle=\|Z_{g}-Z(Z^{+}Z_{g}+PA)\|_{F}^{2}$
$\displaystyle=\|Z_{g}-ZZ^{+}Z_{g}\|_{F}^{2}$
$\displaystyle=\|(I-ZZ^{+})Z_{g}\|_{F}^{2}.$

Since $I-ZZ^{+}$ is an orthogonal projection operator, then by the Pythagorean
Theorem we obtain

$\|Z_{g}-Z\hat{\psi}_{g}\|_{F}^{2}=\|Z_{g}\|_{F}^{2}-\|ZZ^{+}Z_{g}\|_{F}^{2},$

and thus

$S_{g}=1-\frac{\|ZZ^{+}Z_{g}\|_{F}^{2}}{\|Z_{g}\|_{F}^{2}},$

completing the proof. ∎

We now derive the simplified expressions for the regularization terms $R_{g}$
and $S_{g}$ for 1D order observables.

######  Proposition 9.

Let $d=1$. Then the regularization terms $R_{g}$ and $S_{g}$ [Eq. (21)-(22)]
admit the expressions

$\displaystyle R_{g}$
$\displaystyle=\left(1-\frac{\|Z_{g}\|^{2}}{\|Z\|^{2}}(1-S_{g})\right)^{2}$
$\displaystyle S_{g}$
$\displaystyle=1-\left(\frac{Z^{\top}Z_{g}}{\|Z\|\|Z_{g}\|}\right)^{2}.$

###### Proof.

We first consider $S_{g}$. By Lemma 8,

$S_{g}=1-\frac{\|ZZ^{+}Z_{g}\|^{2}}{\|Z_{g}\|^{2}},$

where we replaced the Frobenius matrix norm with the usual vector norm since
$Z$ and $Z_{g}$ are now $N$-dimensional column vectors. Since $ZZ^{+}$ is an
orthogonal projection operator, then $(ZZ^{+})^{\top}(ZZ^{+})=ZZ^{+}$ so that

$S_{g}=1-\frac{Z_{g}^{\top}ZZ^{+}Z_{g}}{\|Z_{g}\|^{2}}.$

Now unless the GE-encoder is exactly zero on every sampled lattice
configuration, $Z$ is a nonzero column vector and thus full-rank. Its
pseudoinverse is thus the row vector

$Z^{+}=\frac{Z^{\top}}{\|Z\|^{2}}.$

Substituting this into our expression for $S_{g}$, we obtain

$\displaystyle S_{g}$
$\displaystyle=1-\frac{Z_{g}^{\top}ZZ^{\top}Z_{g}}{\|Z\|^{2}\|Z_{g}\|^{2}}$
$\displaystyle=1-\left(\frac{Z^{\top}Z_{g}}{\|Z\|\|Z_{g}\|}\right)^{2},$

as claimed.

We now move to $R_{g}$. Since $Z$ is full-rank, then its null space is trivial
so that $P=0$. The estimator $\hat{\psi}_{g}$ [Eq. (19)] thus simplifies to

$\displaystyle\hat{\psi}_{g}$ $\displaystyle=Z^{+}Z_{g}+0$
$\displaystyle=\frac{Z^{\top}Z_{g}}{\|Z\|^{2}}$
$\displaystyle=\frac{\|Z_{g}\|}{\|Z\|}\cdot\frac{Z^{\top}Z_{g}}{\|Z\|\|Z_{g}\|}.$

Substituting this into Eq. (21) and noting $\hat{\psi}_{g}$ is a scalar, we
have

$\displaystyle R_{g}$ $\displaystyle=(1-\hat{\psi}_{g}^{2})^{2}$
$\displaystyle=\left(1-\frac{\|Z_{g}\|^{2}}{\|Z\|^{2}}\left(\frac{Z^{\top}Z_{g}}{\|Z\|\|Z_{g}\|}\right)^{2}\right)^{2}$
$\displaystyle=\left(1-\frac{\|Z_{g}\|^{2}}{\|Z\|^{2}}(1-S_{g})\right)^{2},$

completing the proof. ∎

Observe that the expressions for $R_{g}$ and $S_{g}$ in Prop. 9 match the
first and second regularization terms in Eq. (12), except for the factor
$(1-S_{g})$ in $R_{g}$. Even still, in the optimal case $S_{g}=0$, the
expression for $R_{g}$ matches the first regularization term in Eq. (12).

## References

  * Ashcroft and Mermin [1976] N. W. Ashcroft and N. D. Mermin,  _Solid State Physics_ (Holt-Saunders, 1976).
  * Friedli and Velenik [2017] S. Friedli and Y. Velenik,  _Statistical mechanics of lattice systems: a concrete mathematical introduction_ (Cambridge University Pres, 2017).
  * Gomez  _et al._ [2019] H. Gomez, M. Bures, and A. Moure, A review on computational modelling of phase-transition problems, Philos. Trans. Roy. Soc. A 377, 20180203 (2019).
  * Nagy  _et al._ [2013] Á. Nagy, M. Calixto, and E. Romera, A density Functional Theory View of Quantum Phase Transitions, J. Chem. Theory Comput. 9, 1068 (2013).
  * Wu  _et al._ [2006] L.-A. Wu, M. S. Sarandy, D. A. Lidar, and L. J. Sham, Linking entanglement and quantum phase transitions via density-functional theory, Phys. Rev. A 74, 052335 (2006).
  * Nagy and Romera [2013] A. Nagy and E. Romera, Quantum phase transitions via density-functional theory: Extension to the degenerate case, Phys. Rev. A 88, 042515 (2013).
  * Shahi  _et al._ [2018] C. Shahi, J. Sun, and J. P. Perdew, Accurate critical pressures for structural phase transitions of group IV, III-V, and II-VI compounds from the SCAN density functional, Phys. Rev. B 97, 094111 (2018).
  * Maurer  _et al._ [2019] R. J. Maurer, C. Freysoldt, A. M. Reilly, J. G. Brandenburg, O. T. Hofmann, T. Björkman, S. Lebègue, and A. Tkatchenko, Advances in Density-Functional Calculations for Materials Modeling, Ann. Rev. Mat. Res. 49, 1 (2019).
  * Haile [1992] J. M. Haile,  _Molecular dynamics simulation: elementary methods_ (John Wiley & Sons, Inc., 1992).
  * Sasaki  _et al._ [2020] R. Sasaki, Y. Hayashi, and S. Kawauchi, Acceleration of liquid-crystalline phase transition simulations using selectively scaled and returned molecular dynamics,  _Journal of Chemical Information and Modeling_ , J. Chem. Inf. Model. 60, 3499 (2020).
  * Shanavas and Sharma [2009] K. V. Shanavas and S. M. Sharma, Molecular dynamics simulations of phase transitions in argon-filled single-walled carbon nanotube bundles under high pressure, Phys. Rev. B 79, 155425 (2009).
  * Imada  _et al._ [1998] M. Imada, A. Fujimori, and Y. Tokura, Metal-insulator transitions, Rev. Mod. Phys. 70, 1039 (1998).
  * Johnston [2010] D. C. Johnston, The puzzle of high temperature superconductivity in layered iron pnictides and chalcogenides, Adv. in Phys. 59, 803 (2010).
  * Stewart [2017] G. R. Stewart, Unconventional superconductivity, Advances in Physics 66, 75 (2017).
  * Keimer  _et al._ [2015] B. Keimer, S. A. Kivelson, M. R. Norman, S. Uchida, and J. Zaanen, From quantum matter to high-temperature superconductivity in copper oxides, Nature 518, 179 (2015).
  * Zhou  _et al._ [2017] Y. Zhou, K. Kanoda, and T.-K. Ng, Quantum spin liquid states, Rev. Mod. Phys. 89, 025003 (2017).
  * Savary and Balents [2016] L. Savary and L. Balents, Quantum spin liquids: a review, Rep. Prog. Phys. 80, 016502 (2016).
  * Fradkin  _et al._ [2015] E. Fradkin, S. A. Kivelson, and J. M. Tranquada, Colloquium: Theory of intertwined orders in high temperature superconductors, Rev. Mod. Phys. 87, 457 (2015).
  * Maier  _et al._ [2005] T. A. Maier, M. Jarrell, T. C. Schulthess, P. R. C. Kent, and J. B. White, Systematic study of $d$-wave superconductivity in the 2D repulsive Hubbard model, Phys. Rev. Lett. 95, 237001 (2005).
  * Zheng  _et al._ [2017] B.-X. Zheng, C.-M. Chung, P. Corboz, G. Ehlers, M.-P. Qin, R. M. Noack, H. Shi, S. R. White, S. Zhang, and G. K.-L. Chan, Stripe order in the underdoped region of the two-dimensional Hubbard model, Science 358, 1155 (2017).
  * Jiang and Devereaux [2019] H.-C. Jiang and T. P. Devereaux, Superconductivity in the doped Hubbard model and its interplay with next-nearest hopping $t^{\prime}$, Science 365, 1424 (2019).
  * Haldane [1983] F. Haldane, Continuum dynamics of the 1-D Heisenberg antiferromagnet: Identification with the O(3) nonlinear sigma model, Phys. Lett. A 93, 464 (1983).
  * Kennedy and Tasaki [1992] T. Kennedy and H. Tasaki, Hidden symmetry breaking and the Haldane phase in $S=1$ quantum spin chains, Comm. Math. Phys. 147, 431 (1992).
  * Anderson [1963] P. W. Anderson, Plasmons, gauge invariance, and mass, Phys. Rev. 130, 439 (1963).
  * Wen [1990] X. G. Wen, Topological Orders in Rigid Stages, Int. J. Mod. Phys. B 04, 239 (1990).
  * Kivelson and Lederer [2019] S. A. Kivelson and S. Lederer, Linking the pseudogap in the cuprates with local symmetry breaking: A commentary, Proc. Nat. Acad. Sci. 116, 14395 (2019).
  * Goodfellow  _et al._ [2016] I. Goodfellow, Y. Bengio, and A. Courville,  _Deep learning_ (MIT pres, 2016).
  * Carrasquilla and Melko [2017] J. Carrasquilla and R. G. Melko, Machine learning phases of matter, Nature Phys. 13, 431 (2017).
  * Broecker  _et al._ [2017] P. Broecker, J. Carrasquilla, R. G. Melko, and S. Trebst, Machine learning quantum phases of matter beyond the fermion sign problem, Scientific Rep. 7, 1 (2017).
  * Ch’ng  _et al._ [2017] K. Ch’ng, J. Carrasquilla, R. G. Melko, and E. Khatami, Machine learning phases of strongly correlated fermions, Phys. Rev. X 7, 031038 (2017).
  * Wetzel and Scherzer [2017] S. J. Wetzel and M. Scherzer, Machine learning of explicit order parameters: From the Ising model to SU(2) lattice gauge theory, Phys. Rev. B 96, 184410 (2017).
  * Morningstar and Melko [2018] A. Morningstar and R. G. Melko, Deep learning the ising model near criticality, J. Mach. Learn. Res. 18, 1 (2018).
  * Efthymiou  _et al._ [2019] S. Efthymiou, M. J. S. Beach, and R. G. Melko, Super-resolving the Ising model with convolutional neural networks, Phys. Rev. B 99, 075113 (2019).
  * Walker  _et al._ [2020] N. Walker, K.-M. Tam, and M. Jarrell, Deep learning on the 2-dimensional Ising model to extract the crossover region with a variational autoencoder, Scientific Rep. 10, 1038 (2020).
  * Johnston  _et al._ [2022] S. Johnston, E. Khatami, and R. Scalettar, A perspective on machine learning and data science for strongly correlated electron problems, Carbon Trends 9, 100231 (2022).
  * Krizhevsky  _et al._ [2012] A. Krizhevsky, I. Sutskever, and G. E. Hinton, Imagenet classification with deep convolutional neural networks, in  _Advances in neural information processing systems_ (2012) pp. 1097–1105.
  * Antipov  _et al._ [2015] G. Antipov, S.-A. Berrani, N. Ruchaud, and J.-L. Dugelay, Learned vs. hand-crafted features for pedestrian gender recognition, in  _Proceedings of the 23rd ACM international conference on Multimedia_ (ACM, 2015) pp. 1263–1266.
  * Liang  _et al._ [2017] H. Liang, X. Sun, Y. Sun, and Y. Gao, Text feature extraction based on deep learning: a review, EURASIP Journal on Wireless Communications and Networking 2017, 1186 (2017).
  * Wang [2016] L. Wang, Discovering phase transitions with unsupervised learning, Phys. Rev. B 94, 195105 (2016).
  * Wetzel [2017] S. J. Wetzel, Unsupervised learning of phase transitions: From principal component analysis to variational autoencoders, Phys. Rev. E 96, 022140 (2017).
  * Ch’ng  _et al._ [2018] K. Ch’ng, N. Vazquez, and E. Khatami, Unsupervised machine learning account of magnetic transitions in the Hubbard model, Phys. Rev. E 97, 013306 (2018).
  * Alexandrou  _et al._ [2020] C. Alexandrou, A. Athenodorou, C. Chrysostomou, and S. Paul, The critical temperature of the 2D-ising model through deep learning autoencoders, The European Physical Journal B 93, 1140 (2020).
  * Yevick [2021] D. Yevick, Variational autoencoder analysis of ising model statistical distributions and phase transitions, arXiv:2104.06368 (2021).
  * Hinton and Salakhutdinov [2006] G. E. Hinton and R. R. Salakhutdinov, Reducing the dimensionality of data with neural networks, Science 313, 504 (2006).
  * Kingma and Welling [2014] D. Kingma and M. Welling, Auto-encoding variational Bayes, in  _International Conference on Learning Representations_ (2014).
  * Georgii [2011] H.-O. Georgii,  _Gibbs measures and phase transitions_ (de Gruyter, 2011).
  * Onsager [1944] L. Onsager, Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition, Phys. Rev. 65, 117 (1944).
  * Smith  _et al._ [2018] S. L. Smith, P. Kindermans, C. Ying, and Q. V. Le, Don’t decay the learning rate, increase the batch size, in  _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ (OpenReview.net, 2018).
  * Binder  _et al._ [1993] K. Binder, D. Heermann, L. Roelofs, A. J. Mallinckrodt, and S. McKay, Monte Carlo simulation in statistical physics, Computers in Physics 7, 156 (1993).
  * Young [2015] P. Young,  _Everything you wanted to know about data analysis and fitting but were afraid to ask_ (Springer, 2015).
  * Coniglio  _et al._ [1989] A. Coniglio, F. de Liberto, G. Monroy, and F. Peruggi, Exact relations between droplets and thermal fluctuations in external field, Journal of Physics A: Mathematical and General 22, L837 (1989).
  * [52] GAP, GAP – Groups, Algorithms, and Programming, Version 4.11.1, https://www.gap-system.org (2021).
  * Agrawal and Ostrowski [2022] D. Agrawal and J. Ostrowski, A classification of $G$-invariant shallow neural networks, Advances in Neural Information Processing Systems 35 (2022).
  * Liu  _et al._ [2017] J. Liu, Y. Qi, Z. Y. Meng, and L. Fu, Self-learning Monte Carlo method, Phys. Rev. B 95, 041101 (2017).
  * Shen  _et al._ [2018] H. Shen, J. Liu, and L. Fu, Self-learning Monte Carlo with deep neural networks, Phys. Rev. B 97, 205140 (2018).
  * Li  _et al._ [2019] S. Li, P. M. Dee, E. Khatami, and S. Johnston, Accelerating lattice quantum Monte Carlo simulations using artificial neural networks: Application to the Holstein model, Phys. Rev. B 100, 020302 (2019).
  * Albergo  _et al._ [2019] M. S. Albergo, G. Kanwar, and P. E. Shanahan, Flow-based generative models for Markov chain Monte Carlo in lattice field theory, Phys. Rev. D 100, 034515 (2019).
  * Nagai  _et al._ [2020] Y. Nagai, M. Okumura, and A. Tanaka, Self-learning Monte Carlo method with behler-parrinello neural networks, Phys. Rev. B 101, 115111 (2020).
  * Chen  _et al._ [2018] C. Chen, X. Y. Xu, J. Liu, G. Batrouni, R. Scalettar, and Z. Y. Meng, Symmetry-enforced self-learning Monte Carlo method applied to the Holstein model, Phys. Rev. B 98, 041102 (2018).
  * Vandenberghe [2010] L. Vandenberghe, The cvxopt linear and quadratic cone program solvers, Online: http://cvxopt.org/documentation/coneprog.pdf (2010).