Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a recovery guarantee for gradient-based optimization method applied to high-dimensional vector autoregressive (VAR) models. It considers both single-structured and superposition-structured transition matrix, and shows that the distance between the true parameter and the iterates generated by projected gradient descent (PGD) algorithm will decrease linearly to certain statistical error controlled by sample size and Gaussian width of the assumed structure. In the experiments, PGD is shown to outperform the baseline algorithm FNSL empirically.
main_review: Originality:

The result presented in this paper seems new in the literature, but there are several existing works that share something in common with this paper. For VAR models with general structures, [1] has analyzed the statistical error for regularized estimators using Gaussian width. For superposition structures, Gaussian-width-based analysis is available for linear models in [2]. The linear convergence of PGD has been established for general-structured linear models in [3]. Given these works, I feel that to some extent this paper is like a hybridization of them, and the linear convergence result here is not too surprising. Therefore I would not say that the paper has a lot of originality. 

Quality:

The technical quality of this paper is reasonably high, but not outstanding. To obtain the error bounds for PGD and AltPGD in Section 3 and 4, some effort seems to be required for dealing with the mathematical details, given that VAR models and superposition structures are relatively complicated. The paper also provides additional results on multitask learning and robust PCA. On the other hand, like the comments above for originality, the theoretical results proved in this paper seem to have similar flavor as what existing works have shown, so that the proof ideas can be borrowed in a relatively straightforward manner. By reading the proofs in the supplementary material, it looks to me that the line of attack is more or less standard. 

Clarity:

The presentation of this paper is generally clear, and the technical results are well-organized. For the experiments, one thing that is unclear from the description is how the constraint parameter is set for PGD. In both Eq. (3) and (4), the formulations use the information of the ground truth, which is unknown in practical applications. If the constraint parameter is set as suggested in (3) and (4) but the baseline method FNSL has no access to the ground truth, the comparison might be unfair. Could authors clarify on this?

Significance: 

Using PGD for estimating VAR models is straightforward from the algorithmic perspective, but the linear-convergence result established in the paper fills in the missing piece of statistical guarantees.

[1] I. Melnyk and A. Banerjee. Estimating Structured Vector Autoregressive Models. In International Conference on Machine Learning, pages 830–839, June 2016. 

[2] Q. Gu and A. Banerjee. High dimensional structured superposition models. In Advances in Neural Information Processing Systems, pages 3684-3692, 2016.

[3] S. Oymak, B. Recht, and M. Soltanolkotabi. Sharp time–data tradeoffs for linear inverse problems. IEEE Transactions on Information Theory, vol. 64, no. 6, pp. 4129–4158, 2018.

********************* Post-rebuttal comments *********************
I tend to agree with the author response on Lemma 4 and 5, and after reading other reviews and comments, I would like to increase my score to 7. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analyzes convergence of gradient descent algorithm for estimating the transition matrix under vector-autoregressive models under (i) high-dimensional regularization assumptions on the matrix and (ii) a sparse+low-rank kind of complementary regularization structure on the matrix. The results are more or less along expected lines with one technical difficulty to overcome in the proof (which is done in Lemma 5). 
main_review: 1) The model and the setup considered are general high-dimensional setup and superposition setup. However, I think it would also be good to also consider and discuss the case when there is no regularization (I.e., the low-dimensional setup). I suspect the Projection makes the iterates bounded which enables the analysis at several places. However, in the low-dimensional setup without any projection, the unboundedness of the iterates might cause issues for the analysis ? A discussion on this would be welcome. 

2) If we remove all the standard (i.e., by now well-known steps), the main contribution is in Lemma 5. It might be worth discussing this method in the main paper. 

3) Theorem 2 and Corollary 3 from [18] also provides optimization error. This should be discussed.  

4) Minor: the term 'sharp' is typically referred to the case when the constants also match some form of lower bounds. If upper and lower bound match up to constants, it is typically referred to as 'rate-optimal' 1

==========
Thanks for the response. I maintain my score.

