Journal Title Here DOI HERE Advance Access Publication Date: Day Month Year
Paper

Moore et al.

[$\ast$]Corresponding author.
email:callandra.moore<EMAIL_ADDRESS>
0Year 0Year 0Year

#  _Pyclipse_ , a library for deidentification of free-text clinical notes

Callandra Moore0009-0008-3801-3137  Jonathan Ranisau0000-0002-1178-7510
Walter Nelson0000-0002-5216-7617  Jeremy Petch0000-0003-1614-1046  Alistair
Johnson0000-0002-8735-3014  Child Health Evaluative Sciences, Hospital for
Sick Children, Ontario, Canada  Centre for Data Science and Digital Health,
Hamilton Health Sciences, Ontario, Canada  Department of Statistical Sciences,
University of Toronto, Ontario, Canada  Institute of Health Policy, Management
and Evaluation, University of Toronto, Ontario, Canada  Division of
Cardiology, Department of Medicine, McMaster University, Ontario, Canada
Population Health Research Institute, McMaster University, Ontario, Canada
Dalla Lana School of Public Health, University of Toronto, Ontario, Canada

(2022; 2019; Date; Date; Date)

###### Abstract

Automated deidentification of clinical text data is crucial due to the high
cost of manual deidentification, which has been a barrier to sharing clinical
text and the advancement of clinical natural language processing. However,
creating effective automated deidentification tools faces several challenges,
including issues in reproducibility due to differences in text processing,
evaluation methods, and a lack of consistency across clinical domains and
institutions. To address these challenges, we propose the _pyclipse_
framework, a unified and configurable evaluation procedure to streamline the
comparison of deidentification algorithms. _Pyclipse_ serves as a single
interface for running open-source deidentification algorithms on local
clinical data, allowing for context-specific evaluation. To demonstrate the
utility of _pyclipse_ , we compare six deidentification algorithms across four
public and two private clinical text datasets. We find that algorithm
performance consistently falls short of the results reported in the original
papers, even when evaluated on the same benchmark dataset. These discrepancies
highlight the complexity of accurately assessing and comparing
deidentification algorithms, emphasizing the need for a reproducible,
adjustable, and extensible framework like _pyclipse_. Our framework lays the
foundation for a unified approach to evaluate and improve deidentification
tools, ultimately enhancing patient protection in clinical natural language
processing.

###### keywords:

deidentification, natural language processing, HIPAA, PHI, electronic health
records

##  1 Introduction

The advent of large, open access text corpora and the empirical efficacy of
neural networks have driven advances in model performance in natural language
processing. In healthcare, the increasing volume of electronic health record
(EHR) data from hospitals provides a rich source of information on patient
state, treatment, and outcome in the form of semi-structured and unstructured
text [16, 12]. Barriers to sharing clinical text, however, have stifled the
application of natural language processing in the medical domain. In
particular, clinical text from EHRs cannot be fully leveraged for scientific
research without first minimizing the risk of harm to patients [2].

To use identifiable data for analysis, researchers typically must obtain the
informed consent of individual patients, the approval of an internal review
board, or both. In many jurisdictions these requirements can be waived when
the data are sufficiently de-risked through the process of deidentification,
where patient identifiers are substituted with surrogates or removed entirely.
In the United States, the Health Insurance Portability and Accountability Act
(HIPAA) provides federal protection for protected health information (PHI).
HIPAA permits sharing of non-individually identifiable data, determined either
through “Expert Determination” or via a “Safe Harbor” provision which outlines
the eighteen specific identifiers that must be removed to consider a dataset
“deidentified”. These identifiers include patient names; medical record
numbers; dates; ages over 89 years; any contact information; geographic
locations; and any other identifier, code, or characteristic [6]. Deidentified
datasets are safer to share among multiple research groups which simplifies
complementary analysis, comparisons, and replication [8, 4, 2].

There have been a few shared tasks evaluating EHR deidentification methods, in
particular those hosted in 2006 [22] and 2014 [19] by the Informatics for
Integrating Biology and the Bedside (I2B2) project and in 2016 by the Centers
of Excellence in Genomic Science Neuropsychiatric Genome-Scale and RDoC
Individualized Domains (N-GRID) [18].

