Finally, the next result deals with commutators between paraproduct operators
and Fourier multipliers.

###### Lemma A.14

Let $\kappa$ be a smooth function on $\mathbb{R}^{d}$, which is homogeneous of
degree $m$ away from a neighborhood of $0$. Take
$(s,p,r)\in\mathbb{R}\times[1,+\infty]^{2}$ and $v$ a vector field such that
$\nabla v\in L^{\infty}$. Then, for every $f\in B^{s}_{p,r}$, one has

$\left\|[T_{v},\kappa(D)]f\right\|_{B^{s-m+1}_{p,r}}\leq C(s,d)\,\|\nabla
v\|_{L^{\infty}}\|f\|_{B^{s}_{p,r}}\,.$

####  A.4 Transport equations

In this paragraph, we deal with the transport equations in non-homogeneous
Besov spaces. We refer to Chapter 3 of [5] for additional details. We study,
in $\mathbb{R}_{+}\times\mathbb{R}^{d}$, the initial value problem

$\begin{cases}\partial_{t}f+v\cdot\nabla f=g\\\ f_{|t=0}=f_{0}\,.\end{cases}$
(A.4.1)

We always assume the velocity field $v=v(t,x)$ to be a Lipschitz divergence-
free function. In the case when the Lipschitz condition (A.3.1) is satisfied,
we have the embedding $B^{s}_{p,r}\hookrightarrow W^{1,\infty}$.

We state now the main well-posedness result concerning problem (A.4.1) in
Besov spaces. We point out also that the notation $C^{0}_{w}([0,T];X)$, with
$X$ a Banach space, refers to the space of functions which are continuous in
time with values in $X$ endowed with its weak topology.

###### Theorem A.15

Let $(s,p,r)\in\mathbb{R}\times[1,+\infty]^{2}$ satisfy the Lipschitz
condition (A.3.1). Given $T>0$, take $g\in L^{1}_{T}(B^{s}_{p,r})$. Assume
that $v\in L^{1}_{T}(B^{s}_{p,r})$ and that there exist two real numbers $q>1$
and $\sigma>0$ such that $v\in L^{q}_{T}(B^{-\sigma}_{\infty,\infty})$.
Finally, let $f_{0}\in B^{s}_{p,r}$ be the initial datum. Then, the transport
equation (A.4.1) has a unique solution $f$ in:

  * •

the space $C^{0}\left([0,T];B^{s}_{p,r}\right)$, if $r<+\infty$;

  * •

the space
$\left(\displaystyle\bigcap_{s^{\prime}<s}C^{0}\left([0,T];B^{s^{\prime}}_{p,\infty}\right)\right)\cap
C^{0}_{w}\left([0,T];B^{s}_{p,\infty}\right)$, if $r=+\infty$.

Moreover, the unique solution satisfies the following estimate:

$\|f\|_{L^{\infty}_{T}(B^{s}_{p,r})}\leq\exp\left(C\int_{0}^{T}\|\nabla
v\|_{B^{s-1}_{p,r}}\,\,{\rm
d}\tau\right)\left(\|f_{0}\|_{B^{s}_{p,r}}+\int_{0}^{T}\exp\left(-C\int_{0}^{t}\|\nabla
v\|_{B^{s-1}_{p,r}}\,\,{\rm d}\tau\right)\|g\|_{B^{s}_{p,r}}\,\,{\rm
d}t\right),$

for some constant $C=C(s,p,r,d)>0$.

To conclude this paragraph, we show a refinement of Theorem A.15, proved by
Vishik in [70] and in a different way by Hmidi and Keraani (see [49]). It
states that, if ${\rm div}\,v=0$ and the Besov regularity index is $s=0$, the
estimate in Theorem A.15 can be replaced by an inequality which is linear with
respect to $\|\nabla v\|_{L^{1}_{T}(L^{\infty})}$.

###### Theorem A.16

Given $T>0$, assume that $v$ is a divergence-free vector field such that
$\nabla v\in L^{1}_{T}(L^{\infty})$ and let $g\in
L^{1}_{T}(B^{0}_{\infty,r})$. Take $r\in[1,+\infty]$ and $f_{0}\in
L^{1}_{T}(B^{0}_{\infty,r})$. Then, there exists a constant $C=C(d)$ such
that, for any solution $f$ to problem (A.4.1) in
$C^{0}([0,T];B^{0}_{\infty,r})$ (or with the usual modification of $C^{0}$
into $C^{0}_{w}$ if $r=+\infty$), we have

$\|f\|_{L^{\infty}_{T}(B^{0}_{\infty,r})}\leq
C\left(\|f_{0}\|_{B^{0}_{\infty,r}}+\|g\|_{L^{1}_{T}(B^{0}_{\infty,r})}\right)\left(1+\int_{0}^{T}\|\nabla
v(\tau)\|_{L^{\infty}}\,\,{\rm d}\tau\right)\,.$

###  Appendix B Some well-known results

This appendix is thought for the reader’s convenience in order to quickly
check the statement of some famous theorems. For that reason, we limit ourself
to state such results, used throughout the whole thesis. Unless indicated
otherwise, we refer to the introductory part of book [39] for details (see
also Chapter 10) and to Chapter 1 of [5].

####  B.1 Embedding theorems

We start by recalling the _Rellich-Kondrachov embedding theorem_.

###### Theorem B.1

Let $Q\subset\mathbb{R}^{d}$ be a bounded Lipschitz domain.

  * (i)

If $kp<d$ and $p\geq 1$, then the space $W^{k,p}(Q)$ is continuously embedded
in $L^{q}(Q)$ for any $1\leq q\leq p^{\ast}:=(dp)/(d-kp)$.
Moreover, the embedding is compact if $k>0$ and $q<p^{\ast}$.

  * (ii)

If $kp=d$, the space $W^{k,p}(Q)$ is compactly embedded in $L^{q}(Q)$ for any
$q\in[1,+\infty)$.

  * (iii)

If $kp>d$, then $W^{k,p}(Q)$ is continuously embedded in111The symbol $\lfloor
z\rfloor$ denotes the integer part of $z$. $\mathcal{C}^{k-\lfloor
d/p\rfloor-1,\,\nu}(\overline{Q})$, where either $\nu=\lfloor
d/p\rfloor+1-d/p$ if $(d/p)\not\in\mathbb{Z}$ or $\nu$ is an arbitrary
positive number in $(0,1)$ if $(d/p)\in\mathbb{Z}$.
Moreover, the embedding is compact if $0<\nu<\lfloor d/p\rfloor+1-d/p$.

As a direct consequence of the previous theorem we have the _embedding theorem
for dual Sobolev spaces_.

###### Theorem B.2

Let $Q\subset\mathbb{R}^{d}$ be a bounded domain. Let $k>0$ and $q<+\infty$
satisfy

  * •

$q>p^{\ast}/(p^{\ast}-1)$ where $p^{\ast}:=(dp)/(d-kp)$, if $kp<d$;

  * •

$q>1$, if $kp=d$;

  * •

$q\geq 1$, if $kp>d$.

Then, the space $L^{q}(Q)$ is compactly embedded into the space
$W^{-k,p^{\prime}}(Q)$, with $1/p+1/p^{\prime}=1$.

####  B.2 Mollifiers

Here we recall the main properties of the mollifiers. Such properties are
widely employed in Section 2.4 of Chapter 2.

We start by fixing a smooth, radial and radially decreasing function
$\chi\in{C}^{\infty}_{c}(\mathbb{R}^{d})$, such that

$0\leq\chi\leq 1,\quad\quad\chi(x)=0\;\text{ for }|x|\geq
1\quad\quad\text{and}\quad\quad\int_{\mathbb{R}^{d}}\chi(x)\,{\rm d}x=1.$

Next, we define the _mollifying kernel_
$\big{(}\chi_{\varepsilon}\big{)}_{\varepsilon>0}$ by the formula

$\chi_{\varepsilon}(x)\,:=\,\frac{1}{\varepsilon^{d}}\,\,\chi\\!\left(\frac{x}{\varepsilon}\right)\qquad\qquad\text{for
any}\;\varepsilon>0\;\text{ and }\;x\in\mathbb{R}^{d}\,.$

Then, for any tempered distribution $\mathfrak{S}$ on $\mathbb{R}^{d}$ and any
$\varepsilon>0$, we introduce

$\mathfrak{S}_{\varepsilon}\,:=\,\chi_{\varepsilon}\,*\,\mathfrak{S}\,.$

###### Theorem B.3

Let $X$ a Banach space. If $\mathfrak{S}\in L^{1}_{\rm
loc}(\mathbb{R}^{d};X)$, then we have $\mathfrak{S}_{\varepsilon}\in
C^{\infty}(\mathbb{R}^{d};X)$. In addition, we have the following properties:

  * (i)

if $\mathfrak{S}\in L^{p}_{\rm loc}(\mathbb{R}^{d};X)$ with $1\leq p<+\infty$,
then $\mathfrak{S}_{\varepsilon}\in L^{p}_{\rm loc}(\mathbb{R}^{d};X)$ and

$\mathfrak{S}_{\varepsilon}\longrightarrow\mathfrak{S}\quad\text{in}\quad
L^{p}_{\rm loc}(\mathbb{R}^{d};X)\quad\text{as}\quad\varepsilon\rightarrow
0^{+}\,;$

  * (ii)

if $\mathfrak{S}\in L^{p}(\mathbb{R}^{d};X)$ with $1\leq p<+\infty$, then
$\mathfrak{S}_{\varepsilon}\in L^{p}(\mathbb{R}^{d};X)$,

$\|\mathfrak{S}_{\varepsilon}\|_{L^{p}(\mathbb{R}^{d};X)}\leq\|\mathfrak{S}\|_{L^{p}(\mathbb{R}^{d};X)}$

and

$\mathfrak{S}_{\varepsilon}\longrightarrow\mathfrak{S}\quad\text{in}\quad
L^{p}(\mathbb{R}^{d};X)\quad\text{as}\quad\varepsilon\rightarrow 0^{+}\,;$

  * (iii)

if $\mathfrak{S}\in L^{\infty}(\mathbb{R}^{d};X)$, then
$\mathfrak{S}_{\varepsilon}\in L^{\infty}(\mathbb{R}^{d};X)$ and

$\|\mathfrak{S}_{\varepsilon}\|_{L^{\infty}(\mathbb{R}^{d};X)}\leq\|\mathfrak{S}\|_{L^{\infty}(\mathbb{R}^{d};X)}\,;$

  * (iv)

if $\mathfrak{S}\in C^{k}(Q;X)$ where $k$ is a non-negative integer and
$Q\subset\mathbb{R}^{d}$ is a ball, then
$(\partial^{\alpha}\mathfrak{S})_{\varepsilon}(x)=\partial^{\alpha}\mathfrak{S}_{\varepsilon}(x)$
for all $x\in Q$, $\varepsilon\in(0,{\rm dist}[x,\partial Q])$ and for any
multi-index $\alpha$ such that $|\alpha|\leq k$. Moreover,

$\|\mathfrak{S}_{\varepsilon}\|_{C^{k}(\overline{B};X)}\leq\|\mathfrak{S}\|_{C^{k}(\overline{V};X)}$

for any $\varepsilon\in(0,{\rm dist}[\partial B,\partial V])$, where $B$ and
$V$ are balls in $\mathbb{R}^{d}$ such that $\overline{B}\subset
V\subset\overline{V}\subset Q$. Finally,

$\mathfrak{S}_{\varepsilon}\longrightarrow\mathfrak{S}\quad\text{in}\quad
C^{k}(\overline{B};X)\quad\text{as}\quad\varepsilon\rightarrow 0^{+}\,.$

####  B.3 Some assorted inequalities

We start this section by mentioning some classical inequalities: _Young’s
inequality_ (see Chapter 4 of [13] in this respect), _Hölder’s inequality_ and
_Minkowski’s inequality_.

######  Proposition B.4 (Young’s inequality)

If $a\geq 0$ and $b\geq 0$ are non-negative real numbers and if $p>1$ and
$q>1$ are real numbers such that

$\frac{1}{p}+\frac{1}{q}=1\,,$

then222It is sometimes convenient to use the formulation $ab\leq\varepsilon
a^{p}+\varepsilon^{-1/(p-1)}b^{q}$, with $\varepsilon>0$.

$ab\leq\frac{a^{p}}{p}+\frac{b^{q}}{q}\,.$

######  Proposition B.5 (Hölder’s inequality)

Let $(X,\mu)$ be a measure space and $(p,q,r)$ in $[1,+\infty]^{3}$ be such
that

$\frac{1}{p}+\frac{1}{q}=\frac{1}{r}\,.$

If the couple $(f,g)$ belongs to $L^{p}(X,\mu)\times L^{q}(X,\mu)$, then the
product $fg$ belongs to $L^{r}(X,\mu)$ and

$\|fg\|_{L^{r}}\leq\|f\|_{L^{p}}\|g\|_{L^{q}}\,.$

######  Proposition B.6 (Minkowski’s inequality)

Let $(X_{1},\mu_{1})$ and $(X_{2},\mu_{2})$ be two measure spaces and $f$ a
non-negative measurable function over $X_{1}\times X_{2}$. For all $1\leq
p\leq q\leq+\infty$, we have

$\left\|\|f(\cdot,x_{2})\|_{L^{p}(X_{1},\mu_{1})}\right\|_{L^{q}(X_{2},\mu_{2})}\leq\left\|\|f(x_{1},\cdot)\|_{L^{q}(X_{2},\mu_{2})}\right\|_{L^{p}(X_{1},\mu_{1})}\,.$

The next two results are fundamental to give uniform bounds in Sobolev norms
for the velocity fields and the temperatures. Such propositions are the so-
called _generalized Poincaré inequality_ and _generalized Korn-Poincaré
inequality_ respectively.

###### Proposition B.7

Let $1\leq p\leq+\infty$, $0<r<+\infty$, $V_{0}>0$ and let
$Q\subset\mathbb{R}^{d}$ be a bounded Lipschitz domain. Then, there exists a
positive constant $c=c(p,r,V_{0})$ such that

$\|v\|_{W^{1,p}(Q)}\leq c\left[\|\nabla
v\|_{L^{p}(Q;\,\mathbb{R}^{d})}+\left(\int_{V}|v|^{r}\,{\rm
d}x\right)^{1/r}\right]\,,$

for any measurable $V\subset Q$ with $|V|\geq V_{0}$ and any $v\in
W^{1,p}(Q)$.

###### Proposition B.8

Let $Q\subset\mathbb{R}^{d}$, with $d>2$, be a bounded Lipschitz domain, and
let $1<p<+\infty$, $M_{0}>0$, $K>0$, $\alpha>1$. Then, there exists a positive
constant $c=c(p,M_{0},K,\alpha)$ such that the inequality

$\|v\|_{W^{1,p}(Q;\mathbb{R}^{d})}\leq c\left(\|\nabla v+\,^{t}\nabla
v-\frac{2}{d}\,{\rm div}\,v\,{\rm
Id}\,\|_{L^{p}(Q;\mathbb{R}^{d})}+\int_{Q}f|v|\,{\rm d}x\right)$

holds for any $v\in W^{1,p}(Q;\mathbb{R}^{d})$ and any non-negative function
$f$ such that

$0<M_{0}\leq\int_{Q}f\,{\rm d}x\quad\text{and}\quad\int_{Q}f^{\alpha}\,{\rm
d}x\leq K\;\;\text{for a certain }\alpha>1\,.$

We conclude this paragraph, by stating a classical result in the theory of
Sobolev spaces that relates the $L^{p}$ norms of the weak derivatives of a
function: the so-called Gagliardo–Nirenberg inequality (see [61] for details
of the proof).

###### Theorem B.9

Let $f$ be a function belonging to $L^{q}(\mathbb{R}^{d})$ and its derivatives
of order $m$, denoted by $D^{m}f$, belong to $L^{r}(\mathbb{R}^{d})$ with
$1\leq q,r\leq+\infty$. For the derivatives $D^{j}f$, where $0\leq j<m$, the
following inequality holds

$\|D^{j}f\|_{L^{p}}\leq
C\|D^{m}f\|_{L^{r}}^{\alpha}\|f\|_{L^{q}}^{1-\alpha}\,,$ (B.3.1)

where

$\frac{1}{p}=\frac{j}{d}+\alpha\left(\frac{1}{r}-\frac{m}{d}\right)+(1-\alpha)\frac{1}{q}\,,$

for all $\alpha$ in the interval

$\frac{j}{m}\leq\alpha\leq 1\,,$

with the following exceptional cases:

  * (i)

if $j=0$, $rm<d$ and $q=+\infty$, then we make the additional assumption that
either $f$ tends to zero at infinity or $f\in L^{b}(\mathbb{R}^{d})$ for some
$b>0$;

  * (ii)

if $1<r<+\infty$ and $m-j-d/r$ is a non-negative integer, then (B.3.1) holds
only for $\alpha$ satisfying $j/m\leq\alpha<1$.

####  B.4 Elliptic estimates

This part of the appendix is devoted to a classical result pertaining $L^{2}$
solutions of the following elliptic equation:

$-{\rm div}\,(A\nabla\Pi)={\rm div}\,F\quad\text{in}\quad\mathbb{R}^{d}\,,$
(B.4.1)

where $A=A(x)$ is a given suitably smooth bounded function satisfying

$A_{\ast}:=\inf_{x\in\mathbb{R}^{d}}A(x)>0\,.$ (B.4.2)

###### Lemma B.10

For all vector fields $F$ in $L^{2}(\mathbb{R}^{d})$, there exists a tempered
distribution $\Pi$ (unique up to constant functions) such that $\nabla\Pi\in
L^{2}(\mathbb{R}^{d})$, and equation (B.4.1) is satisfied. Moreover, we have

$A_{\ast}\|\nabla\Pi\|_{L^{2}}\leq\|F\|_{L^{2}}\,.$ (B.4.3)

We refer to [21] for details of the proof.

Let us now state higher order estimates for the pressure term in Besov spaces
(we refer again to [21] for details).

###### Proposition B.11

Let $1<p<+\infty$ and $1\leq r\leq+\infty$. Let $A$ be a bounded function
satisfying (B.4.2) such that $\nabla A\in B^{s-1}_{p,r}$ for some $s>1+d/p$ or
$s\geq 1+d/p$ if $r=1$.

  * (i)

If $\sigma\in\;]1,s]$ and $\nabla\Pi\in B^{\sigma}_{p,r}$ satisfies (B.4.1)
for some function $F$ such that ${\rm div}\,F\in B^{\sigma-1}_{p,r}$, then we
have for some constant $C=C(s,\sigma,p,d)$ that

$A_{\ast}\|\nabla\Pi\|_{B^{\sigma}_{p,r}}\leq C\left(\|{\rm
div}\,F\|_{B^{\sigma-1}_{p,r}}+A_{\ast}(1+A_{\ast}^{-1}\|\nabla
A\|_{B^{s-1}_{p,r}})^{\sigma}\|\nabla\Pi\|_{L^{p}}\right).$

  * (ii)

If $2\leq p<+\infty$ and $F$ is in $L^{2}$ and satisfies ${\rm div}\,F\in
B^{\sigma-1}_{p,r}$ for some $\sigma\in\;]1+d/p-d/2,\,s]$, then (B.4.1) has a
unique solution $\Pi$ (up to constant functions) such that $\nabla\Pi\in
L^{2}\cap B^{\sigma}_{p,r}$. Furthermore, inequality (B.4.3) is satisfied and
there exist a positive exponent $\gamma=\gamma(\sigma,p,d)$ and a positive
constant $C=C(s,\sigma,p,d)$ such that

$A_{\ast}\|\nabla\Pi\|_{B^{\sigma}_{p,r}}\leq C\left(\|{\rm
div}\,F\|_{B^{\sigma-1}_{p,r}}+(1+A_{\ast}^{-1}\|\nabla
A\|_{B^{s-1}_{p,r}})^{\gamma}\|\nabla\Pi\|_{L^{2}}\right).$

  * (iii)

If $\sigma>1$ and $1<p<+\infty$, then the following inequality holds:

$A_{\ast}\|\nabla\Pi\|_{B^{\sigma}_{p,r}}\leq C\left(\|{\rm
div}\,F\|_{B^{\sigma-1}_{p,r}}+\|\nabla
A\|_{L^{\infty}}\|\nabla\Pi\|_{B^{\sigma-1}_{p,r}}+\|\nabla\Pi\|_{L^{\infty}}\|\nabla
A\|_{B^{\sigma-1}_{p,r}}\right).$

####  B.5 Compactness theorems

Next, a “milestone” in our analysis is the compactness of special quantities
in order to perform the asymptotic process. In this sense, the _Ascoli-Arzelà_
and _Aubin-Lions_ theorems come in our “rescue”.

######  Theorem B.12 (Ascoli-Arzelà Theorem)

Let $Q\subset\mathbb{R}^{d}$ be compact and $X$ be a compact topological
metric space endowed with a metric $d_{X}$. Let $(v_{k})_{k}$ be a sequence of
functions in $\mathcal{C}^{0}(Q;X)$ that is equi-continuous, i.e. for any
$\varepsilon>0$ there exists $\delta>0$ such that

$d_{X}\Big{(}v_{k}(y),\,v_{k}(z)\Big{)}\leq\varepsilon\,,$

provided $|y-z|<\delta$ independently of $k$.

Then, $(v_{k})_{k}$ is precompact in $\mathcal{C}^{0}(Q;X)$, meaning that
there exists a subsequence (not relabelled) and a function
$v\in\mathcal{C}^{0}(Q;X)$ such that

$\sup_{y\in Q}d_{X}\Big{(}v_{k}(y),\,v(y)\Big{)}\longrightarrow
0\quad\text{as}\quad k\rightarrow+\infty\,.$

The proof of the next statement can be found in Section 5.3 of Chapter 2 of
[9] (see also Section 5 of Chapter 1 in [54]).

######  Theorem B.13 (Aubin-Lions Theorem)

Let $X_{0}\subset X_{1}\subset X_{2}$ be three Banach spaces. We assume that
the embedding of $X_{1}$ in $X_{2}$ is continuous and that the embedding of
$X_{0}$ in $X_{1}$ is compact. Let $(p,r)$ such that $1\leq p,r\leq+\infty$.
For $T>0$, we define

$E_{p,r}:=\left\\{v\in L^{p}(0,T;X_{0})\quad\text{and}\quad\frac{dv}{dt}\in
L^{r}(0,T;X_{2})\right\\}\,.$

Then,

  * (i)

if $p<+\infty$, the embedding of $E_{p,r}$ in $L^{p}(0,T;X_{1})$ is compact;

  * (ii)

if $p=+\infty$ and $r>1$, the embedding of $E_{p,r}$ in
$\mathcal{C}^{0}(0,T;X_{1})$ is compact.

Now, we present the celebrated _Div-Curl Lemma_ which, roughly speaking,
ensures that the product of two functions weakly converge, if each function
weakly converges and in addition one has information on the ${\rm div}\,$ of
one and the ${\rm curl}\,$ of the other.

###### Theorem B.14

Let $Q\subset\mathbb{R}^{d}$ be an open set. Assume that

$\begin{split}u_{n}\rightharpoonup u\quad&\text{weakly in
}L^{p}(Q;\mathbb{R}^{d})\\\ v_{n}\rightharpoonup v\quad&\text{weakly in
}L^{q}(Q;\mathbb{R}^{d})\end{split}$

where

$\frac{1}{p}+\frac{1}{q}=\frac{1}{r}<1\,.$

In addition, let ${\rm div}\,u_{n}$ be precompact in $W^{-1,s}(Q)$ and ${\rm
curl}\,v_{n}$ be precompact in $W^{-1,s}(Q;\mathbb{R}^{d\times d})$, for a
certain $s>1$. Then,

$u_{n}\cdot v_{n}\rightharpoonup u\cdot v\quad\text{weakly in }L^{r}(Q)\,.$

####  B.6 Grönwall’s lemma

To conclude this appendix, we mention a _Grönwall estimate_ which has been of
constant use in Chapter 4.

###### Lemma B.15

Let $a\in L^{1}(0,T)$, $a\geq 0$, $\beta\in L^{1}(0,T)$, $b_{0}\in\mathbb{R}$
and

$b(\tau)=b_{0}+\int_{0}^{\tau}\beta(t)\,{\rm d}t$

be given. Let $f\in L^{\infty}(0,T)$ satisfy

$f(\tau)\leq b(\tau)+\int_{0}^{\tau}a(t)\,f(t)\,{\rm d}t\quad\text{ for a.a.
}\tau\in[0,T].$

Then, one has

$f(\tau)\leq b_{0}\exp\left(\int_{0}^{\tau}a(t)\,{\rm
d}t\right)+\int_{0}^{\tau}\beta(t)\exp\left(\int_{t}^{\tau}a(s)\,{\rm
d}s\right)\,{\rm d}t$

for a.a. $\tau\in[0,T]$.

