acceptodds
Under review as a conference paper at ICLR 2027

Covariance Estimation with Piecewise-Smooth Regularization

Abstract

Covariance estimation for ordered variables is often built on a global regularity assumption, yet many covariance surfaces are only locally smooth: dependence evolves gradually within regimes and changes slope at a small number of locations. This paper addresses the estimation of such piecewise-smooth covariance matrices under a positive semidefinite constraint. We formulate this structure as sparsity of masked second divided differences, where the mask leaves the central variance coordinate of each stencil unpenalized, preserving near-diagonal dependence while allowing marginal variances to vary freely. The estimator combines a Frobenius data-fidelity term with a folded-concave penalty, and we develop an efficient ADMM-based algorithm that provably converges to a first-order stationary point. Under sub-Gaussian sampling, we further establish a finite-sample oracle inequality showing that the error decomposes into the oracle approximation error and a selection cost of order per unknown slope change. Simulations and an electricity-load forecasting task confirm that the method captures local slope changes that global smoothness models miss.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Covariance matrix estimation, trend filtering, Oracle inequality

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_URUcOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes an estimator for covariance matrices that admits a piecewise smooth structure. The main idea is to regularize this smoothness by penalizing the so-called masked second divided differences via a folded-concave penalty. The optimization problem is solved using the ADMM algorithm, and both theory and simulations are presented to illustrate the properties of the estimator. While this is a well-executed work that leverages existing approaches from the literature, the particular combination brings limited advantage, which is a major shortcoming of the work.

Critical strengths

This is a nicely implemented approach that builds on a well-known line of work in the relevant area. All the important components of the approach are already established in the literature, so the paper reads coherently. I did not read the proofs carefully, but I believe most of the claims are similar to those already present in the literature.

Critical weaknesses
  1. Limited novelty and no demonstrated added value. The paper combines well-established ingredients such as covariance regularization, masked second divided differences, the folded-concave penalty, and ADMM, but does not go beyond this combination to show what it uniquely contributes. There is no ablation or comparison against the individual components, so it remains unclear why this particular combination is necessary or preferable to existing alternatives.

  2. Incomplete numerical work and inherited theory. The data analysis reads as incomplete, with insufficient baselines and no isolation of each modeling choice, making the method appear to win by assertion rather than evidence. Similarly, the theoretical results appear to follow closely from existing literature, without clearly identifying which claims are genuinely new or how the theory addresses the specific challenges of the proposed structure.

Questions for authors
  1. Is there a specific regime, application, or data setting where the combination of the folded-concave penalty with masked second divided differences provably outperforms the individual components—and if so, can the authors point to it directly?

  2. What is the strongest evidence in the paper that this combination is necessary rather than incidental, i.e., that a simpler alternative would fail?

  3. If the novelty is not in the components but in the combination, what is the precise problem for which this combination is the right tool, and why do existing combinations not solve it?

  4. How do you ensure the positive definiteness of the resulting estimator which is a covariance matrix?

5 comments
AuthorsOpenReview ↗

Response to Reviewer URuC

On W1: Limited novelty and no demonstrated added value

We thank the reviewer for raising this important concern. We understand the reviewer’s desire for a clearer statement of novelty and for validation of the necessity of each component.

Specifically:

  1. The novelty lies not in “using these ingredients,” but in identifying and resolving a key obstacle. Covariance estimation cannot be directly handled by scalar trend filtering or graph trend filtering, because the target must be a symmetric PSD matrix. Symmetry couples the difference operators along the row and column directions: applying a difference penalty to a row simultaneously modifies Σij\Sigma_{ij}, and through Σij=Σji\Sigma_{ij}=\Sigma_{ji} directly perturbs the structure of column jj. If rows and columns are penalized separately, the same linear forms are penalized twice. The masked second-order divided difference operator proposed in this paper is designed precisely to address this coupling. By masking out the central variance Σcc\Sigma_{cc}, it preserves near-diagonal dependence information while allowing marginal variances to adapt freely to heteroscedastic or nonsmooth variations. This is not a direct combination of existing operators, but a dedicated construction tailored to the structure of the covariance surface.

  2. The combination of the folded-concave penalty and the PSD constraint is also not cosmetic. The nonconvex penalty reduces shrinkage bias on genuine large slope changes, while the PSD/strict-PD constraint ensures that the estimate is invertible and therefore applicable to downstream tasks requiring the inverse covariance matrix. The ADMM algorithm, its convergence analysis, and the oracle inequality based on the slope-change support are all nontrivial results developed around this nonconvex, PSD-constrained, symmetry-coupled problem.

  3. Experimental evidence of added value. We have compared our method with SCM, SRCov, LRCov, and CholCov in Table 1. On the full-rank lag family, our method outperforms the competing methods at p=50,100,200p=50,100,200; for example, at p=200p=200, the relative Frobenius error is 0.3261, compared with 0.3832/0.4335/0.4239 for SRCov/LRCov/CholCov. On the low-rank family, our method is competitive with low-rank estimators, which is consistent with the expectation that this family naturally favors low-rank covariance estimators. The held-out NLL and roughness results in the appendix further support the ability of our method to recover the piecewise-smooth structure. On the theoretical side, we establish finite-sample error bounds with a support-dependent calibration that adapts to the oracle support.

  4. Regarding ablation. We agree that component ablations would further strengthen the argument. The current manuscript focuses on comparison with existing complete methods and on theoretically characterizing the roles of the masked operator and the folded-concave penalty. The following table reports the related ablation

Table: relative Frobenius error at p=50p=50 over ten paired draws.

