acceptodds
Under review as a conference paper at ICLR 2027

Robust Gaussian Covariance Estimation via Nonconvex Optimization

19 views

Abstract

We study the problem of estimating the covariance matrix of a high-dimensional Gaussian distribution when an -fraction of the samples are arbitrarily corrupted. We focus on developing nonconvex formulations that can be optimized using standard first-order methods. We first introduce a new objective function for the one-dimensional setting and prove that every approximate first-order stationary point yields a near-optimal estimate of the true variance. We then extend this objective and its analysis to high dimensions and propose a heuristic algorithm based on a tractable relaxation. We demonstrate empirically that our algorithm achieves performance comparable to that of existing robust covariance estimation algorithms.

Primary area:
learning theory
Keywords:
robust statistics, optimization landscapes, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.40 over 5 reviews, above 68% of the others.
Reviewer_TMzVOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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.

  2. 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.

  3. 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?

  4. 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

We thank the reviewer for the thoughtful feedback and for recognizing the landscape guarantee and simultaneous control of all directions.

Additive guarantee for FrelF_{\mathrm{rel}}. For the same relaxed objective FrelF_{\mathrm{rel}}, 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 FrelF_{\mathrm{rel}} satisfies ∥Σw−Σ∥F≤O(ϵlog⁡(1/ϵ))∥Σ∥2.\Vert \Sigma_w - \Sigma \Vert_F \le O(\epsilon\log(1/\epsilon)) \Vert \Sigma \Vert_2.

Relation between FF and FrelF_{\mathrm{rel}} (Q1, W1). FrelF_{\mathrm{rel}} relaxes the maximization over rank-one matrices vv⊤vv^\top in FF to all symmetric matrices with unit Frobenius norm, so F≤FrelF \le F_{\mathrm{rel}}, and any ww satisfying Frel(w,k)≤0F_{\mathrm{rel}}(w,k) \le 0 yields a multiplicative approximation of the true covariance Σ\Sigma. As noted in lines 349-350, optimizing FrelF_{\mathrm{rel}} is a heuristic. In our synthetic experiments, we start from k=6k = 6 and minimize Frel(w,k)F_{\mathrm{rel}}(w,k) using gradient descent. Every time the objective value becomes negative we reduce kk by 0.050.05, and we return the ww from the last kk where the objective was negative. All runs in our synthetic Gaussian experiments returned ww satisfying Frel(w,k)<0F_{\mathrm{rel}}(w,k) < 0, with final kk between 3.13.1 and 3.53.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 FrelF_{\mathrm{rel}} 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.

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.

Reviewer_QtsnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents a new non-convex optimization formulation to robust covariance estimation problem. Theoretical guarantees on one-dimensional and high-dimensional scenarios are established. A tractable heuristic relaxation formulation is also proposed and empirically evaluated.

Critical strengths
  1. The paper establishes theoretical guarantees on the new proposed non-convex formulation. The result itself could be of interests considering the formation is arguably simpler compared to the earlier works such as Zhu et al. (2022) where a moment ratio objective is considered, and with a potential stronger guarantees.

  2. For the relaxed heuristics formulation the authors provide experimental results justifying the formulation along with the algorithm works reasonably well compared to existing method.

Critical weaknesses
  1. There are already a series of practical algorithms in the area of robust covariance estimations. The relaxed heuristic formulations and the algorithm, from the experiment section, do not seem to out-perform some of the existing methods such as IterRef PGD or IterRef QUE in some of the genome data settings.

  2. The non-convex formulation along with the proofs, seems to be an extension of earlier works, e.g. Cheng et al. (2022). Even though Cheng et al. (2022) treats matrix sparse mean estimation and sparse PCA.

Questions for authors
  1. It would be interesting to highlight what is the main technical challenges in this paper compared to earlier works Cheng et al. (2022) and what are the new technical tools introduced in this paper that lead to the resolution of the challenges.

  2. Can the authors explain, for example, in the case of Discrete block corruption in Genome data, the proposed algorithm PGD Covariance seems to be performing worse than IterRef PGD and IterRef QUE and what this implies?

1 comment

We thank the reviewer for the thoughtful feedback and for recognizing the simplicity of our formulation.

