A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic

• URL: http://arxiv.org/abs/2410.12389v1
• Date: Wed, 16 Oct 2024 09:16:10 GMT
• Title: A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic
• Authors: Lennert De Smet, Pedro Zuidberg Dos Martires,
• Abstract summary: We formulate linear arithmetic over integer-valued random variables as tensor manipulations. We obtain a differentiable data structure, which unlocks, virtually for free, gradient-based learning.
• Score: 4.7223923266180785
• License:
• Abstract: As illustrated by the success of integer linear programming, linear integer arithmetic is a powerful tool for modelling combinatorial problems. Furthermore, the probabilistic extension of linear programming has been used to formulate problems in neurosymbolic AI. However, two key problems persist that prevent the adoption of neurosymbolic techniques beyond toy problems. First, probabilistic inference is inherently hard, #P-hard to be precise. Second, the discrete nature of integers renders the construction of meaningful gradients challenging, which is problematic for learning. In order to mitigate these issues, we formulate linear arithmetic over integer-valued random variables as tensor manipulations that can be implemented in a straightforward fashion using modern deep learning libraries. At the core of our formulation lies the observation that the addition of two integer-valued random variables can be performed by adapting the fast Fourier transform to probabilities in the log-domain. By relying on tensor operations we obtain a differentiable data structure, which unlocks, virtually for free, gradient-based learning. In our experimental validation we show that tensorising probabilistic linear integer arithmetic and leveraging the fast Fourier transform allows us to push the state of the art by several orders of magnitude in terms of inference and learning times.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Learning Linear Attention in Polynomial Time [115.68795790532289]
  We provide the first results on learnability of single-layer Transformers with linear attention. We show that linear attention may be viewed as a linear predictor in a suitably defined RKHS. We show how to efficiently identify training datasets for which every empirical riskr is equivalent to the linear Transformer.
  arXiv  Detail & Related papers  (2024-10-14T02:41:01Z)
• Tensor Completion via Integer Optimization [7.813563137863005]
  The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate.
  arXiv  Detail & Related papers  (2024-02-06T21:44:07Z)
• Accelerated Nonnegative Tensor Completion via Integer Programming [7.3149416054553065]
  We present an approach to nonnegative tensor completion based on integer programming. We explore several variants that can maintain the same theoretical guarantees as the algorithm, but offer potentially faster computation.
  arXiv  Detail & Related papers  (2022-11-28T21:00:25Z)
• AutoIP: A United Framework to Integrate Physics into Gaussian Processes [15.108333340471034]
  We propose a framework that can integrate all kinds of differential equations into Gaussian processes. Our method shows improvement upon vanilla GPs in both simulation and several real-world applications.
  arXiv  Detail & Related papers  (2022-02-24T19:02:14Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• Characterizing possible failure modes in physics-informed neural networks [55.83255669840384]
  Recent work in scientific machine learning has developed so-called physics-informed neural network (PINN) models. We demonstrate that, while existing PINN methodologies can learn good models for relatively trivial problems, they can easily fail to learn relevant physical phenomena even for simple PDEs. We show that these possible failure modes are not due to the lack of expressivity in the NN architecture, but that the PINN's setup makes the loss landscape very hard to optimize.
  arXiv  Detail & Related papers  (2021-09-02T16:06:45Z)
• Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units [86.9207811656179]
  We show that memory-augmented neural networks (NNs) can achieve higher-order, memory-augmented extrapolation, stable performance, and faster convergence. Our models achieve a 1.53% average improvement over current state-of-the-art methods in equation verification and achieve a 2.22% Top-1 average accuracy and 2.96% Top-5 average accuracy for equation completion.
  arXiv  Detail & Related papers  (2021-04-07T03:50:11Z)
• 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)
• A Solution for Large Scale Nonlinear Regression with High Rank and Degree at Constant Memory Complexity via Latent Tensor Reconstruction [0.0]
  This paper proposes a novel method for learning highly nonlinear, multivariate functions from examples. Our method takes advantage of the property that continuous functions can be approximated by bys, which in turn are representable by tensors. For learning the models, we present an efficient-based algorithm that can be implemented in linear time.
  arXiv  Detail & Related papers  (2020-05-04T14:49:14Z)

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.