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)

  • $\begingroup$ I'm not sure what is the point of limiting the precision of registers, since it's possible to concatenate small registers to a larger one. Limiting the precision only makes sense if the numebr of registers is also limited. Should the number of registers also be limited? $\endgroup$ – LeechLattice Jul 5 at 7:57
  • $\begingroup$ Yes. number of registers is finite. $\endgroup$ – Rajesh Dachiraju Jul 5 at 7:59
  • $\begingroup$ How are you supposed to catch e.g. all bump functions? Also, if you are working with general continuous functions, infinite precision information is completely local so you can safely allow it and still the problem is impossible to solve. $\endgroup$ – Ville Salo Jul 5 at 8:08
  • 2
    $\begingroup$ The randomly part is confusing: there is no uniform distribution on a countably infinite set. $\endgroup$ – Benoît Kloeckner Jul 5 at 13:35
  • 1
    $\begingroup$ Ok, then you clearly need to restrict the modulus of continuity uniformly on the family of functions you want to consider, as is explained in other answers and comments to them. $\endgroup$ – Benoît Kloeckner Jul 5 at 13:46

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$.

| cite | improve this answer | |
  • $\begingroup$ See my question : "compute a function F : Given any query point x, one should give out F(x)"....only once...only for the given single $x$. Need not compute for all $x$ in the domain. Thats what I mean by compute a function. $\endgroup$ – Rajesh Dachiraju Jul 5 at 10:35
  • $\begingroup$ "Compute a function" is an algorithm or a formula that gives out $F(x)$ for a given $x$. And to do this, for a single given $x$, need to be done with finite registers, computations and ...blah blah blah... $\endgroup$ – Rajesh Dachiraju Jul 5 at 10:38
  • $\begingroup$ See this to know what I mean by compute a function : annals.math.princeton.edu/wp-content/uploads/… $\endgroup$ – Rajesh Dachiraju Jul 5 at 10:49
  • 4
    $\begingroup$ But $x$ could be any element in the domain. If the number of registers and their precision need to compute $F(x)$ is bounded independently of $x$, then my argument still applies. $\endgroup$ – LeechLattice Jul 5 at 14:15
  • 1
    $\begingroup$ Agree with you. This finite arithmetic precision to represent data points $x_i$ is problematic. $\endgroup$ – Rajesh Dachiraju Jul 5 at 14:46

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.

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ both the number of samples and there by the arithmetic precision, both should go to infinity and only then we can expect $\lim\limits_{N\to \infty}\|f-F_N\|_{L^{\infty}(\Omega)} \to \epsilon$ or ofcourse it can better. but this is the best thing that can be said. I should probably use limit supremum. $\endgroup$ – Rajesh Dachiraju Jul 6 at 10:17
  • $\begingroup$ Technically, a single function can never be a counterexample, since an unrestricted learner can just have it hard-coded inside. You want a family of functions as a counter-example. $\endgroup$ – Aryeh Kontorovich Jul 9 at 19:58

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$.

| cite | improve this answer | |
  • 2
    $\begingroup$ So you could do this for an equicontinuous family of functions on a compact domain. $\endgroup$ – Aryeh Kontorovich Jul 5 at 9:40
  • $\begingroup$ If you read my question, " at sufficiently large but finite number of data points", so the number of data points required need not be bounded by a bound independent of $f$. They just have to be finite for a given $f$. The bound I am conjecturing is on required precision, and that be independent of $f$. So your answer is valid for all continuous functions, but the problem I am worried is that you may need to draw sample points infinite times to get an $delta$-even distribution? I hope I am wrong. $\endgroup$ – Rajesh Dachiraju Jul 5 at 9:40
  • 1
    $\begingroup$ Your conjecture specifically states "one can derive a bound on required precision p that depends only on Ω and epsilon and is independent of f". $\endgroup$ – Aryeh Kontorovich Jul 5 at 10:03
  • $\begingroup$ @AryehKontorovich : Yes bound on precision. Not the number of data points. Precision means arithmetic precision of floating point number. Suppose the function value at a data point $x$ is $f(x)$, the number of bits used to represent the real number $f(x)$ is what I meant by arithmetic precision. Like we use double precison floating point numbers and single precision floating point numbers in matlab. $\endgroup$ – Rajesh Dachiraju Jul 5 at 10:15
  • $\begingroup$ Yes the precision required in general will depend on $f$ as clearly if you required a large number of data points to get your sampling of $\Omega$ within $\delta$ then you need enough precision to prevent sample data points merging which would not then allow you to pick up the fine details of the function - it could oscillate with arbitrarily small period. If you take only functions with variation bounded by a constant value you can do it I think. $\endgroup$ – Ivan Meir Jul 5 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.