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 pro- cess for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional re- sults. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one pro- vides 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 sit- uation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical conver- gence 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 pro- cess for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional re- sults. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one pro- vides 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 sit- uation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical conver- gence 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 pro- cess for i.i.d. samples, and then show that the generalization bounds have a faster rate of convergence than the traditional re- sults. In particular, we first develop two types of Bennett-type deviation inequality for the i.i.d. learning process: one pro- vides 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 sit- uation where the empirical risk is far away from (at least not close to) the expected risk. Finally, we analyze the asymptotical conver- gence 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