[Manolis]mzBittersweet [Ilias]izgreen [Alkis]akblue

# Transfer Learning Beyond Bounded Density Ratios

Alkis Kalavasis⋆, Ilias Zadik∘,⋆ and Manolis Zampetakis†,⋆

###### Abstract.

We study the fundamental problem of transfer learning where a learning
algorithm collects data from some source distribution $P$ but needs to perform
well with respect to a different target distribution $Q$. A standard change of
measure argument implies that transfer learning happens when the density ratio
$dQ/dP$ is bounded. Yet, prior thought-provoking works by Kpotufe and Martinet
(COLT, 2018) and Hanneke and Kpotufe (NeurIPS, 2019) demonstrate cases where
the ratio $dQ/dP$ is unbounded, but transfer learning is possible.

In this work, we focus on transfer learning over the class of _low-degree
polynomial estimators_. Our main result is a general transfer inequality over
the domain $\mathbb{R}^{n}$, proving that non-trivial transfer learning for
low-degree polynomials is _possible under very mild assumptions_ , going well
beyond the classical assumption that $dQ/dP$ is bounded. For instance, it
always applies if $Q$ is a log-concave measure and _the inverse ratio_ $dP/dQ$
is bounded. To demonstrate the applicability of our inequality, we obtain new
results in the settings of: (1) the classical truncated regression setting,
where $dQ/dP$ equals infinity, and (2) the more recent out-of-distribution
generalization setting for in-context learning linear functions with
transformers.

We also provide a discrete analogue of our transfer inequality on the Boolean
Hypercube $\\{-1,1\\}^{n}$, and study its connections with the recent problem
of Generalization on the Unseen of Abbe, Bengio, Lotfi and Rizk (ICML, 2023).
Our main conceptual contribution is that the maximum influence of the error of
the estimator $\hat{f}-f^{\star}$ under $Q$,
$\mathrm{I}_{\max}(\hat{f}-f^{\star})$, acts as a sufficient condition for
transferability; when $\mathrm{I}_{\max}(\hat{f}-f^{\star})$ is appropriately
bounded, transfer is possible over the Boolean domain.

The main techniques for proving our results are the Carbery-Wright anti-
concentration inequality and the invariance principle of Mossel, O’Donnell and
Oleszkiewicz (Annals of Mathematics, 2010).

∘Department of Statistics and Data Science, Yale University; †Department of
Computer Science, Yale University. ⋆Institute of Foundations of Data Science,
Yale University;
Email: {alvertos.kalavasis, ilias.zadik<EMAIL_ADDRESS>
##  1\. Introduction

Transfer learning is a pivotal concept in Statistics and Machine Learning that
addresses the challenge of applying knowledge gained from one domain (the
_source_) to improve performance in a different, yet related domain (the
_target_). This approach is particularly relevant in scenarios where the
distribution of data in the target domain, denoted as $Q$, differs from that
of the source domain, characterized by distribution $P$. A rich body of
research, including the works by [HK19, HKM23, YHC13, RMH+20, TJJ20, BDBC+10,
BDBCP06, PMW22], and others, has extensively explored transfer learning from
various angles, underscoring its theoretical and practical significance. This
concept, also known as Out-Of-Distribution (OOD) Generalization or Domain
Adaptation, is crucial for understanding how algorithms can be trained on data
from the source domain and then adeptly applied to the target domain. The
quest to pinpoint the exact nature of distributional similarity that
facilitates successful transfer remains a central, yet not well-understood,
inquiry in this domain.

The concept of transfer learning can be encapsulated within the framework of a
standard regression problem. Here, our goal is to identify a _regressor_ $f$
that aims to minimize the mean squared error $\mathbb{E}_{x\sim
P}[(f(x)-f^{\star}(x))^{2}]$, using samples in the form $(x,y)$, where $x$ is
drawn from distribution $P$ and $\mathbb{E}[y|x]=f^{\star}(x)$. The twist in
transfer learning emerges when the objective shifts towards minimizing the
expected error $\mathbb{E}_{x\sim Q}[(f(x)-f^{\star}(x))^{2}]$, despite the
fact that our available samples are drawn from $P$. This raises the pivotal
question: is it possible to establish a relationship between the expected
errors $\mathbb{E}_{x\sim P}[(f(x)-f^{\star}(x))^{2}]$ and $\mathbb{E}_{x\sim
Q}[(f(x)-f^{\star}(x))^{2}]$? In essence, this inquiry delves into the
capability of the regressor $f$ to _extrapolate_ effectively to samples that
are out-of-distribution, originating from the target distribution $Q$, based
on its training with the source distribution $P$.111Throughout the paper, when
talking about the Euclidean domain, we consider a probability space
$(\Omega,\mathcal{F},(P,Q))$ where $\Omega=\mathbb{R}^{n}$ and for clarity we
will assume that both distributions $P$ and $Q$ are _continuous_
distributions. A natural approach to compare the mean squared error with
respect to $P$ with the mean squared error with respect to $Q$ is to apply a
change of measure:

$\displaystyle\mathbb{E}_{x\sim Q}[(f(x)-f^{\star}(x))^{2}]$
$\displaystyle=\mathbb{E}_{x\sim
P}\left[\frac{Q(x)}{P(x)}(f(x)-f^{\star}(x))^{2}\right]$
$\displaystyle\leq\left\lVert\frac{dQ}{dP}\right\rVert_{\infty}\mathbb{E}_{x\sim
P}[(f(x)-f^{\star}(x))^{2}]\,,$ (1.1)

where $\|dQ/dP\|_{\infty}=\sup_{x\in\mathrm{supp}(Q)}Q(x)/P(x)$ 222We note
that, instead of the ratio $\|dQ/dP\|_{\infty},$ applications of Hölder’s
inequality can yield different notions of divergence $\|dQ/dP\|_{r}\triangleq
D_{r}(Q\parallel P)=(\mathbb{E}_{x\sim P}[(Q(x)/P(x))^{r}])^{1/r}$ for $r\geq
1$ [Rén61] in (1.1).. Inequality (1.1), which is meaningful only when $Q$ is
absolutely continuous with respect to $P$, comes with a simple intuition: we
can think of the target distribution $Q$ as the “nature” and the source
distribution $P$ as the “model” aiming to approximate $Q$. If the (asymmetric)
divergence of $Q$ from $P$ (e.g., the $L_{\infty}$-norm of the density ratio
$dQ/dP$) is bounded, then, for any event $A$, if $P(A)=o(1)$, then it also
holds $Q(A)=o(1)$. Based on that, it is natural to expect that replacing the
“nature” $Q$ with the “model” $P$ is not very harmful; for instance, if
$f\approx f^{*}$ with probability $1-o(1)$ under $P$, then $f\approx f^{*}$
with probability $1-o(1)$ under $Q.$ This simple and intuitive idea has
inspired a line of work that explores transfer learning assuming an upper
bound on some norm of the likelihood ratio $dQ/dP$ [SSK12, SK12, SKM07, Kpo17,
QB13, KM18, CMM10, MPW23, PMW22].

This naturally leads us to question the validity of the assumption that the
ratio $\|dQ/dP\|_{\infty}$ remains within a bounded range. Unfortunately, this
ratio can potentially be unbounded in many relevant scenarios such as: (i)
truncation and censoring, which are fundamental challenges in Statistics, with
historical roots tracing back to the works of Galton [Gal98] and Pearson
[Pea02]; (ii) the innovative Generalization On The Unseen framework proposed
by [ABLR23]; (iii) straightforward distribution shifts like translation,
exemplified by the transition from a uniform distribution
$P=\mathcal{U}([0,1])$ to $Q=\mathcal{U}([1,2])$; and (iv) matrix completion
tasks involving data that is missing not at random, along with more complex
combinatorial distribution shifts as discussed by [SGZ23]. Additionally, even
in instances where the ratio is bounded, it can still attain exceedingly high
values. For example, the ratio of two isotropic Gaussian distributions with
different means, $\mu_{1}$ and $\mu_{2}$, escalates _exponentially_ with the
squared distance $\|\mu_{1}-\mu_{2}\|_{2}^{2}$ making inequality (1.1) very
weak even in this simple setting. Due to the many instances where the ratio
$dQ/dP$ is unbounded, a pertinent question arises:

_Is transfer learning possible when $\|dQ/dP\|_{r}\to\infty$? _

This question is further inspired by insightful findings from Kpotufe and
Martinet [KM18], as well as Hanneke and Kpotufe [HK19], within the framework
of nonparametric classification. These studies highlight scenarios in which
the ratio $\|dQ/dP\|_{r}$ is unbounded, yet still transfer successfully
happens. Our research is motivated by these observations and seeks to delve
into broader circumstances where, despite the large magnitude of this ratio,
transfer learning is feasible and effective.

###  1.1. Summary of Contributions

In this paper, we consider the expressive and well-studied class of _low-
degree polynomials_. Our main results are general transfer inequalities, for
functions in this class, under mild assumptions on the distribution pair $P$
and $Q$, going well beyond the boundedness of the ratio $dQ/dP$. In fact, we
can almost always bound the error with respect to $Q$ as a function of the
error with respect to $P$.

Transferability of Low-degree Polynomials in the Euclidean Domain. When the
domain of the covariates $x$ is the $n$-dimensional Euclidean space, we prove
the following theorem.

######  Informal Theorem 1 (See Theorem 2.3).

For any pair of degree-$d$ polynomials
$f,f^{\star}:\mathbb{R}^{n}\to\mathbb{R}$, any log-concave distribution $Q$
and any continuous distribution $P$, it holds that

$\mathbb{E}_{Q}[(f(x)-f^{\star}(x))^{2}]\leq
C_{d}\cdot\left\lVert\frac{dP}{dQ}\right\rVert_{\infty}^{2d}\cdot\mathbb{E}_{P}[(f(x)-f^{\star}(x))^{2}]\,,$
(1.2)

where $C_{d}>0$ is a constant depending only on the degree $d$. Furthermore,
even when $Q$ is not log-concave, it holds that

$\mathbb{E}_{Q}[(f(x)-f^{\star}(x))^{2}]\leq
C_{d}\cdot\inf_{\mu\in\mathcal{L}}\left\lVert\frac{dQ}{d\mu}\right\rVert_{\infty}\left\lVert\frac{dP}{d\mu}\right\rVert_{\infty}^{2d}\cdot\mathbb{E}_{P}[(f(x)-f^{\star}(x))^{2}]\,,$
(1.3)

where the infimum is over the set $\mathcal{L}$ of log-concave distributions
over $\mathbb{R}^{n}$ and $P$, $Q$ are arbitrary333Observe that it is
necessary for the inequality not being void to take the infimum over measures
$\mu\in\mathcal{L}$ whose support contains
$\mathrm{supp(P)\cup\mathrm{supp}(Q)}$. We refer to Section 2 for more
details..

Let us give some explanation of the results of the Theorem above.

Inequality (1.2) (The importance of $dP/dQ$):

If we compare (1.2) with (1.1) we observe the surprising fact that in (1.2)
the “inverse” ratio

$dP/dQ$

arises. Comparing the boundedness assumption on $dP/dQ$ with the naive
assumption that $dQ/dP$ is bounded, our inequality proves something perhaps
surprising. Even in cases where (i) the support of the source $P$ does not
contain that of $Q$, or, more generally, (ii) $P$ assigns much smaller
probability mass to some event compared to $Q$ (so that $dQ/dP$ becomes
extremely large), as long as $dP/dQ$ is bounded, the error with respect to $P$
still transfers to an error with respect to $Q$ for low-degree polynomials.

Inequality (1.3):

Combining (1.2) with the naive bound of (1.1), we get inequality (1.3). This
inequality allows us to show transferability even between distributions $P$
and $Q$ that have completely disjoint supports! Furthermore, the term

$\inf_{\mu\in\mathcal{L}}\left\lVert\frac{dQ}{d\mu}\right\rVert_{\infty}\left\lVert\frac{dP}{d\mu}\right\rVert_{\infty}^{2d}$

defines a novel quantitative notion of “transfer difference” between $P$ and
$Q$ that allows for transferability from $P$ to $Q$ for low-degree
polynomials.

Informal Theorem 1 is a general transferability result that can be applied in
various settings. To illustrate this we show the following applications of
this Theorem.

  1. (1)

Truncated Regression. We show that our inequality can be applied to regression
problems from truncated samples, a fundamental problem in statistical
literature; see as an example the recent work of [DGTZ19] and references
therein. Our result in Corollary 4.4 shows that, in such settings, the MSE in
the truncated domain upper bounds the MSE in the whole population in very
broad regression settings.

  2. (2)

Distribution Shift of Linear Attention. In-context learning linear functions
with linear attention was theoretically explored in [ZFB23] under Gaussianity
assumptions during the training of the model. In Section 4.2, we extend their
statistical results on distribution shifts for in-context learning linear
functions with linear attention in a much more general setting under mild
assumptions.

  3. (3)

Translations of Log-concave Densities. In Appendix B, we show that using our
inequality we can bound the transfer error when the source distribution is
log-concave and the target distribution is a translation of the source. This
illustrates that our result can handle simple transformations of the data.
Revisiting the example of two isotropic Gaussian distributions with different
means, $\mu_{1}$ and $\mu_{2}$, (discussed in the Introduction above) the
transfer coefficient that is implied by Informal Theorem 1 is of order
$\left\lVert\mu_{1}-\mu_{2}\right\rVert_{2}^{d}$, as opposed to
$\exp\left(\left\lVert\mu_{1}-\mu_{2}\right\rVert^{\Theta(1)}_{2}\right)$
which is what we get by applying the naive bound (1.1).

Transferability of Low-degree Polynomials in the Boolean Domain. Next we focus
on discrete domains and in particular on the Boolean domain $\\{-1,1\\}^{n}$.
In this setting, we need some additional assumptions than just that $f$,
$f^{\star}$ being polynomials. The main reason is that any function over
$\\{-1,1\\}^{n}$ can be expressed as a polynomial in the Fourier(-Walsh) basis
and transferability can be easily shown not to hold for all functions. Given
our inequality in the continuous domain, one may wonder if transfer holds as
long as we focus on low-degree Boolean functions. However, it is not difficult
to see that the low-degree assumption is not anymore sufficient for transfer
learning in discrete domains. For instance, let us consider the (shifted)
dictator (in direction $i=1$) function $f(x)=x_{1}+1$, which is a low-degree
non-negative polynomial, $Q$ be the uniform distribution over $\\{-1,1\\}^{n}$
and $P$ be the uniform distribution on the subset of the Boolean hypercube
with $\\{x_{1}=-1\\}.$ It is evident that $\mathbb{E}_{P}f=0,$ while
$\mathbb{E}_{Q}f=1$, which means that transfer from samples of $P$ to samples
of $Q$ does not hold, i.e., no inequality of the form
$\mathbb{E}_{Q}f^{2}=O(\mathbb{E}_{P}f^{2})$ is possible.

A reader familiar with Boolean Fourier analysis may realize that a potential
underlying issue with the dictator function is its _high influence_ 444Recall
that for a function $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ the influence
$\mathrm{Inf}_{i}(f)$ in direction $i$ is the probability that when we flip
the value of the $i$-th coordinate, the value of $f$ is flipped as well. For
instance, for $f(x_{1},...,x_{n})=x_{i}$, we have that $\mathrm{Inf}_{i}(f)=1$
and $\mathrm{Inf}_{j}(f)=0,j\neq i$. This notion of sensitivity naturally
extends to functions $f:\\{-1,1\\}^{n}\to\mathbb{R}$, as we will see in
Section 3. (in direction $i=1)$; it is in fact easy to construct more
counterexamples with other Boolean functions of high influence in some
direction. This perhaps suggests that the maximum influence of low-degree
functions over all directions $i\in[n]$ could be an important parameter for
general transfer. Focusing on low-degree Boolean functions, we actually show
that having a high influence in some direction is the _only bottleneck_ for
transferability in the Boolean domain.

######  Informal Theorem 2 (See Theorem 3.2).

Let $Q$ be the uniform distribution over $\\{-1,1\\}^{n}$ and $P$ be the
uniform distribution conditioned only on a subset $S\subseteq\\{-1,1\\}^{n}$.
For any degree-$d$ polynomials $f,f^{\star}:\\{-1,1\\}^{n}\to\mathbb{R}$ that
satisfy $\mathrm{Inf}_{i}(f-f^{\star})=Q(S)^{O(d)}$ for all $i\in[n]$, it
holds that

$\mathbb{E}_{Q}\left[(f(x)-f^{\star}(x))^{2}\right]\leq C_{d}\cdot
Q(S)^{-2d}\cdot\mathbb{E}_{P}\left[(f(x)-f^{\star}(x))^{2}\right]\,,$ (1.4)

where $C_{d}$ is a constant depending only on the degree $d$.

One application of our transferability Theorem in the Boolean domain is the
Generalization On the Unseen setting of [ABLR23]. In Section 5, we revisit the
problem of [ABLR23] of training an (overparameterized) diagonal linear network
$f_{\mathrm{NN}}$ (cf. Definition 5.1) in order to learn a simple linear
function $f^{\star}:\\{-1,1\\}^{n}\to\mathbb{R}$ via gradient methods. The
catch is that the observed features $x$ are generated by $P$ which is the
uniform distribution conditional on the set
$S=\\{x\in\\{-1,1\\}^{n}|x_{k}=1\\}$ for some $k\in[n]$. We refer to $S$ as
the _seen_ part of the Boolean hypercube. The goal is to understand how this
trained model _generalizes on the unseen_ , i.e., how small is the risk of
$f_{\mathrm{NN}}-f^{\star}$ under the uniform distribution over the whole
Boolean domain. This is an instantiation of our transfer learning framework. A
relatively simple corollary of Informal Theorem 2 and techniques borrowed from
[ABLR23], described below in Proposition 5.2, is that diagonal linear networks
trained with gradient flow exhibit the following interesting behavior: there
exists a critical time $t^{\star}=t^{\star}_{n}=\Omega(\log n)$ for which for
any $0<t<t^{\star}$, the maximum influence of $f_{\mathrm{NN}}-f^{\star}$ is
sufficiently small, our transfer inequality is applicable and therefore
_generalization on the unseen_ takes place. However, for $t>t^{\star}$, the
maximum influence becomes larger than the critical threshold of Informal
Theorem 2 and our transfer inequality is not applicable. The fact that our
inequality is not applicable for “infinite” $t$ is in agreement with [ABLR23,
Theorem 3.11] where it is proven that gradient flow with infinite time has
non-perfect generalization on the unseen. For further details, see Section 5.

Techniques. Our main tool in the proof of Informal Theorem 1 is the use of
_anti-concentration_ properties of polynomials under log-concave densities. To
the best of our knowledge, this is the first time that tools such as the
Carbery-Wright inequality [CW01] are used in the general abstract context of
transfer learning, with our inspiration being the special case of truncated
statistics [Coh91, DGTZ18]. For the proof of Informal Theorem 2, we rely on
the invariance principle of [MOO05] for product measures combined with the
Carbery-Wright inequality. We refer to Section 3 for more technical details.

###  1.2. Empirical Motivation: Polynomial Regression vs. Deep ReLU Networks

Before the formal statements of our results, we present a simple motivating
example, depicted in Figure 1, which illustrates our theoretical findings on
the transferability properties of polynomials and compares them with the
empirical transferability properties of neural networks. To test the
robustness of our results in this example we consider the case where the
dimension $n=2$ and

$f^{\star}(x,y)=\sin(2\pi x)\cdot\sin(2\pi y),$

which is not a low-degree polynomial (but sufficiently smooth). We also pick
the source distribution $P$ to be the uniform distribution over
$[0,1]\times[-1,1]$.

Given i.i.d. samples from $P$ labeled using $f^{\star}$, we train two models:

  * (a)

$f_{1}$ being a low-degree polynomial and,

  * (b)

$f_{2}$ being a deep neural network with ReLU activation functions,

with the common objective of minimizing the mean squared error over the source
$P$ $\mathbb{E}_{P}[(f_{i}-f)^{2}],i=1,2$.

We plot the resulting functions $f_{1}$ and $f_{2}$ over the square
$[-5,5]^{2}$ to test how well $f_{1}$ and $f_{2}$ are approximating
$f^{\star}$ outside of $[0,1]\times[-1,1]$, which helps us understand the
transferability of $f_{1}$ and $f_{2}$ for a distribution $Q$ that is
supported also _outside of_ $[0,1]\times[-1,1]$. As a note, clearly, in this
experimental setup, the ratio $\|dQ/dP\|_{\infty}=\infty$ since
$\mathrm{supp}(P)\subsetneq\mathrm{supp}(Q)$ and therefore no transfer claims
can be based on the naive arguments using this ratio.

(a) $f^{\star}$

(b) $f_{1}$

(c) $f_{2}$

Figure 1. Transferability of polynomial and neural network estimators with
$P=\mathcal{U}([0,1]\times[-1,1])$ (inside the dotted rectangle in (a)). (a)
contour plot of $f^{\star}(x,y)=\sin(2\pi x)\sin(2\pi y)$, (b) contour plot of
a degree-20 polynomial regressor $f_{1}$, (c) contour plot of a 6-layer
size-110 ReLU network $f_{2}$ (see also Section 6).

As one can directly see from the figures, polynomial regression surprisingly
achieves a highly non-trivial generalization on a significant part of the
unseen part of the domain, while the ReLU network completely fails!

This is in agreement with our Informal Theorem 1, and it illustrates that a
theorem similar to Informal Theorem 1 cannot hold in general for neural
networks. We refer to Section 6 for more details.

###  1.3. Related Work

Transfer learning works have mostly focused on classification and regression
tasks [MMR09, BDBC+10, MMR12, DLLP10, YHC13, YHC18, HK19, HKM23, KM18,
MKFAS20]. We note that the recent work of [HK19] introduced the notion of
_transfer exponents_ which, while being an interesting assumption on
transferability, does not indicate when transfer is actually possible (which
is the focus of our inequalities). For further references, see the survey
papers [WKW16, ZQD+20, RMH+20]. Moreover, transfer learning has been a topic
of interest for the statistics community [CW21, RCS21, LCL22]. Finally, recent
work by [KSV23] studies transfer learning through the lens of the testable
learning framework, while [KK21] studies the same problem through the lens of
PQ learning [GKKM20]. We continue with some other related topics.

Generalization on the Unseen (GOTU). GOTU [ABC+22, ABLR23] is a special case
of the OOD setting. In GOTU, the algorithm has access to one part of the
distribution domain and completely omits the complement. The question is how a
learner trained in this (seen) part can extrapolate/generalize on the unseen.
[ABLR23] study the overparameterized setting and want to understand the
implicit bias of SGD on learning a linear function by observing data only a
subset of the hypercube. Among all 0 training loss functions, they show that
the random feature model when trained with GD has bias towards the Min-Degree
Interpolator, i.e., the function $f$ with 0 training loss and whose Fourier
spectrum is concentrated in very low coefficients. Similar results are shown
for diagonal linear NNs, a setting that we also study in Section 5.

Truncated Statistics. Truncated statistics [Gal98, Coh91] is an area that is
closely related to the focus of this work. In this setting, there is a
truncation set $S$, which is a potentially unknown subset of the domain and
some target underlying distribution (e.g., Gaussian). The learner, whose goal
is to estimate the true distribution, observes a sample from the true model
only if this falls in $S$ and observes no samples outside of $S$. For more
details, we refer to Section 4.1. Designing efficient algorithms for truncated
and censored problems has recently gained attention from the computational
learning theory community [DGTZ18, DGTZ19, DRZ20, FKT20, FKKT21, DSYZ21,
FKT22, DNS23, NP20, GKK23, DLNS24, DKTZ21], with the Carbery-Wright inequality
being a major tool for (most of) these results.

Extrapolation in Neural Networks. Deep neural networks behave erratically when
presented with out-of-distribution (OOD) inputs [GPSW17, JSK+23, STR+20,
KSTL23, XZL+20]. Transfer learning in general does not occur in NN training
and hence our general inequalities are not applicable in this setting. The
main intuition is due to the existence of implicit bias during the training of
NNs via (S)GD methods (e.g., [LL19, JT19, CB20]). We refer to the recent work
by [KSTL23] for further justification on the inability of NNs to extrapolate.

Anti-Concentration and Invariance Principle. Our main tool is the well-known
Carbery-Wright inequality [CW01]. Similar inequalities are known in the
continuous case (see e.g., [Kan12, GM22]). There is a lot of work on designing
similar anti-concentration inequalities in discrete domains [LO39, Erd45,
NV13, RV13, MNV15, FKS21]. The invariance principle [MOO05] is a key tool for
anti-concentration in discrete domains. We shortly mention that tools such as
anti-concentration and CLT-type structural results have been extensively
applied in learning theory and analysis of Boolean functions (see [HKM09,
DHK+10, DGTZ18, DP15, KSZ22, DS13, KLS09] and the references therein).

###  1.4. Overview

We next present the formal results of our paper. In Section 2, we present the
necessary definitions that lead to the formal version of Informal Theorem 1.
Then, in Section 3, we present the formal statement of Informal Theorem 2.
Moreover, in Section 4.1, we present the application of Informal Theorem 1 in
truncated regression that we highlighted above and, in Section 4.2, we discuss
the application of Informal Theorem 1 on distribution shifts for in-context
learning linear function with linear attention. The rest of the paper is
organized as follows: in Section 5, we discuss the application of Informal
Theorem 2 in the Generalization on the Unseen (GOTU) problem and, in Section
6, we discuss some empirical observations. In Section 7 we present the proofs
for our results in the Euclidean domain and in Section 8 the associated proofs
for the Boolean domain. In Appendix A, we provide all the proofs omitted from
our applications in the Euclidean and Boolean domains. Appendix B contains
examples evaluating the transfer coefficient
$\|dP/d\mu\|_{\infty}\cdot\|dQ/d\mu\|_{\infty}^{d}$ for natural families of
distributions $(P,Q).$

##  2\. Transfer Learning for Low-Degree Polynomials in the Euclidean Domain

###  2.1. Notation & Definitions

We start with some definitions that we need in order to state our main Theorem
in this section.

######  Definition 2.1.

Let $P,Q$ be two probability distributions over $\mathbb{R}^{n}$. Let $P(x)$
(resp. $Q(x)$) be the probability density function of $P$ (resp. $Q)$
evaluated at $x\in\mathbb{R}^{n}$. We define

$\left\|\frac{dP}{dQ}\right\|_{\infty}\triangleq\sup_{x\in\mathbb{R}^{n}}\frac{P(x)}{Q(x)}\in[1,\infty]\,,$

and, for real $\alpha\geq 1$,

$D_{\alpha}(P\parallel Q)\triangleq\left(\mathbb{E}_{x\sim
Q}\left[\left(\frac{P(x)}{Q(x)}\right)^{\alpha}\right]\right)^{\frac{1}{\alpha}}\,.$

######  Definition 2.2.

A distribution is called log-concave if its density is of the form
$\propto\exp(-f)$, where $f$ is convex. Let $\mathcal{L}$ be the set of all
log-concave distributions over $\mathbb{R}^{n}$.

###  2.2. Main Inequality

We are now ready to state our main result for the Euclidean domain.

######  Theorem 2.3 (Transferability of Polynomials).

Let $\mathcal{L}$ be the space of log-concave probability distributions over
$\mathbb{R}^{n}$. Consider two probability distributions $P,Q$ over
$\mathbb{R}^{n}$ and let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a degree-$d$
polynomial. There exists an absolute constant $C$ such that for
$\alpha,\beta\in[1,\infty]$ with $1/\alpha+1/\beta=1$, it holds that

$\mathbb{E}_{Q}|f|\leq(Cd)^{d}2^{d\beta}\cdot\inf_{\mu\in\mathcal{L}}D_{\alpha}(Q\parallel\mu)D_{\alpha}(P\parallel\mu)^{\beta
d}\cdot\left(\mathbb{E}_{P}|f|^{\beta}\right)^{1/\beta}\,.$ (2.1)

In particular, if $\alpha=\infty$, we get that

$\mathbb{E}_{Q}|f|\leq(2Cd)^{d}\cdot\inf_{\mu\in\mathcal{L}}\left\|\frac{dQ}{d\mu}\right\|_{\infty}\left\|\frac{dP}{d\mu}\right\|_{\infty}^{d}\cdot\mathbb{E}_{P}|f|\,.$
(2.2)

If $Q$ is log-concave, then the above simplifies to the following.

######  Corollary 2.4.

Consider two probability distributions $P,Q$ over $\mathbb{R}^{n}$ where $Q$
is log-concave. Assume that $\mathrm{supp}(P)\subseteq\mathrm{supp}(Q)$. Let
$f:\mathbb{R}^{n}\to\mathbb{R}$ be a degree-$d$ polynomial. Then, for any
$\alpha,\beta\in[1,\infty]$ with $1/\alpha+1/\beta=1$, it holds that

$\mathbb{E}_{Q}|f|\leq(Cd)^{d}2^{d\beta}\cdot D_{\alpha}(P\parallel Q)^{\beta
d}\cdot\left(\mathbb{E}_{P}|f|^{\beta}\right)^{1/\beta}\,.$ (2.3)

In particular, if $\alpha=\infty$, we get that

$\mathbb{E}_{Q}|f|\leq(2Cd)^{d}\cdot\left\|\frac{dP}{dQ}\right\|_{\infty}^{d}\cdot\mathbb{E}_{P}|f|\,.$
(2.4)

Our Theorem 2.3, and in particular Corollary 2.4, perhaps unintuitively,
propose that considering the inverse ratio $\|dP/dQ\|_{\infty}$ allows for
transfering when working with _low-degree polynomials_. For the proof of
Theorem 2.3, we refer to Section 7.1 and for Corollary 2.4 to Section 7.2.

Theorem 2.3 allows us to transfer even in situations where both ratios are
infinity. Consider, for instance, the simple example of distribution shift
from source $P=\mathcal{U}([0,1])$ to target $Q=\mathcal{U}([2,3])$. Our
Theorem 2.3 proposes that we can use an intermediate log-concave measure $\mu$
that “covers” both $P$ and $Q$ (e.g., $\mu=\mathcal{U}([0,3])$ and obtain
transfer results at a cost that scales with
$\|dQ/d\mu\|_{\infty}\cdot\|dP/d\mu\|_{\infty}^{d}$, where $d$ is the degree
of the polynomial. This, perhaps counter-intuitive, phenomenon follows from
the property of polynomials $f$ in the Euclidean space, that the probability
density of the random variable $f(x)$ does not contain point masses when $x$
is drawn from a log-concave distribution.

In Appendix B, we compute such transfer ratios for various $(P,Q)$ pairs. An
interesting example is the setting where both $P$ and $Q$ are standard
Gaussians with different means in $\mathbb{R}^{n}$ (translation). One can show
that the ratio $\|dQ/dP\|_{\infty}$ scales exponentially with the distance of
the two means but, in the contrary, for
$\|dQ/d\mu\|_{\infty}\|dP/d\mu\|_{\infty}$ there exists a log-concave
distribution $\mu$ so that the product scales polynomially with the means’
distance.

##  3\. Transfer Learning for Low-Degree Polynomials in the Boolean Domain

In this section, we will provide a similar transfer inequality for discrete
domains. For simplicity, we will work in the Boolean domain $\\{-1,1\\}^{n}$.

###  3.1. Quick Boolean Analysis Background

We start with some necessary background. For a function
$f:\\{-1,1\\}^{n}\to\mathbb{R}$, we will write
$\sum_{S\subseteq[n]}c_{S}\chi_{S}$ for its Fourier decomposition, where
$\chi_{S}$ (resp. $c_{S})$ is the parity function (resp. the Fourier
coefficient) on $S\subseteq[n]$. We will say that $f$ is of degree-$d$ if
$c_{S}=0$ for any $|S|>d$. Recall also that for
$f:\\{-1,1\\}^{n}\to\\{-1,1\\}$, the influence of $f$ in direction $i\in[n]$
under $\mathcal{U}(\\{-1,1\\}^{n})$ is defined as

$\mathrm{Inf}_{i}(f)=\Pr_{x\sim\mathcal{U}(\\{-1,1\\}^{n})}[f(x)\neq f(x^{\sim
i})],$

where $x^{\sim i}$ is $x$ with $x_{i}$ flipped. This definition can be
extended when the image of $f$ is not Boolean and when the underlying measure
is product but potentially not uniform. For general
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ and product measure $P=\otimes_{i\in[n]}P_{i}$
over $\\{-1,1\\}^{n}$, we have $\mathrm{Inf}_{i}(f)=\mathbb{E}_{x\sim
P}[\mathrm{Var}_{x_{i}\sim P_{i}}(f(x))].$ In the special case where
$P=\mathcal{U}(\\{-1,1\\}^{n})$, we also have $\mathrm{Inf}_{i}(f)=\sum_{S\ni
i}c_{S}^{2}$. For further details on Boolean functions, see [O’D14].

One of our main tools in this section is the Invariance Principle of [MOO05].
This result is a generalization of the Berry–Esseen CLT (in fact, the
invariance principle is an analogue of the Berry–Esseen theorem for low-degree
polynomials) and, informally, states that the CDF of a low-degree Boolean
function with small influences can be approximated by that of the same
function when replacing the input variable by a Gaussian vector.

######  Proposition 3.1 (Invariance Principle [MOO05]).

Let $X_{1},...,X_{n}$ be independent random variables satisfying that
$\mathbb{E}[X_{i}]=0$, $\mathbb{E}[X_{i}^{2}]=1$ and
$\mathbb{E}[|X_{i}|^{3}]\leq\beta$. Let $f(x)=\sum_{S}c_{S}\chi_{S}$ be a
degree-$d$ multilinear function such that $\sum_{|S|>0}c_{S}^{2}=1$ and
$\max_{i}\sum_{S\ni i}c_{S}^{2}\leq\tau$. Then

$\sup_{t}\left|\Pr[f(X_{1},...,X_{n})\leq t]-\Pr[f(Y_{1},...,Y_{n})\leq
t]\right|\leq O(d\beta^{1/3}\tau^{1/8d})\,,$

where $Y_{i}$ are independent standard Gaussians.

We will refer to the additive approximation factor

$c\cdot d\beta^{1/3}\tau^{1/8d}$

as the invariance principle gap, where $c>0$ is an absolute constant.

###  3.2. Main Inequality

We proceed with our main transfer inequality for the Boolean domain. Recall
that in the Euclidean setting, the structure of the function class
(polynomials of low-degree) was crucial for the argument. In the Boolean
domain, _any_ function is essentially a polynomial in the Fourier basis.
Hence, we cannot expect that every function with low-degree Fourier spectrum
will transfer. To this end, we give a sufficient condition for transfer. This
condition essentially requires that the function has also small _influence_ in
any direction. In particular, the maximum influence of the function should be
roughly upper bounded by the inverse of the mass of the seen part of the
Boolean hypercube.

######  Theorem 3.2 (Transferability of Boolean functions).

Let $Q$ be a product probability distribution supported on $\\{-1,1\\}^{n}$
satisfying $\mathbb{E}_{Q}[x_{i}]=0,\mathbb{E}_{Q}[x_{i}^{2}]=1$ and
$\mathbb{E}_{Q}[|x_{i}|^{3}]\leq\beta$ for any $i\in[n]$. Let
$S\subseteq\\{-1,1\\}^{n}$ be the seen part of the Boolean hypercube and let
$P=Q_{S}$ be the distribution $Q$ conditioned on the seen subset $S$. Let
$f(x)=\sum_{S}c_{S}\chi_{S}$ be a degree-$d$ multilinear function with bounded
maximum influence, i.e., $\max_{i}\sum_{S\ni i}c_{S}^{2}\leq\tau$ and unit
variance, i.e., $\sum_{S:|S|>0}c_{S}^{2}=1.$

For some universal constant $c$, assume that $Q(S)$ is larger than the
invariance principle gap, i.e.,

$Q(S)\geq c\cdot d\beta^{1/3}\tau^{1/8d}\,.$ (3.1)

Then, it holds that

$\mathbb{E}_{Q}[f^{2}]\leq d^{O(d)}Q(S)^{-2d}\cdot\mathbb{E}_{P}[f^{2}]\,.$

For the proof, we refer to Section 8. In the domain $\\{-1,1\\}^{n}$, $\tau$
corresponds to the maximum influence of $f,$ i.e.,
$\tau=\max_{i}\mathrm{Inf}_{i}(f)$. Our condition states that $Q(S)$ should be
at least of order $d\tau^{1/d}$, where $d$ is the degree of $f$. For any
measure $Q$, this reveals an interesting connection between the complexity of
$f$ (degree and max-$Q$-influence) and the structure of the seen part (mass
under $Q$). For instance, for $Q$ being the uniform distribution over
$\\{-1,1\\}^{n}$, we have that dictator functions require that $Q(S)=1$
(anything must be seen). We refer the reader to Section 5 for an extensive
discussion on GOTU in Boolean domains and connections with the work of
[ABLR23].

##  4\. Applications in the Euclidean Domain

We next employ our Theorem 2.3 in two application domains. In Section 4.1 we
study truncated statistics and in Section 4.2 we study in-context transfer
learning.

###  4.1. Truncated Statistics

Our first example comes from the literature of truncated statistics [Gal98,
Coh91, DGTZ18]. We can view learning from truncated samples as a transfer
learning problem with source and target distributions defined as follows.

####  4.1.1. General Transfer Learning for Truncated Gaussians

One of the most canonical examples in truncated statistics is learning
Gaussians in $n$ dimensions from truncated examples. In more detail, let us
consider the target distribution $Q=\mathcal{N}(\mu,\Sigma)$ but assume only
sample access to the source probability distribution
$P=\mathcal{N}_{S}(\mu,\Sigma)$, where

$\mathcal{N}_{S}(\mu,\Sigma;x)=\frac{\mathcal{N}(\mu,\Sigma;x)1\\{x\in
S\\}}{\int_{S}\mathcal{N}(\mu,\Sigma;y)dy}\,,$

where $S\subseteq\mathbb{R}^{n}$ corresponds to the truncation set. This is a
standard example where the ratio $\frac{dQ(x)}{dP(x)}$ can be infinite, i.e.,
for $x\not\in S,$
$\frac{dQ(x)}{dP(x)}=\frac{\mathcal{N}(\mu,\Sigma;x)}{\mathcal{N}_{S}(\mu,\Sigma;x)}=\infty$.
On the other side, the opposite ratio $\frac{dP(x)}{dQ(x)}$, on which our main
inequality is based, can be easily proven to be always finite when $S$ is
“full-dimensional”, in the sense
$\mathcal{N}(\mu,\Sigma;S)=\int_{S}\mathcal{N}(\mu,\Sigma;y)dy>0$; more
precisely, it holds
$\|\frac{dP}{dQ}\|_{\infty}=O(1/\mathcal{N}(\mu,\Sigma;S))$.

Assume sample access to a truncated normal
$\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})$ and let
$\mathcal{N}(\mu^{\star},\Sigma^{\star};S)\geq\alpha$ for some $\alpha>0$.
Consider any estimator $\mu$ of $\mu^{\star}$ which is trained using
arbitrarily many samples from $\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})$.
It is natural to expect that in many settings, $\mu$ can achieve a small mean-
square error (MSE) performance (also known as prediction performance) against
a fresh sample from the truncated Gaussian measure
$\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})$. Using Theorem 2.3, we can
derive that this _automatically_ translates to a non-trivial upper bound on
the MSE against a fresh sample from the _non-truncated_ Gaussian measure
$\mathcal{N}(\mu^{\star},\Sigma^{\star})$.

