Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a method to quantify the complexity of a learning task. The paper is motivated from the “20 questions“ game where an agent computes the answer (label) via a sequence of questions asked on the input data with answers given by an Oracle (simple functions of the data, in this case). The authors formalize this process and define the complexity of a learning task as the smallest number of questions from a given set Q necessary to predict the labels accurately averaged across the dataset. Information Pursuit (IP) of Geman & Jedynak 1996 is used to instantiate this definition using variational and normalizing-flow based models to learn the conditional distributions. Experimental results are shown for MNIST, Fashion-MNIST, KMNIST and Caltech Silhouettes datasets.

The main intellectual novelty of the paper is to define the complexity of a learning task using the number of questions. This comes with certain caveats that are discussed in the detailed comments below. While the paper is understandably a first step in this interesting program, more crisp experimental results are necessary before we can ascertain the utility of these ideas.

Detailed comments.

1. I have a philosophical gripe about this framework. It is widely observed that ensembles of decision trees which have been expanded until there is only sample at each leaf or, more recently, over-parameterized deep networks generalize better for machine learning tasks. The definition of task complexity developed in this paper does not relate to “learning” tasks. Indeed the complexity of the same task under decision made by above over-complete decision tree would be very large. The present paper is an attempt at computing the complexity of the conditional distribution p(Y | X) using a different “basis” that comes from the Oracle’s answers to the queries.
2. The complexity of a learning task should also be a function of the hypothesis class that is being used for the task. This is exactly the benefit for using quantities like VC-dimension. Why not, for instance, define the complexity of a task as the minimum-description-length (MDL) of the model that achieves at least a generalization gap of epsilon? Indeed, the prior over the hypothesis class in MDL is similar to the prior over the query set Q in this paper. There is recent work that captures the complexity of transfer learning while incorporating the hypothesis class, e.g., https://arxiv.org/abs/2011.00613, that the authors could seek synergies with.
3. The above two points are also seen in the claim about sub-additivity. Sub-additivity is a difficult property to have in general. If the tasks Y1 and Y2 conflict with each other, e.g., if they do not share any features and the model does not have sufficient capacity to learn both sets of features then the complexity of learning the two tasks simultaneously tasks should be _larger_ than the sum of their individual complexities.
4. The factorization in (8) need not be assumed. Since variational Bayes is used to approximate the true distribution on the left-hand side, one may simply say that the right-hand side is a particular variational family. This also applies to the paragraph above Fig. 3.
5. More refined experimental evidence is necessary before we can understand the merits of this definition. I find the current results difficult to appreciate, e.g., MNIST-0.05 and MNIST-0.1 should essentially have the same test error using any off-the-shelf CNN. Why is there is a gap between the relative test accuracy around, say, epsilon = 10 in Fig. 3a? I suspect this is an artifact of the variational/normalizing flow framework which does not learn good representations with noisy data and thereby results in a degradation of the validation error.
6. The learning task for classifying images in MNIST-translated should have the same complexity as that of MNIST because CNNs are translationally invariant. That this definition leads to a higher complexity for the former indicates that the setup where the agent searches for patches of input images is the real reason for this seeming increase in complexity.
7. It would be good to compare the ordering in complexity of these tasks using some other baseline method in the literature to compute the task distance, e.g., Task2Vec.
review_title: Review of "Quantifying Task Complexity Through Generalized Information Measures"

final_score: rating: 5: Marginally below acceptance threshold
review_content: This proposes a new measurement for the complexity of learning tasks. The proposed method measures the complexity of a learning task by the minimum expected number of questions that need to be answered to solve the task.

Strengths:  
The idea of using the minimum expected number of questions that need to be solved for measuring the task complexity is an interesting idea to me.
The paper provides theoretical justifications and connections with existing information theories. 
The paper is generally clear and well constructed.

