8
$\begingroup$

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)

$\endgroup$
13
  • $\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$ Jul 5, 2020 at 7:57
  • $\begingroup$ Yes. number of registers is finite. $\endgroup$
    – Rajesh D
    Jul 5, 2020 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, 2020 at 8:08
  • 2
    $\begingroup$ The randomly part is confusing: there is no uniform distribution on a countably infinite set. $\endgroup$ Jul 5, 2020 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$ Jul 5, 2020 at 13:46

4 Answers 4

19
$\begingroup$

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

$\endgroup$
6
  • $\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 D
    Jul 5, 2020 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 D
    Jul 5, 2020 at 10:38
  • $\begingroup$ See this to know what I mean by compute a function : annals.math.princeton.edu/wp-content/uploads/… $\endgroup$
    – Rajesh D
    Jul 5, 2020 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$ Jul 5, 2020 at 14:15
  • 1
    $\begingroup$ Agree with you. This finite arithmetic precision to represent data points $x_i$ is problematic. $\endgroup$
    – Rajesh D
    Jul 5, 2020 at 14:46
12
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
  • $\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 D
    Jul 6, 2020 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$ Jul 9, 2020 at 19:58
0
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ So you could do this for an equicontinuous family of functions on a compact domain. $\endgroup$ Jul 5, 2020 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 D
    Jul 5, 2020 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$ Jul 5, 2020 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 D
    Jul 5, 2020 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, 2020 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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