Q1. Compared to Cheng et al. (2022), the challenge in our paper is obtaining a multiplicative error guarantee simultaneously in all directions, including low-variance directions where small additive errors can correspond to large multiplicative errors. A natural scale-free objective is the kurtosis ratio A/BA / B, where A=Ew[(v⊤X)4]A = \mathbb{E}_w[(v^\top X)^4] and B=(Ew[(v⊤X)2])2B = (\mathbb{E}_w[(v^\top X)^2])^2, but it can have bad stationary points. Our key idea is to use the linearized kurtosis A−kBA - kB with kk slightly larger than 33. This preserves the condition A/B≤kA / B \le k in every direction while fixing the optimization landscape. We prove that every approximate stationary point of the maximum over these linearized-kurtosis objectives yields an accurate covariance estimate.

Q2. 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. Under discrete-block corruption, our subspace error is comparable to the best baseline (the largest gap is 0.0680.068 versus 0.0580.058 at ϵ=0.05\epsilon = 0.05), and our method still recovers the geographic structure. When the corruption targets a low-variance direction (inverse-spectrum corruption), our method has substantially lower error than the best baseline (the largest gap is 0.0510.051 versus 0.1800.180 at ϵ=0.1\epsilon = 0.1).

Reviewer_Y1uYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies Gaussian covariance estimation under strong contamination using optimization over sample weights. It proves that every approximate stationary point of a moment-difference objective gives an accurate variance estimate, and extends this landscape result to a high-dimensional quartic objective. A tractable spectral relaxation is optimized heuristically and evaluated on synthetic data and a POPRES subspace-recovery task.

Critical strengths
  • The paper studies Gaussian covariance estimation under strong contamination using optimization over sample weights. It proves that every approximate stationary point of a moment-difference objective gives an accurate variance estimate, and extends this landscape result to a high-dimensional quartic objective. A tractable spectral relaxation is optimized heuristically and evaluated on synthetic data and a POPRES subspace-recovery task.

  • The paper clearly labels optimization of the relaxation as heuristic (lines 349--350). The experiments include ill-conditioned covariances and real genomic data.

Critical weaknesses
  • Theorem 4 concerns FF, whose evaluation is NP-hard in general (lines 326-327), whereas Algorithm 1 optimizes FrelF_{\rm rel}. Corollary 1 certifies accuracy only after a non-positive value is reached. There is no guarantee that PGD reaches such a value, and Algorithm 1 can return at the iteration limit without the certificate (lines 359-360). What accuracy guarantee or empirical failure rate applies to these uncertified returns?

  • The sample complexity of the tractable certificate is unclear. Definition 2 controls fourth moments along vv⊤vv^\top, while the relaxation maximizes over all symmetric matrices. Does any feasible weight vector achieve Frel≤0F_{\rm rel}\le0 at the sample size O~(d2/ε+d/ε2)\widetilde O(d^2/\varepsilon+d/\varepsilon^2) in lines 292-294? In particular, does w⋆w^\star do so?

  • The experiments instead use 2d(d+1)/ε22d(d+1)/\varepsilon^2 samples (line 386). A sample-size sweep would help establish whether the relaxation retains the sample bound of the landscape result. Also, the abstract mentions high-dimensional setting in the first line which is usually considered n>d. Even if large d is considered high-dimensional setting, d = 30 is not large. The authors should define high-dimensional setting formally.

  • The authors should also cite the appropriate literature. Otherwise, it becomes tough to judge the novelty. For example, stability conditions are well known in the literature. See

I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra and A. Stewart. Robust Estimators in High Dimensions without the Computational Intractability. FOCS, 2016

  • In line 124, the authors cite a personal communication with Daniel Kane and not an existing paper. I am not sure if this is appropriate for a submission.
Questions for authors
  • How should Theorem 4 be positioned relative to [1, Exercise 4.3], which gives an inefficient estimator with O(ε)O(\varepsilon) relative spectral error using O(d/ε2)O(d/\varepsilon^2) samples, and the SQ tradeoffs in [2, Theorems 1.4--1.5]? The distinction between a landscape result and an efficient estimator is important here.

  • Under the stronger lifted covariance-stability assumptions of [1, Definition 4.5], does the weighted certificate directly yield a relative Frobenius bound via Proposition 4.7 and Eq.~(4.4)? Please state the assumptions needed; these are stronger than Definition 2.

  • What explicit corruption range do the proofs allow? Line 1226 requires k≤4k\le4 and 64ε≤164\varepsilon\le1, whereas the implementation starts at k=6k=6 and tests corruption up to 0.30.3. Please explain the empirical scope and include sensitivity to $k.

References

[1] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press, 2023.

[2] I. Diakonikolas, D. M. Kane and A. Stewart. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. FOCS, 2017.

