Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies a problem related to zero-shot learning. It aims to answer the question of what is the worst case performance of a classifier, if only given a binary attribute-class association matrix. The lower bound is expressed as a linear program that computes the maximum correlation between any pair of attributes. The paper presents a tight lower bound that can predict the performance of the best classifier given true attribute information of the inputs. However, there are also concerns that the problem being studied is too simple and constrained.
strengths_and_weaknesses: --------------------------
Strengths

- The paper studies a simplified problem that frequently occurs in zero-shot learning and gives insight on when we expect the model to generalize to unseen classes that are defined by an attribute-class matrix.

- The paper shows that the bound is tight.

- The experiments show that the theory predicts the behavior relatively well, especially on adversarial distributions.

-------------------------
Weaknesses

- The theory in the paper generates an intuitive explanation for binary classification (n=2). However, the linear program in general is hard to give an analytical interpretation.

- Although the paper title mentions ZSL, the paper itself actually does not explicitly deal with ZSL but studies a much simpler form of error bound on using only input dimension statistics (probability of attribute i given class j). There might be a lack of mathematical depth for such a constrained problem.

- The assumption might not be realistic enough. Many problems often give a couple attributes that “define” the class, rather than providing full statistics that span across all attribute dimensions. Many attributes are ones that we “don’t care”, and could be spurious attributes if they are provided to the classifier. For example, most of the zebras are on grass, and they are rarely in water. However, we shouldn’t consider these attributes in the classifier even if p(“grass” | zebra) might be close to 1.0, and p("grass" | other animal) is small. This leads to the spurious feature problem, and the hope is that if we could learn disentangled attributes from the space, then it could be solved by focusing only on causal attributes. Now, with the framework presented here, it would be nice if it could be extended to cases where some entries in A are “don’t care”, which motivates the original formulation of ZSL. This might be a trivial modification to the paper but could make the setup more realistic. In the end, attribute-based ZSL should focus on attributes that define the class instead of attributes that correlate with the class.
questions: - Why would the adversarial distribution generate a better error rate for other methods? Could you give an example of what the adversarial distribution looks like?

- Is it correct to understand that all methods use images as input except the lower bound “Q”?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a tight lower bound for attribute-based zero-shot learning based on the class-attribute matrix. When compared with previous bound from limit amount of work studying this, the proposed bound is the first non-trivial tight lower bound.  The proposed bound is empirically validated with several methods on popularly used benchmark datasets, and can be also used for pairwise misclassification prediction. 
strengths_and_weaknesses: Strengths
- First right non-trivial bound for attribute-based zero shot learning
- Good empirical study to demonstrate the bound and its application
- Source code provided 

Weakness
- How can this bound used for improve zero-shot learning in addition to the pairwise misclassification prediction?
- Any relationship between pairwise misclassification from this method and from confusion matrix? (PS: I know there is no samples for unseen class)
questions: - Application of the bound, can it be used to improve the zero-shot learning performance? Or come up with new methods?
limitations: - This bound reveals the importance of class-attribute matrix, which itself is very hard to obtain in real-world application
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the generalization of zero-shot learners with access to attributes. In this work, zero-shot learning is decomposed into two stages as is typically done in practice. The first stage consists of learning to extract attributes from input data. In the second stage, new classes are presented and must be classified using the attribute information that was extracted during the first stage. The results presented in this paper are applicable to the second stage under the assumption that attribute extraction can be learned perfectly.

The authors derive the Bayes optimal classifier for this second stage in terms of an unknown joint distribution over attributes and labels. By considering constraints on this joint distribution in terms of the class-attribute matrix, they are able to produce a lower-bound, $Q$, on the error of a Bayes optimal classifier. A linear program is then designed whose optimal solution corresponds to this $1-Q$. They solve this LP for balanced binary classification and show that the lower-bound is tight in this case.

The authors then show that this lower bound is tight in general by showing that a randomized attribute-class classifier can be designed whose error is upper-bounded by the lower bound. Moreover, this classifier can be computed as the solution of a linear program.

The empirical analysis confirms the theoretical findings on a number of standard ZSL classification problems. Two sets of experiments are conducted: first using the standard ZSL setup, and second using synthetic attribute labels that are generated to match the class-attribute matrix for each task. The lower bound is respected in both cases.

**Post-rebuttal:** Following the author's response, I have increased my score from Weak Accept to Accept. After reviewing the literature referenced by the authors, I am in agreement that the results are a great contribution than I thought them to be initially.
strengths_and_weaknesses: ## Strengths

ZSL is a particularly difficult area to establish theoretical results in. To my knowledge, the results presented in this work are novel and make progress towards understanding theoretical limitations of ZSL.

The empirical analysis is practically relevant and thorough. The authors evaluate their theoretical results on a good range of ZSL tasks. Further, they actively work towards matching the settings with their theoretical assumptions in their second set of experiments.

## Weaknesses

Results are interesting albeit simple in nature. The authors assume that the first stage of learning has been absolutely successful and the attribute functions have been recovered. They then analyze the worst-case error for the second phase where a classifier is learned from the attributes to classes. This is interesting and valuable but it excludes one of the key tenets of zero-shot learning: that some classes have no instances available at training time. This is addressed in the first phase of learning and is, arguably, the more interesting part of the ZSL paradigm. It is possible that the authors analysis can play a role in understanding the full ZSL pipeline, but no effort is made to understand this and I expect that the linear programs are too rigid to account for the necessary changes.

The authors are essentially studying classification with boolean functions with an additional distributional assumption. This is not an area of the literature that I know exceedingly well, but I would expect a discussion from the authors within their paper. Even initial work in this setting [1] capture the binary version of the classification problem that the authors consider.


