Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors introduced a new discrete data-dependent prior to the PAC-Bayesian framework, and prove a high probability generalization based on Floored GD. The bound depends on the gradient difference $\|g_t\|$ between the full batch gradient and that of the prior samples. The empirical results showed that the presented bound could be non-vacuous. 


strengths_and_weaknesses: The FGD is used to derive the bound. While FGD has shown to have a similar learning curve as SGD (Figure 2 (a) vs. (b)), computing two gradients in a row with one of them to be a full batch gradient could be computationally expensive. While I understand the authors introduced FGD as an alternative to GD/SGD as a convenient way to analyze the bound, I do not think FGD/FSGD could become popular in practice and is not easy to understand intuitively.   

The empirical evaluation is fairly weak. The bound on Cifar-10 looks fairly loose even though part of it is non-vacuous. While there exist bounds that are non-vacuous on Cifar-10 and are empirically shown to be much tighter than the presented bound, it is essential to provide a fair comparison to such bound to show the usefulness of the presented new bound.

There are a couple of typos in the paper:
Ln 85-86 "Floored Gradient Descent (FSGD), a variant of SGD." --> Floored Stochastic Gradient Descent (FSGD)
Figure 2 Caption * MNIST+SimpleNet+FSGD/SGD --> Should be CIFAR-10 not MNIST

questions: The presented bound seems to decrease first and then increase again (figure 1(b) and Figure 2(c)), even after the test error stabilizes after certain training steps. This would lead to a very loose and eventually vacuous bound, which is not ideal and becomes useless in the later training steps.  I am wondering how does the cumulative gradient difference change over the training epoch? 

limitations: The experiments are very limited and do not have any comparison with the current available non-vacuous generalization bound.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the generalization property of gradient-based optimization algorithms using PAC-Bayesian bound. To this end, the authors first provide a bound using data-dependent prior (Theorem 4.1) and use it to prove generalization bounds for FGD, FSGD, GLD, and SGLD. The authors also empirically observed that some proposed bounds are not vacuous for the MNIST classification task.
strengths_and_weaknesses: I like the idea of the paper and its results, while there are some unclear parts. I will raise my score once the authors resolve/answer the following issues/questions.
- Is there any reference/application of FGD (or FSGD)? If not, is there any theoretical implication of these results for GD (or SGD)? 
- It seems that the proposed bounds can be vacuous due to the $\eta C_\eta$ multiplicative factor if the learning algorithms cannot achieve nearly zero training error. Is there optimal $\eta$ for the non-zero training error case which enables the bound non-vacuous?
- I am not sure if one can directly compare the GLD and SGLD bounds in the paper with those in [Negrea et al., 2019]. The authors applied Catoni's PAC-Bayesian bound to the result of [Negrea et al., 2019] and derived $O(\frac1{n-m}+\frac{(n-m)}{n^2}\sum_{t=1}^T\frac{\gamma_t^2}{\sigma_t^2}L^2)$. However, this bound and the bound in Theorem 6.2 may not be directly comparable since they bound different quantities; the first terms in RHS in Theorem 4.1 and Lemma 3.2 are different. I would like to see a more detailed discussion comparing the bounds in [Negrea et al., 2019] and this paper.
- Using the proposed GLD bound under mild assumptions including decaying step size (e.g., $\gamma_t\propto1/t$), Lipschitz continuity of $f$, etc., it seems that the generalization gap reduces to $O(1/(n-m))$, regardless of $T$. Using this reduction, can the excess risk bound also be derived?
questions: All questions are listed in the Strength and Weakness section.
limitations: The authors mentioned that the conclusion section (in Appendix) contains the limitation; however, I couldn't find related discussions.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper is concerned with proving new generalization bounds for gradient descent methods, by using suitable priors. To this end, the Catoni's PAC-Bayesian framework is used. But, unlike other work, this paper does not use restrictive assumptions on the learning rate or continuous injected noise. 
More precisely, the authors show a high-probability generalization bound for Floored gradient descent. 
In a similar way, the authors derive generalization bounds for (stochastic) gradient Langevin dynamics.
strengths_and_weaknesses: Strengths: Generalization bounds are an extremely central topic of ML. As far as I know, these bounds are novel. While floored gradient descent seems a bit artificial, the extension to stochastic gradient Langevin dynamics is very useful. The authors explain suitably how they choose the prior P. The literature review is nice and useful.

