PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Gradient-Based Meta-Learning Methods

Mikhail Khodak, Maria-Florina Balcan, Ameet Talwalkar

arXiv:1906.02717v3cs.LGcs.AIstat.ML

TL;DR

The paper addresses the limitation of fixed-point task-similarity assumptions in gradient-based meta-learning. It introduces ARUBA, which reduces meta-learning to online learning over data-dependent regret upper bounds and supports adaptive, dynamic, geometric, and statistical analyses. The framework produces sharper transfer-risk and regret guarantees and improves meta-test-time performance for few-shot and federated learning.

  • Problem

    Existing gradient-based meta-learning theory largely uses fixed-point task similarity and often requires similarity information or tuning choices in advance.

  • Method

    ARUBA analyzes meta-learning through online learning of task-specific regret upper bounds, enabling adaptive learning of similarity and per-coordinate rates.

  • Results

    ARUBA yields adaptive, dynamic, geometric, and statistical learning-to-learn guarantees and improves meta-test-time performance on few-shot and federated learning.

  • Takeaways & Limitations

    The framework provides a general route for deriving practical meta-learning methods from online-learning algorithms while adapting to task structure.

  • Takeaways & Limitations

    Using the last or average within-task iterate instead of the exact OMD/FTRL solution incurs an additional o(√m) regret term under a quadratic growth assumption.

Abstract

from arXiv · show

We build a theoretical framework for designing and understanding practical meta-learning methods that integrates sophisticated formalizations of task-similarity with the extensive literature on online convex optimization and sequential prediction algorithms. Our approach enables the task-similarity to be learned adaptively, provides sharper transfer-risk bounds in the setting of statistical learning-to-learn, and leads to straightforward derivations of average-case regret bounds for efficient algorithms in settings where the task-environment changes dynamically or the tasks share a certain geometric structure. We use our theory to modify several popular meta-learning algorithms and improve their meta-test-time performance on standard problems in few-shot learning and federated learning.

1 Introduction

The paper introduces ARUBA to move gradient-based meta-learning beyond fixed-point task similarity, enabling adaptive methods for dynamic, geometric, and statistical learning-to-learn settings.

  • Background: Gradient-based meta-learning uses a shared initialization φ to adapt models to new tasks through within-task gradient descent.This parameter-transfer approach is used in vision, federated learning, and robotics.
  • Motivation: Previous theoretical work largely modeled task similarity as closeness to one fixed parameter-space point.
  • ARUBA: ARUBA treats meta-learning as online learning over task-specific regret upper bounds whose data-dependent forms encode richer task similarity.The bounds are designed to be compatible with online convex optimization.
  • Contributions: ARUBA learns task similarity on the fly, avoiding known-similarity learning rates, regularization choices, and doubling-trick tuning.
  • Contributions: ARUBA reduces changing-initialization meta-learning to dynamic regret minimization, allowing existing online algorithms with guarantees to be applied.
  • Contributions: ARUBA adapts to inter-task geometry, improves meta-test performance on few-shot learning, and adds tuning-free user personalization to FedAvg.
  • Contributions: For statistical learning-to-learn, ARUBA derives sharper transfer-risk bounds, including fast task-rate guarantees and high-probability results covering linear regression.

2 Average Regret-Upper-Bound Analysis

ARUBA analyzes meta-learning by running low-regret online algorithms on task-specific regret upper bounds, converting their average into task-averaged regret and statistical guarantees.

  • Framework: The framework studies online learning of functions U_t(x) that upper-bound each task's regret R_t(x).
  • Framework: These upper bounds are often smooth or convex, depend on both parameterization and task data, and therefore support adaptive meta-learning.
  • Consequences: A small average regret upper bound implies small task-averaged regret and can also yield statistical learning guarantees in batch settings.
  • Consequences: ARUBA applies any low-regret algorithm over U_t to obtain a vanishing-in-T term plus a data-dependent task-similarity term.
  • Example: OGD: O(GV√m) task-averaged regret improves over O(GD√m) single-task regret when optimal actions are close, with V ≪ D.Here V measures dispersion of task-optimal actions, while D is the ℓ2-radius of Θ.

3 Adapting to Similar Tasks and Dynamic Environments

