Your estimate is robust to a deleted data point? it is a stable estimate. This implies generalisability, apparently. The above statements can be made precise, I am told. Making them precise might give us new ideas for risk bounds, model selection, or connections to optimization.
Supposedly there is also connection to differential privacy, but since I don’t yet know anything about differential privacy I can’t take that statement any further except to note I would like to work it out one day. This is also presumably a connection to robust inference, since the setup sounds very similar.
Reproducibility is imperative for any scientific discovery. More often than not, modern scientific findings rely on statistical analysis of high-dimensional data. At a minimum, reproducibility manifests itself in stability of statistical results relative to “reasonable” perturbations to data and to the model used. Jacknife, bootstrap, and cross-validation are based on perturbations to data, while robust statistics methods deal with perturbations to models.
Moritz Hardt, Stability as a foundation of machine learning:
Central to machine learning is our ability to relate how a learning algorithm fares on a sample to its performance on unseen instances. This is called generalization.
In this post, I will describe a purely algorithmic approach to generalization. The property that makes this possible is stability. An algorithm is stable, intuitively speaking, if its output doesn’t change much if we perturb the input sample in a single point. We will see that this property by itself is necessary and sufficient for generalization.
- BoEl01: Olivier Bousquet, André Elisseeff (2001) Algorithmic Stability and Generalization Performance. In Advances in Neural Information Processing Systems (Vol. 13, pp. 196–202). MIT Press
- BNSS15: Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman (2015) Algorithmic Stability for Adaptive Data Analysis. ArXiv:1511.02513 [Cs].
- KuNi02: Samuel Kutin, Partha Niyogi (2002) Almost-everywhere Algorithmic Stability and Generalization Error. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (pp. 275–282). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
- AgNi09: Shivani Agarwal, Partha Niyogi (2009) Generalization Bounds for Ranking Algorithms via Algorithmic Stability. In Journal of Machine Learning Research (Vol. 10, pp. 441–474).
- MWCW16: Qi Meng, Yue Wang, Wei Chen, Taifeng Wang, Zhi-Ming Ma, Tie-Yan Liu (2016) Generalization Error Bounds for Optimization Algorithms via Stability. In arXiv:1609.08397 [stat] (Vol. 10, pp. 441–474).
- GiSB14: Raja Giryes, Guillermo Sapiro, Alex M. Bronstein (2014) On the Stability of Deep Networks. ArXiv:1412.5896 [Cs, Math, Stat].
- XuCM12: H. Xu, C. Caramanis, S. Mannor (2012) Sparse Algorithms Are Not Stable: A No-Free-Lunch Theorem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(1), 187–193. DOI
- Yu13: Bin Yu (2013) Stability. Bernoulli, 19(4), 1484–1500. DOI
- FrYL06: R.A. Freeman, Peng Yang, K.M. Lynch (2006) Stability and Convergence Properties of Dynamic Average Consensus Estimators. In 2006 45th IEEE Conference on Decision and Control (pp. 338–343). San Diego, CA, USA: IEEE DOI
- BoEl02: Olivier Bousquet, André Elisseeff (2002) Stability and generalization. Journal of Machine Learning Research, 2(Mar), 499–526.
- LiRW10: Han Liu, Kathryn Roeder, Larry Wasserman (2010) Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models. In Advances in Neural Information Processing Systems 23 (pp. 1432–1440). Curran Associates, Inc.
- MeBü10: Nicolai Meinshausen, Peter Bühlmann (2010) Stability selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 72(4), 417–473. DOI
- HaRS15: Moritz Hardt, Benjamin Recht, Yoram Singer (2015) Train faster, generalize better: Stability of stochastic gradient descent. ArXiv:1509.01240 [Cs, Math, Stat].
- ZBHR17: Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals (2017) Understanding deep learning requires rethinking generalization. In Proceedings of ICLR.