PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Guillaume Lecué, Matthieu Lerasle

arXiv:1711.10306v2math.ST

TL;DR

Practical machine-learning procedures can fail under corrupted or heavy-tailed data, motivating robust estimators that remain statistically effective with minimal assumptions. The paper builds median-of-means estimators and computable proxies, obtaining non-asymptotic guarantees under outliers while introducing a performance-based breakdown notion. It also shows that these procedures can be implemented through robust versions of common learning algorithms.

  • Problem

    Practical learning procedures such as least-squares and LASSO are highly sensitive to corrupted data, while existing robust approaches can be computationally unsuitable for machine learning.

  • Method

    The paper plugs median-of-means estimates of loss increments into a minimaximization framework and develops computable algorithmic proxies.

  • Results

    The estimators achieve minimax-optimal non-asymptotic risk bounds under minimal assumptions, including datasets corrupted by outliers in inputs, outputs, or both.

  • Takeaways & Limitations

    The approach provides statistically robust and computationally tractable alternatives to standard empirical-risk procedures, with a breakdown measure tied to estimation performance.

  • Takeaways & Limitations

    ρ-estimators remain far from generally computable for machine learning and require a statistical model and the Hellinger loss.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the sensitivity of practical machine-learning procedures to corrupted or heavy-tailed data by introducing computable median-of-means estimators with non-asymptotic guarantees. It also proposes a risk-based breakdown notion and shows that robust proxies retain strong statistical properties under minimal assumptions.

  • Motivation: Single outliers can break standard least-squares and LASSO procedures because their empirical losses use unbounded functions and function classes.This sensitivity is especially problematic for leverage points and other dataset corruptions.
  • Motivation: ρ-estimators address some robustness problems but require a statistical model, target the Hellinger loss, and are generally not computationally feasible for machine learning.The paper presents these limitations as motivating a different approach.
  • Contributions: The proposed estimator achieves minimax-optimal non-asymptotic risk bounds with outliers affecting inputs, outputs, or both, under minimal geometric assumptions on informative data.The guarantees include adversarial outliers and heavy-tailed informative observations that may appear anomalous.
  • Contributions: The paper introduces a risk-based breakdown point for learning that measures how many outliers can be tolerated without deteriorating an estimator’s statistical performance.This replaces the standard breakdown notion’s lack of estimation or prediction properties with a performance-based definition.
  • Results: σ^2d and σ^2s log(ed/s) are the stated rates for estimating dense and s-sparse d-dimensional vectors, respectively, and these rates are achieved by computationally tractable procedures.The paper further relates the tolerable outlier count to the sample size and convergence rate.
  • Method and practice: Median-of-means estimators remain acceptable when the number of blocks is at least twice the number of outliers, motivating their use inside a minimaximization problem.The paper also reports algorithmic proxies, extensive simulations, and a data-depth measure that can support outlier detection.

2 Setting

The section formulates least-squares learning with a convex function class and replaces empirical risk comparisons by regularized median-of-means tests. The resulting minimaximization estimators retain ERM as the special case K=1 while enabling computationally approximable robust procedures.

  • Setting: The framework uses a convex class F of functions, square loss, an unknown distribution, and a regularization norm on span(F).The oracle f* minimizes the population square risk, while empirical risk minimization replaces unknown expectations with empirical averages.
  • Motivation: A single outlier can invalidate empirical loss comparisons because empirical means of unbounded losses are highly sensitive to corrupted data.The standard ERM approach requires uniform concentration of empirical losses over F.
  • MOM tests: The estimators replace population loss differences in a minimax formulation with MOM tests, with an optional regularization term.Because MOM is nonlinear, inserting it into minimaximization and minimization formulations produces distinct estimators.
  • Computational formulation: The minimaximization formulation yields locally convex-concave procedures that can be approximated by converting classical cost-minimization algorithms into robust algorithms.This computational property distinguishes the proposed estimators from earlier test-aggregation procedures described as impractical to build.
  • MOM tests: MOM estimates expectations by taking the median of empirical means over equal-sized blocks, limiting the influence of outliers when enough blocks remain unaffected.The median step provides robustness because outliers can affect only a subset of block means.
  • Computational formulation: When K=1, the proposed estimators reduce respectively to ERM and regularized ERM.Thus the number of blocks controls the transition from ordinary empirical procedures to robust MOM-based procedures.

3 Assumptions and main results

