# $f(x)$ differentiable at $x_0$ with full rank derivatives implies $|f(x_0) - f(x)| \ge C |x_0 - x|$?!

I found a claim in this highly cited paper:

Pakes, A., & Pollard, D. (1989). Simulation and the asymptotics of optimization estimators. Econometrica: Journal of the Econometric Society, 1027-1057.

The claim appears in the proof of theorem 3.3 and is essentially the following:

(1?) If $$f(x)$$ is differentiable at $$x_0$$ with a derivative matrix $$\Gamma$$ of full rank, then there exists a $$C > 0$$ and a neighborhood $$\mathcal{B}$$ of $$x_0$$ such that, for every $$x$$ in $$\mathcal{B}$$,

$$\| f(x) - f(x_0) \| \ge C \| x - x_0 \|$$

How do I prove this statement?

Any help would be very appreciated.

We have that $$f(x)-f(x_0)=f'_{x_0}\cdot(x-x_0)+\epsilon(x-x_0).$$ Therefore, $$\Vert f(x)-f(x_0)\Vert \geq \Vert f'_{x_0}\cdot(x-x_0)\Vert -\Vert\epsilon(x-x_0)\Vert.$$ It follows that $$\frac{\Vert f(x)-f(x_0)\Vert}{\Vert x-x_0\Vert} \geq \Vert f'_{x_0}\cdot\left(\frac{x-x_0}{{\Vert x-x_0\Vert} }\right)\Vert -\frac{\Vert\epsilon(x-x_0)\Vert}{{\Vert x-x_0\Vert} }.$$ Let $K:= \min_{x \in S^{n-1}} \Vert f'_{x_0}\cdot x\Vert$. This is greater than zero, since $f'_{x_0}$ is injective*. By taking a small enough neighbourhood of $x_0$, we can arrange it so that the last term on the right is smaller than $K/2$. Hence, $$\Vert f'_{x_0}\cdot\left(\frac{x-x_0}{{\Vert x-x_0\Vert} }\right)\Vert -\frac{\Vert\epsilon(x-x_0)\Vert}{{\Vert x-x_0\Vert} } \geq K-K/2 =K/2.$$ Finally, we get that $$\frac{\Vert f(x)-f(x_0)\Vert}{\Vert x-x_0\Vert} \geq K/2,$$ and letting $C:=K/2$ yields what we want.

*If $f'_{x_0}$ is not injective, the result is not true. Indeed, the projection in the first argument $\pi: \mathbb{R}^n \to \mathbb{R}$ for $n>1$ provides a counter-example ($\pi(0,\cdots,0,1)=0$, and thus $\pi(0,\cdots,0,1)-\pi(0,\cdots,0,0)=0 < C \cdot 1$ for any $C>0$). This shows that you are probably under the assumption that $f: \mathbb{R}^n \to \mathbb{R}^m$ with $m \geq n$, so that "full rank" implies injective.

The idea (as usual) is that the function behaves like its derivative near the point $x_0$. If $f$ were linear, say $A: \mathbb{R}^n \to \mathbb{R}^m$, then we could directly pick $C:=K$. You may be more familiar with $\Vert A \Vert$, which is $\max$ instead of $\min$, but the concept is the same and we have $$\left(\min_{y \in S^{n-1}} \Vert A(y) \Vert \right) \Vert x-x_0\Vert \leq \Vert A(x-x_0) \Vert \leq \left(\max_{y \in S^{n-1}} \Vert A(y) \Vert\right) \Vert x-x_0\Vert.$$ We only need the left side for our purposes here, but following the right side would lead to concluding locally "Lipschitzness".

Since $f$ is not necessarily linear, we have to handle the term relating to the error $\epsilon$. The fact that it is $o(h)$ enables us to handle it just well, as we did above. Indeed, by refining a bit we can arrive at the conclusion that for every $c<1$, we have a neighbourhood such that $$\Vert f(x)-f(x_0)\Vert \geq cK\Vert x-x_0\Vert,$$ which says that we can make the inequality look as close to the linear case as possible, provided we are near enough $x_0$.

• I'm sorry, but what is $S^{n-1}$ in the definition of $K$? Jul 8, 2018 at 7:06
• @GuillaumeF. The unit sphere in $\mathbb{R}^n$. Jul 8, 2018 at 7:07
• Wonderful! Thank you! I think the key part I was missing what that for $f'_{x_0}$ injective, $$\Vert f'_{x_0}\cdot\left(\frac{x-x_0}{{\Vert x-x_0\Vert} }\right)\Vert \ge \min_{x \in S^{n-1}} \Vert f'_{x_0}\cdot x\Vert > 0$$ I was working with $f: \mathbb{R}^n \to \mathbb{R}^n$ and hence why I used the term "full rank". However, your injective condition works in more general settings. Jul 8, 2018 at 7:34
• @GuillaumeF. You are welcome! : ) Jul 8, 2018 at 7:36

Well, in $\mathbb{R} = \mathbb{R}^1$, we know that $f'(x_0) = \lim_{x \to x_0} \frac{f(x)-f(x_0)}{x-x_0}$. The condition of full rank just translates to $C := |f'(x_0)| \not = 0$. So, we may take a ball around $x_0$ of radius small enough so that $|\frac{f(x)-f(x_0)}{x-x_0} - C| < \frac{C}{2}$, which will imply $\frac{|f(x)-f(x_0)|}{|x-x_0|} \ge \frac{C}{2} \implies |f(x)-f(x_0)| \ge \frac{C}{2}|x-x_0|$.

In a general $\mathbb{R}^n$, we want the above to hold "in each direction" moving away from $x_0$. I'll leave it to you, using the idea I gave above, to show that having full rank suffices.

• Interestingly, we have $\frac{|C|}{2} < \frac{|f(x) - f(x_0)|}{|x - x_0|} < |C| \frac{3}{2}$, so that $f$ is bilipschitz on the neighborhood. Jul 8, 2018 at 6:49