A Generalization Theory for Zero-Shot Prediction
Authors: Ronak Mehta
Zaid Harchaoui
Venue: ICML 2025 oral (2025)
Keywords: zero-shot
self-supervised learning
foundation models
learning theory
statistical theory
Primary area: theory->learning_theory
TL;DR: We present a theoretical framework for zero-shot prediction by prompting, highlighting the conditional independence relationships supporting the success of this approach.

Abstract: A modern paradigm for generalization in machine learning and AI consists of pre-training a task-agnostic foundation model, generally obtained using self-supervised and multimodal contrastive learning. The resulting representations can be used for prediction on a downstream task for which no labeled data is available. We present a theoretical framework to better understand this approach, called zero-shot prediction. We identify the target quantities that zero-shot prediction aims to learn, or learns in passing, and the key conditional independence relationships that enable its generalization ability.

A Generalization Theory for Zero-Shot Prediction
Ronak Mehta Zaid Harchaoui
Abstract
large unlabeled dataset 21,...,,Ny E X is used to produce an encoder a : + R2, The embedding a(x) is thought to contain information that is relevant for predicting y from x. Pre-training typically occurs through the process of self- supervised learning (SSL), using a pretext task that can be solved with only instances of x (e.g. filling in blank im- age patch). In FSL, the user may then access a labeled dataset (ar y lab). ...b)...... (arla,, y from which a predic- tor can be trained inexpensively. This often takes the form of a linear classifier x + Wa( + for W E R/9 xd and b E RIM, Where ZSP departs from FSL the additional challenge of being given no directly labeled training data.
A modern paradigm for generalization in ma- chine learning and AI consists of pre-training task-agnostic foundation model, generally ob- tained using self-supervised and multimodal con- trastive learning. The resulting representations can be used for prediction on a downstream task for which no labeled data is available. We present a theoretical framework to better understand this approach, called zero-shot prediction. We iden- tify the target quantities that zero-shot prediction aims to learn, or learns in passing, and the key conditional independence relationships that en- able its generalization ability.
At first glance, ZSP seems impossible. Yet, the ingemu- ity of practitioners has yielded the following solution; if 1) each pre- traininii example o; is paired with another "view" z; E (c.g. a caption in natural language) and 2) if each label y E y can intelligently be embedded into Z, then the relationship between each æ; and z; could provide the means to perform prediction. Concretely, one learns com- plementary encoder B 2 + I& during pre-training and = for E y and k l...., m. Then, designs prompts z
1. Introduction
In 2021, OpenAI shocked the world by improving the zero- shot classification accuracy on ImageNet from 11.5% to 76.2% via the CLIIP series of models (Radford et al., 2021). This event redefined the goal of zero-shot prediction from producing models that generalized to unseen classes to those that generalized unseen tasks entirely. Two fun- damental drivers of CLIP's success were 1) the use of natural language as medium for representing arbitrary classes (as in the previous state-of-the-at Visual N- N-grams (Li et al., 2017)), and 2) a massive, yet carefully designed pre-training set which significantly impacted downstream performance (Radford et al., 2021; Fang et al., 2023; Xu al., 2024). Despite the remarkable success of these foun- dation model-based pipelines (Bommasani et al., 2022), there are unique components of zero-shot prediction that warrant investigation from a theoretical point of view.
x + arg max DEY
Σ ((()),
(1)
m
Amm
is employed for prediction. An template text "photo of a _.", ". where the blank can be filled by the textual representation of the class (e.g. "cat" or "dog"). The ZSP pipeline, from pre-training to prompt selection, is clearly a wild departure from what is explained by statistical learning theory. Moreover, while some com- ponents of these systems have been studied in the context of FSL (such as the reasons why various pre- wee-training objec- tives result in encoders that provably accelerate learning), unique aspects of ZSP, such as the role of prompting and the cost of "translating" modalities, have not yet received thcoretical treatment. Herein lies our question.
An example of a prompt is the
To clarify these gaps, we contrast zero-shot prediction (ZSP) with the related setting of few-shot learning (FSL). Let x E X denote an input (often an image) that accompa- nies discrete value y y (often a class label). Common to both ZSP and FSL is pre-training procedure in which
Department Statisties, University of Washington, Seattle. Correspondence to: Ronak Mehta <ronakdm @ uw.edu>.
Through what decomposition of downstream task performance we compare zero-shot prediction to the direct supervised learner, with a transparent de- pendence on the 1) pre-training distribution, 2) eval- uation distribution, and 3) prompting strategy?
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Generalization Theory for Zero-Shot Prediction
Contributions. In Sec. 2, we present learning theoretic framework for the nee-raannng//vallatoo/rroopppppi data and propose two expressions for the population counterpart of (I). These expressions, while equivalent at the popula- tion level, reflect two classes of learning methods which we call the "conditional mean" and the "information density" approaches. In Sec. 3, we prove a generic decomposition of the prediction error on the downstream task, which fur- nishes three components: prompt bias measures the com- patibility of the prompt strategy with the pre-training and evaluation distributions, residual dependence measures the information- -tepmattion-hhoretic cost of using one modality to make predictions on another, and estimation error quantifies the effect of the finite number of pre-training examples and prompts. The estimation error decomposes further depend- ing on whether the conditional mean or information density approaches are taken. To provide insight and demonstrate the usefulness of the decomposition, we analyze the perfor- mance of nonparametric regression methods for each ap- proach by way of simite-sample bounds in high probability. Our framework arms practitioners with a means to imbue existing SSL-to-ZSP pipelines with theoretical guarantees, depending on the approach with which they best align. In Sec. 4, we illustrate our theoretical claims by empirically evaluating prompt bias and residual dependence on zero- shot prediction tasks with simulated and image data.
While informative representations are essential, the core of 7SP is the remarkable ability of models to make predic- tions without any task-specific data, challenge even for the perfect encoder. For context, we avoid the historical term "zero-shot learning" (Larochelle et al., 2008; Akata et al., 2015), which refers to a setting in which pre-training data is not only labeled, but contains metadata-base fea- tures associated with each class. In general, this only han- dles unseen classes, and only if the same features are ob- served at inference time. To our knowledge, the only work studying 7SP based on self- pre-training is Chen et al. (2024). In particular, Chen et al. (2024, Theorem 4.2 and Corollary 5.1) provides bounds on the top-k accuracy of ZSP for CLIPPbased encoders. However, the bound in- creases with the batch size, may not decay to zero even if the pre-training loss is fully optimized and upstream and downstream data distributions are the same, and does not seem to explicitly depend on the prompt quality. The inde- pendent and concurrent work of Oko et al. (2025) develops a statistical analysis based on sufficiency notions, with the aim of capturing the predictive performance in the down- stream task. Their work is complementary to ours, in that they determine the distributional parameter learned by the CLIP objective, but also assume that the prompting strat- egy and downstream data distribution are "idealized", in that the prompt bias and residual dependence quantities al- luded to in the contributions are zero
On the applied side, we are inspired by the number of works that use diverse, class-specific prompts generated us- ing large language models (LLMs) for enhancing 7SP per- formance (Pratt et al., 2023; Yang et al., 2023; Maniparam- bil et al., 2023) and interpretability (Menon and Vondrick, 2023; Esfandiarpoor et al., 2024). While these empiri- cal methods, such as the customized prompts via language models method (CuPL, Pratt et al. (2023)), are often de- signed using intuition from human understanding of natural language, we aim to offer a theoretical explanation for their success from statistical learning theory and probabilistic graphical modeling perspective. Despite this particular ap- plication of LLMs, we also acknowledge that "prompting" in ZSP has a different meaning than in the growing field of prompt engineering. in which inputs are designed for large language models (Pryzant et al., 2023; Wang et al., 2024; Guo al., 2024; Sclar et al., 2024).
Related Work. One can argue that precursors to both FSL and ZSP in machine learning can be found in the literature of meta-learning, or "learning to learn" (Thrun and Pratt, 1998; Andrychowicz et al., 2016; Finn et al., 2017). There, the downstream evaluation tasks are given to the user up- front, so that pre-training an encoder and training predic- tor for all of the evaluation tasks can be performed in one step. On the other hand, FSL and ZSP both involve fully lask-agnostic pre- gre-training phases. Seminal work in com- puter vision on matching words and pictures is also worth mentioning (Barnard et al., 2003; Forsyth et al., 2009).
Two complementary bodies of work studied phenomena common to FSL and 7SP. The first considers which proper- ties of learned encoders can provably improve downstream performance (Wang and Isola, 2020; HaoChen et al., 2021; Atzmon et al., 2020; Wang and Jordan, 2024; Du and Xi- ang, 2024). The other is dedicated to explaining how oth- erwise mysterious SSL objectives achieve these properties (Wen and Li, 2021; Li al., 2021; Pokle al., 2022; Kiani et al., 2022: Johnson et al., 2023; Shwartz-Ziv et al., 2023). In particular, Balestriero and LeCun (2022) and Tan et al. (2024) relate various SSL objectives to spectral clustering. One FSL-specific line of work studies when linear map- pings of pre-trained encoders can achieve optimal down- stream performance (Saunshi et al., 2019; HaoChen et al., 2021; Tosh et al., 2021; Lee et al., 2021).
2. Theoretical Framework
We introduce the mathematical objects that connect the ampirically-mottivere predictor (1) to its theoretical coun- terpart analyzed in Sec. 3. For the reader's convenience, a global notation table is provided in Appx. A.
2

---

A Generalization Theory for Zero-Shot Prediction
Unimodal Contrastive
Reconstructive
Multimodal Contrastive
C
C
"Look kitten"
X
Z
X
Z
X
Z
Yx
Yz
Y
Y
Figure I. Graphical Models of Prediction Paths. Each directed graphical model corresponds to the data types and dependence struc- tures for various SSL pre-training approaches. The variable C' represents unobserved context that determines the observed data- generating distribution. Dotted lines indicate the possibility presence or absence the arrow. Methods compatible with 7SP may learn the relationship between X and Z directly, whereas the relationship between Z and Y is learned via prompting. Methods that compatible with FSL learn the label Y as a latent variable in the process of solving the pretext task.
Prediction Setups. Consider random variables X, Y, and Z observed in X, y, and 2, respectively. We interpret X as the space of images, y as the (not necessarily discrete) space of labels, and as the space of text captions.
X x 2, called the pre-training distribution, and the prompt distribution py,z on y x 2. which represents the user- defined strategy for generating prompts. As a theoretical model for ZSP, we propose the function
Consider probability measure Px,y X x y, called the evaluation distribution. We specify collection of down- stream tasks, with which we may evaluate predictors on data drawn from Px.y (e.g. CIFAR-10) 10). Consider func- tion r y + R, and the least squares prediction problem
no ( = Eqx.z (x)))
(4)
called the indirect predictor, where
gp(2) = EEpri [r(V)
(5)
min EXx.Y [()(X) - r v----R
(2)
Notice that relies only on Px, while 7o is two- stage predictor relying only on the pair (Qx.2, PY,z). ). The pre-training, evaluation, and prompt distributions represent pairwise dependencies between the random variables X, Y, and Z, well as the observable data of the problem. In- tuitively, our analysis of the performance gap between the direct and indirect predictors will quantify the "compatibil- ity" of these three fundamental distributions as a possible joint distribution on y x 2.
The function r serves only to handle multiple task for- mats such regression (r(y) y) or binary classification (r(y) = fy 1}) in unified manner. We discuss for- mulations of multi-class classification and structured pre- diction in Sec. 3. The optimizer of (2) over E L²(Px)', or all measurable, square-integrable functions on X, is
(x) = Epy. [r(Y)] (z).
(3)
Prediction Paths of FSL and ZSP. For context, we con- trast our setup with previous theoretical analyses of FSL, aiming to 1) highlight the fundamental differences between SSL-for-FSL and fSL-for-ZSP, 2) describe assumptions we make (and do not make) to best align with applica- tions. First, we consider two common SSL tasks that precede FSL. In unimodal contrastive learning, X and Z are augmented/corruptee images, and the pretext task is to identify examples derived from the same ("+") or differ- ent ("-") underlying image (Chen et al., 2020). In re- constructive SSL, the encoder is pre-trained to predict a hidden portion of the raw/embedded image (Assran et al., 2023). Foundational works such as Saunshi et al. (2019)
We will call this the direct predictor throughout this pa- per, which will contrast our viewpoint of ZSP as an indi- rect, multi-stage prediction procedure. Indeed, the prompt- ing step in (1) resembles an empirical average of draws from probability distribution Z. based on the class la- bel Y y (especially when considering the M--ee generation methods mentioned in Sec. 1), whereas the en- coders capture dependence relation between X and Z. Accordingly, we introduce a probability measure Qx,z on
II the appendix, carefully construct L -spaccs equivalence classes of functions (see Appx. B.I) for explicitness and rigor. We do not belabor this distinction in the main text.
of
3

---

