  Anomaly estimation, or the problem of finding a subset of a dataset that
differs from the rest of the dataset, is a classic problem in machine learning
and data mining. In both theoretical work and in applications, the anomaly is
assumed to have a specific structure defined by membership in an
$\textit{anomaly family}$. For example, in temporal data the anomaly family may
be time intervals, while in network data the anomaly family may be connected
subgraphs. The most prominent approach for anomaly estimation is to compute the
Maximum Likelihood Estimator (MLE) of the anomaly; however, it was recently
observed that for normally distributed data, the MLE is a $\textit{biased}$
estimator for some anomaly families. In this work, we demonstrate that in the
normal means setting, the bias of the MLE depends on the size of the anomaly
family. We prove that if the number of sets in the anomaly family that contain
the anomaly is sub-exponential, then the MLE is asymptotically unbiased. We
also provide empirical evidence that the converse is true: if the number of
such sets is exponential, then the MLE is asymptotically biased. Our analysis
unifies a number of earlier results on the bias of the MLE for specific anomaly
families. Next, we derive a new anomaly estimator using a mixture model, and we
prove that our anomaly estimator is asymptotically unbiased regardless of the
size of the anomaly family. We illustrate the advantages of our estimator
versus the MLE on disease outbreak and highway traffic data.