The section develops ARUBA-based GBML methods that adapt initialization and learning rates to task similarity, dynamic environments, and inter-task geometry. These methods yield regret guarantees tied to task variation and support practical adaptive updates.

  • Task similarity: Task similarity is measured with Bregman divergence, which generalizes Euclidean distance and supports fixed or changing comparator sequences.Dynamic regret compares the learned initialization with a potentially time-varying reference sequence.
  • Adaptive updates: The adaptive algorithm learns task similarity online rather than requiring a known similarity level or a doubling-trick estimate.SIM updates the learning-rate parameter while INIT updates the meta-initialization.
  • ARUBA framework: ARUBA reduces GBML meta-learning to online learning over regret upper bounds, enabling separate adaptation of initialization and learning rate.The framework uses OCO algorithms INIT and SIM for the two parameter sequences.
  • Similar tasks in static environments: For similar static tasks, average regret converges to O(VΨ/√m) when INIT and SIM have sublinear regret.Here VΨ measures deviation of optimal task actions from a fixed comparator, and the bound tends to zero when V=o(T).

4 Adapting to the Inter-Task Geometry

ARUBA extends gradient-based meta-learning beyond similarity to a single initialization by learning geometric structure across task directions. Its adaptive per-coordinate and matrix-based methods use online optimization to improve within-task adaptation while providing convergence guarantees.

  • Geometric task-similarity: ARUBA models task-similarity through an initialization φ and positive-definite matrix H, rather than only closeness to one fixed point.The matrix defines the regularization geometry used by the within-task method.
  • Per-coordinate adaptation: The diagonal method learns a per-coordinate learning rate η from task history and uses it in coordinate-wise gradient updates.Its construction is related to AdaGrad but incorporates multi-task distances in the numerator.
  • Guarantees: As T →∞, average regret converges to the minimum over initialization and per-coordinate learning rates, with convergence rate T^-2/5.The slower rate reflects adaptivity to within-task gradients instead of assuming known gradient bounds.
  • Guarantees: A full-matrix adaptive regularizer is also covered, but without additional assumptions it requires Ω(d^2) computation and memory.The full-matrix guarantee has a substantially slower rate than the diagonal method.

5 Fast Rates and High Probability Bounds for Statistical Learning-to-Learn

ARUBA converts statistical learning-to-learn analysis into online-to-batch transfer-risk bounds for gradient-based methods. The resulting guarantees include high-probability bounds, fast rates under strong convexity, and adaptive learning of task similarity when it is unknown.

  • Transfer-risk bounds: ARUBA applies online-to-batch conversion to derive transfer-risk bounds for convex regret-upper-bounds in the distribution-over-task-distributions setting.The bounds concern the averaged parameter obtained by running OMD or FTRL on samples from a new task.
  • Transfer-risk bounds: In the general case, excess transfer risk decreases with ¯U/m and 1/√T, so improved average regret-upper-bounds improve asymptotic transfer risk.The statement applies to the general transfer-risk guarantee.
  • Statistical guarantees: For self-bounded losses, including linear regression, ARUBA obtains high-probability guarantees rather than only in-expectation bounds.The self-bounded-loss result uses specialized online-to-batch conversion results.
  • Statistical guarantees: Strongly convex regret-upper-bounds enable fast rates in the number of tasks T.This result is obtained through an online-to-batch conversion for strongly convex losses.
  • Statistical guarantees: When task variance V_Q is known, learning the initialization achieves a faster rate than the O(1/√T) second-term rate reported for Denevi et al.When V_Q is unknown and the learning rate must also be learned, ARUBA matches that rate up to additional fast o(1/√m) terms; the comparisons are not directly equivalent because the similarity measures differ.

6 Empirical Results: Adaptive Methods for Few-Shot & Federated Learning

The empirical procedure replaces a fixed GBML learning rate with rates learned online from per-coordinate task distances and gradients. It is evaluated by modifying GBML methods for few-shot classification and federated next-character prediction.

  • Adaptive algorithm: Algorithm 2 tracks per-coordinate squared distances and gradient norms to replace a generic GBML learning rate with an on-the-fly learned rate.The generic procedure initializes a task model, performs within-task gradient steps, and updates the meta-initialization.
  • Few-shot classification: Table 1 reports meta-test-time performance of GBML algorithms using both first-order and second-order results.The first-order and second-order results come from Nichol et al. and Li et al., respectively.
  • Adaptive algorithm: ARUBA increases learning rates in directions with greater task-to-task variation and assigns faster rates to deeper layers than to lower-level feature extractors.This behavior is reported as matching standard parameter-transfer intuition.
  • Few-shot classification: The experiments modify Reptile for Omniglot and Mini-ImageNet few-shot classification benchmarks.The passage identifies these as standard few-shot learning benchmarks.