A Generalization Theory for Zero-Shot Prediction
and Wang and Isola (2020) explain the success of these SSL-for-FSL pipelines by the following mechanism: the labels y used in the downstream task form a latent vari- able mixture model for the pre- pre-training set, i.e. Qx,2 = Evey Qx,Z (y). Thus, generalization guaran- lees hinge upon the fact that learning parameters of the pre-training distribution must inherently capture its latent variables (the downstream labels). This theory is visual- ized in Fig. 1 (left & center); observe that if the dotted ar- rows were absent, the only path to solve the pretext task is through the label. This FSL "prediction path" motivates another prevalent assumption of exactaaproximate condi- tional independence of X and Z given Y (e.g., as in Lee et al. (2021)). We avoid this assumption, which is unreal- istic in the multimodal context as the dependence between an image and its caption is unlikely to be fully explained by coarse label such as "cat". Moreover, this latent la- bel model assumes equality of the marginals Px = Qx on X. As concrete example, this amounts to assuming that the marginal distribution of images on the Internet (Qx) is equal to that of CIFAR-10 images (Px). We explicitly track this mismatch in our generalization bounds.
As a preview, consider the example of balanced binary clas- sification (r(y) 1 {y = 13) and the classifier that returns 1 when (2(x)) 2 1/2 and 0 otherwise. We will show that there exist encoders a : X - F and [ 2 + R and a sequence of scalars 01 2 2 od 2 0 such that if pz R Qz and is sufficiently large, then this classifier is equivalent to
x + arg ya (a())), [3(Z)Y = u)),
(6)
where (u, v). == E o,, This expression mir- rors (1) down to a rescaling of the inner product. We now present the expressions that are used to derive (6).
For the first, let Qx and Qz be the marginals of Qx.z on X and Z,, respectively. We introduce the fundamental conditional mean operator M2jx L²(Qz) - ('xx), which assigns to any g E L'(Qz) the function x + EQx. [o()))X] (z). Then, it holds by definition that
(,(x) = [M2)x9p)2x).
For the second, consider the case in which Qx.z < Qx Qz², where Qx denotes the probability distribu- tion of the pair (X, Z) drawn independently as X ~ Qx and Z ~ Qz. Then, we define the Radon-Nikodym deriva- tive == dQx,2, the information density² has long history in statistics and information theory. Using R (Lem. 6, Appx. B.3), the indi- rect predictor writes as
For ZSP, the prevailing SSL pretext task is multimodal contrastive learning (Fig. I, right), wherein the foundation model learns similarity function (x, 2) + (z))) To discuss a joint distribution P = Px,,,2, we adopt a la- tent caption model that associates X ~ Px with an unob- served Z-valued latent variable Z (i.e. an unobserved cap- tion). Because pre- pre-training connects X to Z and prompting then connects Y to Z, the ideal dependence structure for ZSP is fundamentally different from FSL; if X and Y are conditionally independent given Z, the direct and indirect predictors are in fact equivalent. Indeed, the tower property of conditional expectation gives the identity
aQxQz : x 2 - R2 The function R, called
Mp(x) = -Eq (gp(Z)R(z, 2) = EEpy, x [r(Y)R(z, Z)] + crr(Q2,
(8)
where err(Qz,p>) term measures the discrepancy be- tween the marginal distributions of the captions gener- ated during pre-traiming and prompting, respectively. The expressions (7) and (8), while equal at the population level, motivate two categories of approaches for learn- ing/estimation that have different statistical properties. The "conditional mean" approach uses pre- pre-training data to learn the operator Mz x and prompts to approximate the func- tion 9p- On the other hand, the "information density" ap- proach learns the function R during pre-training, and ap- proximates the expectation over PY.z using prompts. The information density approach is particularly reflective of the prompting aspect of (1), as one may perceive 2 for k = =1 l,..., m and y E y as M = m | as samples from
n. (x) = P [r(Y) (z)
= P [ (1))) (x)
= Er [r [r()] (z)). (X T YIZ)
The final expression is not equal to (4) because of the differ- ence between (Qx,2, PY.z) and (Px.z. Py.z). Addition- ally, X and Y are not necessarily conditionally indepen- dent given Z. These discrepancies are precisely exposed in our analysis via a measure of distribution mismatch and measure of the conditional dependence of X and Y given z. The latter formalizes the information -theoretccc cost of using natural language as a proxy for image classification.
'A distribution i on U is absolute continuous with respect to another distribution v (denoted μ. & 1/) if v(A) = 0 = ((A) = 0 for every measurable set A C U. If so, there exists RadonnNikodyy derivative du : - R20 such that for every mcasurable set A C U, it holds that μe(
Representations of the Indirect Predictor. We estab- lish several central identities involving the indirect predic-
tor (4). These expressions will strengthen the justification for To as the target function of ZSP and naturally lead to two classes of learning methods that we analyze in Sec. 3.
SA du (u)dd(u). de
"This term actually refers to (x, x) + log R(æ z). but for simplicity, use it for Resee Dytso et al. (2023, Eq. (11).
4

---

A Generalization Theory for Zero-Shot Prediction
PY,z with py chosen be uniform on y. These are then used replace the expectation in (8).
which intends to capture the end-to-end performance from pre-training to downstream prediction.
Finally, we tie back to (6) and describe the formal connec- tion between Mz and R. In Prop. 2 (Appx. B.3), we prove the decomposition of the form
For h E L2(Px), we define the norm [|Al) Jx (x)))xxx(x) using analogous notation for other prob- ability distributions. We will assume throughout the paper that r is bounded by B, with probability one under Py and py, so that 7pp 77 E (P(x). Given square-integrable ip- we first control the mean squared error (MSE) via Im. i Applip(Px)
R(x, z) = (a(x),,((z) + Ed,
(9)
where Ed + 0 as d + oc. Then, (6) follows under the given conditions by plugging (9) into (8).
The encoders a = (ai...... (d)) and 3 = (BI,..., 34), and constants (ox) are none other than the components of the truncated singular value decomposition (SVD) of
2 | - Mo (Ps))) +2 (in--plllee
(12)
information-tevveeic error
estimation error
Mz (Prop. 1, Appx. B.3). The SVD of M2 x and the in- formation density R characterize the full dependence struc- ture of Qx because R is identically 1 when Qx,z = Qx 12Q we may define the (squared) mean square contin- gency dependence measure
The information theooretict error captures the prompt bias and residual dependence that differentiates indirect and di- rect prediction, whereas the estimation error is familiar term in statistical analysis. We discuss in Appx. D.4 how to convert the MSE bounds to risk bounds for classification.
I(X: = EexQ2 [R((X, Z) - 1)²]
(10)
= || x lliis -1
Prompt Bias and Residual Dependence. Here, we con- trol the information-theone our assumptions regarding conditional probability infor- mally and defer the formal descriptions using the language of regular conditional distributions to Appx. C. We work within the latent caption model from Sec. 2, for which we consider joint distribution Px,y, on X x y 2. which equals the evaluation distribution Px,y when marginalized over 2. Similar to the information density R from Sec. 2, we introduce the conditional information density
= 07
(11)
error term in (12). We state
where [l-Ils denotes the Hilbert-Schmidt norm (see Def- inition 7, Appx. B.2), and the identities are proven in Prop. 2. The right-hand side of (10) can also be in- terpreted as the xe-divergence (x=(Qxx21l(xx)) == B=xQ=l( (aQx2, (X, Z)- - 1) between the joint distribu- tion and the product of the marginals (see Definition 8).
3. Generalization Guarantees for ZSP
S. = dPx.Yls d(Px)
xxx x y - R22,
(13)
In this section, we prove generalization guarantees for ZSP methods by comparing 7). to ?p and ?)p to an estimator Ωp. based on an N-sized pre-training set and M-sized prompt set (recall that .M- = m | in (1)). While there are some subtleties in the sampling models between various meth- ods, one can consider (X1, Z1). (NN, Zx) Lid Qx,z itd
where Px,y denotes the conditional distribution of (X, Y) given Z = x, and Px is defined analo-
gously. This naturally motivates the conditional depen- dence measure given by
and (Y1, (i.. (YM, Z'r)) ~ PY.z for intuition pur- poses (see Appx. D.5 for a detailed description). We con- sider specific instances of both the conditional mean and in- formation density approaches, based on learning theory in reproducing kernel Hilbert space (RKHS); our arguments do not intend to interpret foundation modeling method, but to use the detailed analysis of the statistical errors in kernel methods to gain insight. In particular, we aim to expose two key dependences for the random triple (X, Y, Z): the dependence between X and Z (which gov- erns pre-training) and the conditional dependence between X and Y given Z (which governs downstream prediction). Similar statistical guarantees for other function classes (re- viewed in Appx. E) can be plugged into our framework.
T(X; = Exx ())((X)))))3)) -
(14)
called the conditional mean square contingency. Finally, consider the following regularity assumption on the joint distribution Px,y, also discussed in Appx. C.
kernel
Assumption 1. Px.Y.2 on XX Z. satisfies the following:
1) Agreement of caption distribution: Px-almost all xs X. P2| exists and P2 Q2 2) Regularity of con- ditional distributions: For Pz all z E 2, Px,Y|= exists, Px,y|x & Py and the conditional informa- tion density (13) satisfies E (X(() < +oo and Epx.y. (5x(X,Y) Y)] < +00.
To measure the bias of the prompt distribution Pr,z, we
5

---

A Generalization Theory for Zero-Shot Prediction
denote the analog of (5) under Py,z as
Qx,z, under the following assumption.
gPv (z) 2 (z)
Assumption 2. The pre-training distribution satisfies Qx,2 < QxQu, and the information density R is con- tained in (z) (i.e. T(X; 2) is well-defined).
We may now state the main result, proved in Appx. C.
Theorem 1. Under Asm. 1, 11pp - - &
Due to the technical overhead of each method (especially regarding mis-specified function classes), we provide high- level deseriptions below and defer detailed descriptions of the specific estimation procedures and formal assumptions to Appx. D.1 (conditional mean) and Appx. D.2 (informa- tion density). We denote by å E (0, 1] a failure probability, and plog(-) term that is poly- logarithig in its input.
BpZ (1(X; +
119p 1 2 (P))))
(15)
residual dependence
prompt bias
To give context to Thm. 1, conditional independence re- lations have previously been used to describe the perfor- mance of multimodal contrastive SSL for FSL. We are par- ticularly inspired by the multi-view redundancy theory of Tosh et al. (2021), which states informally that the popu- lation FSL predictor can approach the performance of the idealized direct predictor that is given both X and Z at test time, if X T Z and Z T Y|X approximately hold. However, the theory of graphical models (Lauritzen, 1996, Proposition 3.1) asserts that both conditional independence relations hold only if (X, 2) 1 Y. that is, neither view has information predictive of the label. This can be seen intuitively from Fig. by breaking the arrows X + Y and Z + Y. Notice that we compare only to the direct predictor (3) given X (which is reflective of practice), so that we need only that X 1 2| (i.e. X depends on Y through Z) to close the gap. The prompt bias term (15) captures the possible incompatibility of the prompt distri- bution py,z with (Px,y: 2x.2)= we call prompt strategies unbiased (see Appx. D.5) when this term is zero.
Example 1: Nonparametric Regression. This approach, based on (7), uses the pre-training set to produce an es- timate Mz of the conditional mean operator and the prompts to produce an approximation d 2 R of gp. For the former, we use as an example the spectral regularization learning method of Meunier et al. (2024), which produces a conditional mean embedding function F X - G. for an RKHS g of real-valued functions of 2. For any g E G. we then define [M (xx = (g. a.
Note that predicts target that is itself function-such methods are therefore referred to as "vector-valued" re- gression. By the Reisz representation theorem, a similar function F. can be constructed such that [M g] (3r) = (g. (2))). For 9p. we consider standard kernel regular- ized least-squares (e.g.. Smale and Zhou (2007)) applied to M i..dd draws from py,z. Assuming that 9p G. one can then pass the problem to controlling llå 9p Il' and
|| F - F.lli-(ex ( where L (2x)x: denotes a Bochner space (reviewed in Appx. B.4).
Sample Complexity and Distribution Mismatch. The first step in our estimation eтror analysis is to pass the [2(P)) )noom term 1/7p- n f from (12) to the l²(Qx) J-norm counterpart ||Иp 7 [ We then es- tablish high-probability bounds on the L²(Qx) term, with respect to the random sampling of the pre-training and prompting data. Because this initial step follows from a standard distribution shift argument (based on either a additive error
To derive the convergence rates below, we show in Appx. D.1 that the source condition on F. can be ex- pressed in terms of the singular decay exponent of Mzix (i.e. o2 ~ i-7x, from (11)), and the eigendecay expo- nents "x and 7z of the covariance operators of Qx and Qz. respectively. Additionally, Wp > 1/2 is a parameter controlling the convergence rate of the prompt-based based esti- mate of 9p- The parametrization below is chosen so that one may interpret Wp similar source condition for the target function 9p. In the well-specified case (when F, is contained in the hypothesis class), we describe the conver- gence rate with the aggregated exponent
bounded likelihood ratio assumption in total variation distance), we defer it to Appx. D (see Lem. 14). Conceptually, the two examples below are de- rived from estimating the component of either (7) or (8) that involves Qx.z using the pre-training set and the one that involves pv:z using the prompt strategy. In both cases, we discuss the convergence rates of state-of-the-an RKHS- based methods. As we review Appx. B.4, these rates are typically expressed in terms of two quantities: source con- dition constants, which measure the smoothness of the tar- get function being learned, and eigendecay exponents of covariance operators, which measure the effective dimen- sion of the data. It will serve our purposes to interpret the rates in terms of the dependence between X and under
g(t) = (27x,z z + 22 - 1)' 21, (0
where depends on F.. The result below corresponds to Thm. 10 in Appx. D. which relies on a basis alignment assumption to aggregate the singular/cigendecays.
(9., F())) there exist t E (0,1) and C(Qx,z) 2 0 (independent of
Theorem 2 (Informal). For n)(x)) = (g..
6

---

A Generalization Theory for Zero-Shot Prediction
(N, (,)) such that 1| 1pp (xxx x N
rate M-1 reflects that samples are used to learn a joint ex- pectation over pr,z, which is an easier statistical problem than estimating the regression function of Y on Z that ap- pears in Thm. 2. Thus, the information density approach may enjoy faster statistical convergence, at the expense of bias from the distribution mismatch on 2. The con- stant CR, (Qx) relates to the L²(Qx) - of the random function x + ((x))((z Z) for (Y, Z) PY.Z; the error from finite prompts decays when this norm is light-tailed.
plog (1/8)
2(5) TOOTI
+ C(QX,2)M
2up
(16)
with probability at least 1 5 for N sufficiently large.
Let us interpret the constant q(t). First, the dependence on N ranges between O(N- and the parametric rate O(N). Convergence is faster when 7x,7 > or 7i >> 1. The first case implies near-independence of X and Z, for which learning easy as F(x) essentially constant over E X. The second case indicates that the Z variable is near-finite dimensional, or that the vector-valued nature of the problem has been reduced to standard univariate regres- sion. Convergence is slower if 7x > 1, or if the effective dimension of X is small relative to the effective dimension of Z. The balancing constant c(Qx,z) (shown explic- itly in Thm. 10) decays with 7x. and 72. so as (X, Z) becomes more independent Z approaches finite dimen- sions, the variance from prompt sampling decreases. We also discuss the mis-specified case in Appx. D.I.
In both Thm. 2 and Thm. 3. we aim to highlight not particu- lar convergence rates of the chosen methods, but the frame- work that leads to proving them. Similar results can also be leveraged in our framework. SSL procedures such as noise contrastive estimation have been related to the estimation of R (Gutmann and Hyvärinen, 2012). For example, Tosh et al. (2021, Theorem 11) upper bounds ||R - R ([(=((x)2)) using the suboptimality of the population risk, allowing for empirical risk minimization analysis.
4. Experiments
In Sec. 1, we asked how the downstream task performance depends on the pre-training distribution Qx,z. evaluation distribution Px,y, and prompting strategy py,z. At the population level, we captured the dependence on Qx,z and Px, using the residual dependence Epz [I(X; Z)] and incorporated PY,z via the prompt bias (Thm. 1). In the first experiment, we create a simulated setting in which the residual dependence can be controlled and investigate whether it is indeed a determining factor for the empirical performance of CLIP (Radford et al., 2021) and VICReg (Bardes et al., 2022) models in practice. In the second ex- periment, we solve an image classification task in which the images have both captions and labels (i.e., we may sample from true joint distribution Px.y.2). This allows us to un- derstand the effect of prompt bias by comparing template- based prompting strategies to the unbiased setting Pr,z = Pr.z. To understand the dependence on py,z at a sam- ple level, we explore how downstream performance scales with the number of prompts M in both the second exper- iment (unbiased prompting) and third experiment (LLM- based prompting). We are particularly interested in veri- fying the dependence on M (which is the dominant eиror when N >> M) derived in Thm. 3). Appx. F contains fur- ther details of the experiments, and code for reproduction can be found at g thub. www/ com/ronnadm// zeroshot.
Example 2: Radon-Nikodym Derivative Estimation. This approach, based on (8), considers pre-training to re- turn a learned information density R X x Z + Rzo. By approximating the prompt distribution pr,z with yY,z (e.g. the empirical measure in the result below), one may define the estimator (x) = Egy.z [
Z)]. Simi-
lar in spirit to the previous example, we consider the ker- nel Radon- Madoo-Nikodyy derivative estimation with the spectral regularization procedure of Nguyen et al. (2024). The con- vergence rate of R to R is governed by a source condition constant 3 2 associated to (see Appx. D.2). We in- terpret this constant analogously to qt),, in that we prove a relationship to the singular decay exponent 2x but is not directly expressible in terms of the latter. The following result corresponds to Thm. 11 in Appx. D.2.
Theorem 3 (Informal). For ())))) Bay. (r(Y) 2)). and Pz < Qz, there exists CR, (Qx) 2 0 (independent of A,N,M88) such that [| - fhh--nplli (1112=11x)) S
plog (1/8) [N L + (Rx + (pz(11))
with probability at least 1 - for all N sufficiently large.
Notice that the bound of Thm. 3 includes a divergence term between pz (the captions generated by prompting) and Q2 (the captions of the pre-training set). This term comes precisely from the error term in (8). This eluci- dates the fact that the conditional mean approach and the information density are not equivalent representations of the pre- tre-training distribution, as one needs both R and Qz in order to identify the conditional mean. The parametric
Models, Datasets, and Evaluation. For foundation mod- els, we use three publicly available CLIP models from the OpenCLIP repository (Ilharco et al., 2022): ResNet50 pre-trained on YFCC15M (Thomee et al., 2016), NLLB- CLIP pre-trained on a subset of LAION COCO (Visher- atin, 2023), and VIT-B/32 pre-trained on the DataComp
7

---

A Generalization Theory for Zero-Shot Prediction
Sub-Task 1
Sub-Tab Task 2
Sub- Task 3
0.74
Classification Accuracy
Expected (
ResNer50
0.9
0.9
0.8
0.5
0.70
Direct Indirect
0.7
0.7
0.68
CLIP
n.1
NLLB-CLIP
0.5
0.5
01.5
0.00
VICReg
0.0
066
0.5
01.5
0.50
0.75
1.00
0.50
0.75
0
0.4
ViT-B,32
0.9
0.9
Figure 2. Results: Residual Dependence Simulation. Simula- tion for (X, 2, Y) described in Appx. F.4. Left: The y-axis is the accuracy of classifying Y given X and the z-axis is the parameter 0 controlling the residual dependence 1(X; (2) as in (103). Right: The y-axis shows T2 [T;;; 2|2)] as com- puted in Appx. F.4. Error bars indicate standard errors from 10 seeds, which govern the data used for estimating expected values and randomness in the training procodures for CLIP and VICReg.
0.
0.5
0.8
0.7
01.6
25
100
100
10
50
Number of Prompts (Mr) Number Prompts (MT) Number Prompts (M))
Top-1 [Tempbone)
Top-5 (Tempkrtes)
Tap-1 (Pap)
(Par)
Unbiased Prompting. Pre-trained models are varied along the rows and sub-tasks (subsets of 50 ImageNet- Ik classes) are varied along columns. In all plots, the x-axis denotes the number of prompts sampled for each class embedding and the y-axis denotes top-k zero-shot classification accuracy. Error bars indicate standard deviations across 10 seeds for prompt sampling.
Figure 3. Results:
medium pool (Gadre et al., 2023). Our evaluation datasets include five standard benchmarks: the Describable Tex- tures Dataset or DTD (Cimpoi et al., 2014), Flowers 102 (Nilshack and Zisserman, 2008), FGVC Aircraft (Maji et al,,,2011 2013), SUN397 (Xiao et al., 2010), and ImageNet-Ik Ik (Deng et al., 2009). For some experiments, we make use of the ImageNet-Captions dataset (Fang et al., 2023), which pairs a subset of ImageNet images collected from Flickr with their original captions. Evaluation occurs via zero- shot classification top-k accuracy, in which a test exam- ple is considered be classified correctly if the true class is contained within the elements of y with the k largest scores as computed by (1). Evaluation is done using tools from the CLIP Benchmark repository. In Fig. 3 and Fig. 4, "templates" refers to using all default community-curated prompts available in CLIP Benchmark. Finally, detailed descriptions of the prompt sampling schemes are collected and compared to the theory in Appx. D.5.
distributions (Px,z|y=0: Px,z(Y=1): where given Y = y.
x 2
[Xxi]] Cxxix Cx [2ly :
~ N/
Czx
Czz
with class-conditional mean vectors Mxly 22 E Rd and covariance matrices Cxxly; Czx Czz E Rdxd In order to control the conditional dependence between X and Y given Z, we fix all parameters except for fz y and Czxly (for y 0) and define them using a tunable parameter 0 [0. 1] in way such that the conditional distribution of Y given X = stays constant. We make it so that as 0 + 1, (X; Y [=) + 0. Finally, to mea- sure classification accuracy, we directly draw samples from Py.z to simulate unbiased prompting. The full mathemat- ical details are given in Appx. F.4. We observe both of the intended effects; the left panel of Fig. demonstrates that A approaches 1, the indirect, CLIP, and VICReg predictors approach the performance of the direct predic- tor in terms of classification performance. The right panel confirms that indeed controls Ex, [(() in an ap- proximately monotonic fashion.
Classification Accuracy and Residual Dependence. We consider simulated binary classification task in which all distributions are compatible (i.c. Qx.z = Px.z and Pr.z = Py.z for some Px.y.z) and the predictors (3) and (4) can be computed analytically. We also include the zero-shot predictor (I) learned by both the CLIP and VI- CReg objectives. Our goals are two-fold in this simulation: 1) empirically observe that as Ep, [[x;; Y|z)] O, the predictive performance of the indirect predictor T)p does indeed approach that of 1),, and 2) that the predictors gener- ated by common SSL methods used in practice have similar performance trends as 7p- As for the data- gentraagnnaaiggg pro- cess, we consider X = 2. = d and pair of Gaussian
Prompting without Bias with Observations from Pz. Next, we illustrate the importance of the prompt bias term in Thm. by considering an ImageNet-Caption dataset, in which we may observe the joint sample (X, Y, Z). We compare the standard prompting technique using pre- defined templates to the unbiased strategy that draws sam- ples directly from Pr.z We design three sub-tasks by
8

---

A Generalization Theory for Zero-Shot Prediction
Describable Textures
FGVC Aircraft
Flowers 102
SUN397
ImageNet- 1k
0.
0.7
0.5
0.6
ResNe550
0.15
0.4
0.0
0.5
0.5
0.10
0.5
0/2
0.00
0.300
CLIP
0.6
0.005
0.2
0.5
0.4
0.000
0.1
0.025
0.2
0.6
ViT-B/32
0.10
0.5
0.5
0.4
0.1
0.05
0.2
0.3
32
60
20
Number of Prompts (Af)
Number of Prompts (M)
Number of Prompts (Af)
Number of Prompts (M)
Number of Prompts (M)
Top-1 (Templates)
Top-5 (Templates)
Top-1 (CuPL)
Top-5 (CuPL)
Figure 4. Results: Class-oonitiional Prompting. Pre-trained models are varied along the rows and evaluation datasets are varied along columns. In all plots, the araxis denotes the number of prompts sampled for each class embedding and the y-axis denotes top-k zero-shot classification accuracy. Error bars indicate standard deviations across 10 seeds for prompt sampling.
randomly selecting collections of 50 classes from each of 998 classes, reserving held-out prompting examples for which we can draw from PzIY=y for each y E (see the additional details in Appx. F). The zero-shot classi- fication accuracy on held-out evaluation is plotted in Fig. 3. Observe that the threshold at which unbiased prompting outperforms the 18 default templates is approxi- mately M = 10 across tasks. However, the performance of the unbiased approach only saturates at MM = 100 and can have enormous benefits (almost 15% absolute increase in top-1 accuracy for the ResNet50 on Sub-Task 1) in perfor- mance. Thus, for models that have not yet been saturated from pre-training, prompting can close surprisingly wide gaps in zero-shot classification accuracy.
number of classes per task: 47, 100, 102, 397, and 998. Similar phenomena as in Fig. are observed, although the approximate saturation threshold varies per dataset from 20 for Flowers 102 and FGVC Aireraft up to 60 for DTD. Note that the choice of defaults heavily influences the base- line performance. Surprisingly, the Flowers 102 dataset uses a single default: "a photo of and is often able to outperform the class-conditional LLM approach on average. On the other hand, the DTD tem- plates of the form "a photo of a_ {texture, pattern, thing. object]" " are dramatically outperformed by our LLM- generated captions with nearly 20% increase in top-5 accuracy the ResNet50 and ViT-B/32 architectures.
type of flower",
5. Conclusion
Class-Conditional Prompting with Language Models. As mentioned in Sec. 1, we investigate CuPL as means to implement class-conditional prompting (sampling from Pz|Y=y for each y E y) with LLMs. Our experimental setup and scientific goals differ from those used Pratt et al. (2023): 1) we use lightweight encoders that have not saturated their performance during pre- traitraining, as op- posed to the large-scale ViT-L/14 architecture, 2) we quan- tify the variability of classification accuracy with respect to prompting by generating up to fifty times many prompts per experiment, and 3) we employ LlaMA (Llama Team, Meta AI, 2024), which is free and accessible to other, as opposed to GPT-3 (Brown et al., 2020). The results are shown in Fig. 4, where we order the datasets in increasing
We showed how zero-shot prediction (ZSP) can be theo- retically understood as an indirect prediction path from an- other modality to the label. We presented two viewpoints categorizing ZSP methods the conditional mean ap- proach and the information density approach-and framed decomposition formula for their generalization abilities. Our theoretical results and experiments highlighted the role of residual dependence and prompt bias in defining the fun- damental limits of 7.S.. Interesting venues for future work include the extension of our analysis classes of distri- bution shifts between the pre-training distribution and the downstream distribution, and to causal generative model- ing (Scethon et al., 2024; Zhang et al., 2024).
9

---

A Generalization Theory for Zero-Shot Prediction
Impact Statement
R. Balestriero, M. Ibrahim, V. Sobal, A. Morcos, S. Shekhar, T. Goldstein, F. Bordes, A. Bardes, G. Mi- alon, Y. Tian, et al. A cookbook of self-supervised learn- ing. arXiv Technical Report, 2023.
As the capabilities of foundation models become increas- ingly universal, we feel that a comprehensive understand- ing of their underlying mechanisms crucial. Comple- menting the community's 's empirical work on the evaluat- ing the impact of pre-training data and mitigating bias, we aim to spark an equally rigorous line of research that re- thinks theoretical analysis for the purpose of modern learn- ing paradigms that greatly affect humanity.
A. Bardes, J. Ponce, and Y. LeCun. VICReg: Regularization for Self- Supervised Learning. In ICLR, 2022.
K. Barnard, P. Duygulu, D. Forsyth, N. d. Freitas, D. M. Blei, and M. I. Jordan. Matching words and pictures. JMLR, 2003.
Acknowledgements
The authors grateful to D. Hsu, E. Perković, and N. Srebro for fruitful discussions related to this work. The au- thors also thank the reviewers and the area chair for valu- able comments. This work was supported by NSF DMS- 2023166, CCF-2019844, DMS-2134012, NIH, and IARPA 2022-22072200003, Part of this work was performed while R. Mehta and Z. Harchaoui were visiting the Simons Insti- tute for the Theory of Computing.
F. Bartolueci, E. De Vito, L. Rosasco, and S. Vigogna. Understanding neural networks with reproducing kernel Banach spaces, Applied and Computational Harmonic Analysis, 2023. 20233.
F. Bauer, S. Pereverzev, and L. Rosasco. On regularization algorithms in learning theory. Journal of Complexity, 2007.
P. J. Bickel, C. A. Klaassen, P. J. Bickel, Y. Ritov, J. Klaassen, J. A. Wellner, and Y. Ritov. Efficient and Adaptive Estimation for Semiparametric Models. Johns Hopkins University Press Baltimore, 1993.
References
Z. Akata, Z. Harchaoui, and C. Schmid. Label-Embedding for Image Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015.
R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosse- lut, E. Brunskill, et al. On the opportunities and risks of foundation models. arviv Technical Report, 2022.
M. Andrychowicz, M. Denil, S. Gómez, M. W. Hoffman, D. Pfau, T. Schaul, B. Shillingford, and N. de Freitas. Learning to learn by gradient descent by gradient de- scent. In NeurlPS, 2016.
L. Breiman and J. H. Friedman. Estimating optimal trans- formations for multiple regression and correlation. Jour- nal of the American statistical Association, 80(391): 580-598, 1985.
M. Assran, Q. Duval, Misra, P. Bojanowski, P. Vincent, M. Rabbat, Y. LeCun, and N. Ballas, Self-Supervieed Learning from Images with Joint- babedddnb Predic- tive Architecture. In CVPR, 2023.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Ka- plan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sas- try, Askell, S. Agarwal, A. Herbert-Voss, G. Krueger,
Y. Atzmon, F. Kreuk, U. Shalit, and G. Chechik. A causal view of compositional zero-shot recognition. In NeurIPS, 2020.
T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language Models are Few-Shot Learners. In NeurIPS, 2020.
J.-P. Aubin. Applied Functional Analysis. Wiley, 2nd edi- tion, 2000.
F. Bach. Learning Theory from First Principles. The MIT Press, 2024.
A. Buja. Remarks on Functional Canonical Variates, Alter- nating Least Squares Methods and ACE. The Annals of Statistics, 1990.
C. R. Baker. Joint Measures and Cross-Covariance Opera- tors. Transactions of the American Mathematical Soci- ety, 1973.
V. A. Cabannnes, F. Bach, and A. Rudi. Fast Rates for Structured Prediction. In COLT, 2021.
R. Balestriero and Y. LeCun. Contrastive and Non- Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods. In NeurlPS, 2022.
T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A sim- ple framework for contrastive learning of visual repre- sentations. In ICML., 2020.
10

---

A Generalization Theory for Zero-Shot Prediction
Z. Chen, Y. Deng, Y. Li, and Q. Gu. Understanding Trans- ferable Representation Learning and Zero-shot Transfer in CLIP. In ICLR, 2024.
K. Fukumizu, A. Gretton, and F. Bach. Statistical Conver- gence of Kernel CCA. In NeurlPS, 2005.
K. Fukumizu, F. R. Bach, and A. Gretton. Statistical Consistency of Kernel Canonical Correlation Analysis. JMLR, 2007a.
A. Christmann and I. Steinwart. Support vector machines. Springer, 2008.
M. Cimpoi, S. Maji, Kokkinos, S. Mohamed, and A. Vedaldi. Describing Textures in the Wild. In CVPR, 2014.
K. Fukumizu, A. Gretton, X. Sun, and B. Schölkopf. Ker- nel Measures of Conditional Dependence. In NeurIPS, 2007b.
Cucker and X. Zhou. Learning theory: an approx- imation theory viewpoint, volume 24. Cambridge UP. 2007.
S. Y. Gadre, G. Ilharco, A. Fang, Hayase, G. Smyr- nis, I. Nguyen, R. Marten, M. Wortsman, D. Ghosh, J. Zhang, E. Orgad, R. Entezari, G. Daras, S. M. Pratt, V. Ramanujan, Y. Bitton, K. Marathe, S. Muss- mann, R. Vencu, M. Cherti, R. Krishna, P. W. Koh, O. Saukh, A. Ratner, S. Song, H. Hajishirzi, A. Farhadi, Beaumont, S. Oh, A. Dimakis, Jitsev, Y. Carmon, V. Shankar, and L. Schmidt. DataComp: In search of the next generation of multimodal datasets. In NeurlPS, 2023.
J. Deng, W. Dong, R. Socher, Li, K. Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.
R. Verore, R. D. Nowak, R. Parhi, and J. W. Siegel. Weighted variation spaces and approximation by shallow ReLUU networks. Applied and Computational Harmonic Analysis, 2025.
I. Gohberg, S. Goldberg, and M. Kaashoek. Classes of Lin- ear Operators Vol. I. Springer, 1990.
K. Du and Xiang. Low-Rank Approximation of Struc- tural Redundancy for Supe-Supe Learning. In CLeaR, 2024.
Gohberg, S. Goldberg, and M. Kaashock. Basic Classes of Linear Operators Vol. 1. Springer, 2003.
R. Durrett. Probability: Theory and Examples. Cambridge University Press, 2019.
S. Goyal, A. Kumar, S. Garg, Z. Kolter, and A. Raghu- nathan. Finetune like you pretrain: Improved finetuning of zero-shot vision models. In CVPR, 2023.
A. Dytso, M. Cardone, and Zieder. Meta Derivative Iden- tity for the Conditional Expectation. IEEE Transactions on Information Theory, 2023.
Q. Guo, R. Wang, J. Guo, B. Li, K. Song, X. Tan, G. Liu, J. Bian, and Y. Yang. Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers, In ICLR, 2024.
R. Esfandiarpoor, C. Menghini, and S. H. Bach. If CLIP Could Talk: Understanding Vision-Language Model Representations Through Their Preferred Concept De- scriptions. In EMNLP, 2024.
M. U. Gutmann and A. Hyvärinen. mation of Unnormalized Statistical Models, with Appli- cations to Natural Image Statistics. JMLR, 2012.
Esti-
A. Fang, G. Ilharco, M. Wortsman, Y. Wan, V. Shankar, A. Dave, and L. Schmidt. Data determines distributional robustness in contrastive language-image pre-training (CLIP). In ICML, 2023.
J. 7. HaoChen, C. Wei, A. Gaidon, and T. Ma. Prov- able Guarantees for Self- Deep Learning with Spectral Contrastive Loss. In NeurIPS, 2021.
C. Finn, P. Abbeel, and S. Levine. Model-Agnostic Meta- Learning for Fast Adaptation of Deep Networks. In ICML,, 2017.
D. Hendrycks and T. Dietterich. Benchmarking Neural Network Robustness Common Corruptions and Per- turbations. In ICLR, 2019.
S. Fischer and I. Steinwart. Sobolev Norm Learning Rates for Regularized Least-Squares Algorithms. JMLR, 2020.
G. Ilharco, M. Wortsman, R. Wightman, C. Gordon, N. Carlini, R. Taori, A. Dave, V. Shankar, H. Namkoong,
J. Miller, H. Hajishirzi, A. Farhadi, and L. Schmidt. OpenCLIP. GitHub Repository, 2022.
D. A. Forsyth, T. Berg, C. O. Alm, A. Farhadi, J. Hocken- maier, N. Loeff, and G. Wang. Words and pictures: Cat- egories, modifiers, depiction, and iconography. Object categorization: Computer and human vision perspec- tives, 2009.
D. D. Johnson, A. Hanchi, and C. J. Maddison. Con- trastive Learning Can Find An Optimal Basis For Ap- proximately Invarintri Functions. ICLR, 2023.

---

A Generalization Theory for Zero-Shot Prediction
B. T. Kiani, R. Balestriero, Y. Chen, S. Lloyd, and Y. Le- Cun. Joint Embedding Self- SuperSuuee Learning in the Kernel Regime. arXiv Technical Report, 2022.
M.-B. Nilsback and A. Zisserman. Automated Flower Clas- sification over Large Number of Classes. In Indian Conference Computer Vision, Graphics and Image Processing, 2008
Klebanov, I. Schuster, and T. Sullivan. A Rigorous Theory of Conditional Mean Embeddings. SIAM Jour- nal Mathematics Data Science, 2020.
K. Oko, L. Lin, Y. Cai, and S. Mei. A Statistical Theory of Contrastive Pre-training and Multimodal Generative Al. arXiv Technical Report, 2025.
Klebanov, B. Sprungk, and T. Sullivan. The linear con- ditional expectation in Hilbert space. Bernoulli, 2021.
R. Parhi and R. D. Nowak. Banach Space Representer The- orems for Neural Networks and Ridge Splines. JMLR, 2021.
H. O. Lancaster. The Structure of Bivariate Distributions. The Annals of Mathematical Statistics, 1958.
Pinelis and A. I. Sakhanenko. Remarks on Inequalities for Large Deviation Probabilities. Theory of Probability & Its Applications, 1986.
H. Larochelle, D. Erhan, and Y. Bengio. Zero-data Learn- ing of New Tasks. In AAAI, 2008.
S. I.. Lauritzen. Graphical Models. Oxford University Press, 1996.
A. Pokle, J. Tian, Y. Li, and A. Risteski. Contrasting the landscape of contrastive and non-contrastive learning. In AISTATS, 2022.
D. Lee, Q. Lei, Saunshi, J.d Zhuo. Predicting What You Already Know Helps: Provable Self-Supervised Learning. In NeurlPS, 2021.
S. Pratt, Covert, R. Liu, and Farhadi. What does a platypus look like? generating customized prompts for zero-shot image classification. In ICCV, 2023.
A. Li, A. Jabri, A. Joulin, and van der Maaten. Learning Visual N-Grams from Web Data. In ICCV, 2017.
R. Pryzant, D. Iter, J. Li, Y. Lee, C. Zhu, and M. Zeng. Au- tomatic Prompt Optimization with "Gradient Descent" and Beam Search. In EMNLP, 2023.
Y. Li, R. Pogodin, D. J. Sutherland, and A. Gretton. Self- Supervised Learning with Kernel Dependence Maxi- mization. In NeurlPS, 2021.
A. Radford, W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In ICML, 2021.
Z. Li, D. Meunier, M. Mollenhauer, and A. Gretton. To- wards Optimal Sobolev Norm Rates for the Vector- Valued Regularized Least-Squares Algorithm. JMLR, 2024.
B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do Im- ageNet Classifiers Generalize to ImageNet? ICML, 2019.
Llama Team, Meta AI. The Llama Herd of Models. arXiv Technical Report, 2024.
S. Maji, F. Rahtu, J. Kannala, M. Blaschko, and A. Vedaldi. Fine-Grained Visual Classification of Aircraft. arXiv Technical Report, 2013.
A. Rényi. On measures of dependence. Acta Mathematica Academiae Scientiarum Hungarica, 1959.
N. Saunshi, O. Plevrakis, S. Arora, M. Khodak, and
M. Maniparambil, C. Vorster, D. Molloy, N. Murphy, K. McGuinness, and N. E. O'Connor. Enhancing CLIP with GPT-4: Harnessing Visual Descriptions as Prompts. In ICCV, 2023.
Khandeparkar. A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML, 2019.
M. Scetbon and Z. Harchaoui. Harmonic Decompositions of Convolutional Networks. In ICML, 2020.
S. Menon and C. Vondrick. Visual Classification via De- scription from Large Language Models. In ICLR, 2023.
M. Scetbon, J. Jennings, A. Hilmkil, C. Zhang, and C. Ma. fixed-point approach for causal generative modeling. ICML., 2024.
D. Meunier, Z. Shen, M. Mollenhauer, A. Gretton, and Z. Li. Optimal Rates for Vector Valued Spectral Reg- ularization Learning Algorithms. In NeurlPS, 2024.
R. Schilling. Measures, Integrals, and Martingales. Springer, 2nd edition, 2017.
Michaeli, W. Wang, and K. Liveseu. Nonparametric Canonical Correlation Analysis. In 2016,
J. Schmidt-Hieber Rejoinder: Nonparametric regression using deep neural networks with ReLU activation func- tion. The Annals of Statistics, 2020.
D. H. Nguyen, W. Zellinger, and S. Pereverzyev. On Reg- ularized Nikonyyi Differentiation. JMLR, 2024.
12

---

A Generalization Theory for Zero-Shot Prediction
M. Sclar, Y. Choi, Y. Tsvetkov, and A. Suhr. Quantify- ing Language Models' Sensitivity Spurious Features in Prompt Design or: How learned to start worrying about prompt formatting. In ICLR, 2024.
Y. Wang and M. I. Jordan. Desiderata for Representation Learning: A Causal Perspective. JMLRR 2024.
Z. Wen and Y. Li. Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learn- ing. In ICML, 2021.
G. R. Shorack. Probability for Statisticians, volume 951. Springer, 2000.
L. Wu and Long. A spectral-based analysis of the separa- tion between two-layer neural networks and linear meth- ods. JMLR, 2022.
R. Shwartz-Ziv, R. Balestriero, K. Kawaguchi, T. G. J. Rudner, and Y. LeCun. An Information Theory Perspec- tive on Variance-Invariance In NeurlPS, 2023.
Regularization.
J. Xiao, J. Hays, K. A. Ehinger, A. Oliva, and A. Tor- ralba. SUN database: Large-scale scene recognition from abbey to zoo. In CVPR, 2010.
W. Siegel and Xu. Characterization of the Varia- tion Spaces Corresponding to Shallow Neural Networks. Constructive Approximation, 2023.
H. Xu, S. Xie, X. Tan, P.-Y. Huang, R. Howes, V. Sharma, S.-W. Li, G. Ghosh, L. Zettlemoyer, and C. Feichten- hofer. Demystifying CLIP data. In ICLR, 2024.
S. Smale and D.-X. Zhou. Learning Theory Estimates via Integral Operators and Their Approximations. Construc- tive Approximation, 2007.
Y. Yang, A. Panagopoulou, S. Zhou, D. Jin, C. Callison- Burch, and M. Yatskar. Language in bottle: Language model guided concept bottlenecks for interpretable im- age classification. In CVPR, 2023.
Steinwart and Scovel. Mercer's Theorem on General Domains: On the Interaction between Measures, Ker- nels, and RKHSs. Constructive Approximation, 2012.
J. Zbontar, L. Jing, Misra, Y. LeCun, and S. Deny, Bar- low Twins: Supe-vupe Learning via Redundancy Reduction. In ICML, 2021.
Z. Tan, Y. Zhang, J. Yang, and Y. Yuan. Contrastive Learn- ing is Spectral Clustering on Similarity Graph. In ICLR, 2024.
Zhang, Jennings, Hilmkil, N. Pawlowski, C. Zhang, and C. Ma. Towards causal foundation model: on dual- ity between optimal balancing and attention. In ICML, 2024.
B. Thomee, D. A. Shamma, G. Friedland, B. Elizalde, K. Ni, D. Poland, D. Borth, and L.-J. Li. YFCC100M: the New Data in Multimedia Research. Communications of the ACM, 2016.
S. Thrun and L. Pratt. Learning to Learn. Springer, 1998.
C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive learn- ing, multi-view redundancy, and linear models. In ALT, 2021.
M. Unser. Ridges, Neural Networks, and the Radon Trans- form. JMLR, 2023.
A. Visheratin. NLLB- LLBBC-I--- train performant multilingual image retrieval model on budget. In NeurlPS Work- shop: ENLSP-III, 2023.
G. Wahba. Spline models for observational data. SIAM, 1990.
Wang and Isola. Understanding Contrastive Repre- sentation Learning through Alignment and Uniformity on the Hypersphere. In ICML, 2020.
X. Wang, Li, Z. Wang, F. Bai, H. Luo, J. Zhang, N. Jojic. E. Xing, and Z. Hu. PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Op- timization. In ICLR, 2024.
13

---

A Generalization Theory for Zero-Shot Prediction
Appendix
Table of Contents
A Notation
15
B Technical Background
16
B.1 Conditional Expectation and the Hilbert Space L
16
B.2 Compact Operators
18
B.3 The Conditional Mean Operator
20
B.4 Reproducing Kernel Hilbert Spaces
25
C Prompt Bias and Residual Dependence
31
Sample Complexity and Distribution Mismatch
D.I Conditional Mean Approach
35
Information Density Approach
41
D.3 Distribution Shift
46
D.4 From Regression to Classification
47
D.5 Prompting Strategics
49
E
Self-Supervised Objectives Cross Covariance Operators
F Experimental Details
55
F.1
Compute Environment
55
F2
Evaluation Datascts
55
F3 Model Specification and Hyperparameters
56
F4 Derivation of Simulation Setting
57
14

---