These public datasets have been extremely beneficial in providing a consistent
evaluation set for community comparison. Despite the utility of these
benchmark datasets, limitations remain. Performance of existing algorithms
remains difficult to reproduce even on the established benchmark. For
instance, Norgeot et al. (2020), despite using the i2b2 2014 dataset as the
basis and benchmark for their PHIlter deidentification algorithm, first
preprocess the provided gold-standard annotations to remove entities not
required by HIPAA’s Safe Harbor provision [16], complicating reproduction of
their results (see https://github.com/BCHSI/philter-ucsf/issues/11).

Although privately held deidentified clinical corpora range in the millions of
notes, the largest benchmark dataset contains less than 2,000 notes. These
datasets contain only synthetic PHI, as publicly releasing real PHI would be a
legal violation. Generation of synthetic PHI is a challenging endeavour on its
own, and even with great care will result in a distribution shift. Finally,
current benchmark datasets cover a subset of clinical note domains (discharge
summaries, nursing notes, pathology reports), and omit large swaths of other
note types (primary care notes, radiology reports, consult notes, specialist
notes, and so on). These other note types may challenge generalizability of
proposed models.

We identified the need for a consistent framework which solved the above
limitations. Our proposed framework simplifies the comparison of performance
of deidentification algorithms on a single dataset with a consistent
evaluation procedure and solves the above limitations. We provide adapters to
run existing open-source deidentification algorithms and compare their
performance. Most importantly, our framework allows application and comparison
of these algorithms on local clinical data, allowing context-specific
evaluation most relevant to the end user.

This research was reviewed and approved by the Research Ethics Board of the
Hospital for Sick Children and the Hamilton Integrated Research Ethics Board.

##  2 Methods

We created _pyclipse_ , a Python-based package for evaluating deidentification
algorithms on public and private datasets. The goal of _pyclipse_ is two-fold.
First, it provides a consistent format for datasets and utilities to map to
this dataset. This simplifies evaluation of algorithms across the publicly
available benchmark datasets, and ensures similar processing occurs for
privately held datasets. Second, _pyclipse_ provides a structure for
evaluating algorithms on these datasets, as well as wrappers for the currently
available open-source algorithms. _Pyclipse_ is open source and available
under a permissive license https://github.com/kind-lab/pyclipse.

_Pyclipse_ contains a number of utilities common in the evaluation of
deidentification algorithms:

  * •

Standardized dataset format using parquet.

  * •

Method to map PHI entity types from different annotation styles to a common
set (e.g., “medicalrecordnumber” to “ID”). This method can be customized by
the user.

  * •

A set of Python wrappers for the deidentification algorithms tested. These
wrappers enable the usage of algorithms from a variety of languages (Python,
Java, and Perl) with other utilities in _pyclipse_ and may serve as examples
for the evaluation of future deidentification algorithms.

  * •

Evaluation framework which can be applied to any combination of
deidentification algorithm and dataset. Evaluation can be easily configured to
accomodate different tokenizers and other parameters. This includes multiple
methods to merge annotations across algorithms.

  * •

Mechanism to scrub PHI from documents using predicted annotations.

  * •

Tool to visualize the false positives, false negatives, and true positives for
a predicted set of annotations versus the gold standard.

  * •

Utility to save token-level token indices and annotations independent of text
to enable the deletion of all documents and PHI but retain the ability to run
evaluations and ensure replicability.

These utilities contribute to a standardized and replicable evaluation
process, facilitate the comparison of different algorithms and datasets, and
provide a clear pathway and API for adapting future algorithms.

###  2.1 Datasets available

We collected five datasets of free-text notes written during routine clinical
practice and converted existing publicly available datasets into our standard
format. Four of these datasets are publicly available after the respective
data use agreement is signed. Due to restrictions on the distribution of data,
we cannot redistribute reformatted data without express permission. Instead,
we provide clear instructions and code for transforming datasets into our
format.

  * •

i2b2 2006 Corpus: 889 deidentified discharge summaries shared as part of the
2006 i2b2 Challenge. Includes challenge annotations, training and test sets,
and ground truth [22].

  * •

i2b2 2014 Corpus: 1,304 medical records for 296 patients, shared as part of
the 2014 i2b2 Challenge [20].

  * •

PhysioNet Corpus version 2: 2,434 nursing notes collected from patients
admitted to intensive care units at the Beth Israel Deaconess Medical Center,
Boston, Massachusetts, USA [15]. Gold-standard annotations are from an
improved set released by Google [7].

  * •

OpenDeID Corpus: 2,100 pathology reports from 1,833 cancer patients from four
urban Australian hospitals [10].

  * •

RR-SK: 1,083 radiology reports collected from the Hospital for Sick Children
(HSC) in Toronto, Ontario, Canada. This corpus is not currently open-source.

  * •

RR-HHS: 50 radiology reports collected from Hamilton Health Sciences (HHS) in
Hamilton, Ontario, Canada. This corpus is not currenty open-source.

Where specified, we used the author-defined test set for evaluation. For the
RR-HHS dataset, the test set is composed of all fifty currently annotated
notes. Where no test set is available (e.g., the newly collected RR-SK
dataset), we create a random subsample and publish these identifiers to
establish a common test set. These datasets have all been annotated with a set
of gold-standard annotations against which they can be evaluated. However, the
annotation strictness differs in a few key ways between the corpi, namely
whether lone years, ages less than 90, and professions are labeled. These
differences are detailed in Table 3. Summary characteristics of the datasets
are outlined in Table 1. As shown in this table, the types and distributions
of annotations associated with each dataset vary; however, all labels have
been mapped to one of name, profession, age, id, date, location, or contact to
enable comparisons across datasets.

Table 1: Breakdown of protected health information types and subtypes in the five datasets under evaluation. Values in parentheses are the proportion of that entity type to the total PHI tokens.  PHI type | i2b2 2014 | i2b2 2006 | PhysioNet v2 | OpenDeID | RR-SK | RR-HHS
---|---|---|---|---|---|---
[gray]0.9 name | 5559 (0.18) | 2925 (0.24) | 228 (0.35) | 8221 (0.25) | 790 (0.21) | 1143 (0.35)
name | - | - | - | - | 789 | 1143
doctor | 3654 | 2410 | - | 5803 | - | -
patient | 1813 | 515 | - | 2418 | - | -
username | 92 | - | - | - | - | -
hcpname | - | - | 138 | - | - | -
relativeproxyname | - | - | 68 | - | - | -
ptname | - | - | 20 | - | - | -
ptnameinitial | - | - | 2 | - | - | -
misc | - | - | - | - | 1 | -
[gray]0.9 profession | 345 (0.01) | - | - | - | 3 (0.0002) | 0 (0.00)
[gray]0.9 location | 3025 (0.10) | 1921 (0.16) | 85 (0.13) | 7171 (0.22) | 130 (0.03) | 206 (0.06)
location | - | 242 | 85 | - | - | -
loc | - | - | - | - | 41 | -
department | - | - | - | 2704 | - | 206
hospital | 1604 | 1679 | - | 866 | - | -
organization | 154 | - | - | 1 | - | -
org | - | - | - | - | 89 | -
street | 416 | - | - | 1944 | - | -
state | 206 | - | - | 496 | - | -
city | 347 | - | - | 640 | - | -
country | 130 | - | - | 2 | - | -
zip | 148 | - | - | 504 | - | -
location-other | 20 | - | - | 14 | - | -
[gray]0.9 age | 813 (0.03) | 3 (0.0002) | - | 59 (0.001) | 268 (0.07) | 69 (0.02)
[gray]0.9 date | 19701 (0.62) | 5195 (0.43) | 293 (0.45) | 12778 (0.39) | 2551 (0.67) | 1175 (0.37)
date | 19701 | 5195 | 286 | 12778 | 2511 | 1100
dateyear | - | - | 7 | - | - | -
time | - | - | - | - | 40 | 75
[gray]0.9 id | 1592 (0.05) | 1714 (0.14) | 2 (0.003) | 4462 (0.14) | 16 (0.004) | 704 (0.21)
device | 14 | - | - | - | - | -
idnum | 560 | - | - | 2371 | 16 | 704
medicalrecord | 1018 | - | - | 2091 | - | -
id | - | 1714 | - | - | - | -
other | - | - | 2 | - | - | -
[gray]0.9 contact | 662 (0.02) | 245 (0.02) | 50 (0.08) | 1 (0.0000) | 30 (0.008) | 0 (0.00)
email | 5 | - | - | - | - | -
fax | 12 | - | - | - | - | -
phone | 645 | 245 | 50 | 1 | - | -
contact | - | - | - | - | 30 | -
phi total | 31697 | 12003 | 658 | 32692 | 3788 | 3297
total tokens | 435859 | 184731 | 103078 | 544877 | 154491 | 17969
total documents | 514 | 701 | 502 | 702 | 432 | 50

###  2.2 Dataset format

We adopted parquet, an open source columnar based binary format used for
efficient storage of large datasets [13]. In the _pyclipse_ format, the data
is stored in three parquet datasets: a dataset of the document text, a dataset
of annotations partitioned by algorithm, and an optional dataset of
gazetteers. _Pyclipse_ contains utilities to convert data into this format
from various standoff formats, including from individual text files and
eXtended Markup Language (XML) formats used by the i2b2 datasets [22, 20].

Often, annotation methods require the use of gazetteers to form a customizable
dictionary or block list for annotation. Though none of these datasets come
with gazetteers, they were added for the i2b2 2014, i2b2 2006, and OpenDeID
corpi via inspection of the corpus text and the annotation files for the
patients’ first and last names and medical record number.

###  2.3 Algorithms

We implemented wrappers for five openly available deidentification algorithms:
Philter-UCSF [16], TiDE [4], PyDeID [9], PhysioNet-deid [15], and Transformer-
DeID [14]. These algorithms adopt various approaches to deidentification
including the use of supervised machine learning (ML) with labeled training
data, rule-based approaches, and dictionaries of known entities. A comparison
of these algorithms is provided in Table 2. Similar to the datasets described
above, each deidentification algorithm differs slightly in which entities are
considered protected, including the annotation of professions, ages less than
90, non-patient names, large geographic locations such as country, lone years,
and organizations. These differences are highlighted in Table 3. We harmonize
entity types output by each algorithm for consistency.

Table 2: Information for each deidentification algorithm. Dataset | Repository | Citation | Method | Gazetteers Used | Source Dataset
---|---|---|---|---|---
Transformer-DeID
DistilBERT
RoBERTa |  https://github.com/kind-lab/transformer-deid/ | [14] | ML | No | i2b2 2014
Philter |  https://github.com/BCHSI/philter-ucsf | (16) | Rule-based and dictionaries | No | i2b2 2014
PyDeID |  https://github.com/mit-lcp/pydeid | [9] | Rule-based and dictionaries | No | Beth Israel Free Text Notes
TiDE |  https://github.com/susom/tide |  datta2020 | ML, rule-based, and dictionaries | Yes | MTSamples Laparoscopic Gastric Bypass Consult (augmented)
PhysioNet |  https://www.physionet.org/content/deid/1.1/ | [15] | Rule-based and dictionaries | No | PhysioNet
Table 3: Discrepancies between entities considered protected by each deidentification algorithm and dataset. |  |  profession? |  ages $<$ 90? |  non-patient names? |  large-granularity geographic locations? |  year? |  organization?
---|---|---|---|---|---|---|---
|  HIPAA Safe Harbor |  |  |  |  |  |
6* algorithm |  Transformer-DeID |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
|  Philter |  |  |  ✓ |  |  |
|  PyDeID |  |  ✓ |  ✓ |  ✓ |  |  ✓
|  TiDE |  |  |  ✓ |  ✓ |  |
|  PhysioNet |  |  |  ✓ |  |  ✓ |  ✓
6* dataset |  i2b2 2014 |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
|  i2b2 2006 |  |  |  ✓ |  |  |  ✓
|  PhysioNet |  |  |  ✓ |  |  |  ✓
|  OpenDeID |  |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
|  RR-SK |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
|  RR-HHS |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓

###  2.4 Evaluation

Our evaluation pipeline is composed of three phases. First, tokenization is
applied to separate the text into individual tokens which will form the basis
of later comparisons. Many named entity recognition (NER) datasets are
distributed with individual words separated, e.g. CoNLL [21]. As our data
format stores the raw text, tokenization becomes an important component of the
evaluation pipeline. By default, tokenization is done with the
WordPunctTokenizer in the Python Natural Language ToolKit (NLTK) module [3].
This tokenizer separates tokens on whitespace and punctuation. As evaluation
is sensitive to the type of tokenizer used, we allow for the configuration and
comparison of different tokenizers. Second, an entity mapper is used to allow
for various evaluation scenarios. For example, the HIPAA-Strict evaluation
scenario only evaluates performance on the exact entities defined in the HIPAA
Safe Harbor provision, i.e. it does not evaluate professions, doctor names,
and so on. Alternatively, binary evaluation simplifies all entities into
either a PHI or non-PHI category. Finally, measures of model performance are
calculated using the final labels. These include precision, recall, and
F1-scores.

###  2.5 Experiments

Using the established framework of _pyclipse_ , we evaluated all algorithms on
the set of benchmark datasets to establish reference performance measures.
Each algorithm was applied to each dataset, and the resultant annotations were
stored. These annotations were converted to a binary evaluation from
individual entities (i.e. from name, date and so on to PHI vs. non-PHI) to
enhance comparability of the algorithms. Text was tokenized using the default
NLTK tokenizer.

In addition to the binary evaluation, we perform a separate analysis focusing
on recall of the “name” entity. PHI covered by HIPAA’s Privacy Rule differ in
severity, with the most severe being those entities which would allow for
reidentification of patients absent any organizational access, such as name
[12]. Further, this entity type is the most consistently annotated across all
corpi and models.

Finally, we compare the time taken to run each algorithm on fixed hardware
using CPU based inference.

##  3 Results

Table 4 shows the F1-score of the six deidentification algorithms over the six
datasets examined, evaluated token-wise after binarizing labels to PHI or non-
PHI. In this case, a predicted label for a protected entity is considered
correct if the model identifies it as PHI, regardless of specific PHI subtype
identified by the algorithm.

No model-dataset combination achieved an F1-score greater than 0.95. Notably,
none of the algorithms outperformed the state-of-the-art F1-score of 0.977
achieved during the i2b2 2014 deidentification challenge [19]. According to
the F1-score, the Transformer-DeID RoBERTa model is the best performing
algorithm for all datasets with the exception of the RR-SK corpus, on which it
was slightly outperformed by TiDE, PhysioNet, and DistilBERT. The best F1
performance (0.924) was achieved by the Transformer-DeID RoBERTa model on the
i2b2 2014 dataset, which is complementary to its training dataset.

Table 4: F1-scores for each deidentification algorithm over each dataset for all PHI types. Performance is calculated token-wise using binary PHI or non-PHI labels. | i2b2 2014 | i2b2 2006 | PhysioNet v2 | OpenDeID | RR-SK | RR-HHS
---|---|---|---|---|---|---
DistilBERT | 0.905 | 0.710 | 0.461 | 0.699 | 0.790 | 0.721
RoBERTa | 0.924 | 0.743 | 0.625 | 0.786 | 0.789 | 0.823
PHIlter | 0.854 | 0.681 | 0.216 | 0.725 | 0.728 | 0.777
PyDeID | 0.788 | 0.691 | 0.314 | 0.720 | 0.698 | 0.805
TiDE | 0.757 | 0.600 | - | 0.388 | 0.808 | -
PhysioNet-DeID | 0.704 | 0.647 | 0.811 | 0.621 | 0.798 | 0.582

The PyDeID De-Identification algorithm had the highest recall on only name PHI
for most datasets. The Transformer-DeID RoBERTa model outperformed PyDeID on
the i2b2 2006 dataset and the PhysioNet De-Identification algorithm tied with
PyDeID on the PhysioNet dataset.

Table 5: Recall for each deidentification algorithm over each dataset for name labels only. | i2b2 2014 | i2b2 2006 | PhysioNet v2 | OpenDeID | RR-SK | RR-HHS
---|---|---|---|---|---|---
DistilBERT | 0.689 | 0.471 | 0.303 | 0.620 | 0.157 | 0.451
RoBERTa | 0.722 | 0.625 | 0.386 | 0.817 | 0.142 | 0.631
PHIlter | 0.902 | 0.478 | 0.675 | 0.765 | 0.558 | 0.742
PyDeID | 0.940 | 0.472 | 0.969 | 0.856 | 0.565 | 0.933
TiDE | 0.702 | 0.343 | - | 0.324 | 0.539 | -
PhysioNet-DeID | 0.812 | 0.388 | 0.969 | 0.700 | 0.496 | 0.679
Table 6: Number of false negatives for name PHI types per 1000 tokens. | i2b2 2014 | i2b2 2006 | PhysioNet v2 | OpenDeID | RR-SK | RR-HHS
---|---|---|---|---|---|---
DistilBERT | 3.97 | 8.37 | 1.54 | 5.74 | 4.31 | 34.89
RoBERTa | 3.55 | 5.94 | 2.83 | 2.77 | 4.39 | 23.48
Philter | 1.25 | 8.27 | 0.72 | 3.54 | 2.26 | 16.42
PyDeID | 0.77 | 8.36 | 0.07 | 2.17 | 2.23 | 4.29
TiDE | 3.80 | 10.40 | - | 10.20 | 2.36 | -
PhysioNet-DeID | 2.40 | 9.69 | 0.07 | 4.53 | 2.58 | 20.42
Table 7: F1-score and recall for combined RoBERTa and PyDeID algorithms using a recall-maximizing merge strategy.  | F1-score | recall
---|---|---
i2b2 2014 | 0.820 | 0.988
i2b2 2006 | 0.751 | 0.910
PhysioNet-DeID | 0.310 | 0.983
OpenDeID | 0.770 | 0.889
RR-SK | 0.702 | 0.884
RR-HHS | 0.867 | 0.919

We also report the number of false negatives per 1000 tokens for name-entities
(Table 6), which is approximately inversely proportional to recall (Table 5).

Next, we report the F1-score and recall when combining a machine learning-
(RoBERTa) and rule-based (PyDeID) tool in Table 7. These annotations were
merged to maximize the recall (and thus protection of patient privacy) for all
datasets; i.e., if either algorithm marked a token as PHI, the merged set also
labelled that token as PHI.

##  4 Discussion

Enquiries into public views on the use of patient data for research broadly
suggest that there is a willingness to share data where it is for the common
good. This is even true of free-text data contained in EHRs so long as they
are fully deidentified [5]. High performance algorithms for deidentification
of free-text clinical notes is a key step toward conducting research which
maximizes public benefit while minimizing the risk of harm to an individual.
Here we present a software library, _pyclipse_ , which enables reproducible
comparison of deidentification algorithms. The configurable evaluation enables
researchers to compare different evaluation approaches and customizable
annotation filters. Moreover, the framework allows integration of private
datasets, enabling rapid evaluation of these open-source deidentification
tools against local clinical data.

_Pyclipse_ provides a consistent interface to standard deidentification
benchmark datasets including i2b2-2006, i2b2-2014, and OpenDeID. Although
these benchmark datasets are exceedingly useful to the broader community, the
tagged entities were synthetically generated to enable sharing of the dataset
without violating regulatory statues such as HIPAA. Creating accurate
synthetic data is a challenging task in itself. Earlier efforts such as the
i2b2 2006 dataset replaced entities with intentionally adversarial entities to
challenge existing systems, e.g. first and last names were replaced with
unrealistic words such as “Bell Nexbeathefarst” and “Linemase D. Jesc.”
Although the later datasets adopted a more realistic surrogate PHI generation
approach, the use of synthetic PHI remains a potential source of error in
estimating the generalization error of models. Conversely, The two radiology
reports datasets evaluated in this work (RR-HHS and RR-SK) contain real PHI.
While this may provide a better evaluation of algorithm performance, they do
so within a very specific domain (radiology reports) which may not generalize
to other note types. Ultimately evaluation on local data is necessary, which
motivated the utilities in _pyclipse_ which support mapping data into a common
format for evaluation.

Five open-source deidentification algorithms were evaluated here: PyDeid,
TiDE, Philter, Physionet-DeID, and Transformer-DeID. Overall, PydeID obtained
the highest recall both when evaluated on all PHI types and on PHI labeled
“name” on most corpi examined. Careful attention must be paid to the
variability in annotated entities when interpreting the results highlighted in
1. For example, the i2b2-2014 corpus contains entities for all ages, rather
than just those over 89, but the PhysioNet-DeID tool only annotates ages over
89. We evaluated the models on the name entity only to mitigate this factor,
and found Pydeid still had the highest recall for most datasets. To provide an
interpretable measure of model performance, we report the number of false
negatives per 1000 tokens [9]. As PyDeID had the highest recall, it also has
the lowest FN/1000 of 0.77 as seen in Table 6, indicating that for every 1000
tokens processed one name token is missed. We believe this measure will allow
non-experts to better interpret the practical performance of deidentification
algorithms and inform decisions balancing the risk of patient harm with the
benefit of improving care. A notable exception is the i2b2-2006 corpus. As
mentioned earlier, this corpus has intentionally unrealistic entities which
are particularly challenging for rule-based approaches. All models had
substantially lower recall on the name category of i2b2-2006, whereas the
neural network based model (RoBERTa) had reasonable performance. Recent work
has highlighted the potential disparate impact of rule-based deidentification
on uncommon names which are occur in underrepresented groups [23]. When
annotations from PyDeID (rule-based) and RoBERTa (neural network-based)
approaches are combined (Table 7), recall improves relative to that achieved
by PyDeID alone for all datasets, indicating improved protection for patient
privacy. Our comparison highlights the complementary nature of rule-based and
neural-based approaches, which remains a promising avenue for future work
using clinical text [17].

For all of the algorithms, we obtain worse results on all datasets than those
reported by the original paper. The reasons for these differences in
performance are variable and differ across datasets and algorithms. For
Philter, [16] modify the gold-standard annotations to exclude years in
isolation, professions, country names, ages less than 90, and hospital
abbreviations whereas this evaluation does not, potentially accounting for
Philter’s decreased performance. For PhysioNet-DeID, the gold-standard
annotations used in this work are sourced from an improved set published by
[7] rather than [15] used in the original algorithm development and
evaluation.

Another potential source of discrepancy is the method of tokenization and
evaluation. In this paper, we report metrics calculated at the token level
rather than the entity level. Entity-based evaluation requires that the
predicted annotation includes the entirety of a PHI tag whereas token-level
evaluation is only concerned that all parts are identified rather than being
identified together stubbs2015automated. Which method to use depends on the
goals of the annotator. Entity-based evaluation is standard for named-entity
recognition where capturing an entire entity is prioritized. However, for the
purposes of deidentification, whether the tokens of a PHI string are labelled
together is less relevant for protecting patient privacy than all parts being
labelled. Similarly, the tokenizer itself can have significant impacts on
evaluation performance, which has historically been underappreciated.

A major goal of the construction of deidentification algorithms is to be able
to apply them across institutions, specialties, and contexts. The results
presented here indicate that much work remains to enable this sort of
algorithmic generalization. Take, for instance, the model and dataset with the
highest F1-score performance: the RoBERTa model on the i2b2 2014 dataset,
which achieved an F1-score of $0.92$. On all other datasets, the RoBERTa
model’s F1-score did not exceed 0.8, making it clearly currently insufficient
for generalization. In particular, RoBERTa (and the other Transformer-DeID
models) performed extremely poorly on name-only recall for both the PhysioNet
and RR-SK corpi, potentially because in the i2b2 2014 training dataset, most
names occur at the top of the document near other PHI such as medical record
number, whereas in the RR-SK and PhysioNet datasets, names appear in a less
structured and less consistent manner.

To demonstrate the utility of _pyclipse_ , we evaluated the algorithms on two
privately held datasets: RR-SK and RR-HHS (Table 4). The two algorithms with
the highest F1-score on the RR-SK dataset, PhysioNet and DistilBERT (excluding
TiDE for comparison), achieved the lowest F1-score on the RR-HHS dataset. This
variation in performance highlights the need for local evaluation datasets
targeted at the text and clinical domain of interest. Interestingly, this
discrepancy is not strong in the comparison of name-only recall for the
datasets in Tables 5 and 6, indicating that generalizability may differ
between entity types.

This work has a number of important limitations. Firstly, we chose not to
evaluate deidentification algorithms which explicitly require customization
and fine-tuning using a local dataset such as MIST [1]. Our goal with pyclipse
was to provide a rapid interface to compare existing deidentification
approaches, and the custom nature of these approaches prohibit a general
comparison. We further elected to only include algorithms which were open
source, precluding a number of top performing algorithms submitted to the i2b2
2014 challenge [19, 11], as well as proprietary services offered by cloud
providers. Secondly, we were limited in the clinical text available for
evaluation due both to usage restrictions and the paucity of existing
annotated text. Though we have made an effort to include a range of note types
(discharge summaries, nursing notes, pathology reports, and radiology
reports), deidentification research is still limited by the dearth of
annotated text data containing real or surrogate PHI. For instance, the 2016
N-GRID challenge found decreased performance in many established
deidentification approaches due to the data shift toward psychiatric records
[18]. The local data evaluation only included notes from a specific clinical
domain (radiology) had a low number of samples relative to publicly available
datasets, reducing precision in the performance estimates. Including broader
note types such as psychiatric records would enhance the inferences possible
from _pyclipse_.

Our study has a number of strengths. We have containerized a number of open-
source deidentification approaches, enabling rapid deployment with minimal
setup required. Our transparent evaluation pipeline allows a consistent
assessment of the different approaches, and we have provided an extensive
comparison of five open-source algorithms across six datasets. Finally, our
modular design allows extension of _pyclipse_ to additional algorithms and
local datasets.

##  5 Conclusion

A major impediment to deidentification research is the tension between
protecting patient privacy by controlling access to sensitive patient data
while enabling shared discovery across the research community. Given these
constraints, we created _pyclipse_ , a Python library which enables uniform
evaluation of multiple algorithms over public and local datasets. We found
algorithm performance was consistently lower than the results reported by the
original papers, even on the same benchmark dataset. These differences may be
attributed to variability in evaluation protocols, annotation schemes, and
technical implementation. Our work highlights the complexity and challenge of
accurately assessing and comparing deidentification algorithms, hence
demonstrating the necessity and utility of a reproducible, adjustable and
extensible framework such as _pyclipse_. Our work provides a stepping stone
towards a unified approach in evaluating and refining deidentification tools,
facilitating the protection of patient data.

## References

  * [1] John Aberdeen, Samuel Bayer, Reyyan Yeniterzi, Ben Wellner, Cheryl Clark, David Hanauer, Bradley Malin, and Lynette Hirschman.  The MITRE Identification Scrubber Toolkit: design, training, and assessment.  International Journal of Medical Informatics, 79:849–59, 12 2010.
  * [2] Abdullah Ahmed, Adeel Abbasi, and Carsten Eickhoff.  Benchmarking modern named entity recognition techniques for free-text health record deidentification.  In AIMA Joint Summits on Translational Science, pages 102–111, 2021.
  * [3] Steven Bird, Edward Loper, and Ewan Klein.  Natural Language Processing with Python.  O’Reilly Media Inc., 2009.
  * [4] Somalee Datta, Jose Posada, Garrick Olson, Wencheng, Ciaran O’Reilly, Deepa Balraj, Joe Mesterhazy, Joe Pallas, Priyamvada Desai, and Nigam H. Shah.  A new paradigm for accelerating clinical data science at Stanford Medicine.  Computing Research Repository abs/2003.10534, 2020.
  * [5] Elizabeth Ford, Malcolm Oswald, Lamiece Hassan, Kyle Bozentko, Goran Nenadic, and Jackie Cassell.  Should free-text data in electronic medical records be shared for research? a citizens’ jury study in the UK.  Journal of Medical Ethics, 46:367–377, 2020.
  * [6] Health Insurance Portability and Accountability Act, 1996.  Public Law 104-191.
  * [7] Tzvika Hartman, Michael D Howell, Jeff Dean, Shlomo Hoory, Ronit Slyper, Itay Laish, Oren Gilon, Danny Vainstein, Greg Corrado, Katherine Chou, et al.  Customization scenarios for de-identification of clinical notes.  BMC medical informatics and decision making, 20(1):1–9, 2020.
  * [8] Aron Henriksson, Hercules Dalianis, and Stewart Kowalski.  Generating features for named entity recognition by learning prototypes in semantic space: The case of de-identifying health records.  In 2014 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 450–457, 2014.
  * [9] Alistair E. W. Johnson, Tom J. Pollard, Nathaniel R. Greenbaum, Matthew P. Lungren, Chih ying Deng, Yifan Peng, Zhiyong Lu, Roger G. Mark, Seth J. Berkowitz, and Steven Horng.  MIMIC-CXR-JPG, a large publicly available database of labeled chest radiographs, 2019.
  * [10] Jitendra Jonnagaddala, Aipeng Chen, Sean Batongbacal, and Chandini Nekkantti.  The OpenDeID corpus for patient de-identification.  Sci Rep, 11(19973), 2021.
  * [11] Hee-Jin Lee, Yonghui Wu, Yaoyun Zhang, Jun Xu, Hua Xu, and Kirk Roberts.  A hybrid approach to automatic de-identification of psychiatric notes.  Journal of Biomedical Informatics, 75:S19–S27, 2017.  Supplement: A Natural Language Processing Challenge for Clinical Records: Research Domains Criteria (RDoC) for Psychiatry.
  * [12] Jeanmarie Mayer, Shuying Shen, Brett R. South, Stephane Meystre, F. Jeff Friedlin, William R. Ray, and Matthew Samore.  Inductive creation of an annotation schema and a reference standard for de-identification of VA electronic clinical notes.  In AIMA Annual Symposium Proceedings, pages 416–420, 2009.
  * [13] Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, and Theo Vassilakis.  Dremel: Interactive analysis of web-scale datasets.  In Proc. of the 36th Int’l Conf on Very Large Data Bases, pages 330–339, 2010.
  * [14] Callandra Moore, Lucas Bulgarelli, Tom Pollard, and Alistair Johnson.  Transformer-deid: Deidentification of free-text clinical notes with transformers, 2023.
  * [15] Ishna Neamatullah, Margaret M Douglass, Li-wei H Lehman, Andrew Reisner, Mauricio Villarroel, William J Long, Peter Szolovits, George B Moody, Roger G Mark, and Gari D Clifford.  Automated de-identification of free-text medical records.  BMC Medical Informatics and Decision Making, 8:32, 2008.
  * [16] Beau Norgeot, Kathleen Muenzen, Thomas A. Peterson, Xuancheng Fan, Benjamin S. Glicksberg, Gundolf Schenk, Eugenia Rutenberg, Boris Oskotsky, Marina Sirota, Jinoos Yazdany, Gabriela Schmajuk, Dana Ludwig, Theodore Goldstein, and Atul J. Butte.  Protected health information filter (Philter): accurately and securely de-identifying free-text clinical notes.  Nature Partner Journals Digital Medicine, 3(57), 2020.
  * [17] Amber Stubbs, Michele Filannino, Ergin Soysal, Samuel Henry, and Özlem Uzuner.  Cohort selection for clinical trials: n2c2 2018 shared task track 1.  Journal of the American Medical Informatics Association, 26:1163–1171, 11 2019.
  * [18] Amber Stubbs, Michele Filannino, and Özlem Uzuner.  De-identification of psychiatric intake records: Overview of 2016 cegs n-grid shared tasks track 1.  Journal of Biomedical Informatics, 75S:S4–S18, 2017.
  * [19] Amber Stubbs, Christopher Kotfila, and Özlem Uzuner.  Automated systems for the de-identification of longitudinal clinical narratives: Overview of 2014 i2b2/UTHealth shared task track 1.  Journal of Biomedical Informatics, 58:S11–S19, 2015.
  * [20] Amber Stubbs and Özlem Uzuner.  Annotating longitudinal clinical narratives for de-identification: The 2014 i2b2/UTHealth corpus.  Journal of Biomedical Informatics, 58:S20–S29, 2015.
  * [21] Erik F. Tjong Kim Sang and Fien De Meulder.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003, pages 142–147, 2003.
  * [22] Ozlem Uzuner, Yuan Luo, and Peter Szolovits.  Evaluating the state-of-the-art in automatic de-identification.  Journal of the American Medical Informatics Association, 14(5):550–63, 2007.
  * [23] Yuxin Xiao, Shulammite Lim, Tom Joseph Pollard, and Marzyeh Ghassemi.  In the name of fairness: Assessing the bias in clinical record de-identification.  In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’23, page 123–137, New York, NY, USA, 2023. Association for Computing Machinery.


$a=\tilde{U}^{*}u_{i}$ and $b=\tilde{U}^{*}u_{j}$. They are uniformly random
orthogonal unit vectors, not necessarily independent. Now note that

$\displaystyle(\Sigma_{trn}^{-1}(K^{T}K)\Sigma_{trn}^{-1})_{ij}$
$\displaystyle=u_{i}^{T}(\tilde{U}\tilde{\Sigma}\tilde{\Sigma}^{*}\tilde{U}^{*})^{\dagger}u_{j}$
$\displaystyle=u_{i}^{T}\tilde{U}(\tilde{\Sigma}\tilde{\Sigma}^{*})^{\dagger}\tilde{U}^{*}u_{j}$
$\displaystyle=a^{T}(\tilde{\Sigma}\tilde{\Sigma}^{*})^{\dagger}b$
$\displaystyle=\sum_{k=1}^{d}\frac{1}{\tilde{\sigma}_{k}^{2}}a_{k}b_{k}.$

So, we get that

$\displaystyle\mathbb{E}[((\Sigma_{trn}^{-1}(K^{T}K)\Sigma_{trn}^{-1})_{ij})^{2}]$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{d}\sum_{l=1}^{d}\frac{1}{\tilde{\sigma}_{k}^{2}\tilde{\sigma}_{l}^{2}}a_{k}b_{k}a_{l}b_{l}\right]$
$\displaystyle=\left(\frac{c^{2}}{(1-c)^{2}}+o(1)\right)\mathbb{E}\left[\left(\sum_{k=1}^{d}a_{k}b_{k}\right)^{2}\right]$
$\displaystyle\ \ \
+\left(\frac{c^{2}}{(1-c)^{3}}-\frac{c^{2}}{(1-c)^{2}}+o(1)\right)\mathbb{E}\left[\sum_{k=1}^{d}a_{k}^{2}b_{k}^{2}\right]$
$\displaystyle=\left(\frac{c^{3}}{(1-c)^{3}}+o(1)\right)\mathbb{E}\left[\sum_{k=1}^{d}a_{k}^{2}b_{k}^{2}\right]$
$\displaystyle=\frac{c^{3}}{(1-c)^{3}}\sum_{k=1}^{d}\mathbb{E}[a_{k}^{2}]\mathbb{E}[b_{k}^{2}]+o\left(\frac{1}{d}\right),$

