The Relative Instability of Model Comparison with Cross-validation

• URL: http://arxiv.org/abs/2508.04409v1
• Date: Wed, 06 Aug 2025 12:54:56 GMT
• Title: The Relative Instability of Model Comparison with Cross-validation
• Authors: Alexandre Bayle, Lucas Janson, Lester Mackey,
• Abstract summary: Cross-validation can be used to provide a confidence interval for the test error of a stable machine learning algorithm.<n>Relative stability cannot easily be derived from existing stability results, even for simple algorithms.<n>We empirically confirm the invalidity of CV confidence intervals for the test error difference when either soft-thresholding or the Lasso is used.
• Score: 65.90853456199493
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existing work has shown that cross-validation (CV) can be used to provide an asymptotic confidence interval for the test error of a stable machine learning algorithm, and existing stability results for many popular algorithms can be applied to derive positive instances where such confidence intervals will be valid. However, in the common setting where CV is used to compare two algorithms, it becomes necessary to consider a notion of relative stability which cannot easily be derived from existing stability results, even for simple algorithms. To better understand relative stability and when CV provides valid confidence intervals for the test error difference of two algorithms, we study the soft-thresholded least squares algorithm, a close cousin of the Lasso. We prove that while stability holds when assessing the individual test error of this algorithm, relative stability fails to hold when comparing the test error of two such algorithms, even in a sparse low-dimensional linear model setting. Additionally, we empirically confirm the invalidity of CV confidence intervals for the test error difference when either soft-thresholding or the Lasso is used. In short, caution is needed when quantifying the uncertainty of CV estimates of the performance difference of two machine learning algorithms, even when both algorithms are individually stable.

Related papers

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints [5.68594452139461]
  We show that testing the stability of a black-box algorithm is impossible in settings where the data lies in an uncountably infinite space.<n>We develop a unified framework for quantifying the hardness of testing algorithmic stability, which establishes that across all settings, if the available data is limited then exhaustive search is essentially the only universally valid mechanism for certifying algorithmic stability.
  arXiv  Detail & Related papers  (2024-05-23T23:51:25Z)
• Binary Classification with Confidence Difference [100.08818204756093]
  This paper delves into a novel weakly supervised binary classification problem called confidence-difference (ConfDiff) classification. We propose a risk-consistent approach to tackle this problem and show that the estimation error bound the optimal convergence rate. We also introduce a risk correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven.
  arXiv  Detail & Related papers  (2023-10-09T11:44:50Z)
• Distributionally Robust Learning with Stable Adversarial Training [34.74504615726101]
  Machine learning algorithms with empirical risk minimization are vulnerable under distributional shifts. We propose a novel Stable Adversarial Learning (SAL) algorithm that leverages heterogeneous data sources to construct a more practical uncertainty set.
  arXiv  Detail & Related papers  (2021-06-30T03:05:45Z)
• Machine Unlearning via Algorithmic Stability [31.809738694273623]
  We study the problem of machine unlearning and identify a notion of Total Variation (TV) stability. For convex risk minimization problems, we design TV-stable algorithms based on noisy Gradient Descent (SGD) Our techniques to generalize our algorithms are differentially private as well.
  arXiv  Detail & Related papers  (2021-02-25T21:16:56Z)
• Cross-validation Confidence Intervals for Test Error [83.67415139421448]
  This work develops central limit theorems for crossvalidation and consistent estimators of its variance under weak stability conditions on the learning algorithm. Results are the first of their kind for the popular choice of leave-one-out cross-validation.
  arXiv  Detail & Related papers  (2020-07-24T17:40:06Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• Stable Adversarial Learning under Distributional Shifts [46.98655899839784]
  Machine learning algorithms with empirical risk minimization are vulnerable under distributional shifts. We propose Stable Adversarial Learning (SAL) algorithm that leverages heterogeneous data sources to construct a more practical uncertainty set.
  arXiv  Detail & Related papers  (2020-06-08T08:42:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.