# Difference Methods for Double Change Covering Designs

Amanda Lynn Chafee111Supported by MITACS research training award., Brett
Stevens222Supported by the Natural Sciences and Engineering Research Council
of Canada (funding reference number RGPIN 06392).
School of Mathematics and Statistics
Carleton University
1125 Colonel By Drive
Ottawa, ON, K1S 5B6
Canada
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(September 2022; May 2021)

###### Abstract

A double change covering design is a $v$-set $X$ and an ordered list
$\mathcal{L}$ of $b$ blocks of size $k$ where every $t$-set must occur in at
least one block. Each pair of consecutive blocks differs by exactly two
elements. A double change covering design is circular when the first and last
blocks also differ by two elements. We give a recursive construction that uses
1-factorizations and expansion sets to increase $v$ by $\frac{v+k-2}{k-2}$. We
construct CDCCD($2k-2,k,k-1$) and CDCCD($2k-1,k,k-2$) from single change
covering designs. We use difference methods to construct five infinite
families for any $k\geq 3$, minimum CDCCD($c(4k-6)+1,k,c^{2}(4k-6)+c$) when
$c\leq 5$ and CDCCD(61,4,366). Finally, from these, we use the recursion to
construct twelve additional minimum DCCD.

Key Words: Design theory, double change covering designs, difference families,
1-factorizations, ordering of designs

##  1 Introduction

A linear single change covering design (SCCD($v,k,t,b$)) $(V,\mathcal{L})$ is
a $v$-set $V$ and an ordered list of blocks
$\mathcal{L}=(B_{1},B_{2},...,B_{b})$ of size $k$ where every $t$-set, $T$,
must occur in at least one block. Additionally each pair of consecutive blocks
differs by exactly one element. A circular singe change covering design
(CSCCD($v,k,t,b$)) is a SCCD where the first and last blocks also differ by
one element. If no DCCD($v,k,t,b^{\prime})$ exists for all $b^{\prime}<b$ then
a DCCD($v,k,t,b$) is called minimal

The earliest discussion of SCCDs was in 1968 and focused on applications to
efficient computing [8]. The calculation of $AA^{T}$ for some matrix requires
processing all pairs of rows. In 1968 a limited number of rows could be stored
in core memory at one time and updating RAM from a tape was slow. Therefore,
visiting all pairs with the smallest number of accesses to the tape improves
running time significantly. Similar constraints apply today with respect to
CPU cache v.s. RAM access [3, 6].

Gower, Preece, Constable, Zhang, Yucas, Wallis, McSorley and Phillips
substantially developed the theory in the 1990s. For a summarized history
please see [2] and [10]. Today we know constructions for all minimum designs
of block size 2,3 and 4 as well as four classes modulo sixteen for block size
5. We also have difference constructions for circular SCCD for families with
arbitrary $k$ [2].

This previous research only considered changing a single element. This prompts
the question,“Could we instead change other fixed numbers of elements between
blocks”. We call such a design an $m$-change covering design. When $m=2$,
these are called double change covering designs (DCCD). These designs would
prove useful in component testing for balancing costs of both testing a
configuration and changing the components between tests. Given enough known
$m$-change designs, one may choose the most cost efficient testing method.

Preece et al. introduce the concept of linear double change covering designs
and produce an example of a DCCD(9,3,2,12). Nirosh Gangoda Gamachchige and
John McSorley begin a formal exploration of double change covering designs in
Gangoda Gamachchige’s M.Sc and Ph.D. these [4, 5]. In the M.Sc, Gangoda
Gamachchige gives a construction for tight CDCCD($v,3,2,b$) developed using
Bose and Skolem sequences on STS. He also gives constructions for
CDCCD($v,3,2,b$) when $v\equiv 0,2,4,5\pmod{6}$. During his Ph.D. he examines
the regularity of elements in a DCCD. He finds that for a fixed $k$, linear
DCCD($3k-5,k,2,2k-4)$ are minimal and if $2k-3=p^{n}$ for some prime $p\neq
2$, and $n\geq 1$ then $v-3k-5$ is the smallest $v$ where a linear
DCCD($v,k,2,b)$ is minimal. He shows fixed elements do not exist in economical
linear DCCD($v,k,2,b)$ for $v\geq 3k-6$. He shows that a minimal
CDCCD($v,k,2,b$) has a fixed element if and only if $v=2k-3$. He shows all
DCCD($v,2,2,b$) are minimal when $v\geq 6$ He shows there are no fixed
elements in minimal DCCD($v,4,2,b$) for $v\geq 6$. He constructs a minimal
DCCD($v,4,2,b$) for $v=6,...,14$. He gives some alternative constructions that
take minimal CDCCD($v,4,2,b)$ to minimal CDCCD($v^{\prime},4,2,b^{\prime})$
and ends by giving some general constructions for CDCCD($v,4,2,b$) that are
not necessarily minimal.

In this paper we further explore linear and circular double change covering
designs and discuss their constructions using expansion sets and
1-factorizations of complete graphs and difference families.

##  2 Background

We will be using some graph theory in this work. A perfect matching or
1-factor of a graph $G$ is a subset of edges $M$ such that every vertex $v\in
V$ is adjacent to exactly one edge $e\in M$. A partition of the edges of a
graph into perfect matchings is a 1-factorization. Each color in Figure 1 is a
1-factor in a 1-factorization of $K_{6}$. A 1-factorization of $K_{n}$ exists
for all even $n$[1].

abcdef Figure 1: 1-factorization of $K_{6}$

Let $(G,+,0)$ be a finite group of order $v$. For $D\subseteq G$ let $\partial
D=\\{d_{1}-d_{2}:d_{1}\neq d_{2}\in D\\}$. A ($v,k,\lambda$)-difference family
is a collection $\\{D_{1},...,D_{c}\\}$ of $k$-subsets of $G$, $|G|=v$, where
$\partial D_{1}\cup...\cup\partial D_{c}=\lambda G\backslash\\{0\\}$. A
difference family with $c=1$ is a $(v,k,\lambda)-$difference set.

######  Example 1.

$D=\\{1,3,4\\}$ is a (7,3,1)-difference set in $\mathbb{Z}_{7}$.

$D=\big{\\{}\\{0,1,4\\},\\{0,2,8\\}\big{\\}}$ is a (13,3,1)-difference family
over $\mathbb{Z}_{13}$.

##  3 Double Change Covering Designs

A double change covering design (DCCD($v,k,t,b$)) $(V,\mathcal{L})$ is a
$v$-set $V$ and an ordered list of blocks
$\mathcal{L}=(B_{1},B_{2},...,B_{b})$ of size $k$ where every $t$-set must
occur in at least one block. Each pair of consecutive blocks differs by
exactly two elements. A DCCD is circular if the first and last blocks also
differ by two elements. The double change property requires that $v\geq k+2$
if $b>1$. An element $x\in V$ is introduced in a block if $x\in B_{i}$ and
$x\not\in B_{i-1}$. As no block precedes $B_{1}$ in a linear DCCD every
element is introduced here. A $t$-set is covered in $B_{i}$ if at least one
element in the $t$-set was introduced in $B_{i}$.

SCCD and DCCD can optimize costs in component testing [11]. For example,
consider testing a device where running a test will cost $10 and swapping
components between tests costs $1. Using the covering design with 7 blocks,
(1,2,3), (1,4,7), (1,5,6), (3,5,7), (3,4,6), (2,4,5), (2,6,7) would cost $91
to run, a SCCD(7,3,2,10) would cost $112, and a DCCD(7,3,2,7) would cost $85.
If instead, it costs $1 to run a test and $5 to switch components these tests
cost $112, $67, and $77 respectively. [11]

######  Theorem 2.

There are at least
$g_{1}(v,k,t)=\left\lceil\frac{\binom{v}{t}-\binom{k}{t}}{2\binom{k-2}{t-1}+\binom{k-2}{t-2}}\right\rceil+1$
blocks in a linear DCCD and
$g_{2}(v,k,t)=\left\lceil\frac{\binom{v}{t}}{2\binom{k-2}{t-1}+\binom{k-2}{t-2}}\right\rceil$
blocks in a CDCCD.

###### Proof.

The first block of a linear DCCD will cover $\binom{k}{t}$ $t$-sets. Every
other block will have two elements introduced. The number of $t$-sets that
contain $i$ of the two introduced elements and $t-i$ of the remaining $k-2$
points is $\binom{2}{i}\binom{k-2}{t-i}$. Hence
$\sum\limits_{i=1}^{t}\binom{2}{i}\binom{k-2}{t-i}$ $t$-sets are introduced in
each block after the first. There are $\binom{v}{t}$ $t$-sets to cover, so
$\binom{v}{t}\leq\binom{k}{t}+(b-1)\bigg{(}\sum\limits_{i=1}^{s}\binom{2}{i}\binom{k-2}{t-i}\bigg{)}$.
In the circular case, each block covers at most
$\sum\limits_{i=1}^{t}\binom{2}{i}\binom{k-2}{t-i}$ and the calculation is
similar. ∎

We will be focusing on strength $t=2$ designs for this paper so will drop the
parameter $t$ and write DCCD($v,k,b$). If no DCCD($v,k,b^{\prime})$ exists for
all $b^{\prime}<b$ then a DCCD($v,k,b$) is called minimal. A (circular)
DCCD($v,k,b$) is economical if it has $\left\lceil
g^{\prime}_{1}(v,k,2)\right\rceil$ $\big{(}\left\lceil
g^{\prime}_{2}(v,k,2)\right\rceil\big{)}$ blocks and tight if it is economical
and $g_{1}(v,k,2)$ $\big{(}g_{2}(v,k,2)\big{)}$ is an integer. Any economical
DCCD is minimum. In a tight DCCD every pair is covered exactly once. For some
$v,k$ combinations tight DCCD can not exist because $g_{1}$ or $g_{2}$ do not
have integer values, but economical designs can exist. An example of a
CDCCD(7,3,7) is given in Table 1. The blocks are those of $STS(7)$. It is
tight as either a DCCD or CDCCD.

The elements $U_{i}=x\in B_{i}\cap B_{i+1}$ form the $i_{th}$ unchanged
subset. Since no block proceeds $B_{1}$ or follows $B_{b}$ in linear DCCD we
may consider any $k-2$ subset to be the unchanged subset $U_{0}$ and $U_{b}$
respectively. However, circular DCCD must maintain the double change between
the first and last block, so $U_{0}=U_{b}=B_{1}\cap B_{b}$ so we loose any
free choice we had. For example the linear DCCD(7,3,7) has the unchanged
subsets
$U_{1}=\\{0\\},U_{2}=\\{4\\},U_{3}=\\{3\\},U_{4}=\\{6\\},U_{5}=\\{6\\},U_{6}=\\{5\\}$
where $U_{0}$ can be any of $\\{0\\},\\{1\\},$ of $\\{2\\}$ and $U_{7}$ can be
any of $\\{1\\},\\{3\\},$ or $\\{5\\}$. The CDCCD(7,3,7) has the same
$U_{1},...,U_{6}$ however, $U_{0}=U_{7}=\\{1\\}$. If we can partition $V$ into
a collection of unchanged subsets, we say the design has an expansion set. In
Table 1, only the linear DCCD(7,3,7) has an expansion set indicated by
carrots, $\land$.

B1 | B2 | B3 | B4 | B5 | B6 | B7
---|---|---|---|---|---|---
0∗ | 0 | 2∗ | 0∗ | 1∗ | 5∗ | 5
1 | 4∗ | 4 | 6∗ | 6 | 6 | 3∗
∧2∗∧ | 5∗∧ | 3∗∧ | 3 | 4∗∧ | 2∗∧ | 1∗∧
Table 1: A tight CDCCD(7,3,7)

###  3.1 Expansion Set Recursion

Preece et al. use expansion sets to construct a SCCD($v+1,k,b$) from a
SCCD($v,k,b$) [9]. This has been extended to CSCCD[7]. We can do something
similar with double change covering designs by utilizing 1-factorizations of a
complete graph.

######  Theorem 3.

Let $(V,\mathcal{B})$ be a DCCD($v,k,b$) with $v$ an odd multiple of $k-2$ and
expansion set. Then a DCCD($v^{*},k,b^{*}$), ($V^{*},\mathcal{B}^{*}$) exists
for $v^{*}=v+\frac{v}{k-2}+1$ and $b^{*}=b+\frac{v}{k-2}\frac{v+k-2}{2k-4}$.
Moreover, if ($V,\mathcal{B}$) is tight, economic or circular then
($V^{*},\mathcal{B}^{*}$) is too.

###### Proof.

Let ($V,\mathcal{B})$ be a DCCD($v,k,b$) with the expansion set
$\mathcal{E}=\\{U_{i_{j}}:1\leq j\leq l=\frac{v}{k-2}\\}$. Let
$\\{F_{j}\\}_{1}^{l}$ be a 1-factorization of $K_{l+1}$ on set $X$ disjoint
from $V$ [1].

For each edge $e\in F_{j}$ let $B_{j,e}=U_{i_{j}}\cup e$ for each $j$. Insert
all the $B_{j,e}$ in any order at each expansion location
${i_{j}}\in\mathcal{E}$. These insertions maintain the double change property.
All the pairs that were covered in $(V,\mathcal{B})$ are still covered in
$\mathcal{B}$. Since each pair of elements from $X$ is in exactly one 1-factor
all the pairs in $X$ are covered. The blocks inserted at expansion set
locations ensure each pair of elements $\\{x,y\\}$, $x\in X$, $y\in V$ is
covered. So $(V^{*},\mathcal{B}^{*})$ is a DCCD($v^{*},k,b^{*}$) with
$v^{*}v+\frac{v}{k-2}+1$ and $b^{*}=b+\frac{v(v+k-2)}{2(k-2)^{2}}$.

