<p>[Disclaimer: Crossposted in cs --&gt; <a href="https://cs.stackexchange.com/questions/159200/learning-parities-via-gradient-descent">link]
</a></p>
<p>In their recent work <a href="https://arxiv.org/pdf/2002.07400.pdf" rel="nofollow noreferrer">[DM20]</a> Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since <a href="https://doi.org/10.1145/293347.293351" rel="nofollow noreferrer">[Kearn94]</a> it is known that any statistical query algorithm to learn parities needs exponentially many statistical queries.</p>
<p><strong>My question:</strong>
what is the 'loophole' in the middle between gradient descent and the statistical query model that [DM20] is exploiting? In particular:</p>
<ul>
<li>Is their algorithm robust to errors due to finite samples in the gradient estimation?</li>
<li>is there any 'fine tuning' involved (such as it is in e.g. <a href="http://arxiv.org/abs/2001.02992" rel="nofollow noreferrer">[AS20]</a>)?</li>
<li>Is there any other property of GD exploited exploited?</li>
</ul>
<p><strong>Bonus question:</strong>
With the above in mind, does their result actually imply a separation between kernel methods and practically used NN based methods, or is the result more of a theoretic nature and see it as evidence for such a practical separation (where future work would be to prove a similar separation on some concept class for SGD without 'no tuning')?</p>

CC BY-SA 4.0
2023-03-22T16:43:14.823Z
Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2023-03-23T10:28:58.800Z
I just wanted to edit the crosspost disclaimer. Whats the problem with cross posting if made transparent?
uzer.name
CC BY-SA 4.0
2023-03-23T11:14:45.473Z
Honestly, I think that my question is, to use the third answer in your link, one of those exceptions where it is meaningfull to ask identical questions in two comunities. 
If you have a good argument why this is not the case, or why I misjudge the audiences of the two SE's, I am happy to delete the according post.
uzer.name
<machine-learning><parity>
Learning Parities via Gradient Descent
uzer.name
# Learning Parities via Gradient Descent

(Asked by: username_0 on 2023-03-22)

[Disclaimer: Crossposted in cs --> [link]](https://cs.stackexchange.com/questions/159200/learning-parities-via-gradient-descent)

In their recent work [[DM20]](https://arxiv.org/pdf/2002.07400.pdf) Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [[Kearn94]](https://doi.org/10.1145/293347.293351) it is known that any statistical query algorithm to learn parities needs exponentially many statistical queries.

**My question:**
what is the 'loophole' in the middle between gradient descent and the statistical query model that [DM20] is exploiting? In particular:

* Is their algorithm robust to errors due to finite samples in the gradient estimation?
* is there any 'fine tuning' involved (such as it is in e.g. [[AS20]](http://arxiv.org/abs/2001.02992))?
* Is there any other property of GD exploited exploited?

**Bonus question:**
With the above in mind, does their result actually imply a separation between kernel methods and practically used NN based methods, or is the result more of a theoretic nature and see it as evidence for such a practical separation (where future work would be to prove a similar separation on some concept class for SGD without 'no tuning')?

**Tags:** machine-learning, parity

> **Comments:**
> **username_1**: Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_0**: I just wanted to edit the crosspost disclaimer. Whats the problem with cross posting if made transparent?  
> **username_0**: Honestly, I think that my question is, to use the third answer in your link, one of those exceptions where it is meaningfull to ask identical questions in two comunities.  If you have a good argument why this is not the case, or why I misjudge the audiences of the two SE's, I am happy to delete the according post.  

---

## 0 answers