Weakness:
The experimental analysis is weak, only a simple case study is provided in the paper. 
review_title: An interesting paper

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper claims that existing measures of complexity such as entropy are not suitable for measuring task complexity since they focus on the complexity of X rather than the predictive relationship from X to Y. The paper argues that mutual information is not useful for comparing different learning tasks, as two tasks (MNIST vs Fashion-MNIST) can have similar MI but intuitively different complexity (second-to-last paragraph in related work). The paper proposes a measure for task complexity based on the number of queries required to predict a label of an input. The form of the queries is not specified, and the provided examples include half-space queries, single feature (decision-tree-like) queries, or high level semantic queries.  The proposed method instead considers a query generator E, then encoding X as the answers to the sequence of queries generated by E, and predicting Y from the answers. The complexity of a task is related to the number of equivalence classes induced by the input X and the query generator E.

I think the general premise is interesting, although I am not familiar with the related work (eg Achille, Tran) so I can't comment on how novel or different the idea of this paper is. Although the paper claims to have the first subjective notion of task complexity, to me this seems like more of a drawback since measures of complexity should be as standardized as possible, so as to allow comparison between different works. It may have been useful to cement down the three versions of complexity described on page 2, so future works can use them directly (for example provide details of measuring visual semantic complexity; and if it relies on extracting latent features of a neural net, i also wonder how close/different this is to [Achille]). 

Also, the paper claims the drawback of Kolmogorov complexity is that it is not easily computable, but the methods described to compute the paper's proposed complexity are also highly involved, and requires multiple layers of approximations. It would have been helpful to have a more in-depth discussion of how (if at all) the proposed method is easier computationally compared to the other methods.

In proposition 1, epsilon seems not to have been motivated yet? The task complexity in Eq2 did not seem to have any notion of error, so why is there a probability of misclassification in prop 1?

The notation in Equation 1 looks off to me, since the RHS conditions on the set of all x's with the same encoding. Don't we want something to the effect of: p(y|x) = p(y|x')  for all x, x' such that A_q(x) = A_q(x') \forall q ?

The prefix-free constraint seems like it can be avoided if we just include q_STOP in the code? This seems more natural to me, and you can avoid the extra notation and sentences of explanation on the bottom of page 3.

Condition 2 in Prop3: we are assuming that y is categorical, and p_{Y|X=x} is a distribution over the labels in Y? Or does p_{Y|X=x} have all its probability mass on a single label? I assume it is the latter case, but writing it in terms of two inputs disagreeing \forall labels y is confusing when they are only assigned to one label each (in fact, shouldn't it be \exists y where x and x' disagree, instead of \forall y?).

I also didn't quite understand how the conditional inference network takes in {q, A_q(x)}_{1:k}. Isn't this not a fixed length sequence, in fact we don't even know the length of it beforehand since we decide when to stop at runtime based on the stopping condition? So in Fig2, how are the \Psi's able to take in variable-length sequences?

I'm curious about the exact cost of each iteration of the information pursuit algorithm. Given p(A_q(x), y | B) in Eq.9, do you compute p(A_q(x) | B) and p(y | B) exactly to get the mutual information, or do some sample-based approach? How many values can A_q(x) take on? And we need to do this for every possible query q \in Q in order to get argmax_q, so if A_q(x) can take on m values, are you doing O( |Q| m ) number of queries of the distribution p?

On the point of mutual information not being directly useful to predict difficulty in mapping X to Y, it seem that this paper "A Theory of Usable Information under Computational Constraints" Xu et al. [ICLR 2020] is very relevant. For example under a limited computational model, perhaps MNIST will have higher mutual information than Fashion-MNIST.
review_title: Review

Meta-review: This paper proposes a measure of task complexity based on a decision-DAG like "encoder" where we iteratively branch on some test on the input and the selection of future tests depends on the answer to previous tests until we reach a terminal node in the DAG.  We require that if $x$ and $x'$ reach the same terminal node then $P(y|x) = P(y|x')$.  The complexity of the task (the complexity of the distribution $p(x,y)$) is the minimum over all such DAGs of the expected depth of the terminal node for $x$ when drawing $x$ from the marginal $p(x)$.

The reviewers are not enthusiastic and I agree.
Decision: Reject