To be more precise, the MSE of any estimate $\mu$ of $\mu^{\star}$ with
respect to the truncated density is equal to

$\mathbb{E}_{y\sim\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})}[\|y-\mu\|^{2}]\,.$

Since $f(y)=\|y-\mu\|^{2}$ is a non-negative degree-2 polynomial in the
variables of $y$ and the (non-truncated) normal distribution is a log-concave
measure, we can apply our Theorem 2.3 to show that

$\displaystyle\mathbb{E}_{y\sim\mathcal{N}(\mu^{\star},\Sigma^{\star})}[\|y-\mu\|^{2}]\leq
O(1/\alpha^{2})\cdot\mathbb{E}_{y\sim\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})}[\|y-\mu\|^{2}]\,.$
(4.1)

Additionally, using a vanilla change of measure we have that

$\displaystyle\mathbb{E}_{y\sim\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})}[\|y-\mu\|^{2}]\leq(1/\alpha)\cdot\mathbb{E}_{y\sim\mathcal{N}(\mu^{\star},\Sigma^{\star})}[\|y-\mu\|^{2}]\,.$
(4.2)

The above expression relates multiplicatively the MSE of $\mu$ with respect to
the target $Q=\mathcal{N}(\mu^{\star},\Sigma^{\star})$ to that of the source
$P=\mathcal{N}_{S}(\mu^{\star},\Sigma^{\star})$. The term $1/\alpha^{2}$
appears since we transfer a degree-2 polynomial and the density ratio, as
discussed above, is $O(1/\alpha)$. We highlight that (4.1) and (4.2) hold _for
all truncations_ $S$ with mass at least $\alpha,$ and _for all measurable
estimators_ $\mu$.

######  Remark 4.1.

We now discuss how our equations (4.1), (4.2) compare with the recent relevant
works on learning a Gaussian distribution in truncated statistics [DGTZ18,
KTZ19]. To simplify this comparison we are going to assume that
$\Sigma^{\star}=I$. In [DGTZ18, KTZ19] the authors construct estimators
$\hat{\mu}$ from “truncated” samples drawn from
$\mathcal{N}_{S}(\mu^{\star},I)$ that have the property that the distance
$\|\mu^{\star}-\hat{\mu}\|$ is small, and in particular goes to zero as the
number of samples goes to infinity, i.e., $\hat{\mu}$ is consistent. This in
turn implies that the non-truncated error satisfies

$\mathbb{E}_{y\sim\mathcal{N}(\mu^{\star},I)}[\|y-\hat{\mu}\|^{2}]\leq\mathrm{OPT}+o(1),$

where $\mathrm{OPT}$ is the minimum achievable MSE with respect to
$\mathcal{N}(\mu^{\star},I)$. We note that the estimators from [DGTZ18, KTZ19]
achieving this error guarantee are quite sophisticated and carefully exploit
the knowledge of the truncation $S$.

Our equations (4.1) and (4.2) show that one can control the “non-truncated”
MSE with respect to $\mathcal{N}(\mu^{\star},I)$ in an immediate way: as long
as one has any bound on the “truncated” MSE with respect to
$\mathcal{N}_{S}(\mu^{\star},I)$ (so any control on the “standard” testing
error for the samples received), the “non-truncated” MSE is then provably
within a multiplicative factor of $O(1/\alpha^{2})$ from the “truncated” MSE.
Notably these all hold for any estimator $\mu$.

For example, as a corollary, if we choose $\tilde{\mu}$ to minimize the MSE
with respect to the truncated data this already implies a non-trivial upper
bound on the non-truncated MSE; in particular we have that
$\mathbb{E}_{y\sim\mathcal{N}(\mu^{\star},I)}[\|y-\tilde{\mu}\|^{2}]\leq
O(1/\alpha^{2})\cdot\mathbb{E}_{y\sim\mathcal{N}_{S}(\mu^{\star},I)}[\|y-\tilde{\mu}\|^{2}]\leq
O(1/\alpha^{3})\cdot\mathrm{OPT}$ (here we used (4.1) in the first inequality
and (4.2) together with the optimality of $\widetilde{\mu}$ in the second).
This in turn can be translated to a guarantee of the form
$\|\mu^{\star}-\tilde{\mu}\|\leq\mathrm{poly}(1/\alpha)$. Although this
estimator is not consistent, it achieves a non-trivial error _without the need
to know $S$ at all_. Similar estimators $\tilde{\mu}$ with
$\mathrm{poly}(1/\alpha)$ error (without knowing $S)$ are already found useful
as a warm start to build more sophisticated estimators, as in [DGTZ18, KTZ19],
and we can upper bound the error of such $\tilde{\mu}$ by a simple application
of our transfer inequality.

####  4.1.2. General Transfer Learning for Truncated Regression

Our next goal is to employ the idea that we used to derive (4.1) to bound the
error of regression problems from truncated samples.

######  Definition 4.2.

Consider the setting where we observe arbitrary covariates
$x^{(1)},...,x^{(N)}\in\mathbb{R}^{n}$ and labels
$y_{i}=f^{\star}(x^{(i)})+\varepsilon_{i}$, where
$\varepsilon_{i}\sim\mathcal{N}(0,1)$ for some model
$f^{\star}:\mathbb{R}^{n}\to\mathbb{R}$ belonging to some class of functions
$\mathcal{F}$. Let $S\subseteq\mathbb{R}$ be a measurable subset of the real
line. In the truncated setting, we observe the pair $(x^{(i)},y^{(i)})$ only
if $y^{(i)}\in S$, by sampling
$y^{(i)}\sim\mathcal{N}_{S}(f^{\star}(x^{(i)}),1).$

######  Remark 4.3.

We note that the special case of Definition 4.2 where $f^{\star}$ is a linear
function $f_{w}^{\star}(x)=w^{\top}x$ with parameters $w\in\mathbb{R}^{n}$ has
been recently studied in [DGTZ19].

Let us assume that we have sample access to a truncated regression problem, as
in Definition 4.2, with true model $f^{\star}$ and truncation set
$S\subseteq\mathbb{R}$. We will show that transfer learning between the
truncated samples and the non-truncated samples is statistically possible
under very mild assumptions. To do so, we will use our main transfer
inequality to relate the truncated MSE of some model $f$, aiming to estimate
$f^{\star}$, to the non-truncated MSE of $f$.

Let us now rephrase the problem in the transfer learning terminology. Consider
target distribution
$Q=\frac{1}{N}\sum_{i\in[N]}\mathcal{N}(f^{\star}(x^{(i)}),1)$ and source
distribution
$P=\frac{1}{N}\sum_{i\in[N]}\mathcal{N}_{S}(f^{\star}(x^{(i)}),1)$. The
“truncated” MSE of a model $f$ is defined as

$\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{y\sim\mathcal{N}_{S}(f^{\star}(x^{(i)}),1)}[(y-f(x^{(i)}))^{2}]\,$

and the “non-truncated” MSE of $f$ is similarly

$\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{y\sim\mathcal{N}(f^{\star}(x^{(i)}),1)}[(y-f(x^{(i)}))^{2}]\,.$

Using our Theorem 2.3, we can obtain the following result.

######  Corollary 4.4 (Transfer in Truncated Regression).

Consider the truncated regression setting
$y_{i}=f^{\star}(x^{(i)})+\varepsilon_{i},i\in[N]$ of Definition 4.2 with true
model $f^{\star}$ and truncation set $S\subseteq\mathbb{R}$. Let us set
$\mu_{i}\triangleq f^{\star}(x^{(i)})$. Assume that the truncation set $S$ has
mass at least $\alpha>0$ with respect to all $\mu_{i},i=1,\ldots,N$ i.e.,
$\min_{i\in[N]}\mathcal{N}(\mu_{i},1;S)\geq\alpha$.

Then, for any model $f,$ it holds that

$\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{y\sim\mathcal{N}(f^{\star}(x^{(i)}),1)}[(y-f(x^{(i)}))^{2}]\leq\left(\frac{C}{\alpha^{2}}\right)\cdot\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_{y\sim\mathcal{N}_{S}(f^{\star}(x^{(i)}),1)}[(y-f(x^{(i)}))^{2}]\,,$

for some absolute constant $C>0.$

The above inequality allows us to relate multiplicatively the “truncated” MS’
of an arbitrary prediction model $f$ of the true model $f^{\star}$ to the MSE
of $f$ over the whole non-truncated measure.

For the proof, we refer to Section A.1. We mention that [DGTZ19] established a
similar inequality to show that transfer learning is possible under the
assumption that $f^{\star}$ is linear555Also, the assumption that the set $S$
has mass with respect to any Gaussian $\mathcal{N}(\mu_{i},1)$ can be weakened
under some structural properties for the family $\mathcal{F}$. For instance,
for linear functions it suffices to consider a lower bound on the average of
the masses (see Assumption 1 in [DGTZ19]).. The above result applies much more
generally and, in particular, note that the exact details of the function
$f^{\star}$ do not play a role: if $f^{\star}$ is linear or a degree-100
polynomial, the “transfer coefficient” is still simply $C/\alpha^{2}.$

######  Remark 4.5.

We should mention that the above result, does not discuss the (non-trivial)
details on how to efficiently find an estimator that has in fact small MSE
under the truncated measure. While this is beyond the scope of this work, we
would like to mention that for many natural families of parameterized
regression functions $\mathcal{F}=\\{f_{w}:w\in\mathcal{W}\\}$, the truncated
log-likelihood is concave with respect to $w$ and, under some mild
assumptions, one can design a first-order method to optimize it efficiently
and obtain a small truncated MSE. For instance, such an analysis is provided
by [DGTZ19] for the case of linear functions $f_{w}(x)=w^{\top}x$.

###  4.2. In-Context Transfer Learning

Transformers [VSP+17] and in-context learning (ICL) have been extensively
explored and studied recently [VONR+23, ASA+22, GTLV22, LIPO23, BCW+23,
ACDS23, SIS21], mainly because of their applications in text generation via
large language models (LLMs). In-context learning [GTLV22] corresponds to the
ability of a model to condition on a prompt sequence consisting of in-context
examples (input-output pairs corresponding to some task) along with a new
query input, and generate the corresponding output.

####  4.2.1. Background on ICL

We give the formal setting below.

######  Definition 4.6 (Class and Distributions).

We consider a feature space $\mathcal{X}$ and a label space $\mathcal{Y}$. We
let $H\subseteq\mathcal{Y}^{\mathcal{X}}$ be a concept class of functions
$\mathcal{X}\to\mathcal{Y}$. We let $P_{X}$ be a distribution over the feature
space $\mathcal{X}$ and $P_{H}$ be a distribution over functions in $H$.

For our application, we will consider $H$ to be the set of linear functions
$\\{h(x)=w^{\top}x:w\in\mathbb{R}^{n}\\}$. As an example, $P_{X}$ could be the
standard normal distribution and $P_{H}$ could generate a random linear
function $x\mapsto w^{\top}x$ by drawing $w$ from some probability measure
over $\mathbb{R}^{n}$.

######  Definition 4.7 (Training/Testing In-Context Samples).

A realizable training sample or _training prompt_ of length $M\in\mathbb{N}$
from $(P_{X},P_{H})$ corresponds to a random sequence
$(x_{1},y_{1},...,x_{M},y_{M})\in(\mathcal{X}\times\mathcal{Y})^{M}$ generated
as follows.

  1. (1)

We first draw a concept $h\sim P_{H}$.

  2. (2)

Independently of $h$, we draw $x_{1},...x_{M}$ i.i.d. from $P_{X}$.

  3. (3)

We set $y_{i}=h(x_{i})$ for any $i\in[M]$ and return
$(x_{1},y_{1},...,x_{M},y_{M})$.

A realizable testing sample or _testing prompt_ of length $N\in\mathbb{N}$
from $(P_{X},P_{H})$ corresponds to a random sequence
$(x_{1},y_{1},...,x_{N},y_{N},x_{\mathrm{query}})\in(\mathcal{X}\times\mathcal{Y})^{N}\times\mathcal{X}$
generated as follows.

  1. (1)

We first draw $h\sim P_{H}$.

  2. (2)

Independently of $h$, we draw $x_{1},...x_{N},x_{\mathrm{query}}$ i.i.d. from
$P_{X}$.

  3. (3)

We set $y_{i}=h(x_{i})$ for any $i\in[N]$ and return
$(x_{1},y_{1},...,x_{N},y_{N},x_{\mathrm{query}})$.

Note that in each training prompt the labeling hypothesis will likely be
different since it is drawn from $P_{H}$; this is an important difference from
the standard PAC setting.

In what follows, we will need the following notation:

  1. (1)

Fix $H\subseteq\mathcal{Y}^{\mathcal{X}}$ , $P_{X}$ and $P_{H}$, as in
Definition 4.6.

  2. (2)

Let $\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}$ be a loss function, e.g.,
the squared loss.

  3. (3)

Let
$\mathcal{S}=\bigcup_{m\in\mathbb{N}}\\{(x_{1},y_{1},...,x_{m},y_{m}),x_{i}\in\mathcal{X},y_{i}\in\mathcal{Y}\\}$
be the set of finite-length sequences of $(x,y)$ pairs.

Having trained a model with realizable training prompts, each of length $M$,
we test its performance on new prompts of length $N$, potentially different
than the training length $M$. The learning guarantee of such a model is
formally defined as follows.

######  Definition 4.8 (In-Context Learning [ZFB23]).

For $M,N>0,$ we say that a model
$f:\mathcal{S}\times\mathcal{X}\to\mathcal{Y}$, trained on realizable prompts
of the form $(x_{1},y_{1},...,x_{M},y_{M})$, _in-context learns a concept
class $H$ under loss $\ell$ in the realizable setting with respect to
$(P_{X},P_{H})$ up to error $\eta\geq 0$_ if there exists a function
$N_{P_{X},P_{H}}:(0,1)\to\mathbb{N}$ such that for every
$\varepsilon\in(0,1)$, if the length of the testing prompt $N\geq
N_{P_{X},P_{H}}(\varepsilon)$, then

$\mathbb{E}_{\mathcal{T}}[\ell(f(\mathcal{T}),h(x_{\mathrm{query}}))]\leq\eta+\varepsilon\,,$

where $\mathcal{T}=(x_{1},h(x_{1}),...,x_{N},h(x_{N}),x_{\mathrm{query}})$
with $x_{1},...,x_{N},x_{\mathrm{query}}\sim P_{X}$ and $h\sim P_{H}$
independently.

We remark that the definition of the model $f$ as a mapping from
$\mathcal{S}\times\mathcal{X}\to\mathcal{Y}$ allows us to have the flexibility
to change the length of the given prompt. Essentially, the length of the
testing prompt $N$ controls the error parameter $\varepsilon$, while the
length of the training prompt $M$ controls the error parameter $\eta$ (which
can be non-zero even in the realizable setting). Note also that by taking
$P_{H}$ to be point mass and $N=0$, we recover the setting of realizable PAC
regression under loss $\ell$ if the model learns under any $P_{X}$ and any
point mass distribution $P_{H}$ [AHK+24].

In the next section, we specialize the above general abstract setup to the
concrete problem of in-context learning linear functions with single-layer
linear self-attention functions.

####  4.2.2. Problem Setup and Motivation: the Linear Case

