Level set estimation (LSE), the problem of identifying the set of input
points where a function takes value above (or below) a given threshold, is
important in practical applications. When the function is expensive-to-evaluate
and black-box, the \textit{straddle} algorithm, which is a representative
heuristic for LSE based on Gaussian process models, and its extensions having
theoretical guarantees have been developed. However, many of existing methods
include a confidence parameter
βt1/2 that must be specified by the
user, and methods that choose
βt1/2 heuristically do not provide
theoretical guarantees. In contrast, theoretically guaranteed values of
βt1/2 need to be increased depending on the number of iterations and
candidate points, and are conservative and not good for practical performance.
In this study, we propose a novel method, the \textit{randomized straddle}
algorithm, in which
βt in the straddle algorithm is replaced by a random
sample from the chi-squared distribution with two degrees of freedom. The
confidence parameter in the proposed method has the advantages of not needing
adjustment, not depending on the number of iterations and candidate points, and
not being conservative. Furthermore, we show that the proposed method has
theoretical guarantees that depend on the sample complexity and the number of
iterations. Finally, we confirm the usefulness of the proposed method through
numerical experiments using synthetic and real data.