# Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes

arXiv: https://arxiv.org/abs/2205.13068 · HTML: https://mlsanity.com/paper/2205.13068/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 62 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 27 of 27)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Conditional Generative Adversarial Nets](https://mlsanity.com/paper/1411.1784/) (2014)
- [Multitask Prompted Training Enables Zero-Shot Task Generalization](https://mlsanity.com/paper/2110.08207/) (2021)
- [Zero-Shot Learning -- A Comprehensive Evaluation of the Good, the Bad and the Ugly](https://mlsanity.com/paper/1707.00600/) (2017)
- [Taking A Closer Look at Domain Shift: Category-level Adversaries for Semantics Consistent Domain Adaptation](https://mlsanity.com/paper/1809.09478/) (2018)
- [Feature Generating Networks for Zero-Shot Learning](https://mlsanity.com/paper/1712.00981/) (2017)
- [Zero-Shot Learning Through Cross-Modal Transfer](https://mlsanity.com/paper/1301.3666/) (2013)
- [Evaluation of Output Embeddings for Fine-Grained Image Classification](https://mlsanity.com/paper/1409.8403/) (2014)
- [Label-Embedding for Image Classification](https://mlsanity.com/paper/1503.08677/) (2015)
- [f-VAEGAN-D2: A Feature Generating Framework for Any-Shot Learning](https://mlsanity.com/paper/1903.10132/) (2019)
- [A Review of Generalized Zero-Shot Learning Methods](https://mlsanity.com/paper/2011.08641/) (2020)
- [Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs](https://mlsanity.com/paper/1803.08035/) (2018)
- [Learning a Deep Embedding Model for Zero-Shot Learning](https://mlsanity.com/paper/1611.05088/) (2016)
- [Semantic Autoencoder for Zero-Shot Learning](https://mlsanity.com/paper/1704.08345/) (2017)
- [Rethinking Knowledge Graph Propagation for Zero-Shot Learning](https://mlsanity.com/paper/1805.11724/) (2018)
- [Multi-modal Cycle-consistent Generalized Zero-Shot Learning](https://mlsanity.com/paper/1808.00136/) (2018)
- [Leveraging the Invariant Side of Generative Zero-Shot Learning](https://mlsanity.com/paper/1904.04092/) (2019)
- [Zero-Shot Learning via Semantic Similarity Embedding](https://mlsanity.com/paper/1509.04767/) (2015)
- [Unsupervised Domain Adaptation with Similarity Learning](https://mlsanity.com/paper/1711.08995/) (2017)
- [Predicting Deep Zero-Shot Convolutional Neural Networks using Textual Descriptions](https://mlsanity.com/paper/1506.00511/) (2015)
- [Zero Shot Recognition with Unreliable Attributes](https://mlsanity.com/paper/1409.4327/) (2014)
- [Predicting Visual Exemplars of Unseen Classes for Zero-Shot Learning](https://mlsanity.com/paper/1605.08151/) (2016)
- [Zero-Shot Learning with Common Sense Knowledge Graphs](https://mlsanity.com/paper/2006.10713/) (2020)
- [Optimally Combining Classifiers Using Unlabeled Data](https://mlsanity.com/paper/1503.01811/) (2015)

## Abstract (arXiv)

We develop a rigorous mathematical analysis of zero-shot learning with attributes. In this setting, the goal is to label novel classes with no training data, only detectors for attributes and a description of how those attributes are correlated with the target classes, called the class-attribute matrix. We develop the first non-trivial lower bound on the worst-case error of the best map from attributes to classes for this setting, even with perfect attribute detectors. The lower bound characterizes the theoretical intrinsic difficulty of the zero-shot problem based on the available information -- the class-attribute matrix -- and the bound is practically computable from it. Our lower bound is tight, as we show that we can always find a randomized map from attributes to classes whose expected error is upper bounded by the value of the lower bound. We show that our analysis can be predictive of how standard zero-shot methods behave in practice, including which classes will likely be confused with others.