How to learn a continuous function?

Question

Let $\Omega \subset \mathbb{R}^m$ be an open subset bounded with a smooth boundary.

Problem : Given any bounded continuous function $f:\Omega\to\mathbb{R}$, can we learn it to a given accuracy $\epsilon$? ($\epsilon>0$).

Definition : What do you mean by learning a function to a given accuracy $\epsilon$?

Using samples of $f$, at sufficiently large but finite number of data points that are drawn randomly(iid) from the set $\Omega$ (under a uniform probability distribution), and using a sufficiently large but finite number of registers whose precision (arithmetic) is sufficiently large but finite (this finite precision is an important condition), should be able to compute a function $F$ with only a finite number of computations (they could be additions, multiplications, and divisions but performed using registers of finite precision) such that $\|f-F\|_{L^\infty(\Omega)} \le \epsilon$.

compute a function $F$ : Given any query point $x$, one should give out $F(x)$.

Conjecture: There exists a method of learning such that one can derive a bound on required precision $p$ that depends only on $\Omega$ and $\epsilon$ and is independent of $f$.

Question: Has anyone formulated this problem before (any reference). Has anyone solved it? If I solve it, what is its market value? (mathematics market)

PS: solving means coming up with a method to learn such functions in the defined way.

(please feel free to tag appropriately)

Answer 1

The answer is no by a Cantor diagonal argument:

Let $\Omega=(0,1)$.

Let $G$ be all functions that can be computed by a finite number of registers with finite precision. It does not matter where $G$ is learnt from.

• The number of states of $n$ registers with precision $m$ is finite, thus the number of functions computable on $n$ registers with precision $m$ is finite. Let the set of such functions be $G_{mn}$.

• Thus, $G=\bigcup_{m\in \mathbb{N}} \bigcup_{n\in \mathbb{N}} G_{mn}$ is countable. Label the elements of $G$ by $G_1,G_2,...$

Since there're an infinite number of disjoint intervals contained in $\Omega$, it's possible to avoid each $G_i$ on some interval on $\Omega$.

Let $H_n=[1-10^{-n}+\frac1310^{-n},1-10^{-n}+\frac2310^{-n}]$ be a closed interval on $\Omega$. Since $G_n$ is measurable, we can find a continuous function $f_n$ that agrees with $G_n+1$ on at least half of $H_n$ (i.e. the measure of $\{f_n=G_n+1\}$ is at least half of that of $H_n$).

Let $f$ be a continuous function on $\Omega$ that agrees with $f_n$ on $H_n$ for every $n$.

Then, for each $n$, $||f-G_n||_{L^\infty(\Omega)} \geq ||f-G_n||_{L^\infty(H_n)} \geq ||f_n-G_n||_{L^\infty(\{f_n=G_n+1\})}=1$.

Answer 2

The answer is NO from general no-free-lunch principles. In particular, the collection of all continuous functions has infinite fat-shattering dimension, and hence is not learnable in your sense. See Alon, Ben-David, Cesa-Bianchi, and Haussler - Scale-sensitive dimensions, uniform convergence, and learnability.

Answer 3

Counterexample: sin(1/x) over (0,1) Learning the function near 0 requires infinitely many samples.

Answer 4

You can do this if $f$ is uniformly continuous on $\Omega$.

Then given any $\epsilon>0$ you can find $\delta >0$ s.t if you sample $\Omega$ within $\delta >0$ you can reconstruct $f$ to within $\epsilon$ by using nearest neighbour interpolation, define $F(x)$ to have value $f(x_{\Omega})$ where $x_{\Omega}$ is the nearest sample point to $x$ in $\Omega$. Since $\Omega$ is bounded this only needs a finite number of sampling points which are reasonably evenly distributed. i.e. a random sample of sufficient size would do. You can approximate any real number to a fixed precision using a rationals of bounded height so the precision is also finite.

Clearly you cannot do this uniformly. Different functions $f$ will require a different $\delta$ for a given $\epsilon$.