Title: DISCRETE INFOMAX CODES FOR META-LEARNING Anonymous authors Paper under double-blind review

Abstract: 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.

1. INTRODUCTION:

Generalizing to unseen data is a problem of vital importance in machine learning. Many deep metalearning methods optimize for generalization by directly minimizing the loss of held-out validation data. Recent works have used this framework to achieve impressive feats such as learning to classify using one labeled image per class (Snell et al., 2017; Finn et al., 2017) , learning unsupervised update rules that generalize to different domains (Metz et al., 2018) , and accelerating training procedures that are millions of steps long (Flennerhag et al., 2018) . However, the meta-learning setup introduces a new overfitting problem: the model may overfit to the distribution of tasks seen during training. In other words, the meta-learning framework decreases task-specific overfitting at the cost of introducing task-wise overfitting.

The primary aim of this work is to elucidate this tradeoff between task-specific and task-wise overfitting in meta-learning. Specifically, we use tools from information theory to bound the overall generalization gap of a meta-learner. Analogously to how generalization bounds for standard learning algorithms reveal the role of dataset size in generalizing to new datapoints, our bound reveals the roles of both dataset size (m) and number of datasets (n) in generalizing to new tasks. The specific form of our generalization gap suggests that meta-learning models can be implicitly regularized by constructing them to express each datapoint with a small number of bits.

To this end, we propose Discrete InfoMax COdes (DIMCO), a deep neural network model that outputs a discrete representation of each datapoint. Note that a continuous representation x ∈ R n (e.g. Snell et al. (2017) ) uses 32n bits per datapoint. This is wildly inefficient in terms of bit-efficiency: our experiments in Section 5 show that DIMCO's discrete representation requires roughly 10× less bits per datapoint to achieve similar performance compared to continuous methods. DIMCO generalizes well to novel datasets because its learning objective encourages the model to compactly use all of its degrees of freedom, thus enabling it to effectively compare datapoints while only requiring a small number of bits per datapoint.

Our specific contributions are:

1. Derive a generalization bound for meta-learning that makes the tradeoff between taskspecific and task-wise overfitting concrete.

2. Propose DIMCO, a neural network model that is designed to have a low value of a specific term in our generalization bound.

3. Empirically demonstrate that DIMCO generalizes better than previous meta-learning methods when trained with small datasets, and that it is more memory-and time-efficient compared to previous image retrieval methods.

This paper is organized as follows. We detail our problem setup and derive a generalization bound for meta-learning in Section 2. Taking motivation from our bound, we propose our meta-learning model (DIMCO) in Section 3. We put our analysis in the context of previous work in Section 4. Notably, we suggest that certain previous meta-learning methods may have benefitted from implicit regularization.

We present experiments in Section 5 and conclude the paper with a discussion about limitations and future directions of our approach in Section 6.

2 A GENERALIZATION BOUND FOR META-LEARNING Throughout this section, we denote data, model outputs, and labels as x, x, and y, respectively. We use capital symbols X, X, Y to denote the random variables corresponding to x, x, y.

The (discrete) Mutual Information between two random variables X 1 , X 2 is defined as

EQUATION

I(X 1 ; X 2 ) is a symmetric quantity which measures the amount of information shared between X 1 and X 2 . It has its lowest value 0 when X 1 and X 2 are independent and increases with the correlation between X 1 and X 2 . We refer the reader to (Cover & Thomas, 2012) for further exposition.

2.1. PROBLEM SETUP:

We begin by describing our meta-learning problem setup. Define a task T to be a distribution over Z = X × Y. Let tasks T 1 , . . . , T n be sampled i.i.d. from a distribution of tasks τ . Associated with each task T , we define a dataset

D T = z 1 T , . . . , z m T = (x 1 T , y 1 T ), . . . , (x m T , y m T ) which is a set of m i.i.d. samples from the data distribution (z j T ∼ T ).

We consider models with parameters θ that map datapoints X to representations X(X, θ). Our objective is the expecteation of the negative mutual information between representations an labels across all tasks:

EQUATION

)

This objective is closely related to both previous loss functions and evaluation metrics in setups that involve testing on unseen classes (e.g. few-shot classification, image retrieval). We show that previous loss functions can be seen as approximations to (2) in Appendix A, and that mutual information is strongly correlated with metrics such as few-shot accuracy and Recall@1 in Section 5.1.

