Fast Association Recovery in High Dimensions by Parallel Learning

Sparse reduced-rank regression is a widespread tool to reveal the association between multiple responses and predictors, and it has been widely applied to many data-driven applications. Although much of the literature has studied related theoretical properties and numerical algorithms, due to high nonconvexity, the computation burden for large-scale data sets remains a great challenge in practice. Also, the gap between the statistical consistency and the algorithmic convergence needs more research. To address these two issues, we formulate a sparse reduced-rank regression as a set of parallel cosparse unit-rank estimation problems and propose a new algorithm to estimate these subproblems in parallel. Under mild conditions, the iteration complexity of the proposed algorithm is polynomial with high-dimensional responses and predictors. We show a statistical consistency for the numerical solution, thereby bridging the gap between statistical consistency and numerical computation from nonconvex optimization. Moreover, the main calculation of the algorithm is restricted to a small active set, so it exhibits fast computation even in high dimensions. Extensive numerical studies and an application in genetics demonstrate the effectiveness and scalability of our approach.