Provable Meta-Learning of Linear Representations

Problem

• The goal is to recover shared features from multiple tasks and use them to improve learning on a new task with scarce data.The model represents each task parameter as β_t+1 = Bα_t+1.Source: §1 · pp. 1–2

Main result

• Theorem 1 shows that positive transfer can dramatically reduce new-task sample complexity when r ≪ d and n1/n2 ≫ r^2.These conditions mean the shared representation is simpler than the ambient space and feature-learning data sufficiently outweighs new-task data.Source: §1 · p. 2
• The analysis identifies structural conditions on covariate distributions and task diversity that let feature learning use all available samples, yielding 1/n1 rather than 1/√t scaling.The improvement is contrasted with prior rates whose leading feature-learning term decays only with the number of tasks.Source: §1 · p. 2, §1.1 · p. 3

Algorithms

• All local minimizers of the regularized empirical risk lie near the true representation up to statistical error, supporting efficient recovery by first-order methods.Gradient descent is given as an example of such a method.Source: §1 · p. 2
• A method-of-moments estimator aggregates information across tasks to estimate B even when individual task parameters are information-theoretically unlearnable.The paper also analyzes transfer through the bias-variance trade-off of regression using an estimated representation.Source: §1 · p. 2

Lower bounds

• The paper provides an information-theoretic lower bound showing its feature estimator is close to optimal up to logarithmic and task-parameter conditioning factors.It describes this as the first information-theoretic lower bound for representation learning in the multi-task setting.Source: §1 · p. 2

Representation and geometry

• The shared representation is an orthonormal matrix B ∈ R^d×r, with B⊥ spanning its orthogonal complement.The paper treats B as representing an r-dimensional subspace, up to right rotation.Source: §2 · p. 3
• Subspace error is measured using the principal-angle distance sin θ(E, F), with B identified with the subspace it spans.Principal angles are obtained from the singular values of E⊤F.Source: §2 · p. 3

Assumptions

• The model uses random-design linear regression with identity covariance, sub-Gaussian covariates and noise, and noise independent of the covariates.Identity covariance simplifies the technical arguments, though the results do not critically rely on it.Source: §2 · p. 4
• The analysis assumes normalized task parameters and positive task diversity, with ∥α_j∥ = Θ(1) and ν > 0.The normalization corresponds to a constant-order signal-to-noise ratio.Source: §2 · p. 4
• Task diversity is required because insufficiently varied task parameters can make recovery of some feature directions information-theoretically impossible.The parameters ν, κ̄, and κ quantify how spread out task parameters are within the feature space.Source: §2 · p. 4

Meta-learning procedure

• Meta-training learns the shared representation from diverse tasks, while meta-testing transfers it to a new task to improve sample complexity.The paper studies both feature recovery and estimation of a new task parameter using the learned representation.Source: §2 · p. 4

Overview

• The paper addresses both algorithmic and statistical challenges of learning the shared linear representation B.It studies local minima of a regularized empirical-risk objective and a sharper method-of-moments estimator.Source: §3 · p. 4, §3.1 · p. 4, §3.2 · p. 5

Optimization-based estimator

• Joint feature and task-parameter learning is recast as rank-r matrix sensing through M⋆ = (α_1, …, α_t)⊤B⊤ and the factorization M = UV⊤.The column space of the optimal factor V⋆ spans the same subspace as B.Source: §3.1 · pp. 4–5
• All local minimizers recover a representation at subspace distance at most ˜O(max{t, d}r/n_1) from the truth.Theorem 2 requires n_1 ≳ polylog(n_1, d, t)(κr)^4 max{t, d} and holds with probability at least 1 − 1/poly(d).Source: §3.1 · p. 5
• When t ≤ O(d), local minimizers are statistically close-to-optimal up to logarithmic and task-diversity conditioning factors.The comparison lower bound is ≳ dr/n_1 for any estimator.Source: §3.1 · p. 5

Method-of-moments estimator

• The method-of-moments estimator computes the top-r eigenvectors of an empirical moment matrix to recover the feature subspace.Its analysis uses concentration of empirical moments and the Davis–Kahan sin θ theorem.Source: §3.2 · pp. 5–6
• Under Gaussian covariates, Algorithm 1 succeeds when n_1 ≳ polylog(d, n_1) rκ̃/ν̃, with guarantees expressed through empirical task-diversity parameters.Under uniform task sampling, these parameters translate to corresponding population task-diversity quantities.Source: §3.2 · p. 6
• The estimator can learn B with Θ(1) samples per task when t = ˜Θ(dr), even though recovering any individual task parameter is information-theoretically impossible.It aggregates information across tasks rather than estimating each task independently.Source: §3.2 · p. 6
• The method-of-moments guarantee relies on the moment structure induced by Gaussian design.The paper describes the estimator as close-to-optimal in the constant-snr regime.Source: §3.2 · p. 6

Transfer estimator

