PaperlayerView exact revision on arXiv

Source-linked AI summary

Meta-Learning and Universality: Deep Representations and Gradient Descent can Approximate any Learning Algorithm

Chelsea Finn, Sergey Levine

arXiv:1710.11622v3cs.LGcs.AIcs.NE

TL;DR

The paper asks whether deep representations combined with standard gradient descent can approximate any learning algorithm, rather than restricting meta-learning to recurrent or black-box procedures. It formalizes learning-algorithm approximation and proves that sufficiently deep MAML can match recurrent meta-learners’ representational power, while experiments find stronger out-of-domain generalization and resilience to overfitting. The result depends on suitable loss functions and assumptions used in the proof.

  • Problem

    The central question is whether gradient-based meta-learning can represent arbitrary functions of training datasets and test inputs, since standard universal approximation does not directly address the gradient operator.

  • Method

    The paper formalizes universal learning-procedure approximation and analyzes MAML using a sufficiently deep ReLU learner with gradient-based updates.

  • Results

    MAML has the same theoretical representational power as recurrent meta-learners, and experiments find more generalizable out-of-domain strategies plus resilience to overfitting.

  • Takeaways & Limitations

    Embedding standard gradient descent into meta-learning has no theoretical expressivity disadvantage relative to universal recurrent meta-learners and can provide practical benefits.

  • Takeaways & Limitations

    Universality does not hold for all losses: ℓ1 and hinge gradients are piecewise constant and lose label information, while the proof also disregards higher-order α terms.

Abstract

from arXiv · show

Learning to learn is a powerful paradigm for enabling models to learn from data more effectively and efficiently. A popular approach to meta-learning is to train a recurrent model to read in a training dataset as input and output the parameters of a learned model, or output predictions for new test inputs. Alternatively, a more recent approach to meta-learning aims to acquire deep representations that can be effectively fine-tuned, via standard gradient descent, to new tasks. In this paper, we consider the meta-learning problem from the perspective of universality, formalizing the notion of learning algorithm approximation and comparing the expressive power of the aforementioned recurrent models to the more recent approaches that embed gradient descent into the meta-learner. In particular, we seek to answer the following question: does deep representation combined with standard gradient descent have sufficient capacity to approximate any learning algorithm? We find that this is indeed true, and further find, in our experiments, that gradient-based meta-learning consistently leads to learning strategies that generalize more widely compared to those represented by recurrent models.

1 INTRODUCTION

Meta-learning can either use recurrent models to map datasets to learner parameters or predictions, or learn representations adapted through gradient descent. The paper compares these approaches theoretically and studies MAML’s behavior under extended optimization.

  • Recurrent meta-learners ingest training datasets and output learner parameters or predictions for new test inputs.
  • MAML learns initial learner parameters that are adapted with standard gradient descent at meta-test time.
  • MAML has the same theoretical representational power as recurrent meta-learners when the learner is sufficiently deep.
  • MAML initializations remain resilient to overfitting tiny datasets even after many more gradient steps than used during meta-training.

2 PRELIMINARIES

The preliminaries introduce universal function approximation, MAML, and recurrent or optimization-based alternatives. MAML meta-learns an initialization so a few task-specific gradient steps produce effective generalization.

  • Universal function approximation: The universal function approximation theorem states that finite-width one-hidden-layer networks can approximate any continuous function on compact subsets of R^n.The theorem applies to activation functions including sigmoid and ReLU.
  • Model-agnostic meta-learning: MAML learns initial parameters θ such that one or a few gradient steps using small task-specific datasets yield effective generalization.The objective is computed over many tasks.
  • Model-agnostic meta-learning: After meta-training across tasks, MAML adapts to held-out tasks by running gradient descent from the meta-learned representation.
  • Architectural extension: A learned bias transformation concatenates parameters to the input and increases the expressive power of the error gradient without changing model expressivity.The paper uses this modification as a symmetry-breaking mechanism in its universality proof.

3 META-LEARNING AND UNIVERSALITY

