# Automatic Domain Adaptation
by Transformers in In-Context Learning

Ryuichiro Hataya
RIKEN AIP
<EMAIL_ADDRESS>
Kota Matsui
Nagoya University
<EMAIL_ADDRESS>
Masaaki Imaizumi
The University of Tokyo & RIKEN AIP
<EMAIL_ADDRESS>
###### Abstract

Selecting or designing an appropriate domain adaptation algorithm for a given
problem remains challenging. This paper presents a Transformer model that can
provably approximate and opt for domain adaptation methods for a given dataset
in the in-context learning framework, where a foundation model performs new
tasks without updating its parameters at test time. Specifically, we prove
that Transformers can approximate instance-based and feature-based
unsupervised domain adaptation algorithms and automatically select an
algorithm suited for a given dataset. Numerical results indicate that in-
context learning demonstrates an adaptive domain adaptation surpassing
existing methods.

##  1 Introduction

Domain adaptation provides a methodology for transferring “knowledge” obtained
in one domain to another related domain (Ben-David et al., 2010). In
particular, the _unsupervised domain adaptation (UDA)_ setting allows for
training of the predictive model using the rich labeled data in the source
domain, when there is no labeled data in the target domain. Such methods are
vital in the areas where sample sizes are inherently small, such as in the
medical field, and numerous studies have been reported focusing on domain
adaptation for medical image analysis, for example (Guan & Liu, 2021). In this
study, we focus in particular on instance-based and feature-based unsupervised
domain adaptation methods.

One of the challenges associated with domain adaptation is selecting and
differentiating effective methods. There are many existing approaches in
domain adaptation, such as the instance-based methods (Dai et al., 2007;
Sugiyama et al., 2007; Kanamori et al., 2009) and the feature-based
methods(Daumé III, 2009; Ganin et al., 2016). However, when each method is
effective differs based on data. Specifically, the instance-based methods
(Sugiyama et al., 2007; Kanamori et al., 2009) are effective when there exists
a valid density ratio between covariates of the source and target domains,
whilst the feature-based methods are effective if we can find a domain-
invariant representation on a common feature space between the domains. To
properly select an appropriate approach to the given data, it is essential to
assess whether they meet the specific conditions of each method.

There have been some attempts to automatically select appropriate UDA
algorithms. For example, _learning to transfer (L2T)_ (Ying et al., 2018)
employs a meta-learning approach to predict appropriate features to transfer
for a given pair of source and target domains. In addition to L2T, _meta-
transfer learning_ (Sun et al., 2019) and _CNAPS_ (Requeima et al., 2019),
which learn functions to adjust weights of trained neural nets in a task-
adaptive manner, have been proposed, and thus algorithm selection based on
meta-learning have achieved some success. However, these existing methods have
been developed only for selection within specific frameworks, such as feature-
based domain adaptation. That is, the possibility of cross-framework algorithm
selection, such as “choosing which of the instances and features to transfer”
was unknown.

As a method for developing versatile algorithms, the in-context learning
ability of foundation models has garnered significant attention. In-context
learning, a form of meta-learning in foundational models, allows models to
adapt to new tasks without updating their parameters. In particular, the
capabilities of Transformers in in-context learning have been intensively
surveyed: for example, Bai et al. (2023) showed that Transformers can learn
algorithms such as gradient descent, as well as their optimal selection
methods. Such in-context learning abilities of Transformers have been
validated from both experimental and theoretical aspects (Garg et al., 2022;
Li et al., 2023; Von Oswald et al., 2023; Akyürek et al., 2022; Xie et al.,
2021; Zhang et al., 2023; Bai et al., 2023; Lin et al., 2023; Ahn et al.,
2024; Raventós et al., 2024).

In this study, we demonstrate that Transformer models effectively address the
challenge in in-context learning. Specifically, our analysis reveals that
Transformers in the framework (i) solve domain adaptation problems by
approximating the main UDA algorithms, and (ii) automatically select suitable
methods adaptively to the dataset’s characteristics. The results indicate that
Transformers can, in context, not only implement various transfer learning
methods but also possess the capability to appropriately select among them.
These findings suggest that by accurately choosing a combination of these
methods based on the dataset, performance can be enhanced beyond what is
achievable by applying the methods individually.

Our specific contributions are as follows:

  1. 1.

We demonstrate that the Transformer can approximate the instance-based
transfer learning method based on importance weighting with the uLSIF
estimator, which utilizes the density ratio to address covariate shift. We
prove that Transformers internally learn the density ratio, effectively
implementing uLSIF and importance weighting. A technical contribution of this
proof is showing how Transformers can approximate the computation of inverse
matrices multiplication required for uLSIF.

  2. 2.

We show that Transformers can approximate the feature-based transfer learning
method DANN, which uses adversarial learning. Within their architecture,
Transformers solve the minimax optimization using a dual-loop mechanism. A
significant technical contribution is developing the components that compute
this dual-loop.

  3. 3.

We numerically demonstrate that Transformers trained with in-context learning
perform better in domain adaptation tasks than separate existing methods. This
empirically proves that Transformers can adaptively handle complex transfer
learning tasks.

##  2 Preliminary

###  2.1 Unsupervised Domain Adaptation

Setup

We consider the _Unsupervised domain adaptation (UDA)_ problem with two
domains. Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a compact input space and
$\mathcal{Y}$ be an output space. Then, the source and the target domains,
$P_{S}$ and $P_{T}$, are distributions on $\mathcal{X}\times\mathcal{Y}$, let
their density functions be $p_{S}$ and $p_{T}$, and their marginal
distributions on $\mathcal{X}$ be $P_{S}^{X}$ and $P_{T}^{X}$. Denote
$\mathcal{D}_{S}=\\{({\bm{x}}^{S}_{i},y^{S}_{i})\\}_{i=1}^{n}$ and
$\mathcal{D}_{T}=\\{{\bm{x}}^{T}_{i}\\}_{i=1}^{n^{\prime}}$ for the source
labeled data and target unlabeled data, respectively and let $N\coloneqq
n+n^{\prime}$. Given a loss function
$\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}_{\geq 0}$ and a hypothesis
space $\mathcal{F}$, UDA aims to minimize the target risk
$\operatorname*{argmin}_{f\in\mathcal{F}}R_{T}(f)$, where
$R_{T}(f)\coloneqq\mathbb{E}_{({\bm{x}},y)\sim P_{T}}[\ell(f({\bm{x}}),y)]$ is
the target risk, without observing labels of the data from the target domain.
To this end, UDA methods aim to match the source and target distributions in
the feature space, categorized into instance-based and feature-based
approaches.

Instance-based Methods

Instance-based approaches reweight instances from the source domain to
minimize the target risk, based on the following transferability assumption
called _covariate shift_.

######  Assumption 1 (Covariate Shift, Shimodaira (2000)).

Suppose that the distribution of $y$ conditioned on the input ${\bm{x}}$ is
the same in the source and target domains, i.e.,

$p_{S}(y|{\bm{x}})=p_{T}(y|{\bm{x}}).$ (1)

Under this assumption, $R_{T}(f)=\mathbb{E}_{({\bm{x}},y)\sim
P_{S}}(q({\bm{x}})\ell(f({\bm{x}}),y))$ holds, where
$q({\bm{x}})=p_{T}({\bm{x}})/p_{S}({\bm{x}})$ is the density ratio between the
marginal distributions of source and target. Then, _Importance-weighted
learning (IWL)_ Sugiyama et al. (2012); Kimura & Hino (2024) obtains
$\operatorname*{argmin}_{f\in\mathcal{F}}R_{T}(f)$ in two steps:  1.
Empirically learn an estimator of the density ratio $\widehat{q}$ using
$\\{{\bm{x}}_{i}^{S}\\}_{i=1}^{n}$ and $\mathcal{D}_{T}$, and then,  2.
minimize the weighted empirical risk
$\widehat{R}_{T}(f)=\frac{1}{n}\sum_{i=1}^{n}\widehat{q}({\bm{x}}^{S}_{i})\ell(f({\bm{x}}^{S}_{i}),y^{S}_{i})$
consists of data from the source domain.

Here, we introduce _unconstrained Least-Squares Importance Fitting (uLSIF)_
Kanamori et al. (2009), a method for density-ratio estimation. Firstly, the
density ratio is estimated by the linear basis function model

$\widehat{q}_{\bm{\alpha}}({\bm{x}})={\bm{\alpha}}^{\top}{\bm{\phi}}({\bm{x}})=\sum_{j=1}^{J}\alpha_{j}\phi_{j}({\bm{x}}),$
(2)

where ${\bm{\alpha}}=[\alpha_{1},\dots,\alpha_{J}]$ and
${\bm{\phi}}=[\phi_{1},\dots,\phi_{J}]$ are parameter and feature vectors
respectively, where $\phi_{j}:\mathcal{X}\mapsto\mathbb{R}$ are feature maps
for an input ${\bm{x}}$. uLSIF estimates the weight ${\bm{\alpha}}$ to
directly minimize the following squared error:

$L({\bm{\alpha}})=\frac{1}{2}\int_{\mathcal{X}}(\widehat{q}_{\bm{\alpha}}({\bm{x}})-q({\bm{x}}))^{2}p_{S}({\bm{x}})\mathrm{d}{\bm{x}}=\int_{\mathcal{X}}\left\\{\frac{1}{2}\widehat{q}_{\bm{\alpha}}({\bm{x}})^{2}p_{S}({\bm{x}})-\widehat{q}_{\bm{\alpha}}p_{T}({\bm{x}})+\frac{1}{2}q({\bm{x}})^{2}p_{T}({\bm{x}})\right\\}\mathrm{d}{\bm{x}}.$
(3)

As the third term of the RHS is constant to ${\bm{\alpha}}$, we can estimate
${\bm{\alpha}}$ as
$\widehat{{\bm{\alpha}}}=\operatorname*{argmin}_{{\bm{\alpha}}\geq
0}\widehat{L}({\bm{\alpha}})$ such that

$\widehat{L}({\bm{\alpha}})=\frac{1}{2n}\sum_{i=1}^{n}(\widehat{q}_{\bm{\alpha}}({\bm{x}}))^{2}-\frac{1}{n^{\prime}}\sum_{i=1}^{n^{\prime}}\widehat{q}_{\bm{\alpha}}({\bm{x}})+\frac{\lambda}{2}\left\lVert{\bm{\alpha}}\right\rVert^{2}_{2}=\frac{1}{2}{\bm{\alpha}}^{\top}{\bm{\Psi}}{\bm{\alpha}}-{\bm{\psi}}^{\top}{\bm{\alpha}}+\frac{\lambda}{2}{\bm{\alpha}}^{\top}{\bm{\alpha}},$
(4)

