Robust machine learning by median-of-means: theory and practice

DOI10.1214/19-AOS1828zbMATH Open1487.62034arXiv1711.10306OpenAlexW3010140118MaRDI QIDQ2196199FDOQ2196199

M. Lerasle, Guillaume Lecué

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

machine learninghigh-dimensional statisticsempirical processes

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Learning and adaptive systems in artificial intelligence (68T05) Estimation in multivariate analysis (62H12) Ridge regression; shrinkage estimators (Lasso) (62J07) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Title not available (Why is that?)
• Statistics for high-dimensional data. Methods, theory and applications.
• A survey of cross-validation procedures for model selection
• Lasso-type recovery of sparse representations for high-dimensional data
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional generalized linear models and the lasso
• High-dimensional graphs and variable selection with the Lasso
• Title not available (Why is that?)
• Robust Estimation of a Location Parameter
• Title not available (Why is that?)
• Confidence Intervals for Low Dimensional Parameters in High Dimensional Linear Models
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• On asymptotically optimal confidence regions and tests for high-dimensional models
• Confidence sets in sparse regression
• Title not available (Why is that?)
• A General Qualitative Definition of Robustness
• Robust Statistics
• Segmentation of the mean of heteroscedastic data via cross-validation
• Asymptotic methods in statistical decision theory
• The Influence Curve and Its Role in Robust Estimation
• Geometric median and robust estimation in Banach spaces
• Challenging the empirical mean and empirical variance: a deviation study
• Convergence of estimates under dimensionality restrictions
• The Future of Data Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Robust linear least squares regression
• The space complexity of approximating the frequency moments
• Model selection via testing: an alternative to (penalized) maximum likelihood estimators.
• Estimation of High Dimensional Mean Regression in the Absence of Symmetry and Light Tail Assumptions
• Estimator selection with respect to Hellinger-type risks
• SLOPE-adaptive variable selection via convex optimization
• Random generation of combinatorial structures from a uniform distribution
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Weakly decomposable regularization penalties and structured sparsity
• Learning without concentration
• Bounding the Smallest Singular Value of a Random Matrix Without Concentration
• A new method for estimation and model selection: \(\rho\)-estimation
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Statistical performance of support vector machines
• Rho-estimators for shape restricted density estimation
• Risk bounds for statistical learning
• Stabilité et instabilité du risque minimax pour des variables indépendantes équidistribuées
• Sub-Gaussian mean estimators
• Robust low-rank matrix estimation
• Title not available (Why is that?)
• Learning from MOM's principles: Le Cam's approach
• On optimality of empirical risk minimization in linear aggregation
• Regularization and the small-ball method. I: Sparse recovery
• Slope meets Lasso: improved oracle bounds and optimality
• Choice of V for V-Fold Cross-Validation in Least-Squares Density Estimation
• Risk minimization by median-of-means tournaments
• Regularization and the small-ball method II: complexity dependent error rates
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Regularization, sparse recovery, and median-of-means tournaments
• Distributed statistical estimation and rates of convergence in normal approximation

Cited In (37)

• Robust Bregman clustering
• The main contributions of robust statistics to statistical science and a new challenge
• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Outlier detection in networks with missing links
• On least squares estimation under heteroscedastic and heavy-tailed errors
• Robust and tuning-free sparse linear regression via square-root slope
• Super-polynomial accuracy of one dimensional randomized nets using the median of means
• Robust subgaussian estimation with VC-dimension
• All-in-one robust estimator of the Gaussian mean
• ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels
• DeepMoM: Robust Deep Learning With Median-of-Means
• Data perturbations in stochastic generalized equations: statistical robustness in static and sample average approximated models
• Distribution-free robust linear regression
• Byzantine-robust and efficient distributed sparsity learning: a surrogate composite quantile regression approach
• Title not available (Why is that?)
• Byzantine-robust distributed sparse learning for \(M\)-estimation
• Robust \(k\)-means clustering for distributions with two moments
• High-dimensional \(M\)-estimation for Byzantine-robust decentralized learning
• A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
• Iteratively reweighted \(\ell_1\)-penalized robust regression
• Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms
• Robust statistical learning with Lipschitz and convex loss functions
• Exponential concentration for geometric-median-of-means in non-positive curvature spaces
• Mean estimation and regression under heavy-tailed distributions: A survey
• Learning in Repeated Auctions
• Robust partially linear trend filtering for regression estimation and structure discovery
• Non-asymptotic analysis and inference for an outlyingness induced winsorized mean
• Core-elements for large-scale least squares estimation
• Robust classification via MOM minimization
• A robust estimator of the proportional hazard transform for massive data
• Robust multivariate mean estimation: the optimality of trimmed mean
• K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means
• Scale calibration for high-dimensional robust regression
• Robust supervised learning with coordinate gradient descent
• Topics in robust statistical learning
• Title not available (Why is that?)
• Robust sub-Gaussian estimation of a mean vector in nearly linear time

Uses Software

• GitHub

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)