1
$\begingroup$

I would like to study the convergence of the gradient descent method applied to the function

$$f(x)=|x-1|^3$$

In order to do that, I was thinking about using the following theorem:

Assume that $f : \mathbb{R}^n \to \mathbb{R}$ is convex and differentiable. Suppose the gradient of $f$ is Lipschitz continuous with constant $L>0$, meaning

$$\| \nabla f(x) - \nabla f(y) \| \leq L \| x-y \| $$

for any $x, y \in \mathbb{R}^n$. Then, the gradient descent with fixed step size $t \leq \frac{1}{L}$ satisfies

$$f(x^{(k)})-f(x^{*}) \leq \frac{\|x^{(0)}-x^{*}\|^2}{2 t k}$$

that is the gradient descent has convergence rate $O(\frac{1}{k})$.

My problem is that the gradient of the function I am studying is not Lipschitz, unless we put ourselves on a bounded interval, say $(1, a)$.

Could you help me? Any insight is very much appreciated :)

$\endgroup$
  • $\begingroup$ have you tried some value for $t$ to see if you can bind the distance from the optimum? $\endgroup$ – LinAlg Oct 28 '16 at 0:43
  • $\begingroup$ hint : take the set $\{ x : f(x) \leq f(x_0) + 1 \}$. This is a compact set, and your function has a lipschitz gradient on this set. You can prove that with the size of the step being small enough, the function will not increase, so you will remain in your compact set. $\endgroup$ – sjm.majewski Oct 29 '16 at 0:43
  • $\begingroup$ What do you mean by "binding the distance from the optimum"? If the assumptions of the theorem do not hold, the last equation does not hold either... $\endgroup$ – Fred G. Nov 1 '16 at 10:34
  • $\begingroup$ Regarding the compact set, who is $x_0$? The initial guess? $\endgroup$ – Fred G. Nov 1 '16 at 10:35

Your Answer

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

Browse other questions tagged or ask your own question.