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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.