Learning from MOM's principles: Le Cam's approach

DOI10.1016/J.SPA.2018.11.024MaRDI QIDQ2010482zbMATH OpenOpenAlexWikidataFDO

Authors Guillaume Lecué, M. Lerasle

Publication date 27 November 2019

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.01961

zbMATH Keywords

high dimensional statisticsrobust statisticsstatistical learning

Mathematics Subject Classification ID

Gaussian processes (60G15) Nonparametric regression and quantile regression (62G08) Nonparametric robustness (62G35)

Abstract: We obtain estimation error rates for estimators obtained by aggregation of regularized median-of-means tests, following a construction of Le Cam. The results hold with exponentially large probability -- as in the gaussian framework with independent noise- under only weak moments assumptions on data and without assuming independence between noise and design. Any norm may be used for regularization. When it has some sparsity inducing power we recover sparse rates of convergence. The procedure is robust since a large part of data may be corrupted, these outliers have nothing to do with the oracle we want to reconstruct. Our general risk bound is of order �egin{equation*} maxleft(mbox{minimax rate in the i.i.d. setup}, frac{ ext{number of outliers}}{ ext{number of observations}} ight) enspace. end{equation*}In particular, the number of outliers may be as large as (number of data) $imes$(minimax rate) without affecting this rate. The other data do not have to be identically distributed but should only have equivalent $L^1$ and $L^2$ moments. For example, the minimax rate $slog(ed/s)/N$ of recovery of a $s$-sparse vector in $mathbb{R}^d$ is achieved with exponentially large probability by a median-of-means version of the LASSO when the noise has $q_0$ moments for some $q_0>2$, the entries of the design matrix should have $C_{0}log(ed)$ moments and the dataset can be corrupted up to $C_{1}slog(ed/s)$ outliers.

Review text

The authors study estimation of \(f^*\) in \[ f^* \in \arg\min_{f \in F} P \left(Y-f\left(X\right)\right)^2 \] where \(F\) is a convex class of functions \(\mathcal X \to \mathbb R\) and \(\left(X_i, Y_i\right)_{i=1,\dots,N}\) are observed random variables with values in \(\mathcal X \times \mathbb R\) with a measurable space \(\mathcal X\). The focus is on estimators arising from comparisons between functions \(f\) and \(g\) from \(F\) based on regularized median-of-means tests. The authors prove rates of convergence, which are minimax in the sparse setting, and furthermore allow for outliers in the data.

Recommendations

• Robust machine learning by median-of-means: theory and practice
• Robust statistical learning with Lipschitz and convex loss functions
• On convergence rates of convex regression in multiple dimensions
• Learning without concentration for general loss functions
• Robust classification via MOM minimization

Cites work

• A new method for estimation and model selection: \(\rho\)-estimation
• A remark on the diameter of random sections of convex bodies
• A robust, adaptive M-estimator for pointwise estimation in heteroscedastic regression
• Asymptotic methods in statistical decision theory
• Bounding the smallest singular value of a random matrix without concentration
• Challenging the empirical mean and empirical variance: a deviation study
• Concentration inequalities. A nonasymptotic theory of independence
• Convergence of estimates under dimensionality restrictions
• Empirical risk minimization for heavy-tailed losses
• Estimating the intensity of a random measure by histogram type estimators
• Estimation of High Dimensional Mean Regression in the Absence of Symmetry and Light Tail Assumptions
• Estimation of the transition density of a Markov chain
• Estimator selection in the Gaussian setting
• Estimator selection with respect to Hellinger-type risks
• scientific article; zbMATH DE number 6388313 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 28602 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• Learning without concentration
• Model selection via testing: an alternative to (penalized) maximum likelihood estimators.
• On aggregation for heavy-tailed classes
• Random generation of combinatorial structures from a uniform distribution
• Rho-estimators for shape restricted density estimation
• Risk minimization by median-of-means tournaments
• Robust Estimation of a Location Parameter
• Robust linear least squares regression
• Robust Statistics
• Robust tests for model selection
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• SLOPE-adaptive variable selection via convex optimization
• Small ball probabilities for linear images of high-dimensional distributions
• Sparse recovery under weak moment assumptions
• Stabilité et instabilité du risque minimax pour des variables indépendantes équidistribuées
• Statistics for high-dimensional data. Methods, theory and applications.
• Sub-Gaussian mean estimators
• The space complexity of approximating the frequency moments
• Weak convergence and empirical processes. With applications to statistics

Cited in

(26)

• A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
• Iteratively reweighted _1-penalized robust regression
• K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means
• Robust sub-Gaussian estimation of a mean vector in nearly linear time
• All-in-one robust estimator of the Gaussian mean
• Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms
• Robust statistical learning with Lipschitz and convex loss functions
• Confidence regions and minimax rates in outlier-robust estimation on the probability simplex
• Robust machine learning by median-of-means: theory and practice
• Robust classification via MOM minimization
• Risk minimization by median-of-means tournaments
• Efficient learning with robust gradient descent
• Multidimensional linear functional estimation in sparse Gaussian models and robust estimation of the mean
• Mean estimation and regression under heavy-tailed distributions: A survey
• Regularization, sparse recovery, and median-of-means tournaments
• Distributed high-dimensional regression under a quantile loss function
• On the robustness to adversarial corruption and to heavy-tailed data of the Stahel–Donoho median of means
• Topics in robust statistical learning
• Robust subgaussian estimation with VC-dimension
• Core-elements for large-scale least squares estimation
• Trimmed sample means for robust uniform mean estimation and regression
• On deviation probabilities in non-parametric regression with heavy-tailed noise
• Robust Personalized Federated Learning with Sparse Penalization
• Computationally efficient and statistically optimal robust high-dimensional linear regression
• Robust local Wasserstein Fréchet regression under admissible transport deformations
• Learning under \((1 + \epsilon)\)-moment conditions

This page was built for publication: Learning from MOM's principles: Le Cam's approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010482)