The paper formalizes universality as representing functions of training datasets and test inputs, then asks whether gradient-based MAML can match recurrent meta-learners. It targets one-shot and permutation-invariant K-shot settings.

  • Recurrent meta-learners: Recurrent meta-learners can directly represent functions of a task dataset and test input when they satisfy universal approximation conditions.
  • Parameter-generating meta-learners: Some meta-learners map a dataset to updated learner parameters, after which the learner predicts the output for a test input.These approaches can be as expressive as direct dataset-to-prediction models.
  • MAML and universality: MAML replaces recurrent weight updates with standard gradient descent, but its ability to represent arbitrary dataset-dependent functions is not immediate from the universal approximation theorem.The theorem does not directly address the gradient operator.
  • Universality goals: The paper aims to prove one-shot universality and K-shot universality for functions invariant to datapoint permutations, across discrete and continuous labels and selected losses.
  • Universality goals: A sufficiently deep fully connected ReLU network can approximate any function of the dataset and test input after a single gradient step.

4 UNIVERSALITY OF THE ONE-SHOT GRADIENT-BASED LEARNER

The one-shot proof constructs a sufficiently deep ReLU learner whose post-update prediction can approximate any target function of a training pair and test input. The construction separates forward and backward information flow through a single gradient update.

  • One-shot setup: A universal one-shot learning algorithm approximator represents any target function f_target(x, y, x⋆) to arbitrary precision.
  • Deep gradient construction: A single gradient update to one weight matrix is rank-1, while sequencing N linear layers enables a rank-N update to the represented function.
  • Deep gradient construction: The constructed learner uses a deep ReLU network whose intermediate layers behave as linear layers under non-negative activations.The feature extractor and output function are universal approximators.
  • Information-flow construction: The proof independently controls information from x, y, and x⋆ by multiplexing forward information from inputs with backward information from labels.
  • Information-flow construction: The selected weight matrices and network construction satisfy non-negative activation conditions while enabling the required post-update form.
  • Universality result: The resulting post-update function can approximate any continuous function of (x, y, x⋆) on compact subsets under the lemma’s gradient assumption.The construction represents the function as weighted basis components passed through an output network.
  • Universality result: The proof establishes one-shot universality, and the paper extends the result next to K-shot learning algorithms.

5 GENERAL UNIVERSALITY OF THE GRADIENT-BASED LEARNER

The K-shot gradient-based learner can approximate any permutation-invariant function of a training dataset and test datapoint, including when K is not small.

  • 5 GENERAL UNIVERSALITY OF THE GRADIENT-BASED LEARNER: MAML is analyzed in the general K-shot setting, where K need not be small.The section extends the single-example analysis and presents differences from the 1-shot setting, with a full proof in Appendix B.
  • 5 GENERAL UNIVERSALITY OF THE GRADIENT-BASED LEARNER: The learner’s parameters are updated using the K-shot gradient-based update rule.The section defines the update rule for f̂(·, θ) before specifying the post-update function.
  • 5 GENERAL UNIVERSALITY OF THE GRADIENT-BASED LEARNER: The universality construction treats bias parameters as part of the input to address symmetry in the kernels.This interpretation makes the left input (x, θb) and the right input (x⋆, θ′b), under the stated compact-output assumption.
  • 5 GENERAL UNIVERSALITY OF THE GRADIENT-BASED LEARNER: The post-update function can approximate any ordering-invariant function of the training datapoints and test input.The construction selects parameters so an intermediate vector contains a discretized test input and frequency counts of discretized training datapoints; a universal post-function then approximates the target function.

6 LOSS FUNCTIONS