where the last line holds due to the following reasoning, even though $a$ and
$b$ are not independent. We then use the fact that

$\mathbb{E}[a_{k}^{2}b_{k}^{2}]-\mathbb{E}[a_{k}^{2}]\mathbb{E}[b_{k}^{2}]\leq\sqrt{\mathrm{Var}(a_{k}^{2})\mathrm{Var}(b_{k}^{2})}$

and Lemma 13 of Sonthalia & Nadakuditi (2023), to get that
$\mathrm{Var}\left(\sum_{k=1}^{d}a_{k}^{2}\right)=O\left(\frac{1}{d}\right).$
So, by symmetry of coordinates,
$\mathrm{Var}(a_{k}^{2})=O\left(\frac{1}{d^{2}}\right).$ The same holds for
$b_{k}$, giving us that

$\left|\mathbb{E}[a_{k}^{2}b_{k}^{2}]-\mathbb{E}[a_{k}^{2}]\mathbb{E}[b_{k}^{2}]\right|\leq
O\left(\frac{1}{d^{2}}\right).$

This gives us that

$\mathrm{Var}\left((\Sigma_{trn}^{-1}(K^{T}K)\Sigma_{trn}^{-1})_{ij}^{2}\right)=\frac{c^{3}}{d(1-c)^{3}}+o\left(\frac{1}{d}\right)\qquad
i\neq j.$

