PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse CCA: Adaptive Estimation and Computational Barriers

Chao Gao, Zongming Ma, Harrison H. Zhou

arXiv:1409.8565v4stat.MEmath.ST

TL;DR

Sparse CCA lacks computationally feasible, adaptive estimation guarantees in high dimensions, where classical CCA fails. This paper derives separate minimax rates, proposes an adaptive two-stage estimator, and proves that a related sample-size condition is computationally necessary under Planted Clique hardness. The results also yield Gaussian sparse PCA computational lower bounds.

  • Problem

    High-dimensional sparse CCA requires separate estimation theory and efficient procedures because classical CCA fails and prior optimal methods are nonadaptive and computationally infeasible.

  • Method

    The paper derives separate minimax rates and uses a two-stage convex-relaxation and sparse-regression estimator adaptive to nuisance parameters and sparsity levels.

  • Results

    The estimator attains optimal rates adaptively with high probability, while computational lower bounds show a sample-size condition is necessary for randomized polynomial-time consistency.

  • Takeaways & Limitations

    Sparse CCA admits adaptive computationally feasible optimal-rate estimation under the stated sample-size condition, while computational barriers remain below it.

  • Takeaways & Limitations

    The guarantees assume Gaussian distributions, require an additional sample-size condition, and do not fully treat adaptation to M.

Abstract

from arXiv · show

Canonical correlation analysis is a classical technique for exploring the relationship between two sets of variables. It has important applications in analyzing high dimensional datasets originated from genomics, imaging and other fields. This paper considers adaptive minimax and computationally tractable estimation of leading sparse canonical coefficient vectors in high dimensions. First, we establish separate minimax estimation rates for canonical coefficient vectors of each set of random variables under no structural assumption on marginal covariance matrices. Second, we propose a computationally feasible estimator to attain the optimal rates adaptively under an additional sample size condition. Finally, we show that a sample size condition of this kind is needed for any randomized polynomial-time estimator to be consistent, assuming hardness of certain instances of the Planted Clique detection problem. The result is faithful to the Gaussian models used in the paper. As a byproduct, we obtain the first computational lower bounds for sparse PCA under the Gaussian single spiked covariance model.

1 Introduction

This paper studies sparse CCA in high dimensions, where classical CCA breaks down and prior optimal procedures are computationally infeasible and nonadaptive. It derives separate estimation rates, develops an adaptive efficient estimator, and establishes computational lower bounds under Planted Clique hardness.

  • High-dimensional CCA motivates sparse leading canonical coefficient vectors because classical CCA breaks down when dimensions exceed sample size.
  • Prior sparse CCA theory used exhaustive subset search and required known sparsity levels, making its optimal procedure computationally infeasible and nonadaptive.
  • The paper asks for separate minimax rates, computationally efficient sparsity adaptation, and the computational price of attaining optimal rates.
  • Separate rates show that estimating U depends on n, r, λr, p, and su, but not on m or sv, allowing faster convergence when U is sparser.
  • A two-stage method combines a convex relaxation with sparse linear regression to adapt to nuisance parameters and sparsity levels while attaining optimal rates with high probability.
  • Under Planted Clique hardness, a sample size condition is necessary for randomized polynomial-time consistency, with the lower bound established for the paper’s Gaussian model.

2 Problem Formulation

The paper formulates sparse CCA through a Gaussian canonical pair model with row-sparse canonical coefficient matrices and evaluates estimators by prediction loss for new observations. The loss accounts for the nonuniqueness of canonical vectors under joint orthogonal transformations.

  • 2.1 Parameter space: The model observes n independent Gaussian pairs with covariance Σ belonging to a structured canonical pair parameter space.
  • 2.1 Parameter space: The cross-covariance satisfies Σxy = ΣxUΛV′Σy, with U′ΣxU = V′ΣyV = Ir.
  • 2.1 Parameter space: Sparsity is imposed by bounding the numbers of nonzero rows in U and V by su and sv, respectively.
  • 2.1 Parameter space: The parameter space allows su, sv, p, m, r, and λ to vary with n while restricting M to an absolute constant.
  • 2.2 Prediction loss: Prediction loss measures expected squared error for predicting new canonical variables U′X⋆ using estimated vectors, after optimizing over W ∈ O(r).
  • 2.2 Prediction loss: The orthogonal alignment W is necessary because equal canonical correlations make (U,V) identifiable only up to a joint orthogonal transformation.
  • 2.2 Prediction loss: The corresponding loss for V replaces U, bU, X⋆, and Σx with V, bV, Y⋆, and Σy.
  • 2.2 Prediction loss: Prediction loss is stronger than the subspace projection loss, so the paper focuses on the more stringent criterion.