[3] I. Diakonikolas, D. Kane, A. Pensia and T. Pittas. Nearly-Linear Time and Streaming Algo- rithms for Outlier-Robust PCA. ICML, 2023.

2 comments

We thank the reviewer for the careful reading of our paper and the constructive feedback.

Additive guarantee for FrelF_{\mathrm{rel}}. For the same relaxed objective FrelF_{\mathrm{rel}}, we have an additive-error landscape result, 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 FrelF_{\mathrm{rel}} satisfies ∥Σw−Σ∥F≤O(ϵlog⁡(1/ϵ))∥Σ∥2.\Vert \Sigma_w - \Sigma \Vert_F \le O(\epsilon\log(1/\epsilon)) \Vert \Sigma \Vert_2.

Relaxation and sample complexity (W1-W4). In our synthetic experiments, we start from k=6k = 6 and minimize Frel(w,k)F_{\mathrm{rel}}(w,k) using gradient descent. Every time the objective value becomes negative we reduce kk by 0.050.05, and we return the ww from the last kk where the objective was negative. All runs in our synthetic Gaussian experiments returned ww satisfying Frel(w,k)<0F_{\mathrm{rel}}(w,k) < 0, with final kk between 3.13.1 and 3.53.5. We will clarify this.

The reviewer is correct that guaranteeing Frel(w⋆,k)≤0F_{\mathrm{rel}}(w^\star,k) \le 0 requires n=Ω~(d2/ϵ2)n = \widetilde{\Omega}(d^2/\epsilon^2) samples. We thank the reviewer for pointing this out and we will discuss this.

We will add references for stability conditions.

Positioning of Theorem 4 (Q1). Both Theorem 4 and [1, Exercise 4.3] combine one-dimensional variance guarantees across directions and yield inefficient estimators. Theorem 4 needs more samples because it requires fourth-moment stability in all directions. Theorem 4 should be read not as an end-to-end algorithm but as a landscape result that motivates our tractable relaxation. Our broader goal is efficient robust covariance estimation by gradient descent on a simple objective, without semidefinite programming or iterative refinement. Nearly quadratic sample complexity is necessary for efficient SQ algorithms [2], which motivates our focus on the d2d^2 sample regime.

Frobenius guarantee (Q2). Yes. Under the lifted covariance stability of [1, Definition 4.5], the certificate Frel(w,k)≤0F_{\mathrm{rel}}(w,k) \le 0 implies ∥Σ−1/2ΣwΣ−1/2−I∥F≤O(ϵlog⁡(1/ϵ)).\Vert \Sigma^{-1/2}\Sigma_w\Sigma^{-1/2} - I \Vert_F \le O(\epsilon\log(1/\epsilon)). The certificate gives Var⁡w(X⊤UX)≤(k−1)tr⁡(UΣwUΣw)\operatorname{Var}_w(X^\top UX) \le (k-1) \operatorname{tr}(U \Sigma_w U \Sigma_w) for every symmetric UU, and the bound then follows from [1, Proposition 4.7 and Eq. (4.4)], as the reviewer suggests. We thank the reviewer for pointing this out and we will clarify this.

Corruption range and kk (Q3). Our proofs require ϵ\epsilon below a small absolute constant which we did not optimize. Our experiments test larger ϵ\epsilon to evaluate our method beyond the scope of our analysis. Regarding kk, starting at k=6k = 6 is only a warm start, and the final kk in our synthetic experiments is between 3.13.1 and 3.53.5. Empirically this schedule can give smaller error than using a fixed kk (for example, error 0.0540.054 versus 0.0940.094 at k=3.5k = 3.5, under inverse-spectrum corruption with ϵ=0.1\epsilon = 0.1, d=10d = 10, n=105n = 10^5).

[1] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press. 2023.

[2] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. Foundations of Computer Science (FOCS). 2017.

Thank you for the rebuttal. It clarifies the positioning of Theorem 4 and confirms that Frel≤0F_{\rm rel}\le 0 gives a Frobenius bound via the filter analysis in Diakonikolas and Kane. My main concerns remain. There is no formal guarantee that PGD reaches Frel≤0F_{\rm rel}\le 0. As a guarantee for an NP-hard objective, Theorem 4 needs more samples than known estimators. I prefer to retain my initial score.

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

This paper studies robust covariance estimation for high-dimensional Gaussian distributions under adversarial sample corruption. The authors propose a nonconvex objective based on second and fourth moments and prove that its approximate first-order stationary points yield accurate covariance estimates. They also develop a tractable spectral relaxation and a projected gradient algorithm, demonstrating competitive empirical performance on synthetic and semi-synthetic datasets.

