Algorithmic Stability

Follow this topic Ask about this topic

Momentum

3 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 35

Oct 5, 2026cs.LG

Certification-Enhanced Generalization Bounds

We investigate the use of formal methods to provide tight and sound generalization bounds for learning algorithms. By casting the traditional notion of algorithmic stability as a specification to be verified, we demonstrate that recent advances in reachability analysis can yield provable bounds on the generalization of a given model and algorithm on a sample dataset. As sample-specific algorithmic stability is insufficient to bound the usual distributional notion of generalization, we develop a novel concentration inequality to connect the sample-specific results of formal certification algorithms to the required distributional analysis for bounding the expected generalization gap. The resulting framework enables the analysis of prior generalization bounds to extend far beyond their original restrictive assumptions. Our approach computes sound bounds on the expected generalization gap in a constant number of algorithm runs without making any analytical assumptions on the algorithm; to achieve non-vacuous bounds we only require that the certified reachable parameter set is bounded --- a condition that we do not assume but formally verify. In practice, we demonstrate that our framework provides formal generalization guarantees that are orders of magnitude tighter than alternative sound computational approaches at scales ranging from toy datasets to fine-tuning classification heads on top of modern large language models. While we implement certification-enhanced versions of several well-known stability results, future extensions of our approach will enable tighter bounds and enhanced practical adoption across the spectrum of modern generalization bounds.

Leo Elmecker-Plakolm, Matthew Wicker

Department of Computing Imperial College London London, SW7 2AZ, UK

Algorithmic Stability Generalization Bounds

Sep 16, 2026econ.EM

Stable Policy Learning

In evidence-based policymaking, typically one experimental sample is observed, then a learned policy recommendation is implemented at scale. Policies learned from the experimental data can perform well in expected welfare, yet random sampling in the experiment can produce recommendations with poor welfare outcomes. In this paper, we ask: how should policy learning algorithms balance expected welfare against sampling risk? Our main contribution is to show that algorithmic stability plays a central role in characterizing and navigating the tradeoff. Intuitively, if a policy learning algorithm's recommendation remains stable when one experimental unit is replaced, then that algorithm has limited sampling risk. We propose a method for policy learning called policy-vote bagging, which learns treatment decisions on many subsamples then averages their votes into treatment probabilities. Relative to using one subsample, averaging across subsamples preserves expected welfare and improves expected utility for a risk-averse researcher. We derive sharp bounds linking estimation accuracy, subsample size, and welfare variation, including an exact guarantee under CARA utility.

Harvey Barnhard, Giacomo Opocher, Rahul Singh

Harvard University · University of Mannheim

Algorithmic Stability Policy Learning

Sep 16, 2026eess.SP

Stable Filters for Generative Modeling of Graph Signals

Generating signals on graphs requires permutation-equivariant models that exhibit stability with respect to relative structural perturbations. While recent graph-aware Schrödinger bridge models incorporate topology information directly into their reference dynamics, it is unclear how perturbations of the graph propagate through these dynamics and affect the resulting generated distributions. In this paper, we analyze the structural stability of graph-aware continuous-time generative models whose drift combines a graph filter with a learned graph neural network. We derive explicit Wasserstein stability bounds that quantify the effect of relative graph perturbations on the generated distributions. Motivated by these bounds, we introduce a principled framework for designing stable graph filters that preserve the smoothing behavior of graph heat diffusion, while boosting structural stability. Experiments on synthetic and fMRI signals show our stable filters enhance structural robustness while matching or exceeding the generative quality of the heat equation baseline.

Martin Schmidt, Gonzalo Mateos

University of Rochester, Rochester, NY, USA

Graph Signal Processing Algorithmic Stability Generative Modeling

Sep 9, 2026math.ST

Algorithmic stability via ensembling

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.

Rina Foygel Barber, Richard J. Samworth

University of Chicago · University of Cambridge

Ensemble Learning Algorithmic Stability

Aug 25, 2026cs.LG

The Sharp Tail of Uniform Stability

Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a

γ

-uniformly stable algorithm with loss in

[0,L]

has generalization gap at most

O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right)

with probability

1-δ

. Whether an actual bounded-loss learning algorithm can realize the linear dependence on

\log(1/δ)

has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with

n

. The known learning lower bound holds only at constant probability. We close this gap. For every

n

, stability level

γ

, and loss bound

L

, we construct one deterministic

γ

-uniformly stable learning problem whose tail satisfies, simultaneously for

1\le p\le c n

,

\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge e^{-p}.

The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order

γp

without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.

Pahan Dewasurendra

Johns Hopkins University

Algorithmic Stability Generalization Bounds

Aug 10, 2026stat.ML

Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor

\log n

, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let

Z=(Z_1,\ldots,Z_n)

have independent coordinates and let

g_i(Z)

satisfy

\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n,

where

Z_{-i}

denotes all coordinates except

Z_i

. Assume additionally that changing any coordinate

Z_j

,

j\neq i

, changes

g_i

by at most

β

, we prove that, for every

p\ge2

, for every

p\ge2

,

\left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}.

This removes the

\log n

factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

Thanh Nguyen-Cung, Binh T. Nguyen

VinUniversity

Algorithmic Stability Statistical Learning Theory Generalization Bounds

Aug 6, 2026cs.AI

Stability of Ranking-dependent Pair-wise Comparison Patterns in the Analytic Hierarchy Process

The paper addresses several ranking-dependent decision support methods. Ordinal information on compared objects can be used to improve the quality of expert data during estimation and help reduce the number of comparisons that the experts need to perform. In the paper we compare three incomplete ranking-dependent pair-wise comparison patterns which can be used in the Analytic Hierarchy Process - Best-worst method, Best-Second Best (Top 2) method, and the original maximum difference method. The first two comparison patterns (and respective methods) are incomplete, while the third can be a complete one. We determine conditions under which these three methods can be compared in terms of stability to expert errors. We also present the results of a simulation-type experiment, in which the three methods are compared. The research allows us to define the most stable incomplete ranking-dependent pair-wise comparison pattern and reduce the number of comparisons without loss of credibility of expert session results. The research contributes to algorithmic, cognitive, and applied aspects of decision support in uncertain environments.

Vitaliy Tsyganok, Sergii Kadenko, Oleh Andriichuk

Institute for Information Recording National Academy of Sciences of Ukraine Kyiv, Ukraine 03113

Pairwise Comparison Pairwise Preference Evaluation Algorithmic Stability Multi-Criteria Decision Analysis

Jul 29, 2026stat.ML

Feature Bagging Provides Stability

We study feature bagging through the lens of algorithmic stability. Feature bagging is an ensemble strategy that aggregates base learners trained on randomly subsampled feature subsets, possibly in a data-dependent manner. We introduce feature instability (FI), the feature-axis analogue of instance instability (II), which measures sensitivity to removing a single feature. Smaller values of II or FI correspond to stronger stability, and our experiments show that FI captures generalization-relevant information complementary to II. Within this framework, we analyze feature bagging in both a parametric linear model and a model-free setting inspired by recursive feature subsampling in random forests. In both settings, we establish formal guarantees showing that feature bagging improves the relevant stability relative to its non-bagged counterpart, with larger improvements under more aggressive subsampling. We further show that a modest number of bagging rounds is sufficient to approach the infinite-bagging stability level.

Yuheng Ma, Qiang Sun

School of Statistics, East China Normal University · University of Toronto · MBZUAI

Ensemble Learning Algorithmic Stability Statistical Learning Theory

Jul 28, 2026cs.GT

Learning Dynamics of Strategic Publishers in Generative AI Ecosystems

Generative AI (GenAI) search systems are transforming how users access information. Unlike ranking-based search systems, where users observe a ranked list of documents, GenAI search systems, given a user's question, generate an answer, often accompanied by external sources (e.g., in the form of citations). Content creators (publishers) seeking to increase exposure might behave strategically and compete with other creators for users' attention. While publishers in ranking-based systems might strategically modify their content to improve its ranking, the incentives in generative systems take on a new form. Publishers may now gain exposure through generated responses and attributions to those responses. We introduce a novel game-theoretic model of the emerging GenAI ecosystem in which publishers compete for attribution-based exposure. We study the learning dynamics of strategic content creators under better-response dynamics. We associate the convergence of learning dynamics to equilibrium with ecosystem stability. Employing the notion of potential games, we study the stability of GenAI ecosystems under several known content selection mechanisms. We demonstrate the instability of mechanisms representing real-world modern systems and characterize a mechanism that induces a stable ecosystem. We conduct extensive simulations to analyze the stability and welfare of GenAI ecosystems under various mechanisms. The simulations support our theoretical findings and reveal an interplay among stability, publisher welfare, and user welfare. In particular, stable mechanisms do not necessarily maximize welfare, demonstrating an important trade-off for platform designers. We then introduce a study illustrating that the proper selection of the GenAI mechanism enables the manifestation of desired trade-offs between publisher welfare and the different sources of user welfare.

