<p>See the papers by Roi Livni and coauthors:</p>

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

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

CC BY-SA 3.0
2017-12-19T21:06:06.237Z
2017-12-19T21:06:06.237Z
Aryeh
<p>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. </p>

<p>In particular, I'm trying to study questions like: </p>

<ol>
<li>How is training complexity related to network topology ? </li>
<li>How is training complexity related to the complexity of the decision boundary? </li>
</ol>

CC BY-SA 3.0
2017-12-20T14:40:53.107Z
Cross-posted on CS.SE: https://cs.stackexchange.com/questions/85641/references-for-the-computational-complexity-of-training-neural-networks
Clement C.
CC BY-SA 3.0
2017-12-20T17:56:27.887Z
@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.
Alexander S King
<reference-request><machine-learning>
References for the computational complexity of training neural networks
Alexander S King
# References for the computational complexity of training neural networks

(Asked by: username_0 on 2017-12-19)

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?

**Tags:** reference-request, machine-learning
> **Comments:**
> **username_1**: Cross-posted on CS.SE: https://cs.stackexchange.com/questions/85641/references-for-the-computational-complexity-of-training-neural-networks  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2017-12-19. Score: 1

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


---

