# Gradient descent via polynomial approximation

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})$

• Would you want the absolute value of the second derivative to be bounded above? – Baby Dragon Jul 31 '14 at 1:35
• That's the usual assumption I guess. I edited to reflect that, but info on either case would be of interest to me. – ttb Jul 31 '14 at 2:02
• 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. – Baby Dragon Jul 31 '14 at 3:09

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.