The results allow arbitrary outliers and weaken the usual i.i.d. and strong-concentration requirements to moment and metric conditions on informative data. Under these assumptions, the MOM estimators achieve controlled rates and a breakdown number proportional to sample size times the target rate.

  • Assumptions: Outliers may have arbitrary dependence and distribution, while informative observations are assumed independent and are the data used for estimation.No assumptions are imposed on outliers, including their dependence on informative observations.
  • Assumptions: The assumptions require only first and second moments and therefore relax the strong concentration conditions commonly used to analyze ERM.The informative distributions need equivalent L2 metrics and covariance behavior over the function class.
  • Assumptions: The framework includes the i.i.d. case and also permits non-identically distributed informative data when their induced L2 metrics and relevant covariances are equivalent.The i.i.d. setting satisfies the first norm-equivalence assumption with θr0=1.
  • Rates: The minimax rate is governed by the maximum of the quadratic and multiplier complexity radii, with these radii well defined when at least half the observations are informative.The function r(ρ) can be chosen as an upper bound on these two radii.
  • Main results: Theorem 1 provides a high-probability risk guarantee for K between a multiple of the outlier count and an upper sample-size bound, under the stated moment and sparsity conditions.The probability is at least 1−4 exp(−7K/9216) in the stated range of K.
  • Main results: The adaptive estimator has breakdown number at least N r(ρ*)^2 when r(2ρ*) is bounded by an absolute multiple of r(ρ*).This links the number of tolerable outliers to sample size and the squared target rate.

4 Proofs

The proofs separate quadratic and multiplier MOM processes, discarding blocks contaminated by outliers and controlling the remaining blocks. These controls combine with regularization and geometric decompositions to establish the estimator’s risk bounds.

  • Proof strategy: The proof separately establishes lower bounds for quadratic processes and upper controls for multiplier processes through high-probability events.The multiplier term contains the noise, while the quadratic process or regularization term controls it.
  • Proof strategy: Blocks containing outliers are treated as unusable, so the proof controls MOM processes only on blocks containing informative observations.The argument shows that sufficiently many controlled blocks are enough for statistical performance.
  • Quadratic control: The quadratic-process argument uses symmetrization, contraction, and blockwise quantile control to show that many blocks have sufficiently large empirical quadratic terms.The resulting event provides a uniform lower bound over the function class.
  • Multiplier control: The multiplier-process argument uses moment assumptions, symmetrization, bounded differences, and quantile inequalities to control noisy loss terms on most blocks.The proof obtains a block fraction satisfying the required multiplier bound.
  • Criterion control: The proof partitions the function class by distance from f* and uses either the quadratic process or regularization to dominate the multiplier term.Figure 2 describes the corresponding Q>M and R>M regions of the partition.
  • Criterion control: Convexity and homogeneity extend local bounds at radius ρK to functions farther from f*, while the sparsity equation supplies the regularization lower bound.The resulting criterion control yields the excess-risk bound stated in the theorem.

A Simulation study

The simulation study develops computable MOM versions of standard optimization procedures, including LASSO algorithms, using median-selected blocks and robust hyperparameter selection. It also uses the resulting data-depth measure for outlier detection.

  • Algorithms: The proposed min-max procedures can be computed with alternating descent-ascent algorithms based on block gradient descent.Unlike classical or stochastic block updates, blocks are selected according to their centrality through the median operator.
  • LASSO experiments: MOM-LASSO provides robust counterparts to standard LASSO algorithms in a high-dimensional setting.The simulations use the ℓ1 norm and target greater robustness to outliers.
  • Hyperparameter selection: Cross-validation is adapted with MOM estimators because ordinary validation sets may contain outliers.The number of blocks and regularization parameter are selected through robust versions of the cross-validation principle.
  • Optimization and detection: Randomly changing blocks during optimization is advocated to bypass local saddle points identified by the authors.The simulations also motivate a learning-task-specific depth measure for detecting outliers.

A.1 Data generating process and corruption by outliers

The experiments construct informative data and several corruption regimes, including arbitrary outliers, extreme responses, random covariates, and heavy-tailed correlated designs.

  • The corrupted dataset merges and shuffles informative data with outlier datasets D2, D3, and D4, while the selected outlier types may be unrelated to the oracle t∗ and neither independent nor random.
  • D1 contains Ngood i.i.d. informative observations (Xi, Yi) from a common distribution.
  • D2 and D3 use deterministic outliers with Xi=(1)d j=1 and responses Yi=1 or Yi=10000, respectively.
  • D4 uses outliers with Bernoulli 0–1 responses and covariates uniformly distributed over [0, 1]d.
  • D5 follows the same target-vector linear model but changes the design covariance and uses Student-distributed heavy-tailed noise.

A.2 From algorithms for the LASSO to their “MOM versions”

