The proof of random fourier features

Question

I am reading the following paper. https://people.eecs.berkeley.edu/~brecht/papers/07.rah.rec.nips.pdf And I came down to the proof of Claim 1. The proof states in the 6th line of page 8 that "We have $|f(\Delta)|<\epsilon$ for all $\Delta \in M_{\Delta}$ if $|f(\Delta_i)|<\epsilon/2$ and $L_f<\epsilon/2r$ for all $i$." I have no idea why this is true. Any ideas?

Answer 1

Let $j$ be a corresponding index of the ball that covers $\Delta$.

\begin{align} |f(\Delta)| &\le |f(\Delta)-f(\Delta_j)|+|f(\Delta_j)|\\ &< L_f|\Delta - \Delta_j| + \frac{\epsilon}{2}\\ &\le \left(\frac{\epsilon}{2r}\right) (r) + \frac{\epsilon}{2}\\ & = \epsilon \end{align}

The first inequality is due to triangle inequality and the second inequality is due to Lipschitz condition.