### Bibliography

  * [1] S. Alinhac: “Hyperbolic partial differential equations”. Universitext, Springer, Dordrecht (2009).
  * [2] A. Babin, A. Mahalov, B. Nicolaenko: Global splitting, integrability and regularity of 3D Euler and Navier-Stokes equations for uniformly rotating fluids. European J. Mech. B/Fluids, 15 (1996), n. 3, 291-300.
  * [3] A. Babin, A. Mahalov, B. Nicolaenko: Regularity and integrability of 3D Euler and Navier-Stokes equations for rotating fluids. Asymptot. Anal., 15 (1997), n. 2, 103-150.
  * [4] H. Bae, W. Lee, J. Shin: A blow-up criterion for the inhomogeneous incompressible Euler equations. Nonlinear Anal., 196 (2020), 111774.
  * [5] H. Bahouri, J.-Y. Chemin, R. Danchin: “Fourier Analysis and Nonlinear Partial Differential Equations”. Grundlehren der Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences), 343, Springer, Heidelberg (2011).
  * [6] J. Beale, T. Kato, A. Majda: Remarks on the breakdown of smooth solutions for the 3-D Euler equations. Comm. Math. Phys., 94 (1984), n. 1, 61-66.
  * [7] E. Bocchi, F. Fanelli, C. Prange: Anisotropy and stratification effects in the dynamics of fast rotating compressible fluids. Ann. Inst. H. Poincaré Anal. Non Linéaire. To appear (2021).
  * [8] J.-M. Bony: Calcul symbolique et propagation des singularités pour les équations aux dérivées partielles non linéaires. Ann. Sci. École Norm. Sup., 14 (1981), n. 2, 209-246.
  * [9] F. Boyer, P. Fabrie: “Mathematical tools for the study of the incompressible Navier-Stokes equations and related models”. Applied Mathematical Sciences, 183, Springer, New York, (2013).
  * [10] D. Bresch, B. Desjardins: On the existence of global weak solutions to the Navier-Stokes equations for viscous compressible and heat conducting fluids. J. Math. Pures Appl. (9), 87 (2007), n. 1, 57-90.
  * [11] D. Bresch, B. Desjardins, D. Gérard-Varet: Rotating fluids in a cylinder. Discrete Contin. Dyn. Syst., 11 (2004), n. 1, 47-82.
  * [12] D. Bresch, M. Gisclon, C.-K. Lin: An example of low Mach (Froude) number effects for compressible flows with nonconstant density (height) limit. Math. Model. and Num. Anal., 39 (2005), n. 3, 477-486.
  * [13] H. Brezis: “Functional analysis, Sobolev spaces and partial differential equations”. Universitext, Springer, New York (2011).
  * [14] F. Charve: Global well-posedness and asymptotics for a geophysical fluid system. Comm. Partial Differential Equations, 29 (2004), n. 11-12, 1919-1940.
  * [15] J.-Y. Chemin, B. Desjardins, I. Gallagher, E. Grenier: “Mathematical geophysics. An introduction to rotating fluids and the Navier-Stokes equations”. Oxford Lecture Series in Mathematics and its Applications, 32, Oxford University Press, Oxford (2006).
  * [16] D. Cobb, F. Fanelli: Elsässer formulation of the ideal MHD and improved lifespan in two space dimensions. Submitted (2020).
  * [17] D. Cobb, F. Fanelli: On the fast rotation asymptotics of a non-homogeneous incompressible MHD system. Nonlinearity, 34 (2021), n. 4, 2483.
  * [18] D. Cobb, F. Fanelli: Rigorous derivation and well-posedness of a quasi-homogeneous ideal MHD system. Nonlinear Anal. Real World Appl., 60 (2021), 103284.
  * [19] B. Cushman-Roisin, J.-M. Beckers:“Introduction to geophysical fluid dynamics. Physical and numerical aspects. Second edition”. Geophysics Series, 101, Elsevier/Academic Press, Amsterdam (2011).
  * [20] R. Danchin: The inviscid limit for density dependent incompressible fluids. Ann. Fac. Sci. Toulouse Math., 15 (2006), n. 4, 637-688.
  * [21] R. Danchin: On the well-posedness of the incompressible density-dependent Euler equations in the $L^{p}$ framework. J. Differential Equations, 248 (2010), n. 8, 2130-2170.
  * [22] R. Danchin, F. Fanelli: The well-posedness issue for the density-dependent Euler equations in endpoint Besov spaces. J. Math. Pures Appl. (9), 96 (2011), n. 3, 253-278.
  * [23] F. De Anna, F. Fanelli: Global well-posedness and long-time dynamics for a higher order quasi-geostrophic type equation. J. Funct. Anal., 274 (2018), n. 8, 2291-2355.
  * [24] D. Del Santo, F. Fanelli, G. Sbaiz, A. Wróblewska-Kamińska: A multiscale problem for viscous heat-conducting fluids in fast rotation. J. Nonlinear Sci., 31 (2021), n. 1, 21.
  * [25] D. Del Santo, F. Fanelli, G. Sbaiz, A. Wróblewska-Kamińska: On the influence of gravity in the dynamics of geophysical flows. Submitted (2021).
  * [26] A. Dutrifoy: Examples of dispersive effects in non-viscous rotating fluids. J. Math. Pures Appl. (9), 84 (2005), n. 3, 331-356.
  * [27] D. G. Ebin: Viscous fluids in a domain with frictionless boundary. In “Global analysis-analysis on manifolds”, Teubner-Texte Math., 57, Teubner, Leipzig (1983), 93-110.
  * [28] F. Fanelli: A singular limit problem for rotating capillary fluids with variable rotation axis. J. Math. Fluid Mech., 18 (2016), n. 4, 625-658.
  * [29] F. Fanelli: Highly rotating viscous compressible fluids in presence of capillarity effects. Math. Ann., 366 (2016), n. 3-4, 981-1033.
  * [30] F. Fanelli: Incompressible and fast rotation limit for barotropic Navier-Stokes equations at large Mach numbers. Physica D, 428 (2021), 133049.
  * [31] F. Fanelli, I. Gallagher: Asymptotics of fast rotating density-dependent fluids in two space dimensions. Rev. Mat. Iberoam., 35 (2019), n. 6, 1763-1807.
  * [32] F. Fanelli, E. Zatorska: Low Mach number limit for degenerate Navier-Stokes equations in presence of strong stratification. Submitted (2021).
  * [33] E. Feireisl: “Dynamics of viscous compressible fluids”. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford (2004).
  * [34] E. Feireisl, I. Gallagher, D. Gérard-Varet, A. Novotný: Multi-scale analysis of compressible viscous and rotating fluids. Comm. Math. Phys., 314 (2012), n. 3, 641-670.
  * [35] E. Feireisl, I. Gallagher, A. Novotný: A singular limit for compressible rotating fluids. SIAM J. Math. Anal., 44 (2012), n. 1, 192-205.
  * [36] E. Feireisl, B. J. Jin, A. Novotný: Relative entropies, suitable weak solutions, and weak-strong uniqueness for the compressible Navier-Stokes system. J. Math. Fluid Mech., 14 (2012), n. 4, 717-730.
  * [37] E. Feireisl, R. Klein, A. Novotný, E. Zatorska: On singular limits arising in the scale analysis of stratified fluid flows. Math. Models Methods Appl. Sci., 26 (2016), n. 3, 419-443.
  * [38] E. Feireisl, Y. Lu, A. Novotný: Rotating compressible fluids under strong stratification. Nonlinear Anal. Real World Appl., 19 (2014), 11-18.
  * [39] E. Feireisl, A. Novotný: “Singular limits in thermodynamics of viscous fluids”. Advances in Mathematical Fluid Mechanics, Birkhäuser Verlag, Basel (2009).
  * [40] E. Feireisl, A. Novotný: Multiple scales and singular limits for compressible rotating fluids with general initial data. Comm. Partial Differential Equations, 39 (2014), n. 6, 1104-1127.
  * [41] E. Feireisl, A. Novotný: Scale interactions in compressible rotating fluids. Ann. Mat. Pura Appl., 193 (2014), n. 6, 1703-1725.
  * [42] E. Feireisl, A. Novotný, H. Petzeltová: On the existence of globally defined weak solutions to the Navier-Stokes equations”. J. Math. Fluid Mech., 3 (2001), n. 4, 358-392.
  * [43] E. Feireisl, A. Novotný, Y. Sun: Suitable weak solutions to the Navier-Stokes equations of compressible viscous fluids. Indiana Univ. Math. J., 60 (2011), n. 2, 611-631.
  * [44] E. Feireisl, M. E. Schonbek: On the Oberbeck-Boussinesq approximation on unbounded domains. Nonlinear partial differential equations, 131-168, Abel Symp., 7, Springer, Heidelberg (2012).
  * [45] I. Gallagher: The tridimensional Navier-Stokes equations with almost bidimensional data: stability; uniqueness; and life span. Int. Math. Research Notices, (1997), n. 18, 919-935.
  * [46] I. Gallagher, L. Saint-Raymond: Mathematical study of the betaplane model: equatorial waves and convergence results. Mém. Soc. Math. Fr., 107 (2006).
  * [47] I. Gallagher, L. Saint-Raymond: Weak convergence results for inhomogeneous rotating fluid equations. J. Anal. Math., 99 (2006), 1-34.
  * [48] P. Germain: Weak-strong uniqueness for the isentropic compressible Navier-Stokes system. J. Math. Fluid Mech., 13 (2011), n. 1, 137-146.
  * [49] T. Hmidi, S. Keraani: Incompressible viscous flows in borderline Besov spaces. Arch. Ration. Mech. Anal., 189 (2008), n. 2, 283-300.
  * [50] D. Jesslé, B. J. Jin, A. Novotný: Navier-Stokes-Fourier system on unbounded domains: weak solutions, relative entropies, weak-strong uniqueness. SIAM J. Math. Anal., 45 (2013), n. 3, 1907-1951.
  * [51] P. Kundu, I. Cohen, D. Dowling: “Fluid mechanics. Fifth edition”. Academic Press, Elsevier, Oxford (2012).
  * [52] Y.-S. Kwon, D. Maltese, A. Novotný: Multiscale analysis in the compressible rotating and heat conducting fluids. J. Math. Fluid Mech., 20 (2018), n. 2, 421-444.
  * [53] Y.-S. Kwon, A. Novotný: Derivation of geostrophic equations as a rigorous limit of compressible rotating and heat conducting fluids with the general initial data. Discrete Contin. Dyn. Syst., 40 (2020), n. 1, 395-421.
  * [54] J.-L. Lions: “Quelques méthodes de résolution des problèmes aux limites non linéaires”. Dunod, Gauthier-Villars, Paris (1969).
  * [55] P.-L. Lions: Compacité des solutions des équations de Navier-Stokes compressibles isentropiques. C. R. Acad. Sci. Paris Sér. I Math., 317 (1993), n. 1, 115-120.
  * [56] P.-L. Lions: “Mathematical topics in fluid mechanics. Vol. 2. Compressible models”. Oxford Lecture Series in Mathematics, Oxford University Press, New York (1998).
  * [57] P.-L. Lions, N. Masmoudi: Incompressible limit for a viscous compressible fluid. J. Math. Pures Appl., 77 (1998), n. 6, 585-627.
  * [58] A. Majda: “Introduction to PDEs and waves for the atmosphere and ocean”. Courant Lecture Notes in Mathematics, 9, New York University, Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI (2003).
  * [59] N. Masmoudi: Rigorous derivation of the anelastic approximation. J. Math. Pures Appl. (9), 88 (2007), n. 3, 230-240.
  * [60] G. Métivier: “Para-differential calculus and applications to the Cauchy problem for nonlinear systems”. Centro di Ricerca Matematica “Ennio De Giorgi” (CRM) Series, 5, Edizioni della Normale, Pisa (2008).
  * [61] L. Nirenberg: On elliptic partial differential equations. Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3), 13 (1959), 115-162.
  * [62] J. Pedlosky: “Geophysical fluid dynamics”. Springer-Verlag, New-York (1987).
  * [63] G. Prodi: Un teorema di unicità per le equazioni di Navier-Stokes. Ann. Mat. Pura Appl. (4), 48 (1959), 173-182.
  * [64] W. Rudin: “Principles of mathematical analysis. Third edition”. International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-Düsseldorf (1976).
  * [65] G. Sbaiz: Fast rotation limit for the $2$-D non-homogeneous incompressible Euler equations. Submitted (2021).
  * [66] S. Scrobogna: Highly rotating fluids with vertical stratification for periodic data and vanishing vertical viscosity. Rev. Mat. Iberoam., 34 (2018), n. 1, 1-58.
  * [67] J. Serrin: The initial value problem for the Navier-Stokes equations. Nonlinear Problems (Proc. Sympos., Madison, Wis., 1962), Univ. of Wisconsin Press, Madison, Wis. (1963), 69-98.
  * [68] T. W. Sturm: “Open channel hydraulics”. McGraw-Hill, Singapore (2001).
  * [69] G. K. Vallis: “Atmospheric and oceanic fluid dynamics: fundamentals and large-scale circulation”. Cambridge University Press, Cambridge (2006).
  * [70] M. Vishik: Hydrodynamics in Besov spaces. Arch. Ration. Mech. Anal., 145 (1998), n. 3, 197-214.
  * [71] A. Wróblewska-Kamińska: The asymptotic analysis of the complete fluid system on a varying domain: from the compressible to the incompressible flow. SIAM J. Math. Anal., 49 (2017), n. 5, 3299-3334.
  * [72] R. Kh. Zeytounian: “Theory and applications of viscous fluid flows”. Springer-Verlag, Berlin (2004).


# General Transformation for Consistent Online Approximation Algorithms

Jing Dong  The Chinese University of Hong Kong, Shenzhen  Yuichi Yoshida
National Institute of Informatics

###### Abstract

We introduce a transformation framework that can be utilized to develop online
algorithms with low $\epsilon$-approximate regret in the random-order model
from offline approximation algorithms. We first give a general reduction
theorem that transforms an offline approximation algorithm with low average
sensitivity to an online algorithm with low $\epsilon$-approximate regret. We
then demonstrate that offline approximation algorithms can be transformed into
a low-sensitivity version using a coreset construction method. To showcase the
versatility of our approach, we apply it to various problems, including online
$(k,z)$-clustering, online matrix approximation, and online regression, and
successfully achieve polylogarithmic $\epsilon$-approximate regret for each
problem. Moreover, we show that in all three cases, our algorithm also enjoys
low inconsistency, which may be desired in some online applications.

##  1 Introduction

In online learning literature, stochastic and adversarial settings are two of
the most well-studied cases. Although the stochastic setting is not often
satisfied in real applications, the performance and guarantees of online
algorithms in the adversarial case are considerably compromised. This is
particularly true for important online tasks such as $k$-means clustering,
which gives a significantly worse guarantee than their offline or stochastic
counterparts (Cohen-Addad et al.,, 2021). As a result, their practical
applicability is greatly limited.