Each $B_{j,e}$ only covers new pairs and does not effect introductions in
preexisting blocks, so if ($V,\mathcal{B}$) was tight or economical so is
$(V^{*},\mathcal{B}^{*})$. The block insertions do not affect the double
change between the first and last block, so if $(V,\mathcal{B})$ was circular
so is ($V^{*},\mathcal{B}^{*}$). ∎

For example consider the linear DCCD(7,3,7) and expansion set in Table 1. We
may insert four new blocks at each expansion set location that consist of the
unchanged subset and the vertices of an edge in a 1-factor of $K_{8}$ in
Figure 2 to construct a DCCD(13,3,35) as seen in Table 2.

1589101112131415891011121314 Figure 2: K8 B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8 | B9 | B10 | B11 | B12 | B13 | B14 | B15 | B16 | B17 | B18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
8 | 10 | 11 | 12 | 0∗ | 0 | 0 | 0 | 0 | 0 | 8 | 9 | 12 | 13 | 2∗ | 8 | 9 | 10
9 | 14 | 13 | 15 | 1∗ | 8 | 11 | 12 | 9 | 4∗ | 4 | 4 | 4 | 4 | 4 | 15 | 14 | 13
2 | 2 | 2 | 2 | 2 | 10 | 14 | 13 | 15 | 5∗ | 11 | 10 | 14 | 15 | 3∗ | 3 | 3 | 3
B19 | B20 | B21 | B22 | B23 | B24 | B25 | B26 | B27 | B28 | B29 | B30 | B31 | B32 | B33 | B34 | B35 |
11 | 0∗ | 1∗ | 8 | 13 | 9 | 10 | 5∗ | 5 | 5 | 5 | 5 | 5 | 8 | 9 | 10 | 11 |
12 | 6∗ | 6 | 6 | 6 | 6 | 6 | 6 | 8 | 9 | 10 | 14 | 3∗ | 14 | 13 | 12 | 15 |
3 | 3 | 4∗ | 12 | 14 | 11 | 15 | 2∗ | 13 | 12 | 11 | 15 | 1∗ | 1 | 1 | 1 | 1 |
Table 2: A DCCD(15,3,35) built from the DCCD(7,3,2) and $K_{8}$

We note that every new element $x\in X\backslash V$ in Theorem 3 is always
removed one block after it is introduced. Consequently, $x$ is never in an
unchanged subset so $\mathcal{B}^{*}$ never has an expansion set.

###  3.2 Difference Methodology

We can construct CDCCD($v,k,b$) using a construction similar to difference
sets and families. McSorley proved that $\\{0,1,...,k-1\\}$ is a base block of
a CSCCD$(2k-1,k,2k-1)$ over $\mathbb{Z}_{2k-1}$ in [7]. This theorem is not
stated in terms of difference methods but is equivalent to a difference method
construction. In [2] we use difference methods to construct tight
CSCCD$(2c(k-1)+1,k,c^{2}(2k-2)+c+1)$ for all $c\geq 1,k\geq 2$. Here we extend
these methods to CDCCD.

Every element in the tight CSCCD$(2k^{\prime}-1,k^{\prime},2k^{\prime}-1)$ is
introduced exactly once. If we replace $x\in\mathbb{Z}_{2k^{\prime}-1}$ in
each block with $2x$ and $2x+1$ in $\mathbb{Z}_{4k^{\prime}-2}$ to produce a
list of $2k^{\prime}-1$ blocks $B_{i}$ of size $k=2k^{\prime}$ from
$\mathbb{Z}_{2k-2}$ the design is double change. The pairs $\\{2x,2x+1\\}$ are
covered when introduced other pairs $\\{y,z\\}\subset\mathbb{Z}_{2k-2}$ are
covered in the block where
$\\{\lfloor\frac{y}{2}\rfloor,\lfloor\frac{z}{2}\rfloor\\}$ are covered in the
CSCCD. Thus,

######  Theorem 4.

A tight CDCCD$(2k-2,k,k-1)$ exists for all $k\geq 2$ if and only if $k$ is
even.

###### Proof.

Suppose that $k$ is odd, then
$g_{2}(2k-1,k,2)=\left\lceil\frac{\binom{2k-2}{2}}{2\binom{k-2}{1}+\binom{k-2}{0}}\right\rceil=k-1$.
The discussion before this Theorem constructs these for $k$ even. We know show
that $k$ odd cannot exist. Suppose there exists a point, $x$, in every block.
There are $2(k-1)=v$ introductions so at least one point $y$ is introduced at
least twice, so the pair $x,y$ is covered more then once, a contradiction to
tightness. So no point may be in every block. However, there are not enough
introductions for any point to be introduced more then once, so each point is
introduced exactly once.

When a point is introduced it covers $k-1$ pairs and each time it persists it
covers $2$ more pairs. Thus each point is in $r$ blocks where $k-1+(r-1)2\geq
v-1$ so we find $r\geq\frac{k-2}{2}$. Now when $r$ is odd,
$r\geq\left\lceil\frac{k-2}{2}\right\rceil$ which forces repeated pairs, a
contradiction. Thus tight CSCCD(2k-2,k,k-1) do not exist when $k$ is odd. ∎

For example the tight CDCCD(6,4,3) in Table 3 is constructed from the tight
CSCCD(3,2,3) to its left.

B’1 | B’2 | B’3 |  |  |  |  | B1 | B2 | B3
---|---|---|---|---|---|---|---|---|---
0 | 2∗ | 2 |  |  |  |  | 0 | 4∗ | 4
1∗ | 1 | 0∗ |  |  |  |  | 1 | 5∗ | 5
|  |  |  |  |  |  | 2∗ | 2 | 0∗
|  |  |  |  |  |  | 3${}^{*}_{\land}$ | 3∧ | 1${}^{*}_{\land}$
Table 3: A tight CSCCD(3,2,3) and tight CSCCD(6,4,3)

######  Proposition 5.

A CDCCD($2k-2,k,k-1)$ has an expansion set if and only if $k=4$.

###### Proof.

We have $v=2k-2=2(k-2)+2$, so $(k-2)|v$ if and only if $k=3,4$. When $k=3$ the
DCCD cannot exist as $k$ is odd. When $k=4$ the CDCCD(6,4,3) has an expansion
set as shown in Table 3. ∎

Using this in conjunction with the 1-factorization of $K_{4}$ on points
$\\{a,b,c,d\\}$ and Theorem 3 we build the CDCCD(10,4,9) seen in Table 4.

0 | a∗ | c∗ | 4∗ | 4 | 4 | 4 | a∗ | b∗
---|---|---|---|---|---|---|---|---
1 | b∗ | d∗ | 5∗ | 5 | 5 | 5 | d∗ | c∗
2∗ | 2 | 2 | 2 | a∗ | b∗ | 0∗ | 0 | 0
3∗ | 3 | 3 | 3 | c∗ | d∗ | 1∗ | 1 | 1
Table 4: A tight CDCCD(10,4,9)

Adding a single new point to every block in the DCCD constructed in Theorem 4
yields

######  Theorem 6.

A tight CDCCD$(2k-3,k,k-2)$ exists for all odd $k\geq 3$.

Beyond manipulating the CSCCD by doubling elements, we can directly construct
difference sets for CDCCD. Example 7 will help us gain some intuition for
doing this.

######  Example 7.

Consider a CDCCD(11,4,11). In Figure 3 we show a base block $\\{0,1,2,5\\}$
and its successor after incrementing by $1$. The vertices only in the first
block are highlighted in blue, the vertices only on the second block are
highlighted in pink, and the vertices in the unchanged subset in black. We
place a line between each introduced element and the other elements in the
block, blue for the first block and pink for the second; these are the covered
pairs and every difference in $\mathbb{Z}_{11}$ appears. Each subsequent block
is obtained by rotating the previous block by one. After developing the blocks
fully in $\mathbb{Z}_{11}$ all pairs will be covered. We also see pictorially
that there will be double changes between consecutive blocks. Table 5 shows
the table form the CDCCD(11,4,11).

0123456789100125051236 Figure 3: Difference construction for DCCD(11,4,11)

B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8 | B9 | B10 | B11
---|---|---|---|---|---|---|---|---|---|---
0 | 3∗ | 3 | 3 | 6∗ | 6 | 6 | 9∗ | 9 | 9 | 1∗
1 | 1 | 4∗ | 4 | 4 | 7∗ | 7 | 7 | 10∗ | 10 | 10
2∗ | 2 | 2 | 5∗ | 5 | 5 | 8∗ | 8 | 8 | 0∗ | 0
5∗ | 6∗ | 7∗ | 8∗ | 9∗ | 10∗ | 0∗ | 1∗ | 2∗ | 3∗ | 4∗
Table 5: A CDCCD(11,4,11)

We can construct difference families with up to $5$ base blocks for all $k$.

######  Theorem 8 (CDCCD difference families with $c$ initial blocks).

A tight CDCCD$(c(4k-6)+1,k,c^{2}(4k-6)+c)$ exists for all $k\geq 3$ when
$c\leq 5$

###### Proof.

To build each of the tight CDCCD$(c(4k-6)+1,k,c^{2}(4k-6)+c)$, let
$A=\\{0,1,...,(k-3)\\}$ and consider the initial blocks labeled
$B_{0,1},...,B_{0,c}$ in order, given in Table 6.

$c$ | Initial Blocks
---|---
1 | $A\cup\\{(k-2),2(k-2)+1\\}$
2 | $A\cup\\{2(k-2),5(k-2)+2\\},A\cup\\{(k-2),3(k-2)+1\\}$
3 | $A\cup\\{2(k-2),7(k-2)+3\\},A\cup\\{3(k-2)+1,5(k-2)+2\\},$
| $A\cup\\{(k-2),4(k-2)+2\\}$
4 | $A\cup\\{2(k-2),8(k-2)+4\\},A\cup\\{3(k-2)+1,5(k-2)+2\\},$
| $A\cup\\{4(k-2)+2,7(k-2)+4\\},A\cup\\{(k-2),6(k-2)+3\\}$
5 | $A\cup\\{2(k-2),6(k-2)+3\\},A\cup\\{3(k-2),9(k-2)+4\\},$
| $A\cup\\{4(k-2)+2,7(k-2)+4\\},A\cup\\{5(k-2)+3,8(k-2)+4\\},$
| $A\cup\\{(k-2),10(k-2)+5\\}$
Table 6: Families of base blocks for CDCCD

Each block contains $A$ in addition to two distinct elements. Additionally,
$B_{0,c}$ contains $A\cup\\{(k-2)\\}$, which contains $A$ incremented by 1,
thus $(B_{0,1},B_{0,2},...,B_{0,c},B_{1,1},...,B_{1,c},...,B_{v,c})$ is double
change.

Each $B_{0,i}=\\{0,1,...,k-3,x,y\\}$ covers differences
$\pm\\{y-x,x-k+3,...,x,y-k+3,...,y\\}$, which will cover all the differences
$\mathbb{Z}_{v}$. Developing in $\mathbb{Z}_{v}$ covers all pairs. ∎

Example 7 is an example of Theorem 8 when $c=1$ and $k=4$. Let us examine what
happens when $c=2$.

######  Example 9.

When $k=4$ and $c=2$ we construct the tight CDCCD(21,4,42) in Table 7. In this
Table we highlight every $x\in X$ such that the pair $(0,x)$ is covered.

B0,1 | B0,2 | B1,1 | B1,2 | B2,1 | B2,2 | B3,1 | B3,2 | B4,1 | B4,2 | B5,1 | B5,2 | B6,1 | B6,2
---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 | 0 |  5∗ |  3∗ | 3 | 3 | 3 | 3 |  8∗ |  6∗ | 6 | 6 | 6 | 6
1 | 1 | 1 | 1 |  6∗ |  4∗ | 4 | 4 | 4 | 4 |  9∗ |  7∗ | 7 | 7
4∗ | 2∗ | 2 | 2 | 2 | 2 |  7∗ |  5∗ | 5 | 5 | 5 | 5 |  10∗ |  8∗
12∗ | 7∗ |  13∗ |  8∗ |  14∗ |  9∗ |  15∗ |  10∗ |  16∗ |  11∗ |  17∗ |  12∗ |  18∗ |  13∗
B7,1 | B7,2 | B8,1 | B8,2 | B9,1 | B9,2 | B10,1 | B10,2 | B11,1 | B11,2 | B12,1 | B12,2 | B13,1 | B13,2
11∗ |  9∗ | 9 | 9 | 9 | 9 |  14∗ |  12∗ | 12 | 12 | 12 | 12 |  17∗ |  15∗
7 | 7 |  12∗ |  10∗ | 10 | 10 | 10 | 10 |  15∗ |  13∗ | 13 | 13 | 13 | 13
8 | 8 | 8 | 8 | 13∗ |  11∗ | 11 | 11 | 11 | 11 |  16∗ |  14∗ | 14 | 14
19∗ |  14∗ |  20∗ |  15∗ |  0∗ |  16∗ |  1∗ |  17∗ |  2∗ |  18∗ |  3∗ |  19∗ |  4∗ |  20∗
B14,1 | B14,2 | B15,1 | B15,2 | B16,1 | B16,2 | B17,1 | B17,2 | B18,1 | B18,2 | B19,1 | B19,2 | B20,1 | B20,2
15 | 15 | 15 | 15 |  20∗ |  18∗ | 18 | 18 | 18 | 18 |  2∗ |  0∗ | 0 | 0
18∗ | 16∗ | 16 | 16 | 16 | 16 |  0∗ |  19∗ | 19 | 19 | 19 | 19 | 3∗ | 1∗
14 | 14 |  19∗ |  17∗ | 17 | 17 | 17 | 17 |  1∗ |  20∗ | 20 | 20 | 20 | 20
5∗ |  0∗ |  6∗ |  1∗ |  7∗ |  2∗ | 8∗ |  3∗ |  9∗ |  4∗ |  10∗ | 5∗ | 11∗ | 6∗
Table 7: A Tight CDCCD(21,4,2,42)