Let us consider the problem of in-context learning the concept class
$H=\\{h(x)=w^{\top}x:w\in\mathbb{R}^{n}\\}$ of linear functions in $n$
dimensions [GTLV22, ZFB23] in the realizable setting (i.e.,
$y_{i}=w^{\top}x_{i})$ with loss function
$\ell(y,y^{\prime})=(y-y^{\prime})^{2}$ under distributions $(P_{X},P_{H})$;
$P_{H}$ generates a random linear function $x\mapsto w^{\top}x$ by drawing
$w\sim P_{H}$.

It remains to specify the model that we will train in order to in-context
learn linear functions. The standard model of empirical studies is the so-
called single-head attention layer defined as
$f_{\mathrm{SA}}(X)=E+W^{PV}E\cdot\mathrm{softmax}\left(\frac{E^{\top}W^{KQ}E}{\rho}\right)$,
where $E$ is the input prompt, $W^{PV},W^{KQ}$ are trainable matrices and
$\rho>0$ is a normalization factor. In our theoretical application, we follow
the route of recent works by [ZFB23, VONR+23, LIPO23, ACDS23, ACS+23] and
study single-head _linear_ attention layers $f_{\mathrm{LSA}}$, a model which
essentially removes the softmax operator from $f_{\mathrm{SA}}$. Following
[ZFB23], we can formally define the single-layer linear self-attention (LSA)
model with trainable parameters $\theta=(W^{KQ},W^{PV})$ and input data matrix

$E=\begin{bmatrix}x_{1}&...&x_{N}&x_{\mathrm{query}}\\\
y_{1}&...&y_{N}&0\end{bmatrix}\in\mathbb{R}^{(n+1)\times(N+1)}$

as

$f_{\mathrm{LSA}}(E;\theta)=E+W^{PV}E\cdot\frac{E^{\top}W^{KQ}E}{\rho}\,,$
(4.3)

where $\rho>0$ is some normalization factor (we take it equal to $N$). We note
that $f_{\mathrm{LSA}}$ is a matrix and the model’s prediction to some prompt
of length $N$ is

$\widehat{y}_{\mathrm{query}}(E;\theta)=f_{\mathrm{LSA}}(E;\theta)[n+1,N+1]\,,$
(4.4)

i.e., the bottom-right entry of the matrix, where $n$ is the dimension of the
ambient space.

Considering some realizable testing prompt $E$, which essentially corresponds
to the sequence obtained by the independent random variables $w\sim P_{H}$,
$x_{i},x_{\mathrm{query}}\sim P_{X}$ for $i\in[N]$, the population loss of the
LSA model with parameters $\theta$ is

$L_{P}(\theta)=\mathbb{E}_{P_{X}^{\otimes
N+1},P_{H}}[(\widehat{y}_{\mathrm{query}}(E;\theta)-w^{\top}x_{\mathrm{query}})^{2}]\,.$
(4.5)

In the above and hereafter, we will use the notation $P_{X}^{\otimes
N+1},P_{H}$ to denote the distribution of a single test prompt, i.e., we will
abbreviate the notation
$\mathbb{E}_{x_{1},...,x_{N},x_{\mathrm{query}},w}[\cdot]$ with
$\mathbb{E}_{P_{X}^{\otimes N+1},P_{H}}[\cdot].$

####  4.2.3. Application of Transfer Learning to ICL Linear Functions.

We now turn our attention to our problem of interest. We consider the question
of _in-context transfer learning linear functions_ using the model
$f_{\mathrm{LSA}}$. In this setting, the model is given sample access to
prompts generated by the source pair $(P_{X},P_{H})$ but we want to test its
generalization abilities on potentially different target distributions
$(Q_{X},Q_{H}).$ From a theoretical front, this question was also studied by
[ZFB23] where they considered the robustness of the trained linear attention
model under distribution shifts when $P_{X}=\mathcal{N}(0,\Sigma)$ for some
covariance matrix $\Sigma$. We remark that under this choice of source
distribution the prediction of the model $f_{\mathrm{LSA}}$ has a nice closed
form at the global optimum666 [ZFB23] train an LSA model
$f_{\mathrm{LSA}}(\cdot;\theta)$ using gradient flow with training prompts of
length $M$ and show that gradient flow converges to some parameters
$\theta^{\star}$ (see Theorem 4.1 of [ZFB23]). They then check the
generalization properties of the model
$f_{\mathrm{LSA}}(\cdot;\theta^{\star})$. If $P_{X}=\mathcal{N}(0,\Sigma)$,
then the prediction of the LSA model at $\theta^{\star}$, trained on prompts
of length $M$ when given a testing prompt of length $N$ is
$\widehat{y}_{\mathrm{query}}\approx
x^{\top}_{\mathrm{query}}\Sigma^{-1}\left(\frac{1}{N}\sum_{i=1}^{N}x_{i}y_{i}\right)$
for input $(x_{1},y_{1},...,x_{N},y_{N},x_{\mathrm{query}}$) when the training
length $M$ is large. This closed form expression allows the authors to analyze
task,covariate and query distribution shifts on the way they generate the
testing prompt. , which allowed the authors to study task, covariate and query
distribution shifts $(Q_{X},Q_{H})$.

In our application of Theorem 2.3, we allow for general source and target
distributions. As such, our application gives the first general rigorous
transfer learning result for in-context learning in this setting allowing us
to study distribution shifts in a more systematic manner. In what follows we
fix the length of the input prompt to be $N$.

In Corollary 4.9, we give a general transfer result applied on the setting of
in-context learning linear functions with single-layer linear self-attention
layer models in a slightly more general setting than the one we described
before: we consider three _arbitrary_ source distributions: $P_{X}$ over input
features, $P_{X}^{\mathrm{query}}$ over the query feature point and $P_{H}$
over normal vectors. In a similar manner, we define
$Q_{X},Q_{X}^{\mathrm{query}},Q_{H}$ for the _arbitrary_ associated shifts.

######  Corollary 4.9 (In-Context Transfer Learning Linear Functions with LSA
Models).

Consider the setting of in-context learning linear functions with a single
linear self-attention layer $f_{\mathrm{LSA}}$ of (4.3) with prompts of length
$N$ in $n$ dimensions.

Consider product distributions $Q=(Q_{X}^{\otimes
N},Q_{X}^{\mathrm{query}},Q_{H})$ (target) and $P=(P_{X}^{\otimes
N},P_{X}^{\mathrm{query}},P_{H})$ (source) with associated population loss
functions $L_{Q}$ and $L_{P}$ respectively, defined as in (4.5) with (fixed)
parameters $\theta$. Let $\mathcal{L}_{m}$ be the space of $m$-dimensional
log-concave distributions. Then the following hold true.

  1. (1)

It holds that

$L_{Q}(\theta)\leq
C\cdot\inf_{\mu\in\mathcal{L}_{n(N+2)}}\|dQ/\mu\|_{\infty}\|dP/\mu\|^{c}_{\infty}\cdot
L_{P}(\theta)\,,$

for some positive absolute constants $C,c$ with $c\in\mathbb{N}$.

  2. (2)

Assume that $P_{X},P_{X}^{\mathrm{query}}$ are log-concave. The cost of task
shift $P_{H}\to Q_{H}$ (i.e., $P_{X}=Q_{X}$ and
$P_{X}^{\mathrm{query}}=Q_{X}^{\mathrm{query}}$) incurred by the model is

$L_{Q}(\theta)\leq
C\cdot\inf_{\mu\in\mathcal{L}_{n}}\|dQ_{H}/d\mu\|_{\infty}\|dP_{H}/d\mu\|^{c}_{\infty}\cdot
L_{P}(\theta)\,,$

for some positive absolute constants $C,c$ with $c\in\mathbb{N}$.

  3. (3)

Assume that $P_{X},P_{H}$ are log-concave. The cost of query shift
$P_{X}^{\mathrm{query}}\to Q_{X}^{\mathrm{query}}$ (i.e., $P_{X}=Q_{X}$ and
$P_{H}=Q_{H}$) incurred by the model is

$L_{Q}(\theta)\leq
C\cdot\inf_{\mu\in\mathcal{L}_{n}}\|dQ_{X}^{\mathrm{query}}/d\mu\|_{\infty}\|dP_{X}^{\mathrm{query}}/d\mu\|^{c}_{\infty}\cdot
L_{P}(\theta)\,,$

for some positive absolute constants $C,c$ with $c\in\mathbb{N}$.

For the proof, we refer to Section A.2. We believe that our result provides a
more abstract way to study such distribution shifts and adds further insight
on the impact of out-of-distribution generalization studied in [ZFB23].

####  4.2.4. Technical Details

At a technical level, we leverage one of the main observations in [ZFB23] to
simplify the expression of (4.5). In particular, it can be shown that the
prediction $\widehat{y}_{\mathrm{query}}(E;\theta)$ on input $E$ can be
expressed as a quadratic function $u^{\top}Hu$ for some matrix $H$ depending
only on the input matrix $E$ and for some vector $u$ depending only on the
parameters $\theta$.

######  Lemma 4.10 (Lemma 5.1 in [ZFB23]).

Consider the distribution $P=(P_{X}^{\otimes N+1},P_{H})$ over the input
prompt, where $x_{1},...,x_{N},x_{\mathrm{query}}\sim P_{X}$ and $w\sim P_{H}$
are independent random variables and $y_{i}=w^{\top}x_{i}$. Consider the LSA
model with parameters $\theta$ and input matrix
$E=\begin{bmatrix}x_{1}&...&x_{N}&x_{\mathrm{query}}\\\
y_{1}&...&y_{N}&0\end{bmatrix}$. Then the population loss under $P$ (see
(4.5)) can be written as

$L_{P}(u)=\mathbb{E}_{P_{X}^{\otimes
N+1},P_{H}}[(u^{\top}Hu-w^{\top}x_{\mathrm{query}})^{2}]\,.$ (4.6)

In the above, we have that

$H=\frac{X}{2}\otimes\frac{EE^{\top}}{N}\in\mathbb{R}^{(n+1)^{2}\times(n+1)^{2}},~{}~{}~{}~{}~{}~{}X=\begin{bmatrix}0_{n\times
n}&x_{\mathrm{query}}\\\
x_{\mathrm{query}}^{\top}&0\end{bmatrix}\in\mathbb{R}^{(n+1)\times(n+1)}\,,$

where $\otimes$ corresponds to the Kronecker product operator and
$u\in\mathbb{R}^{(n+1)^{2}}$ depends only on the parameters $\theta$.

Our goal is to show a general transfer inequality for in context learning
linear functions with a single linear attention layer, i.e., we would like to
relate $L_{P}(u)=\mathbb{E}_{P_{X}^{\otimes
N+1},P_{H}}[(u^{\top}Hu-w^{\top}x_{\mathrm{query}})^{2}]$ with
$L_{Q}(u)=\mathbb{E}_{Q_{X}^{\otimes
N+1},Q_{H}}[(u^{\top}Hu-w^{\top}x_{\mathrm{query}})^{2}]$ for some other
distributions $Q_{X}$ and $Q_{H}.$

To this end, let us fix the parameters $u$ and consider the polynomial on
$H,x,w$:

$f(H,x,w)=(u^{\top}Hu-w^{\top}x)^{2}\,.$ (4.7)

It follows from Lemma 4.10 and specifically the definitions of $H$ and $u$
that $f:\mathbb{R}^{n(N+2)}\to\mathbb{R}_{\geq 0}$ is actually a non-negative
polynomial of degree-10777By inspecting the structure of $H$ in Lemma 4.10, we
can see that each entry of $EE^{\top}$ is a degree-4 polynomial in the
variables $x_{1},...,x_{N},x_{\mathrm{query}},w$, since $y_{i}=w^{\top}x_{i}$
is degree-2. Then, applying the Kronecker product $X\otimes EE^{\top}$
increases the degree of each entry by at most 1 due to the structure of $X$.
Hence, since we consider the square loss, the total degree of
$(u^{\top}Hu-w^{\top}x_{\mathrm{query}})^{2}$ is 10. on the variables
$x_{1}=(x_{11},...,x_{1n})^{\top},...,x_{N}=(x_{N1},...,x_{Nn})^{\top},x_{\mathrm{query}}=(x_{\mathrm{query},1},...,x_{\mathrm{query},n})^{\top}$
and $w=(w_{1},...,w_{n})^{\top}$. This allows us to relate
$\mathbb{E}_{P_{X}^{\otimes N+1},P_{H}}[f]$ to $\mathbb{E}_{Q_{X}^{\otimes
N+1},Q_{H}}[f]$ in a straightforward manner given Theorem 2.3. For the
details, we refer to Section A.2.

####  4.2.5. Further Comparison With [ZFB23]

[ZFB23] consider the above problem of in-context learning linear functions
with the LSA model when $P_{X}=\mathcal{N}(0,\Sigma)$ and
$P_{H}=\mathcal{N}(0,I_{n})$ and prove the following (among others).

  1. (1)

In terms of ICL training, using prompts of length $M$, they manage to prove
that gradient flow on the population loss objective for LSA models and linear
targets, i.e., the function

$\theta\mapsto\mathbb{E}_{P_{X}^{\otimes
M+1},P_{H}}[(\widehat{y}_{\mathrm{query}}(E;\theta)-w^{\top}x_{\mathrm{query}})^{2}]\,,$

converges to a global optimum $\theta^{\star}=(W^{KQ}_{\star},W^{PV}_{\star})$
under some appropriate initialization conditions. Note that the population
objective corresponds to the case where the number of training prompts goes to
infinity.

  2. (2)

In terms of ICL prediction error, [ZFB23] study the loss of the LSA model in
ICL linear functions in $n$ dimensions with prompts of length $N$ (see (4.5)).
They show that the model with parameters $\theta^{\star}$, obtained by Item
(1) under $P_{X}=\mathcal{N}(0,\Sigma)$, satisfies

$L_{P}(\theta^{\star})\leq\eta+\varepsilon\,,$ (4.8)

where $\eta$ decreases with the training length $M$ as

$\eta=\frac{1+2n+n^{2}\kappa}{M^{2}}\cdot\mathrm{Tr}(\Sigma)\,,$

and $\varepsilon$ decreases with the test length $N$ as

$\varepsilon=\frac{n+1}{N}\cdot\mathrm{Tr}(\Sigma)\,,$

where $\mathrm{Tr}$ is the trace operator and $\kappa$ is the condition number
of $\Sigma$. Interestingly, as proved by [ZFB23], the linear transformer
$f_{\mathrm{LSA}}(\cdot;\theta^{\star})$ learns the class of linear functions
up to error $\eta$, which scales as $O(1/M^{2})$ (recall Definition 4.8), even
if the test length $N\to\infty$. Hence, training on finite-length prompts
leads to a prediction error which is, in general, bounded away from zero.

To summarize, [ZFB23] establish that under suitable distributional (i.e.,
Gaussianity) and initialization conditions, gradient-flow, trained on prompts
of length $M$, converges to some parameters $\theta^{\star}$. More to that
they show that the model $f_{\mathrm{LSA}}(\cdot;\theta^{\star})$ achieves
small generalization loss when tested on prompts of length $N$, as we
described in (4.8). Hence, our transfer results in Corollary 4.9 can then be
directly used to extend (4.8) to general distributions $Q_{X}$ and $Q_{H}$
under the cost of the “transfer coefficient”.

##  5\. Applications in the Boolean Domain: Generalization on the Unseen

In this section, we discuss an application of Theorem 3.2 in the
Generalization on the Unseen (GOTU) setting, introduced by [ABLR23].

Let us first formally introduce the GOTU setup of [ABLR23]. Let us consider
$\Omega=\\{-1,1\\}^{n}$ and $S\subseteq\Omega$ be the seen part. In this
setting, there is some distribution $\nu$ over the Boolean hypercube and we
only observe samples from the conditional distribution on $S$, i.e., we train
our models from samples drawn from $\nu_{S}$ using some gradient-based method
and aim to see how well the model generalizes on the unseen part, i.e., we
test the model on $\nu.$

For simplicity, following [ABLR23], we can think of the underlying measure as
the uniform distribution $\nu=\mathcal{U}\triangleq\mathcal{U}(\Omega)$ over
the Boolean hypercube.

###  5.1. A General Transfer Inequality from Seen to Unseen

Let $P=\mathcal{U}_{S}$ be uniformly supported on the seen part $S$. It is
natural to translate GOTU in terms of transfer learning: one simply wants to
learn using samples from the source $P$ and then achieve good performance on
the target $Q=\mathcal{U}$.

Our Theorem 3.2 directly implies a general transfer inequality between $P$ and
$Q$ as follows. Note that $\|dQ/dP\|_{\infty}$ is infinite but
$\|dP/dQ\|_{\infty}=\frac{1}{\mathcal{U}(S)}$. Hence, we can use Theorem 3.2
(since the invariance principle is applicable on $Q$) and obtain for all $f$
satisfying the conditions of Theorem 3.2 (i.e., $\leq d$-degree and “low”
total influence) that

$\displaystyle\mathbb{E}_{\mathcal{U}}[f^{2}]\leq\frac{1}{\mathcal{U}(S)^{O(d)}}\mathbb{E}_{\mathcal{U}_{S}}[f^{2}]$
(5.1)

One may wonder how (5.1) relates with the GOTU literature. We investigate this
in the following section.

###  5.2. Canonical Holdout with Diagonal Linear Networks

Let us focus on a specific GOTU setup for training diagonal linear networks,
as in [ABLR23]. To introduce the setup, let us consider the model of diagonal
linear neural networks [PPVF21, EPGF23].

######  Definition 5.1.

We define a _diagonal linear network with bias_ with parameter vector

$\theta=(b,w_{1}^{(1)},...,w_{n}^{(1)},...,w_{1}^{(L)},...,w_{n}^{(L)})\,,$

as

$f_{\mathrm{NN}}(x;\theta)=b+\sum_{i\in[n]}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}\right)x_{i}\,,$

where $n$ corresponds to the input dimension and $L$ is the network’s depth.

The target function that we want to learn in this section is a linear function
which we denote as $f^{\star}:\\{-1,1\\}^{n}\to\mathbb{R}$.

We will work in the “canonical holdout” setting where we freeze one coordinate
of the Boolean hypercube during training, i.e., the seen set is
$S=\\{x\in\\{-1,1\\}^{n}|x_{k}=1\\}$ for some $k\in[n]$. Given samples from
the seen set, [ABLR23] train a diagonal linear network using gradient flow to
fit the unknown linear target function $f^{\star}$. Since we train the
diagonal linear network of Definition 5.1 with gradient flow, we define the
trainable parameters for $t>0$ as