Recently, the random-order model has been introduced as a means of modeling
learning scenarios that fall between the stochastic and adversarial settings
(Garber et al.,, 2020; Sherman et al.,, 2021). In the random-order model, the
adversary is permitted to choose the set of losses, with full knowledge of the
learning algorithm, but has no influence over the order in which the losses
are presented to the learner. Instead, the loss sequence is uniformly and
randomly permuted. This effectively bridges the gap between the stochastic
setting, where only the distribution of losses can be chosen by the setting,
and the adversarial setting, where the adversary has complete control over the
order of the losses presented to the learner.

In this work, we introduce a batch-to-online transformation framework designed
specifically for the random-order model. Our framework facilitates the
conversion of an offline approximation algorithm into an online learning
algorithm with $\epsilon$-approximate regret guarantees. Our primary technical
tool is average sensitivity, which was initially proposed by Varma and
Yoshida, (2021) to describe the algorithm’s average-case sensitivity against
input perturbations. We demonstrate that any offline approximation algorithm
with low average sensitivity will result in a transformed online counterpart
that has low $\epsilon$-approximate regret. To achieve small average
sensitivity for offline algorithms, we leverage the idea of a coreset (Agarwal
et al.,, 2005; Har-Peled and Mazumdar,, 2004), which is a small but
representative subset of a larger dataset that preserves important properties
of the original data. We present a coreset construction method that attains
low average sensitivity, and when combined with the approximation algorithm,
yields an overall algorithm with low average sensitivity.

To showcase the practicality and versatility of our framework, we apply it to
three popular online learning problems: online $(k,z)$-clustering, online
matrix approximation, and online regression. In all three cases, our approach
yields a polylogarithmic $\epsilon$-approximate regret. Furthermore, due to
the low average sensitivity of our algorithms, they also enjoy low
inconsistency, which is the cumulative number of times the solution changes.
This additional property may prove useful in certain online settings. We note
that this inconsistency has also been investigated in the classic online
learning and multi-armed bandits literature (Agrawal et al.,, 1988; Cesa-
Bianchi et al.,, 2013).

##  2 Preliminaries

For a positive integer $n$, let $[n]$ denote the set $\\{1,2,\ldots,n\\}$. For
real values $a,b\in\mathbb{R}$, $a\in(1\pm\epsilon)b$ is a shorthand for
$(1-\epsilon)b\leq a\leq(1+\epsilon)b$.

###  2.1 Offline Learning

We consider a general class of learning problems. Let $\mathcal{X}$ be the
input space, $\Theta$ be the parameter space, and
$\ell:\Theta\times\mathcal{X}\rightarrow$ $\mathbb{R}_{+}$ be a loss function.
For simplicity, we assume the loss is bounded, i.e., $\ell(\theta,x)\leq 1$.
Given a set of $n$ data points $X\in\mathcal{X}^{n}$, we are asked to learn a
parameter $\theta\in\Theta$ that minimizes the objective value
$\ell(\theta,X):=\sum_{x\in X}\ell(\theta,x)$. We call this problem the
_offline learning problem_.

When the exact minimization of the loss function $\ell$ is NP-hard or
computationally demanding, one may only hope to obtain an approximate solution
efficiently. Specifically, for $\alpha>0$, we say a solution $\theta\in\Theta$
is _$\alpha$ -approximate_ for $X\in\mathcal{X}^{n}$ if
$\ell(\theta,X)\leq\alpha\cdot\min_{\tilde{\theta}\in\Theta}\ell(\tilde{\theta},X)$.
The value $\alpha$ is called the _approximation ratio_ of the solution. We say
a (possibly randomized) algorithm $\mathcal{A}$ is _$\alpha$ -approximate_ if
the expected approximation ratio of the output solution is at most $\alpha$.

###  2.2 Online Learning with Random-Order Model

In the _online learning problem_ , instead of receiving all points at once,
the data arrives sequentially throughout a time horizon $n$. Specifically, the
data point comes one by one, where $x_{t}$ comes at time $t\in[n]$. At the
time $t$, using the collected data points $X_{t-1}:=(x_{1},\ldots,x_{t-1})$,
we are asked to output a parameter $\theta_{t}\in\Theta$. Then we receive the
data point $x_{t}$ and incur a loss of $\ell(\theta_{t},x_{t})$. In this work,
we consider the _random-order model_ , in which the data points
$x_{1},\ldots,x_{n}$ may be chosen adversarially, but their ordering is
randomly permuted before the algorithm runs.

To evaluate our performance, we use the notion of regret, which is the
cumulative difference between our solution and the best solution in hindsight.
In cases where obtaining the exact solution is hard, and one may only hope to
obtain an approximate solution efficiently, we use the _$\epsilon$
-approximate regret_.

######  Definition 2.1 ($\epsilon$-approximate regret for the random-order
model).

Given a (randomized) algorithm $\mathcal{A}$ that outputs a sequence of
parameters $\theta_{1},\ldots,\theta_{n}$ when given input
$x_{1},\ldots,x_{n}$. The $\epsilon$-approximate regret of $\mathcal{A}$ for
the random-order model is defined as

$\displaystyle\mathrm{Regret}_{\epsilon}(n):=\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{t}\\}}\left[\sum^{n}_{t=1}\ell(\theta_{t},x_{t})-(1+\epsilon)\cdot\min_{\tilde{\theta}\in\Theta}\sum^{n}_{t=1}\ell(\tilde{\theta},x_{t})\right]\,.$

where the randomness is over the internal randomness of $\mathcal{A}$ and the
ordering of data points. When $\epsilon=0$, we simply call it the _regret_.

In certain cases, online algorithms are required to maintain a good solution
while minimizing _inconsistency_ , which is quantified as the number of times
the solution changes. This can be expressed formally as
$\mathrm{Inconsistency}(n)=\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{t}\\}}[\sum^{n-1}_{t=1}\mathbb{I}\\{\theta_{t}\neq\theta_{t+1}\\}]$,
where $\mathbb{I}$ is the indicator function.

###  2.3 Average sensitivity

On a high level, the notion of average sensitivity describes the differences
in the performance of a randomized algorithm with respect to input changes.
This difference is captured by the total variation distance, which is defined
below.

######  Definition 2.2.

For a measurable space $(\Omega,\mathcal{F})$ and probability measures $P,Q$
defined on $(\Omega,\mathcal{F})$. The total variation distance between $P$
and $Q$ is defined as
$\mathrm{TV}(P,Q):=\sup_{A\in\mathcal{A}}\left|P(A)-Q(A)\right|$.

Equipped with this, the average sensitivity of a randomized algorithm is
formally defined as the average total variation distance between the
algorithm’s output on two training data sets that differ by deleting one point
randomly. For a dataset $X=(x_{1},\ldots,x_{n})\in\mathcal{X}^{n}$ and
$i\in[n]$, let $X^{(i)}$ denote the set
$(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n})$ obtained by deleting the $i$-th
data point. Then, the following definition gives a detailed description of the
notion:

######  Definition 2.3 (Average Sensitivity Varma and Yoshida, (2021); Yoshida
and Ito, (2022)).

Let $\mathcal{A}$ be a (randomized) algorithm that takes an input
$X\in\mathcal{X}^{n}$ and outputs $\mathcal{A}(X)$. For
$\beta:\mathbb{Z}_{+}\to\mathbb{R}_{+}$, we say that the average sensitivity
of $\mathcal{A}$ is at most $\beta$ if

$\displaystyle\frac{1}{n}\sum^{n}_{i=1}\mathrm{TV}(\mathcal{A}(X),\mathcal{A}(X^{(i)}))\leq\beta(n)\,.$

for any $X\in\mathcal{X}^{n}$, where we identify $\mathcal{A}(X)$ and
$\mathcal{A}(X^{(i)})$ with their distributions.

##  3 Batch-to-Online Transformation in the Random-Order Model

In this section, we describe a general framework that can transform any
offline $(1+\epsilon)$-approximate algorithm into an online algorithm with low
$\epsilon$-approximate regret. Our goal is to show the following.

######  Theorem 3.1.

Let $\mathcal{A}$ be a (randomized) $(1+\epsilon)$-approximate algorithm for
the offline learning algorithm with average sensitivity
$\beta:\mathbb{Z}_{+}\to\mathbb{R}_{+}$. Then, there exists an online learning
algorithm in the random-order model such that
$\mathrm{Regret}_{\epsilon}(n)=O\left(\sum^{n}_{t=1}\beta(t)+1\right)$.

Our method is described in Algorithm 1. Let $\mathcal{A}$ be an approximation
algorithm for the offline learning algorithm. Then, at each time step, based
on the collected data $X_{t-1}$, we simply output
$\theta_{t}=\mathcal{A}(X_{t-1})$.

Input: Offline approximation algorithm $\mathcal{A}$.

1for  _$t=1,\ldots,n$_ do

2 Obtain $\theta_{t}$ by running $\mathcal{A}$ on $X_{t-1}$.

3 Receive $x_{t}$ and $\ell(\theta_{t},x_{t})$.

Algorithm 1 General batch-to-online conversion

To show that Algorithm 1 achieves a low approximate regret when $\mathcal{A}$
has a low average sensitivity, the following lemma is useful.

######  Lemma 3.2.

Let $\mathcal{A}$ be a (randomized) algorithm for the offline learning problem
with average sensitivity $\beta:\mathbb{Z}_{+}\to\mathbb{R}_{+}$. Then for any
input $X\in\mathcal{X}^{n}$, we have

$\frac{1}{n}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X^{(i)}),x_{i})]=\frac{1}{n}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X),x_{i})]\pm\beta(n)\,,$

###### Proof of Theorem 3.1.

Consider Algorithm 1. For any $t\in[n]$, we have

$\displaystyle\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\ell(\theta_{t+1},x_{t+1})-\frac{1}{t}\ell(\theta_{t+1},X_{t})\right]=\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\frac{1}{t}\sum^{t}_{i=1}\left(\ell(\theta_{t+1},x_{t+1})-\ell(\theta_{t+1},x_{i})\right)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\frac{1}{t}\sum^{t}_{i=1}\left(\ell(\mathcal{A}(X_{t}),x_{t+1})-\ell(\mathcal{A}(X_{t}),x_{i})\right)\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\frac{1}{t}\sum^{t}_{i=1}\left(\ell(\mathcal{A}(X_{t}),x_{t+1})-\ell(\mathcal{A}(X_{t}^{(i)}),x_{i})\right)\right]+\beta(t)$
(By Lemma 3.2)
$\displaystyle=\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\frac{1}{t}\sum^{t}_{i=1}\left(\ell(\mathcal{A}(X_{t}),x_{t+1})-\ell(\mathcal{A}(X_{t}^{(i)}),x_{t+1})\right)\right]+\beta(t)$
$\displaystyle\leq\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\frac{1}{t}\sum^{t}_{i=1}\mathrm{TV}(\mathcal{A}(X_{t}),\mathcal{A}(X_{t}^{(i)}))\right]+\beta(t)\leq
2\beta(t)\,,$

where the last equality follows by replacing $x_{i}$ with $x_{t+1}$ in
$\ell(\mathcal{A}(X_{t}^{(i)}),x_{i})$ because they have the same
distribution, and the last inequality is by the average sensitivity of the
algorithm.

Rearranging the terms, we have

$\displaystyle\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\ell(\theta_{t+1},x_{t+1})\right]\leq\
$
$\displaystyle\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\frac{\ell(\theta_{t+1},X_{t})}{t}\right]+2\beta(t)\leq\
\mathop{\mathbb{E}}_{\\{x_{i}\\}}\left[\frac{(1+\epsilon)\mathrm{OPT}_{t}}{t}\right]+2\beta(t)\,,$

where $\mathrm{OPT}_{t}:=\min_{\theta}\ell(\theta,X_{t})$ is the optimal value
with respect to $X_{t}$, and the second inequality holds because the
approximation ratio of $\theta_{t+1}$ is $1+\epsilon$ in expectation.

Taking summation over both sides, we have

$\displaystyle\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\sum^{n}_{t=1}\ell(\theta_{t},x_{t})\right]=\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\ell(\theta_{1},x_{1})\right]+\mathop{\mathbb{E}}_{\mathcal{A},\\{x_{i}\\}}\left[\sum^{n-1}_{t=1}\ell(\theta_{t+1},x_{t+1})\right]$
$\displaystyle\leq
1+\mathop{\mathbb{E}}_{\\{x_{i}\\}}\left[\sum^{n-1}_{t=1}\frac{(1+\epsilon)\mathrm{OPT}_{t}}{t}\right]+2\sum^{n-1}_{t=1}\beta(t)\,.$

Fix the ordering $x_{1},\ldots,x_{n}$, and let $c_{i}\;(i\in[t])$ be the loss
incurred by $x_{i}$ in $\mathrm{OPT}_{n}$. In particular, we have
$\mathrm{OPT}_{n}=\sum^{n}_{i=1}c_{i}$. Note that $c_{i}$’s are random
variables depending on the ordering of data points, but their sum,
$\mathrm{OPT}_{n}$, is deterministic. Then, we have
$\mathrm{OPT}_{t}\leq\sum^{t}_{i=1}c_{i}$ because $\mathrm{OPT}_{t}$ minimizes
the loss up to time $t$, Hence, we have