######  Example 10.

We may also visualize multiple base blocks pictorially as we did in Example 7.
Consider the base blocks $\\{0,1,4\\}$ and $\\{0,2,7\\}$ of a tight
CDCCD(13,3,26). These blocks are highlighted light blue and dark blue
respectively in Figure 4 and the unchanged subset is highlighted black. All
differences are covered in these two blocks, and in any two consecutive
blocks. Figure 5 shows how we increment Figure 4 by one to move from block 1
to block 3. The light blue highlighting $B_{1}$ is incremented by 1 to form
the light red $B_{3}$.

121110987654321001401427 Figure 4: $c=2$, $k=3$ tight CDCCD(13,3,2,26) initial
blocks $B_{1}$ and $B_{2}$ 121110987654321001501527 Figure 5: $c=2$, $k=3$
tight CDCCD(13,3,2,26) $B_{2}$ and $B_{3}$ which is $B_{1}$ incremented by 1

######  Proposition 11.

When $(k-2)|2c+1$, a CDCCD constructed via Theorem 8 has an expansion set.

###### Proof.

In Theorem 8 the unchanged subsets are all $A+i$, $i\in\mathbb{Z}_{v}$. When
$(k-2)|2c+1$ then $(k-1)|v$. Taking $i\in\\{0,k-2,2k-4,...\\}$ partitions
$\mathbb{Z}_{v}$ giving the expansion set
$\mathcal{E}=\bigcup\limits_{i=0}^{\frac{4ck-6c+1}{k-2}}\\{U_{ic(k-2)}\\}$. ∎

######  Corollary 12.

If $\frac{2c+1}{k-2}$ is odd, then a tight
CDCCD$(c(4k-6)+|\mathcal{E}|+2,k,c^{2}(4k-6)+c+|\mathcal{E}|\frac{|\mathcal{E}|+1}{2})$
exists.

###### Proof.

The order of the expansion set is
$|\mathcal{E}|=\frac{4ck-6c+1}{k-2}=4c+\frac{2c+1}{k-2}$. This is odd if and
only if $\frac{2c+1}{k-2}$ is odd then we apply Theorem 3. ∎

######  Corollary 13.

The following tight CDCCD exist: CDCCD(15,3,35), CDCCD(21,5,30),
CDCCD(27,3,117), CDCCD(55,7,135), CDCCD(39,3,247), CDCCD(105,9,364),
CDCCD(67,3,489), CDCCD(77,5,418), CDCCD(161,11,640), CDCCD(63,3,651),
CDCCD(253,13,1386)

######  Proposition 14.

A tight CDCCD$(61,4,366)$ exists.

###### Proof.

Consider the initial blocks in order as shown in Table 8. Each contains
$A=\\{0,1\\}$ and $B_{0,c}$ contains $A$ and $A+1$ thus
$(B_{0,1},B_{0,2},...,B_{0,c},$ $B_{1,1},...,B_{1,c},...,B_{v,c})$ is double
change. $B_{0,i}=\\{0,1,x,y\\}$ covers differences $\pm\\{y-x,x-1,x,y-1,y\\}$
and as $x,y$ range over values in Table 8 these cover all differences in
$\mathbb{Z}_{6}$ ∎

$k$ | $c$ | Initial Blocks
---|---|---
4 | 6 | $\\{0,1,4,19\\},\\{0,1,6,22\\},\\{0,1,8,25\\},\\{0,1,10,48\\},\\{0,1,12,32\\},$
|  | $\\{0,1,2,28\\}$
Table 8: Base Blocks for a CDCCD(61,4,366)

##  4 Conclusion

We have proved a recursion that uses 1-factorizations and expansion sets to
construct DCCD($v+\frac{v}{k-2}+1,k,b+\frac{v}{k-2}\frac{v+k-2}{2k-4}$) from
DCCD($v,k,b$) when $\frac{v}{k-2}$ is odd. We use the family of tight
CSCCD($2k^{\prime}-1,k^{\prime},2k^{\prime}-1)$ to build tight
CDCCD($2k-2,k,k-1$) and CDCCD($2k-3,k,k-2$). We use difference methods to
construct tight CDCCD(61,4,366) and tight CDCCD($c(4k-6)+1,k,c^{2}(4k-6)+c$)
for $k\geq 3$, $1\leq c\leq 5$. When possible we apply the recursion to these
to construct eleven additional CDCCD.

There are several directions to explore next. Can we develop a version of
Theorem 3 that works when the size of the expansion set is even? Can we
develop a version of Theorem 3 to build economic DCCD from tight DCCD as in
[2]. Does there exist recursive construction that uses expansion sets and two
DCCD to build tight DCCD or CDCCD as in [11, 2] respectively? McSorely proved
the number of blocks in minimum CSCCD as long as $v\leq 2k-1$ [7]. Can we
solve the existence of minimum CDCCD when $v\leq 2k-2$? Finally, can we find
more linear DCCD beyond when $k=4$?

## References

  * [1] J. Akiyama and M. Kano.  Factors and Factorizations of Graphs.  Springer, 2011.
  * [2] A.L. Chafee and B. Stevens.  Circular and non-circular single change covering designs re-visited.  Submitted to J. Combin. Des., 2022.
  * [3] F. cruz.  The ibm 2311 disk drive and 2400 tape drive.  http://www.columbia.edu/cu/computinghistory/2311.html, 2001.  Accessed: 2021-09-23.
  * [4] Nirosh Tharaka Gangoda Gamachchige.  Double-Change Circular Covering Designs: Constructions And Applications.  M.Sc., Southern Illinois University, Carbondale, Il, 2014.
  * [5] Nirosh Tharaka Sandakelum Gangoda Gamachchige.  Double-Change Covering Designs with Block Size K = 4.  Ph.D., Southern Illinois University, Carbondale, IL, 2017.
  * [6] K. Shirriff.  A look at ibm s/360 core memory: In the 1960s, 128 kilobytes weighed 610 pounds.  http://www.righto.com/2019/04/a-look-at-ibm-s360-core-memory-in-1960s.html, 2019\.  Accessed: 2021-09-23.
  * [7] J. P. McSorley.  Single-change circular covering designs.  Discrete Math., 197/198:561–588, 1999.
  * [8] J.A. Nelder.  The efficient formation of a triangular array with restricted storage for data.  Applied Statistics, 18:203–206, 1969.
  * [9] D. A. Preece, R. L. Constable, G. Zhang, J. L. Yucas, W. D. Wallis, J. P. McSorley, and N. C. K. Phillips.  Tight single-change covering designs.  Utilitas Math., 47:55–84, 1995.
  * [10] D.A. Preece.  Tight single-change covering designs - the inside story.  Bulletin of the ICA, 13:51–55, 1995.
  * [11] W. D. Wallis, J. L. Yucas, and G.-H. Zhang.  Single change covering designs.  Des. Codes Cryptogr., 3(1):9–19, 1993.


Domain Generalization (DG) techniques have emerged as a popular approach to address the challenges of domain shift in Deep Learning (DL), with the goal of generalizing well to the target domain unseen during the training. In recent years, numerous methods have been proposed to address the DG setting, among which one popular approach is the adversarial learning-based methodology. The main idea behind adversarial DG methods is to learn domain-invariant features by minimizing a discrepancy metric. However, most adversarial DG methods use 0-1 loss based $\mathcal{H}\Delta\mathcal{H}$ divergence metric. In contrast, the margin loss-based discrepancy metric has the following advantages: more informative, tighter, practical, and efficiently optimizable. To mitigate this gap, this work proposes a novel adversarial learning DG algorithm, MADG, motivated by a margin loss-based discrepancy metric. The proposed MADG model learns domain-invariant features across all source domains and uses adversarial training to generalize well to the unseen target domain. We also provide a theoretical analysis of the proposed MADG model based on the unseen target error bound. Specifically, we construct the link between the source and unseen domains in the real-valued hypothesis space and derive the generalization bound using margin loss and Rademacher complexity. We extensively experiment with the MADG model on popular real-world DG datasets, VLCS, PACS, OfficeHome, DomainNet, and TerraIncognita. We evaluate the proposed algorithm on DomainBed's benchmark and observe consistent performance across all the datasets.

§ INTRODUCTION

Over the past decade, Deep Neural Networks (DNNs) have demonstrated exceptional performance across various fields, including robotics [1], medical imaging [2], agriculture [3], and more. However, the effectiveness of DNNs in supervised learning environments relies heavily on the independently and identically distributed ($i.i.d.$) assumption of the training and test (target) data. Unfortunately, in reality, this assumption can be compromised due to domain shifts in target data [4]. For example, a model trained on different domains of image data may perform poorly when presented with an image of a known label featuring an unseen background or viewpoint, as explained in [5]. To address this issue, researchers have developed techniques under the framework of domain adaptation (DA) [6]. The key idea behind DA is to adapt a model trained on a source dataset to minimize the generalization error on the target dataset [7]. However, the major limitation of DA is that the target data, whether labeled or unlabeled, must be available during training. In contrast, the Domain Generalization (DG) setting aims to leverage knowledge from similar domains to classify previously unseen domains [8].

Recent years have seen the development of various algorithms addressing the DG setting, among which one popular approach is the adversarial learning-based methodology [9, 10, 11, 12, 13, 14]. Other approaches can be broadly classified into  meta-learning techniques [15, 16, 17], data augmentation methods [18, 19, 20], self-supervised learning methods [21, 22, 23], regularization-based methods [24, 25, 26, 27, 28, 29], and so on. Additionally, there have been concerted efforts towards the development of benchmark datasets [30, 31, 32, 33, 34, 35] for the DG setting to study methods. The assumption of distribution shift, i.e., smooth variation between the conditional distribution $\mathbb{P}(Y|X)$ and the marginal distribution $\mathbb{P}(X)$ is also common in DG literature [36, 37].

The main objective of DG methods is to model the functional relationship between the input space $\mathcal{X}$ and the label space $\mathcal{Y}$ for all domains. To achieve this, adversarial DG methods learn a domain-invariant representation by minimizing a discrepancy metric among the source domains. However, despite the myriad efforts, most adversarial learning methods use the 0-1 loss based $\mathcal{H}\Delta\mathcal{H}$ divergence metric [38] for domain alignment. In contrast, divergence metrics based on margin loss are more informative [39], practical, and efficiently optimizable [40]. This work addresses this gap by proposing a novel adversarial DG algorithm, MADG, motivated by a margin-based divergence metric. The proposed MADG leverages margin-based disparity discrepancy [40] to estimate source domain discrepancies in the DG setting and uses adversarial training to ensure that MADG generalizes well to unseen target domains. We also theoretically analyze the proposed MADG algorithm based on bounds for the unseen target error. The proposed generalization bound uses the Rademacher complexity framework [41], which provides data-dependent estimates of functional class complexities. The effectiveness of the proposed algorithm is demonstrated through extensive experiments on multiple benchmark DG datasets.

The key contributions of this work can be summarized as follows: (i) We introduce the use of margin loss and a corresponding scoring function to formulate the relationship between domains and develop upper bounds for the unseen target error (the first such margin-based effort in the DG setting, to the best of our knowledge); (ii) We subsequently analyze the generalization bound in terms of functional class complexity using the Rademacher complexity framework; (iii) We propose a novel margin-based adversarial DG training algorithm, MADG, motivated by our theoretical results; and (iv) We study the proposed method on five well-known benchmark datasets in the DomainBed setup, providing a higher average accuracy and consistency in model performance across these datasets.

§ RELATED WORK

In this section, we discuss earlier literature proposed specifically for adversarial DG, as well as theoretical analysis for the DG problem in general. We discuss other DG literature across a broader set of categories in the Appendix. The main idea behind existing adversarial DG methods is to minimize the $\mathcal{H}\Delta\mathcal{H}$ divergence by employing a minimax optimization between a domain discriminator and a classifier to learn domain-invariant features. One of the early works [9] proposed a method that iteratively divided samples into latent domains via clustering and trained the domain-invariant feature extractor via adversarial learning. Other efforts extended such an approach of adversarial learning with different divergence metrics and regularization techniques. Lin et al. [10] proposed a multi-dataset feature generalization network (MMFA-AAE) based on an adversarial auto-encoder to learn a generalized domain-invariant latent feature representation with the Maximum Mean Discrepancy (MMD) measure to align  distributions across multiple domains. Deng et al. [11] examined adversarial censoring techniques to learn invariant representations from multiple domains. Zhao et al. [12] proposed an entropy regularization term along with adversarial loss to ensure conditional invariance of learned features. Akuzawa et al. [13] proposed the notion of accuracy-constrained
domain invariance, and then developed an adversarial feature learning method with accuracy constraint (AFLAC), which explicitly provided invariance on adversarial training. Rahman et al. [42] proposed a correlation-aware adversarial DG framework where the features of the source and target data are minimized using correlation alignment along with adversarial learning. All these prior works on adversarial DG methods use a 0-1 loss based $\mathcal{H}\Delta\mathcal{H}$ discrepancy metric to align source domains. In this work, we instead leverage a margin-based disparity discrepancy and propose a new adversarial learning strategy founded on our theoretical analysis. The margin loss is advantageous compared to the 0-1 loss as it provides informative generalization bounds, tightness, classifier-aware alignment, and efficient optimization. We discuss each of these advantages in detail in Section <ref>.

