Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions

• URL: http://arxiv.org/abs/2012.07197v2
• Date: Fri, 25 Dec 2020 15:03:01 GMT
• Title: Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions
• Authors: Jake Tuero, Michael Buro
• Abstract summary: Randomized algorithms are used in many state-of-the-art solvers for constraint satisfaction problems (CSP) and Boolean satisfiability (SAT) problems. Previous state-of-the-art methods directly try to predict a fixed parametric distribution that the input instance follows. This new model achieves robust predictive performance in the low observation setting, as well as handling censored observations.
• Score: 1.8275108630751844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized algorithms are used in many state-of-the-art solvers for constraint satisfaction problems (CSP) and Boolean satisfiability (SAT) problems. For many of these problems, there is no single solver which will dominate others. Having access to the underlying runtime distributions (RTD) of these solvers can allow for better use of algorithm selection, algorithm portfolios, and restart strategies. Previous state-of-the-art methods directly try to predict a fixed parametric distribution that the input instance follows. In this paper, we extend RTD prediction models into the Bayesian setting for the first time. This new model achieves robust predictive performance in the low observation setting, as well as handling censored observations. This technique also allows for richer representations which cannot be achieved by the classical models which restrict their output representations. Our model outperforms the previous state-of-the-art model in settings in which data is scarce, and can make use of censored data such as lower bound time estimates, where that type of data would otherwise be discarded. It can also quantify its uncertainty in its predictions, allowing for algorithm portfolio models to make better informed decisions about which algorithm to run on a particular instance.

Related papers

• Adaptive Sparse Gaussian Process [0.0]
  We propose the first adaptive sparse Gaussian Process (GP) able to address all these issues. We first reformulate a variational sparse GP algorithm to make it adaptive through a forgetting factor. We then propose updating a single inducing point of the sparse GP model together with the remaining model parameters every time a new sample arrives.
  arXiv  Detail & Related papers  (2023-02-20T21:34:36Z)
• RF+clust for Leave-One-Problem-Out Performance Prediction [0.9281671380673306]
  We study leave-one-problem-out (LOPO) performance prediction. We analyze whether standard random forest (RF) model predictions can be improved by calibrating them with a weighted average of performance values.
  arXiv  Detail & Related papers  (2023-01-23T16:14:59Z)
• Deep Subspace Encoders for Nonlinear System Identification [0.0]
  We propose a method which uses a truncated prediction loss and a subspace encoder for state estimation. We show that, under mild conditions, the proposed method is locally consistent, increases optimization stability, and achieves increased data efficiency.
  arXiv  Detail & Related papers  (2022-10-26T16:04:38Z)
• Interpretations Steered Network Pruning via Amortized Inferred Saliency Maps [85.49020931411825]
  Convolutional Neural Networks (CNNs) compression is crucial to deploying these models in edge devices with limited resources. We propose to address the channel pruning problem from a novel perspective by leveraging the interpretations of a model to steer the pruning process. We tackle this challenge by introducing a selector model that predicts real-time smooth saliency masks for pruned models.
  arXiv  Detail & Related papers  (2022-09-07T01:12:11Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Imputation-Free Learning from Incomplete Observations [73.15386629370111]
  We introduce the importance of guided gradient descent (IGSGD) method to train inference from inputs containing missing values without imputation. We employ reinforcement learning (RL) to adjust the gradients used to train the models via back-propagation. Our imputation-free predictions outperform the traditional two-step imputation-based predictions using state-of-the-art imputation methods.
  arXiv  Detail & Related papers  (2021-07-05T12:44:39Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)
• Reducing the Amortization Gap in Variational Autoencoders: A Bayesian Random Function Approach [38.45568741734893]
  Inference in our GP model is done by a single feed forward pass through the network, significantly faster than semi-amortized methods. We show that our approach attains higher test data likelihood than the state-of-the-arts on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-02-05T13:01:12Z)
• Neural Model-based Optimization with Right-Censored Observations [42.530925002607376]
  Neural networks (NNs) have been demonstrated to work well at the core of model-based optimization procedures. We show that our trained regression models achieve a better predictive quality than several baselines.
  arXiv  Detail & Related papers  (2020-09-29T07:32:30Z)
• Uncertainty Estimation Using a Single Deep Deterministic Neural Network [66.26231423824089]
  We propose a method for training a deterministic deep model that can find and reject out of distribution data points at test time with a single forward pass. We scale training in these with a novel loss function and centroid updating scheme and match the accuracy of softmax models.
  arXiv  Detail & Related papers  (2020-03-04T12:27:36Z)

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.