The paper converts LASSO algorithms into MOM min-max procedures by selecting blocks through median-based centrality rather than processing blocks sequentially or randomly.

  • Each LASSO algorithm can be transformed into an algorithm approximating the MOM min-max estimator.
  • The median identifies the block index among K blockwise loss values, making the selected block straightforward to compute.
  • The approach alternates descent in t and ascent in t′, optionally using proximal or projection steps and different step sizes.
  • Because the marginal functions may not be convex, local steepest descent is computed under an assumption that the median-achieving block index remains constant locally.
  • Centrality-based block selection is expected to avoid outlier-corrupted blocks and improve descent or ascent directions, while fitting map-reduce data partitioning.
  • The corrupted design matrix is not column-normalized because one corrupted row could contaminate normalization of the entire matrix.

A.3 Subgradient descent algorithm

The paper adapts LASSO subgradient descent to the MOM min-max setting using alternating updates and median-selected blocks.

  • The classical LASSO minimizes the squared residual loss plus an ℓ1 penalty and can be approximated by subgradient descent.
  • Its subgradient combines the residual term −2X⊤(Y−Xtp) with λsign(tp), using sign(0)=0.
  • The MOM version uses alternating subgradient descent and ascent to approximate the min-max estimator.
  • At descent and ascent steps, blocks are chosen by median-based centrality to remove outlier effects from directions and improve their accuracy.
  • Step sizes can use the inverse operator norm of X or an Armijo-Goldstein backtracking line search.

A.4 Proximal gradient descent algorithms

The paper extends proximal gradient, ADMM, and coordinate-descent methods for LASSO into MOM algorithms that approximate the robust min-max estimator.

  • ISTA and FISTA are proximal gradient splitting algorithms that combine gradient descent with soft-thresholding for the ℓ1 penalty.
  • The paper proposes an alternating proximal gradient method for the MOM min-max procedure.
  • ADMM is presented as another splitting algorithm, with a MOM version that returns an approximate min-max solution after a stopping criterion.
  • Repeated coordinate-wise minimization is adapted to the MOM estimator using the columns Xkj of the selected block matrix Xk.
  • The coordinate-descent implementation cycles over coordinates in the MOM min-max procedure.

A.7 Adaptive choice of hyper-parameters via MOM V-fold Cross Validation

MOM V-fold cross-validation robustly selects the number of blocks and regularization parameter in corrupted-data settings by replacing classical test-set means and split aggregation with MOM estimates and medians.

  • Motivation: The procedure is designed because classical cross-validation criteria can be corrupted when test datasets contain outliers.
  • Procedure: MOM V-fold cross-validation selects the number of blocks K and regularization parameter λ from predefined grids using training and test splits.Each candidate is trained on all but one split and evaluated on the held-out split.
  • Robust criterion: Classical test-set means are replaced by MOM estimators, and averaging across V splits is replaced by a median.
  • Empirical behavior: The adaptively chosen K grows with the number of outliers, consistent with requiring at least twice as many blocks as outliers.

A.8 Maximinimization, saddle-point, random blocks, outliers detection and depth

The section develops maximin and random-block variants of MOM optimization, showing that randomization avoids local saddle points and also yields a data-centrality score for outlier detection.

  • Maximinimization: The maximin estimator arises because the oracle also solves a maximinimization problem, although its estimator need not equal the minmax estimator.
  • Saddle-point limitation: Fixed blocks can trap MOM algorithms near potentially suboptimal local saddle points associated with different cells of the parameter space.
  • Random blocks: Randomly repartitioning the data at every descent and ascent step removes the fixed-cell decomposition and addresses this trapping issue.
  • Random blocks: Random-block MOM LASSO converges faster and more smoothly than fixed-block MOM LASSO, while avoiding objective and estimation-error jumps.The objective tends to zero, providing a natural stopping criterion through the duality gap.
  • Outlier detection: Counting how often each observation belongs to a selected median block produces a centrality score that can be interpreted as data depth.
  • Outlier detection: In the synthetic example, observations 1, 32, 170, and 194 receive score 0 and are separated from informative observations by a score gap.

A.9 Simulations setup for the figures

