3
$\begingroup$

It seems that most proofs of convergence for gradient descent algorithms rely on strong conditions on the first and second derivatives of the function, for instance that $$|f''(x)| \leq K$$ over the whole domain of the function. My question is are there results for gradient descent type algorithms when we can only say something like $$|f^{(n)}(x)| \leq K$$ for some $n > 2$?

Convergence in this case can refer to several different sequences, i.e convergence of the parameters $x_{k}$, of function values $f(x_{k})$ or derivatives $f'(x_{k})$

$\endgroup$
  • $\begingroup$ Would you want the absolute value of the second derivative to be bounded above? $\endgroup$ – Baby Dragon Jul 31 '14 at 1:35
  • $\begingroup$ That's the usual assumption I guess. I edited to reflect that, but info on either case would be of interest to me. $\endgroup$ – ttb Jul 31 '14 at 2:02
  • $\begingroup$ I did not know of that is the usual assumption or not. But it seems like the descent can go very wrong otherwise, but I am not sure (that is why I asked). More generally, I suppose that in higher dimensions, one would want the absolute value of the determinate of the hessian to be bounded above. $\endgroup$ – Baby Dragon Jul 31 '14 at 3:09
1
$\begingroup$

Likely, the reason that these proofs are bounding the second derivative is that proofs of convergence for Newton's method require that the derivative of the function be Lipschitz continuous. An everywhere differentiable function $f:\mathbb{R}\rightarrow\mathbb{R}$ is Lipschitz continuous if and only if its derivative is bounded. Basically, if we need our derivative to be Lipschitz, we can guarantee that by bounding the second derivative.

Anyway, Lipschitz continuity states $$ |f(x)-f(y)| \leq \gamma |x - y| $$ in a single dimension. From this, we can prove $$ |f(y)-f(x)-f^\prime(x)(y-x)|\leq\frac{\gamma(y-x)^2}{2} $$ Which is really what we need for proving that Newton's method converges since it bounds how good the affine approximation $f(x)+f^\prime(x)(y-x)$ is to $f(y)$. Newton's method is really just a series of these affine approximations. In any case, the best place to see this and how the proof works is Dennis and Schnabel's book "Numerical Methods for Unconstrained Optimization and Nonlinear Equations". They have both the proof for Newton's method in a single dimension as well as multiple. Especially when going to multiple dimensions, it's much easier to work with Lipschitz continuity. Start on page 21, though, for the single dimensional case.

As a side note, if we use a line-search method, the Lipschitz continuity condition comes up again. Really, it all comes down to guaranteeing that our affine approximations are good enough. To see how it manifests, Nocedal and Wright's book "Numerical Optimization" runs through the proof on page 38.

$\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.