Schur's Positive-Definite Network: Deep Learning in the SPD cone with structure

Dear reviewer,

Thank you for your comments and interesting questions, we are happy that you enjoyed reading the paper. Here is our response:

1. Your intuition that the input features are chosen to best suit the model-based approach and to perform well with GD is correct, we have added more explanations in Section 4.2 (lines 311-314). Regarding the input features of $f$, their core motivation is to impose an inductive bias on models (as addressed in lines 269, 284-286) in the case of UBG and PNP. In the case of E2E, it was drawn from the intuition that the neural network should freely exploit the current state of the column in order to produce an appropriate update (lines 302-305). The input features for $g$ are design choices that were made by inspiration from the $\lambda$ estimator of GLAD [1], and that more importantly showed the best empirical performance. It is based on the intuition that the network should exploit information from the current state of the diagonal of $\Theta$, the diagonal of $S$ which is closely related to the diagonal of the GLasso estimator at convergence, and Schur’s complement which is added to the output of $g$.
2. The overall cost is of the order of $\mathcal{O}(p^3)$ complexity for a complete update, as you state. This cost is the same as an update of $\Theta$ for many other model based solvers, e.g. Graphical-ISTA or Graphical Lasso, and makes inference quite fast (less than 1 s, which is similar to solving one GLasso). As always with learning-based methods, the cost of training on many examples is more important, in the order of hours ; future directions involve making training faster.
3. Yes, structural sparsity could be enforced through $f$. Broadly speaking, any constraint related to the values of the off-diagonal entries, and that can be imposed on the outputs of a neural network, can be imposed with $f$. In the case of sparsity with prior known structure, where some predefined elements are strictly required to be non-zero, a straight-forward approach would be to discard the sparsity-enforcing operation on the appropriate entries. Alternatively, if the desired structure imposes predefined off-diagonal elements to be strictly equal to 0, these entries can be hard-coded to be so. Other non-trivial constraints such as structured sparsity with unknown prior structure could be tackled with neural networks that are designed to produce structured sparse outputs (e.g. in [2]).
4. We agree that this would be a very interesting application of SpodNet and definitely consider this as a potential future direction of research ! However, due to time constraints, it is difficult to design and implement relevant experiments in computer vision in this rebuttal period.

Refs:

[1]: GLAD: Learning Sparse Graph Recovery. Shrivastava et al., 2020.

[2]: Feature selection using a neural network with group lasso regularization. Zhang et al., 2020.

Dear reviewer,

Thank you for your comments and interesting questions, we are happy that you enjoyed reading the paper. Here is our response:

1. You are correct: GLAD-Z is not the projection of GLAD-$\Theta$, nor the other way around. GLAD-Z loses its sparsity if projected onto the SPD cone and additionally becomes singular (since it is actually projected onto the closed cone of semi-definite matrices), see the added Figure 10 (line 802). Going the other way around and trying to sparsify GLAD-$\Theta$ instead, by thresholding its off-diagonal entries, breaks its positive-definiteness guarantee [1]. To the best of our knowledge, there is no obvious way to modify GLAD or its predictions such that a single matrix guarantees both sparsity and positive-definiteness. We emphasize that GLAD-Z’s outperformance comes at the price of the arguably prohibitive sacrifice of the SPD guarantee, which makes its consideration as a valid precision matrix questionable.
2. We agree that SpodNet does not significantly outperform the baselines in the easy large-sample regimes ($n \gg p$, where all traditional methods already achieve excellent performance (down to 2% NMSE in the $p=20$ scenario)). However we emphasize that many real-world applications require methods that work well in limited-sample regimes ($n \approx p$ to $n < p$), which is the most difficult setting. This happens for instance in many time-series applications where signals are assumed to be strongly non-stationary, such as in dynamic connectivity estimation in neuroscience [2, 3, 4] or temporal financial networks [5, 6].
3. We have added the results of GLAD on the Animals dataset (see the updated Figure 6, line 512) and modified Section 5.2 accordingly.
4. We increased the sizes of Figures 4 and 5.
5. The models used in our experiments comprise one SpodNet layer, as addressed in Appendix A.2. We recall that a SpodNet layer updates all column-row pairs and diagonal elements of the input, thus performing much more than one single update. Since a single SpodNet layer is enough in our experiments to yield competitive performance against the baselines with all three of our models, we did not pursue architectural search with more unrolled layers. In line 363, the MSE therefore only involves the final $\Theta$ output.
6. This is an interesting fact indeed. First, notice that the MSE indeed goes down when $n$ increases. The F1 score does not improve because of the choice of $\lambda$ which is tuned by Cross Validation on the left out MSE score, as done by the standard scikit-learn’s GraphicalLassoCV solver that we used (7). It is well-known in the sparsity literature that the optimal regularization strength $\lambda$ in terms of MSE is usually lower than the optimal one for F1 score (see eg. in the Lasso case, Figure 1 in [8]). Since the F1 score cannot be computed in real life, practitioners resort to MSE on left-out data to tune $\lambda$. This may yield a suboptimal value in terms of support recovery performance.

