In non-convex optimization, the argument $x \in \mathbb R^p$ is said to obtian an $\epsilon$-accurate solution if
$$\|\nabla f(x)\|^2\leq \epsilon$$
However, with the increase of the dimension $p$, the accuracy $\epsilon$ is invariant. It seems this convergence criterion becomes stricter as $p$ increases, since the number of terms in $\nabla f(x)$ increases linearly with $p$. Is my understanding correct?
Typically we can use gradient descent to solve the problem and the corresponding convergence rate is $\mathcal O(1/\epsilon)$.
If we set $\epsilon = \mathcal O(p)$ such that the convergence criterion won't be stricter for larger $p$, then the resulting convergence rate is actually a function of $p$, which is wierd.