Neural network approaches to point lattice decoding

• URL: http://arxiv.org/abs/2012.07032v1
• Date: Sun, 13 Dec 2020 10:53:34 GMT
• Title: Neural network approaches to point lattice decoding
• Authors: Vincent Corlay, Joseph J. Boutros, Philippe Ciblat, and Lo\"ic Brunel
• Abstract summary: Voronoi-reduced basis is introduced to restrict the space of solutions to a binary set. We count the number of affine pieces in the CPWL decoding function to characterize the complexity of the decoding problem.
• Score: 6.025026882312586
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We characterize the complexity of the lattice decoding problem from a neural network perspective. The notion of Voronoi-reduced basis is introduced to restrict the space of solutions to a binary set. On the one hand, this problem is shown to be equivalent to computing a continuous piecewise linear (CPWL) function restricted to the fundamental parallelotope. On the other hand, it is known that any function computed by a ReLU feed-forward neural network is CPWL. As a result, we count the number of affine pieces in the CPWL decoding function to characterize the complexity of the decoding problem. It is exponential in the space dimension $n$, which induces shallow neural networks of exponential size. For structured lattices we show that folding, a technique equivalent to using a deep neural network, enables to reduce this complexity from exponential in $n$ to polynomial in $n$. Regarding unstructured MIMO lattices, in contrary to dense lattices many pieces in the CPWL decoding function can be neglected for quasi-optimal decoding on the Gaussian channel. This makes the decoding problem easier and it explains why shallow neural networks of reasonable size are more efficient with this category of lattices (in low to moderate dimensions).

Related papers

• Erasure Coded Neural Network Inference via Fisher Averaging [28.243239815823205]
  Erasure-coded computing has been successfully used in cloud systems to reduce tail latency caused by factors such as straggling servers and heterogeneous traffic variations. We design a method to code over neural networks, that is, given two or more neural network models, how to construct a coded model whose output is a linear combination of the outputs of the given neural networks. We conduct experiments to perform erasure coding over neural networks trained on real-world vision datasets and show that the accuracy of the decoded outputs using COIN is significantly higher than other baselines.
  arXiv  Detail & Related papers  (2024-09-02T18:46:26Z)
• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization [5.982922468400901]
  We show that it is possible to achieve error bounds equivalent to that obtained in the order of the weights of a neural layer. We prove that it is possible to achieve full-network bounds under an infinite alphabet and minimal assumptions on the input data.
  arXiv  Detail & Related papers  (2023-09-20T00:35:16Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Variable Bitrate Neural Fields [75.24672452527795]
  We present a dictionary method for compressing feature grids, reducing their memory consumption by up to 100x. We formulate the dictionary optimization as a vector-quantized auto-decoder problem which lets us learn end-to-end discrete neural representations in a space where no direct supervision is available.
  arXiv  Detail & Related papers  (2022-06-15T17:58:34Z)
• A Sparse Coding Interpretation of Neural Networks and Theoretical Implications [0.0]
  Deep convolutional neural networks have achieved unprecedented performance in various computer vision tasks. We propose a sparse coding interpretation of neural networks that have ReLU activation. We derive a complete convolutional neural network without normalization and pooling.
  arXiv  Detail & Related papers  (2021-08-14T21:54:47Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Artificial Neural Networks generated by Low Discrepancy Sequences [59.51653996175648]
  We generate artificial neural networks as random walks on a dense network graph. Such networks can be trained sparse from scratch, avoiding the expensive procedure of training a dense network and compressing it afterwards. We demonstrate that the artificial neural networks generated by low discrepancy sequences can achieve an accuracy within reach of their dense counterparts at a much lower computational complexity.
  arXiv  Detail & Related papers  (2021-03-05T08:45:43Z)
• Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms [29.975118690758126]
  We describe the semi-output global dual of the two-layer vector-infinite ReLU neural network training problem. We provide a solution which is guaranteed to be exact for certain classes of problems.
  arXiv  Detail & Related papers  (2020-12-24T17:03:30Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Lossless Compression of Deep Neural Networks [17.753357839478575]
  Deep neural networks have been successful in many predictive modeling tasks, such as image and language recognition. It is challenging to deploy these networks under limited computational resources, such as in mobile devices. We introduce an algorithm that removes units and layers of a neural network while not changing the output that is produced.
  arXiv  Detail & Related papers  (2020-01-01T15:04:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.