Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels
Machine learning models trained by different optimization algorithms under different data distributions can exhibit distinct generalization behaviors. In this paper, we analyze the generalization of models trained by noisy iterative algorithms. We derive distribution-dependent generalization bounds by connecting noisy iterative algorithms to additive noise channels found in communication and information theory. Our generalization bounds shed light on several applications, including differentially private stochastic gradient descent (DP-SGD), federated learning, and stochastic gradient Langevin dynamics (SGLD). We demonstrate our bounds through numerical experiments, showing that they can help understand recent empirical observations of the generalization phenomena of neural networks.
Code (0)
등록된 구현이 없습니다.
Tasks
Federated LearningGeneralization BoundsLearning TheoryMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Generalization Error Bounds for Noisy, Iterative Algorithms
In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. Recent work [Xu and Raginsky (2017)] has established a bo…
Learning TheoryGeneralization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage
We adopt an information-theoretic framework to analyze the generalization behavior of the class of iterative, noisy learning algorithms. This class is particularly suitable for study under information-theoretic metrics a…
Generalization BoundsDoeblin Curves
Recent research on Doeblin coefficients has shed light on their usefulness as a multi-way generalization of the Dobrushin contraction coefficient for TV distance, in a separate vein from their classic role in the theory …
Understanding the Generalization Error of Markov algorithms through Poissonization
Using continuous-time stochastic differential equation (SDE) proxies to stochastic optimization algorithms has proven fruitful for understanding their generalization abilities. A significant part of these approaches are …
Generalization BoundsStochastic OptimizationTightening Mutual Information Based Bounds on Generalization Error
An information-theoretic upper bound on the generalization error of supervised learning algorithms is derived. The bound is constructed in terms of the mutual information between each individual training sample and the o…