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?

Improve this question
$\endgroup$
12
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 2:17

1 Answer 1

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

Improve this answer
$\endgroup$
2
  • $\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, 2018 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, 2018 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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