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
• 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

• Crossing the Validation Crisis: Cross-Validation Reduces Benchmarking Variance Surprisingly Well [15.198198886832595]
  We show that cross-validation improves markedly confidence when evaluating and comparing learning algorithm performances.<n>We introduce the concept of sample gain, which quantifies the virtual data augmentation achieved by using multiple cross-validation splits.
  arXiv  Detail & Related papers  (2026-06-10T18:03:19Z)
• Unveiling the Entropy Dynamics of Chain-of-Thought Reasoning [81.57028614960576]
  We show that the Confidence Region possesses two critical properties: 1) High Reliability -- answers in the confidence region become highly accurate and stable, and 2) High Redundancy -- models generate unnecessary tokens long after reaching the correct answer.<n>These properties unlock more efficient and reliable inference strategies.
  arXiv  Detail & Related papers  (2026-06-01T10:11:14Z)
• Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent [2.0999222360659613]
  Recent work has identified stability as a sufficient condition for valid inference under adaptivity.<n>This paper develops a systematic theory of stability for bandit algorithms based on mirror descent.<n>A modified variant of regularized-EXP3 maintains normality of empirical arm means even in the presence of adversarial corruptions.
  arXiv  Detail & Related papers  (2026-03-10T19:27:47Z)
• 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.