We describe a solution method for one of the most common anomaly detection formulations that is proven to be computationally efficient, universally consistent, and to guarantee near optimal finite sample performance for a large class of (practical) distributions. We also describe an algorithm for this method that accepts the desired accuracy (epsilon) as an input and produces an approximate solution that is guaranteed to satisfy this accuracy in low order polynomial time. Experimental results are used to demonstrate the actual run times for a typical problem.
D. Hush, P. Kelly, C. Scovel and I. Steinwart, Provably Fast Algorithms for Anomaly Detection. Los Alamos National Laboratory Technical Report LA-UR-05-4367, 2005. [ Abstract | Postscript (248 KB) | PDF (247 KB) ]
