On the complexity of learning from drifting distributions

It is shown that if each example is drawn from a joint distribution which changes in total variation distance by at most O( 3=(d log(1= ))) between trials, then an algorithm can achieve a probability of a mistake at most worse than the best function in a class of VC-dimension d.

Abstract

Article On the complexity of learning from drifting distributions Share on Authors: Rakesh D. Barve Department of Computer Science, Duke University, P.O. Box 90129, Durham, North Carolina Department of Computer Science, Duke University, P.O. Box 90129, Durham, North CarolinaView Profile , Philip M. Long ISCS Department, National University of Singapore, Singapore 119260, Republic of Singapore ISCS Department, National University of Singapore, Singapore 119260, Republic of SingaporeView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 122–130https://doi.org/10.1145/238061.238077Online:01 January 1996Publication History 5citation176DownloadsMetricsTotal Citations5Total Downloads176Last 12 Months7Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access