This paper analyzes how generalization works in meta-learning. Our core contribution is an information-theoretic generalization bound for meta-learning, which identifies the expressivity of the task-specific learner as the key factor that makes generalization to new datasets difficult. Taking inspiration from our bound, we present Discrete InfoMax Codes (DIMCO), a novel meta-learning model that trains a stochastic encoder to output discrete codes. Experiments show that DIMCO requires less memory and less time for similar performance to previous metric learning methods and that our method generalizes particularly well in a challenging small-data setting.
This paper presents DIMCO, a meta-learner that is trained by maximizing mutual information between a discrete data representation and class labels across tasks. DIMCO is inspired by an information theoretic lower bound on the generalisation gap for meta-learning, which the authors argue identifies overfitting in the task learner as the bottleneck. 
This work proposes to constrain a learner to output discrete codes that are learned to capture the mutual information with class labels. While the idea of using discrete codes is interesting, its presentation in the manuscript is not well motivated and at times hard to follow. This makes it challenging to evaluate the novelty, validity, and generality of the proposed approach. Meanwhile, the empirical evaluation is somewhat lacking. Thus, I do not believe this work is ready for publication in its current form.
Detailed comments
My main concern is with respect to the primary contribution of this paper, a generalisation bound on meta-learning. The bound appears to be on a multi-task loss without task adaptation, and thus the claims made with respect to the theorem seem somewhat over-reaching. I also believe the VC-dimensionality of the encoder is missing in Eq. 4? If so, this changes the interpretation since the length of the code and the expressivity of the encoder are interrelated. Further, I would welcome a deeper analysis of the theorem and its implications. The current interpretation states that the number of tasks is independent of the size of each task, hence given many tasks, using minimal representations is an effective approach to meta-generalisation. Yet minimal representations is a well-known idea and has features in several works that use mutual information as a regularizer, most notably works on the Information Bottleneck. 
Another reservation I have is the use of mutual information between encoder representations and class labels as a loss function (Eq. 1). It lacks context and a proper motivation, especially since the analysis of [1] shows that the loss function in Eq. 1 is the cross-entropy objective. The authors make a similar analysis in Appendix A and argue that Eq. 1 differs in that cross-entropy is an approximation because it adds a parametrized linear layer on top of \tilde{X}. Thus, in the absence of that layer they collapse to the same objective. As DIMCO itself directly extract class label predictions from \tilde{X}, I fail to see a difference between the loss in Eq. 1 and a cross-entropy objective. 
The main motivation behind their loss objective is that it does not require a support / query set. This does not seem to be a feature of the mutual information objective itself, but rather a choice made by the authors. I would have liked a deeper discussion of this seeing as the authors make it a central tenet of DIMCO. Prior works use a support set as a principled means of doing meta-learning: meta-training explicitly takes into account that at test time, the learner will be given a small support set from which to learn how to query points. As far as I understand, DIMCO does not take this into account during meta-training.  At meta-test time however, DIMCO does use a support set to map query points (Eqs. 10 and 11). Why should we break protocols between meta training and testing? Are there any downsides to doing so?  
Empirically, I find the CUB experiment compelling but would welcome some ablations. What are the trade-offs between p and d? Can DIMCO outperform N-pair when number of bits are unconstrained?
miniImagenet is a standard benchmark in few-shot learning, but I am unable to find a results table - could the authors please provide results on the standard setup so that the method can be compared against known baselines? Further, would the results currently presented hold in a N-way-5-shot setup?
As for the constrained version of miniImagenet that the authors propose, I am not convinced this is an interesting protocol. In general, the miniImagenet task distribution is created by N-way permutations of the classes in the meta-set (e.g. meta-training tasks are combinations of the 64 classes in the meta-training set). By keeping the number of classes constant but reducing the number of images per class, this protocol is not reducing samples per task: a task is always defined as 5/20-way-1-shot (Fig. 4). Instead, the effect should be that tasks are in (greater) violation of the task i.i.d. assumption. Thus, I question whether this setup demonstrates the trade-offs the authors present in Theorem 1 and whether the results can be interpreted in light of it. 
Finally, that both experiments are image-based raises questions as to the generality of the method. The paper could be considerably strengthened by evaluating DIMCO on a non-image task, or if not discuss the method’s limitations.  
The idea of discrete codes for few-shot classification is interesting and sufficiently novel, I am likely to increase my score if my concerns are addressed and the experimental section is strengthened.
Further questions and comments:
- I am unable to parse Eq. 11 - what does the notation \prod_i p_{\tilde{x}_i, i} mean? 
- It is unnecessarily hard to follow the proof of theorem 1. It would help the reader if you restated relevant definitions, such as Eq. 1, since the difference with Eq. 23 is very subtle. It would also be helpful to explain how the summand in Eq. 25 differs from either, and Eq. 26 could be expanded or briefly explained after the derivation. 
-  Because DIMCO is trained with backpropagation, the interpretation of Eq. 5 as d independent events seems invalid. How does it affect the method if they are not independent?
- Overloading X and Y as both random variables and mini-batch samples creates unnecessary confusion. I believe the objective in Eq. 1 is approximated, not calculated exactly? For instance, the mutual information in Eq. 8 is with respect to a mini-batch, so should it not be \hat{I}? 
- p^j_{ik} in Eq. 9 is undefined.
- Eq. 9 is interpreted as an exact entropy, however it appears to be a mini-batch approximation to the true entropy? 
References 
[1] Achille and Soatto. Emergence of Invariance and Disentanglement in Deep Representations. JMLR. 2018.