For $i=j$, we use Sonthalia & Nadakuditi (2023) to see that the variance is
$O\left(\frac{1}{d}\right)=O\left(\frac{1}{N}\right)$ since $d=cN$. ∎

######  Lemma 13.

For $c<1$, we have that
$\displaystyle\mathbb{E}[\Sigma_{trn}^{-1}K^{T}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}K\Sigma_{trn}^{-1}]=\frac{1}{\eta_{trn}^{2}}\frac{c^{2}}{(1-c)^{3}}+o(1)$
and the variance of the $ij^{th}$ entry is $O\left(\frac{1}{N}\right)$.

###### Proof.

Let
$M:=\Sigma_{trn}^{-1}K^{T}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}K\Sigma_{trn}^{-1}$
and note that

$\Sigma_{trn}^{-1}K^{T}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}K\Sigma_{trn}^{-1}=\Sigma_{trn}U^{T}(A_{trn}A_{trn}^{T})^{\dagger}(A_{trn}A_{trn}^{T})^{\dagger}U\Sigma_{trn}.$

So,
$M_{ij}=\sigma_{i}u_{i}^{T}(A_{trn}A_{trn}^{T})^{\dagger}(A_{trn}A_{trn}^{T})^{\dagger}u_{j}\sigma_{j}.$
Using ideas from Sonthalia & Nadakuditi (2023), we see that if $i\neq j$, then
the expectation is 0. On the other hand if $i=j$, then using Lemma 6 from
Sonthalia & Nadakuditi (2023), with $p=N$, $q=d$, we get that

$\mathbb{E}[M_{ii}]=\frac{\sigma_{i}^{2}}{\eta_{trn}^{2}}\frac{c^{2}}{(1-c)^{3}}+o(1).$

For the variance, pick arbitrary $i\neq j$ and fix them. Consider
$a=\tilde{U}^{*}u_{i}$ and $b=\tilde{U}^{*}u_{j}$. They are uniformly random
orthogonal unit vectors, not necessarily independent. Now note that

$\displaystyle M_{ij}$
$\displaystyle=u_{i}^{T}(A_{trn}A_{trn}^{T})^{\dagger}(A_{trn}A_{trn}^{T})^{\dagger}u_{j}$
$\displaystyle=u_{i}^{T}(\tilde{U}\tilde{\Sigma}\tilde{\Sigma}^{*}\tilde{\Sigma}\tilde{\Sigma}^{*}\tilde{U}^{*})^{\dagger}u_{j}$
$\displaystyle=u_{i}^{T}\tilde{U}(\tilde{\Sigma}\tilde{\Sigma}^{*}\tilde{\Sigma}\tilde{\Sigma}^{*})^{\dagger}\tilde{U}^{*}u_{j}$
$\displaystyle=a^{T}(\tilde{\Sigma}\tilde{\Sigma}^{*}\tilde{\Sigma}\tilde{\Sigma}^{*})^{\dagger}b$
$\displaystyle=\sum_{k=1}^{d}\frac{1}{\tilde{\sigma}_{k}^{4}}a_{k}b_{k}.$

So, we get that

$\displaystyle\mathbb{E}[M_{ij}^{2}]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{k=1}^{d}\frac{1}{\tilde{\sigma}_{k}^{4}}a_{k}b_{k}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{d}\sum_{l=1}^{d}\frac{1}{\sigma_{k}^{4}\sigma_{l}^{4}}a_{k}b_{k}a_{l}b_{l}\right]$
$\displaystyle=\left(\frac{c^{4}(c^{2}+22/6c+1)}{(1-c)^{7}}+o(1)\right)\mathbb{E}\left[\left(\sum_{k=1}^{d}a_{k}b_{k}\right)^{2}\right]+(\chi(c)+o(1))\mathbb{E}\left[\sum_{k=1}^{d}a_{k}^{2}b_{k}^{2}\right]$
$\displaystyle=(\chi(c)+o(1))\mathbb{E}\left[\sum_{k=1}^{d}a_{k}^{2}b_{k}^{2}\right]$
$\displaystyle=(\chi(c)+o(1))\mathbb{E}\left[\sum_{k=1}^{d}a_{k}^{2}b_{k}^{2}\right]$
$\displaystyle=\chi(c)\sum_{k=1}^{d}\mathbb{E}[a_{k}^{2}]\mathbb{E}[b_{k}^{2}]+o\left(\frac{1}{d}\right),$

where the last line holds due to the argument in the proof of Lemma 12. Here
$\chi(c)$ is some function of $c$. This gives us that
$\mathrm{Var}[M_{ij}]=\frac{1}{d}\chi(c)+o\left(\frac{1}{d}\right)$ for $i\neq
j$. For $i=j$, we use Sonthalia & Nadakuditi (2023) to see that the variance
is $O\left(\frac{1}{d}\right)$. ∎

######  Lemma 14.

For $c<1$, we have that $\mathbb{E}[QQ^{T}]=(1-c)I_{r}$ and the variance of
each entry is $O\left(\frac{1}{d}\right)$. Further,

$\mathbb{E}[(QQ^{T})^{-1}]=\frac{1}{1-c}I_{r}+O\left(\frac{1}{{d}}\right).$

and each element has variance $O(1/d)$

###### Proof.

Recall that $Q=V^{T}(I-A_{trn}^{\dagger}A_{trn})$. We thus have that

$\displaystyle QQ^{T}$ $\displaystyle=V^{T}(I-A_{trn}^{\dagger}A_{trn})V.$
$\displaystyle=V^{T}V-V^{T}A_{trn}^{\dagger}A_{trn}V$
$\displaystyle=I_{r}-V^{T}\tilde{V}\tilde{\Sigma}^{\dagger}\tilde{\Sigma}\tilde{V}^{T}V$
$\displaystyle=I_{r}-R\begin{bmatrix}I_{d}&0\\\ 0&0_{N-d}\end{bmatrix}R^{T}.$

Where $R$ is a uniformly random $r\times N$ unitary matrix. Then by symmetry
(of the sign of rows of $R$), we have that

$\mathbb{E}[QQ^{T}]=I_{r}-cI_{r}=\left(1-c\right)I_{r}.$

Next notice that

$\mathbb{E}[QQ^{T}]=V^{T}(I-\mathbb{E}[A_{trn}^{\dagger}A_{trn}])V,$

thus to compute the variance, we first compute the variance of
$(A_{trn}^{\dagger}A_{trn})_{ij}$. For this, we first note that

$\begin{bmatrix}cI_{d}&0\\\
0&0\end{bmatrix}=\mathbb{E}[A_{trn}^{\dagger}A_{trn}]=\mathbb{E}[A_{trn}^{\dagger}A_{trn}A_{trn}^{\dagger}A_{trn}].$

Since $A_{trn}^{\dagger}A_{trn}$ is symmetric, we can see that

$\sum_{k}^{d}((A_{trn}^{\dagger}A_{trn})_{ik})^{2}=\begin{cases}c&i\leq d\\\
0&i>d\end{cases}.$

From Lemma 15 in Sonthalia & Nadakuditi (2023), we have that
$\mathbb{E}[((A_{trn}^{\dagger}A_{trn})_{ii})^{2}]=c^{2}+\frac{2c}{N}+o(1)$.
Then combining this with the computation above and using symmetry, we have
that for $i\neq j$ and $\min(i,j)\leq d$

