\documentclass{article} \usepackage{me} \usepackage{amssymb} \usepackage{amsfonts} \setlength{\parindent}{0pt} $\newcommand\vol{{\mbox{vol}}}$ $\newcommand{\RR}{\mathbb{R}}$

Lecture 16: Gradient Descent

Unconstrained Minimization

Our focus today: Unconstrained minimization problem: given a real-valued function $f$ over $\RR^n$, find its minimum $x^*$ (assuming it exists). That is, solve the problem \[ x^*=\arg\min_{x\in \RR^n} f(x). \]

Gradient Descent

How to solve an unconstrained minimization problem?

Question: What is the direction of the steepest decrease of $f$?

Resulting algorithm: Gradient descent method:

Question: What should $\eta$ be?

Remaining issue: What if $\|\nabla f(x^k)\|=0$ (or is just very small)?

Convergence Analysis

How fast does gradient descent converge?

Newton's Method

Newton's Method as a Variant of Gradient Descent