Setting (p=50p=50)α\alphamasked MCPmasked ℓ1\ell_1unmasked MCPunmasked ℓ1\ell_1SCMReading
(a) lag, n=100n=100160.22890.22890.23300.23310.3015neither
(b) block ρ=0.6\rho=0.6, n=100n=10010.29440.29700.30320.30620.3592mask −2.9-2.9%, penalty −0.9-0.9%
(c) block ρ=0.6\rho=0.6, n=400n=4000.50.14820.15290.15150.15850.1842mask −2.2-2.2%, penalty −3.1-3.1%
(d) block ρ=0.6\rho=0.6, n=1600n=16000.250.07180.07620.07150.08110.0912mask +0.4+0.4%, penalty −5.8-5.8%
(e) block ρ=0.3\rho=0.3, n=100n=10010.35520.35970.38820.40310.5392mask −8.5-8.5%, penalty −1.3-1.3%
(f) block+hetero, n=100n=10010.26140.26270.26720.26950.3055both

Therefore, we respectfully disagree with the assessment that the paper has “limited novelty and no demonstrated added value.” We believe that the paper makes clear incremental contributions in problem modeling, operator design, nonconvex PSD optimization, statistical theory, and experiments. We will further strengthen the statement of contributions in the revision and add the ablation experiments suggested by the reviewer.

On W2: Incomplete numerical work and inherited theory.

We thank the reviewer for pointing out these two concerns. We understand the reviewer’s desire to see more complete numerical evidence and a clearer boundary of theoretical novelty.

On the numerical work and baselines. The current manuscript does not compare against only a single baseline. In Table 1, we compare SCM, SRCov, LRCov, and CholCov, covering p∈{50,100,200}p\in\{50,100,200\}, two covariance families (full-rank lag and low-rank piecewise-linear), and 100 Monte Carlo simulations. On the full-rank lag family, our method outperforms the competing methods at all dimensions. The appendix also reports held-out NLL and roughness, which show that our method not only reduces the Frobenius error but also better recovers the piecewise-smooth structure. The real electricity-load experiment also provides out-of-sample predictive evidence. Therefore, “insufficient baselines” is not accurate.

As for “no isolation of each modeling choice,” we agree that component ablations would further strengthen the argument. We note that the core contribution of this paper is the piecewise-smooth modeling and statistical guarantee for symmetric PSD covariance matrices, rather than the isolated effect of individual components; the ablations will serve as supplementary evidence to further demonstrate the necessity of each modeling choice, but will not change the positioning of our contributions.

On the theoretical results. We disagree with the judgment that “theory appears to follow closely from existing literature.” The theoretical object of this paper is a nonconvex, PSD-constrained covariance estimation problem with row-column difference coupling, and existing theorems for scalar trend filtering or graph trend filtering cannot be directly applied. Specifically:

  1. We construct a masked second-order divided difference operator LL, whose mask excludes the central variance Σcc\Sigma_{cc}, thereby avoiding duplicate row/column penalization on the space of symmetric matrices while preserving near-diagonal dependence information. The corresponding oracle subspace, effective dimension K‾≤K+ν\overline{K}\leq K+\nu, and support-dependent Green scale $ g_{\mathcal{A}}=\max_{q\in\mathcal{P}\setminus\mathcal{A}}\left|L_{\mathcal{P}\setminus\mathcal{A}}^{+}e_q\right|_{\mathrm{F}} $ are all defined for this masked operator and are used to calibrate the dual noise on off-support coordinates. These quantities are not readily available in the existing covariance estimation literature.

  2. Under the nonconvex folded-concave penalty and the PSD constraint, we establish conditions for ADMM to converge to a first-order stationary point, including $ 0<\eta<1-\mu\kappa_K,\qquad \tau>2\mu+\frac{\mu^2\kappa_K}{\eta}, $ where μ\mu characterizes the weak concavity of the penalty and κK=∥L∥op2+1\kappa_K=\|L\|_{\mathrm{op}}^2+1. Because of the PSD normal cone and the symmetry coupling, this convergence analysis cannot be directly derived from existing scalar trend filtering results.

  3. We provide an oracle inequality and a finite-sample rate for a piecewise-linear covariance surface, $ \left|\hat{\Sigma}-\Sigma^{\star}\right|_{\mathrm{F}}^2 \lesssim \frac{\overline{K}+\log p+C_L^2\zeta^2K\log p}{n}, \qquad \overline{K}\leq K+\nu, $ which shows that the estimator adapts at a near-parametric rate to the unknown slope-change support, with each unknown slope change costing only log⁡pn\frac{\log p}{n}. The key to this result is the combination of the masked operator, the weak convexity of the nonconvex penalty, the PSD normal-cone condition, and the support-dependent Green scale, rather than transplanting existing theorems verbatim.

Q1. Is there a regime where the combination provably outperforms the components?

There is a regime we can name, explain and measure, though not one where we can prove dominance by theorem, and we do not claim that. It is ordered data with heterogeneous marginal scales: load curves, yield curves across maturities, spectral profiles.

The mechanism is an identity, not a heuristic. On a uniform grid of spacing hh, the unmasked stencil centred at cc contains the coordinate

$ (L_{\mathrm{unmasked}}\Sigma)_ {(c,c)}=\frac{1}{2h^2}\left(\Sigma_ {c,c-1}-2\sigma_ {cc}+\Sigma_ {c,c+1}\right), $

so the variance enters that coordinate with coefficient −1/h2-1/h^2, twice the weight of either neighbour and, under heteroscedasticity, the largest magnitude in the row. A penalty on that coordinate is therefore, to leading order, a penalty on the marginal variance itself. The larger the scale heterogeneity, the more of the curvature budget is spent flattening the scale profile rather than the dependence profile.

Q2. What is the strongest evidence that the combination is necessary rather than incidental?

We thank the reviewer for this question. We believe that the strongest evidence in the paper is not any single isolated experiment, but rather a converging chain of evidence formed by the theoretical guarantees in the target regime, experiments on data with the true structure, and the failure mechanisms of the individual components. Together, they show that this combination is not an incidental concatenation, but is necessary for the specific structure of “sparse slope changes on a symmetric PSD covariance surface.”

