Stochastic gradient methods and risk of neural nets
The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $A$ and an $\epsilon &gt;0$ and a loss class $L$ and a data distribution $D$, one cannot use algorithms of type $A$ to find a member of $L$ whose generalization error is below $\epsilon$ unless running time is $f(\epsilon)$"... .

One such lower bound I'm aware of is for the case of Statistical Query based algorithms. See, for example, the paper by Yang, "New lower bounds for statistical query learning",
https://www.sciencedirect.com/science/article/pii/S0022000004001291
where, in particular,
it is shown that "any SQ-based algorithm needs running time $\Omega(2^n)$".