# Getting to the gradient descent algorithm

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.

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

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