Gradient-based meta-learning requires the loss gradient to preserve label information; standard mean-squared error and softmax cross entropy satisfy this condition, whereas several other losses do not.

  • 6 LOSS FUNCTIONS: Universality requires labels to be recoverable from the loss gradient.The pre-update function back-propagates label information through the gradient, so the gradient must encode the label sufficiently for the construction.
  • 6 LOSS FUNCTIONS: The label embeddings e(y) and ě(y) must represent at least any linear function of the label y.This is the label-linearity property used in the gradient-based universality argument.
  • 6 LOSS FUNCTIONS: At zero prediction, the loss gradient must be an invertible linear function of y for labels to remain recoverable.The construction sets the pre-update prediction to zero and requires ∇ŷℓ(y, 0) = Ay with A invertible.
  • 6 LOSS FUNCTIONS: The standard mean-squared error and softmax cross entropy losses satisfy the condition needed for universality.Their gradients at zero are each characterized as linear, invertible functions of the label.
  • 6 LOSS FUNCTIONS: The ℓ1, hinge, and some Huber-loss gradients do not support universality because their piecewise-constant gradients lose label information.A gradient alone is insufficient to determine the label for these losses; gradient-input recurrent meta-learners can suffer the same information loss.

7 EXPERIMENTS

The experiments compare gradient-based and recurrent meta-learners on additional adaptation, out-of-distribution tasks, and representation depth. MAML further improves with extended fine-tuning, generalizes better under task variation, and benefits from deeper representations.

  • 7.1 EMPIRICAL STUDY OF INDUCTIVE BIAS: MAML can improve beyond its five meta-training gradient steps, especially on out-of-distribution sinusoid tasks.On Omniglot, a MAML model trained with five inner steps can be fine-tuned for 100 steps without test-accuracy loss.
  • 7.1 EMPIRICAL STUDY OF INDUCTIVE BIAS: Random initialization reaches perfect training accuracy but overfits the 20 examples, whereas MAML retains good test accuracy during fine-tuning.The MAML-initialized model does not begin to overfit even when fine-tuned for up to 100 steps.
  • 7.1 EMPIRICAL STUDY OF INDUCTIVE BIAS: All three methods perform similarly on in-distribution 5-way 1-shot Omniglot classification and 5-shot sinusoid regression.The comparisons then vary shearing, scaling, amplitude, and phase to create related but out-of-distribution tasks.
  • 7.1 EMPIRICAL STUDY OF INDUCTIVE BIAS: MAML recovers more generalizable learning strategies than recurrent meta-learners on tasks outside the training distribution.Figure 3 evaluates learning performance as task variability changes, including extrapolated sinusoid amplitudes and phases.
  • 7.2 EFFECT OF DEPTH: With a fixed parameter count, MAML benefits from additional depth, while task-conditioned models need no more than one hidden layer.The depth experiment reports standard-deviation error bars over three training runs.

8 CONCLUSION

The paper concludes that deep representations combined with gradient descent can approximate any learning algorithm without a theoretical expressivity disadvantage. Its experiments also associate MAML with stronger out-of-domain performance and resilience to overfitting.

  • 8 CONCLUSION: A sufficiently deep neural network’s initial weights combined with gradient descent can approximate any learning algorithm.The paper formalizes learning-procedure approximation through functions of datasets and test inputs.
  • 8 CONCLUSION: MAML learning strategies are more successful than recurrent learners on out-of-domain tasks across the reported experiments.The conclusion presents this as an empirical comparison, alongside the theoretical expressivity result.
  • 8 CONCLUSION: MAML representations are highly resilient to overfitting.The conclusion identifies this resilience as a practical benefit of gradient-based meta-learning.
  • 8 CONCLUSION: The paper introduces a formal perspective on whether meta-learners can represent functions of training datasets and test inputs.This formalism is intended to support further discussion and research on learning to learn.

A.1 PROOF OF LEMMA 4.1