$\displaystyle\mathop{\mathbb{E}}_{\\{x_{i}\\}}\left[\sum^{n}_{t=1}\frac{\mathrm{OPT}_{t}}{t}\right]\leq\mathop{\mathbb{E}}_{\\{x_{i}\\}}\left[\sum^{n}_{t=1}\frac{\sum^{t}_{i=1}c_{i}}{t}\right]=\mathop{\mathbb{E}}_{\\{x_{i}\\}}\left[\sum^{n}_{i=1}c_{i}\sum^{n}_{t=i}\frac{1}{t}\right]=\sum^{n}_{i=1}\mathop{\mathbb{E}}_{\\{x_{i}\\}}[c_{i}]\sum^{n}_{t=i}\frac{1}{t}$
$\displaystyle=\frac{\mathrm{OPT}_{n}}{n}\cdot\sum^{n}_{i=1}\sum^{n}_{t=i}\frac{1}{t}=\frac{\mathrm{OPT}_{n}}{n}\cdot
n=\mathrm{OPT}_{n}\,.$

Therefore, we have

$\mathbb{E}_{\mathcal{A},\\{x_{i}\\}}\left[\sum^{n}_{t=1}\ell(\theta_{t},x_{t})\right]-(1+\epsilon)\mathrm{OPT}_{n}=O\left(\sum^{n}_{t=1}\beta(t)+1\right)\,.\qed$

##  4 Approximation Algorithm with Low Average Sensitivity via Coreset

To design approximation algorithms for the offline learning problem with low
average sensitivity, we consider the following approach: We first construct a
small subset of the input that well preserves objective functions, called a
coreset, with small average sensitivity, and then apply any known
approximation algorithm on the coreset. Coreset is formally defined as
follows:

######  Definition 4.1 (Har-Peled and Mazumdar, (2004); Agarwal et al.,
(2005)).

Let $\ell:\Theta\times\mathcal{X}\rightarrow\mathbb{R}_{+}$ be a loss function
and let $X\in\mathcal{X}^{n}$. For $\epsilon>0$, we say that a weighted set
$\left(Y,w\right)$ with $Y\subseteq X$ and $w:Y\to\mathbb{R}_{+}$ is an
$\epsilon$-coreset of $X$ with respect to $\ell$ if for any $\theta\in\Theta$,
we have $\sum_{y\in Y}w(y)\ell(\theta,y)\in(1\pm\epsilon)\sum_{x\in
X}\ell(\theta,x)$.

Now, we consider a popular method for constructing coresets based on
importance sampling and show that it enjoys a low average sensitivity. For a
data $x\in X$, its _sensitivity_ $\sigma_{X}(x)$111The reader should not
confuse sensitivity, which is a measure for data points, with average
sensitivity, which is a measure for algorithms. is its maximum contribution to
the loss of the whole dataset, or more formally

$\displaystyle\sigma_{X}(x)=\sup_{\theta\in\Theta}\frac{\ell(\theta,x)}{\ell(\theta,X)}\,.$
(1)

Input: Loss function $\ell:\Theta\times\mathcal{X}\to\mathbb{R}_{+}$, dataset
$X\in\mathcal{X}^{n}$, $m\in\mathbb{N}$, and $\epsilon>0$

1 For each $x\in X$, compute $\sigma_{X}(x)$ and set
$p(x)=\sigma_{X}(x)/\sum_{x^{\prime}\in X}\sigma_{X}(x^{\prime})$.

2 Let $S$ be an empty set.

3 for  _$i=1,\ldots,m$_ do

4 Sample $x$ with probability $p(x)$.

5 Sample $\tilde{p}$ from $[p(x),(1+\epsilon/2)p(x)]$ uniformly at random.

6 if  _$w(x)$ is undefined_ then

7 $S\leftarrow S\cup\\{x\\}$.

8 $w(x)\leftarrow 1/\tilde{p}$.

9 else

10 $w(x)\leftarrow w(x)+1/\tilde{p}$.

11 return $(S,w)$.

Algorithm 2 Coreset Construction Based on Sensitivity Sampling

It is known that we can construct a coreset as follows: A point $x\in X$ is
sampled with probability $p(x):=\sigma_{X}(x)/\sum_{x^{\prime}\in
X}\sigma_{X}(x^{\prime})$, and then its weight in the output coreset is
increased by $1/\tilde{p}$, where $\tilde{p}$ is a slight perturbation of
$p(x)$. This process is to be repeated for a fixed number of times, where the
exact number depends on the approximation ratio of the coreset. See Algorithm
2 for details. We can bound its average sensitivity as follows:

######  Lemma 4.2.

The average sensitivity of Algorithm 2 is $O\left(\epsilon^{-1}m/n\right)$.

A general bound on the number of times we need to repeat the process, i.e.,
$m$ in Algorithm 2, to obtain an $\epsilon$-coreset is known (see, e.g.,
Theorem 5.5 of Braverman et al., (2016)). However, we do not discuss it here
because better bounds are known for specific problems and we do not use the
general bound in the subsequent sections.

##  5 Online $(k,z)$-Clustering

In online applications, unlabelled data are abundant and their structure can
be essential, and clustering serves as an important tool for analyzing them.
In this section, as an application of our general batch-to-online
transformation, we describe an online $(k,z)$-clustering method that enjoys
low regret.

###  5.1 Problem setup

The online $(k,z$)-clustering problem (Cohen-Addad et al.,, 2021) is an
instance of the general online learning problem described in Section 2. We
describe the problem as follows: Let $k\geq 1$ be an integer and $z\geq 1$ be
a real value. Over a time horizon $n$, at each time step $t$, a data point
$x_{t}\in\mathbb{R}^{d}$ is given. Using the set of data points
$X_{t-1}=\\{x_{1},\ldots,x_{t-1}\\}$, we are asked to compute a set
$Z_{t}=\left\\{z_{1},\ldots,z_{k}\right\\}$ of $k$ points in $\mathbb{R}^{d}$
that minimize
$\ell\left(Z_{t},x_{t}\right):=\min_{j=1,\ldots,k}\left\|x_{t}-z_{j}\right\|_{2}^{z}$,
which is the $z$-th power of the Euclidean distance between $x_{t}$ and the
closest point in $Z_{t}$. Note that $Z_{t}$ plays the role of $\theta_{t}$ in
the general online learning problem. The regret and $\epsilon$-approximate
regret are defined accordingly.

###  5.2 Method and results

One important ingredient to our method is the coreset construction method
proposed by Huang and Vishnoi, (2020). The method provides a unified two-stage
importance sampling framework, which allows for a coreset with a size that is
dimension independent. Specifically, the method constructs an
$\epsilon$-coreset of size
$\tilde{O}\left(\min\left\\{\varepsilon^{-2z-2}k,2^{2z}\epsilon^{-4}k^{2}\right\\}\right)$
in $\tilde{O}(ndk)$ time, where the $\tilde{O}$ hides logarithmic factors in
$n$ and $k$. We remark that the importance of sampling steps in the framework
is similar to the ones described in Section 4, which thus allows us to analyze
its average sensitivity.

Algorithm 3 gives a brief description of our algorithm, while a detailed
description is presented in the appendix. The algorithm adheres to the
standard transformation approach, whereby an offline approximation algorithm
is run on the coreset derived from the aggregated data.

Input: Offline algorithm $\mathcal{A}$ for $(k,z)$-clustering, approximation
ratio $\epsilon\in(0,1)$.

1 $\epsilon^{\prime}\leftarrow\epsilon/3$.

2 for  _$t=1,\ldots,n$_ do

3 Construct an $\epsilon^{\prime}$-coreset $C_{t-1}=(S_{t-1},\omega_{t-1})$ on
$X_{t-1}$.

4 Obtain a cluster set $Z_{t}$ by running $\mathcal{A}$ with approximation
ratio of $(1+\epsilon^{\prime})$ on $C_{t-1}$.

5 Receive $x_{t}\in\mathbb{R}^{d}$ and $\ell(Z_{t},x_{t})\in\mathbb{R}_{+}$.

Algorithm 3 Online consistent $(k,z)$-clustering

######  Theorem 5.1.

For any $\epsilon\in(0,1)$, Algorithm 3 gives a regret bound of

$\displaystyle\mathrm{Regret}_{\epsilon}(n)\leq
O\left(\left({(168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{kn}{\epsilon}+\epsilon^{-2z-2}k\log
k\log\frac{kn}{\epsilon}}\right)\log n\right)\,.$

Moreover, there exists an algorithm that enjoys the same regret bound and an
inconsistency bound of
$\mathrm{Inconsistency}(n)=O\left(\left({(168z)^{10z}\epsilon^{-5z-15}k^{5}\log(\epsilon^{-1}kn)+\epsilon^{-2z-2}k\log
k\log(\epsilon^{-1}kn)}\right)\log n\right)$ for $(k,z)$-clustering.

######  Remark 5.1.

When $z=2$, previous results for the adversarial setting show an
$\epsilon$-approximate regret bound of
$O(k\sqrt{d^{3}n}\log(\epsilon^{-1}dkn))$ (Cohen-Addad et al.,, 2021). In
comparison, although our regret is for the random-order model, our method and
results accommodate a range of values for $z$, and the regret bound is only
polylogarithmically dependent on $n$ and is independent of the dimension $d$.

##  6 Online Low-Rank Matrix Approximation

Low-rank matrix approximation serves as a fundamental tool in statistics and
machine learning. The problem is to find a rank-$k$ matrix that approximates
an input matrix ${\mathbf{A}}\in{\mathbb{R}}^{d\times n}$ as much as possible.
In this section, we apply the transformation framework to the offline
approximation algorithm to obtain a low regret online algorithm.

###  6.1 Problem setup

#### Low-rank matrix approximation

By the singular value decomposition (SVD), a rank-$r$ matrix
${\mathbf{A}}\in{\mathbb{R}}^{d\times n}$ can be decomposed as
${\mathbf{A}}={\mathbf{U}}\mathbf{\Sigma}{\mathbf{V}}^{\top}$, where
${\mathbf{U}}\in{\mathbb{R}}^{d\times r}$ and
${\mathbf{V}}\in{\mathbb{R}}^{n\times r}$ are orthonormal matrices,
$\mathbf{\Sigma}\in\mathbb{R}^{r\times r}$ is a diagonal matrix with
${\mathbf{A}}$’s singular values on the diagonal. The best rank-$k$
approximation of ${\mathbf{A}}$ is given by

$\displaystyle{\mathbf{A}}_{k}={\mathbf{U}}_{k}\mathbf{\Sigma}_{k}{\mathbf{V}}_{k}^{\top}=\mathop{\rm
argmin}_{{\mathbf{B}}\in\mathbb{R}^{d\times n}:\mathrm{rank}({\mathbf{B}})\leq
k}\left\|{\mathbf{A}}-{\mathbf{B}}\right\|_{F}\,,$

where $\|\cdot\|_{F}$ denotes the Frobenius norm,
$\mathbf{\Sigma}_{k}\in{\mathbb{R}}^{k\times k}$ is a diagonal matrix with
${\mathbf{A}}_{k}$’s top $k$ singular values on the diagonal, and
${\mathbf{U}}_{k}\in{\mathbb{R}}^{d\times k}$ and
${\mathbf{V}}_{k}\in{\mathbb{R}}^{n\times k}$ are orthonormal matrices
obtained from ${\mathbf{U}}$ and ${\mathbf{V}}$, respectively, by gathering
corresponding columns. The best rank-$k$ approximation can also be found by
projecting ${\mathbf{A}}$ onto the span of its top $k$ singular vectors, that
is, ${\mathbf{A}}_{k}={\mathbf{U}}_{k}{\mathbf{U}}_{k}^{\top}{\mathbf{A}}$.
Then, we can say an orthonormal matrix ${\mathbf{Z}}$ is an
$\epsilon$-approximate solution if

$\displaystyle\left\|{\mathbf{A}}-{\mathbf{Z}}{\mathbf{Z}}^{\top}{\mathbf{A}}\right\|_{F}\leq(1+\epsilon)\left\|{\mathbf{A}}-{\mathbf{U}}_{k}{\mathbf{U}}_{k}^{\top}{\mathbf{A}}\right\|_{F}\,.$

The matrix approximation problem serves as an important tool in data analytics
and is closely related to numerous machine learning methods such as principal
component analysis and least square analysis. When dealing with streaming
data, the online version of the matrix approximation problem becomes a vital
tool for designing online versions of the machine learning algorithms
mentioned above.

#### Online matrix approximation

Through a time horizon of $n$, we receive a column of ${\mathbf{A}}$,
$a_{t}\in{\mathbb{R}}^{d}$ at each time step $t$. We are then asked to compute
${\mathbf{Z}}_{t}\in{\mathbb{R}}^{d\times k}$ that minimizes

$\displaystyle\ell({\mathbf{Z}}_{t},a_{t})=\left\|a_{t}-{\mathbf{Z}}_{t}{\mathbf{Z}}_{t}^{\top}a_{t}\right\|_{F}\,.$

Without loss of generality, we will assume that the losses are bounded between
$[0,1]$. We remark that similar assumptions are also assumed in Nie et al.,
(2016).

The online matrix approximation problem serves as a core component of online
machine learning algorithms such as principle component analysis. These
algorithms are important to a range of applications, such as online
recommendation systems and online experimental design (Warmuth and Kuzmin,,
2008; Nie et al.,, 2016).

###  6.2 Method and results

In the context of low-rank matrix approximation, the coreset of a matrix is
called the projection-cost preserving samples, defined as follows:

######  Definition 6.1 (Rank-$k$ Projection-Cost Preserving Sample Cohen et
al., (2017)).

