2021-07-21-malach21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
The Connection Between Approximation, Depth Separation and Learnability in Neural Networks	Several recent works have shown separation results between deep neural networks, and hypothesis classes with inferior approximation capacity such as shallow networks or kernel classes. On the other hand, the fact that deep networks can efficiently express a target function does not mean that this target function can be learned efficiently by deep neural networks. In this work we study the intricate connection between learnability and approximation capacity. We show that learnability with deep networks of a target function depends on the ability of simpler classes to approximate the target. Specifically, we show that a necessary condition for a function to be learnable by gradient descent on deep neural networks is to be able to approximate the function, at least in a weak sense, with shallow neural networks. We also show that a class of functions can be learned by an efficient statistical query algorithm if and only if it can be approximated in a weak sense by some kernel class. We give several examples of functions which demonstrate depth separation, and conclude that they cannot be efficiently learned, even by a hypothesis class that can efficiently approximate them.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	malach21a	0	The Connection Between Approximation, Depth Separation and Learnability in Neural Networks	3265	3295	3265-3295	3265	false	Malach, Eran and Yehudai, Gilad and Shalev-Schwartz, Shai and Shamir, Ohad	given family Eran Malach given family Gilad Yehudai given family Shai Shalev-Schwartz given family Ohad Shamir	2021-07-21		Proceedings of Thirty Fourth Conference on Learning Theory	134	inproceedings	date-parts 2021 7 21	http://proceedings.mlr.press/v134/malach21a/malach21a.pdf