MLMatthias Löffler

Matthias Löffler

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Computationally efficient sparse clustering

    by Matthias Löffler, Alexander S Wein, Afonso S Bandeira

    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

    by Geoffrey Chinot, Felix Kuchelmeister, Matthias Löffler, Sara van de Geer

    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

    by Matthias Löffler, Antoine Picard

    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

    by Geoffrey Chinot, Matthias Löffler, Sara van de Geer

    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

    by Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira

    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

    by Matthias Löffler, Anderson Y. Zhang, Harrison H. Zhou

    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.