the union of all even-indexed element collections, which equals $\mathcal{U}$.
Namely, $\mathcal{U}=\bigcup_{j\geq 0}\mathcal{U}_{2j}=\bigcup_{j\geq
0}\mathcal{U}_{2j-1}$.

For each $l\geq-1$, we will maintain a set cover
$\mathcal{S}_{l,\mathsf{alg}}\subseteq\mathcal{S}_{l}$ that covers
$\mathcal{U}_{l}$ by applying Theorem 3.1 as a black-box on the set cover
instance $(\mathcal{U}_{l},\mathcal{S}_{l})$. So, for each $l\geq-1$, the
algorithm will maintain a super set
$\mathcal{U}_{l}^{+}\supseteq\mathcal{U}_{l}$ which contains both alive and
dead elements. Overall, by 4.2, we will have two different set cover solutions
for $\mathcal{U}$:

$\mathcal{S}_{\mathrm{even},\mathsf{alg}}:=\bigcup_{j\geq
0}\mathcal{S}_{2j,\mathsf{alg}}\;,\;\mathcal{S}_{\mathrm{odd},\mathsf{alg}}:=\bigcup_{j\geq
0}\mathcal{S}_{2j-1,\mathsf{alg}}.$

The solution of smaller total cost among
$\mathcal{S}_{\mathrm{even},\mathsf{alg}}$ and
$\mathcal{S}_{\mathrm{odd},\mathsf{alg}}$ will be the output solution that is
presented to the adversary.

To illustrate how Theorem 3.1 is applied on the set cover instance
$(\mathcal{U}_{l},\mathcal{S}_{l})$, let us slightly open the black box and
define the following notations. For any index $l\geq-1$, for each set
$s\in\mathcal{S}_{l}$, we will assign a level:

$\mathsf{lev}_{l}(s)\in
I_{l}=\left[\max\\{lK-\lceil\log_{\beta}n\rceil-1,-1\\},(l+2)K+\lceil
10\log_{\beta}1/\epsilon\rceil\right].$

Intuitively, $\mathsf{lev}_{l}(s)$ is the dynamic level that the black-box
algorithm assigns to set $s$ in the $l$-th window $\mathcal{S}_{l}$, and
$I_{l}$ is the batch or interval of levels in which we operate now, instead of
$-1$ to $L$. Notice that $s\in\mathcal{S}_{l}$ cannot cover at a level higher
than $\mathsf{toplev}(s)$, which is less than the upper limit of $I_{l}$. On
the other hand, $s\in\mathcal{S}_{l}$ cannot cover at a level lower than
$\lfloor\log_{\beta}(\frac{1}{\mathsf{cost}(s)})\rfloor$ (its level if it
covers just one element), which is larger than the lower limit of $I_{l}$.
Therefore, $I_{l}$ contains all levels that $s\in\mathcal{S}_{l}$ can cover at
(and has some slack on both ends). The lowest level in each interval $I_{l}$
is reserved for sets in
$\mathcal{S}_{l}\setminus\mathcal{S}_{l,\mathsf{alg}}$, just as we reserved
the level $-1$ for sets not in the cover in the previous section. See Figure 3
for an illustration.

For any element $e\in\mathcal{U}_{l}^{+}$, we will assign it to set
$\mathsf{asn}_{l}(e)\in\mathcal{S}_{l,\mathsf{alg}}$, and conversely, for each
$s\in\mathcal{S}_{l}$, define
$\mathsf{cov}_{l}(s)=\\{e\mid\mathsf{asn}_{l}(e)=s\\}$. The level of an
element $e$ is defined to be
$\mathsf{lev}_{l}(e)=\mathsf{lev}_{l}(\mathsf{asn}_{l}(e))$. Besides, we will
also maintain a value of _passive level_
$\mathsf{plev}_{l}(e)\geq\mathsf{lev}_{l}(e)$. For any $k\in I_{l}$, define
$A_{l,k}=\\{e\in\mathcal{U}_{l}^{+}\mid\mathsf{lev}_{l}(e)\leq
k<\mathsf{plev}_{l}(e)\\}$, and
$P_{l,k}=\\{e\in\mathcal{U}_{l}^{+}\mid\mathsf{plev}_{l}(e)\leq k\\}$. For
each set $s\in\mathcal{S}_{l}$, define $N_{l,k}(s)=A_{l,k}\cap s$. For dead
element $e$ in $\mathcal{U}_{l}^{+}\setminus\mathcal{U}_{l}$, we will have
$\mathsf{plev}_{l}(e)=\mathsf{lev}_{l}(e)$.

Figure 3:  _Element $e$ is in $\mathcal{U}_{l}$ and $\mathcal{U}_{l+1}$. Thus
it must be covered by a set in $\mathcal{S}_{l}$, at level
$\mathsf{lev}_{l}(e)\in I_{l}$, and it must be covered by a set in
$\mathcal{S}_{l+1}$, at level $\mathsf{lev}_{l+1}(e)\in I_{l+1}$. Notice the
overlap between the different intervals._

Our algorithm will maintain the following data structures for each index
$l\geq-1$.

Basic Data Structures for each $l\geq-1$.

  1. (a)

For each level $k\in I_{l}$, we will maintain linked lists
$S_{l,k}=\\{s\mid\mathsf{lev}_{l}(s)=k\\}$ and
$E_{l,k}=\\{e\mid\mathsf{lev}_{l}(e)=k\\}$.

  2. (b)

For each element $e\in\mathcal{U}_{l}$, maintain the assignment
$\mathsf{asn}_{l}(e)$, and then for each set $s\in\mathcal{S}_{l}$ maintain
the set $\mathsf{cov}_{l}(s)$.

######  Invariant 4.1.

The algorithm will maintain the following invariant for each $l\geq-1$:

  1. (1)

For any set $s\in\mathcal{S}_{l}$ and any $k>\min\\{I_{l}\\}$, we have
$\frac{|N_{l,k}(s)|}{\mathsf{cost}(s)}<\beta^{k+1}$.

  2. (2)

For any set $s\in\mathcal{S}_{l,\mathsf{alg}}$, we have
$\frac{|\mathsf{cov}_{l}(s)|}{\mathsf{cost}(s)}\geq\beta^{\mathsf{lev}_{l}(s)}$;
note that $\mathsf{cov}_{l}(s)$ could count dead elements in $\mathcal{U}_{l}$
that are already deleted by the adversary. In particular,
$\mathsf{lev}_{l}(s)\leq\mathsf{toplev}(s)$ for any $s\in\mathcal{S}_{l}$.
Moreover, for each $s\notin\mathcal{S}_{l,\mathsf{alg}}$,
$\mathsf{lev}_{l}(s)=\min\\{I_{l}\\}$.

  3. (3)

For each $k\in I_{l}$ and $k>\min\\{I_{l}\\}$, we have $|P_{l,k}|\leq
2\epsilon|A_{l,k}|$. Note that the algorithm does not maintain the counters
$|A_{l,k}|,|P_{l,k}|$ explicitly.

To analyze the approximation ratio, let $\mathcal{S}^{*}$ denote the optimal
set cover for all elements in $\mathcal{U}$.

######  Lemma 4.1.

For any $l\geq-1$, let $k_{0}\in I_{l}$ be the smallest index such that there
exists a set in $\mathcal{S}_{l}$ covering at level $k_{0}$, or in other
words, $k_{0}$ is the smallest level such that
$\mathcal{S}_{l,\mathsf{alg}}\cap S_{l,k_{0}}\neq\emptyset$. If
$k_{0}\leq(l+1)K$, then we have:

$\sum_{j\geq
0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})\leq(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*}).$

###### Proof.

We apply Lemma 3.1 and Corollary 3.1 for the set system of
$(\mathcal{U}_{l},\mathcal{S}_{l})$, where instead of summations from $k=0$ to
$L-1$ we have summations from $\min\\{I_{l}\\}+1$ to $\max\\{I_{l}\\}-1$,
instead of $L$ we have $\max\\{I_{l}\\}$, and instead of $\mathsf{lev}(e)$ and
$\mathsf{plev}(e)$ we have $\mathsf{lev}_{l}(e)$ and $\mathsf{plev}_{l}(e)$,
respectively. As a result we directly get that
$\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}})\leq(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*}_{l})\leq(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*})$, where $\mathcal{S}^{*}_{l}$ denotes the
optimal set cover for all elements in $\mathcal{U}_{l}$. Consider any set
$s_{0}\in\mathcal{S}_{l,\mathsf{alg}}\cap S_{l,k_{0}}$. For any set
$s\in\mathcal{S}_{l+2j,\mathsf{alg}}$ and $j>0$, we have:

$\mathsf{cost}(s)\leq n\cdot\beta^{1-\mathsf{toplev}(s)}\leq
n\cdot\beta^{1-(l+2)K}\leq
n\cdot\beta^{1-k_{0}-K}\leq\frac{\epsilon}{(1+2\epsilon)n}\cdot\beta^{-k_{0}-1}\leq\frac{\epsilon\cdot\mathsf{cost}(s_{0})}{(1+2\epsilon)n},$
(13)

where the first inequality holds since
$\mathsf{toplev}(s)\leq\log_{\beta}(n/\mathsf{cost}(s))+1$ (by definition of
$\mathsf{toplev}(s)$), the second holds since
$\mathsf{toplev}(s)\geq(l+2j)K\geq(l+2)K$ for any $j>0$ by definition of $s$,
the third follows from the initial assumption that $k_{0}\leq(l+1)K$, the
fourth by definition of $K$ and that $\epsilon>\frac{2}{n^{8}}$ is not too
small, and the fifth holds since $s_{0}$ is covering at level $k_{0}$. Since
at most $n$ elements are alive and at most $2\epsilon\cdot n$ elements may be
dead (otherwise 4.1(3) is violated), and as each element (dead or alive) is
assigned to at most one set in the set cover solution, it follows that the
total number of sets in $\mathcal{S}_{l+2j,\mathsf{alg}}$ over all $j>0$ is
bounded by $(1+2\epsilon)n$. By Equation 13, we get

$\sum_{j>0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})~{}\leq~{}(1+2\epsilon)n\cdot\left(\frac{\epsilon}{(1+2\epsilon)n}\cdot\mathsf{cost}(s_{0})\right)~{}\leq~{}\epsilon\cdot\mathsf{cost}(s_{0})~{}\leq~{}\epsilon\cdot\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}}).$

We conclude that

$\sum_{j\geq
0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})~{}=~{}\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}})+\sum_{j>0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})~{}\leq~{}(1+\epsilon)\cdot\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}})~{}\leq~{}(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*}),$

and the lemma follows. ∎

######  Lemma 4.2.

$\min\\{\mathsf{cost}(\mathcal{S}_{\mathrm{even},\mathsf{alg}}),\mathsf{cost}(\mathcal{S}_{\mathrm{odd},\mathsf{alg}})\\}\leq(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*})$

###### Proof.