$\theta_{t}\triangleq(b(t),w_{1}^{(1)}(t),...,w_{n}^{(1)}(t),...,w_{1}^{(L)}(t),...,w_{n}^{(L)}(t))\,.$
(5.2)

Let $\mathcal{U}$ be the uniform distribution over $\\{-1,1\\}^{n}$ and let
$\mathcal{U}_{S}$ be the source distribution which is uniform in the set $S$
defined above (the “canonical holdout” setting). We study the question of
GOTU, in the following precise sense; we define

  * (1)

the error in the seen data at time $t$ as

$\displaystyle
L_{S}(\theta_{t})=\mathbb{E}_{x\sim\mathcal{U}_{S}}[(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}]$
(5.3)

where $f_{\mathrm{NN}}$ is the diagonal linear network with parameters
$\theta_{t}$ and $f^{\star}$ is the true target linear function;

  * (2)

the generalization on the unseen error at time $t$, as the error in the whole
population at time $t$

$\displaystyle
L(\theta_{t})=\mathbb{E}_{x\sim\mathcal{U}}[(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}]\,.$
(5.4)

This diagonal linear network is clearly _overparameterized_ for the task of
learning linear functions when the number of layers $L\geq 2$. Indeed, in
[ABLR23] it is shown that the diagonal linear network, when trained using
_gradient flow_ , will “memorize” the whole dataset (since it is labeled by a
linear function) and hence can achieve error $o(1)$ in the training loss on
the seen part, i.e., $L_{S}(\theta_{t})$ converges to $0$ as the time $t$
grows. However, as mentioned by [ABLR23], the generalization on the unseen
error $L(\theta_{t})$ will not be tending to zero since $x_{k}=1$ throughout
training; they prove that it will eventually be of order
$\mathrm{Inf}_{k}(f^{\star})=\left(\widehat{f}^{\star}(\\{k\\})\right)^{2}.$
In particular, “transfer” from $\mathcal{U}_{S}$ to $\mathcal{U}$ is _not_
happening for the function
$x\mapsto(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}$ for large enough
$t$.

Based on our general transfer inequality (5.1) we can immediately conclude
that, for large enough $t$, the low-degree function
$x\mapsto(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}$ does not satisfy
the conditions of Theorem 3.2. Motivated by a large body of work on “early
stopping” [YRC07, LSO20, JLT21], it is natural to ask whether there is hope
that transfer does hold for earlier stages in training.

Indeed, in the next result, we show that the conditions of Theorem 3.2 do hold
for the function $x\mapsto(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}$
for some non-trivial initial interval of time during training. To be more
specific, recall that we need the function
$f_{\mathrm{NN}}(\cdot~{};\theta_{t})-f^{\star}(\cdot)$ (which is by
definition linear, i.e., a $d=1$-degree polynomial on $x$) to be of
sufficiently small maximum influence, as described in Equation 3.1. A quick
calculation gives that its maximum influence $\tau(t)$ is given by

$\tau(t)=\frac{\max_{i\in[n]}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}(t)-\widehat{f}(\\{i\\})\right)^{2}}{\sum_{i\in[n]}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}(t)-\widehat{f}(\\{i\\})\right)^{2}}\,.$

Hence for our transfer inequality of Theorem 3.2 to be applicable, we need to
investigate whether

$\tau(t)\leq c(Q(S)/d)^{8d},~{}\textnormal{for some absolute constant}~{}c\,,$

which since, in our case, $d=1$ and $Q(S)=1/2$ boils down to

$\tau(t)<c_{0},~{}\textnormal{for some absolute constant}~{}c_{0}\,.$

Our result shows that, with high probability over the random initialization of
the weights of the diagonal linear network, there exists a time $t^{\star}$
such that $\tau(t)<c_{0}$ for $t<t^{\star}$ (and so transfer happens) and
$\tau(t)>c_{0}$ for $t>t^{\star}$ (our inequality is not applicable).

######  Proposition 5.2.

Let $n$ be sufficiently large. Fix $k\in[n].$ Let
$f^{\star}:\\{-1,1\\}^{n}\to\mathbb{R}$ be an arbitrary linear function with
$|\widehat{f}^{\star}(\\{k\\})|>\gamma>0$. Consider learning $f^{\star}$ with
gradient flow on a diagonal linear network
$f_{\mathrm{NN}}(\cdot~{};\theta_{t})$ with parameters $\theta_{t}$ as in
(5.2) and depth $L\geq 2$. The source distribution is the uniform over the
seen part $S=\\{x\in\\{-1,1\\}^{n}|x_{k}=1\\}$. For any
$\varepsilon\in(0,\gamma/2)$, there exists an $\alpha_{\max}$ (increasing with
$L$, depending on $\varepsilon$) such that if all the model’s parameters
$\theta_{0}$ at time $t=0$ are initialized i.i.d. under the uniform
distribution on $(-\alpha,\alpha)$ for any
$0<\alpha\leq\min\\{\alpha_{\max},1/2\\}$ then:

  1. (1)

(Theorem 3.11 in [ABLR23]) With probability 1, the training loss converges to
0, and the coefficient of the learned function $f_{\mathrm{NN}}$ on the
monomial $x_{k}$ is less than $\varepsilon$, i.e.,
$\widehat{f}_{\mathrm{NN}}(\\{k\\})\leq\varepsilon.$

  2. (2)

With probability $1-\exp(-\Omega(n))$ over the random initialization, there
exists a time

$t^{\star}=\Omega\left(\frac{1}{c^{L}}\log\left(\frac{n}{\gamma-\varepsilon}\right)\right),$

where $c$ is an absolute constant such that for $0<t<t^{\star}$, Equation 3.1
holds for the function
$f_{\mathrm{NN}}(~{}\cdot~{};\theta_{t})-f^{\star}(\cdot)$ with
$P=\mathcal{U}_{S}$ and $Q=\mathcal{U}$ and so

$\mathbb{E}_{x\sim Q}(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}\leq
C\cdot\mathbb{E}_{x\sim P}(f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x))^{2}\,,$

for some absolute constant $C,$ and, for $t>t^{\star}$, the condition of
Equation 3.1 fails to hold.

Based on Proposition 5.2 we conclude that transfer happens as long as
$t<t^{*}$ for some $t^{*}\gtrsim\log n$ (keeping the rest parameters
constant). The proof appears in Section A.3.

##  6\. Empirical Observations

In this section, we discuss further the empirical observations for the
continuous variant of our inequalities.

###  6.1. Setting

Returning to Figure 1 appearing in the introduction, we studied transfer
learning with source distribution $P=\mathcal{U}([0,1]\times[-1,1])$ and
target distribution $Q=\mathcal{U}([-5,5]^{2})$ with true function
$f^{\star}(x,y)=\sin(2\pi x)\sin(2\pi y)$ using as a regressor $f$ (i) a
degree-20 polynomial and (ii) a 6-layer size-110 ReLU network. The
architecture of the NN consists of 6 layers: the first 5 layers contain 20
nodes each and the last layer 10. For model (i), we run polynomial regression
and for model (ii), we run AdaGrad. In a similar spirit, we perform the same
experiment for $f^{\star}(x,y)=\sin(2\pi x)\sin(2\pi y)+xy$,
$P=\mathcal{U}([-1/2,1/2]^{2})$ and $Q=\mathcal{U}([-5,5]^{2})$; the
associated results are in Figure 2. The bottom right plot corresponds to a
6-layer size-110 polynomial NN, i.e., a standard network architecture where we
set the activation functions to be some polynomials. For our polynomial
network, we use as activation function the polynomial mapping
$\sigma(x)=3x^{2}-2x^{3}$.

Figure 2.  Transfer Learning with source distribution
$P=\mathcal{U}([-1/2,1/2]^{2})$ (see dotted box of top left plot) and the
target $Q=\mathcal{U}([-5,5]^{2})$ with true function
$f^{\star}(x,y)=\sin(2\pi x)\sin(2\pi y)+xy$ (top left) using as a regressor
$f$ (i) a degree-20 polynomial (top right), (ii) a 6-layer size-110 ReLU
neural network (bottom left) and, (iii) a 6-layer size-110 polynomial neural
network (bottom right).

###  6.2. Analysis of Results

Let us now comment on Figure 1 and Figure 2. Observe that polynomial
regression learns everything inside the dotted box, which is completely
observable and _non-trivially extrapolates_ around that box. On the contrary,
the ReLU network perfectly learns the observed box but _fails to extrapolate_
around it.

Let us now explain the connection between our Inequality (1.2) with the
extrapolation properties of polynomial regression in Figure 1 and Figure 2.
First note, that in both examples, $P$ and $Q$ are log-concave (in fact,
simply uniform in some rectangle). Hence, our main inequality (1.2) implies
that low-degree polynomials perform transfer learning, i.e., for any $f,p$
$d$-degree polynomials, it holds

$\mathbb{E}_{Q}(f-p)^{2}\leq
C_{d}\cdot\|dP/dQ\|_{\infty}^{2d}\cdot\mathbb{E}_{P}(f-p)^{2}.$

The true function $f^{\star}$ generating Figure 1 (and Figure 2) is not a
polynomial so it is perhaps not immediately clear that doing polynomial
regression on samples from $f^{\star}$ should be enjoying nice transfer
learning properties. Yet, thanks to $f^{\star}$ being smooth on a bounded
domain transfer is still happening. To see this, notice that $f^{\star}$ can
be well approximated by a polynomial $p^{\star}$. Indeed, since we are
interested in $L_{2}$ approximation on a bounded domain, we can use Taylor
approximation to have that for an appropriately high $d^{\prime},$ there is a
$d^{\prime}$-degree polynomial $p^{\star}$ for which both
$\mathbb{E}_{P}(f^{\star}-p^{\star})^{2}$ and
$\mathbb{E}_{Q}(f^{\star}-p^{\star})^{2}$ are arbitrarily small. Let $\hat{f}$
be the output of gradient descent on the polynomial regression task. If
$\hat{f}$ is such that $\mathbb{E}_{P}(f^{\star}-\hat{f})^{2}$ is arbitrarily
small, then, by triangle inequality, $\mathbb{E}_{P}(p^{\star}-\hat{f})^{2}$
becomes arbitrarily small as well. Crucially now $p^{\star}-\hat{f}$ is a
$\max\\{d^{\prime},d\\}$-degree polynomial. Therefore (as long as no
$d^{\prime},d$ became “too large”) our main inequality (1.2) implies
$\mathbb{E}_{Q}(f^{\star}-p^{\star})^{2}$ is becoming small. A final use of
triangle inequality concludes that $\mathbb{E}_{Q}(f^{\star}-\hat{f})^{2}$
becomes small too.

Now the trained ReLU network greatly fails to enjoy such nice extrapolation
properties in our example. We note that this observed inability of ReLU
networks to extrapolate, and in particular, the absence of a similar transfer
inequality like (1.2), is expected based on the literature. In fact, similar
failures of ReLU networks (see e.g., [KSTL23]) have been a topic of discussion
of extensive prior work. A large body of work has observed poor generalization
and overconfidence of NN when presented with OOD inputs [GLP20, KSTL23]. In
particular, NN trained with SGD could present extreme cases of _simplicity
bias_ [STR+20] (standard training procedures such as SGD tend to find simple
models). We leave the extent to which some neural networks (potentially
trained with early stopping) could still enjoy some desired transfer
properties as an interesting future direction.

##  7\. Proofs for the results on the Euclidean Domain

In our proofs, we will use anti-concentration properties of polynomial
functions under log-concave distributions, proved by Carbery and Wright
[CW01].

######  Proposition 7.1 (Theorem 8 in [CW01]).

There exists an absolute constant $C$ such that the following holds: let
$f:\mathbb{R}^{n}\to\mathbb{R}$ be a non-zero polynomial of degree at most
$d$, $\mu$ be a log-concave probability distribution over $\mathbb{R}^{n}$ and
$q,\gamma\in(0,\infty)$. Then it holds that

$\Pr_{x\sim\mu}\Big{[}|f(x)|\leq\gamma\Big{]}\leq\frac{Cq\gamma^{1/d}}{\left(\mathbb{E}_{\mu}|f|^{q/d}\right)^{1/q}}\,.$

In particular, for $q=d$, it holds that
$\Pr_{x\sim\mu}\Big{[}|f(x)|\leq\gamma\Big{]}\leq\frac{Cd\gamma^{1/d}}{\left(\mathbb{E}_{\mu}|f|\right)^{1/d}}\,.$

###  7.1. The Proof of Theorem 2.3

We continue with the proof of Theorem 2.3.

###### Proof.

For $\alpha\geq 1$, we define the divergence $D_{\alpha}(P\parallel
Q)\triangleq\left(\mathbb{E}_{x\sim
Q}\left[\left(\frac{P(x)}{Q(x)}\right)^{\alpha}\right]\right)^{1/\alpha}$; we
denote both distributions and associated density functions by $P,Q$
overloading the notation.

Let us fix some $\mu\in\mathcal{L}$ whose support contains both that of $Q$
and that of $P$. We will overload the notation and denote by $P$ (resp.
$Q,\mu$) the density of the associated distribution. The first step of the
proof is to upper bound the expectation of $f$ under $Q$ by that under $\mu$.
This is done by a simple change of measure and an application of Hölder’s
inequality with parameters $\alpha,\beta$:

$\mathbb{E}_{Q}|f|=\mathbb{E}_{x\sim\mu}\left[\frac{Q(x)}{\mu(x)}|f(x)|\right]\leq
D_{\alpha}(Q\parallel\mu)\left(\mathbb{E}_{\mu}|f|^{\beta}\right)^{1/\beta}\,.$
(7.1)

As a next step we need to relate expectations under the log-concave measure
$\mu$ and under the general measure $P$, which is the non-trivial part of the
argument. We will first lower bound the value of $\mathbb{E}_{P}|f|^{\beta}$.
For some $\gamma>0$ to be decided, we have that

$\mathbb{E}_{P}|f|^{\beta}\geq\mathbb{E}_{x\sim
P}\Big{[}|f|^{\beta}~{}\Big{|}|f(x)|^{\beta}\geq\gamma\Big{]}\Pr_{x\sim
P}\Big{[}|f(x)|^{\beta}\geq\gamma\Big{]}\geq\gamma\Pr_{x\sim
P}\Big{[}|f(x)|^{\beta}\geq\gamma\Big{]}\,.$

Hence we get that

$\mathbb{E}_{P}|f|^{\beta}\geq\gamma\left(1-\Pr_{x\sim
P}\Big{[}|f(x)|^{\beta}\leq\gamma\Big{]}\right)\,.$ (7.2)

In order to further lower bound the right-hand side of the above inequality,
it suffices to obtain an upper bound on the probability mass of the event
$\\{x\in\mathbb{R}^{n}:|f(x)|^{\beta}\leq\gamma\\}$ under $P$. We have that

$\Pr_{x\sim
P}\Big{[}|f(x)|\leq\gamma^{1/\beta}\Big{]}=\mathbb{E}_{x\sim\mu}\left[\frac{P(x)}{\mu(x)}~{}1\\{|f(x)|\leq\gamma^{1/\beta}\\}\right]\,.$

We can upper bound this quantity using Hölder’s inequality for
$\alpha,\beta\in[1,\infty]$ with $1/\alpha+1/\beta=1$:

$\Pr_{x\sim P}\Big{[}|f(x)|^{\beta}\leq\gamma\Big{]}\leq
D_{\alpha}(P\parallel\mu)\left(\Pr_{x\sim\mu}\Big{[}|f(x)|\leq\gamma^{1/\beta}\Big{]}\right)^{1/\beta}$
(7.3)

Using Proposition 7.1 in (7.3), by picking $q=\beta d$, we get that

$\Pr_{x\sim P}\Big{[}|f(x)|\leq\gamma^{1/\beta}\Big{]}\leq
D_{\alpha}(P\parallel\mu)\left(\frac{C\beta d\gamma^{1/(\beta
d)}}{\left(\mathbb{E}_{\mu}|f|^{\beta}\right)^{1/{\beta d}}}\right)^{1/\beta}$
(7.4)

We are now ready to pick $\gamma$. We choose $\gamma$ so that
$D_{\alpha}(P\parallel\mu)\left(\frac{C\beta d\gamma^{1/(\beta
d)}}{\left(\mathbb{E}_{\mu}|f|^{\beta}\right)^{1/(\beta
d)}}\right)^{1/\beta}=1/2\,,$ which implies that
$\gamma=\frac{\mathbb{E}_{\mu}|f|^{\beta}}{\left(C\beta
d2^{\beta}D_{\alpha}(P\parallel\mu)^{\beta}\right)^{\beta d}}\,.$ Using this
choice we can return to (7.2) and get that

$\mathbb{E}_{P}|f|^{\beta}\geq\frac{\mathbb{E}_{\mu}|f|^{\beta}}{2\left(Cd2^{\beta}D_{\alpha}(P\parallel\mu)^{\beta}\right)^{\beta
d}}$

We can now complete the proof using (7.1), which gives that

$\mathbb{E}_{Q}|f|\leq
D_{\alpha}(Q\parallel\mu)\left(\mathbb{E}_{\mu}|f|^{\beta}\right)^{1/\beta}\leq
2C^{d}d^{d}2^{d\beta}D_{\alpha}(Q\parallel\mu)D_{\alpha}(P\parallel\mu)^{\beta
d}\left(\mathbb{E}_{P}|f|^{\beta}\right)^{1/\beta}\,.$

By minimizing over $\mu\in\mathcal{L}$, the proof is complete. ∎

###  7.2. The Proof of Corollary 2.4

###### Proof of Corollary 2.4.

Following the same steps as in the proof of Theorem 2.3 we can get that

$\mathbb{E}_{P}|f|\geq\gamma\left(1-\Pr_{P}\Big{[}|f(x)|\leq\gamma\Big{]}\right)\,,$

and for $\alpha,\beta$ such that $1/\alpha+1/\beta=1$, we have

$\Pr_{P}\Big{[}|f(x)|\leq\gamma\Big{]}\leq D_{\alpha}(P\parallel
Q)\cdot\Pr_{Q}\Big{[}|f(x)|\leq\gamma\Big{]}^{1/\beta}\,.$