7 Conclusion

The paper presents ARUBA as an online-learning framework for adaptive, dynamic, and statistical learning-to-learn. It also derives a per-coordinate learning rate that improves GBML training and meta-test performance in few-shot and federated learning.

  • Conclusion: ARUBA provides new guarantees for adaptive, dynamic, and statistical learning-to-learn through online learning.The framework is presented as flexible and consequential for analyzing gradient-based meta-learning.
  • Conclusion: Its per-coordinate learning rate applies to generic GBML procedures and improves training and meta-test-time performance on few-shot and federated learning tasks.The conclusion identifies these as the demonstrated application areas.

A Background and Results for Online Convex Optimization

The appendix develops core convex-analysis and online-learning tools, including regret guarantees for FTRL, OMD, FTL, AOGD, and EWOO, plus online-to-batch conversions. It also presents a strongly convex coupling trick for transferring FTL guarantees to broader function sequences.

  • Foundations: Convexity, smoothness, exp-concavity, Bregman divergences, and regret provide the analytical foundations for the appendix.The appendix assumes convex subsets in finite-dimensional inner-product spaces and introduces the associated norm and projection notation.
  • Online algorithms: FTRL and lazy linearized OMD are closely connected and share regret guarantees for convex Lipschitz losses under strongly convex regularization.The formulations are equivalent for linear losses, while OMD updates in the dual space induced by its regularizer.
  • Online algorithms: FTL and AOGD achieve logarithmic-regret bounds on sequences of convex, Lipschitz, strongly convex losses.The guarantee applies when losses have per-round strong-convexity parameters α_t and Lipschitz constants G_t.
  • Online algorithms: EWOO provides a regret guarantee for exp-concave losses without explicit dependence on the Lipschitz constant, although it is difficult to run in high dimensions.The appendix uses EWOO in one-dimensional computations requiring only one integral.
  • Online-to-batch conversion: Online-to-batch conversions transform regret guarantees into expected or high-probability generalization bounds, with faster rates available for strongly convex losses.Additional results cover self-bounding losses and bounded nonnegative losses using concentration arguments.
  • Coupling: A strongly convex coupling argument bounds FTL regret for possibly non-convex Lipschitz sequences when FTL plays the same actions on a strongly convex surrogate sequence.The result is identified as potentially independently useful.

B.1 Derivation

This section derives regret bounds by coupling possibly non-convex loss sequences to strongly convex surrogates with identical FTL actions. The approach yields logarithmic regret for Bregman regularizers and sublinear regret for selected non-Lipschitz convex losses.

  • Strongly convex coupling: Theorem B.1 transfers FTL guarantees from a strongly convex Lipschitz sequence to another sequence producing identical actions.The original losses may be non-convex, while the surrogate losses supply the strong-convexity needed for stability analysis.
  • Bregman regularizers: Bregman-regularizer losses can be non-convex, yet FTL obtains logarithmic regret through coupling to squared Euclidean-distance surrogates.For the Euclidean norm, the Bregman regularizer is 1/2∥θ_t−φ∥_2^2 and its Lipschitz constant is bounded by the domain diameter.
  • Non-Lipschitz losses: A coupled ε-FTL construction obtains ˜O(T^3/5)-regret for a sequence of non-Lipschitz convex functions.The algorithm runs FTL on modified losses indexed by ε>0.

C Adaptive and Dynamic Guarantees

The section combines within-task initialization and meta-level similarity updates to obtain adaptive and dynamic task-averaged regret guarantees. It analyzes FTL, AOGD, ε-FTL, and ε-EWOO under convexity, boundedness, and related assumptions.

  • Algorithmic decomposition: Algorithm 1 separates adaptation into INIT, which controls initialization regret, and SIM, whose static regret decreases with task similarity.The meta-update receives task-dependent quantities such as σ_t and Bregman-divergence terms.
  • Adaptive guarantees: Under bounded Bregman divergence, FTL or Euclidean AOGD for INIT combined with ε-FTL for SIM yields adaptive task-averaged regret bounds.The result is stated in Corollary C.1 under the assumptions of Theorem C.1.
  • Similarity updates: The similarity losses used by ε-EWOO are analyzed through Lipschitzness and exp-concavity over a domain bounded away from zero.The construction introduces ε and derives the relevant exp-concavity parameter by optimizing over x and modified task quantities.
  • Adaptive guarantees: ε-EWOO supplies an alternative similarity update for Algorithm 1 under the assumptions of Theorem C.1.The resulting guarantees are stated for FTL or Euclidean AOGD initialization procedures.
  • Dynamic guarantees: Dynamic guarantees incorporate a reference sequence whose variation is measured through path length, allowing changing environments to be analyzed when the reference varies slowly or sparsely.The framework compares dynamic regret against a sequence of reference parameters.

