On the relationship between concentration inequalities and maximum bias for depth estimators

This paper establishes a unified framework using concentration inequalities to analyze the statistical convergence and robustness of depth-based estimators, explicitly deriving their maximum bias curves and breakdown points while demonstrating how slight variations in these inequalities reveal distinct robustness behaviors across different depth formulations.

The Gist

Imagine you are trying to find the "heart" of a crowd of people. In a perfect world, everyone is standing in a neat circle, and the center is obvious. But in the real world, some people are shouting, some are running around wildly, and a few are even trying to drag the whole group in the wrong direction. These are the outliers or contaminants.

This paper is about building a better compass to find that center, even when the crowd is chaotic. It focuses on a statistical concept called Depth, which is essentially a way of measuring how "deeply" a point is buried inside a cloud of data.

Here is a breakdown of the paper's main ideas using simple analogies:

1. The Problem: Finding the Center in a Messy Crowd

In statistics, we often want to find the "average" or the "middle" of a dataset.

• The Old Way: If you just take the average (the mean), one crazy outlier (like a billionaire in a room of teachers) can pull the average so far away that it no longer represents anyone.
• The New Way (Depth): Instead of averaging, we look for the point that is most "surrounded" by data. Think of it like a game of "hot potato." If you are standing in the middle of a circle of friends, you are "deep." If you are on the edge, you are "shallow." The goal is to find the person who is the hardest to push out of the circle.

The paper looks at how to do this not just for a single number (like height), but for complex, multi-dimensional data (like height, weight, and income all at once) and for relationships between variables (like how income affects spending).

2. The "Explosion" and "Implosion" (Bias)

The authors are worried about two specific ways a bad compass can fail:

• Explosion: The compass points so far away that it goes to infinity. (Imagine the "center" of the crowd suddenly teleporting to Mars because one person ran there).
• Implosion: The compass shrinks the world down to nothing. (Imagine the "center" collapsing into a single point, ignoring all the spread of the data).

The paper introduces a concept called Maximum Bias. This is like asking: "What is the worst possible thing a bad actor could do to our data to make our compass point in the wrong direction?" They want to know the limit of how much the data can be messed up before the compass breaks.

3. The Secret Weapon: Concentration Inequalities

This is the technical heart of the paper, but think of it as a safety net.
Mathematicians have developed "Concentration Inequalities." These are like rules that say: "If you have enough data, your compass will stay within this specific box, no matter what."

The authors discovered a clever trick. They realized that the size of this "safety box" is directly related to the Maximum Bias.

• The Analogy: Imagine you are trying to guess the weight of a watermelon. You have a scale that is slightly broken. The "Concentration Inequality" tells you how much the scale might be off. The authors showed that if you look closely at the math of this safety box, you can actually see exactly how much the scale is broken (the bias) before you even start weighing the watermelon.

4. The "Deepest" Scatter Matrix (The Shape of the Cloud)

Usually, we just find the center. But sometimes we need to know the shape of the data cloud (is it a fat circle? a long thin oval?). This is called the Scatter Matrix.

• The paper introduces a "Deepest Scatter Matrix." It's like trying to find the perfect oval shape that fits snugly around the crowd.
• The Discovery: They proved that this "Deepest" method is incredibly robust. It can handle up to 33% (1/3) of the crowd being crazy outliers before the shape of the oval breaks completely. This is the same limit as the famous "Tukey's Median," which is the gold standard for robust statistics.

5. The Trap of Doing Two Things at Once

In Section 5, the authors found a surprising trap.

• Scenario A: You find the center of the crowd, then you find the spread separately. This works great.
• Scenario B: You try to find the center and the spread simultaneously in one giant calculation.
• The Result: The simultaneous method (Scenario B) is much more fragile. It breaks down with far fewer outliers (around 20-25%).
• The Lesson: Sometimes, trying to solve two problems at once makes you weaker. It's like trying to juggle while walking a tightrope; if you separate the tasks, you might be more stable.

6. The Simulation (The Stress Test)

Finally, the authors ran thousands of computer simulations. They created messy crowds with different numbers of crazy outliers and tested various "compasses" (estimators).

• The Winner: They found that a specific type of estimator called the MM-estimator generally performed the best. It was like a Swiss Army knife: it stayed accurate even when the data was messy, and it didn't lose its precision when the data was clean.
• The Loser: The "Deepest" estimator (the one they studied theoretically) was very robust but sometimes a bit slow or less precise in small groups.

