2
$\begingroup$

I am reading some optimization methods and I am facing some issues with two terms "asymptotic and non-asymptotic convergence". What is the difference between them?

$\endgroup$
3
  • $\begingroup$ Is "non-asymptotic" the convergence (in exact arithmetic) in a finite number of steps, like in the CG method? $\endgroup$ Oct 7, 2021 at 9:36
  • 2
    $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Oct 7, 2021 at 12:59
  • $\begingroup$ Please, add a little bit of context and/or reference and, best of all, direct quote — right into the question. $\endgroup$
    – Anton Menshov
    Oct 7, 2021 at 17:19

1 Answer 1

5
$\begingroup$

Traditionally, the convergence of optimization algorithms has been analyzed in terms of the asymptotic rate of convergence. A quadratically convergent algorithm has $x_{k} \rightarrow x^{*}$ and

$\lim_{k \rightarrow \infty} \frac{\| x_{k+1}-x^{*} \|}{\| x_{k}-x^{*} \|^{2}}=L< \infty$

while a linearly convergent algorithm has

$\lim_{k \rightarrow \infty} \frac{\| x_{k+1}-x^{*} \|}{\| x_{k}-x^{*} \|}=L< 1$

a superlinearly convergent algorithm has

$\lim_{k \rightarrow \infty} \frac{\| x_{k+1}-x^{*} \|}{\| x_{k}-x^{*} \|}=0$

and a sublinearly convergent algorithm has $x_{k} \rightarrow x^{*}$, but

$\lim_{k \rightarrow \infty} \frac{\| x_{k+1}-x^{*} \|}{\| x_{k}-x^{*} \|}=1$

When high accuracy solutions (say to 15 digits in double-precision floating-point arihmetic) are needed, algorithms that are quadratically or superlinearly convergent are considered to work well, while linearly convergent and sublinearly convergent algorithms are considered to perform poorly.

In practice, if a quadratically convergent algorithm is used to solve an optimization problem then during the last few iterations of the algorithm, the number of correct digits in the solution will double in each iteration.

In recent years, there has been a lot of interest in first-order methods for convex but non-smooth optimization problems that have sublinear asymptotic convergence but can achieve reasonably useful approximate solutions quickly.

In this setting, the convergence of an optimization algorithm is evaluated in terms of the number of iterations required to obtain a solution $x_{k}$ with $f(x_{k})-f(x^{*}) \leq \epsilon$. Such an algorithm might require $O(1/\epsilon)$ or $O(1/\sqrt{\epsilon})$ iterations to obtain an $\epsilon$-approximate solution. Also note that this convergence is sometimes given in terms of the $\epsilon$ that can be achieved in $k$ iterations (e.g. $O(1/k^{2})$).

In practice, these algorithms are used to compute solutions with optimal objective values that are good to two or three digits rather than to full floating-point accuracy. The algorithms are terminated long before the asymptotic convergence has kicked in and the asymptotic convergence is often sublinear, so asymptotic convergence rates aren't relevant. However, there's a huge difference in performance between an $O(1/\epsilon)$ algorithm and an $O(1/\sqrt{\epsilon})$ algorithm, so the analysis of iteration complexity is useful.

For example, suppose that we want to solve a very large scale optimization problem to $\epsilon=1.0 \times 10^{-4}$ and that it takes an hour to do this computation using an $O(1/\epsilon)$ iteration complexity algorithm. Getting $\epsilon$ down to $1.0 \times 10^{-15}$ would take on the order of $1.0 \times 10^{11}$ hours.

For more on this, see my answer to a related question on math.stackexchange.com

https://math.stackexchange.com/questions/2615576/sublinear-rate-of-convergence-in-mathematical-optimization

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