A Generalization Theory for Zero-Shot Prediction

A Generalization Theory for Zero-Shot Prediction

Speakers: Ronak Mehta, Zaid Harchaoui

Conference: ICML 2025

YouTube: https://slideslive.com/39044005

Overview

In this insightful talk from ICML 2025, Ronak Mehta, in collaboration with his advisor Zaid Harchaoui, presents a groundbreaking theoretical framework for understanding the generalization capabilities of zero-shot prediction (ZSP). Prompted by the rapid advancements and perplexing efficacy of foundation models—encompassing large language models and multimodal embedding models—the research addresses a critical gap in the theoretical understanding of their practical applications. While these models have revolutionized tasks like image classification without direct labeled training data, a robust theoretical analysis akin to classical statistical learning theory has been conspicuously absent.

The core of the presentation focuses on deconstructing the generalization error in ZSP, identifying fundamental limits and convergence rates. Mehta introduces a formal methodology that splits this error into an information-theoretic error, which quantifies the inherent limitations of the zero-shot paradigm, and a statistical learning error, which accounts for the finite nature of pre-training data and prompts. This work is not merely an academic exercise; it provides practitioners with a "roadmap" and two distinct proof strategies to analyze their specific ZSP methods, offering crucial insights into why certain approaches succeed or fail. By formalizing ZSP and uncovering four key quantities that govern its performance, this research lays the groundwork for more principled development and deployment of foundation models in resource-constrained environments.

Background

▶ Watch: Introduction to foundation models and zero-shot prediction (ZSP) (0:00)

The recent explosion of foundation models has transformed the landscape of artificial intelligence. These models, defined here as generative models like large language models (LLMs) and those representing structured data (images, text) in vector spaces, exhibit remarkable capabilities. A particularly exciting application stemming from these models is zero-shot prediction (ZSP), which allows for robust classification or prediction without any directly labeled training data for the target task. This paradigm is especially appealing to individuals and organizations lacking the "enormous amount of resources" typically required for large-scale supervised learning.

The mechanism for ZSP, as exemplified in multimodal embedding models, involves two key steps. First, foundation models are pre-trained on vast datasets of paired modalities, such as images and text, to learn a joint representation space. The objective is to embed semantically similar image-text pairs close to each other in this vector space, often using transformer-based models. Second, for a downstream classification task, the labels of interest are converted into natural language descriptions using prompting techniques. These prompts act as "pseudo-captions" for the classes, such as "photo of a sun" or "a drawing of a moon." Advanced prompting strategies include using multiple templates (e.g., "a silver moon glistened in the night") and ensembling their embeddings. Classification then proceeds by computing the highest average inner product between the target image's embedding and the text embeddings generated from the class prompts.

Despite the significant practical advancements and widespread adoption of ZSP, its theoretical underpinnings have remained largely unexplored. In classical machine learning, generalization bounds, often expressed as a mean squared error between a trained predictor f-hat and a true target function f-star, provide crucial insights into convergence rates with respect to the number of training examples. Such theoretical guarantees help understand the reliability and limits of a model. For ZSP, however, the absence of direct labeled training data for the target task fundamentally changes the problem, making traditional generalization analysis inapplicable. The challenge lies in developing a novel theoretical framework that can account for the indirect nature of ZSP, considering factors like the number of pre-training examples, the quantity and quality of prompts, and the inherent limits compared to direct supervision. This talk directly addresses this void, aiming to provide a formal, quantitative understanding of ZSP's performance.

Key Findings

▶ Watch: The theoretical challenge: generalization analysis of ZSP (2:40)

The talk's primary contributions revolve around establishing a rigorous theoretical framework for zero-shot prediction (ZSP), offering a systematic approach to its analysis, and identifying the critical factors that dictate its success or failure.

The central finding is a novel decomposition of the generalization error in ZSP. Unlike classical settings where error is typically bounded between a learned predictor and a true target function based on direct supervision, ZSP's indirect nature necessitates a different perspective. The authors propose splitting the generalization error into two distinct components:

1. Information Theoretic Error (Non-Random Term): This component captures the fundamental limits of ZSP. It represents the irreducible error that arises from the inherent information bottleneck created by the intermediate representation (Z, e.g., captions) and the indirect prediction path. This term is non-random, meaning it reflects the best possible performance ZSP could achieve given perfect knowledge of the underlying probability distributions, thus revealing the intrinsic "gap" between ZSP and direct supervision.
2. Statistical Learning Error (Random Term): This more familiar component quantifies the error introduced by using finite samples. Specifically, it accounts for the variability and approximation errors due to a finite number of pre-training examples (for the embedding model) and a finite number of prompts (for the zero-shot classifier). This term is amenable to statistical analysis, providing insights into convergence rates.