Summary

This paper is a bridge between two worlds:

1. Theoretical Math: Proving that if you use "Depth" to find the center and shape of data, you have a mathematical guarantee that it won't break until 33% of your data is corrupted.
2. Practical Reality: Showing through simulations that while these "deepest" methods are theoretically strong, other robust methods (like MM-estimators) often perform better in real-world, messy situations.

The Big Takeaway: If you are analyzing data that might have errors or outliers, don't just trust the average. Use "Depth" to find the core, but be careful about trying to solve for everything at once, and know that there is a mathematical limit (the 1/3 rule) to how much chaos your model can handle before it gives up.

Technical Summary

Here is a detailed technical summary of the paper "On the relationship between concentration inequalities and maximum bias for depth estimators" by Jorge G. Adrover and Marcelo Ruiz.

1. Problem Statement

The paper addresses the challenge of evaluating the robustness of statistical depth estimators (such as Tukey's median, depth-based scatter matrices, and regression estimators) under data contamination. While the breakdown point (the maximum proportion of contamination an estimator can withstand before becoming unbounded) is a standard robustness metric, it is a binary threshold that does not describe the estimator's behavior before breakdown.

The authors aim to:

1. Establish a unified framework linking concentration inequalities (which govern statistical convergence rates) with the asymptotic maximum bias (the worst-case deviation of an estimator under contamination).
2. Explicitly derive the maximum bias curves and breakdown points for the deepest scatter matrix estimators introduced by Chen, Gao, and Ren (2018a).
3. Investigate how slight variations in depth formulations affect robustness, specifically comparing two joint location-scale depth estimators.
4. Provide a finite-sample numerical comparison of various robust scatter estimators, including the deepest estimator, to validate theoretical findings.

2. Methodology

Theoretical Framework

The authors utilize Huber's $\epsilon$-contamination neighborhood, where the true distribution $P$ is a mixture of a central model $P_0$ (e.g., multivariate normal) and an arbitrary contaminating distribution $G$:
$$P_\epsilon = (1-\epsilon)P_0 + \epsilon G$$

They analyze affine equivariant and Fisher-consistent functionals. The core methodology involves:

• Concentration Inequalities: Building upon the work of Chen, Gao, and Ren (2018a), the authors refine existing concentration inequalities for depth estimators. They demonstrate that the constants in these inequalities are directly governed by the asymptotic maximum bias of the estimator.
• Bias Derivation: Instead of relying solely on the concentration bound's generic term (e.g., $\epsilon^2$), they explicitly substitute the maximum bias function $B(\epsilon)$ into the inequality. This allows the inequality to visualize the estimator's behavior as a function of contamination level $\epsilon$.
• Optimization: For the scatter matrix, they solve an optimization problem to find the "deepest" matrix $\hat{\Gamma}$ under point-mass contaminations. They analyze the eigenvalues of the resulting matrix to determine when they explode (go to infinity) or implode (go to zero), which defines the breakdown point.

Numerical Study

A Monte Carlo simulation study was conducted to compare finite-sample performance.

• Estimators Compared: Sample Covariance (SCOV), Minimum Volume Ellipsoid (MVE), Minimum Covariance Determinant (MCD), S-estimators (SE), Rocke S-estimators, MM-estimators, Stahel-Donoho (SD), and the Deepest Estimator (MDepth).
• Performance Metrics:
  • Maximum Bias ($B$): Measured via the ratio of eigenvalues of the estimated scatter matrix to the true matrix (explosion and implosion).
  • Condition Number (CN): Used as a proxy for bias stability.
  • Efficiency: Measured as the ratio of Mean Absolute Error (MAE) of the sample covariance to the robust estimator under the central normal model.
• Scenarios: Various dimensions ($p=2, 5, 10, 15$), sample sizes ($n=10p, 40p, 500p$), and contamination levels ($\epsilon = 0.1, 0.2$) with point-mass outliers at varying distances ($k$).

3. Key Contributions

A. Linking Concentration and Bias

The paper provides a theoretical proof that the maximum bias function appears naturally within the concentration inequalities of depth estimators.

• For Tukey's median and the deepest scatter matrix, the concentration bound is shown to be:
  $$P(\|\hat{\theta} - \theta\|^2 \leq C \cdot \max\{p/n, B(\epsilon)^2\} + \dots) \geq 1-\delta$$
  This clarifies that the estimator's convergence rate is limited by the maximum bias once the sample size is large enough.

B. Maximum Bias and Breakdown Point of Deepest Scatter Matrices

The authors explicitly derive the maximum bias curve for the deepest scatter matrix estimator (Chen, Gao, and Ren, 2018a) under known location:

• Breakdown Point: They prove the asymptotic breakdown point is $\epsilon^* = 1/3$. This matches the breakdown point of Tukey's median, confirming that the deepest scatter matrix inherits the robustness properties of the deepest location estimator.
• Bias Curve: They derive the exact analytical form of the bias function $B(\epsilon)$, showing how the eigenvalues of the estimated scatter matrix expand or contract as $\epsilon$ approaches $1/3$.

C. Location-Scale Depth Formulations

The paper compares two depth formulations for joint location-scale estimation:

1. Separate Estimation ($D^1_{LS}$): Maximizing depth for location and scale independently. This yields the standard Median and Median Absolute Deviation (MAD), with a breakdown point of 0.5.
2. Joint Estimation ($D^2_{LS}$): Maximizing a single depth function that simultaneously considers location and scale constraints.
   • Finding: The joint estimator has a significantly lower breakdown point ($1/5 < \epsilon^* < 1/4$).
   • Implication: This highlights a trade-off where simultaneous optimization can degrade robustness compared to separate optimization, a phenomenon also observed in simultaneous M-estimation.

4. Results

Theoretical Results

• The deepest scatter matrix estimator achieves the optimal breakdown point of $1/3$ for multivariate scatter.
• The derived maximum bias curves confirm that the estimator remains bounded and well-behaved for $\epsilon < 1/3$, but becomes unbounded (breaks down) as $\epsilon \to 1/3$.
• The joint location-scale depth estimator is shown to be less robust than its separate counterparts, with a breakdown point strictly less than $0.25$.

Numerical Results

• MM-Estimators: Consistently demonstrated the best overall performance, offering the lowest maximum bias (both explosion and implosion) across small to moderate sample sizes and dimensions. They maintained high efficiency (near 95%) under normality.
• Rocke S-estimators: Performed exceptionally well in high dimensions ($p \geq 10$) and large sample sizes, often outperforming MM estimators in terms of bias stability.
• Deepest Estimator (MDepth): While theoretically sound, the numerical study showed it had higher bias and lower efficiency compared to MM and Rocke estimators in finite samples, particularly in low dimensions. Its performance improved slightly with larger sample sizes but remained competitive rather than superior.
• MCD and MVE: Showed competitive performance in low dimensions but suffered from lower efficiency and higher bias in higher dimensions compared to S- and MM-estimators.
• Efficiency vs. Robustness: As dimension $p$ increased, S-estimators (SE) showed a marked increase in efficiency (approaching the sample covariance) but at the cost of reduced robustness in finite samples, confirming the "curse of dimensionality" for certain robust methods.

5. Significance

1. Unification of Theory: The paper bridges the gap between statistical learning theory (concentration inequalities) and robust statistics (maximum bias). It provides a rigorous justification for why concentration bounds for depth estimators depend on the contamination level $\epsilon$ in the specific way they do.
2. Practical Guidance for Estimator Selection: The numerical study offers critical insights for practitioners. While the "deepest" estimator is theoretically optimal in terms of breakdown point, MM-estimators and Rocke S-estimators often provide superior finite-sample performance in terms of bias and efficiency.
3. Warning on Joint Estimation: The finding that joint location-scale depth estimation reduces the breakdown point serves as a cautionary note against blindly combining robustness criteria into a single optimization problem without analyzing the resulting robustness properties.
4. Benchmarking: The extensive simulation provides a comprehensive benchmark for the behavior of modern robust scatter estimators under various contamination scenarios, filling a gap in the literature regarding finite-sample bias curves for these methods.

In conclusion, the paper successfully demonstrates that while depth-based estimators offer strong theoretical robustness (breakdown point of 1/3), their practical performance in finite samples is highly dependent on the specific algorithm used, with MM-estimators currently leading in a balance of bias control and efficiency.