A Distribution Dependent and Independent Complexity Analysis of Manifold Regularization

Alexander Mey*, Tom Julian Viering, Marco Loog

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
39 Downloads (Pure)


Manifold regularization is a commonly used technique in semi-supervised learning. It enforces the classification rule to be smooth with respect to the data-manifold. Here, we derive sample complexity bounds based on pseudo-dimension for models that add a convex data dependent regularization term to a supervised learning process, as is in particular done in Manifold regularization. We then compare the bound for those semi-supervised methods to purely supervised methods, and discuss a setting in which the semi-supervised method can only have a constant improvement, ignoring logarithmic terms. By viewing Manifold regularization as a kernel method we then derive Rademacher bounds which allow for a distribution dependent analysis. Finally we illustrate that these bounds may be useful for choosing an appropriate manifold regularization parameter in situations with very sparsely labeled data.

Original languageEnglish
Title of host publicationAdvances in Intelligent Data Analysis XVIII - 18th International Symposium on Intelligent Data Analysis, IDA 2020, Proceedings
EditorsMichael R. Berthold, Ad Feelders, Georg Krempl
Number of pages13
ISBN (Print)9783030445836
Publication statusPublished - 2020
Event18th International Conference on Intelligent Data Analysis, IDA 2020 - Konstanz, Germany
Duration: 27 Apr 202029 Apr 2020
Conference number: 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12080 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Intelligent Data Analysis, IDA 2020
Abbreviated titleIDA 2020
OtherVirtual/online event due to COVID-19

Bibliographical note

Virtual/online event due to COVID-19


  • Learning theory
  • Manifold regularization
  • Semi-supervised learning


Dive into the research topics of 'A Distribution Dependent and Independent Complexity Analysis of Manifold Regularization'. Together they form a unique fingerprint.

Cite this