An important difference between (2) and previous objectives for few-shot classification is that we do not split each task into support/query (also called train/test) sets. This property bypasses the pesky issue of using batch normalization (BN) during meta-training. As Nichol & Schulman (2018) points out, BN can leak information from the support set to the query set. This issue is not a problem in our setup since we do not assume a seperate "query set". Additionally, not using support/query splits enables meta-learning with tasks consisting of one image per class, as we demonstrate in Section 5.4. Note that the standard meta-learning setup cannot learn from such tasks since it requires at least two images per class (one for support, one for query) to compute the loss function. Overall, our model demonstrates that the commonly used construction of a held-out test set within each task is not strictly necessary for meta-learning.

2.2. GENERALIZATION BOUND:

We bound the difference between expected loss and empirical loss:

Theorem 1. Let τ, n, m, X, X, Y, θ, L be defined as above. Let d Θ be the VC dimension of the encoder X(•). Let Î( X(X T , θ); Y T ) be the empirical estimate of the mutual information using finite dataset D T , and define empirical loss as The following inequality holds with high probability:

EQUATION

EQUATION

Proof. We use standard Chernoff bounds along with a finite sample bound for mutual information from Shamir et al. (2010) ; see Appendix B.

The generalization gap has three terms, two of which decrease as m increases, and the other decreases as n increases. Typically for few-shot learning, n is very large while m is small: the typical miniImagenet 5-way 1-shot setup has n > 10 10 and m = 5. We therefore claim that the latter two terms are the main difficulties for generalizing to new tasks. We see from Theorem 1 that these terms can be reduced by using small | X|. Therefore, in the context of meta-learning, using short representations (i.e. small | X|) can compensate for having a small train set (i.e. small m).

Meta-learning is typically formulated as performing two levels of learning: task-general learning and task-specific learning. Theorem 1 implies that in the tasks considered in recent literature, task-general learning should have almost no generalization gap, making task-specific learning the main source of (meta-)overfitting. This can be problematic since in many works, the task-specific learning algorithm is usually just a byproduct of whatever clever meta-learning loss was proposed. Our theorem suggests that we should pay more attention to directly regularizing this task-specific learner, and our DIMCO model, described in the next section, can be seen as a minimal working example in this direction.

3. DISCRETE INFOMAX CODES (DIMCO):

We now present our model, Discrete InfoMax COdes (DIMCO). Motivated by Section 2, DIMCO produces a short discrete code X and is trained by maximizing mutual information I( X; Y ). Figure 1 graphically shows the overall structure of DIMCO.

3.1. FACTORIZED DISCRETE CODES:

We propose a factorized discrete representation scheme which enables us to represent discrete distributions with exponentially fewer parameters compared to listing the probability of each event.

We represent each event as the product of d independent events, each of which consists of p different possibilities. We thus have p d events in total, but only require pd parameters to represent the probability of each event. Binary codes can be viewed as a special case of this scheme where p = 2. This factorization trick allows us to consider representations of size | X| = 64 256 (Section 5). This representation has the advantage of requiring only d log 2 p bits per datapoint, whereas a Ddimensional continuous vector embedding requires 32d bits (assuming 32-bit floats).

3.2. MODEL:

Recall that we represent a given image using d independent discrete distributions, each of which has p possibilities. First, a (convolutional) neural network enc(•) takes image X as input and outputs a vector of length dp, which we reshape into a matrix of size d × p:

EQUATION

Each row of this matrix represents the logits of a discrete distribution. We apply the softmax function to each row to get probabilities.

EQUATION

The ith codeword is sampled according to the categorical distribution following these probabilites:

EQUATION

We simply concatenate each x i to obtain the representation: x = ( x 1 , . . . , x d ).

3.3. TRAINING:

Recall that x is a discrete random variable and X is its distribution. Instead of sampling x ∼ X, we directly use X to compute the objective:

EQUATION

The first term, H( X), can be calculated by taking the average of all probabilities and computing the entropy:

EQUATION

The second term is

H( X|Y ) = c k=1 p(Y = k)H( X|Y = k)

where c is the number of classes. The marginal probability of Y (p(Y = k)) is the frequency of k in {y 1 , . . . , y m }. H( X|Y = k) can be obtained by computing (9) using only x j for which y j = k.

