A Generalization Theory for Zero-Shot Prediction

Ronak Mehta, Zaïd Harchaoui

TL;DR

This paper introduces a theoretical framework to understand zero-shot prediction (ZSP), a paradigm where models predict outcomes for unseen tasks without direct training data. The authors decompose ZSP performance into "prompt bias" and "residual dependence," providing a theoretical lens to analyze why and how ZSP works, and offering guarantees for its generalization ability.

What Problem Does This Paper Address?

The rapid success of foundation models like CLIP has revolutionized zero-shot prediction (ZSP), enabling models to perform tasks they weren't explicitly trained for, often by leveraging natural language prompts. However, the theoretical underpinnings of this phenomenon remain largely unexplored. Existing work in few-shot learning (FSL) assumes access to some labeled data for downstream tasks, a luxury ZSP doesn't afford. This paper aims to bridge this gap by developing a theoretical framework that explains ZSP's generalization ability, specifically by analyzing the interplay between pre-training data, evaluation data, and the prompting strategy. The core question is: how can we theoretically compare ZSP to direct supervised learning and understand its performance based on these components?

Methods

The authors propose a theoretical framework for ZSP by modeling it as an indirect, multi-stage prediction process. They introduce two key concepts:

  • Conditional Mean Approach: This approach leverages the pre-training data to learn a conditional mean operator and uses prompts to approximate a target function.
  • Information Density Approach: This approach focuses on learning the information density (a measure of dependence between modalities) during pre-training and uses prompts to approximate an expectation.

They derive a decomposition of the prediction error into three components:

  1. Prompt Bias: Measures the compatibility of the prompt strategy with the pre-training and evaluation distributions.
  2. Residual Dependence: Quantifies the information-theoretic cost of using one modality (e.g., text) to make predictions about another (e.g., images).
  3. Estimation Error: Accounts for the finite number of pre-training examples and prompts.

The paper also introduces theoretical tools like the conditional mean operator, information density, and mean square contingency to formalize these concepts. They provide finite-sample bounds for nonparametric regression methods under these approaches.

Datasets

The paper mentions the following datasets:

  • ImageNet-1k: Used for evaluation in experiments.
  • ImageNet-Captions: Used for experiments to understand prompt bias.
  • Describable Textures Dataset (DTD)
  • Flowers 102
  • FGVC Aircraft
  • SUN397

The paper does not introduce new datasets but utilizes existing ones for empirical validation.

Key Insights and Ideas

  • ZSP as an Indirect Prediction: The paper frames ZSP not as direct prediction, but as a multi-stage process where information is transferred through intermediate representations (e.g., text embeddings).
  • Decomposition of Error: The breakdown of ZSP error into prompt bias, residual dependence, and estimation error provides a clear roadmap for understanding and improving ZSP systems.
  • Prompt Bias is Crucial: The theoretical analysis highlights that the choice of prompts significantly impacts performance, especially when the pre-training and prompting distributions are not perfectly aligned.
  • Residual Dependence as a Fundamental Limit: The "residual dependence" quantifies the inherent difficulty of transferring knowledge between modalities, setting a theoretical limit on ZSP performance.
  • Two Complementary Theoretical Views: The conditional mean and information density approaches offer distinct but complementary ways to theoretically analyze ZSP, each with its own strengths and statistical properties.

Key Results

  • The paper provides theoretical guarantees for ZSP, showing that its performance can be decomposed into prompt bias, residual dependence, and estimation error.
  • Empirical results (Figure 2) demonstrate that as residual dependence (I(X; Y|Z)) decreases, the performance of ZSP predictors (CLIP, VICReg) approaches that of a direct predictor.
  • Experiments (Figure 3) show that unbiased prompting strategies can significantly outperform template-based methods, especially when the number of prompts is sufficient.
  • The paper offers theoretical bounds for both the conditional mean and information density approaches, providing insights into their sample complexity and convergence rates.

Limitations and Future Work

  • Mis-specified Case for Radon-Nikodym Derivative Estimation: The paper acknowledges that the mis-specified case for Radon-Nikodym derivative estimation is less understood and suggests it as an area for future research.
  • Distribution Shifts: The authors suggest extending the analysis to account for distribution shifts between pre-training and downstream distributions.
  • Causal Generative Modeling: Future work could explore the connection between ZSP and causal generative modeling.
  • Practical Implementation of Theoretical Bounds: While theoretical guarantees are provided, bridging the gap to practical, efficient implementations remains an ongoing challenge.

Summary updated

BibTeX
@inproceedings{mehta2025generalization,
  author = {Ronak Mehta and Zaïd Harchaoui},
  title = {{A Generalization Theory for Zero-Shot Prediction}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=kJQgMGLrow},
}
Figure