Stochastic gradient methods and risk of neural nets

Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv.org/abs/1811.04918 https://arxiv.org/abs/1811.03962, https://arxiv.org/abs/1810.12065, https://arxiv.org/pdf/1810.02054.pdf, https://arxiv.org/abs/1705.04591 and dozens more!

Is the focus on stochastic gradient based methods for this question purely motivated by the fact that this is pretty much the only thing used in practice?

Or is there a fundamental/complexity-theoretic reason why there cant be an algorithm (or its improbably hard to find an algorithm) that does not use stochastic gradients (is maybe deterministic!) and yet minimizes the risk of neural nets as fast as one can using SGD-like methods?

• You should first ask, Why is SGD used in practice? The answer has to do with memory efficiency and parallelizability. – Aryeh Nov 17 '18 at 19:20
• That would be a very strong claim to make! I am not aware of anyone claiming that. – Aryeh Nov 18 '18 at 8:08
• Well, you would need a reduction showing that any risk minimizer in this setting is essentially performing SGD as a byproduct. Like I said, I’m not aware of any such results. – Aryeh Nov 18 '18 at 18:16
• Sure, the problem is NP-hard in general. Hard to approximate even, in the case of nearest-neighbor sample compression (see Thm. 4 here cs.bgu.ac.il/~karyeh/semimetric-j.pdf ) – Aryeh Nov 18 '18 at 22:31
• It's rare that "study of X is purely motivated by Y", and it is rare to find results of the form "it is impossible to get benefits B without method M", so I don't think it's very useful to ask for that or expect it to hold in this context -- that seems like asking for an awful lot. – D.W. Nov 20 '18 at 2:17

The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $$A$$ and an $$\epsilon >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)$$".