Over the past decade, new types of estimators have been developed in statistics, signal processing and system identification, which apply tools from supervised learning, such as deep neural networks or kernel regression on synthetic data. In spite of their competitive performance, a systematic finite-sample analysis of these so-called data-driven estimators is still missing. In this paper, we take first steps in this direction by deriving finite-sample bounds for a specific data-driven estimator, known as the Two-Stage method. The derived bounds hold under fairly general conditions, and highlight the effect of different user choices involved in the construction of this estimator.

Many industrial and security applications employ a suite of sensors for detecting abrupt changes in temporal behavior patterns. These abrupt changes typically manifest locally, rendering only a small subset of sensors informative. Continuous monitoring of every sensor can be expensive due to resource constraints, and serves as a motivation for the bandit quickest changepoint detection problem, where sensing actions (or sensors) are sequentially chosen, and only measurements corresponding to chosen actions are observed. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We then propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions. We derive expected delay bounds for the proposed scheme and show that these bounds match our information-theoretic lower bounds at low false alarm rates, establishing optimality of the proposed method. We then perform a number of experiments on synthetic and real datasets demonstrating the effectiveness of our proposed method.