Timezone: »
Nearest-neighbor (NN) procedures are well studied and widely used in both supervised and unsupervised learning problems. In this paper we are concerned with investigating the performance of NN-based methods for anomaly detection. We first show through extensive simulations that NN methods compare favorably to some of the other state-of-the-art algorithms for anomaly detection based on a set of benchmark synthetic datasets. We further consider the performance of NN methods on real datasets, and relate it to the dimensionality of the problem. Next, we analyze the theoretical properties of NN-methods for anomaly detection by studying a more general quantity called distance-to-measure (DTM), originally developed in the literature on robust geometric and topological inference. We provide finite-sample uniform guarantees for the empirical DTM and use them to derive misclassification rates for anomalous observations under various settings. In our analysis we rely on Huber's contamination model and formulate mild geometric regularity assumptions on the underlying distribution of the data.
Author Information
Xiaoyi Gu (Carnegie Mellon University)
Leman Akoglu (CMU)
Alessandro Rinaldo (CMU)
More from the Same Authors
-
2022 Spotlight: Lightning Talks 1B-4 »
Andrei Atanov · Shiqi Yang · Wanshan Li · Yongchang Hao · Ziquan Liu · Jiaxin Shi · Anton Plaksin · Jiaxiang Chen · Ziqi Pan · yaxing wang · Yuxin Liu · Stepan Martyanov · Alessandro Rinaldo · Yuhao Zhou · Li Niu · Qingyuan Yang · Andrei Filatov · Yi Xu · Liqing Zhang · Lili Mou · Ruomin Huang · Teresa Yeo · kai wang · Daren Wang · Jessica Hwang · Yuanhong Xu · Qi Qian · Hu Ding · Michalis Titsias · Shangling Jui · Ajay Sohmshetty · Lester Mackey · Joost van de Weijer · Hao Li · Amir Zamir · Xiangyang Ji · Antoni Chan · Rong Jin -
2022 Spotlight: Detecting Abrupt Changes in Sequential Pairwise Comparison Data »
Wanshan Li · Alessandro Rinaldo · Daren Wang -
2022 Poster: Hyperparameter Sensitivity in Deep Outlier Detection: Analysis and a Scalable Hyper-Ensemble Solution »
Xueying Ding · Lingxiao Zhao · Leman Akoglu -
2022 Poster: Detecting Abrupt Changes in Sequential Pairwise Comparison Data »
Wanshan Li · Alessandro Rinaldo · Daren Wang -
2022 Poster: A Practical, Progressively-Expressive GNN »
Lingxiao Zhao · Neil Shah · Leman Akoglu -
2022 Poster: Dual-discriminative Graph Neural Network for Imbalanced Graph-level Anomaly Detection »
GE ZHANG · Zhenyu Yang · Jia Wu · Jian Yang · Shan Xue · Hao Peng · Jianlin Su · Chuan Zhou · Quan Z. Sheng · Leman Akoglu · Charu Aggarwal -
2021 Poster: Lattice partition recovery with dyadic CART »
OSCAR HERNAN MADRID PADILLA · Yi Yu · Alessandro Rinaldo -
2021 Poster: Automatic Unsupervised Outlier Model Selection »
Yue Zhao · Ryan Rossi · Leman Akoglu -
2020 Poster: Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs »
Jiong Zhu · Yujun Yan · Lingxiao Zhao · Mark Heimann · Leman Akoglu · Danai Koutra -
2019 Poster: Are sample means in multi-armed bandits positively or negatively biased? »
Jaehyeok Shin · Aaditya Ramdas · Alessandro Rinaldo -
2019 Spotlight: Are sample means in multi-armed bandits positively or negatively biased? »
Jaehyeok Shin · Aaditya Ramdas · Alessandro Rinaldo -
2017 : Persistent homology of KDE filtration of Rips complexes »
Jaehyeok Shin · Alessandro Rinaldo -
2017 Poster: A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening »
Kevin Lin · James Sharpnack · Alessandro Rinaldo · Ryan Tibshirani -
2016 Poster: Statistical Inference for Cluster Trees »
Jisu KIM · Yen-Chi Chen · Sivaraman Balakrishnan · Alessandro Rinaldo · Larry Wasserman -
2013 Poster: Cluster Trees on Manifolds »
Sivaraman Balakrishnan · Srivatsan Narayanan · Alessandro Rinaldo · Aarti Singh · Larry Wasserman -
2012 Workshop: Algebraic Topology and Machine Learning »
Sivaraman Balakrishnan · Alessandro Rinaldo · Donald Sheehy · Aarti Singh · Larry Wasserman -
2011 Poster: Minimax Localization of Structural Information in Large Noisy Matrices »
Mladen Kolar · Sivaraman Balakrishnan · Alessandro Rinaldo · Aarti Singh -
2011 Spotlight: Minimax Localization of Structural Information in Large Noisy Matrices »
Mladen Kolar · Sivaraman Balakrishnan · Alessandro Rinaldo · Aarti Singh