1
$\begingroup$

I recently came across the notion of an accumulation point as a result of a certain gradient descent variation. The following definition was found:

An accumulation point $P$ is such that there are an infinite number of terms of the sequence in any neighborhood of $P$.

I'm not sure if I understand the above definition correctly. Since the gradient of the function at this point needs not to be zero ($0$), but is zero at the stationary point, could one state that a stationary point is an accumulation point if it is a result of an iterative approach of minimization of a function $f(\cdot)$, satisfying $$f(P)-f(P_1)=0,$$where $P_1$ is the next iterate?

Note that the notion of oscillation adds to the confusion. Namely, it may not hold that $P=P_1$, and the minimization approach switches between the two (if the termination is determined by relative change of $P$ ). How could the accumulation point be defined in this case? (the last is inspired by the cluster point definition I came across; so, a connection between the three would be appreciated: accumulation point, oscillation, cluster point)

Since it is stated here (Theorem 8.5) that a convergent sequence has one and only one limit point (accumulation point), what could be induced from the case with oscillations? In other words, could one state that the sequence is actually non-convergent?

$\endgroup$
5
$\begingroup$

accumulation point = cluster point.

If a sequence oscillates between increasingly narrow neighborhoods of two different points, such as the sequence $x_n=\frac{(-1)^nn}{n+1}$, both points are accumulation points of the sequence.

In optimization, a local solver is usually reliable in practice when it is provable that each accumulation point of the sequence of iterates is a stationary point. In finite precision arithmetic, the gradient will almost never be zero because of rounding errors made. Therefore (if the sequence is bounded) the method will always get stuck close to one of these accumulation points, and hence will return an approximation to some stationary point (typically a minimizer if a descent method is used).

A stationary point is a property of the function optimized, an accummulation point one of the sequence generated in theory if the algorithm were executed exactly and infinitely long. What is computed is an approximation to an accumulation point of this theoretical sequence. Note that an accumulation point has no intrinsic meaning apart from the sequence of which it is the accumulation point. Thus the result has a useful meaning only if every accumulation point is a stationary point, as (only) then the ''solution'' returned will be an approximate stationary point.

$\endgroup$
  • $\begingroup$ Thanks. So, if a final solution obtained by a solver has gradient not equal to zero, one might state that the result is just an accumulation point (and not the stationary point)? $\endgroup$ – usero Mar 28 '12 at 11:44
  • $\begingroup$ No. I added more explanations to my query. $\endgroup$ – Arnold Neumaier Mar 28 '12 at 12:14
  • $\begingroup$ It is clear the the optimizer should return an approximation to the accumulation point, in practice. I'm feel I'm still unclear with stationary and accumulation point. So, given that the gradient of a function at the stationary point is zero, "one might state that the result is just an approximation to the accumulation point (and not the stationary point)"(from my previous comment). $\endgroup$ – usero Mar 28 '12 at 12:35
  • $\begingroup$ If every accumulation point of the theroetical sequence generate is a stationary point (and any good algorithm should have this property) then ''approximation to an accumulation point'' implies ''approximation to a stationary point'', and only the latter is what one would like to report. But if the final gradient is big, the approximation is so poor that one shouldn't trust the result. $\endgroup$ – Arnold Neumaier Mar 28 '12 at 12:42

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.