1
$\begingroup$

I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class.

Now I am doing a project on optimization. In our optimization class, we were introduced to the notion of rate of convergence which are characterized by the ratio:

$\lim\limits_{k \to \infty} \dfrac{|x_{k+1} - L|}{|x_k-L|}$

where $L$ is the limit of the sequence $(x_k)$. And from there we define linear, superlinear and sublinear convergence raes.

However, when I looked up on some reference online, the above notions of rate of convergence is almost never used. Instead, all the convergence rates are characterized in terms of big-Oh. Quoting from the slides:

Theorem: Gradient decent with fixed step size $t\le\frac{1}{L}$ satisfies $f(x^{(k)})-f(x^*)\le\frac{\|x^{(0)}-x^*\|^2}{2tk}$.

I.e. gradient decent has convergence rate $O\left(\frac{1}{k}\right)$.

I.e. to get $f(x^{(k)})-f(x^*)\le\epsilon$, we need $O\left(\frac{1}{k}\right)$ iterations.

Unfortunately, these authors never define what their notations mean. I am in need of citing the definitions of big-Oh for my class project.

Is there any disparity between the rate of convergence in terms of big-Oh (and other asymptotic) used in optimization versus that used in CS (as can be found in a standard textbook such as CLRS)?

Is there an optimization textbook that addresses big-Oh notation?

$\endgroup$
  • $\begingroup$ Why the downvote? It is not my fault most authors do not define what these terms mean $\endgroup$ – Olórin Jan 20 '18 at 22:31
  • $\begingroup$ Not the downvoter, but please refrain from using pictures (links can break in time), I edited the post to include the related information. $\endgroup$ – Ariel Jan 20 '18 at 23:41
5
$\begingroup$

They are using the standard Landau notation.

In the theorem you stated, it is said that after $k$ steps your distance from the optimal value is smaller than $\frac{c}{k}$, where $c$ is a constant which depends on your initial distance from the point where optimum is achieved, and on the step size. In that case you can indeed say that the convergence rate is $O\left(\frac{1}{k}\right)$, which is interpreted as you quoted in the following line, to get $\epsilon$-close to the optimal value one needs $O\left(\frac{1}{\epsilon}\right)$ iterations.

Note that I wouldn't take this answer as "anywhere in optimization this notation means the Landau notation", and you are probably right to say that it needs to be mentioned. However, in this context, you can pretty safely assume that this was the authors intention.

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