where $\lambda>0$ is a regularization parameter,
$\Psi_{jj^{\prime}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\phi_{j}({\bm{x}}_{i}^{S})\phi_{j^{\prime}}({\bm{x}}_{i}^{S})$
and
$\psi_{j}\coloneqq\frac{1}{n^{\prime}}\sum_{i=1}^{n^{\prime}}\phi_{j}({\bm{x}}_{i}^{T})$.
Then, if $\mathcal{F}$ is a space of linear model, we can obtain a classifier
with an empirical importance-weighted problem:

$\displaystyle{\bm{w}}^{*}=\operatorname*{argmin}_{{\bm{w}}\in\mathbb{R}^{J}}\widehat{R}_{T}({\bm{w}}),~{}\widehat{R}_{T}({\bm{w}}):=\sum_{({\bm{x}},y)\in\mathcal{D}_{S}}\widehat{q}_{\widehat{{\bm{\alpha}}}}({\bm{x}})\ell({\bm{w}}^{\top}{\bm{\phi}}({\bm{x}}),y).$
(5)

Then, we obtain a classifier defined as

$\displaystyle\widehat{f}^{\mathrm{IWL}}({\bm{x}}):=({\bm{w}}^{*})^{\top}\phi({\bm{x}}).$
(6)

Feature-based Methods

A feature-based method learns a domain-invariant feature map
$\phi:\mathcal{X}\to\mathcal{X}^{\prime}$, where $\mathcal{X}^{\prime}$ is a
feature space, so that $R_{T}(f^{\prime})\approx\mathbb{E}_{({\bm{x}},y)\sim
P_{S}}\ell(f^{\prime}(\phi({\bm{x}})),y)$, where
$f^{\prime}:\mathcal{X}^{\prime}\to\mathcal{Y}$. The _domain adversarial
neural network (DANN)_ (Ganin et al., 2016) is a typical method to achieve
this by using adversarial learning. DANN consists of three modules, a feature
extractor $f_{F}:\mathcal{X}\to\mathcal{X}^{\prime}$, a label classifier
$f_{L}:\mathcal{X}^{\prime}\to[0,1]$, and a domain discriminator
$f_{D}:\mathcal{X}^{\prime}\to[0,1]$, parameterized by
${\bm{\theta}}_{F},{\bm{\theta}}_{L},{\bm{\theta}}_{D}$, respectively. Then, a
classifier $f_{L}$ with an invariant feature extractor $f_{F}$ can be obtained
by solving the following minimax problem:

$\displaystyle\min_{{\bm{\theta}}_{F},{\bm{\theta}}_{L}}\max_{{\bm{\theta}}_{D}}L({\bm{\theta}}_{F},{\bm{\theta}}_{L})-\lambda\Omega({\bm{\theta}}_{F},{\bm{\theta}}_{D}).$
(7)

where $\lambda>0$ is a regularization parameter,
$L({\bm{\theta}}_{F},{\bm{\theta}}_{L})\coloneqq\sum_{({\bm{x}},y)\in\mathcal{D}_{S}}\gamma(f_{L}\circ
f_{F}({\bm{x}}),y)$ is label classification loss and
$\Omega({\bm{\theta}}_{F},{\bm{\theta}}_{D})\coloneqq\frac{1}{n}\sum_{({\bm{x}},y)\in\mathcal{D}_{S}}\gamma(f_{D}\circ
f_{F}({\bm{x}}),0)+\frac{1}{n^{\prime}}\sum_{({\bm{x}},y)\in\mathcal{D}_{T}}\gamma(f_{D}\circ
f_{F}({\bm{x}}),1)$ is domain classification loss. Here,
$\gamma(p,q)\coloneqq-q\log p-(1-q)\log(1-p)$ for $p,q\in[0,1]$ is a sigmoid
cross entropy function. The model parameters are updated by gradient descent
with a learning rate of $\eta$ as follows:

$\displaystyle{\bm{\theta}}_{F}$
$\displaystyle\leftarrow{\bm{\theta}}_{F}-\eta\nabla_{{\bm{\theta}}_{F}}\left(L({\bm{\theta}}_{F},{\bm{\theta}}_{L})-\lambda\Omega({\bm{\theta}}_{F},{\bm{\theta}}_{D})\right),$
(8) $\displaystyle{\bm{\theta}}_{L}$
$\displaystyle\leftarrow{\bm{\theta}}_{L}-\eta\nabla_{{\bm{\theta}}_{L}}L({\bm{\theta}}_{F},{\bm{\theta}}_{L}),$
(9) $\displaystyle{\bm{\theta}}_{D}$
$\displaystyle\leftarrow{\bm{\theta}}_{D}-\eta\lambda\nabla_{{\bm{\theta}}_{D}}\Omega({\bm{\theta}}_{F},{\bm{\theta}}_{D}).$
(10)

###  2.2 In-context Learning

Setup.

In in-context learning, a fixed Transformer observes a dataset
$\mathcal{D}=\\{({\bm{x}}_{i},y_{i})\\}_{i=1}^{N}\sim(P)^{N}$ with pairs of an
input ${\bm{x}}_{i}$ and its label $y_{i}$ from a joint distribution $P$ and a
new query input ${\bm{x}}_{*}$ then predicts $y_{*}$ corresponding to
${\bm{x}}_{*}$. Different from the standard supervised learning, in in-context
learning, the Transformer is pre-trained on other datasets
$\mathcal{D}^{\prime}$ from different distributions to learn an algorithm to
predict $y_{*}$. Unlike the standard meta learning, at the inference time of
in-context learning, the parameters of a Transformer are fixed. Our interest
is to study the expressive power of a Transformer model for algorithms on a
given dataset $\mathcal{D}$.

Transformer.

Define an $L$-layer Transformer consisting of $L$ Transformer layers as
follows. The $l$th Transformer layer maps an input matrix
${\bm{H}}^{(l)}\in\mathbb{R}^{D\times N}$ to
$\widetilde{{\bm{H}}}^{(l)}\in\mathbb{R}^{D\times N}$ and is composed of a
self-attention block and a feed-forward block. The self-attention block
$\mathrm{Attn}^{(l)}:\mathbb{R}^{D\times N}\to\mathbb{R}^{D\times N}$ is
parameterized by $D\times D$ matrices
$\\{({\bm{K}}^{(l)}_{m},{\bm{Q}}^{(l)}_{m},{\bm{V}}^{(l)}_{m})\\}_{m=1}^{M}$,
where $M$ is the number of heads, and defined as

$\mathrm{Attn}^{(l)}({\bm{X}})={\bm{X}}+\frac{1}{N}\sum_{m=1}^{M}{\bm{V}}^{(l)}_{m}{\bm{X}}\sigma(({\bm{Q}}^{(l)}_{m}{\bm{X}})^{\top}{\bm{K}}^{(l)}_{m}{\bm{X}}).$
(11)

$\sigma$ denotes an activation function applied elementwisely.

The feed-forward block $\mathrm{MLP}^{(l)}:\mathbb{R}^{D\times
N}\to\mathbb{R}^{D\times N}$ is a multi-layer perceptron with a skip
connection, parameterized by
$({\bm{W}}^{(l)}_{1},{\bm{W}}^{(l)}_{2})\in\mathbb{R}^{D^{\prime}\times
D}\times\mathbb{R}^{D\times D^{\prime}}$, such that

$\mathrm{MLP}^{(l)}({\bm{X}})={\bm{X}}+{\bm{W}}^{(l)}_{2}\varsigma({\bm{W}}^{(l)}_{1}{\bm{X}}),$
(12)

where $\varsigma$ is an activation function applied elementwisely. In this
paper, we let both $\sigma$ and $\varsigma$ the ReLU function in this paper,
following Bai et al. (2023).

In summary, an $L$-layer Transformer $\mathrm{TF}_{\bm{\theta}}$,
parameterized by

${\bm{\theta}}=\\{({\bm{K}}^{(l)}_{1},{\bm{Q}}^{(l)}_{1},{\bm{V}}^{(l)}_{1},\dots,{\bm{K}}^{(l)}_{M},{\bm{Q}}^{(l)}_{M},{\bm{V}}^{(l)}_{M},{\bm{W}}^{(l)}_{1},{\bm{W}}^{(l)}_{2})\\}_{l=1}^{L},$
(13)

is a composition of the abovementioned layers as

$\mathrm{TF}_{\bm{\theta}}({\bm{X}})=\mathrm{MLP}^{(L)}\circ\mathrm{Attn}^{(L)}\circ\dots\circ\mathrm{MLP}^{(1)}\circ\mathrm{Attn}^{(1)}({\bm{X}}).$
(14)

In the remaining text, the superscript to indicate the number of layer (l) is
sometimes omitted for brevity, and the $n$th columns of
${\bm{H}}^{(l)},\widetilde{{\bm{H}}}^{(l)}$ are denoted as
${\bm{h}}^{(l)}_{n},\widetilde{{\bm{h}}}^{(l)}_{n}$. Following Bai et al.
(2023), we define the following norm of a Transformer
$\mathrm{TF}_{\bm{\theta}}$:

$\left\lVert{\bm{\theta}}\right\rVert_{\mathrm{TF}}=\max_{l\in\\{1,\dots,L\\}}\left\\{\max_{m\in\\{1,\dots,M\\}}\left\\{\left\lVert{\bm{Q}}_{m}^{(l)}\right\rVert,\left\lVert{\bm{K}}_{m}^{(l)}\right\rVert\right\\}+\sum_{m=1}^{M}\left\lVert{\bm{V}}_{m}^{(l)}\right\rVert+\left\lVert{\bm{W}}_{1}^{(l)}\right\rVert+\left\lVert{\bm{W}}_{2}^{(l)}\right\rVert\right\\},$
(15)

where $\left\lVert\cdot\right\rVert$ for matrices indicates the operator norm
in this equation.

##  3 Approximating UDA Algorithms by Transformers

This section demonstrates that transformers in in-context learning have the
ability to approximate existing UDA algorithms. Specifically, we show that
transformers can approximate uLSIF-based IWL, an instance-based method, and
DANN, a feature-based method.

###  3.1 Setup and Notion

We consider in-context domain adaptation, where a fixed Transformer model is
given a tuple $(\mathcal{D}_{S},\mathcal{D}_{T},{\bm{x}}_{*})$, where
${\bm{x}}_{*}\sim p_{T}^{X}({\bm{x}})$, and predicts $y_{*}$ without updating
model parameters.

We construct the input matrix using both source and target data. Specifically,
we suppose the input data, namely
$({\bm{x}}_{i}^{S},y_{i}^{S})\in\mathcal{D}_{S}$ and
${\bm{x}}_{i}^{T}\in\mathcal{D}_{T}$, are encoded into
${\bm{H}}^{(1)}\in\mathbb{R}^{D\times(N+1)}$ as follows:

${\bm{H}}^{(1)}=\begin{bmatrix}{\bm{x}}_{1}&\ldots&{\bm{x}}_{n}&{\bm{x}}_{n+1}&\ldots&{\bm{x}}_{N}&{\bm{x}}_{N+1}\\\
y_{1}&\ldots&y_{n}&0&\ldots&0&0\\\
t_{1}&\ldots&t_{n}&t_{n+1}&\ldots&t_{N}&t_{N+1}\\\
s_{1}&\ldots&s_{n}&s_{n+1}&\ldots&s_{N}&s_{N+1}\\\ 1&\ldots&1&1&\ldots&1&1\\\
{\bm{0}}_{D-(d+4)}&\ldots&{\bm{0}}_{D-(d+4)}&{\bm{0}}_{D-(d+4)}&\ldots&{\bm{0}}_{D-(d+4)}&{\bm{0}}_{D-(d+4)}\end{bmatrix},$
(16)

where ${\bm{x}}_{i}={\bm{x}}_{i}^{S}$ and $y_{i}=y_{i}^{S}$ for $1\leq i\leq
n$, ${\bm{x}}_{i}={\bm{x}}_{i-n}^{T}$ for $n+1\leq i\leq N$,
${\bm{x}}_{N+1}={\bm{x}}_{*}$. $t_{i}=1$ for $1\leq i\leq n$ otherwise $0$ is
used to indicate which data point is from the source domain, and $s_{i}=1$ for
$1\leq i\leq N$ otherwise $0$ is used to mark training data. We further define
an output of a transformer for the prediction corresponding to
${\bm{x}}_{N+1}={\bm{x}}_{*}$. For an input ${\bm{H}}^{(1)}$ and its
corresponding output matrix $\mathrm{TF}_{\bm{\theta}}({\bm{H}}^{(1)})$, we
write its $(2,N+1)$-th element of $\mathrm{TF}_{\bm{\theta}}({\bm{H}}^{(1)})$
as $\mathrm{TF}^{*}_{\bm{\theta}}({\bm{H}}^{(1)})$.

We define the concepts necessary for our theoretical results. To approximate
smooth functions, such as loss functions $\ell$ and $\gamma$, we use the
following notion.

######  Definition 1 ($(\varepsilon,R,M,C)$-approximability by sum of ReLUs,
Bai et al. (2023)).

For $\varepsilon>0$ and $R\geq 1$, a function $g:\mathbb{R}^{k}\to\mathbb{R}$
is _$(\epsilon,R,M,C)$ -approximabile by sum of ReLUs_ if there exist a
function

$f({\bm{z}})=\sum_{m=1}^{M}c_{m}\sigma({\bm{a}}_{m}^{\top}{\bm{z}}+b_{m})\quad\text{with}~{}\sum_{m=1}^{M}\left\lvert
c_{m}\right\rvert\leq
C,~{}\max_{m\in\\{1,\dots,M\\}}\left\lVert{\bm{a}}\right\rVert_{1}+b_{m}\leq
1,$ (17)

where ${\bm{a}}_{m}\in\mathbb{R}^{k},b_{m}\in\mathbb{R},c_{m}\in\mathbb{R},$,
such that $\sup_{{\bm{z}}\in[-R,R]^{k}}\left\lvert
g({\bm{z}})-f({\bm{z}})\right\rvert\leq\varepsilon$.

All functions approximated in this paper are included in this class. To use
this, we suppose $\left\lVert{\bm{x}}_{i}\right\rVert\leq B_{x}$ and
$\left\lVert y_{i}\right\rVert\leq B_{y}$ for any $i\in\\{1,\dots,N+1\\}$, and
$\left\lVert{\bm{w}}\right\rVert\leq B_{w}$ for a model weight ${\bm{w}}$ in
in-context learning. Additionally, for the feature map of IWL, we suppose
$\left\lVert{\bm{\phi}}\right\rVert\leq 1$ so that
$\left\lVert{\bm{\phi}}({\bm{x}})\right\rVert\leq B_{x}$.

###  3.2 In-context IWL with uLSIF

We show a transformer in the ICL scheme can approximate the uLSIF estimator-
based IWL algorithm, which we refer to as IWL in the following.

In this section, we consider the following setup: Fix any $B_{w}>0$,
$B_{\alpha}>0$, $L_{1},L_{2}>0$, $\eta_{1}$, and $\eta_{2}$. Given a loss
function $\ell$ that is convex in the first argument, and $\nabla_{1}\ell$ is
$(\epsilon,R,M,C)$-approximable by the sum of ReLUs with
$R=\max(B_{w}B_{x},B_{y},1)$. We first state the main result of this section.
This theorem shows that the transformer has the performance to function as an
algorithm almost equivalent to IWL for any input ${\bm{x}}_{*}$. Note that the
query ${\bm{x}}_{*}$ is encoded in the input matrix ${\bm{H}}^{(1)}$ defined
in (16).

######  Theorem 1.

Consider $\widehat{f}^{\mathrm{IWL}}$ with ${\bm{\phi}}$ which is approximable
by a sum of ReLUs. Fix $\varepsilon>0$ arbitrarily and set $L_{2}$ as
satisfying $0<\epsilon\leq B_{w}/2L_{2}$. Suppose that an input
$(\mathcal{D}_{S},\mathcal{D}_{T},{\bm{x}}_{*})$ satisfies that
$\sup_{{\bm{w}}:\left\lVert{\bm{w}}\right\rVert_{2}\leq
B_{w}}\lambda_{\max}(\nabla^{2}\widehat{R}_{T}({\bm{w}};\mathcal{D}_{S}))\leq\eta_{2}/2$
and the minimizer
${\bm{w}}^{*}\in\operatorname*{argmin}\widehat{R}_{T}({\bm{w}};\mathcal{D}_{S})$
satisfies $\left\lVert{\bm{w}}^{*}\right\rVert\leq B_{w}/2$. Then, there
exists a transformer $\mathrm{TF}_{\bm{\theta}}$ with $L_{1}+L_{2}+1$ layers
and $M$ heads which satisfies the following:

$\displaystyle\|\mathrm{TF}_{\bm{\theta}}^{*}({\bm{H}}^{(1)})-\widehat{f}^{\mathrm{IWL}}({\bm{x}}_{*})\|\leq\varepsilon.$
(18)

This result gives several implications. First, while transformers with ICL
have been shown to approximate algorithms for i.i.d. data Bai et al. (2023),
this theorem extends it to show the capability of handling domain shifts. This
extension is nontrivial since it requires showing that the Transformer can
express the algorithm’s ability of corrections for the domain shifts. Second,
this theorem shows that Transformers do not need to specify the feature map
${\bm{\phi}}(\cdot)$. Specifically, whatever feature map ${\bm{\phi}}(\cdot)$
is used for uLSIF, the transformer can approximate the uLSIF based on it. In
other words, pre-training a transformer induces a situation-specific feature
map ${\bm{\phi}}(\cdot)$.

#### Proof Outline

In our proof, we construct three types of sub-transformers and approximate
IWL-uLSIF by combining them. Specifically, the first sub-transformer with one
layer to construct a feature map ${\bm{\phi}}(\cdot)$, the second one
calculates ${\bm{\alpha}}$ with $L_{1}$ layers, and this one optimizes the
model weight ${\bm{w}}\in\mathbb{R}^{J}$ with $L_{2}$ layers. For simplicity,
we define a notation ${\bm{z}}_{i}=[{\bm{x}}_{i},y_{i},t_{i},s_{i},1]$. In the
following, we describe each approximation step by step. The full proof is
presented in Section A.1.

  1. Step 1:

Feature map approximation. First, we construct a transformer that approximates
the feature map ${\bm{\phi}}(\cdot)$. This construction is trivial under the
assumption that the feature map ${\bm{\phi}}(\cdot)$ is approximable by the
sum of ReLUs. For example, a self-attention block can construct a feature map
with the RBF kernel.

######  Lemma 1.

There exists a transformer with one layer which maps
${\bm{h}}_{i}^{(1)}=[{\bm{z}}_{i},{\bm{0}}_{J},{\bm{0}}_{D-(d+4)}]$ to
$\widetilde{{\bm{h}}}_{i}^{(1)}=[{\bm{z}}_{i},\widehat{{\bm{\phi}}}({\bm{x}}_{i}),{\bm{0}}_{D-J-(d+4)}]$
for $i=1,...,N+1$, such that
$\|{\bm{\phi}}-\widehat{{\bm{\phi}}}\|_{L^{\infty}}\leq\varepsilon$ holds.

  2. Step 2:

Density ratio parameter approximation. Second, we construct a transformer that
approximates $\widehat{{\bm{\alpha}}}$ that minimizes the loss
$\widehat{L}({\bm{\alpha}})$ in Eq. 4, in which a technical difficulty lies.
For the approximation, we define a sequence of parameters
$\\{{\bm{\alpha}}_{\mathrm{GD}}^{(l)}\\}_{l=1,2,...}$ that converge to
$\widehat{{\bm{\alpha}}}$, using an update equation by the gradient descent
algorithm:

$\displaystyle{\bm{\alpha}}_{\mathrm{GD}}^{(l+1)}={\bm{\alpha}}_{\mathrm{GD}}^{(l)}-\eta_{1}\nabla\widehat{L}({\bm{\alpha}}_{\mathrm{GD}}^{(l)}),~{}l=1,2,...,\mbox{~{}and~{}}{\bm{\alpha}}_{\mathrm{GD}}^{(1)}={\bm{0}}_{J}.$
(19)

Then, we develop a Transformer layer that exactly implements a single update
step of this equation. We give the following statement.

######  Lemma 2.

There exists a Transformer with $L_{1}$ layer which maps
$\widetilde{{\bm{h}}}_{i}^{(1)}=[{\bm{z}}_{i},{\bm{\phi}}({\bm{x}}_{i}),{\bm{0}}_{J},{\bm{0}}_{D-2J-(d+4)}]$
to
$\widetilde{{\bm{h}}}_{i}^{(L_{1}+1)}=[{\bm{z}}_{i},{\bm{\phi}}({\bm{x}}_{i}),\widetilde{{\bm{\alpha}}}^{(L_{1})},$
${\bm{0}}_{D-2J-(d+4)}]$ for $i=1,...,N+1$, such that
${{\bm{\alpha}}}_{\mathrm{GD}}^{(L_{1})}=\widetilde{{\bm{\alpha}}}^{(L_{1})}$.