D Adapting to the Inter-Task Geometry

This section extends adaptive meta-learning to inter-task geometry by learning diagonal or full matrix structure for coordinate-wise or directional updates. The resulting analyses use strongly coupled FTL constructions and matrix-valued regularization.

  • Coordinate-wise adaptation: A per-coordinate learning-rate method tracks squared initialization distances and gradients to adapt updates to task geometry.The rate increases along directions with greater distance traveled across tasks.
  • Diagonal geometry: The diagonal-matrix analysis exploits separability across coordinates and applies FTL to modified strongly convex losses.The construction uses element-wise operations and weighted norms to obtain a coordinate-wise regret analysis.
  • Diagonal geometry: Theorem D.1 analyzes an adaptive update over a bounded convex subset of R^d using positive definite diagonal matrices and task sequences of m convex Lipschitz losses.The update sets H through coordinate-wise quantities derived from the history of task parameters and gradients.
  • Matrix geometry: The matrix-valued extension uses trace-based losses and a unique positive definite solution relating B_t^2 to H G_t^2.The analysis relies on operator convexity and spectral properties of symmetric matrices.

E Online-to-Batch Conversion for Task-Averaged Regret

This section derives online-to-batch guarantees that convert task-averaged regret bounds into high-probability transfer guarantees under convexity, boundedness, and regularity assumptions. The results cover general, Lipschitz, strongly convex, and self-bounded loss settings, including adaptive learning-rate meta-learning.

  • General conversion: Theorem E.1 converts a meta-learning algorithm’s task-averaged regret bound into a high-probability guarantee for an averaged action under convex losses.The setup samples tasks from distributions drawn from Q and averages within-task actions.
  • Adaptive learning rates: Corollary E.1 extends the conversion analysis to Algorithm 1 when the learning rate ηt is learned using ε-EWOO.The corollary applies under the assumptions of Theorems 3.2 and 5.1 and Lipschitz losses.
  • General conversion: Convex, nonnegative, B√m-bounded regret upper bounds yield online-to-batch bounds controlled by the total regret upper bound ¯UT.The regret upper bound is treated as a function of the task state in a convex Euclidean state space.
  • Regularity conditions: Strong convexity and Lipschitzness of regret upper bounds support sharper conversion results, including an additional bound under ρ-self-bounded losses.Theorem E.3 assumes nonnegative, B√m-bounded, G-Lipschitz, α-strongly-convex regret upper bounds and gives high-probability guarantees.
  • OGD specialization: Corollary E.2 specializes the results to bounded Θ and online gradient descent with a fixed learning rate.The stated specialization assumes G-Lipschitz losses and uses Algorithm 1 with OGD.
  • Appendix extensions: The appendix frames adaptive task-similarity learning through regret-upper-bound analysis and states that its guarantees avoid the doubling-trick ∆max-error term.It also describes extensions to approximate meta-updates under quadratic growth and adaptive task-similarity.

F.1 Average Regret using Fixed Task Similarity

This section analyzes average regret when task similarity is fixed or adaptively learned under the appendix framework. It states fixed-similarity guarantees and relates the task-similarity measure to prior measures under quadratic growth.

  • Fixed task similarity: Theorem F.1 gives a regret upper-bound guarantee when SIM always uses a fixed task-similarity parameter ε.The result assumes the conditions of Assumption F.1 and applies to Algorithm 3.
  • Adaptive task similarity: Theorem F.2 analyzes adaptive task-similarity by running an online convex optimization algorithm on functions combining Bregman-divergence terms with reciprocal and linear action terms.The adaptive procedure has regret RT and a parameter ε controlling the minimum action.
  • Relation to prior measures: Proposition F.1 relates the paper’s task-similarity measure to Denevi et al.’s measure under an α-quadratic-growth condition.The proposition considers losses drawn from P ∼ Q and compares expected distances involving optimal parameters.
  • Experiments: The experimental appendix evaluates Reptile and FedAvg with Algorithm 2 across few-shot vision and Shakespeare next-character prediction settings.Figures 4–6 report final layerwise learning rates for Omniglot and Mini-ImageNet, while Figure 7 reports them for an LSTM on Shakespeare.
Loading 1906.02717v3…