AutoNumerics-Zero: Automated Discovery of State-of-the-Art Mathematical Functions

• URL: http://arxiv.org/abs/2312.08472v1
• Date: Wed, 13 Dec 2023 19:17:43 GMT
• Title: AutoNumerics-Zero: Automated Discovery of State-of-the-Art Mathematical Functions
• Authors: Esteban Real, Yao Chen, Mirko Rossini, Connal de Souza, Manav Garg, Akhil Verghese, Moritz Firsching, Quoc V. Le, Ekin Dogus Cubuk, David H. Park
• Abstract summary: Computers operate on few limited precision types, such as the popular float32. We show that when aiming for limited precision, existing approximation methods can be outperformed by programs automatically discovered from scratch by a simple evolutionary algorithm.
• Score: 46.36204442052778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computers calculate transcendental functions by approximating them through the composition of a few limited-precision instructions. For example, an exponential can be calculated with a Taylor series. These approximation methods were developed over the centuries by mathematicians, who emphasized the attainability of arbitrary precision. Computers, however, operate on few limited precision types, such as the popular float32. In this study, we show that when aiming for limited precision, existing approximation methods can be outperformed by programs automatically discovered from scratch by a simple evolutionary algorithm. In particular, over real numbers, our method can approximate the exponential function reaching orders of magnitude more precision for a given number of operations when compared to previous approaches. More practically, over float32 numbers and constrained to less than 1 ULP of error, the same method attains a speedup over baselines by generating code that triggers better XLA/LLVM compilation paths. In other words, in both cases, evolution searched a vast space of possible programs, without knowledge of mathematics, to discover previously unknown optimized approximations to high precision, for the first time. We also give evidence that these results extend beyond the exponential. The ubiquity of transcendental functions suggests that our method has the potential to reduce the cost of scientific computing applications.

Related papers

• Reverse That Number! Decoding Order Matters in Arithmetic Learning [49.5504492920404]
  Our work introduces a novel strategy that reevaluates the digit order by prioritizing output from the least significant digit. Compared to the previous state-of-the-art (SOTA) method, our findings reveal an overall improvement of in accuracy while requiring only a third of the tokens typically used during training.
  arXiv  Detail & Related papers  (2024-03-09T09:04:53Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• 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)
• Refining neural network predictions using background knowledge [68.35246878394702]
  We show we can use logical background knowledge in learning system to compensate for a lack of labeled training data. We introduce differentiable refinement functions that find a corrected prediction close to the original prediction. This algorithm finds optimal refinements on complex SAT formulas in significantly fewer iterations and frequently finds solutions where gradient descent can not.
  arXiv  Detail & Related papers  (2022-06-10T10:17:59Z)
• On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples [1.0650780147044159]
  Sparse approximation has become indispensable for approxing smooth, high-dimensional functions from limited samples. This paper introduces algorithms and theoretical guarantees that assert exponential or algebraic rates of convergence, along with robustness to sampling, algorithmic and physical discretization errors.
  arXiv  Detail & Related papers  (2022-03-25T20:56:07Z)
• Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
  One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. We introduce the formalism of encoding so called semi-booleans, which allows convenient generation of unsigned integer arithmetic quantum circuits. We extend this type of evaluation with additional features, such as ancilla-free in-place multiplication and integer coefficient evaluation.
  arXiv  Detail & Related papers  (2021-12-20T14:00:36Z)
• Efficient Evaluation of Exponential and Gaussian Functions on a Quantum Computer [0.0]
  We present algorithms for evaluating exponential and Gaussian functions efficiently on quantum computers. For a specific, realistic NISQ application, the Toffoli count of the exponential function is found to be reduced from 15,690 down to 912. Space requirements are also quite modest, to the extent that the aforementioned NISQ application can be implemented with as few as 71 logical qubits.
  arXiv  Detail & Related papers  (2021-10-12T00:06:51Z)
• Second-order Neural Network Training Using Complex-step Directional Derivative [41.4333906662624]
  We introduce a numerical algorithm for second-order neural network training. We tackle the practical obstacle of Hessian calculation by using the complex-step finite difference. We believe our method will inspire a wide-range of new algorithms for deep learning and numerical optimization.
  arXiv  Detail & Related papers  (2020-09-15T13:46:57Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)

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.