Title: Sparse CCA: Statistical and Computational Limits
Abstract:

This talk will consider the problem of sparse canonical correlation analysis (sparse CCA). The first part of the talk will focus on the statistical side. We will argue that sparse CCA is intrinsic different from the well studied sparse PCA problem because of the presence of high-dimensional nuisance parameters, namely, the marginal covariance matrices. A somewhat surprising result we derived shows that the minimax rate of sparse CCA is nearly independent of the structure of the marginal covariance matrices. The second part of the talk will focus on the computational side. A novel algorithm is proposed to achieve the minimax rate adaptively under an extra sample size condition. We will further present a computational lower bound argument to show that the additional sample size condition is essentially necessary for any polynomial-time algorithm to work under the Planted Clique hypothesis. A novel reduction procedure is constructed to ensure that the lower bound is faithful to the Gaussianity of the model. A byproduct of the argument also provides a computational lower bound for sparse PCA under Gaussian spiked covariance model.

This talk is based on joint work with Chao Gao and Harrison Zhou.