Worst-Case Analysis is Maximum-A-Posteriori Estimation

• URL: http://arxiv.org/abs/2310.09774v1
• Date: Sun, 15 Oct 2023 08:24:02 GMT
• Title: Worst-Case Analysis is Maximum-A-Posteriori Estimation
• Authors: Hongjun Wu and Di Wang
• Abstract summary: Worst-case resource usage of a program can provide useful information for many software-engineering tasks. This paper presents a generic, adaptive, and sound fuzzing framework, called DSE-SMC, for estimating worst-case resource usage.
• Score: 9.61085323616992
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The worst-case resource usage of a program can provide useful information for many software-engineering tasks, such as performance optimization and algorithmic-complexity-vulnerability discovery. This paper presents a generic, adaptive, and sound fuzzing framework, called DSE-SMC, for estimating worst-case resource usage. DSE-SMC is generic because it is black-box as long as the user provides an interface for retrieving resource-usage information on a given input; adaptive because it automatically balances between exploration and exploitation of candidate inputs; and sound because it is guaranteed to converge to the true resource-usage distribution of the analyzed program. DSE-SMC is built upon a key observation: resource accumulation in a program is isomorphic to the soft-conditioning mechanism in Bayesian probabilistic programming; thus, worst-case resource analysis is isomorphic to the maximum-a-posteriori-estimation problem of Bayesian statistics. DSE-SMC incorporates sequential Monte Carlo (SMC) -- a generic framework for Bayesian inference -- with adaptive evolutionary fuzzing algorithms, in a sound manner, i.e., DSE-SMC asymptotically converges to the posterior distribution induced by resource-usage behavior of the analyzed program. Experimental evaluation on Java applications demonstrates that DSE-SMC is significantly more effective than existing black-box fuzzing methods for worst-case analysis.

Related papers

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Monte Carlo Planning for Stochastic Control on Constrained Markov Decision Processes [1.445706856497821]
  This work defines an MDP framework, the textttSD-MDP, where we disentangle the causal structure of MDPs' transition and reward dynamics. We derive theoretical guarantees on the estimation error of the value function under an optimal policy by allowing independent value estimation from Monte Carlo sampling.
  arXiv  Detail & Related papers  (2024-06-23T16:22:40Z)
• Worst-Case Convergence Time of ML Algorithms via Extreme Value Theory [8.540426791244533]
  This paper leverages the statistics of extreme values to predict the worst-case convergence times of machine learning algorithms. Timing is a critical non-functional property of ML systems, and providing the worst-case converge times is essential to guarantee the availability of ML and its services.
  arXiv  Detail & Related papers  (2024-04-10T17:05:12Z)
• Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees [18.7083987727973]
  Satisfiability Modulo Counting (SMC) encompasses problems that require both symbolic decision-making and statistical reasoning. XOR-SMC transforms the highly intractable SMC into satisfiability problems, by replacing the model counting in SMC with SAT formulae. XOR-SMC finds solutions close to the true optimum, outperforming several baselines which struggle to find good approximations for the intractable model counting in SMC.
  arXiv  Detail & Related papers  (2023-09-16T05:34:59Z)
• Data-driven Piecewise Affine Decision Rules for Stochastic Programming with Covariate Information [5.054099828483128]
  We propose an empirical risk (M) method embedded within a non piecewise decision (PADR) We show that the proposed PADR-based method applies to a broad, non-class non-constrained problem with theoretical consistency.
  arXiv  Detail & Related papers  (2023-04-26T16:08:49Z)
• Adaptive sparseness for correntropy-based robust regression via automatic relevance determination [17.933460891374498]
  We integrate the maximum correntropy criterion (MCC) based robust regression algorithm with the automatic relevance determination (ARD) technique in a Bayesian framework. We use an inherent noise assumption from the MCC to derive an explicit likelihood function, and realize the maximum a posteriori (MAP) estimation with the ARD prior. MCC-ARD achieves superior prediction performance and feature selection capability than L1-regularized MCC, as demonstrated by a noisy and high-dimensional simulation study.
  arXiv  Detail & Related papers  (2023-01-31T20:23:32Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  We study the problem of single-channel source separation (SCSS) We focus on cyclostationary signals, which are particularly suitable in a variety of application domains. We propose a deep learning approach using a U-Net architecture, which is competitive with the minimum MSE estimator.
  arXiv  Detail & Related papers  (2022-08-22T14:04:56Z)
• Estimating Average Treatment Effects with Support Vector Machines [77.34726150561087]
  Support vector machine (SVM) is one of the most popular classification algorithms in the machine learning literature. We adapt SVM as a kernel-based weighting procedure that minimizes the maximum mean discrepancy between the treatment and control groups. We characterize the bias of causal effect estimation arising from this trade-off, connecting the proposed SVM procedure to the existing kernel balancing methods.
  arXiv  Detail & Related papers  (2021-02-23T20:22:56Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.