Early efforts for theoretical analysis for the DG problem [43, 44] used kernel-based approaches to the problem setting with corresponding generalization error analysis, and showed empirical results using traditional machine learning methods. A few other efforts [45, 46, 47] also followed a similar path, and focused on kernel-based approaches in traditional methods. From a deep learning perspective, an early attempt at such a theoretically motivated method was proposed in [48] using a convex hull formulation and distribution matching to obtain generalization bounds, which also is an inspiration for parts of our work. In [49], the authors study theoretical bounds in the DG setting using three new concepts: feature invariance across domains, feature discriminability for the classification task, and a feature expansion function to generalize the first two concepts from the source to the target domain. [50] identified measures relating to the Fisher information, predictive entropy, and maximum mean discrepancy to be good predictors of out-of-distribution generalization of empirical risk minimization (ERM) models in the DG setting. [24] proposed generalization bounds in terms of the model's Rademacher complexity and suggested using regularized ERM models for the DG problem. Finally, [14] introduced an online game in which one model (player) reduces the error on test data provided by an adversarial player, but do not provide any empirical studies. In this work, we draw inspiration from [48] by considering a convex combination of source domains and leverage this to propose a new margin-based approach to the theoretical analysis of DG, which helps develop an informative generalization bound. Motivated by this analysis, we propose the MADG algorithm, a novel margin-based adversarial learning approach for DG, which shows consistent performance over other state-of-the-art methods across benchmarks.

§ PRELIMINARIES

We consider a set of source domains $\mathcal{D}_{\mathcal{S}_i}$ with $i \in \bigl\{1,2,\dots,N_s\bigl\}$ and a set of unseen domains $\mathcal{D}_{U_m}$ with $m \in \bigl\{1,2,\dots,N_u\bigl\}$. We use $\mathcal{D}$ to refer to any of these domains when the index is not relevant. We use the terms `domain' and `distribution' interchangeably in this work. Each such domain $\mathcal{D} \subseteq \mathcal{X} \times \mathcal{Y}$, where $\mathcal{X}$ is an input space and $\mathcal{Y}$ is an output space, which is $\{0, 1\}$ in binary classification and $\{1,\cdots,k\}$ in multi-class classification. We use $\hat{{D}}$ to denote a set of samples drawn independently from $\mathcal{D}$, i.e. ${\hat{D}} = \bigl\{(x_i,y_i)\bigl\}_{i=1}^{n}$ where $x_i \in \mathcal{X} \text{ and } y_i \in \mathcal{Y} \text{,}\forall i\in \bigl\{ 1,2,\dots,n\bigl\}$. We use $(x,y)$ to refer to a labeled sample $(x_i,y_i)$, when the index is not relevant.

As in [51], we consider the multi-class setting with a hypothesis space $\mathcal{F}$ of scoring functions $f: \mathcal{X \rightarrow \mathbb{R}^{|\mathcal{Y}|}} =  \mathbb{R}^k$, where the outputs report the confidence of the prediction on each dimension. Similar to [40], we use $f(x,y)$ to denote the component of $f(x)$ that corresponds to
the label $y$. In order to obtain the final predicted label, we also consider a labeling function space $\mathcal{H}$ containing $h_f: \mathcal{X} \rightarrow \mathcal{Y}$ such that
$h_f(x) = \text{argmax}_{y \in \mathcal{Y}} \text{ } f(x, y)$, i.e. the predicted label assigned to data sample $x$ is the
one resulting in the largest confidence score.

The expected error rate of a classifier $h \in \mathcal{H}$ with respect to a distribution $\mathcal{D}$ is defined as $err_{\mathcal{D}}(h) \delequal \mathbb{E}_{(x, y) \sim \mathcal{D}} \mathbbm{1} \bigr[h(x) \neq y\bigr]$ where $\mathbbm{1}$ is the indicator function. We also define the margin $\rho_f(\cdot)$ and the corresponding margin loss of hypothesis $f$ for a labeled example $(x,y)$ as follows:

\begin{equation}
\label{margin_loss}
\centering
\rho_f(x, y) \delequal \frac{1}{2}\Bigl(f(x, y) - \text{max}_{y' \neq y}\text{ }f(x,y')\Bigl); \hspace{9mm}
err_{\mathcal{D}}^{(\rho)} (f) \delequal \mathbb{E}_{x \sim \mathcal{D}} \bigr[\Phi_\rho \circ \rho_f(x, y)\bigr]
\end{equation}

where $\circ$ denotes the composition function and $\Phi_\rho$ is:

\begin{equation}
\Phi_\rho (t) =
\begin{cases}
0 & \text{if } \rho \leq t\\
1 - \frac{t}{\rho} & \text{if } 0 \leq t \leq \rho \\
1 & \text{if } t \leq 0
\end{cases}
\end{equation}

The margin disparity and its empirical version are then defined as:

\begin{equation}
\text{disp}_\mathcal{D}^{(\rho)}\bigl(f', f\bigl) \delequal \mathbb{E}_{\mathcal{D}} \bigr[\Phi_\rho \circ \rho_{f'}(., h_f)\bigr]
\vspace{-5pt}
\end{equation}

\begin{equation}
\text{disp}_{\hat{D}}^{(\rho)}\bigl(f', f\bigl) \delequal \mathbb{E}_{\hat{D}} \bigr[\Phi_\rho \circ \rho_{f'}(., h_f)\bigr] \\
= \frac{1}{n} \sum_{i=1}^n \Phi_\rho \circ \rho_{f'}\bigl(x_i, h_f(x_i)\bigl)
\end{equation}

where $f$ and $f'$ are different scoring functions. Margin disparity discrepancy (MDD) is used to quantify the degree of discrepancy/disagreement between decision boundaries of classifiers (using their margins) trained on different domains in our context. Such a measure can be used to evaluate the generalization performance of a model across multiple domains. The MDD and its empirical version are defined in Eqn. (<ref>) and Eqn. (<ref>) below, respectively.

\begin{equation}
\label{MDD}
\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{S_i}, \mathcal{D}_{S_k}\bigl) \delequal \text{sup}_{f' \in \mathcal{F}} \Bigl(\text{disp}_{\mathcal{D}_{S_k}}^{(\rho)}\bigl(f', f\bigl) - \text{disp}_{\mathcal{D}_{S_i}}^{(\rho)}\bigl(f', f\bigl)\Bigl)
\vspace{-6pt}
\end{equation}

\begin{equation}
\label{MDD_emp}
\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl({\hat{D}}_{S_i}, {\hat{D}}_{S_k}\bigl) \delequal \text{sup}_{f' \in \mathcal{F}} \Bigl(\text{disp}_{{\hat{D}}_{S_k}}^{(\rho)}\bigl(f', f\bigl) - \text{disp}_{{\hat{D}}_{S_i}}^{(\rho)}\bigl(f', f\bigl)\Bigl)
\end{equation}

We use the above terminologies from [40], which however focused on domain adaptation (with one source domain and one seen target domain). Handling multiple seen domains and an unseen target domain in the DG setting is non-trivial, which we focus on in this work.

§ MARGIN-BASED APPROACH TO DOMAIN GENERALIZATION: THEORY

This section presents the theoretical motivation for our margin-based approach to the Domain Generalization (DG) problem. Our approach is based on considering the margin disparity discrepancy (MDD), defined above, between the source domains, thereby obtaining a generalization bound.
We believe such a margin-based approach has a few advantages: (i) Informative: Generalization bounds based on margin loss for classification provide more information (than 0-1 loss-based bounds) by establishing a dependency between any margin function satisfying the Lipschitz condition and the upper bounds, as demonstrated in well-known earlier work [39]. (ii)  Tightness: In contrast to using a 0-1 loss to identify samples causing disagreement between classifiers, margin loss computes disagreement between scoring functions using a smooth function parameterized by the threshold ($\rho$). Consequently, the number of samples causing agreement between classifiers is less, resulting in such an MDD-based bound being tighter, as shown in Fig. <ref>.
(iii) Classifier-aware Discrepancy: MDD considers the classifier function while measuring discrepancy; as shown in Eqns <ref> and <ref>, the supremum is computed over $f'$ while holding $f$ constant ($f$ learns the posterior distribution $\mathbb{P}(y|x)$ discriminatively for the classification task). This provides a classifier-aware approach to computing discrepancy.

Space of intersection (agreement) in MDD (yellow) is reduced as compared to 0-1 loss (blue + yellow) between $f$ and $f'$ for labels $\{0,1\}$.

(iv) Efficient Optimization and Practicality: The definition of MDD, as in Eqn. (<ref>), only requires taking the supremum over one hypothesis.
Therefore, compared to other divergence measures such as $\mathcal{H}\Delta\mathcal{H}$ [38], MDD can be optimized with ease and is practically useful, as also stated in [40].

In this section, we derive a generalization bound for an unseen domain based on the margin-based MDD loss in the DG setting. To this end, we first show an upper bound on the unlabeled source domain error given other labeled source domains (Lemma 1 and Theorem 1). We then leverage this to develop the upper bound for the error on an unseen domain that is not necessarily a source domain (Lemma 2, Theorem 2, and Corollary 1). We subsequently analyze the upper bound from Corollary 1 using the Rademacher complexity framework and develop our final generalization bound for the unseen target domain in the DG setting (Lemma 3 and Theorem 3) using our margin-based loss. In Sec 5, we show the formulation of the proposed adversarial learning algorithm, MADG, motivated by the generalization bound in Sec 4, that employs MDD to address the DG problem.

We begin by considering a setting where training data consists of $N_s-1$ labeled source domains $\mathcal{D}_{\mathcal{S}_i},i=\{1,\dots,N_s-1\}$ and a single unlabeled source domain $\mathcal{D}_{\mathcal{S}_T}$, and show an upper bound on error in this setting. We later use this to show an upper bound for the DG setting. We first establish an upper bound on the MDD between a weighted sum of the labeled source domains and the unlabeled one in Lemma <ref> below.

Consider a weighted sum of $N_s-1$ labeled source distributions defined as $\mathcal{D}_{\bar{\mathcal{S}}} := \sum_{i=1}^ {N_s-1} \alpha_i \mathcal{D}_{\mathcal{S}_i}$, where $\alpha_i$s are mixture co-efficients s.t. $\sum_{i=1}^ {N_s-1} \alpha_i = 1$, and $f$ is a scoring function. Then

\begin{equation}
\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl( \mathcal{D}_{\bar{\mathcal{S}}}, \mathcal{D}_{\mathcal{S}_T}\bigl) \leq \sum_{i=1}^ {N_s-1} \alpha_i \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_i},\mathcal{D}_{\mathcal{S}_T}\bigl)
\end{equation}

Detailed proofs for all our theoretical results are provided in the Appendix.
It follows from Lemma <ref> that an effective way to minimize the discrepancy between the unlabeled source domain and the mixture of labeled source domains in the hypothesis space is by minimizing the convex sum of the pairwise MDD between each labeled and unlabeled source domain. Building upon this insight, we provide bounds on the unlabeled source error below in Theorem <ref>.

Consider a scoring function $f$, unlabeled source domain $\mathcal{D}_{\mathcal{S}_T}$ and a mixture of $N_s-1$ source distributions denoted as $\mathcal{D}_{\bar{\mathcal{S}}} := \sum_{i=1}^ {N_s-1} \alpha_i \mathcal{D}_{\mathcal{S}_i}$, where $\alpha_i$s is mixture co-efficients s.t. $\sum_{i=1}^ {N_s-1} \alpha_i = 1$. Then the error on the unlabeled source $\mathcal{D}_{\mathcal{S}_T}$ is bounded as:

\begin{equation}
\label{th1}
err_{\mathcal{D}_{\mathcal{S}_T}}(h_f) \leq \sum_{i=1}^ {N_s-1} \alpha_i \Bigl( err_{\mathcal{D}_{\mathcal{S}_i}}^{(\rho)}(f) + \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_i},\mathcal{D}_{\mathcal{S}_T}\bigl)\Bigl) + \hat{\lambda}
\end{equation}

Remark 1: From Theorem <ref>, we observe that the unlabeled source error is upper bounded by the labeled source errors, the pairwise discrepancy between each labeled and unlabeled source domain, and the ideal margin loss described below in Remark 2. We can also interpret Theorem <ref> as an upper bound for the multi-source domain adaptation (DA) setting. While this is not our primary focus in this work, we report preliminary empirical results for a multi-source DA algorithm that reduces the first two terms in Theorem <ref> in the Appendix.

Remark 2: The ideal loss $\hat{\lambda}$ is defined as $ \label{lambda_h}
\hat{\lambda} = \min_{f^* \in \mathcal{F}} \Bigl(\sum_{i=1}^ {N_s-1} \alpha_i  \hspace{1mm} err_{\mathcal{D}_{\mathcal{S}_i}}^{(\rho)}(f^*) + err_{\mathcal{D}_{\mathcal{S}_T}}^{(\rho)} (f^*)\Bigl)$ and is a constant that is independent of function $f$.

