Gradient Descent and Learning Rate

Question

Assuming that our function is convex and only has a single minimum. Would gradient descent ever hit the minimum if the learning rate was extremely small? Or would it bounce back and forth without ever hitting the minimum. What would the case be if the function contained two minimums? One that is the global and the other being the local.

Answer 1

Consider the convex function $f(x) = |x|$. Then gradient descent would bounce back and forth forever: since the gradient is always either $+1$ or $-1$, with learning rate $\lambda$ and if $x\in(0, \lambda)$, then $x$ would alternate between $x$ and $x-\lambda$.

If, as another example, $f(x) = x^2$, then gradient descent would converge to the minimum without attaining it. But you would not observe it because of the finite resolution of floats.

Note that there are various extensions of ordinary gradient descent, from more basic ones with decreasing learning rates up to more sophisticated ones like Adam or Nadam.

If there are several local minima, gradient descent can be caught in local minima without reaching the global one. But then your presumption of convexity would be violated.

Answer 2

With arbitrary precision numbers, we can't expect that the $k$th iterate of gradient descent will ever exactly equal the optimal value $f(x^*)$. In practice on a computer with floating-point numbers, we may actually get exact convergence.

In terms of the rate of convergence, there are two theorems that can be generally applied in common cases.

Fixed step size and convex, $L$-Lipschitz gradient function

The first theorem says that if we have a convex function with $L$-Lipschitz-continuous gradient, we get convergence if the step size is less than $1/L$, and the rate of convergence is $\mathcal{O}(1/k)$ for $k$ iterates.

Formally, given:

• A function $f: \mathbb{R}^n \to \mathbb{R}$ which is convex, differentiable and with $L$-Lipschitz-continuous gradient, so $\|\nabla f(x)-\nabla f(y)\|_{2} \leq L\|x-y\|_{2}$ for all $x$, $y$.
• We do $k$ steps of gradient descent with fixed step size $t \leq 1/L$ to obtain a point $x^k$.

Then the optimality gap satisfies

$$f\left(x^{k}\right)-f\left(x^{*}\right) \leq \frac{\left\|x^{(0)}-x^{*}\right\|_{2}^{2}}{2 t k}$$

As an example, the quadratic function $f(x) = x^2$ has a 2-Lipschitz gradient, so a fixed step size $t \leq \frac12$ will converge.

Convex $L$-Lipschitz non-differentiable function

Gradient descent is not a well-defined algorithm on a non-differentiable function, since it's not clear what to do if we have an iterate where $f$ doesn't have a gradient. A useful extension of gradient descent is subgradient descent, where we pick a subgradient if the function doesn't have a gradient at that point.

The second theorem says that for a convex but non-differentiable function $f$ with the function itself having Lipschitz constant $G$, i.e. $\|f(x)-f(y)\|_{2} \leq G\|x-y\|_{2}$ for all $x$, $y$, then doing subgradient descent with fixed step size $t$ will result in convergence to a final iterate with

$$\lim _{k \rightarrow \infty} f\left(x^{k}\right) \leq f\left(x^{*}\right)+G^{2} \frac{t}{2}$$

In other words, a fixed step size will not necessarily result in convergence in the limit.

However, if we pick a step size $t_i$ that decreases at the right rate, so that $\sum_{k=1}^\infty t_i^2 \leq \infty$ and $\sum_{k=1}^\infty t_i = \infty$, we do indeed still get convergence with

$$\lim _{k \rightarrow+\infty} f\left(x^{k}\right)=f\left(x^{*}\right)$$