The Biggest Step Size with Guaranteed Convergence for Constant Step Size Gradient Descent of a Convex Function with Lipschitz Continuous Gradient

Given a convex function $$f \left( x \right) : \mathbb{R}^{n} \to \mathbb{R}$$ with $$L$$ - Lipschitz Continuous Gradient. Namely:

$${\left\| \nabla f \left( x \right) - \nabla f \left( y \right) \right\|}_{2} \leq L {\left\| x - y \right\|}_{2}$$

What is the largest constant step size, $$\alpha$$, one could use in Gradient Descent to minimize the function?
In most literature I see $$\alpha = \frac{1}{L}$$ yet in some other cases I see $$\alpha = \frac{2}{L}$$. Which one is right?

Also, for the case $$f \left( x \right) = \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2}$$ what is $$L$$? Is it the largest Singular Value of $$A$$?

Let $$y$$ be the one step of gradient descent from $$x$$, i.e., $$y = x-\alpha \nabla f(x)$$. Since $$f$$ is Lipschitz gradient function with constant $$L$$, we have \begin{aligned} f(y) - f(x) & \leq \langle \nabla f(x), y-x \rangle + \frac{L}{2}\|y-x\|^2 \\ &= -\alpha \|\nabla f(x)\|^2 + \frac{L}{2}\alpha^2\|\nabla f(x)\|^2. \end{aligned} To guarantee the sufficient decreasing, we need $$$$\frac{L}{2}\alpha^2 - \alpha \leq 0 \Rightarrow \alpha \leq \frac{2}{L}.$$$$ In addition, One can easily find the optimal step size will be $$\frac{1}{L}$$. So if I remember, the step size proving the convergence is $$\frac{2}{L}$$(c.f. Boris T. Polyak - Introduction to Optimization, Page 21), and the optimal choice is $$\frac{1}{L}$$(c.f. Yurii Nesterov - Introductory Lectures on Convex Programming, Page 29).
However, even though the gradient descent can converge when $$0 < \alpha < \frac{2}{L}$$, the convergence rate $$O(1/k)$$ only could be guaranteed for $$0 < \alpha < \frac{1}{L}$$ (c.f.Gradient Descent: Convergence Analysis, Theorem 6.1).
For $$f(x) = \frac{1}{2}\|Ax-b\|^2$$, thus $$$$\|\nabla f(x) - \nabla f(y)\| = \|A^TA(x-y)\| \leq \|A^TA\| \|x-y\|.$$$$ The inequality is induced by operator norm, i.e., the largest eigenvalue of $$A^TA$$, also the largest singular value of $$A$$.
• While I like your answer, I am afraid it only proves that the method converges for all $0<\alpha<\frac{L}{2}$. This is slightly less than showing that $\alpha=\frac{L}{2}$ is the highest possible constant step. Or am I missing something? Apr 13, 2020 at 13:15
• @Ze-NanLi What I was wondering was, whether $\alpha=\frac{2}{L}$ is really the highest possible constant step. But Polyak on page 23 gives an example of a function for which the method does not converge with $\alpha=\frac{2}{L}$, which means that you were right. Apr 20, 2020 at 10:07