Building on Theorem <ref>, we now develop bounds for the DG setting, where all source domains ($N_s$) are labeled, and the target domain is unseen during training. To this end, we consider the relationship between the unseen target and multiple source domains. In particular, we derive our error bound on the unseen target domain using the convex hull of the labeled source domains and MDD. We also provide a DG algorithm motivated by our theoretical analysis, which we describe later in Sec <ref>.

Before stating our main theorem, we present Lemma <ref>, which states that if the maximum MDD between any two sources is bounded above by $\epsilon$, then the MDD between any two domains that belong to the convex hull of all the sources will also be bounded by $\epsilon$. Let $\Lambda_s$ be the convex hull of source domains defined as $\Lambda_s = \Bigl\{ \bar{\mathcal{D}}: \bar{\mathcal{D}} = \sum_{i=1}^{N_s} \pi_i\mathcal{D}_{\mathcal{S}_i} \text{ where } \sum_{i=1}^{N_s} \pi_i = 1\Bigl\}$.

Let $\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_i},\mathcal{D}_{\mathcal{S}_k}\bigl) \leq \epsilon \text{ } \forall i,k \in \bigl\{1,2,\dots,N_s\bigl\}$ and $f$ be a scoring function. Then the following inequality holds for the MDD between any pair of domains $\mathcal{D'}, \mathcal{D''}\in \Lambda_s$:

\begin{equation}
\label{lemma2}
\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D'},\mathcal{D''}\bigl) \leq \epsilon
\end{equation}

We observe from Lemma <ref> that in the hypothesis space, the discrepancy among all the domains (seen or unseen) that belong to the convex hull $\Lambda_s$ can be reduced by minimizing the maximum MDD between two source domains. With the necessary tools at hand, we state the key theorem, i.e., the unseen target error bound for the DG problem below in Theorem <ref>.

Consider a mixture of $N_s$ source distributions, scoring function f, unseen domain $\mathcal{D}_{U_m}$, and $\gamma  = \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{U_m}, \bar{\mathcal{D}}_{U}\bigl)$ where $\bar{\mathcal{D}}_{U}$ is the projection of $\mathcal{D}_{U_m}$ onto the convex hull of the sources i.e. $\bar{\mathcal{D}}_{U} = \text{argmin}_{\pi_1,\pi_2,\dots,\pi_{N_s}}\text{ }\text{d}_{f, \mathcal{F}}^{(\rho)} \Bigl(\mathcal{D}_{U_m},\sum_{i=1}^ {N_s} \pi_i \mathcal{D}_{\mathcal{S}_i}\Bigl), \sum_{i=1}^ {N_s} \pi_i =1. $ Then, the unseen target error is bounded as follows:

\begin{equation}
\label{th2}
err_{\mathcal{D}_{U_m}}(h_f) \leq \sum_{i=1}^ {N_s} \pi_i \Bigl( err_{\mathcal{D}_{\mathcal{S}_i}}^{(\rho)}(f)\Bigl)+ \epsilon + \gamma + \bar{\lambda}
\end{equation}

Remark 3: As defined in Theorem <ref>, $\gamma = \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{U_m}, \bar{\mathcal{D}}_{U}\bigl)$. Two scenarios therefore arise: $\gamma = 0$ when the unseen domain falls in the convex hull, i.e., $\mathcal{D}_{U_m} = \sum_{i=1}^ {N_s} \pi_i\mathcal{D}_{\mathcal{S}_i}$ or $\gamma > 0$ when the unseen domain cannot be represented by available domains alone. Thus this parameter can be interpreted as the need for diverse source domains. The more diverse the source domains are, the smaller the value of $\gamma$.

Remark 4: As seen from Lemma <ref>, $\epsilon$ is defined as the upper bound for the MDD between any two domains that belong to the convex hull $\Lambda_s$ formed by the source domains. Thus, we can also interpret $\epsilon$ as the highest MDD value among the source domains as shown below in Eqn <ref>.

\begin{equation}
\label{eps_app}
\centering
\begin{aligned}
&\epsilon = \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_{i'}},\mathcal{D}_{\mathcal{S}_{k'}}\bigl), \hspace{1mm}
\textbf{s.t. } \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_{i'}},\mathcal{D}_{\mathcal{S}_{k'}}\bigl) \geq \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_i},\mathcal{D}_{\mathcal{S}_k}\bigl) \text{ } \forall i,k,i',k' \in \bigl\{1,\dots,N_s\bigl\}
\end{aligned}
\end{equation}

Equipped with this definition for $\epsilon$, we can re-state Theorem <ref> as Corollary <ref> below.

Consider a mixture of $N_s$ source distributions, scoring function f, unseen domain $\mathcal{D}_{U_m}$, $\gamma  = \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{U_m}, \bar{\mathcal{D}}_{U}\bigl)$, and $\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_{i'}},\mathcal{D}_{\mathcal{S}_{k'}}\bigl)$ where $\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_{i'}},\mathcal{D}_{\mathcal{S}_{k'}}\bigl) \geq \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_i},\mathcal{D}_{\mathcal{S}_k}\bigl) \text{ } \forall i,k,i',k' \in \bigl\{1,2,\dots,N_s\bigl\}$. Then the unseen target error is bounded as follows:

\begin{equation}
\label{c1}
err_{\mathcal{D}_{U_m}}(h_f) \leq \sum_{i=1}^{N_s} \pi_i \Bigl( err_{\mathcal{D}_{\mathcal{S}_i}}^{(\rho)}(f)\Bigl)+ \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_{i'}},\mathcal{D}_{\mathcal{S}_{k'}}\bigl) + \gamma + \bar{\lambda}
\end{equation}

As seen from Corollary <ref>, the unseen target error is bounded above by the source errors, maximum MDD between two source domains, $\gamma$, and the ideal loss given by $\bar{\lambda} = \min_{f^* \in \mathcal{F}} \biggl(\sum_{i=1}^{N_s} \pi_i  err_{\mathcal{D}_{\mathcal{S}_i}}^{(\rho)}(f^*) + err_{\mathcal{D}_{U_m}}^{(\rho)} (f^*)\biggl)$.

Before we derive the generalization bound with the Rademacher complexity framework, we define $\Pi_\mathcal{H}\mathcal{F} = \biggl\{ x \mapsto f\bigl(x,h(x)\bigl) \bigg| h \in \mathcal{H}, f \in \mathcal{F}\biggl\}$ [40] and Rademacher complexity $\mathfrak{R}_{n,\mathcal{D}}$ in Definition <ref>.

Let $\mathcal{F}$ be a class of functions such that $f \in \mathcal{F}: \mathcal{X} \times \mathcal{Y} \rightarrow [a,b]$ and ${\hat{D}} = \bigl\{(x_1,y_1)\dots,(x_n,y_n)\bigl\}$ be a fixed sample of size $n$ drawn from $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$. Then the Rademacher complexity of $\mathcal{F}$ is defined as:

\begin{equation}
\label{radema}
\mathfrak{R}_{n,\mathcal{D}}(\mathcal{F}) \delequal \mathbb{E}_{{\hat{D}}\sim \mathcal{D}^n}\Biggr[\mathbb{E}_\sigma \biggr[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i = 1}^n \sigma_i f(x_i,y_i)\biggr]\Biggr]
\end{equation}

where $\sigma_i$s are independent Rademacher variables that assume values in $\{-1,+1\}$. We now leverage Lemma 3.6 in [40] to derive our Lemma <ref>.

For any $\delta > 0$, with probability $1 - 2\delta$, the following holds simultaneously for any scoring function $f$:

\begin{equation}
\label{l13.6}
\bigg|\text{d}_{f, \mathcal{F}}^{(\rho)} \bigl({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k}\bigl) - \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\mathcal{D}_{\mathcal{S}_i},\mathcal{D}_{\mathcal{S}_k}\bigl)\bigg| \leq \frac{k}{\rho}\mathfrak{R}_{n_i,\mathcal{D}_{\mathcal{S}_i}}\bigl(\Pi_\mathcal{H}\mathcal{F}\bigl) + \frac{k}{\rho}\mathfrak{R}_{n_k,\mathcal{D}_{\mathcal{S}_k}}\bigl(\Pi_\mathcal{H}\mathcal{F}\bigl) + \sqrt{\frac{\log\frac{2}{\delta}}{2n_i}} + \sqrt{\frac{\log\frac{2}{\delta}}{2n_k}}
\end{equation}

where $n_i\text{ and }n_k$ correspond to the sample size of $\hat{D}_{\mathcal{S}_i}\text{ and }\hat{D}_{\mathcal{S}_k}$, respectively. The difference between MDD and its empirical version is bounded by the Rademacher complexity as seen in Eqn <ref>. With these definitions, we derive our generalization bound based on Rademacher complexity and empirical MDD as below.

Given the same setting as Corollary 1 and Lemma 3, for any $\delta > 0$, with probability $1 - 3\delta$, we obtain the following generalization bound for all $f$:

\begin{equation}
\label{th3}
\begin{aligned}
err_{\mathcal{D}_{U_m}}(f) &\leq \sum_{i=1}^{N_s} \pi_i \Bigl( err_{{\hat{D}}_{\mathcal{S}_i}}^{\rho}(f)\Bigl)+ \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl({\hat{D}}_{\mathcal{S}_{i'}},{\hat{D}}_{\mathcal{S}_{k'}}\bigl) + \gamma + \bar{\lambda} + \frac{k}{\rho}\mathfrak{R}_{n_i,\mathcal{D}_{\mathcal{S}_i}}\bigl(\Pi_\mathcal{H}\mathcal{F}\bigl) \\
\vspace{-8pt}
&+\frac{k}{\rho}\mathfrak{R}_{n_k,\mathcal{D}_{\mathcal{S}_k}}\bigl(\Pi_\mathcal{H}\mathcal{F}\bigl)+ \sqrt{\frac{\log\frac{2}{\delta}}{2n_{i'}}} + \sqrt{\frac{\log\frac{2}{\delta}}{2n_{k'}}} + \sum_{i=1}^{N_s} \pi_i \Biggl(\frac{2k^2}{\rho}\mathfrak{R}_{n_i,\mathcal{D}_{\mathbf{S}_i}}\bigl(\Pi_1\mathcal{F}\bigl) + \sqrt{\frac{\log\frac{2}{\delta}}{2n_i}}\Biggl)
\end{aligned}
\end{equation}

where $\Pi_1\mathcal{F} \delequal \bigl\{ x \mapsto f(x,y) \big| y \in \mathcal{Y}, f \in \mathcal{F}\bigl\}$ as defined in [51] and $1$ (in the subscript) represents constant functions mapping all points to the same class (see Appendix for more details). Theorem <ref> thus establishes a relationship between the margin value $\rho$ and the generalization error. The first two terms on the right-hand side exhibit minimal variation with an increase in the margin $\rho$, especially when $\rho$ is small and the hypothesis space is rich, thus reducing the overall right-hand side. However, if $\rho$ exceeds a certain threshold (resulting in a weak classifier), then the first two terms significantly increase, resulting in increase of the overall bound. Choosing a better $\rho$ value thus allows one to obtain a desired error bound, making it more informative than a 0-1 loss-based bound. Inspired by this theoretical framework, we now propose our margin-based adversarial learning algorithm for DG in the next section.

§ MADG: METHODOLOGY

This section details the methodology of the proposed MADG algorithm, a novel adversarial DG algorithm motivated by the theory in Section <ref>. As seen in Theorem <ref>, the unseen target domain error is upper-bounded by the convex sum of the empirical source domain errors, $\hat{\epsilon}$ term defined in Eqn. (<ref>), $\gamma$, $\bar\lambda$ and complexity terms. We hence aim to minimize the two important terms, viz., the convex sum of the empirical source domain errors and the $\hat{\epsilon}$ term (given below).

\begin{equation}
\label{emp_e}
\begin{aligned}
\hat{\epsilon} = \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\hat{D}_{\mathcal{S}_{i'}},\hat{D}_{\mathcal{S}_{k'}}\bigl), \hspace{1mm}
\textbf{s.t. } \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\hat{D}_{\mathcal{S}_{i'}},\hat{D}_{\mathcal{S}_{k'}}\bigl) \geq \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\hat{D}_{\mathcal{S}_i},\hat{D}_{\mathcal{S}_k}\bigl) \text{ } \forall i,k,i',k' \in \bigl\{1,\dots,N_s\bigl\}
\end{aligned}
\end{equation}

Efficient estimation of $\hat{\epsilon}$.
As stated in Eqn. (<ref>), $\hat{\epsilon}$ is defined as the maximum pairwise empirical MDD among all source domains. Similar to Remark 4 and Lemma <ref>, we can also interpret $\hat{\epsilon}$ as the upper bound of the empirical MDD between any two domains inside the convex hull formed by the source domains. If we minimize the sum of the empirical MDD between different pairs of the source domains, then the size of the convex hull reduces, which in turn minimizes $\hat{\epsilon}$. Thus, one effective way to estimate $\hat{\epsilon}$ is to consider the term below in Eqn. (<ref>).

\begin{equation}
\label{eps}
\sum_{i=1}^{N_s-1}\sum_{k=i+1}^{N_s} \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl(\hat{D}_{S_i},\hat{D}_{S_k}\bigl)
\end{equation}

Minimax optimization.
To find the optimal $f$ in the hypothesis space $\mathcal{F}$, we formulate our objective function as a minimization problem. As mentioned earlier, we minimize the sum of the empirical source errors and the $\hat{\epsilon}$ term estimated using Eqn (<ref>). Thus, the minimization problem can be written as:

