The Robustness of Estimator Composition

Pingfan Tang, Jeff M. Phillips

In modern data science, raw data points are rarely the final output. Instead, data is processed through complex "analysis pipelines" consisting of multiple layers—for example, summarizing sensor readings per person, and then summarizing those summaries across an entire population. While we have well-established measures for the robustness of a single estimator, understanding the robustness of these multi-stage pipelines has remained a challenge.

This paper provides the first formal mathematical framework for understanding how robustness "decays" when multiple statistical estimators are chained together. The authors prove a striking "product rule": the robustness of a composite estimator (e.g., a median of medians) is generally the product of the robustness of its individual parts. This means that long analysis chains can become surprisingly fragile, even if every individual step is considered "robust."

Measuring Robustness: The Breakdown Point

To quantify robustness, the authors utilize and expand upon the concept of the breakdown point—informally, the minimum fraction of data points that must be significantly modified to force the estimator's output to become arbitrary or "garbage."

The paper introduces two formal definitions to handle composite functions:

  1. Asymptotic Breakdown Point: The traditional measure of the fraction of data that must be moved to infinity to break the estimator.
  2. Asymptotic Onto-Breakdown Point: A more rigorous definition introduced by the authors. It measures the minimum fraction of data needed to be modified to force the estimator to output any arbitrary value within its range.

The Product Rule of Robustness Decay

The core of the paper is a mathematical proof demonstrating that for a two-stage composition (an estimator $E_1$ followed by $E_2$), the total breakdown point $\beta$ is equal to the product of their individual breakdown points: $\beta = \beta_1 \times \beta_2$. This is subsequently extended to $m$-level compositions.

This leads to several critical insights for pipeline design:

  • Multiplicative, Not Additive Decay: Robustness degrades multiplicatively. If a three-layer pipeline uses an estimator with a breakdown point of 0.5 at each layer (like a median), the total pipeline breakdown point is $0.5 \times 0.5 \times 0.5 = 0.125$. The entire system can be compromised by just 12.5% of outlier data.
  • The "Onto" Nuance: For the product rule to hold strictly, the first estimator must be "onto" (able to reach any value in the next stage's input space). If this condition isn't met, it is sometimes possible to "cheat" the product rule and create more robust compositions.
  • Strategic Balancing: By understanding this mathematical relationship, data scientists can choose specific estimators to balance each other. For instance, pairing a "low" percentile estimator in the first stage with a "high" percentile estimator in the second stage can help recover some lost robustness.

Simulation and Key Results

To demonstrate the practical implications of their theorems, the authors simulated an adversarial attack using gradient descent. They aimed to "game" a system by modifying the minimum number of points required to move a composite $L_1$-median to a specific target.

Simulation of manipulating a composite estimator

In a 2D simulation of an $L_1$-median of $L_1$-medians, the authors successfully moved the final estimate to a distant "target point." Because the breakdown point of a single median is 0.5, the theory predicts the composite breakdown point is $0.5 \times 0.5 = 0.25$. The simulation confirmed this, showing that an adversary could completely control the final output by strategically modifying exactly 25% of the underlying data points.

Limitations and Future Directions

While powerful, the "product rule" relies on specific mathematical conditions (such as the "onto" property and the existence of certain limits) that may not apply to highly exotic estimators. Additionally, the breakdown point is inherently a "worst-case" metric; it describes the threshold for complete failure rather than how the estimator behaves under average, everyday noise.

Future work suggested by the authors includes extending this theory to more complex "analysis graphs" beyond linear chains, ultimately paving the way for designing highly resilient automated data processing systems.

Summary updated

Abstract

We formalize notions of robustness for composite estimators via the notion of a breakdown point. A composite estimator successively applies two (or more) estimators: on data decomposed into disjoint parts, it applies the first estimator on each part, then the second estimator on the outputs of the first estimator. And so on, if the composition is of more than two estimators. Informally, the breakdown point is the minimum fraction of data points which if significantly modified will also significantly modify the output of the estimator, so it is typically desirable to have a large breakdown point. Our main result shows that, under mild conditions on the individual estimators, the breakdown point of the composite estimator is the product of the breakdown points of the individual estimators. We also demonstrate several scenarios, ranging from regression to statistical testing, where this analysis is easy to apply, useful in understanding worst case robustness, and sheds powerful insights onto the associated data analysis.
BibTeX
@inproceedings{tang2016robustness,
  author = {Pingfan Tang and Jeff M. Phillips},
  title = {{The Robustness of Estimator Composition}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=BybzkdWd-S},
}

Loading related content...

Figure