Sagie Dekel, Omer Madmon, Moshe Tennenholtz +1

Technion - Israel Institute of Technology

Generative Engine Optimization Algorithmic Stability Game Theory

Jul 25, 2026eess.IV

Stabilizing Deep Reconstruction Operators with Contractive Anchoring

Pretrained deep denoisers can be used to solve a wide range of model-based image reconstruction tasks via Plug-and-Play (PnP) and Regularization-by-Denoising (RED) algorithms, without retraining per task. These denoisers are trained only for single-step denoising. Using them as Image Reconstruction (IR) regularizers in an iterative process can destabilize reconstruction. A common failure mode is the peak-and-collapse behaviour: metrics such as PSNR improve for early iterations and then abruptly degrade, making these algorithms unreliable in practice. We propose a data-driven stabilization framework that (i) formalizes this instability of any IR operator through a local quantity and (ii) prevents collapse by regularizing this quantity adaptively, requiring no retraining or modification of the given pretrained network. Our key idea is to control the potentially unstable IR operator with a contractive operator whose stable iterates act as an anchor and prevent collapse. We further introduce an efficient family of trainable contractive operators that serve as strong anchors while remaining lightweight. Extensive experiments across proximal algorithms, denoiser architectures, noise levels, and imaging tasks show consistent, collapse-free performance and improved reliability of PnP and RED reconstruction.

Arghya Sinha, Trishit Mukherjee, Kunal N. Chaudhury

Indian Institute of Science, Bengalore, India

Algorithmic Stability Image Reconstruction Image Inverse Problems

Jul 2, 2026cs.NE

Mechanism and Stability Analysis of Metabolic Closed-Loop Metaheuristics

This paper studies the Metabolic Multi-Agent Optimizer (MMAO) at the framework level rather than at the implementation or benchmark level. The central question is whether the metabolic resource loop of private energy, communal budget, role drift, and lifecycle turnover has a framework-level interpretation beyond narrative metaphor. We introduce a generic MMAO state model that abstracts away domain-specific move operators while retaining the resource bookkeeping that defines the framework. Under mild bounded-gain and bounded-spending assumptions, we establish boundedness and nonnegativity properties for private energy, communal budget, role state, and active population size. We then characterize three endogenous behavioral regimes of the loop: contraction under sustained resource deficit, reinvestment under surplus communal accumulation, and search redistribution under heterogeneous marginal returns across agents or subgroups. The analysis is intentionally conservative. It does not claim global convergence of the full adaptive system, universal superiority over specialist optimizers, or a complete stationary characterization of the resulting process. Instead, it identifies which internal regulation properties are generic consequences of the loop and which remain implementation specific. A compact mechanism-validation package on representative continuous and discrete MMAO realizations provides supporting empirical evidence for this reading, but is not intended to replace a full benchmark study. The resulting contribution is therefore a bounded, regenerative, resource-regulated interpretation of MMAO, rather than a complete proof of all adaptive behaviors of the full algorithm family.

Jinliang Xu, Liping Ma

independent researcher in Beijing, China

Multi-Agent System Optimization Algorithmic Stability Metaheuristic Optimization Multi-Agent Systems

Jun 26, 2026cs.LG

Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator. While linear averaging preserves the monotonicity of gradient updates, this property is often violated when gradients are aggregated non-affinely, as in modern pipelines enforcing constraints like adaptivity, privacy, robustness or fairness. Whether it is possible to design non-affine aggregation rules that maintain monotonicity has remained an open question. We answer this question negatively: we prove that the monotonicity of aggregated gradients is preserved if and only if the aggregation rule is positively affine. Consequently, non-affine aggregation prevents steady convergence and substantially degrade algorithmic stability. We quantify these drawbacks and propose a path forward by identifying sufficient conditions under which monotonicity can be restored. Our results provide a unified theoretical framework explaining the disparate failure modes observed in modern learning systems.

Thomas Boudou, Batiste Le Bars, Nirupam Gupta +1

PreMeDICaL team, Inria, Idesp, Inserm, Universit´e de Montpellier, Montpellier, France · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France · Department of Computer Science, University of Copenhagen, Copenhagen, Danemark

Optimization Convergence Analysis Algorithmic Stability

Jun 24, 2026stat.ML

Stabilizing black-box algorithms through task-oriented randomization