Though we have motivated the use of I( X; Y ) as a loss function throughout this paper, we provide yet another perspective using the decomposition in (8). Minimizing H( X|Y ) encourages discriminatory behavior. This term encourages the average embedding of each class to be as concentrated as possible. Maximizing H( X) incentivizes the model to overall use all possible values of X.

We emphasize that such closed-form computation of I( X; Y ) is only possible because we are using discrete codes.

3.4. EVALUATION:

We map all images to their probabilities p ij via ( 5) and ( 6) for all i = 1, . . . , d and j = 1, . . . , p. We map each training image to its most likely code:

EQUATION

Fix a train image and a test image, and let x be the most likely code for the train image. The similarity between train image and test image is measured by the probability of the test image producing x. This amounts to computing the product1 of the test image's probabilites using x i for each i = 1, . . . , d:

EQUATION

We use this as a similarity metric for both few-shot classification and image retrieval. We perform few-shot classification by computing the most likely code for each class via (10) and classifying each test image by choosing the class that has highest value of (11). We similarly perform image retrival by mapping each support image to its most likely code (10) and for each query image retrieving the support image that has highest (11).

4. RELATED WORK:

Regularizing Meta-Learners The ability to generalize to novel datasets is critical in meta-learning benchmarks, and even more so in benchmarks such as Meta-Dataset (Triantafillou et al., 2019) , where a model is tested on datasets from an unseen domain. To the best of our knowledge, no works have proposed an explicit regularizer for generalizing to new tasks.

Our analysis suggests that the success of some previous meta-learning methods can be attributed to being implicitly regularized by reducing the expressive power reducing task-specific learning. The following works have reported benefits from reducing the number of such task-specific parameters:

Lee & Choi (2018) learns a subset of the full network to alter during task-specific learning, Rusu et al. (2018) explicitly represents each task with a low-dimensional latent space, and Zintgraf et al. ( 2018) alters only a pre-specified subset of the full network during task-specific learning. It may be surprising at first that these methods achieve higher accuracy than vanila MAML (Finn et al., 2017) , which is more expressive since it alters all parameters during task-specific learning. Kim et al. (2018) also reports better meta-generalization through approximate variational inference with respect to a learned prior, which can be seen as restricting the search space of the task-specific learner.

We showed through Theorem 1 that restricting inner-loop expressivity reduces the generalization gap; this provides theoretical understanding to this consensus that meta-learning models with simple task-specific learners generalize to new tasks more easily.

Information Bottleneck Theorem 1 is close in spirit to the information bottleneck principle (Tishby et al., 2000; Tishby & Zaslavsky, 2015; Shwartz-Ziv & Tishby, 2017) . This principle states that to generalize, one should maximize I( X; Y ) while simultaneously minimizing I( X; X). Likewise, our objective (2) is I( X; Y ) while our bound (22) suggests that the representation capacity | X| should be low for generalization. Also related is the deterministic information bottleneck (Strouse & Schwab, 2017) which extends the information bottleneck by minimizing H( X) rather than I( X; X). These three approaches to generalization are related via the chain of inequalities I( X; X) ≤ H( X) ≤ log | X|, which is tight when X is an efficient code.

Representation Learning Previous works have applied information-theoretic principles to analyze the objective of VAEs (Alemi et al., 2017; Chen et al., 2018) , derive an objective for GANs to learn disentangled features (Chen et al., 2016) , and to directly learn representations (Alemi et al., 2016; Hjelm et al., 2018; Oord et al., 2018; Grover & Ermon, 2018; Choi et al., 2019) . Our work can also be viewed as an information-theoretic representation learning method, but we assume a supervised meta-learning setup and our main focus is the meta-generalization problem.

Discrete Representations Discrete representations have been thoroughly studied in the context of information theory (Shannon, 1948) . Recent deep learning methods directly learn discrete representations, by learning variational autoencoders with discrete latent variables (Rolfe, 2016; van den Oord et al., 2017; Razavi et al., 2019) or maximizing the mutual information between representation and data (Hu et al., 2017) . DIMCO is related to but differs from these works as it assumes a supervised meta-learning setting and performs infomax using labels instead of data.

