@article {5177,
	title = {How Deep Sparse Networks Avoid the Curse of Dimensionality: Efficiently Computable Functions are Compositionally Sparse},
	year = {2022},
	month = {10/2022},
	abstract = {<p>The main claim of this perspective is that compositional sparsity of the target function, which corresponds\&nbsp; to the task to be learned, is the key principle underlying machine learning. Mhaskar and\&nbsp; Poggio (2016) proved that sparsity of the compositional target functions (when the functions are on\&nbsp; the reals, the constituent functions are also required to be smooth), naturally leads to sparse deep\&nbsp; networks for approximation and thus for optimization. This is the case of most CNNs in current use,\&nbsp; in which the known sparse graph of the target function is reflected in the sparse connectivity of the\&nbsp; network. When the graph of the target function is unknown, I conjecture that transformers are able to\&nbsp; implement a flexible version of sparsity (selecting which input tokens interact in the MLP layer), through\&nbsp; the self-attention layers.\&nbsp; Surprisingly, the assumption of compositional sparsity of the target function is not restrictive in practice,\&nbsp; since I prove here that for computable functions (if on the reals with Lipschitz continuous derivatives)\&nbsp; compositional sparsity is equivalent to efficient computability, that is Turing computability in polynomial\&nbsp; time.</p>
},
	author = {Tomaso A. Poggio}
}