Specifically:First, the strongest theoretical evidence is that the oracle inequality and the piecewise-linear rate depend precisely on the key components of the combination. Corollary 5.4 gives $ |\hat{\Sigma}-\Sigma^{\star}|_ {\mathrm{F}}^2 \lesssim \frac{\overline{K}+\log p+C_L^2\zeta^2K\log p}{n}, \qquad \overline{K}\leq K+\nu, $ where K‾\overline{K} is the effective dimension of the oracle subspace induced by the masked operator LL, and the Green scale gAg_{\mathcal{A}} is also defined for the masked operator. If the mask is removed, the row and column differences double-penalize the same linear forms and smooth the central variance Σcc\Sigma_{cc}, so the above oracle subspace and noise calibration no longer hold. If MCP is replaced by ℓ1\ell_1, the proximal map $ \operatorname{prox}_ {\ell_1}(r)=\operatorname{sign}(r)(|r|-\lambda) _+ $ systematically shrinks every nonzero slope change by λ\lambda, whereas MCP is unbiased when ∣r∣>γλ|r|>\gamma\lambda. Therefore, in this regime, the simpler alternatives are not merely “possibly slightly worse”; rather, they respectively suffer from irreducible double-penalization bias, variance-smoothing bias, or large-kink shrinkage bias.

Second, the strongest experimental evidence is the full-rank lag family. The true covariance in this family is exactly piecewise linear in lag, which matches the structural assumption of this paper. In this regime, where the method’s assumption holds, Table 1 shows that our method outperforms SCM, SRCov, LRCov, and CholCov at p=50,100,200p=50,100,200; for example, at p=200p=200, the relative Frobenius error is 0.3261, compared with 0.3832/0.4335/0.4239 for SRCov/LRCov/CholCov. The held-out NLL and roughness results in the appendix further show that our method not only reduces the Frobenius error but also better recovers the piecewise-smooth structure. The numerical results of the real electricity-load experiment also provide out-of-sample NLL evidence. These results show that the gain of the combination appears in the regime where it should appear.

Third, the failure mechanisms of the components are explicit, not post hoc explanations. The unbiased interval of MCP directly eliminates the shrinkage of large kinks; the masked operator directly avoids row-column double penalization and preserves marginal variances; and the strict PD constraint directly guarantees that the estimate is invertible. Conversely, removing any component leads to an identifiable failure mode: ℓ1\ell_1 shrinks large kinks, the unmasked operator smooths variances and double-penalizes, and without the PSD constraint the estimate may be non-invertible.

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

This paper studies covariance matrix estimation for ordered variables under a piecewise-smooth structural assumption. Instead of imposing global smoothness or element-wise sparsity, the authors model local changes in covariance profiles through sparse second divided differences of the covariance surface. To preserve the positive semidefinite constraint and avoid over-penalizing marginal variances, the paper introduces a masked difference operator that excludes diagonal variance coordinates. The resulting estimator combines a Frobenius loss with a folded-concave penalty under a PSD constraint, and an ADMM algorithm is proposed to obtain a stationary solution. The authors further establish a finite-sample oracle inequality and evaluate the method on synthetic covariance models and an electricity-load forecasting task.

Critical strengths
  1. The paper identifies a meaningful structural regime not covered by standard covariance regularization methods. Many covariance estimators rely on either element-wise sparsity, global smoothness, or low-rank assumptions. The piecewise-smooth assumption is different and potentially useful for ordered data such as yield curves across maturities and daily electricity-load curves across time. The attempt to model local changes in dependence patterns rather than covariance magnitudes is a meaningful direction.
  2. The paper provides a technically substantial treatment of the proposed estimator. Extending sparse divided-difference regularization from vector-valued signals to covariance matrices is technically nontrivial because the estimator must preserve both symmetry and positive semidefinite structure. The authors develop a coherent optimization framework together with an ADMM-based algorithm and finite-sample statistical guarantees, including an oracle inequality that adapts to unknown slope-change locations.
Critical weaknesses
  1. Assumption 5.2 requires the operator norm of L to be bounded independently of p, but the second divided-difference operator depends on the spacing of the ordered grid. In particular, the paper uses t_i=(i-1)/(p-1) in its simulations, for which the coefficients of the operator scale with p. The authors should clarify whether Assumption 5.2 holds uniformly under this grid construction and, if not, how the theoretical guarantees depend on p.

  2. The paper proposes an ADMM-based algorithm but does not analyze its computational complexity. A complexity analysis would help clarify the computational efficiency and scalability of the proposed method.

  3. The empirical comparisons do not sufficiently isolate the contribution of the proposed regularization scheme. While the results show improvements over existing covariance estimators, it remains unclear whether the gains come from the masked second-order divided-difference structure or the choice of penalty. Comparisons with an unmasked second-order difference estimator and a masked operator using an \ell_1 penalty instead of MCP would help clarify the respective contributions of the proposed structure and the folded-concave penalty.

  4. The real-data experiment demonstrates improved predictive NLL, but provides limited insight into whether the estimated covariance structure exhibits the local slope changes targeted by the method. Visualizing the estimated covariance surface and its detected slope changes could help clarify what structural patterns the estimator captures beyond predictive performance.

Questions for authors
  1. Assumption 5.2 requires |L|_{\mathrm{op}}\leq C_L with (C_L) independent of (p). Does this assumption hold uniformly for the equally spaced grid t_i=(i-1)/(p-1) used in the simulations? If not, how do the theoretical guarantees depend on p?
  2. What is the computational complexity of the proposed ADMM algorithm? Can the authors provide an analysis of its computational cost to substantiate the claimed efficiency and scalability?
  3. How much of the empirical improvement can be attributed to the masked second-order divided-difference structure versus the MCP penalty? In particular, how does the proposed method compare with an unmasked second-order difference estimator and a version using an \ell_1 penalty with the same masked operator?
  4. Can the authors provide a visualization of the estimated covariance surface and the detected slope-change locations on the electricity-load dataset?
  5. In the synthetic experiments, the authors generate observations as x=z+e, where z\sim N(0,\Sigma^\star) and e\sim N(0,0.2I), but state that only x is observed. Since Cov(x)=\Sigma^\star+0.2I under independence, could the authors clarify whether the evaluation targets (\Sigma^\star) or the covariance of the observed data, and how the added noise is accounted for when computing the estimation errors?
  6. The manuscript contains several grammatical and typographical errors, including “from from” in the contribution summary, “Tabel 1” in Section 6.1, and “can obtained” in Section 4. Could the authors carefully proofread the manuscript and correct these errors?
3 comments
AuthorsOpenReview ↗

Response to Reviewer wMFT

Thanks for your valuable feedback.

W1 = Q1. Does Assumption 5.2 hold on the grid used in the simulations?

The submitted version conflated two normalizations. On the coordinate ti=(i−1)/(p−1)t_i=(i-1)/(p-1), every entry of LL is (p−1)2(p-1)^2 times its value on the unit-spaced index, so the operator norm there is (p−1)2(p-1)^2 times larger and Assumption 5.2 would fail. The revision removes the ambiguity. All operators act on the integer index grid, whose spacing is one, and tit_i is used only to define the covariance surfaces. Measured on that grid, in the normalization fixed in Sec. 5.1, CL=2C_L=2 holds for every grid we use. The submitted sentence was a description error, not a different experiment.

On the index grid the bound is elementary. With minimum spacing one, a three-point stencil has weights 1a(a+b)\frac{1}{a(a+b)}, −1ab-\frac{1}{ab}, and 1b(a+b)\frac{1}{b(a+b)} with a,b≥1a,b\ge1. Every row sum is 2ab≤2\frac{2}{ab}\le2, and every column sum is at most 2 as well. By the Schur test, ∥D∥2≤2\|D\|_ 2\le2. The map LL applies DD to the symmetric matrix and then keeps the masked entries. Masking is a contraction, so ∥L∥op≤2\|L\|_ {\mathrm{op}}\le2.

Power iteration gives ∥L∥op=1.99498,1.99787,1.99875,1.99863\|L\|_{\mathrm{op}}=1.99498,1.99787,1.99875,1.99863 and κK=4.980,4.992,4.995,4.995\kappa_K=4.980,4.992,4.995,4.995 at p=50,100,200,400p=50,100,200,400. Twelve random jittered grids and twelve clustered grids per size stay below 1.5971.597 (jitter at most 1.288,1.190,1.053,1.0451.288,1.190,1.053,1.045, clustered at most 1.023,1.527,1.440,1.5971.023,1.527,1.440,1.597 for p=50p=50 to 400400). The operator constant is a property of the coordinate normalization, not a fitted quantity.

This establishes clause (i) of Assumption 5.2, ∥L∥op≤CL\|L\|_ {\mathrm{op}}\le C_L. Clause (ii), gA≤Cgg_ {\mathcal{A}}\le C_ g, is a separate condition. It holds for the supports we simulate, a fixed number of knot rows, but we do not claim it for every support in the class (see our response to Gevp Q2). Accordingly, the statement in Sec. 6.1 that the guarantee is uniform in pp refers to the simulated support class.

W2 = Q2. Computational complexity

The revision adds Sec. 4.1. Each iteration requires one solve of ((1+α)I+τL⊤L)Σ=b((1+\alpha)I+\tau L^{\top}L)\Sigma=b and one p×pp\times p symmetric eigendecomposition. Because τ\tau is fixed within a run, the matrix is factorized once, and each later iteration is a triangular solve plus the eigendecomposition. Measured per-iteration times are 1.11.1, 3.03.0, and 11.011.0 ms at p=50,100,200p=50,100,200. The factor has nnz⁡(L⊤L)=10,875,44,250\operatorname{nnz}(L^{\top}L)=10{,}875,44{,}250, and 178,500178{,}500, about 8.7×dim⁡S(p)8.7\times\dim\mathbb{S}(p). Memory is O(p2)O(p^2), the same order as the p22\frac{p^2}{2} unknowns.

We are explicit that the iteration count, not the per-iteration cost, dominates total time. It ranges from a few dozen to a few thousand depending on λ\lambda. For p≫103p\gg10^3, the eigendecomposition can be replaced by a Lanczos partial decomposition.

W3 = Q3. Is the improvement due to the masked structure or to the penalty?

Neither alone: the two choices remove two different biases, and each is decisive only where its bias is large. The two are complementary, not substitutes. The following table reports six settings that move the two switches separately, with the gap each switch is worth.

Table: relative Frobenius error at p=50p=50 over ten paired draws.

Setting (p=50p=50)α\alphamasked MCPmasked ℓ1\ell_1unmasked MCPunmasked ℓ1\ell_1SCMReading
(a) lag, n=100n=100160.22890.22890.23300.23310.3015neither
(b) block ρ=0.6\rho=0.6, n=100n=10010.29440.29700.30320.30620.3592mask −2.9-2.9%, penalty −0.9-0.9%
(c) block ρ=0.6\rho=0.6, n=400n=4000.50.14820.15290.15150.15850.1842mask −2.2-2.2%, penalty −3.1-3.1%
(d) block ρ=0.6\rho=0.6, n=1600n=16000.250.07180.07620.07150.08110.0912mask +0.4+0.4%, penalty −5.8-5.8%
(e) block ρ=0.3\rho=0.3, n=100n=10010.35520.35970.38820.40310.5392mask −8.5-8.5%, penalty −1.3-1.3%
(f) block+hetero, n=100n=10010.26140.26270.26720.26950.3055both
  • Role of the penalty: It targets the bias on the large entries of LΣ⋆L\Sigma^{\star}. ℓ1\ell_1 subtracts λ\lambda from every surviving coordinate, so even a kink well above the threshold is moved; MCP stops shrinking above the threshold. Empirically, the advantage of MCP over ℓ1\ell_1 grows relative to the noise as the sample size increases, which is the signature of a bias.

  • Role of the mask: It excludes the diagonal coordinates from the penalized set, preventing the penalty from shrinking the marginal variances themselves. This bias originates mainly on the diagonal and is most visible under weak dependence and heteroscedasticity; the gain from the mask increases monotonically as dependence weakens. Under strong dependence or with a small λ\lambda, the mask has little effect.

W4 = Q4. Visualization of the estimated surface and of the detected slope changes