To me the more interesting problem to consider is to analyze the dynamics of the algorithm in the 'real' high-dimensional setup (where the dimension and sample size go to infinity with their ratio being bounded and no structural assumptions), which might be more challenging. 

limitations_and_societal_impact: none (to this reviewers knowledge)
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of estimating the transition matrix of a lag-1 vector autoregressive model. The authors propose projected gradient descent as well as alternating projected gradient descent algorithms to learn both single- and supervision-structured transition matrices, respectively. Non-asymptotic analysis is also provided which shows the algorithms convergence linearly tp the statistical error in the high-dimensional settings.
main_review: The paper is well-written and the theoretical results look solid. The authors propose algorithms for learning a single-structured transition matrix as well as a transition matrix as the sum of two single-structured components. The theoretical analysis addresses the key challenge that data matrix has dependent rows, using the extreme eigenvalue bounds for the covariance matrix of Gaussian processes presented in S. Basu  et al. 2015. The authors prove sharp convergence guarantees for the proposed algorithms. Numerical results on S&P500 stock prices are provided to support the theoretical analysis.
limitations_and_societal_impact: - The paper focuses on the special case of VAR models of lag 1 with serially uncorrelated Gaussian errors.
- The propose methods assume that the transition matrix is single-structured or a sum of two single-structured components. This assumption could be restrictive for real data.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes projected gradient descent algorithms for estimating high-dimensional vector auto-regressive models, and conducts convergence analysis following the restricted strong convexity lens.  Specifically, sparse, low-rank and sparse plus low-rank models are of interest.  While many of these topics have been studied "to death", the novelty here seems to be (a) there's limited work in applying sparse plus low-rank approaches to time-series settings, where there is an additional constraint that the transition matrix has to lead to a stable dynamical system (b) Typical convergence analysis is done under iid setting, but for VAR models, samples are naturally dependent with strong auto-correlation.
main_review: Overall it's an interesting paper, but I'm having a difficult time judging its originality,  as each individual piece has been proposed and explored in numerous papers,  but the particular combination of ideas considered in this paper (using RSC arguments to analyze PGD methods for sparse+low-rank problem for the VAR setting and establishing linear convergence) appears to be new.   Many of the new tools + challenges of applying sparse + low-rank methods to VAR setting (e.g. use of spectral densities, e.t.c) have been addressed in earlier publications (e.g. [22]), analysis of non-iid data, and applications of RSC arguments, are also fairly well known, the authors provide a good overview in the intro.   So I'm not sure if the authors are filling-in a natural gap in a tensor of cross-products of various ideas,  or if there's indeed some key novelty in this paper.  Perhaps the authors can comment / highlight. 

The main limitations of the paper:   
1) There is a wealth of algorithms for solving high-dimensional sparse problems, and to my knowledge PGD methods are not  among the most competitive.  I would like the authors to comment on e.g. randomized block-coordinate descent methods, accelerated proximal methods, and all the other popular solvers (where most of these have been applied to sparse/group-sparse/sparse+low-rank, e.t.c problem settings).   Adding a projection (rescaling) to reduce spectral radius for VAR setting should be applicable to many of these. 
Baseline comparison is done with only one method, "FNSL",  which seems to be of accelerated proximal gradient type,  and where parameters are not chosen properly (so there's a typical oscillation pattern).   It'd be more convincing if there were other baselines. 

2) Evaluation on real data is very limited, and the analysis of 'financial data' is naive and misleading / wrong.  VAR model is build on log-prices,  which are non-stationary,  to make sense the paper should apply the analysis to log-returns.    Finding correlations isn't very interesting -- one can use a sample covariance matrix and clustering for that -- if you can comment on interesting lead-lag relationships that would be more interesting. 