Similarly to our setup, Jeong & Song (2018) uses labels to learn a binary hash code. Their focus is on the speedup gained by using sparse codes, whereas DIMCO learns a dense discrete code to generalize better. Additionally, their method solves a minimum cost flow problem within each batch to find the locally optimal code, whereas DIMCO is able to directly compute its loss function.

Factorized Representations The idea of using factorized representations has appeared the contexts of quantizing a continuous input (Jegou et al., 2011) , memory-efficient clustering (Norouzi & Fleet, 2013) , and constructing an expressive attention mechanism using few parameters (Vaswani et al., 2017) . Likewise, DIMCO factorizes its discrete representatations to increase its representation power. 2018) methods. We show in Appendix A that the loss functions of these methods can be seen as approximation to the mutual information (I( X; Y )). While all of these previous methods require a support/query split within each task, DIMCO simply optimizes an information-theoretic quantity of each batch, removing the need for such structured batch construction.

Metric Learning:



5. EXPERIMENTS:

We use the miniImageNet (Ravi & Larochelle, 2016) and CUB200 (Wah et al., 2011) We use two different CNN backbones for our experiments: the 4-layer convnet commonly used for meta-learning (Finn et al., 2017; Sung et al., 2018; Liu et al., 2018) , and the Inception network (Szegedy et al., 2015) with batch normalization (Ioffe & Szegedy, 2015) which is commonly used for deep image retrieval (Sohn, 2016; Movshovitz-Attias et al., 2017; Wu et al., 2017) . We randomly initialize weights for the 4-layer convnet and use pretrained weights for the Inception network

5.1. CORRELATION OF METRICS:

This experiment empirically verifies whether mutual information I( X; Y ) is a reasonable metric for quality of representation. We trained DIMCO on the miniImagenet dataset with p = d = 64 for 20 epochs, for 8 independent runs. We plot the pairwise correlations between five different metrics ( (5, 10, 20)-way 1-shot accuracy, Recall@1, and I( X; Y ) ) in Figure 2 . We see that all five metrics are very strongly correlated. We observed similar trends when training with with previously proposed loss functions: we visualize these results in Figure 5 of the appendix due to space constraints. Alongside this empirical evidence, we prove in Appendix A that previously used loss functions for few-shot classification and image retrieval are approximations to I( X; Y ).

5.2. WHAT DOES EACH CODE REPRESENT?:

We inspected what each code represents in a DIMCO model (d = 16, p = 64) trained on the miniImagenet dataset. Recall that each image produces a d × p probability matrix (5, 6) . For each of these dp entries, we plotted the top 10 images in the test set that assigned highest probability to that entry. We show images corresponding to four such codes in Figure 2 (right) and more in Figure 6 of the appendix.

We see that DIMCO learns a distributed representation. For example, the top code in Figure 2 represents the high-level concept of a furry animal and the shown 10 images span 4 different classes.

On the other hand, the bottom code seems to focus on the color of the background. By aggregating such complementary features in each of its d codewords, DIMCO is able to classify images that belong to previously unseen classes.

5.3. TIME-AND MEMORY-EFFICIENT IMAGE RETRIEVAL:

We conducted an image retrieval experiment using the CUB200 dataset, and used multiclass Npair loss (Sohn, 2016) as a baseline. As is standard for image retrieval, we use the Inception network as specified in the beginning of this section. Using the same backbone, we trained DIMCO with (p, d) ∈ {64, 128, 256} × {128, 256, 512} and multiclass N-pair with embedding dimension ∈ {128, 256, 512}. We measured the time per query for each method on a single Tesla P40 GPU by averaging the time required for 10000 batches of queries of size 32.

Results in Figure 3 show that the compact code of DIMCO takes roughly an order of magnitude less memory for similar performance to N-pair loss, and requires less query time as well. This experiment also demonstrates that discrete representations can match the performance of modern methods that use continuous embeddings on this relatively large-scale task. We additionally note that DIMCO is able to train using large backbones without significantly overfitting, whereas experiments reported in Mishra et al. (2017) indicate that MAML (Finn et al., 2017) overfits tremendously when using a deeper backbone.

5.4. GENERALIZATION TO NEW TASKS:

This experiment measures how well DIMCO can generalize to new datasets after training with a small number of datasets. This challenging experimental setup measures how much generalizable information the model can extract from a limited set of datasets; it can be seen as the meta-learning analogue of measuring the performance of a classifier trained with a small dataset.

