1
$\begingroup$

Suppose that you want to estimate a local maximum of the real function $f(x,y,z)$ with gradient ascent. Given a starting point $(x_0, y_0, z_0)$, the approach is to compute the gradient at this point which is defined as follows:

$$\nabla f(x_0,y_0,z_0) = [\frac{\partial f}{\partial x}(x_0, y_0, z_0), \frac{\partial f}{\partial y}(x_0, y_0, z_0),\frac{\partial f}{\partial z}(x_0, y_0, z_0)]$$

A step towards the gradient is assumed to increase the value of function, and similar steps are repeated until convergence. I will use the following notation for simplicity:

$$\nabla f(x_0,y_0,z_0) =[dx_0,dy_0,dz_0]$$

Now, my interpretation is that the gradient contains three partial derivatives of the function $f$ at point $(x_0,y_0,z_0)$ i.e. the rate of change of the function when moving along one of the three dimensions. Thus, I understand why the following are probably true for small learning rate $\lambda$:

$$f(x_0+\lambda dx,y_0,z_0) > f(x_0,y_0,z_0)$$
$$f(x_0,y_0 + \lambda dy_0,z_0) > f(x_0,y_0,z_0)$$
$$f(x_0,y_0,z_0+ \lambda dz_0) > f(x_0,y_0,z_0)$$

However, gradient ascent does not make single-dimensional steps towards a partial derivative, but moves towards the directional derivative $(dx_0,dy_0,dz_0)$. So, are there any reasons (theoretical or practical) to expect that the following is true?

$$f(x_0+\lambda dx_0,y_0 + \lambda dy_0,z_0 + \lambda dz_0) > f(x_0,y_0,z_0)$$

For instance, is it possible infer that the directional derivative is positive given that the partial derivatives are positive?

$\endgroup$
1
  • $\begingroup$ This holds if the function in question is differentiable (in the multivariate sense, which is rather more nuanced than the univariate case). $\endgroup$
    – Ben Reiniger
    Dec 19, 2022 at 1:43

1 Answer 1

2
$\begingroup$

Yes. Write down a first-order Taylor series expansion for $f$, at $(x_0,y_0,z_0)$. (Equivalently, write down an approximation for $f$ as a linear function.) The gradient lets you find the coefficients of this Taylor series expansion. Call it $\hat{f}$. We expect that $\hat{f}$ will be a good approximation to $f$ near $(x_0,y_0,z_0)$. Now, find the maximum of $\hat{f}$ in the vicinity of $(x_0,y_0,z_0)$, specifically, in the $L_2$ ball $\{(x,y,z) \mid \|(x,y,z) - (x_0,y_0,z_0)\|_2 \le \lambda\}$. Since $\hat{f}$ is linear, it is possible to analytically write down an expression for this maximum, in terms of the coefficients of $\hat{f}$. If you do the write down that expression (in terms of the gradient), it turns out that the maximum is exactly where one step of gradient ascent moves to, using step size $\lambda$.

So, now we can interpret what gradient ascent is doing. It is finding a linear approximation $\hat{f}$ for $f$, that will presumably be a decent approximation for $f$ near $(x_0,y_0,z_0)$ (but might be a bad one far away). Then, it finds the maximum of $\hat{f}$, subject to the constraint that you can't move too far away from $(x_0,y_0,z_0)$ (you have to stay within the region where $\hat{f}$ is a good approximation to $f$). This then is likely to be a good candidate for a new point that increases the value of $f$: in some sense it is the best candidate one can come up with for where to move to next, given the value of $f$ and the gradient of $f$ at $(x_0,y_0,z_0)$.

So, from this perspective, gradient ascent is doing something very reasonable. If you don't know how to optimize $f$, form a good approximation to $\hat{f}$ as a function that you do know how to optimize, optimize the approximation, and repeat iteratively.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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