summaries: This paper investigates the effect of episode difficulty and sampling schemes on the performance of few-shot classification algorithms. It defines difficulty based on the negative log predictive likelihood of the few-shot learner and proposes to use importance sampling to mimic various sampling strategies. Experiments demonstrate that episodic difficulty is (a) approximately normally distributed, (b) tends to transfer across architectures and learning algorithms, (c) tends to be consistent over the course of training, and (d) that a uniform sampling scheme over difficulty tends to produce the best results. An online scheme for computing importance weights is also proposed.   === Post-rebuttal ===  I have read the authors' response and other reviews and will maintain my original rating. This paper explores episode/task difficulty in few-shot learning. The task difficulty is defined as the negative log-likelihood over the query set given the support set and model parameters. The authors find evidence that episode difficulty likely follows a normal distribution and proposes a new method, called UNIFORM, based on importance sampling. The new method achieves similar or better performance than other sampling procedures (EASY, HARD, and CURRICULUM). The paper also presents two variants of UNIFORM: offline and online.  This submission studies episodic sampling, which is used to sample datasets (consisting of support and query sets) for training meta-learning models. The authors define a notion of episodic difficulty (the negative log-likelihood of the query set given the support set and model parameters) and propose using importance sampling to train using several different types of episode-sampling strategies for meta-training. By using importance sampling, there is no sampling required for the target distribution but just weighting the episode loss based on the proposal and target distribution. They conduct experiments both to confirm some of their assumptions that are critical for their proposal (that episodic difficulty is normally distributed) and to show how their episodic sampling strategies compare against random episodic sampling, which is the dominant strategy used by work in this area.  Meta-learning (few-shot learning) algorithms, in general, equally treat all tasks for the training process. Tasks are sampled uniformly at random. This paper proposes a novel meta-learning framework that controls the task sampling probabilities according to difficulties. This paper measures the difficulties of tasks using the negative log-likelihood and leverages the difficulties to introduce different weights to tasks. The main idea of the learning framework is that the prior of the difficulties follows a normal distribution while the target sampling distribution could be uniform or some other interesting forms. Then, important sampling provides different weights to different tasks. From experiments, the uniform target distribution shows good results. 
abstractText: Episodic training is a core ingredient of few-shot learning to train models on tasks with limited labelled data. Despite its success, episodic training remains largely understudied, prompting us to ask the question: what is the best way to sample episodes? In this paper, we first propose a method to approximate episode sampling distributions based on their difficulty. Building on this method, we perform an extensive analysis and find that sampling uniformly over episode difficulty outperforms other sampling schemes, including curriculum and easy-/hard-mining. As the proposed sampling method is algorithm agnostic, we can leverage these insights to improve few-shot learning accuracies across many episodic training algorithms. We demonstrate the efficacy of our method across popular few-shot learning datasets, algorithms, network architectures, and protocols.
authors.name: Sébastien M. R. Arnold
authors.name: Guneet S. Dhillon
authors.name: Avinash Ravichandran
authors.name: Stefano Soatto
references.authors: S.M.R. Arnold P. Mahajan D. Datta I. Bunner K.S. Zarkias
references.title: learn2learn: A library for Meta- Learning research
references.venue: Aug.
references.authors: Y. Bengio J. Louradour R. Collobert J. Weston
references.title: Curriculum learning
references.venue: Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pages 41–48, New York, NY, USA, June
references.authors: L. Bertinetto J.F. Henriques P. Torr A. Vedaldi
references.title: Meta-learning with differentiable closed-form solvers
references.venue: Sept.
references.authors: D.P. Bertsekas J.N. Tsitsiklis
references.title: Neuro-Dynamic programming
references.venue: 27(6), Jan.
references.authors: L. Bottou F.E. Curtis J. Nocedal
references.title: Optimization methods for large-scale machine learning
references.venue: June
references.authors: M. Botvinick S. Ritter J.X. Wang Z. Kurth-Nelson C. Blundell D. Hassabis
references.title: Reinforcement learning, fast and slow
references.venue: Trends in cognitive sciences, 23(5):408–422,
references.authors: W.-L. Chao H.-J. Ye D.-C. Zhan M. Campbell K.Q. Weinberger
references.title: Revisiting meta-learning as supervised learning
references.venue: arXiv preprint arXiv:2002.00573,
references.authors: M. Cimpoi S. Maji I. Kokkinos S. Mohamed A. Vedaldi
references.title: Describing textures in the wild
references.venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3606–3613,
references.authors: D. Csiba P. Richtárik
references.title: Importance sampling for minibatches
references.venue: J. Mach. Learn. Res., 19(27):1–21,
references.authors: J. Deng W. Dong R. Socher L.-J. Li K. Li L. Fei-Fei
references.title: Imagenet: A large-scale hierarchical image database
references.venue: 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee,
references.authors: G.S. Dhillon P. Chaudhari A. Ravichandran S. Soatto
references.title: A baseline for few-shot image classification
references.venue: International Conference on Learning Representations,
references.authors: A. Doucet N. d. Freitas N. Gordon editors
references.title: Sequential Monte Carlo Methods in Practice
references.authors: A. Fallah A. Mokhtari A. Ozdaglar
references.title: Generalization of model-agnostic meta-learning algorithms: Recurring and unseen tasks
references.venue: arXiv preprint arXiv:2102.03832,
references.authors: L. Fei-Fei R. Fergus P. Perona
references.title: One-shot learning of object categories
references.venue: IEEE Trans. Pattern Anal. Mach. Intell., 28(4):594–611, Apr.
references.authors: C. Finn P. Abbeel S. Levine
references.title: Model-agnostic meta-learning for fast adaptation of deep networks
references.venue: International Conference on Machine Learning, pages 1126–1135. PMLR,
references.authors: S. Flennerhag A.A. Rusu R. Pascanu H. Yin R. Hadsell
references.title: Meta-Learning with warped gradient descent
references.venue: Aug.
references.authors: M.P. Friedlander M. Schmidt
references.title: Hybrid Deterministic-Stochastic methods for data fitting
references.venue: SIAM J. Sci. Comput., 34(3):A1380–A1405, Jan.
references.authors: M. Garnelo D. Rosenbaum C. Maddison T. Ramalho D. Saxton M. Shanahan Y.W. Teh D. Rezende S.M.A. Eslami
references.title: Conditional neural processes
references.venue: J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1704–1713, Stockholmsmässan, Stockholm Sweden,
references.authors: G. Ghiasi T.-Y. Lin Q.V. Le
references.title: Dropblock: a regularization method for convolutional networks
references.venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 10750–10760,
references.authors: S. Gidaris N. Komodakis
references.title: Dynamic few-shot visual learning without forgetting
references.venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4367–4375,
references.authors: P. Glasserman
references.title: Monte Carlo methods in financial engineering
references.venue: Springer, New York,
references.authors: E. Grant C. Finn S. Levine T. Darrell T. Griffiths
references.title: Recasting Gradient-Based Meta-Learning as hierarchical bayes
references.venue: Jan.
references.authors: K. He X. Zhang S. Ren J. Sun
references.title: Deep residual learning for image recognition
references.venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778,
references.authors: T. Hospedales A. Antoniou P. Micaelli others
references.title: Meta-learning in neural networks: A survey
references.venue: arXiv preprint arXiv,
references.authors: S. Ioffe C. Szegedy
references.title: Batch normalization: Accelerating deep network training by reducing internal covariate shift
references.venue: International conference on machine learning, pages 448–456. PMLR,
references.authors: T.B. Johnson C. Guestrin
references.title: Training deep models faster with robust, approximate importance sampling
references.venue: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 7265–7275. Curran Associates, Inc.,
references.authors: A. Katharopoulos F. Fleuret
references.title: Not all samples are created equal: Deep learning with importance sampling
references.venue: Mar.
references.authors: D.P. Kingma J. Ba
references.title: Adam: A method for stochastic optimization
references.venue: ICLR (Poster),
references.authors: A. Kong
references.title: A note on importance sampling using standardized weights
references.venue: University of Chicago, Dept. of Statistics, Tech. Rep, 348,
references.authors: S. Laenen L. Bertinetto
references.title: On episodes, prototypical networks, and few-shot learning
references.venue: Dec.
references.authors: B.M. Lake T.D. Ullman J.B. Tenenbaum S.J. Gershman
references.title: Building machines that learn and think like people
references.venue: Behavioral and brain sciences, 40,
references.authors: K. Lee S. Maji A. Ravichandran S. Soatto
references.title: Meta-learning with differentiable convex optimization
references.venue: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10657– 10665,
references.authors: C. Liu Z. Wang D. Sahoo Y. Fang K. Zhang S.C.H. Hoi
references.title: Adaptive task sampling for Meta-Learning
references.venue: July
references.authors: J.S. Liu
references.title: Metropolized independent sampling with comparisons to rejection sampling and importance sampling
references.venue: Statistics and computing, 6(2):113–119,
references.authors: S. Maji E. Rahtu J. Kannala M. Blaschko A. Vedaldi
references.title: Fine-grained visual classification of aircraft
references.venue: arXiv preprint arXiv:1306.5151,
references.authors: E.G. Miller N.E. Matsakis P.A. Viola
references.title: Learning from one example through shared densities on transforms
references.venue: Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662), volume 1, pages 464–471 vol.1, June
references.authors: A. Nichol J. Achiam J. Schulman
references.title: On First-Order Meta-Learning algorithms
references.venue: Mar.
references.authors: M.-E. Nilsback A. Zisserman
references.title: A visual vocabulary for flower classification
references.venue: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), volume 2, pages 1447–1454. IEEE,
references.authors: B.N. Oreshkin P. Rodriguez A. Lacoste
references.title: Tadam: task dependent adaptive metric for improved few-shot learning
references.venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 719–729,
references.authors: E. Park J.B. Oliva
references.title: Meta-Curvature
references.venue: Feb.
references.authors: A. Raghu M. Raghu S. Bengio O. Vinyals
references.title: Rapid learning or feature reuse? towards understanding the effectiveness of maml
references.venue: International Conference on Learning Representations,
references.authors: A. Rajeswaran C. Finn S. Kakade S. Levine
references.title: Meta-Learning with implicit gradients
references.venue: Sept.
references.authors: S. Ravi H. Larochelle
references.title: Optimization as a model for few-shot learning
references.authors: A. Ravichandran R. Bhotika S. Soatto
references.title: Few-Shot learning with embedded class models and Shot-Free meta training
references.venue: May
references.authors: M. Ren E. Triantafillou S. Ravi J. Snell K. Swersky J.B. Tenenbaum H. Larochelle R.S. Zemel
references.title: Meta-learning for semi-supervised few-shot classification
references.venue: International Conference on Learning Representations,
references.authors: H. Robbins S. Monro
references.title: A stochastic approximation method
references.venue: Ann. Math. Stat., 22(3):400–407, Sept.
references.authors: A. Santoro S. Bartunov M. Botvinick D. Wierstra T. Lillicrap
references.title: Meta-Learning with Memory- Augmented neural networks
references.venue: M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1842–1850, New York, New York, USA,
references.authors: T. Schaul J. Quan I. Antonoglou D. Silver
references.title: Prioritized experience replay
references.venue: Nov.
references.authors: J. Schmidhuber
references.title: Evolutionary Principles in Self-Referential Learning
references.venue: PhD thesis,
references.authors: S.S. Shapiro M.B. Wilk
references.title: An analysis of variance test for normality (complete samples)
references.venue: Biometrika, 52(3/4):591–611,
references.authors: A. Shrivastava A. Gupta R. Girshick
references.title: Training region-based object detectors with online hard example mining
references.venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 761–769,
references.authors: P.J. Smith M. Shafi Hongsheng Gao
references.title: Quick simulation: a review of importance sampling techniques in communications systems
references.venue: IEEE J. Sel. Areas Commun.,
references.authors: J. Snell K. Swersky R. Zemel
references.title: Prototypical networks for few-shot learning
references.venue: Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4080–4090,
references.authors: N. Srivastava G. Hinton A. Krizhevsky I. Sutskever R. Salakhutdinov
references.title: Dropout: a simple way to prevent neural networks from overfitting
references.venue: The journal of machine learning research, 15(1):1929–1958,
references.authors: Q. Sun Y. Liu Z. Chen T.-S. Chua B. Schiele
references.title: Meta-Transfer learning through hard tasks
references.venue: Oct.
references.authors: S. Thrun L. Pratt editors
references.title: Learning to Learn
references.authors: E. Triantafillou T. Zhu V. Dumoulin P. Lamblin U. Evci K. Xu R. Goroshin C. Gelada K. Swersky P.-A. Manzagol H. Larochelle
references.title: Meta-dataset: A dataset of datasets for learning to learn from few examples
references.venue: International Conference on Learning Representations,
references.authors: O. Vinyals C. Blundell T. Lillicrap K. Kavukcuoglu D. Wierstra
references.title: Matching networks for one shot learning
references.venue: Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 3637–3645,
references.authors: Y. Wang Q. Yao J.T. Kwok L.M. Ni
references.title: Generalizing from a few examples: A survey on few-shot learning
references.venue: ACM Comput. Surv., 53(3):1–34, June
references.authors: P. Welinder S. Branson T. Mita C. Wah F. Schroff S. Belongie P. Perona
references.title: Caltech-ucsd birds
references.authors: D.H.D. West
references.title: Updating mean and variance estimates: An improved method
references.venue: Commun. ACM, 22(9): 532–535, Sept.
references.authors: C. Wu R. Manmatha A.J. Smola P. Krähenbühl
references.title: Sampling matters in deep embedding learning
references.venue: 2017 IEEE International Conference on Computer Vision (ICCV), pages 2859–2867, Oct.
references.authors: X. Wu E. Dyer B. Neyshabur
references.title: When do curricula work
references.venue: URL http://arxiv.org/ abs/2012.03107
references.authors: H.-J. Ye H. Hu D.-C. Zhan F. Sha
references.title: Few-shot learning via embedding adaptation with set-toset functions
references.venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8808–8817,
references.authors: J. Yoon T. Kim O. Dia S. Kim Y. Bengio S. Ahn
references.title: Bayesian Model-Agnostic Meta- Learning
references.venue: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 7332–7342. Curran Associates, Inc.,
references.authors: C. Zhang C. Öztireli S. Mandt G. Salvi
references.title: Active mini-batch sampling using repulsive point processes
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5741–5748,
references.authors: C. Zhang Y. Cai G. Lin C. Shen
references.title: Deepemd: Few-shot image classification with differentiable earth mover’s distance and structured classifiers
references.venue: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12203–12213,
references.authors: P. Zhao T. Zhang
references.title: Accelerating minibatch stochastic gradient descent using stratified sampling
references.venue: May
references.authors: Y. Zhou Y. Wang J. Cai Y. Zhou Q. Hu W. Wang
references.title: Expert training: Task hardness aware Meta- Learning for Few-Shot classification
references.venue: July
sections.heading: 1 Introduction
sections.text: Large amounts of high-quality data have been the key for the success of deep learning algorithms. Furthermore, factors such as data augmentation and sampling affect model performance significantly. Continuously collecting and curating data is a resource (cost, time, storage, etc.) intensive process. Hence, recently, the machine learning community has been exploring methods for performing transfer-learning from large datasets to unseen tasks with limited data.
  A popular genre of these approaches is called meta-learning few-shot approaches, where, in addition to the limited data from the task of interest, a large dataset of disjoint tasks is available for (pre-)training. These approaches are prevalent in the area of computer vision [31] and reinforcement learning [6]. A key component of these methods is the notion of episodic training, which refers to sampling tasks from the larger dataset for training. By learning to solve these tasks correctly, the model can generalize to new tasks.
  However, sampling for episodic training remains surprisingly understudied despite numerous methods and applications that build on it. To the best of our knowledge, only a handful of works [69, 55, 33] explicitly considered the consequences of sampling episodes. In comparison, stochastic [46] and mini-batch [4] sampling alternatives have been thoroughly analyzed from the perspectives of optimization [17, 5], information theory [27, 9], and stochastic processes [68, 66], among many others. Building a similar understanding of sampling for episodic training will help theoreticians and practitioners develop improved sampling schemes, and is thus of crucial importance to both.
  In this paper, we explore many sampling schemes to understand their impact on few-shot methods. Our work revolves around the following fundamental question: what is the best way to sample episodes? Our focus will be restricted to image classification in the few-shot learning setting – where “best” is taken to mean “higher transfer accuracy of unseen episodes” – and leave analyses and applications to other areas for future work. ∗Equal contributions; work done while at Amazon Web Services.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  Contrary to prior work, our experiments indicate that sampling uniformly with respect to episode difficulty yields higher classification accuracy – a scheme originally proposed to regularize metric learning [62]. To better understand these results, we take a closer look at the properties of episodes and what makes them difficult. Building on this understanding, we propose a method to approximate different sampling schemes, and demonstrate its efficacy on several standard few-shot learning algorithms and datasets.
  Concretely, we make the following contributions:
  • We provide a detailed empirical analysis of episodes and their difficulty. When sampled randomly, we show that episode difficulty (approximately) follows a normal distribution and that the difficulty of an episode is largely independent of several modeling choices including the training algorithm, the network architecture, and the training iteration. • Leveraging our analysis, we propose simple and universally applicable modifications to the episodic sampling pipeline to approximate any sampling scheme. We then use this scheme to thoroughly compare episode sampling schemes – including easy/hard-mining, curriculum learning, and uniform sampling – and report that sampling uniformly over episode difficulty yields the best results. • Finally, we show that sampling matters for few-shot classification as it improves transfer
  accuracy for a diverse set of popular [53, 20, 15, 41] and state-of-the-art [64] algorithms on standard and cross-domain benchmarks.
sections.heading: 2 Preliminaries
sections.heading: 2.1 Episodic sampling and training
sections.text: We define episodic sampling as subsampling few-shot tasks (or episodes) from a larger base dataset [7]. Assuming the base dataset admits a generative distribution, we sample an episode in two steps2. First, we sample the episode classes Cτ from class distribution p(Cτ ); second, we sample the episode’s data from data distribution p(x, y | Cτ ) conditioned on Cτ . This gives rise to the following log-likelihood for a model lθ parameterized by θ:
  L(θ) = E τ∼q(·) [log lθ(τ)] , (1)
  where q(τ) is the episode distribution induced by first sampling classes, then data. In practice, this expectation is approximated by sampling a batch of episodes B each with their set τQ of query samples. To enable transfer to unseen classes, it is also common to include a small set τS of support samples to provide statistics about τ . This results in the following Monte-Carlo estimator:
  L(θ) ≈ 1 |B| ∑ τ∈B 1 |τQ| ∑
  (x,y)∈τQ
  log lθ(y | x, τS), (2)
  where the data in τQ and τS are both distributed according to p(x, y | Cτ ). In few-shot classification, the n-way k-shot setting corresponds to sampling n = |Cτ | classes, each with k = |τS |n support data points. The implicit assumption in the vast majority of few-shot methods is that both classes and data are sampled with uniform probability – but are there better alternatives? We carefully examine these underlying assumptions in the forthcoming sections.
sections.heading: 2.2 Few-shot algorithms
sections.text: We briefly present a few representative episodic learning algorithms. A more comprehensive treatment of few-shot algorithms is presented in Wang et al. [59] and Hospedales et al. [24]. A core question in few-shot learning lies in evaluating (and maximizing) the model likelihood lθ. These algorithms can be divided in two major families: gradient-based methods, which adapt the model’s parameters to the episode; and metric-based methods, which compute similarities between support and query samples in a learned embedding space.
  Gradient-based few-shot methods are best illustrated through Model-Agnostic Meta-Learning [15] (MAML). The intuition behind MAML is to learn a set of initial parameters which can quickly
  2We use the notation for a probability distribution and its probability density function interchangeably.
  specialize to the task at hand. To that end, MAML computes lθ by adapting the model parameters θ via one (or more) steps of gradient ascent and then computes the likelihood using the adapted parameters θ′. Concretely, we first compute the likelihood pθ(y | x) using the support set τS , adapt the model parameters, and then evaluate the likelihood:
  lθ(y | x, τS) = pθ′(y | x) s.t. θ′ = θ + α∇θ ∑
  (x,y)∈τS
  log pθ(y | x),
  where α > 0 is known as the adaptation learning rate. A major drawback of training with MAML lies in back-propagating through the adaptation phase, which requires higher-order gradients. To alleviate this computational burden, Almost No Inner Loop [41] (ANIL) proposes to only adapt the last classification layer of the model architecture while tying the rest of the layers across episodes. They empirically demonstrate little classification accuracy drop while accelerating training times four-fold.
  Akin to ANIL, metric-based methods also share most of their parameters across tasks; however, their aim is to learn a metric space where classes naturally cluster. To that end, metric-based algorithms learn a feature extractor φθ parameterized by θ and classify according to a non-parametric rule. A representative of this family is Prototypical Network [53] (ProtoNet), which classifies query points according to their distance to class prototypes – the average embedding of a class in the support set:
  lθ(y | x, τS) = exp (−d(φθ(x), φyθ))∑ y′∈Cτ exp ( −d(φθ(x), φy ′ θ ) ) s.t. φcθ = 1k ∑
  (x,y)∈τS y=c
  φθ(x),
  where d(·, ·) is a distance function such as the Euclidean distance or the negative cosine similarity, and φcθ is the class prototype for class c. Other classification rules include support vector clustering [32], neighborhood component analysis [30], and the earth-mover distance [67].
sections.heading: 2.3 Episode difficulty
sections.text: Given an episode τ and likelihood function lθ, we define episode difficulty to be the negative loglikelihood incurred on that episode:
  Ωlθ (τ) = − log lθ(τ), which is a surrogate for how hard it is to classify the samples in τQ correctly, given lθ and τS . By definition, this choice of episode difficulty is tied to the choice of the likelihood function lθ.
  Dhillon et al. [11] use a similar surrogate as a means to systematically report few-shot performances. We use this definition because it is equivalent to the loss associated with the likelihood function lθ on episode τ , which is readily available at training time.
sections.heading: 3 Methodology
sections.text: In this section, we describe the core assumptions and methodology used in our study of sampling methods for episodic training. Our proposed method builds on importance sampling [21] (IS) which we found compelling for three reasons: (i) IS is well understood and solidly grounded from a theoretical standpoint, (ii) IS is universally applicable thus compatible with all episodic training algorithms, and (iii) IS is simple to implement with little requirement for hyper-parameter tuning.
  Why should we care about episodic sampling? A back-of-the-envelope calculation3 suggests that there are on the order of 10162 different training episodes for the smallest-scale experiments in Section 5. Since iterating through each of them is infeasible, we ought to express some preference over which episodes to sample. In the following, we describe a method that allows us to specify this preference.
sections.heading: 3.1 Importance sampling for episodic training
sections.text: Let us assume that the sampling scheme described in Section 2.1 induces a distribution q(τ) over episodes. We call it the proposal distribution, and assume knowledge of its density function. We wish
  3For a base dataset with N classes and K input-output pairs per class, there are a total of ( N n )( K k )n possible
  episodes that can be created when sampling k pairs each from n classes.
  Algorithm 1: Episodic training with Importance Sampling Input: target (p) and proposal (q) distributions, likelihood function lθ, optimizer OPT. Randomly initialize model parameters θ. repeat
  Sample a mini-batch B of episodes from q(τ). for each episode τ in mini-batch B do
  Compute episode likelihood: lθ(τ). Compute importance weight: w(τ) = p(τ)q(τ) .
  end for Aggregate: L(θ)← ∑ τ∈B w(τ) log lθ(τ). Compute effective sample size ESS(B). Update model parameters: θ ← OPT( L(θ)ESS(B) ).
  until parameters θ have converged.
  to estimate the expectation in Eq. (1) when sampling episodes according to a target distribution p(τ) of our choice, rather than q(τ). To that end, we can use an importance sampling estimator which simply re-weights the observed values for a given episode τ by w(τ) = p(τ)q(τ) , the ratio of the target and proposal distributions:
  E τ∼p(·) [log lθ(τ)] = E τ∼q(·) [w(τ) log lθ(τ)] .
  The importance sampling identity holds whenever q(τ) has non-zero density over the support of p(τ), and effectively allows us to sample from any target distribution p(τ).
  A practical issue of the IS estimator arises when some values of w(τ) become much larger than others; in that case, the likelihoods lθ(τ) associated with mini-batches containing heavier weights dominate the others, leading to disparities. To account for this effect, we can replace the mini-batch average in the Monte-Carlo estimate of Eq. (2) by the effective sample size ESS(B) [29, 34]:
  E τ∼p(·)
  [log lθ(τ)] ≈ 1 ESS(B) ∑ τ∈B w(τ) log lθ(τ) s.t. ESS(B) = ( ∑ τ∈B w(τ)) 2∑ τ∈B w(τ) 2 , (3)
  where B denotes a mini-batch of episodes sampled according to q(τ). Note that whenw(τ) is constant, we recover the standard mini-batch average setting as ESS(B) = |B|. Empirically, we observed that normalizing with the effective sample size avoided instabilities. This method is summarized in Algorithm 1.
sections.heading: 3.2 Modeling the proposal distribution
sections.text: A priori, we do not have access to the proposal distribution q(τ) (nor its density) and thus need to estimate it empirically. Our main assumption is that sampling episodes from q(τ) induces a normal distribution over episode difficulty. With this assumption, we model the proposal distribution by this induced distribution, therefore replacing q(τ) with N (Ωlθ (τ) | µ, σ2) where µ, σ2 are the mean and variance parameters. As we will see in Section 5.2, this normality assumption is experimentally supported on various datasets, algorithms, and architectures.
  We consider two settings for the estimation of µ and σ2: offline and online. The offline setting consists of sampling 1, 000 training episodes before training, and computing µ, σ2 using a model pre-trained on the same base dataset. Though this setting seems unrealistic, i.e. having access to a pre-trained model, several meta-learning few-shot methods start with a pre-trained model which they further build upon. Hence, for such methods there is no overhead. For the online setting, we estimate the parameters on-the-fly using the model currently being trained. This is justified by the analysis in Section 5.2 which shows that episode difficulty transfers across model parameters during training. We update our estimates of µ, σ2 with an exponential moving average:
  µ← λµ+ (1− λ)Ωlθ (τ) and σ2 ← λσ2 + (1− λ)(Ωlθ (τ)− µ)2, where λ ∈ [0, 1] controls the adjustment rate of the estimates, and the initial values of µ, σ2 are computed in a warm-up phase lasting 100 iterations. Keeping λ = 0.9 worked well for all our
  experiments (Section 5). We opted for this simple implementation as more sophisticated approaches like West [61] yielded little to no benefit.
sections.heading: 3.3 Modeling the target distribution
sections.text: Similar to the proposal distribution, we model the target distribution by its induced distribution over episode difficulty. Our experiments compare four different approaches, all of which share parameters µ, σ2 with the normal model of the proposal distribution. For numerical stability, we truncate the support of all distributions to [µ− 2.58σ, µ+ 2.58σ], which gives approximately 99% coverage for the normal distribution centered around µ.
  The first approach (HARD) takes inspiration from hard negative mining [51], where we wish to sample only more challenging episodes. The second approach (EASY) takes a similar view but instead only samples easier episodes. We can model both distributions as follows:
  U(Ωlθ (τ) | µ, µ+ 2.58σ) (HARD) and
  U(Ωlθ (τ) | µ− 2.58σ, µ) (EASY)
  where U denotes the uniform distribution. The third (CURRICULUM) is motivated by curriculum learning [2], which slowly increases the likelihood of sampling more difficult episodes:
  N (Ωlθ (τ) | µt, σ2) (CURRICULUM)
  where µt is linearly interpolated from µ− 2.58σ to µ+ 2.58σ as training progresses. Finally, our fourth approach, UNIFORM, resembles distance weighted sampling [62] and consists of sampling uniformly over episode difficulty:
  U(Ωlθ (τ) | µ− 2.58σ, µ+ 2.58σ). (UNIFORM)
  Intuitively, UNIFORM can be understood as a uniform prior over unseen test episodes, with the intention of performing well across the entire difficulty spectrum. This acts as a regularizer, forcing the model to be equally discriminative for both easy and hard episodes.
sections.heading: 4 Related Works
sections.text: This paper studies task sampling in the context of few-shot [36, 14] and meta-learning [49, 56].
  Few-shot learning. This setting has received a lot of attention over recent years [58, 43, 47, 18]. Broadly speaking, state-of-the-art methods can be categorized in two major families: metric-based and gradient-based.
  Metric-based methods learn a shared feature extractor which is used to compute the distance between samples in embedding space [53, 3, 44, 30]. The choice of metric mostly differentiates one method from another; for example, popular choices include Euclidean distance [53], negative cosine similarity [20], support vector machines [32], set-to-set functions [64], or the earth-mover distance [67].
  Gradient-based algorithms such as MAML [15], propose an objective to learn a network initialization that can quickly adapt to new tasks. Due to its minimal assumptions, MAML has been extended to probabilistic formulations [22, 65] to incorporate learned optimizers – implicit [16] or explicit [40] – and simplified to avoid expensive second-order computations [37, 42]. In that line of work, ANIL [41] claims to match MAML’s performance when adapting only the last classification layer – thus greatly reducing the computational burden and bringing gradient and metric-based methods closer together.
  Sampling strategies. Sampling strategies have been studied for different training regimes. Wu et al. [62] demonstrate that “sampling matters” in the context of metric learning. They propose to sample a triplet with probability proportional to the distance of its positive and negative samples, and observe stabilized training and improved accuracy. This observation was echoed by Katharopoulos and Fleuret [27] when sampling mini-batches: carefully choosing the constituent samples of a minibatch improves the convergence rate and asymptotic performance. Like ours, their method builds on importance sampling [52, 12, 26] but whereas they compute importance weights using the magnitude
  of the model’s gradients, we use the episode’s difficulty. Similar insights were also observed in reinforcement learning, where Schaul et al. [48] suggests a scheme to sample transitions according to the temporal difference error.
  Closer to our work, Sun et al. [55] present a hard-mining scheme where the most challenging classes across episodes are pooled together and used to create new episodes. Observing that the difficulty of a class is intrinsically linked to the other classes in the episode, Liu et al. [33] propose a mechanism to track the difficulty across every class pair. They use this mechanism to build a curriculum [2, 63] of increasingly difficult episodes. In contrast to these two approaches, our proposed method makes use of importance sampling to mimic the target distribution rather than sampling from it directly. This helps achieve fast and efficient sampling without any preprocessing requirements.