As black-box models become foundational to modern research, ensuring their stability is paramount for the realization of trustworthy artificial intelligence. The inherent diversity of inputs - ranging from structured Gaussian distributions to complex data with unknown structures - poses a significant challenge: how to stabilize black-box outputs while effectively leveraging available prior information. This paper introduces a task-oriented randomization methodology that adaptively tailors its strategy to the underlying generative mechanisms of the input data, specifically addressing unstructured complexities. A comprehensive suite of stability guarantees is proposed. Beyond establishing rigorous theoretical foundations for stability, the research provides a detailed analysis of the intrinsic trade-off between stability and exploration. Motivated by the architecture of Large Language Models, the framework is further extended to top-k ranking problems. The validity and effectiveness of the proposal are demonstrated through extensive numerical simulations and applications to the real-world dataset.

Yali Wang, Zhaojun Wang

Algorithmic Stability

Jun 22, 2026cs.LG

GRAIN: Group Aggregation via Min-Norm Objective

Learning instability is a long-standing problem across machine learning, but it is especially acute in the overparameterized regime that defines modern deep learning: large models fine-tuned or trained on limited data traverse flat loss landscapes with many nearly-equivalent minima, and stochastic factors (initialization, data order, dropout, hardware non-determinism) can route optimization to very different solutions. The rise of large pretrained models (LPMs) makes the problem more urgent: training cost is high, downstream data is often small, and repeated runs for variance reduction are prohibitive. We introduce \textbf{GRAIN} (\textbf{G}roup \textbf{A}ggregation via m\textbf{IN}-norm objective), a lightweight training algorithm that replaces the mean aggregation used in mini-batch optimization (both across mini-batches and within a mini-batch) with a min-norm convex combination of group-wise gradients. \mName guarantees a non-negative inner product between the aggregated update and every group gradient, resolving intra- and inner-batch gradient conflict, and retains an

\mathcal{O}(1/T)

convergence rate comparable to SGD. Under mild smoothness and absolute-continuity assumptions, the min-norm solution differs almost surely from the arithmetic mean, which yields a uniform-stability bound for \mName strictly tighter than the standard bound for SGD. Empirically across generation, classification, and regression at LPM scale, \mName delivers consistent improvements in mean performance and reductions in run-to-run variance over a broad suite of tasks, with no extra training-time or storage cost beyond a single backward pass.

Nghia Bui, Jiarui Yao, Lijing Wang

Department of Data Science New Jersey Institute of Technology · Boston Children’s Hospital Harvard Medical School

Algorithmic Stability Neural Network Training Dynamics Stochastic Gradient Descent

Jun 9, 2026cs.LG

Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity

Mirror Descent (MD) extends Gradient Descent (GD) beyond Euclidean geometry and has recently reappeared as a lens for KL-regularized policy optimization in reinforcement learning and LLM post-training. This raises a basic robustness question, crucial to reproducibility and reliability: how sensitive are MD dynamics to their inputs? We focus on initialization, often itself a pretrained or previously aligned model. Quadratic-regularized MD, including GD and Mahalanobis geometries, is well-known to be stable for convex smooth objectives. We show a sharp contrast: once the regularizer is non-quadratic, MD can be exponentially more sensitive to initialization than GD, even with a well-conditioned regularizer in Euclidean norm. We give a three-dimensional construction with a convex, smooth objective and a strongly convex, smooth, well-conditioned regularizer where an initial

\varepsilon

perturbation is quickly amplified to

\min\{\text{polylog}^{-1}(1/\varepsilon), \varepsilon e^{Ω(ηT)}\}

after

T

iterations of MD with step size

η

. For canonical KL-regularized MD on the simplex, we show that even linear objectives can amplify an initial

\varepsilon

perturbation exponentially fast in high-dimensional or near-boundary regimes. Finally, we show that adding a Bregman regularization term toward an anchor point can stabilize the dynamics while largely preserving the optimization guarantees, and that the choice of anchor is crucial: anchoring at the initialization only partially mitigates the instability, whereas anchoring at a fixed point yields a more stable mechanism.

Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg +1

Blavatnik School of Computer Science and AI, Tel Aviv University · Google Research

Algorithmic Stability Mirror Descent Gradient Descent Dynamics

Jun 7, 2026stat.ML

Generalization in Nonlinear Least Squares via Learned Feature Geometry