Critical strengths
  1. The main theoretical contribution is the landscape guarantee showing that every approximate first-order stationary point of the proposed objective gives an accurate covariance estimate. This offers a new perspective on robust covariance estimation.
  2. The proposed objective has a simple and interesting motivation based on Gaussian moment identities. The numerical experiments also show that the resulting algorithm performs comparably to existing methods across different corruption settings.
Critical weaknesses
  1. The main landscape guarantee applies only to the original nonconvex objective, which is computationally intractable. For the proposed tractable relaxation, the authors do not establish a similar guarantee or prove that the algorithm converges to an accurate solution. This leaves a significant gap between the theoretical results and the proposed algorithm.

  2. The sample complexity of O~(d2/ε+d/ε2)\widetilde{O}(d^2/\varepsilon+d/\varepsilon^2) seems relatively high, especially since the result only guarantees spectral norm accuracy. It would be helpful to clarify whether this dependence is necessary or mainly arises from the uniform fourth-moment concentration argument.

Questions for authors
  1. On page 1, could the authors briefly explain what is meant by “depth-based covariance estimators” and how they differ from the methods considered in this paper?
  2. Theorem 4 requires Ω~(d2/ε+d/ε2)\widetilde{\Omega}(d^2/\varepsilon+d/\varepsilon^2)samples. Could this dependence on dd be improved or replaced by an intrinsic quantity associated with Σ\Sigma, such as its effective rank? What is the main bottleneck in the current analysis?
  3. The landscape guarantee is established for the original objective FF, but the proposed algorithm optimizes its relaxation FrelF_{\mathrm{rel}}. Is it possible to establish a similar guarantee for the relaxed objective, or at least show that the proposed algorithm converges to a solution with Frel(w)≤0F_{\mathrm{rel}}(w)\leq 0?
2 comments

We thank the reviewer for the thoughtful feedback and for recognizing the value of the new landscape perspective.

Additive guarantee for FrelF_{\mathrm{rel}}. For the same relaxed objective FrelF_{\mathrm{rel}}, we have an additive landscape guarantee, which we omitted from the submitted version to focus on multiplicative error. Under the stability condition of [3, Definition 4.5], every sufficiently accurate approximate stationary point of FrelF_{\mathrm{rel}} satisfies ∥Σw−Σ∥F≤O(ϵlog⁡(1/ϵ))∥Σ∥2.\Vert \Sigma_w - \Sigma \Vert_F \le O(\epsilon\log(1/\epsilon)) \Vert \Sigma \Vert_2.

Relaxed objective (Q3). Our Corollary 1 shows that any ww satisfying Frel(w,k)≤0F_{\mathrm{rel}}(w,k) \le 0 yields a multiplicative approximation of the true covariance Σ\Sigma. We do not establish that the proposed algorithm always reaches this condition. Empirically, all runs in our synthetic Gaussian experiments returned weights satisfying Frel(w,k)<0F_{\mathrm{rel}}(w,k) < 0, with kk between 3.13.1 and 3.53.5. We will clarify this.

Sample complexity (Q2). The d2d^2 dependence is supported by computational lower bounds: Diakonikolas, Kane, and Stewart [1] establish a nearly quadratic statistical query lower bound even for constant-factor multiplicative covariance estimation.

Small effective rank does not remove this barrier. The hard covariance CC in [1] can be embedded as Σ=diag⁡(1,C/d)\Sigma = \operatorname{diag}(1,C/d), whose effective rank is O(1)O(1). A multiplicative approximation of Σ\Sigma still recovers CC to the same relative accuracy.

Depth-based estimators (Q1). Depth-based covariance estimators generalize Tukey's median to covariance matrices. For example, [2] fits a matrix AA so that the squared projections (v⊤Xi)2(v^\top X_i)^2 are as evenly split above and below v⊤Avv^\top A v as possible in the worst direction vv. No polynomial-time algorithm is known for computing this estimator in general dimensions. In contrast, all methods in our experiments run in polynomial time. We will clarify this.

[1] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. Foundations of Computer Science (FOCS). 2017.

[2] M. Chen, C. Gao, and Z. Ren. Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model. The Annals of Statistics. 2018.

[3] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press. 2023.

I appreciate the authors’ response and their careful answers to my questions. I have increased the soundness scores. However, I still believe my initial overall rating reflects my assessment of the paper, and therefore I would like to keep it.