• The transfer estimator uses B̂ as a plug-in surrogate for B to estimate the new task's low-dimensional parameter αt+1.It then recovers the task parameter through the shared representation.Source: §4 · p. 7
• B̂ reduces the covariate dimension, allowing new-task learning in a lower-dimensional space via an ordinary least-squares objective.The least-squares problem can be solved analytically.Source: §4 · p. 7

Theoretical guarantee

• Theorem 4 analyzes new-task recovery when sin θ(B̂, B) ≤ δ and n2 ≳ r log n2 under bounded task-parameter norm.The guarantee applies to data from a single unseen task satisfying the stated assumptions.Source: §4 · p. 7
• The transfer error decomposes into a bias term Õ(δ^2) from imperfect features and a variance term Õ(r/n2) from learning in reduced dimension.The bias reflects feature mismatch, while the variance reflects estimation in an r-dimensional space.Source: §4 · p. 7

Transfer conditions

• Meta-learning can significantly reduce sample complexity when δ^2 ≪ d/n2 and r ≪ d, but feature-learning overhead can overwhelm transfer when δ^2 ≫ d/n2.For diverse tasks, positive transfer requires n1/n2 ≫ r/ν.Source: §4 · p. 7

Lower-bound framework

• The lower-bound analysis targets subspace recovery in the Grassmann manifold, measured by subspace angle distance rather than additive prediction error.This addresses the feature-learning problem's geometric structure directly.Source: §5 · p. 8

Lower bound

• Theorem 5 establishes an information-theoretic lower bound for feature recovery under Gaussian covariates and noise, normalized task parameters, and the stated task-diversity assumptions.The theorem considers n total samples distributed equally across tasks.Source: §5 · p. 8

Interpretation

• Algorithm 1 is close to optimal up to logarithmic and task-diversity conditioning factors, independently of the number of tasks t.The relevant conditioning quantities include κ and ν.Source: §5 · p. 8
• The lower bound's dimensional term matches parameter counting because the Grassmann manifold has dimension r(d − r) ≥ Ω(dr) when d/2 ≥ r.This reflects the number of free parameters needed to specify an r-dimensional feature subspace.Source: §5 · p. 8

Open limitation

• Tight dependence on the task-diversity conditioning factors κ and ν remains an open research question.The paper identifies a gap between the upper and lower subspace-recovery bounds.Source: §5 · p. 8

Experimental setup

• The experiments compare first-order and method-of-moments feature learning, then compare their meta-regression estimates with isolated new-task linear regression.The baseline LR uses only data from the new task.Source: §6 · p. 9

Figure 1

• With d = 100, r = 5, and nt = 5, method-of-moments features improve slowly as tasks increase, while the loss-based approach struggles.This setting challenges feature learning because each task has far fewer samples than the ambient dimension.Source: §6 · p. 9
• When n2 = 2500 > d in that setting, meta-learned regressions perform significantly worse than isolated regression because feature-estimation bias overwhelms transfer benefits.The result illustrates negative transfer in a well-sampled new task.Source: §6 · p. 9

Figure 2

• With d = 100, r = 5, nt = 25, and n2 = 25 < d, both feature-learning approaches recover non-trivial representations and improve new-task meta-regression performance.The benefit appears when new-task data are scarce.Source: §6 · p. 9

Additional results

• The loss-based approach can learn an accurate feature representation with significantly fewer samples than method-of-moments in another experimental regime.This reverses the relative behavior observed in the nt = 5 setting.Source: §6 · p. 10
• With t = 20 and n2 = 50, increasing samples per training task significantly improves the generalization of meta-learned regressions.This agrees with the theoretical dependence on the feature-learning sample count.Source: §6 · p. 10

• The paper shows that a shared linear representation can be efficiently learned and transferred between multiple linear regression tasks.Source: §7 · p. 10
• It provides upper and lower bounds on the sample complexity of learning the representation and performing learning-to-learn.Source: §7 · p. 10

• Sub-gaussian variables and vectors are defined through exponential-moment bounds controlled by their scale parameters.Source: Appendices · p. 14
• Sub-exponential variables are likewise defined through an exponential-moment bound involving parameters ν and α.Source: Appendices · p. 14
• A Chernoff argument gives exponential tail bounds for sub-exponential random variables.Source: Appendices · p. 14
• The proof notation uses c and C for universal constants that may change from line to line.Source: Appendices · p. 14

• The formal theorem considers n1 samples from t training tasks and n2 samples from a new (t + 1)st task.Source: A Proofs for Section 1 · p. 14
• Algorithm 1 learns a feature representation from the training samples, and Algorithm 2 uses it with new-task samples to learn the task coefficients.Source: A Proofs for Section 1 · p. 14
• The new task is assumed to have bounded coefficient norm, with ∥αt+1∥2 ≤ O(1).Source: A Proofs for Section 1 · p. 14
• The theorem requires a sufficiently large training sample size and n2 ≳ r log n2 for the new task.Source: A Proofs for Section 1 · p. 14
• The resulting excess prediction error is evaluated on a new datapoint drawn from the covariate distribution.Source: A Proofs for Section 1 · p. 14
• The theorem uses well-conditioned training tasks and a normalization condition on their diversity parameters.Source: A Proofs for Section 1 · p. 14