We note that this approach with the gradient descent is more efficient in the
sense of layer size than the direct minimization of
$\widehat{L}({\bm{\alpha}})$ using an inverse matrix.

  3. Step 3:

Model parameter approximation. In this step, we employ a similar approach to
develop a Transformer that approximates ${\bm{w}}^{*}$, which is the minimizer
of $\widehat{R}_{T}({\bm{w}})$ in Eq. 5. To the aim, we define a sequence of
parameters $\\{{{\bm{w}}}_{\mathrm{GD}}^{(l)}\\}_{l=1,2,...}$ that converge to
${\bm{w}}^{*}$ by the gradient descent algorithm:

$\displaystyle{\bm{w}}_{\mathrm{GD}}^{(l+1)}={\bm{w}}_{\mathrm{GD}}^{(l)}-\eta_{2}\nabla\widehat{R}_{T}({\bm{w}}_{\mathrm{GD}}^{(l)}),~{}l=1,2,...,\text{~{}and~{}}{\bm{w}}_{\mathrm{GD}}^{(1)}={\bm{0}}_{J}.$
(20)

Then, we develop a Transformer layer that approximates this algorithm as
follows:

######  Lemma 3.

There exists a Transformer with $L_{2}$ layer which maps
$\widetilde{{\bm{h}}}_{i}^{(L_{1}+1)}=[{\bm{z}}_{i},{\bm{\phi}}({\bm{x}}_{i}),\widetilde{{\bm{\alpha}}}^{(L_{1})},{\bm{0}}_{D-2J-(d+4)}]$
to
$\widetilde{{\bm{h}}}_{i}^{(L_{1}+L_{2}+1)}=[{\bm{z}}_{i},{{\bm{\phi}}}({\bm{x}}_{i}),\widetilde{{\bm{\alpha}}}^{(L_{1})},\widetilde{{\bm{w}}}^{(L_{2})},0]$
for $i=1,...,N+1$, such that
$\|{{\bm{w}}}_{\mathrm{GD}}^{(L_{2})}-\widetilde{{\bm{w}}}^{(L_{2})}\|_{L^{\infty}}\leq\varepsilon
L_{2}\eta_{2}B_{x}$ holds.

Combining these layers constitutes the transformer that achieves the
approximation capability of Theorem 1. Importantly, this method requires as
many layers as there are iterations, but this can be shortened by using
regression coupling.

###  3.3 In-context DANN

We show the existence of a Transformer that can approximate DANN, presented in
Section 2.1.

At the beginning, we identify the structure of the DANN to be approximated.
First, we assume that a label classifier $f_{L}\circ f_{F}({\bm{x}})$ is
represented by a two-layer neural network model
$\Lambda({\bm{x}};{\bm{U}},{\bm{w}}):=\sum_{k=1}^{K}w_{k}r({\bm{u}}_{k}^{\top}{\bm{x}})$,
and the domain classifier $f_{D}\circ f_{F}({\bm{x}})$ also follows a similar
model
$\Delta({\bm{x}};{\bm{U}},{\bm{v}}):=\sum_{k=1}^{K}v_{k}r({\bm{u}}_{k}^{\top}{\bm{x}})$,
with parameters ${\bm{w}},{\bm{v}}\in\mathbb{R}^{K}$ and
${\bm{U}}=[{\bm{u}}_{1},\dots\bm{u}_{K}]\in\mathbb{R}^{K\times d}$ and an
activation function $r(\cdot)$. Let ${\bm{u}}=\mathrm{vec}({\bm{U}})$ and
${\bm{w}},{\bm{v}},{\bm{u}}$ correspond to
${\bm{\theta}}_{L},{\bm{\theta}}_{D},{\bm{\theta}}_{F}$, respectively. This
simplification using a two-layer neural network was included to simplify the
discussion and is easy to generalize.

We further define a sequence of parameters
$\\{({\bm{u}}^{(l)},{\bm{v}}^{(l)},{\bm{w}}^{(l)})\\}_{l=1}^{L}$ that can be
obtained by $L$ updates by the DANN. In preparation, we define a closed set
$\mathcal{W}=\\{({\bm{w}},{\bm{v}},{\bm{u}}):\left\lVert{\bm{w}}\right\rVert\leq
B_{w},\left\lVert{\bm{v}}\right\rVert\leq
B_{v},\max_{k}\left\lVert{\bm{u}}_{k}\right\rVert\leq
B_{u}\\}\subset\mathbb{R}^{K\times K\times Kd}$ with some
$B_{u},B_{w},B_{v}>0$ and also define a projection $\Pi_{\mathcal{W}}(\cdot)$
onto $\mathcal{W}$. Let
$({\bm{w}}^{(1)},{\bm{v}}^{(1)},{\bm{u}}^{(1)})\in\mathcal{W}$ be a tuple of
initial values. Then, the subsequent parameters are recursively defined by the
following updates:

$\displaystyle{{\bm{u}}}^{(l)}$
$\displaystyle=\Pi_{\mathcal{W}}\left({{\bm{u}}}^{(l-1)}-\eta\nabla_{\bm{u}}\\{{L}({{\bm{u}}}^{(l-1)},{{\bm{w}}}^{(l-1)})-\lambda{\Omega}({{\bm{u}}}^{(l-1)},{{\bm{v}}}^{(l-1)})\\}\right),$
(21) $\displaystyle{{\bm{w}}}^{(l)}$
$\displaystyle=\Pi_{\mathcal{W}}\left({{\bm{w}}}^{(l-1)}-\eta\nabla_{\bm{w}}{L}({{\bm{u}}}^{(l-1)},{{\bm{w}}}^{(l-1)})\right),$
(22) $\displaystyle{{\bm{v}}}^{(l)}$
$\displaystyle=\Pi_{\mathcal{W}}\left({{\bm{v}}}^{(l-1)}-\eta\lambda\nabla_{\bm{v}}{\Omega}({{\bm{u}}}^{(l-1)},{{\bm{v}}}^{(l-1)})\right).$
(23)

These updates are an analogy of the original DANN updates Eqs. 8, 9 and 10 to
optimize the minimax loss function Eq. 7 of DANN depending on
$\mathcal{D}_{S}$ and $\mathcal{D}_{T}$. Here, we introduce the projection to
explain a more realistic setup, for example, Shen et al. (2018). Finally, the
classifier obtained by $L$ updates of DANN is defined as

$\displaystyle\widehat{f}^{\mathrm{DANN}}({\bm{x}}):=\Lambda({\bm{x}};{\bm{u}}^{(L)},{\bm{w}}^{(L)}).$
(24)

We show the existence of a Transformer that successively approximates the
parameter sequence by DANN defined above. The results are given in the
following statement.

######  Theorem 2.

Fix any $B_{u},B_{w},B_{v}>0$, $L>0$, $\eta>0$, and $\epsilon>0$. Suppose
activation function $r$ is $C^{4}$-smooth. Then, there exists a $2L$-layer
Transformer $\mathrm{TF}_{\bm{\theta}}$ with

$\max_{l\in\\{1,\dots,2L\\}}M^{(l)}\leq\widetilde{\mathcal{O}}(\epsilon^{-2}),\quad\max_{l\in\\{1,\dots,2L\\}}D^{(l)}\leq\widetilde{\mathcal{O}}(\epsilon^{-2})+D_{\mathrm{MLP}},\quad\left\lVert{\bm{\theta}}\right\rVert_{\mathrm{TF}}\leq\mathcal{O}(1+\eta)+C_{\mathrm{MLP}},$
(25)

with some existing constants $D_{\mathrm{MLP}},C_{\mathrm{MLP}}>0$, which
satisfies the following: for any input
$(\mathcal{D}_{S},\mathcal{D}_{T},{\bm{x}}_{*})$, an $2l$-th layer of the
transformer maps
$\widetilde{{\bm{h}}}_{i}^{(2l-1)}:=[{\bm{z}}_{i},\widetilde{{\bm{u}}}^{(l-1)},\widetilde{{\bm{w}}}^{(l-1)},\widetilde{{\bm{v}}}^{(l-1)}]$
with any
$(\widetilde{{\bm{w}}}^{(l-1)},\widetilde{{\bm{v}}}^{(l-1)},\widetilde{{\bm{u}}}^{(l-1)})\in\mathcal{W}$
to
$\widetilde{{\bm{h}}}_{i}^{(2l)}:=[{\bm{z}}_{i},\widetilde{{\bm{u}}}^{(l)},\widetilde{{\bm{w}}}^{(l)},\widetilde{{\bm{v}}}^{(l)}]$
for each $i\in\\{1,\dots,N+1\\}$ such that

$\displaystyle\widetilde{{\bm{u}}}^{(l)}$
$\displaystyle=\Pi_{\mathcal{W}}\left(\widetilde{{\bm{u}}}^{(l-1)}-\eta\nabla_{\bm{u}}\\{\widetilde{L}(\widetilde{{\bm{u}}}^{(l-1)},\widetilde{{\bm{w}}}^{(l-1)})-\lambda\widetilde{\Omega}(\widetilde{{\bm{u}}}^{(l-1)},\widetilde{{\bm{v}}}^{(l-1)})\\}+{\bm{\epsilon}}^{(l-1)}_{u}\right),$
(26) $\displaystyle\widetilde{{\bm{w}}}^{(l)}$
$\displaystyle=\Pi_{\mathcal{W}}\left(\widetilde{{\bm{w}}}^{(l-1)}-\eta\nabla_{\bm{w}}\widetilde{L}(\widetilde{{\bm{u}}}^{(l-1)},\widetilde{{\bm{w}}}^{(l-1)})+{\bm{\epsilon}}^{(l-1)}_{w}\right),$
(27) $\displaystyle\widetilde{{\bm{v}}}^{(l)}$
$\displaystyle=\Pi_{\mathcal{W}}\left(\widetilde{{\bm{v}}}^{(l-1)}-\eta\lambda\nabla_{\bm{v}}\widetilde{\Omega}(\widetilde{{\bm{u}}}^{(l-1)},\widetilde{{\bm{v}}}^{(l-1)})+{\bm{\epsilon}}^{(l-1)}_{v}\right),$
(28)

where
${\bm{\epsilon}}^{(l-1)}_{u},{\bm{\epsilon}}^{(l-1)}_{w},{\bm{\epsilon}}^{(l-1)}_{v}\in\mathbb{R}^{k}$
are some vectors satisfying
$\max\\{\|{{\bm{\epsilon}}^{(l-1)}_{u}}\|,\|{{\bm{\epsilon}}^{(l-1)}_{w}}\|,\|{{\bm{\epsilon}}^{(l-1)}_{v}}\|\\}\leq\epsilon$.

The results show that the existing Transformer approximates the original DANN
updates Eqs. 21, 22 and 23, at each step. The terms
${\bm{\epsilon}}^{(l-1)}_{u},{\bm{\epsilon}}^{(l-1)}_{w},{\bm{\epsilon}}^{(l-1)}_{v}$
expresses approximation errors, whose norm are no more than the fixed
$\epsilon$. Consequently, the final output of the transformer approximates the
output of the original DANN after $L$-iterations. The results are given as
follows:

######  Corollary 1.

Consider the setup as in Theorem 2. Then, for any input
$(\mathcal{D}_{S},\mathcal{D}_{T},{\bm{x}}_{*})$, the transformer
$\mathrm{TF}_{{\bm{\theta}}}$ in Theorem 2 outputs a corresponding tuple
$(\widetilde{{\bm{w}}}^{(L)},\widetilde{{\bm{v}}}^{(L)},\widetilde{{\bm{u}}}^{(L)})\in\mathcal{W}$
which satisfies

$\displaystyle\|\mathrm{TF}^{*}_{{\bm{\theta}}}({\bm{H}}^{1})-\widehat{f}^{\mathrm{DANN}}({\bm{x}}_{*})\|\leq
L\varepsilon.$ (29)

#### Proof Outline

Here, we focus on the sub-problem that a pair of Transformer layers
approximates a single step of update of DANN consisting of two-layer neural
networks. Specifically, the attention block at the first layer approximates
the forward passes of networks, the succeeding MLP block computes the partial
derivatives of the loss function, then the next attention block implements the
minimax optimization step, and the last MLP block projects the weights.

The specific procedure is presented in the following steps. For brebity, we
write ${\bm{\gamma}}:=({\bm{u}},{\bm{w}},{\bm{v}})$.

  1. Step 1:

Forward pass approximation. The first attention block performs the forward
passes, that is,
${\bm{x}}_{i}\mapsto(\Lambda({\bm{x}}_{i}),\Delta({\bm{x}}_{i}))$, by
approximating the activation function $r$ by sum-of-ReLUs.

######  Lemma 4.

For each $\varepsilon>0$, there exists an attention block which maps
${\bm{h}}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},{\bm{0}}_{4}]$ to
${\bm{h}}^{\prime}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{\Lambda}({\bm{x}}_{i}),\widetilde{\Delta}({\bm{x}}_{i}),{\bm{0}}_{2}]$
for $i=1,\dots,N$ such that
$\|{\widetilde{\Lambda}-\Lambda}\|_{L^{\infty}}\leq\varepsilon$ and
$\|{\widetilde{\Delta}-\Delta}\|_{L^{\infty}}\leq\varepsilon$ hold.

  2. Step 2:

Loss derivative approximation. The next MLP block obtains loss derivatives,
i.e.,
$(\widetilde{\Lambda}({\bm{x}}_{i}),\widetilde{\Delta}({\bm{x}}_{i}),y_{i},t_{i},s_{i})\mapsto(\mathbbm{1}(i\leq
n)\partial_{1}\gamma(\widetilde{\Lambda}({\bm{x}}_{i}),y_{i}),\mathbbm{1}(i\leq
N)\partial_{1}\gamma(\widetilde{\Delta}({\bm{x}}_{i}),y_{i}))$. We also use
sum-of-ReLUs to approximate $\partial_{1}\gamma$.

######  Lemma 5.

For any $\varepsilon>0$, there exists an MLP block which maps
${\bm{h}}^{\prime}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{\Lambda}({\bm{x}}_{i}),\widetilde{\Delta}({\bm{x}}_{i}),{\bm{0}}_{2}]$
to
${\bm{h}}^{\prime\prime}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{\Lambda}({\bm{x}}_{i}),\widetilde{\Delta}({\bm{x}}_{i}),g_{\Lambda,i},g_{\Delta,i}]$,
where $g_{\Lambda,i}$ and $g_{\Delta,i}$ are scalars satisfying
$|{g_{\Lambda,i}-\mathbbm{1}(i\leq
n)\partial_{1}\gamma(\widetilde{\Lambda}({\bm{x}}_{i}),y_{i})}|\leq\varepsilon$
and $|{g_{\Delta,i}-\mathbbm{1}(i\leq
N)\partial_{1}\gamma(\widetilde{\Delta}({\bm{x}}_{i}),y_{i})}|\leq\varepsilon$.

  3. Step 3:

Gradient descent approximation The attention block at the second layer
approximates the optimization step:
$({\bm{u}},{\bm{w}},{\bm{v}})\mapsto({\bm{u}}-\eta\nabla_{\bm{u}}(L({\bm{u}},{\bm{w}})-\lambda\Omega({\bm{u}},{\bm{v}})),{\bm{w}}-\eta\nabla_{\bm{w}}L({\bm{u}},{\bm{w}}),{\bm{v}}-\eta\lambda\nabla_{\bm{v}}\Omega({\bm{u}},{\bm{v}}))$,
which can be obtained by approximating $(s,t)\mapsto s\cdot r^{\prime}(t)$.

