Accelerating Genetic Programming using GPUs

• URL: http://arxiv.org/abs/2110.11226v1
• Date: Fri, 15 Oct 2021 06:13:01 GMT
• Title: Accelerating Genetic Programming using GPUs
• Authors: Vimarsh Sathia (1), Venkataramana Ganesh (2), Shankara Rao Thejaswi Nanditale (2) ((1) Indian Institute of Technology Madras, (2) NVIDIA Corporation)
• Abstract summary: Genetic Programming (GP) has multiple applications in machine learning such as curve fitting, data modelling, feature selection, classification etc. This paper describes a GPU accelerated stack-based variant of the generational GP algorithm which can be used for symbolic regression and binary classification.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Genetic Programming (GP), an evolutionary learning technique, has multiple applications in machine learning such as curve fitting, data modelling, feature selection, classification etc. GP has several inherent parallel steps, making it an ideal candidate for GPU based parallelization. This paper describes a GPU accelerated stack-based variant of the generational GP algorithm which can be used for symbolic regression and binary classification. The selection and evaluation steps of the generational GP algorithm are parallelized using CUDA. We introduce representing candidate solution expressions as prefix lists, which enables evaluation using a fixed-length stack in GPU memory. CUDA based matrix vector operations are also used for computation of the fitness of population programs. We evaluate our algorithm on synthetic datasets for the Pagie Polynomial (ranging in size from $4096$ to $16$ million points), profiling training times of our algorithm with other standard symbolic regression libraries viz. gplearn, TensorGP and KarooGP. In addition, using $6$ large-scale regression and classification datasets usually used for comparing gradient boosting algorithms, we run performance benchmarks on our algorithm and gplearn, profiling the training time, test accuracy, and loss. On an NVIDIA DGX-A100 GPU, our algorithm outperforms all the previously listed frameworks, and in particular, achieves average speedups of $119\times$ and $40\times$ against gplearn on the synthetic and large scale datasets respectively.

Related papers

• Implementation and Analysis of GPU Algorithms for Vecchia Approximation [0.8057006406834466]
  Vecchia Approximation is widely used to reduce the computational complexity and can be calculated with embarrassingly parallel algorithms. While multi-core software has been developed for Vecchia Approximation, software designed to run on graphics processing units ( GPU) is lacking. We show that our new method outperforms the other two and then present it in the GpGpU R package.
  arXiv  Detail & Related papers  (2024-07-03T01:24:44Z)
• Large-Scale Gaussian Processes via Alternating Projection [23.79090469387859]
  We propose an iterative method which only accesses subblocks of the kernel matrix, effectively enabling mini-batching. Our algorithm, based on alternating projection, has $mathcalO(n)$ per-iteration time and space complexity, solving many of the practical challenges of scaling GPs to very large datasets.
  arXiv  Detail & Related papers  (2023-10-26T04:20:36Z)
• Local Optimization Often is Ill-conditioned in Genetic Programming for Symbolic Regression [0.0]
  We use a singular value decomposition of NLS Jacobian matrices to determine the numeric rank and the condition number. Our results show that rank-deficient and ill-conditioned Jacobian matrices occur frequently and for all datasets.
  arXiv  Detail & Related papers  (2022-09-02T10:39:26Z)
• Sparse Kernel Gaussian Processes through Iterative Charted Refinement (ICR) [0.0]
  We present a new, generative method named Iterative Charted Refinement (ICR) to model Gaussian Processes. ICR represents long- and short-range correlations by combining views of the modeled locations at varying resolutions with a user-provided coordinate chart. ICR outperforms existing methods in terms of computational speed by one order of magnitude on the CPU and GPU.
  arXiv  Detail & Related papers  (2022-06-21T18:00:01Z)
• Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times [119.41129787351092]
  We show that sequential black-box optimization based on GPs can be made efficient by sticking to a candidate solution for multiple evaluation steps. We modify two well-established GP-Opt algorithms, GP-UCB and GP-EI to adapt rules from batched GP-Opt.
  arXiv  Detail & Related papers  (2022-01-30T20:42:14Z)
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers [65.60007071024629]
  We show that Adaptive SGD outperforms four state-of-the-art solutions in time-to-accuracy. We show experimentally that Adaptive SGD outperforms four state-of-the-art solutions in time-to-accuracy.
  arXiv  Detail & Related papers  (2021-10-13T20:58:15Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Why Approximate Matrix Square Root Outperforms Accurate SVD in Global Covariance Pooling? [59.820507600960745]
  We propose a new GCP meta-layer that uses SVD in the forward pass, and Pad'e Approximants in the backward propagation to compute the gradients. The proposed meta-layer has been integrated into different CNN models and achieves state-of-the-art performances on both large-scale and fine-grained datasets.
  arXiv  Detail & Related papers  (2021-05-06T08:03:45Z)
• Exploiting Adam-like Optimization Algorithms to Improve the Performance of Convolutional Neural Networks [82.61182037130405]
  gradient descent (SGD) is the main approach for training deep networks. In this work, we compare Adam based variants based on the difference between the present and the past gradients. We have tested ensemble of networks and the fusion with ResNet50 trained with gradient descent.
  arXiv  Detail & Related papers  (2021-03-26T18:55:08Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16: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.