Minimax-Optimal Algorithms for Detecting Changes in Statistically Periodic Random Processes
Theory and algorithms are developed for detecting changes in the distribution of statistically periodic random processes. The statistical periodicity is modeled using independent and periodically identically distributed processes, a new class of stochastic processes proposed by us. An algorithm is developed that is minimax asymptotically optimal as the false alarm rate goes to zero. Algorithms are also developed for the cases when the post-change distribution is not known or when there are multiple streams of observations. The modeling is inspired by real datasets encountered in cyber-physical systems, biology, and medicine. The developed algorithms are applied to sequences of Instagram counts collected around a 5K run in New York City to detect the run.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms
We study distributed estimation of a Gaussian mean under communication constraints in a decision theoretical framework. Minimax rates of convergence, which characterize the tradeoff between the communication costs and st…
Novelty Detection in Time Series via Weak Innovations Representation: A Deep Learning Approach
We consider novelty detection in time series with unknown and nonparametric probability structures. A deep learning approach is proposed to causally extract an innovations sequence consisting of novelty samples statistic…
Novelty DetectionTime SeriesTime Series AnalysisOptimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization
Algorithmic reproducibility measures the deviation in outputs of machine learning algorithms upon minor changes in the training process. Previous work suggests that first-order methods would need to trade-off convergence…
Minimax Rates and Efficient Algorithms for Noisy Sorting
There has been a recent surge of interest in studying permutation-based models for ranking from pairwise comparison data. Despite being structurally richer and more robust than parametric ranking models, permutation-base…
Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and s…