summaries: This paper explores how different strategies for fine-tuning affect in- and out-of-distribution performance. The authors contrast linear probing (updating only the parameters of the final linear layer), end-to-end fine-tuning (updating all parameters of the model) and a two-stage approach, where linear probing is followed by end-to-end fine-tuning. While end-to-end fine-tuning typically improves in-distribution performance, the authors show that it can also underperform linear probing out-of-distribution. The paper theoretically analyzes the tradeoffs in a simplified scenario with two-layer networks, finding that end-to-end fine-tuning can "distort" pre-trained features. Their experiments on a number of datasets including CIFAR, WILDS-FMoW and others, confirm the intuitions from their theory. The proposed mitigation strategy, a two-stage fine-tuning approach where end-to-end fine-tuning follows linear probing is found to be beneficial, especially out-of-distribution.   **Update:** The authors addressed most of the concerns raised by this and other reviews, and I am raising my score accordingly.

summaries: This paper studies the problem of how to fine-tune a pre-trained model and obtain better results for both ID and OOD. Two methods, fine-tuning and linear probing, are investigated and compared, then a new two-step variant called LP-FT is derived. Results further verify that LP-FT obtains the best performance for ID and OOD tests compared with FT and LP.

summaries: This paper contrasts fine-tuning (i.e., modifying all network weights) and linear probing based on their relative ID/OOD performance. It is known that fine-tuning (FT) outperforms linear probing (LP) ID. This paper presents that the reverse is true OOD (FT outperforms LP). This paper suggests that this occurs because fine-tuning distorts features in conjunction with the final linear layer. Instead, if a final linear layer is trained first, the features do not have to move that much during full fine-tuning. The authors refer to this method as LP-FT and show it often outperforms LP and FT both OOD and ID.

summaries: This paper discovers an interesting behavior of model fine-tuning: the performance is worse compared to linear probing on OOD data (i.e., data from other domains), especially when the distribution shift between inner distribution and out of distribution are big. The explanation provided in the paper is that fine-tuning distorts the feature representations, overfits on inner distributions, and thus has a higher error on OOD data. The authors also provide a simple solution to this issue by fine-tuning with a classification head initialized from linear probing and had better results in all the benchmarks they have in the paper.

abstractText: When transferring a pretrained model to a downstream task, two popular methods are fine-tuning (updating all the model parameters) and linear probing (updating only the last linear layer). It is well known that fine-tuning leads to better accuracy in-distribution (ID). However, in this paper, we show that fine-tuning can achieve worse accuracy than linear probing out-of-distribution (OOD), especially when the pretrained features are good and distribution shift is large. On six distribution shift datasets (Breeds-Living17, Breeds-Entity30, DomainNet, CIFAR → STL, CIFAR10.1, FMoW), fine-tuning obtains an average 2% higher accuracy ID but 6% lower accuracy OOD than linear probing. We theoretically analyze the tradeoffs arising in fine-tuning overparameterized two-layer linear networks, characterizing how fine-tuning can distort high-quality pretrained features which leads to low OOD accuracy. Our analysis suggests that the simple two-step strategy of linear probing then full fine-tuning combines the benefits of both fine-tuning and linear probing to achieve better ID and OOD accuracy than fine-tuning, both theoretically and on the above datasets (1% better ID, 8% better OOD).

authors:
Pierre Antoine Absil
Alan Edelman
Plamen Koev

title: On the largest principal angle between random subspaces

venue: Linear Algebra and its Applications,

authors:
Armen Aghajanyan
Akshat Shrivastava
Anchit Gupta
Naman Goyal
Luke Zettlemoyer
Sonal Gupta

title: Better fine-tuning by reducing representational collapse

venue: In International Conference on Learning Representations (ICLR),

authors:
EA AlBadawy
A Saha
MA Mazurowski

title: Deep learning for segmentation of brain tumors: Impact of cross-institutional training and testing

venue: Med Phys.,

authors:
Anders Andreassen
Yasaman Bahri
Behnam Neyshabur
Rebecca Roelofs

title: The evolution of out-of-distribution robustness throughout fine-tuning

authors:
Sanjeev Arora
Nadav Cohen
Elad Hazan

title: On the optimization of deep networks: Implicit acceleration by overparameterization

venue: In International Conference on Machine Learning (ICML),

authors:
Kumar Ayush
Burak Uzkent
Chenlin Meng
Kumar Tanmay
M. Burke
D. Lobell
Stefano Ermon

title: Geography-aware self-supervised learning

authors:
Peter L. Bartlett
Philip M. Long
G ́abor Lugosi
Alexander Tsigler

title: Benign overfitting in linear regression

authors:
Yonatan Belinkov
Nadir Durrani
Fahim Dalvi
Hassan Sajjad
James Glass

title: What do neural machine translation models learn about morphology

venue: In Association for Computational Linguistics (ACL),

authors:
Mikhail Belkin
Daniel Hsu
Ji Xu

title: Two models of double descent for weak features

authors:
Koby Bibas
Yaniv Fogel
Meir Feder

title: A new look at an old problem: A universal learning approach to linear regression

venue: IEEE International Symposium on Information Theory (ISIT),

authors:
Tianle Cai
Ruiqi Gao
J. Lee
Qi Lei

title: A theory of label propagation for subpopulation shift

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

authors:
Xinlei Chen
Haoqi Fan
Ross B. Girshick
Kaiming He

title: Improved baselines with momentum contrastive learning. arXiv, 2020b

authors:
Xinlei Chen
Saining Xie
Kaiming He

title: An empirical study of training self-supervised vision transformers

venue: arXiv preprint arXiv:2104.02057,

authors:
Yining Chen
Elan Rosenfeld
Mark Sellke
Tengyu Ma
Andrej Risteski

title: Iterative feature matching: Toward provable domain generalization with logarithmic environments. arXiv, 2021b

authors:
Gordon Christie
Neil Fendley
James Wilson
Ryan Mukherjee

title: Functional map of the world

venue: In Computer Vision and Pattern Recognition

authors:
Kurtland Chua
Qi Lei
Jason D Lee

title: How fine-tuning allows for effective meta-learning

venue: arXiv preprint arXiv:2105.02221,

authors:
Adam Coates
Andrew Ng
Honlak Lee

title: An analysis of single-layer networks in unsupervised feature learning

venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,

authors:
Simon S. Du
Wei Hu
Sham M. Kakade
Jason D. Lee
Qi Lei

title: Few-shot learning via learning the representation, provably

authors:
Simon Shaolei Du
Wei Hu
Jason Lee

title: Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced

venue: In Advances in Neural Information Processing Systems (NeurIPS),

authors:
Geoff French
Michal Mackiewicz
Mark Fisher

title: Self-ensembling for visual domain adaptation

venue: In International Conference on Learning Representations,

authors:
Weifeng Ge
Yizhou Yu

title: Borrowing treasures from the wealthy: Deep transfer learning through selective joint fine-tuning

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
Suriya Gunasekar
Blake E Woodworth
Srinadh Bhojanapalli
Behnam Neyshabur
Nati Srebro

title: Implicit regularization in matrix factorization

authors:
Yunhui Guo
Honghui Shi
Abhishek Kumar
Kristen Grauman
Tajana Rosing
Rogerio Feris

title: Spottune: Transfer learning through adaptive fine-tuning

authors:
Trevor Hastie
Andrea Montanari
Saharon Rosset
Ryan J Tibshirani

title: Surprises in highdimensional ridgeless least squares interpolation

venue: arXiv preprint arXiv:1903.08560,

authors:
Kaiming He
Haoqi Fan
Yuxin Wu
Saining Xie
Ross Girshick

title: Momentum contrast for unsupervised visual representation learning

venue: In Computer Vision and Pattern Recognition (CVPR),

authors:
Dan Hendrycks
Kimin Lee
Mantas Mazeika

title: Using pre-training can improve model robustness and uncertainty

authors:
Dan Hendrycks
Kevin Zhao
Steven Basart
Jacob Steinhardt
Dawn Song

title: Natural adversarial examples

venue: arXiv preprint arXiv:1907.07174,

authors:
Dan Hendrycks
Steven Basart
Norman Mu
Saurav Kadavath
Frank Wang
Evan Dorundo
Rahul Desai
Tyler Zhu
Samyak Parajuli
Mike Guo
Dawn Song
Jacob Steinhardt
Justin Gilmer

title: The many faces of robustness: A critical analysis of out-of-distribution generalization

venue: arXiv preprint arXiv:2006.16241,

authors:
John Hewitt
Christopher D. Manning

title: A structural probe for finding syntax in word representations

authors:
Neil Houlsby
Andrei Giurgiu
Stanislaw Jastrzebski
Bruna Morrone
Quentin de Laroussilhe
Andrea Gesmundo
Mona Attariyan
Sylvain Gelly

title: Parameter-efficient transfer learning for NLP

authors:
Neal Jean
Marshall Burke
Michael Xie
W. Matthew Davis
David B. Lobell
Stefano Ermon

title: Combining satellite imagery and machine learning to predict poverty

authors:
Haoming Jiang
Pengcheng He
Weizhu Chen
Xiaodong Liu
Jianfeng Gao
Tuo Zhao

title: Smart: Robust and efficient fine-tuning for pre-trained natural language models through principled regularized optimization

authors:
Pritish Kamath
Akilesh Tangella
Danica J. Sutherland
Nathan Srebro

title: Does invariant risk minimization capture invariance

venue: In Artificial Intelligence and Statistics (AISTATS),

authors:
Fahdi Kanavati
Masayuki Tsuneki

title: Partial transfusion: on the expressive influence of trainable batch norm parameters for transfer learning

venue: In Medical Imaging with Deep Learning,

authors:
Fereshte Khani
Percy Liang

title: Removing spurious features can hurt accuracy and affect groups disproportionately

venue: In ACM Conference on Fairness, Accountability, and Transparency (FAccT),

authors:
Simon Kornblith
Jonathon Shlens
Quoc V. Le

title: Do better imagenet models transfer better

title: Learning multiple layers of features from tiny images

venue: Technical report, University of Toronto,

authors:
Thomas Laurent
James H. von Brecht

title: Deep linear neural networks with arbitrary loss: All local minima are global

authors:
Brian Lester
Rami Al-Rfou
Noah Constant

title: The power of scale for parameter-efficient prompt tuning

venue: arXiv preprint arXiv:2104.08691,

authors:
Xiang Lisa Li
Percy Liang

title: Prefix-tuning: Optimizing continuous prompts for generation

authors:
Xuhong Li
Yves Grandvalet
Franck Davoine

title: Explicit inductive bias for transfer learning with convolutional networks

authors:
Song Mei
Andrea Montanari

title: The generalization error of random features regression: Precise asymptotics and double descent curve

authors:
John Miller
Rohan Taori
Aditi Raghunathan
Shiori Sagawa
Pang Wei Koh
Vaishaal Shankar
Percy Liang
Yair Carmon
Ludwig Schmidt

title: Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization

authors:
Vidya Muthukumar
Kailas Vodrahalli
Vignesh Subramanian
Anant Sahai

title: Harmless interpolation of noisy data in regression

venue: IEEE Journal on Selected Areas in Information Theory,

authors:
Behnam Neyshabur
Ryota Tomioka
Nathan Srebro

title: In search of the real inductive bias: On the role of implicit regularization in deep learning

authors:
Xingchao Peng
Qinxun Bai
Xide Xia
Zijun Huang
Kate Saenko
Bo Wang

title: Moment matching for multi-source domain adaptation

venue: In International Conference on Computer Vision (ICCV),

authors:
Matthew E. Peters
Mark Neumann
Mohit Iyyer
Matt Gardner
Christopher Clark
Kenton Lee
Luke Zettlemoyer

title: Deep contextualized word representations

venue: In North American Association for Computational Linguistics (NAACL),

authors:
Matthew E Peters
Sebastian Ruder
Noah A Smith

title: To tune or not to tune? adapting pretrained representations to diverse tasks

venue: In Proceedings of the 4th Workshop on Representation Learning for NLP (RepL4NLP-2019),

authors:
Viraj Prabhu
Shivam Khare
Deeksha Karthik
Judy Hoffman

title: Selective entropy optimization via committee consistency for unsupervised domain adaptation

authors:
Alec Radford
Jong Wook Kim
Chris Hallacy
Aditya Ramesh
Gabriel Goh
Sandhini Agarwal
Girish Sastry
Amanda Askell
Pamela Mishkin
Jack Clark
Gretchen Krueger
Ilya Sutskever

title: Learning transferable visual models from natural language supervision

authors:
Aditi Raghunathan
Sang Michael Xie
Fanny Yang
John C. Duchi
Percy Liang

title: Understanding and mitigating the tradeoff between robustness and accuracy

authors:
Benjamin Recht
Rebecca Roelofs
Ludwig Schmidt
Vaishaal Shankar

title: Do CIFAR-10 classifiers generalize to CIFAR-10? arXiv, 2018

title: Do imagenet classifiers generalize to imagenet

authors:
Elan Rosenfeld
Pradeep Ravikumar
Andrej Risteski

title: The risks of invariant risk minimization

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: ImageNet large scale visual recognition challenge

venue: International Journal of Computer Vision,

authors:
Shibani Santurkar
Dimitris Tsipras
Aleksander Madry

title: Breeds: Benchmarks for subpopulation

venue: shift. arXiv,

authors:
Andrew M. Saxe
James L. McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

authors:
Shuhan Tan
Xingchao Peng
Kate Saenko

title: Class-imbalanced domain adaptation: An empirical odyssey

venue: arXiv preprint arXiv:1910.10320,

authors:
Rohan Taori
Achal Dave
Vaishaal Shankar
Nicholas Carlini
Benjamin Recht
Ludwig Schmidt

title: Measuring robustness to natural distribution shifts in image classification

venue: arXiv preprint arXiv:2007.00644,

authors:
Nilesh Tripuraneni
Michael I. Jordan
Chi Jin

title: On the theory of transfer learning: The importance of task

venue: diversity. arXiv,

title: An introduction to matrix concentration inequalities

venue: Foundations and Trends in Machine Learning,

authors:
Prasetya Ajie Utama
Nafise Sadat Moosavi
Victor Sanh
Iryna Gurevych

title: Avoiding inference heuristics in few-shot prompt-based finetuning

venue: arXiv preprint arXiv:2109.04144,

authors:
Haohan Wang
Songwei Ge
Zachary Lipton
Eric P Xing

title: Learning robust global representations by penalizing local predictive power

authors:
Mitchell Wortsman
Gabriel Ilharco
Mike Li
Jong Wook Kim
Hannaneh Hajishirzi
Ali Farhadi
Hongseok Namkoong
Ludwig Schmidt

title: Robust fine-tuning of zero-shot models

venue: arXiv preprint arXiv:2109.01903,

