Some contributions to deep learning theory : optimization, robustness, and approximation

Dans cette thèse, nous étudions différents aspects théoriques de l'apprentissage profond, en particulier l'optimisation, la robustesse et l'approximation. Optimisation: Nous étudions le paysage d'optimisation du risque empirique des réseaux neuronaux linéaires profonds avec la perte des moindres carrées. Il est connu que, sous des hypothèses faibles, il n'y a pas de minimiseurs locaux non-globaux et pas de maximiseurs locaux. Cependant, l'existence et la diversité des points selle non-stricts, qui peuvent jouer un rôle dans la dynamique des algorithmes du premier ordre, n'ont été que peu étudiées. Nous fournissons une analyse complète du paysage d'optimisation à l'ordre 2. Nous caractérisons, parmi tous les points critiques, les minimiseurs globaux, les points-selles stricts et les points-selles non stricts. Nous énumérons toutes les valeurs critiques associées. La caractérisation est simple, elle implique des conditions sur les rangs des produits partiels de matrices, et éclaire la convergence globale ou la régularisation implicite qui ont été prouvées ou observées lors de l'optimisation de réseaux neuronaux linéaires. Au passage, nous fournissons une paramétrisation explicite de l'ensemble de tous les minimiseurs globaux et exposons de grands ensembles de points selle stricts et non stricts. Robustesse: Nous étudions les propriétés théoriques des couches convolutives orthogonales. Nous établissons des conditions nécessaires et suffisantes sur l'architecture de la couche garantissant l'existence d'une transformée convolutive orthogonale. Ces conditions prouvent que les transformées convolutives orthogonales existent pour presque toutes les architectures utilisées en pratique pour le padding "circulaire". Nous montrons également des limitations avec des conditions aux bords "valid" et des conditions aux bords "same" avec un zero-padding. Récemment, un terme de régularisation imposant l'orthogonalité des couches convolutives a été proposé, et des résultats empiriques impressionnants ont été obtenus dans différentes applications : (Wang et al. 2020). Nous faisons le lien entre ce terme de régularisation et les mesures d'orthogonalité. Ce faisant, nous montrons que cette stratégie de régularisation est stable vis-à-vis des erreurs numériques et d'optimisation et que, en présence de petites erreurs et lorsque la taille du signal/de l'image est grande, les couches convolutives restent proches de l'isométrie. Les résultats théoriques sont confirmés par des expériences et le paysage du terme de régularisation est étudié. Les expériences sur des jeux de données réels montrent que lorsque l'orthogonalité est utilisée pour renforcer la robustesse, le paramètre multipliant le terme de régularisation peut être utilisé pour régler un compromis entre la précision et l'orthogonalité, au profit de la précision et de la robustesse. Approximation: Nous étudions les limites fondamentales du pouvoir expressif des réseaux de neurones. Étant donné deux ensembles F, G de fonctions à valeurs réelles, nous prouvons d'abord une limite inférieure générale sur la façon dont les fonctions de F peuvent être approximées en norme L^p par des fonctions de G. La borne inférieure dépend du "packing number" de F, de l'étendue de F, et de la "fat-shattering dimension" G. Nous instancions ensuite cette borne au cas où G correspond à un réseau de neurones feedforward dont la fonction d'activation est polynomiale par morceaux, et décrivons en détail l'application à deux ensembles F : les boules de Hölder et les fonctions monotones multivariées. En plus de correspondre aux limites supérieures (connues ou nouvelles) à des facteurs logarithmiques près, nos limites inférieures éclairent les similitudes ou les différences entre l'approximation en norme L^p et en norme sup, résolvant ainsi une question ouverte par (DeVore et al. 2021).In this thesis, we study different theoretical aspects of deep learning, in particular optimization, robustness, and approximation. Optimization: We study the optimization landscape of the empirical risk of deep linear neural networks with the square loss. It is known that, under weak assumptions, there are no spurious local minima and no local maxima. However, the existence and diversity of non-strict saddle points, which can play a role in first-order algorithms' dynamics, have only been lightly studied. We go a step further with a full analysis of the optimization landscape at order 2. We characterize, among all critical points, which are global minimizers, strict saddle points, and non-strict saddle points. We enumerate all the associated critical values. The characterization is simple, involves conditions on the ranks of partial matrix products, and sheds some light on global convergence or implicit regularization that have been proved or observed when optimizing linear neural networks. In passing, we provide an explicit parameterization of the set of all global minimizers and exhibit large sets of strict and non-strict saddle points. Robustness: We study the theoretical properties of orthogonal convolutional layers. We establish necessary and sufficient conditions on the layer architecture guaranteeing the existence of an orthogonal convolutional transform. The conditions prove that orthogonal convolutional transforms exist for almost all architectures user in practice for 'circular' padding. We also exhibit limitations with 'valid' boundary conditions and 'same' boundary conditions with zero-padding. Recently, a regularization term imposing the orthogonality of convolutional layers has been proposed, and impressive empirical results have been obtained in different applications cite{wang2020orthogonal}. The second motivation is to specify the theory behind this. We make the link between this regularization term and orthogonality measures. In doing so, we show that this regularization strategy is stable with respect to numerical and optimization errors and that, in the presence of small errors and when the size of the signal/image is large, the convolutional layers remain close to isometric. The theoretical results are confirmed with experiments and the landscape of the regularization term is studied. Experiments on real datasets show that when orthogonality is used to enforce robustness, the parameter multiplying the regularization term can be used to tune a tradeoff between accuracy and orthogonality, for the benefit of both accuracy and robustness. Altogether, the study guarantees that the regularization proposed in (Wang et al. 2020) is an efficient, flexible and stable numerical strategy to learn orthogonal convolutional layers. Approximation: We study the fundamental limits to the expressive power of neural networks. Given two sets dollarFdollar, dollarGdollar of real-valued functions, we first prove a general lower bound on how well functions in dollarFdollarcan be approximated in dollarL^p(mu) dollar norm by functions in dollarGdollar, for any dollarp geq 1dollar and any probability measure dollarmudollar. The lower bound depends on the packing number of dollarFdollar, the range of dollarFdollar, and the fat-shattering dimension of dollarGdollar. We then instantiate this bound to the case where dollarGdollar corresponds to a piecewise-polynomial feed-forward neural network, and describe in details the application to two sets dollarFdollar: Hölder balls and multivariate monotonic functions. Beside matching (known or new) upper bounds up to log factors, our lower bounds shed some light on the similarities or differences between approximation in dollarL^pdollar norm or in sup norm, solving an open question by (DeVore et al. 2021)