Not having read the paper carefully, could someone tell me what the draw is? It looks like it is going to have the same asymptotic complexity as SGD in terms of

Not having read the paper carefully, could someone tell me what the draw is? It looks like it is going to have the same asymptotic complexity as SGD in terms of sample size, per Table 1. Given that today's large, over-specified models have numerous, comparable extrema, is there even a need for this? I wouldn't get out of bed unless it were sublinear.