The simulations evaluate LASSO and MOM LASSO under progressively corrupted high-dimensional data, and separately compare fixed versus random blocks and test outlier scoring.

  • Main simulation: The main corruption experiment uses N = 200 observations, d = 500 features, sparsity s = 10, noise variance σ = 1, and outlier proportions from 0 to 15%.
  • Main simulation: The experiments run 70 repetitions and report averaged estimation error, adaptively chosen K, and λ for Figures 1, 3, and 4.
  • Main simulation: A single outlier causes the LASSO ℓ2 estimation error to stabilize around 550 in the reported setup.The outlier uses Y = 10000 and X = (1)_500, causing the LASSO to fit the outlier rather than the 200 informative observations.
  • Random-block simulation: The fixed-versus-random-block experiment uses N = 200, d = 300, s = 20, σ = 1, K = 10, and 500 iterations.
  • Outlier detection simulation: The outlier-detection experiment uses N = 200, d = 500, s = 20, σ = 1, and four outliers.

B.3 Classical results for LASSO and SLOPE

Classical LASSO and SLOPE results rely on i.i.d. data, subgaussian design assumptions, and stronger noise conditions, whereas minimal Lq0 moments can still yield optimal rates with weaker guarantees.

  • Assumptions: Classical analyses assume i.i.d. data with isotropic, L-subgaussian design, and typically subgaussian noise.These assumptions define the baseline setup for LASSO and SLOPE results.
  • Weaker noise conditions: A minimal Lq0 noise moment for q0 > 2 still permits optimal LASSO and SLOPE rates, but with severely deteriorated probability estimates.The weaker stochastic assumption applies to the noise rather than requiring subgaussian behavior.
  • LASSO: Theorem 3 extends standard LASSO rates to targets approximable by sparse vectors, arbitrary targets, and heavy-tailed noise dependent on X, but still excludes outliers.The design remains subgaussian and the data remain i.i.d.
  • SLOPE: Theorem 4 provides the corresponding SLOPE result under a sparsity condition and the same probability guarantee as the LASSO theorem.The result uses a sparse approximation measured through the SLOPE norm.

B.4 Statistical analysis of MOM LASSO and MOM SLOPE

The MOM versions of LASSO and SLOPE retain or improve classical statistical guarantees under weaker assumptions, while adding robustness to corruption and removing the need to know sparsity in advance for MOM-LASSO.

  • Approach: MOM-LASSO and MOM-SLOPE apply the general MOM theory to linear functionals regularized by the ℓ1 or SLOPE norm.Their analysis computes fixed points and solves the associated sparsity equations.
  • Adaptation and SLOPE: MOM-LASSO does not require the sparsity parameter s to be known in advance, while SLOPE already achieves the minimax rate s log(ed/s)/N.Theorem 5 establishes the adaptive MOM-LASSO result; MOM-SLOPE retains analogous advantages over SLOPE.
  • Rates: MOM-LASSO achieves the minimax rate s log(ed/s)/N, whereas classical LASSO achieves s log(ed)/N.The improvement is attributed to the adaptation step in MOM-LASSO.
  • Deviation guarantees: MOM-LASSO has exponentially small probability deviation under weaker noise conditions, while classical LASSO has polynomial deviation unless the noise is subgaussian.The classical polynomial deviation is 1/N^(q0/2−1).
  • Robustness: MOM-LASSO tolerates up to s log(ed/s) outliers, and its informative data need only satisfy equivalent L2 moments rather than the classical i.i.d. setup.A single outlier can cause dramatic LASSO breakdown in the comparison described.
  • Assumptions: MOM-LASSO weakens design assumptions from subgaussian coordinates to logarithmic-order coordinate moments plus an L2/L1 equivalence condition.This broadens the assumptions used for the corresponding classical LASSO analysis.

C Learning without regularization

Without regularization, MOM minmax and maxmin estimators provide computable learning procedures that retain controlled rates under outliers and weak moment assumptions, with optimality established through minimax lower bounds.

  • Framework: The unregularized learning framework supports both minmaximization and maxminimization MOM estimators.The setup uses fixed points to determine their statistical properties.
  • Robust computation: Classical ERM corresponds to one block and can only be trusted with a clean dataset, whereas the MOM procedures remain designed for corrupted data.The one-block case is explicitly identified with the classical empirical risk minimizer.
  • Guarantees: The adaptive estimators achieve high-probability guarantees when informative observations satisfy moment equivalence and the number of outliers is bounded.The assumptions include matching L2 norms across informative data and an L2/L1 comparison.
  • Ordinary least squares: For ordinary least squares, fewer than D/8 outliers preserve the classical D/N mean-square-error rate with exponentially large probability.This result requires only L2 moment assumptions on the design and equivalent L2 moments for informative data.
  • Optimality: The MOM rates are essentially minimax optimal, even though the analysis allows outliers, dependent noise and design, and heavy-tailed informative data.The comparison is made against strong Gaussian i.i.d. models where minimax lower bounds apply.
Loading 1711.10306v2…