authors:
Sen Wu
Hongyang R. Zhang
Christopher Ré

title: Understanding and improving information transfer in multi-task learning

authors:
Sang Michael Xie
Ananya Kumar
Robert Jones
Fereshte Khani
Tengyu Ma
Percy Liang

title: In-N-out: Pre-training and self-training using auxiliary information for out-of-distribution robustness

authors:
Sang Michael Xie
Tengyu Ma
Percy Liang

title: Composed fine-tuning: Freezing pre-trained denoising autoencoders for improved generalization

authors:
Fisher Yu
Haofeng Chen
Xin Wang
Wenqi Xian
Yingying Chen
Fangchen Liu
Vashisht Madhavan
Trevor Darrell

title: Bdd100k: A diverse driving dataset for heterogeneous multitask learning

authors:
Xiaohua Zhai
Joan Puigcerver
Alexander Kolesnikov
Pierre Ruyssen
Carlos Riquelme
Mario Lucic
Josip Djolonga
Andre Susano Pinto
Maxim Neumann
Alexey Dosovitskiy
Lucas Beyer
Olivier Bachem
Michael Tschannen
Marcin Michalski
Olivier Bousquet
Sylvain Gelly
Neil Houlsby

title: A large-scale study of representation learning with the visual task adaptation

venue: benchmark. arXiv,

authors:
Jeffrey O Zhang
Alexander Sax
Amir Zamir
Leonidas Guibas
Jitendra Malik

title: Side-tuning: A baseline for network adaptation via additive side networks

venue: In European Conference on Computer Vision (ECCV),

authors:
Kaiyang Zhou
Jingkang Yang
Chen Change Loy
Ziwei Liu

title: Learning to prompt for visionlanguage models

venue: arXiv preprint arXiv:2109.01134,

authors:
Chen Zhu
Yu Cheng
Zhe Gan
Siqi Sun
Tom Goldstein
Jingjing Liu

title: FreeLB: Enhanced adversarial training for natural language understanding

venue: DomainNet: We use the dataset splits in Peng et al

venue: Bibas et al

heading: 1 INTRODUCTION

text:
Pretraining a model on a large dataset before transferring to a downstream task’s training data substantially improves accuracy over training from scratch—for example, pretraining a ResNet-50 on unlabeled ImageNet boosts accuracy on CIFAR-10 from 94% to 98% (Chen et al., 2020a;b). Highstakes applications such as poverty mapping in under-resourced countries (Jean et al., 2016), selfdriving cars (Yu et al., 2020), and medical diagnosis (AlBadawy et al., 2018), require models that also generalize to circumstances not seen in the training distribution. In addition to testing on data drawn from the downstream task’s training distribution (in-distribution; ID) it is increasingly important to test on data distributions unseen during training (out-of-distribution; OOD).
After initializing with a pretrained model, two popular transfer methods are fine-tuning (running gradient descent on all the model parameters), and linear probing (tuning the head but freezing lower layers). In the ID setting it is well known that fine-tuning leads to better accuracy than linear probing (Kornblith et al., 2019; Zhai et al., 2020; He et al., 2020), and even when testing OOD prior work usually fine-tunes all parameters of their model (Hendrycks et al., 2019a; Miller et al., 2021; Andreassen et al., 2021). Intuitively, fine-tuning all layers of a network can improve pretrained features by tailoring them to the specific task, while linear probing freezes these features.
In this work, we investigate the OOD performance of fine-tuning and linear probing and find that surprisingly, fine-tuning often does worse than linear probing in the presence of large distribution shift. We experiment on six distribution shift benchmarks (Breeds Living17, Breeds Entity30, DomainNet, CIFAR → STL, CIFAR10.1, FMoW geo-shift), initializing with good pretrained features from MoCo-v2 (Chen et al., 2020b) and CLIP (Radford et al., 2021). While both methods offer gains over training from scratch, fine-tuning improves the average ID accuracy from 84% to 86% but brings down the OOD accuracy from 72% to 67% (Figure 1).
When and why does fine-tuning underperform linear probing? We theoretically consider fine-tuning a two-layer linear network in an overparameterized regression setting where the feature extractor layer has been pretrained to map high-dimensional inputs to useful, lower-dimensional, features. We prove that fine-tuning is worse than linear probing on worst-case OOD inputs when using high quality pretrained features. Even with an infinitesimally small learning rate, fine-tuning distorts pretrained features—the features of ID data are updated while those of OOD data remain unchanged.
Since the head and feature extractor are simultaneously optimized during fine-tuning to a configuration that works well on ID training data, the head only accomodates the distorted features of ID points and performs poorly on the unchanged features of OOD points. Interestingly, we show that this feature distortion issue cannot be simply fixed by early stopping—throughout the process of fine-tuning, we never pass through parameters that do well OOD. On the other hand, we show that linear-probing extrapolates better OOD because it preserves pretrained features, but does not do as well as fine-tuning ID because linear probing cannot adapt the features to the downstream task.
Technical challenges. Existing theoretical work on transfer learning focuses on linear probing (Wu et al., 2020; Tripuraneni et al., 2020; Du et al., 2020). In contrast, the analysis of fine-tuning is scarce and challenging because it requires understanding the training dynamics, instead of only the loss function and its global minimizers. In fact, fine-tuning and training from scratch optimize the same training loss and only differ in their initializations (pretrained vs random). A mathematical analysis that distinguishes them needs to capture properties of the different global minima that these algorithms converge to, a phenomenon that is sometimes theoretically referred to as the implicit regularization effect of initialization (Neyshabur et al., 2014). Accordingly, our analysis reasons about the parameters that gradient methods pass through starting from the pretrained initialization, which is challenging because there is no known closed form for this trajectory. Two-layer linear networks are widely studied in the implicit regularization community (Saxe et al., 2014; Arora et al., 2018), however they analyze random and often small initializations which don’t capture pretraining.
Algorithmic implications. Our theory says that fine-tuning fails because when trying to fit ID training data with a randomly initialized head, the feature extractor changes significantly for ID examples, making features for ID and OOD examples largely inconsistent. This can be fixed by initializing with a good head that does not need to be updated much during fine-tuning, reducing how much the feature extractor changes. This suggests the simple two-step strategy of first linearprobing to find a good head and then full fine-tuning (LP-FT). Empirically, LP-FT outperforms fine-tuning and linear-probing, both ID and OOD. Even on CIFAR-10.1 (small distribution shift), where fine-tuning is better for both ID and OOD, we find LP-FT outperforms fine-tuning on both metrics. LP-FT and vanilla fine-tuning use similar amounts of compute because the first step of linear probing is relatively very cheap. We note that while LP-FT has sometimes been used as a finetuning heuristic (Kanavati & Tsuneki, 2021), it has not been used for robustness / OOD accuracy, and we show that it addresses the ID-OOD tradeoff theoretically and empirically.
Practical insights. Finally, we check whether fine-tuning fails and LP-FT works, for the reasons predicted by our feature distortion theory. As predicted by the theory, we find that: (1) fine-tuning indeed never matches the OOD accuracy of linear probing throughout the course of training, (2) finetuning changes the features for ID examples more than for OOD examples leading to distortions (3)
fine-tuning can do better than linear probing OOD if the pretrained features are not very high quality (MoCo-v1 instead of MoCo-v2) or the ID and OOD datasets are very close (e.g., CIFAR-10 and CIFAR-10.1) and (4) LP-FT indeed changes both ID and OOD features orders of magnitude less than fine-tuning does.

heading: 2 SETUP

text:
Task and evaluation. Given training samples {(x1, y1), . . . (xn, yn)} sampled from some distribution Pid, our goal is to learn a predictor f : Rd → Y to map inputs x ∈ Rd to outputs y ∈ Y . We evaluate predictors on their standard “in-distribution” (ID) performance Lid on new test samples drawn from Pid that the training data is also sampled from. We also evaluate classifiers on their “out-of-distribution” (OOD) performance Lood on test samples drawn from a new distribution Pood that is different from Pid. Formally, for some loss function ℓ, we evaluate classifiers on:
Lid(f) = E (x,y)∼Pid [ℓ(f(x), y)] and Lood(f) = E (x,y)∼Pood [ℓ(f(x), y)]. (2.1)
Models. In this work, we focus on predictors that leverage pretrained feature extractors . For convenience of such analyses, we parameterize the final predictor in terms of a linear “head” v ∈ V on top of some features gB(x) ∈ Rk for some “base” parameters B ∈ B. Formally, f is parameterized by base parameter B and head parameters v such that fv,B(x) = v⊤gB(x). In our experiments (Section 4), gB is a deep network and in our theory (Section 3), gB is a linear projection.
We assume access to some initial pretrained feature extractor B0 that is obtained by training on potentially large amounts of data from a distribution that could be different from Pid and Pood. We focus on two popular methods to learn a predictor fv,B given training data from Pid: (i) linear probing where B = B0 and the linear head is obtained by minimizing some loss (e.g., logistic loss for classification, squared loss for regression) on the training data, and (ii) fine-tuning where both v and B are updated by performing gradient descent on some loss on the training data with B initialized at B0.

heading: 3 THEORY: FINE-TUNING DISTORTS PRETRAINED FEATURES

text:
We theoretically study the performance of different training methods that use a good pretrained feature extractor. In a linear setting, we characterize when and why fine-tuning, in which all model parameters are updated, can increase OOD loss due to feature distortion. We define the problem setting in Section 3.1, and present the main result and proof sketch in Section 3.2.
Our analysis handles two key challenges which distinguish it from prior work on transfer learning in linear models (Wu et al., 2020; Tripuraneni et al., 2020; Du et al., 2020; Xie et al., 2021a). Prior work focuses on linear probing, while we study fine-tuning where the resulting optimization problem is non-convex and we need to analyze the effect of initialization from a particular pretrained parameter setting. We also study overparameterized models where the number of training examples is less than the input dimension, reflecting the practical setting where neural networks achieve zero training loss. Here, training loss alone does not determine test performance—this fact makes the setting very relevant because both training from scratch and fine-tuning have same training loss but very different test performance, but also makes the analysis challenging.

heading: 3.1 LINEAR OVERPARAMETERIZED SETTING

text:
Models. Recall from Section 2 that we parameterize predictors in terms of base and head parameters. In this section, we study models where the feature extractor is linear, i.e. fv,B(x) = v⊤Bx where B ∈ B = Rk×d, and v ∈ V = Rk.
For simplicity, we assume the models are well-specified i.e. y = v⊤⋆ B⋆x where v⋆ ∈ Rk and B⋆ ∈ Rk×d. 1 Note that B⋆ and v⋆ are only unique up to rotations, i.e., for any rotation matrix U , (Uv⋆) T (UB⋆)x = v T ⋆ B⋆x.
1We note that our main contribution—analysis of fine-tuning (Theorem 3.1) does not require this wellspecified assumption. We compare fine-tuning with linear probing by adapting earlier work on linear probing which requires the well-specified assumption.
Suppose we have a pretrained feature extractor B0 close to B⋆, so minU∥B0 − UB⋆∥2≤ ϵ over rotation matrices U ∈ Rk×k—this follows from prior work in pretraining (Tripuraneni et al., 2020). As in prior work suppose B⋆, B0 have been orthogonalized to have orthonormal rows.
Data distribution and evaluation. For our analysis, we focus on regression , where Y = R and ℓ is the squared loss. Let X ∈ Rn×d, X ̸= 0 be a matrix encoding n training points from Pid where each of the n rows is a training input. Let Y ∈ Rn be the corresponding outputs. We consider an overparameterized setting where 1 ≤ k < n < d and k < d− n. Intuitively, the input dimension d is high (e.g., 10K), feature dimension k is lower (e.g., 100) and n is in the middle (e.g., 5K).
In this work, we are primarily interested in the out-of-distribution (OOD) performance. Since the OOD data can be arbitrary we follow prior work (Rosenfeld et al., 2021; Kamath et al., 2021; Chen et al., 2021b) and consider the worst case loss over distributions (equivalently, individual points) of bounded norm:
Lood(v,B) = max ∥x∥2≤1
(v⊤⋆ B⋆x− v⊤Bx)2 = ∥B⊤⋆ v⋆ −B⊤v∥22 (3.1)
Training methods. Given training data and a pretrained base parameter B0, we study the two popular methods of linear probing (LP) and fine-tuning (FT) to learn the final predictor (See Section 2). Both methods involve optimizing the training loss via gradient descent (or variants). In order to effectively analyze these gradient based algorithms, we study vanishing step sizes leading to gradient flows. Gradient flows can be thought of as a continuous time analog of gradient based methods and have been extensively studied in recent years as a way to understand gradient based methods (Gunasekar et al., 2017; Arora et al., 2018; Du et al., 2018). Formally, for training loss L̂(v,B) = ∥XB⊤v − Y ∥22, the gradient flow differential equations for LP and FT are as follows.
∂tvft(t) = −∇vL̂(vlp(t), Bft(t)), ∂tBft(t) = −∇BL̂(vft(t), Bft(t)) (3.2) ∂tvlp(t) = −∇vL̂(vlp(t), B0), ∂tBlp(t) = 0, (3.3)
initialized with Bft(0) = Blp(0) = B0 and vft(0) = vlp(0) = v0. In practice, the head parameter v0 is initialized randomly—our results hold for any standard random initialization Glorot & Bengio (2010), for example v0 ∼ N (0, σ2I) for any σ2. Recall that the initial value of the base parameter B0 is assumed to be available and obtained via pretraining.
The final LP and FT solutions are the limit points of the corresponding gradient flows:
v∞ft = lim t→∞ vft(t) and B∞ft = lim t→∞ Bft(t) (3.4) v∞lp = lim t→∞ vlp(t) and B∞lp = lim t→∞ Blp(t) = B0 (3.5)

heading: 3.2 FINE-TUNING DISTORTS PRETRAINED FEATURES

text: The more common method of using a pretrained feature extractor is fine-tuning (FT) which typically improves ID performance relative to linear probing (LP). In this section, we show theoretically that FT distorts features leading to poor OOD performance. We first present the key intuitions demonstrating potential issues of FT and then present our formal theorem lower bounding the OOD error of FT .

heading: 3.2.1 KEY INTUITIONS

text: There are two main pieces that we use to characterize when and why FT has higher OOD error.

