Distributed Estimation and Gap-Free Analysis of Canonical Correlations
Canyi Chen [email protected], Liping Zhu [email protected] · 2024
Read Distributed Estimation and Gap-Free Analysis of Canonical Correlations by Canyi Chen [email protected], Liping Zhu [email protected] (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17792.txt.
Introduction
Chen and Zhu design in twenty twenty-four a way to run canonical correlation analysis, a method that finds linked patterns in two datasets, across many machines. Big data often sits split across sites, so the analysis must travel well. Their multi-round scheme builds the key directions through a convex route and uses a preconditioning trick to converge fast while sending little data.
The estimate matches the accuracy of pooling all data in one place, without strict caps on machine count. Their theory drops a common but unrealistic assumption, that successive correlations are cleanly separated. Tests on simulations and three image benchmarks backed the method. The authors present it as practical theory for massive paired data.
Catalog record
| CREATOR | Canyi Chen [email protected], Liping Zhu [email protected] |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 134 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17792
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distributed Estimation and Gap-Free Analysis of Canonical Correlations Canyi Chen [email protected], Liping Zhu [email protected] Abstract Massive data analysis calls for distributed algorithms and theories. We design a multi-round distributed algorithm for canonical correlation analysis. We construct principal directions through convex formulation of canonical correlation analysis, and use the shift-and-invert preconditioning iteration to expedite the convergence rate. This distributed algorithm is communication-efficient. The resultant estimate achieves the same convergence rate as if all observations were pooled together, but does not impose stringent restrictions on the number of machines. We take a gap-free analysis to bypass the widely used yet unrealistic assumption of an explicit gap between the successive canonical correlations in the canonical correlation analysis. Extensive simulations and applications to three benchmark image data are conducted to demonstrate the empirical performance of our proposed algorithms and theories. Author One and Author Two † † heading: 23 2022 1- 1/21; Revised 5/22 9/22 21-0000 † † shortheadings: Distributed Estimation and Gap-Free Analysis of Canonical Correlations / Chen and Zhu † † firstpage: 1 † † editor: My editor keywords Canonical correlation, distributed analysis, gap-free bound. 1 Introduction Rapid advances in information technology allow people to collect data of unprecedented size in various scientific areas such as genomics, neuroscience and physics. These datasets are quite often simultaneously characterized by high dimensions and large sample sizes. Analyzing massive datasets in a single machine through conventional in-memory statistical algorithms is perhaps prohibitive due to constraints such as privacy concerns, limited memory and storage space ( Fan et al., 2014 ) . Easing these constraints calls for distributed algorithms and theories with low communication costs. We are concerned with canonical correlation analysis ( Hotelling, 1936 ) that has already grown into a powerful arsenal for revealing mutual variability in multiple views of two sets of random vectors. It has seen many successful applications in regression, clustering and word embedding ( Dhillon et al., 2011 ) , among many others. In the past two decades many efforts have been made to establish theoretical properties of canonical correlation analysis in the regimes of finite- ( Anderson, 1999 ) and infinite-dimensions ( Hardoon et al., 2004 ; Bao et al., 2019 ; Gao et al., 2015 ; Gao et al., 2017 ; Ma and Li, 2020 ) . Existing works implicitly assume that the observations are stored and processed in a single machine. Canonical correlation analysis of massive data calls for distributed algorithms and theories. Towards this goal, many efforts have been made in a star-networked distributed setting ( Zaharia et al., 2016 ) . These algorithms can be classified into two classes: single- or multiple-round. In particular, in the first class, Lv et al. (2020) developed a one-shot divide-and-conquer algorithm for canonical correlation analysis, which proceeds as follows. Each local machine conducts canonical correlation analysis and transmits the local results to the central machine over which all local estimates are aggregated to produce a final solution. This algorithm indeed generalizes the procedure proposed by Fan et al. (2019) to recover the eigenspace of principal component analysis. This generalization, however, suffers from at least two essential issues. First, the local estimates of canonical correlations are no longer unbiased. Therefore, for the divide-and-conquer algorithm to achieve an optimal convergence rate, a few undesirable and even unrealistic restrictions on the number of local machines have to be imposed to eliminate the biases of the local estimates ( Fan et al., 2019 ; Chen et al., 2022 ) . In a sensor network, the number of local machines usually violates the restrictions. Second, for the canonical correlation analysis to fulfill the orthogonal constraints, the divide-and-conquer algorithm requires each local machine to transmit the full covariance matrices to the central one in order to perform matrix decomposition. This additional procedure introduces an undesirable and even unbearable communication cost, particularly when the random vectors are high or even ultrahigh dimensional. Many multiple-round distributed algorithms, which fall into the second class, are also designed to relax the restrictions on the number of machines that are usually required by distributed principal component analysis. To be precise, Garber et al. (2017) presented two algorithms to estimate the leading principal component, which were later extended to a general number of principal components by Chen et al. (2022) . The above methodologies designed for distributed principal component analysis, however, cannot be adapted directly to distributed canonical correlation analysis because the latter involves inversions of two large covariance matrices. Using the pooled inversion would result in significant communication costs, while using the local one would result in non-negligible estimation biases. In addition, calculating inversions of large covariance matrices usually require very expensive computation costs. In the present article, we design a distributed algorithm for canonical correlation analysis that greatly mitigates the restrictions on the number of local machines and simultaneously eases the communication cost by avoiding communicating the full covariance matrices. The resultant distributed estimate attains an optimal convergence rate after a finite number of communications and fully respects the orthogonal constraints in the canonical correlation analysis. To be precise, we construct the principal directions through convex formulation of canonical correlation analysis, and use the shift-and-invert preconditioning ( Golub and Van Loan, 1983 ) , together with quadratic programming, to expedite the convergence rate of our proposed distributed algorithm. Solving canonical correlation analysis through shift-and-invert preconditioning dates back to Golub and Van Loan (1983) and Golub and Zha (1995) . It is an iterative method that transforms the canonical correlation analysis into a series of least squares problems in order to produce a sequence of increasingly accurate estimates. Ma et al. (2015) , Wang et al. (2016) , Allen-Zhu and Li (2017) and Gao et al. (2019) use this concept to solve the pooled canonical component analysis, where the least squares problems are solved by stochastic techniques. However, when this concept is implemented in the distributed canonical component analysis, numerous iterations may be involved and consequently, unbearable communication costs are to be introduced. We shall show that, the distributed estimate of our proposed algorithm achieves the same convergence rate as if all observations are pooled together after a finite number of communications. This merely requires to transmit vectors and thus reduces the communication cost substantially. By contrast, the divide-and-conquer method proposed by Lv et al. (2020) requires to transmit large dimensional matrices, which results in non-negligible communication cost. We further make an important theoretical contribution to the literature by deriving a gap-free error bound for the distributed canonical correlation analysis. Most existing convergence analyses depend upon the assumption of an explicit canonical correlation gap, \rho_{L}-\rho_{L+1}>B_{L} , where \rho_{\ell} is the \ell -th largest canonical correlation, L is a user-specified integer and B_{L} is a theoretical lower bound. Examples of requiring this assumption include, but not limited to, Wang et al. (2016) and Gao et al. (2019) . This assumption is widely used though, it is likely unrealistic. We demonstrate this phenomenon through three benchmark image data sets, MEDIAMILL ( Snoek et al., 2006 ) , MNIST ( Lecun et al., 1998 ) , and MFEAT ( Dua and Graff, 2017 ) . The Wilks’ lambda test ( Anderson, 2003 ) indicates that the top 50 canonical correlations are significant with