Research map / Learning theory and algorithms / Kernels and regression theory
Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes De-bias & Feature-Whiten (DFW), an alternating minimization-descent method for linear representation learning from non-iid, non-isotropic vector measurements, with linear convergence and near-oracle-ERM sample complexity.
Problem
Linear representation learning (recovering a shared representation across tasks) from noisy vector measurements with non-iid and non-isotropic covariates; existing alternating methods suffer biases that stop noise from scaling with total data size.
Approach
Adapts alternating minimization-descent by de-biasing (computing least-squares task weights and representation gradients on disjoint trajectory subsets) and feature-whitening (preconditioning each task's gradient by its inverse sample covariance), yielding a contraction with noise scaling with total data NT.
Key results
- Vanilla alternating minimization-descent fails catastrophically even with iid but mildly non-isotropic data, plateauing at a highly suboptimal bias while DFW converges to near-optimality.
- Main theorem: one DFW iteration gives dist(Phi_+, Phi*) <= (1 - 0.897 eta lambda_min^F) dist(Phi, Phi*) + C sigma_avg sqrt((d_x + log(T/delta))/(T N_2) log(d_x/delta)), so noise scales with total data T N_2.
- Neural-net representation with AMD takes almost two orders of magnitude more iterations than DFW to reach optimality in the linear regression experiment.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DFW instead of vanilla alternating minimization-descent (FedRep) | Linear representation learning · IID non-isotropic linear regression | subspace distance | Helped |
| Use vanilla alternating minimization-descent instead of DFW | Linear representation learning · IID non-isotropic linear regression | subspace distance | Hurt |
| Use multi-task DFW (T=25) instead of single-task DFW (T=1) | DFW · IID non-isotropic linear regression | subspace distance | Helped |
| Use DFW instead of AMD with a neural network representation | Linear regression with neural network representation · Linear regression with neural network representation | validation least-squares loss: almost two orders of magnitude more iterations | Helped |
| Use DFW instead of FedRep | Linear system identification · Linear system identification | subspace distance | Helped |
| Add de-biasing by estimating task weights and representation gradients on independent data batches (ablation) | Alternating minimization-descent · Non-isotropic linear representation learning | representation-update noise | Helped |
| Add feature-whitening by preconditioning the gradient with the inverse sample covariance (ablation) | Alternating minimization-descent · Non-isotropic linear representation learning | representation-update bias | Helped |
| Remove de-biasing and feature-whitening (ablation) | DFW · IID mildly non-isotropic linear regression | subspace distance | Hurt |
Surprising findings
- Vanilla alternating minimization-descent fails catastrophically even for iid but mildly non-isotropic data.
- The number of samples used to compute least-squares weights (N_1) need not grow across rounds; only N_2 needs to grow for monotone subspace-distance decrease.
Limitations
- Requires an initialization close to the optimal representation; initialization scheme not addressed.
- Burn-in on N_2 scales linearly with d_x, so the analysis does not cover the low per-task data regime N < d_x for non-isotropic covariates.
- Analysis restricted to linear representations and subgaussian, geometrically beta-mixing covariates.
Experimental setup
Datasets: synthetic linear regression data synthetic linear system identification data
Benchmarks: synthetic linear regression (d_x=d_y=50, r=7) synthetic linear system identification (d_x=25, r=6)
Metrics: subspace distance suboptimality of representation least-squares validation loss
Baselines: FedRep vanilla alternating minimization-descent (AMD) AltGD-Min
Builds on: FedRep AltGD-Min ERM-based multi-task linear representation analysis
Closest papers by meaning
- Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples (ICML 2024 · similarity 0.88)
- Statistically and Computationally Efficient Linear Meta-representation Learning (NeurIPS 2021 · similarity 0.88)
- Few-Shot Learning via Learning the Representation, Provably (ICLR 2021 · similarity 0.88)
- Optimal Representation Size: High-Dimensional Analysis of Pretraining and Linear Probing (NeurIPS 2026 · similarity 0.86)
- A Unified Framework for Learning with Nonlinear Model Classes from Arbitrary Linear Samples (ICML 2024 · similarity 0.85)
- Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.