Illustration of functional gradient descent

Question

I'm trying to understand boosting as gradient descent (GD) in functional space. I've followed the argument in the classic paper on the subject, but would characterize my understanding as tenuous at best. Proceeding by the way of analogy, I'll make following statements.

Regular GD aims to locate optimal points of scalar-valued function. Functional GD aims to find functions (over the entire domain of definition). In theory, regular GD is a numerical substitute for the calculus-based procedure of setting the derivative to zeros and solving the resulting equation (of course practical problems aren't easily solvable this way). Equivalent direct procedure in functional space is to find functional derivative and solve the resulting Euler-Lagrange equation. That is how we solve the isoperimetric problem, Brachistochrone problem, max entropy problems etc.

To further my understanding of functional GD, I want to solve a simple calculus of variations problem using functional GD. Say, I want to find a 2D curve that minimizes the distance between two points. I know how to solve this using Euler Lagrange. I want to reproduce this solution numerically by seeing a randomly picked function (obeying constraints) evolve toward a straight line.

Is there a text, a tutorial, arXiv document, blog, a video or any other document that provides a gentle introduction to functional GD using simple examples? My searches yielded some student-scribed lecture notes, but they didnt help much beyond clarifying the notation in the paper.

Can someone help set up a functional GD for a simple problem? I'm not asking for explicit code, as I'm quite happy to write that myself.

Answer 1

Functional Gradient Descent

Functional Gradient Descent - Part 1 and Part 2 will give a brief introduction and theoretical illustration. Functional Gradient Descent was introduced in the NIPS publication Boosting Algorithms as Gradient Descent by Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean in the year 2000.

We are all familiar with gradient descent for linear functions $f(x) = w^Tx$. Once we define a loss $L$, gradient descent does the following update steps ($η$ is a parameter called the learning rate.

$w \rightarrow w - \eta \nabla L(w)$

where we move around in the space of weights. An example of a loss of $L$ is:

$L(w) = \sum_{i=1}^n(y_i - w^Tx_i)^2 + \lambda\lVert w \rVert ^2$

where the first term (the $‘L2’$ term) measures how close $f(x)$ is to $y$, while the second term (the ‘regularization’ term) accounts for the ‘complexity’ of the learned function $f$.

Suppose we wanted to extend $L$ to beyond linear functions $f$. We want to minimize something like:

$L(f) = \sum_{i=1}^n(y_i - f(x_i))^2 + \lambda\lVert f \rVert ^2$

where $\lVert f \rVert ^2$ again serves as a regularization term, and we have updates of the form:

$f \rightarrow f - \eta \nabla L(f)$

where we move around in the space of functions, not weights!

Turns out, this is completely possible! And goes by the name of ‘functional’ gradient descent or gradient descent in function space.

In general, you can parametrize any function in a number of ways, each parametrization gives rise to different steps (and different functions at each step) in gradient descent.

The advantage is that some loss functions that are non-convex when parametrized, can be convex in the function space: this means functional gradient descent can actually converge to global minima when ‘ordinary’ gradient descent could possibly get stuck at local minima or saddle points.

Illustration Example

Code

For more

• Why functional gradient descent can be useful,
• What it means to do functional gradient descent, and,
• How we can do functional gradient descent, with an example.

Visit