The revision adds the visualization of these two things in the manuscript( Figure 4). The figure shows, for the first electricity window, the fitted surface, the detected slope-change map, four covariance profiles along the day with the detected centres shaded, and the estimated against the held-out curvature.

Curvature is indexed by the pair (stencil centre, column), so a slope change is a region of the (c,j)(c,j)-plane rather than one number per time of day. In the electricity fit, the detected curvature concentrates on the near-diagonal band and on a few columns. The top decile of coordinates carries 6969% of the curvature mass, and the linear correlation between ∣LΣ^∣|L\hat{\Sigma}| and the held-out ∣LStest∣|LS_{\mathrm{test}}| is 0.780.78, so the map tracks structure that survives out of sample. The estimated magnitudes sit below the identity line, which is the shrinkage of the penalty.

Q5. The noise model, and what the error is measured against

What the experiments do. The reviewer's inference Cov⁡(x)=Σ⋆+0.2I\operatorname{Cov}(x)=\Sigma^{\star}+0.2I is correct for it. But he noise model e∼N(0,0.2I)e\sim\mathcal{N}(0,0.2I) is contamination used to additionally inflate the sample covariance matrix. In the field of smooth covariance estimation, this can make the surface of the sample covariance in the synthetic experiments rougher, as shown in subplot (b) of Figure 2 in the main text, thereby enabling a better comparison of the performance of different methods.

Why the conclusions do not change. Our relative Frobenius norm error is reported relative to ∥Σ⋆∥F\|\Sigma^{\star}\|_F. Using ∥Σ⋆+0.2I∥F\|\Sigma^{\star}+0.2I\|_F instead only increases the denominator and does not affect the ranking of the methods' performance.

Q6. Typographical errors

Thanks for you pointing out this issue. We have corrected these errors in the revised paper: "from from" →\to "from" (contribution (iii)), "Tabel 1" →\to "Table 1" (Sec. 6.1), "can obtained" →\to "can be obtained" (Sec. 4), "penatlies" →\to "penalties" (Sec. 3.2).

Thank you for the clarification. I have two further questions regarding the additional experiments and the response to Q5.

First, regarding the ablation results, they provide some evidence for the benefits of both design choices, but I have a question regarding the effect of the mask. In particular, in Setting (d), the masked MCP estimator (0.0718) performs slightly worse than its unmasked counterpart (0.0715), whereas masking improves the performance of the ℓ1\ell_1 estimator (0.0762 versus 0.0811). Could the authors explain this difference? Is the effect of masking dependent on the penalty type, the regularization strength, or the underlying marginal variance structure?

Second, I believe the response to Q5 does not fully address my concern.

The argument that replacing ∥Σ⋆∥F\|\Sigma^\star\|_F with ∥Σ⋆+0.2I∥F\|\Sigma^\star+0.2I\|_F only changes the denominator and therefore does not affect the ranking of the methods is incomplete. If the target covariance is changed from Σ⋆\Sigma^\star to Σ⋆+0.2I\Sigma^\star+0.2I, the numerator must also be changed accordingly. Specifically, the corresponding relative Frobenius error becomes $ \frac{ |\widehat\Sigma-(\Sigma^\star+0.2I)|_F }{ |\Sigma^\star+0.2I|_F }, $ which can lead to a different ranking across methods.

If the intended target is the latent covariance Σ⋆\Sigma^\star, it is important to clarify how the additional noise covariance 0.2I0.2I is accounted for in the estimation procedure. Since only x=z+ex=z+e is observed, the sample covariance of xx converges to Σ⋆+0.2I\Sigma^\star+0.2I, rather than Σ⋆\Sigma^\star. Do the authors explicitly correct for the noise covariance, for example, by using Sx−0.2IS_x-0.2I as the input to the estimation procedure, or employ another approach to recover the latent covariance? If so, please clarify the procedure and how the positive semidefinite constraint is handled after noise correction.

I therefore ask the authors to clarify which covariance matrix is actually targeted in their experiments and to provide a consistent evaluation. Specifically, either:

(i) If the target is Σ⋆\Sigma^\star, explain how the noise covariance 0.2I0.2I is accounted for in the estimation procedure; or

(ii) If no such correction is performed and the target is the covariance of the observed data, report the relative Frobenius errors using Σ⋆+0.2I\Sigma^\star+0.2I as the ground truth, and update the comparisons across all methods accordingly.

This clarification is important for interpreting the synthetic experimental results and determining whether the reported improvements reflect more accurate recovery of the intended covariance target.

Overall, I appreciate the improvements, but the methodological novelty remains somewhat incremental, and the above concern has not yet been fully resolved. I therefore maintain my current assessment.

Reviewer_GevpOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper estimates a psd covariance matrix for variables on an ordered grid, assuming each row of the covariance surface is piecewise linear with few kinks. Kinks are encoded as sparsity of a masked second divided-difference operator. The proposed estimator minimizes a Frobenius fit to the sample covariance plus an MCP penalty. It is solved by ADMM with a closed-form MCP prox and an eigenvalue projection. Theorem 4.1 provides conditions that guarantee convergence to a stationary point. Numerical experiments compare the proposed method against existing methods on synthetic data as well as on a power grid dataset.

Critical strengths

Authors study an interesting structural assumption on the covariance structure of stochastic processes.

Critical weaknesses
  • the relevant of the proposed theoertical analysis is unclear. do the error bounds certify that the proposed method is optimal of "efficient" in a precise sense (e.g. attaining a minimax lower bound for the error level)?

  • the interpreation of numerical experiments against the theoretical findings should be expanded. to the results confirm/contradict the upper bounds. are the assumptions of the theorems guaranteed to hold in the experiments?

Questions for authors
  • Could Sec. 6 report ||L||_op and kappa_K at p = 50, 100, 200, and state whether tau > 2mu + mu^2 kappa_K/eta, (3/2)muC_L^2 < 1 and lambda >= Czetasqrt(2 log p / n) hold there at gamma = 10, tau = 1?

  • Can g_A be bounded, or reported numerically on the grid used? Could the Corollary 5.4 rate be stated explicitly in p and compared with p^2/n?

  • does any claim in the paper require the nonconvex regime? If both theorems imply strong convexity (W1), could you say what Theorem 4.1 adds over standard convex ADMM convergence, and in which regime the MCP is preferable to l1?

  • the term "Efficient" is used of the ADMM in Sec. 4 and in the conclusion. in which sense is your algorithm efficient? does it achieve optimal accuracy/compute tradeoffs? are these tradeoffs known?

  • below Eq. (2) the strict-PD variant is defined with delta >= 0, should this be delta > 0?

  • Corollary 5.4 predicts scaling in n, in K and in log p. In Sec. 6 p is the quantity varied, with n = 100 throughout and K fixed by construction in both families; a p-sweep alone cannot isolate log p, because ||L||_op and g_A move with p as well. could you add error against n at fixed p and K, and against K at fixed n and p?

  • if true knots are known by construction, precision/recall of recovered kink locations would make the link to the theory more direct

  • is there a matching minimax lower bound for {Sigma >= 0 : ||L*Sigma||_0 <= s}? Sec. 5.2 calls the rate "near-parametric";which seems an analogy to the known-support case rather than a statement of optimality, and a lower bound would also settle whether the C_L^2 zeta^2 factor of W2 is intrinsic to the class.

  • could "SCM" be spelled out at its first use in Sec. 6, "sample covariance matrix" appears in Secs. 1 and 3.1 and S is defined in Sec. 3.1, but I could not find the acronym

5 comments
AuthorsOpenReview ↗

Response to Reviewer Gevp

Thanks for your valuable feedback.

On W1 (is the analysis relevant if it does not certify optimality?). The bounds are oracle-adaptive, not optimal. Theorem 5.3 says the estimator is within constants of an oracle that knows the support A\mathcal{A}. Corollary 5.4 gives the rate K+log⁡p+CL2ζ2Klog⁡pn\frac{K + \log p + C_L^2\zeta^2K\log p}{n}. We do not prove a matching lower bound for the whole class. What we can add is the local bound in Q8: on the oracle subspace the minimax risk is du/nd_u/n, with no CLC_L, no ζ\zeta and no log⁡p\log p in it. That tells us where the logarithmic factor comes from. It is the price of not knowing A\mathcal{A}, not part of the estimation problem on the support.

On W2 (do the experiments confirm the bound?). Three answers, in Q1, Q6 and Q8. The constants of Thm. 4.1 hold with margin at every setting used. The nn-sweep follows the bias-plus-variance form the bound predicts, with constants we do not optimise: at p=50p = 50, n=100n = 100 the estimate is within 1.34×1.34\times of the oracle projection risk, and the bound of Cor. 5.4 is looser than that.

Q1. Are the conditions satisfied at p=50,100,200p = 50, 100, 200?

Yes, at the settings of Sec. 6 (γ=10\gamma = 10, so μ=0.1\mu = 0.1, and τ=1\tau = 1). Measured on the index grid, in the normalization fixed in Sec. 5.1, the constants are as in the following table, hence 1−μκK≈0.501 - \mu\kappa_K \approx 0.50. τmin⁡=2μ+μ2κK/η\tau_{\min} = 2\mu + \mu^2\kappa_K/\eta increases as η\eta falls, so with τ=1\tau = 1 the condition holds once η>μ2κK/(1−2μ)≈0.06\eta > \mu^2\kappa_K/(1 - 2\mu) \approx 0.06. At η=0.25\eta = 0.25 it gives τmin⁡=0.40\tau_{\min} = 0.40, at η=0.1\eta = 0.1 it is 0.700.70, and τ=1\tau = 1 clears it. With CL=2C_L = 2, (3/2)μCL2=0.60<1(3/2)\mu C_L^2 = 0.60 < 1.

CL=2C_L = 2 holds for every grid we use. On a grid with minimum spacing 1, a three-point stencil has weights 1a(a+b)\frac{1}{a(a+b)}, −1ab-\frac{1}{ab}, 1b(a+b)\frac{1}{b(a+b)} with a,b≥1a, b \ge 1, so each row sum is 2ab≤2\frac{2}{ab} \le 2 and each column sum is at most 2 as well. The Schur test then gives ∥D∥2≤2\|D\|_2 \le 2, and LL is DD restricted to symmetric matrices and to the masked rows. The measured norm approaches 2 from below and moves by less than 0.004 between p=50p = 50 and 400400.

**Table **: operator scale on the index grid. Uniform is one grid, and jittered and clustered report the worst of twelve random draws.

Gridp=50p=50p=100p=100p=200p=200p=400p=400
uniform, ∥L∥op\|L\|_{\mathrm{op}}1.9951.9981.9991.999
uniform, κK\kappa_K4.984.995.005.00
jittered, ∥L∥op\|L\|_{\mathrm{op}}1.2881.1901.0531.045
clustered, ∥L∥op\|L\|_{\mathrm{op}}1.0231.5271.4401.597

For the λ\lambda-condition, λ≥Cζ2log⁡p/n\lambda \ge C\zeta\sqrt{2\log p/n}, we cannot certify the inequality at a specific λ\lambda, because it involves ζ≥gA\zeta \ge g_{\mathcal{A}} and we do not know the size of gAg_{\mathcal{A}} (Q2). What we can show is that the estimate is insensitive to λ\lambda in the range the condition allows. At p=50p = 50, n=100n = 100, varying λ\lambda by a factor of 1616 around the threshold 2log⁡p/n=0.28\sqrt{2\log p/n} = 0.28 moves RelFro only between 0.2283 and 0.2397, with the minimum near four times the threshold, which is what cross-validation selects.

Q2. Can gAg_{\mathcal{A}} be bounded? What is the rate in pp?

Status of gAg_{\mathcal{A}}. The oracle inequality needs only a deterministic ζ≥gA\zeta \ge g_{\mathcal{A}}, and Cor. 5.4 absorbs ζ\zeta into a constant, which presupposes that gAg_{\mathcal{A}} is bounded independently of pp. gAg_{\mathcal{A}} is a property of LL on the complement of A\mathcal{A}, and for supports that place the free coordinates far from the penalized ones it grows with pp, so no single constant covers every A\mathcal{A}. For the supports we simulate, a fixed number of knot rows, gAg_{\mathcal{A}} is fixed by the grid and the mask, and the assumption holds. Whether it holds for every support in the class is a deterministic question about LL restricted to the complement of A\mathcal{A} that we have not settled.

Rate. Cor. 5.4 gives K+log⁡p+CL2ζ2Klog⁡pn\frac{K + \log p + C_L^2\zeta^2K\log p}{n}. Our supports grow linearly in pp, with K=580,1364,2740K=580,1364,2740 at p=50,100,200p = 50, 100, 200, i.e. K/pK/p between 11.611.6 and 13.713.7, so the rate is p+log⁡pn\frac{p+\log p}{n} against p2n\frac{p^2}{n} for an unstructured estimate: a factor pp in squared error, p\sqrt{p} in relative Frobenius error. Table 1 shows the pattern, with the ratio to SCM at 1.42, 1.50, 1.49 at p=50,100,200p = 50, 100, 200.

Q3. Is the nonconvex regime needed? What does Thm. 4.1 add?

What Thm. 4.1 adds. The nonconvexity is in the subproblem, not in the proof technique. The objective in (2) is not convex, since ρ\rho is folded-concave, and the ZZ-update is the proximal map of ρ∘L\rho\circ L. Standard two-block ADMM results assume a convex objective and do not cover this split. Thm. 4.1 gives a region, η<1−μκK\eta < 1-\mu\kappa_K and τ>2μ+μ2κK/η\tau > 2\mu+\mu^2\kappa_K/\eta, in which the iteration still converges to a stationary point, and it implies τ>μ\tau > \mu, which is what makes each ZZ-subproblem single-valued.

The convex penalty is the case μ=0\mu = 0 of our assumption. Assumption 3.2 asks for a folded-concave ρ\rho with weak-concavity modulus μ≥0\mu \ge 0. The ℓ1\ell_1 penalty, ρ(t)=λt\rho(t)=\lambda t, satisfies every clause with μ=0\mu=0, and is the γ→∞\gamma\to\infty limit of the MCP family. SCAD is another member of the same class. So the nonconvex setting is not an extra hypothesis on the data or on the estimator. It is the convex setting plus one nonnegative scalar. The constants of Sec. 5 specialize to the convex case at μ=0\mu=0: the factor 11−(3/2)μCL2\frac{1}{1-(3/2)\mu C_L^2} of Cor. 5.4 equals 11 at μ=0\mu=0 and 2.482.48 at γ=10\gamma=10, and γ>6\gamma>6 is the binding constraint the theory places on the concavity. The convex estimator is therefore always available inside the assumption class, and, with λ\lambda tuned per method, the nonconvex family, being a one-parameter extension of ℓ1\ell_1, has an error envelope no worse than that of its μ=0\mu=0 member. In this envelope sense ℓ1\ell_1 is the lower bound of the family. It is the case we fall back on when the data give no evidence of large slope changes.

What the extra shapes buy. The two proximal maps differ only above the threshold. For t>λt>\lambda (τ=1\tau=1), ℓ1\ell_1 sends tt to t−λt-\lambda, while MCP sends it to γ(t−λ)γ−1\frac{\gamma(t-\lambda)}{\gamma-1} up to γλ\gamma\lambda and to tt beyond. The two maps agree at t=λt=\lambda, and MCP becomes unbiased above γλ\gamma\lambda, where ℓ1\ell_1 keeps shrinking by λ\lambda. If LΣ⋆L\Sigma^{\star} has a few entries much larger than λ\lambda, which is the structure Assumption 3.1 postulates, ℓ1\ell_1 pays that bias on every one of them and MCP does not. If LΣ⋆L\Sigma^{\star} is dense and small, as on the lag family (max⁡∣LΣ⋆∣=0.067\max |L\Sigma^{\star}|=0.067, 23%23\% nonzeros), the selected threshold exceeds almost every entry, both maps zero the same coordinates, and the estimators coincide. That is why the ablation table reports 0.22890.2289 against 0.22890.2289: at the cross-validated λ\lambda (α≈16\alpha\approx16 to 3232) both penalties are in the all-zero regime.

Experiment. p=50p=50, n∈{100,1600}n\in\{100,1600\}, five paired draws per cell, λ=α⋅RMS(LS)\lambda=\alpha\cdot\mathrm{RMS}(LS) with α∈{0.5,1,2,4,8,16,32}\alpha\in\{0.5,1,2,4,8,16,32\}, refined to {0.0625,…,2}\{0.0625,\ldots,2\} for the block truth and to {64,128}\{64,128\} for the lag truth at n=100n=100 where the oracle fell on the grid edge. α\alpha is chosen per method by the smallest mean error over the draws (oracle α\alpha), with δfloor=0.05⋅tr(S)/p\delta_{\mathrm{floor}}=0.05\cdot\mathrm{tr}(S)/p, τ=1\tau=1, tol=2⋅10−3\mathrm{tol}=2\cdot10^{-3}. The block truth is Σij⋆=0.6⋅1{block(i)=block(j)}+0.4⋅1{i=j}\Sigma^{\star}_{ij}=0.6\cdot\mathbf 1\{\mathrm{block}(i)=\mathrm{block}(j)\}+0.4\cdot\mathbf 1\{i=j\} with five contiguous blocks of ten indices, for which ∣LΣ⋆∣|L\Sigma^{\star}| has 9.9%9.9\% nonzeros of size up to 0.50.5.

Table 1: relative Frobenius error, p=50p=50, oracle α\alpha per method, five paired draws.

Truthnnℓ1\ell_1MCP, γ=10\gamma=10MCP, γ=3\gamma=3
smooth lag1000.23960.23960.2396
smooth lag16000.07570.07550.0754
block, 5 blocks1000.28850.2857 (−1.0%-1.0\%)0.2821 (−2.2%-2.2\%)
block, 5 blocks16000.08220.0774 (−5.8%-5.8\%)0.0736 (−10.5%-10.5\%)

