- 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
- To the best of my knowledge, the proposed formulation is novel.
- The theoretical analysis and algorithm in this paper make useful contributions to the field.
Critical weaknesses
- 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.
- 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.
- The worst-case iteration bound of the algorithm (i.e., Theorem 5) is rather large. In particular, any , even , yields , which is superpolynomial. This bound thus offers only limited theoretical support for efficiency and scalability.
Questions for authors
- 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."
- As an aside, the paper would also benefit from polynomial-time approximation algorithms with explicit approximation ratios.