Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms

Sijia Zhou; Yunwen Lei; Ata Kaban

Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms

Sijia Zhou, Yunwen Lei^*, Ata Kaban

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Downloads (Pure)

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	https://neurips.cc/

Bibliographical note

Acknowledgements. The authors are grateful to the anonymous reviewers
for 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.

Access to Document

ZhouLeiKaban-Neurips23Accepted author manuscript, 414 KBLicence: Creative Commons: Attribution (CC BY)

FORGING: Fortuitous Geometries and Compressive Learning
Kaban, A.
Engineering & Physical Science Research Council
9/01/17 → 8/01/23
Project: Research Councils

Cite this

@inproceedings{dec463d1189f4fbbaeef5adecb1d0395,

title = "Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms",

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.",

author = "Sijia Zhou and Yunwen Lei and Ata Kaban",

note = "Acknowledgements. The authors are grateful to the anonymous reviewers for 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.; Thirty-seventh Conference on Neural Information Processing Systems, NeurIPS 2023 ; Conference date: 10-12-2023 Through 16-12-2023",

year = "2023",

month = nov,

day = "2",

language = "English",

series = "Advances in Neural Information Processing Systems",

booktitle = "Advances in Neural Information Processing Systems",

url = "https://neurips.cc/",

}

TY - GEN

T1 - Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms

AU - Zhou, Sijia

AU - Lei, Yunwen

AU - Kaban, Ata

N1 - Acknowledgements. The authors are grateful to the anonymous reviewers for 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.

PY - 2023/11/2

Y1 - 2023/11/2

N2 - 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.

AB - 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.

UR - https://openreview.net/forum?id=F6j16Qr6Vk

UR - https://proceedings.neurips.cc/

M3 - Conference contribution

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems

T2 - Thirty-seventh Conference on Neural Information Processing Systems

Y2 - 10 December 2023 through 16 December 2023

ER -

Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Fingerprint

Projects

FORGING: Fortuitous Geometries and Compressive Learning

Cite this