On the Stability of Empirical Risk Minimization in the Presence of Multiple Risk Minimizers

Benjamin I. P. Rubinstein, Aleksandr Simma

TL;DR

This paper investigates how the number of "best possible" solutions (risk minimizers) in a learning problem affects the stability of the learning algorithm. They prove that if there are multiple equally good solutions, the learning algorithm's stability degrades significantly, preventing fast convergence, thus resolving a conjecture in the field. This has implications for understanding why feature selection can be crucial in machine learning.

What Problem Does This Paper Address?

In machine learning, we often use Empirical Risk Minimization (ERM) to find a hypothesis (a model or classifier) that performs best on the training data. The "risk" is the expected error of a hypothesis on unseen data, and the "empirical risk" is the error on the training data. ERM aims to minimize this empirical risk.

A key property of learning algorithms is "algorithmic stability," which is conceptually similar to continuity. Intuitively, a stable algorithm shouldn't change its output drastically if you slightly alter the training data. Previous work by Kutin and Niyogi showed that for finite hypothesis spaces (where the set of possible models is limited), if there's a unique best model (risk minimizer) for the true underlying data distribution, ERM exhibits strong stability, scaling exponentially with the number of training samples. However, they conjectured that if there are multiple equally best models, this strong stability is lost, and ERM's convergence rate would be significantly slower, at best quadratic. This paper tackles this conjecture, specifically focusing on a weaker notion of stability called CV-stability.

Methods

The paper defines and works with several notions of algorithmic stability:

  • Weak Hypothesis Stability: Measures how much the predicted hypothesis changes when one training example is removed.
  • CV-Stability (Cross-Validation Stability): Measures how much the predicted hypothesis changes when one training example is replaced by a new one from the data distribution.
  • Overlap Stability: Measures how much the empirical risk of the predicted hypothesis changes when one training example is replaced.
  • Training Stability: A combination of CV-stability and Overlap stability.

The core of the paper's contribution lies in proving the conjecture for CV-stability. They achieve this by:

  1. Focusing on the case of two risk minimizers: They analyze the scenario where the hypothesis space has exactly two equally optimal solutions.
  2. Analyzing the probability of switching: They show that when ERM is applied to a sample, the probability that the learned hypothesis belongs to the set of risk minimizers is high (exponentially increasing with sample size).
  3. Quantifying the "switch": They then analyze the probability that the learned hypothesis switches between these two risk minimizers when a single data point is perturbed. They use probabilistic tools, including Chernoff bounds and approximations for binomial distributions, to show that this probability of switching is non-negligible.
  4. Connecting to CV-stability: By showing that the learned hypothesis can change significantly (switch between risk minimizers) with a non-trivial probability when a single data point is altered, they demonstrate that CV-stability is degraded.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on abstract hypothesis spaces and data distributions rather than specific datasets.

Key Insights and Ideas

  • The "Curse of Multiple Minima": The presence of multiple equally good solutions in the hypothesis space fundamentally limits the stability of ERM. This is a crucial insight for understanding why algorithms might struggle to converge quickly in certain scenarios.
  • Stability as a Proxy for Convergence: The paper reinforces the idea that algorithmic stability is a strong indicator of generalization performance and convergence rates. Degraded stability directly implies slower convergence.
  • Feature Selection Motivation: The authors highlight that this theoretical result has practical implications. If learning from raw features leads to multiple risk minimizers (e.g., due to irrelevant features), ERM might perform poorly. This provides a theoretical justification for why feature selection, which aims to create a more "unique" optimal solution, can be beneficial.
  • Resolution of a Conjecture: The paper definitively resolves a specific conjecture made by Kutin and Niyogi regarding the stability limitations imposed by multiple risk minimizers.

Key Results

  • The paper proves that for a finite hypothesis space with more than one risk minimizer, ERM is not (0, δ)-CV-stable for any δ = o(m⁻¹/²), where 'm' is the number of training samples. This means the stability degrades to at least a rate of O(m⁻¹/²).
  • Conversely, they show that ERM is (0, δ)-CV-stable for δ = O(m⁻¹/²). This establishes the precise rate of stability degradation.
  • These results positively resolve Conjecture 10.11 from Kutin and Niyogi's work.

Limitations and Future Work

  • Focus on Finite Hypothesis Spaces: The results are primarily for finite hypothesis spaces. Extending these findings to infinite-dimensional function spaces (like those used in deep learning) would be a significant next step.
  • Specific Stability Notions: The paper focuses on CV-stability. While this is a weaker notion than training stability, exploring the implications for other stability measures or for ERM itself in more complex settings could be valuable.
  • Two Risk Minimizers vs. Many: The proof is detailed for the case of two risk minimizers. While the theorem generalizes to |H*| > 1, the specific quantitative bounds might differ for a larger number of risk minimizers.
  • Practical Implications of Feature Selection: While the paper provides theoretical motivation, further empirical studies could explore how different feature selection methods impact the number of risk minimizers and the resulting ERM stability.

Summary updated

Abstract

Recently, Kutin and Niyogi investigated several notions of algorithmic stability-a property of a learning map conceptually similar to continuity-showing that training stability is sufficient for consistency of empirical risk minimization (ERM) while distribution-free CV-stability is necessary and sufficient for having finite VC-dimension. This paper concerns a phase transition in the training stability of ERM, conjectured by the same authors. Kutin and Niyogi proved that ERM on finite hypothesis spaces containing a unique risk minimizer has training stability that scales exponentially with sample size, and conjectured that the existence of multiple risk minimizers prevents even super-quadratic convergence. We prove this result for the strictly weaker notion of CV-stability, positively resolving the conjecture.
BibTeX
@article{rubinstein2012stability,
  author = {Benjamin I. P. Rubinstein and Aleksandr Simma},
  title = {{On the Stability of Empirical Risk Minimization in the Presence of Multiple Risk Minimizers}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  doi = {10.1109/tit.2012.2191681},
}
Figure