######  Lemma 6.

For each $\varepsilon>0$, there exists an attention block that maps
${\bm{h}}^{\prime\prime}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{\Lambda}({\bm{x}}_{i}),\widetilde{\Delta}({\bm{x}}_{i}),g_{\Lambda,i},g_{\Delta,i}]$
to
${\bm{h}}^{\prime\prime\prime}_{i}=[{\bm{z}}_{i},{\bm{u}}-\eta{\bm{g}}_{u},{\bm{w}}-\eta{\bm{g}}_{w},{\bm{v}}-\eta{\bm{g}}_{v},\widetilde{\Lambda}({\bm{x}}_{i}),\widetilde{\Delta}({\bm{x}}_{i}),g_{\Lambda,i},g_{\Delta,i}]$,
where
$\|{{\bm{g}}_{u}-\nabla_{\bm{u}}(\widetilde{L}({\bm{u}},{\bm{w}})-\lambda\widetilde{\Omega}({\bm{u}},{\bm{v}}))}\|_{2},\|{{\bm{g}}_{w}-\nabla_{\bm{w}}\widetilde{L}({\bm{u}},{\bm{w}})}\|_{2},\|{{\bm{g}}_{v}-\lambda\nabla_{\bm{v}}\widetilde{\Omega}({\bm{u}},{\bm{v}})}\|_{2}\leq\varepsilon$.

  4. Step 4:

Projection approximation. The last MLP block projects
${\bm{u}},{\bm{w}},{\bm{v}}$ onto $\mathcal{W}$ appropriately by the
assumption.

By stacking such pairs of such layers, a $2L$-layer Transformer can implement
$L$ steps of DANN in context. The detailed derivation is presented in Section
A.2.

##  4 Automatic Algorithm Selection by In-Context UDA

We demonstrate that Transformers can automatically select UDA algorithms based
on data in context. Specifically, we consider the selection of methods
determined by whether the supports of the source distribution $p_{S}$ and the
target distribution $p_{T}$ sufficiently overlap. In cases where the support
of the target distribution $p_{T}$ overlaps with that of the source
distribution $p_{S}$, the IWL algorithm, which operates using the density
ratio $q({\bm{x}})=p_{T}({\bm{x}})/p_{S}({\bm{x}})$, is employed. In other
words, IWL should be employed when we have

$\displaystyle
p_{S}({\bm{x}})>0\mbox{~{}holds~{}for~{}all~{}}{\bm{x}}\mbox{~{}such~{}that~{}}p_{T}({\bm{x}})>0.$
(30)

Conversely, when there is no such overlap, i.e., $p_{S}({\bm{x}})=0$ for some
${\bm{x}}$ with $p_{T}({\bm{x}})>0$, one should select DANN, which does not
rely on the density ratio.

We show that Transformers are capable of realizing the above design
automatically.

$\displaystyle\widehat{f}^{\mathrm{ICUDA}}({\bm{x}}):=\begin{cases}\widehat{f}^{\mathrm{IWL}}({\bm{x}}_{*})&\text{~{}if~{}}p_{S}({\bm{x}})>0,\forall{\bm{x}}\text{~{}such~{}that~{}}p_{T}({\bm{x}})>0,\\\
\widehat{f}^{\mathrm{DANN}}({\bm{x}}_{*})&\text{~{}otherwise},\end{cases}$
(31)

The statement is as follows:

######  Theorem 3.

Fix any $\epsilon>0$. Suppose that $n^{\prime}\geq(1/\epsilon)^{3}\log
n^{\prime}$ holds and $p_{T}(\cdot)$ is Lipschitz continuous. Then, there
exists a Transformer $\mathrm{TF}_{\bm{\theta}}$ with three layers and $M$
heads satisfies the following with probability at least
$1-1/n^{\prime}-O(\epsilon)$: for any input
$(\mathcal{D}_{S},\mathcal{D}_{T},{\bm{x}}_{*})$, a transformer
$\mathrm{TF}_{\bm{\theta}}$ satisfies

$\displaystyle\|\mathrm{TF}^{*}_{\bm{\theta}}({\bm{H}}^{1})-\widehat{f}^{\mathrm{ICUDA}}({\bm{x}}_{*})\|\leq\epsilon.$
(32)

The results show that the Transformer can automatically check the condition
(30) and use the appropriate algorithm without the user having to make a
choice. Note that the density ratio condition (30) is one of the options that
are automatically learned, and in practice, Transformers can learn more
complicated conditions. Importantly, in this case, cross-validation cannot be
used to make a selection since true labels of the target domain data cannot be
observed.

#### Proof Outline

The key idea is to first implement kernel density estimation of
$p_{S}({\bm{x}})$ for ${\bm{x}}\in\mathcal{D}_{T}$ and then select an
algorithm with
$\min_{{\bm{x}}\in\mathcal{D}_{T}}\widehat{p}_{S}({\bm{x}})>\delta$, where
$\delta>0$ is a given threshold. Here, we assume that each token is
${\bm{h}}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),{\bm{0}}]$,
where ${\bm{\gamma}}$ consists of weights of in-context IWL and DANN and is
unused in this selection process. Further details are discussed in Section
A.3.

  1. Step 1:

Approximation of density estimation. The first step is to approximate the
density function $p_{S}$ with kernel density estimation
$\widehat{p}_{S}(\cdot)=\frac{1}{n}\sum_{i=1}^{n}K(\cdot,{\bm{x}}_{i})$, where
$K$ is a kernel, such as the RBF kernel, and evaluate it on each data point.

######  Lemma 7.

For any $\epsilon>0$, there exists an attention block that maps ${\bm{h}}_{i}$
to
${\bm{h}}^{\prime}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},{\bm{0}}]$,
where $\left\lvert p_{i}-\bar{p}_{S}({\bm{x}}_{i})\right\rvert\leq\epsilon$.

  2. Step 2:

Algorithm selection approximation. Then, the Transformer decides which
algorithm is appropriate based on
$\operatorname*{softmin}_{\beta,i}p_{i}>\delta$, where
$\operatorname*{softmin}_{\beta,i}p_{i}=-\frac{1}{\beta}\log\sum(-\beta
p_{i})$ is a relaxation of $\min$ with an inverse temperature parameter
$\beta>0$.

######  Lemma 8.

For any $\epsilon>0$, there is an MLP block succeeded by a Transformer layer
that maps ${\bm{h}}^{\prime}_{N+1}$ to
${\bm{h}}^{\prime\prime}_{N+1}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{*}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{*}),p_{i},-\frac{1}{\beta}\log\sum_{i}\exp(-\beta
p_{i}),\widetilde{f}({\bm{x}}_{*})]$, where
$|{\widetilde{f}-\widehat{f}^{\mathrm{ICUDA}}}|\leq\epsilon$.

##  5 Experiments

We verify our theory by using the in-context domain adaptation abilities of
Transformers using two synthetic problems. The ICL domain adapter is compared
with  1. IWL with uLSIF using the RBF kernel;  2. DANN of a two-layer neural
network with the ELU activation function; and  3. the same neural network
trained on the source domain only.  For the in-context learning, we used an
eight-layer Transformer with eight heads and pre-trained it to minimize
$\gamma(\mathrm{TF}_{\bm{\theta}}({\bm{x}}^{\prime}_{*};\mathcal{D}^{\prime}_{S},\mathcal{D}^{\prime}_{T}),y^{\prime}_{*})$,
where $({\bm{x}}^{\prime}_{*},y^{\prime}_{*})\sim\mathcal{D}^{\prime}_{T}$,
for randomly synthesized datasets
$(\mathcal{D}^{\prime}_{S},\mathcal{D}^{\prime}_{T})(\neq(\mathcal{D}_{T},\mathcal{D}_{S}))$
for $10^{4}$ iterations. Each dataset consists of $n=n^{\prime}=N/2$ data
points. Note that test data used to report test accuracy are unseen during
pre-training. Further experimental details can be found in Appendix B and the
source is included in the supplementary material.

Figure 1 (Left) presents test accuracy on the two-moon 2D problem, where the
target distribution is a rotation of the source one. The decision boundaries
are also presented, and we can observe that the Transformer learns a smoother
boundary than others. Additionally, Fig. 1 (Right) demonstrates the results of
the colorized MNIST problem, where each dataset consists of images of two
digits resized to $8\times 8$ pixels, and their background colors alter based
on the domains, as presented at the rightmost. On both problems, ICL
consistently achieves much better performance than the baselines. These
results indicate that Transformer implements adaptive domain adaptation
algorithms to given datasets.

Figure 1: (Left) Test accuracy averaged over five runs of Transformer (ICL)
and baseline models on the two-moon 2D problem. Decision boundaries of the
models are presented when $N=200$. (Right) Test accuracy averaged over five
runs on the colorized MNIST.

##  6 Conclusion and Discussion

This paper proved that Transformers can approximate instance-based and
feature-based domain adaptation algorithms and select an appropriate one for
the given dataset in the in-context learning framework. Technically, our
results revealed that Transformers can approximately solve some types of
linear equations and minimax problems. Numerical experiments demonstrated that
domain adaptation in in-context learning outperforms UDA methods tailored for
specific assumptions.

Limitations

In this work, we presented that Transformer models can approximate popular UDA
methods, namely, importance-weighted learning with the uLSIF estimator and
domain adversarial neural networks. However, the approximability of other
domain adaptation techniques, such as parameter-based methods, is left
unclear, and investigating it is an interesting direction. Furthermore,
investigating whether appropriate domain adaptation algorithms can be
automatically selected from a larger pool of candidates remains a task for
future work.

## References

  * Ahn et al. (2024) Ahn, K., Cheng, X., Daneshmand, H., and Sra, S.  Transformers learn to implement preconditioned gradient descent for in-context learning.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Akyürek et al. (2022) Akyürek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D.  What learning algorithm is in-context learning? investigations with linear models.  _arXiv preprint arXiv:2211.15661_ , 2022.
  * Bai et al. (2023) Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S.  Transformers as statisticians: Provable in-context learning with in-context algorithm selection.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=liMSqUuVg9.
  * Ben-David et al. (2010) Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W.  A theory of learning from different domains.  _Machine learning_ , 79:151–175, 2010.
  * Dai et al. (2007) Dai, W., Yang, Q., Xue, G.-R., and Yu, Y.  Boosting for transfer learning.  In _Proceedings of the 24th international conference on Machine learning_ , pp. 193–200, 2007.
  * Daumé III (2009) Daumé III, H.  Frustratingly easy domain adaptation.  _arXiv preprint arXiv:0907.1815_ , 2009.
  * Ganin et al. (2016) Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., March, M., and Lempitsky, V.  Domain-adversarial training of neural networks.  _Journal of machine learning research_ , 17(59):1–35, 2016.
  * Garg et al. (2022) Garg, S., Tsipras, D., Liang, P. S., and Valiant, G.  What can transformers learn in-context? a case study of simple function classes.  _Advances in Neural Information Processing Systems_ , 35:30583–30598, 2022.
  * Guan & Liu (2021) Guan, H. and Liu, M.  Domain adaptation for medical image analysis: a survey.  _IEEE Transactions on Biomedical Engineering_ , 69(3):1173–1185, 2021.
  * Jiang (2017) Jiang, H.  Uniform convergence rates for kernel density estimation.  In _International Conference on Machine Learning_ , pp. 1694–1703. PMLR, 2017.
  * Kanamori et al. (2009) Kanamori, T., Hido, S., and Sugiyama, M.  A least-squares approach to direct importance estimation.  _The Journal of Machine Learning Research_ , 10:1391–1445, 2009.
  * Kimura & Hino (2024) Kimura, M. and Hino, H.  A short survey on importance weighting for machine learning.  _Transactions on Machine Learning Research_ , 2024.  ISSN 2835-8856.  URL https://openreview.net/forum?id=IhXM3g2gxg.  Survey Certification.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J. L.  Adam: a Method for Stochastic Optimization.  In _ICLR_ , 2015.
  * Li et al. (2023) Li, Y., Ildiz, M. E., Papailiopoulos, D., and Oymak, S.  Transformers as algorithms: Generalization and implicit model selection in in-context learning.  _arXiv preprint arXiv:2301.07067_ , 2023.
  * Lin et al. (2023) Lin, L., Bai, Y., and Mei, S.  Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining.  In _NeurIPS 2023 Foundation Models for Decision Making Workshop_ , 2023.
  * Loshchilov & Hutter (2019) Loshchilov, I. and Hutter, F.  Decoupled weight decay regularization.  In _ICLR_ , 2019.  URL https://openreview.net/forum?id=Bkg6RiCqY7.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  Pytorch: An imperative style, high-performance deep learning library.  In _NeurIPS_ , 2019.
  * Raventós et al. (2024) Raventós, A., Paul, M., Chen, F., and Ganguli, S.  Pretraining task diversity and the emergence of non-bayesian in-context learning for regression.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Requeima et al. (2019) Requeima, J., Gordon, J., Bronskill, J., Nowozin, S., and Turner, R. E.  Fast and flexible multi-task classification using conditional neural adaptive processes.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Shen et al. (2018) Shen, J., Qu, Y., Zhang, W., and Yu, Y.  Wasserstein distance guided representation learning for domain adaptation.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2018.
  * Shimodaira (2000) Shimodaira, H.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of statistical planning and inference_ , 90(2):227–244, 2000.
  * Sugiyama et al. (2007) Sugiyama, M., Krauledat, M., and Müller, K.-R.  Covariate shift adaptation by importance weighted cross validation.  _Journal of Machine Learning Research_ , 8(5), 2007.
  * Sugiyama et al. (2012) Sugiyama, M., Suzuki, T., and Kanamori, T.  _Density ratio estimation in machine learning_.  Cambridge University Press, 2012.
  * Sun et al. (2019) Sun, Q., Liu, Y., Chua, T., and Schiele, B.  Meta-transfer learning for few-shot learning.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pp. 403–412. Computer Vision Foundation / IEEE, 2019.
  * Von Oswald et al. (2023) Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M.  Transformers learn in-context by gradient descent.  In _International Conference on Machine Learning_ , pp. 35151–35174. PMLR, 2023.
  * Xie et al. (2021) Xie, S. M., Raghunathan, A., Liang, P., and Ma, T.  An explanation of in-context learning as implicit bayesian inference.  In _International Conference on Learning Representations_ , 2021.
  * Ying et al. (2018) Ying, W., Zhang, Y., Huang, J., and Yang, Q.  Transfer learning via learning to transfer.  In _International conference on machine learning_ , pp. 5085–5094. PMLR, 2018.
  * Zhang et al. (2023) Zhang, R., Frei, S., and Bartlett, P.  Trained transformers learn linear models in-context.  In _R0-FoMo: Robustness of Few-shot and Zero-shot Learning in Large Foundation Models_ , 2023.

##  Appendix A Proofs

###  A.1 In-context IWL with uLSIF

We prove Theorem 1 in three steps: the first layer applies some feature map to
the input data, the next $L_{1}$ layers estimate ${\bm{\alpha}}$, and then the
last $L_{2}$ layers compute ${\bm{w}}$ with importance-weighted learning.

###### Proof of Theorem 1.

  1. Step 1:

(The first layer) It is trivial that the feature map ${\bm{\phi}}(\cdot)$ is
approximable by the sum of ReLUs. As a typical example, Section A.3 presents
the approximation of the RBF kernel.

  2. Step 2:

