<p>The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms <span class="math-container">$A$</span> and an <span class="math-container">$\epsilon &gt;0$</span> and a loss class <span class="math-container">$L$</span> and a data distribution <span class="math-container">$D$</span>, one cannot use algorithms of type <span class="math-container">$A$</span> to find a member of <span class="math-container">$L$</span> whose generalization error is below <span class="math-container">$\epsilon$</span> unless running time is <span class="math-container">$f(\epsilon)$</span>"... .</p>

<p>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",
<a href="https://www.sciencedirect.com/science/article/pii/S0022000004001291" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0022000004001291</a>
where, in particular,
it is shown that "any SQ-based algorithm needs running time <span class="math-container">$\Omega(2^n)$</span>".</p>

CC BY-SA 4.0
2018-11-20T19:04:01.533Z
Thanks for your answer. I was also beginning to think in this direction. So is stochastic gradient descent a SQ-type algorithm?
gradstudent
CC BY-SA 4.0
2018-11-20T19:28:48.117Z
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: https://dl.acm.org/citation.cfm?doid=2488608.2488692
Aryeh
CC BY-SA 4.0
2018-11-19T11:22:49.590Z
2018-11-19T11:22:49.590Z
Aryeh
<p>Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : <a href="https://arxiv.org/abs/1811.03804" rel="nofollow noreferrer">https://arxiv.org/abs/1811.03804</a>, <a href="https://arxiv.org/abs/1811.04918" rel="nofollow noreferrer">https://arxiv.org/abs/1811.04918</a> <a href="https://arxiv.org/abs/1811.03962" rel="nofollow noreferrer">https://arxiv.org/abs/1811.03962</a>, <a href="https://arxiv.org/abs/1810.12065" rel="nofollow noreferrer">https://arxiv.org/abs/1810.12065</a>, <a href="https://arxiv.org/pdf/1810.02054.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1810.02054.pdf</a>, <a href="https://arxiv.org/abs/1705.04591" rel="nofollow noreferrer">https://arxiv.org/abs/1705.04591</a> and dozens more!</p>

<p>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? </p>

<p>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? </p>

CC BY-SA 4.0
2018-11-17T19:20:55.300Z
You should first ask, Why is SGD used in practice? The answer has to do with memory efficiency and parallelizability.
Aryeh
CC BY-SA 4.0
2018-11-18T00:49:06.983Z
Yes. And is the claim that its impossible to get such benefits without stochastic gradients?
gradstudent
CC BY-SA 4.0
2018-11-18T08:08:39.077Z
That would be a *very* strong claim to make! I am not aware of anyone claiming that.
Aryeh
CC BY-SA 4.0
2018-11-18T17:46:19.567Z
Indeed it would be strong! I am wondering if there is any theoretical proof which makes stochastic gradient based algorithms for risk minimization look somewhat inevitable.
gradstudent
CC BY-SA 4.0
2018-11-18T18:16:42.440Z
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
CC BY-SA 4.0
2018-11-18T22:22:31.230Z
So are there run-time lowerbounds on any kind of risk minimization?
gradstudent
CC BY-SA 4.0
2018-11-18T22:31:08.833Z
Sure, the problem is NP-hard in general. Hard to approximate even, in the case of nearest-neighbor sample compression (see Thm. 4 here
https://www.cs.bgu.ac.il/~karyeh/semimetric-j.pdf
)
Aryeh
CC BY-SA 4.0
2018-11-18T22:53:11.307Z
Thanks. But why is Theorem 4 a theorem of the kind I am looking for? I was imagining a theorem of this kind "Given a class of algorithms A and an epsilon >0 and a loss class L and a data distributions 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)"  (..the "loss class" L is like say squared losses on some net architecture so that the members of L are parameterized by the weights of L..)
gradstudent
CC BY-SA 4.0
2018-11-18T23:09:06.733Z
You asked for run-time lower bounds, but we only know how to prove reductions from NP-hard problems, which is what Thm. 4 is.
Aryeh
CC BY-SA 4.0
2018-11-19T02:51:34.697Z
Interesting. So you mean that the only notion of hardness of risk minimization known is when we can relate that to some NP-hardness equation? So we dont have any "unconditional" hardness theorems which are like the statement I was imagining : which would say that for some class of algorithms a certain risk minimization is hard to do.
gradstudent
CC BY-SA 4.0
2018-11-20T02:17:36.703Z
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.
CC BY-SA 4.0
2018-11-20T05:58:07.580Z
Yes. It seems like. I wanted to know if there are any theoretical arguments which make the prevalent method of risk minimization somehow look "inevitable". Interprete my question as what is the "closest" to such an inevitability of stochastic gradients kind of proof do we have.
gradstudent
<optimization><machine-learning><ai.artificial-intel><stochastic-process>
Stochastic gradient methods and risk of neural nets
gradstudent
# Stochastic gradient methods and risk of neural nets

(Asked by: username_0 on 2018-11-16)

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?

**Tags:** optimization, machine-learning, ai.artificial-intel, stochastic-process

> **Comments:**
> **username_1**: You should first ask, Why is SGD used in practice? The answer has to do with memory efficiency and parallelizability.  
> **username_0**: Yes. And is the claim that its impossible to get such benefits without stochastic gradients?  
> **username_1**: That would be a *very* strong claim to make! I am not aware of anyone claiming that.  
> **username_0**: Indeed it would be strong! I am wondering if there is any theoretical proof which makes stochastic gradient based algorithms for risk minimization look somewhat inevitable.  
> **username_1**: 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.  
> **username_0**: So are there run-time lowerbounds on any kind of risk minimization?  
> **username_1**: Sure, the problem is NP-hard in general. Hard to approximate even, in the case of nearest-neighbor sample compression (see Thm. 4 here https://www.cs.bgu.ac.il/~karyeh/semimetric-j.pdf )  
> **username_0**: Thanks. But why is Theorem 4 a theorem of the kind I am looking for? I was imagining a theorem of this kind "Given a class of algorithms A and an epsilon >0 and a loss class L and a data distributions 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)"  (..the "loss class" L is like say squared losses on some net architecture so that the members of L are parameterized by the weights of L..)  
> **username_1**: You asked for run-time lower bounds, but we only know how to prove reductions from NP-hard problems, which is what Thm. 4 is.  
> **username_0**: Interesting. So you mean that the only notion of hardness of risk minimization known is when we can relate that to some NP-hardness equation? So we dont have any "unconditional" hardness theorems which are like the statement I was imagining : which would say that for some class of algorithms a certain risk minimization is hard to do.  
> **username_2**: 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.  
> **username_0**: Yes. It seems like. I wanted to know if there are any theoretical arguments which make the prevalent method of risk minimization somehow look "inevitable". Interprete my question as what is the "closest" to such an inevitability of stochastic gradients kind of proof do we have.  

---

## 1 answers

### Answer by username_1 on 2018-11-19. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks for your answer. I was also beginning to think in this direction. So is stochastic gradient descent a SQ-type algorithm?  
> **username_1**: 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: https://dl.acm.org/citation.cfm?doid=2488608.2488692  

---

