  We propose a novel non-parametric adaptive anomaly detection algorithm for
high dimensional data based on rank-SVM. Data points are first ranked based on
scores derived from nearest neighbor graphs on n-point nominal data. We then
train a rank-SVM using this ranked data. A test-point is declared as an anomaly
at alpha-false alarm level if the predicted score is in the alpha-percentile.
The resulting anomaly detector is shown to be asymptotically optimal and
adaptive in that for any false alarm rate alpha, its decision region converges
to the alpha-percentile level set of the unknown underlying density. In
addition we illustrate through a number of synthetic and real-data experiments
both the statistical performance and computational efficiency of our anomaly
detector.
