Learning lipschitz functions

Abstract

Abstract Considered here is the problem of learning a nonlinear mapping with uncountable domain and range. The learning model used is that of piecewise linear interpolation on random samples from the domain. More specifically, a network learns a function by approximating its value, typically within some small ∈, when presented an arbitrary element of the domain. For reliable learning, the network should accurately return the function's value with high probability, typically higher than 1 − δ for some small δ.The focal results of this article are the derivations of bounds showing that, given ∈ and δ and an arbitrary Lipschitz function f: [0, 1] k →R, samples from the uniform distribution on [0,1] k are sufficient to reliably learn f, and that samples are necessary for reliable learning. The Delaunay triangulation technique, which necessarily keeps simplex sizes small, is exploited. Keywords: Function learningPAC learningLipschitz functionsDelaunay triangulationAMS Subject Classifications: 68TO5 (Learning and adaptive systems)systems), 26A16 (Lipschitz (Hölder) classes)C.R. Categories: G.1.1I.2.8.