sections.heading: 5 Experiments
sections.text: We first validate the assumptions underlying our proposed IS estimator and shed light on the properties of episode difficulty. Then, we answer the question we pose in the introduction, namely: what is the best way to sample episodes? Finally, we ask if better sampling improves few-shot classification.
sections.heading: 5.1 Experimental setup
sections.text: We review the standardized few-shot benchmarks and provide a detailed description in Appendix A.
  Datasets. We use two standardized image classification datasets, Mini-ImageNet [58] and TieredImageNet [45], both subsets of ImageNet [10]. Mini-ImageNet consists of 64 classes for training, 16 for validation, and 20 for testing; we use the class splits introduced by Ravi and Larochelle [43]. Tiered-ImageNet contains 608 classes split into 351, 97, and 160 for training, validation, and testing, respectively.
  Network architectures. We train two model architectures. A 4-layer convolution network conv(64)4 Vinyals et al. [58] with 64 channels per layer. And ResNet-12, a 12-layer deep residual network [23] introduced by Oreshkin et al. [39]. Both architectures use batch normalization [25] after every convolutional layer and ReLU as the non-linearity.
  Training algorithms. For the metric-based family, we use ProtoNet with Euclidean [53] and scaled negative cosine similarity measures [20]. Additionally, we use MAML [15] and ANIL [41] as representative gradient-based algorithms.
  Hyper-parameters. We tune hyper-parameters for each algorithm and dataset to work well across different few-shot settings and network architectures. Additionally, we keep the hyper-parameters the same across all different sampling methods for a fair comparison. We train for 20k iterations with a mini-batch of size 16 and 32 for Mini-ImageNet and Tiered-ImageNet respectively, and validate every 1k iterations on 1k episodes. The best performing model is finally evaluated on 1k test episodes.
sections.heading: 5.2 Understanding episode difficulty
sections.text: All the models in this subsection are trained using baseline sampling as described in Section 2.1, i.e., episodic training without importance sampling.
sections.heading: 5.2.1 Episode difficulty is approximately normally distributed
sections.text: We begin our analysis by verifying that the distribution over episode difficulty induced by q(τ) is approximately normal. In Fig. 1, we use the difficulty of 10k test episodes sampled with q(τ). The difficulties are computed using conv(64)4 trained with ProtoNet and MAML on Mini-ImageNet for 1-shot 5-way classification. The episode difficulty density plots follow a bell curve, which are naturally modeled with a normal distribution. The Q-Q plots, typically used to assess normality, suggest the same – the closer the curve is to the identity line, the closer the distribution is to a normal.
  Finally, we compute the Shapiro-Wilk test for normality [50], which tests for the null hypothesis that the data is drawn from a normal distribution. Since the p-value for this test is sensitive to the
  sample size4, we subsample 50 values 100 times and average rejection rates over these subsets. With α = 0.05, the null hypothesis is rejected 14% and 17% of the time for Mini-ImageNet and Tiered-ImageNet respectively, thus suggesting that episode difficulty can be reliably approximated with a normal distribution.
sections.heading: 5.2.2 Independence from modeling choices
sections.text: By definition, the notion of episode difficulty is tightly coupled to the model likelihood lθ (Section 2.3), and hence to the modeling variables such as learning algorithm, network architecture, and model parameters. We check if episode difficulty transfers across different choices for these variables.
  1.0
  1.5
  2.0
  2.5
  Pr ot
  ot yp
  ica l N
  et wo rk (E uc lid ea n)
  1.0
  1.5
  2.0
  2.5
  Pr ot
  ot yp
  ica l N
  et wo rk (c os in e)
  1.0
  1.5
  2.0
  2.5
  M AM
  L
  1 2 Prototypical Network
  (Euclidean)
  1.0
  1.5
  2.0
  2.5
  AN IL
  1 2 Prototypical Network
  (cosine)
  1 2 MAML
  1 2 3 4 ANIL
  Network architecture. Next we analyze the dependence on the network architecture. We trained conv(64)4 and ResNet-12’s using all training algorithms for Mini-ImageNet 1-shot 5-way classi-
  4For a large sample size, the p-values are not reliable as they may detect trivial departures from normality.
  fication. We compute the episode difficulties for 10k test episodes and compute their Spearman rank-order correlation coefficients across the two architectures, for a given algorithm. The correlation coefficients are 0.57 for ProtoNet (Euclidean), 0.72 for ProtoNet (cosine), 0.58 for MAML, and 0.49 for ANIL. Fig. 3 illustrates this positive correlation, suggesting that episode difficulty is transferred across network architectures with high probability.
  Model parameters during training. Lastly, we study the dependence on model parameters during training. We select the 50 easiest and 50 hardest episodes, i.e., episodes with the lowest and highest difficulties respectively, from 1k test episodes. We track the episode difficulty for all episodes over the training phase and visualize the trend in Fig. 4 for conv(64)4’s trained using different training algorithms on Mini-ImageNet (1-shot 5-way). Throughout training, easy episodes remain easy and hard episodes remain hard, hence suggesting that episode difficulty transfers across different model parameters during training. Since the episode difficulty does not change drastically during the training process, we can estimate it with a running average over the training iterations. This justifies the online modeling of the proposal distribution in Section 3.2.
