We've seen that different estimators have different sensitivities to outliers. Huber regression is more robust than OLS. Tukey's bisquare is more robust than Huber. RANSAC can handle extreme contamination. But how do we quantify these claims? How do we rigorously compare the robustness of different methods?

Enter the breakdown point—the single most important concept in robust statistics. Introduced by Frank Hampel in his 1968 dissertation and further developed by Peter Rousseeuw, the breakdown point answers a fundamental question:

What fraction of the data can be arbitrarily corrupted before the estimator becomes completely unreliable?

This seemingly simple question has profound implications. An estimator with breakdown point 50% can withstand nearly half the data being replaced with arbitrary values—even adversarially chosen values designed to maximize damage. An estimator with breakdown point 0% (like the sample mean or OLS) can be completely corrupted by a single observation.

The breakdown point provides an absolute limit on robustness. No matter how extreme the outliers, an estimator cannot break down unless the contamination fraction exceeds its breakdown point. This mathematical guarantee is invaluable when dealing with real-world data where you don't know how bad the contamination might be.

This page develops the complete theory of breakdown points, from the formal definition to calculations for specific estimators to practical implications for choosing robust methods.

Finite-Sample Breakdown Point:

Consider an estimator $T$ applied to a sample $\mathbf{Z} = {z_1, z_2, \ldots, z_n}$. The finite-sample breakdown point $\varepsilon^*_n(T, \mathbf{Z})$ is defined as:

$$\varepsilon^*n(T, \mathbf{Z}) = \frac{1}{n} \max\left{m : \sup{\mathbf{Z}'_m} |T(\mathbf{Z}'_m) - T(\mathbf{Z})| < \infty \right}$$

In words: the maximum fraction of observations that can be replaced with arbitrary values while the estimator remains bounded.

Unpacking the definition:

