New analysis and algorithm for learning with drifting distributions

Mehryar Mohri, Andres Muñoz Medina

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a new analysis of the problem of learning with drifting distributions in the batch setting using the notion of discrepancy. We prove learning bounds based on the Rademacher complexity of the hypothesis set and the discrepancy of distributions both for a drifting PAC scenario and a tracking scenario. Our bounds are always tighter and in some cases substantially improve upon previous ones based on the L 1 distance. We also present a generalization of the standard on-line to batch conversion to the drifting scenario in terms of the discrepancy and arbitrary convex combinations of hypotheses. We introduce a new algorithm exploiting these learning guarantees, which we show can be formulated as a simple QP. Finally, we report the results of preliminary experiments demonstrating the benefits of this algorithm.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings
Pages124-138
Number of pages15
DOIs
StatePublished - 2012
Event23rd International Conference on Algorithmic Learning Theory, ALT 2012 - Lyon, France
Duration: Oct 29 2012Oct 31 2012

Publication series

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

Other

Other23rd International Conference on Algorithmic Learning Theory, ALT 2012
CountryFrance
CityLyon
Period10/29/1210/31/12

Keywords

  • Drifting environment
  • domain adaptation
  • generalization bound

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'New analysis and algorithm for learning with drifting distributions'. Together they form a unique fingerprint.

Cite this