3 Minimax Rates

The paper derives separate minimax rates for estimating the two sparse canonical coefficient vectors and proposes a two-stage estimator that attains these rates under an additional sample-size condition. The resulting rate for U depends only on U-side sparsity and problem parameters, while the joint estimator can depend on V-side complexity.

  • Minimax rates: Separate minimax rates are established for U and V, with a combinatorial upper bound matched by a minimax lower bound.The resulting rate is minimax whenever the rate expression is bounded by a constant.
  • Adaptive estimation: The proposed procedure splits the data into three batches, obtains an initial sparse CCA estimate, and refines U through a second-stage constrained least-squares problem.The final estimator is a normalized version of the second-stage solution, and sample splitting facilitates the proof.
  • Adaptive estimation: The first-stage estimator can depend on s_v and m, whereas the second stage is introduced to pursue the optimal estimation rates.The second-stage refinement uses a group-Lasso convex relaxation when rows of the coefficient matrix are treated as groups.
  • Minimax rates: The rate for estimating U depends on n, r, λ_r, p, and s_u, but not on m or s_v.Its probability tail can still involve m and s_v, although the corresponding term vanishes as m grows.
  • Rate dependence: The prediction-loss rate for U does not depend on parameters associated with V, while alternative norm-loss rates can include the condition number of Σ_x.The paper assumes bounded marginal-covariance eigenvalues in its discussion of these rates.

4 Adaptive and Computationally Efficient Estimation

The paper replaces exhaustive, nonadaptive sparse CCA optimization with the computationally feasible CoLaR procedure, combining convex relaxation and group-Lasso refinement. Under an additional sample-size condition, it achieves optimal adaptive rates, while related computational lower bounds show that such a condition is necessary for efficient consistency.

  • Estimation scheme: CoLaR replaces exhaustive subset searches and known-sparsity requirements with a two-stage convex-program approach that is computationally feasible and sparsity-adaptive.The first stage relaxes a matrix sparsity problem using an ℓ1 penalty; the second uses group-Lasso refinement.
  • Estimation scheme: The first-stage convex relaxation estimates a cross-product matrix by replacing its ℓ0 sparsity constraint with an ℓ1 penalty and convexifying the feasible set.The asymmetric factorization is handled through the product LR′ rather than optimizing over L and R separately.
  • Theoretical guarantees: Under sample condition (21), the refinement stage converts a potentially sub-optimal first-stage estimate into optimal convergence rates for the canonical coefficient matrices.The first-stage estimate need only be sufficiently close in Frobenius norm for the refinement to attain the optimal rates.
  • Theoretical guarantees: The penalty choices do not depend on su or sv, so the estimator adapts over sparsity levels; the stated guarantees also extend from Gaussian to subgaussian distributions.Adaptation to the marginal-covariance parameter M is not fully treated, although the paper notes possible routes when dimensions are bounded relative to n.
  • Estimation scheme: The second stage applies group-Lasso to row groups, because the group sparsity penalty achieves su(r + log p)/(nλ2), whereas an ℓ1 penalty yields rsu log p/(nλ2).The group penalty is the sum of rowwise ℓ2 norms and controls sparsity through its penalty parameter.
  • Computational barriers: The adaptive scheme is optimal over a smaller parameter-space collection because its stronger sample-size condition is also necessary for randomized polynomial-time consistency under Planted Clique hardness.The paper states analogous computational barriers for sparse PCA and sparse CCA.

5 Computational Lower Bounds