On the smooth family the three columns agree to 0.5% for n≤1600n\le1600. On the block truth MCP is better at every nn, and the gap grows with nn: 1.0%1.0\% at n=100n=100, 5.8%5.8\% at n=1600n=1600 for γ=10\gamma=10, and 2.2%2.2\% and 10.5%10.5\% at γ=3\gamma=3. It also grows with the number of large slope changes: with ten blocks of five indices the gap at n=1600n=1600 reaches 8.2%8.2\% (γ=10\gamma=10) and 14.5%14.5\% (γ=3\gamma=3). The gain is not an artefact of tuning each method separately. At the single α=0.5\alpha=0.5 the paired difference is −11.3%-11.3\% (t=9.3t=9.3) at n=1600n=1600 and −15.8%-15.8\% (t=9.7t=9.7) at n=6400n=6400 over the same five draws. A bias term that does not decay with nn, while the variance term does, produces exactly this pattern.

The nonconvex regime is what removes the residual shrinkage bias when the surface really is piecewise-linear with few large kinks, and on smooth surfaces it returns the ℓ1\ell_1 estimate, so the choice is not harmful there in practice.

Q4. In what sense is the algorithm efficient?

The formulation is hard. Three features of (2) rule out a generic solver. The penalty Pλ(LΣ)P_\lambda(L\Sigma) is folded-concave, so the objective is nonconvex and no convex solver applies. The constraint $\Sigma \in \mathbb{S}_ {+,\delta}(p) $ is a semidefinite constraint on p(p+1)2\frac{p(p+1)}{2} variables, 1,2751{,}275, 5,0505{,}050 and 20,10020{,}100 at p=50,100,200p = 50, 100, 200. And LL is a masked second-difference operator acting on the symmetric upper triangle, so the penalty couples entries and is not separable in Σ\Sigma. An interior-point method on vec⁡(Σ)\operatorname{vec}(\Sigma) would need a dense Newton system of order p(p+1)2\frac{p(p+1)}{2}, i.e. O(p6)O(p^6) work per iteration. At p=200p=200 the matrix alone has ≈4×108\approx4\times10^8 entries, and the method would still require PλP_\lambda to be smooth, which it is not.

Why ADMM. The splitting Σ=Z\Sigma=Z, Σ=V\Sigma=V assigns one difficulty to each update and leaves every update either closed-form or a fixed sparse solve. The Z-update is the proximal map of Pλ/τP_\lambda/\tau, coordinatewise and in closed form for ℓ1\ell_1, MCP and SCAD, so the nonconvexity costs nothing per iteration. The VV-update is the eigenvalue projection Qdiag⁡(max⁡{di,δ})Q⊤Q\operatorname{diag}(\max\{d_i,\delta\})Q^{\top}, so the semidefinite constraint and the eigenvalue floor are enforced exactly, with no relaxation and no inner solver. And the Σ\Sigma-update is one linear system, ((1+τ)I+τL⊤L)Σ=b((1+\tau)I+\tau L^{\top}L)\Sigma=b, whose matrix does not change across iterations. No update linearizes the penalty, relaxes the PSD constraint, or needs a step size. The two dual variables only enforce the two splits.

Cost per iteration. One sparse solve of ((1+τ)I+τL⊤L)Σ=b((1+\tau)I+\tau L^{\top}L)\Sigma=b and one p×pp\times p eigendecomposition. The matrix has nnz⁡(L⊤L)=10,875,44,250\operatorname{nnz}(L^{\top}L)=10{,}875,44{,}250 and 178,500178{,}500 at p=50,100,200p = 50, 100, 200, about 8.78.7 times dim⁡S(p)\dim\mathbb{S}(p), so it is sparse enough to factor once per run. Each later iteration is a triangular solve plus the eigendecomposition, measured at 1.11.1, 3.03.0 and 11.011.0 ms. Memory is O(p2)O(p^2). Total time is set by the iteration count, which we cannot bound a priori (tens to a few thousand depending on λ\lambda). In our runs it ranges from a few hundred to about two thousand, so one fit costs roughly 11 to 22 s at p=50p=50, 33 to 66 s at p=100p=100 and 1010 to 2525 s at p=200p=200. We do not claim an optimal accuracy/compute tradeoff. What the revision states is this structural guarantee: every subproblem is exact, and the cost of one iteration is fixed by pp and by the sparsity of LL.

Q5. Should the strict-PD condition read δ>0\delta>0?

It should. The revision changes Eq. (2) to δ>0\delta>0 for the strict-PD variant, with δ=0\delta=0 as the limiting case, and renames the cross-validated eigenvalue floor in Sec. 6 to δfloor\delta_{\mathrm{floor}}, since the two play different roles.

Q6. Sweeps in nn and in KK

(a) nn-sweep. p=50p=50, α=16\alpha=16, ten paired draws.

**Table **: relative Frobenius error against nn.

nn50100200400
Ours0.3350.2290.1730.137
SCM0.4500.3020.2150.155
Ratio (SCM / ours)1.341.321.241.13

Our error falls like 1/n1/\sqrt{n} up to n≈400n\approx400.

(b) KK-sweep. p=50p=50, n=100n=100, ten paired draws, with the number of slope changes varying.

**Table **: relative Frobenius error against the number of knots.

Knots012481216
Ours0.1620.1880.2020.2190.2270.2290.230
SCM0.1820.2160.2370.2630.2890.2980.303
Ratio (SCM / ours)1.131.151.171.201.271.301.32

The ratio grows with the number of knots, and the paired difference from −0.020-0.020 to −0.073-0.073 (s.e. at most 0.0050.005).

(c) We agree that a pp-sweep cannot isolate log⁡p\log p. In K+log⁡p+CL2ζ2Klog⁡pn\frac{K+\log p+C_L^2\zeta^2K\log p}{n} the log⁡p\log p term is dominated by KK once KK grows linearly in pp.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.