For $n^{\prime}<n$, a subset of rescaled columns
$\mathbf{C}\in\mathbb{R}^{d\times n^{\prime}}$ of
$\mathbf{A}\in\mathbb{R}^{d\times n}$ is a $(1+\epsilon)$ projection-cost
preserving sample if, for all rank-$k$ orthogonal projection matrices
$\mathbf{X}\in\mathbb{R}^{d\times d}$,
$(1-\epsilon)\|{\mathbf{A}}-\mathbf{X}{\mathbf{A}}\|_{F}^{2}\leq\|\mathbf{C}-\mathbf{X}\mathbf{C}\|_{F}^{2}\leq(1+\epsilon)\|{\mathbf{A}}-\mathbf{X}{\mathbf{A}}\|_{F}^{2}$.

Such sketches that satisfy Definition 6.1 can be constructed via importance
sampling-based routines, which are modifications of the “leverage scores”.
Specifically, for the $i$-th column $a_{i}$ of matrix $A$, the _ridge leverage
score_ is defined as
$\tau_{i}({\mathbf{A}})=a_{i}^{\top}\left({\mathbf{A}}{\mathbf{A}}^{\top}+\frac{\left\|{\mathbf{A}}-{\mathbf{A}}_{k}\right\|_{F}^{2}}{k}\mathbf{I}\right)^{\dagger}a_{i}$,
where $\dagger$ denotes the Moore-Penrose pseudoinverse of a matrix (Cohen et
al.,, 2017).

Now, we introduce our online matrix approximation algorithm in Algorithm 4,
which builds upon our transformation framework. It computes the approximation
of the matrix from the sketch derived from the aggregated matrix using ridge
leverage scores.

Input: Approximation parameters $\epsilon\in(0,1)$.

1 Set $\delta=O(\epsilon/n)$ and
$m=O\left(\epsilon^{-2}k\log(\delta^{-1}k)\right)$.

2 for  _$t=1,\ldots,n$_ do

3 Construct ${\mathbf{A}}_{t-1}\in{\mathbb{R}}^{d\times(t-1)}$ by
concatenating $a_{1},\ldots a_{t-1}$.

4 Let ${\mathbf{C}}_{t-1}\in{\mathbb{R}}^{d\times m}$ be the zero matrix.

5 for  _$j=1,\ldots,m$_ do

6 Sample the $i$-th column $a_{i}\in\mathbb{R}^{d}$ of ${\mathbf{A}}_{t-1}$
with probability
$p_{i}:=\frac{\tau_{i}({\mathbf{A}}_{t-1})}{\sum_{j=1}^{t-1}\tau_{j}({\mathbf{A}}_{t-1})}$.

7 Sample $w\in\mathbb{R}$ uniformly from
$[1/\sqrt{tp_{i}},(1+\epsilon)/\sqrt{tp_{i}}]$.

8 Replace the $j$-th column of ${\mathbf{C}}_{t-1}$ with $w\cdot a_{i}$.

9 Set ${\mathbf{Z}}_{t}\in\mathbb{R}^{d\times k}$ to the top $k$ left singular
vectors of ${\mathbf{C}}_{t}$

10 Receive $a_{t}\in\mathbb{R}^{d}$ and
$\ell({\mathbf{Z}}_{t},a_{t})\in\mathbb{R}_{+}$.

11

Algorithm 4 Online consistent low rank matrix approximation

######  Theorem 6.2.

For any $\epsilon\in(0,1)$, Algorithm 4 has regret
$\mathrm{Regret}_{\epsilon}(n)=O\left(\epsilon^{-2}k\log
n\log(\epsilon^{-1}kn)\right)$. Moreover, there exists an algorithm for online
low-rank matrix approximation that enjoys the same regret bound and an
inconsistency bound of $\mathrm{Inconsistency}(n)=O\left(\epsilon^{-2}k\log
n\log(\epsilon^{-1}kn)\right)$.

######  Remark 6.1.

The online matrix approximation with the random-order setting has previously
been investigated in the context of principle component analysis by Garber et
al., (2020). They established a regret of $O\left(\zeta^{-1}\sqrt{kn}\right)$,
where $\zeta$ is the smallest difference between two eigenvalues of
${\mathbf{A}}_{t}{\mathbf{A}}_{t}^{\top}$. In contrast, our result gives a
polylogarithmic result on $\epsilon$-regret, which translate to an exact
regret of $O(\epsilon\mathrm{OPT}+O\left(\epsilon^{-2}k\log
n\log(\epsilon^{-1}kn)\right))$, with $\mathrm{OPT}$ being the minimum
possible cumulative loss attained by the hindsight best approximate.

##  7 Online Regression

In the online regression problem, at each time step $t\in[n]$, we are asked to
output a vector $x_{t}\in\mathbb{R}^{d}$, and then we receive vectors
$a_{t}\in\mathbb{R}^{d}$ and $b_{t}\in{\mathbb{R}}$ that incurs the loss of
$\ell(x_{t},a_{t},b_{t})=\|a_{t}^{\top}x_{t}-b\|_{2}$. Without loss of
generality, we assume that the losses are bounded between $[0,1]$. We note
that similar assumptions are also assumed in (Cesa-Bianchi et al.,, 1996;
Ouhamma et al.,, 2021).

With our general reduction framework, we show an $\epsilon$-regret upper bound
as follows.

######  Theorem 7.1.

For any $\epsilon\in(0,1)$, Algorithm 5 has regret
$\mathrm{Regret}_{\epsilon}(n)=O\left(\epsilon^{-2}d\log
n\log(\epsilon^{-1}dn)\right)$. Moreover, there exists an algorithm for online
regression that enjoys the same regret bound and an inconsistency bound of
$\mathrm{Inconsistency}(n)=O\left(\epsilon^{-2}d\log
n\log(\epsilon^{-1}dn)\right)$.

######  Remark 7.1.

In the stochastic setting, the online regression problem has been extensively
investigated (Foster,, 1991; Littlestone et al.,, 1995; Cesa-Bianchi et al.,,
1996; Ouhamma et al.,, 2021). Using online ridge regression or forward
algorithms, the regret is shown to be $O\left(d\log n\right)$. In the random-
order model setting, Garber et al., (2020); Sherman et al., (2021) give
$O(\sqrt{n})$-type regret when the loss is strongly convex or the matrix
${\mathbf{A}}$ has a small condition number. In comparison, our result attains
polylogarithmic $\epsilon$-approximate regret, while maintaining no
requirement on the loss function or the condition number. Our result can be
translated to an exact regret of
$O(\epsilon\mathrm{OPT}+O\left(\epsilon^{-2}d\log
n\log(\epsilon^{-1}dn)\right)$, with $\mathrm{OPT}$ being the minimum possible
cumulative loss attained by the hindsight best parameter.

###  7.1 Method and results

Similar to the low-rank matrix approximation problem, we utilize the leverage
score method to learn a subspace that preserves information regarding the
regression. Specifically, we use the leverage score to learn a
$\epsilon$-subspace embedding, which is defined as follows.

######  Definition 7.2 ($\epsilon$-Subspace Embedding).

A matrix ${\mathbf{S}}\in{\mathbb{R}}^{m\times n}$ is said to be an
$\epsilon$-subspace embedding of ${\mathbf{A}}\in{\mathbb{R}}^{n\times d}$ if
for any vector $x\in{\mathbb{R}}^{d}$, we have
$(1-\epsilon)\|{\mathbf{A}}x\|\leq\|{\mathbf{S}}{\mathbf{A}}x\|\leq(1+\epsilon)\|{\mathbf{A}}x\|$.

The subspace embedding serves the same functionality as coreset in the problem
of matrix approximation, it preserves the loss of information while enjoying a
much lower dimension. In the online regression problem context, we define the
leverage score as follows.

######  Definition 7.3 (Leverage Score).

Let ${\mathbf{A}}={\mathbf{U}}\mathbf{\Sigma}{\mathbf{V}}^{\top}$ be the
singular value decomposition of ${\mathbf{A}}\in{\mathbb{R}}^{n\times d}$. For
$i\in[n]$, the $i$-th leverage score of ${\mathbf{A}}$, is defined as
$\tau_{i}=\left\|{\mathbf{U}}_{i,:}\right\|_{2}^{2}$.

With the leverage score, we propose Algorithm 5. The algorithm follows the
general transformation framework, where the regression problem is solved at
every step with the sketch derived from the aggregated matrix using leverage
score. For notational convenience, we construct the sketch by appending rows
instead of columns as we did in Section 6.

Input: Approximation parameters $\epsilon\in(0,1)$

1 Set $\delta=O(\epsilon/n)$ and
$m=O\left(\epsilon^{-2}d\log(\delta^{-1}d)\right)$.

2 for  _$t=1,\ldots,n$_ do

3 Construct ${\mathbf{A}}_{t-1}\in{\mathbb{R}}^{(t-1)\times d}$ by stacking
$a_{1}^{\top},\ldots a_{t-1}^{\top}$.

4 Construct $b\in{\mathbb{R}}^{t-1}$ by stacking $b_{1},\ldots,b_{t-1}$.

5 Set ${\mathbf{S}}^{t}\in\mathbb{R}^{m\times(t-1)}$ be the zero matrix.

6 for  _$j=1,\ldots,m$_ do

7 Sample $i\in[t-1]$ with probability
$p_{i}:=\frac{\tau_{i}({\mathbf{A}}_{t-1})}{\sum_{j=1}^{t-1}\tau_{j}({\mathbf{A}}_{t-1})}$.

8 Sample $w\in\mathbb{R}$ uniformly from
$\left[\frac{1}{\sqrt{mp_{i}}},\frac{1+\epsilon}{\sqrt{mp_{i}}}\right]$.

9 Replace the $j$-th row of ${\mathbf{S}}^{t}$ with $w\cdot e_{i}^{\top}$,
where $e_{i}\in{\mathbb{R}}^{t-1}$ is a one-hot vector with $1$ on the $i$-th
index.

10 Solve the regression problem
$x_{t}=\min_{x}\|{\mathbf{S}}^{t}{\mathbf{A}}_{t-1}x-{\mathbf{S}}^{t}b\|_{2}$,
e.g., by an iterative method such as Newton’s method.

11 Receive $a_{t}\in{\mathbb{R}}^{d}$, $b_{t}\in{\mathbb{R}}$, and loss
$\ell(x_{t},a_{t},b_{t})$.

12

Algorithm 5 Online consistent regression

The subspace embedding result of (Woodruff,, 2014) immediately shows the
following:

######  Theorem 7.4.

For any $\epsilon,\delta\in(0,1)$, if
$m=O\left(\epsilon^{-2}d\log(\delta^{-1}d)\right)$, then with probability
$\geq 1-\delta$, ${\mathbf{S}}^{t}$ is an $\epsilon$-subspace embedding for
${\mathbf{A}}_{t-1}$ with $O\left(\epsilon^{-2}d\log(\delta^{-1}d)\right)$
columns.

To obtain Theorem 7.1, we first analyze the average sensitivity of the
leverage score sampling. Then, with Theorem 7.4 and the general reduction
Theorem 3.1, we obtain the regret bound.

## Acknowledgement

This work is supported by JSPS KAKENHI Grant Number 20H05965 and 22H05001.

## References

  * Agarwal et al., (2005) Agarwal, P. K., Har-Peled, S., Varadarajan, K. R., et al. (2005).  Geometric approximation via coresets.  Combinatorial and computational geometry, 52(1):1–30.
  * Agrawal et al., (1988) Agrawal, R., Hedge, M., and Teneketzis, D. (1988).  Asymptotically efficient adaptive allocation rules for the multiarmed bandit problem with switching cost.  IEEE Transactions on Automatic Control, 33(10):899–906.
  * Braverman et al., (2016) Braverman, V., Feldman, D., Lang, H., Statman, A., and Zhou, S. (2016).  New frameworks for offline and streaming coreset constructions.  arXiv preprint arXiv:1612.00889.
  * Cesa-Bianchi et al., (2013) Cesa-Bianchi, N., Dekel, O., and Shamir, O. (2013).  Online learning with switching costs and other adaptive adversaries.  Advances in Neural Information Processing Systems.
  * Cesa-Bianchi et al., (1996) Cesa-Bianchi, N., Long, P. M., and Warmuth, M. K. (1996).  Worst-case quadratic loss bounds for prediction using linear functions and gradient descent.  IEEE Transactions on Neural Networks, 7(3):604–619.
  * Cohen et al., (2017) Cohen, M. B., Musco, C., and Musco, C. (2017).  Input sparsity time low-rank approximation via ridge leverage score sampling.  In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms.
  * Cohen-Addad et al., (2021) Cohen-Addad, V., Guedj, B., Kanade, V., and Rom, G. (2021).  Online $k$-means clustering.  In International Conference on Artificial Intelligence and Statistics.
  * Feldman and Langberg, (2011) Feldman, D. and Langberg, M. (2011).  A unified framework for approximating and clustering data.  In Proceedings of the 43th Annual ACM SIGACT Symposium on Theory of Computing.
  * Foster, (1991) Foster, D. P. (1991).  Prediction in the worst case.  The Annals of Statistics, pages 1084–1090.
  * Garber et al., (2020) Garber, D., Korcia, G., and Levy, K. (2020).  Online convex optimization in the random order model.  In International Conference on Machine Learning.
  * Har-Peled and Mazumdar, (2004) Har-Peled, S. and Mazumdar, S. (2004).  On coresets for $k$-means and $k$-median clustering.  In Proceedings of the 36th Annual ACM SIGACT Symposium on Theory of Computing.
  * Huang and Vishnoi, (2020) Huang, L. and Vishnoi, N. K. (2020).  Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.
  * Kumabe and Yoshida, (2022) Kumabe, S. and Yoshida, Y. (2022).  Average sensitivity of dynamic programming.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms.
  * Littlestone et al., (1995) Littlestone, N., Warmuth, M. K., and Long, P. M. (1995).  On-line learning of linear functions.  Computational Complexity, 5:1–23.
  * Nie et al., (2016) Nie, J., Kotłowski, W., and Warmuth, M. K. (2016).  Online PCA with optimal regret.  The Journal of Machine Learning Research, 17(1):6022–6070.
  * Ouhamma et al., (2021) Ouhamma, R., Maillard, O.-A., and Perchet, V. (2021).  Stochastic online linear regression: the forward algorithm to replace ridge.  Advances in Neural Information Processing Systems.
  * Sherman et al., (2021) Sherman, U., Koren, T., and Mansour, Y. (2021).  Optimal rates for random order online optimization.  Advances in Neural Information Processing Systems.
  * Varma and Yoshida, (2021) Varma, N. and Yoshida, Y. (2021).  Average sensitivity of graph algorithms.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms.
  * Warmuth and Kuzmin, (2008) Warmuth, M. K. and Kuzmin, D. (2008).  Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension.  Journal of Machine Learning Research, 9(Oct):2287–2320.
  * Woodruff, (2014) Woodruff, D. P. (2014).  Sketching as a tool for numerical linear algebra.  Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157.
  * Yoshida and Ito, (2022) Yoshida, Y. and Ito, S. (2022).  Average sensitivity of Euclidean $k$-clustering.  In Advances in Neural Information Processing Systems.

##  Appendix A Proofs for Section 3

See 3.2

###### Proof.

We have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X^{(i)}),x_{i})]$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X),x_{i})]+\frac{1}{n}\sum_{i=1}^{n}\bigl{|}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X),x_{i})]-\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X^{(i)}),x_{i})]\bigr{|}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X),x_{i})]+\frac{1}{n}\sum_{i=1}^{n}\mathrm{TV}(\mathcal{A}(X),\mathcal{A}(X^{(i)}))$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\mathcal{A}}[\ell(\mathcal{A}(X),x_{i})]+\beta(n).$

The other direction can be shown analogously. ∎

##  Appendix B Proofs for Section 4

In this section, we prove Lemma 4.2.

######  Lemma B.1.

For any $i\in[n]$ and $x\in X^{(i)}$, let $\theta^{(i)}=\mathop{\rm
argmax}_{\theta}\frac{\ell(\theta,x)}{\sum_{x^{\prime}\in
X^{(i)}}\ell(\theta,x^{\prime})}$. Then, we have

$\displaystyle
0\leq\sigma_{X^{(i)}}(x)-\sigma_{X}(x)\leq\frac{\ell\left(\theta^{(i)},x_{i}\right)\cdot\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)\cdot\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)}\,.$

###### Proof.

Denote $\theta=\mathop{\rm
argmax}_{\theta}\frac{\ell(\theta,x)}{\sum_{x^{\prime}\in
X}\ell(\theta,x^{\prime})}$, then for the left-hand side of the inequality, we
have

$\displaystyle\sigma_{X^{(i)}}(x)-\sigma_{X}(x)\geq\ $
$\displaystyle\frac{\ell(\theta,x)}{\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta,x^{\prime}\right)}-\frac{\ell(\theta,x)}{\sum_{x^{\prime}\in
X}\ell\left(\theta,x^{\prime}\right)}$ $\displaystyle\geq\ $ $\displaystyle
0\,.$

For the second inequality, we have

$\displaystyle\sigma_{X^{(i)}}(x)-\sigma_{X}(x)\leq\ $
$\displaystyle\frac{\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)}-\frac{\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)}$ $\displaystyle=\ $
$\displaystyle\frac{\ell\left(\theta^{(i)},x_{i}\right)\cdot\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)\cdot\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)}\,.$

∎

######  Lemma B.2.

For any $i\in[n]$, we have

$\displaystyle\sum^{n}_{i=1}\left|\sum_{x\in
X}\sigma_{X}(x)-\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})\right|\leq\sum_{x\in X}\sigma_{X}(x)\,.$

###### Proof.

By Lemma B.1, we have

$\sum_{x\in X}\sigma_{X}(x)-\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})=\sigma_{X}\left(x_{i}\right)-\sum_{x\in
X^{(i)}}\left(\sigma_{X^{(i)}}(x)-\sigma_{X}(x)\right)\leq\sigma_{X}\left(x_{i}\right)\,,$

and we have

$\displaystyle\sum_{x\in X}\sigma_{X}(x)-\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})=$
$\displaystyle\sigma_{X}\left(x_{i}\right)-\sum_{x\in
X^{(i)}}\left(\sigma_{X^{(i)}}(x)-\sigma_{X}(x)\right)$ $\displaystyle\geq$
$\displaystyle\sigma_{X}\left(x_{i}\right)-\sum_{x\in
X^{(i)}}\frac{\ell\left(\theta^{(i)},x_{i}\right)\cdot\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)\cdot\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)}$ $\displaystyle=$
$\displaystyle\sigma_{X}\left(x_{i}\right)-\frac{\ell\left(\theta^{(i)},x_{i}\right)}{\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)}\geq 0\,.$

Then, we have

$\displaystyle\sum_{i=1}^{n}\left|\sum_{x\in
X}\sigma_{X}(x)-\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})\right|=\sum_{i=1}^{n}\left(\sum_{x\in
X}\sigma_{X}(x)-\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})\right)$
$\displaystyle\leq\sum_{i=1}^{n}\sigma_{X}\left(x_{i}\right)\leq\sum_{x\in
X}\sigma_{X}(x)\,.$

∎

######  Lemma B.3.

We have

$\sum_{i=1}^{n}\sum_{x\in X^{(i)}}\left|\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right|\leq 2\,.$

###### Proof.

First, we have

$\displaystyle\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}$ $\displaystyle=\ $
$\displaystyle\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x\in
X}\sigma_{X}(x)}\left(1-\frac{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in
X}\sigma_{X}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right)$ $\displaystyle=\ $
$\displaystyle\sigma_{X^{(i)}}(x)\frac{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in X}\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}-\frac{1}{\sum_{x\in
X}\sigma_{X}(x)}\left(\sigma_{X^{(i)}}(x)-\sigma_{X}(x)\right)\,.$

We can bound this quantity from below and above by Lemma B.1,

$\displaystyle\sigma_{X^{(i)}}(x)\frac{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in X}\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}-\frac{1}{\sum_{x\in
X}\sigma_{X}(x)}\frac{\ell\left(\theta^{(i)},x_{i}\right)\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)\cdot\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)}$ $\displaystyle\leq\ $
$\displaystyle\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}$ $\displaystyle\leq\ $
$\displaystyle\sigma_{X^{(i)}}(x)\frac{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in X}\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)\sum_{x^{\prime}\in X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\,.$

Then, we have

$\displaystyle\left|\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right|$ $\displaystyle\leq\ $
$\displaystyle\frac{\sigma_{X^{(i)}}(x)}{\sum_{x\in
X}\sigma_{X}(x)\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\left|\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in X}\sigma_{X}(x)\right|$
$\displaystyle\ +\frac{1}{\sum_{x\in
X}\sigma_{X}(x)}\frac{\ell\left(\theta^{(i)},x_{i}\right)\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)\cdot\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)}\,.$

It then follows,

$\displaystyle\sum_{i=1}^{n}\sum_{x\in
X^{(i)}}\left|\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right|$ $\displaystyle\leq\ $
$\displaystyle\sum_{i=1}^{n}\sum_{x\in
X^{(i)}}\left(\frac{\sigma_{X^{(i)}}(x)}{\sum_{x\in
X}\sigma_{X}(x)\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\left|\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in X}\sigma_{X}(x)\right|\right.$
$\displaystyle\ \left.+\frac{1}{\sum_{x\in
X}\sigma_{X}(x)}\frac{\ell\left(\theta^{(i)},x_{i}\right)\ell\left(\theta^{(i)},x\right)}{\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)\cdot\sum_{x^{\prime}\in
X^{(i)}}\ell\left(\theta^{(i)},x^{\prime}\right)}\right)$
$\displaystyle=\sum_{i=1}^{n}\left(\frac{\left|\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})-\sum_{x\in
X}\sigma_{X}(x)\right|}{\sum_{x\in X}\sigma_{X}(x)}+\frac{1}{\sum_{x\in
X}\sigma_{X}(x)}\frac{\ell\left(\theta^{(i)},x_{i}\right)}{\sum_{x^{\prime}\in
X}\ell\left(\theta^{(i)},x^{\prime}\right)}\right)$ $\displaystyle\leq\ $
$\displaystyle 1+\frac{1}{\sum_{x\in X}\sigma_{X}(x)}$ $\displaystyle\leq\ $
$\displaystyle 2\,,$

where the second to last inequality is from Lemma B.2, and the last inequality
is by $\sum_{x\in X}\sigma_{X}(x)\geq 1$. ∎

######  Lemma B.4.

For $\epsilon>0$, let $X$ and $X^{\prime}$ be sampled from the uniform
distribution over $[B,(1+\epsilon)B]$ and
$\left[B^{\prime},(1+\epsilon)B^{\prime}\right]$, respectively. Then, we have

$\mathrm{TV}(X,X^{\prime})\leq\frac{1+\epsilon}{\epsilon}\left|1-\frac{B^{\prime}}{B}\right|\,.$

###### Proof.

The proof is implicit in Lemma 2.3 of Kumabe and Yoshida, (2022). ∎

See 4.2

###### Proof.

The average sensitivity of importance sampling can be bounded by the sum of
the average total variation distance between selected elements and that
between assigned weights, conditioned on that the selected elements are the
same. The former is bounded by

$\displaystyle\
\frac{1}{n}\sum_{i=1}^{n}|C|\cdot\left(\frac{\sigma_{X}\left(x_{i}\right)}{\sum_{x\in
X}\sigma_{X}(x)}+\sum_{x\in X^{(i)}}\left|\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right|\right)$ $\displaystyle=\ $
$\displaystyle O\left(\frac{|C|}{n}\right)+O\left(\frac{|C|}{n}\right)$
$\displaystyle=\ $ $\displaystyle O\left(\frac{|C|}{n}\right)\,,$

where the first equality is Lemma B.3. With Lemma B.4, we have the latter as

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}|C|\cdot\left(\sum_{x\in
X^{(i)}}\min\left\\{\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)},\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right\\}\cdot\frac{1+\epsilon}{\epsilon}\left|1-\frac{\sigma_{X^{(i)}}(x)/\left(\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})\right)}{\sigma_{X}(x)/\sum_{x\in
X}\sigma_{X}(x)}\right|\right)$ $\displaystyle\leq\ $
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}|C|\cdot\left(\sum_{x\in
X^{(i)}}\frac{1+\epsilon}{\epsilon}\left|\frac{\sigma_{X}(x)}{\sum_{x\in
X}\sigma_{X}(x)}-\frac{\sigma_{X^{(i)}}(x)}{\sum_{x^{\prime}\in
X^{(i)}}\sigma_{X^{(i)}}(x^{\prime})}\right|\right)$ $\displaystyle=\ $
$\displaystyle O\left(\frac{|C|}{\epsilon n}\right)\,.$

Combining the two terms, we have the average sensitivity of importance
sampling be bounded as $O\left(\frac{|C|}{n}\right)+O\left(\frac{|C|}{\epsilon
n}\right)=O\left(\frac{|C|}{\epsilon n}\right)$. ∎

##  Appendix C Proofs for Section 5

###  C.1 Algorithm

We now introduced the detailed version of Algorithm 3. In Algorithm 7, we
provide a detailed description of the coreset construction method for
clustering, which is based on Huang and Vishnoi, (2020). To make the coreset
construction enjoys small average sensitivity, we perturbe the weights
assigned (Line 6 and Line 11). We show that this preserves the approximation
ratio while makes the overall algorithm insensitivity. With this, we obtain
the online consistent clustering algorithm 6, which clusters data from a
coreset at each step.

Input: PTAS algorithm $\mathcal{D}$ for $(k,z)$-clustering, approximation
ratio $\epsilon,\delta\in(0,1)$.

1 for  _$t=1,\ldots,n$_ do

2 Construct an $\epsilon$-coreset $C_{t-1}=(S_{t-1},\omega_{t-1})$ by running
Algorithm 7 on $X_{t-1}$.

3 Obtain cluster set $Z_{t}$ by running a PTAS $\mathcal{D}$ with
approximation ratio of $(1+\epsilon)$ on $C_{t-1}$.

4 Receive $x_{t}$ and $\ell(Z_{t},x_{t})$.

Algorithm 6 Online consistent $(k,z)$-clustering

Input: A set of point $X$, approximation parameter $\epsilon,\delta\in(0,1)$,
integer $k,z$.

1Set $\epsilon=\epsilon/c$ for some large constant $c>0$.

2 Compute a $k$-center set $C^{\ast}_{t}\subseteq\mathbb{R}^{d}$ as an
$\epsilon$-approximation of the $(k,z)$-clustering problem over $X$ with the
$D^{z}$-sampling algorithm with an approximation ratio of $O(2^{z}\log k)$.

3 For each $x\in X$, compute the closest point to $x$ in $C^{\ast}$,
$c^{\ast}(x)$, with ties broken arbitrarily. For each $c\in C^{\ast}$, denote
$X^{c}$ to be the set of points $x\in X$ with $c^{\ast}(x)=c$.