(The $2$nd to $L_{1}$th layers) As
${\bm{\Psi}}=\frac{1}{n}\sum_{i=1}^{n}{\bm{\phi}}({\bm{x}}_{i}){\bm{\phi}}({\bm{x}}_{i})^{\top}\in\mathbb{R}^{J\times
J}$, its vector product with ${\bm{\alpha}}\in\mathbb{R}^{J}$ is
${\bm{\Psi}}{\bm{\alpha}}=\frac{1}{n}\sum_{i=1}^{n}{\bm{\phi}}({\bm{x}}_{i}){\bm{\phi}}({\bm{x}}_{i})^{\top}{\bm{\alpha}}=\frac{1}{n}\sum_{i=1}^{n}({\bm{\phi}}({\bm{x}}_{i})^{\top}{\bm{\alpha}}){\bm{\phi}}({\bm{x}}_{i})$.
Similarly,
${\bm{\psi}}=\frac{1}{n^{\prime}}\sum_{i=n+1}^{n+n^{\prime}}{\bm{\phi}}({\bm{x}}_{i})$.
Thus,
$\eta_{1}\nabla_{\bm{\alpha}}\widehat{L}({\bm{\alpha}})=\eta_{1}({\bm{\Psi}}{\bm{\alpha}}-{\bm{\psi}}+\lambda{\bm{\alpha}})$
can be constructed with matrices
${\bm{Q}}_{m}^{(l)},{\bm{K}}_{m}^{(l)},{\bm{V}}_{m}^{(l)}$ for $m=1,2,3,4$ as
follows:

$\displaystyle{\bm{Q}}_{1}^{(l)}{\bm{h}}_{i}$
$\displaystyle=\begin{bmatrix}{\bm{\alpha}}^{(l)}\\\ -R^{\prime}\\\
{\bm{0}}_{D-J-1}\end{bmatrix},\quad{\bm{K}}_{1}^{(l)}{\bm{h}}_{j}$
$\displaystyle=\begin{bmatrix}{\bm{\phi}}({\bm{x}}_{j})\\\ 1-t_{j}\\\
{\bm{0}}_{D-J-1}\end{bmatrix},\quad{\bm{V}}_{1}^{(l)}{\bm{h}}_{j}$
$\displaystyle=-\frac{(N+1)\eta_{1}}{n}\begin{bmatrix}{\bm{0}}_{D-J-d}\\\
{\bm{\phi}}({\bm{x}}_{j})\\\ {\bm{0}}_{d}\end{bmatrix}$ (33)
$\displaystyle{\bm{Q}}_{2}^{(l)}{\bm{h}}_{i}$
$\displaystyle=\begin{bmatrix}-{\bm{\alpha}}^{(l)}\\\ -R^{\prime}\\\
{\bm{0}}_{D-J-1}\end{bmatrix},\quad{\bm{K}}_{2}^{(l)}{\bm{h}}_{j}$
$\displaystyle=\begin{bmatrix}{\bm{\phi}}({\bm{x}}_{j})\\\ 1-t_{j}\\\
{\bm{0}}_{D-J-1}\end{bmatrix},\quad{\bm{V}}_{2}^{(l)}{\bm{h}}_{j}$
$\displaystyle=-\frac{(N+1)\eta_{1}}{n}\begin{bmatrix}{\bm{0}}_{D-J-d}\\\
{\bm{\phi}}({\bm{x}}_{j})\\\ {\bm{0}}_{d}\end{bmatrix}$ (34)
$\displaystyle{\bm{Q}}_{3}^{(l)}{\bm{h}}_{i}$
$\displaystyle=\begin{bmatrix}1\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{K}}_{3}^{(l)}{\bm{h}}_{j}$
$\displaystyle=\begin{bmatrix}s_{j}-t_{j}\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{V}}_{3}^{(l)}{\bm{h}}_{j}$
$\displaystyle=\frac{(N+1)\eta_{1}}{n^{\prime}}\begin{bmatrix}{\bm{0}}_{D-J-d}\\\
{\bm{\phi}}({\bm{x}}_{j})\\\ {\bm{0}}_{d}\end{bmatrix}$ (35)
$\displaystyle{\bm{Q}}_{4}^{(l)}{\bm{h}}_{i}$
$\displaystyle=\begin{bmatrix}1\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{K}}_{4}^{(l)}{\bm{h}}_{j}$
$\displaystyle=\begin{bmatrix}s_{j}\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{V}}_{4}^{(l)}{\bm{h}}_{j}$
$\displaystyle=-\frac{(N+1)\lambda\eta_{1}}{N}\begin{bmatrix}{\bm{0}}_{D-J-d}\\\
{\bm{\alpha}}^{(l)}\\\ {\bm{0}}_{d}\end{bmatrix},$ (36)

where $R^{\prime}=\max(B_{x}B_{\alpha},1)$. These matrices exist, and we
obtain

$\displaystyle\widetilde{{\bm{h}}}_{i}^{(l)}=$
$\displaystyle{\bm{h}}_{i}^{(l)}+\frac{1}{N+1}\sum_{j=1}^{N+1}\sum_{m=1}^{4}\sigma(\langle{\bm{Q}}_{m}^{(l)}{\bm{h}}_{i},{\bm{K}}_{m}^{(l)}{\bm{h}}_{j}\rangle){\bm{V}}_{m}^{(l)}{\bm{h}}_{j}$
(37) $\displaystyle=$
$\displaystyle{\bm{h}}_{i}^{(l)}+\sum_{j=1}^{N+1}-\left\\{\\{\sigma({\bm{\phi}}({\bm{x}}_{j})^{\top}{\bm{\alpha}}^{(l)}-R^{\prime}(1-t_{j}))-\sigma(-{\bm{\phi}}({\bm{x}}_{j})^{\top}{\bm{\alpha}}^{(l)}-R^{\prime}(1-t_{j}))\\}[{\bm{0}},\frac{\eta_{1}}{n}{\bm{\phi}}({\bm{x}}_{j}),{\bm{0}}]\right.$
(38)
$\displaystyle\left.+\sigma(s_{j}-t_{j})[{\bm{0}},\frac{\eta_{1}}{n^{\prime}}{\bm{\phi}}({\bm{x}}_{j}),{\bm{0}}]+[{\bm{0}},\frac{\eta_{1}\lambda}{N}{\bm{\alpha}}^{(l)},{\bm{0}}]\right\\}$
(39) $\displaystyle=$
$\displaystyle{\bm{h}}_{i}^{(l)}+(-\eta_{1})\left\\{\frac{1}{n}\sum_{j=1}^{n}{\bm{\phi}}({\bm{x}}_{j})^{\top}{\bm{\alpha}}^{(l)}[{\bm{0}},{\bm{\phi}}({\bm{x}}_{j}),{\bm{0}}]-\sum_{j=n+1}^{n+n^{\prime}}[{\bm{0}},{\bm{\phi}}({\bm{x}}_{j}),{\bm{0}}]+[{\bm{0}},\lambda{\bm{\alpha}}^{(l)},{\bm{0}}]\right\\}$
(40) $\displaystyle=$
$\displaystyle[{\bm{x}}_{i},\dots,\underline{{\bm{\alpha}}^{(l)}},{\bm{0}}_{J}]+[{\bm{0}}_{D-2J},\underline{-\eta_{1}({\bm{\Psi}}{\bm{\alpha}}^{(l)}-{\bm{\psi}}+\lambda{\bm{\alpha}}^{(l)})},{\bm{0}}_{J}].$
(41)

We used $z=\sigma(z)-\sigma(-z)$ for $z\in\mathbb{R}$,
$\sigma({\bm{\phi}}({\bm{x}}_{j})^{\top}{\bm{\alpha}}-R^{\prime}(1-t_{j}))=\sigma({\bm{\phi}}({\bm{x}}_{j})^{\top}{\bm{\alpha}})\cdot\mathbbm{1}(j\leq
n)$, $\sigma(s_{j})=\mathbbm{1}(j\leq N)$, and
$\sigma(s_{j}-t_{j})=\mathbbm{1}(n\leq j\leq N)$. The weight matrices have
norm bounds of

$\max_{m}\left\lVert{\bm{Q}}_{m}^{(l)}\right\rVert\leq
1+R,\quad\max_{m}\left\lVert{\bm{K}}_{m}^{(l)}\right\rVert\leq
1,\quad\sum_{m}\left\lVert{\bm{V}}_{m}^{(l)}\right\rVert\leq(\frac{2(N+1)}{n}+\frac{(N+1)}{n^{\prime}}+\frac{\lambda}{N+1})\eta_{1}.$
(42)

  3. Step 3:

(The $L_{1}+1$th to $L_{1}+L_{2}+1$th layers) As $(s,t,u)\mapsto
u\partial_{1}\ell(s,t)$ is $(\epsilon,R,M,C)$-approximable by sum of ReLUs
with $R=\max\\{B_{x}B_{w},B_{y},1\\}$, there exists a function
$f:[-R,R]^{3}\to\mathbb{R}$ of a form

$f(s,t,u)=\sum_{m=1}^{M}c_{m}\sigma(a_{m}s+b_{m}t+d_{m}u+e_{m})\quad\text{with}\quad\sum_{m=1}^{M}\left\lvert
c_{m}\right\rvert\leq C,\left\lvert a_{m}\right\rvert+\left\lvert
b_{m}\right\rvert+\left\lvert d_{m}\right\rvert+\left\lvert
e_{m}\right\rvert\leq 1~{}(\forall m),$ (43)

such that $\sup_{(s,t,u)\in[-R,R]^{3}}\left\lvert
f(s,t,u)-u\partial_{1}\ell(s,t)\right\rvert\leq\epsilon$.

Then, there exists matrices
${\bm{Q}}_{m}^{(l)},{\bm{K}}_{m}^{(l)},{\bm{V}}_{m}^{(l)}$ for
$m\in\\{1,\dots,M\\}$ such that

${\bm{Q}}_{m}^{(l)}{\bm{h}}_{i}=\begin{bmatrix}a_{m}\widehat{\bm{w}}^{(l)}\\\
b_{m}\\\ d_{m}{\bm{\alpha}}^{(L_{1})}\\\ e_{m}\\\
-2\end{bmatrix},\quad{\bm{K}}_{m}^{(l)}{\bm{h}}_{j}=\begin{bmatrix}{\bm{\phi}}({\bm{x}}_{j})\\\
y_{j}\\\ {\bm{\phi}}({\bm{x}}_{j})\\\ 1\\\
R(1-t_{j})\end{bmatrix},{\bm{V}}_{m}^{(l)}{\bm{h}}_{j}=-\frac{(N+1)c_{m}\eta_{2}}{n}\begin{bmatrix}{\bm{0}}_{D-d}\\\
{\bm{\phi}}({\bm{x}}_{j})\end{bmatrix},$ (44)

with norm bounds of

$\max_{m}\left\lVert{\bm{Q}}_{m}^{(l)}\right\rVert\leq
3,\quad\max_{m}\left\lVert{\bm{K}}_{m}^{(l)}\right\rVert\leq
2+R,\quad\sum_{m}\left\lVert{\bm{V}}_{m}^{(l)}\right\rVert\leq\frac{N+1}{n}C\eta_{2}.$
(45)

With these matrices, we get

$\displaystyle\widetilde{{\bm{h}}}_{i}^{(l)}$
$\displaystyle={\bm{h}}_{i}^{(l)}+\frac{1}{N+1}\sum_{j=1}^{N+1}\sum_{m=1}^{M}\sigma(\langle{\bm{Q}}_{m}^{(l)}{\bm{h}}_{i},{\bm{K}}_{m}^{(l)}{\bm{h}}_{j}\rangle){\bm{V}}_{m}^{(l)}{\bm{h}}_{j}$
$\displaystyle={\bm{h}}_{i}^{(l)}+\sum_{j=1}^{n}\sum_{m=1}^{M}-\sigma(a_{m}\widehat{\bm{w}}^{(l)\top}{\bm{\phi}}({\bm{x}}_{j})+b_{m}y_{j}+d_{m}{\bm{\alpha}}^{(L_{1})\top}{\bm{\phi}}({\bm{x}}_{j})+e_{m})\frac{c_{m}\eta_{2}}{n}[{\bm{0}},{\bm{\phi}}({\bm{x}}_{j})]$
$\displaystyle={\bm{h}}_{i}^{(l)}+\frac{\eta_{2}}{n}\sum_{j=1}^{n}-f(\widehat{\bm{w}}^{(l)\top}{\bm{\phi}}({\bm{x}}_{j}),y_{j},{\bm{\alpha}}^{(L_{1})\top}{\bm{\phi}}({\bm{x}}_{j}))[{\bm{0}},{\bm{\phi}}({\bm{x}}_{j})]$
$\displaystyle={\bm{h}}_{i}^{(l)}+[0,-\frac{\eta_{2}}{n}\widehat{q}_{{\bm{\alpha}}}({\bm{x}}_{j})\partial_{1}\ell(\widehat{\bm{w}}^{(l)\top}{\bm{\phi}}({\bm{x}}_{j}),y_{j}){\bm{\phi}}({\bm{x}}_{j})+{\bm{\epsilon}}]$
$\displaystyle=[{\bm{x}}_{i},\dots,\underline{\widehat{\bm{w}}^{(l)}}]+[{\bm{0}}_{D-d},\underline{-\eta_{2}\nabla_{\bm{w}}\widehat{R}_{T}(\widehat{\bm{w}}^{(l)})+{\bm{\epsilon}}}],$

where the error ${\bm{\epsilon}}$ satisfies

$\displaystyle\left\lVert{\bm{\epsilon}}\right\rVert_{2}$
$\displaystyle=\left\lVert-\frac{\eta_{2}}{n}\sum_{j=1}^{n}\left\lvert
f(\widehat{\bm{w}}^{(l)\top}{\bm{\phi}}({\bm{x}}_{j}),y_{j},{\bm{\alpha}}^{(L_{1})\top}{\bm{\phi}}({\bm{x}}_{j}))-\widehat{q}_{{\bm{\alpha}}^{(L_{1})}}({\bm{x}}_{j})\nabla_{1}\ell({\bm{w}}^{(l)\top}\phi({\bm{x}}_{j}),y_{j})\right\rvert{\bm{\phi}}({\bm{x}}_{j})\right\rVert_{2}$
(46) $\displaystyle\leq\frac{\eta_{2}}{n}\sum_{j=1}^{n}\left\lvert
f(\widehat{\bm{w}}^{(l)\top}{\bm{\phi}}({\bm{x}}_{j}),y_{j},{\bm{\alpha}}^{(L_{1})\top}{\bm{\phi}}({\bm{x}}_{j}))-\widehat{q}_{{\bm{\alpha}}^{(L_{1})}}({\bm{x}}_{j})\nabla_{1}\ell({\bm{w}}^{(l)\top}\phi({\bm{x}}_{j}),y_{j})\right\rvert\left\lVert{\bm{\phi}}({\bm{x}}_{j})\right\rVert_{2}$
(47) $\displaystyle\leq\frac{\eta_{2}}{n}n\epsilon B_{x}\cdot
1=\epsilon\eta_{2}B_{x},$ (48)

since $\|{\bm{\phi}}\|\leq 1$ by the assumption. As a result, we get
$\left\lVert{\bm{\theta}}_{\mathrm{TF}}\right\rVert\leq
1+R+\max\\{(\frac{2(N+1)}{n}+\frac{(N+1)}{n^{\prime}}+\frac{\lambda}{N+1})\eta_{1},1+\frac{N+1}{n}C\eta_{2}\\}$.
∎

###  A.2 In-context DANN

To prove Theorem 2, we show its single-step version.

######  Proposition 1.