A Generalization Theory for Zero-Shot Prediction
A. Notation
Symbol
Description
Instances and sample spaces for data modalities/views, often images, labels, and captions.
x E
a
Encoders a X + Rd and , 2 - Rdd.
(X, Y, %)
Random variable realized in X x y 2.
Px,
Evaluation distribution over X x H.
Qx,7
Pre-training distribution over X 2.
PY,z
Prompting distribution over 2.
function
R.
n. (x)
Direct predictor E Exx,y [r()) (x).
(x(2)
Prediction function E,,,y [+ (z).
(o(x)
Indirect predictor EQx.z [X) (2z).
N
Sample size of pre-training set (X1, Z1), ..., (XN, ZN) iid Qx,z.
M
Number of prompts (Y1, 21) .... (YM, ZM) PY.Z.
Set containing equivalence classes of measurable functions h X lR. satisfying [ = (x²x < +00.
LP(Px)
Conditional mean operator [Mz]x0](== = Exx, [z(2) (ar).
Information density dQx
dQx.2 :X + Rzu-
(xa(P1Q)
x divergeence Eu^q (de (U) 1)²]
T(X;2)
Mean square contingency x (Qx. Q Qz).
(o
Singular values of M
(a;, B1)
Left and right singular functions of M Conditional information density dPx.y|= 4xx X y - R20-
S₂
T(X;Y12)
Conditional mean square contingency 2 x y Xx| Pr Hilbert-Schmidt norm of a linear operator from & to H.
[1-11s((),0)
Table 1. Notation used throughout the main text.
In the appendix, we use slightly more explicit notation. For example, the product measure of Qx and Qz on X x 2, is denoted Qx @ Qz. The bracket notation [xxx and [ are used to indicate equivalence classes in L²((Qx) and (2())). respectively. Such changes are marked as they are introduced.
15

---

A Generalization Theory for Zero-Shot Prediction
B. Technical Background
In this section, we review the necessary background and construct any theoretical tools used our analyses in a self- contained manner. Appx. B.1 describes the broadest function class we consider and gives a rigorous description of the conditional means that we employ in this work. Appx. B.2 reviews the basic classes of linear operators (trace class, Hilbert-Schmidt, etc.) that consider. Appx. B.3 contains central tools regarding the structure of bivariate distributions. Finally, Appx. B.4 contains brief introduction reproducing kernel Hilbert spaces and some recent statistical results used in the proof's of Thm. 2 and Thm. 3.
B.1. Conditional Expectation and the Hilbert Space I
Consider common probability space (2, P) and topological space X equipped with its Borel o-algebra B()). Given random variable X Ω + X representing some observable data, we consider Px to be the law of X, i.c. Px(B) = (B)- for every Borel set B E B(X). Our goal is to define (²)Px), Hilbert space containing equivalence classes of functions that are square integrable under Px- As an intermediate step, we will also construct a Hilbert space L2( for the o-algebra 9 S F, which contains equivalence classes of S-measurable functions that are square integrable under P. Having both of these constructions will be helpful in working with conditional mean operators in a rigorous manner.
Quotient Space. As starting point, consider the set
(P) F- --easuurablee functions u Ω + IR satisfying | = / (2(()dP(w) coo).
<oo
For any u, E L (3), consider the equivalence relation "~"" defined by
+ 321 I such that u(w) v(w) we Ωi and P(L,) 1.
(17)
For any u+ E (3), we define [u+]~ e L2( as indexing the equivalence class containing all functions that differ from 4 only set of P-measure zero. The global Hilbert space will be defined using the quotient of L (F) under this equivalence relation.
Lemma 1. The quotient space (2(3) = L3 (F) ~ is a Hilbert space with the addition and scalar multiplication rules
(u, v) + au + bv == Jau+ + bu+]> for some 44 and u4
for scalars o, b e IR and the inner product
(u, ~> (u, ()3))) == I u+ (w)x+ (w)dP(w) for some u4 E u and u. E E,e,
where the definitions are independent of the choice of 44 and 0+-
Proof. It is easy to verify that the addition, scalar multiplicattin, and inner product operations well-defined (i.e. invariant to the choice of u4 and v4). Define the norm u + || == / (u, ")aarr) and consider Cauchy sequence ) in LF). To confirm completeness, we identify limit of this sequence as element of L2( First, consider an arbitrary sequence w "....... where w( E (n)) for all n 2 1. Then, we have by the Riesz-Fischer theorem (Schilling, 2017, Theorem 13.7), there exists a limit u4 E (3) such that
lim |/ u4 1411 + 0.
(18)
We then define limn- (n)) = [u+] J-n and see that
( [u+]~||<3s) ( u+ 112 - 0 0o,
where the last step follows by (18) and completes the proof.
Next, we construct closed subspaces of (2) which contain random variables that are measurable functions of another
16

---

A Generalization Theory for Zero-Shot Prediction
random variable. Notice that for u, (3), the statement indicates equality of two partitions, namely collections of random variables that differ pairwise on sets of measure zero. Letting a (X) denote the o-algebra generated by X, define the set
(x))) = {u (3) s.t. u meessurbble.
(19)
Then, using the equivalence relation (17), we define the space
(x)o L(xx))))
In the upcoming Cor. 1, we will confirm that (x)) is indeed closed subspace of (3F for any random variable X. Before doing so, consider the induced probability space ((X), Px). Then, define the related linear space
L (Px)
measurable functions f X IR satisfying [Px == ((x)dPx(a) < <00
We define analogous equivalence relation "~x" defined as
f~ 9 3XE E B(X)) such that f(x) g(xx Vo X2 and Px(X2)) 1,
(20)
and the quotient L (2(Px) : (Px)) ~x. These sets related to another in the following lemma.
Corollary 1. The set (X)) is Hilbert space with respect to the inner product used in Lem. 1, whereas L²(Px) Hilbert space with respect to the analogous inner product (I,, (X)), Px). Furthermore, (²()(X)) is a closed subspace of (FF,, and it holds that
) is
L2(o(()) = (2(Px) o = (1+(((()) f+ E Lx
(21)
Proof. That (X)) and (2(Px) are Hilbert spaces follows by identical arguments to Lem. 1. Additionally, we may invoke Schilling (2017, Lemma 27.1) to assert that (x)) is a closed subspace of (2))). Finally, to show (21), we will show that
= LIxx (1 f4 E (Px))
and take the quotient with respect to "~~" on either side to complete the proof. First, (Px) X S L3 (x()) holds because f+ (X) clearly ar (XX) measurablee and
(x)(())))) (F)((())) Px X
/ (1]_aP(()))1[(1[[22 S0.
(22)
To show that (x()) C (Px) o A, first note that for any -eeauurbael random variable U, there exists
measurable function I+ X + I such that U (X) (Durrett, 2019, Exercise 1.3.8). Applying (22) gives
11+ [ig (Px) to0 I1 (x)
+oo, which yields contradiction as [|g+ (X) | ( to0.
Thus, 119+ (Px) < to0, completing the proof.
Conditional Expectation. Using Cor. for any collection of random variables (X, Z,Y, can now construct the Hilbert subspaces L (Px.), (Px)x), (P2).. We can then identify them with conditional expectations, i.c. projections onto (x,, Y)), ((((), respectively. This is done in the definition below.
Definition 3 (Conditional Expectation). For any random variable U E L2()), we define the conditional expectation (X)) as the orthogonal projection of U onto (X))))).. or
[U)o(x))
== arg wEL3(o(X))
arg min ||u - Ull
which uniquely exists due to the closedness of (x)) and the projection theorem (Schilling, 2017, Theorem 26. 26.13).
17

---

A Generalization Theory for Zero-Shot Prediction
Owing Cor. I, will also define the conditional expectation function
[U|X] X
as any measurable function satisfying the conditions [E P-almost every E S2 The specific function choice will not affect any of the forthcoming arguments.
[U|]]]~ (Px)x) and E (X]] = E (X(()) for
Here, defined the conditional expectation as element of (X)) and associated it with function in (Pxxx). Without the qquaredinteerrbbiii requirement, the conditional expectation may also be defined using the familiar tower property. We include the tower property below for completeness.
Lemma 2. (Schilling, 2017, Theorem 27.12) Consider U E (3) and X Ω X. Then, for every measurable set A E o(X). it holds that
/ U()) = / (W)
/
JX(A) E (x)
We will make use of both the projection property and tower property throughout this manuscript. While conditional expec- tation may be defined for specific integrable functions, we may wish to define probability measures whose integrals can produce all conditional expectations simultancously- ideal captured by regular conditional distributions (I.c.d.s) (Shorack, 2000), which we recall below.
Definition Consider random variables (U.V) Ω - x V. Let B(L)) denote the Borel o-algebra on U. A map:
μ: V x ((U) + 00, 1] is called regular conditional distribution (r.c.d.) if the following two properties hold:
1. For each A e B(U) and V, it holds that
p(v, A) = EPoy (M)(
for the conditional expectation defined Definition 3.
2. For Py-almost every V. p(v, -) is probability measure on B(U).
This will primarily be used for the conditional dependence arguments in Appx. C.
B.2. Compact Operators
We collect several generalities about Hilbert spaces and linear operators (hereafter, simply "operators")) between them. Many computations will require expanding an element of separable Hilbert space onto an orthonormal basis.
Definition 5 (Separability, Orthonormal Basis, Complete Orthonormal System). For Hilbert space (H, (,))))))) over R, the orthonormal system c1, ... H. of vectors is called an orthonormal basis (ONB) or complete orthonormal system (CONS) of H if any of the following properties hold, which are equivalent by Schilling (2017, Theorem 26.21).
1. For every h E H. (h, ex) = 0 for all 2 1 implies that h = 0.
2. U span (e1, } is dense in H.
3. For every h E H. it holds that h = Die (h, ei)
4. For every h H, it holds that Eie Kh, ex) 12 11
5. For every h, E H. it holds that E (h, ci) (h', (h',eiin = (h, h')
If there exists a countable orthonormal basis, then H. is called separable (Schilling, 2017, Definition 26.23 & Theorem 26.24).
When linear operators are compact, then we may decompose them in a way that generalizes the eigendecomposition and singular value decomposition for matrices.
18

---

A Generalization Theory for Zero-Shot Prediction
Definition 6 (Compact Operator). A linear operator M
H between Hilbert spaces & and H is called compact if for every totally bounded subset B C G, the image M ()) is relatively compact (i.e. the closure of (BB) is compact) in H.
Compact operators are bounded, and every bounded linear operator M admits a unique adjoint operator M satisfying (h, Mg) (M* g) for all 9 and h E H. An operator T H - H. is called self-adjoint T T Next, we collect two operator decompositions that will be used repeatedly. We refer the reader to Gohberg et al. (2003, Chapter IV) and Gohberg et al. (2003, Chapter X) for further discussion these topics. Just their analogs for matrices, we refer to them as the eigendecompositiinn and singular value decomposition, respectively.
Theorem 4. (Gohberg al., 2003, Chapter IV, Theorem 5.1) Let T H - H be compact, self-adjoint operalor on separable Hilbert space H on E. Then, there exists countable orthonormal basis {ez}jes of H. and sequence of non-zero real numbers {delver with X₂ 0, I S J. and for all h E H. we have that
Th = Σ te
(23)
Furthermore, if (h, Th 2 for all h E H (i.e. T is positive semidefinite), then we may take X; > for all E I, and order them in a mon-onnnnennn iettt-ccreasing sequence.. We call {Ailier the non-zero eigenvalues Tf
Theorem 5. (Gohberg et al., 2003, Chapter X, Theorem 4.2) Let M G - H be compact operator between separable Hilbert spaces 9 and H on R. Then, there exists an orthonormal basis {Wi}}e of H. an orthonormal basis {vk} Jekkee ke of G, and sequence of positive real numbers {sitter with s; + 0 such that the following statements hold.
All collections are most countable, ie. I,J,K S N. and I JNK.
For all g E 9 and h H. we have that
Mg = Σ
s: (elg,wi)gtt Uil and M Σ iEI
si us)
(24)
iEl
We call {silies the non-zero singular values of M, which can be ordered in a non-increasing sequence.
The sets J and K are used to index the bases of H and G, so they may be larger in cardinality than 7, which only indexes the non-zero eigenvalue and singular values, respectively. We will also consider more specific classes of compact operators.
Definition 7. A compact operator M with singular values {s: her (Thm. 5) is called trace class if EiEr 8; +oc (the singular values are summable) and Hilbert-Schmidi if E1er of +00 (the singular values are square summable).
Using the singular value decomposition, we see that if M is Hilbert-Schine Schhmid,, then MM and M M are self-adjoint trace class operators. The set of all Hilbert-Schhice operators M 9 H between Hilbert spaces (9, ( ))) and (H, (x)) will be denoted by HS(G, H). This is itself Hilbert space with the inner product
(A, B) HS(G.. = Σ (Ags. Bog)
JEJ
where (grbze. can be taken be any orthonormal basis of g. Similarly, let (helLek be an arbitrary orthonormal basis of H. Then, the Hilbert-Schmidt norm |A| |A||HS()HH) will be defined as
A l [
(A, A) HS(...)) H)
(Agj, Agi
jEJ
ΣΣΣ Σ
(Ag,, lux (Agss 11) (has 14)
KEJKEKIER
=Σ
(12 Agji = ΣΣ
(A" h4, 9/)9
(25)
JEJKEA
JEJ kek
19

---

A Generalization Theory for Zero-Shot Prediction
Using the singular value decomposition, Definition 7. For h H and g 9, we define the rank-one operator h g : - H via (h & g)g' (g. g gh for all g' G. For an operator A HS(G, H),, the following identity regarding rank-one operators will be useful for norm computations:
that (25) equal the sum of the squared singular values referenced in
(h, Ag) (A = (A, 9) US(G.))) = (A".9 00 h) NS(H..))
Finally, we will often compute Hilbert-Schmidt norms using assumptions on the singular decays of the operator in question. Lemma 3. Let M: g + H be a Hillbrrt-Shhmie operator with singular values {8t) (Thm. 5). Assume that I = N and that there exist constants e, C, > O such that ci? S S Ci
"ii""oo for all i E N. Then, Y > 1/2, and it holds that
2²
27C²
M | HS S
2 -
24 -
Proof. The requirement that 7 > 1/2 follows from the square summability of {8t) and the bound 8, 2 ci For the upper bound, write
1" [x]] 21
1+ { x -=
27
Σ
Σ
dr
s C²
27
1m
For the lower bound, write
8
8
20
i+1
x
2y
dr
2 ²² (
1
-2
6² 27 -
the result desired.
B.3. The Conditional Mean Operator
This section contains key properties of the conditional mean operator Mz and the information density from Sec. 2, based the foundations of Appx. B.1 and Appx. B.2. As we shall show, owing particular Lancaster decomposition (Prop. 2), both operators enjoy convenient spectral representations and relate to measure of dependence- the mean- squared contingency.
Recall the probability space (, P). Consider Borel measurable spaces (X, B())) and (2, B(2)), and a random variable
(X, (): : Ω + X x 2. We denote by Qx.z z the law of (X, 2), i.e. 2x.2(B) ((X, 2) (B)) for every B E B x 2). Note that by Schilling (2017, Corollary 27.24), the Hilbert spaces (²² ) L² ((xxz.), and (² @ Qz) are separable, a fact we will maintain in this section. We use the notation []x and [+]z index equivalence classes in L ((x)
and (Q2),, respectively. In other words, for measurable function h : X -> R, will write [h]x (²(xx) indicate that fx (x))Qxx (x)) < +oo. Recall the conditional mean function introduced in Definition 3. We define the conditional
mean operator
Mzxx
Mz [glz = [Exx [o(Z))
(26)
The specific function g E [ølz chosen for the output conditional expectation is not relevant, as all choices will result in the same equivalence class. We define Mxiz as the analogous operator for the conditional mean of h(X) given for [h]x E (Qxx.
Spectral Representation. In the case that M is compact, the conditional mean operator admits a singular value decomposition, which will be instrumental in obtaining several important properties.
Proposition 1 (Singular Value Decomposition of the Conditional Mean Operator). Let Mz L²(Qz) L²(Qx) be compact. There exists a countable orthonormal basis {aj}yes of LQxx),, countable orthonormal basis (Bx) of L²((z), and a countable sequence of positive real numbers {otheer satisfying o; 0, I S J K, and the following statements in addition:
20

---

A Generalization Theory for Zero-Shot Prediction
We may take 01 1x O1, and 1 E Bo where 1x is identically X and 1 identically 2.
For all [glz E L2()z) and [1]x E L²(Qx), we have that
Mzix(ølz Σ Ea - and Mx|z (a
(27)
01, (1) and that 2 Mxiz (which relates (24) to (27)) to achieve the desired result. For the first, appeal to the variational representation of the first singular value (Gohberg et al., 1990, Section IV.1, Eq. (2)), which states that
Proof. Beyond the direct application of Thm. 5, we must prove the statement regarding (01,
sup ( g (Q2),, (1g7)),l99l11 l1glT = =1}.
(28)
We will show that 31 [1z]z achieves the supremum. Then, it will hold that because any version of the conditional expectation Eqx,2 [1[X] is Qx- -llammost surely equal to 1. Consider any [glz
1 and as Mz = [1x]x.
(Qz) satisfying [[]l)=((()) = Then, we apply Jensen's inequality and the tower property (Lem. 2) to achieve
/ (Bex.z lb(Z) (z))² d2x((x)
Maxxlllzlia
{ B (z) xx)
xx Eqz [g (19l)t>(2)) 1.
Setting 922) [z) = achieves the upper bound, hence also achieving the supremum (28). Next, to prove that M Mx|z. similarly consider [h]x (2xx) and write
(1 M2 Eox [M(X) [x(
Eex. = [N(X)g(2)) (2)
EQz [Bxx.2 [x())2))((2)
(Mxizlb)x 191z 19lz) z2(0)))
which satisfies the adjoint relationship and completes the proof.
Lancaster Decomposition. In the remaining proofs of this section, we do not differentiate an equivalence class in an L'-space with its component functions, the distinction will be clear from context. First, using the orthonormal bases defined in Prop. 1, we may form convenient orthonormal basis of LQ @ Q2).
Lemma 4. The collection (a.,kk (o jEkKeK from Prop. I, where {az]zes countable orthonormal basis of ( and (BakeR is a countable orthonormal basis of (2(2)) forms an orthonormal basis of LQ @ Q2).
Proof. We first show that {ayBa) is an orthonormal system. For any indices i, E and j.j e J, it holds via independence that
(058,,03BB (aj, 0 (a., (e (Be,
{ if = j' and = k'
otherwise
To establish that this orthonormal system now complete, we use the first equivalent condition in Definition Consider E L2(Qx & Qz) such that (s, (5. for all j and k K. Then, via Fubini's theorem (Schilling.
21

---

A Generalization Theory for Zero-Shot Prediction
2017, Corollary 14.9), it holds that
0 S (L s(x, 205 (1)) (e(z)dQz(z)= (0s, (2)
(x)))
(+)
Because {,x kee forms an ONB, it holds that the equivalence class of gj is the zero element in LQ(2), or other words, (,(=) = for Qlmmmmsst all = E Due the fact that countable, we have that
21 = n {= E 2: (z(2)) 03 {= 2: ()))
jEJ
is probability one set under Qz. Because {az} is an ONB of L (Qx). it also holds that
f E 2: (z) = OVj E J - fz s
s(x, x)
for Qx-almost all æ E X},
indicating that the right-hand side is also probability one set under Qz. Then, applying again the iterated integral,
Jnn 2zxxx) @ (z)(2x 2)
/ (// (2 x)Qx (x) dQz(z)
[ 2
(Lr 80, x)(xx()) dQ2(z)
=0,
indicating the s(x, 2) O for (Qx @ Qz)-almost all (æt, E X x 2. This completes the proof.
This basis allows to relate the conditional mean operator particular Radon-Nite Radon-Nikodym derivative. As result, both can be used to measure the dependence between X and Z (Lancaster, 1958).
Proposition 2 (Lancaster Decomposition). Assume that Qx.2 & Qx & Qz, in which case there exists a Radon-Nikodyni dQx.z
derivative R d(Qx0Qz) Then, the following identity holds:
Σ NEI
(29)
In particular, the operator Mz Hilbert-Schmidt if and only ifR E L2(Qx & Q2), with the equality
| (isseeniss) || (R())0))))
of
iEl
Proof. Using Lem. 4, we represent R on the ONB (agB8e) je.Mer For any E J and k K, use the definition of the Radon-Nikodym derivative (Schilling, 2017, Theorem 20.2) to write
(R,0,00))
Eqx 0 |R(X, ()X, (X)3((2)
EQxx (x)
EEx [as(X)EE [3)
= =(ay, Mz x 3k ) LA(Qx)
-o: Sa: ifj=k=iel
otherwise
where we recall as the set indexing the non-zero singular values of Z (see Prop. 1). This proves (29), the first claim.
22

---

A Generalization Theory for Zero-Shot Prediction
For the second claim, we the orthonormality of (aySk)Je in L2 Qz). that
= Σ o
1E1
so that sqmmallsummaillity of (orhee implies finiteness and equality of the left-hand and right-hand sides above.
The formulas in Sec. 2 simply equated / N (1,2....) .... for ease of presentation. For completeness, the Ea term in (9) represents the tail of (29), i.e.,
OC
Ed
which vanishes d + oo because 0 and ag is unit-norm in (2x & Q2).
The Radon-Nikodym derivative R d@x.z is also useful for converting conditional expectation computations into alQx 8Qz)
marginal expectation computations. this sense, we may say that R acts as a kernel for an integral operator representation of M 2 where the integral is taken with respect to Qz. The following identity referenced by Buja (1990, Section 3) and Dytso al. (2023, Lemma Eq. (14)). We provide self-contained proof below.
Lemma 5, Adopt the setting of Prop. 2. Then, for all (Q2)) and h (Qx),, it holds that
Eqx.= [z (a) = 1E (Z) Z)] for Qx-almost all æ E X, _Qx [x(X) Z (z) = Eqx [M(X)((X =)] for Qz-almost all z E 2.
Proof. We prove the first identity, whereas the second follows by symmetric argument. To confirm that the two functions are equal almost surely, it is sufficient to prove that for any measurable set A E (X) (the o-algebra generated by X), the relation
f Exx (z) = Eqz [o(2)R(x, ()))((22))dd)) dQx
(30)
By the definition of conditional expectation, we have that
/ E
/ EQx x (z)
= -Qxx2 (o(Z)1,(X))
EQx (X)RXX Z)].
where the last step follows from the Radon-Nikodym theorem (Schilling, 2017, Theorem 20.2). Next, we compute the expectation, taken under the product measure, using Fubini's theorem (Schilling, 2017, Corollary 14.9). That is,
J. Box (x = E xx (X)(XX
/ ( o(x)R(xx=)d(2(())) dQx(w)
/ Eoz d(2
This achieves (30) and completes the proof.
While Lem. applies for a general function g, the function 9p from (5) is itself a conditional mean. This can be leveraged to produce yet another identity, which acts as a technical lemma for the proof of Thm. 3.
23

---

A Generalization Theory for Zero-Shot Prediction
Lemma 6. Recall that gp(2) Epr. (x) E (Py))) Assume in addition that E (px)). Then,
(z) no(2)= E (r +
dzz(z)).
for Qx almost all X.
Proof. By Lem. 5, we already have that for Q -lmmss all a E X, the identity
(p(x) = oz (Z)R(,, 2)]
= Ep (2p(2) 2]] + -Eq (2)()) Z) Epp (g,(Z)R(z, 2)1
pz (go 2]] { [)(=)) =) (dQz(z) (=)).
Now, unpacking the first term the right-hand side above, we recognize that for fixed æ E the random variable R(x, 2) o oZ mme-maauua,, so via the properties of conditional expectation (Schilling, 2017, Theorem 27.11 (vii)) in L (p2),
may write
pZ 1gp (Z) Z)] = pz pey (Y)))))((( 2)] Ep p [r(Y)R(a Z)
Using the expression above and the tower property of the conditional expectation (Lem. 2), write
Ep (Z) 2)] Ex [Bry. (r(Y)R(z; Epy.z [r(Y) Z)},
completing the proof.
Mean Square Contingency. Both singular value decomposition from Prop. and the Radon-Nikodym derivative from Prop. 2 can be used to calculate dependence measure between X and Z (Buja, 1990). This dependence measure arises in nonlinear canonical correlation analysis and alternating conditional expectations (Breiman and Friedman, 1985; Bickel ct al., 1993).
Definition 8 (Mean Square Contingency). Assume that Mz is filbeet-Schmide Assume that I N (Prop. 1), where we may append zeros if 1 is finite. Recalling that 1, define the mean square contingency I(X; Z) any of the expressions
20
I(X;)) |Maxlissaa 11
Σ of
Our definition of the square contingency is in fact the square of the quantity that originally introduced such by Rényi (1959), which is shown below.
Definition 9. Assume that Qx.z & Qx & Qz. so that R exists, and that E L?(Qx @ Q2). Define the Rényi mean squared contingency Rényi (1959, Eq. (13)) as
Rédy (X; = || [[ V /xx2 (R(x, - -1) d(Qx & Qz)
If Qx,z is absolutely continuous with respect measure (gx, 92), we have that
2, with joint density qx.z and marginal densities
(R(x,z) 1)² gx (x))))g())dd z). Rényii (X;Z)= /
Written in the form above, TRemsi( Xx 2) may also be called the 2-ffunctional (Buja, 1990).
24

---

A Generalization Theory for Zero-Shot Prediction
We apply I(X;2) -Réuyi (X; 2) achieve the sequence of identities following (10). Using the singular decay compu- (X;
tations from Lem. 3 with C 1, we have that if 0; 1 then
(X; +2 11(X;2)+ +1 2 2 +1 S
1 - (X;
(31)
27
27
2 ((x
For simplicity, we will use the upper bounds to describe the order of the quantities, that is,
I(X; + 21(X;
((:
(32)
27
We employ this relation in the sample complexity calculations in Appx. D.
B.4. Reproducing Kernel Hilbert Spaces
In this section, we review facts about the interplay between reproducing kernel Hilbert spaces (RKHSs), the L2-spaces defined in Appx. 1.I, the Hilbert-Schhiie spaces from Appx. B.2, and Bochner spaces (introduced below). The goal is to provide the necessary background in order to understand the results regarding kernel-based estimation methods that are used in other parts of the manuscript. The analyses in Appx. D rely on being able to decompose some target function (related to the dependence between X and Z) so that it may be estimated in multiple ways. One method involves estimating the Nadon-Nikodym derivative R introduced in Prop. 2. The second technique relies on vector-valued regression, with a target function denoted by F.. Most of the setup below
service of the vector-valued regression estimation portion.
We maintain the Borel spaces (X,, (())) and (2, (()) from Appx. B.3, with the topological assumption that X and 2 second countable, locally compact, and Hausdorff. In addition, H and G each denote separable reproducing kernel Hilbert space (RKHS) containing real-valued functions of X and real-valued functions of 2,, respectively. We let Φ X - 7 and </= 2 + G be the canonical feature maps and let k X x X + R and : 2 x 2 - I be the reproducing kernels for H and g. The boundedness assumptions suPæ, eX k(x, I kmax < 00 and = ((z,²)) S /max < Do are maintained throughout the paper.
Bochner Space. We will adopt the equivalence class notation first introduced in Appx. B.1, with respect to probability measures Qx and Qz. That is, for any two real-valued measurable functions f X IR and h X + R, say that f~x if
Qx ((x E X; f(x) + h(x))) 0.
The notation [f]x denotes equivalence class with respect the equivalence relation ~x, with representative f. We say that [[lx E (²2 if
J (xxx))(x(() < xo for some, or equivalently all h E [flx-
We define ~2, H2, and L2(22) similarly. We introduce similar construction to L²( for vector-valued functions, ie., those whose outputs lie in a Hilbert space. For measurable functions F : X + 9 and H : : -> G, we will define the equivalence relation F' ~ via Qx ((æ E ::: F(x) & (x))) = O, and corresponding equivalence classes will be denoted [F]x. We define the Bochner space (Qx:9) via [F]x L²(Qx:9) if
J |1((z)) [dQx oo for some, equivalently all H [F]x.
Analogous lxx this is set of equivalence classes of veluer functions. Recall from Appx. B.2 and Appx. B.3 that we use HS(U, V) denote the space of Hilbert-SShhiit operators mapping from Hilbert space U to another Hilbert space V. The following result allows us to relate elements of the Bochner space l²(Qx; to elements of a space of Hilbert- Schbidt operators US(L)((xx.9)) (Qx).9) For [flx e L2(xx) and g E G, the notation f()) refers to the function mapping a E X to fxx)g E.
25

---

A Generalization Theory for Zero-Shot Prediction
Theorem 6. (Aubin, 2000, Theorem 12.6.1) There exists function & HS(L)(Qx), L²(Qx;9) that is a bijective linear transformation satisfying
[[(x)))))))))) = =10(() for all C (xx))),
eveery
every [fxx (Qx) and g G, associates
(g [flx) [f()gxx = g 1fxx 4 ([f(O))))))
(33)
for the rank-one operator g @ [fxx E (X(L)))
Based on the definition of the Hilbert-Schmine norm in (25) (Appx. B.2, Thm. 6 will make computation of (Qx:) 9)- norms more convenient by relating them to ( The following technical lemma can be used to simplify computations regarding the inverse of this isomorphism.
Lemma' 7. Let (gi) be any countable orthonormal basis g, and les C = x(F((( for some F + G such that [F]x L²(:x: Define the functions (fz)zeJ via ff(æ)) (g), g. Then, [f,]x E [2x for all j E J, and have the identity
C= C= JEJ
91 @ lf,x,
where the convergence is interpreted in terms of ((x)))
Proof. First, consider the case in which we can write the equivalence class of F in L2 () in the form
FF = E1,00,
(34)
JEJ
for some sequence functions JI, J,, E L²² Then, because $-1 is a linear isometry, it is a bounded (hence continuous) operator with respect the norm on 2 (Qx, 9). This implies via continuity
C= C= 4 (E)))
Σ Φ -
EE, lfilx.
jEJ
JEJ
where the last step follows because - satisfies the relation (33). To achieve the identity (34), fix any E X, expand F(x) onto the basis (0z)jes to write
F(x) = Σ
(oj. F(x)) 95-
SEJ
fs(2)
To pass this pointwise equality to (34), consider any sequence of G-valued functions (H2)seJ such that Hy(æ) = f, (x)g, for all Xy X,, where Qx (Xz) 1. Similarly, consider Ho X - such that Ho(æ:) F(x)) for all E Xo with Qx),,) = 1. Thus, we have that
Ho( = EYEJ Hz(2)) for all Xo (Nse) x3)
and because J is countable, this implies that Ho( Ejes (m) for Qx-almost all x: X, granting (34). It remains to be shown that [fixx L²(2x). This follows by the Bochner-square integrability of F, as
J [()))(((=) / (g), d(x)) < 19,118
/ (1(x))((0x())) < <0,
which completes the proof.
In the sequel, we will define statistical learning problem in which the target function F. is an element of L2(Qx::),
26

---

A Generalization Theory for Zero-Shot Prediction
For the kernel-based estimation approach, the estimation function F Fx (where À is to-be-specified regularization parameter) will live in particular vector-valued RKHS that will be isometrically isomorphic HS(H, g) Using Thm. 6, F. will be associated embeddings and interpolation spaces to describe exactly where C, lies in between HS(H, () and HS(L)((Qx) (Qx),9) g) (via source condition).
element C, HS(L)(Qx), 9) via isometric isomorphism. We introduce the concept of
Embedding Operator. See Appx. B.2 for review of the terminology surrounding compact operators. Consider the embedding operator Ix H + l²(xx), ), which identifies a function h E H with its equivalence class [M]x E xQx).. Under the bounded kernel assumption, we have that Ix is compact, and moreover Hilbert-Schmide with norm bounded as [ [| (Qxx)) I Vkmax (Steinwart and Scovel, 2012, Lemma 2.3). We denote its adjoint by Sx = Ix and finally. construct the self-adjoint, trace class operator
Tx IxSx - L(((xx)
(35)
Applying the eigendecomposition Thm. 4, there exists an orthonormal basis of cl(range(Ix)) S [²xxx), denoted ([ex,)x) xee,, and sequence of positive, non-increasing eigenvalues (ux,))er such that
Tx =
px, Ex=Exxx -un. IE!
(36)
Note that we have only used the index set from Thm. as opposed to the larger set for which we can define an ONB for the entirety of (Qxx), not only cl(range(Ix)). Analogous to Tx, , can also define the uncentered covariance operator
Cx SxIx H H.
Similar to (36), Cx enjoys an eigendecompoositinn
Cx = Euzak ex gfx
(37)
The equation above implicitly contains another fact, which is that the equivalence classes in (36) all contain representatives that are in H. This defines the collection the embedding can be described using a singular value decomposition
which forms ONB of null(Ix)* S H. Combining (36) and (37),
Ix = Σ xxx (lex,l2 @ 1/2 (uxfex.))
(38)
iES
Lastly, we define (Iz, Sz, Tz, Cz) as the analogous operators for (²()z) and G.
Interpolation Spaces and the Inclusion Map. For any a 2 0, we define the operator
a/2 (lx.
x
(39)
{ |Ixx E l2((x):
xxx (Ifxxx (Xxx <
dom
12
Σ iel
which is considered to be well-defined when dom dom(To) (T o Ø. Then, we define the a-interpolation space [H]a via
[
Σ RET
0/2 a. an x (ai)er e (2(1)) C C
where (as)ez (T) indicates that EiEr of < +00. When 0, we recover '7000 claanngc whereas for 1, [H]] is isometrically isomorphic to null(Ix) C H (Fischer and Steinwart, 2020). Thus, for a E 1), we interpret [?]] as an "interpolation" between the well-behaved functions the RKHS H and the elements of (Q Associated each
27

---

A Generalization Theory for Zero-Shot Prediction
[H]] is the inclusion map x which simply views element [b]x E [+]] as an element of L (Qx) (this requires the boundedness of the kernel). Here, L (Qx) denotes equivalence classes of real-valued functions on X that have finite essential supremum under Qx We write xx [H] + L (Qx) when the inclusion map is continuous (see Asm. 10),
We use the standard generalization of these notions onto spaces of vector-valued functions (Li et al., 2024; Meunier et al., 2024): for any B 2 0, we define the 3-interpolation norm for C E (Qx)), via the formula
|| == IICT 8/2 (Is(( e +o0]
(40)
This norm, when finite, will used to define the source condition of the target function F, alluded in Sec. 3, as we may compute ||C, for C. := & '([FIxx (see Thm. 6). While we phrase the condition in terms of the constant 3 above in order to relate it to the kernel methods and inverse problem literature below, we will use the constructions of Appx. B.3 to phrase the finiteness of (40) for C, in terms of the mean square contingency (Definition 8) in Appx. D.
Vector- Vector-Valued Valued Spectral Regularization Learning. We may now describe estimation techniques for an L2(Qx:9)- valued target function that fall into the category of vector-valued spectral regularization learning. We give only brief overview in order state the statistical convergence guarantees; see Meunier et al. (2024) for a detailed description, including computational properties of the estimator. As we prove in Lem. 8, there exists a function F, : X + 9 such that [F.]x S L²(Qx; 9) and for every g,
E [ (æ) = F.))))
(41)
For each æ E X, we also refer to F. (x) as the conditional mean embedding of Z given X = æ. Note that for fixed y E G, we do not assume that æ: {g. F.(ar) is an element of an RKHS H. This avoids some of the technical challenges raised, for instance, in Klebanov et al. (2020; 2021), where this requirement places strong implicit restrictions on the chosen kernel and RKHS. Instead, the mis-specified case is handled using vector-valued interpolation spaces.
Next, using Thm. 6, we associate to F. the element C, = (FL) E HS(L'(Qx), distributed pre-training data (X1, 21),.... ...,, (XN, Zn) drawn from Qx,z, z, define the empirical (uncentered) auto-covariance and cross-covariance operator
9). Given independent and identically
N (Z.) ((X)).
1 Čxx N
Σ
(Xx)) 2 d(x)) and Čzx
1
Σ
N
Let fx R20 + Rzo denote the spectral cutoff function
x
if 2 otherwise
[x(x)
(42)
We can interpret (x:) a regularized inverse that behaves in reasonable manner near x 0. A similar function corresponding to the more familiar Tikhonov regularization is fx(x) (a + -)- While other options for fx (i.e. filter functions) exist owing to the tools of regularization theory (Bauer et al., 2007), the spectral cutoff function will be sufficient for our purposes, as it allows for the simplest statement of the upcoming results. For a self-adjoint positive semidefinite operator C, we define (C) as replacing each eigenvalue 14 2 0 of C with fx(4;) in the eigendecomposition (see Thm. 4). For regularization parameter À > we define the estimator
(.) == Cx+(-) for C = C2x(x(xxx: : -
(43)
Now, consider the following assumptions, which include the source condition.
Assumption 10. (Meunier al., 2024, Assumptions (SRC), (MOM), (EVD), (EMB)
1. There exist positive constants 3 > and B such that |F : ||C,|ls S B.
28

---

A Generalization Theory for Zero-Shot Prediction
2. For positive constants o², e 0 the Bernstein moment condition
Æ [2])(2) - F.( (x) s 50l0209-2
is satisfied for Qx-almost all æ E X and all 2 2.
3. There exist constants D > 0 and such that
Ax,i S Di-1/p.
4. For a E (p, 1J. the inclusion map Ix [H]a + L (Qx) is bounded, with operator norm || llop S A.
Note that the first assumption is always satisfied for a = 1, due to boundedness of the kernel (as the [H] norm can be associated to the RKHS norm of an element of H). We pay particular attention to the constant which defines the aforemenntoned source condition. In Appx. D.I, we translate this condition into one regarding the dependence between X and Z, using the tools from Appx. B.3. We refer to the case when 3 as the well-specified case. We also employ one additional assumption to state the result.
Assumption 11 (Sub-Gaussian Tail). There exists a positive constant >> 0 such that the following holds:
Pox [X >1 < 2e 207
Asm. 11 is only used replace statement of the form "for N 2 sufficiently large" from Meunier et al. (2024, Theorem 4) with quantitative condition N. It is used control the probability that (X.)lle for any i 1, 1,..., N for the choices of i specified in the proof of Meunier et al. (2024, Theorem 8).
Theorem 7. (Meunier et al., 2024, Theorem 4) Consider failure probability 5 E (0, 1}, the estimate Fs defined in (43), and the target function F. defined in (41). Under Asm. 10 and Asm. 11, there exists constant C >> 0 (independent of N and 8) such that the following statements hold.
Case 1: 1B a. (JN((((4)))))) 2 2v² plog(N/6)) and O(N ((>)) then
[[[Fax F.) S Cplog(1/8)N zi
with probability at least 1 8/4.
Case 2: B + +tpSS a. If -f 2 2v2 plog(N/6) and
then
|| - F. F.ll S Cplog((10))N//og larhs/oooog/00 (N))
with probability least 5/4.
This result applied in Appx. D.1 and provides an example of the "conditional mean" approach outlined Sec. 2 and Sec. 3. Regarding the setting of À in Thm. 7, the argument follows the typical recipe of defining element Fx L (²x 9) which represents the population version of the regularized predictor. Let ||-I|, denote the 7-interpolation norm y E [0, 1], which is equal to ||=I==((x:)) when 7 0. Then, the approximation error [[[Ax]x - F. decays according 2 when using the spectral cutoff regularizer, which reflects the classical analyses of Smale and Zhou (2007). In the well-specified case, the estimation error, ||. [x]xx [FX]x |by decomposes into multiple terms which include irreducible noise terms of order N ~ and additional approximation terms of order (f-))2 By using À = @(N-*t) and the condition 3 + > a from Case 1, the irreducible noise error converges at rate - whereas the approximation term converges at rate N 9/2((t))) Note that these rates will be squared Thm. 7. The argument for Case 2 follows similarly.
Radon-Nikodym Derivative Estimation. To set the stage for this technique, we describe function class in which
R: X x 2 T2 will live. Let S denote a separable reproducing kernel Hilbert space (RKHS) of real-valued functions
29

---

A Generalization Theory for Zero-Shot Prediction
on X x Z, with canonical feature map yp X x 2. + I and reproducing kernel (Xc x 2) (X x 2) - R. As before, first assume boundedness of the kernel, i.e., sup {n((2, 2, æ², =²) (ar, (ær, 2') E X 2.}
Kmmax.
Let us describe the estimation procedure, which relies on similar spectral regularization technique as the one described dQx.z
for vector-valued regression. Because the Radon-Nikodym derivative being estimated is a(Qx*Q2]' we consider having samples from both distributions available. In particular, we observe Np paired examples (X1, Z....... (Xx,, Zx,) ~ Qx,z and Nu unpaired examples (X1, -.)...., (X',, yx ~ Qx @ Qz. Define the uncentered covariance operators
N. Σ ((X @ p(x)
1 Np
Σ
p pX, O Z.), C. = Nu
(44)
representing the paired and unpaired examples, respectively. Then, using the spectral cutoff function fx (see (42)), define the estimate
R R= R I
(45)
where 1(x, 2) = 1 for all (x) E X 2. Because fx be viewed regularized inverse, R can readily be interpreted as the "ratio" of the covariance operator of the paired sample over that of the unpaired sample.
To state the assumptions for the analysis, we require an analogous operator to Ix and Iz introduced earlier in this section. We then define the embedding operator Ix,z equivalence class in L2 x & Qz). We will not need to define an explicit notation for the equivalence class for this discussion, but will do so in Appx. D.2. Due to Steinwart and Scovel (2012, Lemma 2.3), the bounded kernel assumption implies that I I is Tillert-Schmidt with norm bounded | HSSSSLL (Qxx))
+ L2 x X Qz). which takes an element E and indexes its
VEmax.
Recall the powers of operators introduced in (39). We will use similar construction for this technique well. Define the (compact) adjoint operator Sx.2 = -x [²x @ Q2) + S. Via Thm. 4, let (pt)ser denote the non-zero eigenvalues of the compact, trace class operator Ix,zIx,2. where we consider = N for simplicity. Let the degrees of freedom function be defined as
8
df(A) = Σ
Pi
14 1
Consider the following assumption.
Assumption 12. (Nguyen al., 2024, Eq. (9) and Remark 13) There exists an absolute constant Car and constant such that (2) CarA-1/o, There exists B 2 1, along with element SQx. mmlll[xxx) such that
= (Sx,zIx,22 S
The upper bound on (A) reflects polynomial eigendecay of order b4 ~ i- (see Bach (2024, Section 7.6.6)). Asm. 12 more specific than the one stated in the referenced work, in that we use the specific index function æ + x growing at least linearly. Furthermore, their result may achieve faster convergence rates than the one stated in Cor. using an additional source condition on the feature map p. However, our intention is not necessarily provide convergence rates that are optimal in particular parameter regime, but ones that are informative with regard to the dependence structure of Qx,z. To this end, we do not incorporate the additional condition.
To state the result, we define X, as the solution of
df(A) No,
which is guaranteed to exist as X
dF(X) is decreasing from +oo on the interval (0.+ Observe the following.
Theorem 8. (Nguyen al., 2024, Proposition 10 and Lemma II) Consider a failure probability 8 E (0, 1] and constant
30

---

A Generalization Theory for Zero-Shot Prediction
from Asm. 12. Consider the estimate R = R₂ defined in (45) and the larget function R defined in (2). Finally, define
Kmax == (4
Kmmax) )
There exists a constant C > (independent of N and 5) such that for all X E [dx; Kmax |.
K
R1/2 max
| 1 --|sss= ploo((100)
Kmax 22
(Nr 1/2 + Nr 122)
(46)
with probability at least - 5/2.
By optimizing the bound appearing in (46) in X, we get that
Np 1p2 + Nu 1/2
d+1
A = AN
(47)
K K1/22
the expression from (47) falls within [A,, Kmmax J. this yields the upper bound
R R||s S (loog(1/6)
K
2(341)
d+3
(N/,1/2 +N FFI
(48)
The condition N, S Amax be satisfied by taking (Np; Nu) sufficiently large. For the condition that Ax,..N, 2 A we find upper bound on X, by first deriving upper bound on (A) and then solving the resulting equation in X. By Asm. 12, we have that
df(() S Card
Cat N
a+
= d. S
(49)
Viewing the dependence of (47) on Nu. we see that if B 2 (1 - (2x), then there exists N₂ large enough such that (47) greater than the right-hand side of (49). This always satisfied, as a 1 is required for Sx.zIx,2 to be trace class. Thus, have the following convergence rate.
Corollary 2. Adopt the setting of Thm. 8. Let Nu be large enough such that (47) is upper bounded by Kmmx and lower bounded by the right-hand hand side of (49). Then, for the choice (47), it holds that
R R < plog((1/))
a-2 Kmix
(N= + 1/2
(50)
This result is applied in Appx. D.2 and provides an example of the "information density" approach outlined in Sec. 2 and Sec. 3. In the sequel, we will simply assume that Np N, = N/2 to simplify the statement of the result. Finally, note that the source condition Asm. 12 does have any implications for the mis- specified case (R & S). This aspect of Radon-Nikodym estimation methodology is still an active area of research in statistical learning.
C. Prompt Bias and Residual Dependence
This appendix dedicated to the proof of Thm. 1, which controls the population quantity 1/7,- - 77 m The result will follows from Thm. 9, which a more mathematically precise version of Thm. from the main text.
We recall the problem setting of Sec. 3. We consider the three central probability measures Рx, (evaluation distribution), Qx,z (pre-training distribution), and Py,z (prompt distribution). We notice that 7). (from (3)) depends on Рx,y, while no (from (4)) depends on the pair (Qx.z, PY,z). ). Neither component of this term depends on a joint probability over X y x 2. Thus, in order to relate them on common ground, we consider joint probability measure Px,y,z, which satisfies certain constraints that make it compatible with the distributions that have observable data. We call this the latent caption model.
To proceed, we will need to make several mild regularity conditions on Px,Y.2. We use the notion of regular conditional distribution, or r.c.d. (Definition 4), introduced in Appx. B.1. We use more explicit notation this section (e.g. = 2) as
31

---

A Generalization Theory for Zero-Shot Prediction
compared to Sec. 3 to emphasize the random variable being conditioned on. The assumption below provides more formal description of Asm. from Sec. 3.
Assumption 13. The joint probability Px,Y, on X x y x 2. satisfies the following constraints.
Agrees jointly with the evaluation distribution: For all measurable sets A S X x y, we have that Px,y,2(Ax2)) Px,((A) (i.e. Px, agrees with the given marginal )x,y).
Agrees conditionally with the pre-training distribution: There exists a measurable set X, S X with Px(Xi) such that the regular conditional distributions Qz|x== and Pz|x= =m on 2 exist. Furthermore, these satisfy Qz|x== x for all x E 1.
Regularity of conditional distributions: There exists a measurable set 21 S 2 with P2(Z1) such that the regular conditional distributions Px,yız= on X y exists for all E 21- Furthermore, have the absolute continuity relation Px,y|Z=x < Px z= Priz=z with Radon-Nikodym derivative
S dPx,yIZ=>
(51)
d(Pxiz=x & PrIz=*)
that satisfies Exx [Sx(X, < too for each z E 21 and Exx.v. (Sz(X, < +00.
That Px,y,2 marginalizes to Px,y is more of an axiomatic property than an assumption, but we phrase as so to empha- size that Px,y,z is meant to describe the evaluation distribution. The assumption that the conditionals Q2 and P2|x match almost surely represents the viewpoint that, after fixing an image x, the latent caption Z| follows the same relationship to æ as seen during pre-training. Importantly, this does not require imply that Px Qx that Pz Qz- The marginal distribution Px is supplied entirely by the evaluation distribution Px,y, for any measurable set A C X. we have by definition that (A) Px,y (A x y). On the other hand, the marginal Pz can be defined using the Markov kernel P in that for any measurable B C Z, it holds that
///00/-/-00 Pz(B) = 1xx, P (B)dPx(() = xx (B)
Finally, the absolute continuity condition, i.c., the existence of (51), rules out degeneracies such as Y being a deterministic function of X given Z = z (outside of a set of Pe-muurre zero). It is also worth pointing out that the first two conditions Asm. 13 do not contradict one another. For example, one can consider Px,Y.2 that satisfies the Markov chain Y - X + Z, where (X, Y) is drawn according to Px,y, and and Y are conditionally independent given X. Then, informally, we have that X22 = PzIx Q2ix, so Px,y, zi.zin is uniquely determined. While this example implies the existence of a valid joint probability measure Px,x.2, it is also, in sense, showcasing the "least desirable" distribution for zero-shot prediction, as the dependence between X and Z does not provide any additional information about Y
We recall some notation from Sec. 3. Let
JPv (z) Epy. [r(Y] (z).
Note that JPy.z is simply a conditional expectation constructed via Definition 3, and does not require the existence of an r..dd Priz=z. In the bound, we will encounter a prompt bias term that compares gPr, to 9p from (5). This reflects the notion that if Px,y.z agrees with two of the three fundamental distributions governing the problem, it will not be able to agree with the prompt distribution PY.z in general. Finally, the r.c.d. Zx,y allows us to measure conditional dependence using the conditional mean squared contingency, defined by the formula
I(X;YiZ 2) EEp z-, OPizze [a-- Sz Sx.Y
As is shown in the proof, I(X;Y|2 = xx) and its expectation over Pz are well-defined under Asm. 13. We are now ready to state the result.
32

---

A Generalization Theory for Zero-Shot Prediction
Theorem 9. Assume that is bounded in absolute value by By Under Asm. 13, it holds that Then, it holds that
1| 17, (111)((px)) S 2119p gPv.2 l1P((2)) +2B; Pp [I(X;
(52)
prompt Bias
residiual dependence
Proof. We first establish useful representation the conditional mean of r(Y) given æ, in terms of the (conditional) information density from Lem. 5. Fix æ X1 and Z1, the sets on which the regular conditional distributions Pz x x= and iZ= are defined (see Asm. 13). Because of the existence the Radon-Nikodym derivative S₂ from (51), may apply Lem. 5 with U =Y.V X, and h write
Bxxxiz- [ (x) BPIIZ- (Y)))) for all (z, X1 21.
The chosen notation Exx [ (x) indicates that after fixing the probability measure Px,yıZ=>, we take the conditional expectation of the function E (2 via Definition 3, which does not necessarily posit the existence of the r.c.d. Pyjx==,2== Z=x- We have denoted the right-hand side by the function f(æ, z). Integrate both sides over X then use the tower property of conditional expectation (Lem. 2) to achieve
/ EPxYII= [r(Y]] (2)
77 (x) = Exx,Y [x())
Jz [xx 2)dP2(x==())
EzIxx= [f ()]
(53)
Using the identity (53) and Q2 Pz|X== on x E X1 (Asm. 13), we write
(x) - 1// (xx)
EQzix= [gp(Z)] EpIxx= [f 2)]
EPzx-= [9p(Z)] Ep [f(x, Z)]
X (())(Z) 9Py.z (2)) + Epxix=n (2) (xx,
Taking the integral over Px, we have by the decomposition above that
/ (1p((x) nh (
1/1 - 7/ 11((((()))
$ / (Epz x=o [go(Z] gpy. (2)))² dPx(x)
(54)
/ (EPzixEn [9)r f(x, z)))² dPx(x).
+ [x)
(55)
To handle (54), we apply Jensen's inequality for each r.c.d. Pz|x= to achieve
[ (E (E (()(l)) - (pxx dxx(x) < / EPZIXED (9)(()) - (2)) dPx(x))
= =Epz (g0(2) -9P).2(2))
||gr gpy z 11::(P2)
"This is why we do not write, for instance. PByix=e, Z- [r(Y). This consideration is purely technical, and the reader may make this substitution conceptual understanding the proof.
33

---

A Generalization Theory for Zero-Shot Prediction
remains control (55). Applying Jensen's inequality for each re.dd P2|x== once again, have that
SSp [ f ([(,,)))] 2))]) dPx(x) - Jz1
/ (Eraix=a (2) f(x,, ()) d(x(x))
=Exx2 [(9P)a(Z) (2) f(x,()()2))
=/ 2z ExXIZ-O (9Pv)2 -
x(x. dP2(2))
(56)
where the last step follows due to the existence of the r.c.d. Pxiz=z for 2 E 21, as Px|z==(A)) == Px,r12=2(A1 x 4) for every measurable A S X, and the latter exists by assumption. Using the definition of gpv, write
gPy.z - [(x, 2) P (r()) <=(V,
We may substitute this expression into the integrand of (56) and apply Jensen's incquality to Py z= to achieve
E Exxzz== (x))((x)xxx)))) = Px
(ERviz=s (r()) SY, x))))
Pxxi==
Eprizan
(x))))))
|| E Pxiz==
(1 - (X), [BPri=-e
|| PxI2=x
(1- S=(Y,
where the final step follows by applying Fubini's theorem (Schilling, 2017, Corollary 14.9) to the product measure Pxiz=z @ Priz=z for fixed 2 E 2j. By the definition of mean squared contingency (Definition 8), it holds that
Pr (1- S1 = I(X I
(57)
After confirming that (57) is Pz- Pz-integrable, substituting this expression back into (56) achieves the desired result. Expand the quadratic term and apply the Radon-Nikodym theorem (Schilling, 2017, Theorem 20.1) to achieve
I(X:YIZ 2)
2E Pxiz=x Prizz [S, + 0 [S
-x [1]
+ EXxxriz (Y,
-Exxyiz== [Y, -1.
Thus, by integrating against Pz, we see that
Ep [[X; = Exx.v S2,YXX) - 1,
where the expectation term is finite by Asm. 13. The proof is complete.
D. Sample Complexity and Distribution Mismatch
This appendix provides the proofs of Thm. and Thm. by way of Thm. 10 and Thm. 11, respectively. To recall the bigger picture, we first applied the decomposition (12), which exposed the estimation error term
| nolliP(PX)
(58)
where Px is the X-marginal of the evaluation distribution Px,,, Mp defined by ()(x)) == TX [x) (æ) (see (5)), and i one of two estimation procedures that based on either (7) or (8). By using standard change of measure arguments (collected in Appx. D.3), pass the problem of controlling (58) in high probability to controlling [,, - 7 [ (i.c. the
mean squared error with respect to the pre- pre-training marginal Qx). Thus, the format of both Thm. 10 and Thm. 11 will be
an upper bound on І, - Up 1 ((x)((()))) that holds with an arbitrary failure probability 5 E (0, 1].
34

---

A Generalization Theory for Zero-Shot Prediction
The identities (7) and (8) from Sec. can be summarized with the equality
M = 7p = Bpr. [r(Y)R(: Z)] + err(Qz,, PZ),
(59)
where the err (Qz, p2) is elaborated on in Appx. D.2. Appx. D.I, we consider the left-hand side of (59), and define dpp by constructing an estimate Mz of ZI using pre-training data and 9p of Ip using prompts. This will be referred to as the conditional mean approach. In Appx. D.2, we consider the right-hand side of (59) and define ñi by using an estimate of R using pre-training data and žy,z of pr,z using prompts. This will be referred to as the information density approach. For both approaches, we adopt parallel structure and break the analysis into the following steps.
1. Decomposing the Global Error: We first provide a generic upper bound on the mean squared error
M M n
(60)
in terms of the individual estimators defined by the pre- treiiiin and prompting data. While some additional structure may be employed in these bounds (e.g. the estimate lives in a reproducing kernel Hilbert space), the decomposition is generally agnostic to the choice of method and can accommodate multiple estimation/leaming strategies.
2. Interpreting the Source Condition: The error term related to the pre-training data refers to the distance between the conditional mean operators Mz x and Mz the information densities R and R measured in appropriate sense. This is initially controlled by substituting a particular estimation method among those reviewed in Appx. B. As mentioned in Sec. 3, the convergence rates of these methods rely on source conditions that describe the regularity of the target function. We derive expressions that relate the source conditions to measures of dependence between X and Z, so that, in turn, the rate can also be expressed in terms of these fundamental quantities.
3. Controlling the Prompting Term:
The error term related to the prompting data will have high probability bound, which is stated in the form of an assumption. This generality is maintained because the estimation based on the prompting data usually relies on simple primitives such as real-valued regression or finite-dimensional parameter estimation. Statistically, these problems are easier than the vector-valued regression or Radon-Nikodym derivative estimation problems that arise the pre-training step. Thus, many possible methods can be used, and we provide examples in each case.
4. Completing the Proof: We combine the steps above to state the final bounds on (60). They are stated in Thm. 10 and Thm. 11, respectively.
The steps above comprise the subsections of Appx. D.1 and Appx. D.2 below. The bounds on mean square error on Qx are tied to misclassification risk on Px,y via Appx. D.3 and Appx. D.4 to produce end-to-end performance guarantees. We compare the sampling schemes used for prompting that are employed in the theoretical analysis to the sampling schemes used empirically in Appx. D.5.
D.1. Conditional Mean Approach
This approach is based on the LHS of (59) yielding the result of Thm. 2. The exposition relies heavily on the background introduced in Appx. B.4. In particular, we maintain the reproducing kernel Hilbert spaces H. and g containing real- valued functions on X and Z, respectively. We denote by L2x 9) the Bochner space containing equivalence classes of functions mapping from X to G. We also use the the bracket notation [:]x to index a functions equivalence class in L (or (Qx:: 9) for G-valued functions).
9) which can be used to represent the function æ + [Max99)(<t.. We then describe how an estimator F of F, and an approximation 9, of gp can be used to define an estimated predictor Åp. Recall the boundedness assumptions suxx,,"e k(æ,, x²) kmax < and sup (2,22' S Imx 00.
Setup. We first introduce an element F, of L2x
Lemma 8. It holds that 1) [npxx E L²(Qx). and 2) there exists a function F, X + G such that [F.]x L²(Qx:9) and
[ lo(Z))x] (l)) for all g G.
(61)
35

---

A Generalization Theory for Zero-Shot Prediction
In particular, [nlx Kyp F. gl)
Proof. Using the notation from Appx. B. if we show that the random variable + 9p(((w)) is contained in (9)),, then the first claim holds by the definition of conditional expectation in (Qxx (see Definition 3). Using the reproducing property the RKHS G, we have that
Eoz [o](22) -Ee2 (9 (Z)) - &1lgoll Ezz (22l1122)1 & max 1190113.
(62)
granting the claim that Oolx E L²(Qx). Next, fix any a E Xt and define the map
g (x) = [Mz)xx](x)) = Eqx x [)
By the same argument (62), we have that [g) - Vlmax 11g llg. indicating that Te a bounded linear functional. By the Riesz representation theorem, there exists element of G, denoted as EQx,z [ [Z) [X] (æz), that satisfies
EQx.z [o(Z)] (a) (g. Eex. [v6 (2))) for all g E G.
Next, given the collection of Riesz representers {EExx. [z) (x) E ].. one may construct the mapping
F, X + G, defined by (x E (Z) (x) Eg.
only remains to show that [ E L²(Qxi9). By Jensen's inequality and the tower property (Lem. 2), we have that
J (I((0))))) < BQz (2))2 s Imax < 0o,
completing the proof.
Now that we have identified the vector-valued function of interest, F., we can consider an estimation procedure that will return F = Fs. with [F]x E (2x G) and regularization parameter À > O. Then, we may define the estimator i of nh via the inner product
())))) = (gp- F(x))
(63)
where 9 satisfies some approximation bound with respect to 9p- Our decomposition will expose an error term for which we can apply Thm. 7, which describes the convergence rate of spectral regularization learning.
D.1.1. DECOMPOSING THE GLOBAL ERROR
Returning the original quantity we wish to control from (58), we apply the following decomposition. Lemma (Error Decomposition). For any choice of f E L²(Qx:9) il holds that
Ι, n (1) s 31 | F. F.1l + +3 1lă 1pl6
+ +3 1pl F F.IlA((xx)))
Proof. Using the reproducing property of the RKHS & and Young's 's inequality have that
11 1/ (
/ (()(() dd(xx)))(((((
$3 3 / (gp, ((x))(((())))) - =F. +3 / (f(z). (f( dx (x)
x
+3 (f(x) - F.(xx) d
36

---

A Generalization Theory for Zero-Shot Prediction
Then, applying the Cauchy-Schwaazz inequality in G, we have that
$ <3111113 [ R.( +3 (/IR 11ă, - -
+ +1100 - 90113 x
= =3/وb113 11 - F. (( 3.
1. (( 119p - -9oll
(64)
+ 31 - 3ollē | (2
the result as desired.
In the decomposition of Lem. 9, observe the dominating terms 11
and ( - l läg
along with the higher order term 1l0p gpll || F.1 We consider estimators F and 9p based kernel regularized learning techniques in order to bound the dominating terms, as function of N and M. The bounds are optimized individually with respect to the regularization parameters of each learning objective.
D.1.2. INTERPRETING THE SOURCE CONDITION
To approach this, we associate our function of interest F, E (=((x:9) 9) to an object C. HS(L'((xx,, 9) by way of an isometric isomorphism introduced in Thm. 6. This then allows to derive convenient formula for the quantity || lla. which appears in Asm. 10, and relies on the interplay between H and (²x))) described in Appx. B.4.
Lemma 10. Let (gi)eeJ be any orthonormal basis (ONB) of 9 and recall the eigenfunctions ([ex,)x)ies xieer from (36). Assuming that [F l| is finite, it holds that
|
Nel JEJ
Proof. By the definition of ||-1|s, we have that
Fl = ||C.|l =
II ||C,TT 8/2 HS((P((x).)))
(65)
Then, notice that by the eigendecompposition (36), we have that
[f]x for all [flx (cl(range(Ix)))
Thus, when computing the (65), we may restrict (Qx))) (S(cl(range(Ix)) )): 9). This allows to employ the eigenvectors ([ex,]x)iEr as basis of cl(range(Ix)) when computing the norm. We have that
FF
IIC. 3/2 1/211
HS (iscc()rage((xx))))
ΣΣ (0), "
(by definition)
SET jEJ
ΣΣ Σ
lo C.(ex.lx1@
(by (36))
iET jeJ
ΣΣ
(C.. @ (lxxax))
NET TEJ
-Σ NET JEJ KEJ IEJ
Lo @ Ifulx.9/ @ (exx.lx)nsssrrres)ss) (gi & [fixx, 9, @ @lex.lx)nssu2(q2..00
(Lem. 7)
where fx(x)) (F.(2). =Eex, (z:). Phrased in terms of the conditional mean operator M :
37

---

A Generalization Theory for Zero-Shot Prediction
L2(Qz) (Qx), we have that
[fulx MZxx 19122.
Plugging this into the display above, we have that
1
-ΣEE
/ Mx (at (Mzx(alzz)1) @0 (ex.ll))sstrooeeeapf @ (Mzx(aalz).9) 00 (exx.x))ss
VEI JEJ REJ LEJ
Σ Σ
x (yn, (5)gg( (an, 9i1g (aw.
NEI JEJ KEJ LEJ
(M
(ex,
KEI JEJ
where the last step follows from the fact that 91, I2.... is an ONB of G. This completes the proof.
It remains to select a choice of the collection (gj)jes. Note that (1gglz)jes does not form an orthonormal system in (Q2), due to the distortion of the embedding. However, by explicitly writing the embedding Iz (analogous to Ix introduced in (35)), we can derive one. Consider the singular value decomposition
I2 = Σ P2 (le2,l2 @ (22
(66)
KEK
which is analogous to the one introduced for Ix in (38). The index set K is smaller in cardinality that J, as the collection (ez,))eek forms an ONB of mull(Iz)) C G, whereas (gz)se) should be an ONB for all of G. Thus, we can expand the embedding 19ilz [l) into
[0,12 = I29;
1/2 1/2 Σ
( 12, 9j. 1 (2. Jezzlz-
REK
This decomposition allows us to simplify the equality in Lem. 10 further. Proposition 3. In the setting of Lem. 10, it holds that
|[F 3 ΣΣ
(67)
JEJ
=|T 3/2
M M
1/2
(68)
In particular, [|F110 |F.1B2((
|| I
1/2
1/222
Proof. The sequence of functions (HZ, c2,)kkk form ONB of mull(I2)) 1/2 have that K C J. Then, we may complete (,,,ee7,u)EE to form the basis (gi)ie. of G, where 9j 1 ez,j for all j K and gj is defined arbitrarily for j & K. Plug (g))se. into the right-hand side of the formula given in Lem. 10 gives (67), the first part of the claim.
G. Because J indexes basis of G, we 1/2
For the second equality, we note that ([ex,)x)iEEr and (lezslz)je. form orthonormal bases of cl(range(Ix)) and cl(range(I respectively. We complete them (using the index sets 7 and J) to form (possibly uncountable) orthonomal bases (2x)x) and L ((().. Then, by the definition of the Hilbert-Schmidt norm, it holds that
| 0/2 M x T 1//2 (1
ΣΣ NET JEJ ΣΣ Mewt
8/2 M2 T 1/2 le2zlz (exxxx) x
NE1 jEJ
38

---

A Generalization Theory for Zero-Shot Prediction
where we used in the second line that [ex,)]x null(TX 3/2) gives the (68) and completes the proof.
x for P and [ez,]z mull(T//) for J.J This
remains interpret the equality in Prop. 3 to complete the analysis.
D.1.3. CONTROLLING THE PROMPTING TERM
From the decomposition given in Lem. 9, the estimate 9o will be designed as control the RKHS-norm error Il 8pllå- We phrase the assumption generically, but in a way that is reflective of the convergence rates seen in real-valued nonparametric regression. Recall the probability space (S2, F, P) introduced in Appx. B.
Assumption 14. For constants å E (0, 1], M 2 1, and wp E (1/2, 1], there is an event E(,, M, wp) that is independent of the pre-training data (X1, 71,,................ (XN, ZN). such that on {6, M, Wp)),
2wp 11 9pll S CB,, (1og
2up+1
(69)
for a constant C' independent of 8 and M. On (2, F. P), the event { wp) occurs with probability at least 8/2.
The notation up chosen for the constant that determines the convergence rate, because can interpreted itself as a source condition constant for real-valued nouparametric regression framework. Indeed, consider the case which 9o is computed using kernel ridge regression with parameter A. Via the proof of their Theorem 2, Smale and Zhou (2007) show that with probability at least 1 - 8/2.
19p splls S ((py:2)log((/0))) B,M- +
(70)
estimation
upproximation
where C(py,) is a constant that depends on the prompting measure PY,z and the choice of kemel. Optimizing the bound yields x = Am ~ M-11(20,++)) which ultimately leads to the convergence rate (notice the square) in (69). We comment that the choice to control the error in 9p in G-norm comes from the vector-valued regression framework, in which the output space of the target function always lies in L (Qxx::9 g). In isolation, the mean squared error of 9p can be controlled as well as interpolation norms between L'(pz) and 9 (see Fischer and Steinwart (2020), for
both in L L2( instance). Indeed, when applying the decomposition (70) in L (p2) (p2)-norm, Smale and Zhou (2007, Lemma 3) show that the approximation error decays A (instead of ( In this case, the optimum is achieved at Am M-1/(22,-2) so that llqp (pl) enjoys a convergence rate of M -1)((u++1)
D. 1... COMPLETING THE PROOF
We may now prove Thm. 2. Next, we place the requisite conditions on 3, given eigendecay assumptions on Tx and Tz. and singular decay assumptions on MzІx (see Appx. B.2 for a review of these operator decompositions). Under these assumptions, we will have that all operators will have countably infinite number of non-zero eigenvalues/singular values.
Assumption 15 (Eigendecay and Singular Decay). Let the eigenvalues of Tx, eigenvalues of Tz, and singular values of M be given by { ) (uz,=),=1 and { respectively. There exist positive constants c, C, 7x,, 72. and 7x,7 such that for all i = 1,2, we have the inclusions
xx,a E [ci [x 7C E [a Ci Ci and 0; [ci Txi Ci -i
Assumption 16 (Basis Alignment). There exists a finite index m E N and a permutation क [m]] - [m]] such that the operator Mz admits the singular value decomposition
M
Σ Lageez 2 [ex,il++
Σ
a.lezolz @ [ex,iz..
jmm+l
Asm. 16 allows us to reason about the finiteness of the Hilbert-Schhmid norm | based on the eigendecays of the various operators introduced in Asm. 15. These will imply maximal value of the source
x 3/2 M2 1/2
(Q))
39

---

A Generalization Theory for Zero-Shot Prediction
condition constant B.
Lemma 11. Under Asm. 15 and Asm, 16, it holds that ||F, 1 < +oo if and only if
8 < 21x.2 + 72 -1
(71)
7X
Proof. For ease of presentation, we extend the permutation æ from Asm. 16 so that (1)) = for all i 2 m + 1. Applying the result from Prop. 3, and using the eigenbases of Tx and Tz, we that
F+ 11
|TT
8/2
M
1/2
HS(L'
xx MMzx/ez, ) (x((x)
(Asm. 15)
1
1=
x ([
(2))) (lex,xx, (ex,xx)
Σ S7x 1 x0)
frx 72 72 of
(Asm. 16)
C8
i=m+1
12 o
+
f1x - 72 2xx,2
(Asm. 15)
C
i=m+1
where the rightmost term is finite only if (71) holds. Arguing similarly for the upper bound, we have that
C
|F.113
nxx 12
+C
Σ
1 12 21x.2
3
700
(=m+1
where we may claim that [3 too if (71) holds.
We can now wrap together the results of this section. Recalling the estimator F = Fx based on vector-valued spectral regularization learning, described in Appx. B.4. The well-specified case refers to the condition that 3 2 1, indicating that the RKHS in which F is learned does indeed contain F.. When 3 < 1, we require more sophisticated tools, namely, vector-valued interpolation spaces. In both cases, after establishing the results above, we capture the sample complexity via Thm. from Appx. B.4.
Well-Specified Case. Under Asm. 15 and Asm. 16, this implies via Lem. 11 that
22xx,2 z + 72 -
27x, + 72 -
1 158-
for & 10,
(72)
7x
7x
Thus, we may use the parameter [0, measure the degree to which the upper bound is saturated. This yields the following result, which reflects Thm. from the main text. To state the result, define the quantity
a(t) (27x,z 7z 1)
1-t
(73)
and observe the following, which is an immediate consequence of Lem. 9, Thm. and the formula (72). Note that the constant p in Thm. 7 refers to 1/7x in the notation of this section.
Theorem 10. Consider failure probability 8 (0, 1]. Let Asm. 14, Asm. 15, Asm. 16, and the conditions of Thm. 7 hold |
with | 1/2 /2/M//XX /22112 ( +00. Then, for û defined via (63), there exist constants t E [0, 1) and
40

---

A Generalization Theory for Zero-Shot Prediction
C 0 such that with probability at least 8,
1p m)lle((ex) & (00g(110)) N Wa 20 + 2 2 1 M
2wp
-up-1
for all N 2 plog((N6)) where I1-llss = -llis==llllssaccae 11111000=((22211(0000))
1/2211 2 is equal (via Prop. 3) the || [[=+ll2(((x:))) term from Lem. 9, and is rendered (along with B3 The term ||Mz 1 as the constant x))x,z) in Thm. 2.
Mis-Specified Case. The first inequality of (72) holds only when F. is well-specified, or contained in the vector-valued RKHS used in the estimation procedure that defines (43). We may employ the interpolation space machinery from Appx. B.4 to achieve a convergence guarantee in this setting. Recall the constant a E [1/7x; 1] shown in Asm. 10, which associated to the continuous embedding Ix [H] 4 L (Qx). This constant describes the RKHS itself, and not the specific target function F,. The rate of Thm. 10 may still be achieved for function classes that are "not too mis-specified" in the sense of Case from Thm. 7. The incquality (71) provides sufficient condition for Case 2, that is, when B + 1/7x S a. Indeed,
2xx.z + 72 =a = 8+11/x <
(T)) 2xx,2 + 72 Sa a.
(74)
XX
7X
The left-hand side may also be phrased differently as 27x.2 + 72 S 07x. Thus, we may interpret a'x E rx] as parameter that controls the mis-specification threshold. Concretely, becomes easier for F, to be mis-specified when: 7x,2 is low (X, Z) are highly dependent), 72 is low (the effective dimension of Z is large), or " is high (the effective dimension of the input X is small). Under the sufficient condition (74), along with Asm. 15 and Asm. 16, the best upper bound on the convergence rate in the current mis-specification model (see Thm. 7, Case 2), is then
1| - moli n S plog(1/0)
2x 17z
B²
M T
1/2 Iis
M
TTpTT
2
for sufficiently large.
D.2. Information Density Approach
This approach is based on the RHS of (59) and yields the result of Thm. 3. Here, we assume that during the pre-training phase, the user produces an estimated function R, which is an element of a reproducing kernel Hilbert space (RKHS). Unlike in Appx. D.I, where we approximated gn using a function 9, (which aligns with the conditional mean viewpoint), the information density viewpoint in this section warrants estimating the mean of a function under py,z directly, using samples (Yi, Zz)...., (YM,, Zas) iid ~ pz. It is also important to point out a slight difference in the sampling model for the derivative
pre-training data. In order define the estimate (45) for method of choice (and similar Radon- estimation techniques), it is typically assumed that we observe data from both distributions in the ratio. In the case of Qx,z and Qx @ Q2, this corresponds to observing Np paired examples and N, unpaired examples such that N = NN + N.. For simplicity, we assume that Np = No N/2, but remark that the regime in which No, >>>>>>>>>>>> No is an interesting and practically relevant model for future investigations.
Setup. Let S denote separable reproducing kernel Hilbert space (RKHS) of real-valued functions on X x Z, with canonical feature map o X x 2 + and reproducing kernel K : (X x 2.) x (X x 2.) - R. We will express the error in terms of the RKHS norm difference || -Il among other terms that capture notion of "distribution mismatch" between the prompting marginal pz and the pre-training marginal Qz. This may also be interpreted as another instance of prompt bias. This error occurs because at prompting time, the user does not necessarily have any data drawn from Qz. As
before, we maintain sup {1o(1, x, x', x²) (x. x), (x', zz) E X x 2} S Kmax
Recall that the true R a kernel for the conditional mean operator when integrated under Qz (see Lem. 5), but can also be

---

A Generalization Theory for Zero-Shot Prediction
related via Lem. 6 to the marginal distribution pz:
(a(=)) = E [r())R(z, + (o(=) (dQ2(()) dpz(2)).
This motivates the approximation ž expressed directly in terms of the prompt distribution, and the estimator
(x(x) Exr. (x())((x)))))))))))((((()()()( 2)
(75)
Below, we consider the empirical measure
M
Pv.
1
Σ 2,,
(76)
M
1=1
so that for fixed æ E X, (75) reduces to sample mean.
1.2.1. DECOMPOSING THE GLOBAL ERROR
The estimation error decomposition below will take the two differences into account: between the marginal distributions Q2 and pz and between the joint distribution py,z and PY.Z. For the latter, we will define random variables that take values in Hilbert space (specifically, L²(Qx)) )) This will allow for controlling deviations between ýy,z and pr, directly for the test functions being integrated. Define the independent and identically random variables Wi, W....., WM by
W5 (YY))(( Zz):
and the element of L²) (interpreted the expectation) Exy [Wi]: x Exr. ((x,)) Zi)]-
Lemma 12 (Error Decomposition). Assume the following conditions.
pz & Qz with Qz-square integruble Radon-Nikodym derivative (i.e. x2(oz < +00).
R is contained L²(Qx pz) and L²(Qx Qz).
Then, it holds that
MM no 7 S (M | R + x(22
(77)
+ +3 3े E/ W, - Epr.z [ [
Proof. Using Lem. 6, we have that for Qx- all X,
(x) - (x)))) = Epr. ()()))(( Z) Epy [r(Y) Z)]
+ J (dQQ21)) dpz(z))
= Epr (1))2
( r(y) 2) (dpr. dpy. (3,
+
yxz
+ (o(2))(xx (d) dpz(z))
42

---

A Generalization Theory for Zero-Shot Prediction
Then, have that
li - m s 3Bex ( (Exxxa)000)6xxx22 2), R]]}]
(78)
+3 / ( r(y) (dpr: - dpr.z(u.2)) dQx(x)
(79)
+ / (1 (x) - dQx(x).
2
(80)
To control (78), apply boundedness to achieve
Eex (1 R()²))
B2 max ||
R
For (79), the term is equal to T Σド= - Bpy. [wi [i)ll by definition of Wi,..., WM. For (80), we use that pz < Qz and looo S B, and apply the Cauchy-Schware inequality on L²(Qz) so that
M
( 9p (z(2) 2) (dQ2(z) - ) = (G
(1-
dQz (g2(2)) (x) d((z(z))
dpz
/ (1
(1-
dpz (z) dQz(z).
$ ||||||||[( )ll
dQz
(p22)(22)
Taking the expectation over Qx gives Eex [ ((2))))))
|| (2QxxQ9)) and completes the proof.
Given the decomposition shown in Lem. 12, it remains to bound both the error term || R regarding the estimated Radon-Nikodyn derivative R, and the approximation term 1 to this end. Unlike the arguments Appx. D.I, there is only a single kernel regularized learning algorithm at play, that is, for the estimation of R. We proceed to interpret the source condition Asm. 12.
M E W, - E E,y, [wi]lix We will employ Cor.
D.2.2. INTERPRETING THE SOURCE CONDITION
To proceed, we introduce some notation related to L²(Qx @ Q2) and the RKHS S. These objects are also introduced in Appx. B.4, we review their properties briefly. Let [h]~ index the equivalence class in L² & Qz) for square- integrable function h X x 2 + R. This indexing can also be identified with embedding operator Ix,z S + (2x @ Qz), which is Hilbert-Schmidt under the boundedness of the kernel by Emax Letting Sx,z I xx,2 L² Qz) + S be its adjoint, we have that Ix,2Sx,7 L² Qz) + L²(Qx & Qz) and Z compact, trace class operators. These form the analogs of (Tx, Tz) and (Cx, Cz). respectivvy, from Appx. B.4, Via Thm. 4, we write the eigendecomposition
S S
Ix,2 Eutlleelww
(81)
iET
where we may take each representative as an element of S (Steinwart and Scovel, 2012, Lemma 2.).). Then, we also have that
xx Euc..n D s1) iel
(82)
These constructions (along with Prop. 2) give us the following relationship between the Hilbert-Schmidt norm of the conditional mean operator Mz and the Ridon-Nikodym derivative under the condition Asm. 12. In fact, finiteness follows from the source condition itself and boundedness of the kernel.
43

---

A Generalization Theory for Zero-Shot Prediction
Lemma 13. Under Asm. 12, it holds that
| (Maxxlissuueeaeaaaaroro -IxxA))20x00))
Σ
23+1 Pi
(SQx.z u4
1 2
Proof. Without loss of generality, assume that R E nnll(Ix.2) (as the component in mull(Tx.2) will be excluded from the norm calculation anyway). We expand the expression for appearing in Asm. 12 on an ONB of null(Ix,2) To do so, combine (81) and (82) to introduce the singular value decomposition
Ix, = Σ
p4 (-
1/2 (.
gle
VEl
Then, it holds under Asm. 12 that
R
8 p (S Σ
1/2 es)
sll
e and Ix,2R = Σ
14 8+1/2
1/2 (Sex
ei) Pa)
iE!
sEl
Using that (lei)=)ier
orthonormal system, may the second expression to perform the computation.
To make use of Lem. 13, we now interpret 3 in terms of eigendecay exponents of the operators in question.
Assumption 17 (Eigendecay and Singular Decay), Let the eigenvalues of Ix,2Sx.2 and singular values of M M be given by { and {a respectively. There exist positive constants c, C, a >> 1, and 7x,2 > 1/2 such that for all i 1,2,.... we have the inclusions
A4s $ ot "d"",
c and 0, E [xi-,x.2, 1x
The following relationship holds over an interval in B. We explicitly account for the dependence of SQx.2 on B when comes to satisfying Asm. 12.
Proposition Let Asm. 17 be satisfied. Let Asm. 12 be satisfied for all 0 < B B +oo, where SQx.2 SQx. (3) bounded in S-norm by B for all [0, 3). Then, we have that
(B2 + + -
7x.z 2
B2 +1)
Proof. Write
20
M M2x w
0
28+1
(SQx,z>Hl
M4
1/2
1/2es)3
ee)
|SQx.z
28+1
(SQx,z/I|Sxx..
lls, p4
1/2
< B2
2(8+1/2)
(83)
1=1
The right-hand side is finite, for all > 0, the (n.) sequence is associated to trace class operator. Next, using that 1 8+1/2 < (29+1,-(8+1/2) we use Lem. 3 to upper bound (83) via
C28+1 1)a
239+1
2(+1122)
(23 1)x
(2 + 1)-1a
44

---

A Generalization Theory for Zero-Shot Prediction
On the other hand, using Definition and Lem. the Hilbert-Schmidt norm is lower bounded via
c²
| (Mxxxliisssar(e))x00000)) 2
2xx,z
Combining both bounds, we have
c²
B
2
(23 + 1a-
Inverting the bound gives the condition
7x,7
1
1
+1
B2C
a23 + 1)
(BA + (23 +
=
B² (23 +1)
the result desired.
From Prop. 4, we consider the case in which a oo (the data is finite-rank under independence), and derive the singular decay condition
[BC28T++ +c²
7x,2 2
BºC
>
for O. While the relationship is not direct as in the of (72), may still observe some regimes in which "maximally smooth" target function boils down an independence assumption. This holds intuitively well, in the sense that R = holds (Qx @ Qz )almost surely if and only if X and Z are independent.
D.2.3. CONTROLLING THE PROMPTING TERM
The term that relates ě to pY,z is simply a measurement of the deviation sample mean from its population counter- part, within a Hilbert space. Thus, is reasonable to assume an (1/MM) scaling on this term. Below, we use the notation (X,, 4) indicate sample drawn from Qx Qz, i.e., an unpaired example.
Assumption 18. For constants 8 E (0, 1] and M 2 there is event E(ō, M), which independent of the pre-training N/2
data ((X,, 2 {(X, ))), N/2 such that on { M).
M EE W Epy. [W]] 2 L(((x) I
(84)
where (Qx) depends only on arguments and r, and is independent of M and 5. On (2,F, P), the event E occurs with probability least 1 8/2.
M)
The scaling shown in Asm. 18 be satisfied by placing Bernstein-type condition the random variable W, and inequality (Pinclis and Sakhanenko, 1986). Specifically, consider the case in
applying, for instance, the which there are positive constants a, such that
Σ E 1 W, B,y. (Wlllip(e)) s g! zora- 2
for all q 2 2. Then, (84) is satisfied, wherein the scalars a and e will scale as 1/M, and have additional constants that depend on r, R, py,z, and Qx (but not Qz or Qx,z). This generates the constant (Qx) above.
45

---

A Generalization Theory for Zero-Shot Prediction
D.2.4. COMPLETING THE PROOF
Well-Specified Case. Because Prop. yields an inexact relationship between the singular decay exponent 7x,z and the source condition constant 8, we maintain the statement of the result in terms of this constant. The following result comes immediate consequence of Lem. 12 and Cor. 2.
Theorem 11. Consider failure probability 8 E (0, 1}. Assume that the conditions of Lem. 12 are satisfied and that N large enough such that the conditions of Cor. 2 are satisfied, in addition to Asm. 18. Define
Kmax == (4ramax
Kimax )
Then, with probability at least holds that
M 7o (()))())) & plog(1/6)
K Kmax N di (CR + x (oz
Uia
where CR.p(Qx depends only on its arguments and r, and not M 8.
The constant (Qx) appears directly from Asm. 18.
Mis-Specified Case. As mentioned in Appx. B.4, the mis-specified case (R & S) for Radon-Nikodym derivative estimation problems is less understood than the mis-specified case for real-valued and vector-valued nonparametric regression. We intend here to highlight the overall decomposition of error, for which such results could be plugged in as well.
D.3. Distribution Shift
The results of the previous two subsections provided bounds in high probability on the term І - 77 -o Returning to
the original error decomposition of (12), we would like relate this to similar bound on '| 17p-10 11p 1 We collect two general techniques for performing this change of measure, which lead to either multiplicative or additive error depending on the assumptions the user is willing to make.
Lemma (Distribution Shift), Assume that Px and Qx have densities px and qx with respect to a common dominating measure vx on the measurable space (X, B(X)), and define the total variation metric
TV(Px, (x) 1/8 1xx(x)) ax (x(x)) dxx
Then, for any 1) X R such that (n)x L2(Px) n L2(@x) (see Appx. B.1), the following holds.
the essential supremua [| == relation
==inf inf SupAEB()) suP [n(x)] vx (A9) 0} is finite, then have the additive
Inlla((px) & IIl + linll& TV(Px,Qx).
(85)
IfQx < Px, and dQx aPx (x, 2) S for Px-almost all x E X, then we have the multiplicatiie relation
| S Bpelllliz
(86)
Proof. In the case of (85), we apply Hölder's inequality to achieve
InllE Epx [T](x] Eox [x](X)] /
- (x(x)) dxx(2)
S In 11 / |xx(x) (x))) (xx)
Inlli 11 TV(Px,Qx).
46

---

A Generalization Theory for Zero-Shot Prediction
which proves the first claim. For (86), on the other hand, write
|n (PX)
Ex [x)] -Bex
(x(
dex dPx
(x) S BBelllliie
proving the second claim and completing the proof.
From Lem. 14 and the boundedness assumption |r(-)1 S By, we alter (12) slightly read
1n (px) S 2// 7p (x + 2//7, s +BB, TV(Px,
(87)
and plug in the previous bounds on the - -ol--ell term for overall result.
D.4. From Regression to Classification
Throughout this appendix, we evaluated the quality of an estimated map ?p X -> R via its (2xx) distance some target predictor Vp-- This goal was based on the error decomposition (87), which feeds into ultimate upper bound for μ - 17 [px)) where each term was controlled using the techniques of Appx. C, Appx. D.I, and Appx. D.2. In the case that + IR represents classification structured prediction problem (e.g. r(y) {y = cf for class c 9), it is of clear interest whether the control of mean squared error translates to risk guarantees for classification error. Establishing these guarantees, using the notion of structure encoding loss function (SELF) described in Bach (2024, Section 13.2), is the subject of this section.
Assume that y is discrete, or that ||| < co. We consider a loss function é y + and regular conditional distribution Pyix (+laz) (see Definition 4), under which ((s y) is integrable for all (z. y. The corresponding risk of any map h: X will be denoted
R(h) Ex,x [(())
(88)
There are a number of assumptions that mark the SELF framework.
Assumption 19 (SELF Loss for Structured Prediction). Consider the existence of Hilbert space F, and mappings x: y + F and & y + IF which act as embeddings of objects in y. Then, assume that l satisfies the equality
fly, y (x(3))
As of yet, assumptions (such as being RKHS) have been placed on F. Under Asm. 19, the Bayes optimal predictor (with respect to (88), and not mean squared error) is given by
(x) E arg min
Σ l(y. (yxx()))
y'Ey
yEy
where ties can be broken arbitrarily. In other words, h, argminn R(h). Additionally, because y is finite, we may take the expectation
Σ Ely Pyxp(ll))))))) = Σ (x(1)) DEy
y
(Epx, [x (z),
which is only based on finite sums of vectors F. Next, we define the notation of surrogate loss. To construct predictor (c.g. classifier), we consider function s : X F called the score function and a map dec F - y known as decoder. define the risk
We will then define an integrable surrogate loss L y x F - R. for which
(*) Exxx [LYY, s())]
(89)
47

---

A Generalization Theory for Zero-Shot Prediction
We then define the Bayes surrogate risk
R
Px
inf Byx, [I(Y,))|X] WEF
The relationship between the surrogate risk (89) and the true risk (88) for squared surrogates is given in the following result. Proposition 5. (Bach, 2024, Section 13.4.2) Consider the surrogate loss and decoder given by
((y.s(z)) = (1E(t) =sx)) and dec(h) E arg min (x(x), h)
DEN
Then, for any score function s: X F, holds that
os) - R(h,) s 2 supll RR((s) RR4
yey
We stated Prop. 5 generally; we now map it to classification, the prototypical task associated with zero-shot prediction.
Let y = [l,..., C}2 where C' denotes the number of classes (in contrast to the absolute constants in Thm. 2 and Thm. 3). Then, we have that x(y) is the one-hot encoding in RC, whereas E(y) is the complement, that is, Eg( = - X; (1) for I,...,C.. C. Thus, their inner product generates the 0-1 loss
[ v²) {y + 3¹) = (x()))((v)))))
Then, we immediately have that sup yey yey (x)))((>>>>>>>>>>>>))))) = 1. It remains to determine the score function 8 s X + RC, Note that we used function r to define (3) and (4); we will now use C' such functions y()) ,.).....,, ((0) each defined by
( {ソ( 1
(90)
which in turn gives the individual mean squared error minimizers
n (x) Pyyx x [r (Y) (x) Ppy. [Y [x)
Finally, may any of the estimation strategies developed in Appx. D.I Appx. D.2 produce estimators 16th ..... 1 (i.e. the predicted probability per class) to give the score function
s(x) = (x))
(x)) E RR.
(91)
Each f/c)) is then associated to the conditional mean given by the prompt distribution, which we denote gh As final step, we use the classical relationship between mean squared prediction error and mean squared integrated error, as seen below. Corollary 3. For the score function given in (91) and decoder given in Prop. 5, it holds that
R(dec os) R(hh. s 2 E5 11,
T BaR
Proof. Given Prop. 5, we need only show that
(*) (s) Ri - =
Σ1 110 -n
(92)
/=1
First, note that for the score function s given in (91), it holds by (90) that
T(y,)(x)) = (1) s(m) -
assume the map æ ++ inf Exxxy [ (m)) to be measurable as a technical consideration.
48

---

A Generalization Theory for Zero-Shot Prediction
Epy,e [3(Z)|Y =oat
Unbiased
Unbiased
Bry,z [3(2)|X dog
"ay meswring
Class Conditional
Class Conditional
"st bereord naccs avar me"
drawing of cas"
R."
Template-Based
Template-Basee Based
ofa
dog"
"a phodo a deg"'
Figure 5. Illustration of Prompting Strategies. hypothetical distribution of embeddings ((Z) parametrized by two classes ("eat" and "dog"). Three prompting strategies (emplate-based, class-conditoonal and unbiased) are shown with example text and resulting embeddings Rd. Colors represent the probability of each class given the embedding.
and after taking the expectation over Px,y,
(5) = Exxy s(X)) Σ
Exxy (y) - - (x)))
j=1
Then, by the bias-variance decomposition for each c= 1,..., C, it holds that
C
E Exxx
> 1110 n!
m +
Σ E Exxx [( n))))
(s)
34
Rearranging terms gives (92) and completes the proof.
In particular, when applying the bound above to results Thm. Thm. 2, and Thm. 3, derive bound of the form
R(dec os)- R(hh) / CEP, [TX;Y + 1ll IPY. l(EA(PE) + CTV(Pxx,QX Qx)
2wp Tup
plog (C/8) N 2GC + M
(conditional mean)
plog (C/8) N 2(+ M-1/2) DD>=(pz Qz)
(information density)
which holds with probability at least 5- While generalization bounds for classification and structured prediction can have sharper dependences on the number of examples and number of classes for supervised learning (e.g., via the techniques of Cabannnes et al. (2021) and references therein), the conversion from regression to classification is a remarkably general way to account for the residual dependence, prompt bias, and multiple stages of estimation that mark our problem.
D.5. Prompting Strategies
We have stated upper bounds on the statistical error in this section that depend on the size of the pre-training set N and the number prompts M. To state them more precisely, however, we must also specify the sampling schemes that lead to these examples/prompts. Sampling of the pre-training data falls into fixed and well-understood categories, boiling down to whether only paired examples or a combination of paired and unpaired examples are available. We describe
49

---

A Generalization Theory for Zero-Shot Prediction
these as part of the background (Appx. B.4), alongside the method to which they apply. However, the interpretation of prompting (the empirical procedure used in (1)) formally sampling scheme from a probability measure PY,z is itself contribution of this paper. In the results of Appx. D.I and Appx. D.2, we considered simple random sampling Z.)......... (YM, ZMi) ~ PY,z i..d. to provide examples of scenarios in which Asm. 14 and Asm. 18 can be satisfied. However, multiple practical and idealized strategies exist for prompting (such as the ones explored in Sec. 4). Below, we represent them in our framework below, as ways to define pv,z and approximate it with Pr,2.
This technique reflects the earlier iterations of representing labels in natural language. Examples include "photo of ". "realiistic photo of a ". "drawing of ". etc. Notice that the prompt templates have relationship with the class label. One way this can be understood is by representing the caption via the structural equation Z f(Y, U). where U represents the text of the caption with the label left blank (drawn according to probability measure pt)), and f represents the action of inserting the natural language label. Then, we have that under the template-basee prompting distribution, U 1 Y. This does not imply that Z + Y, but instead that the dependence is governed fully by the function f- To sample, a fixed number of m examples ui,.... Um are drawn directly from Pu. We then use the empirical measure Py, (y. 2) = 1 uniform distribution on the discrete set y. Here, M- = m [
Template-Based:
m -E= (U) {f us) = 2), where py is fixed as the
Class Conditional: This technique reflects the modern LLM-based techniques, such CuPL (Pratt et al., 2023), We parameterize the joint distribution using the conditional distributions Pr,z Eyey P (r( for each class y E y. Sampling from each Pz|Y=y occurs by meta-prompting the LLM (such as the one we use in Appx. F), which generates samples z ........ z and empirical measures ŪZ|Y= Py,z= Evey PZ|Y=y py (y), with M m [9).
> k==1 dzg. Our final approximation is
This techniques reflects the setting of Fig. 3, where the user may drawn samples from a joint distribution Px,y,2, where the marginal Px,y is in fact the data on which the zero-shot classifier will be evaluated. Then, the prompt distribution can be constructed, as we do, by drawing samples (y1, = =1),.... (y #M) directly from Pr,z, and defining ~v,2= = M ΣØ= (())) We call this "unbiased", because the prompt bias term in Thm. is zero for this example. is worth pointing out that even if Py|z=z can be matched by the prompt distribution, the distribution mismatch term from Thm. 3 will be zero if and only if pz = Qz (or the prompt captions match the pre-training captions in distribution). In this sense, Py,z may not be the ideal prompting distribution, but instead, PrizQz.
Unbiased:
1
E. Self-Supervised Objectives and Cross Covariance Operators
In Sec. 3, we considered specific instances of both the conditional mean and information density approaches based on nonparametric regression in reproducing kernel Hilbert space (RKHS). This reflected the statistical goals of Thm. 2 and T.m. In this appendix, we aim to draw relationships with other approaches based on optimizing self-supervised learning (SSL) objectives, in order to align with practice. In particular, we focus on the relationship between such objectives and the mean square contingency I [X;; Z) introduced in Sec. 2. To do so, we make explicit the intuition that SSL objectives (such CLIP and VICReg) are implicit forms of dependence maximization between the representations ax (x) and (Z)). Some of the arguments below have previously appeared in the literature- do not claim originality for them, but instead aim to consolidate them together in single vignette.
When it comes to specific SSL objectives, we describe here their properties as functions acting on a batch of encoded data (==))),,((1))). ((21), (ax.),,,(z..). This abstract description is agnostic to the function class used for the encoder. Reproducing kernel Hilbert space theory has been frequently used, in the recent literature, to define the function classes involved in contrastive and non-contrastive self-supervised foundation modeling (Li et al., 2021: Balestriero and LeCun, 2022; Kiani al., 2022; Johnson et al., 2023; Tan et al., 2024). We also mention that the precise characterization of the function classes of various deep neural networks is an active area of research Scchmidt-Hieber, 2020; Scetbon and Harchaoui, 2020; Parhi and Nowak, 2021; Wu and Long, 2022; Bartolucci et al., 2023; Unser, 2023; Siegel and Xu, 2023; Shwartz-Ziv et al., 2023; De et al., 2025). However, these exciting yet still burgeoning theories of deep neural networks have not yet reached a maturity level comparable to the one of RKHS theory (Wahba, 1990; Cucker and Zhou, 2007: Christmann and Steinwart, 2008; Bach, 2024) needed for the thcoretical analysis we develop in this paper. For more practical details on self-supervised learning, we point the reader to the recent survey (Balestriero et al., 2023).
50

---

A Generalization Theory for Zero-Shot Prediction
Covariance Operators. To relate theory (which centers around the mean square contingency measure of dependence) SSL. objectives, we first draw the relationship covariance operators of Qx,z on particular function spaces. Let H be an RKHS of real-valued functions X and G be RKHS of real-valued functions on 2. Then, define the cross-covariance operator Cxz: G - H by
(h, Cxz9)x = Covox, ( (h(X),
and the analogously defined auto-covariance operators Cxx: H - H and Czz G G. When Cxx and Czz are compact, we define the powers C//2 and C in the sense (39). It then holds by Baker (1973, Theorem 1) that there exists unique bounded linear operator Vx x G H. that
Cxz C VX2
(93)
The operator Vxz is called the normalized cross-cvaariace operator, or NOCCO for short (Fukumizu et al., 2005). As 1/2
an abuse of notation, the NOCCO (93) sometimes communicated Vx2 Cx Cx2C2z 11/2
though is uniquely defined without necessarily constructing the square-root inverses. To rigorously use the formula xx C CxzCzz with well-defined adjoint, we must make assumptions on the closure of the range of Cxz and Czx being contained within the closure of the range of Cxx and Czz, respectively. The Hilbert-Schmidt norm of the population NOCCO, when finite, is equal to the mean square contingency
V x | (i = I(X;)).
(94)
as shown in Fukumizu et al. (2007b, Theorem 4). The relation (94) requires a few additional technical conditions, such as x @ Q2) and Qx.z having joint and marginal densities
(H. @ G) + E being dense in L2(Qx
Variational Characterization of the Hilbert-Schmidt Norm. This operator is an essential component of the kernel canonical correlations analysis (CCA) problem, which (with (94)) will be the common bridge that ties together SSL and the mean square contingency. From the nonparametric CCA perspective, the singular values (o,) refer precisely to the canonical correlations and the singular functions ((a;, 8:)) refer to the canonical variates (Lancaster, 1958; Buja, 1990; Michaeli et al., 2016). Returning to (94), this operator is estimated with a regularization scheme, i.e.
vx.z = (Čxx + AL) -1/2 1ACx AI)
where Čxx, Čxz, and Čzz are the standard empirical covariance estimates (see Appx. B.4) and À >> is regularization parameter. Then, one solves the empirical CCA problem
max A Ea H o.b.b 91 g9
(hi, V Vx,29)
(95)
1=1
where o.n.b denotes an orthonormal basis. Setting aside matters of estimation, we consider how the norm quantity
|[V x | R) relates to the actual encoders returned by the CCA problem (95) (assuming that V Xx R V V. Let
(s be ordered singular values of the Hilbert-Schmidt operator V x,z In this case, denoting hy,..., ha E H. and
'Recall that definition of T(X: does not include the square root that is usually used in the definition of mean square contin- gency.
51

---

A Generalization Theory for Zero-Shot Prediction
:1....:9 Da the orthonormal bases of H. and & resp. maximizing the criterion ((95)), we have
d
Vx,291 = (hs.
8
(96)
|V
i=d+1
06
d( (1(x:2)
(97)
The two orthonormal bases maximizing the criterion (95) actually the left and right singular functions of Vxy sociated the leading d singular values (see Thm. 5). The larger the truncation level d, the closer the quantity is to the mean-square contingency, up to the truncation level factor d.
In either the population (96) or empirical (95) problems, the functions are maximizing an objective that is measure of covariance with a constraint on variance. The constraint on variance is imposed by the norm condition on h,,..., ha E H and 91..... 9d E G, respectively); see (Fukumizu et al., 2007a). This norm condition relaxed into a penalization term in popular SSL objectives.
Indeed, several SSL objectives be written in analogous variance-reullarized covariance form. This may offer one intuitive viewpoint to why estimators based these objectives might exhibit similar statistical properties to those analyzed in Sec. 3. We first describe format for these variance-reeullarized covariance objectives and show that a number of popular SSL objectives can be expressed in this form.
Variance-Regulariize Regularized Covariance Objectives. Recall that a X Rd and B 2 - Rd denote encoders for X- valued and v-lulued objects (often images and text, respectively). We denote the standard Euclidean inner product by (u, v) Σド= Uj in Rd. In either case, consider a batch of data points (x1, ...,.... (En, zn) which thought to be n independent and identically distributed realizations of (X, Z) from the probability distribution Qx, over X. Z. Let us then define the design matrices induced by the embeddings, written as
(x))) -
3(21) -
A =
E R and B ==
E Rund
a<x,,)
B(zz)
Let J : I - 111 E Raxx be the centering matrix and construct the empirical auto-covariance and cross-covariance matrices
ΣA (JA), ΣBB = (JB) (JB), and ΣAB (AA)T(JB)
We aim to write the upcoming objectives in the form
((a,3)=-1 - Tr (DAB) + EABIE (()
for hyperparameter x 2 0. matrix ΣAB (which ΣAR with its diagonal components set to zero), and variance-
regularization term V(a, 33. The term V(a, () may explicitly include the regularized inverses of Σ Exx and Σzz, or may penalize variance or non-smoothness more implicitly.
52

---

A Generalization Theory for Zero-Shot Prediction
Multimodal InfoNCE (CLIP). Consider the empirical objective for the contrastive language-image pre- training (CLIP) model (Radford et al., 2021) with batch size n.
Example 1:
(c 9) = (a(x)),((z)) + log (ole.) log (a(2)) + log nt,
2
where the log factor is appended to normalize the sums in the logarithmic terms and does not change the minimizer. Following arguments used (e.g. by Li et al. (2021)) for the SimCLR objective- the single-modality counterpart to CLIP- we analyze the logarithmic terms via Tayler expansion. To simplify the analysis, take the large-sample limit to define the population objective
(cLir(aff) = -Ep(a(X),,((2)
+ Erx [oo Ep Ep [ x]] + Bry [log E. [ela(X).0(2)) z]]
(98)
Next, define the quantity d(x) = Exx2 X, the approximation
(x) and apply a second-order Taylor expansion for every (1+
((())) (00)))((((0)
= c(w)
- d(x) + ((a(z),8())) -c(x))))
Plugging this approximation into the first term (98) yields
log Ep ela(X)
x
(x) = c(x) log (1 + 1 Var ((a(z),8(Z))( (x))
Using the Taylor expansion log(1 y) y + oly) centered at y 0, and evaluate the first-order approximation
y Var (())) (a=), we finally have that
Bpx [oog Ep, (((())) x
Er
Erx ((a(((()))
2
Applying an identical argument the second term of (98) gives
(alir(a, 9) (3)= (Er(a(X)) (Erx [a(X)) Er, (B()))))
Epx (aa ((((X), Er War (o(X),
Tr (C))()( + Bpxx [Var ((a(X), B(2)) X)] + E [Var (((()))))(1))
which is the desired form for the population. Now, to rewrite the empirical version, we have
( - (AA + IN
Vary ((a(X),(12))x) (z.) IN Σ Vary (la(x), (z),,
variance regularization
where Vary denotes the variance with respect to the empirical measure + Ei= 8(
Example 2: BarlowTwins. The Barlow Twins objective (Zbontar et al., 2021) has already been interpreted as instance of kernel canonical correlations analysis (CCA) by previous work (c.g. by Balestriero and LeCun (2022)). This objective usually defined in terms the cross-correlation and auto-correlation matrices. To be consistent with other objectives in this section, we handle this by enforcing a constraint on the variance. Let is Rdxd + {0, +oo denote the convex analytic indicator function such that i (E) Σ E S and equals +00 otherwise. Let I be the identity matrix in ddd
53

---

A Generalization Theory for Zero-Shot Prediction
Given hyperparameter K. > O, the objective can be written
(a 3=: Σ
(SAn)ss - + x|| AnIEBBl + (Ens) + un) (Enn)
d = - TT((Ann)++ + A +
Σ m An An), + 4 (()((a)) + quy (Ean).
covariance
variance regularization
Thus, this objective falls into the class as well, as the penalties enforce a particular variance structure akin to the regularizers above.
Example 3: Spectral Contrastive Loss. Finally, we consider the spectral contrastive loss from the pioneering work of HaoChen et al. (2021). This relates to similar viewpoints of contrastive learning spectral methods found in the literature, such as the Laplacian eigenmap viewpoint of VICReg (Balestriero and LeCun, 2022, Section 3), the multidimensional scaling viewpoint of InfoNCE (Balestriero and LeCun, 2022, Section 4), or the recent spectral clustering viewpoint of SimCLR/CLIP (Tan et al., 2024, Sections 3 and 4). Recall that == 1 Σ a(x,) and β = E. ((z)). In the multimodal setting, this loss (HaoChen et al., 2021, Eq. (6)) be written
n
Bsc(a,3):= -
1
Σ
(a(z;),B(zz) + n(n Σ (la(z,), its
==1
1
(a(x:) -a B(z)) - 33 - (3.
11
Σ
((a(x;; - a, B))² + ((a,3))²
+ n(n 1)
i
--Tr(EuB) + |AB 1| - (a, + ((a, B))
-Tr(EAn) +
E An F
(o. (a. 2 4
cuvariance
regularization
where we set K := 1/(n 1) to complete the argument.
Example Multimodal VICReg. We use a variant of the VICReg objective shown in Shwartz-Ziv et (2023, Equation 1). Note that this method is typically designed for one encoder being applied two augmentations of the same object; however, it naturally generalizes to the multimodal case. The similarity graph simply connects paired observations, leading to the invariance term below. The multimodal VICReg objective has hyperparameters (c1, C22 C3, k).. To state it, define the real-valued function r(x) max (0, Vx 02) } for x E R. We will also apply to matrix, which returns the matrix of clement-wise applications of the function. The objective is written
LVTOReg (a,
C3
Tr (f(EAA)) Tr (r(EBB)
A B
2d
covariance
variance
While usually thought of as capturing a separate property, we will incorporate the invariance term into the other two terms, which crucially relies on having an extra degree of freedom via the second encoder (as opposed to the single-modality
54

---

A Generalization Theory for Zero-Shot Prediction
setting). Define
1 n
Σ (xx))) and B 1 Σi= B(2,), then write
1 2n
A
B
(a(x))) B(2:)11
71
1
[a((x)) - a B(zi) + 311 - l| -3112
2n
i=1
1 Tr
+ Tr {B 2Tr
S AAB) + 5 - 31
2
The final term || B12 can harmlessly be dropped in the objective, all other terms do not depend on the individual means. Thus, we can redefine our VICReg objective as
EVICReg (a. 3) = Tr
Σ AB
+
+
EABIF
covariance
Tr (AA)) 2
+Tr Σ (BBB) Tr (M(SAA) Tr (((EBB)))
2d
variance regularization
as intended.
F. Experimental Details
This appendix accompanies Sec. with further details of the study. Before describing the experiments, we comment one quantity appearing in the risk bounds that is not analyzed experimentally is the distribution shift error that passes (Px norm to the L²(Qx) (nQQm))ommmm -norm from Sec. 3. For this, refer the reader to the host of empirical work at the intersection of FSL, attribute-based and prompting-base based ZSP, and distribution shift (see Recht et al. (2019); Hendrycks and Dietterich (2019); Goyal et al. (2023) and references therein).
F.1 Compute Environment
Experiments were run CPU/GPU workstation with 12 virtual cores, 126G of memory, and four NVIDIA TITAN Xp GPUs with 12G memory each. The code was written in Python 3.10 with the environment given by the YAML file in the supplement. The OpenCLIP and CLIP Benchmark repositories were either used directly or adapted our codebase.
F22 Evaluation Datasets
We use the following datasets as evaluation benchmarks for zero-shot image classification. Note that the following standard statistics describe their test sets.
Describable Textures Dataset (DTD): 1,880 examples labeled with 47 classes (Cimpoi al., 2014).
Flowers 102: 6,149 examples labeled with 102 classes. (Nilsback and Zisserman, 2008).
FGVC Aircraft: 3,333 examples labeled with 100 classes (Maji et al., 2013).
SUN397: 21,750 examples labeled with 397 classes (Xiao et al., 2010).
ImageNet-1k: 100,000 examples labeled with 998 classes. (Deng et al., 2009).
The ImageNet-Caption dataset (Fang et al., 2023) is also used for evaluation using subset of 134,593 examples, whereas a 40,000 held-out subset is used to estimate the conditional means of the text embeddings. For the subsets of ImageNet- Captions, the exact filenames the ImageNet-16 1k subsets are provided along with their captions. Image preprocessing for evaluation was done using the transformations in the PyTorch trans forms module that were associated with each OpenCLIP model.
55

---

A Generalization Theory for Zero-Shot Prediction
For the experiment behind Fig. 3, we design three in-distribution sub-tasks by randomly selecting collections of 50 classes (y1, 82, Vs) from each of 998 classes, reserving held-out prompting examples (Z1, Yi). :.... (Z Y15,000). 100 for each of 150 classes. Then, for task i, using M examples ji (y)..... (y) selected randomly without replacement for y ys. we use the vector NT Em= ((Z)m(t) as the class embedding (projected unit norm). Using an evaluation set of approximately 25,000 examples from each sub-task, compute the classification accuracy of this approach.
F.3. Model Specification and Hyperparameters
CLIP Architectures First, we specify which OpenCLIP models and pre-training sets were used. These models were chosen due their range of top-1 zero-shot accuracies the ImageNet-Ik 1k benchmark (as shown below). As opposed to already highly performant models (250% ImageNet-Ik), these models benefited more from optimized prompting techniques in our initial experiments.
Model ResNet-50
OpenCLIP Model Tag
Pre-Training Set Tag
ImageNet-It 1k Top-1 Acc.
RN50 allb-clip-ae ViT-B-32
yfcc15m v1 datacomp m s128m b4k
28. 11%
NLLB-CLIP
33.51% 11%
ViT-B/32
32.81%
Prompt-Generating Model We employed the tt model publicly available
2----..------ttteeeccc----- on HuggingFace. For the purpose of generation, we used a top-p hyperparameter of 0.9 and temperature hyperparameter of 0.99 for more diverse responses. Meta-prompting was based the following instructions per dataset, which slight variations of those used in Pratt et al. (2023):
Describable Textures Dataset (DTD):
"What does material look like?",
"What does surface look like?".
"What does texture look like?".
"What does a object look like?".
"What does pattern look like?"
Flowers 102:
"Describe how to identify a(n) type of flower." "What does a(n) flower looks like?" ?"
FGVC Aircraft:
"Describe a(n) aireraft.".
"Describe the aircraftt"
SUN397:
"Describe what a(n)
looks like."
"How can you identify a(n)
?"
"Describe photo of a(n)
"Describe the scene of a(n)
ImageNet-lk:
"Describe what a(n)
looks like."
"How can you identify a(n) ?
"What does a(n) (o))_oooh look like?".
"Describe an image from the Internet of a(n)
- "Write a caption of an image of a(n)
56

---

A Generalization Theory for Zero-Shot Prediction
The following additional instruction was appended for better-formatted responses: "Please format your response as one that contains only lower case letters and special characters (including lines, bold, and any markdown artifacts) other than a period (?) or commas (?)). The response should be single sentence ending in period that is directed toward the final instruction in this message. Your sentence should be a minimum of three words and maximum of thirty.".
Our reproducibility effort includes not only the full list of all 164,400 prompts generated from LlaMA 3, but the subset of prompts used for each class and each seed used to generate the figures in Sec. 4.
E.4. Derivation of Simulation Setting
The data-ge data-generating process for (X, 2, Y) in the simulation from Sec. is as follows. Because we isolate the effect residual dependence in this simulation, we construct a joint distribution Рx,,, that satisfies Asm. I, and moreover, such that Qx.2 2 Px,2 z and PY.2 Py,z. Let = {0, 1}, indicating binary classification. We consider X 2 Rd and pair of Gaussian distributions Y==; Px, (r)) where
X 2
(1 |x |2
Cxx
Cx Czz
~ N
given =
(99)
C2xls
Then, the distribution is fully specified by mean vectors and covariance matrices along with the parameter P P = 1]. Letting (t: C) indicate the density function of the N(,, C) distribution, the direct predictor is equal to
pN(x;; 1x pN(x:; (1 p)N(xxXXx))
p(a))
Exxx [Y]X]
(100)
Similarly, the indirect predictor is given by
no (x) Exx,z E2yy [Y] [X] (x) = Exx, [p(Z) (x), (N:21PZ11
(101)
p(z) (2 12)11) (1 (2: (1200 12210)
(102)
The expectation in (101) over Z given x can be evaluated via simulation based on the mixture model P
(1 xo X= and the exact calculation
Z N (122 + Czx Cx X (x: ( Czzww - Czxis X Cxzww given X = xx Y= =
Finally, the residual dependence Fx ( [)] can be computed by the following steps. First, notice that the conditional distribution X given = z and Y = y is given by
X C~~ N (xxI + Cxz C (= -22y) Cxxis Cxz C C2xlv)
The likelihood ratio Sg from (13) can be computed (where the evaluation refers to the density) via
(x) (1 y) p(=))] Px)z=2(z))pP( + +1 y) p(=))]
PxIy=n,==x(1))
(x]z=z(<)
Pxir=y,Z=al0
(1 (1= ((E)
To simulate from the marginal Pz. we use the mixture pP pP + (1-p) To interpolate between the setting in which X Z (the indirect predictor performs at chance) and X JL Y (the
after which (14) can be directly applied.
57

---

A Generalization Theory for Zero-Shot Prediction
indirect predictor is equivalent to the direct one), we the setting
Mxjo 1 Mxj1 -
Let a. > be constants and let [0, 1| be a parameter. Then, we define
2zj0 = 20a 1211 = 201
Czzio = aI, Czx 2
Czz bI, Czxj1 = Øb I
and finally Cxxjo = (1 + ) and Cxx11 = (1 I. Due to Gaussianity, is clear that
f= = C2x1o = Czx =0 0 - X Z = vy.
On the other hand, using the distribution of X given (2, Y), that is,
X~ X~N (ux1u - Cx 22 (z 1211) Cxxls - Cxz y 221y C2XIu) given 2 =22Y Y = = y.
we have that
Mxjo Cxz1o 0x = PxI1 CxzI1 C2Z
0=1-
Cx21o 2210 2210 Cxzu 22
X - (103)
Cxxxo Cxz1o C 22 Czx1o Cxx11 Cx C 22 Czxl1
as the distribution of X remains the same given either Z = 2, Y 0 or = Y 1. Thus, in the simulation, we interpolate between and for the value of O. We set the parameters which Ep [x;;; Y [)] can be computed in a numerically stable manner. We set p and d = 2.
and simply to different numbers for
Finally, the lines labeled CLIP and VICReg in Fig. indiçate the predictors generated by training two MLP encoders using i==1 the corresponding objective on observations {(X,, } for N = 10, 000 pre-training observations. The encoder had single hidden layer of 16 units and an output dimension of d. When performing classification, the prompting distribution used for the methods based on self-supervised learning is the true distribution of 2 y with M 500 samples, allowing us to isolate residual dependence while incurring no prompt bias and negligible prompt variance. Each model learning rate of 0.01. In the case of the VICReg objective, we
was trained for epochs with the AdamW optimizer used the parameterization of the original paper (Bardes et al., 2022) with the settings (7, A, n4, e,) (1, 25, 25, 0.0001) per the authors' recommendations (see their Eq. (6)).
58


Reviews:
[{"review_id": "nJqnEpk2nf", "reviewer": "Reviewer_55ie", "summary": "The paper proposes a theoretical framework for zero-shot prediction linking pre-training to prompting and also introduces residual dependence (information loss between modalities) and prompt complexity (sample/prompt trade-offs). Risk bounds show ZSP needs huge pre-training data but few prompts.\n\n\n## update after rebuttal\nThanks for the effort,  I decide to keep the score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review&mdash;we address your main comment below.\n\n> **\"The theoretical analysis is limited to CLIP-like multi-modal models.\"**\n\nOur analysis broadly describes multimodal encoder + prompting strategies, where the encoders could be learned by a variety of objectives (not only CLIP). Please see Appendix E for a review of such multimodal encoder strategies, including Multimodal InfoNCE/CLIP, BarlowTwins/Nonlinear CCA, the Spectral Contrastive Loss, and Multimodal VICReg. Crucially, we do not focus on the mechanics of how particular objectives or optimization algorithms result in particular encoders (see the related work Section 1 and references therein). We focus on the downstream performance is affected by 1) the dependence structure of $(X, Z, Y)$, the image-caption-label triple, and 2) the nature and amount of the prompting strategy. \n\nTo improve based on your feedback, we have included a simulation in [Figure 6](https://tinyurl.com/av8sd5x5) of the rebuttal wherein the two-stage predictor analyzed in our paper is compared to both CLIP and VICReg trained on the corresponding data. We find that the dependence of two-stage prediction on the residual dependence follows the same trend as that of both CLIP and VICReg.\n\nIf this point is addressed adequately, then we would appreciate that the score be raised; if not, please let us know if you have further comments or questions and thank you once again for this feedback!", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes. The framework and experimental design rigorously explains why self supervised learning pre-training + prompting works for zero-shot image tasks.", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The work proposes a theoretical framework for zero-shot prediction linking pre-training to prompting", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:  Rigorous analysis; connects SSL objectives (CLIP, VICReg) to theory; Explains success of LLM-generated prompts\nWeakness: The theoretical analysis is limited to CLIP-like multi-modal models.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ab9SVvF4MY", "reviewer": "Reviewer_fhW7", "summary": "This paper explores the theoretical foundations of zero-shot prediction (ZSP) in foundation models, establishing a formal statistical framework to analyze how pretraining on large-scale, multimodal, unlabeled datasets transitions into downstream zero-shot inference via prompting. The authors identify key factors influencing the success of ZSP and introduce a novel perspective by modeling multimodal data as a joint distribution over X (input images), Y (latent labels), and Z (image captions).\n\nBuilding on this framework, they reformulate image classification as a text classification problem through prompting, leading to a perspective where zero-shot inference is viewed as a sample estimator within a two-stage regression problem. Leveraging concepts from reproducing kernel Hilbert spaces (RKHS), the authors derive closed-form estimators for their statistical framework. They further provide a theoretical analysis of sample complexity, examining the impact of both dataset size and the number of prompts used in estimation. Additionally, they propose a new loss function for ZSP, referred to as the Variance Regularized Covariance objective, and show its connection to existing self-supervision objectives. Finally, the authors conduct semi-synthetic experiments using CLIP models to empirically assess their theoretical results, particularly the relationship between prompt sample complexity and performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read our manuscript critically. This is undoubtedly one of the most comprehensive reviews we have ever received. Please see your comments addressed below.\n\n> **“What are the implications of prompt bias and residual dependence?... Clarifying their role... would strengthen the paper's contributions… would it be possible to construct a synthetic dataset that aligns with the theoretical assumptions?”**\n\nWe provide a synthetic example (see [Figure 6](https://tinyurl.com/av8sd5x5)) to highlight these implications. We focus on residual dependence, which has only been previously alluded to in Oko et al (arXiv, 2025), but simply assumed be zero. We aim to clearly illustrate two claims: 1) the residual dependence $I(X;Y|Z)$ (for image-caption-label $(X, Z, Y)$) governs the performance gap between the two-stage predictor (Eq. (5) / Eq. (6) of our paper) and the Bayes optimal predictor and 2) the encoder-based zero-shot predictors used in practice (such as in CLIP) behave as the two-stage predictor given enough data. The mathematical details are given in the [linked derivations](https://tinyurl.com/av8sd5x5). This experiment controllably interpolates between the “worst” setting $I(X;Z|Y) = 0$, where ZSP performs at near chance and  $I(X;Y|Z) = 0$, where ZSP performs optimally. While further investigation would be interesting, both claims are supported within the simulation.\n \nIn other words, $I(X;Y|Z)$ is a simple distribution parameter that governs how close the best ZSP method can do compared to the optimal downstream predictor, which is of clear interest both in theory and practice. While out of scope for this paper, we hypothesize that this quantity can be estimated in pre-training data selection methods.\n\n> **“… are the authors proposing a new loss function for ZSP…? … it remains unclear whether this [variance-regularized covariance] formulation offers practical benefits over existing self-supervised learning objectives.”**\n\nThere is no intention in the paper to propose a new loss function for SSL, or to even promote one SSL method over another. On the contrary, we include Appendix E to embrace existing, complementary work on SSL and to provide intuition on the relationship between our normalized cross-covariance-based estimator and the common SSL procedures used in practice. This is verified experimentally at least for the motivating example of CLIP in the given simulation.\n\n> **“zero-shot image classification benchmarks… are reasonable choices for proof-of-concept experiments on prompt complexity… the analysis does not extend to other self-supervised learning (SSL) settings.”**\n\nDue to character limits, please see our response to Reviewer GT2x, in which we describe the motivation for this task. In summary, because we specifically study zero-shot prediction through prompting, similar tasks such as image/text retrieval (which do not include a prompting component) are not meaningful in our setting.\n\n> **“…what exactly does \"ideal prompting\" refer to?.”**\n\nThe ideal prompting strategy is one in which the prompt bias term is zero, i.e. the user is able to draw from the distribution $P\\_{Z|Y=y}$ (one of the implications of defining prompt bias in the first place). In the ImageNet-Captions dataset, we are able to compare to this ideal strategy because we observe direct observations of $(Y,Z)$ pairs (as images have both captions and labels). Thus, we hold out a pool of pre-training examples and draw from these pairs to estimate the prompts. \n\n> **“Moreover, the paper explicitly poses the question: \"...does ZSP achieve near-optimal statistical performance on a downstream task, and with what dependence on (1) the pre-training data distribution, (2) the downstream task distribution, and (3) the prompting strategy?\" However, the empirical experiments are not structured to directly address this question.”**\n\nThank you for raising this point. On (1), our theoretical analysis suggests that this dependence is captured by the residual dependence quantity $I(X;Y|Z)$, and upon your suggestion, we designed synthetic experiments to address this claim. We can perform similar real data experiments if the reviewer finds it helpful. On (2), we did not dedicate experiments to showing how distribution shift may affect performance, as countless empirical studies (see Quiñonero-Candela et al. (2022)) exist on this topic. On (3), the experiments in Section 4 help determine the scaling behavior of the accuracy with the number of prompts, highlighting that the ideal range for reducing prompt variance can be as high as 50-100.\n\nWe also have addressed all other comments (references, clarifications) but reserve them for the discussion period due to space limitations. Given our efforts to improve the paper in experimentation and presentation in light of your recommendations, we hope you will consider raising your score to above the acceptance threshold. Please allow us to answer additional concerns you have!", "claims_and_evidence": "The paper presents a statistical framework for analyzing zero-shot prediction (ZSP) in foundation models. It introduces key concepts such as prompt bias, residual dependence, and prompt sample complexity while relating a class of self-supervised learning (SSL) objectives to a variance-regularized covariance (VRC) form. While this framework offers an interesting theoretical perspective, the claims made in the paper are not sufficiently supported by empirical evidence. Below, I outline specific issues with the key claims:\n\n1. Prompt Bias and Residual Dependence:\n- Claim: The authors introduce the notions of prompt bias and residual dependence to quantify deviations from optimal zero-shot inference.\n- Issue: The paper does not provide empirical evidence demonstrating the practical usefulness of these concepts. While they are mathematically well-defined, their impact on real-world zero-shot tasks remains unverified.\n\n2. Connection Between SSL Objectives and Variance-Regularized Covariance (VRC):\n- Claim: The paper relates a class of SSL objectives to a variance-regularized covariance formulation, suggesting theoretical connections to VICReg.\n- Issue: Despite establishing these theoretical connections, the authors do not provide any experiments to validate the proposed loss function's effectiveness in the ZSP setting. Without empirical results, it remains unclear whether this formulation offers practical benefits over existing self-supervised learning objectives.\n\n\n3. Prompt Sample Complexity and LLM-Ensembled Prompts:\n- Claim: The authors propose a notion of prompt sample complexity to support their theoretical analysis and argue that ensembling LLM-generated prompts improves zero-shot performance.\n- Issue: The proposed prompt sample complexity does not substantively contribute to the theoretical analysis, as it does not establish new insights beyond existing work. Moreover, the claim that ensembling LLM-generated prompts improves performance is already well-documented in the community (e.g., [1][2][3]), making this result unsurprising rather than a novel contribution.\n\nReferences:\n[1] Menon, Sachit, and Carl Vondrick. \"Visual Classification via Description from Large Language Models.\" ICLR, 2023.\n[2] Yang, Yue, et al. \"Language in a Bottle: Language Model Guided Concept Bottlenecks for Interpretable Image Classification.\" CVPR, 2023.\n[3] Esfandiarpoor, Reza, Cristina Menighini, and Stephen Bach. \"If CLIP Could Talk: Understanding Vision-Language Model Representations Through Their Preferred Concept Descriptions.\" EMNLP, 2024.", "methods_and_evaluation_criteria": "The authors use CLIP models and standard zero-shot image classification benchmarks, which are reasonable choices for proof-of-concept experiments on prompt complexity. However, this setup is insufficient to fully support the broader claims made in the paper. Notably, the analysis does not extend to other self-supervised learning (SSL) settings, such as image-to-image tasks, which could provide a more comprehensive evaluation.\n\nMoreover, the paper explicitly poses the question: \"By what composition of learning stages does ZSP achieve near-optimal statistical performance on a downstream task, and with what dependence on (1) the pre-training data distribution, (2) the downstream task distribution, and (3) the prompting strategy?\" However, the empirical experiments are not structured to directly address this question, limiting the strength of the paper’s conclusions.", "theoretical_claims": "I checked the correctness of the theoretical proofs in detail, but the analysis appears to be a straightforward combination of standard results in RKHS theory. However, I noticed a potential issue in lines 1621–1622, where the approximation $\\log(1+y) \\approx y$ is used without justification. Without further clarification, the validity of this assumption and the subsequent results remains unclear.", "experimental_designs_or_analyses": "I reviewed the experimental design and analysis. The authors use CLIP models and standard zero-shot image classification benchmarks, which are reasonable choices for proof-of-concept experiments on prompt complexity. However, some aspects need further clarification.  \n\nFirst, it is unclear how the number of prompts is scaled in \\textit{Ideal Prompting with Observations from} $P^{\\mathcal{\\tau}}_{Z, Y}$. Specifically, do the authors sample captions from a predefined caption pool and simply combine them? More details on this process would help clarify their approach.  \n\nSecond, a potential issue arises from the use of LLaMA 3 for generating prompts. The distribution $P_{Z|Y=y} $ in CLIP may not be well approximated by a language model, introducing an additional source of bias. This discrepancy could affect the validity of the results and should be addressed.", "relation_to_broader_scientific_literature": "The main contribution of this paper is to provide a theoretical foundation for the common practice of zero-shot prediction (ZSP) using multiple prompts per class as an ensemble. While this approach is widely used in the community, its theoretical underpinnings have not been well studied. The authors attempt to formalize this practice by introducing a two-stage regression framework and analyzing prompt sample complexity. This theoretical perspective helps unify existing empirical findings and suggests promising future research directions.\n\nSpecifically, prior works have demonstrated the effectiveness of class-conditional prompt ensembling in improving zero-shot classification:\n\n- [1] Uses large language models (LLMs) to generate class descriptors for classification prompts, averaging them to create an ensemble—a direct example of the class-conditional prompt ensemble approach.\n- [2] Generates visual descriptions for each class and averages them, another instance of class-conditional prompt ensembling.\n- [3] Utilizes multiple concepts to describe each class and applies them in concept bottleneck models.\n- [4] Extracts detailed visual descriptions from LLMs for zero-shot classification and extends this technique to few-shot adaptation.\n- [5] Investigates the visual features that are most effective for vision-language model (VLM) classification, which can be interpreted as a direct attempt to estimate Y instead of sampling Z.\n\nThe proposed two-stage regression framework provides a unified theoretical perspective on these empirical approaches, offering a mathematical basis for prompt ensembling and prompting strategies in ZSP. This connection highlights key aspects of prompt bias, residual dependence, and sample complexity, which could inspire future work on designing more theoretically grounded prompting techniques.\n\nReferences\n\n[1] Menon, Sachit, and Carl Vondrick. \"Visual Classification via Description from Large Language Models.\" ICLR, 2023.\n\n[2] Pratt, Sarah, et al. \"What does a platypus look like? Generating customized prompts for zero-shot image classification.\" ICCV, 2023.\n\n[3] Yang, Yue, et al. \"Language in a Bottle: Language Model Guided Concept Bottlenecks for Interpretable Image Classification.\" CVPR, 2023.\n\n[4] Maniparambil, Mayug, et al. \"Enhancing CLIP with GPT-4: Harnessing Visual Descriptions as Prompts.\" ICCV, 2023.\n\n[5] Esfandiarpoor, Reza, Cristina Menighini, and Stephen Bach. \"If CLIP Could Talk: Understanding Vision-Language Model Representations Through Their Preferred Concept Descriptions.\" EMNLP, 2024.", "essential_references_not_discussed": "[1] analyzes the relationship between concept frequency in the pretraining dataset and its impact on downstream performance. Since the proposed framework discusses the role of pretraining data distribution in ZSP, this phenomenon seems directly relevant to their theory and could provide additional insights into sample complexity and residual dependence.\n\n[2] proposes another statistical framework for ZSP and provides a theoretical analysis of multimodal generative AI, including CLIP. Given that the current paper also introduces a new theoretical framework, it is important to compare these approaches and clarify how they relate. This work seems particularly relevant to understanding the assumptions and limitations of the proposed framework.\n\nReferences:\n[1] Udandarao, Vishaal, et al. \"No 'Zero-Shot' Without Exponential Data: Pretraining Concept Frequency Determines Multimodal Model Performance.\" NeurIPS, 2024.\n[2] Oko, Kazusato, et al. \"A Statistical Theory of Contrastive Pre-training and Multimodal Generative AI.\" arXiv preprint arXiv:2501.04641, 2025.", "other_strengths_and_weaknesses": "Strengths\n- The theoretical framework is interesting and could serve as a solid foundation for future work.\n- The paper provides an integrated perspective on self-supervised learning (SSL) and zero-shot prediction (ZSP), which may be valuable for bridging these areas.\n\nWeaknesses\n- The paper lacks clear organization. The scope is quite broad, yet the theoretical analysis and empirical results are not well integrated to support the full range of topics covered.\n- The main contribution is unclear, making it difficult to pinpoint the paper’s key takeaway.\n- The experimental validation is not comprehensive enough to fully support the claims and theoretical results.\n- The theoretical analysis is heavily reliant on RKHS theory but does not offer practical guidance on key aspects such as the choice of the number of prompts or effective prompting strategies.", "other_comments_or_suggestions": "Please see questions.", "questions_for_authors": "1. Clarification on \"Ideal Prompting\": In the experiment section, what exactly does \"ideal prompting\" refer to? Does it mean prompts manually designed by humans, in contrast to those generated by LLMs as described in the next paragraph? Understanding this distinction is important because it affects how the results should be interpreted. If \"ideal\" refers to human-generated prompts, it would be useful to clarify how they were designed and why they are considered ideal. If they are derived from some theoretical criterion, explaining that explicitly would improve clarity.\n\n2. In the section \"Learning via Variance-Regularized Covariance\", are the authors proposing a new loss function for ZSP, or are they simply re-deriving existing self-supervised learning (SSL) objectives within the proposed framework? This distinction is important because if a new loss function is being introduced, its effectiveness should be empirically validated to demonstrate its advantages over existing approaches. If the section instead provides a theoretical reinterpretation of existing objectives, a more detailed discussion on how this perspective enhances our understanding of SSL objectives and whether it offers any practical benefits would improve the paper.\n\n3. Can the authors control the pretraining process to empirically validate the proposed framework? If direct control over pretraining is not feasible, would it be possible to construct a synthetic dataset that aligns with the theoretical assumptions? This would provide stronger empirical support for the framework.\n\n4. What are the implications of prompt bias and residual dependence? These concepts are introduced as key components of the framework, but their practical significance is not clearly articulated in the later sections of the paper. Clarifying their role—either through empirical validation or additional theoretical discussion—would strengthen the paper's contributions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OPCErVviwp", "reviewer": "Reviewer_8U7M", "summary": "This paper provides a formal modeling of the two-stage learning procedure, known as CuPL: (1) pretraining on multimodal labeled data and (2) zero-shot prediction (ZSP) on the pre-trained model with natural language prompts. The goal is to offer a theoretical explanation of the success of CuPL. To achieve this, the paper analyzes how ZSP optimality depends on the pretraining task distribution, the downstream ZSP task distribution, and the prompting strategy. \n\nTo me, the key of this model is Equation (6), where two encoders, respectively on input and latent variables, are introduced. Via this modeling, the authors point out that the ideal prompt samples an unobservable conditional distribution of latent variables, given the label. Based on this construct, the authors then compare the informational dependence of unimodal contrastive learning, reconstructive learning, and multimodal contrastive learning. They point out that the last one is the most compatible dependence structure for ZSP. \n\nOn top of the selected dependence structure, Theorem 1 identifies the epistemic error bounded by the pre-training sample size and the number of prompts. Then, Theorem 2 identifies the aleatoric error bound. These bounds eventually lead to the variance-regularized covariance loss in Equation (12). Experiments on image classification compare default community-curated prompts (baselines) and CuPL. Results show an increasing trend in CuPL accuracy with more prompts, supporting the claims of how the number of prompts affects error bound in the theorems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review. We address your comments below.\n\n> **“I hope the authors could discuss more on the relationship between FSL, ZSP and MAML.”**\n\nWe discuss model agnostic meta-learning (MAML) in its [offline](https://proceedings.mlr.press/v70/finn17a.html) variant, i.e., as a tool for multi-task or meta-learning. The offline meta-learning method can be thought of a simpler setting than FSL, in which the downstream evaluation tasks are given to the user *upfront*. Thus, pre-training an encoder and training a predictor for all of the evaluation tasks can be done in one end-to-end step. On the other hand, FSL is not (in general) given any downstream task upfront, so models cannot be learned in an end-to-end manner at once. ZSP is a \"harder\" setting still, as no downstream data is given at any point in the training-evaluation pipeline.\n\n> **“Although Section 2 has demonstrate why ZSP is best compatible with multimodal contrastive learning, it does not necessary discuss the advantage of ZSP over other SSL methods. One reason could be that obtaining labels for FSL is hard, but I would like to see more evidence supporting this.”**\n\nFirst, we clarify that we do not intend to “discuss the advantage of ZSP over other SSL methods”, because SSL is precursor to ZSP; they are not comparable. However, for the comparison of ZSP to FSL, obtaining labeled data is *precisely* the bottleneck that motivates ZSP (as you correctly pointed out). Second, the authors request additional clarification on what “more evidence supporting this” refers to, so we may adequately address your points. Having no access to downstream training data is not a claim; it is a specific data availability regime that is now well-established a modern machine learning setting (see [Pourpanah (2022)](https://ieeexplore.ieee.org/abstract/document/9832795)). ZSP is the corresponding pipeline for this problem. Thus, we do not argue for any advantage of ZSP over FSL&mdash;they are simply different methods for different problems. Accordingly, different SSL methods accompany these problems, as alluded to in Section 2.\n\nIn fact, we generally always expect FSL to perform better than ZSP with equal pre-training data, as FSL receives strictly more task information than ZSP. That being said, a question we do consider is 1) “how close can ZSP get to the performance of FSL (with a large amount of training data)?” and 2) “how do we quantify it?”. This exactly leads to our mathematical notions of prompt complexity and residual dependence. That is, if the prompting strategy approximates the conditional distribution of the text $Z$ given $Y = y$ and we have that $X$ and $Y$ are approximately conditionally independent given $Z$ (see Figure 2 in the paper), then ZSP has no *theoretical* disadvantage over FSL. In response to your review, we verify this in simulation in [Figure 6](https://tinyurl.com/av8sd5x5) of the rebuttal.\n\n> **“[Q1 + Q2] ...how are prompts generated in the baseline method... Why does the performance of the baseline stay exactly the same as more prompts are provided? Are the baseline prompts provided all at once?”**\n\nThe baseline prompts are not “generated”, as they are selected by humans as defaults in the CLIP benchmark package. Therefore, they cannot be created in arbitrarily large amounts such as LLM-generated prompts. Rather than matching the number of prompts between human baselines and LLMs, this illustration shows the scaling of the downstream classification accuracy as the user generates a large volume of prompts. Moreover, the goal of the experiment is not to market class-conditional prompting as a new method, but to experimentally verify the saturation point at which $O(1/M)$ prompt variance term in Theorem 1 becomes negligible.\n\n> **[Q3] “The experiment does not compare ZSP with FSL baselines. I hope the authors could provide a sound reason for not doing so. To me, demonstrating the success of ZSP requires analysis and/or experiments to show it defeats other SSL methods… Why not compare CuPL/ZSP methods to these baselines?... the paper needs to demonstrate the advantages of CuPL/ZSP over other SSL methods, but not just community-curated prompts.”**\n\nAs mentioned above, demonstrating the success of ZSP as compared to FSL was not a goal of this paper. Similarly, SSL was not a baseline for ZSP to defeat, but rather a form of pre-training that may lead to the ZSP capability. However, we are interested in studying the performance gap and its dependence (see [Figure 6](https://tinyurl.com/av8sd5x5)). We provide experiments that compare the ZSP performance to FSL baselines using linear probing on the evaluation datasets seen in the paper: FGVC Aircraft, DTD, Flowers 203, SUN397 (see [Figure 5](https://tinyurl.com/av8sd5x5)). \n\nIf we have addressed your concerns, we would appreciate that your score be raised, and if not, we are happy to answer any questions or consider additional experiments!", "claims_and_evidence": "Overall, I see several important claims in this paper, and they are all well supported. First, the authors claim that the dependence structure of multimodal contrastive learning fits the best for ZSP, and it is well-supported by the analysis in Section 2. Next, another claim is the epistemic and aleatoric error bounds in ZSP, given pre-training data size and number of prompts (Theorem 1 and 2). The proofs of these claims are sound, and the experimental evaluation supports the influence of prompt numbers. Finally, a third claim is a generalized form of variance-regularized covariance loss in Equation (12), and state-of-the-art CuPL methods are identified to fit this generalized form.", "methods_and_evaluation_criteria": "The evaluation method is reasonable by comparing CuPL methods that fit in Equation (12) to default prompting strategy. The metrics is standard top-k accuracy, and the experiments not only compares between CuPL to the baseline, but also shows how increasing number of prompts affect the result. There are still several things unclear to me about the baseline methods, and I will point them out in the questions to authors.", "theoretical_claims": "As stated above, the theoretical claims are supported by sound analysis.", "experimental_designs_or_analyses": "As stated above, the experimental design looks reasonable to me, except for the selection of baseline. I will list my questions in the last part.", "relation_to_broader_scientific_literature": "This paper is well-related to broader literature, as it aims to provide theoretical support for the success of CuPL methods.", "essential_references_not_discussed": "I hope the authors could discuss more on the relationship between FSL, ZSP and MAML [1].\n\n[1] Finn, Chelsea, Pieter Abbeel, and Sergey Levine. \"Model-agnostic meta-learning for fast adaptation of deep networks.\" International conference on machine learning. PMLR, 2017.", "other_strengths_and_weaknesses": "Strengths:\n+ The paper is very well motivated, as the goal is to explain the success of CuPL.\n+ The proofs are rigorous and sound.\n\nWeaknesses\n- Although Section 2 has demonstrate why ZSP is best compatible with multimodal contrastive learning, it does not necessary discuss the advantage of ZSP over other SSL methods, i.e., unimodal contrastive learning and reconstructive learning. One reason could be that obtaining labels for FSL is hard, but I would like to see more evidence supporting this.\n- Like the above bullet point, the experiment does not compare ZSP with FSL baselines. I hope the authors could provide a sound reason for not doing so. To me, demonstrating the success of ZSP requires analysis and/or experiments to show it defeats other SSL methods.\n- The narrative structure could be improved. For example, Assumption 1 is crucial for both theorems, but it is in the appendix. Many discussion of Theorem 1 appears before the theorem itself. It would be better if Assumption 1 and Theorem 1 are first stated, and then the analysis follows.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I would love to improve my rating if the authors can answer the following questions.\n\n1. In the experiment setup, how are prompts generated in the baseline method, i.e., community-curated prompts?\n\n2. Why does the performance of the baseline stay exactly the same as more prompts are provided? Are the baseline prompts provided all at once? If so, this does not seem to be an apple-to-apple comparison, as CuPL gradually generates prompts.\n\n3. Section 2 has discussed alternative approaches in SSL: unimodal contrastive FSL and reconstructive FSL. Why not compare CuPL/ZSP methods to these baselines? In order to demonstrate the success of CuPL/ZSP, I suppose that the paper needs to demonstrate the advantages of CuPL/ZSP over other SSL methods, but not just community-curated prompts.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fWRAmH73Az", "reviewer": "Reviewer_GT2x", "summary": "The papers takes a theoretical approach towards understanding key quantities driving zero-shot prediction. Introducing and deriving bound for the aforementioned problem setting, the paper analyzes translation between modalities and effectiveness of prompt engineering strategies a multi-modal learning setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your hard work in verifying the paper. The authors are happy to hear that you found the narrative insightful and well-written. We address your concerns below.\n\n> **“[The Methods And Evaluation Criteria] make sense, even though they can be extended considerably… [The Experimental Designs Or Analyses] make sense but…are quite limited to classification… Heavy focus on theory and limited experimental results and demonstrations.”**\n\nWe acknowledge this feedback by 1) motivating why this is the most relevant task for studying modern ZSP, 2) providing additional experimentation with simulations using CLIP/VICReg and linear probe baselines, and 3) by further justifying the theoretical focus of the work. Details are given below.\n\nFirstly, we would like to emphasize that this task is by far the canonical one for studying ZSP. This is largely due to the fact that prompting is inherently tied to natural language. Indeed, consider [Gadre et. al. (NeurIPS, 2023)](https://openreview.net/forum?id=dVaWCDMBof), one of the largest-scale studies on the design of multimodal pre-training data for foundation models. In over three hundred experiments, models are evaluated on either zero-shot image classification, zero-shot image/text retrieval, or linear probing. As in our case, only the encoder architectures, datasets, and prompting strategies are varied. In retrieval, there is no prompting, and in linear probing, training data is available. \n\nSecondly, in response to the explicit requests of 8U7M, we also include linear probing comparisons in [Figure 5](https://tinyurl.com/av8sd5x5) of the rebuttal. This gives an idea for the near optimal performance of the ZSP methods in the case there there was no residual dependence and that the prompting strategy was unbiased. How this performance gap depends on the residual dependence $I(X;Y|Z)$ is studied experimentally in [Figure 6](https://tinyurl.com/av8sd5x5) of the rebuttal as well.\n\nFinally, while you correctly pointed out that there is a relatively heavy focus on theoretical work in the paper, we highlight that this is an intention, as the mathematical foundations of modern ZSP is still in its infancy. During the time of submission, the only directly related work we were aware of was [Chen et. al. (ICLR, 2024)](https://openreview.net/forum?id=S5yOuNfSA0), which we comment on the bottom of Page 2. We were also made aware of the very recent preprint Oko et al. (arXiv, Jan. 2025) by Reviewer fhW7. Thus, we feel as though the theoretical focus of the work is apt based on the current gaps in the scientific literature on this topic.\n\nOnce again, we are grateful for your recommendation of acceptance and are open to address any additional comments or questions during the discussion period.", "claims_and_evidence": "To the level I managed to delve deep, this the claims are supported with solid and rigorous evidence and theoretical corroboration.", "methods_and_evaluation_criteria": "They make sense, even though they can be extended considerably.", "theoretical_claims": "Verifying this completely is almost a full time job! To the level I could dive deep, the derivation follow smoothly and make sense. I reviewed most of Appendix B.", "experimental_designs_or_analyses": "Yes, they make sense but again they are quite limited to classification in two simplistic settings.", "relation_to_broader_scientific_literature": "In my view, this is an extremely insightful and well written paper --- definitely of value to the community. I enjoyed reading this paper.", "essential_references_not_discussed": "Covers it reasonably well.", "other_strengths_and_weaknesses": "Strengths\n- Well written paper, and extremely insightful narrative. \n- Solid theoretical foundation.\n\nWeaknesses:\n- Heavy focus on theory and limited experimental results and demonstrations. \n- Lots of empty spaces within the text, I would just move Appendix F to the main text to cover that, or even better than that expand the numerical results to other settings.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper develops risk bounds for multi-modal foundation models in the zero-shot prediction (ZSP) setting. In such models, two modalities (such as text and images in the case of vision-language models like CLIP) are each embedded into a shared space. In the ZSP setting, test instances of one modality are classified by measuring their distance in the shared space to possible class labels represented by prompts in the other modality.

The first contribution of this paper is to present a nice formalization of this complex setup that relates the pre-training data of the foundation model to the data of the downstream task. Crucially, this setup relaxes the assumptions of prior work that require the marginal distributions of example descriptions to match between the pre-training and test data. Instead, the proposed framework allows for distribution shift between the two.

The second contribution is to formulate generalization guarantees in this setting. The guarantees are built in terms of reproducing kernel Hilbert spaces. A key piece of these guarantees is formalizing the notion of prompt bias with respect to a hypothetical ideal prompt.

The reviewers agreed that the paper was insightful and significant for an important setting that has been challenging to analyze theoretically. During the discussion period, several clarifications were developed that the authors are encouraged to add to the final version. In addition, Reviewer fhW7 noted the relationship between the paper's analysis of class conditional prompts and a recent line of practical in generating such prompts. The paper could also benefit from discussing this connection.
Decision: Accept (oral)