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?
Asked
Active
Viewed 85 times
1 Answers
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.
Siong Thye Goh
- 149,520
- 20
- 88
- 149
-
Why is $|\Delta-\Delta_j|\leq r$? – nonpara Apr 14 '20 at 15:59
-
1$\Delta_j$ is the center of a ball with radius $r$ and $\Delta$ is within the ball. – Siong Thye Goh Apr 14 '20 at 16:03