FOUNDATIONAL PRINCIPLES FOR LARGE SCALE INFERENCE ...

1 FOUNDATIONAL PRINCIPLES FOR LARGE SCALE INFERENCE : ILLUSTRATIONS THROUGH CORRELATION MINING By Alfred O. Hero Bala Rajaratnam Technical Report No. 2015-13 May 2015 Department of Statistics STANFORD UNIVERSITY Stanford, California 94305-4065 FOUNDATIONAL PRINCIPLES FOR LARGE SCALE INFERENCE : ILLUSTRATIONS THROUGH CORRELATION MINING By Alfred O. Hero University of Michigan Ann Arbor Bala Rajaratnam Stanford University Technical Report No. 2015-13 May 2015 This research was supported in part by National Science Foundation grants DMS 0906392, CMG 1025465, AGS 1003823, and DMS 1106642. Department of Statistics STANFORD UNIVERSITY Stanford, California 94305-4065 FOUNDATIONAL PRINCIPLES for LARGE SCALE INFERENCE :Illustrations through correlation miningAlfred O. Hero and Bala Rajaratnam University of Michigan, Ann Arbor, MI 48109-2122, USA Stanford University, Stanford, CA 94305-4065, USAA bstractWhen can reliable INFERENCE be drawn in the Big Data context?

2 This paper presents aframework for answering this fundamental question in the context of correlation mining,with implications for general LARGE SCALE INFERENCE . In LARGE SCALE data applications likegenomics, connectomics, and eco-informatics the dataset is often variable-rich but sample-starved: a regime where the numbernof acquired samples ( statistical replicates) is far fewerthan the numberpof observed variables (genes, neurons, voxels, or chemical constituents).Much of recent work has focused on understanding the computational complexity of proposedmethods for Big Data . Sample complexity however has received relatively less attention,especially in the setting when the sample sizenis fixed, and the dimensionpgrows withoutbound. To address this gap, we develop a unified statistical framework that explicitly quanti-fies the sample complexity of various inferential tasks. Sampling regimes can be divided intoseveral categories: 1) the classical asymptotic regime where the variable dimension is fixedand the sample size goes to infinity; 2) the mixed asymptotic regime where both variabledimension and sample size go to infinity at comparable rates; 3) the purely high dimensionalasymptotic regime where the variable dimension goes to infinity and the sample size is regime has its niche but only the latter regime applies to exa- SCALE data illustrate this high dimensional framework for the problem of correlation mining, whereit is the matrix of pairwise and partial correlations among the variables that are of mining arises in numerous applications and subsumes the regression context asa special case.

3 We demonstrate various regimes of correlation mining based on the unifyingperspective of high dimensional learning rates and sample complexity for different structuredcovariance models and different INFERENCE : LARGE SCALE INFERENCE , Big Data, sample complexity, asymptotic regimes,purely high dimensional, unifying learning theory, triple asymptotic framework, correlationmining, correlation estimation, correlation selection, correlation screening, graphical [ ] 18 May 2015 This paper is to appear in the Proceedings of the IEEE: Special Issue on Big IntroductionThe increasing availability of LARGE SCALE and high dimensional data is driving a major resur-gence of data science, recently rebranded under the moniker Big Data [90]. There hasbeen a preponderance of catch phrases such as big-data-biology, ecoinformatics, pre-cision medicine, data-driven decision-making, Big Data business analytics in scientificpublications and the media.

4 However, until recently, most of the research in Big Data hasconcentrated on issues of data management, data warehousing, computational data analysis,and end-user data utilization [129], [93], [96]. While the data management research commu-nity has made progress on the problem of quality assurance, , associated with provenanceand computer errors [80], the issue of limited sample size and statistical reproducibility re-mains largely open. This issue has been recognized as one of the principal hurdles that standin the way of success of the scientific enterprise [154], [116]. The negative consequences ofinsufficient samples can be especially dire when the data is high dimensional, heterogenousand uncalibrated [26], [91]. It is therefore both important and timely to address the problemof INFERENCE on Big Data from the point of view of statistical statistical reproducibility point of view is founded on a non-monolithic notion of BigData: the data should be considered as a matrix withpcolumns andnrows indexed by,respectively,pvariables over each of the data fields andnindependent samples of these vari-ables.