The paper argues that the sample-size condition required by its adaptive sparse CCA estimator is likely unavoidable for computationally efficient consistency, under Planted Clique hardness. It establishes this through reductions involving Gaussian sparse PCA and sparse CCA, and obtains the first such sparse PCA lower bounds for the Gaussian single-spiked model.

  • Sparse CCA lower bound: Theorem 5.1 links violation of the sample-size condition to a randomized polynomial-time Planted Clique test, contradicting the conjectured hardness assumption.The reduction applies to sparse CCA estimation under the stated parameter-space and asymptotic conditions.
  • Sparse CCA lower bound: Subject to a sub-polynomial factor, condition (21) is necessary for consistent sparse CCA estimation within polynomial time.The comparison is made directly between conditions (21) and (23).
  • Computational model: The continuous-model complexity statement assumes unit-cost real arithmetic and sampling, with discretization needed for a probabilistic Turing-machine formulation.The paper later supplies an asymptotically equivalent discretized treatment.
  • Reduction strategy: The reduction proceeds through computational hardness of sparse PCA under the Gaussian single spiked covariance model, followed by a reduction from sparse PCA to sparse CCA.This separates the lower-bound argument into two computational reductions.
  • Reduction strategy: A good sparse-eigenvector estimator can be transformed into a low-error Planted Clique test through the Gaussian reduction, under the theorem’s parameter conditions.The construction starts from a graph adjacency matrix, Gaussianizes it, and applies the estimator to generated observations.
  • Sparse PCA consequence: Theorems 5.3–5.4 provide the first computational lower bounds for sparse PCA in Gaussian single spiked covariance models.Earlier lower bounds cited by the paper applied to broader restricted-covariance-concentration classes rather than directly to this spiked Gaussian model.

6 Proofs

The proofs establish the adaptive estimators’ error bounds through feasibility, empirical-process control, cone conditions, and restricted-eigenvalue or curvature arguments. Separate proof sequences handle the two canonical coefficient-vector estimators and conclude with the stated prediction-loss rates.

  • Feasibility and curvature: The constructed matrix eA = eU eV′ is shown to be feasible for the optimization problem, enabling comparison with the estimator’s objective value.This feasibility statement is used in the subsequent error analysis.
  • Assumptions: The proof framework assumes sufficiently small normalized covariance-estimation errors and controls constants through the marginal-covariance eigenvalue parameter M.A separate remark explains that explicit eigenvalue dependence can be tracked when M diverges.
  • Theorem 4.1: The proof of Theorem 4.1 first bounds the estimation criterion, then derives a generalized cone condition, and finally converts the resulting bound into an error bound.The argument uses feasibility of the constructed comparator and curvature-type inequalities.
  • Theorem 4.1: Theorem 4.1 controls off-support error by partitioning indices according to the largest entries of the estimation error and applying restricted-eigenvalue bounds.The support decomposition and choice of t yield a positive lower curvature constant under the sample-size assumptions.
  • Theorem 4.1: Theorem 4.1’s final rate follows after bounding the estimation error and combining it with the approximation error between eA and UV′.The proof concludes using the triangle inequality and the high-probability covariance bounds.
  • Theorem 4.2: Theorem 4.2 uses a three-step argument: bound a quadratic form, derive a cone condition controlling the Frobenius error, and translate that control into the loss L(bU, U).The proof treats the first-stage estimate as independent of the sample covariance matrices used in the second stage.

7 Proofs of Results in Section 5

The proofs of the Section 5 lower bounds construct reductions from Planted Clique to Gaussian sparse PCA and then to sparse CCA. Total-variation approximations transfer testing performance between graph-generated data and spiked Gaussian models, yielding contradictions under the hardness hypothesis.

  • Distributional approximation: The reduction uses Gaussianization distributions whose mixtures match the relevant normal densities, with total variation controlling the approximation error.The construction introduces auxiliary distributions and applies data-processing and total-variation inequalities.
  • Distributional approximation: The proof approximates graph-generated observations by Gaussian samples under the null and by a sparse spiked Gaussian model under the alternative.The null distribution is close to samples from Q0, while the alternative is close to a mixture over sparse (θ, τ) pairs.
  • Dimension extension: When p ≥ 2n, the proof analyzes the first 2n coordinates and shows that the remaining coordinates contribute zero additional total-variation error.This extends the reduction beyond the square-coordinate case.
  • Testing reduction: A uniformly consistent sparse-eigenvector estimator yields a randomized Planted Clique test whose error can be made smaller than any fixed nonzero probability.The conclusion follows by bounding Type-I and Type-II errors under the null and alternative distributions.
  • Lower-bound conclusion: Choosing N = 12n and k = ⌊2s/3⌋ transfers the sparse PCA testing contradiction to the parameter regime used for the computational lower bound.The resulting testing error is bounded below the threshold required by the Planted Clique hardness hypothesis.
  • Technical control: The proof also controls normalization constants and Gaussian tail terms so that the constructed densities remain valid and the approximation errors are negligible.The paper bounds the normalization deviations by order N^-4 for the relevant range of μ.

8 Discretization and Computational Lower bounds

