Scalable Anomaly Detection in Large Homogenous Populations
This addresses the challenge of efficiently detecting anomalies in large-scale systems, which is incremental as it builds on existing optimization approaches.
The authors tackled the problem of scalable anomaly detection in large homogenous populations by formulating it as a multi-hypothesis combinatorial optimization problem and relaxing it into a convex, distributable solution that remains computationally tractable as the number of systems increases, with the relaxation shown to be tight under certain conditions.
Anomaly detection in large populations is a challenging but highly relevant problem. The problem is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and anomal systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problems of practical interests. In the current paper we take an optimization approach to this multi-hypothesis problem. We first observe that the problem is equivalent to a non-convex combinatorial optimization problem. We then relax the problem to a convex problem that can be solved distributively on the systems and that stays computationally tractable as the number of systems increase. An interesting property of the proposed method is that it can under certain conditions be shown to give exactly the same result as the combinatorial multi-hypothesis problem and the relaxation is hence tight.