Minor comments: 
1) It's unclear what is "connectivity measuring among financial firms",  and also it's unclear why radar/SAR signal processing would have a network structure -- is there perhaps a low-rank spatial structure? Please explain clearly. 
2) 'studied by numerous literatures' - awkward. 
3) Please take a look at references for some clean-up e.g. pca->PCA .. S&p -> S&P, e.t.c. , ref[40], ...


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This manuscript proposes two algorithms for estimation of transition matrices in single-structured as well as superposition-structured VAR models. Linear convergence to true parameters are verified under certain stability conditions, and additional assumptions on the data distribution, step size and minimum sample size. Some empirical results are reported to illustrate good performance of proposed algorithms in finite sample cases.
main_review: - On results of Theorem 1: The consistency rate appeared in equation 16 and then later on equation 18, seems to depend on the some norm of the covariance of error terms (It is not clear which norm is used since authors have not defined the notation in the manuscript). This norm may be related to the dimensions of the covariance matrix of error terms and might be at least of order d. This will impose an upper bound on d, at least of the form $d \leq n$ which makes it impossible for the results to hold in high-dimensional cases in which $d > n$. Further, if one includes the bound in equation 15, the consistency rate in equation 16 might include $\sqrt{d}$ which does not even vanish with the sample size. The authors are encouraged to elaborate further on the consistency rate in Theorem 1 (similarly in Theorem 2), specifically discuss under which combinations of n and d, the consistency rates would vanish in their theoretical results.


- Assumption 3 is a rather technical condition and hard to check given a specific superposition-structured VAR model. It would be appropriate for the authors to simplify this assumption at least for some specific superposition-structured cases such as the low rank plus sparse one. Moreover, it is not clear whether this assumption ensures the identifiability of transition matrices L and S. The identifiability issue is only mentioned in Remark 6, but not discussed further. This is a serious issue which should be addressed thoroughly, otherwise the interpretation of estimates of transition matrices would be impossible. There are results in the literature which could help verifying the identifiability in some specific cases, such as Theorem 1 in Hsu et. al. (2011) for the case of low rank plus sparse.



- The manuscript seems to be written hastily since there are some incomplete sentences and several mathematical notations which are either not defined at all or defined after the first time being used in the manuscript which might be confusing for readers. Some examples:

- Sentence seems to be incomplete: page 2, line 72, ``when the transition ..."

- Incomplete sentence on page 3, line 86: ``we require ..."

- cone(.) is not defined but used on page 4, line 108

- The set $S_F$ used in equation 15, page 4, but not defined before (Same for $S_2$ in equation 35 in the supplement).

- Which norm on the covariance of error terms does appear in equation 18? Is it the operator norm?

- The notation script P, i.e. $\mathcal{P}$ (projection) is used in equation 5 on page 3, but not defined before.






- Gaussianity seems to be a major assumption throughout the manuscript. This assumption is restrictive in applications. The authors need to discuss whether the results hold for some heavier tail distributions, and if not, describe the main theoretical bottlenecks.



- On the algorithms: (1) Is it possible/needed to select different step sizes for the superposition-structured case in equation 21? (2) How are the projections performed in both algorithms 1 and 2 for the low rank and sparse components? This needs to be added for completeness; (3) There is no discussion on how step sizes are selected/computed in numerical studies. Convergence in both algorithms might be sensitive to this hyperparameter as hinted by the theoretical results (there is a lower bound requirement for step size in all theoretical results in the manuscript). This issue should be addressed comprehensively.



- Real data: There is no comparison with competing methods such as the FNSL in the real data section, i.e. section 5.2 (similarly in the additional numerical results in section D in the supplement).

- It is not clear why the inequality in equation 18 holds, please elaborate.

Reference:

Hsu, D., Kakade, S. M., \& Zhang, T. (2011). Robust matrix decomposition with sparse corruptions. IEEE Transactions on Information Theory, 57(11), 7221-7234.
limitations_and_societal_impact: NA
review_title: null

Meta-review: Given that the authors have satisfactorily addressed the concerns of the reviewers, the consensus of the review committee is that the paper should be accepted for presentation at Neurips. I would like to ask the authors to read the paper carefully one more time and revise all the typos/missed notation definitions including the ones that are pointed out by the reviewers.


Decision: Accept (Poster)