On the complexity of nonsmooth automatic differentiation - ANITI - Artificial and Natural Intelligence Toulouse Institute Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

On the complexity of nonsmooth automatic differentiation

Résumé

We provide a simple model to estimate the computational costs of the backward and forward modes of algorithmic differentiation for a wide class of nonsmooth programs. Prominent examples are the famous relu and convolutional neural networks together with their standard loss functions. Using the recent notion of conservative gradients, we then establish a "nonsmooth cheap gradient principle" for backpropagation encompassing most concrete applications. Nonsmooth backpropagation's cheapness contrasts with concurrent forward approaches which have, at this day, dimensional-dependent worst case estimates. In order to understand this class of methods, we relate the complexity of computing a large number of directional derivatives to that of matrix multiplication. This shows a fundamental limitation for improving forward AD for that task. Finally, while the fastest algorithms for computing a Clarke subgradient are linear in the dimension, it appears that computing two distinct Clarke (resp. lexicographic) subgradients for simple neural networks is NP-Hard.
Fichier principal
Vignette du fichier
nonSmoothAD.pdf (354.95 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03683640 , version 1 (31-05-2022)
hal-03683640 , version 2 (30-01-2023)
hal-03683640 , version 3 (01-02-2023)

Identifiants

  • HAL Id : hal-03683640 , version 1

Citer

Jérôme Bolte, Ryan Boustany, Edouard Pauwels, Béatrice Pesquet-Popescu. On the complexity of nonsmooth automatic differentiation. International Conference on Learning Representations (ICLR 2023), International Conference on Learning Representations, May 2023, Kigali, Rwanda. ⟨hal-03683640v1⟩
422 Consultations
239 Téléchargements

Partager

Gmail Facebook X LinkedIn More