Finite Sample Complexity of Rare Pattern Anomaly Detection

Md Amran Siddiqui Oregon Sate University, Alan Fern, Thomas Dietterich Oregon State University, Shubhomoy Das Oregon State University
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:612-621, 2016.

Abstract

Anomaly detection is a fundamental problem for which a wide variety of algorithms have been developed. However, compared to supervised learning, there has been very little work aimed at understanding the sample complexity of anomaly detection. In this paper, we take a step in this direction by introducing a Probably Approximately Correct (PAC) framework for anomaly detection based on the identification of rare patterns. In analogy with the PAC framework for supervised learning, we develop sample complexity results that relate the complexity of the pattern space to the data requirements needed for PAC guarantees. We instantiate the general result for a number of pattern spaces, some of which are implicit in current state-of-the-art anomaly detectors. Finally, we design a new simple anomaly detection algorithm motivated by our analysis and show experimentally on several benchmark problems that it is competitive with a state-of-the-art detector using the same pattern space.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-university16o, title = {Finite Sample Complexity of Rare Pattern Anomaly Detection}, author = {University, Md Amran Siddiqui Oregon Sate and Fern, Alan and University, Thomas Dietterich Oregon State and University, Shubhomoy Das Oregon State}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {612--621}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/university16o/university16o.pdf}, url = {https://proceedings.mlr.press/r14/university16o.html}, abstract = {Anomaly detection is a fundamental problem for which a wide variety of algorithms have been developed. However, compared to supervised learning, there has been very little work aimed at understanding the sample complexity of anomaly detection. In this paper, we take a step in this direction by introducing a Probably Approximately Correct (PAC) framework for anomaly detection based on the identification of rare patterns. In analogy with the PAC framework for supervised learning, we develop sample complexity results that relate the complexity of the pattern space to the data requirements needed for PAC guarantees. We instantiate the general result for a number of pattern spaces, some of which are implicit in current state-of-the-art anomaly detectors. Finally, we design a new simple anomaly detection algorithm motivated by our analysis and show experimentally on several benchmark problems that it is competitive with a state-of-the-art detector using the same pattern space.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Finite Sample Complexity of Rare Pattern Anomaly Detection %A Md Amran Siddiqui Oregon Sate University %A Alan Fern %A Thomas Dietterich Oregon State University %A Shubhomoy Das Oregon State University %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-university16o %I PMLR %P 612--621 %U https://proceedings.mlr.press/r14/university16o.html %V R14 %X Anomaly detection is a fundamental problem for which a wide variety of algorithms have been developed. However, compared to supervised learning, there has been very little work aimed at understanding the sample complexity of anomaly detection. In this paper, we take a step in this direction by introducing a Probably Approximately Correct (PAC) framework for anomaly detection based on the identification of rare patterns. In analogy with the PAC framework for supervised learning, we develop sample complexity results that relate the complexity of the pattern space to the data requirements needed for PAC guarantees. We instantiate the general result for a number of pattern spaces, some of which are implicit in current state-of-the-art anomaly detectors. Finally, we design a new simple anomaly detection algorithm motivated by our analysis and show experimentally on several benchmark problems that it is competitive with a state-of-the-art detector using the same pattern space. %Z Reissued by PMLR on 04 October 2026.
APA
University, M.A.S.O.S., Fern, A., University, T.D.O.S. & University, S.D.O.S.. (2016). Finite Sample Complexity of Rare Pattern Anomaly Detection. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:612-621 Available from https://proceedings.mlr.press/r14/university16o.html. Reissued by PMLR on 04 October 2026.

Related Material