We study the generalization of ridge-regularized nonlinear least-squares models via on-average algorithmic stability, deriving error bounds for local minimizers in terms of a data-dependent effective dimension that reflects the geometry of the gradient model at the trained parameters, through the empirical Jacobian Gram matrix and a residual-curvature term. In the linear case, where the curvature term vanishes, this recovers the classical effective dimension of the Jacobian kernel covariance, but evaluated at the trained model rather than at initialization as is typical in neural tangent kernel analyses. We further bound this effective dimension via covering complexity of the gradient features, leading to guarantees that depend on learned geometry rather than parameter count. In particular, for manifold-supported data and piecewise Lipschitz Jacobians, the bounds scale with intrinsic dimension, while for one-hidden-layer ReLU networks, the mechanism can be made explicit through counts of activation-stable regions. Experiments on synthetic manifolds, clustered distributions, and benchmark datasets illustrate trained-Jacobian compression, the tightness of the residual-curvature linearization, and agreement between the stability bound and observed generalization gaps. A key feature of our bounds is the simplicity of their derivation, which follows from first principles using the Brascamp-Lieb inequality under strongly log-concave noise.

Ayub Kharel, Ilja Kuzborskij, Patrick Rebeschini +1

University of Oxford · Google DeepMind · Sapient Intelligence

Neural Representation Geometry Algorithmic Stability Generalization Bounds

Jun 6, 2026math.NA

Stable and Scalable Probabilistic Numerical Solvers for Stiff and High-Dimensional ODEs

Filtering-based probabilistic numerical solvers for ordinary differential equations (ODEs) have been established as a flexible and efficient simulation framework with built-in numerical uncertainty quantification. However, problems that are both stiff and high-dimensional remain a challenge, as current methods are either stable and have cubic cost in the ODE dimension, or scale linearly at the expense of stability. In this paper, we close this gap and develop probabilistic ODE solvers that are both stable and scalable. We propose two complementary strategies. First, we develop a matrix-free update step that uses Jacobian-vector products, iterative linear solvers, and stochastic covariance estimation to enable linear scaling, all while retaining stability. Second, we propose iterative re-linearization to further improve stability without sacrificing scalability, turning probabilistic ODE solvers into fully implicit methods. We evaluate the proposed approaches on a range of stiff and high-dimensional problems and demonstrate improved stability and scalability over established probabilistic solvers.

Nathanael Bosch

EPFL, Lausanne, Switzerland

Dynamical Systems Uncertainty Quantification Algorithmic Stability

Jun 5, 2026cs.LG

Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters

We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic or stochastic rounding. We show that deterministic rounding degrades the generalization error of GD on convex, Lipschitz, and smooth loss functions, increasing the rate from

O(T/n)

to

O(T/\sqrt{n})

, and establish matching lower bounds. We further prove that uniform stability of GD becomes

Ω(T)

, showing that stability-based generalization bounds are vacuous in this setting. In contrast, for the same losses, stochastic gradient descent with deterministic rounding admits nontrivial uniform stability guarantees, which differ qualitatively from the real-valued case and exhibit distinct dependencies on the number of iterations and the dimension: we prove tight bounds

O(T/n)

for one dimension and

O(T^2/n)

for higher dimensions. We also show that stochastic rounding can introduce generalization error that increases with the dimension; such a phenomenon is absent in standard real-valued optimization and in the deterministic rounding case. Finally, we provide upper bounds on uniform argument stability for stochastic rounding schemes and show that these bounds are tight when the loss can be represented as a sum of coordinate-wise functions.

Jonghyun Shin, Sejun Park

Department of Artificial Intelligence Korea University Seoul, Korea

Algorithmic Stability Gradient Descent Stochastic Gradient Descent Generalization Bounds

Jun 5, 2026stat.ML

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments

While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite

L_p

moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under

L_p

constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that

L_p

stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.

Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1

Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.

Algorithmic Stability Generalization Bounds

Jun 1, 2026cs.LG

FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo

Shampoo is attracting considerable attention for its superior performance on large-scale optimization benchmarks; yet it faces a significant practical bottleneck: the prohibitive computational overhead of matrix inversion. To mitigate this, practitioners typically rely on stale preconditioner updates, creating a fundamental trade-off between computational efficiency and optimization fidelity. In this work, we provide a theoretical study of staleness through the complementary lenses of convergence and stability. While staleness improves computational efficiency, it inherently degrades performance and introduces numerical instability. Crucially, we identify that damping, acting as a numerical stabilizer, can effectively suppress these negative effects. Guided by this analysis, we propose FOAM, an adaptive algorithm that stabilizes training by dynamically controlling both the damping factor and the eigendecomposition frequency based on an approximation of the staleness-oriented error. Experimental results demonstrate that FOAM reduces wall-clock time compared to standard Shampoo while maintaining robust convergence.

Kyunghun Nam, Sumyeong Ahn

KENTECH, Naju, Republic of Korea.

Deep Learning Optimization Optimization Convergence Analysis Algorithmic Stability Second-Order Optimization

