On the CVP for the root lattices via folding with deep ReLU neural networks - Equipe Communications numériques Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

On the CVP for the root lattices via folding with deep ReLU neural networks

Résumé

Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in R n , known as the closest vector problem (CVP), becomes a classification problem in the fundamental parallelotope with a piecewise linear function defining the boundary. Theoretical results are obtained by studying root lattices. We show how the number of pieces in the boundary function reduces dramatically with folding, from exponential to linear. This translates into a two-layer ReLU network requiring a number of neurons growing exponentially in n to solve the CVP, whereas this complexity becomes polynomial in n for a deep ReLU network.
Fichier principal
Vignette du fichier
ISIT_2019_Corlay.pdf (515.4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02282190 , version 1 (09-09-2019)

Identifiants

  • HAL Id : hal-02282190 , version 1

Citer

Vincent Corlay, Joseph Boutros, Philippe Ciblat, Loïc Brunel. On the CVP for the root lattices via folding with deep ReLU neural networks. IEEE International Symposium on Information Thoery (ISIT), Jul 2019, Paris, France. ⟨hal-02282190⟩
31 Consultations
96 Téléchargements

Partager

Gmail Facebook X LinkedIn More