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: The authors present a new concentration of measure inequality for sum of independent bounded random variables namely split-kl inequality. They derive this new inequality by combining kl-inequalities (1 and 2) in a clever way. They provide empirical cmparison of this new inequalities with the existing concentration inequalities such as kl-inequality, Empirical Bernstein inequality and Unexpected Bernstein inequality. They show that their new inequality is tighter than all of these inequalities in some regimes.

They further extend their contribution to PAC Bayes setting and derive PAC-Bayes-split-kl inequality. Again, they empirically (in synthetic and real world data) identify regimes where their inequality performs better than other existing inequalities such as PAC-Bayes-kl, PAC-Bayes Empirical Bernstein, PAC-Bayes Unexpected Bernstein, and PAC-Bayes Empirical Bennett inequalities.
strengths_and_weaknesses: Strengths:
The paper is easy to follow and claims stem from logical arguments. The experiments are extensive and support the claims made by authors. Theoretically, the idea is simple but interestingly, it leads to good empirical results.

Weaknesses:
It is difficult to understand that how is this new inequality fundamentally different than the kl inequality. Without a careful choice of $\mu$, I am not sure if this new inequality would always be tighter than kl inequality in all the regimes. My observation comes from the following argument: consider Z $\in [a, b]$. Take $\mu = a$, then $Z^+ = Z-a$ and $Z^- = 0$. Similalry, take $\mu = b$, then $Z^+ = 0$ and $Z^- = b - Z$. In both these cases, we are just translating Z and both kl inequality and kl-split inequality should behave similar for these choices of $\mu$. Of course, there might be a clever choice of $\mu$ which makes one perform better than the other but I am not sure how to make that choice.   

questions: - Can you add some experiments to show the dependency of the bound on choice of $\mu$?
- It would also be helpful to discuss the tighntness of various bounds as we increase n.

limitations: The limitations are discussed adequately.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors introduced a new approach to a concetration inquality for random variables over a bounded interval called "split kl inequality", which first decomposes the original random variable into three terms and then applies an existing bound "kl ineqaulity" to the decomposed terms. Then the authors proposed to use the split kl inequality for PAC-Bayes bounds of generalisation error of learning alrogrithms as well as to combine it with existing approaches of excess loss and informed prior. The derived PAC Bayes generalisation error bound were compared and examined in a few different experiments.
strengths_and_weaknesses: The reviewer is personally very much fond of the authors' writing in this paper, which explains important matters of this work / other existing works in an intuitive and comprehensive manner. For example, the motivation of this work is nicely lined up with a proper technical level to wide audiences in introduction. In addition, the advantage of split kl inequality has been made clear in Figure 1. Comprehensive presentation and simplicity of the idea is a clear strengh of this work. My main concern is the significance / impact when we combine this idea with PAC-Bayes bounds. The derived new generalisation bound in Figure 2, 3 seemed similar to the other existing bounds at first glance, or it was unclear how to interprete the improvement level. For the first experiment for example, since the authors combined their idea of split kl inequality with existing approaches of "informed priors", some might get an impression from these figures that the "informed prior" part has already finished the majority of works to lower a bound in each bound and they may wonder about how critical the improvement by the split kl part is.

questions: - How much is "informed prior" crucial to produce meaningful generalisation bounds in this context? — Would it be possilble to see how much improvement of bounds are done by "informed prior"? 
- I was also not familier with how commonly or frequently "informed prior" is used in PAC-Bayes domain. It may be helpful to more strongly justify that "informed prior" is a reasonable approach to use in practice by additional references.
- It would be visually helpful to make clear which bound is the proposed one in Figure 2 and 3 e.g. adding "(Ours)" or something to the name lavel of the proposed one in Figure 2 and 3.
- The models in the experiments dealt in this paper seem relatively simple. I understand that proving generalisation bounds of complex models is challenging but I was personally interested in seeing if the generalisation bound still works for more complex models e.g. LeNet for MNIST.
limitations: There would not no concern for potential negative societal impact. To me personally, the current limitation is that it is difficult to interprete from experiments or equations if the proposed idea of PAC-Bayes-split-kl inequalities has imporved the generalisation bounds to a fair defree or not. For example, would the difference of number in the figures be significant in the context of PAC-Bayes? The reviewer's position on this paper is neutral and the reviewer is happy to increase the score if the technical or practical impact is well justified.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a new concentration inequality for the sum of iid bounded random variables.  
The paper uses a  technique of splitting the samples with a threshold and then using a kl-inequality on each part.  This splitting allows using both the lower and upper bound kl-inequalities. 
The resulting bound enjoys both the tightness of the kl-inequality and the ability to exploit the lower variance of r.v. that takes values within a segment.
The empirical comparison clearly shows how the tightness of the new split-kl bound in different regimes, compared to the empirical Berenstein and the standard kl inequalities.

The paper then derives PAC-Bayes-Split-kl inequality
and applies it to the excess loss of a binary classification problem.
The new bound exploits the lowered variance of the excess losses compared to the binary losses, and therefore, the overall split-kl-PB bound can be competitive with the standard kl-PB bound, as demonstrated on synthetic and real-world data.

