Linear Programming and Representer Theorems. Neural Networks are non-parametric models enjoying universal approximation over the class of continuous functions, similarly as Reproducing Kernel Hilbert Spaces. Fitting such neural networks on a finite dataset of n data points in dimension d thus naturally defines two distinct regimes: the overparametrised (resp. underparametrised) regime, corresponding to the setting when the number of neurons is larger (resp. smaller) than the number of data points. Several authors noted a remarkable phenomenon around this transition, such as the so-called double-descent [8, 9, 10, 11], leading to the apparent paradox of having good generalization capabilities even as the number of neurons grows indefinitely [8].

 

A possible hypothesis supporting this behavior comes from the implicit regularisation built-in by gradient descent methods at solving the Empirical Risk Minimisation. Weight-decay is a popular regularisation strategy that penalizes the squared L₂ norm of the neuron’s weights. In the context of shallow ReLU networks, the resulting training problem can be formulated in terms of a probability measure over the neuron parameters [5, 12], leading to a sparse regularised convex program over a ‘continuous’ dictionary {φ_θ;θ ∈ Θ}, where Θ ⊆ R^d is the space of neuron parameters and φ_θ(x) =  is a single neuron. Classic results from convex geometry assert that such convex programs admit sparse solutions with at most n atoms [13, 14, 15], the so-called Representer theorem. In fact, [16] recently have shown that all solutions of this program are sparse, therefore resulting in only a finite number of neurons, irrespective of the amount of overparameterization. In other words, training shallow ReLU networks in the overparametrised regime amounts to solving a linear program in finite dimension, given by the hyperplane arrangement generated by the dataset when identifying a point x ∈ R^d with a hyperplane in the dual. Although this reduction is not computationally useful (since the size of the hyperplane arrangement is O(n^d)), studying properties of the dataset that allow for substantially smaller arrangements is a promising direction for future research.

 

Spectral/Fourier analysis. Deep networks usually require a massive amount of labeled data for their training. Yet, such data may include some mistakes in the labels. Interestingly, networks have been shown to be robust to such errors. By analyzing the function space of neural networks in the spectral domain, an explanation for this robustness has been provided. In particular, it has been shown that this is related to the fact that neural networks tend to learn smooth functions, i.e., functions whose spectrum decays rapidly [17, 18, 19, 20]. This has been related to both the fact that networks have bounded weights as discussed above and to the structure of the network [21]. Noisy labels mainly affect the high frequencies in the learned function. Thus, the attenuation of high frequencies in neural networks may explain their robustness to noise. This understanding has led to the use of spectral regularization to further improve the network robustness to label noise [22].

 

Summary. We have briefly discussed how classic signal processing tools can greatly help in improving and understanding deep neural networks. The above directions are just an example and there are directions that used for deep learning other tools from signal processing such as sparse representation [23], max affine splines [24], wavelets [25]. We hope that others in the research community will be encouraged to do so as well.
 

---

References:

1. K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359–366, July 1989.
2. G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signals Systems, 2:303–314, 1989.
3. Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667–2690, 2019.
4. Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Processing Systems 32, pages 8376–8385, 2019.
5. Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width ReLU nets: The multivariate case. In International Conference on Learning Representations (ICLR), 2020.
6. Raja Giryes. A function space analysis of finite neural networks with insights from sampling theory. CoRR, abs/2004.06989, 2020.
7. Shady Abu Hussein, Tom Tirer, and Raja Giryes. Correction filter for single image super-resolution: Robustifying off-the-shelf deep super-resolvers. In The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
8. Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the bias-variance trade-off. arXiv preprint arXiv:1812.11118, 2018.
9. Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560, 2019.
10. Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv:1908.05355, 2019.
11. Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
12. Lenaic Chizat. Sparse optimization on measures with over-parameterized gradient descent. arXiv preprint arXiv:1907.10300, 2019.
13. S. Zuhovickii. Remarks on problems in approximation theory. Mat. Zbirnik KDU, 1948.
14. SD Fisher and Joseph W Jerome. Spline solutions to l1 extremal problems in one and several variables. Journal of Approximation Theory, 13(1):73–83, 1975.
15. Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629–681, 2017.
16. Jaume de Dios and Joan Bruna. On sparsity in overparametrised shallow relu networks. arXiv preprint arXiv:2006.10225, 2020.
17. Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 5301–5310, 2019.
18. Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior of deep neural network in frequency domain. In International Conference on Neural Information Processing, pages 264–274, 2019.
19. Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems (NeurIPS), pages 4761–4771, 2019.
20. Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In ICML, 2020.
21. Reinhard Heckel and Mahdi Soltanolkotabi. Denoising and regularization via exploiting the structural bias of convolutional generators. In International Conference on Learning Representations (ICLR), 2020.
22. Oshrat Bar, Amnon Drory, and Raja Giryes. A function space spectral perspective of neural network robustness to label noise. CoRR, 2020.
23. Vardan Papyan, Yaniv Romano, and Michael Elad. Convolutional neural networks analyzed via convolutional sparse coding. The Journal of Machine Learning Research, 18(1):2887–2938, 2017.
24. Randall Balestriero and richard baraniuk. A spline theory of deep learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 374–383, 10–15 Jul 2018.
25. Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE transactions on pattern analysis and machine intelligence, 35(8):1872–1886, 2013.