In the above, since for any $x$ with $P(x)>0$, it holds that $Q(x)>0$, the
densities’ ratio does not explode. Since $Q$ is log-concave, we can apply
Proposition 7.1 and get

$\Pr_{P}\Big{[}|f(x)|\leq\gamma\Big{]}\leq D_{\alpha}(P\parallel
Q)\cdot\left(\frac{Cd\gamma^{1/d}}{\left(\mathbb{E}_{Q}|f|\right)^{1/d}}\right)^{1/\beta}\,.$

By choosing $\gamma=\frac{\mathbb{E}_{Q}|f|}{(Cd2^{\beta}D_{\alpha}(P\parallel
Q)^{\beta})^{d}}$, we can conclude that

$\mathbb{E}_{Q}|f|\leq C^{d}d^{d}2^{\beta d}\cdot D_{\alpha}(P\parallel
Q)^{\beta d}\cdot\mathbb{E}_{P}|f|\,.$

∎

##  8\. Proofs for the Result in the Boolean Domain

We now focus on the proof of Theorem 3.2, that is of our main transfer
inequality in the Boolean domain.

###### Proof of Theorem 3.2.

Let $f(x)=\sum_{S\subseteq[d]}c_{S}\chi_{S}$ be a degree-$d$ multilinear
function from $\\{-1,1\\}^{n}$ to $\mathbb{R}$ and fix $Q$ and $P$ be two
distributions over $\\{-1,1\\}^{n}$. We assume that $f,Q,P$ are such that: (i)
$Q$ is product, i.e., $Q=\otimes Q_{i}$ and satisfies $\mathbb{E}_{x\sim
Q_{i}}[x]=0,\mathbb{E}_{x\sim Q_{i}}[x^{2}]=1$ and $\mathbb{E}_{x\sim
Q_{i}}[|x|^{3}]\leq\beta$ for any $i\in[n]$, (ii) $\sum_{|S|>0}c_{S}^{2}=1$
and $\sum_{S\ni i}c_{S}^{2}\leq\tau$ for all $i$, and, (iii) $P$ corresponds
to the distribution $Q$ conditioned on the seen part
$S\subseteq\\{-1,1\\}^{n}$ of the Boolean hypercube, i.e., $P=Q_{S}$ for some
set $S\subseteq\\{-1,1\\}^{n}$. We have that

$\mathbb{E}_{P}f^{2}\geq\gamma\cdot\left(1-\Pr_{P}[f^{2}\leq\gamma]\right)=\gamma\cdot\left(1-\Pr_{P}\left[\left(\sum_{S}c_{S}\chi_{S}\right)^{2}\leq\gamma\right]\right)\,.$

Hence, it suffices to upper bound the above right-hand side probability term.
Since $Q$ is supported on the Boolean hypercube, the ratio
$\|dP/dQ\|_{\infty}<\infty$ and we can proceed as follows:

$\Pr_{P}\left[\left(\sum_{S}c_{S}\chi_{S}\right)^{2}\leq\gamma\right]\leq\left\|\frac{dP}{dQ}\right\|_{\infty}\cdot\Pr_{Q}\left[\left|\sum_{S}c_{S}\chi_{S}\right|\leq\sqrt{\gamma}\right]\,.$

Next we remark that over $\\{-1,1\\}^{n}$, we have that
$g=|f|=\sum_{S}|c_{S}|\chi_{S}$ is a multilinear function of degree $d$ and
so, by the invariance principle (cf. Proposition 3.1) applied on $Q$ and $g$,
we get that

$\Pr_{x\sim
Q}\left[g(x)\leq\sqrt{\gamma}\right]\leq\Pr_{y\sim\mathcal{N}(0,I)}\left[g(y)\leq\sqrt{\gamma}\right]+O(d\beta^{1/3}\tau^{1/8d})\,.$

This means that

$\Pr_{x\sim
Q}\left[f(x)^{2}\leq\gamma\right]\leq\Pr_{y\sim\mathcal{N}(0,I)}\left[f(y)^{2}\leq\gamma\right]+O(d\beta^{1/3}\tau^{1/8d})\,.$

Next, we can apply the Carbery-Wright inequality (cf. Proposition 7.1) and get
that

$\Pr_{x\sim
Q}\left[f(x)^{2}\leq{\gamma}\right]\leq\frac{d\gamma^{1/2d}}{(\mathbb{E}_{y\sim\mathcal{N}(0,I)}f(y)^{2})^{1/2d}}+O(d\beta^{1/3}\tau^{1/8d})\,.$

Observe that

$\mathbb{E}_{y\sim\mathcal{N}(0,I)}[f(y)^{2}]=\mathbb{E}_{y\sim\mathcal{N}(0,I)}\left[\sum_{|S|\leq
d,|T|\leq
d}c_{S}c_{T}\chi_{S}(y)\chi_{T}(y)\right]=c_{\emptyset}^{2}+\sum_{|S|\leq
d}c_{S}^{2}=\mathbb{E}_{x\sim Q}[f(x)^{2}]\,,$

and so

$\Pr_{x\sim
Q}\left[f(x)^{2}\leq{\gamma}\right]\leq\frac{d\gamma^{1/2d}}{(\mathbb{E}_{x\sim
Q}f(x)^{2})^{1/2d}}+O(d\beta^{1/3}\tau^{1/8d})\,.$

We now have to optimize over $\gamma:$ we pick

$\gamma=\mathbb{E}_{x\sim
Q}[f(x)^{2}]/d^{O(d)}\cdot\left(\frac{1}{\|dP/dQ\|_{\infty}}-O(d\beta^{1/3}\tau^{1/8d})\right)^{2d}.$

Note that (i) since $P$ is the seen part of $Q$, we have that
$\|dP/dQ\|_{\infty}=1/Q(S)$, and (ii) we have, by assumption, that $Q(S)$ is
at least the invariance gap. These two properties imply that

$\mathbb{E}_{Q}[f^{2}]\leq\frac{d^{O(d)}}{(Q(S)-c_{1}d\beta^{1/3}\tau^{1/8d})^{2d}}\cdot\mathbb{E}_{P}[f^{2}]\,,$

for some constant $c_{1}>0$, which completes the proof. ∎

##  9\. Conclusion

In this work, we show general transfer inequalities for low-degree polynomials
in the Euclidean domain. We apply this inequality in order to obtain new
results in truncated statistics and in-context transfer learning for linear
attention layers. We also provide an extension of this inequality to the
Boolean domain and study its connections with the GOTU setup of [ABLR23].

So far, the theory of statistics and statistical learning theory have been
traditionally focusing on three axes: _sample complexity_ (how many examples
are required to learn the class), _expressivity_ (what type of functions can
be expressed by the class) and _training time_ (how much computation is
required to learn the class). In all three axes, multiple beautiful and
structural results have been proven. We believe that transferability (i.e.,
which distribution shifts do not deteriorate generalization) is also a crucial
criterion for the statistician. Our work demonstrates that general and
structural statistical results can also be proven in this axis, paving the way
for hopefully more to come. For instance, we present a few intriguing future
directions.

  1. (1)

Whether transferability holds or not is a property of (a) the class of
estimators used, (b) the pair of source and target distributions $P$ and $Q$,
_and_ , (c) the training algorithm. While our work focus solely on (1) an (2),
understanding the ability of transfer learning as an _algorithmic property_
(i.e., focusing on (3) apart from solely (1) and (2)) is an interesting
direction for future work.

  2. (2)

A natural question is whether similar inequalities can be obtained beyond
regression, for _classification settings_. It is rather clear that the answer
is, in general, no; consider the simple example of learning a threshold
function $h^{\star}(x)=\mathbb{1}\\{x>t^{\star}\\},x\in\mathbb{R}$ with source
distribution $P$ and target $Q$; if
$\mathrm{supp}(Q)=[t^{\star}-1,t^{\star}+1]$ and
$\mathrm{supp}(P)=[t^{\star}+c_{1},t^{\star}+2c_{1}]$ for $c_{1}>1$ then any
algorithm cannot distinguish $h^{\star}$ from the function $h=1$ using the
source labeled examples and hence cannot do better than random guessing in the
target distribution. Yet, it would be interesting if, for instance, one could
use our inequalities in the context of polynomial regression in agnostic PAC
learning by leveraging the connection between regression and classification.
As an example of this connection, we refer to the work of [KSV23] and
specifically their “transfer lemma” (Lemma 2.8).

  3. (3)

We establish in Theorem 2.3 that general transfer is possible in the
continuous domain for polynomial functions. Can we generalize our result
beyond polynomial functions? Interestingly, our experiments suggest ReLU
neural networks fail to enjoy such transfer properties, but is this a
structural truth or does something else in our experiment lead to this
failure? From a mathematical standpoint this quest is also non-trivial, as our
proof crucially uses the Carbery-Wright inequality which is proven solely for
polynomial functions. We believe exploring more this direction is interesting
both from a mathematical and applied point of view.

  4. (4)

Finally, our Theorem 3.2 deepens the connections between transferability and
key notions from Boolean Fourier analysis. We prove that as long as the
maximum influence of the error of an estimator is sufficiently small, the
estimator enjoys general transfer properties. The result naturally arises from
the invariance principle from Boolean Fourier analysis. From a mathematical
standpoint, the maximum influence condition is also necessary for transfer
inequalities to hold (e.g., the Dictator function provides a counterexample).
Yet, is the maximum influence the key measure that explains in practical
scenaria when a given estimator will enjoy desired transfer properties or not?
Our results do not answer this instance-specific question and we believe this
is a very interesting future direction to explore.