[1] A theory of the learnable. L. Valiant. Artificial Intelligence and Language Processing, 1984.
questions: My main concern with this work is the extent to which the results generalize to the true ZSL setting where there is a distribution shift and the attribute functions must be learned. I am also concerned that the results presented may already be known within the boolean function learning literature --- I hope that another reviewer has greater expertise in this area or that the authors themselves can comment on this comparison.

The authors write that "this result also formally proves that for binary classification, the worst-case is determined by a single attribute, and there is no compounded benefit in having multiple attributes". This statement is entirely dependent on the fact that all attribute functions are assumed to be given to the classifier. In a true ZSL setting, where these attribute functions must be learned, some attributes may be easier to recover than others and so we would certainly expect a compound effect from having access to multiple attributes.

### Minor comments

Minor comments:

I personally find the concatenation notation to be confusing as it could be mistaken for a product. Perhaps consider adopting `[v, v']`, `cat(v, v')` or similar.

Some extra structure (e.g. paragraph headings) in the preliminary chapter could make things easier to parse.

Before Equation 3, I would have found it useful to include a brief explanation in words of the optimal binary classifier. Something like: "In words, the optimal classifier chooses the class which is most likely under the given attribute configuration."

- L255: "A[n] attribute-class classifier"
limitations: The authors provide a thorough and balanced discussion of the limitations of their work. Here I include some additional minor suggestions.

The bounds presented are of the maximum of the minimum and not the more common minimax risk. The latter is more common in learning theory, as we want to know the performance of the best *learning* algorithm on the hardest problem we consider (thus the learner is problem-agnostic). The bound presented ignores learning and lower-bounds the best performance of a perfect classifier with all information of the task. In this case, by von Neumann's minimax theorem the two are equivalent (as is used in the proofs in the appendix). Perhaps this could be further discussed.

Assuming access to the attribute functions is a strong assumption that moves away from the core of ZSL. The first stage of ZSL is typically to recover this attribute mapping. This two-stage decomposition is represented accurately in the fourth paragraph of the introduction, in the preliminaries. This limitation of the work is discussed in Section 6. It would be valuable to discuss this limitation in terms of the theoretical results that are presented too. What needs to be done to address both stages of learning? To what extent can errors in the attribute functions be incorporated into the proofs? Where does this fail?
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Authors derive a new bound for zero-shot learning (ZSL) corresponding to the worst-case Bayes Error, taken across all distributions that satisfy some given attribute-class matrix. The bound assumes access to a perfect item-to-attribute mapping. Authors show that computing the derived bound amounts to solving an LP problem. Authors show that this problem admits a closed-form solution in the binary case (given along with the expression of the actual classifier that achieves that bound), and can be approximated in the multi-class setting. They also show that the bound is tight in general.
strengths_and_weaknesses: ## Strength

- The paper is well written. As a non-expert for ZSL, I can say the notations and ideas were well introduced, and easy to follow. The proper amount of background on the problem was introduced.

- The general problem of formally characterizing the difficulty of a zero-shot problem is an interesting one.

- The work appears substantial to me. The formalization of the problem, the bound/its computation and the tightness results seem non-trivial and novel.

- The result in the binary case appears non-trivial and could already be of practical relevance. If I understand correctly, authors provide a closed-form expression of a classifier $g_a(\textbf{v})$ that is essentially optimal, independently of the distribution, i.e optimal $\forall ~ p, ~ p \in \mathcal{P}(\textbf{A})$. The classifier has a simple expresison that can be readily computed from the class-attribute matrix $\textbf{A}$.

## Weaknesses (c.f Questions below)

C.f questions below

questions: ### Interpreting experimental results

The first row of Fig.1 is quite hard to interpret, because a large part of the gap between the lower bound and methods seems to be due to the poor item-to-attribute mapping generalization. I find the set of adversarial experiments more interesting. However, some methods do go below the lower bound, which lets me think that the actual "best" classifier could further 'break' the theoretical lower bound. Is this due to sampling / approximate computation of the bound in the multi-class setting ? Could authors clarify ?

### Motivating the use of worst-case bounds

I believe I'm not super clear with the motivation of using worst-case bounds for ZSL. The bound considers the performance of the best possible classifier in the worst-case distribution. However in practice, how likely is this to happen (such that the bound actually applies) ? The results on SUN dataset for instance, clearly show that the lower bound is way above most methods (even with the presence of training/testing shift), and the gap keeps increasing as the number of attributes increases. Would best-case lower bounds be trivial here? i.e. given some $\textbf{A}$, how well could any method achieve, assuming the 'easiest' distribution compatible with $\textbf{A}$ . I'd be curious to hear authors' thoughts.

### Sanity checking

Binary results would have been easier to sanity check / interpret, because less confounding factors. In particular, given that the found value Q neither depends on a particular distribution or on the number of attributes, there would be no need to adversarially choose the distribution or to worry about approximating Q, and a direct apple-to-apple comparison would have been possible. Is there any particular reason for not experimenting in a binary situation ?




limitations: Authors do discuss that the bound assumes perfect item-to-item mapping, which is far from true in real life. Authors also discuss the difficulty associated with computing the bound (scaling to multi-class and to multiple attributes).
review_title: null

Meta-review: metareview: The paper provides a lower bound on the error attainable by a zero-shot learning method in terms of a linear program involving the class-attribution matrix which is provided as side-information.  All the reviewers agree that the analysis is novel and studies an important problem. The main concerns are that: a. the problem itself is studied in a highly constrained setup, b. hard to understand the exact insights from the result, and how it could be used to further the state of the art. 
In particular, it would be important to tone down some of the claims, and clarify to the reader that the claims are in context of the considered problem setup only. 
confidence: Certain
Decision: Accept