Fast and close Shannon entropy approximation

• URL: http://arxiv.org/abs/2505.14234v1
• Date: Tue, 20 May 2025 11:41:26 GMT
• Title: Fast and close Shannon entropy approximation
• Authors: Illia Horenko, Davide Bassetti, Lukáš Pospíšil,
• Abstract summary: A non-singular rational approximation of Shannon entropy and its gradient achieves a mean absolute error of $10-3$.<n>FEA allows around $50%$ faster computation, requiring only $5$ to $6$ elementary computational operations.<n>On a set of common benchmarks for the feature selection problem in machine learning, we show that the combined effect of fewer elementary operations, low approximation error, and a non-singular gradient allows significantly better model quality.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Shannon entropy (SE) and its quantum mechanical analogue von Neumann entropy are key components in many tools used in physics, information theory, machine learning (ML) and quantum computing. Besides of the significant amounts of SE computations required in these fields, the singularity of the SE gradient is one of the central mathematical reason inducing the high cost, frequently low robustness and slow convergence of such tools. Here we propose the Fast Entropy Approximation (FEA) - a non-singular rational approximation of Shannon entropy and its gradient that achieves a mean absolute error of $10^{-3}$, which is approximately $20$ times lower than comparable state-of-the-art methods. FEA allows around $50\%$ faster computation, requiring only $5$ to $6$ elementary computational operations, as compared to tens of elementary operations behind the fastest entropy computation algorithms with table look-ups, bitshifts, or series approximations. On a set of common benchmarks for the feature selection problem in machine learning, we show that the combined effect of fewer elementary operations, low approximation error, and a non-singular gradient allows significantly better model quality and enables ML feature extraction that is two to three orders of magnitude faster and computationally cheaper when incorporating FEA into AI tools.

Related papers

• Gradient-Based Excitation Filter for Molecular Ground-State Simulation [6.627541720714792]
  We introduce a method to efficiently simplify the Unitary Coupled-Cluster with Single and Double Excitations (UCCSD) ansatz on classical computers.<n>We demonstrate that our approach achieves up to $46%$ parameter decrease, $60%$ circuit depth reduction and $678times runtime.
  arXiv  Detail & Related papers  (2025-06-25T13:12:45Z)
• Neural Estimation for Scaling Entropic Multimarginal Optimal Transport [14.389645696715599]
  We propose a new computational framework for entropic MOT, dubbed Neural Entropic MOT (NEMOT)<n>NEMOT employs neural networks trained using mini-batches, which transfers the computational complexity from the dataset size to the size of the mini-batch, leading to substantial gains.<n>In particular, orders-of-magnitude speedups are observed relative to the state-of-the-art, with a notable increase in the feasible number of samples and marginals.
  arXiv  Detail & Related papers  (2025-05-31T14:10:27Z)
• Enabling Automatic Differentiation with Mollified Graph Neural Operators [75.3183193262225]
  We propose the mollified graph neural operator (mGNO), the first method to leverage automatic differentiation and compute emphexact gradients on arbitrary geometries.<n>For a PDE example on regular grids, mGNO paired with autograd reduced the L2 relative data error by 20x compared to finite differences.<n>It can also solve PDEs on unstructured point clouds seamlessly, using physics losses only, at resolutions vastly lower than those needed for finite differences to be accurate enough.
  arXiv  Detail & Related papers  (2025-04-11T06:16:30Z)
• Slow Invariant Manifolds of Singularly Perturbed Systems via Physics-Informed Machine Learning [0.0]
  We present a physics-informed machine-learning (PIML) approach for the approximation of slow invariant manifold (SIMs) of singularly perturbed systems. We show that the proposed PIML scheme provides approximations, of equivalent or even higher accuracy, than those provided by other traditional GSPT-based methods. A comparison of the computational costs between symbolic, automatic and numerical approximation of the required derivatives in the learning process is also provided.
  arXiv  Detail & Related papers  (2023-09-14T14:10:22Z)
• Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
  We introduce a numerically exact algorithm to calculate process tensors. Our approach requires only $mathcalO(nlog n)$ singular value decompositions for environments with infinite memory.
  arXiv  Detail & Related papers  (2023-04-11T15:40:33Z)
• Towards provably efficient quantum algorithms for large-scale machine-learning models [11.440134080370811]
  We show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms. We benchmark instances of large machine learning models from 7 million to 103 million parameters.
  arXiv  Detail & Related papers  (2023-03-06T19:00:27Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Function Approximation for High-Energy Physics: Comparing Machine Learning and Interpolation Methods [0.0]
  In high-energy physics, the precise computation of the scattering cross-section of a process requires the evaluation of computationally intensive integrals. A variety of methods in machine learning have been used to tackle this problem, but often the motivation of using one method over another is lacking. We consider four and three machine learning techniques and compare their performance on three toy functions.
  arXiv  Detail & Related papers  (2021-11-29T18:43:57Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
  We study two different methods to prepare excited states on a quantum computer. We benchmark these techniques on emulated and real quantum devices. These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
  arXiv  Detail & Related papers  (2020-09-28T17:21:25Z)

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.