Sampling is a key step of stochastic methods. In some contexts, minimizing the sample size can be of critical importance and determine by itself the viability of various approaches. Rethinking the way samples are generated can even lead to new algorithms, better suited than their alternatives to tackle specific real-world problems for which the sampling task is a costly step of the estimation process. For instance, strategies of formal verification and statistical model checking can be greatly improved by the use of adaptive stopping algorithms. Instead of initially computing the necessary sample size, those algorithms generate the samples progressively while continuously monitoring their progress along the way, allowing them to stop the sampling process as soon as possible. We present a generalization of two existing adaptive stopping algorithms for statistical model checking, and we show how this generalization can be exploited to derive tailor-made variations for specific use cases.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Adaptive Stopping Algorithms Based on Concentration Inequalities

  • Maxime Parmentier,
  • Axel Legay

摘要

Sampling is a key step of stochastic methods. In some contexts, minimizing the sample size can be of critical importance and determine by itself the viability of various approaches. Rethinking the way samples are generated can even lead to new algorithms, better suited than their alternatives to tackle specific real-world problems for which the sampling task is a costly step of the estimation process. For instance, strategies of formal verification and statistical model checking can be greatly improved by the use of adaptive stopping algorithms. Instead of initially computing the necessary sample size, those algorithms generate the samples progressively while continuously monitoring their progress along the way, allowing them to stop the sampling process as soon as possible. We present a generalization of two existing adaptive stopping algorithms for statistical model checking, and we show how this generalization can be exploited to derive tailor-made variations for specific use cases.