3
$\begingroup$

I've been following the CS 229 lecture videos for machine learning, and in lecture 4 (~14:00), Ng explains Newton's Method for optimization to maximize an objective function ($f$), but doesn't clearly explain the derivation of the higher dimension generalization:

$$ \theta := H^{-1} \nabla_{\theta}\ f(\theta) $$

I've read that the Hessian matrix ($H$) is a multiple dimension generalization of the second order derivative, but other than that I'm not sure I understand the formulation of the Hessian or why we multiply by its inverse; perhaps I need to brush up on linear algebra.

What's an intuitive explanation of the Hessian and its inverse in this formula?

$\endgroup$
3
$\begingroup$

Overview

Suppose we want to minimize an objective function $f$ that maps a parameter vector $x \in \mathbb{R}^d$ to a scalar value. The idea behind Newton's method is to locally approximate $f$ with a quadratic function, then solve for the point that minimizes this approximation. We then jump to this new point, where we build a new approximation, and repeat the process until convergence.

Local quadratic approximation

Say our current location in parameter space is the vector $x_0$. We can approximate $f$ in the vicinity of $x_0$ using the second order Taylor series expansion:

$$f(x) \approx f_T(x) = f(x_0) + (x-x_0)^T \nabla f(x_0) + \frac{1}{2}(x-x_0)^T H(x_0) (x-x_0)$$

This is a quadratic function whose value at $x_0$, as well as its first and second partial derivatives, match those of $f$. $\nabla f(x_0)$ is the gradient of $f$ evaluated at $x_0$. This is a vector containing the partial derivatives of $f$, and is analogous to the derivative for functions of single variables. Similarly, $H(x_0)$ is the Hessian of $f$ evaluated at $x_0$. It's a matrix containing second partial derivatives of $f$, and is analogous to the second derivative for functions of single variables.

$$\nabla f(x_0) = \left [ \matrix{ \frac{\partial f}{\partial x_1} (x_0) \\ \vdots \\ \frac{\partial f}{\partial x_d} (x_0) \\ } \right ] \quad H(x_0) = \left [ \matrix{ \frac{\partial^2 f}{\partial x_1^2} (x_0) & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_d} (x_0) \\ \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_d \partial x_1} (x_0) & \cdots & \frac{\partial^2 f}{\partial x_d^2} (x_0) \\ } \right ]$$

Minimizing the local approximation

Given the local approximation $f_T$ at the current point $x_0$, we want to find a new point $x$ that minimizes $f_T$. This can be done in closed form by taking the gradient of $f_T$ with respect to $x$, setting it to zero, then solving for $x$.

The gradient of $f_T$ can be found by differentiating the expression above (keeping in mind that $\nabla f(x_0)$ is just a fixed vector and $H(x_0)$ is just a fixed matrix):

$$\nabla f_T(x) = \nabla f(x_0) + H(x_0) (x - x_0)$$

Setting it to zero, we have:

$$H(x_0) (x - x_0) = -\nabla f(x_0)$$

We need to isolate $x$, so multiply both sides by the inverse of the Hessian, then move $x_0$ to the righthand side:

$$x = x_0 - \Big( H(x_0) \Big)^{-1} \nabla f(x_0)$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.