Sara van de Geer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sara van de Geer has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Peter Bühlmann
Seminar for Statistics, ETH Zurich
16 shared publications - Alexandre B. Tsybakov
CREST-ENSAE
3 shared publications - Andreas Elsener
ETH Zürich, Seminar für Statistik
3 shared publications - Jon A. Wellner
University of Washington
3 shared publications - Karim Lounici
Statistical Laboratory University of Cambridge Cambridge UK
3 shared publications - Massimiliano Pontil
University College London
3 shared publications
Latest Publications
- Open Access
Entropy bounds for the absolute convex hull of tensors
We derive entropy bounds for the absolute convex hull of vectors $X= (x_1 , \ldots , x_p)\in \mathbb{R}^{n \times p} $ in $\mathbb{R}^n$ and apply this to the case where $X$ is the $d$-fold tensor matrix $$X = \underbrace{Ψ\otimes \cdots \otimes Ψ}_{d \ {\rm times} }\in \mathbb{R}^{m^d \times r^d },$$ with a given $Ψ= ( ψ_1 , \ldots , ψ_r ) \in \mathbb{R}^{m \times r} $, normalized to that $ \| ψ_j \|_2 \le 1$ for all $j \in \{1 , \ldots , r\}$. For $ε>0$ we let ${\cal V} \subset \mathbb{R}^m$ be the linear space with smallest dimension $M ( ε, Ψ)$ such that $ \max_{1 \le j \le r } \min_{v \in {\cal V} } \| ψ_j - v \|_2 \le ε$. We call $M( ε, ψ)$ the $ε$-approximation of $Ψ$ and assume it is -- up to log terms -- polynomial in $ε$. We show that the entropy of the absolute convex hull of the $d$-fold tensor matrix $X$ is up to log-terms of the same order as the entropy for the case $d=1$. The results are generalized to absolute convex hulls of tensors of functions in $L_2 (μ)$ where $μ$ is Lebesgue measure on $[0,1]$. As an application we consider the space of functions on $[0,1]^d$ with bounded $q$-th order Vitali total variation for a given $q \in \mathbb{N}$. As a by-product, we construct an orthonormal, piecewise polynomial, wavelet dictionary for functions that are well-approximated by piecewise polynomials.Open AccessEntropy bounds for the absolute convex hull of tensors
We derive entropy bounds for the absolute convex hull of vectors $X= (x_1 , \ldots , x_p)\in \mathbb{R}^{n \times p} $ in $\mathbb{R}^n$ and apply this to the case where $X$ is the $d$-fold tensor matrix $$X = \underbrace{Ψ\otimes \cdots \otimes Ψ}_{d \ {\rm times} }\in \mathbb{R}^{m^d \times r^d },$$ with a given $Ψ= ( ψ_1 , \ldots , ψ_r ) \in \mathbb{R}^{m \times r} $, normalized to that $ \| ψ_j \|_2 \le 1$ for all $j \in \{1 , \ldots , r\}$. For $ε>0$ we let ${\cal V} \subset \mathbb{R}^m$ be the linear space with smallest dimension $M ( ε, Ψ)$ such that $ \max_{1 \le j \le r } \min_{v \in {\cal V} } \| ψ_j - v \|_2 \le ε$. We call $M( ε, ψ)$ the $ε$-approximation of $Ψ$ and assume it is -- up to log terms -- polynomial in $ε$. We show that the entropy of the absolute convex hull of the $d$-fold tensor matrix $X$ is up to log-terms of the same order as the entropy for the case $d=1$. The results are generalized to absolute convex hulls of tensors of functions in $L_2 (μ)$ where $μ$ is Lebesgue measure on $[0,1]$. As an application we consider the space of functions on $[0,1]^d$ with bounded $q$-th order Vitali total variation for a given $q \in \mathbb{N}$. As a by-product, we construct an orthonormal, piecewise polynomial, wavelet dictionary for functions that are well-approximated by piecewise polynomials. - 17 July 2023
- Published by Springer Nature
- p. 163-195
The Lasso with Structured Design and Entropy of (Absolute) Convex Hulls
- 17 July 2023
- Published by Springer Nature
- p. 163-195
The Lasso with Structured Design and Entropy of (Absolute) Convex Hulls
- Open Access
AdaBoost and robust one-bit compressed sensing
This paper studies binary classification in robust one-bit compressed sensing with adversarial errors. It is assumed that the model is overparameterized and that the parameter of interest is effectively sparse. AdaBoost is considered, and, through its relation to the max-$\ell_1$-margin-classifier, prediction error bounds are derived. The developed theory is general and allows for heavy-tailed feature distributions, requiring only a weak moment assumption and an anti-concentration condition. Improved convergence rates are shown when the features satisfy a small deviation lower bound. In particular, the results provide an explanation why interpolating adversarial noise can be harmless for classification problems. Simulations illustrate the presented theory.
Open AccessAdaBoost and robust one-bit compressed sensing
This paper studies binary classification in robust one-bit compressed sensing with adversarial errors. It is assumed that the model is overparameterized and that the parameter of interest is effectively sparse. AdaBoost is considered, and, through its relation to the max-$\ell_1$-margin-classifier, prediction error bounds are derived. The developed theory is general and allows for heavy-tailed feature distributions, requiring only a weak moment assumption and an anti-concentration condition. Improved convergence rates are shown when the features satisfy a small deviation lower bound. In particular, the results provide an explanation why interpolating adversarial noise can be harmless for classification problems. Simulations illustrate the presented theory.
- Open Access
On the robustness of minimum norm interpolators and regularized empirical risk minimizers
This article develops a general theory for minimum norm interpolating estimators and regularized empirical risk minimizers (RERM) in linear models in the presence of additive, potentially adversarial, errors. In particular, no conditions on the errors are imposed. A quantitative bound for the prediction error is given, relating it to the Rademacher complexity of the covariates, the norm of the minimum norm interpolator of the errors and the size of the subdifferential around the true parameter. The general theory is illustrated for Gaussian features and several norms: The $\ell_1$, $\ell_2$, group Lasso and nuclear norms. In case of sparsity or low-rank inducing norms, minimum norm interpolators and RERM yield a prediction error of the order of the average noise level, provided that the overparameterization is at least a logarithmic factor larger than the number of samples and that, in case of RERM, the regularization parameter is small enough. Lower bounds that show near optimality of the results complement the analysis.Open AccessOn the robustness of minimum norm interpolators and regularized empirical risk minimizers
This article develops a general theory for minimum norm interpolating estimators and regularized empirical risk minimizers (RERM) in linear models in the presence of additive, potentially adversarial, errors. In particular, no conditions on the errors are imposed. A quantitative bound for the prediction error is given, relating it to the Rademacher complexity of the covariates, the norm of the minimum norm interpolator of the errors and the size of the subdifferential around the true parameter. The general theory is illustrated for Gaussian features and several norms: The $\ell_1$, $\ell_2$, group Lasso and nuclear norms. In case of sparsity or low-rank inducing norms, minimum norm interpolators and RERM yield a prediction error of the order of the average noise level, provided that the overparameterization is at least a logarithmic factor larger than the number of samples and that, in case of RERM, the regularization parameter is small enough. Lower bounds that show near optimality of the results complement the analysis. - 16 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (4) , 2507-2527
De-Biased Sparse PCA: Inference for Eigenstructure of Large Covariance Matrices
Sparse principal component analysis has become one of the most widely used techniques for dimensionality reduction in high-dimensional datasets. While many methods are available for point estimation of eigenstructure in high-dimensional settings, in this paper we propose methodology for uncertainty quantification, such as construction of confidence intervals and tests for the principal eigenvector and the corresponding largest eigenvalue. We base our methodology on an M-estimator with Lasso penalty which achieves minimax optimal rates and is used to construct a de-biased sparse PCA estimator. The novel estimator has a Gaussian limiting distribution and can be used for hypothesis testing or support recovery of the first eigenvector. The empirical performance of the new estimator is demonstrated on synthetic data and we also show that the estimator compares favourably with the classical PCA in moderately high-dimensional regimes.
- 16 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (4) , 2507-2527
De-Biased Sparse PCA: Inference for Eigenstructure of Large Covariance Matrices
Sparse principal component analysis has become one of the most widely used techniques for dimensionality reduction in high-dimensional datasets. While many methods are available for point estimation of eigenstructure in high-dimensional settings, in this paper we propose methodology for uncertainty quantification, such as construction of confidence intervals and tests for the principal eigenvector and the corresponding largest eigenvalue. We base our methodology on an M-estimator with Lasso penalty which achieves minimax optimal rates and is used to construct a de-biased sparse PCA estimator. The novel estimator has a Gaussian limiting distribution and can be used for hypothesis testing or support recovery of the first eigenvector. The empirical performance of the new estimator is demonstrated on synthetic data and we also show that the estimator compares favourably with the classical PCA in moderately high-dimensional regimes.
- Open Access
Convergence rates for Penalised Least Squares Estimators in PDE-constrained regression problems
We consider PDE constrained nonparametric regression problems in which the parameter $f$ is the unknown coefficient function of a second order elliptic partial differential operator $L_f$, and the unique solution $u_f$ of the boundary value problem \[L_fu=g_1\text{ on } \mathcal O, \quad u=g_2 \text{ on }\partial \mathcal O,\] is observed corrupted by additive Gaussian white noise. Here $\mathcal O$ is a bounded domain in $\mathbb R^d$ with smooth boundary $\partial \mathcal O$, and $g_1, g_2$ are given functions defined on $\mathcal O, \partial \mathcal O$, respectively. Concrete examples include $L_fu=\Delta u-2fu$ (Schr\"odinger equation with attenuation potential $f$) and $L_fu=\text{div} (f\nabla u)$ (divergence form equation with conductivity $f$). In both cases, the parameter space \[\mathcal F=\{f\in H^\alpha(\mathcal O)| f > 0\}, ~\alpha>0, \] where $H^\alpha(\mathcal O)$ is the usual order $\alpha$ Sobolev space, induces a set of non-linearly constrained regression functions $\{u_f: f \in \mathcal F\}$. We study Tikhonov-type penalised least squares estimators $\hat f$ for $f$. The penalty functionals are of squared Sobolev-norm type and thus $\hat f$ can also be interpreted as a Bayesian `MAP'-estimator corresponding to some Gaussian process prior. We derive rates of convergence of $\hat f$ and of $u_{\hat f}$, to $f, u_f$, respectively. We prove that the rates obtained are minimax-optimal in prediction loss. Our bounds are derived from a general convergence rate result for non-linear inverse problems whose forward map satisfies a modulus of continuity condition, a result of independent interest that is applicable also to linear inverse problems, illustrated in an example with the Radon transform.Open AccessConvergence rates for Penalised Least Squares Estimators in PDE-constrained regression problems
We consider PDE constrained nonparametric regression problems in which the parameter $f$ is the unknown coefficient function of a second order elliptic partial differential operator $L_f$, and the unique solution $u_f$ of the boundary value problem \[L_fu=g_1\text{ on } \mathcal O, \quad u=g_2 \text{ on }\partial \mathcal O,\] is observed corrupted by additive Gaussian white noise. Here $\mathcal O$ is a bounded domain in $\mathbb R^d$ with smooth boundary $\partial \mathcal O$, and $g_1, g_2$ are given functions defined on $\mathcal O, \partial \mathcal O$, respectively. Concrete examples include $L_fu=\Delta u-2fu$ (Schr\"odinger equation with attenuation potential $f$) and $L_fu=\text{div} (f\nabla u)$ (divergence form equation with conductivity $f$). In both cases, the parameter space \[\mathcal F=\{f\in H^\alpha(\mathcal O)| f > 0\}, ~\alpha>0, \] where $H^\alpha(\mathcal O)$ is the usual order $\alpha$ Sobolev space, induces a set of non-linearly constrained regression functions $\{u_f: f \in \mathcal F\}$. We study Tikhonov-type penalised least squares estimators $\hat f$ for $f$. The penalty functionals are of squared Sobolev-norm type and thus $\hat f$ can also be interpreted as a Bayesian `MAP'-estimator corresponding to some Gaussian process prior. We derive rates of convergence of $\hat f$ and of $u_{\hat f}$, to $f, u_f$, respectively. We prove that the rates obtained are minimax-optimal in prediction loss. Our bounds are derived from a general convergence rate result for non-linear inverse problems whose forward map satisfies a modulus of continuity condition, a result of independent interest that is applicable also to linear inverse problems, illustrated in an example with the Radon transform. - Open Access
Oracle inequalities for square root analysis estimators with application to total variation penalties
Through the direct study of the analysis estimator we derive oracle inequalities with fast and slow rates by adapting the arguments involving projections by Dalalyan, Hebiri and Lederer (2017). We then extend the theory to the square root analysis estimator. Finally, we focus on (square root) total variation regularized estimators on graphs and obtain constant-friendly rates, which, up to log-terms, match previous results obtained by entropy calculations. We also obtain an oracle inequality for the (square root) total variation regularized estimator over the cycle graph.
Open AccessOracle inequalities for square root analysis estimators with application to total variation penalties
Through the direct study of the analysis estimator we derive oracle inequalities with fast and slow rates by adapting the arguments involving projections by Dalalyan, Hebiri and Lederer (2017). We then extend the theory to the square root analysis estimator. Finally, we focus on (square root) total variation regularized estimators on graphs and obtain constant-friendly rates, which, up to log-terms, match previous results obtained by entropy calculations. We also obtain an oracle inequality for the (square root) total variation regularized estimator over the cycle graph.
- 8 July 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (11) , 7304-7324
A Framework for the Construction of Upper Bounds on the Number of Affine Linear Regions of ReLU Feed-Forward Neural Networks
We present a framework to derive upper bounds on the number of regions that feed-forward neural networks with ReLU activation functions are affine linear on. It is based on an inductive analysis that keeps track of the number of such regions per dimensionality of their images within the layers. More precisely, the information about the number regions per dimensionality is pushed through the layers starting with one region of the input dimension of the neural network and using a recursion based on an analysis of how many regions per output dimensionality a subsequent layer with a certain width can induce on an input region with a given dimensionality. The final bound on the number of regions depends on the number and widths of the layers of the neural network and on some additional parameters that were used for the recursion. It is stated in terms of the L1-norm of the last column of a product of matrices and provides a unifying treatment of several previously known bounds: Depending on the choice of the recursion parameters that determine these matrices, it is possible to obtain the bounds from Mont4ufar 1 (2014), 2 (2017) and Serra et. al. 3 (2017) as special cases. For the latter, which is the strongest of these bounds, the formulation in terms of matrices provides new insight. In particular, by using explicit formulas for a Jordan-like decomposition of the involved matrices, we achieve new tighter results for the asymptotic setting, where the number of layers of the same fixed width tends to infinity.
- 8 July 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (11) , 7304-7324
A Framework for the Construction of Upper Bounds on the Number of Affine Linear Regions of ReLU Feed-Forward Neural Networks
We present a framework to derive upper bounds on the number of regions that feed-forward neural networks with ReLU activation functions are affine linear on. It is based on an inductive analysis that keeps track of the number of such regions per dimensionality of their images within the layers. More precisely, the information about the number regions per dimensionality is pushed through the layers starting with one region of the input dimension of the neural network and using a recursion based on an analysis of how many regions per output dimensionality a subsequent layer with a certain width can induce on an input region with a given dimensionality. The final bound on the number of regions depends on the number and widths of the layers of the neural network and on some additional parameters that were used for the recursion. It is stated in terms of the L1-norm of the last column of a product of matrices and provides a unifying treatment of several previously known bounds: Depending on the choice of the recursion parameters that determine these matrices, it is possible to obtain the bounds from Mont4ufar 1 (2014), 2 (2017) and Serra et. al. 3 (2017) as special cases. For the latter, which is the strongest of these bounds, the formulation in terms of matrices provides new insight. In particular, by using explicit formulas for a Jordan-like decomposition of the involved matrices, we achieve new tighter results for the asymptotic setting, where the number of layers of the same fixed width tends to infinity.
- Open Access
Synthesis and analysis in total variation regularization
We generalize the bridge between analysis and synthesis estimators by Elad, Milanfar and Rubinstein (2007) to rank deficient cases. This is a starting point for the study of the connection between analysis and synthesis for total variation regularized estimators. In particular, the case of first order total variation regularized estimators over general graphs and their synthesis form are studied. We give a definition of the discrete graph derivative operator based on the notion of line graph and provide examples of the synthesis form of $k^{\text{th}}$ order total variation regularized estimators over a range of graphs.Open AccessSynthesis and analysis in total variation regularization
We generalize the bridge between analysis and synthesis estimators by Elad, Milanfar and Rubinstein (2007) to rank deficient cases. This is a starting point for the study of the connection between analysis and synthesis for total variation regularized estimators. In particular, the case of first order total variation regularized estimators over general graphs and their synthesis form are studied. We give a definition of the discrete graph derivative operator based on the notion of line graph and provide examples of the synthesis form of $k^{\text{th}}$ order total variation regularized estimators over a range of graphs. - 6 August 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (3) , 1452-1472
Sharp Oracle Inequalities for Stationary Points of Nonconvex Penalized M-Estimators
Many statistical estimation procedures lead to nonconvex optimization problems. Algorithms to solve these are often guaranteed to output a stationary point of the optimization problem. Oracle inequalities are an important theoretical instrument to assess the statistical performance of an estimator. Oracle results have focused on the theoretical properties of the uncomputable (global) minimum or maximum. In the present work a general framework used for convex optimization problems to derive oracle inequalities for stationary points is extended. A main new ingredient of these oracle inequalities is that they are sharp: they show closeness to the best approximation within the model plus a remainder term. We apply this framework to different estimation problems.
- 6 August 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (3) , 1452-1472
Sharp Oracle Inequalities for Stationary Points of Nonconvex Penalized M-Estimators
Many statistical estimation procedures lead to nonconvex optimization problems. Algorithms to solve these are often guaranteed to output a stationary point of the optimization problem. Oracle inequalities are an important theoretical instrument to assess the statistical performance of an estimator. Oracle results have focused on the theoretical properties of the uncomputable (global) minimum or maximum. In the present work a general framework used for convex optimization problems to derive oracle inequalities for stationary points is extended. A main new ingredient of these oracle inequalities is that they are sharp: they show closeness to the best approximation within the model plus a remainder term. We apply this framework to different estimation problems.