5 If there is only a single sample then the matrix collapses to a vector and no statisticalanalysis of reproducibility can be performed. With larger sample size, the probability ofreproducibility can be studied in the context of the statistical theory of random we develop this perspective for a particular Big Data problem: correlation miningin high dimension where the number of samples is much smaller than the dimension, asetting that we call sampled starved. Correlation mining is an area of data mining wherethe objective is to discover patterns of correlation between a LARGE number (p) of observedvariables based on a limited number (n) of samples. Correlation mining can be framed as themathematical problem of reliably reconstructing different attributes of the correlation matrixof the population from the sample covariance matrix that is empirically constructed fromthep ndata matrix. The INFERENCE task depends on the attributes of the correlation thatare of interest, while the performance of a correlation mining algorithm for a particular taskdepends on the number of samples and the underlying structure of the population high dimensional settings wherep n, correlation mining presents significant challengesto the practitioner, both in terms of unavailability of computationally tractable algorithmsand in terms of lack theory that could be used to specify sample size requirements.

6 Thispaper will provide some perspective on the latter matrices arise in a very diverse set of Big Data applications including: em-pirical finance and econometrics [84], [85], [86], [127], [14], [44]; MIMO radar and commu-nications [54], [51], [77], [13], [48], [89],[62], [12]; image analysis [49],[92],[18],[152]; networksensing [137], [17], [102], [103], [19], [21]; life and biomedical sciences [94], [136], [2], [118],[79], [156], [106]; and climate science [55], [145], [119], [122], to name just a few. However,covariance matrices are used differently depending on the application and the task. Fortracking of targets from space-time-adaptive-radar (STAP) the task is to estimate the entire2covariance matrix in so far as it yields estimates of eigenvectors that span the signal (target)subspace [53]. For exploring functional gene regulation networks the task is to determine thematrix locations of the largest pairwise correlations or inverse correlations, often obtainedby thresholding the sample correlation matrix [61] or by performing sparsity constrained op-timization [7], [47].

7 In linear discriminant analysis the task is to estimate a quadratic formof the inverse covariance matrix [19], [97]. In anomaly detection, it is the Schur complementof the covariance matrix that is of interest as it is related to residual prediction error covari-ance [150]. In independence screening one is interested in the support of the non-zero rowsof the covariance [36]. In variable selection for prediction it is the support of the regressioncoefficient vector that is of interest [37] (a setting in which correlation mining subsumes theregression context as a special case).Of central importance for all of these applications are the sample size requirements, whichcan differ from task to task. Reliably performing some of these correlation mining tasks mightrequire relatively few samples, , screening for the presence of variables that are hubs ofhigh correlation in a sparsely correlated population, while other tasks might require manymore samples, , accurately estimating all entries of the inverse covariance matrix in adensely correlated population.

8 A theoretical framework has been emerging for predictingthese sampling requirements as a function of the population correlation structure and as afunction of the INFERENCE task. The principal aim of this paper is to present building blocksof this framework with an emphasis on the high dimensional setting where the numberpof variables is much larger than the numbernof samples (p n), a setting relevant tocorrelation mining in massive data real-world examples of this high dimensional setting are given below: In studies of correlation networks of the annotated human genomepis on the orderof tens of thousands of genes whilenis typically fewer than a hundred samples, ,corresponding to a population of human subjects. In these studies correlation levelsof magnitude as low as are sometimes considered significant [30], though some ofthem may actually be spurious. In space-time-adaptive-processing (STAP) radar a spatio-temporal covariance matrixis used to filter out clutter in order to better detect a moving target at a particularrange and Doppler frequency.

9 For full degrees-of-freedom (DOF) STAP the estimatorof the spatio-temporal clutter covariance can have dimensionp=rqon the order ofhundreds of thousands and the number of samplesnunder a hundred. Hereris thenumber of radar pulses (time),qis the number of elements in the radar array (space),andnis the number of range bins in the vicinity of the target [53],[89]. For spambot network discovery from honeypot data, correlation of spamming profilesis performed betweenp= hundreds of thousands of known IP addresses while thenumber of time points in each profile may only be on the order ofn= 30 [153]. In recommender systems preference vectors ofp= millions of subscribers are correlatedwith other subscribers on the basis ofn= a few hundred preference categories, ,movies or music, to predict future user preferences [78], [64].3 In fMRI connectomics a long term goal is to correlate brain activations across individualbrain neurons, ,p= 1011.

10 Currently connectome researchers might parcel thebrain intopregions, withp= several thousand, and estimate correlation by averagingovern= hundreds of repeated activation stimuli. The objective is to use the samplecorrelation matrix to study patterns of activation in order to reveal the brain network [125], [133].Therefore, it is not an exaggeration to say that correlation mining practitioners face adeluge of variables with very limited sample size. With so few samples one is bound to findspurious correlations between some pairs of the many variables. It is therefore essential tounderstand the intrinsic sampling requirements of such statistical INFERENCE problems. Thestudy of sampling requirements falls into several different asymptotic regimes. Classicalstatistical error prediction and control methods are based on an asymptotic regime wherethe dimensionpis fixed and the sample sizengoes to infinity.