[Disclaimer: Crossposted in cs --> link]

In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [Kearn94] 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])?
  • 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')?

  • $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Commented Mar 22, 2023 at 16:43
  • $\begingroup$ I just wanted to edit the crosspost disclaimer. Whats the problem with cross posting if made transparent? $\endgroup$
    – uzer.name
    Commented Mar 23, 2023 at 10:28
  • $\begingroup$ 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. $\endgroup$
    – uzer.name
    Commented Mar 23, 2023 at 11:14


Your Answer

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

Browse other questions tagged or ask your own question.