In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a bound for the total number of iterations for some process. See page 109:

$$\left[\frac{1}{\ln(2(1-\kappa))} \ln\frac{t_0-t^*}{(1-\kappa) \epsilon}+2\right]\cdot \left[1+\sqrt\frac{L}{\mu}\ln\frac{2(L-\mu)}{\kappa \mu}\right]\\+\sqrt\frac{L}{\mu}\cdot\ln\left(\frac{1}{\epsilon}\max_{1\leq i \leq m}\{f_0(x_0)-t_0; f_i(x_0)\}\right)\label{eq1}\tag{1}$$

Then, the principal term in the above estimate is of the order $$\ln\frac{t_0-t^*}{\epsilon} \sqrt\frac{L}{\mu} \ln\frac{L}{\mu} \label{eq2}\tag{2}$$

How did we arrive at statement $\eqref{eq2}$? Is that true the second term $\sqrt\frac{L}{\mu}\cdot\ln\big(\frac{1}{\epsilon}\max_{1\leq i \leq m}\{f_0(x_0)-t_0; f_i(x_0)\}\big)$ in $\eqref{eq1}$ is eliminated? I would appreciate any advice here.

  • 1
    $\begingroup$ Can you say what variable goes to infinity in this asymptotic analysis? If it's $L/\mu$, then he's right to drop the last term because $\log(L/\mu)$ increase while $\log(\epsilon^{-1}\max\cdots)$ is independent of $L/\mu$ and therefore treated as a constant. The coefficient of $\sqrt{L/\mu}\log(L/\mu)$ doesn't look right to me, it should be the large expression $2+\cdots$ in the first pair of brackets, unless something else goes to infinity also. It would really help to have the full original expression with context. $\endgroup$ – Kirill Oct 12 '18 at 15:43
  • $\begingroup$ [It looks like only $\epsilon$ is changing. This is page 109][1]books.google.com/… $\endgroup$ – John Smith Oct 12 '18 at 15:55
  • $\begingroup$ If only $\epsilon$ is changing, then it would be $\log\frac{t_0-t^*}{\epsilon} \sim -\log\epsilon$, so I'm not sure that's it. $\endgroup$ – Kirill Oct 12 '18 at 16:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.