1
$\begingroup$

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,

$\endgroup$
3
$\begingroup$

Suppose you want to minimize

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

The gradient is

$$\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.

$\endgroup$
0
1
$\begingroup$

Adding another answer to the second part of your question:

"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<c_{k+1}$ 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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.