- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies robust Gaussian covariance estimation under strong contamination. It proposes a nonconvex moment-difference objective and proves that approximate stationary points yield accurate estimates in one and multiple dimensions. A spectral relaxation makes the method tractable, but its accuracy certificate applies only when the relaxed objective is nonpositive. Experiments show performance comparable to existing baselines.
Critical strengths
-
The exact objective has a useful landscape guarantee: under the stated Gaussian stability assumptions, every sufficiently approximate stationary point gives an accurate estimate, not just a global optimum. The proof links second-moment error to objective value and shows descent toward the clean weights.
-
The high-dimensional result uses one set of weights to control every projection direction, yielding a multiplicative spectral-norm guarantee. This gives a principled extension from variance estimation to covariance estimation.
Critical weaknesses
-
The main theorem does not guarantee that the proposed algorithm works. Theorem 4 concerns stationary points of the exact high-dimensional objective F, which the paper describes as intractable. The implementation instead optimizes F_rel. Corollary 1 certifies accuracy only when F_rel <= 0, but the paper does not show that projected gradient descent reaches this value or that its approximate stationary points are accurate. Algorithm 1 can also stop at its iteration limit. The experiments further search over k and use Delta_{n,1.01 epsilon}, unlike the theorem's stated parameters and feasible set. This leaves a substantial gap between the theory and the algorithm.
-
The paper does not show a clear advantage over existing robust covariance methods or related nonconvex reweighting approaches. Prior work already gives high-dimensional estimators with multiplicative Frobenius-norm guarantees. Here, experiments show comparable accuracy on a limited set of synthetic settings and a modified POPRES task, but report no runtime, scaling beyond d = 30, or multiplicative spectral-norm error. The theory also relies on Gaussian moment-stability assumptions and sample-size requirements. It is therefore unclear what the new objective offers beyond its landscape result.
Questions for authors
-
How does the exact objective F in Theorem 4 relate to the implemented method for F_rel? Can you show that projected gradient descent reaches F_rel <= 0, or that an approximate stationary point of F_rel is accurate? Please report how often runs reach F_rel <= 0, including those stopped by iteration or progress limits.
-
What obstacle in existing robust covariance methods does this formulation address, and what statistical or computational advantage does it offer over existing estimators and nonconvex reweighting methods? Please separate the landscape result from any end-to-end algorithmic guarantee, and compare runtime and scaling under matched conditions.
-
Theorem 4 bounds multiplicative spectral-norm error, but the synthetic experiments report only multiplicative Frobenius-norm error. Could you report both metrics for all methods and corruption settings, and say whether the method rankings change under spectral norm?
-
Which assumptions and conclusions are tested by each experiment? Do the synthetic sample sizes support the uniform second- and fourth-moment stability assumptions at the tested dimensions and corruption levels? Since POPRES may not satisfy the Gaussian moment identity and uses a different top-three-subspace objective, what does that experiment establish about the proposed method or theory?
3 comments
The rebuttal addresses some of my concerns and provides useful additional evidence. However, it does not resolve my main concern about the significance of the contribution. The paper aims to construct a nonconvex objective whose approximate stationary points yield accurate covariance estimates. But the method does not sufficiently explain why this formulation provides an important benefit beyond existing approaches.
The response then criticizes existing methods for relying on repeated whitening or semidefinite programming. However, I do not consider these to be shortcomings of those methods. Beyond the simplicity of the optimization objective, I do not see any additional value in the proposed method, as its robustness also relies on a standard reweighting approach.
I therefore maintain my rating.
Thank you for the follow-up. We did not intend our discussion of whitening or semidefinite programming as criticism of these approaches. We see value both in advancing algorithmic dimensional robust statistics with these powerful techniques and in exploring simple objectives with favorable optimization landscapes. These are complementary research directions, and our motivation is to broaden the available approaches to robust covariance estimation.
We thank the reviewer for the thoughtful feedback and for recognizing the landscape guarantee and simultaneous control of all directions.
Additive guarantee for Frel. For the same relaxed objective Frel, we have an additive landscape guarantee, which we omitted from the submitted version to focus on multiplicative error. Under the stability condition of [1, Definition 4.5], every sufficiently accurate approximate stationary point of Frel satisfies ∥Σw−Σ∥F≤O(ϵlog(1/ϵ))∥Σ∥2.
Relation between F and Frel (Q1, W1). Frel relaxes the maximization over rank-one matrices vv⊤ in F to all symmetric matrices with unit Frobenius norm, so F≤Frel, and any w satisfying Frel(w,k)≤0 yields a multiplicative approximation of the true covariance Σ. As noted in lines 349-350, optimizing Frel is a heuristic. In our synthetic experiments, we start from k=6 and minimize Frel(w,k) using gradient descent. Every time the objective value becomes negative we reduce k by 0.05, and we return the w from the last k where the objective was negative. All runs in our synthetic Gaussian experiments returned w satisfying Frel(w,k)<0, with final k between 3.1 and 3.5. We will clarify this.
Contribution (Q2, W2). Our contribution is a simple objective function and its landscape analysis. To achieve multiplicative approximation, many existing approaches handle the unknown and possibly very different variances across directions through repeated whitening and/or semidefinite programming. Our formulation instead handles all scales within a single objective function. Our main goal is not to improve accuracy or runtime over existing estimators, but to show that robust covariance estimation can be cast as a single nonconvex objective whose gradients can be computed with basic matrix-vector operations and whose approximate stationary points are all good solutions.
Error metric (Q3). We report multiplicative Frobenius error because existing methods target this stronger error metric, whereas we focus on multiplicative spectral error. To be fair to existing approaches, we compare on their benchmark, which if anything favors them. We will add spectral-norm results for all methods and corruption settings.
Assumptions and experiments (Q4). Our experiments complement our theoretical results and mainly compare methods empirically, including at corruption levels beyond the scope of our analysis. The synthetic experiments check whether PGD on Frel reaches the certificate of Corollary 1. The theoretical guarantees of all methods in our experiments (including ours) rely on Gaussian moment assumptions, so on the POPRES data they are all heuristics. The POPRES experiment empirically tests a top-three-subspace adaptation of our difference-of-moments objective on real data.
[1] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press. 2023.