## References

  * [ABC+22] Emmanuel Abbe, Samy Bengio, Elisabetta Cornacchia, Jon Kleinberg, Aryo Lotfi, Maithra Raghu, and Chiyuan Zhang.  Learning to reason with neural networks: Generalization, unseen data and boolean measures.  Advances in Neural Information Processing Systems, 35:2709–2722, 2022.
  * [ABLR23] Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk.  Generalization on the unseen, logic reasoning and degree curriculum.  arXiv preprint arXiv:2301.13105, 2023.
  * [ACDS23] Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra.  Transformers learn to implement preconditioned gradient descent for in-context learning.  arXiv preprint arXiv:2306.00297, 2023.
  * [ACS+23] Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra.  Linear attention is (maybe) all you need (to understand transformer optimization).  arXiv preprint arXiv:2310.01082, 2023.
  * [AHK+24] Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, and Grigoris Velegkas.  Optimal learners for realizable regression: Pac learning and online learning.  Advances in Neural Information Processing Systems, 36, 2024.
  * [ASA+22] Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou.  What learning algorithm is in-context learning? investigations with linear models.  arXiv preprint arXiv:2211.15661, 2022.
  * [BCW+23] Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei.  Transformers as statisticians: Provable in-context learning with in-context algorithm selection.  arXiv preprint arXiv:2306.04637, 2023.
  * [BDBC+10] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  Machine learning, 79:151–175, 2010.
  * [BDBCP06] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of representations for domain adaptation.  Advances in neural information processing systems, 19, 2006.
  * [CB20] Lenaic Chizat and Francis Bach.  Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss.  In Conference on Learning Theory, pages 1305–1338. PMLR, 2020.
  * [CMM10] Corinna Cortes, Yishay Mansour, and Mehryar Mohri.  Learning bounds for importance weighting.  Advances in neural information processing systems, 23, 2010.
  * [Coh91] A Clifford Cohen.  Truncated and censored samples: theory and applications.  CRC press, 1991.
  * [CW01] Anthony Carbery and James Wright.  Distributional and lq norm inequalities for polynomials over convex bodies in rn.  Mathematical research letters, 8(3):233–248, 2001.
  * [CW21] T Tony Cai and Hongji Wei.  Transfer learning for nonparametric classification: Minimax rate and adaptive classifier.  The Annals of Statistics, 49(1), 2021.
  * [DGTZ18] Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis.  Efficient statistics, in high dimensions, from truncated samples.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 639–649. IEEE, 2018.
  * [DGTZ19] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis.  Computationally and statistically efficient truncated regression.  In Conference on Learning Theory, pages 955–960. PMLR, 2019.
  * [DHK+10] Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghavendra, Rocco A Servedio, and Li-Yang Tan.  Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 533–542, 2010.
  * [DKTZ21] Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, and Emmanouil Zampetakis.  A statistical taylor theorem and extrapolation of truncated densities.  In Conference on Learning Theory, pages 1395–1398. PMLR, 2021.
  * [DLLP10] Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál.  Impossibility theorems for domain adaptation.  In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 129–136. JMLR Workshop and Conference Proceedings, 2010.
  * [DLNS24] Anindya De, Huan Li, Shivam Nadimpalli, and Rocco A Servedio.  Detecting low-degree truncation.  arXiv preprint arXiv:2402.08133, 2024.
  * [DNS23] Anindya De, Shivam Nadimpalli, and Rocco A Servedio.  Testing convex truncation.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4050–4082. SIAM, 2023.
  * [DP15] Constantinos Daskalakis and Christos Papadimitriou.  Sparse covers for sums of indicators.  Probability Theory and Related Fields, 162:679–705, 2015.
  * [DRZ20] Constantinos Daskalakis, Dhruv Rohatgi, and Emmanouil Zampetakis.  Truncated linear regression in high dimensions.  Advances in Neural Information Processing Systems, 33:10338–10347, 2020.
  * [DS13] Ilias Diakonikolas and Rocco A Servedio.  Improved approximation of linear threshold functions.  computational complexity, 22(3):623–677, 2013.
  * [DSYZ21] Constantinos Daskalakis, Patroklos Stefanou, Rui Yao, and Emmanouil Zampetakis.  Efficient truncated linear regression with unknown noise variance.  Advances in Neural Information Processing Systems, 34:1952–1963, 2021.
  * [EPGF23] Mathieu Even, Scott Pesme, Suriya Gunasekar, and Nicolas Flammarion.  (s) gd over diagonal linear networks: Implicit regularisation, large stepsizes and edge of stability.  arXiv preprint arXiv:2302.08982, 2023.
  * [Erd45] P Erdös.  On a lemma of littlewood and offord.  Bulletin of the American Mathematical Society, 51(12):898–902, 1945.
  * [FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos.  Efficient algorithms for learning from coarse labels.  In Conference on Learning Theory, pages 2060–2079. PMLR, 2021.
  * [FKS21] Jacob Fox, Matthew Kwan, and Lisa Sauermann.  Combinatorial anti-concentration inequalities, with applications.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 171, pages 227–248. Cambridge University Press, 2021.
  * [FKT20] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos.  Efficient parameter estimation of truncated boolean product distributions.  In Conference on Learning Theory, pages 1586–1600. PMLR, 2020.
  * [FKT22] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos.  Perfect sampling from pairwise comparisons.  arXiv preprint arXiv:2211.12868, 2022.
  * [Gal98] Francis Galton.  An examination into the registered speeds of american trotting horses, with remarks on their value as hereditary data.  Proceedings of the Royal Society of London, 62(379-387):310–315, 1898.
  * [GKK23] Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros.  Learning hard-constrained models with one sample.  arXiv preprint arXiv:2311.03332, 2023.
  * [GKKM20] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser.  Beyond perturbations: Learning guarantees with arbitrary adversarial test examples.  Advances in Neural Information Processing Systems, 33:15859–15870, 2020.
  * [GLP20] Ishaan Gulrajani and David Lopez-Paz.  In search of lost domain generalization.  arXiv preprint arXiv:2007.01434, 2020.
  * [GM22] Itay Glazer and Dan Mikulincer.  Anti-concentration of polynomials: Dimension-free covariance bounds and decay of fourier coefficients.  Journal of Functional Analysis, 283(9):109639, 2022.
  * [GPSW17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In International conference on machine learning, pages 1321–1330. PMLR, 2017.
  * [GTLV22] Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant.  What can transformers learn in-context? a case study of simple function classes.  Advances in Neural Information Processing Systems, 35:30583–30598, 2022.
  * [HK19] Steve Hanneke and Samory Kpotufe.  On the value of target data in transfer learning.  Advances in Neural Information Processing Systems, 32, 2019.
  * [HKM09] Prahladh Harsha, Adam Klivans, and Raghu Meka.  Bounding the sensitivity of polynomial threshold functions.  arXiv preprint arXiv:0909.5175, 2009.
  * [HKM23] Steve Hanneke, Samory Kpotufe, and Yasaman Mahdaviyeh.  Limits of model selection under transfer learning.  arXiv preprint arXiv:2305.00152, 2023.
  * [JLT21] Ziwei Ji, Justin Li, and Matus Telgarsky.  Early-stopped neural networks are consistent.  Advances in Neural Information Processing Systems, 34:1805–1817, 2021.
  * [JSK+23] Saachi Jain, Hadi Salman, Alaa Khaddaj, Eric Wong, Sung Min Park, and Aleksander Madry.  A data-based perspective on transfer learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3613–3622, 2023.
  * [JT19] Ziwei Ji and Matus Telgarsky.  The implicit bias of gradient descent on nonseparable data.  In Conference on Learning Theory, pages 1772–1798. PMLR, 2019.
  * [Kan12] Daniel M Kane.  A structure theorem for poorly anticoncentrated gaussian chaoses and applications to the study of polynomial threshold functions.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 91–100. IEEE, 2012.
  * [KK21] Adam Tauman Kalai and Varun Kanade.  Efficient learning with arbitrary covariate shift.  In Algorithmic Learning Theory, pages 850–864. PMLR, 2021.
  * [KLS09] Adam R Klivans, Philip M Long, and Rocco A Servedio.  Learning halfspaces with malicious noise.  Journal of Machine Learning Research, 10(12), 2009.
  * [KM18] Samory Kpotufe and Guillaume Martinet.  Marginal singularity, and the benefits of labels in covariate-shift.  In Conference On Learning Theory, pages 1882–1886. PMLR, 2018.
  * [Kpo17] Samory Kpotufe.  Lipschitz density-ratios, structured data, and data-driven tuning.  In Artificial Intelligence and Statistics, pages 1320–1328. PMLR, 2017.
  * [KSTL23] Katie Kang, Amrith Setlur, Claire Tomlin, and Sergey Levine.  Deep neural networks tend to extrapolate predictably.  arXiv preprint arXiv:2310.00873, 2023.
  * [KSV23] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan.  Testable learning with distribution shift.  arXiv preprint arXiv:2311.15142, 2023.
  * [KSZ22] Alkis Kalavasis, Konstantinos Stavropoulos, and Emmanouil Zampetakis.  Learning and covering sums of independent random variables with unbounded support.  Advances in Neural Information Processing Systems, 35:25185–25197, 2022.
  * [KTZ19] Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis.  Efficient truncated statistics with unknown truncation.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1578–1595. IEEE, 2019.
  * [LCL22] Sai Li, T Tony Cai, and Hongzhe Li.  Transfer learning in large-scale gaussian graphical models with false discovery rate control.  Journal of the American Statistical Association, pages 1–13, 2022.
  * [LIPO23] Yingcong Li, M Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak.  Transformers as algorithms: Generalization and implicit model selection in in-context learning.  arXiv preprint arXiv:2301.07067, 2023.
  * [LL19] Kaifeng Lyu and Jian Li.  Gradient descent maximizes the margin of homogeneous neural networks.  arXiv preprint arXiv:1906.05890, 2019.
  * [LO39] John Edensor Littlewood and A Cyril Offord.  On the number of real roots of a random algebraic equation. ii.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 35, pages 133–148. Cambridge University Press, 1939.
  * [LSO20] Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak.  Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks.  In International conference on artificial intelligence and statistics, pages 4313–4324. PMLR, 2020.
  * [MKFAS20] Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi.  Minimax lower bounds for transfer learning with linear and one-hidden layer neural networks.  Advances in Neural Information Processing Systems, 33:1959–1969, 2020.
  * [MMR09] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  arXiv preprint arXiv:0902.3430, 2009.
  * [MMR12] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Multiple source adaptation and the rényi divergence.  arXiv preprint arXiv:1205.2628, 2012.
  * [MNV15] Raghu Meka, Oanh Nguyen, and Van Vu.  Anti-concentration for polynomials of independent random variables.  arXiv preprint arXiv:1507.00829, 2015.
  * [MOO05] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz.  Noise stability of functions with low influences: invariance and optimality.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 21–30. IEEE, 2005.
  * [MPW23] Cong Ma, Reese Pathak, and Martin J Wainwright.  Optimally tackling covariate shift in rkhs-based nonparametric regression.  The Annals of Statistics, 51(2):738–761, 2023.
  * [NP20] Sai Ganesh Nagarajan and Ioannis Panageas.  On the analysis of em for truncated mixtures of two gaussians.  In Algorithmic Learning Theory, pages 634–659. PMLR, 2020.
  * [NV13] Hoi H Nguyen and Van H Vu.  Small ball probability, inverse theorems, and applications.  Erdős centennial, pages 409–463, 2013.
  * [O’D14] Ryan O’Donnell.  Analysis of boolean functions.  Cambridge University Press, 2014.
  * [Pea02] Karl Pearson.  On the systematic fitting of frequency curves.  Biometrika, 2:2–7, 1902.
  * [PMW22] Reese Pathak, Cong Ma, and Martin Wainwright.  A new similarity measure for covariate shift with applications to nonparametric regression.  In International Conference on Machine Learning, pages 17517–17530. PMLR, 2022.
  * [PPVF21] Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion.  Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity.  Advances in Neural Information Processing Systems, 34:29218–29230, 2021.
  * [QB13] Qichao Que and Mikhail Belkin.  Inverse density as an inverse problem: The fredholm equation approach.  Advances in neural information processing systems, 26, 2013.
  * [RCS21] Henry WJ Reeve, Timothy I Cannings, and Richard J Samworth.  Adaptive transfer learning.  The Annals of Statistics, 49(6):3618–3649, 2021.
  * [Rén61] Alfréd Rényi.  On measures of entropy and information.  In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 4, pages 547–562. University of California Press, 1961.
  * [RMH+20] Ievgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani.  A survey on domain adaptation theory: learning bounds and theoretical guarantees.  arXiv preprint arXiv:2004.11829, 2020.
  * [RV13] Alexander Razborov and Emanuele Viola.  Real advantage.  ACM Transactions on Computation Theory (TOCT), 5(4):1–8, 2013.
  * [SGZ23] Max Simchowitz, Abhishek Gupta, and Kaiqing Zhang.  Tackling combinatorial distribution shift: A matrix completion perspective.  In The Thirty Sixth Annual Conference on Learning Theory, pages 3356–3468. PMLR, 2023.
  * [SIS21] Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber.  Linear transformers are secretly fast weight programmers.  In International Conference on Machine Learning, pages 9355–9366. PMLR, 2021.
  * [SK12] Masashi Sugiyama and Motoaki Kawanabe.  Machine learning in non-stationary environments: Introduction to covariate shift adaptation.  MIT press, 2012.
  * [SKM07] Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller.  Covariate shift adaptation by importance weighted cross validation.  Journal of Machine Learning Research, 8(5), 2007.
  * [SSK12] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori.  Density ratio estimation in machine learning.  Cambridge University Press, 2012.
  * [STR+20] Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli.  The pitfalls of simplicity bias in neural networks.  Advances in Neural Information Processing Systems, 33:9573–9585, 2020.
  * [TJJ20] Nilesh Tripuraneni, Michael Jordan, and Chi Jin.  On the theory of transfer learning: The importance of task diversity.  Advances in neural information processing systems, 33:7852–7862, 2020.
  * [VONR+23] Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov.  Transformers learn in-context by gradient descent.  In International Conference on Machine Learning, pages 35151–35174. PMLR, 2023.
  * [VSP+17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [WKW16] Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang.  A survey of transfer learning.  Journal of Big data, 3(1):1–40, 2016.
  * [XZL+20] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  How neural networks extrapolate: From feedforward to graph neural networks.  arXiv preprint arXiv:2009.11848, 2020.
  * [YHC13] Liu Yang, Steve Hanneke, and Jaime Carbonell.  A theory of transfer learning with applications to active learning.  Machine learning, 90:161–189, 2013.
  * [YHC18] Liu Yang, Steve Hanneke, and Jaime Carbonell.  Bounds on the minimax rate for estimating a prior over a vc class from independent learning tasks.  Theoretical Computer Science, 716:124–140, 2018.
  * [YRC07] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.  On early stopping in gradient descent learning.  Constructive Approximation, 26:289–315, 2007.
  * [ZFB23] Ruiqi Zhang, Spencer Frei, and Peter L Bartlett.  Trained transformers learn linear models in-context.  arXiv preprint arXiv:2306.09927, 2023.
  * [ZQD+20] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He.  A comprehensive survey on transfer learning.  Proceedings of the IEEE, 109(1):43–76, 2020.

##  Appendix A Deferred Proofs

In this section, we present all the missing proofs from the main body of the
paper.

###  A.1. The Proof of Corollary 4.4

###### Proof of Corollary 4.4.

Fix some $\alpha>0$. Let us consider the input feature vectors
$x^{(1)},...,x^{(N)}$.

Let us fix a model $f$ and some feature $x^{(i)}$. Then we introduce the
polynomial $f_{i}$ over $\mathbb{R}$

$f_{i}(y)=\frac{1}{2}(y-f(x^{(i)}))^{2}\,.$

It is clear that $f_{i}$ is a non-negative degree-$2$ polynomial of $y$. To
get the desired result, we will apply $N$ times our Corollary 2.4, once for
each polynomial $f_{i}(y),i\in[N]$. For any $i\in[N]$, fix feature vector
$x^{(i)}$ and consider the log-concave target distribution
$Q^{(i)}=\mathcal{N}(f^{\star}(x^{(i)}),1)$ and source truncated distribution
$P^{(i)}=\mathcal{N}_{S}(f^{\star}(x^{(i)}),1)$. For the $i$-th case, our
Corollary 2.4 implies that

$\mathbb{E}_{y\sim Q^{(i)}}f_{i}(y)\leq
C\cdot\|dP^{(i)}/dQ^{(i)}\|_{\infty}^{2}\cdot\mathbb{E}_{y\sim
P^{(i)}}f_{i}(y)\,,$

for some absolute constant $C>0.$ Note that we have that
$\|dP^{(i)}/dQ^{(i)}\|_{\infty}=1/\alpha$ for any $i\in[N]$ under the mass
assumption for $S$. Let us finally take the uniform average of the $N$
inequalities and get

$\frac{1}{N}\sum_{i\in[N]}\mathbb{E}_{y\sim\mathcal{N}(f^{\star}(x^{(i)}),1)}f_{i}(y)\leq(C/\alpha^{2})\cdot\frac{1}{N}\sum_{i\in[N]}\mathbb{E}_{y\sim\mathcal{N}_{S}(f^{\star}(x^{(i)}),1)}f_{i}(y)\,.$

∎

###  A.2. The Proof of Corollary 4.9

###### Proof of Corollary 4.9.

Consider two distributions $P_{H},Q_{H}$ over $\mathbb{R}^{n}$ (distributions
over the normal vector of the linear function) and $P_{X},Q_{X}$ over
$\mathbb{R}^{n}$ (distributions over the feature space). Let us fix the source
distribution $P=P_{H}\otimes P_{X}^{\otimes(N+1)}$ and the target distribution
$Q=Q_{H}\otimes Q_{X}^{\otimes(N+1)}$888For simplicity we assume that
$Q_{X}=Q_{X}^{\mathrm{query}}$ but, due to independence of the random
variables, the proof could go through even if they are different.. Note that
each sample from $P$ or $Q$ can be seen as an in-context prompt.

Let us set $x=(x_{1},...,x_{N},x_{\mathrm{query}})$ and consider the squared
loss between the linear function $w^{\top}x_{\mathrm{query}}$ and the
prediction of a linear single-layer self-attention model, i.e.,
$f(x,w)=(u^{\top}Hu-w^{\top}x_{\mathrm{query}})^{2}$; recall (4.7) and note
that $H$ is a matrix where each entry is a low-degree polynomial of $x$ and
$w$ and $u$ is only depending on the trainable parameters of the LSA model,
which are considered fixed in the upcoming analysis. We hence remark that the
degree of $f$ is $d=O(1)$. Our goal is to relate the source loss
$\mathbb{E}_{P}[f(x,w)]$ with the target loss $\mathbb{E}_{Q}[f(x,w)]$.

Item (1) in Corollary 4.9 follows directly from Theorem 2.3 applied on $P$ and
$Q$ with $\beta=1$ and $\alpha=\infty$.

For Items (2) and (3), we will apply the proof technique of Theorem 2.3 on an
appropriate product subspace $\mathbb{R}^{n}\otimes...\otimes\mathbb{R}^{n}$
with $\beta=1$ and $\alpha=\infty$. We will focus on task shift (Item (2));
similar steps would yield the result for Item (3), thanks to the independence
of the random variables. For the case of task shift, we proceed as follows.

Let us fix some $\mu\in\mathcal{L}_{n}$, which is a log-concave measure over
$\mathbb{R}^{n}$. We will overload the notation and denote by $P_{H}$ (resp.
$Q_{H},\mu$) the density of the associated distribution. The first step of the
proof is to upper bound the expectation of $f$ under $Q=Q_{H}\otimes
Q_{X}^{\otimes N+1}$. Note that we will handle only a distribution shift for
the task distribution and so, thanks to the product structure of $Q$:

$\displaystyle\mathbb{E}_{(x,w)\sim Q}[f(x,w)]$
$\displaystyle=\mathbb{E}_{x\sim Q_{X}^{\otimes
N+1}}\mathbb{E}_{w\sim\mu}\left[\frac{Q_{H}(w)}{\mu(w)}f(x,w)\right]$ (A.1)
$\displaystyle\leq\|dQ_{H}/d\mu\|_{\infty}\left(\mathbb{E}_{x\sim
P_{X}^{\otimes N+1}}\mathbb{E}_{\mu}[f(x,w)]\right)\,,$ (A.2)

where in the last inequality we also used that $Q_{X}=P_{X}$.

As a next step we need to relate expectations under the log-concave measure
$\mu$ and under the general measure $P_{H}$. For some $\gamma>0$ to be
decided, we have that

$\displaystyle\mathbb{E}_{(x,w)\sim P}[f(x,w)]$
$\displaystyle\geq\mathbb{E}_{(x,w)\sim
P}\Big{[}f(x,w)~{}\Big{|}f(x,w)\geq\gamma\Big{]}\Pr_{(x,w)\sim
P}\Big{[}f(x,w)\geq\gamma\Big{]}$ $\displaystyle\geq\gamma\Pr_{(x,w)\sim
P}\Big{[}f(x,w)\geq\gamma\Big{]}\,.$

Hence we get that

$\mathbb{E}_{(x,w)\sim P}[f(x,w)]\geq\gamma\left(1-\Pr_{(x,w)\sim
P}\Big{[}f(x,w)\leq\gamma\Big{]}\right)\,.$ (A.3)

It suffices to obtain an upper bound on the probability mass of the event
$\\{(x,w)\in(\mathbb{R}^{n})^{\otimes N+2}:f(x,w)\leq\gamma\\}$ under $P$.
Under distribution shift from $P_{H}$ to $\mu$, we have that

$\Pr_{(x,w)\sim P}\Big{[}f(x,w)\leq\gamma\Big{]}=\mathbb{E}_{x\sim
P_{X}^{\otimes
N+1}}\mathbb{E}_{w\sim\mu}\left[\frac{P_{H}(w)}{\mu(w)}~{}1\\{f(x,w)\leq\gamma\\}\right]\,.$

We can upper bound this quantity as follows:

$\Pr_{(x,w)\sim
P}\Big{[}f(x,w)\leq\gamma\Big{]}\leq\|dP_{H}/d\mu\|_{\infty}\left(\Pr_{x\sim
P_{X}^{\otimes N+1},w\sim\mu}\Big{[}f(x,w)\leq\gamma\Big{]}\right)\,.$ (A.4)

Since $x$ and $w$ are independent and the product of two log-concave densities
is log-concave, we can apply Proposition 7.1 in (A.4), by picking $q=d$ (the
degree of $f)$, and get that

$\Pr_{(x,w)\sim
P}\Big{[}f(x,w)\leq\gamma\Big{]}\leq\|dP_{H}/d\mu\|_{\infty}\left(\frac{Cd\gamma^{1/d}}{\left(\mathbb{E}_{x\sim
P_{X}^{\otimes N+1},w\sim\mu}[f(x,w)]\right)^{1/{d}}}\right)\,.$ (A.5)

We choose $\gamma$ so that

$\|dP_{H}/d\mu\|_{\infty}\left(\frac{Cd\gamma^{1/d}}{\left(\mathbb{E}_{x\sim
P_{X}^{\otimes N+1},w\sim\mu}[f(x,w)]\right)^{1/d}}\right)=1/2\,,$

which implies, since $d$ is some absolute constant, that there exist some
universal positive constants $C,c$ so that

$\gamma=\frac{\mathbb{E}_{x\sim P_{X}^{\otimes
N+1},w\sim\mu}[f(x,w)]}{C\|dP_{H}/d\mu\|_{\infty}^{c}}\,.$

Using this choice we can return to (A.3) and get that, for some absolute
constants $C,c$,

$\mathbb{E}_{x\sim P_{X}^{\otimes N+1},w\sim
P_{H}}[f(x,w)]\geq\frac{\mathbb{E}_{x\sim P_{X}^{\otimes
N+1},w\sim\mu}[f(x,w)]}{C\|dP_{H}/d\mu\|_{\infty}^{c}}\,.$

We can now complete the proof using (A.2), which gives that

$\mathbb{E}_{(x,w)\sim Q}[f(x,w)]\leq
C\cdot\left\|\frac{dQ_{H}}{d\mu}\right\|_{\infty}\left\|\frac{dP_{H}}{d\mu}\right\|_{\infty}^{c}\cdot\mathbb{E}_{(x,w)\sim
P}[f(x,w)]\,.$

By minimizing over $\mu\in\mathcal{L}_{n}$, the proof for the task shift (Item
(2)) is complete. The proof for Item (3) is similar. ∎

###  A.3. The Proof of Proposition 5.2

###### Proof of Proposition 5.2.

Let us assume that $|\widehat{f}^{\star}(\\{k\\})|>\gamma>0$ and pick any
$\varepsilon\in(0,\gamma/2)$. Given that $\varepsilon$, we can tune the
initialization of the weights of the model as described in the Theorem. In
particular, we independently draw the random variable

$w_{i}^{(\ell)}(0)\sim\mathcal{U}(-\alpha,\alpha),i\in[n],\ell\in[L]\,,$

where $\alpha=\min\\{1/2,\alpha_{\max}\\}$ and
$\alpha_{\max}=\left((L-2)RT_{\varepsilon}+(8/\varepsilon)^{(L-2)/L}\right)^{1/(2-L)},R=1+|\widehat{f}^{\star}(\\{0\\})+\widehat{f}^{\star}(\\{k\\})|,T_{\varepsilon}=c\log(R/\varepsilon)$,
as defined by [ABLR23].

For $t>0$, recall that

$\theta_{t}=(b_{\mathrm{NN}}(t),w_{1}^{(1)}(t),...,w_{n}^{(1)}(t),...,w_{1}^{(L)}(t),...,w_{n}^{(L)}(t))\,,$

and

$f_{\mathrm{NN}}(x;\theta_{t})=b_{\mathrm{NN}}(t)+\sum_{i\in[n]}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}(t)\right)x_{i}\,.$

Let us consider the function
$f_{\mathrm{NN}}(\cdot;\theta_{t})-f^{\star}(\cdot)$, which is equal to

$f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x)=\sum_{S\subseteq[n]}(\widehat{f}_{\mathrm{NN}}(S;\theta_{t})-\widehat{f}^{\star}(S))\chi_{S}=(b_{\mathrm{NN}}(t)-b^{\star})+\sum_{i=1}^{n}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}(t)-\widehat{f}^{\star}(\\{i\\})\right)x_{i}\,.$

We consider the setting of [ABLR23][Theorem 3.11] where $P=\mathcal{U}_{S}$
and $Q=\mathcal{U}$. Since we have that $d=1,\beta=O(1)$ and $Q(S)=1/2$, the
condition requires that the maximum influence of
$f_{\mathrm{NN}}(\cdot;\theta_{t})-f^{\star}(\cdot)$, denoted as $\tau(t)$, is
at most $c_{0}<1$, for some absolute constant $c_{0}$, where

