CPSC 340 Gradient Descent

Gradient Descent

• starts with a guess $w_0$
• use the gradient $\nabla f(w^0)$ to generate a better $w^1$
• …
• the limit of $w^t$ goes to $\infty$ has $\nabla f(w^t) = 0$

It converges to a global optimum if f is convex. More details Gradient Descent

Gradient Descent for Least Squares

$f(w) = \frac{1}{2} ||Xw-y||^2$

$\nabla f(w) = X^T(Xw-y)$

$w^{t+1} = w^t - \alpha^tX^T(Xw-y)$

Cost of each iteration is $O(nd)$, t iterations.

How to Know a Convex Function

• Previous
  CPSC340 Outlier Detection
• Next
  CPSC 340 Linear Regression