The proof constructs a sufficiently deep gradient-based learner whose post-update function retains a complete description of the training input, label, and test input. A universal post-update network can therefore approximate any continuous function of these variables on compact domains.

  • A.1 PROOF OF LEMMA 4.1: Consequently, the constructed model can approximate any continuous function of (x, y, x⋆) on compact subsets of R^dim(y).The lemma assumes that e(y) may be chosen as any linear, non-affine function of y.
  • A.1 PROOF OF LEMMA 4.1: The construction uses small epsilon-scaled identity matrices to effectively ignore boundary terms while maintaining positive definiteness.This choice is made for B_1 and A_N, with analogous definitions appearing in the proof.
  • A.1 PROOF OF LEMMA 4.1: The construction uses one-hot discretization to index training and test inputs through the variables j and l.The function k_jl is one when discr(x)=e_j and discr(x⋆)=e_l, and zero otherwise.
  • A.1 PROOF OF LEMMA 4.1: The label encoding duplicates y across positions, while A_jl selects the copy associated with the input and test-input indices.A small positive epsilon is added to preserve positive definiteness in the constructed matrices.
  • A.1 PROOF OF LEMMA 4.1: The post-update vector −αv(x, x⋆, y) completely describes x, x⋆, and y because each can be decoded from it.The proof then applies universal approximation to the post-update function.
  • A.1 PROOF OF LEMMA 4.1: The proof chooses network components so the gradient update independently carries information from x, y, and x⋆.Forward information is supplied by x, while backward information from the error gradient carries y.
  • A.1 PROOF OF LEMMA 4.1: The output network approximates a multiplexer function and its derivatives, enabling the post-update output expression when z⋆ is nonzero.The proof also assumes zero-bias networks with nonlinearities that output zero at zero.

B FULL K-SHOT PROOF OF UNIVERSALITY

The proof constructs a sufficiently deep network whose one-step gradient update can approximate any permutation-invariant function of a K-point training set and a test input. It achieves this by independently controlling forward input information, backward label information, and their post-update combination.

  • The construction targets any permutation-invariant function of K training datapoints and a test datapoint, without requiring K to be small.
  • The learner parameters update by one gradient step with learning rate α, using standard cross-entropy or mean-squared-error losses.The proof excludes arbitrary loss functions but identifies these two standard supervised objectives as suitable.
  • The network separates forward information from training and test inputs from backward information carried by training labels through decomposed weights, features, and error gradients.This multiplexing enables independent control of the three information sources during the construction.
  • The output function combines label-dependent basis vectors weighted by input-dependent terms and passes their sum into a post-update neural network.The input-dependent terms can be viewed as a kernel-like weighting, although the kernel connection is not needed for the proof.
  • A bias transformation variable breaks symmetry in the input-dependent weighting, which is necessary to represent arbitrary functions of training and test inputs after one update.
  • The construction concludes that a suitable neural network structure makes the post-update predictor a universal approximator of target learning algorithms.

C SUPPLEMENTARY PROOF FOR K-SHOT SETTING

The supplementary K-shot proof extends the one-shot construction to arbitrary training-set size while preserving permutation invariance. It uses discretized input indicators and positive-definite matrix constructions to route label information into the post-update predictor and realize a ReLU network.

  • The proof shows that the post-update function can approximate any ordering-invariant function of K training pairs and a test input.
  • The construction uses indicator functions over one-hot discretizations of training and test inputs to select the relevant input pair.
  • Matrices A_jl select the label copy associated with each discretized training-test input pair, while positive offsets preserve positive definiteness.
  • For discrete one-shot labels, the summation represents frequency counts; for continuous labels, the proof assumes that no two datapoints share the same input value.
  • Because the post-update input contains all required dataset and test-input information, a universal post-processing network can approximate the target function.
  • The linear-layer construction can be represented by a generic deep ReLU network because its inputs and intermediate activations are non-negative.

E PROOF OF THEOREM 6.1

The theorem proof establishes that standard mean-squared error and softmax cross-entropy provide label gradients with the invertibility needed by the universality construction. The surrounding experiments compare gradient-based and recurrent strategies under distribution shift and extended optimization.

  • Theorem 6.1 states that mean-squared-error gradients evaluated at zero predictions are linear and invertible functions of the labels.
  • For mean-squared error, the gradient at zero prediction is −y, corresponding to the invertible matrix A = −I.
  • In the Figure 6 comparison, gradient descent shows better out-of-distribution generalization than recurrent meta-learned strategies such as SNAIL.
  • A MAML initialization avoids overfitting on five Omniglot training examples even after 100 gradient steps, unlike a randomly initialized network.
  • Theorem 6.2 states that softmax cross-entropy gradients with respect to pre-softmax logits are linear and invertible in one-hot labels when evaluated at zero.
  • The cross-entropy gradient can be written as (C − I)y, and the proof states that C − I is invertible.
Loading 1710.11622v3…