Under the assumptions of Theorem 2, there exists a two-layer Transformer
$\mathrm{TF}_{\bm{\theta}}$ such that for any input
$(\mathcal{D}_{S},\mathcal{D}_{T},{\bm{x}}_{*})$ and any
$({\bm{w}},{\bm{v}},{\bm{U}})\in\mathcal{W}$, $\mathrm{TF}_{\bm{\theta}}$ maps
${\bm{h}}_{i}=[{\bm{x}}_{i},y_{i},t_{i},s_{i},1,{\bm{u}},{\bm{w}},{\bm{v}},{\bm{0}}]$
to
${\bm{h}}^{\prime}_{i}=[{\bm{x}}_{i},y_{i},t_{i},s_{i},1,{\bm{u}}^{\prime},{\bm{w}}^{\prime},{\bm{v}}^{\prime},{\bm{0}}]$,
where

$\displaystyle{\bm{u}}^{\prime}$
$\displaystyle=\Pi_{\mathcal{W}}\left\\{{\bm{u}}-\eta\nabla_{\bm{u}}(\widehat{L}({\bm{u}},{\bm{w}})-\lambda\widehat{\Omega}({\bm{u}},{\bm{v}}))+{\bm{\epsilon}}_{u}\right\\},$
(49) $\displaystyle{\bm{w}}^{\prime}$
$\displaystyle=\Pi_{\mathcal{W}}\left\\{{\bm{w}}-\eta\nabla_{\bm{w}}\widehat{L}({\bm{u}},{\bm{w}})+{\bm{\epsilon}}_{w}\right\\},$
(50) $\displaystyle{\bm{v}}^{\prime}$
$\displaystyle=\Pi_{\mathcal{W}}\left\\{{\bm{v}}-\eta\lambda\nabla_{\bm{v}}\widehat{\Omega}({\bm{u}},{\bm{v}})+{\bm{\epsilon}}_{v}\right\\},$
(51)

and

$\left\lVert{\bm{\epsilon}}_{u}\right\rVert,\left\lVert{\bm{\epsilon}}_{w}\right\rVert,\left\lVert{\bm{\epsilon}}_{v}\right\rVert\leq\eta\epsilon.$
(52)

###### Proof of Proposition 1.

Fix $\epsilon_{r},\epsilon_{p},\epsilon_{\gamma}$ that will be specified
later. Our goal is to approximate the following values:

$\displaystyle\nabla_{{\bm{u}}_{k}}L({\bm{u}},{\bm{w}})$
$\displaystyle=\frac{1}{n}\sum_{({\bm{x}},y)\in\mathcal{D}_{S}}\partial_{1}\gamma(\Lambda({\bm{x}}),y)\cdot{\bm{w}}_{k}\cdot
r^{\prime}({\bm{u}}_{k}^{\top}{\bm{x}})\cdot{\bm{x}},$ (53)
$\displaystyle\nabla_{{\bm{w}}_{k}}L({\bm{u}},{\bm{w}})$
$\displaystyle=\frac{1}{n}\sum_{({\bm{x}},y)\in\mathcal{D}_{S}}\partial_{1}\gamma(\Lambda({\bm{x}}),y)\cdot
r({\bm{u}}_{k}^{\top}{\bm{x}}),$ (54)
$\displaystyle\nabla_{{\bm{u}}_{k}}\Omega({\bm{u}},{\bm{v}})$
$\displaystyle=-\frac{1}{n}\smashoperator[]{\sum_{({\bm{x}},\cdot)\in\mathcal{D}_{S}}^{}}\partial_{1}\gamma(\Delta({\bm{x}}),0)\cdot{\bm{v}}_{k}\cdot
r^{\prime}({\bm{u}}_{k}^{\top}{\bm{x}})\cdot{\bm{x}}-\frac{1}{n^{\prime}}\smashoperator[]{\sum_{({\bm{x}},\cdot)\in\mathcal{D}_{T}}^{}}\partial_{1}\gamma(\Delta({\bm{x}}),1)\cdot{\bm{v}}_{k}\cdot
r^{\prime}({\bm{u}}_{k}^{\top}{\bm{x}})\cdot{\bm{x}},$ (55)
$\displaystyle\nabla_{{\bm{v}}_{k}}\Omega({\bm{u}},{\bm{v}})$
$\displaystyle=\frac{1}{n}\sum_{({\bm{x}},\cdot)\in\mathcal{D}_{S}}\partial_{1}\gamma(\Delta({\bm{x}}),0)\cdot
r({\bm{u}}_{k}^{\top}{\bm{x}})+\frac{1}{n^{\prime}}\sum_{({\bm{x}},\cdot)\in\mathcal{D}_{T}}\partial_{1}\gamma(\Delta({\bm{x}}),1)\cdot
r({\bm{u}}_{k}^{\top}{\bm{x}}),$ (56)

Following (Bai et al., 2023), we show that a Transformer can approximate them
in the following four steps.

  1. Step 1:

(The attention block of the first layer) As the activation function $r(t)$ is
$(\epsilon_{r},R_{1},M_{1},C_{1})$-approximable for
$R_{1}=\max(B_{w}B_{x},B_{v}B_{x})$ and
$M_{1}\leq\widetilde{O}(C_{1}^{2}\epsilon_{r}^{-2})$, where $C_{1}$ depends
only on $R_{1}$ and the $C^{2}$-smoothness of $r$, there exists a function
$\bar{r}:[-R_{1},R_{1}]\to\mathbb{R}$ of a form

$\bar{r}(t)=\sum_{m=1}^{M_{1}}c_{m}^{1}\sigma(a_{m}^{1}t+b_{m}^{1})\quad\text{with}~{}\sum_{m=1}^{M_{1}}\left\lvert
c_{m}^{1}\right\rvert\leq C_{1},~{}\left\lvert
a_{m}^{1}\right\rvert+\left\lvert b_{m}^{1}\right\rvert\leq 1~{}(\forall m),$
(57)

such that $\sum_{t\in[-R_{1},R_{1}]\left\lvert
r(t)-\bar{r}(t)\right\rvert}\leq\epsilon_{r}$. Then, the forward pass of the
networks $\Lambda$ and $\Delta$ can be approximated by a single self-attention
layer. Namely, there exists matrices
$\\{{\bm{Q}}_{k,m},{\bm{K}}_{k,m},{\bm{V}}_{k,m}\\}_{k\in\\{1,\dots,K\\}}^{m\in\\{1,\dots,M_{1}\\}}$
such that

${\bm{Q}}_{k,m}{\bm{h}}_{i}=\begin{bmatrix}a_{m}^{1}{\bm{x}}_{i}\\\
b_{m}^{1}\\\
{\bm{0}}\end{bmatrix},\quad{\bm{K}}_{k,m}{\bm{h}}_{j}=\begin{bmatrix}{\bm{u}}_{k}\\\
1\\\
0\end{bmatrix},\quad{\bm{V}}_{k,m}{\bm{h}}_{j}=c_{m}^{1}({\bm{w}}_{k}\cdot{\bm{e}}_{D^{\prime}+1}+{\bm{v}}_{k}\cdot{\bm{e}}_{D^{\prime}+1}),$
(58)

where $D^{\prime}=(K+3)d+4$ with norm bounds of

$\max_{k,m}\left\lVert{\bm{Q}}_{k,m}\right\rVert\leq
1,\quad\max_{k,m}\left\lVert{\bm{K}}_{k,m}\right\rVert\leq
1,\quad\sum_{k,m}\left\lVert{\bm{V}}_{k,m}\right\rVert\leq C_{1}.$ (59)

Then,

$\sum_{m,k}\sigma(\langle{\bm{Q}}_{m,k}{\bm{h}}_{i},{\bm{K}}_{m,k}{\bm{h}}_{j}\rangle){\bm{V}}_{m,k}{\bm{h}}_{j}=\sum_{k=1}^{K}\\{{\bm{w}}_{k}\bar{r}({\bm{u}}_{k}{\bm{x}}_{i})\cdot{\bm{e}}_{1}+{\bm{v}}\bar{r}({\bm{u}}_{k}^{\top}{\bm{x}}_{i})\cdot{\bm{e}}_{2}\\}.$
(60)

Denoting
$\bar{\Lambda}({\bm{x}})=\sum_{k=1}^{K}{\bm{w}}_{k}\bar{r}({\bm{u}}_{k}^{\top}{\bm{x}})$
and
$\bar{\Delta}({\bm{x}})=\sum_{k=1}^{K}{\bm{v}}_{k}\bar{r}({\bm{u}}_{k}^{\top}{\bm{x}})$,
this first attention block maps ${\bm{h}}_{i}$ to
${\bm{h}}^{\prime}_{i}=[{\bm{x}}_{i},y_{i},t_{i},s_{i},1,{\bm{u}},{\bm{w}},{\bm{v}},\bar{\Lambda}({\bm{x}}_{i}),\bar{\Delta}({\bm{x}}_{i}),{\bm{0}}_{2}]$.

  2. Step 2:

(The MLP block of the first layer) Because the function
$(t,s)\mapsto\partial_{1}\gamma(t,s)$ is
$(\epsilon_{\gamma},R_{2},M_{2},C_{2})$-approximable for
$R_{2}=\max(1,B_{x}B_{w}B_{u},B_{x}B_{w}B_{v},B_{y})$ and
$M_{2}\leq\widetilde{O}(C_{2}^{2}\epsilon_{\gamma}^{-2})$, where $C_{2}$
depends only on $R_{2}$ nad $C^{3}$-smootheness of $\partial_{1}\gamma$, there
is a function $g:[-R_{2},R_{2}]^{2}\to\mathbb{R}$ of a form

$g(t,s)=\sum_{m=1}^{M_{2}}c_{m}^{2}(a_{m}^{2}t+b_{m}^{2}s+d_{m}^{2})\quad\text{with}~{}\sum_{m=1}^{M_{2}}\left\lvert
c_{m}^{2}\right\rvert\leq C_{2},\left\lvert a_{m}^{2}\right\rvert+\left\lvert
b_{m}^{2}\right\rvert+\left\lvert d_{m}^{2}\right\rvert\leq 1~{}(\forall m),$
(61)

such that $\sup_{(t,s)\in[-R_{2},R_{2}]^{2}}\left\lvert
g(t,s)-\partial_{1}\gamma(t,s)\right\rvert\leq\epsilon_{\gamma}$. By picking
matrices $W_{1},W_{2}$ such that $W_{1}\in\mathbb{R}^{2M_{2}\times D}$ maps

${\bm{W}}_{1}{\bm{h}}^{\prime}_{i}=\begin{cases}&[a_{m}^{2}\bar{\Lambda}({\bm{x}}_{i})+b_{m}^{2}y_{i}+d_{m}^{2}-R_{2}(1-t_{i})]_{m=1}^{M_{2}}\\\
&[a_{m}^{2}\bar{\Delta}({\bm{x}}_{i})+b_{m}^{2}y_{i}+d_{m}^{2}-R_{2}(1-t_{i})]_{m=M_{2}+1}^{2M_{2}}\end{cases}$
(62)

and $W_{2}\in\mathbb{R}^{D\times 2M_{2}}$ consists of elements of

$({\bm{W}}_{2})_{j,m}=\begin{cases}c_{m}^{2}\mathbbm{1}(j=D^{\prime}+3)\quad\text{if
$1\leq m\leq M_{2}$}\\\
c_{m}^{2}\mathbbm{1}(j=D^{\prime}+4)\quad\text{otherwise}\end{cases}$ (63)

we have

$\displaystyle{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{h}}^{\prime}_{i})$
$\displaystyle=\sum_{m=1}^{M_{2}}\sigma(a_{m}^{2}\bar{\Lambda}({\bm{x}}_{i})+b_{m}^{2}y_{i}+d_{m}^{2}-R_{2}(1-t_{j}))\cdot
c_{m}^{2}{\bm{e}}_{D^{\prime}+3}$ (64)
$\displaystyle\quad+\sum_{m=M_{2}+1}^{2M_{2}}\sigma(a_{m}^{2}\bar{\Delta}({\bm{x}}_{i})+b_{m}^{2}y_{i}+d_{m}^{2}-R_{2}(1-s_{j}))\cdot
c_{m}^{2}{\bm{e}}_{D^{\prime}+4}$ (65) $\displaystyle=\mathbbm{1}(i\leq
n)\cdot
g(\bar{\Lambda}({\bm{x}}_{i}),y_{i})\cdot{\bm{e}}_{D^{\prime}+3}+\mathbbm{1}(i\leq
N)\cdot g(\bar{\Delta}({\bm{x}}_{i}),y_{i})\cdot{\bm{e}}_{D^{\prime}+4},$ (66)

where ${\bm{e}}_{k}$ indicates a vector whose $i$th element is
$\mathbbm{1}(i=k)$. Denoting $g_{\Lambda,i}=\mathbbm{1}(i\leq n)\cdot
g(\bar{\Lambda}({\bm{x}}_{i}),y_{i})$ and $g_{\Delta,i}=\mathbbm{1}(i\leq
N)\cdot g(\bar{\Delta}({\bm{x}}_{i}),y_{i})$, this MLP layer transforms
${\bm{h}}^{\prime}_{i}\mapsto{\bm{h}}^{\prime\prime}_{i}=[{\bm{x}}_{i},y_{i},t_{i},s_{i},1,{\bm{u}},{\bm{w}},{\bm{v}},\bar{\Lambda}({\bm{x}}_{i}),\bar{\Delta}({\bm{x}}_{i}),g_{\Lambda,i},g_{\Delta,i}]$.
By definition of $g$,

$\left\lvert
g_{\Lambda,i}-\partial_{1}\gamma(\Lambda({\bm{x}}_{i}),y_{i})\right\rvert\leq\epsilon_{\gamma}+B_{u}L_{\gamma}\epsilon_{r},$
(67)

where $L_{\gamma}=\max\left\lvert\partial_{11}\gamma(t,s)\right\rvert$ is the
smoothness of $\partial_{1}\gamma$. The same holds for $g_{\Delta,i}$.

  3. Step 3:

(The self-attention block of the second layer) The function $(t,s)\mapsto
s\cdot r^{\prime}(t)$ and $(t,s)\mapsto-s\cdot r^{\prime}(t)$ are
$(\epsilon_{p},R_{3},M_{3},C_{3})$-approximable for
$R_{3}=\max\\{B_{x}B_{u},B_{g}B_{u}1\\}$ and
$M_{3}\leq\widetilde{O}(C_{3}^{2}\epsilon_{p}^{-2})$, where $C_{3}$ depends
only on $R_{3}$ and $C^{3}$-smoothness of $r^{\prime}$. Thus, there exists a
function

$p(t,s)=\sum_{m=1}^{M-3}c_{m}^{3}\sigma(a_{m}^{3}t+b_{m}^{3}s+d_{m}^{3})\quad\text{with}~{}\sum{m=1}^{M_{3}}\left\lvert
c_{m}^{3}\right\rvert\leq C_{3},~{}\left\lvert
a_{m}^{3}\right\rvert+\left\lvert b_{m}^{3}\right\rvert+\left\lvert
d_{m}^{3}\right\rvert\leq 1~{}(\forall m),$ (68)

such that $\sup_{(s,t)\in[-R_{3},R_{3}]^{2}}\left\lvert p(s,t)-(\pm s)\cdot
r^{\prime}(t)\right\rvert\leq\epsilon_{p}$. The gradients for gradient descent
can be computed by using $p$ and $\bar{r}$. To this end, we use matrices
$\\{{\bm{Q}}_{k,m,n},{\bm{K}}_{k,m,n},{\bm{V}}_{k,m,n}\\}_{k=1,\dots,K}^{m=1,\dots,M_{3}}$
for $n=1,\dots,4$ such that

