Geometric median and robust estimation in Banach spaces

Abstract

In many real-world applications, collected data are contaminated by noise with heavy-tailed distribution and might contain outliers of large magnitude. In this situation, it is necessary to apply methods which produce reliable outcomes even if the input contains corrupted measurements. We describe a general method which allows one to obtain estimators with tight concentration around the true parameter of interest taking values in a Banach space. Suggested construction relies on the fact that the geometric median of a collection of independent "weakly concentrated" estimators satisfies a much stronger deviation bound than each individual element in the collection. Our approach is illustrated through several examples, including sparse linear regression and low-rank matrix recovery problems.

Published at http://dx.doi.org/10.3150/14-BEJ645 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (8)

• Regularized estimation of large covariance matrices
• Covariance regularization by thresholding
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Geometric median and robust estimation in Banach spaces
• High-Breakdown Robust Multivariate Methods
• Loss minimization and parameter estimation with heavy tails
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm

Cited by in corpus (85)

• Robust Aggregation for Federated Learning
• Geometric median and robust estimation in Banach spaces
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Generalized Byzantine-tolerant SGD
• Robust Federated Learning in a Heterogeneous Environment
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• An Overview of Robust Subspace Recovery
• Loss minimization and parameter estimation with heavy tails
• Empirical risk minimization for heavy-tailed losses
• On the Optimality of Averaging in Distributed Statistical Learning
• Online estimation of the geometric median in Hilbert spaces : non asymptotic confidence balls
• Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
• Resilient Primal-Dual Optimization Algorithms for Distributed Resource Allocation
• Simpler PAC-Bayesian Bounds for Hostile Data
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Distributed Robust Learning
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• BEV-SGD: Best Effort Voting SGD for Analog Aggregation Based Federated Learning against Byzantine Attackers
• Fast Mean Estimation with Sub-Gaussian Rates
• Learning from History for Byzantine Robust Optimization
• Estimation of the covariance structure of heavy-tailed distributions
• Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence
• Modeling Massive Spatial Datasets Using a Conjugate Bayesian Linear Regression Framework
• Dimension-free PAC-Bayesian bounds for the estimation of the mean of a random vector
• Principal component analysis for big data
• Median Selection Subset Aggregation for Parallel Inference
• DECOrrelated feature space partitioning for distributed sparse regression
• Concentration study of M-estimators using the influence function
• Securing Federated Sensitive Topic Classification against Poisoning Attacks
• When OT meets MoM: Robust estimation of Wasserstein Distance
• A Unified Approach to Robust Mean Estimation
• A Case Study Competition Among Methods for Analyzing Large Spatial Data
• MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means
• DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
• Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability
• Bearing-Only Consensus and Formation Control under Directed Topologies
• Distribution-Free Robust Linear Regression
• Pufferfish Privacy: An Information-Theoretic Study
• Randomized maximum-contrast selection: subagging for large-scale regression
• Robust Subspace Recovery with Adversarial Outliers
• Lecture Notes: Selected topics on robust statistical learning theory
• Sub-Gaussian estimators of the mean of a random vector
• Robust descent using smoothed multiplicative noise
• TAdam: A Robust Stochastic Gradient Optimizer
• From low probability to high confidence in stochastic convex optimization
• PAC-Bayesian bounds for Principal Component Analysis in Hilbert spaces
• Outlier Robust Online Learning
• Robust estimation of U-statistics
• On the Wasserstein median of probability measures
• Linear-Cost Covariance Functions for Gaussian Random Fields
• Robust and Parallel Bayesian Model Selection
• Weak and Strong Gradient Directions: Explaining Memorization, Generalization, and Hardness of Examples at Scale
• Budget-Constrained Bandits over General Cost and Reward Distributions
• Convergence rates of least squares regression estimators with heavy-tailed errors
• Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: $L^p$ and almost sure rates of convergence
• On Medians of (Randomized) Pairwise Means
• A spectral algorithm for robust regression with subgaussian rates
• KNG: The K-Norm Gradient Mechanism
• Efficient learning with robust gradient descent
• Exponential Concentration for Geometric-Median-of-Means in Non-Positive Curvature Spaces
• Continuous-Time Multi-Armed Bandits with Controlled Restarts
• Trimmed sample means for robust uniform mean estimation and regression
• Generalization Bounds in the Presence of Outliers: a Median-of-Means Study
• Online Factorization and Partition of Complex Networks From Random Walks
• On deviation probabilities in non-parametric regression with heavy-tailed noise
• Robust Extrinsic Regression Analysis for Manifold Valued Data
• Communication-efficient Byzantine-robust distributed learning with statistical guarantee
• On Weighted Multivariate Sign Functions
• Improved scalability under heavy tails, without strong convexity
• Disease Prediction based on Functional Connectomes using a Scalable and Spatially-Informed Support Vector Machine
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
• ByzShield: An Efficient and Robust System for Distributed Training
• On the estimation of the mean of a random vector
• One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning
• Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
• On the distance between mean and geometric median in high dimensions
• Byzantine-Resilient Federated Machine Learning via Over-the-Air Computation
• Geometric medians on product manifolds
• Geometric Median Shapes
• Robust Online Convex Optimization in the Presence of Outliers
• Introduction to Coresets: Approximated Mean
• Robust Principal Component Analysis in Hilbert spaces
• Better scalability under potentially heavy-tailed feedback