heading: 1. Features get distorted because representations change only in the ID subspace (i.e., subspace

text:
along the training data) and are unchanged in the orthogonal subspace. Taking the derivative of the training loss L̂(v,B) = ∥XB⊤v − Y ∥22 with respect to the base feature parameter B, we get:
∇BL̂(v,B) = 2v(Y −XBv)⊤X (3.6)
By definition, if u is a direction orthogonal to the training subspace, ∇BL̂(v,B)u = 0, that is the gradient updates to B do not modify Bu for u ∈ S⊥. However, the gradient is non-zero for directions u in the ID subspace and the corresponding features Bu change across the FT process. This leads to feature distortion where the features in some subspaces are updated but not others,
leading to inconsistencies relative to the pretrained initialization. Next we discuss the nature and effect of these inconsistencies.
2. Distorted features can lead to higher OOD error. Consider a toy example (Figure 2) where d = 2 and the dimensionality of the representations k = 1. The linear head is a scalar quantity that denotes how much the features have to be scaled by. Suppose the ID-subspace is the x-axis. There are different ways of fitting the ID subspace depending on the base features as shown in the figure— both fine-tuned and linear probed estimators match the true parameter in the ID subspace. If the base features are optimal or scaled versions of the optimal, constraints on the ID subspace are sufficient to get good performance in all orthogonal subspaces as well. However, in FT, the features change only for inputs in the ID subspace (see (1)) and thus the updated features are not simply scaling but distortions where even if the ID error is low, error in subspaces orthogonal to the ID subspace can be high, leading to high worst-case OOD error.
The only way the pretrained features are not distorted and only scaled during FT is if the initial features B0 is exactly aligned with the ID subspace (i.e. the subspace of training data). In Figure 2, if B0 is along the x-axis, then updating the features exclusively along the x-axis would simply scale the initial features and not distort them. In this case, the OOD error would not change during FT. However, if the angle is non-zero, the updates would lead to distortions. This motivates our mild non-degeneracy condition where we require the “coverage-angle” to be non-zero.
Definition 3.1 (principal-angle). Let E and F be matrices with orthonormal columns (orthogonal and unit norm) whose columns span R and S⊥. Recall that k = dim(R). We define cos θk(R,S⊥) = σk(E TF ) which is the k-th largest singular value of E⊤F .

heading: 3.2.2 GENERAL RESULT ON THE OOD ERROR OF FINE-TUNING

text:
Our main theorem says that the OOD error of fine-tuning is high.
Theorem 3.1. In the overparameterized linear setting let S⊥ = rowspace(X)⊥, R = rowspace(B0), and v⋆, B⋆ be the optimal parameters with w⋆ = B⋆v⋆. If cos θk(R,S⊥) > 0, then for all t the OOD error of the fine-tuning iterates (Bft(t), vft(t)) is lower bounded:√
Lood(vft(t), Bft(t)) ≥ cos θk(R,S ⊥)√ k min(φ,φ2/∥w⋆∥2) (1 + ∥w⋆∥2)2 − ϵ, (3.7)
where φ2 = (v⊤0 v⋆) 2 − (v⊤⋆ v⋆)2 is defined to be inital head alignment error and ϵ = minU∥B0 − UB⋆∥22 (over rotation matrices U ) is the error in the pretrained feature extractor. Proof sketch. Since the features do not change for examples in S⊥ (perpendicular to the training data), we show that in order to achieve low error on S⊥ the linear head vft(t) would have to become the optimal v⋆ at some time t. The head initialization v0 is random and likely to be far from v⋆
(measured by the alignment error φ), so the the head would have to change a lot for this. As we see from the fine-tuning gradient flow (3.2), vft(t) and Bft(t) change in a “coupled" manner, and a ‘balancedness’ invariant in Du et al. (2018) holds across the fine-tuning trajectory. Correspondingly, if vft(t) changes a lot the features Bft(t) also change a lot—we show that this change would lead to high error on other examples (specifically, examples in S). Either ways, fine-tuning would get some subspace of examples wrong, leading to high OOD error. The full proof appears in Appendix A.
Interpretations of various quantities. Quality of pretrained features (ϵ). To unpack the bound consider a special case where the pretrained features are perfect (ϵ = 0). With perfect features, Proposition A.2 shows that linear probing gets zero OOD error. Theorem 3.1 shows that Lood(vft(t), Bft(t)) > 0 at all times t—so fine-tuning underperforms when the features are perfect.
Alignment error of random head initialization (φ). The lower bound increases as φ increases i.e. alignment error increases. The gradient updates to the head and base parameters are coupled. If the head was initialized perfectly at v⋆, then fine-tuning updates would not increase the OOD error. However, when the head is randomly initialized as is standard in fine-tuning, the alignment error is high, leading to high OOD error. We use this insight in Section 3.4 to show that smarter head initialization (namely via first linear probing) improves OOD performance of fine-tuning.

heading: 3.3 LINEAR PROBING VS FINE-TUNING

text:
In this section, we use our main theorem on fine-tuning (Theorem 3.1) and adapt prior work on linear probing to show for a simple Gaussian data distribution that LP is better than FT, OOD. We assume each training example Xi ∼ N (0, I). Theorem 3.2. In the linear overparameterized setting, suppose the training data is Gaussian. and recall that ϵ is the error in the pretrained feature extractor. Then as the feature extractor error ϵ goes to 0, linear probing does much better than fine-tuning OOD:
Lood(v ∞ lp , B0)
Lood(vft(t), Bft(t))
p→ 0, as ϵ → 0 (3.8)
This holds for all times t for FT (and therefore also for the limit v∞ft , B ∞ ft ) and the LP iterates converge to v∞lp , B0 as a result of the gradient flow on a convex problem.
Intuitively, if the pretrained features are good, LP learns the optimal linear head which has small OOD error while Theorem 3.1 provides a lower bound on the OOD error for fine-tuning. In Appendix A, we also give a threshold T (in terms of d, n, k) where LP does better than FT if ϵ < T .
ID vs OOD error tradeoffs. Until now, we focused on the OOD error and showed how FT can have higher OOD error than LP. However, in practice, we also care about the in-distribution ID error. How do the two methods compare in their ID performance?
For simplicity, we consider the “ID subspace loss” which measures the maximum loss over points in the subspace of training data (S). This allows us to work without distributional assumptions on Pid but it is straightforward to extend to particular distributions. See Appendix A for a formal definition and relationship between ID subspace loss and ID test loss for Gaussian distribution.
If the pretrained initialization is perfect, i.e. B0 = B⋆, then both LP and FT get zero Lid:subspace as they can fit the training data perfectly in an overparameterized setting. But if B0 ̸= B⋆, there may not be a linear head on B0 that fits the training data perfectly and LP can have high ID error. FT, on the other hand, can update the features to find a new B∞ft that can fit the training data perfectly with a linear head v∞ft . We state the formal proposition below relating the ID errors of the two methods.
Proposition 3.1. Suppose w⋆ = B⊤⋆ v⋆ ̸∈ rowspace(B0), and that fine-tuning converges to a local minimum of its loss, then fine-tuning does better ID: Lid:subspace(v∞ft , B ∞ ft ) < Lid:subspace(v ∞ lp , B0).
To summarize, we proved that in a simple Gaussian setting, there are tradeoffs between ID and OOD error: FT has lower ID error but higher OOD error than LP. In the next section, we extend our theoretical insights to show that a simple variant of FT can mitigate such tradeoffs.

heading: 3.4 LINEAR PROBING THEN FINE-TUNING: A SIMPLE VARIANT TO MITIGATE TRADEOFFS

text:
The advantage of fine-tuning is it can adapt both the feature extractor and head to fit the downstream task. Can we keep this benefit while ensuring that our OOD error is low when we have good pretrained features?
Going back to Theorem 3.1, we see that the alignment error in the head initialization φ2 = (v⊤0 v⋆)
2 − (v⊤⋆ v⋆)2 plays an important role. The issue with FT was that under random initialization, φ is usually large and since the gradient updates to the base parameter are coupled with that of the head parameter, the base features get distorted in a manner that increases the OOD error. This suggests that we should use a better head initialization—one obtained from linear probing. If the pretrained features are decent, a linear probed head would be much better aligned with v⋆ allowing the base features to be updated in a manner that does not increase the OOD error. We formally prove this intuition in a simple setting below.
Proposition 3.2. Suppose we have perfect pretrained features B0 = UB⋆ for some rotation U . Let R = rowspace(B0). Under the non-degeneracy conditions cos θk(R,S) ̸= 0, cos θk(R,S⊥) ̸= 0:
∀t, Lood(Bft(t)⊤vft(t)) > 0, if v0 ∼ N (0, σ2I) is randomly initialized (FT) (3.9) ∀t, Lood(Bft(t)⊤vft(t)) = 0, if v0 is initialized to v∞lp (LP-FT) (3.10)

heading: 4 EXPERIMENTS

text:
We run experiments on six benchmark datasets with deep neural networks and see that given good pretrained features, fine-tuning does better ID but worse OOD than linear probing. As predicted by the theory, we find that LP-FT does better than both methods. Finally, we see that a number of predictions from the feature distortion theory hold up in practice. The datasets we use are:
• DomainNet (Peng et al., 2019) is a standard domain adaptation dataset. Here, our ID dataset contains ‘sketch’ images (e.g., drawings of apples, elephants, etc), and the OOD dataset contains ‘real’, ‘clipart’, and ‘painting’ images of the same categories. We use the version of the dataset from Tan et al. (2020).
• Living-17 and Entity-30 are sub-population shift datasets from the BREEDS benchmark (Santurkar et al., 2020). For example, in Living-17 the goal is to classify an image as one of 17 animal categories such as ‘bear’—the ID dataset contains images of black bears and sloth bears and the OOD dataset has images of brown bears and polar bears.
• FMoW Geo-shift is adapted from the satellite remote sensing dataset ‘Functional Map of the World’ (Christie et al., 2018; Koh et al., 2021). The goal is to classify a satellite image into one of 62 categories such as ‘impoverished settlement’. Our ID dataset contains images from North America, and the OOD dataset contains images from Africa and Europe.
• CIFAR-10 → STL is another standard domain adaptation dataset (French et al., 2018), where the ID is CIFAR-10 (Krizhevsky, 2009), and the OOD is STL (Coates et al., 2011).
• CIFAR-10 → CIFAR-10.1 (Recht et al., 2018) is a dataset collected using a very similar protocol to CIFAR-10, and the authors describe it as “a minute distributional shift". The hope is that a classifier trained on CIFAR-10 gets high accuracy on CIFAR-10.1.
Pretraining and models. We use a ResNet-50 architecture for our experiments. We consider a diverse range of pretraining methods and datasets: MoCo-v2 (Chen et al., 2020b), CLIP (Radford et al., 2021), and MoCo-TP (Ayush et al., 2020)—see Appendix B for details.
In Appendix B, we also show results for a larger vision transformer architecture, more fine-tuning baselines, and larger scale datasets (linear probing or fine-tuning on ImageNet (Russakovsky et al., 2015) and evaluating on ImageNetV2 (Recht et al., 2019), ImageNet-R (Hendrycks et al., 2020), ImageNet-Sketch (Wang et al., 2019), ImageNet-A (Hendrycks et al., 2019b)).

heading: 4.1 LINEAR PROBING VS FINE-TUNING

text:
Experiment protocols. We initialize with the pretrained model, and fine-tune or linear probe on ID training examples. For fine-tuning on each dataset we swept over 6 learning rates, using a cosine learning rate schedule and batch size of 64. We early stop and choose the best learning rate using ID validation accuracy. For linear probing we train an ℓ2-regularized logistic regression classifier on frozen features from the penultimate layer of the pretrained model, selecting the best ℓ2-regularization hyperparameter based on ID validation accuracy. For all methods, we run each hyperparameter configuration 3 times (with different random seeds), and take the average accuracy. OOD data was only used for evaluation. For more details, see Appendix B.
Results. Fine-tuning does better than linear probing on 4 out of 5 ID datasets (average accuracy of 85.8% vs 83.5% for linear probing, see Table 1). This is consistent with prior work and intuitions. However, OOD, linear-probing does better on 5 out of 6 distribution shift datasets (average accuracy of 71.6% for linear probing vs 66.8% for fine-tuning, see Table 2). Our datasets vary in size from 20K examples to 150K examples, so this doesn’t appear to be simply because of sample size.

heading: 4.2 LINEAR PROBING THEN FINE-TUNING (LP-FT)

text:
Experiment protocols. For LP-FT, we initialize the neural network head using the linear probed solution, and then fine-tune the model. LP-FT and fine-tuning use similar compute because the linear probing step is much faster than fine-tuning. As with fine-tuning, we sweep over 6 learning rates, early stopping using ID validation accuracy (more details are in Appendix B).
Results. We find that LP-FT gets the best accuracy ID (average: 86.5%) and OOD (average: 74.4%). This is true for 4/5 ID and 6/6 OOD datasets—every dataset except FMoW ID, where LP-FT is better than linear probing but worse than fine-tuning. Since the ID accuracy on FMoW is low (56.5%), this could be because the pretrained features are not good.

heading: 4.3 EXAMINING THE FEATURE DISTORTION THEORY

text:
Early stopping. Our theory predicts that fine-tuning would do worse OOD throughout the process of fine-tuning, and not just at the end. Here, we early stop each fine-tuning method and choose the best learning rate based on target validation accuracy. As expected, fine-tuning does improve a little, but linear probing (average accuracy: 73.0%) is still better than fine-tuning (average accuracy: 70.1%). See Appendix B for per-dataset results.
ID-OOD Features get distorted. The feature distortion theory predicts that fine-tuning changes features for ID examples more than for OOD examples, which is why fitting a head on ID examples performs poorly OOD. The theory also predicts that LP-FT changes the features less than than fine-tuning does. For each example in Living-17, we took the Euclidean distance of the ResNet-50 features before and after fine-tuning. As expected, the average distance for ID examples (0.019) is more than for OOD examples (0.017), and both distances are 20× smaller for LP-FT. We show results for all the other datasets in Appendix B.
Pretrained features must be good, ID-OOD far apart. Our theory says that linear probing does better than fine-tuning OOD, but only if the OOD and ID data are quite different, and the pretrained features are good—otherwise fine-tuning can do better OOD by adjusting the feature extractor ID.
Feature quality: We use a checkpoint of MoCo that got 10% worse accuracy (on ImageNet) and compare linear probing and fine-tuning on Living-17. With worse features, both methods do worse, but fine-tuning (96% ID, 71% OOD) does better than linear probing (92% ID and 66% OOD).
ID ≈ OOD: We fine-tune / linear probe on CIFAR-10, and test on CIFAR-10.1, a dataset collected using a similar protocol to CIFAR-10. As expected, fine-tuning (92.3%) outperforms linear probing OOD (82.7%). Even in this case LP-FT does the best (93.5%).

heading: 5 RELATED WORK AND DISCUSSION

