0
$\begingroup$

I understand that gradient descent comes from the (quite natural) idea that we might want to choose our next weight vector ($w^{t+1}$) as

$$w^{t+1} = \arg \min_w \frac{1}{2} \|w-w^t\|^{2} + \eta f(w^t) + \langle w-w^t, \nabla f(w^t) \rangle$$

because the approximation $$f(w) \approx f(w^t)~+ \langle w-w^t,\nabla f(w^t) \rangle$$ gets worse as $\|w-w^t\|$ grows.

But, how do I get from the first expression above to the gradient descent algorithm: $$w^{t+1} = w^t + \nabla f(w^t)?$$ A step-by-step explanation would be much appreciated.

$\endgroup$
1
  • $\begingroup$ Why is the term $\eta f(w^t)$ in the objective function? $\endgroup$ Commented Mar 9, 2019 at 16:48

1 Answer 1

0
$\begingroup$

You can motivate gradient descent as both minimization of a quadratic approximation of the objective or a linear function with a penalty for moving away from the current point. Here's what you are minimizing actually: $$x_{k+1} = \arg\min_{x\in \mathbb{R}^n}{f(x_{k}) + \nabla f(x_k) \cdot (x-x_k) + \frac{1}{2\tau}||x-x_k||^2}$$ $$x_{k+1} = \arg\min_{x\in \mathbb{R}^n}{\nabla f(x_k) \cdot (x-x_k) + \frac{1}{2\tau}||x-x_k||^2}$$ $$\nabla f(x_k) + \frac{1}{\tau}(x_{k+1}-x_k) = 0$$ $$x_{k+1} = x_k - \tau \nabla f(x_k)$$ The second interpretation follows from considering the function $f_{x_k}(x) = f(x_k) + \nabla f(x_k) \cdot (x-x_k)$ which is obviously linear, and adding the penalty you get $f_{x_k}^{\tau}(x) = f_{x_k}(x) + \frac{1}{2\tau}||x-x_k||^2$ which is a $\tau^{-1}$ strongly convex function and thus has a unique minimizer $x_{k+1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .