We investigate measures of complexity of function classes based on continuity moduli of Gaussian and Rademacher processes. For Gaussian processes, we obtain bounds on the continuity modulus on the convex hull of a function class in terms of the same quantity for the class itself. We also obtain new bounds on generalization error in terms of localized Rademacher complexities. This allows us to prove new results about generalization performance for convex hulls in terms of characteristics of the base class. As a byproduct, we obtain a simple proof of some of the known bounds on the entropy of convex hulls.
Description
Some Local Measures of Complexity of Convex Hulls and Generalization Bounds | SpringerLink
%0 Conference Paper
%1 10.1007/3-540-45435-7_5
%A Bousquet, Olivier
%A Koltchinskii, Vladimir
%A Panchenko, Dmitriy
%B Computational Learning Theory
%C Berlin, Heidelberg
%D 2002
%E Kivinen, Jyrki
%E Sloan, Robert H.
%I Springer Berlin Heidelberg
%K bounds generalization learning mathematics probability stats theory
%P 59--73
%T Some Local Measures of Complexity of Convex Hulls and Generalization Bounds
%X We investigate measures of complexity of function classes based on continuity moduli of Gaussian and Rademacher processes. For Gaussian processes, we obtain bounds on the continuity modulus on the convex hull of a function class in terms of the same quantity for the class itself. We also obtain new bounds on generalization error in terms of localized Rademacher complexities. This allows us to prove new results about generalization performance for convex hulls in terms of characteristics of the base class. As a byproduct, we obtain a simple proof of some of the known bounds on the entropy of convex hulls.
%@ 978-3-540-45435-9
@inproceedings{10.1007/3-540-45435-7_5,
abstract = {We investigate measures of complexity of function classes based on continuity moduli of Gaussian and Rademacher processes. For Gaussian processes, we obtain bounds on the continuity modulus on the convex hull of a function class in terms of the same quantity for the class itself. We also obtain new bounds on generalization error in terms of localized Rademacher complexities. This allows us to prove new results about generalization performance for convex hulls in terms of characteristics of the base class. As a byproduct, we obtain a simple proof of some of the known bounds on the entropy of convex hulls.},
added-at = {2019-04-26T13:37:49.000+0200},
address = {Berlin, Heidelberg},
author = {Bousquet, Olivier and Koltchinskii, Vladimir and Panchenko, Dmitriy},
biburl = {https://www.bibsonomy.org/bibtex/2a80635507d2edc5bb62a0da234375f48/kirk86},
booktitle = {Computational Learning Theory},
description = {Some Local Measures of Complexity of Convex Hulls and Generalization Bounds | SpringerLink},
editor = {Kivinen, Jyrki and Sloan, Robert H.},
interhash = {2420a7704ce93292e0b27ba6a58cc560},
intrahash = {a80635507d2edc5bb62a0da234375f48},
isbn = {978-3-540-45435-9},
keywords = {bounds generalization learning mathematics probability stats theory},
pages = {59--73},
publisher = {Springer Berlin Heidelberg},
timestamp = {2019-04-26T13:37:49.000+0200},
title = {Some Local Measures of Complexity of Convex Hulls and Generalization Bounds},
year = 2002
}