Jun 1, 2026cs.LG

A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling

We study finite-sample generalization for a client-sampled distributed optimization scheme with matrix-valued parameters and orthogonalized momentum updates. The central quantity is the gap between the population and empirical objectives at the returned model when only a subset of clients participates in each round. Under independent heterogeneous client data, unequal local sample counts, and fixed aggregation weights, we derive a finite-round upper-tail guarantee from a coupled-neighbor stability recursion and a weighted concentration step. The bound keeps the client-selection counts through the amplification factor

Y_i(\mathcal C)

; in the uniform full-participation full-batch regime, it yields

\widetilde{\mathcal O}(n^{-1}+n^{-1/2})

scaling whenever the horizon-dependent amplification terms are controlled. The matrix-orthogonalization rule is required to be Lipschitz along paired trajectories, a condition satisfied by regularized polar-type maps and normalized finite-step Newton--Schulz orthogonalizers. For the unregularized matrix sign, the same argument requires coupled spectral separation, whereas Gaussian smoothing gives a finite-round smoothed variant. A one-dimensional counterexample shows why a gap, smoothing, or regularity condition is necessary.

Da Chang, Qiankun Shi, Lvgang Zhang +2

University of Chinese Academy of Sciences · Sun Yat-sen University · Southern University of Science and Technology +1

Algorithmic Stability Distributed Optimization Federated Learning Generalization Bounds

May 27, 2026math.OC

Implicit Regularization in Perturbed Deep Matrix Factorization: Spectral Conditions and Stability

This paper studies the stability of low-rank implicit regularization in perturbed deep matrix factorization, where the target matrix is corrupted by a noise matrix. We first derive sufficient spectral conditions under which gradient descent exhibits a low-rank phase in the noiseless setting. These conditions show how the target spectrum, initialization, and step size jointly determine the existence of a nonempty low-rank interval. We then analyze the perturbed gradient descent dynamics, proving convergence guarantees and quantifying how the perturbation affects iteration complexity and eigenvalue recovery. Finally, we show that the low-rank phase persists under perturbation, with explicit dependence on the perturbation size. Numerical experiments support the theoretical findings.

Jingzhe Wang, Hung-Hsu Chou

Department of Informatics and Networked Systems, University of Pittsburgh · Department of Mathematics, University of Pittsburgh

Algorithmic Stability Low-Rank Matrix Decomposition Low-Rank Approximation Matrix Optimization Implicit Regularization Matrix Factorization+1

May 27, 2026cs.LG

Stochastic Gradient Descent with Momentum is Algorithmically Stable

Stochastic gradient descent with momentum (SGDM) is one of the most widely used optimization algorithms in machine learning. While optimization properties of SGDM have been extensively studied in the literature, it remains insufficiently understood whether and when SGDM can generalize well to unseen data. In particular, it has been conjectured that while momentum accelerates training, it may degrade generalization. In this paper, we close this gap by developing a comprehensive generalization analysis of SGDM through the lens of algorithmic stability. More specifically, we introduce a generalized SGDM framework that encompasses both Polyak's and Nesterov's momentum schemes, and establish tight on-average model stability bounds for smooth and convex problems. Notably, the obtained bounds exploit small optimization error bounds along the trajectory, apply to any momentum parameter in the interval

[0, 1)

, and do not require the commonly assumed Lipschitzness of loss functions. We further derive optimization error bounds for the generalized SGDM, and combine them with our generalization analyses to obtain optimal excess population risk bounds for SGDM with both Polyak's and Nesterov's momentum.

Yunwen Lei, Zimeng Wang, Xiaoming Yuan

Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Umeå University, Sweden

Momentum Methods Algorithmic Stability Stochastic Optimization Convergence Accelerated Gradient Methods Stochastic Gradient Descent Generalization Bounds

May 19, 2026cs.LG

Smooth Partial Lotteries for Stable Randomized Selection

Competitive selection processes, from scientific funding to admissions and hiring, use evaluations to score candidates, and eventually choose a subset of them based on those scores. Recently, many organizations have adopted partial lotteries, which randomize selection based on evaluation scores. However, existing lottery designs are inherently unstable, as a small change to a single candidate's score can cause large shifts in their selection probabilities. This instability undermines a key goal of lotteries: reducing the influence of fine-grained score distinctions near the decision boundary. We propose smoothness as a design principle for partial lotteries, formalizing it as a Lipschitz condition on the mapping from review scores over candidates to selection probabilities. We introduce the Clipped Linear Lottery, a simple mechanism in which selection probabilities scale linearly with estimated quality between an upper threshold, above which we always accept, and a lower threshold, below which we always reject. We prove that the Clipped Linear Lottery's worst-case regret matches a lower bound for any smooth selection rule up to a factor of

