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

Question

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.

Answer 1

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$.

Answer 2

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.