Projects per year
Abstract
We give sharper bounds for uniformly stable randomized algorithms in a PAC-Bayesian framework, which improve the existing results by up to a factor of $\sqrt{n}$ (ignoring a log factor), where is the sample size. The key idea is to bound the moment generating function of the generalization gap using concentration of weakly dependent random variables due to Bousquet et al (2020). We introduce an assumption of sub-exponential stability parameter, which allows a general treatment that we instantiate in two applications: stochastic gradient descent and randomized coordinate descent. Our results eliminate the requirement of strong convexity from previous results, and hold for non-smooth convex problems.
Original language | English |
---|---|
Title of host publication | Advances in Neural Information Processing Systems |
Subtitle of host publication | NeurIPS 2023 |
Number of pages | 23 |
Publication status | E-pub ahead of print - 2 Nov 2023 |
Event | Thirty-seventh Conference on Neural Information Processing Systems - Ernest N. Morial Convention Centre, New Orleans, United States Duration: 10 Dec 2023 → 16 Dec 2023 https://neurips.cc/ |
Publication series
Name | Advances in Neural Information Processing Systems |
---|---|
ISSN (Electronic) | 1049-5258 |
Conference
Conference | Thirty-seventh Conference on Neural Information Processing Systems |
---|---|
Abbreviated title | NeurIPS 2023 |
Country/Territory | United States |
City | New Orleans |
Period | 10/12/23 → 16/12/23 |
Internet address |
Bibliographical note
Acknowledgements. The authors are grateful to the anonymous reviewersfor their thoughtful comments and constructive suggestions. The work of Yunwen Lei is partially supported by the Research Grants Council of Hong Kong [Project No. 22303723]. The work of Sijia Zhou is funded by CSC and UoB scholarship. AK acknowledges funding by EPSRC Fellowship grant EP/P004245/1.
Fingerprint
Dive into the research topics of 'Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms'. Together they form a unique fingerprint.Projects
- 1 Finished
-
FORGING: Fortuitous Geometries and Compressive Learning
Kaban, A. (Principal Investigator)
Engineering & Physical Science Research Council
9/01/17 → 8/01/23
Project: Research Councils