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)



How to learn a continuous function?
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](https://en.wikipedia.org/wiki/Lusin%27s_theorem) 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](https://en.wikipedia.org/wiki/Tietze_extension_theorem) 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$.


