5
$\begingroup$

Inspired by AnoE's answer to the problem Can a neural network with only 1 hidden layer solve any problem?, I want to rigorously prove that the sine function over the real line cannot be well approximated by a shallow neural network. So we want to show that $$ \sup_{x\in \mathbb{R}} |f(x) - \sin(x)| \geq 1$$ for any, say, neural network $f$ with 1 hidden layer and ReLU activation function.

Can you give me some ideas on how to approach this problem?

$\endgroup$
5
  • 2
    $\begingroup$ A ReLU network (of any depth and width) is ultimately a piecewise-linear function; the end behavior will at best be constant, and at worst go to infinity. $\endgroup$ Sep 28, 2022 at 14:38
  • $\begingroup$ @BenReiniger That sounds like an answer! $\endgroup$
    – Dave
    Sep 28, 2022 at 14:55
  • $\begingroup$ Are you assuming finite width of the hidden layer? $\endgroup$
    – Firebug
    Sep 28, 2022 at 14:59
  • $\begingroup$ @Firebug I assume no restriction on the width. $\endgroup$
    – itowan
    Sep 28, 2022 at 18:46
  • 2
    $\begingroup$ With infinite width (cardinality of the integers, convergence I guess needs some care), surely sine can be approximated. With arbitrary but finite width, it cannot. $\endgroup$ Sep 28, 2022 at 19:08

2 Answers 2

3
$\begingroup$

A ReLU network is ultimately a piecewise-linear continuous function. Each neuron in the first hidden layer is just a shifted and scaled ReLU. Taking a linear combination of those produces a piecewise linear function, with (at most) as many hingepoints as there are neurons. Applying ReLU to that can create new hingepoints whenever the function crosses 0, but this is at most once per linear segment, so you end up with at most twice as many hingepoints as neurons.

Having established that, the end behavior is linear. If the slope is nonzero, the function goes to infinity, and the supremum of errors is also infinite; if the slope is zero, the supremum of errors is at least 1.

... a shallow neural network

Actually, this isn't an important assumption. Adding layers can increase the number of hinge points multiplicatively, but at the end you're still stuck with a finite number of hinges and hence a bounded good-estimation range.

$\endgroup$
5
  • 1
    $\begingroup$ It is not clear that a bounded good-estimation range is necessarily problematic for $\sin (x)$, for example "over the real line" seems to me to be an abstraction which does not describe any actual data set. So is the OP's question, and your response to it concerned with mathematical abstractions (in which case, why not a ReLU with an infinite number of nodes?), or is it concerned with actual applications (in which case it is not clear how 'stuck at a finite number of hinges' is necessarily a problem)? $\endgroup$
    – Alexis
    Sep 29, 2022 at 18:10
  • $\begingroup$ @Alexis I think you’re getting at the compactness condition in the Cybenko universal approximation theorem. $\endgroup$
    – Dave
    Sep 29, 2022 at 18:38
  • $\begingroup$ I interpret the question as asking about one particular assumption (compact domain) in "the" universal approximation theorem. // Since a finite network is another assumption, I didn't touch on that (except in the comments). You can "easily" get real-line approximation in an infinite network by using the UAT on the continuous f(x)={sin(x) for x in [0, 2pi], 0 else}, and then setting the networks next to each other (?). $\endgroup$ Sep 29, 2022 at 18:40
  • $\begingroup$ Thanks, @Dave ! Ben Reiniger, I think just saying 'finite network' does not really get at this distinction between abstracting behavior across the real line versus application, since if someone says for $n$ hinges, the breakdown occurs at some value or some range of $x$, one can always respond $n+c$ hinges does not break down at this value of $x$ or over this entire range of $x$. $\endgroup$
    – Alexis
    Sep 29, 2022 at 19:08
  • $\begingroup$ @Alexis, sorry, I don't understand what you mean. Are we getting into the order of the quantifiers in the UAT? $\endgroup$ Sep 29, 2022 at 19:34
11
$\begingroup$

The classical (Cybenko) universal approximation theorem has a condition about the function being approximated on a compact space.

On the real line, the Heine-Borel theorem says that compacts sets are the closed and bounded sets.

Therefore, the Cybenko universal approximation theorem does not apply to a function over the whole real line. If you approximate $\sin(x)$ over a compact space, such as a closed interval, then the theorem holds.

$\endgroup$
1
  • 4
    $\begingroup$ This shows that the title of the Question is false, but the body of the Question remains open: prove that $\sin$ cannot be closely approximated. $\endgroup$ Sep 28, 2022 at 14:33

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.