Summary
The authors propose and analyze a variable metric projected gradient method for a variant of the graphical Lasso problem where the off-diagonal elements are additionally constraint to be non-positive, and in which specific entries of the precision matrix are known to be zero.
The proposed metric which is used to precondition the gradients comes from the curvature of the function $X \mapsto -\operatorname{log det}(X)$ , which is part of the objective, and thus incorporates second-order information of the objective function, unlike more standard approaches for the problem.
The authors put their result in the context of the recent literature, and show in numerical experiments on covariances created from multivariate Gaussian whose precision matrix sparsity comes from a Barabási-Albert random graph that the proposed method outperforms other methods used to optimize the same objective function, such as block coordinate descent or the proximal point algorithm in terms of clock-time convergence speed.
From a theoretical point of view, the authors show that the proposed algorithm indeed converges to the unique minimizer of the (convex) objective, that the proposed stepsize rule indeed works, and that the algorithm identifies the true support in a finite number of iterations under an additional reasonable assumption on the minimizer.
Strengths
I consider the proposed efficient estimator for the sparse precision matrix with off-diagonal non-negativity constraint of interest for the machine learning community due to wide potential applicability of the setting to engineering problems.
The specific gradient preconditioning through the weighted metric induced by the second derivatives of the $\ell_2$-error is original for the problem, and the computational advantages compared to state-of-the-art methods are well explained ($O(p^3)$ time complexity) and showcased in sufficiently timing experiments. The choice of the comparison methods is adequate and the experimental setups are informative.
The paper is clearly and well written. A strength of the paper is the suitable co-design that heavily takes into account the problem structure, which makes the Hessian approximation used in the variable metric preconditioning simple enough to compute in a reasonable amount of time, while at the same time delivering a benefit in per-iteration improvement.
Weaknesses
While the problem as formulated in (1) is convex as stated, the underlying estimator pipeline is somewhat inherently non-convex due to the fact that the $\lambda_{ij}$ correspond to weights of a reweighted $\ell_1$-term whose weights are chosen based on the MLE. This detail could be mentioned more prominently in the paper.
From a computational point of view, the line search method deployed has the computational disadvantage that a lot of function evaluations, which might be expensive due to their need for spectral decompositions, might be needed to make the method work.
It remains unclear whether the convergence rate result Theorem 4.5 is optimal. Due to the incorporation of second-order information, a discussion of why superlinear convergence cannot be shown or observed would be further informative.
Questions
- When discussing the positive definiteness constraint in line 112, you mention that it is not closed and furthermore, cannot be managed by a projection. However, by looking at (1), it seems that due to the objective, it is clear that the minimizer will not be singular due to the existence of the term $- \operatorname{log det}(X)$ in the minimization: If at least one of the eigenvalues of X is 0, $\operatorname{log det}(X)$ is finite. Lemma B.1 touches upon this, but couldn't the positive definiteness constraint be relaxed to a psd constraint?
- In the considered model (1), the role of the disconnectivity constraint remains slightly unclear. Appendix A.1. and also the discussion of the financial time series example leaves the impression that the disconnectivity set is found by a similar method as the weights of the $\ell_1$-term $\lambda_{ij}$. Can you make the distinction clearer?
- In Theorem 4.2, it will be convenient if one the authors can refer definition equation for $L_f$.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The this discussion of limitations is adequate in general. However, it would have been beneficial if the "hidden - $\lambda$-dependence" on the sparsity of the estimated covariance matrix had been explained better in the paper.