2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You should first ask, Why is SGD used in practice? The answer has to do with memory efficiency and parallelizability. $\endgroup$ – Aryeh Nov 17 '18 at 19:20
  • 1
    $\begingroup$ That would be a very strong claim to make! I am not aware of anyone claiming that. $\endgroup$ – Aryeh Nov 18 '18 at 8:08
  • 2
    $\begingroup$ 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. $\endgroup$ – Aryeh Nov 18 '18 at 18:16
  • 1
    $\begingroup$ 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 ) $\endgroup$ – Aryeh Nov 18 '18 at 22:31
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Nov 20 '18 at 2:17
2
$\begingroup$

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)$".

$\endgroup$
  • $\begingroup$ Thanks for your answer. I was also beginning to think in this direction. So is stochastic gradient descent a SQ-type algorithm? $\endgroup$ – gradstudent Nov 20 '18 at 19:04
  • $\begingroup$ Hmm, I tend to think "yes" but not 100% sure about that. Have a look at this paper and if you still have questions, try contacting one of the authors: dl.acm.org/citation.cfm?doid=2488608.2488692 $\endgroup$ – Aryeh Nov 20 '18 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.