2
$\begingroup$

I'm reading Why momentum really works and I have a problem with a piece of math in part related to gradient descent analysis.

Article's author analyzes the gradient descent on the simplest nontrivial problem: quadratic form with $A$ being symmetric and invertible: $$ f(w) = \frac{1}{2} w^TAw - b^Tw, \quad w \in \mathbb{R}^n. $$ The problem has optimal solution at $w^* = A^{-1}b$. We approach it though using gradient descent: $$ w^{k+1} = w^k - \alpha (Aw^k - b). $$ If we change the basis for $w^k = Qx^k + w^*$, where $Q$ is the matrix of $A$'s eigenvectors ($A = Q \Lambda Q^T$), we soon realize that: $$ w^k - w^* = Qx^k = \sum_i^n x_i^0 (1 - \alpha \lambda_i)^k q_i. $$ So we get the error at $k$-th iteration of gradient descent.

Then, in Decomposing the Error section, the author visualizes how error components contribute to the loss. To do so he writes the contributions of each eigenspace's error to the loss: $$ f(w^k) - f(w^*) = \sum(1 - \alpha \lambda_i)^{2k} \lambda_i [x_i^0]^2. $$ How did he get that? I tried using least squares, so I assumed $d=w^k - w^*$ and took the norm ($d^Td)$ but I did get: $$ \sum(1 - \alpha \lambda_i)^{2k} [x_i^0]^2 [q_i]^2. $$ Do I even approach it in the right way?

$\endgroup$
  • $\begingroup$ @whuber this question is not a duplication. The linked question explains $w^k - w^\star$ while this one asks about $f(w^k) - f(w^\star)$ $\endgroup$ – Kentzo Mar 29 at 23:05
  • $\begingroup$ the result can be derived as following: $f(w) - f(w^\star) = \\ \frac{1}{2} w^TAw - b^Tw - \frac{1}{2} [w^\star]^TAw^\star + b^Tw^\star) = \\ \frac{1}{2} (w^TAw - 2(Aw^\star)^Tw - [w^\star]^TAw^\star + 2(Aw^\star)^Tw^\star) = \\ \frac{1}{2} (w^TAw - 2[w^\star]^TAw + [w^\star]^TAw^\star) = \\ \frac{1}{2} (w^TA(w - w^\star) - [w^\star]^TA(w - w^\star)) = \\ \frac{1}{2} (w - w^\star)^TA(w - w^\star) = \\ \frac{1}{2} (w - w^\star)^TQ\Lambda Q^T(w - w^\star) = \\ \frac{1}{2} x^T \Lambda x = \\ \frac{1}{2} \sum_i^n (1-\alpha\lambda_i)^{2k}\lambda_i[x_i^0]^2$ $\endgroup$ – Kentzo Mar 29 at 23:51
  • $\begingroup$ Simpler answer: in the eigenbasis, $f$ is the sum of squares, QED. $\endgroup$ – whuber Mar 30 at 14:23

Your Answer

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

Browse other questions tagged or ask your own question.