Refs:

[1]: Functions preserving positive definiteness for sparse matrices. Guillot & Rajaratnam, 2015

[2]: Defining epileptogenic networks: contribution of SEEG and signal analysis. Bartolomei et al., 2017.

[3]: Brain functional and effective connectivity based on EEG recordings: a review. Cao et al., 2021.

[4]: Automatic detection of epileptic seizure events using the time-frequency features and machine learning. Zeng et al., 2021.

[5]: Non-Stationarity in financial time series and generic features. Schmitt et al., 2013.

[6]: The physics of financial networks. Bardoscia et al., 2021.

[8]: Beyond L1: Faster and Better Sparse Models with skglm. Bertrand et al., 2022.

Dear reviewer,

Thank you for your comments and interesting questions, we are happy that you enjoyed reading the paper. Here is our response:

• We have added a discussion on the current limitations of SpodNet in our conclusion (lines 525-528). Namely, we would like to improve our theoretical understanding of the eigenvalues’ dynamics during training, and make the training faster.
• We have increased the sizes of our figures.
• Eq. (3) stems from the Banachiewicz inversion formula (stated under its general form in Eq. (4)); to obtain Eq. (3) we namely identify $g(\Theta)$ with $\theta_{22} - \theta_{21} [\Theta_{11}]^{-1} \theta_{12}$. This has been clarified in the text (lines 195-196).
• We have added explanations on Eq. (5), the GLasso loss (lines 233-235). The data fidelity term is the negative log-likelihood under Gaussian assumption, while the penalty enforces sparsity of $\Theta$.
• The MSE is used only to train the data-driven models (SpodNet and GLAD). The GLasso estimator is obtained by solving Eq. (5) and its hyperparameter $\lambda$ tuned by cross-validation, using Scikit-Learn’s GraphicalLassoCV. Then the MSE is measured for the solution obtained by the GLasso.
• The SpodNet layer performs block-coordinate updates on the input matrix, each of which in $\mathcal{O}(p^2)$, resulting in an $\mathcal{O}(p^3)$ complexity for a complete update, as mentioned in the paper (line 200). This cost is the same as an update of $\Theta$ for many solvers, e.g. Graphical ISTA or Graphical Lasso, and makes inference quite fast (less than 1 s, which is similar to solving one GLasso). As always with learning-based methods, the cost of training on many examples is more important, in the order of hours ; future directions involve making training faster.
• Colors in Figure 1 are an illustrative choice. At a given iteration inside a SpodNet layer, a new column is predicted by a neural network. This new column is represented by a colored block. Colors were used to emphasize that each column is different, with no particular meaning behind each color choice. The green color only represents the input matrix.

I thank the authors for the response. They have answered my questions, and I am happy to maintain my positive rating.