(1 - k/n)

, where

k/n

is the acceptance rate. We compare smooth selection to other stability notions like Individual Fairness and Differential Privacy, showing that the Clipped Linear Lottery achieves a better smoothness-regret tradeoff than alternatives. Experiments on real peer review data from ICLR 2025, NeurIPS 2024, and the Swiss National Science Foundation demonstrate that existing lottery designs are highly unstable in practice even under perturbations to a single score. Our experiments also confirm the tightness of our theoretical analysis and show that our proposed Clipped Linear Lottery achieves a better smoothness-utility tradeoff than alternatives in practice.

Alexander Goldberg, Giulia Fanti, Nihar B. Shah

Carnegie Mellon University

Algorithmic Stability Algorithmic Fairness

May 11, 2026cs.LG

Unveiling High-Probability Generalization in Decentralized SGD

Decentralized stochastic gradient descent (D-SGD) is an efficient method for large-scale distributed learning. Existing generalization studies mainly address expected results, achieving rates limited to

\mathcal{O}\left(\frac{1}{δ\sqrt{mn}}\right)

, where

δ

is the confidence parameter,

m

the number of workers, and

n

the sample size. When

m=1

, D-SGD reduces to traditional SGD, whose optimal high-probability generalization bound is

\mathcal{O}\left(\frac{1}{\sqrt{n}}\log (1/δ)\right)

. This discrepancy reveals a gap between high-probability guarantees for SGD and those for D-SGD. To close this, we develop a high-probability learning theory for D-SGD, aiming for the optimal

\mathcal{O}\left(\frac{1}{\sqrt{mn}}\log (1/δ)\right)

rate. We refine bounds for D-SGD using pointwise uniform stability in distributed learning-a weaker notion than uniform stability-and analyze them across convex, strongly convex, and non-convex settings. We also provide high-probability results for gradient-based measures in non-convex cases where only local minima exist, and derive optimization error and excess risk bounds. Finally, accounting for communication overhead, we analyze generalization bounds for local models within time-varying frameworks.

Jiahuan Wang, Ping Luo, Ziqing Wen +2

College of Computer Science and Technology National University of Defense Technology Changsha, Hunan 410073, China

Algorithmic Stability Decentralized Learning Decentralized Optimization Generalization Bounds

May 8, 2026math.OC

A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizers

We develop a unified Lyapunov-integral quadratic constraint (IQC) framework for establishing uniform stability of first-order accelerated optimization algorithms in the

β

-smooth and

γ

-strongly convex regime. Classical analyses of uniform stability, such as the work of Hardt, Recht, and Singer for stochastic gradient descent (SGD), rely on direct coupling arguments and case-by-case control of iterate differences under random sampling. Extending such arguments to accelerated methods, such as Nesterov Accelerated Gradient (NAG), is complicated by the presence of higher-order state dynamics induced by momentum. We first extend this classical approach with the use of Lyapunov functions to provide a uniform stability bound for smooth quadratic NAG, and supplement this result with small-scale numerical experiments. We then extend this framework by modeling first-order accelerated optimizers as Lur'e-type feedback interconnections between a linear dynamical system and a (non-linear) gradient operator.

β

-Smoothness and

γ

-strong convexity are encoded a sector IQC inequality. Under this representation, uniform stability is certified via the existence of a quadratic Lyapunov function satisfying a finite-dimensional linear matrix inequality (LMI) in the form of a feasibility problem, which can be solved via semi-definite programming (SDP). We instantiate this framework for NAG and show how classical uniform stability bounds can be recovered via this framework. These results underscore a structural connection between optimization dynamics and robust control theory, providing a modular methodology for reliable and reproducible numerical certification of uniform stability and generalization behavior of first-order methods via convex optimization tools that is adaptable to increasingly complex optimization algorithms.

Don Li, Dacian Daescu

Department of Mathematics & Statistics, Portland State University, Portland, OR 97201, USA

Lyapunov Stability Algorithmic Stability Gradient Descent Accelerated Gradient Methods

May 8, 2026cs.LG

A Flexible Adaptive Stable Clustering Algorithm for Archive-Scale Online Mass Spectrometry

