Source-linked AI summary
Meta-Learning with Differentiable Convex Optimization
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, Stefano Soatto
TL;DR
Few-shot meta-learning commonly uses simple base learners, despite evidence that discriminatively trained linear classifiers can generalize better and exploit richer embeddings. MetaOptNet learns representations with differentiable convex linear learners using implicit KKT differentiation and dual optimization, achieving state-of-the-art performance across four benchmarks. The approach offers higher embedding dimensions and better generalization at a modest computational cost, while large embeddings can make forward and backward passes expensive.
Problem
Few-shot meta-learning needs base learners that generalize well from limited examples, while commonly used nearest-neighbor rules may underuse negative examples and high-dimensional embeddings.
Method
MetaOptNet learns embeddings end-to-end with regularized linear classifiers by differentiating convex QP KKT conditions and solving the dual problem.
Results
MetaOptNet achieves state-of-the-art performance on miniImageNet, tieredImageNet, CIFAR-FS, and FC100 few-shot benchmarks.
Takeaways & Limitations
Regularized linear models offer better generalization than nearest-neighbor classifiers, support higher embedding dimensions with reduced overfitting, and add only modest computational cost.
Takeaways & Limitations
Forward and backward passes can be expensive when the embedding dimension is large, and the reported SVM advantage is hypothesized to depend on semantic overlap between training and test data.
Abstract
from arXiv · showhide
Many meta-learning approaches for few-shot learning rely on simple base learners such as nearest-neighbor classifiers. However, even in the few-shot regime, discriminatively trained linear predictors can offer better generalization. We propose to use these predictors as base learners to learn representations for few-shot learning and show they offer better tradeoffs between feature size and performance across a range of few-shot recognition benchmarks. Our objective is to learn feature embeddings that generalize well under a linear classification rule for novel categories. To efficiently solve the objective, we exploit two properties of linear classifiers: implicit differentiation of the optimality conditions of the convex problem and the dual formulation of the optimization problem. This allows us to use high-dimensional embeddings with improved generalization at a modest increase in computational overhead. Our approach, named MetaOptNet, achieves state-of-the-art performance on miniImageNet, tieredImageNet, CIFAR-FS, and FC100 few-shot learning benchmarks. Our code is available at https://github.com/kjunelee/MetaOptNet.
1. Introduction
Few-shot meta-learning learns embeddings whose base learners generalize across tasks, but nearest-neighbor rules can be outperformed by regularized linear classifiers. MetaOptNet makes such convex learners practical through differentiable optimization and reports state-of-the-art results across several benchmarks.
- Motivation: Few-shot meta-learning learns an embedding model and base learner that minimize generalization error across tasks with few training examples.Each task contains a few-shot training set and a test set.
- Motivation: Regularized linear classifiers can outperform nearest-neighbor classifiers by using negative examples and high-dimensional embeddings while controlling capacity.Weight sparsity or norm regularization provides capacity control.
- Approach: MetaOptNet uses linear SVMs as base learners and exploits convexity, implicit differentiation of KKT conditions, and dual low-rank structure for efficient meta-learning.The dual formulation reduces the number of optimization variables in few-shot settings.
- Approach: A differentiable QP solver enables end-to-end learning with multiclass SVMs or linear regression for few-shot classification.The solver supports differentiating the learner with respect to the embedding model.
2. Related Work
Prior work backpropagates through optimization using unrolling or analytic differentiation, while MetaOptNet formulates linear classification as convex optimization. KKT-based implicit differentiation and GPU QP solvers provide a practical route for learning representations with flexible convex learners.
- Meta-learning approaches: Meta-learning methods include gradient-based adaptation, nearest-neighbor prediction, and other approaches that learn task-general biases or priors.Nearest-neighbor methods learn distance-based prediction rules over embeddings.
- Differentiating through optimization: Unrolling optimization requires storing intermediate optimizer states, which can create prohibitive storage overhead for large problems.Analytic gradients are available when an argmin has a closed-form solution, such as unconstrained quadratic minimization.
- Convex optimization: MetaOptNet formulates linear classifiers as convex quadratic programs and backpropagates through their KKT conditions using the implicit function theorem.The approach uses efficient GPU routines for QP solutions and gradients.
- Convex optimization: The framework supports other loss functions and nonlinear kernels, including ridge regression as an alternative convex learner.Experiments focus on hinge loss with ℓ2 regularization.
3. Meta-learning with Convex Base Learners
The framework learns an embedding by evaluating convex linear base learners on task test sets, then differentiating through their optimal solutions. Dual optimization reduces dependence on feature dimension, making the approach practical for few-shot meta-learning.
- Problem formulation: Few-shot meta-learning learns an embedding whose task-specific base learner generalizes from support examples to unseen task examples.Tasks contain training and test datasets, and held-out meta-validation tasks select hyperparameters and the embedding model.
- Episodic sampling of tasks: Episodes sample K categories, N support examples per category, and Q query examples, with train, validation, and test categories mutually disjoint.Support and query sets are sampled separately without replacement to measure generalization to unseen categories.
- Convex base learners: The base learner uses a convex multiclass linear classifier, including SVMs, logistic regression, or ridge regression, trained on embedded support examples.The SVM objective is convex, and its unique optimum permits differentiation with respect to the embedding features.
- Differentiating through optimization: Implicit differentiation through the KKT conditions computes gradients from the optimum without backpropagating through the entire optimization trajectory.Because the convex solution is unique, the gradient does not depend on the optimization trajectory or initialization and requires less memory.
- Computational considerations: The method’s backward pass costs O(d^2) after forward factorization, while the forward QP solve costs O(d^3), making large embeddings computationally expensive.Both passes can be expensive when the embedding dimension is large.
- Dual formulation: The dual QP has optimization size equal to the number of training examples times the number of classes, often smaller than the feature dimension.The QP solver’s runtime is comparable to feature computation with ResNet-12, while the linear SVM shows a slight advantage over ridge regression.
4. Experiments
Experiments evaluate MetaOptNet across ImageNet- and CIFAR-derived few-shot benchmarks, comparing architectures, base learners, training-shot choices, and optimization efficiency. Results show strong benchmark performance, benefits from discriminative classifiers with high-dimensional embeddings, and modest computational overhead.
- Comparisons between base learners: When embeddings are 16000-dimensional, SVMs yield better few-shot accuracy than other base learners, whereas 1600-dimensional features show no substantial discriminative-classifier benefit.Regularized linear classifiers provide robustness when high-dimensional features are available.
- Comparisons between base learners: MetaOptNet-SVM performance generally increases for both 1-shot and 5-shot evaluation as meta-training shot increases.This supports meta-training one embedding with a high shot for all meta-testing shots.
- Comparisons between base learners: For ResNet-12, ridge regression adds around 13% overhead and SVM adds around 30-50% overhead relative to nearest class mean classification.These increases are described as a modest computational cost.
- Efficiency of dual optimization: The ridge-regression QP reaches its optimum in one iteration, while one SVM iteration already outperforms other base learners on 5-shot tasks.With one SVM iteration, episodes take 69 ± 17 ms for 1-shot and 80 ± 17 ms for 5-shot tasks, comparable to ridge regression.
5. Conclusion
The paper presents meta-learning with convex base learners for few-shot learning, using dual formulations and KKT conditions for computationally and memory-efficient optimization.
- Dual formulations and KKT conditions enable computationally and memory-efficient meta-learning with convex base learners.The framework is designed for few-shot learning problems.