$\displaystyle\tau(t)$
$\displaystyle=\max_{i\in[n]}\mathrm{Inf}_{i}(f_{\mathrm{NN}}(\cdot;\theta_{t})-f^{\star}(\cdot))=\max_{i\in[n]}\mathbb{E}_{x\sim\mathcal{U}(\\{-1,1\\}^{n})}\mathrm{Var}_{x_{i}\sim\mathrm{Rad}(1/2)}[f_{\mathrm{NN}}(x;\theta_{t})-f^{\star}(x)]$
(A.6)
$\displaystyle=\frac{\max_{i\in[n]}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}(t)-\widehat{f}^{\star}(\\{i\\})\right)^{2}}{\sum_{i\in[n]}\left(\prod_{\ell=1}^{L}w_{i}^{(\ell)}(t)-\widehat{f}^{\star}(\\{i\\})\right)^{2}}\triangleq\frac{\max_{i\in[n]}\Delta(i,t)}{\sum_{i\in[n]}\Delta(i,t)}\,,$
(A.7)

where we normalize so that the conditions of the invariance principle are
satisfied. At time $t=0$, using the random initilization described above, we
have that

$\tau(0)=\frac{\Delta(i^{\star}(0),0)}{\sum_{i\in[n]}\Delta(i,0)}\,,$

where $i^{\star}(0)$ is the index with the largest gap at the initialization.
Our goal is to show that $\tau(0)<c_{0}$ with high probability over the
initialization.

Since the Fourier coefficients of $f^{\star}$ are $O(1)$ as $n$ increases, it
suffices to show that the sum of the random variables $\Delta(i,0),i\in[n]$
will be at least $cn$ with probability $1-\exp(-\Omega(n))$ for some absolute
constant $c$. To be more specific, consider the random variable

$X_{i}=1\\{\Delta(i,0)\geq\beta_{0}^{2}\\}$

for $i\in[n]$, where $\beta_{0}$ to be decided. The event $\\{X_{i}=1\\}$
corresponds to the “good” case where the initialization of the weights in
direction $i$ and the true Fourier coefficient differ by an absolute constant.

Note that $X_{1},...,X_{n}$ are independent Bernoulli random variables with

$\mathbb{E}[X_{i}]=1-\Pr[\Delta(i,0)<\beta_{0}^{2}]=1-\Pr_{w_{i}^{(1)}(0),...,w_{i}^{(L)}(0)}\left[\prod_{\ell=1}^{L}w_{i}^{(\ell)}(0)\in[\widehat{f}^{\star}(\\{i\\})-\beta_{0},\widehat{f}^{\star}(\\{i\\})+\beta_{0}]\right]\,,$

The random variable $Y_{i}=\prod_{\ell=1}^{L}w_{i}^{(\ell)}(0)$ is a product
of $L$ independent uniform random variables over $(-\alpha,\alpha)$ and so
$Y_{i}\in(-\alpha^{L},\alpha^{L}),L\geq 2$. The cumulative density function of
$Y_{i}$ at $z$ for $L=2$ is

$\displaystyle F_{Y_{i}}(z)$ $\displaystyle=\Pr[w_{i}^{(1)}w_{i}^{(2)}\leq
z]=\int_{-\alpha}^{\alpha}\Pr[w_{i}^{(2)}\leq z/x]f_{w_{i}^{(1)}}(x)dx=$
$\displaystyle=\int_{-\alpha}^{z}\frac{dx}{2\alpha}+\int_{z}^{\alpha}(-\alpha+z/x)\frac{dx}{(2\alpha)^{2}}=(z+\alpha)/(2\alpha)-\alpha(\alpha-z)/(2\alpha)^{2}-z\log(z/\alpha)/(2\alpha)^{2}\,.$

This means that the probability density function for $L=2$ is
$f_{Y_{i}}(z)=C_{1,\alpha}-C_{2,\alpha}\log(z)$ for some constants
$C_{1,\alpha},C_{2,\alpha}$ and $Y_{i}$ is supported on
$(-\alpha^{2},\alpha^{2}).$ A similar expression can be obtained by induction
on $L$ for the case $L>2$. This means that

$\mathbb{E}[X_{i}]=1-\mathbb{1}\\{\widehat{f}^{\star}(\\{i\\})\in(-\alpha^{L},\alpha^{L})\\}\cdot
p_{i}$

where

$p_{i}(\alpha,L,\widehat{f}^{\star}(\\{i\\}),\beta_{0})=\int_{\widehat{f}^{\star}(\\{i\\})-\beta_{0}}^{\widehat{f}^{\star}(\\{i\\})+\beta_{0}}f_{Y_{i}}(z)dz\,.$

Note that since we initialize each weigth with a uniform distribution over
$(-\alpha,\alpha)$, the probability $p_{i}$ decreases as
$|\widehat{f}^{\star}(\\{i\\})|$ increases. Let us pick
$\beta_{0}=\alpha^{L}/1000$. If $|\widehat{f}^{\star}(\\{i\\})|>\alpha^{L}$,
then we are done, since $\Delta(i,0)$ is at least some absolute constant for
any $i\in[n]$. Otherwise, having fixed $\varepsilon,L$, the initialization
interval $(-\alpha,\alpha)$ is also fixed (independent of $n)$ and so the
probability of the “bad” event $p_{i}$ is a constant depending on
$\alpha,L,\widehat{f}^{\star}(\\{i\\})$ which is bounded away from $1$.

Recall that if $\sum_{i=1}^{n}X_{i}>cn$, for some absolute constant $c$, then
$\tau(0)<c_{0}$ for sufficiently large $n$. We have that

$\mu=\mathbb{E}\sum_{i=1}^{n}X_{i}=n-\sum_{i=1}^{n}{1\\{\widehat{f}^{\star}(\\{i\\})\in(-\alpha^{L},\alpha^{L})\\}}p_{i}(\alpha,L,\widehat{f}^{\star}(\\{i\\}),\alpha^{L}/1000)=Cn\,,$

for some absolute constant $C=C_{\alpha,L,f^{\star}}$. Hoeffding’s inequality
implies that

$\Pr\left[\left|\sum_{i=1}^{n}X_{i}-\mu\right|>\mu/10\right]\leq
2\exp(-\mu^{2}/50)\,.$

This means that with probability $1-\exp(-Cn)$, it holds that
$\sum_{i=1}^{n}X_{i}>cn$ for some absolute constants $C,c$. Conditioning on
this event, we get that

$\tau(0)\leq\frac{C}{n}<c_{0}$

for some absolute constant $C>0$. It remains to show that there exists
$t^{\star}>0$ such that $\tau(t)<c_{0}$ for $t<t^{\star}$ and $\tau(t)>c_{0}$
for $t>t^{\star}$.

As gradient flow evolves, it is shown in the proof of Theorem 3.11 in [ABLR23]
that

$\widehat{f}_{\mathrm{NN}}(\\{k\\})(t)\leq\varepsilon~{}~{}\forall t\,,$ (A.8)

and, for any $i\neq k$, it holds that

$\Delta(i,t)\leq\Delta(i,0)O(e^{-2c_{i}^{L-1}t})\,,$ (A.9)

where, for fixed $i\in[n]$, $c_{i}$ is defined as follows: first let
$j_{i}^{\star}=\operatorname*{arg\,min}_{j\in[L]}|w_{i}^{(j)}(0)|$ and take
$c_{i}=\min_{j\neq
j_{i}^{\star}\in[L]}(w_{i}^{(j)}(0))^{2}-(w_{i}^{(j_{i}^{\star})}(0))^{2}(>0$
with high probability). Moreover, $\Delta(i,t)$ is a decreasing function of
$t$ for $i\neq k$.

From (A.8) we know that $\Delta(k,t)=\Omega(1)$ with probability 1 since the
two Fourier coefficients have a constant gap. Since for $i\neq k,$ the
function $\Delta(i,t)$ is decreasing with $t$, it will hold that, with
probability 1, there exists some $t_{k}$ such that $i^{\star}(t)=k$ for any
$t>t_{k}$, i.e, the numerator of $\tau(t)$ is always equal to $\Delta(k,t)$
for $t>t_{k}$.

Fix a parameter $\eta$ sufficiently small. We will say that the diagonal
linear NN has learned $f^{\star}$ in direction $i\neq k$ if for some time
$t_{i}$, it holds that $\Delta(i,t)\leq\eta$ for any $t>t_{i}$. Clearly, the
diagonal linear NN cannot learn $f^{\star}$ in direction $k.$

Let us define $t^{\star}$ as the first time that $\tau(t^{\star})>c_{0}$. We
mention that $t^{\star}$ exists and is finite since $\Delta(i,t)$ are
decreasing in $t$ for $i\neq k$ but $\Delta(k,t)$ is not. Hence, $\tau(t)\to
1$ as $t\to\infty$.

This means that for any $t<t^{\star}$, the condition of Theorem 3.2 holds. On
the other side, when $t>t^{\star}$, our transfer inequality cannot be applied.

Having conditioned on the event that $\sum_{i=1}^{n}\Delta(i,0)>cn$, there
exists an absolute constant $\beta$ such that if $I_{0}$ is the set of indices
$i\neq k$ such that $\Delta(i,0)>\beta$, then $|I_{0}|=\Omega(n)$ (since each
$\Delta(i,0)$ is $O(1))$. We are going to specify a lower bound for the time
value $t^{\star}.$ It is necessary for $t^{\star}$ to be larger than a time
$t_{\mathrm{LB}}$ such that that $\sum_{i\in
I_{0}}\Delta(i,t_{\mathrm{LB}})=o(n);$ this means that at time
$t_{\mathrm{LB}}<t^{\star}$ there must exist $i\in I_{0}$ such that
$\Delta(i,t_{\mathrm{LB}})\leq C(\gamma-\varepsilon)^{2}/n$, where
$(\gamma-\varepsilon)^{2}$ is a lower bound on $\Delta(k,t_{\mathrm{LB}})$.
This means that it must be the case that
$\Delta(i,0)e^{-2c_{i}^{L}t_{\mathrm{LB}}}\leq C(\gamma-\varepsilon)^{2}/n$,
which implies that
$t_{\mathrm{LB}}\geq\frac{C_{i}}{2c_{i}^{L}}\log\left(\frac{n\Delta(i,0)}{C(\gamma-\varepsilon)^{2}}\right)$
for some absolute constants $C_{i},c_{i},C$. Then it holds that

$t^{\star}\geq\frac{C}{2c^{L}}\log(\beta n/(\gamma-\varepsilon))\,,$

for some absolute constants $C,c>0$. ∎

##  Appendix B Transfer Coefficient Examples

In this section, we give a couple of examples to better understand the
transfer coefficient of Theorem 2.3.

We first consider the setting where both $P$ and $Q$ are standard Gaussians
with means $0$ and $\mu$ respectively in the single-dimensional setting. We
show that the ratio $\|dQ/dP\|_{\infty}$ scales exponentially with the
distance of the two means. In the contrary when we consider the ratio
$\inf_{\nu}\|dQ/d\nu\|_{\infty}\|dP/d\nu\|_{\infty}$ the scaling drops to
polynomial, where the infimum runs over log-concave measures.

######  Lemma B.1 (Transfer Coefficient for Gaussians in 1D).

Consider target distribution $Q=\mathcal{N}(\mu,1)$ and source distribution
$P=\mathcal{N}(0,1)$ where $\mu\neq 0$. Then it holds that
$\|dQ/dP\|_{\infty}=\Omega(\exp(\mu^{2}))$ but there exists a log-concave
probability distribution $\nu$ such that
$\|dQ/d\nu\|_{\infty}\cdot\|dP/d\nu\|_{\infty}=1+O(\mu^{2}).$

###### Proof.

We have that $\|dQ/dP\|_{\infty}=\Omega(\exp(\mu^{2}/2))$ by setting $x=\mu$.
Without loss, assume that $\mu>0.$ Consider the function

$f(x)=1\\{x\leq
0\\}\mathcal{N}(0,1;x)+1\\{x\in(0,\mu)\\}\mathcal{N}(0,1;0)+1\\{x\geq\mu\\}\mathcal{N}(\mu,1;x)\,,$

where $\mathcal{N}(\mu,1;x)=\frac{1}{\sqrt{2\pi}}e^{-(x-\mu)^{2}/2}$. Clearly,
$f$ is not a density and, in order define the desired log-concave distribution
$\nu$ so we have to compute the value

$Z_{\nu}=\int_{\mathbb{R}}f(x)dx=1+\int_{0}^{\mu}\mathcal{N}(0,1;0)dx=1+\frac{\mu}{\sqrt{2\pi}}\,.$

Let us consider the measure $\nu$ with density $f/Z_{\nu}$. It remains to
argue about the value of each density ratio. We start with the case
$d\mathcal{N}(0,1)/d\nu.$

  * •

If $x\leq 0$, we have that

$\frac{d\mathcal{N}(0,1)}{d\nu}(x)=Z_{\nu}=1+\mu/\sqrt{2\pi}\,.$

  * •

If $x\geq\mu$, we have that

$\frac{d\mathcal{N}(0,1)}{d\nu}(x)=Z_{\nu}\cdot\frac{\exp(-x^{2}/2)}{\exp(-(x-\mu)^{2}/2)}\,.$

Since we take the supremum over $x\geq\mu$, we observe that the numerator
$\exp(-x^{2}/2)$ decays much faster than the denominator $\exp(-(x-\mu)^{2})$
in the interval $(\mu,\infty)$ and so the density ratio in this regime is
upper bounded by $1+\mu/\sqrt{2\pi}.$

  * •

Finally, if $x\in(0,\mu)$, then

$\frac{d\mathcal{N}(0,1)}{d\nu}(x)=Z_{\nu}\cdot\exp(-x^{2}/2)\,.$

This means that taking the supremum over $(0,\mu)$ we get a density ratio
upper bounded by $1+\mu/\sqrt{2\pi}$.

The cases for $\mathcal{N}(\mu,0)$ are symmetric. Hence in total we have that
the transfer coefficient

$\|d\mathcal{N}(0,1)/d\nu\|_{\infty}\|d\mathcal{N}(\mu,1)/d\nu\|_{\infty}=O((1+\mu)^{2})\,.$

We remark that the function $\phi(x)=1\\{x\leq
0\\}x^{2}+1\\{x\geq\mu\\}(x-\mu)^{2}$ is continuous and convex and so $\nu$ is
log-concave. ∎

We can also extend this construction in high dimensions.

######  Lemma B.2 (Transfer Coefficient for Gaussians in High Dimensions).

Consider target distribution $Q=\mathcal{N}(\mu,I)$ and source distribution
$P=\mathcal{N}(0,I)$ where $\mu\in\mathbb{R}^{n}$ with $\|\mu\|_{2}>0$. Then
there exists a log-concave probability distribution $\nu$ such that
$\|dQ/d\nu\|_{\infty}\cdot\|dP/d\nu\|_{\infty}=O((1+\|\mu\|_{2})^{2}).$

###### Proof.

Without loss of generality let us assume that $\mu=\gamma
e_{1}\in\mathbb{R}^{n},\gamma>0.$ Let us define the Gaussian density
$\mathcal{N}(\mu,I;x)=(2\pi)^{-n/2}\exp(-\|x-\mu\|_{2}^{2}/2)$. We consider
the mapping

$f(x)=1\\{x_{1}<0\\}\mathcal{N}(0,I;x)+1\\{x_{1}>\gamma\\}\mathcal{N}(\mu,I;x)+1\\{x_{1}\in(0,\gamma)\\}\mathcal{N}(0,I;(0,x_{-1}))\,,$

where $(0,x_{-1})$ corresponds to the $n$-dimensional vector $x$ with its
first coordinate fixed to 0. In order to make $f$ a density function that
corresponds to a distribution $\nu$, we have to normalize with the integral

$Z_{\nu}=\int_{\mathbb{R}^{n}}f=1+\int_{x_{1}=0}^{\gamma}\int_{x_{-1}}\mathcal{N}(0,I;(0,x_{-1}))dx=1+\gamma/\sqrt{2\pi}\,.$

Let us take $\nu$ be the log-concave distribution with density $f/Z_{\nu}$.
Then using a similar case analysis as in the 1-dimensional proof of Lemma B.1,
we get that the transfer coefficient is of order
$\|d\mathcal{N}(0,I)/d\nu\|_{\infty}\|d\mathcal{N}(\mu,I)/d\nu\|_{\infty}=O((1+\|\mu\|_{2})^{2})$.
∎

We remark that the way we design the distribution $\nu$ in the above lemma can
be adapted to more general log-concave distributions $P$ and $Q$ where $Q$ is
a translated version of $P$ and $P$ is a product measure.

######  Lemma B.3 (Transfer Coefficient for Translated Log-concave Products).

Consider a source distribution $P$ with density
$P(x)=\prod_{i\in[n]}\phi_{i}(x_{i})$, where each $\phi_{i}$ is log-concave
with mode at 0 and $\phi_{i}(0)=\Theta(1)$ and let $Q$ be a translation of $P$
in direction $\mu\in\mathbb{R}^{n}$. Then there exists a log-concave
probability distribution $\nu$ such that
$\|dP/d\nu\|_{\infty}\|dQ/d\nu\|_{\infty}=O((1+\|\mu\|_{2})^{2})$.

###### Proof.

Let $\mu=\gamma e_{1},\gamma>0$. Then define
$f(x)=1\\{x_{1}<0\\}P(x)+1\\{x_{1}>\gamma\\}P(x-\gamma
e_{1})+1\\{x_{1}\in(0,\gamma)\\}P(0,x_{-1})$, where $(0,x_{-1})$ corresponds
to the $n$-dimensional vector $x$ with its first coordinate fixed to 0. In
order to make $f$ a density function we have to normalize with the integral
$\int_{\mathbb{R}^{n}}f=1+\int_{x_{1}=0}^{\gamma}\phi_{1}(0)\int_{x_{2}}\phi_{2}(x_{2})\cdots\int_{x_{n}}\phi_{n}(x_{n})=1+\int_{x_{1}=0}^{\gamma}\phi_{1}(0)=1+\Theta(\gamma)$.
The result follows by a similar case analysis as in Lemma B.1. ∎

We mention that the above results can be extended for translations of log-
concave densities over $\mathbb{R}^{n}$ which are not necessarily products. As
a simple ilustration, consider $P=\mathcal{N}(0,\Sigma)$ and
$Q=\mathcal{N}(\gamma e_{1},\Sigma)$ for some arbitrary full-rank $\Sigma$ and