We trained each model using {1, 4, 16, 64} samples from each training class in the miniImageNet dataset. For example, by using 4 samples, we are reducing the full train split of (64 classes × 600 images per class) into (64 classes × 4 images per class). We compare against three baseline methods:

Triplet Nets (Hoffer & Ailon, 2015) , multiclass N-pair loss (Sohn, 2016) , and ProtoNets (Snell et al., 2017) . We report the average and standard deviation of the top 5 results of a random hyperparameter search (see appendix for details). We show {5, 10, 20}-way 1-shot accuracies and Recall@1 of the test set in Figure 4 .

First note that DIMCO is the only method that can train using a dataset consisting of 1 example per class. This is because other methods require at least one train and test example per class within each batch, while DIMCO requires no such train/test (also called support/query) split and simply maximizes the mutual information within a batch. Furthermore, Figure 4 shows that DIMCO learns much more effectively when the number of examples per class is low; this is because DIMCO uses fewer bits to describe each datapoint, which lowers its generalization gap (24) when applying to novel datasets.

6. CONCLUSION AND DISCUSSION:

Summary We derived a generalization bound for meta-learning using information-theoretic principles. Building on our bound, we proposed DIMCO, a model that learns a discrete representation of data by maximizing its mutual information with the label. DIMCO had benefits in time, memory, and generalization in our experiments.

Towards Explicit Meta-Regularization In Section 4, we have suggested with analogy to Theorem 1 that the benefits of some previous meta-learning methods can be attributed to implicitly being regularized by reducing the expressivity of their task-specific learners. While DIMCO has demonstrated better generalization by reducing this expressivity via hyperparameters (d, p), this is only applicable to DIMCO's specific setup of few-shot classification through mutual information maximization. In future work, we would like to explore explicit meta-regularization schemes that can be applied to other problems (regression, reinforcement learning etc.) and algorithms (MAML, Neural Process etc.).

Meta-Learning Without Splits Our meta-learning problem setup in Section 2.1 does not assume a support/query (also called train/test) split within each dataset. Along with showing that the traditional support/query split is not strictly necessary, we demonstrated in Section 5.4 that removing it has the benefit of enabling meta-learning in datasets having one image per class. We believe future work could benefit from further exploring this space of meta-learning algorithms that use datasets without splits.

A PREVIOUS LOSS FUNCTIONS ARE APPROXIMATIONS TO MUTUAL INFORMATION:

Cross-entropy Loss The cross-entropy loss has directly been used for few-shot classification (Vinyals et al., 2016; Snell et al., 2017) .

Let q(y| x; φ) be a parameterized prediction of y given x, which tries to approximate the true conditional distribution q(y| x). Typically in a classification network, φ is the parameters of a learned projection matrix and q(•) is the final linear layer. The expected cross-entropy loss can be written as

EQUATION

Assuming that the approximate distribution q(•) is sufficiently close to p(y| x), minimizing ( 12) can be seen as

EQUATION

where the last equality uses the fact that H(Y ) is independent of model parameters. Therefore, crossentropy minimization is approximate maximization of the mutual information between representation X and labels Y .

The approximation is that we parameterized q(y| x; φ) as a linear projection. This structure cannot generalize to new classes because the parameters φ are specific to the labels y seen during training.

For a model to generalize to unseen classes, one must amortize the learning of this approximate conditional distribution. (Vinyals et al., 2016; Snell et al., 2017) sidestepped this issue by using the embeddings for each class as φ.

Triplet Loss The Triplet loss (Hoffer & Ailon, 2015) is defined as

EQUATION

where x q , x p , x n ∈ R d are the embedding vectors of query, positive, and negative images. Let y q denote the label of the query data. Recall that the pdf function of a unit Gaussian is log N

( x|µ, 1) = -c 1 -c 2 x -µ 2 2

, where c 1 , c 2 are constants. Let p p ( x) = N ( x p , 1) and p n ( x) = N ( x n , 1) be unit Gaussian distributions centered at x p , x n respectively. We have

EQUATION

Two approximations were made in the process. We first assumed that the embedding distribution of images not in y q is equal to the distribution of all embeddings. This is reasonable when each class only represents a small fraction of the full data. We also approximated the embedding distributions p( x|y), p( x) with unit Gaussian distributions centered at single samples from each.

