---
OA_place: publisher
OA_type: gold
_id: '21324'
abstract:
- lang: eng
text: Learning models have been shown to rely on spurious correlations between non-predictive
features and the associated labels in the training data, with negative implications
on robustness, bias and fairness. In this work, we provide a statistical characterization
of this phenomenon for high-dimensional regression, when the data contains a predictive
core feature x and a spurious feature y. Specifically, we quantify the amount
of spurious correlations C learned via linear regression, in terms of the data
covariance and the strength λ of the ridge regularization. As a consequence, we
first capture the simplicity of y through the spectrum of its covariance, and
its correlation with x through the Schur complement of the full data covariance.
Next, we prove a trade-off between C and the in-distribution test loss L, by showing
that the value of λ that minimizes L lies in an interval where C is increasing.
Finally, we investigate the effects of over-parameterization via the random features
model, by showing its equivalence to regularized linear regression. Our theoretical
results are supported by numerical experiments on Gaussian, Color-MNIST, and CIFAR-10
datasets.
acknowledgement: Marco Mondelli is funded by the European Union (ERC, INF2, project
number 101161364). Views and opinions expressed are however those of the author(s)
only and do not necessarily reflect those of the European Union or the European
Research Council Executive Agency. Neither the European Union nor the granting authority
can be held responsible for them. Simone Bombari is supported by a Google PhD fellowship.
The authors would like to thank GuanWen Qiu for helpful discussions.
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Simone
full_name: Bombari, Simone
id: ca726dda-de17-11ea-bc14-f9da834f63aa
last_name: Bombari
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Bombari S, Mondelli M. Spurious correlations in high dimensional regression:
The roles of regularization, simplicity bias and over-parameterization. In: Proceedings
of the 42nd International Conference on Machine Learning. Vol 267. ML Research
Press; 2025:4839-4873.'
apa: 'Bombari, S., & Mondelli, M. (2025). Spurious correlations in high dimensional
regression: The roles of regularization, simplicity bias and over-parameterization.
In Proceedings of the 42nd International Conference on Machine Learning
(Vol. 267, pp. 4839–4873). Vancouver, Canada: ML Research Press.'
chicago: 'Bombari, Simone, and Marco Mondelli. “Spurious Correlations in High Dimensional
Regression: The Roles of Regularization, Simplicity Bias and over-Parameterization.”
In Proceedings of the 42nd International Conference on Machine Learning,
267:4839–73. ML Research Press, 2025.'
ieee: 'S. Bombari and M. Mondelli, “Spurious correlations in high dimensional regression:
The roles of regularization, simplicity bias and over-parameterization,” in Proceedings
of the 42nd International Conference on Machine Learning, Vancouver, Canada,
2025, vol. 267, pp. 4839–4873.'
ista: 'Bombari S, Mondelli M. 2025. Spurious correlations in high dimensional regression:
The roles of regularization, simplicity bias and over-parameterization. Proceedings
of the 42nd International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 267, 4839–4873.'
mla: 'Bombari, Simone, and Marco Mondelli. “Spurious Correlations in High Dimensional
Regression: The Roles of Regularization, Simplicity Bias and over-Parameterization.”
Proceedings of the 42nd International Conference on Machine Learning, vol.
267, ML Research Press, 2025, pp. 4839–73.'
short: S. Bombari, M. Mondelli, in:, Proceedings of the 42nd International Conference
on Machine Learning, ML Research Press, 2025, pp. 4839–4873.
conference:
end_date: 2025-07-19
location: Vancouver, Canada
name: 'ICML: International Conference on Machine Learning'
start_date: 2025-07-13
corr_author: '1'
date_created: 2026-02-18T11:58:00Z
date_published: 2025-07-30T00:00:00Z
date_updated: 2026-02-19T08:08:55Z
day: '30'
ddc:
- '000'
department:
- _id: MaMo
external_id:
arxiv:
- '2502.01347'
file:
- access_level: open_access
checksum: d4ba4f7717b362ca38878f45e57bd643
content_type: application/pdf
creator: dernst
date_created: 2026-02-19T08:04:38Z
date_updated: 2026-02-19T08:04:38Z
file_id: '21335'
file_name: 2025_ICML_Bombari.pdf
file_size: 887526
relation: main_file
success: 1
file_date_updated: 2026-02-19T08:04:38Z
has_accepted_license: '1'
intvolume: ' 267'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 4839-4873
project:
- _id: 911e6d1f-16d5-11f0-9cad-c5c68c6a1cdf
grant_number: '101161364'
name: 'Inference in High Dimensions: Light-speed Algorithms and Information Limits'
- _id: 92099302-16d5-11f0-9cad-f9a785f54fbd
name: 'Trustworthy Deep Learning Theory: Private Over-Parameterized Models and Robust
LLMs'
publication: Proceedings of the 42nd International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: 'Spurious correlations in high dimensional regression: The roles of regularization,
simplicity bias and over-parameterization'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 267
year: '2025'
...
---
APC_amount: 2754,32 EUR
OA_place: publisher
OA_type: hybrid
_id: '19627'
abstract:
- lang: eng
text: Differentially private gradient descent (DP-GD) is a popular algorithm to
train deep learning models with provable guarantees on the privacy of the training
data. In the last decade, the problem of understanding its performance cost with
respect to standard GD has received remarkable attention from the research community,
which formally derived upper bounds on the excess population risk RP in different
learning settings. However, existing bounds typically degrade with over-parameterization,
i.e., as the number of parameters p gets larger than the number of training
samples n -- a regime which is ubiquitous in current deep-learning practice.
As a result, the lack of theoretical insights leaves practitioners without clear
guidance, leading some to reduce the effective number of trainable parameters
to improve performance, while others use larger models to achieve better results
through scale. In this work, we show that in the popular random features model
with quadratic loss, for any sufficiently large p , privacy can be obtained for
free, i.e., |RP|=o(1) , not only when the privacy parameter ε has constant
order, but also in the strongly private setting ε=o(1) . This challenges the
common wisdom that over-parameterization inherently hinders performance in private
learning.
acknowledgement: This research was funded in whole, or in part, by the Austrian Science
Fund (FWF) Grant number COE 12. For the purpose of open access, the author has applied
a CC BY public copyright license to any Author Accepted Manuscript version arising
from this submission. The authors were also supported by the 2019 Lopez-Loreta prize,
and Simone Bombari was supported by a Google PhD fellowship. We thank Diyuan Wu,
Edwige Cyffers, Francesco Pedrotti, Inbar Seroussi, Nikita P. Kalinin, Pietro Pelliconi,
Roodabeh Safavi, Yizhe Zhu, and Zhichao Wang for helpful discussions.
article_number: e2423072122
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Simone
full_name: Bombari, Simone
id: ca726dda-de17-11ea-bc14-f9da834f63aa
last_name: Bombari
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Bombari S, Mondelli M. Privacy for free in the overparameterized regime. Proceedings
of the National Academy of Sciences. 2025;122(15). doi:10.1073/pnas.2423072122
apa: Bombari, S., & Mondelli, M. (2025). Privacy for free in the overparameterized
regime. Proceedings of the National Academy of Sciences. National Academy
of Sciences. https://doi.org/10.1073/pnas.2423072122
chicago: Bombari, Simone, and Marco Mondelli. “Privacy for Free in the Overparameterized
Regime.” Proceedings of the National Academy of Sciences. National Academy
of Sciences, 2025. https://doi.org/10.1073/pnas.2423072122.
ieee: S. Bombari and M. Mondelli, “Privacy for free in the overparameterized regime,”
Proceedings of the National Academy of Sciences, vol. 122, no. 15. National
Academy of Sciences, 2025.
ista: Bombari S, Mondelli M. 2025. Privacy for free in the overparameterized regime.
Proceedings of the National Academy of Sciences. 122(15), e2423072122.
mla: Bombari, Simone, and Marco Mondelli. “Privacy for Free in the Overparameterized
Regime.” Proceedings of the National Academy of Sciences, vol. 122, no.
15, e2423072122, National Academy of Sciences, 2025, doi:10.1073/pnas.2423072122.
short: S. Bombari, M. Mondelli, Proceedings of the National Academy of Sciences
122 (2025).
corr_author: '1'
date_created: 2025-04-27T22:02:13Z
date_published: 2025-04-15T00:00:00Z
date_updated: 2026-05-20T08:23:19Z
day: '15'
ddc:
- '000'
department:
- _id: MaMo
doi: 10.1073/pnas.2423072122
external_id:
arxiv:
- '2410.14787'
isi:
- '001471214000001'
pmid:
- '40215275'
file:
- access_level: open_access
checksum: 1ac6f78e368d35a0cafb4d2d9bd63443
content_type: application/pdf
creator: dernst
date_created: 2025-05-05T07:27:54Z
date_updated: 2025-05-05T07:27:54Z
file_id: '19648'
file_name: 2025_PNAS_Bombari.pdf
file_size: 2328320
relation: main_file
success: 1
file_date_updated: 2025-05-05T07:27:54Z
has_accepted_license: '1'
intvolume: ' 122'
isi: 1
issue: '15'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
- _id: 92099302-16d5-11f0-9cad-f9a785f54fbd
name: 'Trustworthy Deep Learning Theory: Private Over-Parameterized Models and Robust
LLMs'
publication: Proceedings of the National Academy of Sciences
publication_identifier:
eissn:
- 1091-6490
issn:
- 0027-8424
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Privacy for free in the overparameterized regime
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 122
year: '2025'
...