Let $l^{\prime}$ be the smallest value such that
$\mathcal{U}_{l^{\prime}}\neq\emptyset$. Pick an arbitrary element $e$ in both
$\mathcal{U}_{l^{\prime}}$ and $\mathcal{U}_{l^{\prime}+1}$ with the lowest
$\mathsf{lev}_{l^{\prime}+1}(e)$ value; such an element exists by definition
of $l^{\prime}$ and by Observation 4.1. Write
$k_{1}=\mathsf{lev}_{l^{\prime}+1}(e)$, and denote the set that covers $e$ at
level $k_{1}$ by $s_{1}\in\mathcal{S}_{l^{\prime}+1,\mathsf{alg}}$. By
Observation 4.1, $s_{1}$ is also in either $\mathcal{S}_{l^{\prime}}$ or
$\mathcal{S}_{l^{\prime}+2}$. If $s_{1}$ were in $\mathcal{S}_{l^{\prime}+2}$,
then since $s_{1}$ contains $e$, by definition $e$ would be in
$\mathcal{U}_{l^{\prime}+2}$, but it is not. Thus
$s_{1}\in\mathcal{S}_{l^{\prime}},\mathcal{S}_{l^{\prime}+1}$. Since
$s_{1}\in\mathcal{S}_{l^{\prime}}$, by definition of
$\mathcal{S}_{l^{\prime}}$ we know that
$\mathsf{toplev}(s_{1})<(l^{\prime}+2)K$. Moreover,
$k_{1}\leq\mathsf{toplev}(s_{1})$ since $s_{1}$ cannot cover at a level higher
than its top level. Thus, we get that $k_{1}<(l^{\prime}+2)K$.

Now, denote by $k_{0}\in I_{l^{\prime}+1}$ the smallest index such that there
exists a set in $\mathcal{S}_{l^{\prime}+1}$ covering at level $k_{0}$. We
have $k_{0}\leq k_{1}$ by definition, thus $k_{0}<(l^{\prime}+2)K$. Plugging
this in Lemma 4.1 (with our $l^{\prime}+1$ as $l$ in the lemma), we obtain:

$\sum_{j\geq
0}\mathsf{cost}(\mathcal{S}_{l^{\prime}+1+2j,\mathsf{alg}})\leq(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*}).$

Since for $j<0$ there are no elements in $\mathcal{U}_{l^{\prime}+1+2j}$,
Observation 4.2 implies that the set $\bigcup_{j\geq
0}\mathcal{S}_{l^{\prime}+1+2j,\mathsf{alg}}$ is a valid set cover for all
elements in $\mathcal{U}$. Note also that $\bigcup_{j\geq
0}\mathcal{S}_{l^{\prime}+1+2j,\mathsf{alg}}$ is equal to either
$\mathcal{S}_{\mathrm{even},\mathsf{alg}}$ or
$\mathcal{S}_{\mathrm{odd},\mathsf{alg}}$, depending on whether $l^{\prime}$
is odd or even, respectively. Therefore,

$\min\\{\mathsf{cost}(\mathcal{S}_{\mathrm{even},\mathsf{alg}}),\mathsf{cost}(\mathcal{S}_{\mathrm{odd},\mathsf{alg}})\\}~{}\leq~{}\sum_{j\geq
0}\mathsf{cost}(\mathcal{S}_{l^{\prime}+1+2j,\mathsf{alg}})~{}\leq~{}(1+O(\epsilon))\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*}),$

which completes the proof. ∎

###  4.2 Algorithm Description

For each index $l\geq-1$, we will maintain the subset of sets
$\mathcal{S}_{l}\in\mathcal{S}$ and the subset of elements
$\mathcal{U}_{l}\subseteq\mathcal{U}$, to coincide with Definition 4.1; we
will also apply the algorithm provided by Theorem 3.1, as a black-box, on the
set system $(\mathcal{U}_{l},\mathcal{S}_{l})$. However, we cannot afford to
run the black-box algorithm on all set systems following every update.
Instead, since each element may belong to at most two set systems, element
updates are handled in the following manner:

  * •

Insertion. When an element $e$ is inserted, enumerate all sets containing $e$
to find the cheapest one, denoted $s$. Letting $l$ denote the index such that
$s\in\mathcal{S}_{l},\mathcal{S}_{l+1}$, we add $e$ to both $\mathcal{U}_{l}$
and $\mathcal{U}_{l+1}$, and run the element insertion algorithm on the two
set systems $(\mathcal{U}_{l},\mathcal{S}_{l})$ and
$(\mathcal{U}_{l+1},\mathcal{S}_{l+1})$.

  * •

Deletion. When an element $e\in\mathcal{U}_{l},\mathcal{U}_{l+1}$ is deleted,
remove $e$ from $\mathcal{U}_{l}$ and $\mathcal{U}_{l+1}$, and run the element
deletion algorithm on the two set systems $(\mathcal{U}_{l},\mathcal{S}_{l})$
and $(\mathcal{U}_{l+1},\mathcal{S}_{l+1})$.

Upon each update step, if the inserted/deleted element belongs to
$\mathcal{U}_{l}$ and $\mathcal{U}_{l+1}$, then we only run the reset
operations for these two systems. By Theorem 3.1, the worst-case update time
of our algorithm is $O\left(\frac{f\log n}{\epsilon^{2}}\right)$. Also,
Theorem 3.1 implies that all conditions of 4.1 are preserved for every set
system; recalling that the solution of smaller total cost among
$\mathcal{S}_{\mathrm{even},\mathsf{alg}}$ and
$\mathcal{S}_{\mathrm{odd},\mathsf{alg}}$ is the output solution, Lemma 4.2
implies that the approximation factor is in check. This concludes the proof of
Theorem 1.1.

##  5 Extension to the Low-Frequency Regime

In this section we present a dynamic set cover algorithm with an improved
worst-case update time, in the low-frequency regime of $f=O(\log n)$. We will
mostly follow the known algorithm with worst-case update time
$O\left(\frac{f\log^{2}(Cn)}{\epsilon^{3}}\right)$ [BHNW21, BHN19], and focus
on the adjustments that we make, omitting most of the details that remain the
same.

Before unfolding the technical details, let us explain on a high level why we
are able to shave the extra $\log_{\beta}n$ factor in the time bound, where
recall that $\beta=1+\epsilon$. Similar to the high-frequency regime, the
algorithm of [BHNW21] also assigns elements and sets to levels at most
$O(\log_{\beta}(Cn))$. Moreover, as before, for each level $k$, there is a
$\mathsf{reset}(k)$ instance running on a chunk of local memory in the
background, which is disjoint from and independent of the hierarchical data
structure on the foreground. During the execution of $\mathsf{reset}(k)$, it
performs a water-filling primal-dual algorithm while also handling element
updates from the adversary, in a similar way that we have done with the greedy
set cover algorithm.

When the execution of $\mathsf{reset}(k)$ terminates, it switches its local
memory to the foreground and aborts all other instances
$\mathsf{reset}(i),\forall i<k$. To ensure that all the aborted instances
$\mathsf{reset}(i)$ will have a local copy of the current data structure up to
level $i$, besides executing the water-filling procedures, the approach of
[BHNW21] is that the instance $\mathsf{reset}(k)$ will also be responsible for
initializing an independent copy of the data structures up to level $i$ for
instance $\mathsf{reset}(i)$, for all $i<k$, right after $\mathsf{reset}(i)$
is aborted by $\mathsf{reset}(k)$. This is the main time bottleneck of the
algorithm of [BHNW21]: as the $\mathsf{reset}(k)$ instance prepares the
initial memory contents for all other instances below it, this incurs a
running time of at least
$\sum_{i=0}^{k}O(i)=O(k^{2})=O(\log^{2}_{\beta}(Cn))$.

To save one extra $\log_{\beta}(Cn)$ factor in the runtime, we do the same as
our algorithm in the high-frequency regime. In our algorithm,
$\mathsf{reset}(k)$ will not be responsible for initializing the memory
contents of $\mathsf{reset}(i)$, for any $i<k$. Instead, each instance
$\mathsf{reset}(i)$ will initialize its own memory in the background by
copying data structures in the foreground up to level $i$, and only when the
initialization phase is done, should it begin with the water-filling
procedure. By doing so, we can obtain an improved time bound of
$O\left(\frac{f\log(Cn)}{\epsilon^{2}}\right)$. In the end, to remove runtime
dependency on the aspect ratio $C$, we will apply the same black-box reduction
as we did in the high-frequency regime, refer to Section 5.4 for details.

As mentioned above, our first goal will be to prove the following Lemma:

######  Lemma 5.1.

For any set system $(\mathcal{U},\mathcal{S})$ with set cost range $[1/C,1]$
that undergoes a sequence of element insertions and deletions, where the
frequency is always bounded by $f$, and for any $\epsilon\in(0,1)$, there is a
dynamic algorithm that maintains a $((1+\epsilon)f)$-approximate minimum set
cover in $O\left(\frac{f\log(Cn)}{\epsilon^{2}}\right)$ deterministic worst-
case update time.

To do so, we will follow the general lines of Section 3, highlighting two
major points throughout. The first, is the differences between our low-
frequency algorithm presented next and the high-frequency algorithm presented
in Section 3, regarding certain definitions, invariants, properties, etc. The
second is the differences between our low-frequency algorithm presented next
and the algorithm presented in [BHN19] and [BHNW21]. We mention that there are
some differences between [BHN19] and [BHNW21] regarding specific
invariants/definitions/etc., and we mainly chose to compare to [BHNW21], since
the aim of that paper and this section is essentially the same, to deamortize
the low-frequency amortized algorithm presented in [BHN19]. For the sake of
brevity we will omit several details that remain the same from
[BHN19]/[BHNW21] or Section 3, and refer to the relevant
lemmas/properties/invariants/etc. when needed.

###  5.1 Preliminaries and Invariants

Each set $s\in\mathcal{S}$ is assigned a level value
$\mathsf{lev}(s)\in[0,\lceil\log_{\beta}(Cn)\rceil+1]$; here the difference
from the greedy set cover is that we start from level $0$ rather than $-1$.
For each element $e$, its level is given by
$\mathsf{lev}(e)=\max\\{\mathsf{lev}(s):s\in\mathcal{S},e\in s\\}$. Following
[BHN19, BHNW21], each element will be classified as _alive_ , or _dead_ , and
further classify alive elements as _active_ or _passive_. An element is dead
when it has been deleted from $\mathcal{U}$ by the adversary, but is still
lingering in the system due to the algorithm. As before,
$\mathcal{U}^{+}\supseteq\mathcal{U}$ denotes the set of all elements
including dead ones, and $\mathcal{U}$ denotes the set of existing elements
from the perspective of the adversary. For each level $k$, define
$E_{k}=\\{e\in\mathcal{U}^{+}\mid\mathsf{lev}(e)=k\\},A_{k}=\\{e\in\mathcal{U}\text{
is active}\mid\mathsf{lev}(e)\leq k\\},P_{k}=\\{e\in\mathcal{U}^{+}\text{ is
not active}\mid\mathsf{lev}(e)\leq k\\}$. Note that $P_{k}$ contains both
passive and dead elements, as in Section 3 and as opposed to [BHNW21], but
$A_{k}$ does not, as opposed to Section 3. Moreover, the partition now of
$\mathcal{U}$ to passive and active is binary, in contrast to what we had
before where passiveness is parameterized by levels, which will simplify
things.

As before, during the algorithm, each set $E_{k}$ is maintained as a linked
list, and all pointers to non-empty sets $E_{k}$ are stored in a doubly-linked
list. Moreover, sets $A_{k},P_{k}$ will not be maintained explicitly in our
algorithm, and they are only used for the analysis of approximation ratio,
just like in Section 3, and in contrast to [BHNW21].