$\displaystyle{\bm{Q}}_{k,m,1}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}a_{m}^{3}w_{k}\\\ b_{m}^{3}{\bm{u}}_{k}\\\
d_{m}^{3}\\\ {\bm{0}}\end{bmatrix},\quad{\bm{K}}_{k,m,1}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}g_{\Lambda,j}\\\ {\bm{x}}_{i}\\\ 1\\\
{\bm{0}}\end{bmatrix},\quad{\bm{V}}_{k,m,1}{\bm{h}}_{j}=$
$\displaystyle-\frac{(N+1)\eta c_{m}^{3}}{n}\begin{bmatrix}{\bm{0}}\\\
{\bm{x}}_{j}\\\ {\bm{0}}\end{bmatrix}$ (69)
$\displaystyle{\bm{Q}}_{k,m,2}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}a_{m}^{1}{\bm{u}}_{k}\\\ b_{m}^{1}\\\
{\bm{0}}\end{bmatrix},\quad{\bm{K}}_{k,m,2}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}{\bm{x}}_{j}\\\ 1\\\
{\bm{0}}\end{bmatrix},\quad{\bm{V}}_{k,m,2}{\bm{h}}_{j}=$
$\displaystyle-\frac{(N+1)\eta c_{m}^{1}}{n}\begin{bmatrix}{\bm{0}}\\\
g_{\Lambda,j}\\\ {\bm{0}}\end{bmatrix}$ (70)
$\displaystyle{\bm{Q}}_{k,m,3}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}a_{m}^{3}v_{k}\\\ b_{m}^{3}{\bm{u}}_{k}\\\
d_{m}^{3}\\\ {\bm{0}}\end{bmatrix},\quad{\bm{K}}_{k,m,3}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}g_{\Delta,j}\\\ {\bm{x}}_{j}\\\ 1\\\
{\bm{0}}\end{bmatrix},\quad{\bm{V}}_{k,m,3}{\bm{h}}_{j}=$
$\displaystyle\frac{(N+1)\lambda\eta c_{m}^{3}}{N}\begin{bmatrix}{\bm{0}}\\\
{\bm{x}}_{j}\\\ {\bm{0}}\end{bmatrix}$ (71)
$\displaystyle{\bm{Q}}_{k,m,4}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}a_{m}^{1}{\bm{u}}_{k}\\\ b_{m}^{1}\\\
{\bm{0}}\end{bmatrix},\quad{\bm{K}}_{k,m,4}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}{\bm{x}}_{j}\\\ 1\\\
{\bm{0}}\end{bmatrix},\quad{\bm{V}}_{k,m,4}{\bm{h}}_{j}=$
$\displaystyle-\frac{(N+1)\lambda\eta c_{m}^{1}}{N}\begin{bmatrix}{\bm{0}}\\\
g_{\Delta,j}\\\ {\bm{0}}\end{bmatrix}$ (72)

with norm bounds of

$\max_{k,m,n}\left\lVert{\bm{Q}}_{k,m,n}\right\rVert\leq
1,\quad\max_{k,m,n}\left\lVert{\bm{K}}_{k,m,n}\right\rVert\leq
1,\quad\sum_{k,m,n}\left\lVert{\bm{V}}_{k,m,n}\right\rVert\leq
4\eta(C_{1}+C_{3}).$ (73)

Then, we have

$\displaystyle\widehat{G}\coloneqq$
$\displaystyle\frac{1}{N+1}\sum_{j=1}^{N+1}\sum_{k,m,n}\sigma(\langle{\bm{Q}}_{k,m,n}{\bm{h}}_{i},{\bm{K}}_{k,m,n}{\bm{h}}_{j}\rangle){\bm{V}}_{k,m,n}{\bm{h}}_{j}$
(74) $\displaystyle=$
$\displaystyle-\frac{\eta}{n}\sum_{j=1}^{n}\begin{bmatrix}{\bm{0}}_{d+4}\\\
p(w_{1}g_{\Lambda,j},{\bm{u}}_{1}^{\top}{\bm{x}}_{j})\cdot{\bm{x}}_{j}\\\
\vdots\\\
p(w_{K}g_{\Lambda,j},{\bm{u}}_{1}^{\top}{\bm{x}}_{j})\cdot{\bm{x}}_{j}\\\
\bar{r}({\bm{u}}_{1}^{\top}{\bm{x}}_{j})\cdot g_{\Lambda,j}\\\ \vdots\\\
\bar{r}({\bm{u}}_{K}^{\top}{\bm{x}}_{j})\cdot g_{\Lambda,j}\\\ 0\\\ \vdots\\\
0\\\
{\bm{0}}_{4}\end{bmatrix}-\frac{\eta}{N}\sum_{j=1}^{N}\begin{bmatrix}{\bm{0}}_{d+4}\\\
-\lambda
p(v_{1}g_{\Delta,j},{\bm{u}}_{1}^{\top}{\bm{x}}_{j})\cdot{\bm{x}}_{j}\\\
\vdots\\\ -\lambda
p(v_{K}g_{\Delta,j},{\bm{u}}_{1}^{\top}{\bm{x}}_{j})\cdot{\bm{x}}_{j}\\\ 0\\\
\vdots\\\ 0\\\ \bar{r}({\bm{u}}_{1}^{\top}{\bm{x}}_{j})\cdot g_{\Delta,j}\\\
\vdots\\\ \bar{r}({\bm{u}}_{K}^{\top}{\bm{x}}_{j})\cdot g_{\Delta,j}\\\
{\bm{0}}_{4}\end{bmatrix}.$ (75)

For $\Lambda$, as $\left\lvert p(s,t)-s\cdot
r^{\prime}(t)\right\rvert\leq\epsilon_{p}$, we have

$\displaystyle\left\lvert
p({\bm{w}}_{k}g_{\Lambda,j},{\bm{u}}_{k}^{\top}{\bm{x}}_{j})-\partial\gamma(\Lambda({\bm{x}}_{j}),y_{j})\cdot
w_{k}\cdot r^{\prime}({\bm{u}}_{k}^{\top}{\bm{x}}_{j})\right\rvert$
$\displaystyle\leq\epsilon_{p}+\left\lvert
g_{\Lambda,j}-\partial_{1}\gamma(\Lambda({\bm{x}}_{j}),y_{j})\right\rvert\cdot\left\lvert
w_{k}\right\rvert\cdot\left\lvert
r^{\prime}({\bm{u}}_{k}^{\top}{\bm{x}}_{j})\right\rvert$ (76)
$\displaystyle\leq\epsilon_{p}+B_{u}L_{r}(\epsilon_{\gamma}L_{\gamma}\epsilon_{r}),$
(77)

where $L_{r}=\max\left\lvert r^{\prime}(t)\right\rvert$. Also,

$\left\lvert\bar{r}({\bm{u}}_{k}^{\top}{\bm{x}}_{j})\cdot
g_{\Lambda,j}-r({\bm{u}}_{k}^{\top}{\bm{x}}_{j})\cdot\gamma(\Lambda({\bm{x}}_{j}),y_{j})\right\rvert\leq
B_{g}\epsilon_{r}+B_{r}(\epsilon_{\gamma}+B_{u}L_{\gamma}\epsilon_{r}).$ (78)

The same holds for $\Delta$. Consequently, letting the actual gradient
corresponding to $\widehat{G}$ be $G$, we have

$\frac{1}{\eta}\left\lVert\widehat{G}-G\right\rVert_{2}\leq\sqrt{K}B_{x}(\epsilon_{p}+B_{u}L_{r}(\epsilon_{\gamma}+B_{u}L_{\gamma}\epsilon_{r}))+2\sqrt{K}(B_{g}\epsilon_{r}+B_{r}(\epsilon_{\gamma}+B_{u}L_{\gamma}\epsilon_{r})).$
(79)

By choosing $\epsilon_{p},\epsilon_{\gamma},\epsilon_{r}$ appropriately, we
can ensure $\left\lVert\widehat{G}-G\right\rVert\leq\eta\epsilon$. Thus, we
have an attention block
${\bm{h}}^{\prime\prime}\mapsto{\bm{h}}^{\prime\prime\prime}_{i}=[{\bm{x}}_{i},y_{i},t_{i},s_{i},1,{\bm{u}}-\eta\nabla_{{\bm{u}}}(L-\lambda\Omega),{\bm{w}}-\eta\nabla_{\bm{w}}L,{\bm{v}}-\eta\nabla_{\bm{v}}\Omega,{\bm{0}},\bar{\Lambda}({\bm{x}}_{i}),\bar{\Delta}({\bm{x}}_{i}),g_{\Lambda,i},g_{\Delta,i}]$.

  4. Step 4:

(The MLP block of the second layer) This block projects the weights onto
$\mathcal{W}$ and fill the last four elements of
${\bm{h}}^{\prime\prime\prime}_{i}$ with zeros, that is,
${\bm{h}}^{\prime\prime\prime}_{i}\mapsto[{\bm{x}}_{i},y_{i},t_{i},s_{i},1,\Pi_{\mathcal{W}}({\bm{u}}^{\prime}),\Pi_{\mathcal{W}}({\bm{w}}^{\prime}),\Pi_{\mathcal{W}}({\bm{v}}^{\prime}),{\bm{0}}_{4}]$.
By assumption, such a block exists.

∎

###  A.3 In-context UDA Algorithm Selection

######  Lemma 9.

Suppose that the density $p_{S}$ is Lipschitz continuous. Define a density
estimator
$\widehat{p}_{S}(\cdot):=(nh)^{-1}\sum_{i=1}^{n^{\prime}}K^{\prime}({\bm{x}},{\bm{x}}_{i}^{T})$
with a bandwidth $h>0$ and some kernel function $K^{\prime}$, which is
continuous and satisfying $\inf K^{\prime}d=1$. Fix $\varepsilon>0$. For
$n^{\prime}\geq\varepsilon^{-1/3}\log n$, with probability at least $1-1/n$,
we obtain

$\displaystyle\sup_{{\bm{x}}\in\mathcal{X}}|p_{S}({\bm{x}})-\widehat{p}_{S}({\bm{x}})|\leq\varepsilon.$
(80)

###### Proof of Lemma 9.

We regard the kernel function $K^{\prime}$ as parameterized by the bandwidth
parameter $h$ as $K^{\prime}_{h}$, such that
$\widehat{p}_{S}(\cdot)=(nh)^{-1}\sum_{i=1}^{n}K^{\prime}_{h}({\bm{x}},{\bm{x}}_{i})$
as a kernel function specified in Jiang (2017). We apply Theorem 2 in Jiang
(2017), then we obtain the statement. ∎

###### Proof of Theorem 3.

We show the theorem in the following steps. We use a three-layer Transformer:
the first self-attention block constructs a kernel density approximation
$p_{i}=\widehat{p}_{S}({\bm{x}}_{i})$, the succeeding MLP block computes
$\exp(-p_{i})$, then the next self-attention block computes
$\sum_{i}\exp(-\beta p_{i})$, and then, the MLP layer computes
$-\beta\sum_{i}\exp(-\beta p_{i})$, and the attention block of the third
Transformer layer selects the final output from the outputs of UDA algorithms
based on $-\beta\log\sum_{i}\exp(-\beta p_{i})>\delta$.

  1. Step 1:

(The self-attention block of the first layer) This block constructs kernel
density estimation of the source domain
$\widehat{p}_{S}(\cdot)=\frac{1}{n}\sum_{i=1}^{n}K(\cdot,{\bm{x}}_{i})$, where
$K$ is a kernel function, and obtains $p_{i}=\widehat{p}_{S}({\bm{x}}_{i})$
for $i=1,\dots N$. We adopt the RBF kernel as $K$, as it is universal. As the
RBF kernel $({\bm{x}},{\bm{x}}^{\prime})\mapsto K({\bm{x}},{\bm{x}}^{\prime})$
is $(\epsilon_{1},B_{x},M_{1},C_{1})$-approximable, there exists a function
$\bar{K}$ such that

$\bar{K}({\bm{x}},{\bm{x}}^{\prime})=\sum_{i=1}^{M_{1}}c_{m}\sigma({\bm{a}}_{m}^{\top}{\bm{x}}+{\bm{b}}_{m}^{\top}{\bm{x}}^{\prime}+d_{m}),\quad\text{with
}\sum_{m=1}^{M_{1}}|c_{m}|\leq C_{1},|{\bm{a}}_{m}|+|{\bm{b}}_{m}|+d_{m}\leq
1~{}(\forall m),$ (81)

where
$\sup_{({\bm{x}},{\bm{x}}^{\prime})\in[-B_{x},B_{x}]^{d}\times[-B_{x},B_{x}]^{d}}|K({\bm{x}},{\bm{x}}^{\prime})-\bar{K}({\bm{x}},{\bm{x}}^{\prime})|\leq\epsilon_{1}$.
A self-attention layer can represent $\bar{K}$ with matrices

$\displaystyle{\bm{Q}}_{m}{\bm{h}}_{i}=\begin{bmatrix}{\bm{a}}_{m}\\\
{\bm{x}}_{i}\\\ d_{m}\\\ -2B_{x}\\\
{\bm{0}}_{D-2(d+1)}\end{bmatrix},\quad{\bm{K}}_{m}{\bm{h}}_{j}=\begin{bmatrix}{\bm{x}}_{j}\\\
{\bm{b}}_{m}\\\ 1\\\ 1-t_{j}\\\
{\bm{0}}_{D-2(d+1)}\end{bmatrix},\quad{\bm{V}}_{m}{\bm{h}}_{j}=c_{m}\frac{N+1}{n}\begin{bmatrix}{\bm{0}}_{D-5}\\\
1\\\ {\bm{0}}_{4}\end{bmatrix}.$ (82)

These matrices exist, and we obtain

$\displaystyle\frac{1}{N+1}\sum_{j=1}^{N+1}\sum_{m=1}^{M_{1}}\sigma(\langle{\bm{Q}}_{m}{\bm{h}}_{i},{\bm{K}}_{m}{\bm{h}}_{j}\rangle){\bm{V}}_{m}{\bm{h}}_{j}$
(83) $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{j=1}^{N+1}\sum_{m=1}^{M_{1}}c_{m}\sigma({\bm{a}}_{m}^{\top}{\bm{x}}_{i}+{\bm{b}}_{m}^{\top}{\bm{x}}_{j}+d_{m}-2B_{x}(1-t_{j}))[{\bm{0}}_{D-5},1,{\bm{0}}_{4}]$
(84) $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{j=1}^{n}\bar{K}({\bm{x}}_{i},{\bm{x}}_{j})[{\bm{0}}_{D-5},1,{\bm{0}}_{4}].$
(85)

Letting $p_{i}=\frac{1}{n}\sum_{j=1}^{n}\bar{K}({\bm{x}}_{i},{\bm{x}}_{j})$,
the output of this layer is
${\bm{h}}^{(1)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),{\bm{0}}_{5}]$
to
${\bm{h}}^{\prime(1)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},{\bm{0}}_{4}]$.

  2. Step 2:

(The MLP block of the first layer) Because $p\mapsto\exp(-\beta p)$ is
$(\epsilon_{2},1,M_{2},C_{2})$-approximable, there exists a function $e(t)$,
where

$e(t)=\sum_{m=1}^{M_{2}}c_{m}\sigma(a_{m}t+b_{m})\quad\text{with
}\sum_{m=1}^{M_{2}}|c_{m}|\leq C_{2},|a_{m}|+|b_{m}|\leq 1~{}(\forall m),$
(86)

such that $\sup_{t\in[-R_{2},R_{2}]}|e(t)-\exp(-\beta t)|\leq\epsilon_{2}$. By
choosing matrices ${\bm{W}}_{1},{\bm{W}}_{2}$ such that
${\bm{W}}_{1}\in\mathbb{R}^{M_{2}\times D}$ such that

${\bm{W}}_{1}{\bm{h}}^{\prime}_{i}=[a_{m}p_{i}+b_{m}]_{m=1}^{M_{2}},$ (87)