• The method-of-moments analysis first establishes concentration of the estimator and then applies top-r PCA to the resulting noisy matrix.Source: B Proofs for Section 3.2 · p. 14
• The proof decomposes estimation error into signal and noise terms and controls their fluctuations using matrix-concentration tools.Source: B Proofs for Section 3.2 · pp. 14–15
• The estimator is designed to extract a subspace ˆB close to the true column space of B.Source: B Proofs for Section 3.2 · p. 14
• The sample-complexity condition depends polylogarithmically on n and d and polynomially on task-related parameters and the representation dimension.Source: B Proofs for Section 3.2 · pp. 14–15, C Proofs for Section 3.1 · p. 19
• Davis–Kahan converts spectral perturbation bounds into a bound on the angle between the estimated and true subspaces.Source: B Proofs for Section 3.2 · pp. 14–15
• With high probability, the concentration lemmas provide error bounds whose failure probabilities scale as O(n^-100) or O((nd)^-100).Source: B Proofs for Section 3.2 · p. 15
• The analysis uses Gaussian isotropy and moment calculations to characterize the estimator's expectation and signal structure.Source: B Proofs for Section 3.2 · pp. 15–17

• The analysis exploits rotation alignment between W and W⋆ and compares factorized matrices through perturbation and Hessian bounds.Source: §C.1.2 · p. 20, §C.2 · p. 23
• Sufficient samples ensure every stationary point inside the incoherence region that is not near the optimum has a negative-curvature direction.This structural result is used to characterize the objective landscape away from the optimal representation.Source: §C.1.2 · p. 20
• Under Assumption 1 and n ≥ Cpolylog(n, d, t)µ^2r^4 max{t, d}(κ⋆)^4, every local minimum in the incoherence region satisfies the theorem’s stated conditions with probability at least 1 − 1/poly(d).Source: §C.1.2 · p. 21
• The proof combines an RIP condition over a tangent matrix space with concentration bounds tailored to rank-r structure and different distance-to-optimality regimes.Source: §C.3 · p. 23

• The new-task estimator projects linear regression onto the estimated feature space using ˆα = (ˆB⊤X⊤XˆB)^−1ˆB⊤X⊤y.Source: D Proofs for Section 4 · p. 28
• The analysis requires concentration of low-dimensional empirical covariances and correlations in ˜O(r) samples.Source: D Proofs for Section 4 · p. 28
• Assumption 3 requires bounded covariance conditioning, sub-gaussian covariates, and independent i.i.d. sub-gaussian additive noise.Source: D Proofs for Section 4 · p. 28
• The estimation error ∥ˆBˆα − Bα0∥^2 is decomposed into a bias term from representation mismatch and a variance term from additive noise.Source: D Proofs for Section 4 · pp. 28–29
• The bias and variance bounds hold with probability at least 1 − O(n^−100) under their respective sample-size conditions.Source: D Proofs for Section 4 · p. 29

• The lower-bound proof uses a non-standard Fano method with χ^2-divergence, together with packing and distributional covering bounds.Source: E Proofs for Section 5 · p. 30
• Grassmannian covering numbers scale with the subspace dimension r(d − r), supplying the complexity term in the minimax lower bound.Source: E Proofs for Section 5 · p. 31
• The combined argument applies independent lower bounds to feature-space and task-diversity terms and joins them with a union bound.Source: E Proofs for Section 5 · p. 31
• Feature matrices are treated as equivalent under orthogonal rotation, so recovery is measured between r-dimensional subspaces on the Grassmann manifold.Source: E Proofs for Section 5 · pp. 32–33
• A separate LeCam two-point construction captures dependence on task diversity by using two feature subspaces that are difficult to distinguish for an ill-conditioned task matrix.Source: E Proofs for Section 5 · pp. 31, 33

• A matrix perturbation lemma controls the inverse of A + E by expanding it around A^−1 when ∥EA^−1∥ is sufficiently small.Source: F Auxiliary Results · p. 34
• For scaled random matrices, concentration holds with probability at least 1 − 2 exp(−t^2), with bounds depending on K = max_i |a_i|.Source: F Auxiliary Results · p. 34
• L-L4-L2 hypercontractivity yields bounds on projected moments, including E[∥x∥^4] ≤ L(trΣ)^2 and ∥E[∥P_Vx∥^4]∥ ≤ L∥Σ∥^2r^2.Source: F Auxiliary Results · p. 35
• A sub-gaussian norm bound gives high-probability control of random-vector norms through a logarithmic dependence on 1/δ.Source: F Auxiliary Results · p. 35
• In experiments, L-BFGS optimized the nonconvex loss faster and with less tuning than gradient descent, and the learned representation was extracted from V’s column space.Source: G Experimental Details · p. 36