Similarly to [BHNW21], each active element $e$ is assigned a weight
$\omega(e)=\beta^{-\mathsf{lev}(e)}$, and each passive element is assigned a
weight $\omega(e)\leq\beta^{-\mathsf{lev}(e)}$. From the moment an element
becomes dead, its weight in the system will not change until the algorithm
removes it from the system. The weight of a set $s$ is given by
$\omega(s)=\sum_{e\in s\cap\mathcal{U}^{+}}\omega(e)$. Moreover:

######  Definition 5.1.

A set $s\in\mathcal{S}$ is called _tight_ if
$\omega(s)>\frac{\mathsf{cost}(s)}{\beta}$; otherwise it is called _slack_.

The algorithm will maintain the following invariant; refer to 3.1 for
comparison.

######  Invariant 5.1.

  1. (1)

For each $s\in\mathcal{S}$, $\omega(s)\leq\mathsf{cost}(s)$.

  2. (2)

All sets $s$ for which $\mathsf{lev}(s)\geq 1$ are tight.

  3. (3)

$|P_{k}|\leq 2\epsilon\cdot|A_{k}|$ for each $k\geq 0$.

The above invariants underlie a fully global approach: for the first
invariant, element insertions will be handled lazily and we will exploit the
fact that passive elements have lower weights with respect to their levels;
for the second invariant, element deletions will also be handled lazily and
set tightness are preserved by dead weights.

The algorithm will make sure that every element is contained in at least one
tight set, and the output set cover $\mathcal{S}_{\mathsf{alg}}$ of our
algorithm will be the set of all tight sets in $\mathcal{S}$. Assuming 5.1
holds, the approximation ratio is guaranteed by the following statement.

######  Lemma 5.2 (Theorem $4.7$ in [BHN19]).

All tight sets form a $(1+O(\epsilon))f$-approximate minimum set cover of
$(\mathcal{U},\mathcal{S})$.

###  5.2 Algorithm Description and Update Time Analysis

We follow our deamortization approach from the previous sections; at a high-
level, the resulting deamortized algorithm is of similar flavor to the one in
the high-frequency regime, but there are of course significant differences,
starting with the fact that the basic subroutine here for the reset procedure
is the water-filling primal-dual algorithm rather than the greedy algorithm.
For each level $k$, there is an instance of $\mathsf{reset}(k)$ that operates
on an independent chunk of memory, disjoint from the foreground memory where
the data structure is stored, and computes a partial solution up to level $k$
using a water-filling algorithm. As in the deamortization for the high-
frequency regime, we distinguish between operations on the foreground and the
background.

####  5.2.1 Foreground

Element deletions and insertions will be handled in the foreground as follows,
similarly to [BHN19] and [BHNW21].

  * •

Deletions in the Foreground. When an element $e\in\mathcal{U}$ gets deleted by
the adversary, mark $e$ as dead, and for each $k\geq\mathsf{lev}(e)$, feed the
deletion to $\mathsf{reset}(k)$ which is running in the background.

  * •

Insertions in the Foreground. When a new element $e$ is inserted by the
adversary, go over all sets $s\ni e$ to compute
$\mathsf{lev}(e)=\max_{s\in\mathcal{S}}\\{\mathsf{lev}(s)\\}$. If exists a set
$s\ni e$ that is tight then assign $\omega(e)\leftarrow 0$. Otherwise, assign
$\omega(e)\leftarrow\min_{s\ni e}\\{\mathsf{cost}(s)-\omega(s)\\}$, which
ensures us that each element has at least one tight set containing it. In both
cases $e$ becomes passive. Finally, for each $s\ni e$, update the set weight
$\omega(s)\leftarrow\omega(s)+\omega(e)$. After that, feed this new insertion
to all instances of $\mathsf{reset}(k)$ for $k\geq\mathsf{lev}(e)$.

  * •

Termination of $\mathsf{reset}(\cdot)$ Instances. Upon any element update
(deletion or insertion), go over all levels $0\leq
k\leq\lceil\log_{\beta}(Cn)\rceil+1$ and check if any instance
$\mathsf{reset}(k)$ has just terminated right after the update. If so, take
the largest such level $k$, and switch its memory to the foreground; we will
describe how a memory switch is done later on. Then, abort all instances of
$\mathsf{reset}(i),\forall 0\leq i<k$.

  * •

Initiating $\mathsf{reset}(\cdot)$ Instances. Similarly to Section 3, upon any
element update (deletion or insertion), go over all levels $0\leq k\leq L$ and
check if there is currently an instance $\mathsf{reset}(k)$. Denote by
$k_{1},k_{2},k_{3},\ldots$ the levels that do not have such an instance, where
$k_{1}<k_{2}<k_{3}<\ldots$. Next, we want to partition all levels $k_{i}$ into
_short levels_ and _non-short levels_. All of the short levels will be lower
than the non-short levels, meaning exists $i$ such that $k_{i^{\prime}}$ is a
short level for any $i^{\prime}<i$ and a non-short level for any
$i^{\prime}\geq i$. In a nutshell, we will be able to execute a short level
reset in a single update step, since the number of elements participating in
the reset is small enough. Recall that upon termination of a reset we abort
all instances of lower level resets, thus there is no reason to run all short
level resets, only the highest one. Regarding the non-short levels, we
initiate a reset to each and every one of them. To find the highest short
level given $k_{1},k_{2},k_{3},\ldots$ we do as follows. First, count all the
first $\frac{L}{f}$ elements, from level $0$ upwards. Say that the
$\frac{L}{f}$-th element is at level $j$. Thus, we know that
$|\bigcup_{i=0}^{j^{\prime}}E_{i}|<\frac{L}{f}$ for any $0\leq j^{\prime}<j$.
Define $i$ to be the highest such that $k_{i}<j$. If no such $i$ exists then
there are no short levels, otherwise $k_{i}$ is the highest short level, and
we initiate the resets for levels $k_{i},k_{i+1},\ldots$, where again $k_{i}$
is a short level and the rest are non-short levels.

####  5.2.2 Foreground and Background Data Structures

Similar to our previous algorithm, for each level
$k\in[0,\lceil\log_{\beta}(Cn)\rceil+1]$, any instance of $\mathsf{reset}(k)$
that operates (in the background) maintains a partial copy of the foreground
data structures in the background. Specifically, it maintains the following
data structures.

  1. (1)

Maintain subsets of elements
$\mathcal{U}^{(k)},\mathcal{U}^{(k)+}\subseteq\mathcal{U}^{+}$, and for each
element $e\in\mathcal{U}^{(k)+}$, maintain its level $\mathsf{lev}^{(k)}(e)$
as well as its weight $\omega^{(k)}(e)$. In addition, maintain a subset of
sets $\mathcal{S}^{(k)}\subseteq\mathcal{S}$, and for each set
$s\in\mathcal{S}^{(k)}$, maintain its level $\mathsf{lev}^{(k)}(s)$ as well
its weight $\omega^{(k)}(s)$.

  2. (2)

For each level $i\in[0,k+1]$, let
$S^{(k)}_{i}=\\{s\mid\mathsf{lev}^{(k)}(s)=i\\}$,
$E^{(k)}_{i}=\\{e\mid\mathsf{lev}^{(k)}(e)=i\\}$.

Similarly to the previous algorithm, we maintain the following data structures
that link between the foreground and background, which help improve the update
time of [BHNW21].

Data Structures that Link between the Foreground and Background.

  1. (a)

For each $k$, we have pointers to the sets $S^{(k)}_{i}$ and $E^{(k)}_{i}$,
stored in two arrays of size $L+2$ and $L+1$, respectively (an entry for every
$i\in[-1,L]$ and $i\in[0,L]$, respectively). In addition, the head of the list
$S^{(k)}_{i}$ and $E^{(k)}_{i}$ keeps a Boolean value which indicates whether
it is in the foreground or not.

  2. (b)

We store an array in the foreground $\mathsf{lev}[\cdot]$ indexed by
$s\in\mathcal{S}$ and $e\in\mathcal{U}$. So the size of this array should be
$O(|\mathcal{S}|+|\mathcal{U}|)$. Here we have assumed that sets and elements
have unique identifiers from a small integer universe (if the sets and
elements belong to a large integer universe and assuming we would like to
optimize the space usage, we can use hash tables instead of arrays). For each
$s\in\mathcal{S}$ and $0\leq k\leq L$, $\mathsf{lev}[s][k]$ stores a pointer
to the memory location containing the value of $\mathsf{lev}^{(k)}(s)$, as
well as a pointer to the list head of $S^{(k)}_{i}$ if
$\mathsf{lev}^{(k)}(s)=i$ (and $i\neq-1$). Similarly, $\mathsf{lev}[e][k]$
stores a pointer to the memory location of $\mathsf{lev}^{(k)}(e)$, as well as
a pointer to the memory location of the pointer to $E^{(k)}_{i}$ if
$\mathsf{lev}^{(k)}(e)=i$.

  3. (c)

Similarly, we store an array in the foreground $\omega[\cdot]$ indexed by
$s\in\mathcal{S}$ and $e\in\mathcal{U}$, of size
$O(|\mathcal{S}|+|\mathcal{U}|)$. For each $s\in\mathcal{S}$ and $0\leq k\leq
L$, $\omega[s][k]$ stores a pointer to the memory location containing the
value of $\omega^{(k)}(s)$. Similarly, $\omega[e][k]$ stores a pointer to the
memory location of $\omega^{(k)}(e)$.

##### Foreground Operations.

The collections $S_{i}$ and $E_{i}$ for each $i$ will be maintained in doubly
linked lists in the foreground. To access the level and weight values in the
foreground, $\mathsf{lev}(s)$ and $\omega(s)$ respectively, we can enumerate
all indices $k\in[0,L]$ and check the entry $\mathsf{lev}[s][k]$ that points
to $\mathsf{lev}^{(k)}(s)=i$ and list head $S^{(l)}_{i},l\geq i$. If either
$\mathsf{lev}[s][k]$ is a null pointer, or $\mathsf{lev}[s][k]$ points to a
value $\mathsf{lev}^{(k)}(s)=i$ but $S_{i}^{(l)}$ is not in the foreground,
then we know $\mathsf{lev}^{(k)}(s)\neq\mathsf{lev}(s)$. Once we reach
$k^{\prime}$ such that $\mathsf{lev}^{(k^{\prime})}(s)=i^{\prime}$ and
$S_{i^{\prime}}^{(l)}$ is in the foreground (determined by the Boolean value),
we know that $\mathsf{lev}(s)=\mathsf{lev}^{(k)}(s)=i^{\prime}$ and
$\omega(s)=\omega^{(k)}(s)$. Therefore, accessing the foreground level value
$\mathsf{lev}(s)$ and weight value $\omega(s)$ takes time $O(L)$. Similarly,
accessing the foreground level value $\mathsf{lev}(e)$ and weight value
$\omega(e)$ takes time $O(L)$ as well. We conclude that upon insertion of
element $e$, enumerating all sets $s\ni e$ to decide which level $e$ should be
at, determining the weight of element $e$, and updating the set weights of all
sets that contain $e$, takes time $O(f\cdot L)=O(f\cdot\log_{\beta}(Cn))$.
Regarding initiating resets, in $O(L)=O(\log_{\beta}(Cn))$ time we can go over
all levels to check which ones need to be initiated, and also check which is
the highest short level, by using $E_{i}$ which is maintained in the
foreground. We remind that a short level is a level $k$ such that
$\mathsf{reset}(k)$ is not working currently in the background, and
$f\cdot\sum_{i=0}^{k}|E_{i}|<L$. Moreover, there is only one short level reset
operating per update step (the highest one).