text:
Fine-tuning vs linear probing. Fine-tuning (FT) and linear probing (LP) are popular transfer learning algorithms. There is substantial evidence of FT outperforming LP in-distribution (ID) including recent large-scale investigations (Kornblith et al., 2019; Chen et al., 2021a; Zhai et al., 2020; Chen et al., 2020b) (the only notable exception is in Peters et al. (2019) where LP performs better than FT when using ELMo representations, but worse using BERT). FT is therefore the method of choice for improving accuracy, while LP is used to analyze properties of representations (Peters et al., 2018; Belinkov et al., 2017; Hewitt & Manning, 2019). In our work, we find that FT can underperform LP especially when using high quality pretrained features in the presence of a large distribution shift. There are a variety of other fine-tuning heuristics (Ge & Yu, 2017; Guo et al., 2019; Zhang et al., 2020; Zhu et al., 2020; Jiang et al., 2021; Aghajanyan et al., 2021)—combining our insights with these ideas might lead to better methods.
The benefit of preserving pretrained features. Our work adds to growing evidence that lightweight fine-tuning where only small parts of a pretrained model are updated, extrapolates better under distribution shifts. Zero-shot language prompting in vision (Radford et al., 2021) and other lightweight fine-tuning approaches in NLP (Houlsby et al., 2019; Li & Liang, 2021; Xie et al., 2021b; Lester et al., 2021; Utama et al., 2021; Zhou et al., 2021) improve OOD performance. In independent and concurrent work, Andreassen et al. (2021) observe that through the course of fine-tuning, ID accuracy continues to increase but OOD accuracy plateaus.
Mitigating ID-OOD tradeoffs. While LP-FT has sometimes been used as a fine-tuning heuristic (Kanavati & Tsuneki, 2021; fastai), it has not been used for robustness / OOD accuracy, and we show that it addresses the ID-OOD tradeoff theoretically and empirically. Tradeoffs between ID and OOD accuracy are widely studied and prior work self-trains on large amounts of unlabeled data to mitigate such tradeoffs (Raghunathan et al., 2020; Xie et al., 2021a; Khani & Liang, 2021). In contrast, LP-FT uses no extra unlabeled data and is a simple variant of fine-tuning. In concurrent and independent work, Wortsman et al. (2021) show that ensembling the weights of a zero-shot and fine-tuned model mitigates the ID-OOD tradeoff between these approaches, and this method could be promising for our datasets as well.
Theoretical analysis of transfer learning. Prior works look at ID error (Wu et al., 2020; Tripuraneni et al., 2020; Du et al., 2020), while we look at OOD error. In recent work (Chua et al., 2021) study regularized fine-tuning in an underparameterized regime where there is a unique global optimum. In contrast, our analysis deals with the overparameterized regime (mirroring modern settings of zero train loss) where we need to analyze the trajectory of fine-tuning from the pretrained initialization because there is no unique optimizer of the objective function. See Section C for additional related work on theory of overparameterized models.
Conclusion. There is a strong trend towards leveraging pretrained models to improve downstream performance, and whenever feasible, it is common to fine-tune all model parameters. In this work, we show theoretically and empirically that preserving features might be important for robustness, and simpler approaches like linear-probing can improve OOD performance. This OOD gap between FT and LP grows as the quality of pretrained features improve, so we believe our results are likely to gain significance over time with growing innovations and scale of pretraining.
Theoretical understanding of modern deep learning remains limited, especially the effect of pretraining and transfer learning—our work introduces some ideas for dealing with these challenges. There are several open questions and extensions such as dealing with non-linear activations, different layerwise learning rates, and the effect of explicit regularization.
Finally, we showed LP-FT can mitigate tradeoffs between ID and OOD accuracy in our context. LPFT could be useful in other situations, for example in CLIP we could initialize the final layer with the zero-shot classifier and then fine-tune the entire model, as done in concurrent work (Wortsman et al., 2021). LP-FT is just a first step in leveraging the intuition from our theoretical analysis and we hope that this work inspires new methods of leveraging powerful pretrained models.
Reproducibility: We include proofs for our theoretical results in Appendix A, additional experiment details in Appendix B, and include anonymized source code.

heading: A PROOFS FOR SECTION 3

text:
A.1 ID SUBSPACE LOSS Formally, we define the ID subspace loss as the following:
Lid:subspace(v,B) = max ∥x∥2≤1,x∈S
(v⋆ ⊤B⋆x− v⊤Bx)2 = ||ΠS(B⊤⋆ v⋆)−ΠS(B⊤v)||22, (A.1)
where ΠS projects points onto the subspace S, and we consider norm bounded inputs because the linear regression error scales with the norm.
Consider the simple setting of Gaussian distributions where Pid is drawn from identity covariance in a low dimensional subspace. In this case, the ID subspace loss is equal to the ID test loss with high probability as the training data would span the entire subspace.

heading: A.2 FEATURE DISTORTION THEOREM

