Generalization of Hamiltonian algorithms

Summary

This work provides a novel approach to bound the generalization error (high probability bounds) of the Gibbs algorithm as an important example of Hamiltonian algorithms. The authors also applied their method to a different example of the Hamiltonian algorithm.

Strengths

Strengths: 1- A novel approach is proposed for bounding the generalization error of the Gibbs algorithm. 2- There are some improvements in comparison with other works. 3- The proof approach is well-discussed. 4- Section about Randomization of stable algorithms is interesting.

Weaknesses

1- In the case of the Gibbs algorithm, the contribution of this work is incremental. In particular, the authors should elaborate on why their results for the Gibbs algorithm are novel. 2- For the Gibbs algorithm, the main challenge is studying the asymptotic regime, where $\beta$ ---> \infty. It would be useful to study this regime or mention it as limitation of this analysis.

Questions

Sea weaknesses.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Sea weaknesses.

Summary

Summary ------- The papers presents a method to bound the `generalization gap', i.e the difference between the expected and empirical losses for a hypothesis h drawn from a probability class returned by the stochastic learning algorithm. The authors present a general-purpose method to bound the exponentiated difference, and apply this technique to Gibbs sampling (and other applications). As someone who is not an expert on the topic, but still theoretically inclined, I was unable to appreciate the contributions of this paper. It didn't help that the paper's presentation was not up to scratch either (see comments below). I have given a middle-of-the-line score to reflect this but will wait to hear from expert reviewers. Detailed comments ================= Questions - Is h a hypothesis or a loss function? In 9, 10 and equation (1), it is written as a loss but in line 12 it is treated as a hypothesis? - What is the motivation for bounding the difference between the expected loss of a a *learned* hypothesis, and the error on the training set? In typical use cases, one is interested in the test/generalization error after training. - From what I could gather from the Gibbs sampling use case in 4.1, this can be used to bound the rate of convergence of Gibbs sampling. Is this correct? The presentation of the paper could improve significantly. - It is customary (at least in CS venues), to include an outline of the results, describe their significance of each result, and outline the key challenges and techniques used in the paper. - The paper would also benefit from a dedicated related work section, where the authors explicitly state the most relevant work and how their results compare to them. The most interesting comparison I saw was in section 4.1 where they compare their bound to Rivasplata et al, and the improvement in the \sqrt{\log(1/\delta)} term. Even here, the authors have not explained why this gap \Delta is significant. Does it lead to fast convergence rates for Gibbs sampling? Perhaps the authors could state this result up front to prime the reader for what they can expect from this paper. - On the same note, the authors should do a better job of highlihgting the key results in this paper. Currently, there are several lemmas/theorems presented one after the other and it is hard to appreciate which ones are the most significant, and why they are significant. My recommendation would be to identify the ~2 main theorems of the paper

Strengths

See above

Weaknesses

See above

Questions

See above

Rating

6

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

See above

Summary

This submission is a purely theoretical work, whose main goal is to bound $\Delta(h,\mathbf{X})=\mathbb{E}[h(X)]-\frac{1}{n}\sum^n_{i=1}h(X_i)$, i.e. equation (1). After some preliminary results, the results that show this bound under different conditions are Theorem 3.4, Theorem 3.5 and Theorem 3.8. Some possible (theoretical) applications are also shown, in the form of the Gibbs algorithm, randomisation of stable algorithms and PAC-Bayes bounds with data-dependent priors.

Strengths

Unfortunately, I have not worked in any of the subfields that this paper is concerned with, so my judgment on its importance should be taken with a pinch of salt, but I am convinced of its significance and the contributions that this paper makes. I have also tried to go through some of the maths in detail to check for its soundness, and barring a couple of very minor errors (see "Questions"), I think this paper is excellent in that regard. I really liked the way this paper was written, straight to the point with minimum fuss, and my impression is overwhelmingly positive.

Weaknesses

I think the authors made a deliberate choice to be concise with the proofs so that the proof can be included in the main body of the paper. I really like this, but in some places, the proof is too short, so that the readers are asked to do a significant amount of algebra by themselves. If possible, it would be great if the authors could use the extra page to flesh out the proofs a little bit.

Questions

Displayed equation after L89: This seems to be a pointwise statement for both $h$ and $\mathbf{x}$, so should it be “for all $h\in\mathcal{H}$ and for all $\mathbf{x}\in\mathcal{X}^n$? Unless the statement should be “… is called a Hamiltonian for $Q_\mathbf{x}$” instead of “Hamiltonian for $Q$”? Displayed equation after L162: Shouldn’t $2bc$ be $\frac{bc}{2}$, taking into account the factor of $\frac{1}{8}$? The $2nc^2$ in the numerator of the fraction should also be $\frac{nc^2}{2}$. It looks like this is corrected on L163, and working through the maths, I indeed got the claimed inequality in Theorem 3.4(ii). L183: I think you are missing a $\ln$ in front of the exponential?

Rating

8

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

L88: "A function $H:\mathcal{H}\times\mathcal{X}^n$" perhaps it is better to write “A function $H$ on $\mathcal{H}\times\mathcal{X}^n$? I leave this up to the authors. Displayed equation after L153: The spacing is a bit strange on the left? L185: an -> and Displayed equation after L195: The comma should be a full stop. L178, L389: “Assume that all” -> “Assume that for all” L391: everz -> every

Summary

This paper introduces a general method to bound the logarithm of the expecattion of the exponential of the generalization gap for stochastic learning algorithms. This method is applicable when the distribution of the algorithm concentrates exponentially around its mean, extending to cases where the Hamiltonian form satisfies a bounded difference condition or is sub-Gaussian. Further, the paper discuss applications to the gibbs algorithm, improving existing bounds, Lastly the paper extends generalization guarantees to hypotheses sampled once from stochastic kernels centered at the output of uniformly stable algorithms. This advancement strengthens previous results and improves the understanding of generalization properties for algorithms based on stochastic kernels.

Strengths

The paper is very-well written. it is crisp and clear about the notations, contributions and the context of the novel results with respect to the exsiting literature. The theoretical rigor is well-presented and the results are very well supported through coherent arguments. I specially appreciate the "self-contained" nature of the paper, where everything including the very fundamental markov inequality is written in the appendix for convenience of the reader so there is no need to refer to other papers to understand, verify and appreciate the contributions of the paper. The paper makes non-trivial theoretical contributions. It provides generalization guarantees for bounded hypothesis (section 3.1) and unbounded hypothesis through subgaussianity (Section 3.2). The contributions include a general method for bounding generalization gaps for the specific case of Hamiltonian algorithms, thereby identifying an important subclass of problems to bound the notorious ln E_X E_h [exp \lambda \Delta] which is often not amenable for general problems. This contribution is important. Further, the authors specify precisely where the bounds improve upon exisiting results (e.g. dependence on the confidence parameter \delta is improved from previously known O(\sqrt(1/\delta) to O(1/\delta) for the gibbs algorithm), often with simpler proof techniques and cleaner constants/exponents.

Weaknesses

The paper is very notation-heavy, and likely not accessible to everyone. This is not really a critique of the paper tbh, but more of the nature of the result/paper and the short conference format. The authors have done a fair job of explaining the notations. But It is easy to get lost in keeping track. For example, the notion of canonical Hamiltonian H_Q and its usefulness (for example in the simple proof of Prop 3.1) is easy to overlook unless one really gets into the weeds. I would suggest adding a couple of sentences cementing the importance of H_Q in the analysis. Beyond helping through and simplifying some results, is there additional importance of H_Q ? The conclusion and future directions/discussions/limitations section is severely lacking. Can the authors talk about limitations of the proposed method, and any further possible open problems that the reader might be interested in. There is no empirical verification, even with toy setups. Can the authors comment on how the presented theory can be empirically demonstrated/verified?

Questions

In addition to the weaknesses: In context of the paper, and the definition of \Delta(h,X), which we know is centered, I am not sure how Prop 3.1 is useful or applied in this paper. I understand it could be potentially useful where F and H_Q can be handled separately (assuming F being non-centered is still somehow amenable to this). But for this paper, this is not the case. The notation S^k_X f(\mathbf{x}) used in prop 3.2 onwards is clunky at best, and badly overloaded at worst. May I suggest using f(S^k_X \mathbf{x}) ? theorem 3.4 needs h(y’) \in [0,b] ? I think you mean \forall t \in \mathcal{X} h(t) \in [0,b] ? “In practice Q is often defined by specifying some Hamiltonian H , so HQ (h, x) = H (h, x) − ln Z (x) in general” – I am not sure what this sentence means. Please expand. Are you saying the canonical H_Q can be trivially written like that? How is Q being defined through that? L186 “generalization guarantee of rapid convergence” .. could you expand on this please? What order is considered as “rapid”? Minor: In a couple of places some of the references seem to be hard-coded ? e.g. references to A.1 because those are not clickable links.

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Partially.

Thank you for your response

The authors have clarified my minor doubts and I confirm my opinion that this is a solid theoretical contribution. Some experiments, even simulated ones, to validate the results will improve the quality of the paper even further.

Increasing score

Thanks for your response. Based on the rebuttal and the other reviews, I have increased my score.

Feedback

I want to thank the authors for their response. I hope that the asymptotic discussion will be included in the final version.