In classical optimization, an enormous amount of effort is taken to characterize the rate of convergence of optimization algorithms and designing fast gradient algorithms. You can find tables upon tables, for example, on page 16 https://arxiv.org/pdf/1405.4980.pdf

However, I have not found any of the rates ever useful in any ways when it comes to deep learning.

In modern machine learning such as the training of deep neural networks, does convergence rate matter?

Some reasons why it might not.

  1. Most convergence rates are for convex/strongly convex setting which does not hold for deep learning. The loss surface in deep learning looks like this: enter image description here

  2. The rate of convergence measures the worst-case big Oh iterations of how fast we can get to a global optimum, whereas in deep learning we don't care about how many iterations (run for N epoches, use that as the model, the end.), and we don't care about the global optimum either (don't care about the quality of local optimum all that much either)

  3. Accelerated methods such as Nesterov's method are almost always multiple steps, which adds to computational burden rather than reducing it; so "faster algorithm" could actually mean more wall-clock time by computing those extra-steps, let alone the worse space complexity coming from computing a whole extra step.

  4. Adding compute and parallism translates to higher speed almost 100% of the time, which classical algorithm design ignores. People obsessed for years about fasters methods such as Levenberg-Marquardt or conjugate gradient in the 80s, let alone dozens of training algorithm and then GPU came along and now everyone runs SGD (which has pretty bad theoretical rate I might add).

Ok I might be completely wrong, but has anyone found any usage for the rate of convergence in the literature and how that has helped in training of networks? .

  • $\begingroup$ Shazer told Andrew ng in interview that it cost 1 million dollars to train nlp model. You bet they care about the speed of convergence $\endgroup$
    – Aksakal
    Jun 20 '20 at 2:33
  • 1
    $\begingroup$ @Aksakal Yes of course we care how fast the problem is solved, but I just don't think the rate of convergence of optimizers/optimization routines matters in the deep learning domain. The whole point of making gradient based optimization faster is that at each iteration we take a step along the gradient (or processing of this gradient) towards the minimum, of course the "better" this step takes us to the minimum, then the faster we can arrive. But we have no way of quantify this "better" in the deep learning domain: non-convexity, stopping criterion not based on any distance measure, etc. $\endgroup$ Jun 20 '20 at 2:42
  • $\begingroup$ Do you mean some theoretical rate estimate then? $\endgroup$
    – Aksakal
    Jun 20 '20 at 2:48

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.