Reviewer_RskPOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper revolves around covariance estimation from Gaussian samples of which a bounded fraction can be adversarially perturbed (Definition 1). In parituclar, it studies the optimizaion of sample weights that are used to de-emphasize potentially correupted data poitns. A main theoretic contribution are sufficient conditions such that first-order methods deliver good choices for the sample weights. These sample weights are then, in turn, used to compute estimates for the covariance matrix. Numerical experiments on synthetic data and on genomic datasets study the usefulness of the proposed methods.

Critical strengths
  • interesting analysis for a highly relevant model for cyber security.

  • the studied methods seem attractive for practical deployment.

Critical weaknesses
  • I could not tell from the paper which of its parts is the main contribution: the objective, the landscape theorem, the relaxation, the algorithm, or the experiments. Theorem 4 concerns the exact objective F, while Algorithm 1 runs on the relaxation, and the experiments are somewhat inconclusive. A clear statement would help the reader weigh the paper.

  • The relation between the analysed objective and the algorithm that is run deserves to be spelled out. I could not find a stationary-point or convergence statement for the relaxed objective, nor a report of how often Algorithm 1 terminates with a non-positive certificate.

  • The numerical experiments secsion does not refer back to the theoretical results (Thms); the reported metric (Frobenius) differs from the one the theorems bound (multiplicative spectral), and n is chosen for a reason unrelated to Lemma 1.

  • The synthetic experiments seem to study the "easy" or high-SNR regime.

  • I also could not find a classical baseline such as a trimmed covariance estimator (generalizing the trimmed mean estimator which is attractive for estimating the expectation of a distribution in the strong contamination setting).

  • I found it hard to keep track of which expectations are taken with respect to the Gaussian and which with respect to a weighted empirical distribution. Plain E[.] seems to denote expectations w.r.t some underlying prob. dist.? while E_w[.] denotes weighted averages over some dataset also over the clean set G*, with weights often supported on the subset G.

  • Definition 2 is given without a reference. is this notion of stability new, i.e., an original contribution? it not, pls refer to the relevant literature which introduced this notion.

Questions for authors

see Weaknesses.

2 comments

We thank the reviewer for the thoughtful feedback on our work.

Main contribution. Our main contribution is a simple nonconvex formulation and its landscape analysis. The practical method runs projected gradient descent directly on sample weights, handling all directions through eigenvalue computations without repeated reductions to other specialized robust-estimation subroutines. We will highlight this contribution more clearly.

Additive guarantee for FrelF_{\mathrm{rel}}. For the same relaxed objective FrelF_{\mathrm{rel}}, we have an additive landscape guarantee, which we omitted from the submitted version to focus on multiplicative error. Under the stability condition of [2, Definition 4.5], every sufficiently accurate approximate stationary point of FrelF_{\mathrm{rel}} satisfies ∥Σw−Σ∥F≤O(ϵlog⁡(1/ϵ))∥Σ∥2.\Vert \Sigma_w - \Sigma \Vert_F \le O(\epsilon\log(1/\epsilon)) \Vert \Sigma \Vert_2.

Relaxed objective. Our Corollary 1 shows that any ww satisfying Frel(w,k)≤0F_{\mathrm{rel}}(w,k) \le 0 yields a multiplicative approximation of the true covariance Σ\Sigma. We do not establish that the proposed algorithm always reaches this condition. Empirically, all runs in our synthetic Gaussian experiments returned weights satisfying Frel(w,k)<0F_{\mathrm{rel}}(w,k) < 0, with kk between 3.13.1 and 3.53.5. We will clarify this.

Experimental comparison. The experiments evaluate the practical performance of our method against existing estimators. We use multiplicative Frobenius error because these methods target this stronger metric, and choose the sample size to keep clean sampling error comparable across dimensions. To support a fair comparison, we checked the publicly available baseline implementations and corrected several implementation issues, as detailed in Appendix E.1. We will release the revised implementations together with our code.

Expectation notation. Your interpretation of the expectation notation is correct.

Stability conditions. Stability conditions of this kind were introduced in [1]. We will add references accordingly.

[1] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust Estimators in High Dimensions without the Computational Intractability. Foundations of Computer Science (FOCS). 2016.

[2] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press. 2023.

Thank you for the response. The stated main contribution and the additive landscape guarantee for F_rel answer my first two concerns, provided the guarantee and its proof appear in the paper.

My experimental concerns are still standing:

  • focus of "easy" or high-SNR regime, n of order d^2/eps^2 (see author reply to Reviewer Y1uY),

  • runtimes and a trimmed baseline are still missing.

I keep my rating of 3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.