acceptodds
Under review as a conference paper at ICLR 2027

Worst-Case Sparse Principal Subspace Estimation

Abstract

Sparse principal component analysis is normally posed as the maximization of an aggregate of captured variance—a single Rayleigh quotient, or the trace of the projected covariance—subject to a sparsity constraint. This choice matters when more than one component is required. An aggregate objective is dominated by its leading term, so a shared feature budget is spent first on the strongest components, and the weakest is returned as little more than an arbitrary direction. We make this precise by exhibiting covariances for which every maximizer of the trace criterion returns a degenerate subspace, one of whose directions carries no variance at all, while a worst-case objective yields a subspace in which every component keeps a fixed share of what it has in the population. Motivated by this, we study sparse principal subspace estimation under the worst-case componentwise retention ratio, defined as the smallest, across the population directions we wish to recover, of the fractions of variance that survive the restriction to the selected features. We show that this criterion is attained exactly by a choice of support, that it is largest precisely at the target eigenspace, and that taking the worst case over the individual columns of the estimated basis instead would give nothing new, since the Schur–Horn theorem reduces it to the trace criterion. To solve the resulting non-convex max–min program we develop TRIM, built on minorization–maximization (MM). We apply a tangent-plane minorizer to each of the eigenvalue functions, solve the resulting subproblem on each candidate support in closed form by a polar factor, and accept a support only if it raises the exact objective. TRIM needs no tuning parameters and no relaxation (in the sense of losing tightness), and it does not build the subspace one direction at a time by projecting out what it has already found. It is monotone by construction, terminates finitely, and reports an a posteriori bound on its own optimality gap. It succeeds on general covariances for which one-shot thresholding provably fails, it outperforms the competing estimators on a real corpus at every sparsity level we test, and under a limited feature budget it keeps far more of the weakest component—the one an aggregate objective neglects.

