Optimization problem of Stochastic gradient descent Fix initial data $x_0^i$ for $i=1,\dots n$ on the unit sphere ($\|x_0\|_2=1$). Define $H=\sum_{i,j=1}^n J_{ij}x_t^ix_t^j$ with $J_{ij}\sim^{iid} N(0, \frac{1}{n})$. $J$ is symmetric and $J=G^TDG$ where $D=diag(\lambda^1,\dots, \lambda^N)$.
If random output $x_t=[x_t^1,\dots, x_t^n]^T$ on the unit sphere are generated by the following ODE
$$
dx_t=-\nabla_{S^{n-1}}Hdt,
$$
where $\nabla_{S^{n-1}}$ is the gradient on the $n-$dimensional sphere and it is in the form of
$$
\nabla_{S^{n-1}}H=\nabla H-(\nabla H\cdot x_t)x_t.
$$
Let $v=[v^1,\dots, v^n]^T$ with $v^i\sim ^{iid} N(0, \frac{\lambda}{n})$ for some $\lambda>0$. Fix $\epsilon>0$, let $q:=\inf_{t}\{x_t\cdot v\ge\epsilon\}$.
My question is how to prove that for every $\epsilon>0$, $q\ge \log n$?

Since $H=\langle Jx_t,x_t\rangle$ and $\nabla H=2Jx_t$, then
$$
\nabla_{S^{n-1}}H=\nabla H-(\nabla H\cdot x_t)x_t=2Jx_t-2(x_t^TJx_t)x_t
$$
To simplify the above ODE, I can get
$$
dx_t=-2Jx_tdt+2(x_t^TJx_t)x_tdt
$$
So I can get
$$
h(t)\le h(0)e^{4\|J\|_{op}t}
$$
How to  get
$$
P(\log N \le T_\epsilon)\ge P(h(\log N)\le \epsilon)\ge P(h(0)e^{4\|J\|_{op}\log N}\le \epsilon) \ge ...
$$
 A: As it turns out, the ODE is a distraction, because $\log{\!(n)}$ is way too weak a bound.
First, compute the derivative of $v\cdot x_0$: $$\frac{1}{2}\frac{d}{dt}(v\cdot x)=(v\cdot x)H(x)-v\cdot Jx\leq2\|J\|_2\|v\|$$  The latter bound is, of course, extremely crude, but it turns out not to matter much.  Integrating ("Grönwall's inequality"), $$v\cdot x_t\leq v\cdot x_0+4\|J\|_2\|v\|t$$ and correspondingly $$\mathbb{P}[{q\geq\log{\!(n)}}]\geq\mathbb{P}[{\epsilon>v\cdot x_0+4\|J\|_2\|v\|\log{\!(n)}}]$$  Now I'm going to take a step back; that equation is more complicated than necessary.
First, we have a spherical symmetry in $\|v\|$ and the construction of $x_0$ that we can "spend" to simplify $v$.  In particular, let $e_0=(1,0,0,\dots,0)$; rotating $v$ and $x$ to match, it suffices to take $v=\frac{\lambda R}{n}e_0$ for some $R$ that is $\chi(n)$-distributed.
Second, let $x_0=(\cos{\theta},Y\sin{\theta})$; then $\cos{\theta}=e_1\cdot x_0$.  Also, $\theta$ has pdf $$\mathrm{pdf}(\theta)\,d\theta=\frac{\mathrm{area}(S^{n-2})}{\mathrm{area}(S^{n-1})}\sin^{n-2}{\!(\theta)}\,d\theta$$ just from marginalizing the distribution of $x_0$ over $y$.
Third, $$\|J\|_2=\sqrt{\sum_{i,j}{J_{i,j}^2}}$$ is also almost $\chi$-distributed: $n\|J\|_2\sim\chi(n^2)$, so let $A=n\|J\|_2$.
Then $$\mathbb{P}[{q\geq\log{\!(n)}}]\geq\mathbb{P}\left[{n\epsilon\geq\lambda R\left(\cos{\theta}+4\frac{A}{n}\log{\!(n)}\right)}\right]\tag{1}$$
Replacing $\epsilon$ with $\frac{\epsilon}{\lambda}$, we may take $\lambda=1$ w/oLoG.
Now since $R$, $\theta$, and $A$ are independent, \begin{align*}
\mathbb{E}\left[R\left(\cos{\theta}+4\frac{A}{n}\log{\!(n)}\right)\right]&=\left(\sqrt{2}\frac{\Gamma\left(\frac{n+1}{2}\right)}{\Gamma\left(\frac{n}{2}\right)}\right)
\left(0+4\frac{\log{\!(n)}}{n}\cdot\sqrt{2}\frac{\Gamma\left(\frac{n^2+1}{2}\right)}{\Gamma\left(\frac{n^2}{2}\right)}\right) \\
&\approx\sqrt{n}\left(\frac{4\log{\!(n)}}{n}\cdot n\right) \\
&\ll\epsilon n
\end{align*} where I have applied the "large-$n$" approximation that the mean of a $\chi(k)$ distribution is roughly $\sqrt{k}$; despite the name, this holds very well even at small $k$.  By Markov's inequality, $q\geq\log{\!(n)}$ holds wlp for any $n\gg\frac{2}{\sqrt{\epsilon}}$.
For smaller $n$, you'll need to sit down and estimate the integrals you get when you substitute the pdfs into the RHS of (1).  I wouldn't bother marginalizing over $\theta$; just estimate $\cos{\theta}\leq1$ and call it a day.  But dealing with the $\chi$ distributions is going to be annoying, so I'm going to leave it to you.