Weaknesses: 
--- The writing is unfortunately poor, many typos and formulations which are difficult to understand. Due to this, I found the paper lacking in quality and could not follow the flow of the arguments in many cases. 
--- The main result is on floored gradient descent, which is not a very relevant method. According to Algorithm 1, it seems to consist of computing the full gradient and a batch gradient. Why would one compute the batch gradient if one already afforded to compute the full gradient? This has to be much better justified... 
--- The concept of data-dependent prior needs more explanation. Is this a usual concept in the literature?
--- The experiment section is very short.
--- No plots or illustrations are given to provide intuition. It would, however, be important to give intuition for the data-dependent priors, etc.
--- The paper ends abruptly, without any conclusion or discussion of future work.
questions: 1. Floor Gradient descent seems a bit constructed. Why would one be interested in that? Why would one use a mini-batch gradient if one computes the full gradient anyway?
2. There are some references missing that also don't come with the restrictions of a step-size schedule or injected noise, e.g. https://proceedings.neurips.cc/paper/2020/hash/37693cfc748049e45d87b8c7d8b9aacd-Abstract.html
3. I would suggest to carefully clean up the text, there are quite a few language mistakes.

Overall, the clarity of the writing and presentation has to be improved. Like this, I cannot recommend the paper for NeurIPS.
limitations: The authors have adequately addressed the limitations. There are no potential negative societal impacts.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper utilizes data-dependent PAC-Bayesian bounds to derive generalization errors for a variety of gradient-based learning algorithms. The key idea is to construct a special prior based on a run of the algorithm from a randomly selected subset of the data. In the algorithms studied, these priors lead to tractble upper bounds on the PAC-Bayesian bounds, and thus bounds on the overall generalization error. In tests on MNIST, the bounds are quite tight, and they also give non-vacuous bounds on generalization error for CIFAR. 
strengths_and_weaknesses: Strengths
The methodology for deriving the bounds is quite interesting, and the bounds themselves give nice insights into the performance of various algorithms. The basic ideas seem quite extensible to a variety of different algorithms. The paper is well-written and well-organized.

Weaknesses
The paper does have some typos and basic mistakes. All of them appear to be fixable. 

Lemma 3.2 appears to be stated incorrectly. The bound on the right should probably include an empircal risk term, not a population risk term. However, this lemma is never actually used in the paper, from what I can tell. (The correctly stated Theorem 4.1 is used.) So, it could likely be removed. 

There are a few fixable mistakes at the end of the proof of Theorem 4.1. Specifically, the equality between lines 517 and 518 does not hold. A related inequality, based on convexity does hold, but that goes the wrong way. So, a different approach is needed.

Edit: Based on discussions, some better motivation for the algorithms is required.

Here is a way to fix it. Let $c=\frac{\lambda}{n-m}$ and recall that $w$ is fixed. Note that for random $z_i$, $\mathcal{R}(w,z_i)$ is a Bernoulli random variable which has expected value $\mathcal{R}(w,\mathcal{D})$. For simpler notation, set $b=\mathcal{R}(w,z_i)$ and $q=\mathcal{R}(w,\mathcal{D})$. Direct calculation shows that 
$$
E_b\left[e^{c(\Phi(q)-b)} \right] = 
\frac{e^{0}(1-q) + e^{-c}q}{1-(1-e^{-c})q}=
1
$$

The reference to Theorem 1 on line 538 probably should refer to Theorem 5.2

In line 554, the bound should probably be $\|V_t\|\le \frac{2}{m} L(W_{t-1})$. Based on this, the looser bound from line 551 seems unnecessary. 




questions: From what I can tell, the FGD is deterministic once the data set is fixed. As a result, Theorem 5.2 can be applied to a single run on FGD to give a high-probability bound on the test error. 

In contrast, it would seem that this is not necessarily possible for the stochastic algorithms, FSGD and the Langevin variants. In particular, the term $\mathcal{R}(W_T,S_I)$ requires averaging out the effects of the randomness of the algorithms. Is this the correct way to interpret this?

Based on that question above, is there a way to get true high-probability bounds for these stochastic algorithms? Would it just require running them several times (for a fixed dataset and selected $J$) and doing a concentration bound on the training error? Is there something more clever that can be done?
limitations: Yes. They indicate that the potential for negative societal impact is not applicable, and I agree.
review_title: null

Meta-review: metareview: Authors study generalization properties of gradient-based optimization algorithms via a PAC-Bayesian approach. Based on a data-dependent prior, authors establish a generalization bound for FGD, FSGD, GLD, and SGLD. The authors also provide convincing empirical studies to demonstrate that their results are not vacuous.

- Authors should better motivate the use of their seemingly synthetic algorithms.

- There are many typos in this paper, other than the ones listed by the reviewers. Although the reviewers did not raise this issue, authors should make sure their paper is ready for camera ready if the paper is accepted.
confidence: Less certain
Decision: Accept