####  5.2.3 Background

##### Initialization Phase.

When an instance of $\mathsf{reset}(k)$ has been initiated, it initializes its
own data structures by setting
$\mathcal{S}^{(k)}_{\mathsf{alg}}=S_{i}^{(k)}=E_{i}^{(k)}\leftarrow\emptyset,\forall
i\in[0,k+1]$, and
$\mathcal{U}^{(k)}=\mathcal{U}^{(k)+}\leftarrow\bigcup_{i=0}^{k}E_{i}$. After
that, enumerate all elements of $\mathcal{U}^{(k)}$ and let
$\mathcal{S}^{(k)}$ be all the sets containing at least one element in
$\mathcal{U}^{(k)}$. So $\mathcal{S}^{(k)}\subseteq\\{s\mid
0\leq\mathsf{lev}(s)\leq k\\}$. Note that we cannot create $\mathcal{S}^{(k)}$
directly from the sets $S_{k},S_{k-1},\ldots,S_{0}$, as there might be some
tight sets on level $0$ containing some elements in $\mathcal{U}^{(k)}$ and
there might be some slack sets on level 0, but finding the tight sets at level
0 out of all sets there might take too much time.

To obtain all the pointers to $E_{i},0\leq i\leq k$, we follow the linked list
consisting of these pointers, from $E_{k}$ down to $E_{0}$. One remark is
that, during the enumeration of the list from $E_{k}$ down to $E_{0}$, some
pointers might already be switched by other instances of
$\mathsf{reset}(i),i<k$; the correctness of this step can be argued
equivalently to the proof of 3.1.1.

During the initialization phase, we remove all dead elements from
$\mathcal{U}^{(k)+}$. All the above steps will be planned in the background
for the non-short levels. Copying the memory locations of the pointers of
$\\{E_{k},E_{k-1},\cdots,E_{0}\\}$ and $\\{S_{k},S_{k-1},\cdots,S_{-1}\\}$
takes time at most $O(k)$. Obtaining the collection $\mathcal{S}^{(k)}$ takes
$O(f|\mathcal{U}^{(k)}|)$ time, so the total running time of this phase is
$O(f|\mathcal{U}^{(k)}|+k)=O(f|\mathcal{U}^{(k)}|+L)$. Since all the non-short
levels satisfy $f\cdot|\mathcal{U}^{(k)}|\geq L$, we get that the running time
of this phase for non-short levels is $O(f|\mathcal{U}^{(k)}|)$, and for the
short level reset it is $O(L)=O(\log_{\beta}(Cn))$.

##### Water-Filling Phase.

Once an instance of $\mathsf{reset}(k)$ has been initiated, we run the
algorithm _EfficientRebuild( $k$)_ given in [BHNW21]. If an element $e$ is
inserted or deleted by the adversary during the initialization phase or the
water-filling phase, it is treated just as it is in [BHNW21]. The following
properties hold following the execution of _EfficientRebuild( $k$)_, by
[BHN19] and [BHNW21].

  1. (1)

Every element $e$ that was active at level up to $k$ in the foreground upon
beginning this phase will end up active and at level up to $k+1$.

  2. (2)

Every element $e$ that was passive at level up to $k$ in the foreground upon
beginning this phase will end up active at level up to $k+1$ or passive at
level _exactly_ $k+1$.

  3. (3)

Every element $e$ that was dead at level up to $k$ in the foreground upon
beginning this phase will end up removed completely of the system.

  4. (4)

The procedure does not touch any element that was at level $\geq k+1$ in the
foreground upon the beginning of this phase.

  5. (5)

Each set in $S^{(k)}_{i}$ for any $1\leq i\leq k+1$ is tight.

  6. (6)

Each element participating in the reset is contained in at least one tight
set.

  7. (7)

$|P_{i}|<\epsilon\cdot|A_{i}|$ for all $i\leq k$. Notice that by $(2)$ it may
seem that $|P_{i}|=0$ for any $i\leq k$, but $(2)$ refers only to elements
that were in the system when this phase began, and not elements that were
inserted during the execution.

The running time of this procedure is given in the following lemma:

######  Lemma 5.3 (Claim $C.2$ in [BHNW21]).

The running time of the water-filling phase of $\mathsf{reset}(k)$ is
$O(f\cdot|\mathcal{U}^{(k)+}|)$.

##### Termination Phase.

When the water-filling algorithm $\mathsf{reset}(k)$ is finished, we set
$S_{i},E_{i}$ to be $S_{i}^{(k)},E_{i}^{(k)},i\in[0,k]$, and append the linked
list of $S^{(k)}_{k+1},E^{(k)}_{k+1}$ to $S_{k+1},E_{k+1}$. Finally, abort all
lower-level reset instances. The implementation of switching the pointers is
roughly the same as in the high-frequency regime, as explained next.

When $\mathsf{reset}(k)$ has finished and called upon to switch its memory to
the foreground, for every index $0\leq i\leq k$, we replace every pointer to
$S_{i}$ with the pointer to $S^{(k)}_{i}$, and connect all pointers to
nonempty lists $S^{(k)}_{i},0\leq i\leq k$ with a linked list.

Merging the list $S_{k+1}^{(k)}$ with the list $S_{k+1}$ on the foreground is
in fact done in the water-filling phase, as it does not have worst-case
runtime guarantee. Nevertheless it will be explained here as part of the
termination phase. Upon merging $S_{k+1}^{(k)}$ with $S_{k+1}$, suppose
$S_{k+1}$ is equal to some $S_{k+1}^{(l)}$ for some $l\geq k+1$; in other
words, $S_{k+1}$ was computed in some instance $\mathsf{reset}(l)$, where
$l\geq k+1$. Then, for each set $s\in S^{(k)}_{k+1}$, redirect the pointer
$\mathsf{lev}[s][k]$ from the list head $S^{(k)}_{k+1}$ to the list head
$S_{k+1}^{(l)}$. After that, concatenate the two lists
$S_{k+1}^{(k)},S_{k+1}$. We can merge the two lists $E_{k+1}^{(k)}$ and
$E_{k+1}$ in a similar manner. The running time of this is clearly
$O(f\cdot|\mathcal{U}^{(k)}|)$, thus not the bottleneck of the water-filling
phase.

As for the runtime of the termination phase, the number of memory pointers to
be switched is at most $O(L)=O(\log_{\beta}(Cn))$, so the worst-case runtime
is $O(L)=O(\log_{\beta}(Cn))$. For any set $s\in\mathcal{S}^{(k)}$, to access
any level value $\mathsf{lev}^{(k)}(s)$ in the background, we can follow the
pointer $\mathsf{lev}[s][k]$ and check $\mathsf{lev}^{(k)}(s)$ in constant
time; similarly we can check the value of $\mathsf{lev}^{(k)}(e)$ for any
$e\in\mathcal{U}^{(k)+}$ in constant time.

Since our data structures maintain multiple versions of the level values, and
our algorithm keeps switching memory locations between the foreground and the
background, we need to argue the consistency of the foreground data
structures; this was done in 3.1.1 for the high-frequency regime, which
equivalently holds for the low-frequency regime as well.

By the algorithm description, upon an element update, we scan all the levels,
and if any instance of $\mathsf{reset}(\cdot)$ has just terminated, we switch
the one $\mathsf{reset}(k)$ on the highest level $k$ to the foreground as we
have discussed in the previous paragraph, while aborting all other instances
of $\mathsf{reset}(i),i<k$. As we have seen, switching a single instance of
$\mathsf{reset}(\cdot)$ to the foreground takes $O(L)=O(\log_{\beta}(Cn))$
time, and so the worst-case time of this part is $O(L)=O(\log_{\beta}(Cn))$.
Therefore, the termination can be done in a single update step (along with the
short level reset).

To conclude Section 5.2, any insertion/deletion in the foreground can be dealt
with in $O(f\cdot L)$ time, thus it can be done within a single update step.
Dealing with the short level reset (finding the highest one, initializing the
reset, and executing it) takes $O(L)$ time, thus it will all be done within a
single update step as well. Likewise, termination can be done in $O(L)$ time
(updating data structures of the highest finished reset and aborting the
rest). Every other $\mathsf{reset}(k)$ will take
$O(f\cdot|\mathcal{U}^{(k)+}|)$ time (initialization and water-filling phase).
Since this cannot be executed within a single update step, for each $k$ we
will execute $O(\frac{f}{\epsilon})$ computations per update step. In Section
5.3 we will prove that by working in such a pace, we can ensure that 5.1
holds, which in turn will be enough to prove that the approximation factor
holds, by Lemma 5.2.

###  5.3 Proof of Correctness

In this section we prove that 5.1 always holds in the foreground, mainly
relying on the properties of _EfficientRebuild( $k$)_ given in [BHNW21].

######  Claim 5.3.1.

5.1(1) always holds in the foreground.

###### Proof.

Assume 5.1(1) holds right before time step $t$. Following the
insertion/deletion at time $t$, it is easy to verify that 5.1(1) still holds.
Indeed, a deletion does not raise the weight of any element, and due to an
insertion of element $e$ either $\omega(e)=0$, or $e$ is assigned a weight
small enough such that the weight of any set $s\ni e$ does not surpass its
cost, by the description of the algorithm. Following the termination of some
$\mathsf{reset}(k)$, 5.1(1) holds from the description of the reset procedure
presented in Section $C.4$ in [BHNW21]. ∎

######  Claim 5.3.2.

5.1(2) always holds in the foreground.

###### Proof.

Assume 5.1(2) holds right before time step $t$. Following the
insertion/deletion at time $t$, it is easy to verify that 5.1(2) still holds.
Indeed, following the update the weight of any set at level $\geq 1$ does not
reduce. Following the termination of some $\mathsf{reset}(k)$, 5.1(2) holds by
Lemma C.10 in [BHNW21]. ∎

######  Claim 5.3.3 (Lemma C.11 in [BHNW21]).

Following the termination of an instance $\mathsf{reset}(k)$, we have
$|P_{i}|<\epsilon\cdot|A_{i}|$ for all $i\leq k$.

######  Claim 5.3.4.

When $\mathsf{reset}(k)$ terminates and is transferred to the foreground, it
does not change $A_{k^{\prime}}$ or $P_{k^{\prime}}$, for any $k^{\prime}>k$.

###### Proof.

The claim follows immediately from the description of the reset procedure
presented in Section $C.4$ in [BHNW21], and by Property $3.6(4)$ in [BHN19]. ∎

######  Lemma 5.4.

5.1(3) always holds in the foreground.

###### Proof.

Assume by contradiction that there exists $k$ such that
$|P_{k}|>2\epsilon\cdot|A_{k}|$ for some $k$, at the end of update step $t$
(right before update step $t+1$). Let $t^{\prime}$ be the last time step
before $t$ that $\mathsf{reset}(k)$ was initiated. $\mathsf{reset}(k)$ was
initiated at time $t^{\prime}$ right after the termination of some
$\mathsf{reset}(k^{\prime})$, where $k^{\prime}\geq k$, by the algorithm
description. By 5.3.3, we know that at time $t^{\prime}$ (following the
termination of $\mathsf{reset}(k^{\prime})$) we have
$|P_{k}|<\epsilon\cdot|A_{k}|$ in the foreground.

