  Inaccurate records of inventory occur frequently, and by some measures cost
retailers approximately 4% in annual sales. Detecting inventory inaccuracies
manually is cost-prohibitive, and existing algorithmic solutions rely almost
exclusively on learning from longitudinal data, which is insufficient in the
dynamic environment induced by modern retail operations. Instead, we propose a
solution based on cross-sectional data over stores and SKUs, observing that
detecting inventory inaccuracies can be viewed as a problem of identifying
anomalies in a (low-rank) Poisson matrix. State-of-the-art approaches to
anomaly detection in low-rank matrices apparently fall short. Specifically,
from a theoretical perspective, recovery guarantees for these approaches
require that non-anomalous entries be observed with vanishingly small noise
(which is not the case in our problem, and indeed in many applications).
  So motivated, we propose a conceptually simple entry-wise approach to anomaly
detection in low-rank Poisson matrices. Our approach accommodates a general
class of probabilistic anomaly models. We show that the cost incurred by our
algorithm approaches that of an optimal algorithm at a min-max optimal rate.
Using synthetic data and real data from a consumer goods retailer, we show that
our approach provides up to a 10x cost reduction over incumbent approaches to
anomaly detection. Along the way, we build on recent work that seeks entry-wise
error guarantees for matrix completion, establishing such guarantees for
sub-exponential matrices, a result of independent interest.