$\mathbb{E}[(A_{trn}^{\dagger}A_{trn})^{2}_{ij}]=\frac{1}{d-1}\left(\frac{1}{c}-\frac{1}{c^{2}}+\frac{3}{cd}+o(1)\right).$

Now consider the other (full) SVD of $X_{trn}$ given by $\hat{U}_{d\times
d}\hat{\Sigma}_{d\times N}\hat{V}^{T}_{N\times N}$. Note that the top left
$r\times r$ block of $\hat{\Sigma}$ is $\Sigma_{trn}$, and the first $r$ rows
of $\hat{V}$ give $V$. Note that since $\hat{V}^{T}\tilde{V}$ is still
uniformly random, the variance argument above follows for
$\hat{V}^{T}A_{trn}^{\dagger}A_{trn}\hat{V}$. Additionally, for $i,j\leq r$,
$(\hat{V}^{T}A_{trn}^{\dagger}A_{trn}\hat{V})_{ij}=(V^{T}A_{trn}^{\dagger}A_{trn}V)_{ij}$
Thus, we see that for $i,j\leq r$,

$\mathbb{E}[((V^{T}A_{trn}^{\dagger}A_{trn}V)_{ij})^{2}]=\frac{1}{d-1}\left(c-c^{2}+\frac{2}{cd}+o(1)\right).$

Thus, finally, we have that arranged as a matrix $\mathbb{E}[QQ^{T}\odot
QQ^{T}]=O\left(\frac{1}{d}\right).$ By an analogous symmetry argument, we can
show that
$\mathrm{Var}\left((V^{T}A_{trn}^{\dagger}A_{trn}V)_{ij}^{2}\right)=O\left(\frac{1}{d}\right).$
In principle, one can get a faster decay bound with a more sophisticated
argument, but this is sufficient for our purposes. Now, by Lemma 5, we get
that

$\mathbb{E}[(QQ^{T})^{-1}]=\frac{1}{1-c}I_{r}+O\left(\frac{1}{{d}}\right).$

and each element has variance $O(1/d)$.

∎

######  Lemma 15.

For $c<1$,

$\mathbb{E}\left[\Sigma_{trn}^{-1}H_{1}\Sigma_{trn}^{-1}\right]=\frac{1}{1-c}\Sigma_{trn}^{-2}+\frac{1}{\eta_{trn}^{2}}\frac{c}{1-c}I_{r}+o(1)$

and the variance of each element is $O\left(\frac{1}{d}\right)$. Additionally

$\mathbb{E}\left[\Sigma_{trn}H_{1}^{-1}\Sigma_{trn}\right]=(1-c)\eta_{trn}^{2}(\eta_{trn}^{2}\Sigma_{trn}^{-2}+cI_{r})^{-1}+o(1),$

and the variance of each term is $O\left(\frac{1}{d}\right)$

###### Proof.

Recall that

$H_{1}=K^{T}K+Z^{T}(QQ^{T})^{-1}Z=K^{T}K+Z^{T}\Sigma_{trn}^{-1}(\Sigma_{trn}(QQ^{T})^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}Z.$

Using Lemmas 7, 12 and 14 along with an argument analogous to the one in Lemma
8, we get that

$\mathbb{E}[\Sigma_{trn}^{-1}H_{1}\Sigma_{trn}^{-1}]=\frac{1}{1-c}\Sigma_{trn}^{-2}+\frac{1}{\eta_{trn}^{2}}\frac{c}{1-c}I_{r}+O\left(\frac{1}{d}\right)+o(1)$

and the variance of each element is $O\left(\frac{1}{d}\right)$.

For the inverse, we define $\delta H_{1}:=H_{1}-\mathbb{E}[H_{1}]$ and by an
argument analogous to the one in the proof of Lemma 8, we get that

$\mathbb{E}\left[\Sigma_{trn}H_{1}^{-1}\Sigma_{trn}\right]=(1-c)\eta_{trn}^{2}(\eta_{trn}^{2}\Sigma_{trn}^{-2}+cI_{r})^{-1}+o(1)$

and the variance of each term is $O\left(\frac{1}{d}\right)$. ∎

######  Lemma 16.

When $c<1$, we have for $W=W_{opt}$ that

$\mathbb{E}[\|W\|_{F}^{2}]=\frac{c^{2}}{1-c}\operatorname{Tr}\left(\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I_{r}\right)(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I_{r})^{-2}\right)+o(1).$

###### Proof.

Again, like in Lemma 9, we first use the estimates for the expectations from
the lemmas above to get an estimate for the expectation of $\|W\|_{F}^{2}$,
and then bound the deviation from it using the variance estimates in this
section. We see that the first term in $\operatorname{Tr}(W^{T}W)$ is

$\operatorname{Tr}((A_{trn}^{\dagger})^{T}K(H_{1}^{-1})^{T}\Sigma_{trn}^{2}H_{1}^{-1}K^{T}A_{trn}^{\dagger})=\operatorname{Tr}(K^{T}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}K(H_{1}^{-1})^{T}\Sigma_{trn}^{2}H_{1}^{-1}).$

Then using Lemma 13 along with cyclic invariance of traces, we see that this
is estimated by

$\frac{1}{\eta_{trn}^{2}}\frac{c^{2}}{(1-c)^{3}}\operatorname{Tr}(\Sigma_{trn}(H_{1}^{-1})^{T}\Sigma_{trn}^{2}H_{1}^{-1}\Sigma_{trn})+o(1).$

Then using Lemma 15, we get that this is estimated by

$\displaystyle\eta_{trn}^{2}\frac{c^{2}}{(1-c)^{3}}(1-c)^{2}(cI_{r}+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-2}+o(1)$
$\displaystyle=\eta_{trn}^{2}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\Sigma_{trn}^{4}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I_{r})^{-2}\right)+o(1).$

The second term is

$\operatorname{Tr}(((QQ^{T})^{-1})^{T}Z(H_{1}^{-1})^{T}\Sigma_{trn}^{2}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}HH^{T}).$

We can rewrite this as

$\operatorname{Tr}(((QQ^{T})^{-1})^{T}Z\Sigma_{trn}^{-1}(\Sigma_{trn}(H_{1}^{-1})^{T}\Sigma_{trn})(\Sigma_{trn}H_{1}^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}Z^{T}(QQ^{T})^{-1}HH^{T}).$

Using Lemmas 4 and 7, we can estimate its expectation by

$\frac{1}{\eta_{trn}^{2}}\frac{c^{2}}{1-c}\operatorname{Tr}\left(((QQ^{T})^{-1})^{T}\Sigma_{trn}^{-1}(\Sigma_{trn}(H_{1}^{-1})^{T}\Sigma_{trn})(\Sigma_{trn}H_{1}^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}(QQ^{T})^{-1}\right)+o(1).$

Then using Lemma 14 and the fact that $H_{1}^{T}=H_{1}$, we get that this be
further estimated by

$\frac{1}{\eta_{trn}^{2}}\frac{c^{2}}{(1-c)^{3}}\operatorname{Tr}(\Sigma_{trn}^{-1}(\Sigma_{trn}(H_{1}^{-1})\Sigma_{trn})^{2}\Sigma_{trn}^{-1})+o(1).$

Then using Lemma 15, we can simplify this estimate to

$\begin{split}\frac{1}{\eta_{trn}^{2}}\frac{c^{2}}{(1-c)^{3}}(1-c)^{2}\eta_{trn}^{4}(cI_{r}+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-2}+o(1)\hskip
113.81102pt\\\
=\eta_{trn}^{2}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I_{r})^{-2}\right)+o(1).\end{split}$

The cross term in $\operatorname{Tr}(W^{T}W)$ is

$-2\operatorname{Tr}((A_{trn}^{\dagger})^{T}K(H_{1}^{-1})^{T}\Sigma_{trn}^{2}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H).$

Here the term (after cyclically permuting) that we should focus on is

$\operatorname{Tr}(H(A_{trn}^{\dagger})^{T}K)=-\operatorname{Tr}(V_{trn}^{T}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}A_{trn}^{\dagger}\Sigma_{trn}U).$

Here since $A_{trn}=\eta_{trn}\tilde{U}\tilde{\Sigma}\tilde{V}^{T}$ and
$\tilde{U},\tilde{V}$ are independent of each other, we see that using ideas
from Lemma 8 in Sonthalia & Nadakuditi (2023) and extending them to rank $r$
as before, the expectation of this term is 0 with $O(1/d)$ variance. Thus, the
whole cross-term has an expectation equal to 0.

Again, to bound the deviation from this estimate, note that for real valued
random variables $X,Y$ we have that
$|\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]|=|Cov(X,Y)|\leq\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}$.
For real valued random variables $X,Y,Z,W$, we have the following fact, from
Bohrnstedt & Goldberger (1969).

$\displaystyle Cov(XY,WZ)$
$\displaystyle=\mathbb{E}X\mathbb{E}WCov(Y,Z)+\mathbb{E}Y\mathbb{E}ZCov(X,W)+\mathbb{E}X\mathbb{E}ZCov(Y,W)+$
$\displaystyle\qquad\mathbb{E}Y\mathbb{E}WCov(X,Z)+Cov(X,W)Cov(Y,Z)+Cov(Y,W)Cov(X,Z).$

We repeatedly apply these two to upper bound the deviation between the product
of the expectations in the estimates above and the expectation of the product.
It is then straightforward to see that since all variances are $O(1/d)$, the
estimation error is $O(1/{d})=o(1)$.

Finally, combining the terms, we get that

$\mathbb{E}[\|W\|_{F}^{2}]=\frac{c^{2}}{1-c}\operatorname{Tr}\left(\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I_{r}\right)(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I_{r})^{-2}\right)+o(1).$

∎

######  Theorem 8.

When $d<N-r$ and $\beta=I$, then the test error $\mathcal{R}(W,X_{tst})$ for
$W=W_{opt}$ is given by

$\begin{split}\frac{\eta_{trn}^{4}}{N_{tst}}\|\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-1}L\|_{F}^{2}\hskip
227.62204pt\\\
+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I_{r}\right)(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I_{r})^{-2}\right)+o\left(\frac{1}{d}\right).\end{split}$

###### Proof.

Note that
$\mathcal{R}(W,X_{tst})=\frac{1}{N_{tst}}\|U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1}L\|_{F}^{2}+\frac{\eta_{tst}^{2}}{d}\|W\|_{F}^{2}$.

To compute the first term, we observe that it is given by

$\frac{1}{N_{tst}}Tr(U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1}LL^{T}\Sigma_{trn}^{-1}(QQ^{T})^{-1}ZH_{1}^{-1}\Sigma_{trn}U^{T}).$

This can be rewritten using cyclic invariance as

$\frac{1}{N_{tst}}Tr(U^{T}U\Sigma_{trn}H_{1}^{-1}Z^{T}\Sigma_{trn}^{-1}\Sigma_{trn}(QQ^{T})^{-1}\Sigma_{trn}^{-1}LL^{T}\Sigma_{trn}^{-1}(QQ^{T})^{-1}\Sigma_{trn}\Sigma_{trn}^{-1}ZH_{1}^{-1}\Sigma_{trn}).$

We apply Lemmas 14, 15 and 7 to get that its expectation can be estimated by

$\displaystyle\frac{1}{N_{tst}}Tr\left(\left((c-1)\eta_{trn}^{2}(\eta_{trn}^{2}I+c\Sigma_{trn}^{2})^{-1}\right)^{2}\left(\frac{1}{1-c}\right)^{2}LL^{T}\right)+o(1/d)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}Tr\left(\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}LL^{T}\right)+o(1/d)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\|\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-1}L\|_{F}^{2}+o(1/d).$

We get $o\left(\frac{1}{d}\right)$ due to the $\Sigma_{trn}^{-2}$ term. Again,
we can argue as in the proof of Lemma 16 to bound the deviation of the true
expectation from this estimate by $o(1/d)$, noting that since train and test
data assumptions are decoupled, $LL^{T}/N_{tst}$ can be treated as constant as
$N$ grows.

Combining this with Lemma 9, we get that

$\begin{split}\frac{\eta_{trn}^{4}}{N_{tst}}\|\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-1}L\|_{F}^{2}\hskip
227.62204pt\\\
+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I_{r}\right)(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I_{r})^{-2}\right)+o\left(\frac{1}{d}\right).\end{split}$

∎

See 1

###### Proof.

The version for $\beta=I$ follows immediately from Theorem 7 and Theorem 8.

We now demonstrate how the the general version is a straightforward repetition
of the proofs of the two theorems. First denote by $Z_{opt}$ the minimum norm
solution to the denoising problem (where $\beta=I$). Then
$Z_{opt}=X_{trn}(X_{trn}+A_{trn})^{\dagger}$ and note that

$W_{opt}=Y_{trn}(X_{trn}+A_{trn})^{\dagger}=\beta^{T}X_{trn}(X_{trn}+A_{trn})^{\dagger}=\beta^{T}Z_{opt}$

We present the adaptation of Lemma 9, the other lemmas can be adapted
accordingly.

We first use the estimates for the expectations from the lemmas to get an
estimate for $\|W_{opt}\|_{F}^{2}=\|\beta^{T}Z_{opt}\|_{F}^{2}$, and then
bound the deviation from it using the variance estimates above. We begin the
calculation as

$\|\beta^{T}Z_{opt}\|_{F}^{2}=\operatorname{Tr}(Z_{opt}^{T}\beta\beta^{T}Z_{opt})$

Using Lemma 1, we see that the trace has three terms. The first term is

$\operatorname{Tr}(H^{T}(K_{1}^{-1})^{T}Z((P^{T}P)^{-1})^{T}\Sigma_{trn}^{T}U^{T}\beta\beta^{T}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H)$

Using $\beta_{U}^{T}=\beta^{T}_{opt}U$ Then since the trace is invariant under
cyclic permutations, we get the following term

$\operatorname{Tr}(\beta_{U}^{T}\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}HH^{T}(K_{1}^{-1})^{T}Z((P^{T}P)^{-1})^{T}\Sigma_{trn}^{T}\beta_{U})$

The rest of the proof for this term is the same as Lemma 9.

The second term in $\operatorname{Tr}(W^{T}\beta\beta^{T}W)$ is

$-2\operatorname{Tr}(H^{T}(K_{1}^{-1})^{T}Z^{T}((P^{T}P)^{-1})^{T}\Sigma_{trn}^{T}\beta_{U}\beta_{U}^{T}\Sigma_{trn}Z^{-1}HH^{T}ZP^{\dagger})$

Then the rest of the proof for this term is identical to the one in the proof
of Lemma 9.

Finally, the last term in $\operatorname{Tr}(W^{T}\beta\beta^{T}W)$ is

$\operatorname{Tr}((P^{\dagger})^{T}Z^{T}(K_{1}^{-1})^{T}HH^{T}(Z^{-1})^{T}\Sigma_{trn}^{T}\beta_{U}\beta_{U}^{T}\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}P^{\dagger})$

The rest of the proof is the same again, after using the cyclic invariance of
the trace.

∎

###  C.2 Proof of Corollary 1, The Distribution Shift Bound

We first prove Theorem 5, bounding the difference in generalization error in
terms of the change in the test set. Recall the theorem below. See 5

###### Proof.

We will first show this for $c<1$. Let
$\mathcal{R}_{i}:=\mathcal{R}(W_{opt},X_{tst,i})$. Remember that the test
error is given by

$\displaystyle\mathcal{R}_{i}$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L_{i}\right\|_{F}^{2}$
$\displaystyle\quad+\eta_{tst}^{2}\eta_{trn}^{2}\frac{1}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I\right)\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}\right)+o\left(\frac{1}{N}\right)$

Note that the second term above has no dependence on $X_{tst,i}$, so the
difference is given by

$\displaystyle\mathcal{R}_{2}-\mathcal{R}_{1}$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\left(\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L_{2}\right\|_{F}^{2}-\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L_{1}\right\|_{F}^{2}\right)$
$\displaystyle\qquad+o\left(\frac{1}{N}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}Tr\left((\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\beta_{U}\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\right)+o\left(\frac{1}{N}\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\frac{\eta_{trn}^{4}}{N_{tst}}\|(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\beta_{U}\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\|_{F}\|(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\|_{F}+o\left(\frac{1}{N}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\|\beta_{U}\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-2}\|_{F}\|(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\|_{F}+o\left(\frac{1}{N}\right)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\frac{\eta_{trn}^{4}}{N_{tst}}\|\beta_{U}\beta_{U}^{T}\|_{2}\|(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-2}\|_{F}\|(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\|_{F}+o\left(\frac{1}{N}\right)$

where $(i)$ above is by the Cauchy-Schwarz inequality for the Frobenius norm
and $(ii)$ above holds since $\|AB\|_{F}\leq\|A\|_{2}\|B\|_{F}$. So, for
$\Sigma_{trn}$ with lower bounded diagonal entries $\sigma_{i}>M$, we have
that

$\displaystyle|\mathcal{R}_{2}-\mathcal{R}_{1}|$
$\displaystyle\leq\frac{\eta_{trn}^{4}r}{N_{tst}(\sigma_{r}(X_{trn})^{2}c+\eta_{trn}^{2})^{2}}\|\beta_{U}\beta_{U}^{T}\|_{2}\|(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\|_{F}+o\left(\frac{1}{N}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}r}{N_{tst}(\sigma_{r}(X_{trn})^{2}c+\eta_{trn}^{2})^{2}}\|U^{T}\beta\beta^{T}U\|_{2}\|(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\|_{F}+o\left(\frac{1}{N}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}r}{N_{tst}(\sigma_{r}(X_{trn})^{2}c+\eta_{trn}^{2})^{2}}\|\beta\beta^{T}\|_{2}\|(L_{2}L_{2}^{T}-L_{1}L_{1}^{T})\|_{F}+o\left(\frac{1}{N}\right)$
$\displaystyle=\frac{\sigma_{1}(\beta)^{2}}{N_{tst}}\frac{\eta_{trn}^{4}r}{(\sigma_{r}(X_{trn})^{2}c+\eta_{trn}^{2})^{2}}\|L_{2}L_{2}^{T}-L_{1}L_{1}^{T}\|_{F}+o\left(\frac{1}{N}\right)$

Similarly, for $c>1$, we have that

$|\mathcal{R}_{2}-\mathcal{R}_{1}|\leq\frac{\sigma_{1}(\beta)^{2}}{N_{tst}}\frac{\eta_{trn}^{4}r}{(\sigma_{r}(X_{trn})^{2}+\eta_{trn}^{2})^{2}}\|L_{2}L_{2}^{T}-L_{1}L_{1}^{T}\|_{F}+O\left(\frac{\|\Sigma_{trn}\|_{F}^{2}}{N^{2}}\right)+o\left(\frac{1}{N}\right)\\\
$

∎

We now prove our corollary below.

See 1

###### Proof.

Let $\bar{L}_{i}:=L_{i}-[\mu_{i}\ \mu_{i}\ \dots\ \mu_{i}]$ be the centered
version of the test data matrix. In that case,
$\mathbb{E}_{X_{tst,i}}[\bar{L}_{i}]=\mathbb{E}_{X_{tst,i}}[U^{T}\bar{X}_{tst,i}]=0$
and

$\mathbb{E}_{X_{tst,i}}[\bar{L}_{i}\bar{L}_{i}^{T}]=\mathbb{E}_{X_{tst,i}}[U^{T}\bar{X}_{tst,i}\bar{X}_{tst,i}^{T}U]=N_{tst}\Sigma_{i}$

Now note the following elementary computation.

$\displaystyle\mathbb{E}_{X_{tst,i}}[L_{i}L_{i}^{T}]$
$\displaystyle=\mathbb{E}_{X_{tst,i}}[(\bar{L}_{i}+[\mu_{i}\ \mu_{i}\ \dots\
\mu_{i}])(\bar{L}_{i}+[\mu_{i}\ \mu_{i}\ \dots\ \mu_{i}])^{T}]$
$\displaystyle=\mathbb{E}_{X_{tst,i}}[\bar{L}_{i}\bar{L}_{i}^{T}]+0+0+N_{tst}\mu_{i}\mu_{i}^{T}$
$\displaystyle=N_{tst}\Sigma_{trn}+N_{tst}\mu_{i}\mu_{i}^{T}$

We can now follow the initial part of the proof of Theorem 5 to get the
following for $c<1$.

$\displaystyle\mathcal{G}_{2}-\mathcal{G}_{1}$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}Tr\left(\beta_{U}\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-2}(\mathbb{E}_{X_{tst},2}[L_{2}L_{2}^{T}]-\mathbb{E}_{X_{tst},1}[L_{1}L_{1}^{T}])\right)+o\left(\frac{1}{N}\right)$
$\displaystyle={\eta_{trn}^{4}}Tr\left(\beta_{U}\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-2}(\Sigma_{2}-\Sigma_{1}+\mu_{2}\mu_{2}^{T}-\mu_{1}\mu_{1}^{T})\right)+o\left(\frac{1}{N}\right)$

Now, we can follow the rest of the proof of Theorem 5 to complete the proof. ∎

###  C.3 Proofs for Theorem 2, Out-of-Subspace Generalization

See 2

###### Proof.

Here we see that

$\displaystyle\|(I-W)X_{tst}-(I-W)UL\|_{F}^{2}$
$\displaystyle=\|(I-W)(X_{tst}-UL)\|_{F}^{2}$
$\displaystyle\leq\sigma_{1}(W-I)^{2}\|X_{tst}-UL\|_{F}^{2}$
$\displaystyle=\alpha^{2}\sigma_{1}(W-I)^{2}$

The inequality is due to Cauchy-Schwarz inequality. Then using the reverse
triangle inequality, we have that

$\Big{|}\|(I-W)X_{tst}\|_{F}^{2}-\|(I-W)UL\|_{F}^{2}\Big{|}\leq\alpha^{2}\sigma_{1}(W+I)^{2}.$

∎

###  C.4 Proofs for Corollary 4, Generalization Error

See 4

###### Proof.

We begin by noting that the variance term is independent of $X_{tst}$. Hence
we only need to focus on the bias term. Let $\bar{L}:=L-[\mu\ \mu\ \dots\
\mu]$ be the centered version of the test data matrix. In that case,
$\mathbb{E}_{X_{tst,i}}[\bar{L}]=\mathbb{E}_{X_{tst,i}}[U^{T}\bar{X}_{tst,i}]=0$
and

$\mathbb{E}_{X_{tst,i}}[\bar{L}\bar{L}^{T}]=\mathbb{E}_{X_{tst,i}}[U^{T}\bar{X}_{tst,i}\bar{X}_{tst,i}^{T}U]=N_{tst}\Sigma$

Now note the following elementary computation.

$\displaystyle\mathbb{E}_{X_{tst,i}}[LL^{T}]$
$\displaystyle=\mathbb{E}_{X_{tst,i}}[(\bar{L}+[\mu\ \mu\ \dots\
\mu])(\bar{L}+[\mu\ \mu\ \dots\ \mu])^{T}]$
$\displaystyle=\mathbb{E}_{X_{tst,i}}[\bar{L}\bar{L}^{T}]+0+0+N_{tst}\mu\mu^{T}$
$\displaystyle=N_{tst}\Sigma_{trn}+N_{tst}\mu\mu^{T}$

Consider the following sequence on computations about the bias term.

$\displaystyle\mathbb{E}_{X_{tst}}\left[\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L\right\|_{F}^{2}\right]$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}Tr\left(\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\mathbb{E}_{X_{tst}}[LL^{T}](\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\beta_{U}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}Tr\left(\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}(\Sigma+\mu\mu^{T})(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\beta_{U}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}(\Sigma+\mu\mu^{T})^{1/2}\right\|_{F}^{2}$

This establishes our claim. ∎

###  C.5 Proof for Theorem 4, Test Error for $W^{*}$

See 4

###### Proof.

To prove the first part of the theorem, we first note that

$\mathbb{E}_{A_{trn}}\left[\|Y_{trn}-W(X_{trn}+A_{trn})\|_{F}^{2}\right]=\|Y_{trn}-WX_{trn}\|_{F}^{2}+\frac{\eta_{trn}^{2}N}{d}\|W\|_{F}^{2}.$

Solving this is equivalent to solving

$\|\begin{bmatrix}Y_{trn}&0\end{bmatrix}-W\begin{bmatrix}X_{trn}&\mu
I\end{bmatrix}\|_{F}^{2}.$

where $\mu^{2}=\frac{\eta_{trn}^{2}N}{d}$. We know from classical linear
algebra that the solution to the above is

$W^{*}=\begin{bmatrix}\beta^{T}X_{trn}&0\end{bmatrix}\begin{bmatrix}X_{trn}&\mu
I\end{bmatrix}^{\dagger}.$

Using Lemmas 5 and 6 from Sonthalia et al. (2023), we have that if
$X_{trn}=U\Sigma_{trn}V_{trn}^{T}$ where $U$ is $d$ by $d$, $\Sigma_{trn}$ is
$d$ by $d$ and $V_{trn}$ is $N\times d$, then

$\begin{bmatrix}X_{trn}&\mu
I\end{bmatrix}=U\underbrace{\begin{bmatrix}\sqrt{\sigma_{1}(X_{trn})^{2}+\mu^{2}}&0&\cdots&&&0\\\
0&\ddots&0&&&\\\ \vdots&&\sqrt{\sigma_{r}(X_{trn})^{2}+\mu^{2}}&&&\vdots\\\
&&0&\mu&0&\\\ &&&0&\ddots&0\\\
0&&&&0&\mu\end{bmatrix}}_{\hat{\Sigma}}\begin{bmatrix}V_{trn}\Sigma_{trn}\hat{\Sigma}^{-1}\\\
\mu U\hat{\Sigma}^{-1}\end{bmatrix}^{T}.$

Thus, we have that

$W^{*}=\begin{bmatrix}\beta^{T}U\Sigma_{trn}V_{trn}^{T}&0\end{bmatrix}\begin{bmatrix}V_{trn}\Sigma_{trn}\hat{\Sigma}^{-1}\\\
\mu
U\hat{\Sigma}^{-1}\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt{\sigma_{1}(X_{trn})^{2}+\mu^{2}}}&0&\cdots&&&0\\\
0&\ddots&0&&&\\\
\vdots&&\frac{1}{\sqrt{\sigma_{r}(X_{trn})^{2}+\mu^{2}}}&&&\vdots\\\
&&0&\frac{1}{\mu}&0&\\\ &&&0&\ddots&0\\\
0&&&&0&\frac{1}{\mu}\end{bmatrix}U^{T}.$

Simplifying, we get

$\displaystyle W^{*}$
$\displaystyle=\beta_{U}^{T}\Sigma_{trn}^{2}\hat{\Sigma}^{-2}U^{T}$
$\displaystyle=\beta_{U}^{T}\begin{bmatrix}\frac{\sigma_{1}(X_{trn})^{2}}{\sigma_{1}(X_{trn})^{2}+\mu^{2}}&0&\cdots&&&0\\\
0&\ddots&0&&&\\\
\vdots&&\frac{\sigma_{r}(X_{trn})^{2}}{\sigma_{r}(X_{trn})^{2}+\mu^{2}}&&&\vdots\\\
&&0&0&0&\\\ &&&0&\ddots&0\\\ 0&&&&0&0\end{bmatrix}U^{T}$
$\displaystyle=\beta_{U}^{T}\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\mu^{2}I)^{-1}U^{T}$
$\displaystyle=\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{\eta_{trn}^{2}N}{d}I\right)^{-1}U^{T}$
$\displaystyle=\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-1}U^{T}$

