# Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples

arXiv: https://arxiv.org/abs/2410.11227 · HTML: https://mlsanity.com/paper/2410.11227/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 62 references that are in the map.
- First posted on arXiv 15 Oct 2024.

## Builds on (most cited first, 30 of 45)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [RT-1: Robotics Transformer for Real-World Control at Scale](https://mlsanity.com/paper/2212.06817/) (2022)
- [Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution](https://mlsanity.com/paper/2202.10054/) (2022)
- [Perceiver-Actor: A Multi-Task Transformer for Robotic Manipulation](https://mlsanity.com/paper/2209.05451/) (2022)
- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Surgical Fine-Tuning Improves Adaptation to Distribution Shifts](https://mlsanity.com/paper/2210.11466/) (2022)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [On the Theory of Transfer Learning: The Importance of Task Diversity](https://mlsanity.com/paper/2006.11650/) (2020)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Understanding and Improving Information Transfer in Multi-Task Learning](https://mlsanity.com/paper/2005.00944/) (2020)
- [Neural-Fly Enables Rapid Learning for Agile Flight in Strong Winds](https://mlsanity.com/paper/2205.06908/) (2022)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Impact of Representation Learning in Linear Bandits](https://mlsanity.com/paper/2010.06531/) (2020)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [How Fine-Tuning Allows for Effective Meta-Learning](https://mlsanity.com/paper/2105.02221/) (2021)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [On the Power of Multitask Representation Learning in Linear MDP](https://mlsanity.com/paper/2106.08053/) (2021)
- [A No-Free-Lunch Theorem for MultiTask Learning](https://mlsanity.com/paper/2006.15785/) (2020)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [Sample Efficient Linear Meta-Learning by Alternating Minimization](https://mlsanity.com/paper/2105.08306/) (2021)

## Built on by (most cited first, 2 of 2)

- [Safety Certification is Classification](https://mlsanity.com/paper/2605.06087/) (2026)
- [Byzantine-Robust Federated Representation Learning](https://mlsanity.com/paper/2609.36660/) (2026)

## Abstract (arXiv)

A driving force behind the diverse applicability of modern machine learning is the ability to extract meaningful features across many sources. However, many practical domains involve data that are non-identically distributed across sources, and statistically dependent within its source, violating vital assumptions in existing theoretical studies. Toward addressing these issues, we establish statistical guarantees for learning general textitnonlinear representations from multiple data sources that admit different input distributions and possibly dependent data. Specifically, we study the sample-complexity of learning T+1 functions f_star(t) circ g_star from a function class mathcal F × mathcal G, where f_star(t) are task specific linear functions and g_star is a shared nonlinear representation. A representation hat g is estimated using N samples from each of T source tasks, and a fine-tuning function hat f(0) is fit using N' samples from a target task passed through hat g. We show that when N gtrsim Cdep (dim(mathcal F) + C(mathcal G)/T), the excess risk of hat f(0) circ hat g on the target task decays as nudiv big(fracdim(mathcal F)N' + fracC(mathcal G)N T big), where Cdep denotes the effect of data dependency, nudiv denotes an (estimatable) measure of textittask-diversity between the source and target tasks, and mathrm C(mathcal G) denotes the complexity of the representation class mathcal G. In particular, our analysis reveals: as the number of tasks T increases, both the sample requirement and risk bound converge to that of r-dimensional regression as if g_star had been given, and the effect of dependency only enters the sample requirement, leaving the risk bound matching the iid setting.