3
$\begingroup$

The question is very simple which is to calculate the gradient descent step of a quadratic function.

However, the given answer is very confusing. How can we directly get the equation (yellow part in the picture given below) without any further information?

link_to_the_problem_picture

$\endgroup$
  • $\begingroup$ The yellow does not make sense to me. It's not even correct for $k=0$. I think it should be $\begin{bmatrix} (1-t)^k \gamma \\ (1-\gamma t)^k\end{bmatrix}$. $\endgroup$ – kccu Oct 9 at 16:43
2
$\begingroup$

The question is why $$ \begin{bmatrix}x_1^{(k)}\\x_2^{(k)}\end{bmatrix}= \left(\frac{\gamma-1}{\gamma+1}\right)^k\begin{bmatrix}\gamma\\(-1)^k\end{bmatrix}. $$ It is because for all previous steps the step $t$ is chosen to be optimal (from the exact line search). For example, the first step for the initial point $(\gamma,1)$: $$ \begin{bmatrix}x_1^{(1)}\\x_2^{(1)}\end{bmatrix}= \begin{bmatrix}(1-t)\gamma\\1-\gamma t\end{bmatrix}. $$ To pick the optimal $t$, we need to minimise $$ \frac12(x_1^2+\gamma x_2^2)=\frac12(1-t)^2\gamma^2+\frac12\gamma(1-\gamma t)^2. $$ Differentiating w.r.t. $t$ and setting the derivative to zero gives $$ t_{opt}=\frac{2}{\gamma+1}, \qquad 1-t_{opt}=\frac{\gamma-1}{\gamma+1},\qquad 1-\gamma t_{opt}=-\frac{\gamma-1}{\gamma+1}. $$ Doing that for all other iterations you get the yellow formula.

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