4 For each $x\in X$, let
$\sigma_{1,X}(x)=2^{2z+2}\epsilon^{2}\left(\frac{\left\|x-c^{\ast}(x)\right\|_{2}^{z}}{\sum_{x\in
X}\ell\left(C^{\ast},x\right)}+\frac{1}{\left|X_{c^{\ast}(x)}\right|}\right)$.

5 Pick a non-uniform random sample $D^{1}$ of
$N_{1}=O\left((168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{k}{\delta}\right)$
points from $X$, where each $x\in X$ is selected with probability
$\frac{\sigma_{1,X}(x)}{\sum_{y\in X}\sigma_{1,X}(y)}$.

6 For each $x\in D^{1}$, sample $\tilde{u}_{X}(x)$ from
$\left[\frac{\sum_{y\in
X}\sigma_{1,X}(y)}{\left|D^{1}_{t}\right|\cdot\sigma_{1,X}(x)},(1+\epsilon)\frac{\sum_{y\in
X}\sigma_{1,X}(y)}{\left|D^{1}_{t}\right|\cdot\sigma_{1,X}(x)}\right]$.

7 Set $u_{X}(x)=\tilde{u}_{X}(x)$

8 For each $c\in C^{\ast}$, compute $D_{c}$ to be the set of points in $D^{1}$
whose closest point in $C^{\ast}$ is $c$ with ties broken arbitrarily.

9 For each $x\in D^{1}$, let
$\sigma_{2,X}(x)=\frac{u_{X}(x)\cdot\ell\left(C^{\ast},x\right)}{\sum_{y\in
D^{1}}u_{X}(y)\cdot\ell\left(C^{\ast},y\right)}$

10 Pick a non-uniform random sample $D^{2}$ of
$N_{2}=O\left(\epsilon^{-2z-2}k\log k\log\frac{k}{\epsilon\delta}\right)$
points from $X_{t}$, where each $x\in X_{t}$ is selected with probability
$\frac{\sigma_{2,X}(x)}{\sum_{y\in D^{1}}\sigma_{2,X}(y)}$

11 For each $x\in D^{2}$, sample $\tilde{w}_{X}(x)$ from
$\left[\frac{\sum_{y\in
D^{1}}\sigma_{2,X}(y)}{\left|D^{2}\right|\cdot\sigma_{2,X}(x)},(1+\epsilon)\frac{\sum_{y\in
D^{1}}\sigma_{2,X}(y)}{\left|D^{2}\right|\cdot\sigma_{2,X}(x)}\right]$.

12Set $w_{X}(x)=\tilde{w}_{X}(x)$

13 For each $c\in C^{\ast}$, let $w_{X}(c)=(1+10\epsilon)\sum_{x\in
D_{c}}u_{X}(x)-\sum_{x\in D^{2}\cap D_{c}}w_{X}(x)$.

14 $S=D^{2}\cup C^{\ast}$

15 $w(x)=w_{X}(x)$

16 Output $(S,w)$

Algorithm 7 Coreset construction for clustering Huang and Vishnoi, (2020)

###  C.2 Analysis

######  Theorem C.1.

Algorithm 7 outputs an $\epsilon$-coreset with probability at least $1-\delta$
and has an average sensitivity of

$O\left(\frac{k+(168z)^{10z}\epsilon^{-5z-15}k^{6}\log\frac{k}{\delta}+\epsilon^{-2z-2}k\log
k\log\frac{k}{\epsilon\delta}(1+\epsilon^{-2z-2}k^{2}\log
k\log\frac{k}{\epsilon\delta})}{n}\right)\,.$

###### Proof.

We first show that our coreset construction method gives an
$\epsilon$-coreset.

We remark that the way we assigned the weights is a perturbed version of the
method presented in Huang and Vishnoi, (2020). Then, to show that the
perturbed version of the assignment of the weight still preserves the coreset
approximation ratio, we show that the perturbed version still satisfies
Corollary 15.3 of Feldman and Langberg, (2011) and Theorem 14.5. Then using
the same argument as Theorem 15.4 of Feldman and Langberg, (2011), our coreset
construction method gives an $\epsilon$-coreset.

In the first importance sampling stage, we only perturb $\tilde{u}_{X}(x)$ by
a ratio of $1+\epsilon$, for each $x\in D^{1}$. The same is applied in the
second stage with $\tilde{w}_{X}(x)$, for all $x\in D^{2}$. For $c\in
C^{\ast}$, we have

$\displaystyle(1+10\epsilon)\sum_{x\in D_{c}}u_{X}(x)-\sum_{x\in D^{2}\cap
D_{c}}w_{X}(x)\leq(1+\epsilon)\left((1+10\epsilon)\sum_{x\in
D_{c}}\tilde{u}_{X}(x)-\sum_{x\in D^{2}\cap D_{c}}\tilde{w}_{X}(x)\right)\,.$

In all cases, the result from (Feldman and Langberg,, 2011) still holds, as
the weights are scaled by $(1+\epsilon)$ at most. By the same argument that
all perturbed weights are scaled by $(1+\epsilon)$ at most, we have Theorem
15.4 of Feldman and Langberg, (2011) holds with a ratio of
$\epsilon(1+\epsilon)$. This results in an approximation of
$1+\epsilon(1+\epsilon)$ by applying the argument of Theorem 15.4 of Feldman
and Langberg, (2011). Rescale $\epsilon$ to $\epsilon/c$ for some constant
$c>0$ gives an approximation ratio of $1+\epsilon$ and completes our argument
that Algorithm 7 produces an $\epsilon$-coreset with probability at least
$1-\delta$.

To show that our method enjoys low average sensitivity, we upper bound the
average sensitivity of the two importance sampling stage of Algorithm 7
separately.

The average sensitivity of importance sampling in the first stage can be
bounded by the average total variation distance between selected elements and
that between assigned weights, conditioned on the selected elements are the
same. By Lemma 4.2, we can upper bound the average sensitivity of the first
importance sampling stage to be $O(N_{1}/n)$, where
$N_{1}=O\left((168z)^{10z}\epsilon^{-5z-15}k^{5}\log(\delta^{-1}k)\right)$.

In the second stage, as points are selected with probability
$\frac{\sigma_{2,X}(x)}{\sum_{y\in X}\sigma_{2,X}(y)}$, we bound the total
variation distance between selected points in a similar way as to that for the
first stage. This gives a bound of $O(N_{2}/n)$, where
$N_{2}=O\left(\epsilon^{-2z-2}k\log k\log\frac{k}{\epsilon\delta}\right)$. To
bound the average total variation distance between assigned weights, we again
apply the same argument as above and obtain a bound of $O(N_{2}/n)$.

Combining these and that the average sensitivity of Line 2 of Algorithm 7 is
$O(k/n)$ (by Lemma 2.2 of Yoshida and Ito, (2022)), we have the average
sensitivity as

$O\left(\frac{k+N_{1}+N_{2}}{n}\right)=O\left(\frac{k+(168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{k}{\delta}+\epsilon^{-2z-2}k\log
k\log\frac{k}{\epsilon\delta}}{n}\right)\,.\qed$

See 5.1

###### Proof.

First, we note that the approximation ratio of the algorithm with respect to
the aggregated loss is at most

$(1-\delta)\left(1+\frac{\epsilon}{3}\right)\left(1+\frac{\epsilon}{3}\right)+\delta
n\leq 1+\epsilon$

from the choice of $\delta$, i.e., $\delta=O(\epsilon/n)$.

Also, we note that the overall average sensitivity is

$\displaystyle\sum^{n}_{t=1}\beta(t)=\ $
$\displaystyle\sum^{n}_{t=1}O\left(\frac{(168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{k}{\delta}+\epsilon^{-2z-2}k\log
k\log\frac{k}{\epsilon\delta}}{t}\right)$ $\displaystyle=\ $ $\displaystyle
O\left(\left({(168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{k}{\delta}+\epsilon^{-2z-2}k\log
k\log\frac{k}{\epsilon\delta}}\right)\log n\right)\,.$

Then substituting this into Theorem 3.1, for $z\geq 1$, we have a regret bound
of

$\displaystyle\mathrm{Regret}_{\epsilon}(n)\leq\ $ $\displaystyle
O\left(\left({(168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{k}{\delta}+\epsilon^{-2z-2}k\log
k\log\frac{k}{\epsilon\delta}}\right)\log n\right)$ $\displaystyle=\ $
$\displaystyle
O\left(\left({(168z)^{10z}\epsilon^{-5z-15}k^{5}\log\frac{kn}{\epsilon}+\epsilon^{-2z-2}k\log
k\log\frac{kn}{\epsilon}}\right)\log n\right)\,.$

For the second claim about inconsistency, we first convert the average
sensitivity bound to an inconsistency bound of the same order. This can be
done by Lemma 4.2 of (Yoshida and Ito,, 2022) and by arguing in a similar way
as Lemma 4.5 of (Yoshida and Ito,, 2022) by showing that there exists a
computable probability transportation for the output of Algorithm 3. This thus
yields an inconsistency of
$O\left(\left({(168z)^{10z}\epsilon^{-5z-15}k^{5}\log(\epsilon^{-1}kn)\epsilon^{-2z-2}k\log
k\log(\epsilon^{-1}kn)}\right)\log n\right)$. ∎

##  Appendix D Proofs for Section 6

See 6.2

###### Proof.

Let $\delta>0$ be determined later. By Theorem 6 from Cohen et al., (2017),
with probability $1-\delta$, for any rank-$k$ orthogonal projection
${\mathbf{X}}$, by sampling $m=O\left(\epsilon^{-2}k\log(\delta^{-1}k)\right)$
columns, in Line $4$ of Algorithm 5, we have,

$\left(1-\frac{\epsilon}{2}\right)\|{\mathbf{A}}_{t}-{\mathbf{X}}{\mathbf{A}}_{t}\|_{F}^{2}\leq\|{\mathbf{C}}_{t}-{\mathbf{X}}{\mathbf{C}}_{t}\|_{F}^{2}\leq\left(1+\frac{\epsilon}{2}\right)\|{\mathbf{A}}_{t}-{\mathbf{X}}{\mathbf{A}}_{t}\|_{F}^{2}\,.$

With this, we note that the algorithm has an approximation of $1+\epsilon$ as
$1+\epsilon/2+\delta n\leq 1+\epsilon$ by choosing the hidden constant in
$\delta$ small enough.

Note that by applying Lemma 4.2, this routine has an average sensitivity of
$O(m/t)=O\left(\epsilon^{-2}k\log(\delta^{-1}k)/t\right)$ at any step $t$.
Then set ${\mathbf{Z}}_{t}$ to the top $k$ left singular vectors of
${\mathbf{C}}_{t}$, and we have

$\displaystyle\left\|{\mathbf{A}}_{t}-{\mathbf{Z}}_{t}{\mathbf{Z}}_{t}^{\top}{\mathbf{A}}_{t}\right\|_{F}\leq\
$
$\displaystyle(1+\epsilon)\left\|{\mathbf{A}}_{t}-{\mathbf{U}}_{k}{\mathbf{U}}_{k}^{\top}{\mathbf{A}}_{t}\right\|_{F}\,.$

To obtain the regret, we calculate the overall average sensitivity as
$\sum_{t=1}^{n}\beta(t)=\sum^{n}_{t=1}O\left(\epsilon^{-2}k\log(\delta^{-1}k)/t\right)=O\left(\epsilon^{-2}k\log
n\log(\delta^{-1}k)\right)$. Applying Theorem 3.1, and from the choice
$\delta=O(\epsilon/n)$, we have
$\mathrm{Regret}_{\epsilon}(n)=O\left(\epsilon^{-2}k\log
n\log(\epsilon^{-1}kn)\right)$.

For the second claim about inconsistency, we prove this convert the average
sensitivity bound to an inconsistency bound of the same order. This can be
done by Lemma 4.2 of (Yoshida and Ito,, 2022) and by arguing in a similar way
as Lemma 4.5 of (Yoshida and Ito,, 2022) by showing that there exists a
computable probability transportation for the output of Algorithm 3. ∎

##  Appendix E Proof for Section 7

See 7.1

###### Proof.

By Theorem 7.4, the algorithm has an approximation of $1+\epsilon$ as
$1+\epsilon/2+\delta n\leq 1+\epsilon$ by choosing the hidden constant in
$\delta$ small enough.

Similar to the low-rank case, the average sensitivity of leverage score
sampling at step $t$ is $O\left(\frac{d\log(d/\delta)}{\epsilon^{2}t}\right)$.
Summing over the average sensitivity

$\displaystyle\sum^{n}_{t=1}O\left(\frac{d\log(d/\delta)}{\epsilon^{2}t}\right)=O\left(\frac{d\log
n\log(d/\delta)}{\epsilon^{2}}\right)\,.$

Take this into Theorem 1, and with $\delta=O(\epsilon/n)$, we have a
$\epsilon$-regret of $O\left(\epsilon^{-2}d\log n\log(dn/\epsilon)\right)$.

Similar to that of Theorem 5.1 and Theorem 6.2, we prove the second claim by
converting the average sensitivity bound to an inconsistency bound of the same
order. This can be done by Lemma 4.2 of (Yoshida and Ito,, 2022) and by
arguing in a similar way as Lemma 4.5 of (Yoshida and Ito,, 2022) by showing
that there exists a computable probability transportation for the output of
Algorithm 3. ∎