# 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. Nov 17, 2018 at 19:20
• That would be a very strong claim to make! I am not aware of anyone claiming that. Nov 18, 2018 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. Nov 18, 2018 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 ) Nov 18, 2018 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, 2018 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)$$".