Infimum of the inner product between the gradient of a least square loss and the direction Let $A\in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$. The gradient of a least square loss ($f(x)=\frac{1}{2}\|Ax-b\|^2$) is $A^{\top}(Ax-b)$. Is it possible to find a $\delta>0$ for every given $\epsilon>0$ such that the following holds for any $x \in \mathbb{R}^n$ when $x_0$ is given:
$$
\inf_{\|x-x_0\|\geq \epsilon} \frac{\langle x-x_0, A^{\top}(Ax-b) \rangle}{\|x-x_0\|^2 } \geq \delta
$$
My try
$$
\begin{aligned}
\frac{\langle x-x_0, A^{\top}(A(x-x_0+x_0)-b) \rangle}{\|x-x_0\|^2 } 
&=
\frac{\langle x-x_0, A^{\top}A(x-x_0) \rangle}{\|x-x_0\|^2 } 
+
\frac{\langle x-x_0, A^{\top}(Ax_0-b) \rangle}{\|x-x_0\|^2 }
\\
&\geq
\frac{\lambda_{\min}(A^{\top}A)\|x-x_0\|^2 }{\|x-x_0\|^2 }
+
\frac{\langle x-x_0, A^{\top}(Ax_0-b) \rangle}{\|x-x_0\|^2 } \\
&=
\lambda_{\min}(A^{\top}A)
\end{aligned}.
$$
Now there are two situations:

*

*$A$ is full columns rank. Hence, $(\lambda_{\min}(A^{\top}A)>0)$. Then, how do I know $\frac{\langle x-x_0, A^{\top}(Ax_0-b) \rangle}{\|x-x_0\|^2 } > \lambda_{\min}(A^{\top}A) $?


*$A$ is not full columns rank. Hence, $(\lambda_{\min}(A^{\top}A)=0)$. Then, how do I know $\frac{\langle x-x_0, A^{\top}(Ax_0-b) \rangle}{\|x-x_0\|^2 } > 0 $?
 A: TL;DR; Such $\delta$ exists if and only if

*

*$A$ is full column rank, i.e., $\lambda_{\min}(A^\top A) > 0$;

*$A^\top(Ax_0 - b) = 0$.


This means $x_0$ is the optimal solution that minimizes loss, and the Hessian of the loss function is positive definite. Therefore, any movement from $x_0$ would induce a positive gain, which is the operational meaning of the statement you want to prove.

The sufficiency is easy to see.
Your attempt is also very close to proving the necessity. Let's start with the first line you wrote:
$$
h(x) \triangleq \frac{\langle x-x_0, A^{\top}(A(x-x_0+x_0)-b) \rangle}{\|x-x_0\|^2 } 
=
\underbrace{\frac{\langle x-x_0, A^{\top}A(x-x_0) \rangle}{\|x-x_0\|^2 } }_{h_1(x)}
+
\underbrace{\frac{\langle x-x_0, A^{\top}(Ax_0-b) \rangle}{\|x-x_0\|^2 }}_{h_2(x)}
.
$$
Let $\displaystyle x' = x_0 - \epsilon \cdot \frac{A^\top (A x_0 - b)}{\|A^\top (A x_0 - b)\|}$.
Then we have
$\displaystyle
h_2(x') = -\frac{1}{\epsilon} \cdot \|A^\top (A x_0 - b)\|.
$
Therefore, when take $x$ to be $x'$, we have  $\|x' - x_0\| = \epsilon$ and
$$ h(x') = h_1(x') + h_2(x') \leq \lambda_\max(A^\top A) -\frac{1}{\epsilon} \cdot \|A^\top (A x_0 - b)\|.$$
Then, if $A^\top(Ax_0 - b) \neq 0$, we can always pick a small $\epsilon$ such that $h(x') < 0$.
When $A^\top(Ax_0 - b) = 0$, we have
$h(x) = h_1(x) \geq \lambda_{\min}(A^\top A),$ and the equality can be achieved.
Hence, to ensure that a positive $\delta$ exists, we must have $\lambda_{\min}(A^\top A) > 0$.