Hence we have finished proving the first part.

For the second part, we note that similar to before, we need to calculate

$\frac{1}{N_{tst}}\mathbb{E}_{A_{tst}}\left[\|Y_{tst}-W^{*}(X_{tst}+A_{tst})\|_{F}^{2}\right]=\frac{1}{N_{tst}}\|Y_{tst}-W^{*}X_{tst}\|_{F}^{2}+\frac{\eta_{tst}^{2}}{d}\|W^{*}\|_{F}^{2}.$

For the first term recall that $X_{tst}=UL$ and $Y_{tst}=\beta^{T}X_{tst}$.
Hence we have that

$\displaystyle\frac{1}{N_{tst}}\|Y_{tst}-W^{*}X_{tst}\|_{F}^{2}=\frac{1}{N_{tst}}\left\|\beta_{U}^{T}\left(I-\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-1}\right)L\right\|_{F}^{2}=\frac{1}{N_{tst}}\frac{\eta_{trn}^{4}N^{2}}{d^{2}}\left\|\beta_{U}^{T}\left(\Sigma_{trn}^{2}+\frac{\eta_{trn}^{2}N}{d}\right)^{-1}L\right\|_{F}^{2}$

For the second term, we have that

$\displaystyle\frac{\eta_{tst}^{2}}{d}\|W^{*}\|_{F}^{2}$
$\displaystyle=\frac{\eta_{tst}^{2}}{d}\operatorname{Tr}\left(\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\beta_{U}\right)=\frac{\eta_{tst}^{2}}{d}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\right)$

∎

###  C.6 Proof for Corollary 2, Relative Excess Error

See 2

###### Proof.

Recall from Theorem 4 that the test error for $W^{*}$ is given by

$\mathcal{R}(W^{*},UL)=\frac{\eta_{trn}^{4}N^{2}}{d^{2}}\left\|\beta_{U}^{T}\left(\Sigma_{trn}^{2}+\frac{\eta_{trn}^{2}N}{d}I\right)^{-1}L\right\|^{2}+\frac{\eta_{tst}^{2}}{d}Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\right)$

We prove this for $c>1$, the proof for $c<1$ is analogous and in fact simpler.
Notice that when $|\Sigma_{trn}\|_{F}^{2}=\Omega(N^{1/2+\epsilon})$, in both
$\mathcal{R}(W_{opt},X_{tst})$ and $\mathcal{R}(W^{*},X_{tst})$, the bias
terms are $O(1/d^{1+2\epsilon})$ while the variance terms are $\Theta(1/d)$.
In particular, as $d,N\to\infty$, with $d/N\to c$, the limit of the excess
risk is given by only considering the variance terms and the estimation
errors.

$\displaystyle\lim_{d,N\to\infty,d/N\to
c}\frac{\mathcal{R}(W_{opt},X_{tst})-\mathcal{R}(W^{*},X_{tst})}{\mathcal{R}(W^{*},X_{tst})}$
$\displaystyle=\lim_{d,N\to\infty,d/N\to
c}\frac{\frac{\eta_{tst}^{2}}{d}Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\right)-\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})}{\frac{\eta_{tst}^{2}}{d}Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\right)}$
$\displaystyle\qquad+\lim_{d,N\to\infty,d/N\to
c}\frac{O\left(\frac{\|\Sigma_{trn}\|_{F}^{2}}{N^{2}}\right)+o\left(\frac{1}{N}\right)}{\frac{\eta_{tst}^{2}}{d}Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\right)}$
$\displaystyle=\lim_{d,N\to\infty,d/N\to
c}\frac{Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}}{c}\Sigma_{trn}^{-2}\right)^{-2}\right)-\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})}{Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}}{c}\Sigma_{trn}^{-2}\right)^{-2}\right)}$
$\displaystyle\qquad+\lim_{d,N\to\infty,d/N\to
c}\frac{O\left(\frac{c\|\Sigma_{trn}\|_{F}^{2}}{N}\right)+o\left(c\right)}{\eta_{tst}^{2}Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}}{c}\Sigma_{trn}^{-2}\right)^{-2}\right)}$
$\displaystyle=\lim_{d,N\to\infty,d/N\to
c}\frac{Tr\left(\beta_{U}\beta_{U}^{T}\right)-\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T})}{Tr\left(\beta_{U}\beta_{U}^{T}\right)}+\lim_{d,N\to\infty,d/N\to
c}\frac{O\left(\frac{c\|\Sigma_{trn}\|_{F}^{2}}{N}\right)+o(1)}{\eta_{tst}^{2}Tr\left(\beta_{U}\beta_{U}^{T}\right)}$
$\displaystyle=1-\frac{c}{c-1}+\lim_{d,N\to\infty,d/N\to
c}O\left(\frac{\|\Sigma_{trn}\|_{F}^{2}}{N}\right)$
$\displaystyle=\begin{cases}\frac{1}{c-1}&;\|\Sigma_{trn}\|_{F}^{2}=o(N)\\\
\frac{1}{c-1}+k&;\|\Sigma_{trn}\|_{F}^{2}=\Theta(N)\end{cases}$

for some unknown problem-dependent constant $k$. This establishes the claim
for $c>1$, and the proof for when $c<1$ is analogous and in fact simpler.

∎

###  C.7 Proof for Corollary 6

See 6

###### Proof.

Follows immediately from Corollary 4. ∎

###  C.8 Proofs for Theorem 6, IID Training Data With Isotropic Covariance

See 6

###### Proof.

Then if $X_{trn}$ is the data matrix, the singular values squared for
$X_{trn}$ are the eigenvalues of

$X_{trn}^{T}X_{trn}=Z^{T}U^{T}UZ=Z^{T}Z$

Then $Z^{T}Z$ is a $N\times N$ matrix, and due to the normalization of the
variance of the entries, this is a Wishart Matrix. Further, we know that the
eigenvalue distribution can be approximated by the Marchenko Pastur
distribution with shape parameter $r/N$ Marcenko & Pastur (1967); Götze &
Tikhomirov (2011; 2003; 2004; 2005); Bai et al. (2003).

Then we have that for the $c<1$ case, we have the variance is

$\frac{1}{d}\frac{c}{1-c}\sum_{i=1}^{r}\frac{1}{c^{2}}\left(\frac{\sigma_{i}^{4}}{(\sigma_{i}^{2}+\sigma_{trn}^{2}/c)^{2}}+\frac{1}{\sigma_{trn}^{2}}\frac{\sigma_{i}^{2}}{(\sigma_{i}^{2}+\sigma_{trn}^{2})^{2}}\right)$

Then we simplify this as the following.

$\frac{r}{d}\frac{1}{c(1-c)}\left(\mathbb{E}\left[\frac{\sigma_{i}^{4}}{(\sigma_{i}^{2}+\sigma_{trn}^{2}/c)^{2}}\right]+\frac{1}{\sigma_{trn}^{2}}\mathbb{E}\left[\frac{\sigma_{i}^{2}}{(\sigma_{i}^{2}+\sigma_{trn}^{2})^{2}}\right]\right)$

If $\lambda$ is an eigenvalue of the training data gram matrix, then the
variance term of the generalization error has terms of the following form.

$\frac{\lambda^{2}}{(\lambda+1/c)^{2}},\quad\frac{\lambda}{(\lambda+1/c)^{2}},\quad\frac{\lambda}{\lambda+1}$

The value of these for the Marchenko Pastur distribution can be found in
Sonthalia et al. (2023).

$\mathbb{E}\left[\frac{\lambda}{\lambda+\eta_{trn}^{2}}\right]=\frac{1}{2}+\frac{1+\eta_{trn}^{2}c_{r}-\sqrt{(1-c_{r}+\eta_{trn}^{2}c_{r})^{2}+4c_{r}^{2}\eta_{trn}^{2}}}{2c_{r}}$
$\mathbb{E}\left[\frac{\lambda}{(\lambda+\eta_{trn}^{2})^{2}}\right]=\frac{1+c_{r}+\eta_{trn}^{2}c_{r}}{2\sqrt{(1-c_{r}+c_{r}\eta_{trn}^{2})^{2}+4c_{r}^{2}\eta_{trn}^{2}}}-\frac{1}{2}+o(1)$
$\mathbb{E}\left[\frac{\lambda^{2}}{(\lambda+\eta_{trn}^{2})^{2}}\right]=\mathbb{E}\left[\frac{\lambda}{\lambda+\eta_{trn}^{2}}\right]-\eta_{trn}^{2}\left(\mathbb{E}\left[\frac{\lambda}{(\lambda+\eta_{trn}^{2})^{2}}\right]\right)$

