I am an ETH AI Center Doctoral Fellow. My research interest is in High-Dimensional Statistics and more generally in the combination of Mathematics & Machine Learning. I’m part of the groups led by Fanny Yang and Afonso Bandeira.
Papers
-
Fast rates for noisy interpolation require rethinking the effects of inductive bias
Konstantin Donhauser,
Nicolo Ruggeri,
Stefan Stojanovic,
and Fanny Yang
International Conference on Machine Learning (ICML),
2022
Good generalization performance on high-dimensional data crucially hinges on a simple structure of the ground truth and a corresponding strong inductive bias of the estimator. Even though this intuition is valid for regularized models, in this paper we caution against a strong inductive bias for interpolation in the presence of noise: Our results suggest that, while a stronger inductive bias encourages a simpler structure that is more aligned with the ground truth, it also increases the detrimental effect of noise. Specifically, for both linear regression and classification with a sparse ground truth, we prove that minimum \ell_p-norm and maximum \ell_p-margin interpolators achieve fast polynomial rates up to order 1/n for p > 1 compared to a logarithmic rate for p = 1. Finally, we provide experimental evidence that this trade-off may also play a crucial role in understanding non-linear interpolating models used in practice.
-
Tight bounds for minimum l1-norm interpolation of noisy data
Guillaume Wang*,
Konstantin Donhauser*,
and Fanny Yang
International Conference on Artificial Intelligence and Statistics (AISTATS),
2022
We provide matching upper and lower bounds of order σ2/log(d/n) for the prediction error of the minimum ℓ1-norm interpolator, a.k.a. basis pursuit. Our result is tight up to negligible terms when d≫n, and is the first to imply asymptotic consistency of noisy minimum-norm interpolation for isotropic features and sparse ground truths. Our work complements the literature on "benign overfitting" for minimum ℓ2-norm interpolation, where asymptotic consistency can be achieved only when the features are effectively low-dimensional.
-
How rotational invariance of common kernels prevents generalization in high dimensions
Konstantin Donhauser,
Mingqi Wu,
and Fanny Yang
International Conference on Machine Learning (ICML),
2021
Kernel ridge regression is well-known to achieve minimax optimal rates in low-dimensional settings. However, its behavior in high dimensions is much less understood. Recent work establishes consistency for high-dimensional kernel regression for a number of specific assumptions on the data distribution. In this paper, we show that in high dimensions, the rotational invariance property of commonly studied kernels (such as RBF, inner product kernels and fully-connected NTK of any depth) leads to inconsistent estimation unless the ground truth is a low-degree polynomial. Our lower bound on the generalization error holds for a wide range of distributions and kernels with different eigenvalue decays. This lower bound suggests that consistency results for kernel ridge regression in high dimensions generally require a more refined analysis that depends on the structure of the kernel beyond its eigenvalue decay.
-
Interpolation can hurt robust generalization even when there is no noise
Konstantin Donhauser*,
Alexandru Tifrea*,
Michael Aerni,
Reinhard Heckel,
and Fanny Yang
Neural Information Processing Systems (NeurIPS),
2021
Numerous recent works show that overparameterization implicitly reduces variance for min-norm interpolators and max-margin classifiers. These findings suggest that ridge regularization has vanishing benefits in high dimensions. We challenge this narrative by showing that, even in the absence of noise, avoiding interpolation through ridge regularization can significantly improve generalization. We prove this phenomenon for the robust risk of both linear regression and classification and hence provide the first theoretical result on robust overfitting.
Preprints
Blog posts
There will be hopefully soon some blog posts.
Short C.V.
04/2021 - |
PhD, ETH Zurich |
10/2018 - 3/2021 |
Research Intern - SML Group, ETH Zurich |
1/2018 - 6/2020 |
M.Sc. Electrical Engineering, ETH Zurich |
10/2017 - 6/2020 |
B.Sc. Mathematics, ETH Zurich |
10/2014 - 4/2018 | B.Sc. Electrical Engineering, ETH Zurich |
You can find me on find me Linkedin, Twitter and Google Scholar or just simply write me an Email via konstantin.donhauser [at] ai.ethz.ch or