# Coding up a toy model for gradient-descent -- what step size to choose?

I'm coding up a simple model for gradient-descent, and using it to minimize some simple, deterministic functions.

What step size could I choose that's simple enough for me to get started with?

Should I choose a constant step size of .1? .001? 1? 1.5?

On Wikipedia, it gives a model for this step size, called the Barzilai–Borwein method, but this is too complicated for me at the moment.

Besides a constant step size, is there an easy variable-step size I could implement and play with?

Thanks,

Suppose you want to minimize

$$\Phi(x)=\frac{1}{2}||Ax-b||^2$$

$$\frac{\partial \Phi}{\partial x} = A^T(Ax-b)$$

The step size to guarantee convergence is

$$\alpha=||A^TA||^{-1}$$

Why? The direct solution to the problem is:

$$x_{opt}=(A^TA)^{-1}A^Tb$$ This can be achieved iteratively if we look at the update on the estimate $$x_k$$. Suppose we start with $$x_0=0$$, then

$$x_1 = \alpha A^Tb$$ subsequent steps are $$x_{k+1}=x_k-\alpha A^T(Ax_k-b)$$ We can therefore write $$x_{k+1}=\alpha\left(\sum_{n=0}^k(I-\alpha A^TA)^n\right)A^Tb$$ Using the singular value decomposition $$A=USV^T$$, we can rewrite the equation as $$x_{k+1}=\alpha V\left(\sum_{n=0}^k(I-\alpha S^2)^n\right)SU^Tb$$ The sum $$\sum_{n=0}^k(I-\alpha S^2)^n$$ Is a geometric series of the form $$\sum_{n=0}^k x^n$$, which we can rewrite as as in the following form as long as $$||x||<1$$ to guarantee convergence: $$\sum_{n=0}^\infty x^n=\frac{1}{1-x}$$ We thus can rewrite:

\begin{align} x_{opt}&= \alpha V\left(\sum_{n=0}^\infty(I-\alpha S^2)^n\right)SU^Tb\\ &=\alpha V((\alpha S^2)^{-1})SU^Tb\\ &=VS^{-1}U^Tb \end{align} This expression is the same as the one for $$x_{opt}$$ by noting that

\begin{align} A^TAx&=A^Tb\\ VSU^TUSV^Tx&=VSU^Tb\\ \Rightarrow x &=VS^{-1}U^Tb \end{align}

The only condition we need to ensure is that the singular values in $$S$$ are rescaled for the sum $$\sum_{n=0}^k(I-\alpha S^2)^n$$, such that the sum is convergent for $$k\rightarrow\infty$$. This is why we use the step size

$$\alpha=||A^TA||^{-1}$$ Because it rescales the largest singular value in $$S$$ to be equal to $$1$$, which means all other singular values are above $$0$$ and below $$1$$. This way, the geometric series will converge.

I hope I didn't do any mistake here, but if anyone finds something, feel free to correct me.

"Besides a constant step size, is there an easy variable-step size I could implement and play with?"

An easy way to implement some variable step size would be the following algorithm: Consider your cost function $$\Phi(x)$$ you would like to minimize.

• Choose an initial step size $$\alpha$$
• Choose a starting point $$x_0$$
• Compute the value of the cost function $$c_0=\Phi(x_0)$$
• Update $$x$$ via the step $$x_{k+1}=x_k-\alpha\frac{\partial \Phi}{\partial x}$$
• Compute the value at the new position $$c_{k+1}=\Phi(x_{k+1})$$
• Compare the values $$c_k$$ and $$c_{k+1}$$:
• If $$c_k Then
• Redo the iteration with $$x_k$$ and decreased $$\alpha$$, e.g. $$\alpha\rightarrow 0.5\alpha$$
• Else
• Use $$x_{k+1}$$ for the next iteration and increase the step size $$\alpha$$, e.g. $$\alpha\rightarrow 1.2\alpha$$
• Stop after some stopping criterion.