$c_{r}=r/N$

The proofs for the rest of the terms are similar. ∎

###  C.9 Proofs for Corollary 7, IID Training and Test Data With Isotropic
Covariance

See 7

###### Proof.

For the bias, we get

$\frac{\eta_{trn}^{4}}{N_{tst}}\frac{1}{c^{2}}\mathbb{E}\left[\frac{1}{(\sigma_{i}^{2}+\eta_{trn}^{2}/c)^{2}}\right]\|L\|_{F}^{2}$

The value of these for the Marchenko Pastur distribution can be found in
Sonthalia et al. (2023).

$\mathbb{E}\left[\frac{1}{(\lambda+\eta_{trn}^{2})^{2}}\right]=\frac{\eta_{trn}^{2}c_{r}^{2}+c_{r}^{2}+\eta_{trn}^{2}c_{r}-2c_{r}+1}{2\eta_{trn}^{4}c_{r}\sqrt{4\eta_{trn}^{2}c_{r}^{2}+(1-c_{r}+\eta_{trn}^{2}c_{r})^{2}}}+\frac{1}{2\eta_{trn}^{4}}\left(1-\frac{1}{c_{r}}\right)$

∎

##  Appendix D Numerical Details

In this section, we include the computational details required to reproduce
the data and figures in the paper. The code for the experiments can be found
in the following anonymized repository [Link].

##### Data

For our transfer learning results, we use real datasets namely CIFAR
Krizhevsky (2009), STL10 Coates et al. (2011) and SVHN Netzer et al. (2011).
We will mostly be working with the training and test split of CIFAR, training
split of STL10 and training split of SVHN. We will also use the test split of
STL10 for our data augmentation results, refer figure 8(h) and section D.3, to
avoid overlaps between training and test data.

To verify the application of our results to I.I.D. data, we generate datasets
from certain distributions, the details of which are presented in the upcoming
sections.

The test data is normalized so that each coordinate has mean zero and a
standard deviation of 5. This is done before we do any other pre-processing.

##### Compute Time

For figures 2, 1, 11 and 10, we use the same training data from CIFAR train
split. Thus, we combine our code implementation for these figures. This saves
up compute time for mean empirical error since inversion of the matrix
$X_{trn}+A_{trn}$, for obtaining $W_{opt}$, occurs once for each empirical run
for all 4 figures. The code was implemented using Google Colab with A100
Nvidia GPU which took approximately 1 hour for the 200 trials for each value
of r. Since the results are computed for 4 values of r, the entire experiment
was completed within approximately 4 hours.

Figures 8 and 8(h) took approximately 4 hours each using A100 Nvidia GPU on
Google Colab. Figures 5 and 6 were computed together in approximately 40
minutes. Figure 12 took approximately 1 hour to compute. Figure 13 only took
around 10 minutes due to less number of $N$ values and only 50 trials. All the
above was implemented using A100 GPU on Colab. Figure 2(c) took approximately
4.5 hours using T4 Nvidia GPU on Google Colab.

###  D.1 Principal Component Regression

We use four datasets for the set of results obtained through principal
component regression namely, CIFAR train split, CIFAR test split, STL10
dataset and SVHN dataset.

##### In-Subspace

For figure 2(a), the test data lies in the same low-dimensional subspace as
the training dataset. The experimental setting is as follows.

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 1050 and 10500 with an increment
of 550 for the results.

  * •

We project our training data over the first $r$ principal components where $r$
refers to the rank and varies as 25, 50, 100 and 150.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$.

  * •

We also project these test datasets onto the low-dimensional subspace using
the projection matrices.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

The theoretical error is calculated using the formula in Theorem 1 and the
empirical error is the mean squared error.

##### Out-of-Subspace

Next, we test our formulas for test datasets which lie outside the training
distribution space.

##### Small $\alpha$

We detail the numerical setup required to generate figure 2(b).

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 1050 and 10500 with an increment
of 550 for the results.

  * •

We project our training data over the first $r$ principal components where $r$
refers to the rank and varies as 25, 50, 100 and 150.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$.

  * •

We project these test datasets onto the low-dimensional subspace using the
projection matrices.

  * •

We add a small amount of full-dimensional Gaussian noise to the projected
datasets to generate out-of-subspace datasets with small $\alpha$. Here, we
consider the case where $\alpha=0.1$.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

The empirical error shown in figure 2(b) is the square root of the mean
squared error. The theoretical bounds on the error are calculated using
Theorem 2.

##### Large $\alpha$.

For figure 10, the experimental setup is as follows.

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 1050 and 10500 with an increment
of 550 for the results.

  * •

We project our training data over the first $r$ principal components where $r$
refers to the rank and varies as 25, 50, 100 and 150.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$.

  * •

We do not project these test datasets onto the low-dimensional subspace. We
retain their high dimensions. The values of $\alpha$ for different values of
$r$ are provided in figure 10.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

###  D.2 Linear Regression

To consider the linear regression case for figure 1,

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 1050 and 10500 with an increment
of 550 for the results.

  * •

We project our training data over the first $r$ principal components where $r$
refers to the rank and varies as 25, 50, 100 and 150.

  * •

Gaussian noise matrix with norm $\sqrt{N}$ is added to the training data.

  * •

We generate normally-distributed $\beta_{opt}$ of order $d\times 1$ with norm
1. The learned estimator is computed as $\beta^{T}=\beta_{opt}^{T}W$ where $W$
is the minimum norm solution to the least squares denoising problem. For
theoretical error, we compute $\hat{\beta}^{T}=\beta_{opt}U$.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$.

  * •

We also project these test datasets onto the low-dimensional subspace using
the projection matrices.

  * •

Gaussian noise matrix with norm $\sqrt{N_{tst}}$ is added to the test
datasets.

  * •

Finally, the test datasets, $X_{tst}$, are replaced with $\beta^{T}X_{tst}$ to
compute the error for the linear regression problem.

###  D.3 Data Augmentation

To emphasize the application of our results to non-I.I.D. data, we consider
two cases of data augmentation to our training data.

##### Without Independence

The experimental setting to obtain the empirical generalization error is as
follows.

  * •

We sample 1000 images from the CIFAR train split as the first batch of our
training data. For experimental results

  * •

We augment the above batch with the same batch to vary $N$ between 1000 and
6000 with an increment of 1000. We project the dataset onto its first $r$
principal components where $r=25,50,100$ and 150.

  * •

We add gaussian noise with norm $\sqrt{N}$ to the training data as before.
Note that the noise on augmented batches would be independent of the noise in
the original batch. This is the only assumption required for our result.

  * •

Test datasets, of order $d\times N_{tst}$, sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$ are
also projected onto the low-dimensional subspace.

We calculate the theoretical generalization error for more values of $c$ to
obtain smoother curves. Note that the left singular vectors i.e., the columns
of matrix $U$, do not change when we augment our training batches. We utilize
this to speed-up our computation for theoretical curves.

  * •

We sample 1000 images from the CIFAR train split as the first batch of our
training data.

  * •

We obtain the projection matrix $P=UU^{T}$ and the matrix $L=U^{T}X_{tst}$
from the SVD of the first batch itself.

  * •

The generalization error is computed from the formula in Theorem 1 for values
of $N$ between 1000 and 6000 with an increment of 50.

  * •

We scale the singular values by a factor of $\nicefrac{{N}}{{1000}}$ to
account for the augmenting.

##### Without Identicality

To generate figure 8(h),

  * •

We use training data, of order $d\times N$, such that $d=3072$ and N ranges
between 1050 and 10500 with an increment of 550 for the results.

  * •

We use $N/2$ images from the CIFAR training split and $N/2$ images from the
STL10 training split concatenated together for our training data.

  * •

We project our training data over the first $r$ principal components where $r$
refers to the rank and varies as 25, 50, 100 and 150.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 test split and SVHN train split where $d=3072$ and $N_{tst}=2500$. This
is done to avoid any overlaps between training and test data.

  * •

We also project these test datasets onto the low-dimensional subspace using
the projection matrices.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

###  D.4 I.I.D. Data

We also perform experiments to verify our results in cases where training and
test datasets are I.I.D. The numerical details for those experiments are
presented in this section.

##### I.I.D. Test Data

To generate figure 11,

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 1050 and 10500 with an increment
of 550 for the results.

  * •

We project our training data over the first $r$ principal components where $r$
refers to the rank and varies as 25, 50, 100 and 150.

  * •

We generate $L$ from Gaussian distribution of norm $\sqrt{N_{tst}}$ where
$N_{tst}=2500$.

  * •

We obtain our I.I.D. test data of order $d\times N_{tst}$ as $X_{tst}=UL$
where $U$ contains the left singular vectors of the projected training data.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

##### I.I.D. Train Data

To generate figure 12,

  * •

We generate the left singular matrix $U$ from the SVD of a Gaussian matrix of
order $d\times r$ where $M=3072$ and $r=50$.

  * •

We generate the training matrix $X_{trn}=UZ$ where $Z$ is of order $r\times N$
such that each column is normally distributed with mean 0 and variance $1/r$.

  * •

Here, $N$ varies from 1050 to 10500 with an increment of 550.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$.

  * •

We also project these test datasets onto the $r$-dimensional subspace using
projection matrices.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

##### I.I.D Train and Test Data

To generate figure 13,

  * •

We generate the left singular matrix $U$ from the SVD of a Gaussian matrix of
order $d\times r$ where $M=3072$ and $r=50$.

  * •

We generate the training matrix $X_{trn}=UZ$ where $Z$ is of order $r\times N$
such that each column is normally distributed with mean 0 and variance $1/r$.

  * •

Here, $N$ varies from 500 to 6010 with an increment of 550 for the empirical
markers and with an increment of 55 for theoretical values on the solid curve.

  * •

We generate $L$ from Gaussian distribution of norm $\sqrt{N_{tst}}$ where
$N_{tst}=5000$.

  * •

We obtain our I.I.D. test data of order $d\times N_{tst}$ as $X_{tst}=UL$
where $U$ contains the left singular vectors of the projected training data.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

###  D.5 Full Dimensional Denoising

To generate figure 2(c),

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 1050 and 10500 with an increment
of 550 for the results.

  * •

We project our training data over the first $r$ principal components where $r$
is the minimum of $d$ and $N$. This implies that the data is full dimensional.

  * •

Test datasets, of order $d\times N_{tst}$, are sampled from CIFAR test split,
STL10 train split and SVHN train split where $d=3072$ and $N_{tst}=2500$.

  * •

We also project these test datasets onto the low-dimensional subspace using
the projection matrices.

  * •

For denoising, we generate Gaussian noise matrix $A_{trn}$ with norm
$\sqrt{N}$ for the training data and $A_{tst}$ with norm $\sqrt{N_{tst}}$ for
the test datasets.

###  D.6 Optimal $\eta_{trn}$

To generate figures 5 and 6,

  * •

Training data, of order $d\times N$, is sampled from flattened CIFAR train
split such that $d=3072$ and N ranges between 500 and 5500 as {500, 750, 1000,
1250, 1500, 1750, 2000, 2250, 2500, 2600, 2700, 2800, 2900, 3000, 3020, 3130,
3200, 3300, 3400, 3500, 3750, 4000, 4250, 4500, 4750, 5000, 5250, 5500}.

  * •

We project our training data over the first $r$ principal components where
$r=50$.

  * •

Test datasets, of order $d\times N_{tst}$, are the training dataset with new
noise and sampled from CIFAR test split, STL10 train split and SVHN train
split where $d=3072$ and $N_{tst}=N$.

  * •

We compute generalization error for 2000 $\eta_{trn}$ values ranging from
1/3.5 to 100 for each $N$ from our formula in Theorem 1.

  * •

We report the optimal $\eta_{trn}$ found to minimise the generalization error
in figure 5 and the optimal generalization error in figure 6.