Suppose I want to use fixed-sized gradient descent for a function like $y=x^2$ using the formula starting at some point (for example $x_0=4$):
$x_{i+1}=x_{i}-\alpha*f'_{x}(x_i)$
I am trying to figure out how I could determine what would be the smallest possible value of $\alpha$ so that my algorithm won't actually converge.
I was thinking that I should probably find some value $\delta>0$ so that starting from $x_0$ method will never come to a region $(-\delta; \delta)$. Is this correct approach? If so, how would I find one?
Thanks in advance.
Fix any $x_0$ in $\mathbb{R}\backslash\{0\}$ (if $x_0=0$ the sequence obtained is constant and it's trivial the method converges).
Then, $|x_{i+1}|=|x_i-\alpha\cdot f'(x_i)|=|x_i-\alpha\cdot 2x_i|=|x_i||1-2\alpha|$
If $c=|1-2\alpha|<1$ (which is equivalent to $0<\alpha<1$), then $|x_n|=c^n|x_0|\to 0$, so $x_n$ converges to $0$ (as desired, since it is the only minimum of $f$).
If $\alpha=1$, then $|x_{i+1}|=|x_i-\alpha\cdot 2x_i|=|-x_i|=|x_i|$, so the sequence oscillates between $x_0$ and $-x_0$, and thus does not converge.