Within the information-theoretic error, two critical quantities emerge:

• Conditional Dependence (X, Y given Z): This measures how much information about the label (Y) is retained in the input (X) when the intermediate representation (Z, e.g., caption) is known. Conceptually, it represents the "strength of the arrow" in a graphical model linking X, Y, and Z. If Z perfectly mediates the relationship between X and Y, then X and Y would be conditionally independent given Z, and this error would be minimal. However, if Z is insufficient to bridge the gap, ZSP will inherently perform poorly. This relationship was experimentally verified using models like CLIP and ViT-L-14.
• Prompt Bias Term: This quantity measures the incompatibility of the three fundamental distributions involved in ZSP: the evaluation distribution (P_XY for the downstream task), the pre-training distribution (Q_XZ for image-caption pairs), and the prompting distribution (rho_YZ for caption-label relationships). A misalignment between these distributions introduces a bias, hindering ZSP's performance even with perfect information.

For the statistical learning error, the authors introduce two proof strategies. One strategy focuses on an identity that relates the population ZSP predictor (f-bar) to a similarity score function R (e.g., the inner product in CLIP) and the true prompt distribution (rho). By estimating these quantities with R-hat (from finite pre-training samples) and rho-hat (from a finite ensemble of M prompts), two additional key quantities are identified:

• Sample Complexity: This relates to the number of pre-training examples (N) used to learn the embedding model and thus estimate R.
• Prompt Complexity: This relates to the number of prompts (M) used to approximate the prompt distribution (rho).

In summary, the talk formalizes ZSP by comparing the empirical zero-shot predictor (f-hat) and the direct supervision target (f-star) to a population zero-shot predictor (f-bar). Through this decomposition, it uncovers four essential quantities—conditional dependence, prompt bias, sample complexity, and prompt complexity—that are argued to be crucial determinants of ZSP's theoretical success or failure, providing a concrete framework for its analysis.

Technical Deep Dive

▶ Watch: Decomposition of ZSP error: information-theoretic and statistical (4:50)

The theoretical framework for Zero-Shot Prediction (ZSP) presented by Mehta and Harchaoui begins by rigorously defining the components of the prediction process and their relationships. Let X represent the input (e.g., images), Y the label (e.g., categories), and Z the intermediate natural language representation (e.g., captions or prompts).

The core of the analysis involves comparing three distinct functions:

1. f-star: The ideal, Bayes-optimal predictor for the downstream task, representing direct supervision. It is defined as f-star(x) = E[Y | X=x] and is derived from the true evaluation distribution P_XY.
2. f-hat: The empirical zero-shot prediction procedure observed in practice. This involves using a learned embedding model (from finite pre-training data) and a finite set of prompts.
3. f-bar: The population version of ZSP. This represents the ideal zero-shot predictor if one had access to the true underlying probability distributions Q_XZ (pre-training) and rho_YZ (prompting), without any sampling error. It follows an indirect prediction path: X -> Z -> Y. Formally, f-bar(x) = E[Y | Z] E[Z | X], where E[Z | X] captures the image-caption dependence (e.g., a CLIP-like score) and E[Y | Z] captures the caption-label dependence (from prompting).

The generalization error of f-hat with respect to f-star is decomposed into two principal terms, by introducing f-bar as an intermediary:

E[ (f_hat - f_star)^2 ] = E[ (f_bar - f_star)^2 ] + E[ (f_hat - f_bar)^2 ]

The first term, E[ (f_bar - f_star)^2 ], is the information theoretic error. This term is non-random and captures the fundamental limits of ZSP. It represents the inherent gap between the indirect ZSP path and direct supervision, even under ideal conditions (infinite data, perfect prompts). This term can be further broken down:

• Conditional Dependence (X, Y given Z): This component quantifies how well Z acts as a sufficient statistic for Y given X. If Y is conditionally independent of X given Z (i.e., P(Y|X,Z) = P(Y|Z)), then Z fully mediates the relationship, and this part of the error would be minimal. The talk explains this using a graphical model analogy, where the "strength of the arrow" from X to Y given Z is assessed. A weak arrow implies strong conditional independence, favoring ZSP.
• Prompt Bias Term: This term measures the incompatibility between the three fundamental probability distributions: P_XY (the target task), Q_XZ (the pre-training data distribution), and rho_YZ (the distribution from which prompts are sampled). If these distributions are misaligned—for instance, if the pre-training captions Z are not relevant to the target labels Y, or if the prompting strategies rho_YZ do not accurately reflect the Y-Z relationship present in the target domain—a bias is introduced that f-bar cannot overcome, leading to an increased error.