Primary area:
optimization
Keywords:
sparse principal component analysis, worst-case componentwise retention ratio

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_K1C9OpenReview ↗
Rating
3
Confidence
2(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a new formulation for robust feature-sparse PCA. The central idea is to maximize the worst-case (i.e., smallest) eigen-component, leading to a minimax optimization problem. The paper then analyzes the theoretical properties of the formulation, demonstrates its advantage (over the trace criterion) through an example (i.e., Proposition 2), and develops an MM-based algorithm for computing local maxima.

Critical strengths
  1. To the best of my knowledge, the proposed formulation is novel.
  2. The theoretical analysis and algorithm in this paper make useful contributions to the field.
Critical weaknesses
  1. The practical motivation for the proposed worst-case formulation is a bit underdeveloped. In particular, as I read it, the introduction doesn't identify a concrete application that demonstrates why maximizing the smallest eigen-component would be beneficial or necessary.
  2. The statistical guarantee (i.e., Theorem 7) is established for global maximizers only, while the algorithm is only shown to attain local optimality (i.e., Theorem 5). (I acknowledge that Corollary 6 provides a condition to certify global optimality, but the algorithm is not guaranteed to satisfy that condition.) A gap thus remains between the analysis and algorithm.
  3. The worst-case iteration bound of the algorithm (i.e., Theorem 5) is rather large. In particular, any s=ω(1)s=\omega(1), even s=log⁡log⁡ds=\log\log d, yields (ds)=dω(1)\binom{d}{s}=d^{\omega(1)}, which is superpolynomial. This bound thus offers only limited theoretical support for efficiency and scalability.
Questions for authors
  1. While the problem is NP-hard in general, I'd encourage the authors to identify meaningful special cases that admit polynomial-time computability. For comparison, Tian et al. (2020) establish polynomial-time solvability of the trace-based formulation in a low-rank regime; see Section 4.1 of "Tian, L., Nie, F., Wang, R., & Li, X. (2020). Learning feature sparse principal subspace. Advances in neural information processing systems, 33, 14997-15008."
  2. As an aside, the paper would also benefit from polynomial-time approximation algorithms with explicit approximation ratios.
Reviewer_udLAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies sparse principal subspace estimation under a shared feature budget. Instead of maximizing total captured variance, it proposes maximizing the minimum normalized eigenvalue. The authors give a construction in which every trace-optimal support produces a degenerate subspace, derive an exact support reduction, and introduce TRIM method. The paper also provides monotonicity and finite-termination results, an a posteriori optimality-gap bound, and conditional statistical recovery guarantees.

Critical strengths
  1. Proposition 2 provides a useful and concrete separation between aggregate variance maximization and the proposed spectral objective.

  2. The tangent minorizer in Lemma 3 seems valid, and evaluating candidate supports using the exact objective provides a mechanism for monotone improvement.

Critical weaknesses
  1. Equation (5) requires maximizing the minimum of the normalized minorizers. Equation (6) rewrites this objective that minimizes affine functions, but Lemma 4 solves only the maximization of one affine function for a fixed weight.

  2. Proposition 1(iii) shows that the baseline eigenvalue objective and the relationship between equality and inequality-constrained formulations do not extend to the MM surrogate.

  3. The objective compares ordered eigenvalues, but not the variance from each original population eigendirection.

  4. The statistical guarantee is not proved for the normalizers used by Algorithm 1. The algorithm uses κj=λj(Σ^)\kappa_j=\lambda_j(\widehat{\Sigma}), whereas Corollary 11 obtains the advertised slog⁡ds\log d scaling using sparse normalizers κj=max⁡∣S∣≤sλj(Σ^S)\kappa_j=\max_{|S|\le s}\lambda_j(\widehat{\Sigma}_S).

Questions for authors
  1. Can the authors supply the missing point showing that the proposed update solves the complete max–min surrogate in Equation (5), rather than a linear problem for a fixed weight?

  2. Under Setting 1 alone, how is η\eta controlled at the sample size when κj=λj(Σ^)\kappa_j=\lambda_j(\widehat{\Sigma}), as specified in Algorithm 1?

  3. How should the claim that the criterion “cannot neglect a component” be understood in light of the covariance counterexample above? Is the intended guarantee preservation of ordered spectral values rather than preservation of each population eigendirection?

  4. Remark 9- The claim that the objective is maximized by allocating coordinates appears incorrect when the eigenvalues change order.

Reviewer_8fBHOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies sparse k-PCA when k directions share one feature budget s. Aggregate objectives (trace, or sequential Rayleigh quotients) spend that budget on the strongest components. To keep the subspace energy allocation more balanced, the authors maximize the worst-case retention R(V)=min⁡jλj(V⊤ΣV)/κjR(V) = \min_j \lambda_j(V^\top\Sigma V)/\kappa_j over row-sparse orthonormal VV. TRIM is proposed to solve this max–min program by MM. Theoretically, Theorem 7 ensures any global maximizer recovers the leading eigenspace at an slog⁡ds \log d rate when ∣S⋆∣≤s|S^\star| ≤ s. The experiments show that TRIM obtains a promising retention score, and 20 Newsgroups reports the best held-out worst-component retention at every tested s.

Critical strengths
  1. The paper finds a new perspective on identifying an important issue in current PCA, where the classical trace maximization (summing up the energy) may ignore some informative directions. It proposes a novel objective to illustrate the energy retained by PCA, providing an interesting direction for subspace analysis. This paper also
  2. The proposed solver is sound. The MM procedure seems done right, which ensures the convergence of the proposed sparse PCA.
Critical weaknesses
  1. The theorem is not about the problem the paper motivates. Setting 1 and Thm. 7 assume s≥∣S⋆∣s\geq|S^\star| and a global maximizer of (P). In that regime, both RR and the trace are maximized at S∗S^* in the population, so this theory does not apply to the scenario in Prop. 2 (where ∣S⋆∣=2k>s|S^\star|=2k>s). The limited-budget regime in the introduction and Fig. 1(a,b), i.e., the one the authors call the regime that matters, has no corresponding theoretical support. Listing “a statistical guarantee under a general covariance” as a main contribution overstates what is actually proved.

  2. The main experiments score methods on RR, which is exactly the quantity TRIM is designed to maximize. Winning on worst-component retention is then largely by construction. It does not show that one should want RR. There is no strong "third-party metric" result for the proposed algorithm, for example, the highest accuracy for the downstream classification tasks. In Fig. 1(c), Sequential RTPM has the smallest subspace error (it is an "third-party metric"), but the paper does not discuss this. On the only real corpus, TRIM beats the same-search trace baseline by 0.6–1.4 points of held-out R, with total EVR 2.00 vs 2.03, but this is vacuous as it still uses R as the metric, and there is no downstream task. “Outperforms at every sparsity” oversells the algorithm.

Questions for authors

Q1. Will you state in the contributions and in Thm. 7 that recovery assumes s≥∣S⋆∣s ≥ |S^\star| and applies to global maximizers of (P)? Do you have any guarantee for s<∣S⋆∣s < |S^\star|?

Q2. Fig. 1 uses Remark 9’s disjoint blocks, where sequential extraction remains sparse after each deflation. Can you repeat Fig. 1(b)–(c) on one k>1 covariance that is not a union of disjoint blocks (overlapping supports, or your Model-2 background)? In particular, does Sequential RTPM still win on subspace error?

Q3. Fig. 1(c) is scored on subspace error, and Sequential RTPM is lowest. How should that panel be read against the claim that sequential extraction fails in the sparse setting? More generally, can you report a metric that is not R, e.g., metric of a downstream task?

Q4. The 20 Newsgroups gap is at most 1.4 points of held-out R, and total EVR is slightly worse than the trace. Why is worst-component retention the quantity a practitioner should use to choose a method?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.