sections.heading: 5.3 Comparing episode sampling methods
sections.text: We compare different methods for episode sampling. To ensure fair comparisons, we use the offline formulation (Section 3.2) so that all sampling methods share the same pre-trained network (the network trained using baseline sampling) when computing proposal likelihoods. We compute results over 2 datasets, 2 network architectures, 4 algorithms and 2 few-shot protocols, totaling in 24 scenarios. Table 1 presents results on ProtoNet (cosine), while the rest are in Appendix D.
  We observe that, although not strictly dominant, UNIFORM tends to outperform other methods as it is within the statistical confidence of the best method in 19/24 scenarios. For the 5/24 scenarios
  where UNIFORM underperforms, it closely trails behind the best methods. Compared to baseline sampling, the average degradation of UNIFORM is −0.83% and at most −1.44% (ignoring the standard deviations) in 4/24 scenarios. Conversely, UNIFORM boosts accuracy by as much as 8.74% and on average by 3.86% (ignoring the standard deviations) in 13/24 scenarios. We attribute this overall good performance to the fact that uniform sampling puts a uniform distribution prior over the (unseen) test episodes, with the intention of performing well across the entire difficulty spectrum. This acts as a regularizer, forcing the model to be equally discriminative for easy and hard episodes. If we knew the test episode distribution, upweighting episodes that are most likely under that distribution will improve transfer accuracy [13]. However, this uninformative prior is the safest choice without additional information about the test episodes.
  Second best is baseline sampling as it is statistically competitive on 10/24 scenarios, while EASY, HARD, and CURRICULUM only appear among the better methods in 4, 4, and 9 scenarios, respectively.
sections.heading: 5.4 Online approximation of the proposal distribution
sections.text: Although the offline formulation is better suited for analysis experiments, it is expensive as it requires a pre-training phase for the proposal network and 2 forward passes during episodic training (one for the episode loss, another for the proposal density). In this subsection, we show that the online formulation faithfully approximates offline sampling and can retain most of the performance improvements from UNIFORM. We take the same 24 scenarios as in the previous subsection, and compare baseline sampling against offline and online UNIFORM. Table 2 reports the full suite of results.
  We observe that baseline is statistically competitive on 9/24 scenarios; on the other hand, offline and online UNIFORM perform similarly on aggregate, as they are within the best results in 16/24 and 15/24 scenarios respectively. Similar to its offline counterpart, online UNIFORM does better than or comparable to baseline sampling in 21 out of 24 scenarios. On the 3/24 scenarios where online UNIFORM underperforms compared to baseline, the average degradation is −0.92%, and at most −1.26% (ignoring the standard deviations). Conversely, in the remaining scenarios, it boosts accuracy by as much as 6.67% and on average by 2.24% (ignoring the standard deviations). Therefore, using online UNIFORM, while computationally comparable to baseline sampling, results in a boost in few-shot performance; when it underperforms, it trails closely. We also compute the mean accuracy difference between the offline and online formulation, which is 0.07%± 0.35 accuracy points. This confirms that both the offline and online methods produce quantitatively similar outcomes.
sections.heading: 5.5 Better sampling improves cross-domain transfer
sections.text: To further validate the role of episode sampling as a way to improve generalization, we evaluate the models trained in the previous subsection on episodes from completely different domains. Specifically, we use the models trained on Mini-ImageNet with baseline and online UNIFORM sampling to evaluate on the test episodes of CUB-200 [60], Describable Textures [8], FGVC Aircrafts [35], and VGG Flowers [38], following the splits of Triantafillou et al. [57]. Table 3 displays results for ProtoNet (cosine) and MAML on CUB-200 and Describable Textures, with the complete set of experiments available in Appendix F. Out of the 64 total cross-domain scenarios, online UNIFORM does statistically better in 49/64 scenarios, comparable in 12/64 scenarios and worse in only 3/64 scenarios. These results further go to show that sampling matters in episodic training.
sections.heading: 5.6 Better sampling improves few-shot classification
sections.text: The results in the previous subsections suggest that online UNIFORM yields a simple and universally applicable method to improve episode sampling. To validate that state-of-the-art methods can also benefit from better sampling, we take the recently proposed FEAT [64] algorithm and augment it with our IS-based implementation of online UNIFORM. Concretely, we use their open-source implementation5 to train both baseline and online UNIFORM sampling. We use the prescribed hyper-parameters without any modifications. Results for ResNet-12 on Mini-ImageNet and TieredImageNet are reported in Table 4, where online UNIFORM outperforms baseline sampling on 3/4 scenarios and is matched on the remaining one. Thus, better episodic sampling can improve few-shot classification even for the very best methods.
sections.heading: 6 Conclusion
sections.text: This manuscript presents a careful study of sampling in the context of few-shot learning, with an eye on episodes and their difficulty. Following an empirical study of episode difficulty, we propose an importance sampling-based method to compare different episode sampling schemes. Our experiments suggest that sampling uniformly over episode difficulty performs best across datasets, training algorithms, network architectures and few-shot protocols. Avenues for future work include devising better sampling strategies, analysis beyond few-shot classification (e.g., regression, reinforcement learning), and a theoretical grounding explaining our observations.
  5Available at: https://github.com/Sha-Lab/FEAT
title: Uniform Sampling over Episode Difficulty