Matthias Löffler
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
Matthias Löffler has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Geoffrey Chinot
Seminar for Statistics Department of Mathematics ETH Zürich Switzerland
2 shared publications - Sara van de Geer
ETH Zurich
2 shared publications Afonso S Bandeira
Department of Mathematics, ETH Zurich , Rämistrasse 101, 8092 Zurich , Switzerland
1 shared publication- Afonso S. Bandeira
Department of Mathematics ETH Zurich
1 shared publication Alexander S Wein
Department of Mathematics , Courant Institute of Mathematical Sciences NY 10012-1110 , USA
1 shared publication- Alexander S. Wein
University of California at Davis, Davis, USA
1 shared publication
Latest Publications
- 8 August 2022
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 11 (4) , 1255-1286
Computationally efficient sparse clustering
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretical analysis focuses on the model |$X_i=z_i \theta +\varepsilon _{i}, \ z_i \in \{-1,1\}, \ \varepsilon _i \thicksim \mathcal{N}(0, I)$|, which has two clusters with centres |$\theta $| and |$-\theta $|. We provide a finite sample analysis of a new sparse clustering algorithm based on sparse Principal Component Analysis (PCA) and show that it achieves the minimax optimal misclustering rate in the regime |$\|\theta \| \rightarrow \infty $|. Our results require the sparsity to grow slower than the square root of the sample size. Using a recent framework for computational lower bounds—the low-degree likelihood ratio—we give evidence that this condition is necessary for any polynomial-time clustering algorithm to succeed below the Baik-Ben Arous-Péché (BBP) threshold. This complements the existing evidence based on reductions and statistical query lower bounds. Compared with these existing results, we cover a wider set of parameter regimes and give a more precise understanding of the runtime required and the misclustering error achievable. Our results imply that a large class of tests based on low-degree polynomials fail to solve even the weak testing task.
- 8 August 2022
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 11 (4) , 1255-1286
Computationally efficient sparse clustering
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretical analysis focuses on the model |$X_i=z_i \theta +\varepsilon _{i}, \ z_i \in \{-1,1\}, \ \varepsilon _i \thicksim \mathcal{N}(0, I)$|, which has two clusters with centres |$\theta $| and |$-\theta $|. We provide a finite sample analysis of a new sparse clustering algorithm based on sparse Principal Component Analysis (PCA) and show that it achieves the minimax optimal misclustering rate in the regime |$\|\theta \| \rightarrow \infty $|. Our results require the sparsity to grow slower than the square root of the sample size. Using a recent framework for computational lower bounds—the low-degree likelihood ratio—we give evidence that this condition is necessary for any polynomial-time clustering algorithm to succeed below the Baik-Ben Arous-Péché (BBP) threshold. This complements the existing evidence based on reductions and statistical query lower bounds. Compared with these existing results, we cover a wider set of parameter regimes and give a more precise understanding of the runtime required and the misclustering error achievable. Our results imply that a large class of tests based on low-degree polynomials fail to solve even the weak testing task.
- 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
Spectral thresholding for the estimation of Markov chain transition operators
We consider nonparametric estimation of the transition operator $P$ of a Markov chain and its transition density $p$ where the singular values of $P$ are assumed to decay exponentially fast. This is for instance the case for periodised, reversible multi-dimensional diffusion processes observed in low frequency. We investigate the performance of a spectral hard thresholded Galerkin-type estimator for $P$ and ${p}$, discarding most of the estimated singular triplets. The construction is based on smooth basis functions such as wavelets or B-splines. We show its statistical optimality by establishing matching minimax upper and lower bounds in $L^2$-loss. Particularly, the effect of the dimensionality $d$ of the state space on the nonparametric rate improves from $2d$ to $d$ compared to the case without singular value decay.Open AccessSpectral thresholding for the estimation of Markov chain transition operators
We consider nonparametric estimation of the transition operator $P$ of a Markov chain and its transition density $p$ where the singular values of $P$ are assumed to decay exponentially fast. This is for instance the case for periodised, reversible multi-dimensional diffusion processes observed in low frequency. We investigate the performance of a spectral hard thresholded Galerkin-type estimator for $P$ and ${p}$, discarding most of the estimated singular triplets. The construction is based on smooth basis functions such as wavelets or B-splines. We show its statistical optimality by establishing matching minimax upper and lower bounds in $L^2$-loss. Particularly, the effect of the dimensionality $d$ of the state space on the nonparametric rate improves from $2d$ to $d$ compared to the case without singular value decay. - 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. - Open Access
Computationally efficient sparse clustering
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretical analysis focuses on the model $X_i = z_i \theta + \varepsilon_i, ~z_i \in \{-1,1\}, ~\varepsilon_i \thicksim \mathcal{N}(0,I)$, which has two clusters with centres $\theta$ and $-\theta$. We provide a finite sample analysis of a new sparse clustering algorithm based on sparse PCA and show that it achieves the minimax optimal misclustering rate in the regime $\|\theta\| \rightarrow \infty$. Our results require the sparsity to grow slower than the square root of the sample size. Using a recent framework for computational lower bounds -- the low-degree likelihood ratio -- we give evidence that this condition is necessary for any polynomial-time clustering algorithm to succeed below the BBP threshold. This complements existing evidence based on reductions and statistical query lower bounds. Compared to these existing results, we cover a wider set of parameter regimes and give a more precise understanding of the runtime required and the misclustering error achievable. Our results imply that a large class of tests based on low-degree polynomials fail to solve even the weak testing task.Open AccessComputationally efficient sparse clustering
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretical analysis focuses on the model $X_i = z_i \theta + \varepsilon_i, ~z_i \in \{-1,1\}, ~\varepsilon_i \thicksim \mathcal{N}(0,I)$, which has two clusters with centres $\theta$ and $-\theta$. We provide a finite sample analysis of a new sparse clustering algorithm based on sparse PCA and show that it achieves the minimax optimal misclustering rate in the regime $\|\theta\| \rightarrow \infty$. Our results require the sparsity to grow slower than the square root of the sample size. Using a recent framework for computational lower bounds -- the low-degree likelihood ratio -- we give evidence that this condition is necessary for any polynomial-time clustering algorithm to succeed below the BBP threshold. This complements existing evidence based on reductions and statistical query lower bounds. Compared to these existing results, we cover a wider set of parameter regimes and give a more precise understanding of the runtime required and the misclustering error achievable. Our results imply that a large class of tests based on low-degree polynomials fail to solve even the weak testing task. - Open Access
Optimality of Spectral Clustering in the Gaussian Mixture Model
Spectral clustering is one of the most popular algorithms to group high dimensional data. It is easy to implement and computationally efficient. Despite its popularity and successful applications, its theoretical properties have not been fully understood. In this paper, we show that spectral clustering is minimax optimal in the Gaussian Mixture Model with isotropic covariance matrix, when the number of clusters is fixed and the signal-to-noise ratio is large enough. Spectral gap conditions are widely assumed in the literature to analyze spectral clustering. On the contrary, these conditions are not needed to establish optimality of spectral clustering in this paper.
Open AccessOptimality of Spectral Clustering in the Gaussian Mixture Model
Spectral clustering is one of the most popular algorithms to group high dimensional data. It is easy to implement and computationally efficient. Despite its popularity and successful applications, its theoretical properties have not been fully understood. In this paper, we show that spectral clustering is minimax optimal in the Gaussian Mixture Model with isotropic covariance matrix, when the number of clusters is fixed and the signal-to-noise ratio is large enough. Spectral gap conditions are widely assumed in the literature to analyze spectral clustering. On the contrary, these conditions are not needed to establish optimality of spectral clustering in this paper.