  Identifying dependency in multivariate data is a common inference task that
arises in numerous applications. However, existing nonparametric independence
tests typically require computation that scales at least quadratically with the
sample size, making it difficult to apply them to massive data. Moreover,
resampling is usually necessary to evaluate the statistical significance of the
resulting test statistics at finite sample sizes, further worsening the
computational burden. We introduce a scalable, resampling-free approach to
testing the independence between two random vectors by breaking down the task
into simple univariate tests of independence on a collection of 2x2 contingency
tables constructed through sequential coarse-to-fine discretization of the
sample space, transforming the inference task into a multiple testing problem
that can be completed with almost linear complexity with respect to the sample
size. To address increasing dimensionality, we introduce a coarse-to-fine
sequential adaptive procedure that exploits the spatial features of dependency
structures to more effectively examine the sample space. We derive a
finite-sample theory that guarantees the inferential validity of our adaptive
procedure at any given sample size. In particular, we show that our approach
can achieve strong control of the family-wise error rate without resampling or
large-sample approximation. We demonstrate the substantial computational
advantage of the procedure in comparison to existing approaches as well as its
decent statistical power under various dependency scenarios through an
extensive simulation study, and illustrate how the divide-and-conquer nature of
the procedure can be exploited to not just test independence but to learn the
nature of the underlying dependency. Finally, we demonstrate the use of our
method through analyzing a large data set from a flow cytometry experiment.