text:
We first prove our core theorem, that fine-tuning distorts pretrained features.
Restatement of Theorem 3.1. In the overparameterized linear setting let S⊥ = rowspace(X)⊥, R = rowspace(B0), and v⋆, B⋆ be the optimal parameters with w⋆ = B⋆v⋆. If cos θk(R,S⊥) > 0, then for all t the OOD error of the fine-tuning iterates (Bft(t), vft(t)) is lower bounded:√
Lood(vft(t), Bft(t)) ≥ cos θk(R,S ⊥)√ k min(φ,φ2/∥w⋆∥2) (1 + ∥w⋆∥2)2 − ϵ, (A.2)
where φ2 = (v⊤0 v⋆) 2 − (v⊤⋆ v⋆)2 is defined to be inital head alignment error and ϵ = minU∥B0 − UB⋆∥22 (over rotation matrices U ) is the error in the pretrained feature extractor.
We follow the sketch in the main paper. We begin with a few lemmas, showing that certain quantities are preserved throughout the fine-tuning process.
Our first lemma says that the representations Btftx do not change for examples perpendicular the span of the training examples. Note that the final output vtft ⊤ Btftx still changes, because v t ft changes.
Lemma A.1. For all times t and all x ∈ S⊥, we have:
B0x = B t ftx (A.3)
Proof. We initialized fine-tuning with the feature extractor Bft(0) = B0. It suffices to show that ∂tB t ftx = 0 for all x ∈ S⊥. Recall that ∂tBtft is given by the gradient flow update equation:
∂tB t ft = −∂BL̂(vtft, Btft) = −∂B∥XB⊤v − Y ∥22 (A.4)
Computing the RHS explicitly using multivariable chain rule, we get:
∂tB t ft = −2v(XB⊤v − Y )⊤X (A.5)
Since x is a constant, we get:
∂tB t ftx = −2v(XB⊤v − Y )⊤Xx (A.6)
But Xx = 0 for x ∈ S⊥, since x ∈ S⊥ is defined as x is perpendicular to the rowspace of X (i.e., perpendicular to the rows of X). So the RHS is 0—that is, ∂tBtftx = 0, as desired.
Next, we show that the change in the head and feature extractor are ‘coupled’. So if the head changes in a certain way, then the feature extractor cannot just stay the same. In the literature, this is sometimes called the “balancedness" lemma, and has been proved in prior work on two layer linear networks.
Lemma A.2. For all t we have:
v0v ⊤ 0 −B0B⊤0 = vtftvtft ⊤ −BtftBtft ⊤ (A.7)
Proof. This follows by showing that the derivative is 0:
∂t[v t ftv t ft ⊤ −BtftBtft ⊤ ] = 0 (A.8)
Which can be verified by direct calculation. See Theorem 2.2 in Du et al. (2018) and the proof of Theorem 1 in Arora et al. (2018).
For our proof we will require that every feature r ∈ R can be generated from some OOD direction, that is r = B0u for some u ∈ S⊥. We will show that this is implied by the condition on the principal angle: cos θk(R,S⊥) > 0 where R = rowspace(B0), which we assumed in Theorem 3.1. The following lemma shows this (and also quantifies that the norm of u does not shrink too much when projected onto R).
Lemma A.3. Suppose R is a dimension k subspace of Rd and S⊥ has dimension d′ ≥ 1. Consider any vector r ∈ R with ∥v∥2= cos θk(R,S⊥). Then there exists u ∈ S⊥ with ∥u∥2≤ 1 such that ΠR(u) = r.
Proof. Let c = cos θk(R,S⊥). Firt, we get rid of an easy case—if c = 0, then we have ∥r∥2= 0, so r = 0. Then we can just pick u = 0, and ΠR(u) = 0 = r. So for the rest of the proof we assume c > 0.
Consider arbitrary vector r ∈ R with ∥r∥2≤ c. Let E ∈ Rd×d ′ , F ∈ Rd×k have orthonormal columns, which form a basis for S⊥ and R respectively. We can write r = Fz for some z ∈ Rk since the columns of F form a basis for R.
By definition of cos θk (Definition 3.1), we have that c = σk(F⊤E). So σk(F⊤E) > 0 which means F⊤E has rank k. Since columns of F⊤E are in Rk this means F⊤E has full column rank so we can find y ∈ rowspace(V ⊤) with F⊤Ey = z. Then since y is in the rowspace of F⊤E, a standard result (e.g., see Lemma A.4) is:
∥z∥2= ∥F⊤Ey∥2≥ σk(F⊤E)∥y∥2= c∥y∥2 (A.9) But since F has orthonormal columns, ∥r∥2= ∥Fz∥2= ∥z∥2. This means ∥y∥2≤ ∥r∥2/c ≤ 1. Letting u = Ey, so far we’ve shown that r = Fz = F (F⊤Ey) = (FF⊤)u, with ∥y∥2≤ 1, where we note that FF⊤ = ΠR is the projection operator onto R. So r = ΠR(u). But since the columns of E are orthonormal, we have ∥u∥2= ∥Ey∥2= ∥y∥2≤ 1. u = Ey is also in S⊥, because the columns of E form a basis for S⊥.
So to summarize, we found u ∈ S⊥ such that ΠR(u) = r and ∥u∥≤ 1, as desired.
In the lemma above, we used a standard linear algebraic result that we include for completeness. This says that A cannot shrink vectors in its rowspace too much, where the shrinkage factor is given by the minimum singular value of A.
Lemma A.4. Let A ∈ Rm×n. Let r = min(m,n). Then if x ∈ rowspace(A), we have ∥Ax∥2≥ σr(A)∥x∥2.
Proof. We bound the norm of x using the SVD. Consider the singular value decomposition (SVD) of A: A = UDV ⊤ (A.10) Where U ∈ Rm×r, D ∈ Rr×r, V ⊤ ∈ Rr×n, where U and V have orthonormal columns, and D = diag(σ1, . . . , σr) is a diagonal matrix with σ1 ≥ . . . ≥ σr ≥ 0.
∥Ax∥2 = ∥UDV ⊤x∥2 [Definition of r] (A.11) = ∥DV ⊤x∥2 [U ∈ Rm×r has orthonormal columns] (A.12) ≥ σr∥V ⊤x∥2 [D is diagonal] (A.13) = σr∥x∥2 [rows of V ⊤ are orthonormal, x is in rowspace] (A.14) = σr(A)∥x∥2 (A.15)
Where for the fourth step, we used the fact that if x ∈ rowspace(V ⊤) and the rows of V ⊤ are orthonormal, then ∥V ⊤x∥2= ∥x∥2. One way to see this is by writing x = ∑ i αivi, where vi are rows of V ⊤, and then noting that V ⊤x = (α1, . . . , αr) and so x and V ⊤x have the same norm.
We now prove Theorem 3.1, following the 3 steps outlined in the main text.
Proof of Theorem 3.1. Let c = cos θk(R,S⊥).
Because it makes the proof much easier, we will prove the contrapositive, and then convert back to the original theorem statement. We assume √ Lood(vtft, B t ft) ≤ ∆, and will show that:
|(v⊤0 v⋆)2 − (v⊤⋆ v⋆)2| ≤ ∆+ ϵ
c g1(∥w∥2)
√ k + (∆+ ϵ)2
c2 g2(∥w∥2)k (A.16)
Where g1 and g1 are non-negative polynomials we will bound in the proof.
We gave a basic outline of the proof in the main paper, and here we are just trying to be careful about capturing all the dependencies. We also give intuition for each step before diving into algebra (which we include for completeness).
Recall that in the overparameterized linear setting we assumed we have orthonormal B0 with ∥B0− UB⋆∥2≤ ϵ for some U . We note that the setup is rotationally symmetric so without loss of generality we can suppose ∥B0 − UB⋆∥2≤ ϵ. This is because we can let B′⋆ = UB⋆ and v′⋆ = Uv⋆, and we have w⋆ = B⊤⋆ v⋆ = (UB⋆)
⊤(Uv⋆), where w⋆ is the optimal classifier—so we can now write the entire proof in terms of B′⋆ and v ′ ⋆.
Step 1: Show that ∥vtft − v⋆∥2≤ ∆/c: We first give intuition and then dive into the math. The key insight is to use the fact that in ‘many’ directions Btft and B0 are the same (formally, for all x ∈ S⊥, Btftx = B0x). But B0 and B⋆ are close by assumption, which means that B t ft and B⋆ are close in ‘many’ directions. Since we assumed in the contrapositive that vtft ⊤ Btft and v ⊤ ⋆ B⋆ are close, we get that vtft and v⋆ are close in ‘many’ directions. Because S ⊥ covers the rowspace of B0, we get that ‘many’ is k, which is precisely the dimensionality of v⋆, so the two vectors vtft and v⋆ must be close.
We now dive into the math. Since B0 has orthogonal rows, B0 has full column rank.
Let z be given by:
z = c
∥vtft − v⋆∥2 (vtft − v⋆) (A.17)
We note that ∥z∥2= c. Then, we can find y ∈ R = rowspace(B0) such that B0y = z (since B0 has full column-rank) and then ∥y∥2= ∥z∥2= c (since B0 has orthonormal rows).
Since c = cos θk(R,S⊥) > 0, and y ∈ R with ∥y∥= c, from Lemma A.3 we can choose x ∈ S⊥ with ∥x∥2≤ 1 and ΠR(x) = y. Then, we have B0x = z.
From Proposition A.1, since x ∈ S⊥, B0 does not change in directions of x when fine-tuning so we have: B0x = Btftx.
The claim now follows from simple algebraic manipulation, following the intuition we described. The algebra just captures what ‘close’ means and adds up the error terms.
∥vtft − v⋆∥2 = 1
c (vtft − v⋆)⊤( c(vtft − v⋆) ∥vtft − v⋆∥2 ) [Algebra] (A.18)
= 1
c (vtft − v⋆)⊤z [Definition of z] (A.19)
= 1
c (vtft − v⋆)⊤B0x [Since B0x = z] (A.20)
= 1
c (vtft
⊤ B0x− v⊤⋆ B0x) [Algebra] (A.21)
= 1
c (vtft
⊤ Btftx− v⊤⋆ B0x) [Btftx = B0x since x ∈ S⊥]
(A.22)
= 1
c (vtft
⊤ Btft − v⊤⋆ B0)x [Algebra] (A.23)
≤ 1 c ∥vtft ⊤ Btft − v⊤⋆ B0∥2∥x∥2 [Cauchy-Schwarz] (A.24) ≤ 1 c ∥vtft ⊤ Btft − v⊤⋆ B0∥2 [since ∥x∥2≤ 1] (A.25) ≤ 1 c ∥vtft ⊤ Btft − v⊤⋆ B⋆∥2+ 1 c ∥v⊤⋆ B⋆ − v⊤⋆ B0∥2 [Triangle inequality] (A.26) = 1
c Lood(v
t ft, B t ft) +
1 c ∥v⊤⋆ B⋆ − v⊤⋆ B0∥2 [definition of Lood] (A.27)
= 1
c Lood(v
t ft, B t ft) +
1 c σmax(B0 −B⋆)∥v⋆∥2 [definition of max singular value]
(A.28)
= 1
c Lood(v
t ft, B t ft) +
1 c ϵ∥v⋆∥2 [since σmax(B0 −B⋆) ≤ ϵ]
(A.29)
≤ ∆+ ϵ∥v⋆∥2 c
[since Lood(vtft, B t ft) ≤ ∆]
(A.30) (A.31)
Which shows that ∥vtft − v⋆∥2≤ (∆ + ϵ∥v⋆∥2)/c.
Step 2A: Show that ∥Btft∥2F is small: The key insight is to take the trace on both sides of Proposition A.2, which bounds the Frobenius norm of Btft and therefore the operator norm.
Rearranging Proposition A.2, we have:
BtftB t ft ⊤ = B0B ⊤ 0 + v⋆v ⊤ ⋆ − v0v⊤0 (A.32)
Taking the trace everywhere, we get:
Tr(BtftB t ft ⊤ ) = Tr(B0B ⊤ 0 ) + Tr(v⋆v ⊤ ⋆ )− Tr(v0v⊤0 ) (A.33)
For any matrix A, Tr(AA⊤) = ∥A∥2F , and for a vector v the Frobenius norm is just the ℓ2-norm, so Tr(vv⊤) = ∥v∥22. So we have:
∥Btft∥2F= ∥B0∥2F+∥v⋆∥22−∥v0∥22 (A.34) Squares are non-negative, so we get the inequality:
∥Btft∥2F≤ ∥B0∥2F+∥v⋆∥22 (A.35)
Step 2B: Show that ∥B⊤0 v⋆∥22−∥Btft ⊤ v⋆∥22 is small: This step doesn’t involve much insight, and is standard peturbation analysis—we simply factor the difference of squares and bound each term.
First, we bound ∥Btft ⊤ vtft −Btft ⊤ v⋆∥2:
∥Btft ⊤ vtft −Btft ⊤ v⋆∥2 ≤ σmax(Btft)∥vtft − v⋆∥2 (A.36)
≤ ∥Btft∥F ∥vtft − v⋆∥2 (A.37) ≤ √ ∥B0∥2F+∥v⋆∥22∥v t ft − v⋆∥2 (A.38)
≤ √ ∥B0∥2F+∥v⋆∥22 (∆+ ϵ∥v⋆∥2
c
) (A.39)
Next, we bound ∥B⊤0 v⋆ −Btft ⊤ v⋆∥2:
∥B⊤0 v⋆ −Btft ⊤ v⋆∥2 ≤ ∥B⊤0 v⋆ −B⊤⋆ v⋆∥2+∥B⊤⋆ v⋆ −Btft ⊤ v⋆∥2 (A.40)
≤ σmax(B0 −B⋆)∥v⋆∥2+∥B⊤⋆ v⋆ −Btft ⊤ v⋆∥2 (A.41) ≤ ϵ∥v⋆∥2+∥B⊤⋆ v⋆ −Btft ⊤ v⋆∥2 (A.42) ≤ ϵ∥v⋆∥2+∥B⊤⋆ v⋆ −Btft ⊤ vtft∥2+∥Btft ⊤ vtft −Btft ⊤ v⋆∥2 (A.43)
≤ ϵ∥v⋆∥2+∆+ √ ∥B0∥2F+∥v⋆∥22 (∆+ ϵ∥v⋆∥2 c ) (A.44)
=: ∆2 (A.45)
Finally, we bound |∥B⊤0 v⋆∥22−∥Btft ⊤ v⋆∥22|, using the identity:
|∥u∥22−∥v∥22| = |(u− v)⊤(u+ v)| (A.46) ≤ ∥u− v∥2∥u+ v∥2 (A.47) ≤ ∥u− v∥2(2∥u∥2+∥u− v∥2) (A.48)
Applying this:
|∥B⊤0 v⋆∥22−∥Btft ⊤ v⋆∥22| ≤ ∥B⊤0 v⋆ −Btft ⊤ v⋆∥2(2∥B⊤0 v⋆∥2+∥B⊤0 v⋆ −Btft ⊤ v⋆∥2) (A.49)
≤ ∆2(2∥B⊤0 v⋆∥2+∆2) (A.50) ≤ ∆2(2∥B⊤⋆ v⋆∥2+2∥B⊤0 v⋆ −B⊤⋆ v⋆∥2+∆2) (A.51) ≤ ∆2(2∥w⋆∥2+2ϵ∥v⋆∥2+∆2) (A.52) =: ∆3 (A.53)
Step 3: Use Proposition A.2 to show v0 and v⋆ must be close: The key insight is that we start from Proposition A.2, and left and right multiply by v⋆, after that we use the previous steps and do some some standard perturbation analysis.
We start from Proposition A.2:
v0v ⊤ 0 −B0B⊤0 = vtftvtft ⊤ −BtftBtft ⊤ (A.54)
The key step is to left multiply both sides by v⊤⋆ and right multiply both sides by v⋆ to get:
(v⊤0 v⋆) 2 − ∥B⊤0 v⋆∥22= (vtft ⊤ v⋆) 2 − ∥Btft ⊤ v⋆∥22 (A.55)
Rearranging, and then using Equation A.49, we get:
|(vtft ⊤ v⋆) 2 − (v⊤0 v⋆)2| = |∥Btft ⊤ v⋆∥22−∥B⊤0 v⋆∥22| ≤ ∆3 (A.56)
This is close to what we want, except we have (vtft ⊤ v⋆) 2 on the LHS instead of (v⊤⋆ v⋆) 2. We previously showed that vtft and v⋆ are close, in Step 1, so with some algebra we can bound the difference between (vtft ⊤ v⋆) 2 and (v⊤⋆ v⋆) 2:
|(vtft ⊤ v⋆) 2 − (v⊤⋆ v⋆)2| = |(vtft ⊤ v⋆ − v⊤⋆ v⋆)⊤(vtft ⊤ v⋆ + v ⊤ ⋆ v⋆)| (A.57)
= |(vtft ⊤ v⋆ − v⊤⋆ v⋆)⊤[2v⊤⋆ v⋆ + (vtft ⊤ v⋆ − v⊤⋆ v⋆)]| (A.58) = |(v⊤⋆ (vtft − v⋆))⊤[2v⊤⋆ v⋆ + (v⊤⋆ (vtft − v⋆))]| (A.59) ≤ ∥vtft − v⋆∥2∥v⋆∥22[2∥v⋆∥2+∥vtft − v⋆∥2] (A.60) = (∆/c)∥v⋆∥22(2∥v⋆∥2+(∆/c)) := ∆4 (A.61)
Above, from the third line to the fourth line, we used triangle inequality and Cauchy-Schwarz.
So finally, by triangle-inequality we can now bound |(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2|:
|(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2| ≤ |(v⊤⋆ v⋆)2 − (vtft ⊤ v⋆) 2|+ |(vtft ⊤ v⋆) 2 − (v⊤0 v⋆)2| (A.62) ≤ ∆4 +∆3 (A.63)
Wrap up i.e., writing out ∆4 +∆3 explicitly: This is basically the bound we want, but we would like to express ∆3,∆4 in terms of ∆ and ϵ. Note that this step has no insight, and is just algebra—we include the details for reference and verifiability. We recall:
∆4 = (∆/c)∥v⋆∥22(2∥v⋆∥2+(∆/c)) (A.64) ∆3 = ∆2(2∥w⋆∥2+2ϵ∥v⋆∥2+∆2) (A.65)
∆2 = ϵ∥v⋆∥2+∆+ √ ∥B0∥2F+∥v⋆∥22 (∆+ ϵ∥v⋆∥2
c
) (A.66)
Since B0 has orthogonal rows (by assumption), B⊤0 has orthogonal columns, so ∥w⋆∥2= ∥B⊤0 v⋆∥2= ∥v⋆∥2. In addition, since B0 has k orthogonal rows, ∥B0∥F= √ k. We also note
that √ ∥B0∥2F+∥v⋆∥22 ≤ ∥B0∥F+∥v⋆∥2= √ k + ∥w⋆∥2. Since c ≤ 1, we have:
ϵ∥v⋆∥2+∆ ≤ (∆+ ϵ∥v⋆∥2
c
) (A.67)
So for ∆2, up to constant factors we can ignore the ϵ∥v⋆∥2+∆ term—this means we get: ∆2 ≤ O ( ( √ k + ∥w⋆∥2) (∆+ ϵ∥w⋆∥2 c )) (A.68) Using the fact that √ k + ∥w⋆∥2≤ √ k(1 + ∥w⋆∥) we get:
∆2 ≤ O (√ k(1 + ∥w⋆∥) (∆+ ϵ∥w⋆∥2
c
)) (A.69)
Then since ∆+ ϵ∥w⋆∥2≤ (1 + ∥w⋆∥2)(∆ + ϵ), we get: ∆2 ≤ O (√ k(1 + ∥w⋆∥)2 (∆+ ϵ
c
)) (A.70)
Now for ∆3, first note that ϵ ≤ 2, since B⋆ and B0 have orthogonormal rows so ∥B⋆ − B0∥2≤ 2. This means that ϵ∥w⋆∥2≤ ∥w⋆∥2, so ∆3 simplifies to:
∆3 ≤ O(∆2(∥w⋆∥2+∆2)) = O(∆2∥w⋆∥2+∆2) (A.71) Substituting the bound for ∆2 into ∆3, we get:
∆3 ≤ O (√ k∥w⋆∥2(1 + ∥w⋆∥)2 (∆+ ϵ∥w⋆∥2
c
) + k(1 + ∥w⋆∥)4 (∆+ ϵ∥w⋆∥2 c )2) (A.72)
For ∆4, we get:
∆4 ≤ O ( ∥w⋆∥32 ∆
c + ∥w⋆∥2(
∆ c ) )
(A.73)
Since ∆/c ≤ (∆ + ϵ)/c and ∥w⋆∥22≤ (1 + ∥w⋆∥2)2 we have for the final error ∆3 +∆4:
∆3 +∆4 ≤ √ kw(1 + ∥w⋆∥22)2 (∆+ ϵ c ) + k(1 + ∥w⋆∥22)4 (∆+ ϵ c )2 (A.74)
Wrap up i.e., taking the contrapositive: So we’ve shown that if √ Lood(vtft, B t ft) ≤ ∆, then:
|(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2| ≤ ∆+ ϵ
c w(1 + ∥w⋆∥22)2
√ k + (∆+ ϵ)2
c2 (1 + ∥w⋆∥22)4k (A.75)
We’d like to flip this around: suppose |(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2| ≥ φ2 for some φ. To lower bound Lood(v t ft, B t ft), we simply take the contrapositive of what we have proved. Let ∆ be given by:
∆ = min ( c w(1 + ∥w⋆∥22)2 √ k φ2, c√ (1 + ∥w⋆∥22)4k φ ) − ϵ (A.76)
In this case with some algebra, we can show that:
|(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2| ≥ φ2 ≥ ∆+ ϵ
c w(1 + ∥w⋆∥22)2
√ k + (∆+ ϵ)2
c2 (1 + ∥w⋆∥22)4k (A.77)
To see this, we bound each of the terms in the RHS separately using our definition of ∆. Then, from the contrapositive of what we proved (compare with Equation A.75, we get:√
Lood(vtft, B t ft) ≥ ∆ (A.78)
Finally, we can massage ∆ to combine terms and make it look slightly nicer:
∆ ≥ c√ k min(φ,φ2/∥w⋆∥2) (1 + ∥w⋆∥2)2 − ϵ (A.79)
For even more interpretability, if ∥w∥2= 1 and φ is bounded above by some constant, then you can think of ∆ as approximately c√
k φ2 − ϵ. This completes the proof.

heading: A.3 LP VS FT IN THE GAUSSIAN SETTING (OOD)

text:
We now prove Theorem 3.2, which compared linear probing and fine-tuning in the linear overparameterized setting, when the covariates were Gaussian.
Restatement of Theorem 3.2. In the linear overparameterized setting, suppose the training data is Gaussian. and recall that ϵ is the error in the pretrained feature extractor. Then as the feature extractor error ϵ goes to 0, linear probing does much better than fine-tuning OOD:
Lood(v ∞ lp , B0)
Lood(vft(t), Bft(t))
p→ 0, as ϵ → 0 (A.80)
This holds for all times t for FT (and therefore also for the limit v∞ft , B ∞ ft ) and the LP iterates converge to v∞lp , B0 as a result of the gradient flow on a convex problem.
At a high level, we use Theorem 3.1 to lower bound the OOD error of fine-tuning, and then upper bound the OOD error of linear probing.
To lower bound the OOD error of fine-tuningwe need to lower bound cos θk(R,S⊥) and Head-Error(v0, v⋆). We reduce lower bounding cos θk(R,S⊥) to a Random Matrix Theory of bounding the min and max singular values of matrices involving B0 and S⊥. Lower bounding Head-Error(v0, v⋆) is a straightforward anti-concentration result (showing that a sample from a Gaussian is not too close to 0).
We first bound cos θk(R,S) and then the bound for cos θk(R,S⊥) follows. We show that cos θk(R,S) > 0 almost surely (with probability 1), and moreover give a quantitative lower bound for cos θk(R,S).
Lemma A.5. Fix a k dimensional subspace R. Let S be a subspace spanned by x1, . . . , xn ∈ Rd where xi are sampled independently from N(0, σ2I), with k < n < d. Then with probability at least 1− δ,
cos θk(R,S) ≥
√ n− √ k − √ 2 log 1δ√
d log 2dδ
(A.81)
In addition, we get that cos θk(R,S) > 0 almost surely (with probability 1).
If n ≥ 5k and n ≥ 10 log 1δ , then we get: cos θk(R,S) ≥ O (√ n
d log 2dδ
) (A.82)
Recall that big-oh notation here means that the RHS is true for some universal constant (independent of any other problem parameters).
Proof. We note that since x1, . . . , xn are sampled from N(0, σ2Id), which is rotationally invariant, every rotation of the subspace spanned by the n points has equal probability. In other words, we are choosing a uniformly random n dimensional subspace (formally: this is a uniform random measure over the Grassmannian manifold).
Note that principal angles are invariant if we rotate R and S by the same rotation matrix U . This symmetry means that we can fix S and instead consider R to be a uniform random k dimensional subspace on the Grassmannian manifold. Without loss of generality, we can also fix S to be the first k standard basis vectors ((1, 0, 0, . . . , 0), (0, 1, 0, . . . , 0), . . . , (0, 0, 0, . . . , 1)).
Equivalently, let MR be a d-by-k matrix, where each column is sampled independently from N(0, Id) (the σ2 makes no difference to the subspace)—since the columns of MR span a uniformly random k-dimensional subspace, so we can let R be range of MR. This is equivalent to sampling each entry of MR from N(0, 1).
Let c = cos θk(R,S). We note that c can be written as (this is a simple transformation of Definition 3.1):
c = min r∈R,∥r∥2≤1
∥ΠS(r)∥2 (A.83)
Now, any r ∈ R can be written as r = MRλ for some λ ∈ Rk. We first show that ∥λ∥2 cannot be much smaller than ∥r∥2. This is because:
∥r∥2= ∥MRλ∥2≤ σmax(MR)∥λ∥2 (A.84)
So this gives us:
∥λ∥2≥ ∥r∥2
σmax(MR) (A.85)
So every r ∈ R can be written as MRλ where ∥λ∥2 is lower bounded as above. We now simplify the definition of c, starting from Equation A.83.
c = min r∈R,∥r∥2≤1
∥ΠS(r)∥2 (A.86)
≥ min ∥λ∥≥1/σmax(MR) ∥ΠSMRλ∥2 (A.87)
≥ min ∥λ∥≥1/σmax(MR) σmin(ΠSMR)∥λ∥2 (A.88)
= σmin(ΠSMR)
σmax(MR) (A.89)
So now we want to lower bound the ratio of two random matrices. We note that ΠSMR is a matrix of size (n, k) with each entry sampled independently from N(0, 1) (this is because ΠS simple selects the first n rows of MR). MR is a matrix of size (d, k) with each entry sampled independently from N(0, 1). So standard matrix concentration results (Tropp, 2015; Absil et al., 2006) bound the singular values, and we get that with probability at least 1− δ:
σmin(ΠSMR) ≥ √ n− √ k − √ 2 log 1
δ (A.90) σmax(MR) ≤ √ d log 2d
δ (A.91)
Note that we can use alternate bounds for σmin that are sometimes tighter. So for the ratio of the two, we get that with probability at least 1− δ, we have:
c ≥ σmin(ΠSMR) σmax(MR) ≥
√ n− √ k − √ 2 log 2δ√
d log 2dδ
(A.92)
For interpretability, ignoring log factors this is approximately:
c ⪆
√ n− √ k√
d (A.93)
The result when n ≥ 5k and n ≥ 10 log 2δ follows with simple algebra. For the result where we show cos θk(R,S) > 0 almost surely, we recall that ΠSMR is a matrix of size (n, k) with each entry sampled independently from N(0, 1). Then applying Lemma 3 in Xie et al. (2021a), we get that σmin(ΠSMR) > 0 almost surely. Since σmax(MR) is finite, this gives us cos θk(R,S) > 0 almost surely.
If the training data is Gaussian then the span of the training data S is a random n-dimensional subspace with n < d. So the orthogonal complement S⊥ is a random d − n dimensional subspace and the same argument as Lemma A.5 applies.
Corollary A.1. In the linear overaparameterized setting, under the Gaussian data assumption, let R = range(B0). Then with probability at least 1 − δ, where the probability is over the fine-tuning examples:
cos θk(R,S ⊥) ≥
√ d− n− √ k − √ 2 log 1δ√
d log 2dδ
(A.94)
In addition, we get that cos θk(R,S⊥) > 0 almost surely (with probability 1).
If d− n ≥ 5k and d− n ≥ 10 log 1δ , then we have:
cos θk(R,S ⊥) ≥ √ d− n d log 2dδ
(A.95)
We now bound Head-Error(v0, v⋆). Note that if the head is initialized as v0 = 0, then Head-Error(v0, v⋆) = ∥v⋆∥22= ∥w⋆∥22. In practice, the head is usually initialized randomly, for example normally distributed. Intuitively, the head error is still high because we do not know which direction the head is pointing in, so most of the time the initial (randomly sampled) head will be pointing in the wrong direction. If v0 ∼ N(0, σ2I) can show that for any σ2, the head error will still typically be at least Ω(∥v⋆∥2) This is an illustrative result, one can show similar results for other random initializations as well.
We first prove an anti-concentration lemma, which says that if u is univariate Gaussian, then it cannot be too close to any particular constant a, no matter how the variance of the Gaussian is chosen.
Lemma A.6. For some universal constant c, given a > 0, for all ν2 if u ∼ N(0, ν2) then for all 0 ≤ δ ≤ 1:
P (|u− a| ≤ cδa) ≤ δ (A.96)
Proof. Consider δ such that δ ≤ 1/10. Then for all u with |u − a| ≤ δa, we have u ≥ 9a/10. For all u ≥ 9a/10, the density f(u) is upper bounded (from the formula for the density of a Gaussian random variable) by:
f(u) ≤ O(1 v exp
−92a2
2 · 102v2 ) ≤ 1 v (1− 9
2a2
2 · 102v2 ) (A.97)
We can maximize this explicitly (e.g., use Mathematica) and we get for some universal constant c′ ≥ 10 (it is OK to choose a larger universal constant than needed):
f(u) ≤ c ′
a (A.98)
Since the density is less than 1/a and if |u − a| ≤ δa the size of the interval is 2δa, we get for all δ ≤ 1/10:
P (|u− a| ≤ δa) ≤ 2c ′δa
a = 2c′δ (A.99)
Now, we substitute δ′ = 2c′δ. We get for all δ′ ≤ 2c′/10:
P (|u− a| ≤ 1 2c′ δ′a) ≤ δ′ (A.100)
Since c′ ≥ 10, 2c′/10 ≥ 1, so the statement is true for all 0 ≤ δ′ ≤ 1.
We now bound the error in the head if the initialization is Gaussian. This bound holds for all initialization variances σ2. Similar bounds can be shown for other (non-Gaussian) head initializations using similar anti-concentration arguments.
Lemma A.7. For all σ, if v0 ∼ N(0, σ2Ik), for some universal constant c, we have with probability at least 1− δ:
(Head-Error(v0, v⋆))2 = |(v⊤0 v⋆)2 − (v⊤⋆ v⋆)2| > cδ(v⊤⋆ v⋆)2 (A.101)
Proof. First note that Head-Error(v0, v⋆) = Head-Error(−v0, v⋆) and v0 is symmetric around 0 (v0 and −v0 have the same probability). So without loss of generality, we can suppose that v⊤0 v⋆ ≥ 0. Suffices to bound |v⊤0 v⋆ − v⊤⋆ v⋆|: We decompose the error:
|(v⊤0 v⋆)2 − (v⊤⋆ v⋆)2| = |v⊤0 v⋆ − v⊤⋆ v⋆|(|v⊤0 v⋆ + v⊤⋆ v⋆|) (A.102) ≥ |v⊤0 v⋆ − v⊤⋆ v⋆|(v⊤⋆ v⋆)| (A.103)
So we bound |v⊤0 v⋆ − v⊤⋆ v⋆|. v⊤0 v⋆ is normally distributed: We note that v⊤0 v⋆ is distributed as:
v⊤0 v⋆ ∼ N(0, σ2v⊤⋆ v⋆) (A.104)
In other words, a normal with mean 0, and variance σ21 = σ 2v⊤⋆ v⋆, and therefore standard deviation σ1 = σ √ v⊤⋆ v⋆.
Apply Gaussian anti-concentration lemma: Then, from Lemma A.6, we have for some universal constant c that with probability at least 1− δ:
|v⊤0 v⋆ − v⊤⋆ v⋆| ≥ cδv⊤⋆ v⋆ (A.105)
So substituting this back into Equation A.102, we get the desired result::
|(v⊤0 v⋆)2 − (v⊤⋆ v⋆)2| > cδ(v⊤⋆ v⋆)2 (A.106)
Lemma A.8. In the overparameterized linear setting, if d ≥ n ≥ 5k and n ≥ 10 log 1δ then with probability at least 1− δ, the linear probing OOD error is upper bounded by:√
Lood(v∞lp , B0) ≤ O ( d n log ( d δ )ϵ∥w⋆∥2 ) (A.107)
Without these conditions on d, n, k, we have for every δ > 0, there exists some cδ > 0 such that with probability 1− δ: √
Lood(v∞lp , B0) ≤ cδϵ∥w⋆∥2 (A.108)
Proof. Suppose n > k. Let X be a matrix of shape (n, d), where the i-th row contains the i-th data point (which we assumed was sampled from N(0, Id).
Before proceeding with the proof, we make a quick note that BX⊤XB⊤ is invertible almost surely. Reason: X is a Gaussian random matrix with each entry sampled independently from N(0, σ2), with shape (n, d). B is a matrix of shape (k, d) with orthogonal rows, so BX⊤ is a matrix of shape (k, n) with each entry sampled independently from N(0, σ2). Since n > k this has rank k almost surely, and BX⊤XB⊤ has the same rank (k) and is therefore full rank, which means it is invertible.
In other words, there is a unique global minimum (minimizing over v) to the loss optimized by linear-probing:
argmin v
∥XB⊤0 v −XB⊤⋆ v⋆∥22= (B0X⊤XB⊤0 )−1B0X⊤XB⊤⋆ v⋆ (A.109)
We can see this by noting that the loss function on the LHS is strongly convex in v since BX⊤XB⊤ is invertible. Then, gradient flow converges to the unique minimizer on the RHS, so:
v∞lp = (B0X ⊤XB⊤0 ) −1BX⊤XB⊤⋆ v⋆ (A.110)
We now bound the square-root OOD error (taking the square root makes it easier to apply triangle inequalities), starting with the definition:√
Lood(v∞lp , B0) = ∥B ⊤ ⋆ v⋆ −B⊤0 v∞lp ∥2 (A.111)
≤ ∥(B⊤⋆ v⋆ −B⊤0 v⋆) + (B⊤0 v⋆ −B0v∞lp )∥2 (A.112) ≤ ∥B⊤⋆ v⋆ −B⊤0 v⋆∥2︸ ︷︷ ︸
(1)
+ ∥B⊤0 v⋆ −B0v∞lp )∥2︸ ︷︷ ︸ (2)
(A.113)
We bound each term on the RHS of the last line. For term (1):
∥B⊤⋆ v⋆ −B⊤0 v⋆∥2 ≤ σmax(B⋆ −B0)∥v⋆∥2 (A.114) ≤ ϵ∥w⋆∥2 (A.115)
Let Σ = X⊤X . For term (2), we first subtitute v∞lp and do some algebra to get:
∥B⊤0 v⋆ −B0v∞lp )∥2 = ∥B⊤0 (B0ΣB⊤0 )−1B0Σ(B0 −B⋆)v⋆∥2 (A.116) ≤ σmax(B⊤0 (B0ΣB⊤0 )−1B0Σ)σmax(B0 −B⋆)∥w⋆∥2 (A.117) ≤ σmax(B⊤0 (B0ΣB⊤0 )−1B0Σ)ϵ∥w⋆∥2 (A.118)
≤ σmax(B0)2σmax(Σ) 1
σmin(B0ΣB⊤0 ) ϵ∥w⋆∥2 (A.119)
≤ σmax(B0) 2σmax(X) 2
σmin(XB⊤)2 ϵ∥w⋆∥2 (A.120)
(A.121)
So it suffices to bound the max singular value in the RHS. Since B0 has orthonormal rows, σmax(B0) = 1. For the other singular values, we do some standard random matrix theory (Tropp, 2015; Absil et al., 2006). We get with probability at least 1− δ:
σmax(X) 2 ≤ O(d log d
δ ) (A.122)
σmin(XB ⊤) ≥ √ n− √ k − √ 2 log 1
δ (A.123)
We assumed n ≥ 5k and n ≥ 10 log 1δ , then we get:
σmin(XB ⊤) ≥ O( √ n) (A.124)
Substituting back into Equation A.116 we get: ∥B⊤0 v⋆ −B0v∞lp )∥2≤ O ( d n log ( d δ )ϵ∥w⋆∥2 ) (A.125)
Substituting into equation A.111 and noting that n ≤ d, we have:√ Lood(v∞lp , B0) ≤ O ( d n log ( d δ )ϵ∥w⋆∥2 ) (A.126)
Which completes the proof of the first part. For the second part, where we want to show √
Lood(v∞lp , B0) ≤ cδϵ∥w⋆∥2 without the extra conditions on n, k, we use the fact that σmax(X) is upper bounded almost surely, and σmin(XB⊤) > 0 almost surely (from Lemma 3 in Xie et al. (2021a), which only requires absolute continuity). This implies that for some cδ > 0 that can depend on δ, with probability at least 1− δ:
σmax(B0) 2σmax(X) 2
σmin(XB⊤)2 ≤ cδ (A.127)
which means that √ Lood(v∞lp , B0) ≤ cδϵ∥w⋆∥2, as desired.
We now prove Theorem 3.2. This shows that the ratio of the OOD errors of linear probing over fine-tuning goes to 0 as the representation error ϵ goes to 0. In the next Proposition, we also give a stronger non-asymptotic result, where we give a particular threshold T (in terms of n, k, d), such that if ϵ < T then linear probing does better than fine-tuning.
Proof of Theorem 3.2. Combining the fine-tuning bounds: From Theorem 3.1, we have:√ Lood(vtft(t), Bft(t)) ≥ cos θk(R,S ⊥)√
k
min(φ,φ2/∥w⋆∥2) (1 + ∥w⋆∥2)2 − ϵ (A.128)
Here φ2 is the head-error |(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2|. From Corollary A.1 we have cos θk(R,S⊥) > 0 almost surely. From Lemma A.7 we have φ2 > 0 almost surely. So for any δ > 0, there exists some c′δ > 0 such that with probability at least 1− δ:√
Lood(vtft(t), Bft(t)) ≥ c ′ δ − ϵ (A.129)
Linear-probing bound: From Lemma A.8, for every δ > 0, there exists some cδ > 0 such that with probability 1− δ: √
Lood(v∞lp , B0) ≤ cδϵ∥w⋆∥2 (A.130)
Ratio converges to 0 in probability: We simply take the ratio of the OOD errors of linear-probing and fine-tuning that we wrote above. Notice that we have an upper bound for linear-probing and a lower bound for fine-tuning. We get that with probability at least 1− 2δ:√
Lood(v∞lp , B0)√ Lood(vtft, Bft)
≤ O (cδϵ∥w⋆∥2
c′δ − ϵ
) (A.131)
Notice that for every failure probability δ, as ϵ → 0, the RHS goes to 0. Since the LHS is always non-negative, this implies convergence in probability to 0. This implies convergence in probability to 0 for the squared of the LHS as well, which is what we wanted to show.
We can actually show a more precise, quantitative version of Theorem 3.2, which we do below.
Proposition A.1. In the linear overparameterized setting, assuming Gaussian covariates, let ∥w⋆∥2 be a fixed constant. Then for all w⋆, B0, n, d, k, ϵ, if d − n, n ≥ 5k, d − n, n ≥ 10 log 1δ , and if ϵ = ∥B0 −B⋆∥2 is small so that:
ϵ ≤ O ( δ
√ n2(d− n)
kd3 1
(log dδ ) 3
) (A.132)
Then we have for all times t:
Lood(v ∞ lp , B0) < Lood(v t ft, B t ft) (A.133)
Proof. Combining the fine-tuning bounds: From Theorem 3.1, we have:√ Lood(vtft(t), B t ft(t)) ≥ cos θk(R,S ⊥)√
k
min(φ,φ2/∥w⋆∥2) (1 + ∥w⋆∥2)2 − ϵ (A.134)
Here φ2 is the head-error |(v⊤⋆ v⋆)2 − (v⊤0 v⋆)2|. From Corollary A.1, we have with probability at least 1− δ:
cos θk(R,S ⊥) ≥ √ d− n d log 2dδ
(A.135)
For Gaussian initialization, from Lemma A.7, we have with probability at least 1− δ:
φ2 ≥ O(δ(v⊤⋆ v⋆)2) = O(δ(w⊤⋆ w⋆)2) (A.136)
We assumed ∥w⋆∥2 is a constant, so since big-oh ignores constant factors, we omit the ∥w⋆∥2 terms. So we get φ2 = O(δ). Combining everything, we get:√
Lood(vtft, B t ft) ≥ O ( δ√ k √ d− n d log 2dδ ) − ϵ (A.137)
Simplifying the fine-tuning bound: We assumed:
ϵ ≤ O (n(d− n)1/2
k1/2d3/2 δ
(log dδ ) 3/2
) (A.138)
With some algebra, we can show:(n(d− n)1/2 k1/2d3/2
δ
(log dδ ) 3/2
) ≤ ( δ√ k √ d− n d log 2dδ ) (A.139)
This reduces to showing n ≤ d log dδ which is true since we assumed n ≤ d in the overparameterized setting. So this means we have:
ϵ ≤ O ( δ√
k √ d− n d log 2dδ ) (A.140)
This then gives us that for all small ϵ that we consider, we have:√ Lood(vtft, B t ft) ≥ O ( δ√ k √ d− n d log 2dδ ) (A.141)
Linear-probing bound: For linear-probing, from Lemma A.8 we have:√ Lood(v∞lp , B0) ≤ O ( d n log ( d δ )ϵ∥w⋆∥2 ) (A.142)
To simplify presentation, we let ∥w⋆∥2 be a constant, so we have:√ Lood(v∞lp , B0) ≤ O ( d n log ( d δ )ϵ )
(A.143)
Take the ratio: We take the ratio of the OOD errors of linear-probing and fine-tuning that we wrote above. Notice that we have an upper bound for linear-probing and a lower bound for fine-tuning. We get: √
Lood(v∞lp , B0)√ Lood(vtft, B t ft)
≤ O ( ϵ δ
√ kd3
n2(d− n) (log
d δ )3 )
(A.144)
Finer characterization: Lood(v∞lp , B0) < Lood(vtft, Btft) iff the above ratio is of the losses is less than 1. Simple algebra (moving over terms to the correct side) gives us the desired result, that Lood(v ∞ lp , B0) < Lood(v t ft, B t ft) if:
ϵ ≤ O ( δ
√ n2(d− n)
kd3 1
(log dδ ) 3
) (A.145)
Which completes the proof.

heading: A.4 LP VS FT IN THE GAUSSIAN SETTING (ID)

text:
Restatement of Proposition 3.1. Suppose w⋆ = B⊤⋆ v⋆ ̸∈ rowspace(B0), and that fine-tuning converges to a local minimum of its loss, then fine-tuning does better ID: Lid:subspace(v∞ft , B ∞ ft ) < Lid:subspace(v ∞ lp , B0).
Proof. Fine-tuning gets 0 ID loss: It is well known from prior work (Laurent & von Brecht, 2018) that all local minima are global for optimizing two layer linear networks under convex losses, so if fine-tuning converges to a local minimum, it actually converges to a global minimum of the train loss. Since there exists parameters that achieve 0 loss on the training data (namely, B⋆, v⋆), this means fine-tuning gets 0 loss on the training data as well. In noiseless linear regression, 0 loss on the training data implies 0 loss on the span of the training data as well, so:
Lid:subspace(v ∞ ft , B ∞ ft ) = 0 (A.146)
Suffices to show linear-probing gets positive ID loss: So it suffices to show that Lid:subspace(v ∞ lp , B0) > 0. The high level intuition of our proof is that for every subset of k examples of the training data (of size n), there is a unique linear-probing solution that fits these k examples. Since the data is random, the chance that the linear probing solution for one set of k examples agrees with another set of k examples is 0. Since k < n, this means that wlp = B⊤0 v ∞ lp cannot fit all the training examples, which means it gets positive loss. We formalize this argument below.
Recall that we have n > k training examples. For i ≤ n, let Xi denote a matrix of shape (i, d) where the rows are the first i training examples. Xi is a random matrix, because the training examples are random.
Linear probing objective on first i examples: Given a head v, consider the linear probing objective on the first i examples:
Li(v) = ∥XiB⊤0 v −XiB⊤⋆ v⋆∥22 (A.147)
Unique minimizer of Li for i ≥ k: Expanding Li(w), we see that it is a quadratic form with quadratic matrix B0X⊤i XiB ⊤ 0 . We note that since Xi is a matrix with independent standard Gaussian (N(0, 1)) entries. B0 has orthonormal rows, so B0X⊤i is a matrix of shape (k, i) with standard Gaussian entries. So if i ≥ k, then B0X⊤i has rank k almost surely. This means B0X⊤i XiB⊤0 has rank k—since it is positive semi-definite and has full rank, it is in fact positive definite. This means that for i ≥ k, Li(v) is strongly convex, and has a unique minimum given by:
vi = (B0X ⊤ i XiB ⊤ 0 ) −1B0X ⊤ i XiB ⊤ ⋆ v⋆ (A.148)
This can be shown by noting that ∇Li(vi) = 0, and since Li is strongly convex this implies that vi is the unique minimizer of L. Since Li is non-negative with a unique minimizer, any v ̸= vi gives us Li(v) > 0.
vk gets the (k + 1)-th example wrong: Now, we examine vk which is the unique solution that minimizes Lk, the loss on the first k examples. The prediction on the (k + 1)-th example xk+1 is: (B⊤0 vk) ⊤xk+1. The ground truth target for the (k + 1)-th example is (B⊤⋆ v⋆) ⊤xk+1. So the difference (error) is: Ek+1 = [(B ⊤ 0 vk −B⊤⋆ v⋆)⊤xk+1]2 (A.149)
Since w⋆ = B⊤⋆ v⋆ is not in the range of B ⊤ 0 (the rowspace of B0), we have B ⊤ 0 vk − B⊤⋆ v⋆ ̸= 0. Since xk+1 is a unit Gaussian vector, (B⊤0 vk − B⊤⋆ v⋆)⊤xk+1 ̸= 0 almost surely. This means Ek+1 > 0 almost surely.
vn must get some example wrong: Finally, we examine vn. First we note that the linear-probing loss is a strongly convex quadratic, so gradient flow on all n training examples converges to the solution wlp = B⊤0 vn. We now consider two cases.
Case 1, vn = vk: Then wlp = B⊤0 vn gets example xk+1 wrong, which is in the span of the training data, so Lid:subspace(v∞lp , B0) > 0.
Case 2, vn ̸= vk: Then Lk(vn) > 0 since vk is the unique minimizer of Lk. This means that the loss of B⊤0 vn on one of the first k training examples is non-zero, and therefore Lid:subspace(v ∞ lp , B0) > 0.
Either way, Lid:subspace(v∞lp , B0) > 0 almost surely. Since Lid:subspace(v ∞ ft , B ∞ ft ) = 0, we have Lid:subspace(v ∞ ft , B ∞ ft ) < Lid:subspace(v ∞ lp , B0) which completes the proof.

heading: A.5 LP-FT

text:
We start by showing a simple proposition, that if the initial feature extractor is perfect, then linear probing recovers the optimal weights.
Proposition A.2. In the overparameterized linear setting, let R = rowspace(B0). If B0 = B⋆, and cos θk(S,R) > 0, then Lood(v∞lp , B0) = 0 for all t.
Proof. We first show that because cos θk(R,S) > 0, the training loss for linear probing is strongly convex. Recall that the training loss is:
L̂(v,B) = ∥XB⊤v − Y ∥22 (A.150)
Linear probing keeps B fixed as B0 = B⋆ and only tunes v, so we are interested in the Hessian of the loss with respect to v evaluated at v,B⋆:
Hessv L̂(v,B⋆) = 2(B⋆X ⊤)(B⋆X ⊤)⊤ (A.151)
For strong convexity, it suffices to show that the min singular value of the Hessian is bounded away from 0 by a constant. Recall the definition of cos θk(R,S). For some F whose columns form an orthonormal basis for S, we have (since the rows of B⋆ form an orthonormal basis for R):
σk(B⋆F ) = cos θk(R,S) > 0 (A.152)
Note that B⋆F is a k-by-n matrix, so if the k-th singular value is positive it must be full rank. Since the columns of X⊤ span F (since we defined F to be such that the columns of F are an orthonormal basis for S, i.e. the rows of X), this means B⋆X⊤ is rank k. But that means the Hessian (B⋆X⊤)(B⋆X⊤)⊤ is rank k as well. So the linear probing loss is strongly convex.
Since the loss is strongly convex, there is a unique minimizer, and gradient flow converges to that. However, since we are in the well-specified setting, we know the training loss is:
L̂(v,B⋆) = ∥XB⊤⋆ v −XB⊤⋆ v⋆∥22 (A.153)
So v = v⋆ achieves 0 loss and must be the (unique) minimizer. Therefore we have shown that linear probing converges to the unique minimizer v∞lp = v⋆, which attains 0 loss, as desired.
Note that the entire proof works out if B0 = UB⋆ for some rotation matrix U . In that case, the Hessian becomes 2U(B⋆X⊤)(B⋆X⊤)⊤U⊤ which is still rank k, since multiplying by square rotation matrices does not change the rank. In this case, the minimizer of the loss is v = Uv⋆, since (UB⋆) ⊤(Uv⋆) = B ⊤ ⋆ v⋆. So linear probing converges to v ∞ lp = Uv⋆, which achieves 0 loss, as desired.
Restatement of Proposition 3.2. Suppose we have perfect pretrained features B0 = UB⋆ for some rotation U . Let R = rowspace(B0). Under the non-degeneracy conditions cos θk(R,S) ̸= 0, cos θk(R,S ⊥) ̸= 0:
∀t, Lood(Bft(t)⊤vft(t)) > 0, if v0 ∼ N (0, σ2I) is randomly initialized (FT) (A.154) ∀t, Lood(Bft(t)⊤vft(t)) = 0, if v0 is initialized to v∞lp (LP-FT) (A.155)
Proof. We first use Proposition A.2, which in the proof we showed still works if B0 = UB⋆ for some rotation matrix U (which doesn’t have to be identity). We get that v∞lp = Uv⋆. Then we have B⊤0 v ∞ lp = B ⊤ ⋆ v⋆ = w⋆.
We now just show that the gradients with respect to the training loss L̂ at (v∞lp , B0) is 0, so gradient flow does not update the parameters at all.
The training loss is: L̂(v,B) = ∥XB⊤v −XB⊤⋆ v⋆∥22 (A.156)
The derivative with respect to v is:
∂vL̂(v,B) = 2BX ⊤(XB⊤v −XB⊤⋆ v⋆) (A.157)
Then since B⊤0 v ∞ lp = B ⊤ ⋆ v⋆, we have:
∂vL̂(v ∞ lp , B0) = 0 (A.158)
Next, the derivative with respect to B is:
∂BL̂(v,B) = 2v(XB ⊤v −XB⊤⋆ v⋆)⊤X (A.159)
Then since B⊤0 v ∞ lp = B ⊤ ⋆ v⋆, we have:
∂BL̂(v ∞ lp , B0) = 0 (A.160)
So since both the derivatives are 0, we have ∂tvft(t) = 0 and ∂BBft(t) = 0, which means the parameters don’t change at all—at all times t we have vft(t) = Uv⋆ and Bft(t) = UB⋆ which gives us zero OOD loss: Lood(Bft(t)⊤vft(t)) = 0 as desired.

heading: B MORE INFORMATION ON EXPERIMENTS

text: In this Appendix, we include more details on the datasets, pretraining methods, and adaptation methods. We also include the OOD accuracies for fine-tuning and linear-probing if we early stop and choose the learning rate based on OOD data, where we see that linear-probing is still typically better than fine-tuning OOD. Finally, we include results for additional baselines, pretraining models, larger scale datasets, and conclude with a discussion about the effective robustness of LP-FT.

heading: B.1 DATASET AND METHOD DETAILS

text:
We use a diverse range of datasets and pretraining strategies.
• CIFAR-10 → STL: We fine-tune or linear probe on CIFAR-10 (Krizhevsky, 2009) and test on STL (Coates et al., 2011). This is a benchmark used in domain adaptation papers (French et al., 2018). CIFAR-10 and STL share 9 classes, so we follow the common practice of omitting the unshared class in STL (which is the ‘monkey’ class) when reporting accuracies. We use a publicly available MoCo-v2 ResNet-50 checkpoint pretrained on unlabeled examples from ImageNet-1k (Russakovsky et al., 2015), and fine-tune for 20 epochs.
• DomainNet: We use the dataset splits in Peng et al. (2019) which is also used by followup work, e.g., in Prabhu et al. (2021). We use the ‘sketch’ domain as ID, and all other domains (‘real’, ‘clipart’, ‘painting’) as OOD, and in the main paper we report the average accuracies across the OOD domains. In Table 3 we see that the same trends hold for each of the three OOD domains. We use a CLIP (Radford et al., 2021) pretrained ResNet-50 model, and fine-tune for 50 epochs (since this is a smaller dataset).
• Living-17 and Entity-30: We use a publicly available MoCo-v2 ResNet-50 checkpoint pretrained on unlabeled examples from ImageNet-1k (Russakovsky et al., 2015), and finetune for 20 epochs. Note that Living-17 and Entity-30 are subpopulation shifts derived from ImageNet, but the pretraining is done on unlabeled data and does not see any OOD labels, following the pretraining and fine-tuning strategy in Cai et al. (2021). Entity-30 is a relatively large dataset that contains around 140K training examples.
FT 2.23 (0.03) 3.05 (0.02) 1.88 (0.01) 207.6 (12.31) 4.87 (0.15) LP-FT 0.07 (0.00) 0.03 (0.01) 0.11 (0.01) 0.19 (0.03) 0.57 (0.19)
• FMoW Geo-shift: We adapt the version of the dataset from (Koh et al., 2021). We use training data from ‘North America’ to fine-tune or linear probe, and then evaluate on validation data from Africa and Europe. We use a MoCo-TP (Ayush et al., 2020) checkpoint, pretrained on unlabeled FMoW satellite images. We fine-tune for 50 epochs here since the ID training dataset is smaller (around 20K examples).
• CIFAR-10 → CIFAR-10.1 (Recht et al., 2018): We follow the same protocols as CIFAR10 → STL, except we test on CIFAR-10.1.
We note that our results say that the pretraining has to be good (e.g., at least get reasonable accuracy ID) for linear probing to outperform fine-tuning OOD. So, for example, we use a model pretrained on unlabeled satellite images for the satellite image dataset—if we pretrain the model on ImageNet, we expect that fine-tuning might do better. Similarly, for DomainNet we use a CLIP pre-trained model, which is pretrained on the very large WebImageText dataset, and sees a variety of photo and sketch like images. Pretraining on ImageNet alone does not lead to high accuracies on DomainNet (features are not very good), so we do not necessarily expect linear probing to outperform fine-tuning with these lower quality features (for example, see the MoCo ablation in our main paper where we used a worse pretrained model, and fine-tuning did better OOD).
As a sanity check of our implementation, fine-tuning did substantially better than training from scratch on all datasets (both ID and OOD) and matched existing fine-tuning numbers where available (e.g. ResNet50 on CIFAR-10 (Chen et al., 2020b) and Entity-30 (Cai et al., 2021)).
Fine-tuning and linear probing both do substantially better than training from scratch, ID and OOD, across the datasets. For example, on Living-17, training from scratch gets 89.3% ID and 58.2% OOD which is over 5% worse ID and nearly 20% worse OOD, than all the adaptation methods. For reference linear probing gets 96.5% ID and 82.2% OOD, and fine-tuning gets 97.1% ID and 77.8% OOD. This is even though training from scratch was run for 300 epochs, which is 15 times longer than fine-tuning and LP-FT.

heading: B.2 TARGET EARLY STOPPING

text:
In the main paper, one ablation we mention is early stopping each fine-tuning method and choose the best learning rate based on target validation accuracy. As expected, fine-tuning does improve a little, but linear probing (average accuracy: 73.0%) is still better than fine-tuning (average accuracy: 70.1%). Table 4 shows the full results.
FT 1.70 (0.04) 2.60 (0.02) 1.67 (0.01) 159.97 (16.23) 5.62 (0.30) LP-FT 0.04 (0.00) 0.02 (0.00) 0.09 (0.01) 0.18 (0.02) 0.54 (0.17)

heading: B.3 FEATURE CHANGE

text:
We examine how much the features changed for ID and OOD examples in each dataset. Specifically, for each dataset, for each input example in the held out validation set, we computed the Euclidean distance of the ResNet-50 features before and after fine-tuning. We averaged these numbers across the dataset, showing the results for ID validation examples in Table 5, and for OOD examples in Table 8.
The feature distortion theory predicts that the features for ID examples change more than for OOD examples. This bears out in 9 out of 10 cases, that is all cases except for FT on FMoW. To see this, compare each cell in Table 5 with the corresponding cell in Table 8—the former is higher in 9 out of 10 cases.
The feature distortion theory says that this large feature change is caused because the head is randomly initialized—since the head needs to be updated by a large amount, the feature extractor is also updated a lot because the updates are coupled. Our theory predicts that if the head is initialized via linear probing then the feature extractor should change a lot less for both ID and OOD examples. As predicted by the theory, across all the datasets in Table 5 and Table 8, the features change a lot less for LP-FT than for FT. For example, on CIFAR-10, the features change 30× less for LP-FT than for FT.
These results suggest that fine-tuning underperforms OOD, and LP-FT does well ID and OOD, for the reasons predicted by the feature distortion theory.

heading: B.4 ADDITIONAL ARCHITECTURES, FINE-TUNING METHODS

text:
The main contributions of our paper are conceptual understanding and theory. However, to strengthen the empirical investigation we ran two additional models (a CLIP vision transformer and CLIP ResNet-50), as well as three additional fine-tuning heuristics. We focus on the Living-17 dataset because some of these ablations require lots of compute and can take a long time to run on all the datasets.
Architectures and pretraining source: In the main paper, we showed results when initializing with a MoCo-v2 ResNet-50 model pretrained on unlabeled ImageNet examples. Here we examine how the results change when we 1. Use a ResNet-50 model pretrained on CLIP’s WebImageText dataset, and, 2. Use a much larger vision transformer model (ViT-B/16) pretrained on CLIP’s WebImageText dataset—this is the largest publicly available CLIP model at the time of writing. We see that similar findings to our main paper hold—fine-tuning does better than linear probing ID, but does worse than linear probing (‘underperforms’) OOD. Finally, LP-FT does better than both methods ID, and closes most (75%-90%) of the gap OOD.
These results are from early stopping on ID validation data. If we early stop on OOD validation data, LP-FT achieves 87.9±0.4% OOD accuracy, and LP gets 88.3±0.2% OOD accuracy and here there is no statistically significant difference between the two. On the other hand, even if we early stop on OOD validation data, fine-tuning gets 84.4± 0.5% OOD accuracy which is lower.
Fine-tuning heuristics: Transfer learning (initializing with a pretrained model, and then adapting it to a downstream task) is the standard way to build modern ML models, because it improves accuracy and speeds up training. Since this paradigm is so widely used, there are many heuristics people use when training their models (as mentioned in the main paper, LP-FT has sometimes been used as a
heuristic as well, although not in the context of OOD). We showed that LP-FT is one way to do well ID and OOD, but we hope that our theory leads to even better fine-tuning algorithms.
In this section, we compare LP-FT with additional fine-tuning heuristics: using a larger learning rate for the head layer, regularizing the features towards their original values, and side-tuning (Zhang et al., 2020) where we freeze the features but add a side-network.
The intuitions from our theory suggest two other potential ways to improve OOD accuracy: 1. We could use a higher learning rate on the linear layer, so that the linear layer learns quicker and the features do not get as distorted, and 2. We could regularize the weights of the feature extractor towards the pretrained initialization, to prevent feature distortion. These heuristics have been used in prior work on fine-tuning as well, for example method 2 corresponds to L2-SP in (Li et al., 2018).
We run these two approaches on Living-17. For approach (1), we use a 10× higher learning rate for the linear layer, and for approach (2) we regularize the Euclidean distance between the current feature extractor weights (so ignoring the linear head) from the pretrained weights, multiplying by a hyperparameter λ. We grid search over the same learning rates as fine-tuning for both methods, and in addition for (2) we grid search over λ ∈ {1.0, 0.1, 0.01, 0.001, 0.0001}, so this amounts to sweeping over 30 hyperparameters as opposed to just 6 for fine-tuning and LP-FT. For each hyperparameter configuration we run 3 replication runs with different seeds to reduce the estimation variance, and early stop and model select using ID data just like for fine-tuning and LP-FT. Just like for fine-tuning and LP-FT, we use a cosine learning rate decay and train for the same number of epochs. Indeed, we find that both (1) and (2) are able to close part of the OOD gap between fine-tuning and linear-probing. However, LP-FT does better than both methods ID and OOD. The full results are in Table 9.
We also compare with another method, (3) side-tuning (Zhang et al., 2020). Side-tuning freezes the pretrained features g(x) but trains another ‘side’ model s(x), and then outputs v⊤(g(x) + h(x)), where the head v and the parameters of the side model s are tuned. The intuition for trying this is that side-tuning also preserves the pretrained features which likely reduces feature distortion. In the supplementary of Zhang et al. (2020) they use a ResNet-50 for both the original model and the side model in their vision experiments, so we do the same. We sweep over twelve learning rates (3 · 10−5, 1 · 10−4, 3 · 10−4, . . . , 1.0, 3.0, 10.0), with three replication runs with different seeds for each learning rate. Just like for fine-tuning and LP-FT, we use a cosine learning rate decay and train for the same number of epochs, and we early stop and model select using ID validation data. We
checked that the best learning rate was not at the boundary of the grid search. On OOD, side-tuning (81.0%) improves over fine-tuning (77.7%). However, side-tuning doesn’t do as well ID. LP-FT did better ID and OOD. This could be because side-tuning does not get to refine the pretrained features for the ID task—while the side-network is powerful enough to learn good features, it is initialized randomly and effectively trained from scratch, so it might not be able to learn these good features on the limited sized training dataset (around 40K examples). The results are also in Table 9.
We also include results for training from scratch in Table 9—these results are from Santurkar et al. (2020). Note that training from scratch was done for 450 epochs, whereas fine-tuning was done for 20 epochs. As a sanity check, all the fine-tuning methods and linear probing do substantially better than training from scratch, both ID and OOD.

heading: B.5 LARGER SCALE DATASETS

text:
In our original paper we used popular distribution shift datasets like DomainNet, Breeds, CIFAR-10 → STL and the satellite remote sensing dataset FMoW. Here, we see that our findings hold up in larger scale datasets. Specifically, we linear probe or fine-tune on ImageNet (Russakovsky et al., 2015), and evaluate on ImageNetV2 (Recht et al., 2019), ImageNet-R (Hendrycks et al., 2020), ImageNet-A (Hendrycks et al., 2019b), and ImageNet-Sketch (Wang et al., 2019). We begin with a CLIP ViT-B/16 (vision transformer), the largest publicly available CLIP model (Radford et al., 2021), which is much larger than a ResNet-50. This model is pretrained on the WebImageText dataset (Radford et al., 2021).
Recall that our theory says that linear probing does better than fine-tuning when the shift is large. We expect linear probing to do better on ImageNet-R, ImageNet-A, ImageNet-Sketch. We expect fine-tuning to do better on ImageNetV2 because it is collected by “repeating the dataset curation process" (Recht et al., 2019) of ImageNet—this is similar to CIFAR-10 → CIFAR-10.1 in our original paper.
Training details: since the dataset is large (over one million training images), we did not run replication runs. However, we swept over three learning rates for fine-tuning (0.0001, 0.0003, 0.001) and linear probing (0.01, 0.03, 0.1)—as is standard we use larger learning rates for linear probing. Both fine-tuning and linear probing were run for 10 epochs over the ImageNet training data, with batch size 128, and cosine learning rate decay. As in our other experiments, we early stopped the models and selected the best learning rate to maximize in-distribution validation accuracy (on ImageNet). However, we did not find the results to be sensitive to hyperparameter choices.
We find that fine-tuning gets 2% higher accuracy ID than linear probing, but averaged across the four OOD datasets fine-tuning gets 10% lower accuracy OOD. The ID results are in Table 10 and the OOD results are in Table 11. As expected, fine-tuning does better than linear probing ID (ImageNet validation) and on ImageNetV2 which replicates the collection process of ImageNet and is a small
shift. However, fine-tuning does worse than linear probing OOD on ImageNet-R, ImageNet-A, and ImageNet-Sketch.

heading: B.6 DISCUSSION OF EFFECTIVE ROBUSTNESS

text:
LP-FT gets higher OOD accuracy than fine-tuning, but it sometimes gets higher ID accuracy as well. Taori et al. (2020) and Miller et al. (2021) show that OOD accuracy can often be correlated with ID accuracy, and suggest examining the effective robustness: intuitively the extra gain in OOD accuracy than can be predicted from improved ID accuracy alone. Is LP-FT simply better in-distribution, or does it have higher effective robustness as well?
We start out by noting that linear probing clearly has higher effective robustness in most of our datasets. Linear probing does worse than fine-tuning ID so based on the effective robustness framework we would expect it to do worse than fine-tuning OOD as well. However, linear probing does better than fine-tuning OOD and therefore has effective robustness.
The solutions found by LP-FT also appear to have higher effective robustness than fine-tuning, because when they have similar ID accuracy, LP-FT does much better OOD. For a few pieces of evidence:
1. On CIFAR-10 → STL, there is no statistically significant difference between FT and LP-FT on ID, but LP-FT gets 8% higher accuracy OOD in Table 2.
2. If we look at checkpoints earlier in training for CIFAR-10 → STL we can exactly equalize ID accuracy and compare OOD accuracies. In-distribution, LP-FT and FT both get 97.2% accuracy, but OOD, LP-FT (90.2%) is much better than FT (81.8%).
3. Finally, in Figure 3 we plot the OOD accuracy against the ID accuracy for fine-tuning and LP-FT on Living-17. We plot these for three different pretrained models (CLIP ResNet-50, CLIP ViT-B/16, MoCo-V2 ResNet-50). We see that the ID-OOD line for LP-FT is above the line for FT indicating effective robustness.
Note that higher effective robustness does not mean a method is better. For example, a method A can have higher effective robustness B by doing a lot worse in-distribution even when they have the same OOD accuracy. In this case, A is clearly inferior since it does worse ID and same OOD, but has higher effective robustness because of its worse ID accuracy.
We believe the finding that linear probing and LP-FT has higher effective robustness than fine-tuning when the distributon shift is large is particularly interesting because Taori et al. (2020) and Miller et al. (2021) show that it is uncommon for methods to have higher effective robustness. In our case linear probing and LP-FT appear to consistently have higher effective robustness which suggests that with proper transfer learning methods we can get both high in-distribution accuracy and higher effective robustness.

heading: C ADDITIONAL RELATED WORK

text: Theoretical analysis of overparameterized models. Modern deep learning presents an interesting paradigm for theoretical analysis where the number of parameters is much larger than the number of training points. The model class is highly expressive and several solutions obtain zero training loss even in the presence of noise. Such overparameterized models have received a lot of interest recently especially with a focus on understanding “benign overfitting” or the phenomenon where fitting noisy training data to zero loss leads to classifiers that generalize well. By analyzing different linear overparameterized settings Belkin et al. (2019); Hastie et al. (2019); Bartlett et al. (2019); Muthukumar et al. (2020); Mei & Montanari (2019); Bibas et al. (2019) study various statistical properties such as the “double descent curve” in addition to benign overfitting. One important aspect of overparameterized models is that there is no unique minimizer of the training loss. We need some inductive bias which is typically implicit via the optimization procedure. Prior works study the statistical properties of the explicit inductive bias of minimum norm interpolation. In contrast, we study the effect of gradient based optimization from a particular pretrained initialization where we effectively capture the exact implicit inductive bias of gradient based fine tuning.