The second term, E[ (f_hat - f_bar)^2 ], is the statistical learning error. This term is random and arises from the finite nature of the data available to learn f-hat. Crucially, this error depends only on Q_XZ (pre-training data) and rho_YZ (prompts), not on the target evaluation distribution P_XY. The authors propose two main proof strategies to bound this term:

Approach 1: Similarity Score Function (R)

This strategy leverages an identity proven in the paper that relates f-bar to a similarity score function R and the true prompt distribution rho.

• Similarity Score Function (R): This function measures the dependence or similarity between inputs X and intermediate representations Z. For models like CLIP, R(x, z) would naturally be the inner product between the embedded vector representations of image x and caption z. The speaker notes that R can be thought of as a Radon-Nikodym derivative relating Q_XZ to its marginals, though a simpler intuition is a measure of "score" or "similarity."
• Estimators: In practice, R is approximated by R-hat using finite pre-training samples (N), and rho is approximated by rho-hat using a finite ensemble of M prompts. For instance, rho-hat could be the average embedding of M different prompts for a given class.
• Bound Structure: The resulting generalization bound for this term captures the discrepancy between R-hat and R, and rho-hat and rho. This leads directly to two further key quantities:
• Sample Complexity: This quantifies how N, the number of pre-training examples used to train the embedding model and thus learn R-hat, affects the error. Higher N generally leads to a better R-hat and lower error.
• Prompt Complexity: This quantifies how M, the number of prompts used to form rho-hat, affects the error. A larger M (e.g., through ensembling diverse prompts) typically yields a more robust rho-hat and reduces error.

Approach 2: Two-Stage Prediction Problem

The talk briefly mentions an alternative approach that views ZSP as a two-stage prediction problem. While less detailed in the transcript, this likely involves analyzing the error propagation from the first stage (X to Z prediction/embedding) to the second stage (Z to Y prediction/classification) separately. This approach would also yield relationships dependent on the number of samples (N) and prompts (M).

In essence, the theoretical framework provides a comprehensive breakdown of ZSP's performance determinants. It highlights that ZSP's efficacy is not solely dependent on the size of the pre-training dataset but also on the intrinsic alignment of distributions, the information content of the intermediate representation, and the careful design of prompting strategies. The four key quantities—conditional dependence, prompt bias, sample complexity, and prompt complexity—serve as a complete set of diagnostic tools for understanding, predicting, and ultimately improving ZSP methods.

Experimental Setup & Results

▶ Watch: Understanding ZSP's alternate prediction path (X to Z to Y) (5:50)

The talk primarily focuses on establishing a theoretical framework for zero-shot prediction (ZSP) rather than presenting an extensive empirical evaluation. Consequently, the details regarding experimental setup and specific results are not as elaborated upon as the theoretical derivations. However, the speaker does allude to the validation of certain theoretical aspects through practical experiments.

Specifically, the presentation states that the "conditional dependence relationship is also verified in in our experiments." This refers to the first key quantity identified in the information-theoretic error term, which measures the conditional dependence or independence of the input X and label Y given the intermediate representation Z. The implication is that practical experiments confirmed that when Z (e.g., captions) provides sufficient information to mediate the relationship between X (images) and Y (labels), ZSP performs well, aligning with the theoretical prediction of low conditional dependence error. Conversely, if Z is insufficient, ZSP's performance degrades, confirming the theoretical limit.

The models mentioned in this context are CLIP (Contrastive Language-Image Pre-training) and ViT-L-14 (Vision Transformer Large, patch size 14). These are widely recognized multimodal models, where CLIP, in particular, is a quintessential example of the type of embedding model that enables ZSP. The experiments likely involved comparing the performance of ZSP using these models to the predictions derived from the conditional dependence term, potentially by manipulating the information content of Z or the relatedness of X, Y, and Z in various classification tasks.

While the talk emphasizes that exact convergence rates are "method-specific" and that "there are examples done in the paper," it does not provide headline numbers, specific dataset names, hardware configurations, or detailed ablation studies within the verbal presentation. The intention is to provide a general roadmap for theoretical analysis, with the specifics to be found in the accompanying research paper. Therefore, this section acknowledges that experimental verification exists for some theoretical claims, particularly regarding the role of conditional dependence, utilizing prominent multimodal models like CLIP and ViT-L-14, but details on the full experimental setup and quantitative results are beyond the scope of this conference talk.

Practical Implications

▶ Watch: Second key quantity: prompt bias term in ZSP analysis (8:20)

This generalization theory for zero-shot prediction (ZSP) carries significant practical implications for a wide range of stakeholders in the AI/ML ecosystem, from model builders and infrastructure teams to practitioners deploying these systems.

For practitioners and model builders, this work provides a crucial roadmap for theoretical analysis of their specific ZSP methods. Instead of relying solely on empirical trial-and-error, they can now align their approach with one of the proposed proof strategies (e.g., the similarity score function approach) to derive method-specific generalization bounds. This enables a more principled understanding of when and why their ZSP solution will succeed or fail. It encourages a shift from purely empirical observation to theoretically informed design, potentially leading to more robust and predictable ZSP systems.

