Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms
Authors: Sijia Zhou, Yunwen Lei, Ata Kaban
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give sharper bounds for uniformly stable randomized algorithms in a PACBayesian framework, which improve the existing results by up to a factor of n (ignoring a log factor), where n 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. |
| Researcher Affiliation | Academia | 1School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom 2 Department of Mathematics, The University of Hong Kong, Pokfulam, Hong Kong, China |
| Pseudocode | No | The paper does not contain any sections or figures explicitly labeled 'Pseudocode' or 'Algorithm'. |
| Open Source Code | No | The paper does not provide any statement or link regarding the release of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical experiments on specific, publicly available datasets. It refers to 'training examples' in a general theoretical context, but does not identify any specific dataset used for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with datasets. Therefore, it does not provide details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental setups. Therefore, it does not provide specific hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe experimental setups. Therefore, it does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experimental setups. While it discusses theoretical parameters for algorithms (e.g., step-size sequences), these are not details of an empirical experiment setup for reproducibility. |