Modern online mass spectrometry generates multi-terabyte data streams critical for understanding Earth's environmental systems. However, extracting actionable chemical insights from these repositories is impeded by a computational bottleneck: existing clustering methods force a compromise among scalability, metric flexibility, and algorithmic stability. Here, we introduce Flexible Adaptive Stable Clustering (FASC), a dynamical systems framework that resolves these constraints by architecturally decoupling the similarity kernel from rigorous optimization logic. Unlike legacy heuristics that suffer from stochastic drift and algorithmic blending, FASC employs a Density-Augmented Similarity Selection rule and geometric constraints to guarantee deterministic, order-independent convergence. After validating FASC on canonical machine-learning ground truths (achieving >99.5% cluster purity and 0.99 Adjusted Rand Index), we deployed the framework on 25 million mass spectra of atmospheric aerosols. Demonstrating strictly linear empirical runtime scaling (O(N)), FASC autonomously mapped atmospheric aging pathways of secondary inorganic aerosols while isolating ultra-rare industrial tracers (<0.2% abundance), providing a scalable infrastructure for mining environmental big data.

Shao Shi, Xin Yang, Huiran Feng +8

Shenzhen Key Laboratory of Precision Measurement and Early Warning Technology for Urban Environmental Health Risks, School of Environmental Science and Engineering, Southern University of Science and Technology, 1088 Xueyuan Avenue, Shenzhen, 518055, Guangdong, China. · Guangdong Provincial Observation and Research Station for Coastal Atmosphere and Climate of the Greater Bay Area, Southern University of Science and Technology, 1088 Xueyuan Avenue, Shenzhen, 518055, Guangdong, China.

Algorithmic Stability Clustering Unsupervised Clustering Mass Spectrometry

May 3, 2026cs.LG

Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability

We study differential privacy (DP) in Graph Convolutional Networks (GCNs) through the framework of \textit{subsampling stability}. We derive upper bounds on the misclassification rate that depend explicitly on the subsampling probability

p_s

. Furthermore, we characterize the \textit{privacy--utility trade-off} by identifying feasible ranges of

p_s

; if

p_s

is too large, the stability-based privacy condition becomes difficult to satisfy, yielding vacuous guarantees, whereas if it is too small, accuracy deteriorates. Our results provide the first rigorous theoretical framework for understanding subsampling stability in GCNs under DP.

Yexin Zhang, Zhongtian Ma, Qiaosheng Zhang +1

School of Cybersecurity, Northwestern Polytechnical University, Xi’an, China · Shanghai Artificial Intelligence Laboratory, Shanghai, China · Shanghai Innovation Institute, Shanghai, China

Algorithmic Stability Privacy-Preserving ML Differential Privacy Convolutional Neural Networks Privacy-Utility Tradeoff

May 3, 2026cs.LG

Stability and Generalization for Decentralized Markov SGD

Stochastic gradient methods are central to large-scale learning, yet their generalization theory typically relies on independent sampling assumptions. In many practical applications, data are generated by Markov chains and learning is performed in a decentralized manner, which introduces significant analytical challenges. In this work, we investigate the stability and generalization of decentralized stochastic gradient descent (SGD) and stochastic gradient descent ascent (SGDA) under Markov chain sampling. Leveraging a stability-based framework, we characterize how Markovian dependence and decentralized communication jointly influence generalization behavior. Our analysis captures the effects of network topology, Markov chain mixing properties, and primal-dual dynamics. We establish non-asymptotic generalization bounds for both algorithms, extending existing results on Markov stochastic gradient methods to decentralized and minimax settings.

Jiahuan Wang, Ziqing Wen, Ping Luo +2

National Key Laboratory of Parallel and Distributed Computing, National University of Defense Technology, Changsha, 410073, China

Algorithmic Stability Decentralized Optimization Stochastic Gradient Descent Generalization Bounds

Apr 20, 2026stat.ME

Improving reproducibility by controlling random seed stability in machine learning based estimation via bagging

Predictions from machine learning algorithms can vary across random seeds, inducing instability in downstream debiased machine learning estimators. We formalize random seed stability via a concentration condition and prove that subbagging guarantees stability for any bounded-outcome regression algorithm. We introduce a new cross-fitting procedure, adaptive cross-bagging, which simultaneously eliminates seed dependence from both nuisance estimation and sample splitting in debiased machine learning. Numerical experiments confirm that the method achieves the targeted level of stability whereas alternatives do not. Our method incurs a small computational penalty relative to standard practice whereas alternative methods incur large penalties.

Nicholas Williams, Alejandro Schuler

Division of Biostatistics, University of California, Berkeley, California, U.S.A.

Debiased ML Ensemble Learning Algorithmic Stability ML Reproducibility