Consistent Learning Methods are Approximately Local

Ya'acov Ritov
Hebrew University
Jerusalem

Abstract

        We consider a typical learning problem: given a sample Sn={(xi,yi), i=1,...,n} and a point x, we have an estimate yhat(Sn,x) of y. We say that yhat is local if it produces a guess that is not much different, asymptotically speaking, from the guess it would have made using only the points in Sn that are close to x. We formally define this concept, as well as an approximate version of it, and present several theoretical results, in particular that any consistent method is approximately local. We also discuss practical applications of this approach and present empirical results consistent with the theory.

This is joint work with Alon Zakai