Algorithmic stability via ensembling

• URL: http://arxiv.org/abs/2609.10428v1
• Date: Wed, 09 Sep 2026 16:39:35 GMT
• Title: Algorithmic stability via ensembling
• Abstract summary: Algorithmic stability refers to the property of an algorithm being insensitive to perturbations of the input data.<n>We develop a general framework to quantify the extent to which any ensembling strategy defined via averaging can yield stability guarantees for any type of data perturbation.
• Score: 4.404496835736175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithmic stability refers to the property of an algorithm being insensitive to perturbations of the input data, where the type of perturbation may vary depending on the setting. In this work, we develop a general framework to quantify the extent to which any ensembling strategy defined via averaging can yield stability guarantees for any type of data perturbation. Our main theoretical result is a guarantee on the stability of this ensembled algorithm, given in terms of the norm of a certain covariance operator that describes the ensembling process. We show how our general framework yields interpretable and intuitive insights in several examples of perturbations of practical interest, and provides much sharper guarantees than those obtained from privacy considerations.

Related papers

• Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees [42.99716861039235]
  We show that the shuffling strategy can be used to solve variational inequality problems.<n>We provide the first theoretical convergence estimates for shuffling methods in this context.<n>We validate our findings through extensive experiments on diverse benchmark variational inequality problems.
  arXiv  Detail & Related papers  (2025-09-04T12:00:18Z)
• 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)
• FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures [3.377298662011438]
  This paper presents a novel algorithm that leverages Gradient Descent strategies in conjunction with Random Features to augment the scalability of Conic Particle Gradient Descent (CPGD)<n>We provide rigorous mathematical proofs demonstrating the following key findings: $mathrm(i)$ The total variation norms of the solution measures along the descent trajectory remain bounded, ensuring stability and preventing undesirable divergence; $mathrm(ii)$ We establish a global convergence guarantee with a convergence rate of $O(log(K)/sqrtK)$ over $K$, showcasing the efficiency and effectiveness of
  arXiv  Detail & Related papers  (2023-12-10T20:41:43Z)
• Towards stable real-world equation discovery with assessing differentiating quality influence [52.2980614912553]
  We propose alternatives to the commonly used finite differences-based method. We evaluate these methods in terms of applicability to problems, similar to the real ones, and their ability to ensure the convergence of equation discovery algorithms.
  arXiv  Detail & Related papers  (2023-11-09T23:32:06Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms [61.59448949684493]
  We provide the stability and generalization analysis of compositional descent algorithms built from training examples. We establish the uniform stability results for two popular compositional gradient descent algorithms, namely SCGD and SCSC. We derive-independent excess risk bounds for SCGD and SCSC by trade-offing their stability results and optimization errors.
  arXiv  Detail & Related papers  (2023-07-07T02:40:09Z)
• Distributed Stochastic Optimization under a General Variance Condition [13.911633636387059]
  Distributed optimization has drawn great attention recently due to its effectiveness in solving largescale machine learning problems. We revisit the classical Federated Averaging (Avg) and establish the convergence results under only a mild variance for smooth non objective functions. Almost a stationary convergence point is also established under the gradients condition.
  arXiv  Detail & Related papers  (2023-01-30T05:48:09Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. This research provides guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice.
  arXiv  Detail & Related papers  (2022-01-21T04:25:35Z)
• Black box tests for algorithmic stability [10.495496415022064]
  Knowing an algorithm's stability properties is often useful for many downstream applications. Many modern algorithms currently used in practice are too complex for a theoretical analysis of their stability properties.
  arXiv  Detail & Related papers  (2021-11-30T16:36:58Z)
• Stability Analysis of Unfolded WMMSE for Power Allocation [80.71751088398209]
  Power allocation is one of the fundamental problems in wireless networks. It is essential that the output power allocation of these algorithms is stable with respect to input perturbations. In this paper, we focus on UWMMSE, a modern algorithm leveraging graph neural networks.
  arXiv  Detail & Related papers  (2021-10-14T15:44:19Z)
• Algorithmic Stability and Generalization of an Unsupervised Feature Selection Algorithm [20.564573628659918]
  Algorithmic stability is a key characteristic of an algorithm regarding its sensitivity to perturbations of input samples. In this paper, we propose an innovative unsupervised feature selection algorithm attaining this stability with provable guarantees.
  arXiv  Detail & Related papers  (2020-10-19T12:25:39Z)
• Stable and consistent density-based clustering via multiparameter persistence [49.1574468325115]
  We consider the degree-Rips construction from topological data analysis.<n>We analyze its stability to perturbations of the input data using the correspondence-interleaving distance.<n>We integrate these methods into a pipeline for density-based clustering, which we call Persistable.
  arXiv  Detail & Related papers  (2020-05-18T19:45:04Z)

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.