4
$\begingroup$

I am reading paper [1] by C. Josz regarding the global convergence of the gradient method. The main result is the following:

$\textbf{Theorem}$: For a definable differentiable function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ with locally Lipschitz gradients, the following statements are equivalent:

  1. For all initial conditions $x_0 \in \mathbb{R}$, there exist $\bar{\alpha} > 0$ and $c > 0$ such that the sequence $(x_k)_{k \geq 0}$ defined by $x_{k+1} = x_k - \alpha_k x_k $, where $\alpha_k $ are arbitrary in $[0, \bar{\alpha}]$ satisfies $\| x_k \| \leq c, \forall k \geq 0$.
  2. For all $ T \in (0, \infty]$ and differentiable solution of the gradient flow $x^\prime(t) = -\nabla f(x(t)), \forall t \in (0, T)$, there exists $c > 0$ such that the solution is bounded, i.e. $\| x(t) \| \leq c, \forall t \in [0, T)$.
  3. For any $X \subset \mathbb{R}^n$ bounded, there exist $\bar{\alpha} > 0$ and $c > 0$ such that for any $x_0 \in X$, the sequence $(x_k)_{k \geq 0}$ (defined as in 1.) satisfies $\sum_{k=1}^\infty \| x_{k+1} - x_k \| \leq c $.

In order to prove this theorem, the following Lemma is used:

$\textbf{Lemma}$: If a locally Lipschitz definable function has bounded continuous gradient trajectories, then continuous subgradient trajectories initialized in a bounded set have uniformly bounded lengths.

While I do understand the proofs, I would like to convince myself of the necessity of o-minimality of $f$ for obtaining the conclusions of the theorem by finding some counter-examples of the implications when $f$ is not definable. However, I have trouble coming up with such counter-examples.

For example, I agree that 3. is stronger than 1. and there is no reason why the implication 1. $\implies $ 3. would be generally true. I think that the existence of a counter-example might be shown using a strategy similar to the one from [2], namely design a $C^k$ convex function by specifying some of its level sets. I think that maybe one could design a convex function such that the gradient descent iterates are bounded, but the lengths of the gradient descent paths are unbounded (this could be achieved with a function for which $(x_k)_{k \geq 0}$ has more than one accumulation point; while boundedness of the iterates might be achieved through the specification of some level sets of the function). But I'm not familiar enough with the techniques used in [2] in order to judge if this would indeed work.

As another example, for 2. $ \implies $ 1., I cannot imagine how all solutions of gradient flow would be bounded and yet gradient descent with however small step size might have unbounded iterates. Intuitively, I would expect this to be true in general.

When it comes to the Lemma, however, I have a clear counter-example: if one looks at the Mexican hat function [3] (which is $C^\infty$, but not analytic; and non-definable, I would assume), then continuous gradient trajectories remain bounded, but the lengths of the trajectories can be unbounded, since the solution might end up rotating around the unit circle infinitely.

Any thoughts or references are appreciated! Thanks!

[1] Global convergence of the gradient method for functions definable in o-minimal structures by C. Josz

[2] Curiosities and counterexamples in smooth convex optimization by J. Bolte and E. Pauwels

[3] Convergence of the Iterates of Descent Methods for Analytic Cost Functions by PA. Absil, R. Mahony and B. Andrews

$\endgroup$
1
  • $\begingroup$ When you quote someone's work, please consider using > $\endgroup$ Jun 30, 2023 at 18:09

1 Answer 1

1
$\begingroup$

Regarding $1\Longrightarrow 3$, by [1,Corollary 3.9] the discrete trajectories of convex functions have finite length. So I don't think you can find a counterexample among convex functions.

[1] Böhm, A., Daniilidis, A.: Ubiquitous algorithms in convex optimization generate self-contracted sequences. J. Conv. Anal. 29, 119–128 (2022)

Regarding $1\Longrightarrow 2$, it is not necessary for $f$ to be definable. It suffices for it be $C^{1,1}_\mathrm{loc}$ (i.e., differentiable with locally Lipschitz gradient).

$\endgroup$

Your Answer

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