Between $t^{\prime}$ and $t$, $|P_{k}|$ can increase and $|A_{k}|$ can
decrease only due to insertions/deletions, since by definition of $t^{\prime}$
no termination of $\mathsf{reset}(k^{\prime})$ for any $k^{\prime}\geq k$
exists, and any termination of $\mathsf{reset}(k^{\prime})$ for any
$k^{\prime}<k$ would not raise $|P_{k}|$ or change $A_{k}$ by 5.3.4. By
denoting $A_{k}$ at times $t^{\prime}$ and $t$ by $A_{k}^{t^{\prime}}$ and
$A_{k}^{t}$ respectively, we conclude that there must be more than
($2\epsilon\cdot|A_{k}^{t}|-\epsilon\cdot|A_{k}^{t^{\prime}}|$) update steps
between $t^{\prime}$ and $t$, since again due to one insertion/deletion only
one element can join $P_{k}$.

If we denote by $x$ the total number of update steps throughout which
$\mathsf{reset}(k)$ is executed, we can execute the reset at a pace such that:

$x<\frac{\epsilon}{2}(|P_{k}^{t^{\prime}}|+|A_{k}^{t^{\prime}}|),$ (14)

since the collection of all elements participating in $\mathsf{reset}(k)$
initiated at time $t^{\prime}$ is $P_{k}^{t^{\prime}}\cup A_{k}^{t^{\prime}}$.
We assume that at update step $t$, $\mathsf{reset}(k)$ is still running, thus
we will reach a contradiction if:

$\frac{\epsilon}{2}(|P_{k}^{t^{\prime}}|+|A_{k}^{t^{\prime}}|)<2\epsilon\cdot|A_{k}^{t}|-\epsilon\cdot|A_{k}^{t^{\prime}}|.$
(15)

Now, notice that:

$|A_{k}^{t}|\geq|A_{k}^{t^{\prime}}|-x,$ (16)

since again, in each update step during the reset up to one element can be
removed from $A_{k}$, and we assumed that $x\geq t-t^{\prime}$. Thus, we need
to show that:

$\frac{\epsilon}{2}(|P_{k}^{t^{\prime}}|+|A_{k}^{t^{\prime}}|)<2\epsilon\cdot(|A_{k}^{t^{\prime}}|-x)-\epsilon\cdot|A_{k}^{t^{\prime}}|.$
(17)

Plugging in $x$ from Equation 14 and rearranging, we get that we need to show:

$(\frac{1}{2}+\epsilon)|P_{k}^{t^{\prime}}|<(\frac{1}{2}-\epsilon)|A_{k}^{t^{\prime}}|.$
(18)

Since we know that $|P_{k}^{t^{\prime}}|<\epsilon|A_{k}^{t^{\prime}}|$, it is
enough to show that:

$(\frac{1}{2}+\epsilon)\cdot\epsilon|A_{k}^{t^{\prime}}|<(\frac{1}{2}-\epsilon)|A_{k}^{t^{\prime}}|,$
(19)

meaning that

$2\epsilon^{2}+3\epsilon-1<0,$ (20)

which holds for any $\epsilon<\frac{1}{4}$. Thus, we reach our contradiction
and the lemma follows. ∎

We conclude that our algorithm indeed maintains 5.1, in worst-case update time
of $O(\frac{f\cdot L}{\epsilon})=O\left(\frac{f\log(Cn)}{\epsilon^{2}}\right)$
as proved in Section 5.2. Since 5.1 holds, the approximation factor of the
maintained minimum set cover is $(1+\epsilon)f$, as shown in Lemma 5.2. This
concludes the proof of Lemma 5.1.

###  5.4 Removing Dependency on Aspect Ratio

To remove the dependency on $C$ in the update time, we employ the same black-
box reduction from Section 4 for the high-frequency regime. Define the _top
level_ of set $s$ as
$\mathsf{toplev}(s)=\lceil\log_{\beta}(n/\mathsf{cost}(s))\rceil$. Define a
parameter $K=\lceil 10\log_{\beta}n\rceil$.

######  Definition 5.2.

For any $l\geq-1$, define
$\mathcal{S}_{l}=\\{s\in\mathcal{S}\mid\mathsf{toplev}(s)\in[lK,(l+2)K)\\}$,
and let $\mathcal{U}_{l}$ be the collection of all elements such that the
cheapest set containing them is in $\mathcal{S}_{l}$.

For each $l\geq-1$, we will maintain a set cover
$\mathcal{S}_{l,\mathsf{alg}}\subseteq\mathcal{S}_{l}$ that covers
$\mathcal{U}_{l}$ by applying Lemma 5.1 as a black-box which takes
$O\left(\frac{f\log n}{\epsilon^{2}}\right)$ worst-case update time. Overall,
by 4.1 and 4.2 we will have two different set cover solutions for
$\mathcal{U}$:

$\mathcal{S}_{\mathrm{even},\mathsf{alg}}=\bigcup_{j\geq
0}\mathcal{S}_{2j,\mathsf{alg}}\;,\;\mathcal{S}_{\mathrm{odd},\mathsf{alg}}=\bigcup_{j\geq
0}\mathcal{S}_{2j-1,\mathsf{alg}}.$

Following similar lines to those in the argument for the high-frequency
setting, it can be proved that at least one solution from
$\\{\mathcal{S}_{\mathrm{even},\mathsf{alg}},\mathcal{S}_{\mathrm{odd},\mathsf{alg}}\\}$
is a $(1+\epsilon)f$-approximation; we next provide this argument, for
completeness, which would complete the proof of Theorem 1.2.

######  Lemma 5.5.

For any $l\geq-1$, let $k_{0}\in I_{l}$ be the smallest index such that there
exists a set in $\mathcal{S}_{l}$ covering at level $k_{0}$, or in other
words, $k_{0}$ is the smallest level such that
$\mathcal{S}_{l,\mathsf{alg}}\cap S_{l,k_{0}}\neq\emptyset$. If
$k_{0}\leq(l+1)K$, then we have:

$\sum_{j\geq
0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})\leq(1+O(\epsilon))f\cdot\mathsf{cost}(\mathcal{S}^{*}).$

###### Proof.

We know that
$\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}})\leq(1+O(\epsilon))f\cdot\mathsf{cost}(\mathcal{S}^{*}_{l})\leq(1+O(\epsilon))f\cdot\mathsf{cost}(\mathcal{S}^{*})$.
Consider any set $s_{0}\in\mathcal{S}_{l,\mathsf{alg}}\cap S_{l,k_{0}}$. For
any set $s\in\mathcal{S}_{l+2j,\mathsf{alg}}$ and $j>0$, we have:

$\mathsf{cost}(s)\leq n\cdot\beta^{1-\mathsf{toplev}(s)}\leq
n\cdot\beta^{1-(l+2)K}\leq
n\cdot\beta^{1-k_{0}-K}\leq\frac{\epsilon}{(1+2\epsilon)n}\cdot\beta^{-k_{0}-1}\leq\frac{\epsilon\cdot\mathsf{cost}(s_{0})}{(1+2\epsilon)n},$
(21)

where the first inequality holds since
$\mathsf{toplev}(s)\leq\log_{\beta}(n/\mathsf{cost}(s))+1$ (by definition of
$\mathsf{toplev}(s)$), the second holds since
$\mathsf{toplev}(s)\geq(l+2j)K\geq(l+2)K$ for any $j>0$ by definition of $s$,
the third follows from the initial assumption that $k_{0}\leq(l+1)K$, the
fourth by definition of $K$ and that $\epsilon>\frac{2}{n^{8}}$ is not too
small, and the fifth holds since $s_{0}$ is covering at level $k_{0}$. Since
at most $n$ elements are alive and at most $2\epsilon\cdot n$ elements may be
dead (otherwise 5.1(3) is violated), and as each element (dead or alive) is
assigned to at most one set in the set cover solution, it follows that the
total number of sets in $\mathcal{S}_{l+2j,\mathsf{alg}}$ over all $j>0$ is
bounded by $(1+2\epsilon)n$. By Equation 21, we get

$\sum_{j>0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})~{}\leq~{}(1+2\epsilon)n\cdot\left(\frac{\epsilon}{(1+2\epsilon)n}\cdot\mathsf{cost}(s_{0})\right)~{}\leq~{}\epsilon\cdot\mathsf{cost}(s_{0})~{}\leq~{}\epsilon\cdot\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}}).$

We conclude that

$\sum_{j\geq
0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})~{}=~{}\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}})+\sum_{j>0}\mathsf{cost}(\mathcal{S}_{l+2j,\mathsf{alg}})~{}\leq~{}(1+\epsilon)\cdot\mathsf{cost}(\mathcal{S}_{l,\mathsf{alg}})~{}\leq~{}(1+O(\epsilon))f\cdot\mathsf{cost}(\mathcal{S}^{*}),$

and the lemma follows. ∎

Next, by following the same lines of Lemma 4.2 (with $f$ instead of $\ln n$)
and using Lemma 5.5, we can show that:

$\min\\{\mathsf{cost}(\mathcal{S}_{\mathrm{even},\mathsf{alg}}),\mathsf{cost}(\mathcal{S}_{\mathrm{odd},\mathsf{alg}})\\}\leq(1+O(\epsilon))f\cdot\mathsf{cost}(\mathcal{S}^{*}),$

and we have thus concluded the proof of Theorem 1.2.

##  6 From Dynamic Dominating Set to Set Cover

##### The Standard Reduction from Static Dominating Set to Set Cover.

Given our graph $G=(V,E)$ with $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, one can
construct a set cover instance $(\mathcal{U},\mathcal{S})$ as follows. The
universe is $\mathcal{U}=\\{e_{1},e_{2},\ldots,e_{n}\\}$, and the family of
sets is $\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{n}\\}$ such that $S_{i}$
consists of the element $e_{i}$ and all elements $e_{j}$ such that $v_{j}$ is
adjacent to $v_{i}$ in $G$. Now if $D$ is a dominating set for $G$, then
$\mathcal{S}_{\mathsf{alg}}=\\{S_{i}~{}|~{}v_{i}\in D\\}$ is a feasible
solution of the set cover problem, with
$\mathsf{cost}(\mathcal{S}_{\mathsf{alg}})=\mathsf{cost}(D)$. Conversely, if
$\mathcal{S}_{\mathsf{alg}}$ is a feasible solution of the set cover problem,
then $D=\\{v_{i}~{}|~{}S_{i}\in\mathcal{S}_{\mathsf{alg}}\\}$ is a dominating
set for $G$, with
$\mathsf{cost}(D)=\mathsf{cost}(\mathcal{S}_{\mathsf{alg}})$. Hence, the cost
of a minimum dominating set for $G$ equals the cost of a minimum set cover for
$(\mathcal{U},\mathcal{S})$, and in particular, if
$\mathcal{S}_{\mathsf{alg}}$ provides an $\alpha$-approximation for the set
cover problem given by $(\mathcal{U},\mathcal{S})$, then
$D=\\{v_{i}~{}|~{}S_{i}\in\mathcal{S}_{\mathsf{alg}}\\}$ provides an
$\alpha$-approximation for the dominating set problem given by $G$.

###  6.1 A Reduction in the Dynamic Setting

##### Handling Edge Insertions and Deletions.

There is a key difference between the set cover problem and the dominating set
problem in the dynamic setting. In the set cover problem the adversary inserts
or deletes an element upon each update step, whereas in the dominating set
problem the adversary inserts or deletes an edge upon each update step, which
can be thought of as creating or removing two _connections_ between an element
to a set in the set cover problem. That is, if the edge $(v_{i},v_{j})$ is
inserted, then in the set cover problem we would want to add $e_{i}$ to
$S_{j}$ and $e_{j}$ to $S_{i}$; similarly, if the edge $(v_{i},v_{j})$ is
deleted, then in the set cover problem we want to remove $e_{i}$ from $S_{j}$
and $e_{j}$ from $S_{i}$. Since such an operation does not exist in the basic
dynamic setting of the set cover problem, we will treat such an operation as
an element deletion followed by an element insertion of the same element, just
with a different (by one set) collection of sets that can cover the element,
as explained next.

##### Algorithm.

We will use _as a black box_ the algorithm for the set cover problem in the
high-frequency regime, provided by Theorem 1.1 (and presented in Sections 3
and 4). We are given initially a graph $G$ with $n$ vertices and no edges.
Thus, in our reduction to set cover, we will begin with $n$ active elements
$e_{1},e_{2},\ldots,e_{n}$, and $n$ sets $S_{1},S_{2},\ldots,S_{n}$ such that
each $S_{i}$ contains only $e_{i}$. Upon insertion of edge $(v_{i},v_{j})$ by
the adversary, in our set cover system we delete $e_{i}$ and insert it with
the same collection of sets that it was contained in before, _plus_ $S_{j}$;
likewise, we delete $e_{j}$ and insert it with the same collection of sets
that it was contained in before, _plus_ $S_{i}$. Upon deletion of edge
$(v_{i},v_{j})$ by the adversary, in our set cover system we delete $e_{i}$
and insert it with the same collection of sets that it was contained in
before, _minus_ $S_{j}$; likewise, we delete $e_{j}$ and insert it with the
same collection of sets that it was contained in before, _minus_ $S_{i}$.
Overall, each adversary edge update is translated to four set cover updates.
Explicitly performing each of these four set cover updates in the set cover
instance takes time that is linear in the degrees of the two endpoints of the
updated edge, which is at most $O(\Delta)$. By working at a pace four times
faster than in the set cover algorithm, the worst case update time will still
be $O\left(\frac{f\log n}{\epsilon^{2}}\right)$. Notice that the frequency of
each element is upper bounded by $\Delta+1$, thus we actually obtain a worst-
case update time of $O\left(\frac{\Delta\log n}{\epsilon^{2}}\right)$.
Regarding the approximation factor, recall that by Lemma 3.1 we have that
$\mathsf{cost}(\mathcal{S}_{\mathsf{alg}})\leq(1+O(\epsilon))\cdot\ln
n^{\prime}\cdot\mathsf{cost}(\mathcal{S}^{*})$, where $\mathcal{S}^{*}$ is an
optimal set cover for $\mathcal{U}$, and $n^{\prime}$ is an upper bound to the
size of each set throughout the update sequence, which is $\Delta+1$ in this
setting. Thus, we obtain an approximation factor of
$(1+O(\epsilon))\cdot\ln(\Delta+1)=(1+O(\epsilon))\cdot\ln\Delta$, which
concludes the proof of Theorem 1.3.

## References

  * [AAG+19] Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha.  Dynamic set cover: improved algorithms and lower bounds.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 114–125, 2019.
  * [AS21] Sepehr Assadi and Shay Solomon.  Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach.  In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [BCH17] Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger.  Deterministic fully dynamic approximate vertex cover and fractional matching in o (1) amortized update time.  In International Conference on Integer Programming and Combinatorial Optimization, pages 86–98. Springer, 2017.
  * [BHI15] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano.  Design of dynamic algorithms via primal-dual method.  In International Colloquium on Automata, Languages, and Programming, pages 206–218. Springer, 2015.
  * [BHN19] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  A new deterministic algorithm for dynamic set cover.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 406–423. IEEE, 2019.
  * [BHNW21] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu.  Dynamic set cover: Improved amortized and worst-case update time.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2537–2549. SIAM, 2021.
  * [BSZ23] Anton Bukov, Shay Solomon, and Tianyi Zhang.  Nearly optimal dynamic set cover: Breaking the quadratic-in-$f$ time barrier.  arXiv preprint arXiv:2308.00793, 2023.
  * [DS14] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624–633, 2014.
  * [GKKP17] Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi.  Online and dynamic algorithms for set cover.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 537–550, 2017.
  * [GP13] Manoj Gupta and Richard Peng.  Fully dynamic (1+ e)-approximate matchings.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 548–557. IEEE, 2013.
  * [KR08] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within $2-\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [SU23] Shay Solomon and Amitai Uzrad.  Dynamic $((1+\epsilon)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1187–1200, 2023.
  * [WS11] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.


[1]Davide La Torre

[1]SKEMA Business School, Université Côte d’Azur, Sophia-Antipolis, France
2]University of Milan-Bicocca, Milan, Italy 3]Siemens S.p.a., Milan, Italy
4]Abu Dhabi School of Management, Abu Dhabi, UAE

# Federated Deep Learning in Electricity Forecasting: An MCDM Approach