The paper discretizes the continuous Gaussian models to make randomized polynomial-time complexity rigorous while preserving their statistical difficulty. It then adapts the reductions and states computational lower bounds for the discretized sparse PCA and sparse CCA problems.

  • Asymptotic equivalence: The discretized sparse PCA and sparse CCA parameter spaces are asymptotically equivalent to their continuous counterparts at logarithmic discretization levels.Consequently, consistency conditions remain the same for the original and discretized problems.
  • Computational model: The discretized formulation uses the probabilistic Turing-machine model rather than the unit-cost continuous computation model.The paper modifies the reductions to account for finite-precision sampling and computation.
  • Discretized lower bounds: Theorem 8.1 extends the sparse PCA computational lower bound to randomized polynomial-time estimators in the discretized Gaussian spiked model.Its discretization level is t = ⌈4 log2(p + n)⌉.
  • Discretized lower bounds: Theorem 8.2 provides the corresponding discretized sparse CCA lower bound for randomized polynomial-time estimators.Its discretization level is t = ⌈4 log2(p + m + n)⌉.
  • Discrete sampling: The reduction samples discretized variables by quantizing and truncating continuous distributions, with total variation error controlled by the discretization parameters.The resulting discrete distribution can be sampled in polynomial time.
  • Complexity accounting: The modified reduction generates O(n(p + n)) random variables, while random-number generation and other reduction computations have complexity O(p^10(log p)^(3/2)).This bound excludes the complexity of the supplied estimator itself.

9 Additional Proofs

The proofs establish finite-sample bounds and minimax lower bounds for sparse CCA under stated sparsity and sample-size conditions. They use projection-loss comparisons, packing arguments, KL divergence, and Fano’s lemma.

  • Finite-sample bounds: Theorem 9.1 gives a high-probability bound for the estimator under the stated sample-size assumption.The bound applies uniformly over the specified covariance class.
  • Discussion: The loss-dependent analysis removes dependence on the marginal covariance bound M from the error bound.This distinguishes the theorem from the cited joint-error result.
  • Minimax lower bounds: The minimax lower-bound proof combines packing constructions with KL-divergence control and Fano’s lemma.The construction separates contributions involving r s_u and s_u log(ep/s_u).
  • Finite-sample bounds: The prediction-loss analysis is linked to squared subspace distance through a covariance-eigenvalue bound.An analogous inequality holds for estimating V.
  • Minimax lower bounds: A sufficient-statistic argument reduces one lower-bound component to estimating a rank-one direction under projection loss.The reduction uses the (X_2,Y_2) observations.

10 Implementation of (18)

The implementation converts the first-stage convex program into an ADMM procedure with sparse and singular-value-controlled updates. Its matrix updates admit Lasso and singular value capped soft-thresholding interpretations.

  • ADMM implementation: ADMM iteratively updates the primal and dual matrices until a convergence criterion is met.The dual update is explicit, while the two primal updates have optimization interpretations tied to sparse CCA.
  • ADMM implementation: The F update is equivalent to a standard Lasso problem after vectorization.This update targets sparsity in the matrix U V′.
  • ADMM implementation: The G update solves a constrained singular-value optimization problem with nuclear-norm and operator-norm constraints.The solution is obtained by thresholding ordered singular values.
  • ADMM implementation: The G update is implemented as singular value capped soft thresholding, which controls its singular values.The operation is denoted SVCST(W).
  • ADMM implementation: The convex program is summarized as Algorithm 5 and can be solved directly with standard convex-programming software.The implementation avoids the more expensive vectorized Kronecker-product formulation.

11 Numerical Studies

Numerical studies evaluate CoLaR across three covariance settings and show consistent advantages over PMA and over its initial estimator. The experiments also examine implementation details and model misspecification.

  • Simulation results: Tables 1–3 report median prediction errors over 100 repetitions across four dimension and sample-size configurations.The reported columns distinguish PMA, initialization, and two-stage CoLaR estimates.
  • Simulation results: In all simulation settings, the renormalized initial estimators and CoLaR consistently outperform PMA.The comparison covers both U and V estimation errors.
  • Simulation results: The two-stage CoLaR estimators significantly improve over the renormalized initial estimators.This improvement agrees with the theoretical results for the adaptive procedure.
  • Summary: The study concludes that CoLaR has consistent and competitive performance across covariance settings and dimension–sample-size configurations.Its observed behavior agrees well with the theory.
  • Model misspecification: Under model misspecification with three nontrivial canonical-correlation pairs but r=2, the estimator remains robust in both examined scenarios.The misspecified-model experiment uses Identity, Toeplitz, and SparseInv marginal covariances.
Loading 1409.8565v4…