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

2019/02/06 by Vincent Corlay, Joseph J. Boutros, Corlay, Vincent +6 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Handwritten Text Recognition Techniques #Neural Networks and Applications #cs.IT #cs.LG #math.IT

paper · pdf · doi:10.48550/arxiv.1902.05146

Submitted to 2019 IEEE International Symposium on Information Theory (ISIT)

arxiv created 2019/02/28 · arxiv updated 2019/03/01

Abstract

Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in Rn, 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.

Cited by

• A lattice-based approach to the expressivity of deep ReLU neural networks

Related

• Neural network approaches to point lattice decoding
• A lattice-based approach to the expressivity of deep ReLU neural networks
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks
• The Lattice Geometry of Neural Network Quantization -- A Short Equivalence Proof of GPTQ and Babai's Algorithm
• Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes