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.
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)
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.
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? .