The identification of the four key quantities offers actionable insights:

1. Conditional Dependence (X, Y given Z): This highlights the fundamental limitation of ZSP. If the intermediate representation Z (e.g., natural language captions) cannot adequately bridge the information gap between the input X and the target label Y, ZSP will inherently underperform direct supervision. Practitioners must critically evaluate if the chosen Z truly captures the necessary semantics for their task. This might guide choices in pre-training data curation (to ensure Z is rich enough) or even suggest tasks where ZSP might be fundamentally unsuitable.
2. Prompt Bias Term: This emphasizes the critical importance of distribution alignment. For ZSP to be effective, the pre-training data (Q_XZ), the prompting strategy (rho_YZ), and the target task distribution (P_XY) must be compatible. Infrastructure teams and model builders should focus on sourcing or generating pre-training data that is semantically relevant to potential downstream tasks. Similarly, prompt engineers must design prompts that accurately reflect the Y-Z relationship present in the target domain, rather than just generic descriptions. Misalignment here is a source of irreducible error.
3. Sample Complexity (N): This term quantifies the impact of the pre-training dataset size. It reinforces the intuition that larger and more diverse pre-training datasets (leading to better R-hat estimators) are crucial for robust ZSP. Infrastructure teams deploying foundation models need to ensure sufficient computational resources for pre-training on massive datasets to minimize this error component.
4. Prompt Complexity (M): This term underscores the value of prompt engineering and ensembling. A higher number of diverse and well-crafted prompts (M) for each class can significantly reduce the statistical error associated with approximating the true prompt distribution (rho). Practitioners should invest in sophisticated prompt generation techniques, including multiple templates, class-specific conditioning, and ensemble methods, to improve ZSP performance.

Tradeoffs and Limitations:

The framework implicitly highlights several tradeoffs. While ZSP offers significant resource savings by avoiding labeled training data, it comes with an inherent information-theoretic gap compared to direct supervision. This means that for tasks requiring extremely fine-grained distinctions not easily captured by an intermediate representation Z, ZSP might never reach the accuracy of a fully supervised model. Practitioners must weigh the cost savings against this potential performance ceiling.

Furthermore, the theory, while general, requires aligning a specific ZSP method to one of the proposed proof strategies. Deriving concrete numerical bounds and convergence rates still necessitates detailed analysis for each particular model architecture (e.g., specific transformer variants, embedding dimensions) and dataset. The talk itself acknowledges that exact rates are "method-specific," implying that applying this theory still requires significant analytical effort.

Finally, the reliance on population distributions (f-bar) for the information-theoretic error assumes these distributions are well-defined and discoverable, which might not always be straightforward in complex real-world scenarios. Despite these considerations, the framework provides an invaluable lens through which to understand, diagnose, and strategically improve the design and application of zero-shot prediction systems powered by foundation models.

Key Takeaways

• Decomposition of Generalization Error: The generalization error in Zero-Shot Prediction (ZSP) can be rigorously decomposed into an information-theoretic error (representing fundamental limits) and a statistical learning error (from finite samples and prompts).
• Four Essential Quantities: ZSP's success is governed by four key quantities: conditional dependence (of X, Y given Z), prompt bias (incompatibility of distributions), sample complexity (from pre-training data size N), and prompt complexity (from number of prompts M).
• Roadmap for Theoretical Analysis: The talk provides a formal theoretical framework and two distinct proof strategies, offering practitioners a systematic approach to analyze the generalization capabilities of their specific ZSP methods.
• Fundamental Limits of ZSP: The information-theoretic error highlights that ZSP's performance is fundamentally limited by how well the intermediate representation (Z) captures the necessary information to mediate the X-Y relationship, and by the alignment of pre-training, prompting, and target task distributions.
• Impact of Data and Prompts: The statistical learning error components underscore the importance of both the quantity of pre-training examples (N) for learning robust embeddings (e.g., CLIP) and the quality/quantity of prompts (M) for accurate zero-shot classification.
• Guiding Principled Development: This theory moves beyond empirical observations, providing a principled foundation for understanding, diagnosing, and optimizing ZSP systems, enabling more informed design choices for model builders and deployers.

About the Speaker(s)

Ronak Mehta is the primary speaker for this presentation at ICML 2025. He is the lead researcher on this work, which represents a significant contribution to the theoretical understanding of zero-shot prediction.

Zaid Harchaoui is Ronak Mehta's advisor and co-author on this research. His involvement highlights his expertise and guidance in the development of this theoretical framework for analyzing generalization in foundation models.