# Bootstrap SGD: Algorithmic Stability and Robustness

arXiv: https://arxiv.org/abs/2409.01074 · HTML: https://mlsanity.com/paper/2409.01074/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 2 Sep 2024.

## Builds on (most cited first, 14 of 14)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel](https://mlsanity.com/paper/2107.12723/) (2021)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization](https://mlsanity.com/paper/2205.14278/) (2022)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [On the Robustness of Regularized Pairwise Learning Methods Based on Kernels](https://mlsanity.com/paper/1510.03267/) (2015)
- [On the Consistency of the Bootstrap Approach for Support Vector Machines and Related Kernel Based Methods](https://mlsanity.com/paper/1301.6944/) (2013)

## Abstract (arXiv)

In this paper some methods to use the empirical bootstrap approach for stochastic gradient descent (SGD) to minimize the empirical risk over a separable Hilbert space are investigated from the view point of algorithmic stability and statistical robustness. The first two types of approaches are based on averages and are investigated from a theoretical point of view. A generalization analysis for bootstrap SGD of Type 1 and Type 2 based on algorithmic stability is done. Another type of bootstrap SGD is proposed to demonstrate that it is possible to construct purely distribution-free pointwise confidence intervals of the median curve using bootstrap SGD.