Learning with side information: PAC learning bounds

P. Kuusela, D. Ocone

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper considers a modification of a PAC learning theory problem in which each instance of the training data is supplemented with side information. In this case, a transformation, given by a side-information map, of the training instance is also classified. However, the learning algorithm needs only to classify a new instance, not the instance and its value under the side information map. Side information can improve general learning rates, but not always. This paper shows that side information leads to the improvement of standard PAC learning theory rate bounds, under restrictions on the probable overlap between concepts and their images under the side information map.

Original languageEnglish (US)
Pages (from-to)521-545
Number of pages25
JournalJournal of Computer and System Sciences
Issue number3
StatePublished - May 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Dependent data
  • Learning theory
  • Probably Approximately Correct learning
  • Uniform convergence of empirical means


Dive into the research topics of 'Learning with side information: PAC learning bounds'. Together they form a unique fingerprint.

Cite this