• $\mathbf{Z}'_m$: A corrupted sample where $m$ of the original $n$ observations are replaced with arbitrary (possibly infinite) values
• $\sup_{\mathbf{Z}'_m}$: The supremum over all possible replacements (worst case)
• $|T(\mathbf{Z}'_m) - T(\mathbf{Z})| < \infty$: The estimate remains finite (doesn't explode)

The breakdown point is the largest $m/n$ for which no adversarial corruption can make the estimator explode.

Asymptotic Breakdown Point:

As $n \to \infty$, the finite-sample breakdown point converges to the asymptotic breakdown point:

$$\varepsilon^* = \lim_{n \to \infty} \varepsilon^*_n(T, \mathbf{Z})$$

For most estimators, this limit exists and is independent of the original sample $\mathbf{Z}$.

Let's compute breakdown points for estimators we've encountered:

1. Sample Mean (Arithmetic Average)

For the sample mean $\bar{x} = \frac{1}{n}\sum_{i=1}^n x_i$:

Consider replacing just one observation $x_j$ with $x_j' \to \infty$: $$\bar{x}' = \bar{x} + \frac{x_j' - x_j}{n} \to \infty$$

A single corrupted point makes the estimate unbounded.

$$\varepsilon^*_{\text{mean}} = \frac{1}{n} \xrightarrow{n \to \infty} 0$$

The sample mean has 0% asymptotic breakdown point!

2. Sample Median

The median is the middle value when data is sorted. To move the median arbitrarily:

• Replace the median and all values above it (>50% of data)
• Or replace the median and all values below it (>50% of data)

With less than 50% corruption, the median remains bounded by the uncorrupted data.

$$\varepsilon^*_{\text{median}} = \frac{\lfloor n/2 \rfloor + 1}{n} \xrightarrow{n \to \infty} 0.5$$

The sample median has 50% asymptotic breakdown point!

3. Ordinary Least Squares (OLS)

OLS regression is essentially a conditional mean. A single high-leverage outlier can make coefficients unbounded.

$$\varepsilon^*_{\text{OLS}} = \frac{1}{n} \xrightarrow{n \to \infty} 0$$

OLS has 0% breakdown point—identical to the mean.

It's natural to ask: can we design an estimator with breakdown point higher than 50%? The answer is no—and for a fundamental reason.

The Impossibility Argument:

Consider any sample $\mathbf{Z} = {z_1, \ldots, z_n}$ and any estimator $T$.

Suppose more than 50% of the data can be corrupted—say, we can replace $m > n/2$ observations.

Scenario 1: Replace those $m$ observations with copies of $z_1$. Scenario 2: Replace those $m$ observations with copies of $z_n$ (something very different).

Both resulting samples have the same number of corrupted points, so if the estimator survives one, it must survive the other.

But the two scenarios create completely different data distributions:

• Scenario 1 has >50% of data near $z_1$
• Scenario 2 has >50% of data near $z_n$

A sensible estimator must recognize these as different situations and produce different estimates. But then the adversary can choose which scenario to create, making the change in the estimate arbitrarily large.

The Formal Statement:

For any location or scale estimator, the maximum achievable breakdown point is:

$$\varepsilon^* \leq \frac{\lfloor n/2 \rfloor + 1}{n} \xrightarrow{n \to \infty} 0.5$$

This is called the 50% breakdown point barrier.

Achieving the 50% breakdown point in regression is harder than for location estimation. The design matrix X introduces complications—outliers can be extreme in X-space (leverage points), Y-space (vertical outliers), or both.

Least Median of Squares (LMS)

Proposed by Rousseeuw (1984), LMS minimizes the median of squared residuals:

$$\hat{\boldsymbol{\beta}}{\text{LMS}} = \arg\min{\boldsymbol{\beta}} \text{median}_i(r_i^2)$$

Properties:

• Breakdown point: $\varepsilon^* \approx 50%$ (achieves the barrier!)
• Very robust to outliers in both X and Y
• But: only $n^{-1/3}$ convergence rate (inefficient)
• Computationally expensive (NP-hard exactly, approximations used)

Least Trimmed Squares (LTS)

Also by Rousseeuw, LTS minimizes the sum of the $h$ smallest squared residuals:

$$\hat{\boldsymbol{\beta}}{\text{LTS}} = \arg\min{\boldsymbol{\beta}} \sum_{i=1}^{h} r_{(i)}^2$$

where $r_{(i)}^2$ are the order statistics and $h \approx n/2$ for 50% breakdown.

Properties:

• Breakdown point: $(n - h + 1)/n \approx 50%$ for $h \approx n/2$
• More efficient than LMS ($n^{-1/2}$ rate)
• Still requires global optimization (expensive)

S-Estimators

Minimize a robust scale of residuals:

$$\hat{\boldsymbol{\beta}}{S} = \arg\min{\boldsymbol{\beta}} \hat{\sigma}(r_1, \ldots, r_n)$$

where $\hat{\sigma}$ is an M-estimate of scale satisfying:

$$\frac{1}{n}\sum_{i=1}^n \rho\left(\frac{r_i}{\hat{\sigma}}\right) = K$$

for a bounded ρ-function and appropriately chosen constant $K$.

Properties:

• Breakdown point: up to 50% with appropriate ρ
• Better efficiency than LMS/LTS
• Foundation for MM-estimators

MM-estimators (introduced by Yohai, 1987) achieve the seemingly impossible: 50% breakdown point AND 95% efficiency under Gaussian errors.

The Two-Stage Approach:

Stage 1: High-Breakdown Initial Estimate Compute an S-estimate $\hat{\boldsymbol{\beta}}_S$ using a bounded ρ-function (e.g., bisquare with c yielding 50% breakdown). This gives:

• 50% breakdown point
• Low efficiency (~30%)
• A robust scale estimate $\hat{\sigma}_S$

Stage 2: Efficient Local Refinement Starting from $\hat{\boldsymbol{\beta}}_S$ and using the scale $\hat{\sigma}_S$ (held fixed), solve:

$$\hat{\boldsymbol{\beta}}{MM} = \arg\min{\boldsymbol{\beta}} \sum_{i=1}^n \rho^*\left(\frac{y_i - \mathbf{x}_i^\top \boldsymbol{\beta}}{\hat{\sigma}_S}\right)$$

where $\rho^*$ is a second (typically less bounded) function tuned for 95% efficiency.

Key Insight: The first-stage provides a "safe" starting point. The second stage only searches locally, so it can use a more efficient (less robust) criterion without risk of converging to an outlier-induced solution.

What's next:

We've now covered breakdown point—the ultimate measure of how much contamination an estimator can survive. The final page introduces influence functions—a complementary measure that describes how individual observations gradually affect estimates. Together, breakdown point and influence functions provide the complete picture of estimator robustness.