2
$\begingroup$

I'm working on this question which can be found at page 282 of "Understanding Machine Learning: From Theory to Algorithms" by Shai Shalev-Shwartz and Shai Ben-David.

The statement is as follows: Let $f : [−1, 1]^n \rightarrow [−1, 1]$ be a $\rho$-Lipschitz function. Fix some $\epsilon > 0$. Construct a neural network N : $[−1, 1]^n → [−1, 1]$, with the sigmoid activation function, such that for every $x \in [−1, 1]^n$ it holds that $|f(x) − N(x)| \leq \epsilon$.

Hint: Similarly to the proof of Theorem 19.3, partition $[−1, 1]^n$ into small boxes. Use the Lipschitzness of f to show that it is approximately constant at each box. Finally, show that a neural network can first decide which box the input vector belongs to, and then predict the averaged value of f at that box.

I looked up the solution from the solutions manual (made available by the author), but not sure I quite understand everything. The solution is a follows:

"Let $\epsilon > 0$. Following the hint, we cover the domain $[−1, 1]^n$ by disjoint boxes such that for every $x, x'$ which lie in the same box, we have $|f(x) − f(x')| \leq \epsilon/2$. Since we only aim at approximating $f$ to an accuracy of $\epsilon$, we can pick an arbitrary point from each box. By picking the set of representative points appropriately (e.g., pick the center of each box), we can assume w.l.o.g. that f is defined over the discrete set $[−1 + \beta, −1 + 2\beta, . . . , 1]^d$ for some $\beta \in [0, 2]$ and $d \in \mathbb{N}$ (which both depends on $\rho$ and $\epsilon$).

From here, the proof is straightforward. Our network should have two hidden layers. The first layer has $(2/\beta)^d$ nodes which correspond to the intervals that make up our boxes. We can adjust the weights between the input and the hidden layer such that given an input $x$, the output of each neuron is close enough to 1 if the corresponding coordinate of $x$ lies in the corresponding interval (note that given a finite domain, we can approximate the indicator function using the sigmoid function). In the next layer, we construct a neuron for each box, and add an additional neuron which outputs the constant $−1/2$. We can adjust the weights such that the output of each neuron is $1$ if $x$ belongs to the corresponding box, and $0$ otherwise. Finally, we can easily adjust the weights between the second layer and the output layer such that the desired output is obtained (say, to an accuracy of $\epsilon/2$)."

Now I understand the gist of the solution (we discretize the input space, use the Lipschitz proprety, and build the network), but I still have a lot of problems. Namely,

  1. What do $\beta$ and $d$ represent? Why do they depend on $\rho$ and $\epsilon$?
  2. How do we guarantee we can create a box such that $|f(x) − f(x')| \leq \epsilon/2$?
  3. What's the point of the "picking an arbitrary point" step? In the same vein, why do we create the intervals instead of just boxes?
  4. Why do we need two hidden layers? Why can't we just have the first layer map directily into the box?
  5. What's the point of the -1/2 neuron?

Basically I'm looking for someone to guide the proof to maybe a more intuitive undergrad level.

$\endgroup$
2
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$
    – vl_knd
    Commented Feb 15 at 15:00
  • $\begingroup$ 2. As you said "use the Lipschitz proprety" $\endgroup$
    – Robert
    Commented Feb 15 at 15:11

1 Answer 1

1
$\begingroup$

$\beta$ is the size of all the intervals used to partition the input space, and thus $(2/\beta)$ is the number of intervals along each dimension. $d$ is the number of input space dimensions actually used in the neural network's universal approximation of $ρ$-Lipschitz functions. These parameters depend on $ρ$ and $ϵ$ because they determine the granularity of the partitioning of the input space, which in turn affects the approximation accuracy of the neural network. Obviously if $ρ$ becomes smaller $\beta$ can become larger still satisfying $|f(x) − f(x')| \leq ρ|x − x'| \leq ρ\beta = \epsilon/2$ (i.e. $\beta=\epsilon/2ρ$) and if $\epsilon$ becomes larger, conceivably $d$ could become much less than $n$ as some features may not contribute much to the target value.

Therefore we can always ensure that the functional difference within any box is bounded above by $ϵ/2$ for any fixed $ϵ$, based on above inequality and appropriately choosing small enough $\beta$ of the boxes.

The arbitrary point is chosen to represent each box. By doing so, we reduce the problem of approximating the function over the entire box to approximating it at a single point within the box. Creating intervals along each dimension instead of just boxes as the first step is necessary and helps discretizing the input space, making it easier to design a neural network that operates on this discretized space.

The two hidden layers are used to perform two distinct tasks. The first layer with $(2/β)d$ nodes is responsible for determining which intervals the input $x$ belongs to. The second layer then refines this information, associating each neuron with a specific box where the final approximated function value can be computed in the output unit by manipulating the network's remaining parameters.

Including an additional neuron that outputs a constant $-1/2$ is ad hoc to help the network adjust or offset its decision boundary more flexibly which might lead to better accuracy related performance.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .