1
$\begingroup$

I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

  1. How is training complexity related to network topology ?
  2. How is training complexity related to the complexity of the decision boundary?
$\endgroup$
  • $\begingroup$ Cross-posted on CS.SE: cs.stackexchange.com/questions/85641/… $\endgroup$ – Clement C. Dec 20 '17 at 14:40
  • $\begingroup$ @ClementC. I realized only after posting that this SE might be better suited for my question. I can't delete the old post because it already has an answer. $\endgroup$ – Alexander S King Dec 20 '17 at 17:56
1
$\begingroup$

See the papers by Roi Livni and coauthors:

*Roi Livni, Daniel Carmon, Amir Globerson: Learning Infinite Layer Networks Without the Kernel Trick. ICML 2017: 2198-2207

*Roi Livni, Shai Shalev-Shwartz, Ohad Shamir: On the Computational Efficiency of Training Neural Networks. NIPS 2014: 855-863

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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