Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence

Chao Zhang, Jieping Ye
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:717-725, 2013.

Abstract

In this paper, we present the Bennett-type generalization bounds of the learning process for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional results. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one provides the generalization bounds based on the uniform entropy number; the other leads to the bounds based on the Rademacher complexity. We then adopt a new method to obtain the alternative expressions of the Bennett-type generalization bounds, which imply that the bounds have a faster rate o(N -1 2 ) of convergence than the traditional results O(N -1 2 ). Additionally, we find that the rate of the bounds will become faster in the large-deviation case, which refers to a situation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical convergence of the learning process and compare our analysis with the existing results.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-zhang13a, title = {Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence}, author = {Zhang, Chao and Ye, Jieping}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {717--725}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/zhang13a/zhang13a.pdf}, url = {https://proceedings.mlr.press/r11/zhang13a.html}, abstract = {In this paper, we present the Bennett-type generalization bounds of the learning process for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional results. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one provides the generalization bounds based on the uniform entropy number; the other leads to the bounds based on the Rademacher complexity. We then adopt a new method to obtain the alternative expressions of the Bennett-type generalization bounds, which imply that the bounds have a faster rate o(N -1 2 ) of convergence than the traditional results O(N -1 2 ). Additionally, we find that the rate of the bounds will become faster in the large-deviation case, which refers to a situation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical convergence of the learning process and compare our analysis with the existing results.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence %A Chao Zhang %A Jieping Ye %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-zhang13a %I PMLR %P 717--725 %U https://proceedings.mlr.press/r11/zhang13a.html %V R11 %X In this paper, we present the Bennett-type generalization bounds of the learning process for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional results. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one provides the generalization bounds based on the uniform entropy number; the other leads to the bounds based on the Rademacher complexity. We then adopt a new method to obtain the alternative expressions of the Bennett-type generalization bounds, which imply that the bounds have a faster rate o(N -1 2 ) of convergence than the traditional results O(N -1 2 ). Additionally, we find that the rate of the bounds will become faster in the large-deviation case, which refers to a situation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical convergence of the learning process and compare our analysis with the existing results. %Z Reissued by PMLR on 04 October 2026.
APA
Zhang, C. & Ye, J.. (2013). Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:717-725 Available from https://proceedings.mlr.press/r11/zhang13a.html. Reissued by PMLR on 04 October 2026.

Related Material