Algorithmic Stability

Follow this topic Ask about this topic

Algorithmic stability studies how much a learned model or prediction changes when training examples, initialization, or computation are perturbed, and how that sensitivity affects generalization and reproducibility. Common tools include uniform, on-average, and pointwise stability, analyzed through coupled runs on neighboring datasets and combined with concentration inequalities to bound generalization gaps. These methods are applied to stochastic gradient descent and its variants, neural networks, decentralized and bilevel optimization, and ensemble or subsampling procedures, with newer work addressing heavy-tailed data, data reuse, and finite-precision updates. A central tension is that stronger stability can improve generalization or reliability but may constrain accuracy, convergence, or regret, while available guarantees can depend sharply on assumptions and may not capture every form of real-world robustness.

Latest papers

46 papers4 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

Fine-Grained Analysis of Catastrophic Forgetting in Continual Learning via Algorithmic Stability
Oct 22, 2026Guodong Zheng, Yan Sun, Peng Wang +5Catastrophic Forgetting Generalization Bounds
School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University, Shenzhen, China. · College of Computing and Data Science and the Generative AI Lab at Nanyang Technological University, Singapore. · Tencent Hunyuan, Shenzhen, China.
Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems
Oct 14, 2026Shuang Zeng, Yunwen Lei, Yiming YingMin-Max Optimization Generalization Bounds
Department of Mathematics, The University of Hong Kong, Hong Kong, China · School of Mathematics and Statistics, The University of Sydney, Sydney, Australia
Certification-Enhanced Generalization Bounds
Oct 5, 2026Leo Elmecker-Plakolm, Matthew WickerAlgorithmic Stability Generalization Bounds
Department of Computing Imperial College London London, SW7 2AZ, UK
Preferent Compression Bounds Are Tight
Sep 28, 2026Dario Paccagnan, Marius TirleaSample Compression Statistical Learning Theory
Department of Computing, Imperial College London, London, UK
Stable Policy Learning
Sep 16, 2026Harvey Barnhard, Giacomo Opocher, Rahul SinghAlgorithmic Stability Policy Learning
Harvard University · University of Mannheim
Stable Filters for Generative Modeling of Graph Signals
Sep 16, 2026Martin Schmidt, Gonzalo MateosGraph Signal Processing Algorithmic Stability
University of Rochester, Rochester, NY, USA
Algorithmic stability via ensembling
Sep 9, 2026Rina Foygel Barber, Richard J. SamworthEnsemble Learning Algorithmic Stability
University of Chicago · University of Cambridge
Stability and Generalization of Straight-Through Estimators for Training Two-Layer Quantized Neural Networks
Sep 6, 2026Yiming YingStraight-Through Estimator Neural Network Generalization
School of Mathematics and Statistics University of Sydney
The Sharp Tail of Uniform Stability
Aug 25, 2026Pahan DewasurendraAlgorithmic Stability Generalization Bounds
Johns Hopkins University
Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
Aug 10, 2026Thanh Nguyen-Cung, Binh T. NguyenAlgorithmic Stability Statistical Learning Theory
VinUniversity
Stability of Ranking-dependent Pair-wise Comparison Patterns in the Analytic Hierarchy Process
Aug 6, 2026Vitaliy Tsyganok, Sergii Kadenko, Oleh AndriichukPairwise Comparison Pairwise Preference Evaluation
Institute for Information Recording National Academy of Sciences of Ukraine Kyiv, Ukraine 03113
Feature Bagging Provides Stability
Jul 29, 2026Yuheng Ma, Qiang SunEnsemble Learning Algorithmic Stability
School of Statistics, East China Normal University · University of Toronto · MBZUAI
Learning Dynamics of Strategic Publishers in Generative AI Ecosystems
Jul 28, 2026Sagie Dekel, Omer Madmon, Moshe Tennenholtz +1Generative Engine Optimization Algorithmic Stability
Technion - Israel Institute of Technology
Stabilizing Deep Reconstruction Operators with Contractive Anchoring
Jul 25, 2026Arghya Sinha, Trishit Mukherjee, Kunal N. ChaudhuryAlgorithmic Stability Image Reconstruction
Indian Institute of Science, Bengalore, India
Mechanism and Stability Analysis of Metabolic Closed-Loop Metaheuristics
Jul 2, 2026Jinliang Xu, Liping MaMulti-Agent System Optimization Algorithmic Stability
independent researcher in Beijing, China
Dangerous Liaisons of Convex Learning and Non-Affine Aggregation
Jun 26, 2026Thomas Boudou, Batiste Le Bars, Nirupam Gupta +1Optimization Convergence Analysis Algorithmic Stability
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
Stabilizing black-box algorithms through task-oriented randomization
Jun 24, 2026Yali Wang, Zhaojun WangAlgorithmic Stability
GRAIN: Group Aggregation via Min-Norm Objective
Jun 22, 2026Nghia Bui, Jiarui Yao, Lijing WangAlgorithmic Stability Neural Network Training Dynamics
Department of Data Science New Jersey Institute of Technology · Boston Children’s Hospital Harvard Medical School
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
Jun 9, 2026Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg +1Algorithmic Stability Mirror Descent
Blavatnik School of Computer Science and AI, Tel Aviv University · Google Research
Generalization in Nonlinear Least Squares via Learned Feature Geometry
Jun 7, 2026Ayub Kharel, Ilja Kuzborskij, Patrick Rebeschini +1Neural Representation Geometry Algorithmic Stability
University of Oxford · Google DeepMind · Sapient Intelligence
Stable and Scalable Probabilistic Numerical Solvers for Stiff and High-Dimensional ODEs
Jun 6, 2026Nathanael BoschDynamical Systems Uncertainty Quantification
EPFL, Lausanne, Switzerland
Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters
Jun 5, 2026Jonghyun Shin, Sejun ParkAlgorithmic Stability Gradient Descent
Department of Artificial Intelligence Korea University Seoul, Korea
Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
Jun 5, 2026Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1Algorithmic Stability Generalization Bounds
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.
FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo
Jun 1, 2026Kyunghun Nam, Sumyeong AhnDeep Learning Optimization Optimization Convergence Analysis
KENTECH, Naju, Republic of Korea.
A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling
Jun 1, 2026Da Chang, Qiankun Shi, Lvgang Zhang +2Algorithmic Stability Distributed Optimization
University of Chinese Academy of Sciences · Sun Yat-sen University · Southern University of Science and Technology +1
Implicit Regularization in Perturbed Deep Matrix Factorization: Spectral Conditions and Stability
May 27, 2026Jingzhe Wang, Hung-Hsu ChouAlgorithmic Stability Low-Rank Matrix Decomposition
Department of Informatics and Networked Systems, University of Pittsburgh · Department of Mathematics, University of Pittsburgh
Stochastic Gradient Descent with Momentum is Algorithmically Stable
May 27, 2026Yunwen Lei, Zimeng Wang, Xiaoming YuanGeneralization Bounds Algorithmic Stability
Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Umeå University, Sweden
Smooth Partial Lotteries for Stable Randomized Selection
May 19, 2026Alexander Goldberg, Giulia Fanti, Nihar B. ShahAlgorithmic Stability Algorithmic Fairness
Carnegie Mellon University
Unveiling High-Probability Generalization in Decentralized SGD
May 11, 2026Jiahuan Wang, Ping Luo, Ziqing Wen +2Algorithmic Stability Decentralized Learning
College of Computer Science and Technology National University of Defense Technology Changsha, Hunan 410073, China
A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizers
May 8, 2026Don Li, Dacian DaescuLyapunov Stability Algorithmic Stability
Department of Mathematics & Statistics, Portland State University, Portland, OR 97201, USA

Oct 22, 2026J/K move · Enter open · S save

Fine-Grained Analysis of Catastrophic Forgetting in Continual Learning via Algorithmic Stability

Guodong Zheng, Yan Sun, Peng Wang, Enneng Yang+4

School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University, Shenzhen, China. · College of Computing and Data Science and the Generative AI Lab at Nanyang Technological University, Singapore. · Tencent Hunyuan, Shenzhen, China.

Catastrophic Forgetting Generalization Bounds Algorithmic Stability

Open paper AskPDF arXiv

Understanding catastrophic forgetting, in which learning new tasks degrades performance on previously learned tasks, remains a fundamental challenge in continual learning (CL). Existing theoretical analyses often rely on specific model or task structures and offer limited insight into how iterative optimization affects forgetting. To address this gap, we develop an algorithmic stability framework for expected population forgetting under SGD without prescribing a particular model architecture. Specifically, we decompose forgetting into intra-task and cross-task generalization gaps and empirical forgetting. To bound the generalization gaps, we track how a sample perturbation affects updates within a task and propagates through subsequent tasks. We consider constant, intra-task decaying, and continuously decaying learning-rate schedules. Comparing the two decaying schedules allows us to characterize how restarting learning-rate decay at task boundaries affects the propagation of historical sample perturbations. For empirical forgetting, we derive bounds for all three schedules by retaining cumulative gradient alignment along the optimization trajectory, without requiring convexity. Combining these results yields upper bounds on expected forgetting that capture the effects of training set size, the number of updates per task, the total number of tasks, learning-rate schedules, and cumulative gradient alignment. Finally, we conduct experiments on Split CIFAR-100 and Split MiniImageNet to examine the empirical implications of our theoretical findings.