N-pair Loss Multiclass N -pair loss (Sohn, 2016) was proposed as an alternative to Triplet loss. This loss function requires one positive embedding x + and multiple negative embeddings x 1 , . . . , x N -1 , and takes the form

EQUATION

)

This can be seen as the cross-entropy loss applied to softmax( x x + , x x 1 , . . . , x x N -1 ).

Following the same logic as the cross-entropy loss, this is also an approximation to I( X; Y ). This objective should have less variance than Triplet loss since it approximates p( x) using more examples.

Adversarial Metric Learning Deep Adversarial Metric Learning (Duan et al., 2018) tackles the problem of most negative exmples being uninformative by directly generating meaningful negative embeddings. This model employs a generator which takes as input the embeddings of anchor, positive, and negative images. The generator then outputs a "synthetic negative" embedding that is hard to distinguish from a positive embedding while being close to the negative embedding.

This can be seen as optimizing E log p p ( x)log p( x) = I( X; Y ) (20) by estimating p( x) using a generative network rather than directly from samples. Rather than modelling the marginal distribution p( x), this method conditionally models p( x; x q , x p , x n ) so that x is hard to distinguish from x p while sufficiently close to both x q x n .

B PROOF OF THEOREM 1

We restate and prove our main theorem.

Theorem 1. Let d Θ be the VC dimension of the encoder X(•). Let Î( X(X T , θ); Y T ) be the empirical estimate of the mutual information using finite dataset D T , and define empirical loss as

EQUATION

)

The following inequality holds with high probability:

EQUATION

Proof. We use the following lemma from Shamir et al. (2010) , which we restate using our notation.

Lemma 1. Let X be a random mapping of X. Let D be a sample of size m drawn from the joint probability distribution p(X, Y ). Denote the empirical mutual information observed from D between X and Y as Î( X; Y ). For any δ ∈ (0, 1), the following holds with probability at least 1δ: We simplify this and plug in our specific quantities of interest ( X(X T , θ), Y T ):

EQUATION

)

We similarly bound the error caused by estimating L with a finite number of tasks sampled from τ . Denote the finite sample estimate of L as

EQUATION

)

Let the mapping X → X be parameterized by θ ∈ Θ and let this model have VC dimension d Θ .

Using d Θ , we can state that with high probability,

EQUATION

where d Θ is the VC dimension of hypothesis class Θ. 

:

In practice, we add log probabilities instead of multiplying probabilities for numerical stability.

Figures and Tables:

Figure 1: A graphical overview of Discrete InfoMax COdes (DIMCO). A dataset D consists of pairs of images X and labels Y . DIMCO is a stochastic encoder that maps each image X to a distribution of discrete codes p( X|X). Each discrete code x ∼ p( X|X) is a p-way code of length d. If p = 4, d = 2 (as in the diagram), each code consists of 2 symbols and each symbol is ∈ {1, 2, 3, 4}. Inside the 4 × 4 grid that represents the p d = 16 possible codes, the most likely row and column are colored. The most likely code in the diagram is (1, 2) with probability 30%. DIMCO is optimized by maximizing the mutual information between the discrete code and the label within each batch.

The structure and loss function of DIMCO is closely related to embedding-based meta-learning Vinyals et al. (2016); Snell et al. (2017); Oreshkin et al. (2018) and image retrieval Hoffer & Ailon (2015); Sohn (2016); Wu et al. (2017); Duan et al. (

Figure 2: Left: Pairwise correlation between MI = I(X; X) and previous metrics. Right: Visualization of codes of a small trained DIMCO model (d = 16, p = 64); we show the top 10 test set images that assign highest probability to a specific code, for 4 different codes.

Figure4: Performance of methods trained using subsets of miniImageNet of varying size. The lowermost y axis value for each metric corresponds to the expected performance of random guessing.

|I(X; Y ) -Î( X; Y )| ≤ (3| X| + 2) log(m) log(4/δ) √ 2m + (|Y | + 1)(| X| + 1) -4 m(23)

Figure 5: Correlation between few-shot accuracy and retrieval measures.

Peer review (iclr2020):
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 	ilde{X}. Thus, in the absence of that layer they collapse to the same objective. As DIMCO itself directly extract class label predictions from 	ilde{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_{	ilde{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.