Have you seen any analytic bound on gradient descent (for number of iterations to achieve to $\epsilon$ error, and possibly based on the form of cost function and initial value)?

Here is the problem; I have a cost function which is being optimized by gradient descent. Someone has changed the cost function, in some ways, and has shown to converge to the main result (the result of gradient descent on the main cost function). I want to compare the convergence-time bounds for these two algorithm ...

Are you aware of any such bounds for similar optimization algorithms ?


Here's the reference you want: Introductory Lectures on Convex Optimization by Yurii Nesterov. Bounds galore! Performance generally depends on the Lipschitz continuity of the function, as well as any strong convexity behavior. Keep in mind thought that these bounds tend to be worst case. There really is no substitution for experimentation when comparing real-world performance.

  • $\begingroup$ Thanks Michael! I think you mean this: core.ucl.ac.be/~nesterov/Courses/INMA2460/Intro-nl.pdf Can you give me a quick reference to chapter/page (time bound for gradient descent) ? $\endgroup$ – Daniel Apr 26 '13 at 22:56
  • $\begingroup$ I don't know if that matches the book I'm referring to or not. I'm afraid I can't offer a page number. It's not hard to find if you have the right book though. $\endgroup$ – Michael Grant Apr 26 '13 at 23:17
  • $\begingroup$ I couldn't find such "time"-bound in the book you are referring to... $\endgroup$ – Daniel Apr 27 '13 at 7:51
  • $\begingroup$ What? Of course it's there. One of the key aspects of the book are the worst-case iteration counts for the gradient method, and for "accelerated" gradient methods. I've used that book for a reference in publications for that very purpose. $\endgroup$ – Michael Grant Apr 27 '13 at 12:29
  • $\begingroup$ oh, I found the main book. Thanks for your guidance. $\endgroup$ – Daniel Apr 28 '13 at 6:12

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.