Header logo is ei

Uniform Convergence of Adaptive Graph-Based Regularization


Conference Paper


The regularization functional induced by the graph Laplacian of a random neighborhood graph based on the data is adaptive in two ways. First it adapts to an underlying manifold structure and second to the density of the data-generating probability measure. We identify in this paper the limit of the regularizer and show uniform convergence over the space of Hoelder functions. As an intermediate step we derive upper bounds on the covering numbers of Hoelder functions on compact Riemannian manifolds, which are of independent interest for the theoretical analysis of manifold-based learning methods.

Author(s): Hein, M.
Book Title: COLT 2006
Journal: Learning Theory: 19th Annual Conference on Learning Theory (COLT 2006)
Pages: 50-64
Year: 2006
Month: September
Day: 0
Editors: Lugosi, G. , H.-U. Simon
Publisher: Springer

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1007/11776420_7
Event Name: 19th Annual Conference on Learning Theory
Event Place: Pittsburgh, PA, USA

Address: Berlin, Germany
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Uniform Convergence of Adaptive Graph-Based Regularization},
  author = {Hein, M.},
  journal = {Learning Theory: 19th Annual Conference on Learning Theory (COLT 2006)},
  booktitle = {COLT 2006},
  pages = {50-64},
  editors = {Lugosi, G. , H.-U. Simon},
  publisher = {Springer},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Berlin, Germany},
  month = sep,
  year = {2006},
  month_numeric = {9}