Marco Repetto<EMAIL_ADDRESS><EMAIL_ADDRESS>Muhammad Tariq
<EMAIL_ADDRESS>*  [  [  [

###### Abstract

Large-scale data analysis is growing at an exponential rate as data
proliferates in our societies. This abundance of data has the advantage of
allowing the decision-maker to implement complex models in scenarios that were
prohibitive before. At the same time, such an amount of data requires a
distributed thinking approach. In fact, Deep Learning models require plenty of
resources, and distributed training is needed. This paper presents a
multicriteria approach for distributed learning. Our approach uses the
Weighted Goal Programming approach in its Chebyshev formulation to build an
ensemble of decision rules that optimize aprioristically defined performance
metrics. Such a formulation is beneficial because it is both model and metric
agnostic and provides an interpretable output for the decision-maker. We test
our approach by showing a practical application in electricity demand
forecasting. Our results suggest that when we allow for dataset split
overlapping, the performances of our methodology are consistently above the
baseline model trained on the whole dataset.

###### keywords:

Multiple Criteria Optimization, Training, Algorithm

##  1 Introduction

It is well know that Artificial Intelligence (AI) identifies in a broad sense
the ability of a machine to learn from experience, to simulate the human
intelligence, to adapt to new scenarios, and to get engaged in human-like
activities. AI identifies an interdisciplinary area which includes computer
science, robotics, engineering, mathematics. Over the years, it has made a
rapid progress: it will contribute to the society transformation through the
adoption of innovating technologies and creative intelligence and the large-
scale implementation of AI in technologies such as IoT, smart speakers, chat-
bots, cybersecurity, 3D printing, drones, face emotions analysis, sentiment
analysis, natural language processing, and their applications to human
resources, marketing, finance, and many others.

With the term Machine learning (ML), instead, we identify a branch of AI in
which algorithms are used to learn from data to make future decisions or
predictions. ML algorithms are trained on past data in order to make future
predictions or to support the decision making process.

Deep Learning (DL), instead, is a subset of ML and it includes a large family
of ML methods and architectures based on Artificial Neural Networks (ANNs). It
includes Deep Neural Networks, Deep Belief Networks, Deep Reinforcement
Learning, Recurrent Neural Networks and Convolutional Neural Networks, to
mention a few of them. DL algorithms have been used in several applications
including computer vision, speech recognition, natural language processing,
bioinformatics, medical image analysis, and in most of these areas they have
demonstrated to perform better than humans. In the recent years DL has
disrupted every application domain and it provides a robust, generalized, and
scalable approach to work with different data types, including time-series
data lecun2015deep ; bengio2013representation ; he2016deep ; van2015lbann .

Fostered by the abundance of data, many recent DL architectures require a
considerable amount of training. At the same time, local regulations posed
significant constraints in terms of data transmission in distributed systems
ahmed2021 . Because of this konecny2017  proposed the concept of Federated
Learning (FL). FL is a distributed learning methodology allowing model
training on a large corpus of decentralized data bonawitz2019 .

Recent applications of the FL focus primarily on the medical field, as
particular attention has to be placed on patient information. In jimenez-
sanchez2021  the authors proposed an FL system based on memory-aware
curriculum learning to solve the problem of class imbalance in the data of
multiple institutions. In beguier2021 , the authors proposed a sound FL
methodology with Differential Privacy with an acceptable compromise between
privacy and performance. It is worth noting how both techniques may suffer
from data leakage as by sharing gradients within nodes, some of the original
information may be reconstructed zhu2020 . Aside from the medical field,
kholod2021  investigated FL applied on the Internet of Things (IoT) comparing
different out-of-the-shelf open-source approaches. In particular, the authors
evaluated several aspects ranging from ease of use to performance in terms of
implementation.

Aside from the performance, FL carries different concerns in terms of data
leakage depending on the method utilized in the aggregation phase lim2021 .
Moreover, as pointed out by bagdasaryan2020  these systems can be subject to
adversarial attacks.

Adversarial training is a fairly recent field in ML and DL. It is about the
limitations of existing algorithms in their ability to correctly classify when
they have been trained on adversarially datasets or to react against the
effect of inputs purposely designed to fool a ML model. A critical scenario in
adversarial learning happens when training the same model from different
datasets that show conflicting trends or behaviours. For instance, this is the
case in financial forecasting when one tries to predict the future evolution
of financial markets based on covid or pre-covid data.

Adversarial training impacts FL based on how the aggregation procedure is
carried out. As demonstrated in lim2021  in the case of FL in which gradients
are shared, the attacker can leverage models gradients to either reconstruct
datapoints or to inject an adversarial attack. In particular, adversarial
attacks may happen even in federated averaging as these aggregation techniques
lack node accountability bagdasaryan2020 .

Motivated by the above considerations, in order to avoid the bias given by one
dataset with respect to another, in this paper we propose an new approach
based on Multiple Criteria Decision Making (MCDM). The different loss
functions obtained by training the same model on different datasets are
combined in a unique framework by means of MCDM techniques. More in
particular, we propose a Goal Programming (GP) model to deal with this complex
scenario. Numerical experiments show the goodness of this approach and provide
strategic managerial insights.

The intersections between MCDM and DL have not been explored yet and in the
literature there are just a few contributions that try to combine MCDM and
forecasting/machine learning techniques. To mention a few of them, for
instance in angelopoulos2019disaggregating  the authors analyze the
relationship between times series and influential multiple criteria and they
offer long-term electricity demand predictions in Greece. In stoilova2021novel
, instead, the authors propose a novel fuzzy multiple criteria time series
modelling method based on fuzzy linear programming and sequential interactive
techniques and they apply it to urban transportation planning.

Our approach aligns with the FL paradigm as our dataset is heterogeneous and
spread across many nodes with some computing capabilities. Moreover, our
approach is affected by the literature on adversarial training as models
compete in the aggregation phase. In our case, the number of models coincides
with the number of nodes, but theoretically, this can be extended by allowing
ensemble in each local node. Our approach distinguishes from the previous ones
as it is not model-dependent kholod2021 . Moreover, our approach is different
from model averaging as proposed by yager1988 , warnat-herresthal2021  and
mcmahan2017  as we allow for nodes accountability and attribute nodes
relevance based on their performance.

The paper is organized as follows. Section 2 is devoted to the literature
review on MCDM. In Section 3 we present our main model. In Section 4 we
present numerical experiments and discuss the results of our approach in the
case of electricity demand forecasting. Section 5 concludes.

##  2 Multiple Criteria Decision Making and Goal Programming

MCDM is a branch of Operations Research and Management Science. MCDM includes
the set of methods and processes through which the concern for several
conflicting criteria can be explicitly incorporated into the analytical
process ehrgott2002 . Several strategies, spanning from a priori to
interactive ones, have been developed to address this issue. Furthermore,
these methods were widely used in a variety of fields, including economics,
engineering, finance, and management colapinto2017multi . Historically MCDM’s
first roots are the ones laid by Pareto at the end of the 19th century. An
MCDM problem is expressed mathematically as follows:

$\displaystyle\min_{\boldsymbol{x}}$
$\displaystyle(f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\dots,f_{p}(\boldsymbol{x}))$
(1) s.t. $\displaystyle\boldsymbol{x}\in S$ (2)

where $f_{i}:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ is the ith objective and
the vector $\boldsymbol{x}$ contains the decionsion variabels that belong to
the feasible set $S$.

Scalarization is a common approach for dealing with Multicriteria optimization
problems. By scalarization, a vector optimization problem is converted into a
single objective optimization problem by means of a weighted sum scalarization
$f(\boldsymbol{x})=\boldsymbol{w}^{\top}\boldsymbol{f}(\boldsymbol{x})=\sum_{i=1}^{p}w_{i}f_{i}(\boldsymbol{x})$
where $\boldsymbol{w}$ is a vector weights. Each criterion is included in the
scalarized version with different weights which express the relative
importance of that criterion for the Decision Maker (DM). Another method that
can be used to solve vector-valued problems is Goal Programming (or GP
approach). The method was initially proposed by charnes1955optimal  and it
aims at minimizing the deviations coming from the over or under achievement of
different objectives. The innovative idea behind this model is the
determination of the aspiration levels of an objective function. This model
does not try to find an optimal solution but an acceptable one (or satisfying
one), and it tries to achieve the goals set by the DM rather than maximising
or minimising the different criteria. Given a set of ideal goals $g_{i}$ ,
with $i=1,...,p$, chosen by the DM, a weighted GP problem takes the form:

$\displaystyle\min_{\boldsymbol{x},\delta^{+}_{i},\delta^{-}_{i}}$
$\displaystyle\sum_{i=1}^{p}w^{+}_{i}\delta^{+}_{i}+w^{-}_{i}\delta^{-}_{i}$
(3) s.t. $\displaystyle
f_{i}(\boldsymbol{x})+\delta^{-}_{i}-\delta^{+}_{i}=g_{i},\quad i=1\dots p$
(4) $\displaystyle\boldsymbol{x}\in S$ (5)
$\displaystyle\delta^{-}_{i},\delta^{+}_{i}\geq 0,\quad i=1\dots p$ (6)

where $\delta^{+}_{i},\delta^{-}_{i}$ measures respectively the negative and
the positive deviations to the optimal level $g_{i}$, whereas
$w^{+}_{i},w^{-}_{i}$ express the relative importance of the modeler to these
goals.

##  3 Model Formulation

Before specifying our approach is worth defining some notation that will be
used through the section and in the empirical application. In our setup, we
observe a tuple of the target variable and features over time, that is
$\\{(y_{t},\boldsymbol{x}_{t})\mathchar 24635\relax\;t=1...T\\}$. As our
empirical application focuses on univariate time series forecasting, the
features are the lagged values of the target variable. However, our approach
is suitable for any use case in which a large dataset prevents any model
estimation in a single machine or whether the dataset is distributed across
many nodes not belonging to the same device. Now let’s assume that we slice
the whole dataset into $K$ partitions such that $\sum_{k=1}^{K}S_{k}\geq T$.
In other words, the sum of the lengths of each partition is at least the
length of the dataset itself. This formulation allows for overlapping in
between partitions. This is a recurrent situation in many distributed systems,
as data redundancy is used to enforce the system’s reliability. In our
empirical experiment, we considered the different degrees of overlapping
ranging from no overlapping at all, that is, $\sum_{k=1}^{K}S_{k}=T$ to full
overlapping in which each partition includes the two adjacent ones. In other
words $\sum_{k=1}^{K}S_{k}\approx 3T$

Given these premises, the proposed FL approach can be divided into three
steps: local learning, federated validation-aggregation, and local updating.

In step 1, we train a model for each data partition, that is
$f_{k}(w_{k},\boldsymbol{x}_{k,t})$, $\forall k\in K,\forall t\in S_{k},$
where $S_{k}$ index the subset of each partition, we can define the
predictions of such model as $\hat{y}_{k,t}$ where the prediction depends on
both the model indexed with $k$ and the subset of features provided indexed
with $t$. In step 2, we solve the following Chebyshev Goal Programming
(flavell1976, ) problem to find an ensemble of models that jointly performs
better than the sole models on all the dataset splits:

<b> α_j, λλ δ_k^+≤λ∀k ∈K ∑_j=1^Kα_j L_j(y_k,t, ^y_k,t)- δ_k^+ + δ_k^- =
L_k(y_t, ^y_k,t) ∀k ∈K, ∀t ∈S_k ∑_k=1^Kα_k = 1 α_k, δ^+_k, δ^-_k≥0 ∀k ∈K

In step 3, with the optimal set of weights $\boldsymbol{\alpha}$ we predict
the output as a convex combination of the $1...K$ trained models, that is:

$\hat{y_{t}}=\sum_{k=1}^{K}\alpha_{k}f_{k}(w_{k},\boldsymbol{x}_{k,t})$

.

The advantage of such an approach is that it is both model and metric
agnostic. More specifically, the approach is model agnostic in the sense that
$f(\cdot)$ can be any predictive function, ranging from Deep ANNs to Gradient
Boosted Machines. Moreover, the approach is metric agnostic as $L(\cdot)$ can
be substituted with any, possibly non-differentiable, performance metric. An
example in the case of classification may be to use accuracy or the Area Under
the Receiving Operating Curve (AUROC). However, in such cases, as both the
accuracy and AUROC need to be maximized, $\delta^{-}$ should be placed in the
first soft constraint of the GP.

##  4 Numerical Experiments and Discussion

This section describes an application of our approach to the use case of
electricity demand forecasting. In particular, we employ a publicly available
dataset, the 2017 Global Energy Forecasting Competition (GEFCom2017) dataset
(hong2019, ). The dataset consists of information about the electricity load,
holiday, and weather data. Our application in electricity demand forecasting
focuses only on electricity load, particularly on the total electricity load
given by the sum of all the different New England zones.

Figure 1: Total electricity demand for the New England from 1st March 2003 to
30th April 2017 on a hourly basis.

The plot in Figure 1 gives a perspective on the size of the time series that
spans from 1st March 2003 to 30th April 2017 with a frequency of one hour. In
total, the time series consists of more than 100 thousand observations.

###  4.1 Experimental setup

The GEFCom2017 competition required only one month ahead forecast. In our
setup, we extend the forecasting horizon in order to compare our approach to
the approach proposed by other authors, such as the one proposed in wang2020 .
Therefore we split the time series into training and test set. The training
set starts at the beginning of the dataset and ends on the 31st of December
2016. The test set starts on the 1st of January 2017 and ends on the 30th of
April 2017. The forecasting horizon is then of 2879 steps. To model this time
series, we use the Feedforward Artificial Neural Network (FANN) in its most
straightforward architecture, the Multilayer Perceptron (MLP). The functional
form of the MLP can be elicited as in arifovic2001 :

$f(x)=\phi\left(\beta_{0}+\sum_{j=1}^{d}\beta_{j}G\left(\gamma_{j0}+\sum_{i=1}^{p}\gamma_{ji}x_{i}\right)\right)$
(7)

where G is the activation function, in our case $G(x)=\frac{1}{1+e^{-\alpha
x}}$, $\beta$ and $\gamma$ represent weights and biases at each layer, whereas
$\phi(\cdot)$ is the network output function that in our case is the identity
function as our goal is to regress electricity demand and not time series
classification. To test our approach’s robustness, we used different
configurations in terms of split size and splits overlapping. For the split
size, we considered 10, 150, and 200, whereas, for the overlapping ratio, we
considered complete, half, and no overlaps in between the splits.

###  4.2 Evaluation metrics

The evaluation metrics we used are: Root Mean Squared Error (RMSE), Mean
Absolute Error (MAE), Mean Absolute Scaled Error (MASE) and Symmetric Mean
Absolute Percentage Error (SMAPE). RMSE is a standard metric used both in time
series contexts and more broadly in any supervised learning setting. It is
defined as:

$RMSE=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\hat{y}_{i})^{2}}$

the RMSE is a scale-dependent metric and, because it uses squared errors, is
more sensitive to higher deviations than other measures such as MAE. MAE,
while being also a scale-dependent measure metric, is formulated as:

$MAE=\frac{1}{n}\sum_{i=1}^{n}\absolutevalue{y_{i}-\hat{y}_{i}}$

Differently from the first two metrics, MASE is a scale-independent metric
that is used chiefly in time series contexts, initially proposed by
hyndman2006 , MASE is defined as follows:

$MASE\frac{\frac{1}{J}\sum_{j}\absolutevalue{y_{j}-\hat{y}_{j}}}{\displaystyle\frac{1}{T-1}\sum_{t=2}^{T}\absolutevalue{y_{t}-y_{t-1}}}.$

Firstly appeared in armstrong1985  SMAPE is also an accuracy metric used in
time series. Contrary to the MASE, the SMAPE is a percentage based metric
formulated as:

$SMAPE=\frac{1}{n}\sum_{i=1}^{n}\frac{\absolutevalue{y_{i}-\hat{y}_{i}}}{\frac{\absolutevalue{y_{i}}+\absolutevalue{\hat{y}_{i}}}{2}}$

Both SMAPE and MASE are used extensively in time series, and this is the
reason behind their inclusion (makridakis2020, ; shankar2020, ).

###  4.3 Approach results

To test the performances of our approach, we treated both the number of splits
and the overlapping ratio as hyperparameters. A glimpse of the results is
presented in Table 1.

Table 1: Approach performances based on different parametrization of split
size and overlapping ratio.

Split | Overlap | RMSE | MAE | MASE | SMAPE
---|---|---|---|---|---
10 | 1.0 | 1588.22 | 1256.06 | 2.66 | 0.10
200 | 1.0 | 2979.64 | 2474.38 | 5.25 | 0.18
150 | 1.0 | 3352.54 | 2640.00 | 5.60 | 0.19
200 | 0.0 | 4083.87 | 3398.31 | 7.21 | 0.23
10 | 0.5 | 4598.62 | 3548.89 | 7.53 | 0.24
150 | 0.0 | 4545.16 | 3710.49 | 7.87 | 0.25
200 | 0.5 | 4568.74 | 3747.89 | 7.95 | 0.25
150 | 0.5 | 5105.29 | 3962.41 | 8.40 | 0.26
10 | 0.0 | 9211.98 | 8755.59 | 18.57 | 0.49

Figure 2 shows the different performances, measured with the SMAPE metric, of
our approach and the sensitivity to hyperparameters change. In particular, a
low number of splits in combination with no overlaps results in a worse model
than the baseline (dashed red line). On the contrary, an increase in splits
and overlapping results in an ensemble model on par with the benchmark. It is
worth noting that although the performance is similar between the two
approaches in this setting, the advantage of our approach is that it allows
for training in different machines and does not force the data to reside on
the same device that is doing the model estimation. Last, the more relevant
result is that overlapping affects model performance positively. The result is
far better than the benchmark, with a SMAPE of less than $0.1$ in the case of
ten splits. More specifically, overlapping seems to offset the number of
splits. The potential of overlapping was already signaled by the literature
(scott1974analysis, ).

Figure 2: Symmetric Mean Absolute Percentage Error on the test set under
different split size and overlapping ratios.

This difference in performance is straightforward if we look at Figure 3. In
contrast to the model trained on the whole dataset, the combined forecast
captures better the decreasing trend of the time series. Moreover, the
forecast is less volatile than the benchmark.

Figure 3: Test set forecasts with respect to the true electricity demand (red
line). The green line depicts the forecasts based on the model trained on the
full dataset. The blue line depicts the forecasts based on the model trained
with our approach with split size 10 and full overlapping.

To investigate better the inner workings of our approach is also worth looking
at the weights attributed by our multicriteria decision problem. These weights
are in Figure 4 and are attributed to the model trained on a particular data
split. Therefore, for example, the model trained on the first split, the most
recent one, has zero weights and does not contribute to the final forecast. On
the contrary, the models trained on the fourth and sixth split are the only
ones with non-zero weights. This means that these models are the ones that
score best in comparison with other models trained on different splits.

Figure 4: Weights partitioning of the ensemble model based on split size 10
and complete overlapping.

These dynamics are particularly highlighted in Figure 5. This figure
represents the SMAPE of each model applied to a different split. The model
that performs worst is the tenth model, and we can see that by looking at the
last column, which is the one with the darkest cells. Another relevant
information is that every model performs poorly on both the first split and
the last one. What, instead, is clear is that both M4 and M6 perform better in
almost all the splits.

Figure 5: Symmetric Mean Absolute Percentage Error on all the training data
splits based on the model.

##  5 Conclusion

The presence of adversarial training, biased datasets, and conflicting trends
can generate problems during the machine learning process. This appears to be
very crucial when thinking that splitting a dataset into training, test, and
hold-out subsets is, most of the time, arbitrary and only led by the need to
improve the algorithm performance and accuracy. On the top of this, dealing
with huge amount of information can lead to long execution time of the
gradient descent algorithm. In order to get efficient and prompt decisions it
looks like of paramount importance to be able to split the original dataset
into smaller chunks, training the same or different models on each of them
separately, and finally recombine all of them in a unique framework. The
advantages of this approach are twofold: from one side it allows to combine
different models that are trained on different datasets without exchange of
information during the gradient descent approach. This can be run on parallel
architectures. From another the proposed GP formulation allows to recombine
these models in a unique and efficient framework. Our numerical results
confirm the goodness of this approach in the case of time-series analysis.
Future avenues include the extensions of this framework by including different
MCDM and GP approaches.

## References

  *   * (1) LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. nature 521(7553), 436–444 (2015)
  * (2) Bengio, Y., Courville, A., Vincent, P.: Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence 35(8), 1798–1828 (2013)
  * (3) He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778 (2016)
  * (4) Van Essen, B., Kim, H., Pearce, R., Boakye, K., Chen, B.: Lbann: Livermore big artificial neural network hpc toolkit. In: Proceedings of the Workshop on Machine Learning in High-performance Computing Environments, pp. 1–6 (2015)
  * (5) Ahmed, A.S., Abood, M.S., Hamdi, M.M.: Advancement Of Deep Learning In Big Data And Distributed Systems. In: 2021 3rd International Congress on Human-Computer Interaction, Optimization and Robotic Applications (HORA), pp. 1–7 (2021). https://doi.org/10.1109/HORA52670.2021.9461274
  * (6) Konečný, J., McMahan, H.B., Yu, F.X., Richtárik, P., Suresh, A.T., Bacon, D.: Federated Learning: Strategies for Improving Communication Efficiency (2017). http://arxiv.org/abs/1610.05492 Accessed 2021-11-22
  * (7) Bonawitz, K., Eichner, H., Grieskamp, W., Huba, D., Ingerman, A., Ivanov, V., Kiddon, C., Konečný, J., Mazzocchi, S., McMahan, H.B., Van Overveldt, T., Petrou, D., Ramage, D., Roselander, J.: Towards Federated Learning at Scale: System Design (2019). http://arxiv.org/abs/1902.01046 Accessed 2021-11-27
  * (8) Jiménez-Sánchez, A., Tardy, M., Ballester, M.A.G., Mateus, D., Piella, G.: Memory-aware curriculum federated learning for breast cancer classification. arXiv:2107.02504 [cs] (2021) arXiv:2107.02504 [cs]
  * (9) Beguier, C., du Terrail, J.O., Meah, I., Andreux, M., Tramel, E.W.: Differentially Private Federated Learning for Cancer Prediction. arXiv:2101.02997 [cs, stat] (2021) arXiv:2101.02997 [cs, stat]
  * (10) Zhu, L., Han, S.: Deep Leakage from Gradients. In: Yang, Q., Fan, L., Yu, H. (eds.) Federated Learning: Privacy and Incentive. Lecture Notes in Computer Science, pp. 17–31. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-63076-8_2
  * (11) Kholod, I., Yanaki, E., Fomichev, D., Shalugin, E., Novikova, E., Filippov, E., Nordlund, M.: Open-Source Federated Learning Frameworks for IoT: A Comparative Review and Analysis. Sensors 21(1), 167 (2021). https://doi.org/10.3390/s21010167
  * (12) Lim, J.Q., Chan, C.S.: From Gradient Leakage To Adversarial Attacks In Federated Learning. In: 2021 IEEE International Conference on Image Processing (ICIP), pp. 3602–3606 (2021). https://doi.org/10.1109/ICIP42928.2021.9506589
  * (13) Bagdasaryan, E., Veit, A., Hua, Y., Estrin, D., Shmatikov, V.: How To Backdoor Federated Learning. In: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pp. 2938–2948 (2020). https://proceedings.mlr.press/v108/bagdasaryan20a.html
  * (14) Angelopoulos, D., Siskos, Y., Psarras, J.: Disaggregating time series on multiple criteria for robust forecasting: The case of long-term electricity demand in greece. European Journal of Operational Research 275(1), 252–265 (2019)
  * (15) Stoilova, S., Munier, N.: A novel fuzzy simus multicriteria decision-making method. an application in railway passenger transport planning. Symmetry 13(3), 483 (2021)
  * (16) Yager, R.R.: On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Transactions on Systems, Man, and Cybernetics 18(1), 183–190 (1988). https://doi.org/10.1109/21.87068
  * (17) Warnat-Herresthal, S., Schultze, H., Shastry, K.L., Manamohan, S., Mukherjee, S., Garg, V., Sarveswara, R., Händler, K., Pickkers, P., Aziz, N.A., Ktena, S., Tran, F., Bitzer, M., Ossowski, S., Casadei, N., Herr, C., Petersheim, D., Behrends, U., Kern, F., Fehlmann, T., Schommers, P., Lehmann, C., Augustin, M., Rybniker, J., Altmüller, J., Mishra, N., Bernardes, J.P., Krämer, B., Bonaguro, L., Schulte-Schrepping, J., De Domenico, E., Siever, C., Kraut, M., Desai, M., Monnet, B., Saridaki, M., Siegel, C.M., Drews, A., Nuesch-Germano, M., Theis, H., Heyckendorf, J., Schreiber, S., Kim-Hellmuth, S., Nattermann, J., Skowasch, D., Kurth, I., Keller, A., Bals, R., Nürnberg, P., Rieß, O., Rosenstiel, P., Netea, M.G., Theis, F., Mukherjee, S., Backes, M., Aschenbrenner, A.C., Ulas, T., Breteler, M.M.B., Giamarellos-Bourboulis, E.J., Kox, M., Becker, M., Cheran, S., Woodacre, M.S., Goh, E.L., Schultze, J.L.: Swarm Learning for decentralized and confidential clinical machine learning. Nature 594(7862), 265–270 (2021). https://doi.org/10.1038/s41586-021-03583-3
  * (18) McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication-Efficient Learning of Deep Networks from Decentralized Data. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273–1282 (2017). PMLR
  * (19) Ehrgott, M., Gandibleux, X., Hillier, F.S. (eds.): Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. International Series in Operations Research & Management Science, vol. 52. Springer US, Boston, MA (2002). https://doi.org/10.1007/b101915
  * (20) Colapinto, C., Jayaraman, R., Marsiglio, S.: Multi-criteria decision analysis with goal programming in engineering, management and social sciences: A state-of-the art review. Annals of Operations Research 251(1-2), 7–40 (2017)
  * (21) Charnes, A., Cooper, W.W., Ferguson, R.O.: Optimal estimation of executive compensation by linear programming. Management science 1(2), 138–151 (1955)
  * (22) Flavell, R.: A new goal programming formulation. Omega 4(6), 731–732 (1976). https://doi.org/10.1016/0305-0483(76)90099-2
  * (23) Hong, T., Xie, J., Black, J.: Global energy forecasting competition 2017: Hierarchical probabilistic load forecasting. International Journal of Forecasting 35(4), 1389–1399 (2019). https://doi.org/10.1016/j.ijforecast.2019.02.006
  * (24) Wang, X., Kang, Y., Hyndman, R.J., Li, F.: Distributed ARIMA Models for Ultra-Long Time Series (2020). http://arxiv.org/abs/2007.09577 Accessed 2021-09-16
  * (25) Arifovic, J., Gencay, R.: Using genetic algorithms to select architecture of a feedforward artiÿcial neural network. Physica A, 21 (2001)
  * (26) Hyndman, R.J., Koehler, A.B.: Another look at measures of forecast accuracy. International Journal of Forecasting 22(4), 679–688 (2006). https://doi.org/10.1016/j.ijforecast.2006.03.001
  * (27) Armstrong, J.S.: Long-Range Forecasting: From Crystal Ball to Computer, 2\. ed edn. Wiley, ??? (1985)
  * (28) Makridakis, S., Spiliotis, E., Assimakopoulos, V.: The M4 Competition: 100,000 time series and 61 forecasting methods. International Journal of Forecasting 36(1), 54–74 (2020). https://doi.org/10.1016/j.ijforecast.2019.04.014
  * (29) Shankar, S., Ilavarasan, P.V., Punia, S., Singh, S.P.: Forecasting container throughput with long short-term memory networks. Industrial Management & Data Systems 120(3), 425–441 (2020). https://doi.org/10.1108/IMDS-07-2019-0370
  * (30) Scott, A., Smith, T.: Analysis of repeated surveys using time series methods. Journal of the American Statistical Association 69(347), 674–678 (1974)