and ${\bm{W}}_{2}\in\mathbb{R}^{D\times M_{2}}$ consisting of elements of

$({\bm{W}}_{2})_{j,m}=c_{m}\mathbbm{1}(j=D-4),$ (88)

so that

${\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{h}}^{\prime}_{i})=\sum_{m=1}^{M_{2}}\sigma(a_{m}p_{i}+b_{m})c_{m}{\bm{e}}_{D-4}.$
(89)

Consequently, this block maps
${\bm{h}}^{\prime(1)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},{\bm{0}}_{4}]$
to
$\widetilde{{\bm{h}}}^{(1)}_{i}={\bm{h}}^{(2)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},e(p_{i}),{\bm{0}}_{3}]$.

  3. Step 3:

(The Attention block of the second layer) With a single-head self-attention
block, we get $\sum_{i=n}^{n+n^{\prime}}e(p_{I})$ with the following matrices:

$\displaystyle{\bm{Q}}_{1}{\bm{h}}_{i}=\begin{bmatrix}1\\\ 1\\\
{\bm{0}}_{D-2}\end{bmatrix},\quad{\bm{K}}_{1}{\bm{h}}_{j}=\begin{bmatrix}e(p_{i})\\\
1-(t_{j}-s_{j})\\\
{\bm{0}}_{D-2}\end{bmatrix},\quad{\bm{V}}_{1}{\bm{h}}_{j}=(N+1)\begin{bmatrix}{\bm{0}}_{D-3}\\\
1\\\ {\bm{0}}_{2}\end{bmatrix},$ (90)

so that

$\displaystyle\sum_{j=1}^{N+1}\sigma(\langle{\bm{Q}}_{1}{\bm{h}}_{i},{\bm{K}}_{1}{\bm{h}}_{j}\rangle){\bm{V}}_{1}{\bm{h}}_{j}=\sum_{j=1}^{N+1}e(p_{i})\mathbbm{1}(n+1\leq
j\leq
n+n^{\prime})[{\bm{0}}_{D-3},1,{\bm{0}}_{2}]=[{\bm{0}}_{D-3},\sum_{j=n}^{n+n^{\prime}}e(p_{i}),{\bm{0}}_{2}].$
(91)

Thus, this block maps
${\bm{h}}^{(2)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},e(p_{i}),{\bm{0}}_{3}]$
to
${\bm{h}}^{\prime(2)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},e(p_{i}),\sum_{j=n}^{n+n^{\prime}}e(p_{j}),{\bm{0}}_{2}]$

  4. Step 4:

(The MLP block of the second layer) Since $\log$ is
$(\epsilon_{4},n^{\prime},M_{4},C_{4})$-approximable by sum-of-ReLUs, there
exists a function $\mu(t)$, where

$\mu(t)=\sum_{m=1}^{M_{4}}c_{m}\sigma(a_{m}t+b_{m})\quad\text{with}\sum_{m=1}^{M_{4}}|c_{m}|\leq
C_{4},|a_{m}|+|b_{m}|\leq 1~{}(\forall m),$ (92)

such that $\sup_{t\in(0,n^{\prime})}|\mu(t)-\log(t)|\leq\epsilon_{4}$. By
selecting matrices ${\bm{W}}_{1},{\bm{W}}_{2}$ such that
${\bm{W}}_{2}\in\mathbb{R}^{1\times D}$ such that

${\bm{W}}_{1}{\bm{h}}_{i}=[a_{m}e+b_{m}]_{m=1}^{M_{4}},$ (93)

and ${\bm{W}}_{2}\in\mathbb{R}^{D\times 1}$ consisting of elements of

$({\bm{W}}_{2})_{j,m}=-\frac{1}{\beta}\mathbbm{1}(j=D),$ (94)

so that

$\displaystyle{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{h}}_{i})$ (95)
$\displaystyle=$
$\displaystyle-\frac{1}{\beta}\sum_{m=1}^{M_{4}}c_{m}\sigma(a_{m}e+b_{m})[{\bm{0}},1,0]$
(96) $\displaystyle=$
$\displaystyle[{\bm{0}},-\frac{1}{\beta}\mu(\sum_{j=n}^{n+n^{\prime}}e(p_{i})),0].$
(97)

As a result, by letting
$q=-\frac{1}{\beta}\mu(\sum_{j=n}^{n+n^{\prime}}e(p_{i}))$, this block maps
${\bm{h}}^{\prime(2)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},e(p_{i}),\sum_{j=n}^{n+n^{\prime}}e(p_{i}),{\bm{0}}_{2}]$
to
$\widetilde{{\bm{h}}}^{(2)}_{i}={\bm{h}}^{(3)}_{i}=[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},e(p_{i}),\sum_{j=n}^{n+n^{\prime}}e(p_{i}),q,0]$.

  5. Step 5:

(The self-attention block of the third layer) The outputs of UDA algorithms
can be selected by
$\mathbbm{1}(q\geq\delta)\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{*})+(1-\mathbbm{1}(q\geq\delta))\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{*})$.
This process can be approximated by
$\widehat{\mathbbm{1}}_{a}(t,s)=\sigma(a(t-s)+0.5)-\sigma(a(t-s)-0.5)$, where
$a>0$, which approximates $\mathbbm{1}(t\geq s)$ as $|\mathbbm{1}(t\geq
s)-\widehat{\mathbbm{1}}_{a}(t,s)|=\frac{1}{2a}$. This process can be
represented by a self-attention layer with four heads consisting of the
following matrices:

$\displaystyle{\bm{Q}}_{1}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}aq-a\delta+0.5\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{K}}_{1}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}1\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{V}}_{1}{\bm{h}}_{j}=$
$\displaystyle(N+1)\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{*}){\bm{e}}_{D},$
(98) $\displaystyle{\bm{Q}}_{2}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}aq-a\delta-0.5\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{K}}_{2}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}1\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{V}}_{2}{\bm{h}}_{j}=$
$\displaystyle-(N+1)\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{*}){\bm{e}}_{D},$
(99) $\displaystyle{\bm{Q}}_{3}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}aq-a\delta+0.5\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{K}}_{3}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}1\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{V}}_{3}{\bm{h}}_{j}=$
$\displaystyle(N+1)\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{*}){\bm{e}}_{D},$
(100) $\displaystyle{\bm{Q}}_{4}{\bm{h}}_{i}=$
$\displaystyle\begin{bmatrix}aq-a\delta-0.5\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{K}}_{4}{\bm{h}}_{j}=$
$\displaystyle\begin{bmatrix}1\\\
{\bm{0}}_{D-1}\end{bmatrix},\quad{\bm{V}}_{4}{\bm{h}}_{j}=$
$\displaystyle-(N+1)\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{*}){\bm{e}}_{D},$
(101)

so that

$\displaystyle\sum_{m=1,\dots,4}\sigma(\langle{\bm{Q}}_{m}{\bm{h}}_{i},{\bm{K}}_{m}{\bm{h}}_{j}\rangle){\bm{V}}_{m}{\bm{h}}_{j}$
(102) $\displaystyle=$
$\displaystyle\\{\sigma(a(q-\delta)+0.5)-\sigma(a(q-\delta)-0.5)\\}\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{*}){\bm{e}}_{D}$
(103) $\displaystyle+$
$\displaystyle\\{1-\sigma(a(q-\delta)+0.5)+\sigma(a(q-\delta)-0.5)\\}\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{*}){\bm{e}}_{D}$
$\displaystyle=$
$\displaystyle\widehat{\mathbbm{1}}_{a}(q,\delta)\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}){\bm{e}}_{D}+(1-\widehat{\mathbbm{1}}_{a}(q,\delta))\widetilde{f}({\bm{x}}_{i})^{\mathrm{DANN}}{\bm{e}}_{D}.$
(104)

Letting
$\widetilde{f}({\bm{x}}_{i})=\widehat{\mathbbm{1}}_{a}(q,\delta)\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}){\bm{e}}_{D}+(1-\widehat{\mathbbm{1}}_{a}(q,\delta))\widetilde{f}({\bm{x}}_{i})^{\mathrm{DANN}}{\bm{e}}_{D}$,
this block finally outputs
$[{\bm{z}}_{i},{\bm{\gamma}},\widetilde{f}^{\mathrm{IWL}}({\bm{x}}_{i}),\widetilde{f}^{\mathrm{DANN}}({\bm{x}}_{i}),p_{i},e(p_{i}),\sum_{j=n}^{n+n^{\prime}}e(p_{i}),q,\widetilde{f}({\bm{x}}_{i})]$.

We have

$\displaystyle\left\lVert\widetilde{f}-\widehat{f}^{\mathrm{ICUDA}}\right\rVert$
(105) $\displaystyle=$
$\displaystyle\left\lVert(\widetilde{\zeta}\widetilde{f}^{\mathrm{IWL}}+(1-\widetilde{\zeta})\widetilde{f}^{\mathrm{DANN}})-(\zeta\widehat{f}^{\mathrm{IWL}}+(1-\zeta)\widehat{f}^{\mathrm{DANN}})\right\rVert$
(106) $\displaystyle\leq$
$\displaystyle\left\lVert\widetilde{\zeta}\right\rVert\left\lVert\widetilde{f}^{\mathrm{IWL}}-\widehat{f}^{\mathrm{IWL}}\right\rVert+\left\lVert\widetilde{\zeta}-\zeta\right\rVert\left\lVert\widehat{f}^{\mathrm{DANN}}-\widehat{f}^{\mathrm{IWL}}\right\rVert+\left\lVert
1-\widetilde{\zeta}\right\rVert\left\lVert\widetilde{f}^{\mathrm{DANN}}-\widehat{f}^{\mathrm{DANN}}\right\rVert$
(107) $\displaystyle\leq$
$\displaystyle\left\lVert\widetilde{f}^{\mathrm{IWL}}-\widehat{f}^{\mathrm{IWL}}\right\rVert+C\left\lVert\widetilde{\zeta}-\zeta\right\rVert+\left\lVert\widetilde{f}^{\mathrm{DANN}}-\widehat{f}^{\mathrm{DANN}}\right\rVert$
(108) $\displaystyle\leq$
$\displaystyle\epsilon_{\mathrm{IWL}}+\epsilon_{\mathrm{DANN}}+C\left\lVert\widetilde{\zeta}-\zeta\right\rVert,$
(109)

where $\widetilde{\zeta}=\widehat{\mathbbm{1}}_{a}(q,\delta)$,
$\zeta=\mathbbm{1}(\min_{i}\widehat{p}_{S}({\bm{x}}_{i})>\delta)$, and
$C=\left\lVert\widetilde{f}^{\mathrm{DANN}}-\widehat{f}^{\mathrm{DANN}}\right\rVert$.
Further, defining
$r=\operatorname*{softmin}_{\beta}\widehat{p}_{S}({\bm{x}}_{i})$, we obtain

$\displaystyle\left\lVert\widetilde{\zeta}-\zeta\right\rVert$
$\displaystyle=\left\lVert\mathbbm{1}(r>\delta)-\widehat{\mathbbm{1}}_{a}(q,\delta)\right\rVert$
(110)
$\displaystyle\leq\left\lVert\mathbbm{1}(r>\delta)-\widehat{\mathbbm{1}}_{a}(r,\delta)\right\rVert+\left\lVert\widehat{\mathbbm{1}}_{a}(r,\delta)-\widehat{\mathbbm{1}}_{a}(q,\delta)\right\rVert$
(111)
$\displaystyle\leq\frac{1}{2a}+\left\lVert\widehat{\mathbbm{1}}_{a}(r,\delta)-\widehat{\mathbbm{1}}_{a}(q,\delta)\right\rVert$
(112)

Assuming $r$ is random, and its density is bounded, the second term is
$\left\lVert\widehat{\mathbbm{1}}_{a}(r,\delta)-\widehat{\mathbbm{1}}_{a}(q,\delta)\right\rVert=0$
with probability of $1-O(|r-q|)$. Here, we have

$\displaystyle|r-q|$
$\displaystyle\leq|\operatorname*{softmin}_{\beta}\widehat{p}_{S}-\operatorname*{softmin}_{\beta}p_{S}|B_{x}+|\operatorname*{softmin}_{\beta}p_{S}-\min
p_{S}|B_{x}$ (113)
$\displaystyle\leq\|\operatorname*{softmin}_{\beta}\|\|\widehat{p}_{S}-p_{S}\|B_{x}+\|\operatorname*{softmin}_{\beta}-\min\|\|p_{S}\|B_{x}$
(114) $\displaystyle\leq\frac{\log n}{\beta}\epsilon^{\prime}B_{x}+\frac{\log
n}{\beta}B_{x},$ (115)

where $\epsilon^{\prime}=\|\widehat{p}_{S}-p_{S}\|$. We used
$\operatorname*{softmin}_{\beta}p_{i}=-\frac{1}{\beta}\log\sum_{i}^{n}\exp(-\beta
p_{i})\leq\frac{1}{\beta}\log n$ and
$|\operatorname*{softmin}_{\beta}p_{i}-\min p_{i}|\leq\frac{\log n}{\beta}$
for $(p_{1},\dots,p_{n})$ such that $p_{i}\geq 0$. Hence, we can obtain
$|r-q|<\epsilon$ with sufficiently large $\beta$. Thus, by properly selecting
$a,\beta,\epsilon_{\mathrm{IWL}},\epsilon_{\mathrm{DANN}}$,
$\left\lVert\widetilde{f}-\widehat{f}^{\mathrm{ICUDA}}\right\rVert$ can be
upper bounded by any $\epsilon>0$ with probability at least
$1-1/n^{\prime}-O(|r-q|)=1-1/n^{\prime}-O(\epsilon)$. ∎

##  Appendix B Experimental Details

For the experiments, we used a machine equipped with an AMD EPYC 7543P 32-core
CPU and an NVIDIA RTX 6000 Ada GPU with CUDA 12.4. The Transformer model and
the baselines were implemented with PyTorch v2.3 (Paszke et al., 2019).

###  B.1 Two-moon 2D

In this problem, the source distribution is two-moon-shaped, and the target
distribution is its random rotation, where the rotation is uniformly chosen
between $-\pi/3$ and $\pi/3$. Gaussian noise of a standard deviation of 0.1 is
added to each data point. During the pre-training of the Transformer model,
the source distribution is randomly rotated.

We used a Transformer model with eight layers, eight heads, and an embed
dimension of 128 without Layer Normalization and trained it with an AdamW
optimizer (Loshchilov & Hutter, 2019) of a learning rate of $10^{-4}$ and a
weight decay of $10^{-2}$ with a batch size of 64 for $10^{4}$ iterations. The
baseline models were optimized for $10^{4}$ iterations using an Adam optimizer
(Kingma & Ba, 2015) with the full batch. uLSIF was trained with a learning
rate of $0.1$, and the regularization term $\lambda$ was set to $1.0$. DANN
was trained with a learning rate of $0.1$, and the regularization term
$\lambda$ was set to $1.0$. The source-only neural network follows the DANN’s
setup.

###  B.2 Colorized MNIST

In this setting, images of two digits are selected from the MNIST dataset to
make a binary classification problem. Images are downsampled to $8\times 8$
pixels. Their background colors depend on domains, where the color of the
source domain is a given RGB color, and that of the target domain is its
complement. During the pertaining phase, digits and colors are randomly
chosen.

We trained the Transformer model with the same setting as the Two-moon 2D
problem, except for the embed dimension set to 256. The baseline models were
optimized for $10^{4}$ iterations using an Adam optimizer with the full batch.
uLSIF was trained with a learning rate of $0.1$ and the regularization term
$\lambda$ was set to $1.0$. DANN was trained with a learning rate of
$10^{-3}$, and the regularisation term $\lambda$ was set to $10$. The source-
only neural network follows the DANN’s setup.