Learning lipschitz functions
Duane A. Cooper · International Journal of Computer Mathematics · 1995
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.