\begin{equation}
\label{minmax_eps}
\min_{f \in \mathcal{F}} \sum_{i=1}^{N_s} \pi_i \Bigl( err_{{\hat{D}}_{\mathcal{S}_i}}^{(\rho)}(f)\Bigl) + \sum_{i=1}^{N_s-1}\sum_{k=i+1}^{N_s} \text{d}_{f, \mathcal{F}}^{(\rho)} \bigl({\hat{D}}_{S_i},{\hat{D}}_{S_k}\bigl)
\end{equation}

Since empirical MDD is defined as the supremum of the hypothesis space $\mathcal{F}$, minimizing it is in turn a minimax game with a strong max player and weaker min player. In order to strengthen the min player, we use a feature extractor, $\mathcal{G}$, which further modifies the optimization problem as follows:

\begin{equation}
\label{opt_prob}
\begin{aligned}
&\min_{f,\mathcal{G}} \sum_{i=1}^{N_s} \pi_i \Bigl( err_{\mathcal{G}({\hat{D}}_{\mathcal{S}_i})}^{(\rho)}(f)\Bigl) + \sum_{l=1}^{j}\Bigl(\text{disp}_{\mathcal{G}({\hat{D}}_{\mathcal{S}_i})}^{(\rho)}\bigl(f_l^*, f\bigl) - \text{disp}_{\mathcal{G}({\hat{D}}_{\mathcal{S}_k})}^{(\rho)}\bigl(f_l^*, f\bigl)\Bigl), \\
&f_l^* = \max_{f_l'} \Bigl(\text{disp}_{\mathcal{G}({\hat{D}}_{\mathcal{S}_i})}^{(\rho)}\bigl(f_l', f\bigl) - \text{disp}_{\mathcal{G}({\hat{D}}_{\mathcal{S}_k})}^{(\rho)}\bigl(f_l', f\bigl)\Bigl)\text{, where } f,f_l' \in \mathcal{F}\text{ and }\forall l=\bigl\{1,\dots,j\bigl\}.
\end{aligned}
\end{equation}

where $ j = \binom{N_s}{2}$. The relationship between $l,i\text{ and }k$ is as follows: if $l=3$ then we pick the $i$ and $k$ value corresponding to the $3^{\text{rd}}$ element of the set $\Bigl\{(i,k): i=\bigl\{1,\dots,N_s-1\bigl\},k=\bigl\{i+1,\dots,N_s\bigl\}\Bigl\}$.
To solve the minimization problem in Eqn. (<ref>), we design an adversarial learning algorithm whose model architecture is shown in Fig. <ref>. One classifier $f$ performs the  classification task on all source domains, while $j$ other classifiers, denoted by $f'$, compute the empirical MDD between different pairs of source domains, which finally sum together as the transfer loss. To compute the source errors in Eqn. (<ref>), we use the standard cross-entropy loss $\mathcal{E}({\hat{D}}_{\mathcal{S}_i})$. For convenience of optimization (MDD can be hard to optimize directly using stochastic gradient descent), in practice, following [40], we approximate the MDD loss as $\Bigl(\mathcal{D}_{({\hat{\rho}},l)}\bigl({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k}\bigl)\Bigl)$ in terms of two loss functions, $L$ and $L'$, as shown below.

Architecture of the proposed MADG methodology

\begin{equation}
\label{E&D}
\begin{aligned}
\mathcal{E}\bigl(\hat{D}_{\mathcal{S}_i}\bigl) &= \mathbb{E}_{(x,y)\sim \hat{D}_{\mathcal{S}_i}}\biggr[L\Bigl(f\bigl(\mathcal{G}(x)\bigl),y\Bigl)\biggr]\\
\mathcal{D}_{(\hat{\rho},l)}\bigl({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k}\bigl) &=  \mathbb{E}_{(x,y)\sim {\hat{D}}_{\mathcal{S}_k}}\biggr[L'\Bigl(f_{l}'\bigl(\mathcal{G}(x)\bigl),f\bigl(\mathcal{G}(x)\bigl)\Bigl)\biggr] - \hat{\rho}\mathbb{E}_{(x,y)\sim {\hat{D}}_{\mathcal{S}_i}}\biggr[L\Bigl(f_{l}'\bigl(\mathcal{G}(x)\bigl),f\bigl(\mathcal{G}(x)\bigl)\Bigl)\biggr]\\
\end{aligned}
\end{equation}

We train the feature extractor, $\mathcal{G}$, to minimize the above MDD loss term by using a Gradient Reversal Layer (GRL) proposed in [52], as $\mathcal{D}_{(\hat{\rho},l)}({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k})$ is not differentiable w.r.t the parameters of $f$. $L$ and $L'$ are defined as:

\begin{equation}
\label{L}
\centering
\begin{aligned}
L\Bigl(f\bigl(\mathcal{G}(x)\bigl),y\Bigl) &\delequal - \log\biggr[\sigma_y\Bigl(f\bigl(\mathcal{G}(x)\bigl)\Bigl)\biggr]\text{,}\hspace{2mm}
L'\Bigl(f'\bigl(\mathcal{G}(x)\bigl),f\bigl(\mathcal{G}(x)\bigl)\Bigl) \delequal \log\biggr[1 - \sigma_{h_f\bigl(\mathcal{G}(x)\bigl)}\Bigl(f'\bigl(\mathcal{G}(x)\bigl)\Bigl)\biggr]\\
\end{aligned}
\end{equation}

where $\sigma_w(z) = \frac{e^{z_w}}{\sum_{i=1}^ke^{z_i}}\text{, }z \in \mathbb{R}^k \text{, for }w = 1,\dots,k,$ and $\hat{\rho} = e^{\rho}$. The final optimization problem that the MADG method solves is shown below.

\begin{equation}
\label{final_optm}
\begin{aligned}
&\min_{f,\mathcal{G}}\sum_{i =1}^{N_s} \pi_i \Bigl(\mathcal{E}({\hat{D}}_{\mathcal{S}_i})\Bigl) + \sum_{l=1}^{j}\Bigl(\mathcal{D}_{({\hat{\rho}},l)}\bigl({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k}\bigl)\Bigl) \text{,}\hspace{2mm}\max_{f_{1}',\dots,f_{j}'} \sum_{l=1}^{j}\Bigl(\mathcal{D}_{({\hat{\rho}},l)}\bigl({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k}\bigl)\Bigl)
\end{aligned}
\end{equation}

Margin-based adversarial learning for Domain Generalization (MADG)

INPUT: $N_s$ labeled source domains

$\text{epoch} \gets 1$ to total_epochs
$\text{batch} \gets 1$ to total_batches

Update parameters of $f$, $\mathcal{G}$, using Eqn. (<ref>)

$\hat{y}_{\hat{D}_{\mathcal{S}_i}} \gets f(\mathcal{G}(x)) \text{ }\forall i \in \{1,2,\dots,N_s\}$

Compute $MDD_l$ as in Eqn. (<ref>) using $\hat{y}_{\hat{D}_{\mathcal{S}_i}}$

Compute Transfer loss

$= \sum_{l=1}^{j}(\mathcal{D}_{({\hat{\rho}},l)}\bigl({\hat{D}}_{\mathcal{S}_i},{\hat{D}}_{\mathcal{S}_k}\bigl))$

Update parameters of $f'$and $\mathcal{G}$ as in Eqn. (<ref>)

We propose an adversarial DG algorithm to solve the minimization problem, as shown in Algorithm <ref>. We train the proposed adversarial model in two steps. In the first step, we update the parameters $f \text{and } \mathcal{G}$. In the next step, we first do a forward pass to compute the outputs from $f$ and then update the parameters $f' \text{and } \mathcal{G}$ as shown in the algorithm. We further show through our ablation studies that this way of updating parameters at different steps outperforms a joint update strategy.

§ EXPERIMENTS

Datasets and Implementation Details.
We perform an extensive evaluation on five benchmark DG datasets for image classification: VLCS [30], PACS [31], OfficeHome (OH) [32], TerraIncognita (TI) [33] and DomainNet (DN) [34].
We follow [53] in using `Test-domain validation' procedure for hyperparameter selection. We use the Resnet50 architecture [54] pre-trained on ImageNet dataset [55] as the feature extractor ($\mathcal{G}$). We train our model using stochastic gradient descent with momentum  [56]. We use a mini-batch that contains 32 samples from all source domains. All other implementation details including hyperparameters such as learning rate, margin, and weight decay are provided in the Appendix.

Baselines and evaluation metrics.
We report the results of all baseline models from [35], which are represented by $\dagger$ in Table <ref>. We also present the results from [53], which are represented by $\perp$. We run our experiments for three trials and report the average accuracy (with standard deviation). Existing state-of-the-art methods (see [35]) focus on average accuracy across the benchmarks, with each method doing well on a subset of datasets. In order to reward consistent performance across datasets while improving average accuracy, we additionally include a ranking-based metric (from [53]) and go beyond ranking with two new metrics (AD and GD), which more precisely capture the consistent performance of a method across datasets:
(i) Median rank (M) [53]: This measures the median rank of a model's performance across all datasets and is not skewed to best/worst ranks when compared to the mean rank. (ii) Arithmetic mean of differences (AD): This measures the difference of a model's performance w.r.t the highest-performing model's accuracy on a given dataset, and then taking its arithmetic mean across datasets. (iii) Geometric mean of differences (GD): This similarly measures the geometric mean of the difference between the highest accuracy and the achieved accuracy of a model across all datasets.

Accuracy(%) on benchmark DG datasets. Values in red and orange are best and second best-performing models in a column, respectively. We report deviation as $\pm \text{N/A}$ for models that did not report them. OH = OfficeHome dataset, TI = TerraIncognita dataset, DN = DomainNet dataset, M = Median rank, AD = Arithmetic mean of differences, GD = Geometric mean of differences, Avg. = Average accuracy(%).

Algorithm        1c AD$(\downarrow)$     1cGD$(\downarrow)$     1cM$(\downarrow)$     1cVLCS     1cOH     1cPACS     1cTI     1cDN     1cAvg.$(\uparrow)$

ERM (1998)$^\dagger$ [57]
2.2     1.8     8      77.6$\pm0.3$    	66.4$\pm0.5$     86.7$\pm0.3$     	53.0$\pm0.3$	    41.3$\pm0.1$    	65.0

CORAL (2016)$^\dagger$ [58]         1.9     1.1     3     77.7$\pm0.2$    	68.4$\pm0.2$    	87.1$\pm0.5$     	52.8$\pm0.2$    	41.8$\pm0.1$    	65.6

DANN (2016)$^\dagger$ [59]         3.4     2.1     16     79.7$\pm0.5$   	65.3$\pm0.8$    	85.2$\pm0.2$    	50.6$\pm0.4$    	38.3$\pm0.1$    	63.8

CDANN (2018)$^\dagger$ [60]        3.2     0.7     14     79.9$\pm0.2$    	65.3$\pm0.5$    	85.8$\pm0.8$     	50.8$\pm0.6$    	38.5$\pm0.2$    	64.1

MLDG (2018)$^\dagger$ [61]        2.3     1.8     6     77.5$\pm0.1$    	66.6$\pm0.3$    	86.8$\pm0.4$     	52.0$\pm0.1$    	41.6$\pm0.1$    	64.9

MMD (2018)$^\dagger$ [62]        5.9     0.9     10     77.9$\pm0.1$    	66.2$\pm0.3$    	87.2$\pm0.1$     	52.0$\pm0.4$    	23.5$\pm9.4$    	61.4

IRM (2019)$^\dagger$ [63]        6.7     5.3     18     76.9$\pm0.6$    	63.0$\pm2.7$    	84.5$\pm1.1$     	50.5$\pm0.7$    	28.0$\pm5.1$    	60.6

GroupDRO (2019)$^\dagger$ [64]         3.9     1.9     10     77.4$\pm0.5$    	66.2$\pm0.6$    	87.1$\pm0.1$     	52.4$\pm0.1$    	33.4$\pm0.3$    	63.3

Mixup (2020)$^\dagger$ [65]        1.9     0.4     5     78.1$\pm0.3$    	68.0$\pm0.2$    	86.8$\pm0.3$     	54.4$\pm0.3$    	39.6$\pm0.1$    	65.4

ARM (2020)$^\dagger$ [66]        4.1     3.4     14     77.8$\pm0.3$    	64.8$\pm0.4$    	85.8$\pm0.2$     	51.2$\pm0.5$    	36.0$\pm0.2$    	63.1

RSC (2020)$^\dagger$ [67]        2.9     2.5    9     77.8$\pm0.6$    	66.5$\pm0.6$    	86.2$\pm0.5$     	52.1$\pm0.2$    	38.9$\pm0.6$    	64.3

SagNet (2021)$^\dagger$ [68]         2.3     2.0     6     77.6$\pm0.1$   	67.5$\pm0.2$    	86.4$\pm0.4$     	52.5$\pm0.4$    	40.8$\pm0.2$    	65.0

V-REx (2021)$^\dagger$ [69]        4.7     0.8     12     78.1$\pm0.2$    	65.7$\pm0.3$    	87.2$\pm0.6$    	51.4$\pm0.5$    	30.1$\pm3.7$    	62.5

AND-mask (2021)$^\perp$ [70]         3.9     3.3     13     76.4$\pm0.4$   	66.1$\pm0.2$    	86.4$\pm0.4$     	49.8$\pm0.4$    	37.9$\pm0.6$    	63.3

Fish (2021)$^\perp$ [71]         2.5     0.6     13     77.8$\pm0.6$    	66.0$\pm2.9$    	85.8$\pm0.6$     	50.8$\pm0.4$    	43.4$\pm0.3$    	64.8

SAND-mask (2021)$^\perp$ [72]         5.2     4.2     16     76.2$\pm0.5$   	65.9$\pm0.5$    	85.9$\pm0.4$     	50.2$\pm0.1$    	32.2$\pm0.6$    	62.1

Fishr (2022)$^\perp$ [53]          1.5     1.2     3     78.2$\pm0.2$   	68.2$\pm0.2$    	86.9$\pm0.2$     	53.6$\pm0.4$    	41.8$\pm0.2$    	65.7

G2DM (2019)$^{\dagger*}$[48]      2* [origin=c]90[c]2cmTheory Based Methods   -    -    -     75.9$\pm \text{N/A}$     -    73.6$\pm \text{N/A}$     -    -    -

MTL(2021)$^{\dagger*}$[47]         2.5     2.0     8     77.7$\pm0.5$    	66.5$\pm0.4$    	86.7$\pm0.2$     	52.2$\pm0.4$    	40.8$\pm0.1$    	64.8

Transfer(2021)* [73]        -    -    -   -     64.3$\pm \text{N/A}$     85.3$\pm \text{N/A}$    -   -   -

Ood(2021)* [49]       -    -    -     76.3$\pm \text{N/A}$   68.1$\pm \text{N/A}$    86.6$\pm \text{N/A}$     -    -    -

MADG (ours)        1.2     0.3      3     78.7$\pm0.2$    	71.3$\pm0.3$    	86.5$\pm0.4$     	53.7$\pm0.5$    	39.9$\pm0.4$    	66.0

We report the results on different DG benchmark datasets on the considered evaluation metrics in Table <ref>. It is observed that most previous methods are far from the best-performing model's accuracy on at least one of the datasets. This is captured well by the metrics AD and GD, which quantify the mean of the differences from the best accuracy across all the datasets. Thus, we observe higher values in the first two columns of Table <ref>, where our MADG model performs the best showing its consistency. The MADG algorithm outperforms all other models on average accuracy, median rank, AD, and GD, thus demonstrating consistent performance.

The results also show that MADG outperform DANN and CDANN models (which are based on the 0-1 loss discrepancy theory) across most datasets and improves the average accuracy by $\approx 2\%$ with significantly better AD and GD values too – corroborating our margin-based approach to the DG problem. MADG is 1% better on the avg accuracy (and lower AD-GD values) when compared to ERM, which was found to be a strong baseline for DG in [35]. Our model also reports an accuracy improvement of $\approx 3\%$ on the OfficeHome dataset compared to all other models.

To highlight our contribution, we also provide a grouping of DG methods that are theory-based in Table <ref> (also denoted with a $*$), some of which do not report results on all benchmark datasets. For the only such method that reports results on all datasets – MTL, MADG achieves $1.2\%$ more average accuracy, 1.3 units less AD, 1.7 units less GD, and a lower median ranking as compared to MTL. More results, including `Training-domain' model selection results, are provided in the Appendix.

§ MORE EMPIRICAL ANALYSIS AND ABLATION STUDIES

Computational Cost. The computational cost of a model is usually measured in terms of GPU RAM occupied (GB) and time taken per step (s). In terms of computational cost, following Eqn. (<ref>), while we iteratively compute MDD over all domains, our computational cost during training is similar to other benchmark methods as shown in Table <ref>. As seen in the table, even simple methods like ERM and Mixup have running times in similar ranges.

Computational cost and Average Accuracy (%) (Avg.) for different baselines.

Model    GPU(GB)($\downarrow$)   Time(s)($\downarrow$)    Avg.($\uparrow$)

MADG     $\sim$10.5     $\sim$1.3     66.0

Fishr [53]     $\sim$15.7     $\sim$0.6     65.7

Fish [71]     $\sim$3.4     $\sim$ 1.2     64.8

Mixup [65]     $\sim$8.2     $\sim$0.4     65.4

ERM [57]     $\sim$8.2     $\sim$0.4     65.0

Margin. As shown in Theorem <ref>,
the margin value $\rho$ plays an important role, especially with its dependency on the generalization error. In practice, to get the desired margin while training the MADG algorithm, we approximate it as $\hat{\rho}\delequal \exp\rho$. We experiment with different margin values, $\hat{\rho} =1\text{, } 1.5\text{, }2\text{, and }3$, and report the average accuracy for PACS and VLCS dataset in Table <ref>. Table <ref> shows that $\hat{\rho} = 1.5$ outperforms other values on both datasets. As seen from the definition of the margin loss function Eqn. (<ref>) and MDD Eqn. (<ref>), although having a large margin is better to achieve low loss and higher target accuracy, there is a tradeoff between optimal margin and loss value. We observe a similar trend in Table <ref>.

Accuracy(%) of MADG model for different $\hat{\rho}$ values.

$\hat{\rho}$     PACS     VLCS

$1$     86.2     78.4

1.5    86.5     78.7

$2$    86.2     78.4

$3$    85.7     77.8

Experiments on Colored MNIST. As stated in Theorem <ref>, $\gamma$ is defined as the projection of the unseen domain onto the convex hull. It is also defined in Theorem <ref> as the MDD between the convex hull and the unseen domain, which can be further approximated with a combination of two different cross-entropy functions as in Eq (<ref>). This equation is equivalent to a balanced Jensen-Shannon (JS) Divergence as shown in Proposition D.1. in [40]. Thus, we can approximate this projection by computing the JS divergence between domains. We experimented on the Colored MNIST dataset, where we noted the $\gamma$ values to be small for all domains, as shown in Table <ref>. This is because the distributions of different domains in Colored MNIST are relatively close to each other when compared to real-world datasets.

Pairwise JS divergence for the ColoredMNIST dataset and the approximated $\gamma$ value.

+90   +80   -90   $\sim \gamma$

+90    0     0.019     0.024     0.043

+80    0.019     0     0.029     0.048

-90   0.024     0.029     0     0.054

As seen in Table <ref>, the proposed MADG algorithm achieves 65.6% average accuracy, which is significantly higher than the ERM model (57.8% average accuracy), thus showing that using a margin-based DG algorithm, MADG, learns better domain-invariant features on the Colored MNIST dataset. Besides, Table <ref> shows that $\gamma$ is small across domains in this dataset, showcasing the promise of the proposed method when the unseen domain is within the convex hull of the source domains.

Accuracy (%) on ColoredMNIST dataset (C).

C    ERM   MADG

+90    71.8$\pm{0.4}$     72.3$\pm{\textbf{0.3}}$

+80    72.9$\pm{0.1}$     74.0$\pm{\textbf{0.2}}$

-90   28.7$\pm{0.5}$    50.5$\pm{\textbf{0.4}}$

Average    57.8     65.6

MDD classifiers. The proposed MADG algorithm uses `j' $f'$ classifiers, and each one calculates the MDD between a pair of source domains. In the algorithm, `j' is defined as $j = \binom{N_{S}}{2}$. In this section, we analyze the algorithm with $j = N_{S} - 1$ where $l$ takes corresponding $i$ and $k$ values from $\{(1,i):i=\{2,\dots,N_s\}\}$. As seen in Table <ref>, for `$N_\mathcal{S} - 1$', the model performs low across all the datasets, significantly ($\sim 2.5\%$) for the TerraIncognita dataset because the model fails to capture all possible domain discrepancies, leading to poor performance by the feature extractor in learning invariant features.

Accuracy(%) of the MADG model for different MDD classifiers. New = $ N_S-1$, Org. = $\binom{N_{S}}{2}$

Data   j=Org.   j=New

VLCS    78.7   78.5

PACS     86.5     86.4

OH     71.3     70.8

TI     53.7     51.1

Additional Results. The proposed MADG algorithm is further compared with recent methods, MIRO [29] and SD [74], which report results using different hyperparameter selection procedures. For a fair comparison, we run both these methods following our setting and report the results on OfficeHome data as shown in Table <ref>. As seen from Table <ref>, the proposed MADG outperforms the SD model on all domains. The MADG model also outperforms MIRO on two domains and achieves the same accuracy on the `R`domain.

Accuracy(%) on OfficeHome (OH) dataset

OH   Miro   SD   MADG

A    67.0 $\pm{0.7}$    64.8$\pm{0.9}$    68.6 $\pm{\textbf{0.5}}$

C     56.5 $\pm{\textbf{0.9}}$     49.9 $\pm{1.2}$     55.5 $\pm{0.2}$

P     79.4 $\pm{1.4}$     75.6 $\pm{1.3}$     79.6 $\pm{\textbf{0.3}}$

R     81.5 $\pm{\textbf{0.5}}$     79.1 $\pm{0.2}$     81.5 $\pm{\textbf{0.4}}$

Avg    71.1     67.4     71.3

Weighted MDD.
The proposed MADG algorithm calculates the Transfer loss as the arithmetic sum of the `j' MDD losses.  This section analyzes the effect on the model's performance using a weighted ($w$) arithmetic sum. The different weights used in this section are $w_l = \frac{1}{N_\mathcal{S}}\text{, }\forall l = 1\dots j$(Average) and  $w_l = \frac{MDD_L}{\sum_{l=1}^{j}MDD_l}$ (Dynamic).  The performance of the MADG algorithm using different weights is reported in Table <ref>. The model with $w_l = 1\text{, }\forall l = 1\dots j$ performs better than other weight values as reported in Table <ref>.

§ CONCLUSION

This study presented a novel adversarial algorithm for DG called MADG.

Accuracy(%) of the MADG with different $w_l$ values. One: $w_l = 1$, Avg.=Average, Dyn.=Dynamic

One   Avg.   Dyn.

P    97.7    97.8    97.6

A     87.8     87.3     87.5

C     82.2     82.0     82.4

S     78.3     77.4     77.2

Avg    86.5     86.1     86.2

Our approach is inspired by a theoretical framework that formulates the relationship between the source and unseen domains in real-valued hypothesis space. We used the margin loss function and Rademacher complexity framework to develop a generalization bound, which is informative. The proposed bound also shows a dependency between the margin value and the generalization error, which can be easily translated into an algorithm. To this end, we developed the MADG algorithm that leverages the MDD metric with minimax optimization to learn domain-invariant features and generalize well to the unseen domain. The algorithm was studied on five well-known DG benchmark datasets and reported consistent performance across all datasets as compared to other methods. We also report several empirical analyses and ablation studies.

§ ACKNOWLEDGMENTS

The research of AD is supported in part by the Prime Minister Research Fellowship, Ministry of Education, Government of India. The research of LRC is supported by the Indo-Norwegian Collaboration in Autonomous Cyber-Physical Systems (INCAPS) project: 287918 of the International Partnerships for Excellent Education, Research and Innovation (INTPART) program and the Low-Altitude UAV Communication and Tracking (LUCAT) project: 280835 of the IKTPLUSS program from the Research Council of Norway. The research of AK is supported by TiHAN Faculty Fellowship. VNB would like to acknowledge the support through the Govt of India SERB IMPRINT and DST ICPS funding programs for this work. We are grateful to the anonymous reviewers for the feedback that helped improved the presentation of this paper.

[1]
K. Aggarwal, S. K. Singh, M. Chopra, S. Kumar, and F. Colace, “Deep learning in robotics for strengthening industry 4.0.: opportunities, challenges and future directions,” Robotics and AI for Cybersecurity and Critical Infrastructure in Smart Cities, pp. 1–19, 2022.

[2]
M. Tsuneki, “Deep learning models in medical image analysis,” Journal of Oral Biosciences, vol. 64, no. 3, pp. 312–320, 2022.

[3]
T. Ayoub Shaikh, T. Rasool, and F. Rasheed Lone, “Towards leveraging the role of machine learning and artificial intelligence in precision agriculture and smart farming,” Computers and Electronics in Agriculture, vol. 198, p. 107119, 2022.

[4]
J. Quionero-Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence, Dataset Shift in Machine Learning.1em plus 0.5em minus 0.4emThe MIT Press, 2009.

[5]
J. Wang, C. Lan, C. Liu, Y. Ouyang, T. Qin, W. Lu, Y. Chen, W. Zeng, and P. Yu, “Generalizing to unseen domains: A survey on domain generalization,” IEEE Transactions on Knowledge and Data Engineering, 2022.

[6]
Y. Zhang, “A survey of unsupervised domain adaptation for visual recognition,” arXiv preprint arXiv:2112.06745, 2021.

[7]
X. Liu, C. Yoo, F. Xing, H. Oh, G. El Fakhri, J.-W. Kang, J. Woo et al., “Deep unsupervised domain adaptation: A review of recent advances and perspectives,” APSIPA Transactions on Signal and Information Processing, vol. 11, no. 1, 2022.

[8]
G. Blanchard, G. Lee, and C. Scott, “Generalizing from several related classification tasks to a new unlabeled sample,” in Advances in Neural Information Processing Systems, vol. 24, 2011.

[9]
T. Matsuura and T. Harada, “Domain generalization using a mixture of multiple latent domains,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, 2020, pp. 11 749–11 756.

[10]
S. Lin, C.-T. Li, and A. C. Kot, “Multi-domain adversarial feature generalization for person re-identification,” IEEE Transactions on Image Processing, vol. 30, pp. 1596–1607, 2020.

[11]
Z. Deng, F. Ding, C. Dwork, R. Hong, G. Parmigiani, P. Patil, and P. Sur, “Representation via representations: Domain generalization via adversarially learned invariant representations,” arXiv preprint arXiv:2006.11478, 2020.

[12]
S. Zhao, M. Gong, T. Liu, H. Fu, and D. Tao, “Domain generalization via entropy regularization,” Advances in Neural Information Processing Systems, vol. 33, pp. 16 096–16 107, 2020.

[13]
K. Akuzawa, Y. Iwasawa, and Y. Matsuo, “Adversarial invariant feature learning with accuracy constraint for domain generalization,” in Machine Learning and Knowledge Discovery in Databases: European Conference.1em plus 0.5em minus 0.4emSpringer, 2020, pp. 315–331.

[14]
E. Rosenfeld, P. Ravikumar, and A. Risteski, “An online learning approach to interpolation and extrapolation in domain generalization,” in International Conference on Artificial Intelligence and Statistics.1em plus 0.5em minus 0.4emPMLR, 2022, pp. 2641–2657.

[15]
M.-H. Bui, T. Tran, A. Tran, and D. Phung, “Exploiting domain-specific features to enhance domain generalization,” Advances in Neural Information Processing Systems, vol. 34, pp. 21 189–21 201, 2021.

[16]
V. Narayanan, A. A. Deshmukh, U. Dogan, and V. N. Balasubramanian, “On challenges in unsupervised domain generalization,” in NeurIPS 2021 Workshop on Pre-registration in Machine Learning.1em plus 0.5em minus 0.4emPMLR, 2022, pp. 42–58.

[17]
Y. Shu, Z. Cao, C. Wang, J. Wang, and M. Long, “Open domain generalization with domain-augmented meta-learning,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 9624–9633.

[18]
J. Yuan, X. Ma, D. Chen, K. Kuang, F. Wu, and L. Lin, “Label-efficient domain generalization via collaborative exploration and generalization,” in Proceedings of the 30th ACM International Conference on Multimedia, 2022, pp. 2361–2370.

[19]
S. Paul, T. Dutta, and S. Biswas, “Universal cross-domain retrieval: Generalizing across classes and domains,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 12 056–12 064.

[20]
Q. Xu, R. Zhang, Y. Zhang, Y. Wang, and Q. Tian, “A fourier-based framework for domain generalization,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 14 383–14 392.

[21]
Z. Li, Z. Cui, S. Wang, Y. Qi, X. Ouyang, Q. Chen, Y. Yang, Z. Xue, D. Shen, and J.-Z. Cheng, “Domain generalization for mammography detection via multi-style and multi-view contrastive learning,” in Medical Image Computing and Computer Assisted Intervention–MICCAI Proceedings, 2021, pp. 98–108.

[22]
D. Kim, Y. Yoo, S. Park, J. Kim, and J. Lee, “Selfreg: Self-supervised contrastive regularization for domain generalization,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 9619–9628.

[23]
Y. Chen, Y. Wang, Y. Pan, T. Yao, X. Tian, and T. Mei, “A style and semantic memory mechanism for domain generalization,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 9164–9173.

[24]
D. Li, H. Gouk, and T. Hospedales, “Finding lost dg: Explaining domain generalization via model complexity,” arXiv preprint arXiv:2202.00563, 2022.

[25]
M. Zhang, H. Marklund, N. Dhawan, A. Gupta, S. Levine, and C. Finn, “Adaptive risk minimization: Learning to adapt to domain shift,” Advances in Neural Information Processing Systems, vol. 34, pp. 23 664–23 678, 2021.

[26]
A. Nasery, S. Thakur, V. Piratla, A. De, and S. Sarawagi, “Training for the future: A simple gradient interpolation loss to generalize along time,” Advances in Neural Information Processing Systems, vol. 34, pp. 19 198–19 209, 2021.

[27]
J. Cha, S. Chun, K. Lee, H.-C. Cho, S. Park, Y. Lee, and S. Park, “Swad: Domain generalization by seeking flat minima,” Advances in Neural Information Processing Systems, vol. 34, pp. 22 405–22 418, 2021.

[28]
A. Robey, G. J. Pappas, and H. Hassani, “Model-based domain generalization,” Advances in Neural Information Processing Systems, vol. 34, pp. 20 210–20 229, 2021.

[29]
J. Cha, K. Lee, S. Park, and S. Chun, “Domain generalization by mutual-information regularization with pre-trained models,” in Proceedings of the European Conference on Computer Vision (ECCV), 2022, pp. 440–457.

[30]
C. Fang, Y. Xu, and D. N. Rockmore, “Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias,” in 2013 IEEE International Conference on Computer Vision, 2013, pp. 1657–1664.

[31]
D. Li, Y. Yang, Y.-Z. Song, and T. M. Hospedales, “Deeper, broader and artier domain generalization,” in Proceedings of the IEEE international conference on computer vision, 2017, pp. 5542–5550.

[32]
H. Venkateswara, J. Eusebio, S. Chakraborty, and S. Panchanathan, “Deep hashing network for unsupervised domain adaptation,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 5018–5027.

[33]
S. Beery, G. Van Horn, and P. Perona, “Recognition in terra incognita,” in Proceedings of the European conference on computer vision (ECCV), 2018, pp. 456–473.

[34]
X. Peng, Q. Bai, X. Xia, Z. Huang, K. Saenko, and B. Wang, “Moment matching for multi-source domain adaptation,” in Proceedings of the IEEE/CVF international conference on computer vision, 2019, pp. 1406–1415.

[35]
I. Gulrajani and D. Lopez-Paz, “In search of lost domain generalization,” in 9th International Conference on Learning Representations, ICLR, 2021.

[36]
A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf, “Covariate Shift by Kernel Mean Matching,” in Dataset Shift in Machine Learning.1em plus 0.5em minus 0.4emThe MIT Press, 2008.

[37]
J. Lin, Y. Tang, J. Wang, and W. Zhang, “Mitigating both covariate and conditional shift for domain generalization,” in 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems (CCIS).1em plus 0.5em minus 0.4emIEEE, 2022, pp. 437–443.

[38]
S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan, “A theory of learning from different domains,” Machine learning, vol. 79, no. 1, pp. 151–175, 2010.

[39]
V. Koltchinskii and D. Panchenko, “Empirical margin distributions and bounding the generalization error of combined classifiers,” The Annals of Statistics, vol. 30, no. 1, pp. 1–50, 2002.

[40]
Y. Zhang, T. Liu, M. Long, and M. Jordan, “Bridging theory and algorithm for domain adaptation,” in Proceedings of the 36th International Conference on Machine Learning, vol. 97, 2019, pp. 7404–7413.

[41]
P. L. Bartlett and S. Mendelson, “Rademacher and gaussian complexities: Risk bounds and structural results,” Journal of Machine Learning Research, vol. 3, no. Nov, pp. 463–482, 2002.

[42]
M. M. Rahman, C. Fookes, M. Baktashmotlagh, and S. Sridharan, “Correlation-aware adversarial domain adaptation and generalization,” Pattern Recognition, vol. 100, p. 107124, 2020.

[43]
G. Blanchard, G. Lee, and C. Scott, “Generalizing from several related classification tasks to a new unlabeled sample,” Advances in neural information processing systems, vol. 24, 2011.

[44]
K. Muandet, D. Balduzzi, and B. Schölkopf, “Domain generalization via invariant feature representation,” in International conference on machine learning.1em plus 0.5em minus 0.4emPMLR, 2013, pp. 10–18.

[45]
A. A. Deshmukh, Y. Lei, S. Sharma, U. Dogan, J. W. Cutler, and C. Scott, “A generalization error bound for multi-class domain generalization,” arXiv preprint arXiv:1905.10392, 2019.

[46]
S. Hu, K. Zhang, Z. Chen, and L. Chan, “Domain generalization via multidomain discriminant analysis,” in Uncertainty in Artificial Intelligence.1em plus 0.5em minus 0.4emPMLR, 2020, pp. 292–302.

[47]
G. Blanchard, A. A. Deshmukh, Ü. Dogan, G. Lee, and C. Scott, “Domain generalization by marginal transfer learning,” The Journal of Machine Learning Research, vol. 22, no. 1, pp. 46–100, 2021.

[48]
I. Albuquerque, J. Monteiro, M. Darvishi, T. H. Falk, and I. Mitliagkas, “Generalizing to unseen domains via distribution matching,” arXiv preprint arXiv:1911.00804, 2019.

[49]
H. Ye, C. Xie, T. Cai, R. Li, Z. Li, and L. Wang, “Towards a theoretical framework of out-of-distribution generalization,” Advances in Neural Information Processing Systems, vol. 34, pp. 23 519–23 531, 2021.

[50]
R. Vedantam, D. Lopez-Paz, and D. J. Schwab, “An empirical investigation of domain generalization with empirical risk minimizers,” Advances in Neural Information Processing Systems, vol. 34, pp. 28 131–28 143, 2021.

[51]
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of machine learning.1em plus 0.5em minus 0.4emMIT press, 2018.

[52]
Y. Ganin and V. Lempitsky, “Unsupervised domain adaptation by backpropagation,” in International conference on machine learning.1em plus 0.5em minus 0.4emPMLR, 2015, pp. 1180–1189.

[53]
A. Rame, C. Dancette, and M. Cord, “Fishr: Invariant gradient variances for out-of-distribution generalization,” in International Conference on Machine Learning.1em plus 0.5em minus 0.4emPMLR, 2022, pp. 18 347–18 377.

[54]
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.

[55]
O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein et al., “Imagenet large scale visual recognition challenge,” International journal of computer vision, vol. 115, pp. 211–252, 2015.

[56]
N. Qian, “On the momentum term in gradient descent learning algorithms,” Neural networks, vol. 12, no. 1, pp. 145–151, 1999.

[57]
V. N. Vapnik, “An overview of statistical learning theory,” IEEE transactions on neural networks, vol. 10, no. 5, pp. 988–999, 1999.

[58]
B. Sun and K. Saenko, “Deep coral: Correlation alignment for deep domain adaptation,” in Computer Vision–ECCV 2016 Workshops: Amsterdam, The Netherlands, October 8-10 and 15-16, 2016, Proceedings, Part III 14.1em plus 0.5em minus 0.4emSpringer, 2016, pp. 443–450.

[59]
Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky, “Domain-adversarial training of neural networks,” The journal of machine learning research, vol. 17, no. 1, pp. 2096–2030, 2016.

[60]
Y. Li, X. Tian, M. Gong, Y. Liu, T. Liu, K. Zhang, and D. Tao, “Deep domain generalization via conditional invariant adversarial networks,” in Proceedings of the European conference on computer vision (ECCV), 2018, pp. 624–639.

[61]
D. Li, Y. Yang, Y.-Z. Song, and T. Hospedales, “Learning to generalize: Meta-learning for domain generalization,” in Proceedings of the AAAI conference on artificial intelligence, vol. 32, 2018.

[62]
H. Li, S. J. Pan, S. Wang, and A. C. Kot, “Domain generalization with adversarial feature learning,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 5400–5409.

[63]
M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz, “Invariant risk minimization,” arXiv preprint arXiv:1907.02893, 2019.

[64]
S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang, “Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization,” arXiv preprint arXiv:1911.08731, 2019.

[65]
S. Yan, H. Song, N. Li, L. Zou, and L. Ren, “Improve unsupervised domain adaptation with mixup training,” arXiv preprint arXiv:2001.00677, 2020.

[66]
M. Zhang, H. Marklund, A. Gupta, S. Levine, and C. Finn, “Adaptive risk minimization: A meta-learning approach for tackling group shift,” arXiv preprint arXiv:2007.02931, vol. 8, p. 9, 2020.

[67]
Z. Huang, H. Wang, E. P. Xing, and D. Huang, “Self-challenging improves cross-domain generalization,” in Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part II 16.1em plus 0.5em minus 0.4emSpringer, 2020, pp. 124–140.

[68]
H. Nam, H. Lee, J. Park, W. Yoon, and D. Yoo, “Reducing domain gap by reducing style bias,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 8690–8699.

[69]
D. Krueger, E. Caballero, J.-H. Jacobsen, A. Zhang, J. Binas, D. Zhang, R. Le Priol, and A. Courville, “Out-of-distribution generalization via risk extrapolation (rex),” in International Conference on Machine Learning.1em plus 0.5em minus 0.4emPMLR, 2021, pp. 5815–5826.

[70]
G. Parascandolo, A. Neitz, A. Orvieto, L. Gresele, and B. Schölkopf, “Learning explanations that are hard to vary,” in 9th International Conference on Learning Representations, ICLR, 2021.

[71]
Y. Shi, J. Seely, P. H. Torr, N. Siddharth, A. Hannun, N. Usunier, and G. Synnaeve, “Gradient matching for domain generalization,” arXiv preprint arXiv:2104.09937, 2021.

[72]
S. Shahtalebi, J.-C. Gagnon-Audet, T. Laleh, M. Faramarzi, K. Ahuja, and I. Rish, “Sand-mask: An enhanced gradient masking strategy for the discovery of invariances in domain generalization,” ArXiv, vol. abs/2106.02266, 2021.

[73]
G. Zhang, H. Zhao, Y. Yu, and P. Poupart, “Quantifying and improving transferability in domain generalization,” Advances in Neural Information Processing Systems, vol. 34, pp. 10 957–10 970, 2021.

[74]
M. Pezeshki, O. Kaba, Y. Bengio, A. C. Courville, D. Precup, and G. Lajoie, “Gradient starvation: A learning proclivity in neural networks,” Advances in Neural Information Processing Systems, vol. 34, pp. 1256–1272, 2021.