IJPAM: Volume 32, No. 1 (2006)

LEARNING $C^{2}$ AND HÖLDER FUNCTIONS

Duane A. Cooper
Department of Mathematics
Morehouse College
830 Westview Drive SW, Atlanta, GA 30314, USA
e-mail: dcooper@morehouse.edu


Abstract.Considered here is the problem of learning nonlinear mappings drawn from certain classes of functions with uncountable domain and range. The learning model used is that of piecewise linear interpolation on random samples from the domain. In more detail, a network learns a function by approximating its value, typically within some small $\epsilon$, 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-\delta$ for some small $\delta$.

The primary results of this article are the derivations of bounds showing that, given $\epsilon$ and $\delta$ and arbitrary $C^{2}$ function $f:[0,1]^{k} \rightarrow \mathbb{R}$,

\begin{displaymath}m \geq (kC)^{k/2} \cdot (\frac{1}{\epsilon})^{k/2} \cdot (\fr... ...) + \frac{k}{2} \ln \frac{1}{\epsilon} + \ln \frac{1}{\delta}) \end{displaymath}

samples from the uniform distribution on $[0,1]^{k}$ are sufficient to reliably learn $f$, and that

\begin{displaymath}m \geq (\frac{Ck}{4})^{k/2} \cdot (\frac{1}{\epsilon})^{k/2} \cdot \ln \frac{1}{\delta} \end{displaymath}

samples are necessary for reliable learning.

Furthermore, given $\epsilon$ and $\delta$ and arbitrary Hölder function $f:[0,1]^{k} \rightarrow \mathbb{R}$,

\begin{displaymath}m \geq (3C)^{k/\alpha} \cdot k^{k/2} \cdot (\frac{1}{\epsilon... ...frac{k}{\alpha} \ln \frac{1}{\epsilon} + \ln \frac{1}{\delta}) \end{displaymath}

samples from the uniform distribution on $[0,1]^{k}$ are sufficient to reliably learn $f$, and

\begin{displaymath}m \geq (\frac{C^{1/\alpha}\sqrt{k}}{2})^{k} \cdot (\frac{1}{\epsilon})^{k/\alpha} \cdot \ln \frac{1}{\delta} \end{displaymath}

samples are necessary for reliable learning.

Received: August 24, 2006

AMS Subject Classification: 68T05, 26B35

Key Words and Phrases: function learning, PAC learning, $C^{2}$ functions, Hölder functions

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2006
Volume: 32
Issue: 1