strengths_and_weaknesses: 
### Strengths
1. I believe the work is original and well-motivated.  
2. The use of the splitting technique is clever and novel, as far as I know.   
3. The paper is well-written and clear.
4. The authors provide an adequate survey of related work.
5. The empirical evaluation of the split-kl inequality clearly shows its merits.

### Weaknesses
1. The empirical evaluation of the split-kl-PAC-Bayes bound does not seem to give definitive conclusions, besides the looseness of PAC-Bayes-Empirical-Bennett on certain datasets.  I suggest adding more controlled synthetic experiments, as were done in Fig 1. for the concentration bounds since it can give good intuition to when certain bounds are preferable. 

questions: No additional questions
limitations: No additional limitations
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors address the question of providing PAC-Bayes bounds for losses when the (empirical) variance is low, as previously addressed by e.g. [1, 2].

A special case of this is finding bounds for ternary losses in {-1,0,1}, which arises in two important ways:
1. bounds on the excess misclassification loss, which can also be used as per [1] to tighten PAC-Bayes bounds on the non-excess loss
2. in conjunction with the Cantelli-Chebyshev relaxation given by [3] to provide bounds on the (non-randomized) weighted majority vote via PAC-Bayes.

For losses in {0, 1} the small-kl PAC-Bayes bound [e.g. 4] is usually the tightest, even when the variance is low, but not for losses in [-1, 1] (after rescaling the bound). In order to leverage this, the authors decompose translate each random variable in the sum before decomposing it into positive and negative parts,
$$Z_i = \mu + Z_i^+ Z_i^- = \mu + \max(0, Z_i-\mu) + \max(0, -Z_i+\mu)$$
before applying the small-kl bound to the sums of $Z_i^+$ and $Z_i^-$ separately (which are both {0, 1} valued in the ternary untranslated case). This is called the *split-kl* (PAC-Bayes) bound.

This is used to prove new concentration and PAC-Bayes bounds. These are further combined with the excess risk and informed prior ideas from [1], or the Cantelli-Chebyshev relaxation from [3], and evaluated in experimental setups taken from the above.



-----

[1] Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes un-expected Bernstein inequality.

[2] Ilya Tolstikhin and Yevgeny Seldin. PAC-Bayes-Empirical-Bernstein inequality.

[3] Yi-Shan Wu, Andres Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev-cantelli pac-bayes-bennett inequality for the weighted majority vote.

[4] John Langford. Tutorial on practical prediction theory for classification.


----

UPDATE:

Overall I am not satisfied with the quite limited evaluation of this bound, which does not show clear improvements from previous results. This weakens the motivation for the paper too because of the limited number of new technical ideas.

Therefore I find myself much more on the borderline than my original review and I do agree with some of the criticisms of reviewer nL9t. However, given that related work has previously appeared at NeurIPS with similarly negligible empirical improvements, I will keep my "weak accept" score.
strengths_and_weaknesses: ### Strengths

**Clarity and motivation**: the paper is very well written and was a pleasure to read. The relationships to previous works [1, 2] was very well explained and the incorporation of ideas from [1] was well motivated. The alternative form of the main result from [1] is an improvement in clarity to how it is stated therein and the situation of this work within its wider context was reasonably clear. My only minor criticism is that the experiments in section 4.2 do not sufficiently explain the use of the Chebyshev-Cantelli bound and majority votes as used there. This is a shame as I think the use of the split-kl bound for majority votes is a good use case.
 
**Relevance**: I think that the paper makes a contribution to an important and highly-active area of machine learning, improving PAC-Bayes bounds, which are among the most useful in contemporary learning theory. They bring some ideas from [1] to a wider application which is a valuable contribution.


### Weaknesses

**Technical contribution and originality**: here I think the paper falls down a bit. The main technical result is simply a decomposition of a random variable into positive and negative parts, combined with an application of the small-kl PAC-Bayes inequality. This is combined with the excess loss idea from [1] and the experimental setup therein, or the Cantelli-Chebyshev bound from [3] and their experimental setup, all of which is straightforward. Such simple ideas are can be very valuable when they lead to breakthroughs but that does not seem to be the case here, and most of the ideas used in the paper and discussed at length were originated by [1].

**Experimental results**: in the more important PAC-Bayes setting the new results are quite weak, with the new bound giving very similar results to that of [1]. The bound is not shown to be any improvement as optimization objective either. The simpler concentration inequality setting is not particularly interesting except as a motivation, and for the ternary r.v.s used an even better bound would be obtained by applying the test set bound (Th. 8) to the decomposition $Z = Z^+ - Z^-$ (i.e. a "split-Binomial" bound).
questions: 1. Is the bound stated in Theorem 3 equivalent to the different form given by [1]? It would be nice to show this.
2. In the experiments in section 4.2, it seems all of the bounds are based on the Cantelli-Chebyshev relaxation (with the tandem bound being $\alpha = 0$). Why have you not also compared to other bounds for the weighted majority vote, in particular the first order bound $L(MV) \le 2 L(\rho)$ with the small-kl, which is often the tightest?
limitations: N/A the results are primarily of a theoretical nature.
review_title: null

Meta-review: metareview: This meta review is based on the reviews, the authors rebuttal and the discussion with the reviewers, and ultimately my own judgement on the paper. There was a consensus that the paper contributes an interesting new concentration of measure inequality and derive a useful PAC-Bayes inequality. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers. Congratulations!
confidence: Certain
Decision: Accept