Robust machine learning by median-of-means: theory and practice
From MaRDI portal
Publication:2196199
Abstract: We introduce new estimators for robust machine learning based on median-of-means (MOM) estimators of the mean of real valued random variables. These estimators achieve optimal rates of convergence under minimal assumptions on the dataset. The dataset may also have been corrupted by outliers on which no assumption is granted. We also analyze these new estimators with standard tools from robust statistics. In particular, we revisit the concept of breakdown point. We modify the original definition by studying the number of outliers that a dataset can contain without deteriorating the estimation properties of a given estimator. This new notion of breakdown number, that takes into account the statistical performances of the estimators, is non-asymptotic in nature and adapted for machine learning purposes. We proved that the breakdown number of our estimator is of the order of (number of observations)*(rate of convergence). For instance, the breakdown number of our estimators for the problem of estimation of a d-dimensional vector with a noise variance sigma^2 is sigma^2d and it becomes sigma^2 s log(d/s) when this vector has only s non-zero component. Beyond this breakdown point, we proved that the rate of convergence achieved by our estimator is (number of outliers) divided by (number of observation). Besides these theoretical guarantees, the major improvement brought by these new estimators is that they are easily computable in practice. In fact, basically any algorithm used to approximate the standard Empirical Risk Minimizer (or its regularized versions) has a robust version approximating our estimators. As a proof of concept, we study many algorithms for the classical LASSO estimator. A byproduct of the MOM algorithms is a measure of depth of data that can be used to detect outliers.
Recommendations
- Robust classification via MOM minimization
- Learning from MOM's principles: Le Cam's approach
- Robust statistical learning with Lipschitz and convex loss functions
- Regularization, sparse recovery, and median-of-means tournaments
- Mean estimation and regression under heavy-tailed distributions: A survey
Cites work
- A General Qualitative Definition of Robustness
- A new method for estimation and model selection: \(\rho\)-estimation
- A survey of cross-validation procedures for model selection
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- 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
- Choice of V for V-Fold Cross-Validation in Least-Squares Density Estimation
- Confidence intervals for low dimensional parameters in high dimensional linear models
- Confidence sets in sparse regression
- Convergence of estimates under dimensionality restrictions
- Distributed statistical estimation and rates of convergence in normal approximation
- Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
- Estimation of High Dimensional Mean Regression in the Absence of Symmetry and Light Tail Assumptions
- Estimator selection with respect to Hellinger-type risks
- Geometric median and robust estimation in Banach spaces
- High-dimensional generalized linear models and the lasso
- High-dimensional graphs and variable selection with the Lasso
- scientific article; zbMATH DE number 6388313 (Why is no real title available?)
- scientific article; zbMATH DE number 5957408 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1332320 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 3320125 (Why is no real title available?)
- scientific article; zbMATH DE number 3336465 (Why is no real title available?)
- Lasso-type recovery of sparse representations for high-dimensional data
- Learning from MOM's principles: Le Cam's approach
- Learning without concentration
- Model selection via testing: an alternative to (penalized) maximum likelihood estimators.
- On asymptotically optimal confidence regions and tests for high-dimensional models
- On optimality of empirical risk minimization in linear aggregation
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Random generation of combinatorial structures from a uniform distribution
- Regularization and the small-ball method. I: Sparse recovery
- Regularization and the small-ball method. II: Complexity dependent error rates
- Regularization, sparse recovery, and median-of-means tournaments
- Rho-estimators for shape restricted density estimation
- Risk bounds for statistical learning
- Risk minimization by median-of-means tournaments
- Robust Estimation of a Location Parameter
- Robust linear least squares regression
- Robust low-rank matrix estimation
- Robust Statistics
- Segmentation of the mean of heteroscedastic data via cross-validation
- Simultaneous analysis of Lasso and Dantzig selector
- SLOPE is adaptive to unknown sparsity and asymptotically minimax
- Slope meets Lasso: improved oracle bounds and optimality
- SLOPE-adaptive variable selection via convex optimization
- Stabilité et instabilité du risque minimax pour des variables indépendantes équidistribuées
- Statistical performance of support vector machines
- Statistics for high-dimensional data. Methods, theory and applications.
- Sub-Gaussian mean estimators
- Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
- The Future of Data Analysis
- The Influence Curve and Its Role in Robust Estimation
- The space complexity of approximating the frequency moments
- Weakly decomposable regularization penalties and structured sparsity
Cited in
(60)- Learning from MOM's principles: Le Cam's approach
- A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
- Iteratively reweighted _1-penalized robust regression
- Robust \(k\)-means clustering for distributions with two moments
- K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means
- Scale calibration for high-dimensional robust regression
- Distribution-free robust linear regression
- On least squares estimation under heteroscedastic and heavy-tailed errors
- 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
- Robust classification via MOM minimization
- ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels
- Outlier detection in networks with missing links
- Risk minimization by median-of-means tournaments
- Mean estimation and regression under heavy-tailed distributions: A survey
- Regularization, sparse recovery, and median-of-means tournaments
- Robust multivariate mean estimation: the optimality of trimmed mean
- Classifier selection using the predicate depth
- Parallel and robust empirical risk minimization via the median trick
- Variance reduced median-of-means estimator for Byzantine-robust distributed inference
- Super-polynomial accuracy of one dimensional randomized nets using the median of means
- Distributed high-dimensional regression under a quantile loss function
- Robust high dimensional learning for Lipschitz and convex losses
- Learning in repeated auctions
- On the robustness to adversarial corruption and to heavy-tailed data of the Stahel–Donoho median of means
- DeepMoM: Robust Deep Learning With Median-of-Means
- Data perturbations in stochastic generalized equations: statistical robustness in static and sample average approximated models
- Byzantine-robust distributed sparse learning for M-estimation
- High-dimensional \(M\)-estimation for Byzantine-robust decentralized learning
- A robust estimator of the proportional hazard transform for massive data
- Robust partially linear trend filtering for regression estimation and structure discovery
- Non-asymptotic analysis and inference for an outlyingness induced winsorized mean
- Topics in robust statistical learning
- Robust supervised learning with coordinate gradient descent
- Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
- Robust and tuning-free sparse linear regression via square-root slope
- Robust subgaussian estimation with VC-dimension
- Byzantine-robust and efficient distributed sparsity learning: a surrogate composite quantile regression approach
- Exponential concentration for geometric-median-of-means in non-positive curvature spaces
- Core-elements for large-scale least squares estimation
- Sparse linear regression when noises and covariates are heavy-tailed and contaminated by outliers
- Statistical guarantees for distribution estimation of contaminated data via DNN-based MoM-GANs
- Heavy Lasso: sparse penalized regression under heavy-tailed noise via data-augmented soft-thresholding
- Trimmed sample means for robust uniform mean estimation and regression
- Uniform bounds for robust mean estimators
- Outlier robust and sparse estimation of linear regression coefficients
- On deviation probabilities in non-parametric regression with heavy-tailed noise
- Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination
- Generalized median of means principle for Bayesian inference
- Uniform inference in linear error-in-variables models: Divide-and-conquer
- Estimation from indirect observations under stochastic uncertainty in observation matrix
- Robust Personalized Federated Learning with Sparse Penalization
- Byzantine-Robust Distributed One-Step Estimation
- Robustness aspects of optimal transport
- Robust sparse penalization under heavy-tailed noise and outliers with exponential-type loss via the LASSO
- Inference via robust optimal transportation: theory and methods
- Robust Bregman clustering
- The main contributions of robust statistics to statistical science and a new challenge
This page was built for publication: Robust machine learning by median-of-means: theory and practice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196199)
